天乾物燥,小心摳圖 —— A journey of matting

作者:Manstern

編輯:Origamidancen

Matting是計算機科學中一個很基本的問題,在matting的歷史中有不少人留下足跡,也產生了不少好的工作,這些工作反映了機器學習乃至計算機科學中很本質的一些概念。n

近年來,深度學習很火,其中非常重要的一類工作就是圖像分割(Segmentation)。圖像分割就是將圖片中的像素分成多個類別,如果是前背景分割,那麼就是分成兩個類別,一個類別代表前景,一個類別代表背景,這類問題我們也稱之為硬分割(Hard Segmentation)。n

Matting也是一類前背景分割問題,但是matting不是硬分割,而是軟分割(Soft Segmentation),像玻璃、頭髮這類前景,對應像素點的顏色不只是由前景本身的顏色決定,而是前背景顏色融合的結果,matting問題的目標就是,找出前背景顏色,以及它們之間的融合程度。n

Blue Screen Mattingn

這篇SIGGRAPH文章的作者是Alvy Ray Smith和James F. Blinn,如果按修真的設定,這就是開宗立派的祖師爺了,這篇文章正式定義了matting問題。n

James F. Blinn原來在JPL工作,對,就是《火星救援》里,把馬特達蒙從火星救回來的的那個JPL。n

Alvy Ray Smith是圖形學的先驅,他的職業生涯十分傳奇,最開始在施樂做繪圖程序,當然後面的故事我們都知道了,圖靈獎得主艾倫凱邀請喬布斯訪問施樂,接著擁有圖形界面的mac正式問世,從此改變了世界。離開施樂後,老爺子給自己所在的動畫公司起了名字,叫Pixar,再後來,老爺子就到了微軟。在微軟期間,他完成了這篇論文,當然他還是HSV顏色空間的作者。n

老爺子有個很酷的中文名字,值得講一下。老爺子的英文是Alvy Ray Smith,Ray是光線的意思,Smith在英文中有鐵匠之意,所以老爺子的英文名應該翻譯為:操控光線的匠人,這既是他的名字,又暗指了他的工作,圖形學不就是操作光線么?有位中國人為他起了這個十分精彩的中文名:匠白光。(此處我想起了高德納這個名字,也是精彩之極。)n

返回這篇文章,這篇文章第一次定義了matting問題,即:

I=alpha F +(1-alpha)B

一張圖片I,應該由前景F和前景B合成,合成的方式,就是通過透明度α來操作。使用透明度、前景和背景,我們可以合成這樣的照片。nn

matting問題研究的是,如何通過左邊的I,推測出右邊的三個變數α、F和B,難度可想而知。n

在這篇文章中,作者給出了Triangulation Matting的方法,整體思想也很簡單,既然matting原問題那麼難,不如把條件放鬆,使得問題簡單一些。假設我知道了B和I,那麼有沒有可能得到α和F,於是乎,作者提出了,針對同一張前景,切換背景,來計算得到前景和透明度的方法。如下圖所示:n

假設知道了兩張前景背景圖和對應的背景圖:n

應用最小二乘法,計算得到對應的透明度和前景:n

隨後結合新的背景,就可以生成極富真實性的合成圖片了:

當然那個時候,matting問題還主要應用於電影拍攝等場景,因此可以看出,這篇文章的操作很複雜,應用範圍也很有限。n

這篇文章還介紹了一些工業界的方法,裡面有一些Magic Number,本文讓我深切地感受到,真正的技術壁壘,並不是方法或者理論,而是資料庫,和經過無數次實驗找到的Magic Number。n

Poisson Mattingn

2000年以後,計算機科學家逐漸將Poisson Equation引入了計算機圖形學領域,尤其是Poisson Image Editing這篇文章:nn

隨後2004年的SIGGRAPH上,就有了Poisson Matting這篇文章。這篇文章的作者列表上,有Sun Jian,Jia Jiaya,Tang Chi-Keung,Shum Heung-Yeung。前段時間MSRA周年慶,不少大牛都來了,讀這些大牛的paper,就彷彿閱讀《三國志》一樣,你可以很清晰地看到,這些人的名字是如何一個一個串聯在一起,推動計算機行業發展的。n

回到這篇文章,隨著matting技術的發展,學術界也形成了一套解決matting的數據集、評價體系和標準流程,其中最特殊的一點是,使用tri-map作為輔助工具。tri-map分為三種顏色,黑色代表完全背景(此處α為0),白色代表完全前景(此處α為1),灰色代表不確定區域(α待定)。n

