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

01-28

作者：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：http://www.juew.org/。n