一種基于KNN后處理的魯棒性摳圖方法

白 楊 姚桂林

(哈爾濱商業大學計算機與信息工程學院 黑龍江 哈爾濱 150028)

0 引 言

圖像摳圖技術是把圖像的前景從背景中精確地分離出來的過程，圖像合成[1]則是把分離出來的前景通過某種方法放到新背景中的過程。利用摳圖與合成技術，可以將一個實體的目標放到虛擬的環境中，這種技術已經被影視業廣泛應用，同時這種功能也被一些圖像處理軟件所應用，例如目前使用最為廣泛的Photoshop。

圖像摳圖和圖像分割仍有較大區別，對于前景物體的邊緣和一些半透明物體，圖像分割只能將它們和背景分割成二值化形式。但在實際圖像的形成過程中，在前景物體邊緣附近的像素值是很復雜的，并不是簡單的前景/背景這兩種模式。圖像摳圖則對前景物體加入了α通道(或稱為Alpha通道，透明度)，成功解決了這個問題，從而可以更加精確地提取物體的前景。

對于一幅圖像中的某個像素，假設其坐標為z，觀察到的顏色為Iz，前景的顏色為Fz，背景的顏色為Bz，則物體的實際顏色可由{Fz,Bz}的線性組合得到：

Iz=αzFz+(1-αz)Bz

(1)

式中：Fz、Bz、αz為未知量;αz的取值范圍是[0,1]中的一個數。將αz∈(0,1)時的所有點稱作混合點，這些點通常在圖像的前景和背景的分界處，比如物體的頭發或者一些半透明物體等，并將αz=0或1的點稱為不透明點或絕對點。在自然圖像中，大部分點都是絕對前景點和絕對背景點，而混合像素點所占的比例非常小，如何將{Fz,Bz,αz}準確地計算出來是摳圖問題所面臨的任務。

式(1)有三個未知數，即有無窮多解，所以必須加上一些約束條件才能求解。在以往的摳圖過程中都會使用單一的背景(藍屏摳圖)來減少未知量，但是該方法對于顏色較復雜的前景效果并不好。于是提出了一種基于Trimap的交互式摳圖，人為將圖像標注成三個區域絕對前景ΩF、絕對背景ΩB和未知區域ΩU。其算法實例如圖1所示，前兩個區域為已知區域，分別用白色、黑色表示，未知區域用灰色表示。在絕對前景ΩF中包含大部分α=1的點，在絕對背景ΩB中包含大部分α=0的點，在未知區域ΩU中則包含全部0<α<1的混合點，并且有少量絕對點。本文將Trimap作為算法的先驗信息，然后求出未知區域的{Fz,Bz}。

圖1 圖像摳圖算法實例

1 相關工作

當前基于Trimap的主流摳圖方式有采樣法[2]和仿射法[3]?；诜律涞膿笀D方法并不孤立地計算每個未知點，而是考慮像素鄰域之間的聯系，利用遞歸的方法求出每個未知像素的Alpha值?；诓蓸拥膿笀D方法和仿射方法正好相反，該方法對每個未知點都獨立計算，并不考慮像素之間的相關性。針對未知區域ΩU中的像素z，假設其前景和背景為{Fz,Bz}，可以在ΩF和ΩB中可以直接找到或者通過計算找到一些近似樣本，并計算α。

1.1 采樣類方法

較早的采樣類方法采用高斯混合模型[4]分離前景和背景。貝葉斯摳圖[5]將圖像前景F、背景B和α看作一種概率分布，對于每一個待計算的像素z，建立先驗概率模式進行求解。Wang等[6]提出了一種優化采樣方式的魯棒性摳圖算法，該方法為每個未知點建立前景、背景樣本對，分別計算每個樣本對的信度值和Alpha值，然后選出三個信度值最高的樣本對，將這三個樣本對計算出的Alpha值取平均作為未知點的Alpha值。Gastal等[7]提出了共享采樣的摳圖方法，該方法以未知點作為起點，然后向空間中發射4條射線，每條射線最多采集一個前景點和一個背景點，經過一些優化方式得到未知點的最終Alpha值。文獻[8]提出了一種全局采樣的方法，對于未知區域，在靠近已知區域處用較小的鄰域進行采樣，在遠離已知區域處采用較大的鄰域采樣。

1.2 仿射類方法

泊松摳圖[9]將圖像的α看成一個場，將泊松方程引入到了摳圖問題中，隨機游走摳圖[10]將像素當成是圖的節點，用鄰域權值的方法去求解摳圖問題。而閉合形式(Closed Form)摳圖[11]假設在3×3或者5×5的小窗口符合顏色線性模型的性質，即該窗口中所有的像素值都是由某個固定的前景顏色F和背景顏色B的線性組合得到，構造拉普拉斯摳圖矩陣，并求解相應的稀疏線性方程得到每個未知像素的Alpha值。KNN摳圖[12]利用K近鄰算法來匹配非局部的鄰域像素，為每個未知點建立空間加顏色的特征，然后將未知點的K個鄰域設置權值，最后通過求解類似的稀疏線性方程得到未知像素的Alpha值。