這篇文章,對matting等式進行觀察後,兩邊求導,得到如下的式子:n nabla I=(F-B)nabla alpha+alphanabla F+(1-alpha)nabla B

在這裡我們假設?F和?B很小,所以式子就簡化成如下的形式:

nabla alphaapprox frac{1}{F-B}nabla I

於是乎,我們就能寫出一個這樣的能量方程:

alpha^*=argmin_alphaintint_{pin Omega}||nablaalpha_p-frac{1}{F_p-B_p}nabla I_p||^2dp

其中 Omega 指的就是不確定區域。上述問題可以很自然地轉成微分方程去做,具體地,轉為泊松方程求解,這也是這個方法叫Poisson Equation的原因。當然,這篇文章發表的時間段,也正是研究人員將泊松方程系統地引入圖像處理的時間段,在計算機歷史上,我們經常可以看到,將數學和物理的研究成果,借鑒到計算機科學的故事。n

泊松方程有一個非常美妙的定理,即如果指定了邊界上的Dirichlet條件或者Neumann條件,那麼泊松方程在區域內的解是唯一可確定的,因此當我們知道不確定區域內的密度函數,和邊界上的alpha 值,我們就可以計算出這個區域內的 alpha 值。於是乎,我們定義邊界條件:n alpha_{partial Omega}=1 quad pinOmega_F

alpha_{partial Omega}=0quad pinOmega_B

而密度函數是:

Delta alpha=div(frac{nabla I}{F-B})

隨後我們就可以通過Gauss-Seidel演算法來求解得到 alpha 。n

當然這裡還有一個小問題是,F和B我們是不知道的,在這裡採用了一種非常直觀的方式,就是使用最近鄰的方法,確定F和B的值,當然隨後使用filter平滑F-B,來保證F-B的變化不會太突兀。n

最後整個演算法是一個迭代式的演算法,通過多次迭代,來保證 alpha 達到一個比較穩定的狀態。n

最後的效果圖是這樣的:n

Bayes Mattingn

貝葉斯公式算是這個世界上應用最廣泛的公式了,也是機器學習非常基礎的一個工具。n

matting問題可以直觀地表示為如下形式:

argmax_{F,B,alpha}P(F,B,alpha|C)=argmax_{F,B,alpha}P(C|F,B,alpha)P(F)P(B)P(alpha)/P(C)=argmax_{F,B,alpha}L(C|F,B,alpha)+L(F)+L(B)+L(alpha)

L是取log之意,這個操作的意義在於:由於概率都是[0,1],如果大量概率連乘,在計算機中的表示會變為0,同時由於P(C)是常量,因此可以忽略。n

那麼接下來的任務就是,對 L(C|F,B,alpha),L(F),L(B),L(alpha) 建立模型,建立的模型可以多種多樣,只要reasonable即可。所有應用貝葉斯公式和最大後驗概率(MAP)的方法,關鍵就在於對概率的定義。n

比如下圖的定義表示:對於預測的 alpha 、F和B,它們融合的結果和真實的圖像越接近,那麼概率越高。

L(C|F,B,alpha)=-||C-alpha F-(1-alpha)B||^2/sigma^2_C

對於L(F)來講,我們要建立的是前景顏色的概率分布,表示當前選定的F概率有多大,在文章中,它使用一種聚類方法,來對前景的顏色分布建模。n

對於L(B)來講,文中說針對不同類型的matting問題,可以使用不同的定義,在這裡,我們直接使用L(F)的定義。n

對於 L(alpha),這篇文章假設 alpha 的分布是平均的,因此我們可以在MAP中忽略這一項。n

最後就是求解這個MAP問題了,對於凸優化問題,我們可以直接使用導數為0的方式求解。n

當然由於alpha 會和F、B相乘,因此這個MAP問題比較難,所以文章採用兩段法求解,先固定 alpha 求解F、B,隨後固定F、B,求解 alpha ,迭代這個過程,直到結果比較穩定。n

結果是這樣的:nn

Learning Based Digital Mattingn

隨著機器學習的興起和數據集的豐富,關於matting的工作也轉為了數據驅動的思路,在這裡我們介紹基於半監督學習的方法。n

半監督學習的核心在於:在給定標記數據的情況下,預測結果不止和標記數據有關,還和未標記數據有關,更精確地說,和數據的相對位置有關。n

如果能建立一種 alpha 和像素點顏色的映射,那麼給定一個像素點,通過它的顏色來預測 alpha ,是一件多麼美妙的事情啊!於是就有了本文的解決方案。n

