關于圖像摳圖算法,Levin等人在2007年基于圖像的局部光滑 假設,利用代數的方法推導出了alpha matte矩陣閉合解的形式。原文名稱是”A Closed Form Solution to Natural Image Matting”。
在摳圖問題中,假設第i個像素點的值 Ii 是由前景點 Fi 和背景點 Bi 按下式權重合成的:
Ii=αiFi+(1−αi)Bi式1
其中 αi 稱為前景透明度,也就是要求解的”alpha matte”矩陣,指定了原圖中對應像素點的類型——屬于背景( αi=0 )、前景( αi=1 )或是未知( 0<αi<1 )。鑒于前景圖F和背景圖B都是未知,要想求解出alpha矩陣,需要其他條件——使用者輸入提示和圖像分布假設。
使用者輸入方式
不同的摳圖系統所接受的使用者輸入一般有兩種形式——trimap或scribbles。兩種方式的目的都是要給出alpha matte矩陣的初始估計。trimap的方式需要使用者指出所有的混合像素點,哪怕以摻入大量的前景點和背景點為代價,如(a)所示;而scribbles的方法隻需使用者在确定的前景和背景區域分别畫出一些條狀區域即可,如下圖(b)所示,在轉化成alpha matte矩陣時, α 的值同樣也是前景處為1,背景處為0,scribble的互動方式顯然比trimap的方式要簡單,尤其當對于圖像前景輪廓比較複雜的時候。
![]() | |
(a)trimap | (b)scribble |
灰階圖
為了使式1可以被求解,必須對F和B施加一些假設,該算法即假定F和B是局部光滑的,也就是在一個小的圖像視窗w中(如3x3),F和B固定不變,那麼式(1)就可以寫成:
αi≈aIi+b,∀i∈w式2
也就是說 α 與 Ii 是線性關系( a=1F−B , b=−BF−B 是常數)。那麼就可以簡單的定義要優化的目标函數為 α 的估計值與實際值的差:
J(α,a,b)=∑j∈I(∑i∈wj(αi−ajIi−bj)2+εa2j)式3
從表達式可以看出,子視窗存在大量重疊,正是該性質使得像素資訊可以進行傳播。該算法的巧妙之處在于通過一些代數推導,可以将a和b從式3中消去,轉換為隻有一個變量 α 的優化問題。
J(α)=mina,bJ(α,a,b)
J(α)=αTLα式4
其中, α 是Nx1維的列向量(N是像素總數),L是一個NxN的對稱正定矩陣:
L(i,j)=∑k|(i,j)∈wk(δij−1|wk|(1+1ε|wk|+σ2k(Ii−μk)(Ij−μk))
隻有當i=j時, δij 才等于1,其他情況下為0, μk 和 σ2k 分别是子視窗内像素的均值和方差。
在摳圖算法中,L是一個很重要的矩陣,人們稱之為matting laplace矩陣,它除了是一個對稱的正定矩陣之外,還是一個稀疏矩陣,隻有滿足 |i−j|<|wk|−1 的像素處L才是非0。是以,雖然L的次元很高,但仍可以采用高效的方式求解,尤其是利用MATLAB自帶的一些稀疏矩陣函數。
推導過程也比較簡單,主要就是先将式3平方和累加的形式轉換為列向量的模,恰好是一個最小二乘法的形式,再根據最小二乘法解的公式求出使得J最小時a,b的值,即可消去a,b,隻留下 α 。在摳圖時,除了希望得到alpha matte矩陣,一般還希望可以得到對應的前景圖和背景圖的值,是以在這裡詳細推導一遍,同時給出a,b與 α 之間的關系。
用列向量模的形式表示式3:
J(α)=∑k||Gk[akbk]−αk¯¯¯¯||2
其中,
Gk=[Ikε√10]
α¯¯k=[αk0]
這是一個典型的最小二乘問題,求解結果就是:
[akbk]=(GTkGK)−1GTkαk¯¯¯¯
帶入 J(α) 的表達式中即可整理出L。
彩色圖
如果是rgb圖,因為有了3個通道,是以需要對每個通道重複上述過程,但原文卻采取了另外一種假設模型——color line model。與灰階圖的局部光滑假設不同,color line 模型假定子視窗内的前景和背景像素值不是固定的,而是位于一條直線上:
{Fi=βFiF1+(1−βFi)F2Bi=βBiB1+(1−βBi)B2
将此假設帶入到式1中,經過推導(原文中給出了證明),可以得到彩色圖像的線性模型:
αi=∑cacIci+b,∀i∈w式5
ac 和b是僅與F,B,I有關的變量。将式5帶入灰階圖像的推導過程,同樣可以将目标函數化簡成式4,隻是L略有不同:
L(i,j)=∑k|(i,j)∈wk(δij−1|wk|(1+(Ii−μk)(∑k+ε|wk|I3)−1(Ij−μk)))式6
此時 ∑k 變成了視窗内所有像素的協方差矩陣, μk 是三維列向量,分别對應三個通道的像素均值, I3 是3x3的機關陣。L又被稱為matting laplace矩陣。
使用者輸入限制下的優化問題
施加了像素分布的假設後,還需要考慮使用者指定的前景和背景的先驗分布。當使用者按圖(b)的方式在原始圖像上畫出一系列區域時, α 中相應像素點被指派1(前景)或0(背景),那麼式4的優化問題就變成了:
α=argminαTLα,s.t. αi=si, ∀i∈S式5
S是使用者所指定的像素點的集合, si 取0或1.
為求解式5,首先對L中的像素位置進行重組,再次強調之前所說的,L是對稱矩陣:
L=[LMBTBLU]
LM 是已知像素點的集合, LU 是未知像素點的集合,也就是将圖像中所有标記出的像素排在前面,要求解的未知像素排在後面,當然為保證變換前後等式關系一緻, α 也需要相應調整:
α=[αMαU]
帶入式4:
J(α)=[αTMαTU][LMBTBLU][αMαU]=αTMLMαM+αTUBTαM+αTMBαU+αTULUαU
要求 J(α) 的最小值,需要進行矩陣求導,矩陣求導的通用公式如下:
∂xTa∂x=∂aTx∂x=a
∂xTAx∂x=Ax+ATx
因為 αM 已知,是以上式中的第一項導數為0:
∂J∂αU=LUαU+LTUαU+BTαM+BTαM=0
LU 是對稱的,是以最後求出的解為:
LUαU=−BTαM
算法運作效果
原圖和使用者輸入的scribble圖如下:
| |
(a)原圖 | (b)scribble圖 |
程式輸出的結果如下:
| |
(c)alpha matte矩陣 | (d)前景圖 |
| |
(e)背景圖 |
可以看出,盡管該算法比較簡單,但即使是與一些采用繁複的疊代的算法相比,其效果也是不錯的。
當然,最終結果的好壞還是取決于兩個因素——圖像是否滿足color line model的假設以及使用者輸入的先驗資訊,據原文的說法,一般的自然圖像都可以較好的滿足color line model。
關于其matlab源碼的解析将在下一篇文章中介紹。