2 后處理介紹

3 算法設計

3.1 對未知點進行魯棒性采樣

從已知區域的邊界ΦF和ΦB找到與未知點z在空間距離上最近的點FC和BC，然后以這2個點為起點，沿著上述邊界向兩側方向每隔一定的距離采集一個樣本點，對于每個未知點，共采集20個前景樣本點和20個背景樣本點，共包括400個樣本對。

3.2 初始Alpha估計與可信度計算

在采集了樣本點后，需要從上述樣本對中選擇較好的樣本對。為了使采集到的前景/背景樣本對能夠精確地體現未知點的前景與背景顏色，本文算法分為如下4步進行。

(1) 用每個樣本對估計未知點的α：

(2)

(2) 定義距離比率：

(3)

(3) 在普通圖像中，大部分像素都是絕對前景或絕對背景，因此需要額外設置以下兩個權值：

(4)

(5)

式中：DF=maxi‖Fi-C‖；DB=maxj‖Bj-C‖。在顏色空間中，前景或背景樣本點與未知點的顏色越接近，權值就越大。

(4) 最終的信度值計算如下：

(6)

式中：σ為常數，通常取0.1。

采用上述4個步驟可以計算出每一對樣本點的信度值f(Fi,Bj)和初級Alpha值，之后選擇3個最高信度的樣本對，對每個未知點，分別求出其信度值的平均值和初級Alpha值的平均值。

3.3 構建未知像素的數據權重矩陣

(7)

(8)

3.4 KNN后處理算法

3.4.1KNN算法流程

KNN算法是利用FLANN算法在指定的特征(一般為顏色特征)下尋找與未知點i最近的K個點，這里的“最近”指的是未知點與指定的顏色特征最近，而非空間距離最近，即以顏色特征的相似性代替了空間距離相似性，這樣可以搜尋到更多的空間遠距離像素，其具體步驟如下：

(1) 建立特征。為每個未知點i建立特征，并尋找在此特征下最接近i的K個像素。令{Bi,Gi,Ri}為像素點i的顏色特征，{xi,yi}為像素點i的空間特征。那么在RGB顏色空間下，未知點i的特征可以表示為：

(9)

(2) 計算權值。為每個未知點建立了特征以后，對未知點i的K個最近鄰點設置權值，其計算公式為：

(10)

式中：Xi為未知點i的特征；Xik為K個近鄰點的特征；c為一個權值系數。如果未知點i與樣本k的特征差異越大，權值越小。

(3) 構造稀疏矩陣。將計算的權值映射到一個稀疏對稱矩陣中。

3.4.2后處理的過程

在建立了KNN類型的稀疏矩陣后，就可以對采樣得到的初級α進行后處理。令α*為最終后處理的值，它的表達式為：

(11)

(L+θD+λ·diag(P(F)+P(B)))α=

θbs+λ·P(F)

(12)

3.5 算法優勢

在以往的仿射類后處理算法中采用的是基于空間特征和顏色線性模型的Closed Form算法對α進行后處理，但該方法存在兩個問題：(1) 局部窗口wk大小通常需要根據前景與背景的顏色分布進行選取，以往經驗上大小一般是3×3或5×5大小，但對于顏色分布復雜的場景，通常需要選取更大的窗口。(2) 假設算法在這個小窗口中的像素滿足顏色線性模型，然后利用摳圖公式和局部窗口進行復雜的權值累加計算。這種模型在局部顏色變化較緩慢的區域效果尚可，但顏色變化比較劇烈的區域效果不好。

針對上述兩個問題，本文采用KNN類方法做后處理，相比于Closed Form算法，其優點如下：(1) 顏色相似性的優勢，KNN類方法為每個未知點尋找K個近鄰點，這些近鄰點的顏色與當前未知點的顏色比較相近，因此用它們去線性組合未知點的顏色所形成的擬合誤差要比單純的采用空間特征去擬合的誤差要小。另外，由于KNN類方法采用的是顏色相似性，對于不同的顏色分布可能產生不同的顏色模型，相較于簡單的顏色線性模型要準確得多。(2) 全局搜索的優勢性。對于一些分布較廣但是前景、背景顏色差異較大的顏色分布，非常適合用KNN類方法去搜索像素。相較于只利用空間特征去尋找像素的一些算法，該算法能夠使未知點找到空間距離比較遠的像素，尤其是絕對前景和背景像素。另外，由于絕對前景和背景像素在未知區域內的比例很大，而對它們的計算也會更加準確，因此也能使得最終的α結果更加準確。

4 實驗結果分析

本實驗的硬件為Core i7四核3.8 GHz的CPU 以及8 GB內存的PC機，實驗環境采用的是Visual Studio 2017結合OpenCV，并采用C++語言實現。鑒于本文算法的特點，將該方法命名為RobustKNN。

本文采用Rhemann等[15]提出的在線摳像訓練數據集。該系統提供了27幅訓練圖像，并且使用均方誤差(MSE)和絕對誤差(SAD)作為誤差評判標準，其公式如下：

(13)

(14)