本文有兩個假設:n

1、任何未知的像素的 alpha ,是周圍像素 alpha 的線性組合,從而我們可以將這種線性組合關係表達為矩陣的形式,注意:在這裡我們使用了半監督學習中相對位置的概念;n

2、假設 alpha 和該像素點的顏色向量呈線性相關關係;n

於是乎,對於每一個點的 alpha ,我們期望使用周圍像素 alpha 的線性組合來預測,這個線性組合的參數,又是通過學習得到的,這個學習的過程,就是建立 alpha 和顏色特徵向量之間相關關係的過程。n

這個方法更美妙的一點在於,在建立 alpha 和顏色特徵向量的關係時,問題的解析解中出現了內積的形式,這時就可以引入Kernel Trick,將維度升高,去學更複雜的關係,Kernel Trick也是機器學習中極具數學之美的內容。n?

?nKNN Mattingn

還記得大三時在人人上,看到冠一姐和黃神討論SBTree時,知道了Chen Qifeng這個人,頓時膜拜了起來orz。後來在GraphiCon里聽士瑋兄回憶,Chen Qifeng帶他們訓練的往事,士瑋兄講了一句話,我很贊同:「發現以前的偶像居然跟我在同一領域,有點小激動!」n

就是這些優秀的人,給了我勇闖新世界的勇氣。n

這篇文章雖然實現起來很簡單,但是信息量卻很大,作者在文中很細緻地討論了idea和motivation,以及operation,而且這篇文章的目標也不是一般的Natural Image Matting,還涉及到了multiple layer matting。n

真要細細說來,不知何年何月,所以只是在此提及。n

Deep Automatic Portrait Mattingn

傳統的matting方法,有個比較大的限制,就是需要提供tri-map,而提供tri-map的方式,往往是人機交互,總是勞煩用戶動手,這是件不太理想的事情,end-to-end方法才是大家喜聞樂見的。n

當下Deep Learning如火如荼,深度學習引出了一大批end-to-end的工作,這篇來自Shen Xiaoyong博士的文章,使用過往的matting方法,構造了一個portrait image資料庫,同時在此基礎上,提出了一種基於CNN的matting方法,深度學習網路會自己預測tri-map,因此用戶只需要提供圖片,就可以得到matting結果了。nn

於是,回頭看看,matting經過了二十多年的變革,從最初需要提供多張背景圖片和原圖,到需要用戶交互提供tri-map,最後到當下的end-to-end solution,this is an amazing journey!n

從Matting到Dehazen

上個月在知乎上看到有個問題,博士三年還沒發paper是一種怎樣的體驗,底下有個回答講了He Kaiming的故事。真偽不談,但是從He Kaiming的文章中,我們明顯可以看到matting問題的影子。n

He Kaiming那篇著名的Single Image Haze Removal Using Dark Channel Prior,裡面把包含霧霾的圖像建模成這個樣子:

I(x)=J(x)t(x)+A(1-t(x))

其中I是圖像,J是場景輻射強度,A是global atmospheric light,t可以理解為相對權重,我們希望得到去霧後的圖像,就是J。n

可以看出,這個問題和matting一摸一樣。He Kaiming這篇文章的貢獻就在於,他發現了暗通道先驗,而有了這個異常良好的性質,這個很像matting的問題就沒那麼病態了,通過一些假設,我們可以直接使用矩陣運算,得到J。nn

當然為了讓最後的圖像效果更好,He Kaiming又做了Guided Filter,這個工作的精髓就是,嶺回歸。n

He Kaiming和Sun Jian的工作,從Poisson Matting,到Single Image Haze Removal Using Dark Channel Prior,到ResNet,給我的感覺就是,對問題的洞察極其深刻,使用的方法又極其簡單,頗有一種重劍無鋒,大巧不工的感覺。n

結語n

Matting對我影響很大,這個問題很基本也很難,於是前輩們使用了各種各樣的假設去求解,這些工作讓我大開眼界,極大地影響了我的研究思路。nn

當然,有關matting,還有很多漂亮的工作,我只很淺薄地介紹了我最喜歡的幾個方法。至於matting的詳細survey,請閱讀Wang Jue的Homepage:juew.org/。n


推薦閱讀:

為何一個byte有8bit而不是7/9/4/16bit ?
從工作角度出發,學習編譯原理和操作系統哪個對於個人幫助更大?
如何看待清華大學計算機科學在U.S.News的排名中位列第二?

TAG:计算机图形学 | 计算机科学 | 计算机视觉 |