式中：m是圖像的寬；n是圖像的高；E(i,j)為摳圖算法得到的結果；H(i,j)為訓練集提供的真實結果。

4.1 定性觀察

本文選取了訓練集中的3幅圖像。圖2為前景區域存在孔洞的2幅圖像經各算法處理得到的Alpha結果圖。其中，圖2(a)為GT01，其特點是前景存在較多空洞，這些空洞處的背景與已知背景距離較遠。Trimap為原圖的三分圖，Ground Truth為GT01的真實Alpha值(只展示在Trimap圖中用黑色矩形框框住的那一部分)，下面的三幅圖分別是Closed Form、Robust和RobustKNN算法輸出的結果(只展示在Trimap圖中用黑色矩形框框住的那一部分)。從圖中可以看出，三種算法都能將物體的前景輪廓摳取出來，但是對于前景空洞(如用橢圓框住的那一部分)，Closed Form算法和Robust算法表現要稍微差一些，前者將這部分空洞劃分到前景中去，后者雖然能摳取出這部分空洞的大致輪廓，但是還是有很多像素被劃分到前景中導致摳圖準確性下降，這也是單一的使用距離作為特征所帶來的問題。而本文算法(RobustKNN)能夠準確地將這部分空洞摳取出來，這得益于本文算法在后處理階段使用的是顏色特征與距離特征相結合的方式，能夠利用顏色相似性找到與未知點顏色相近但空間距離比較遠的像素，提高了Alpha值的準確性。

另一個前景存在空洞的例子如圖2(b)所示，其中GT02為原始圖像，其特點為前景中同樣存在大量的空洞。Trimap為原圖的三分圖，Ground Truth為GT02的真實Alpha值(只展示在Trimap圖中用黑色矩形框框住的那一部分)，下面的三幅圖分別是Closed Form、Robust和RobustKNN算法輸出的結果(只展示在Trimap圖中用黑色矩形框框住的那一部分)。從圖中可以看出，三種算法都能將物體的前景輪廓提取出來，但是在輪廓內部的一些空洞點，三種算法的表現不盡相同。Closed Form算法表現的最差，大量的空洞點被劃分到前景中去，造成錯誤劃分。而Robust算法稍好一些，但一些細小的空洞點也被其劃分到前景中，造成錯誤劃分。本文算法的效果最好，能夠準確地劃分出一些細小的空洞點。

圖2 各算法對前景區域存在大量孔洞時的圖像的Alpha結果圖

對于有效樣本缺失的情況，原圖及各算法處理結果如圖3所示。其中GT03為原始圖像，其特點為國旗部分缺少有效樣本。Trimap為原圖的三分圖，Ground Truth為GT03的真實Alpha值，下面的三幅圖分別是Closed Form、Robust和本文算法輸出的結果?？梢钥闯?，Robust算法表現最差，國旗的輪廓沒有完整地摳取出來。Closed Form算法表現稍好一些，能提取出國旗的輪廓，但是國旗內部許多地方還是劃分到背景中，造成劃分錯誤。本文算法的表現最好，它將國旗的整體區域都劃分到前景中。

圖3 各算法對有效樣本缺失時的圖像的Alpha結果圖

4.2 定量分析

4.1節是從視覺角度對算法進行評價，本節通過MSE和SAD這兩個指標來對算法進行評價。表1與表2為上述3幅圖像的MSE和SAD?？梢钥闯?，本文算法無論是均方誤差還是絕對誤差都比其他算法小，即本文算法的結果最接近真實結果。

表1 3幅圖片的均方誤差(MSE)

表2 3幅圖片的絕對誤差(SAD)

為了更加客觀地評價本文算法，將訓練集中的27幅圖像的均方誤差和絕對誤差全部計算出，并求平均值，同時計算出在不同型號Trimap下各個算法的誤差，結果如表3、表4所示。這些不同型號的Trimap最主要的區別就是在標注前景區域、背景區域和未知區域時的精準程度，其中小型號的Trimap標注最為精細而巨大型號的Trimap標注則比較粗糙?？梢钥闯?，同一種算法中小型號Trimap的誤差要小于巨大型號的誤差；在相同Trimap型號下，本文算法造成的誤差要小于其他兩種算法。

表3 27幅圖像的平均均方誤差

表4 27幅圖像的平均絕對誤差

5 結 語

本文在魯棒摳圖算法的基礎上，采用KNN算法對采樣得到的初級α進行后處理，算法彌補了以往使用傳統仿射類算法做后處理時，使用單一的空間距離作為特征的缺陷，這會造成搜索范圍較小。而在局部窗口中使用簡單的顏色線性模型使得對于顏色分布較復雜的圖片造成較大的誤差。本文采用KNN搜索方法用作后處理，為每個未知點建立顏色特征和空間特征，使得未知點能找到與其顏色相近的一些近鄰點，同時KNN類仿射算法具備采樣范圍較寬的特點，能搜索到較遠處的像素。實驗結果表明，使用KNN類仿射算法做后處理相較于傳統的仿射類算法，無論在視覺方面還是準確性方面，其Alpha結果都有較大的提高。