一種基于雙層框架的仿射類圖像摳像方法

姚桂林 趙志杰 蘇曉東 辛海濤 胡文 秦相林

數字圖像的摳像與合成問題是在虛擬現實中圖像處理領域的兩種經典問題,目的是從一幅合成圖像中將前景物體從背景中分離出來,并合成到一幅新背景圖像中.對于合成問題,對于在數字圖像I中的某個位置i=(x,y),給定前景圖像的顏色Fi、背景圖像顏色Bi以及一個透明度標量αi ∈[0,1],其觀察到的顏色Ii能夠用如下摳像公式表示為

如果αi=0 或αi=1,將點i稱作絕對前景或者絕對背景,并統稱為絕對像素.對于其余0<αi <1的點,稱為混合像素.

摳像問題為合成問題的逆問題,同時也是欠約束問題:給出各點的合成像素Ii,需要求出未知量Fi、Bi與αi.很多一般背景摳像問題都需要用戶提供手工輸入的輔助三分圖Trimap,如圖1(a) 和(b)所示,它包括已知絕對前景區域?F和已知絕對背景區域?B,剩余部分為未知區域.于是,依據已知像素,并根據摳像公式及某些先驗條件,可以估計未知區域內的每個像素的{F,α}值.基于Trimap 的圖像摳像算法通常分為如下2 種方式:1) 基于仿射的摳像方法[1?7].該方法并不孤立地計算每個點,而是考慮像素間的相關性,利用間接、迭代的方式遞歸地求出未知區域中各個點的α值.2) 基于采樣的摳像方法[8?17].該方法對每個未知點獨立從已知區域中選取樣本,并采用逐對樣本的計算方式,而并不考慮各個像素之間的聯系.

本文主要討論仿射類方法[18].雖然相比仿射類方法,采樣類方法的采樣位置和采樣方式變化較多,而且獲取樣本方式非常直接,然而,仿射類方法具有以下優勢.1) 仿射類方法充分強調了像素間的相關性,該方式也可視為由已知區域向未知區域緩慢、漸進的計算,因此在最終α結果的平滑性以及帶給或用戶的視覺感受上要明顯好于采樣類方法.2) 采用遠距離搜索的仿射類方法對絕對點的計算效果較好,而在事實上,未知區域內的大多數點為絕對像素,因此該類方總體準確率上有較為明顯的優勢.本文在第1 節首先闡述了仿射類方法的2 種分類方式以及它們優點和缺點,在第2 節中針對KNN 類的特點討論了絕對像素劃分(即預處理) 方式,在第3 節中針對Matting Laplacian 類的特點討論了剩余混合像素的計算,并在第4 節中討論了這2 類方法各自的實驗結果.最后第5、6 節討論了仿射方法目前存在的問題并得出本文的結論.本文基于仿射方法的雙層次摳像框架如圖1 所示.需要說明的是,由于仿射類方法與采樣類方法、乃至其他類如特殊類[19]、深度學習類[20?22]等方法采用完全不同的計算機制,而且本文主要研究前者,因此無論在理論研究和實驗數據上,本文并未引入任何其他類方法,而且也不將結果傳至α評估系統[23]中,以保持仿射類方法的整體一致性.

1 仿射類摳像方法概述

假設每個未知像素的α值是它的K鄰域像素α值α1,α2,···,αK的線性組合,表示為

實際求解中,所有未知點i的αi可通過求解如下大型稀疏線性方程得到

其中,L為長與寬均為圖像像素總數的稀疏方陣,未知點i所在行對應K鄰域的系數記為wj,j=1,···,K,D為對角陣,在已知點所對應的對角線元素的位置為1,未知點為0,θ為某個較大的數.b為長度等于像素總數的列向量,前景?F處位置為1,背景未知區域?U位置為0.上式可采用共軛梯度法求解.

1.1 仿射類方法的分類

各仿射類方法、亦即稀疏矩陣L的構造方式之間的主要區別是每個未知點i的若干近鄰像素位置的遠近以及相應權值wj的構造方式.按是否采用摳像公式以及在摳像中的實際效果,仿射類方法可分為不采用摳像公式的簡單權重類方法以及采用摳像公式的Matting Laplacian 類方法.

圖1 圖像摳像問題的基本輸入輸出和本文的雙層次摳像結構Fig.1 Input and output of image matting and the hierarchical framework of our method

1.1.1 簡單權重類方法

該類方法如圖2 左欄所示,其特點是不采用摳像公式,直接采用顏色差異的方法確定權重.具體的,當前點i與各近鄰點j顏色差異的某個負函數即為各個權重,即與j的顏色越接近,權值越大,二者的α越相似.起初的Random Walk 算法[6]僅采用8 鄰域處最近的搜索范圍,但無論在絕對像素還是混合像素,其計算效果均很不理想.Nonlocal 算法[3]對鄰域空間進行了擴展,采用以每個未知點為中心、半徑為r的方形搜索尋找K個顏色最相近的點.為減少計算量,采樣半徑r通常不大.KNN 算法[4]的搜索距離則更遠,需要尋找每個點在顏色約束和空間距離約束的特征下最近的K個點.

圖2 仿射類方法的2 種分類方式對應的算法及適用范圍(其中Lap 表明在原簡單權重方法的基礎上采用Matting Laplacian)Fig.2 Two types of affinity based matting method and the corresponding algorithms and application scopes(where Lap denotes the application of matting Laplacian based on simple weight methods)

根據式(2),若αi或其K個近鄰像素的αj均接近于0 或1,即它們均為絕對前景或背景,此時的權值wj顯然幾乎無法構成影響.因此,在KNN 算法中討論的權值是否采用exp(-x) 還是1-x的問題則顯得不大重要.但若αi和αj為小數,即它們均為混合點,則權wj非常重要.然而,由于簡單權重模式下的wj的產生并不采用摳像公式,而真實值αtrue是由摳像公式算出,因此此時的結果肯定不理想.由此可得出的結論是:該類方法適合于計算絕對像素,而不是混合像素.

另一方面,搜索范圍較近的Random Walk 和Nonlocal 等方法,需要經過多次傳遞才能到達已知區域,因此較易造成誤差累積.相反,搜索范圍較廣的KNN 算法可以通過較少次數的傳遞或直接搜索到達已知區域,會產生較少誤差累積,更有利于絕對前景和背景的計算.這與采樣類方法中直接訪問已知區域的方式較為相似.

絕對像素計算步驟也同時在文獻[24]中進行了深入討論.據統計,在評估系統[23]提供的所有訓練圖像中,大型號與小型號Trimap 中的絕對點數量大大超過了混合點的數量,由此可以看出該步驟的重要性.進一步,該步驟必須單獨采用一個獨立的、不采用摳像公式的步驟,使其區別于普通的混合像素計算步驟,而簡單權重類方法則完全符合這種絕對像素計算準則.目前,絕對像素的計算的算法僅出現在采樣類計算方式中,但局部類方法[13?16,19]容易遺漏較遠處的樣本,誤劃分率偏高,而全局類方法[17]易受全局前景和背景顏色重疊影響,誤劃分率較高.由此可以看出,目前的絕對像素劃分方法仍然受到全局與局部采樣方式相互平衡的困擾.

1.1.2 Matting Laplacian 類方法

該類方法如圖2 右欄所示,它假設在某“局部集合”S內,任何點i的前景和背景顏色Fi和Bi都是兩個固定顏色{F1,F2} 和{B1,B2} 的線性組合,稱為顏色線性模型(Color line model).結合摳像公式并經推導,結論為在某個集合S內的(i,j)∈S,點i與j產生的權重為

其中,xi與xj分別為點i與j的三維顏色向量,X3為3×3 單位陣,ΣS、μS分別為S內的3×3 協方差矩陣與3×1 的均值向量,ε為一個較小的數.未知點i與j的權重為所有包含二者的集合S所產生的權重之和.顯然,由于采用了摳像公式,該類方法非常適合于混合點的計算,也是目前為止,仿射類方法中對混合點最重要的計算方式.

該類方法的關鍵問題是相關集合S如何選擇.Closed-Form 算法[1]提出將集合S定義為較小的局部窗口,對于寬度較窄的前景硬邊界效果較好,然而該類小窗口無法充分涵蓋較寬的混合區域或前景空洞等實例的顏色信息.Large Kernel 算法[2]改進了基于空間局部窗口的思想,提出了核寬度r與不同未知局部區域的寬度成比例的方式.然而事實上,核寬度很大程度上依賴于真實混合區域的寬度信息,而未知區域僅為用戶的粗略手工輸入,尤其輸入為稀疏的線條不能充分表達混合區域的實際信息,現實中還會存在很多偏差.CCM 算法[5]采用了KNN方式中的顏色近似的方法選取集合S,取代了空間方式的局部窗口.由于該方法搜索范圍過大并引入大量已知樣本,在實際中,它對絕對像素計算的效果較好,但對于混合像素的計算也受到全局絕對樣本影響,出現過于二值化的現象.

CNN Matting 方法[20]提到,KNN 算法與Closed Form 算法之間的區別并不直接,由此采用基于深度學習方式對二者進行融合.然而經本文討論至此,它們的區別已經非常明朗,即KNN 類方法適用于絕對像素的劃分,而Matting Laplacian類(即Closed Form 類) 適用于混合像素的計算.本文從仿射類方法自身入手,據各類方法自身的優點和缺點做出相互的補充,避免了大量訓練數據以及長時間訓練等問題.

圖3 顯示了5 種典型算法在α評價系統[23]的52 幅訓練圖像上(27 幅訓練圖像中的大、小Trimap且不包含GT16),各αtrue區間的平均MSE 比較(不包含Random Walk),顯然,KNN 在0～0.25與0.95～1 區間較好,印證了它非常擅長于絕對像素劃分,而較為平滑的背景使得在絕對背景劃分上更加優秀.CCM 僅在0～0.05 區間較好,說明它受前景和背景重疊的影響非常大.Closed Form 與Large Kernel 大致0.25～0.95 間較好,印證了它們擅長混合像素的計算.同時,近距離Nonlocal 算法在各區間中均不理想.

圖3 各αtrue 區間中5 種傳統仿射類算法α 結果的平均MSE 比較(其中x 軸坐標中的0.0 表示0.0～0.05 區間等)Fig.3 MSE comparison on five traditional affinity based matting algorithms in each αtrue interval (where 0.0 in x-label denotes the range of 0.0～0.05,etc)

1.2 本文方法的提出

事實上,KNN 類算法中K近鄰像素的遠近的選取,對該類方法的絕對像素劃分結果會產生重要影響.在前景與背景的整體重合度不高的前提下,選擇更遠距離的搜索范圍,不僅會為當前未知點提供更多相似的已知點,而且在Trimap 真實樣本距離未知點較遠時(如未知區域較大、或者前景存在空洞) 計算效果更好.但如果較遠處的前景與背景顏色存在較大重合,則會產生計算錯誤,此時需要采用較小的搜索范圍.因此,所選取的近鄰像素的遠近也是一個重要的平衡.然而,KNN 采用固定的遠距離與近距離相結合的方式,無法根據空間上的顏色變化情況進行自適應調整.

基于上述分析,本文在第2 節新引入了KNN搜索上的3 種范圍(如圖2 左欄所示),并依據全局重疊與局部重疊程度,相應采用其中2 種層次相結合的方式,以期對大部分絕對像素進行劃分,并進一步縮小未知區域的寬度.同時,由于無法保證初始Trimap 與混合點之間的關系,該層次采用與初始Trimap 未知區域大小無關的方式,這與Large Kernel 算法不同.

如前文所述,混合像素計算過程中的Matting Laplacian 類方法中的核寬度、或者搜索空間的大小,需要與真實未知區域的寬度相一致.若搜索范圍過小則無法充分涵知區域的信息,造成CNN 算法[20]提到的“過平滑”,而搜索范圍過大會導致混合像素的絕對像素化,如CCM.由于在第2 節中,相當多的絕對像素已被劃分,且混合像素區域的大致輪廓也已確定,因此在此基礎上,第3 節引入了KNN及Nonlocal 搜索上的5 種范圍(如圖2 右欄所示),并采用結合未知區域寬度的Matting Laplacian 方法,計算最終剩余混合像素.

2 絕對像素劃分

本節討論基于KNN 搜索方式的絕對像素劃分.第2.1 節提出了搜索范圍因子的概念,并定義3 種搜索范圍下的直接點差異度,為后續章節打下基礎;第2.2 節提出了圖像重概念,將圖像劃分為低重合度圖像和高重合度圖像,前者按2.3 節計算α,后者按第2.4 節計算α.最后按第2.5 節的截取方式得到預處理后的Trimap.

2.1 搜索范圍因子與直接點差異度

首先,類似于KNN 算法,定義像素i的特征矢量(f)=[ri,gi,bi,sxi(f),syi(f)]為i的3 個通道的顏色值,{ri,gi,bi} 為點i的空間距離特征,表述為

其中,xi和yi為i的空間橫坐標與縱坐標,f為控制空間距離遠近的重要參數.f越大,采集的像素越近,反之則越遠.在KNN 算法中,f的取值為1 和0.01 之間的融合,其最終效果近似于0.5,如圖2 所示.

前文曾提到,搜集像素位置的遠近是KNN 類方法的決定因素之一,該問題非常依賴于前景與背景顏色的重合度.然而,傳統的仿射類方法并不是直接訪問已知區域的,直接獲取每個點的前景和背景信息.因此,本文提出一種類似于采樣方式的、直接訪問已知區域的方法,用來模擬和引導每個未知點間接搜索距離的方式.這里需要利用FLANN (Fast library approximate nearest neighbors)方法,在相關特征xi(f) 下,靠近未知區域的5 個像素寬度的已知前景區域ΦF和背景區域ΦB位置(簡記為F與B),對每個像素i分別尋找最近的前景和背景點j各K=10 個,將它們稱為直接點,如圖4(a) 下方的j點所示(以背景為例).在xi為xsi的前3 個空間無關特征分量、即顏色特征下,計算未知點i與上述前景與背景直接采樣點對于K個直接點的平均顏色差異di(f,F) 與di(f,B),之后在給定距離參數f之下,計算點i的前景與背景顏色的差異系數:

圖4 以背景為例,未知點的各種搜索方式與搜索范圍Fig.4 Various kinds of searching manners and searching ranges for an unknown pixel

其中,θ1的取值在1 至2 之間時,前景與背景的區分效果最好,這里取經驗值θ1=1.5.DFi(f) 越高,表明在距離參數f下,點i的直接前景與背景顏色差異性越大,重合性越低,該距離參數f就比較理想;否則,該距離參數就不理想.

對每個未知點i,計算近、中、遠3 個級別的差異度DFi(0.5),DFi(0.1)和DFi(0.01),并為后面的計算所采用.這3 個級別的近似搜索范圍如圖4(b)所示.

2.2 像素采集遠近及圖像的重合度判別

按文獻[25]的理論,局部(或近距離) 采樣方式應作為基本方式,而全局(或遠距離) 采樣方式是局部的一種補充.而這對于仿射類方法同樣有效.考慮到各圖像中前中前景與背景的重疊程度不盡相同,采集像素遠與近的范圍也不相同.首先,在未知區域?U內、靠近已知前景和背景區域的位置,分別定義1 個像素寬度為“學習區域”(簡記為F與B),首先在距離參數f之下,計算這2 個區域到各自已知前景和背景的平均顏色差異dL(f,F) 與dL(f,B),

rt1越小表明近處像素點已經足夠判別絕對像素點;否則,需要采集遠處像素來實現.

其次,在特定集合M下定義如下準則:

其中,判定條件Cr=(DFi(0.5)

其中,M1={i|i ∈?U∧DFi(0.1)<1},M2={i|i ∈?U∧DFi(0.1)≥1},θ2=0.7,θ3=0.4.之后,若T1≤0.7×10?4,則該圖像為前景與背景重合度較高的圖像;否則,若T1≥1.2×10?4,則該圖為重合度較低的圖像.若T1在上述二值之間,則進一步令T2=rt1·rt2(M1)θ2,若T2<0.8×10?4,則該圖為重合度較高的圖像,否則為重合度較低的圖像.上述參數均根據經驗取值.

最后,設定低度重合的圖像采用2 個遠距離級別的f為0.1 和0.01,而高度重合的圖像采用2 個近距離的0.5 和0.1.每種重合度形式均采用近距離搜索范圍為主、遠距離為輔的搜索形式.

2.3 低重合度圖像

對每個未知點i,計算如下比例:

其中,di為在第2.1 節中求得的i與直接點顏色差異.定義如下f=0.01 處的判別準則

經第1 節分析可知,背景通常較為平滑,而前景變化相對較大,因此,若rti(F)>rti(B),則θ4=5,否則θ4=1.5,同時對上述情況均取θ5=1,上述參數取值表明對前景的約束要高一些.上式成立時表明:1) 該點在f=0.01 下與直接前景點或背景點的差異較在f=0.1 時小;2) 該點在f=0.01 下對應直接點的前景與背景之間差異較大.圖5 的第2、3 列顯示了DF的例子.

如前文所述,該方法需要利用直接點的前景與背景的重合程度,模擬KNN 類方法對間接點的采集遠近.具體的,利用FLANN 方法,對每個未知點i在空間特征xsi(0.1)、xsi(0.01) 下,在?U處以及靠近它的40 個像素寬度的已知前景和背景區域位置(比直接點區域要寬),尋找與i最近的點j各K個,稱為間接點,如圖4(a) 上方的j點所示.于是,若滿足式(11) 對應的約束條件,則未知點i選取遠處f=0.01 的K個間接點,否則選取中距離處f=0.1 的.最后,對于像素i搜索到的K個像素,令它們同時對應了式(2) 中的K個位置,顏色特征為xj,則該類方法的對應式(2) 下的權值為wj=1-‖xi-xj‖/3.采用共軛梯度法求解所α值,記為αpre?our.

為了比較,本文也實現了單獨運行的中距離搜索方法KNN-0.1 以及遠距離搜索方法KNN-0.01.圖5 同時顯示了本文方法能夠結合KNN-0.1 與KNN-0.01 的優點,并避免它們的缺點的例子(包括局部與全局圖像).其中,前2 行顯示了2 個前景存在空洞、且前景與背景差異相對較大的圖像,此時第2、3 列顯示了KNN-0.01 比KNN-0.1 在較多關鍵點中的DF要大,本文結果會利用這種優勢來覆蓋遠處的已知背景像素,并避免在近距離搜索中容易遺漏的像素,使得更多已知點可以被劃分出來.第3行顯示了一幅前景與背景重合較大的全局圖像,此時KNN-0.1 與KNN-0.01 的DF大都較小,而第4 行的局部圖像顯示了它們的DF仍然較為相似,此時對變化過大的前景像素進行過量采集時會產生“過搜索”.在這2 種情況下,本文方法采用相對保守的近距離搜索,避免了這些情況產生的誤劃分.

圖5 全局低重合度圖像中本文預處理方法與其他2 種單一搜索方式的結果比較(前2 列與后2 列分別顯示了遠距離與近距離搜索方法較好的例子,圖像中的線條表示前景與背景邊界)Fig.5 Comparison of pre-processing results between our method and two unary searching methods in low global overlapped cases (where the first and last two rows show good results in methods with long and short searching ranges respectively,and the lines in the input images show known foreground and background boundaries)

2.4 高重合度圖像

由于高重合度圖像在直接點處前景與背景的重合度也較高,無法完全提供二者的準確信息,因此需要利用間接點的方式.類似于第2.3 節,首先,利用FLANN 方法,在上節定義的區域內對每個未知點i,在空間特征(0.5)、(0.1) 下,尋找最近的K個間接點j.之后在f下計算每個未知點i與K個間接點的平均差異,記為di(f),并定義如下f=0.1處的判別準則

其中,θ6=10,θ7=1,上述參數均根據經驗取值.上式成立時表明:1) 該點在f=0.1 下與鄰域間接點的差異較在f=0.5 時小很多;2) 該點f=0.1下對應直接點的前景與背景之間差異較大.于是,若滿足式(12) 對應的約束條件,則未知點i選取較遠處f=0.1 的K個間接像素,否則選取f=0.5 處的.求解αpre?our過程仍采用共軛梯度法.為了比較,我們也實現了單獨運行的近距離方法KNN-0.5.圖6 的2 個例子(包括局部和全局圖像) 顯示了前景與背景在遠距離搜索KNN-0.1 上存在較大重合的圖像,此時KNN-0.5 較KNN-0.1 在DF的很多像素上要大一些,本文則傾向于采用KNN-0.5 來避免這類重合所造成的計算錯誤.其中第2 個例子是測試圖像,沒有真實值,因此實際上我們引入了評價系統[23]上排名最高算法的結果圖作為近似真實值.

最后,一種特例是該圖所有未知點與前景和背景的顏色差異都較大,該例在正常計算時誤差較大,此時該例完全簡化為KNN-0.1,該平均顏色差異計算為

其中,直接像素差異di(0.01,O) 在第2.1 節定義,nU為未知點的個數,該約束條件為≥0.003.

圖6 全局高重合度圖像中本文預處理方法與其他2 種單一搜索方式的結果比較Fig.6 Comparison of pre-processing results between our method and two unary searching methods in high global overlapped cases

2.5 Trimap 的更新

經之前的分析可知,KNN 類方法對絕對像素的計算較好,因此需要將αpre?our的絕對像素作為已解決的像素,并且將混合像素留給Matting Laplacian 方法計算.首先,對于未知像素i,成為新已知前景與新已知背景需要滿足的條件為

3 混合像素計算

圖7 顯示了經過前節得到的新Trimap 的6 個例子,可以明顯看出,大部分絕對點都已被計算為已知點,而且剩余未知區域也可以基本描述出混合像素的分布情況,包括變化迅速的實心物體邊緣(硬邊界)、毛發式邊界(軟邊界)、半透明物體等,這對于核寬度的選擇或采用其他處理方式都是極大的幫助.同時,也很好地解決了Large Kernel 算法中提出的僅依據初始Trimap 中未知區域大小的缺陷.

依據前文的理論,混合像素的計算需要首先產生第1.2.2 節中的集合S,并利用Matting Laplacian 的方式生成權重.不同的是,本文并不采用Closed Form 和Large Kernel 算法中的基于空間連續的搜索方式,而是采用顏色特征相匹配的Nonlocal、KNN 及CCM 的搜索方式,該方式可以擴大搜索范圍,并減少顏色線性模型帶來的計算誤差.這里每個未知點產生集合S的原則是:一方面,該集合要盡可能引入已知前景和背景區域,以消除在未知區域中傳遞次數過多而造成的累積誤差,另一方面,獲取的已知像素不能過多,以減少顏色過度重合造成的計算誤差.

具體的,在新Trimap 下,首先計算每個未知點i與新已知前景和背景的最近空間距離,分別記為Di(F),Di(B),并求出二者的平均距離,記為Di,之后利用該參數調整Nonlocal 方法中的方形搜索半徑r.進一步,若r較大,逐點方形搜索的方式所花開銷太大,這時需采用KNN 或CCM 算法中的FLANN 方法.此時仍然遵循第2 節的多層次搜索原則,分為f=0.5、0.1、0.01 的3 級搜索方式.此外,本節依然采用與第2 節類似的、計算整幅圖像重合度的方式,以此作為搜索范圍的依據.在新Trimap 下,對每個未知點i獲取經第2.1 節計算的3 個級別的差異度DFi(0.5)、DFi(0.1) 和DFi(0.01),按第2.2 節重新計算已知前景和背景的平均顏色差異dL(f,F) 與dL(f,B),并按式(9) 重新計算整幅圖像的重疊度T1,若T1<2.0 則為高重合度圖像,否則為低重合度圖像.

根據每個未知點i與已知區域的空間距離,具體分為以下3 種常規情形,如圖7(a)～(c) 所示:

1)“硬邊界”,需要滿足至少如下2 種情形之一.a)Di ≤8;b) 整幅圖像是高重合度圖像.2 個局部的例子如圖7(a) 所示.此時對未知點i采用Nonlocal 的方形搜索方法,而搜索窗口要盡量覆蓋到已知前景和已知背景區域,但也要避免窗口過寬.因此在半徑為r下,按單純的顏色特征x搜索K=10個與之最近鄰的像素.半徑r計算為

2)“軟邊界”,需要滿足8≤Di <40.該情形代表較多毛發的邊緣,2 個局部的例子如圖7(b) 所示.類似于第2.4 節,利用FLANN 方法,在整幅圖像中對每個未知點i,在f=0.5、f=0.1 時尋找最近的K個間接像素.并定義f=0.1 處的判別準則為DFi(0.1)≥0.1.若滿足該約束條件,則未知點i選取較遠處f=0.1 的K個間接像素,否則選取較近處f=0.5 的.

3) 長毛發邊緣與前景空洞,需要滿足Di ≥40,表明該點與已知背景距離很大,2 個局部的例子如圖7(c) 所示.類似于第2.4 節,對i在f=0.1、f=0.01 時,尋找最近的K個間接像素,并定義f=0.01 處的判別準則為DFi(0.01)≥0.1,若滿足該約束條件,則未知點i選取較遠處f=0.01的K個間接像素,否則選取較近處f=0.1 的.

有時,整幅圖像未知區域的空間距離或顏色差異較大,分為以下特例,如圖7(d)～(f) 所示,此時以上常規方法并不奏效,需獨立于上述情形之外單獨考慮.

4) 存在大量與已知區域差異較大的點,或者所謂的“突兀點”,此時需要滿足ˉd >0.003,ˉd為式(13) 定義的未知區域的平均顏色差異.一個全局的例子如圖7(d) 所示,其中旗子部分與前景和背景的顏色差異都很大.此時在實踐中將式(15) 中min 函數內的max 也同樣變為min 可以使得最終摳像效果大為改善.

圖7 預處理后的各種Trimap 情況Fig.7 Various kinds of Trimap after pre-processing

5) 存在大量半透明像素的前景物體,如塑料袋、網袋、杯子等.此時需要滿足ˉD >25,ˉD為所有Di的平均值,且不滿足條件4) 的情形.在大量像素需要遠距離搜索的情況下,與CCM 類似,此時Matting Laplacian 會經常失效,又分為以下2 種情形:a) 該圖為低重合度圖像,一個全局的例子如圖7(e) 所示.此時不做后續處理,直接采用預處理后的結果.b) 該圖為高重合度圖像,一個全局的例子如圖7(f) 所示.此時意味著前面的預處理步驟很可能也不準確,這里直接采用KNN 算法下的HSV 色彩區間的結果.

最后,對于上述前4 種情形搜索到的K個像素,按第1.1.2 節形成Matting Laplacian 的集合S,并按式(4) 為像素i提供K個未知的權值貢獻,采用共軛梯度法求出最終解αlap.要注意的是,此時式(3) 中的列向量b,對應所有已知點位置為其實際的α值,即新已知前景?′F處位置的范圍為[αupper,1],新已知背景?′B處位置的范圍為[0,αlower],其余未知點位置為0.求解中,若遇到共軛梯度法不收斂的情況,則直接采用預處理后的結果即可.

4 實驗

為了體現本文方法對于Trimap 大小的兼容性,對于評價系統[23]中的27 幅訓練圖像,除了大型號與小型號的Trimap 之外,我們另外為它們創建了“巨大”型號的Trimap,它們通過將大型號Trimap未知區域膨脹10 個像素、并保留面積小于500 的前景和背景區域得到.

4.1 絕對像素劃分

本文選擇了9 種仿射類的預處理方法,包括5 種已存在的算法(不包含Random Walk),3 種KNN 類算法KNN-0.5、KNN-0.1、KNN-0.01,以及本文方法.其中,Large Kernel 算法僅簡單地將Matting Laplacian 的核寬度設為2,Nonlocal 算法的搜索半徑為20,搜索10 個最相似的像素.對各方法中獲得的α進行預處理方式均按式(14) 進行截取.為了比較預處理方法的有效性,未經預處理的方法也被引入.

4.1.1 預處理劃分代價的比較

與傳統意義上的預處理評價準則不同,由于在本文預處理步驟中的已知區域會引入一些半透明點,因此在某種劃分下,將未知點i的代價函數定義為

表1 顯示了上述10 種預處理方法(包含無預處理) 在3 種型號Trimap 下的總體代價比較,本文算法在各種不同型號的Trimap 下,劃分代價均為10種預處理方法的最低.其他方法中,遠距離方法(如CCM、KNN-0.01)在巨大型號Trimap 下代價較低,近距離搜索方法(如KNN-0.5)在小型號Trimap 下代價較低,過近距離搜索方法(如Nonlocal、Closed Form、Large Kernel) 在各種型號的Trimap 下代價均較高.搜索范圍適中的KNN-0.1 各種代價也較低,而KNN 算法本身效果與KNN-0.5 較為相似.

表1 9 種預處理方法與未預處理方法在3 種型號Trimap之下對所有訓練圖像的代價值之和的比較Table 1 Comparison on sum cost of all the training images within 9 pre-processing methods and no pre-processing method over three types of Trimap

圖8 顯示了從圖5 和圖6 中獲取的5 個局部圖像,對它們采用10 種預處理方法(包含無預處理)的預劃分代價.同樣,本文算法的劃分代價基本為10 種預處理方法的最低.

圖8 9 種預處理方法與無預處理方法在一些局部圖像中的代價比較(×10?4)Fig.8 Comparison on cost of several local images in 9 pre-processing methods and no pre-processing method (×10?4)

4.1.2 與后續摳像算法的聯合比較

預處理方法不僅需要單獨比較它們的漏劃分和誤劃分率,同時注意到,預處理步驟和摳像步驟終究是一個整體,預處理步驟的成敗需要最終的摳像結果反映出來,因此需要適當引入一些后續的摳像方法加以驗證.本文選擇了8 種典型的后續摳像算法,其中4 種仿射類算法(Closed Form、Nonlocal、KNN、CCM),3 種采樣類算法(Robust、Global、KL-D-Sparse),1 種特殊算法(Sparse Coded).由于在預處理步驟中同時會引入一些半透明已知點,它們也會為后續摳像步驟產生作用,因此需要對這些摳像算法做出稍許改進.1)仿射類方法按第3 節方式初始化并求解;2) 采樣類方法,假設每個未知點i的真實前景顏色Fi及背景顏色Bi與它的前景樣本點j和背景樣本點k的實際顏色相同,利用摳像式(1) 并推導可得

其中,Fj及Bk為前景和背景樣本點實際顯示的顏色,αj及αk為前景和背景樣本點的α值.之后αi通過如下一般求解公式得到

3) Sparse Coded 算法,對于未知點i,設其字典D中p點的透明度值為αp,編碼系數為βp,于是有

圖9 顯示了在巨型、大型、小型的Trimap 下10 種預處理方法針對上述8 種摳像算法的比較,因此每種型號下共有80 個結果,每個結果(即圖9 中的每個點) 是由27 個訓練圖像結果的平均MSE 計算得到.顯然,本文算法在各種不同型號的Trimap下,對8 種摳像算法的平均排名均位列10 種預處理方法的第一位,在每種單一摳像算法下的排名同樣位居前列.與上節類似,遠距離方法(CCM、KNN-0.01)、較近距離搜索方法(KNN-0.5) 分別在巨大型號和在小型號Trimap 下摳像效果較好,而過近距離搜索方法(Nonlocal、Closed Form、Large Kernel)在各種型號的Trimap 下的摳像效果都較差.搜索范圍適中的KNN-0.1 排名也比較靠前,KNN 算法摳像效果與KNN-0.5 較為相似.

與上節不同,無預處理方法的排名并不在最后,說明一些預處理中誤差過大的誤劃分對整體摳像結果影響非常大.而且,無預處理方法隨著Trimap 未知區域的變小而效果變好,說明預處理的主要功能還是對于未知區域內的絕對點的劃分.另一個有趣的現象是“自預處理”操作,即用一種算法本身進行截取,之后再采用該算法本身做出最終摳像.結果表明,這種方式并不能為該算法帶來實質性的提升.例如圖9(a) 中,若采用Closed Form 進行預處理并采用Closed Form 進行摳像,效果比單純采用Closed Form 摳像要差.從而進一步說明預處理與摳像步驟進行分離、并采用不同方法的必要性.

4.2 混合像素計算

圖9 3 種型號的Trimap 下,對所有訓練圖像摳像結果的平均MSE 比較,格式為:算法名稱排名,排名為在8 種后續摳像算法下,每種預處理方法在10 種預處理方法中的平均排名Fig.9 Average MSE Comparisons on the matting results of all the training images over three types of Trimap,where the format is [algorithm name]rank and the rank denotes the average rank for each of the pre-processing methods out of 10 over the 8 matting methods

在第4.1 節本文預處理結果的基礎上,為了與本文混合像素的計算方法相比較,本文采用了其他8 種單一混合像素的計算方法,其中包括搜索半徑5、10、20 的Nonlocal 方法,將式(15) 中min 函數分別采用min 和max 時的方法,KNN-0.5 和KNN-0.1 方法,以及Closed Form 方法(即Nonlocal 的搜索半徑為1).另外,第4.1 節處理后的預處理結果(即第2 節中的αpre?our) 也被直接引入(記為無后處理).注意,這里各方法與第4.1 節的區別是它們均采用Matting Laplacian 取代了簡單權重.

圖10 顯示了在圖7(a)～(c) 中的6 個局部圖像中采用上述10 種計算方法(包括無處理) 的MSE比較.顯然無論在硬邊界還是軟邊界,本文方法的計算效果均為最好.同時注意并未采用Matting Laplacian 的無預處理方法,該結果雖然也較為不錯,但相比上述方法中的一些結果要差,這驗證了前文提出的需要進一步引入Matting Laplacian 進行混合像素計算的基本理論.在其他方法中,對于未知區域很窄的第1、2 個例子,Closed Form、半徑為5的Nonlocal 等近距離方法尚且不錯,但在第3、4 個例子中隨著未知區域的擴大,一些半徑為10、20 的Nonlocal 方法變好,而至最后未知區域非常寬的第5、6 例子時,固定搜索半徑的方法已基本失效.然而,由于KNN-0.5 及KNN-0.1 的搜索范圍并不完全受距離因子的局限,可以根據顏色變化情況,靈活和動態選擇較遠處的像素,因此它們的效果始終較好.

圖10 對于圖7 的前6 個局部圖像及預處理后的Trimap,采用10 種方法進行摳像計算后的MSE 比較,其中前2 個例子為硬邊界,中間2 個例子為軟邊界,后2 個例子為長毛發邊緣與前景空洞,且這些例子中未知區域的寬度也逐漸增大Fig.10 MSE comparison on matting results of the first 6 local images in Fig.7 for 10 matting methods,where the first,median,and last 2 cases are hard boundaries,soft boundaries,and long hair edges and foreground holes respectively,in which the sizes of unknown regions gradually enlarge

為了顯示本文方法的綜合計算能力,與上節類似,上述10 種方法在3 種型號Trimap 下的27 幅訓練圖像的α結果的平均MSE 比較均顯示在圖11 中.同時,為了顯示α結果分別對于絕對像素和混合像素的處理能力,與圖3 類似,將各αtrue劃分為若干均勻區間,并將絕對像素區間(0～0.15、0.85～1)與混合像素區間(0.15～0.85)分別顯示.

圖11 3 種型號的Trimap 下,在各α 區間上,10 種混合像素計算方法對所有訓練圖像的摳像結果的平均MSE 比較,其中x 坐標軸中的0.15 表示0.15～0.25 區間等Fig.11 Average MSE comparisons on matting results of all the training images for 10 matting methods over 3 types of Trimap in each α range,where 0.15 in x-label denotes the range of 0.15～0.25,etc.

顯然,相對其他處理方法,本文方法除了在混合像素上計算精確外,對剩余絕對像素的計算仍然具有明顯優勢.在其他方法中,由于大寬度未知區域的例子偏多,且占據誤差計算的主導地位,因此固定搜索寬度的Nonlocal 方法始終不理想,而搜索范圍相對靈活的KNN-0.5 及KNN-0.1 方法則要好很多.一個特殊的例子是搜索半徑為1、且效果同樣不錯的Closed Form 方法,此時仍然可以理解為Matting Laplacian 在較小范圍內更為有效,因此搜索范圍的遠近也是一個微妙的平衡.

4.3 算法的整體評價

最后,我們將本文中的絕對像素劃分步驟與混合像素計算步驟合并為一個整體算法,并與9 種已經出現的仿射類算法(或變形) 做出比較.其中采用簡單權重方法的有:搜索半徑20、10、5 的Nonlocal 方法,KNN-0.01、KNN-0.1、KNN-0.5、KNN方法;采用Matting Laplacian 方法的有:CCM 和Closed Form 方法.需要注意的是,上述單層次方法是可以與本文雙層次方法相比較的,主要由于這些單層次的方法也可以視為雙層方法,即首先對自身做預處理(先運行一次該算法并做出α ≥0.95 和α ≤0.05 的絕對像素劃分)、再用自身做后處理(在預處理基礎上再運行一次該算法).如前文所述,這些算法按雙層次方法運行2 次,和只運行該算法一次的效果相近,因此可以用一次運行的上述算法模擬2 層次運行結果.

表2 顯示了上述10 種方法在3 種型號的Trimap 下的平均MSE 總體排名和分別排名,本文方法對整體和各Trimap 型號的效果均為最優.

表2 10 種仿射類方法最終摳像結果的MSE 比較Table 2 Final MSE comparison on matting results for 10 affinity based matting methods

圖12 10 種仿射類摳像方法的3 個實例Fig.12 3 Cases of matting results for 10 affinity based matting methods

圖12 顯示了各算法對于摳像效果的視覺比較,其中前2 個例子(前4 行) 顯示了2 幅訓練圖像.其中第一幅來自于圖7(d),國旗部分與前景和背景部分的顏色差異均非常大,而第2 幅的前景與Trimap的形狀均非常復雜.本文方法對這2 個例子均能處理的非常好.第3 個例子(后2 行) 顯示了1 幅測試圖像,它們經第一步預處理后的未知區域仍然非常大,且無法通過普通Matting Laplacian 計算得到,本文方法能夠獲得最好的結果.

5 討論與后續工作

1) 離散與連續的KNN 類搜索方式.本文對KNN 類算法中的3 種由遠及近的搜索范圍因子0.01、0.1、0.05,是3 種離散化的初級方式.而如何根據前景背景的重合情況,采用連續函數方式進行搜索,需要后續工作的進一步研究.

2) 簡單權重與Matting Laplacian 的適用范圍.如圖2 所示,簡單權重方法較適用在中遠距離范圍,而Matting Laplacian 方法較適用在中近距離搜索范圍,但在二者的共同區域、即中距離或偏遠的范圍上,應采用何種權重的計算方式仍顯得非常模糊,例如KNN-0.01、KNN-0.1、Nonlocal 20 等方法,對于它們確切的應用范圍仍需要進一步實驗來驗證.

3) 初始Trimap 未知區域大小的問題.介于本文在第一步預處理中對于Trimap 輸入無關的設計模式,并未考慮初始Trimap 未知區域的形狀和大小,這對于未知區域較寬的實例非常有效.然而事實上,當初始Trimap 的未知區域非常小時(如評價系統中的小號Trimap),也可以適當考慮采用更加保守的搜索方式以減少誤劃分,這種方式的摳像結果需要進一步實驗驗證.

4) 仿射類方法的局限性.盡管本文在預處理步驟中采用了直接像素,然而采樣類方法的迭代最終需要間接的方式求解,與采樣類方法相比,仍然缺乏前景和背景的直接信息,在某些場合中容易造成間接誤差的累積,而且無法像采樣類方法在算法結束后對單個點進行觀察與調試,若效果不佳,只能嘗試改進一些算法參數,并重新運行整個程序,這也影響到了該類算法的后續分析和改進.因此類似于后處理方法[26?28],本文方法仍然可以與采樣方法結合.

5) 對于大規模圖像和視頻數據的摳像應用,算法效率非常重要,今后的工作將考慮采用多核CPU、眾核GPU 等并行技術[29?30]來加速所提出的算法,以便處理大數據量的圖像和視頻.

6 結論

本文采用了“絕對像素劃分―混合像素計算”的雙層次計算方式求解仿射類圖像摳像問題.其中,第一層預處理步驟采用了基于KNN 類簡單權重的多種搜索距離的聯合方式,第二層后續摳像步驟采用了基于Matting Laplacian 的多種搜索距離的聯合方式,以充分發揮這兩種傳統摳像方法的特點.同時,本文針對全局與局部前景與背景的重合度,相應采用不同的搜索層次,并采用了以局部近距離搜索為基礎、全局搜索為補充的策略.在實驗中,本文同時引入了若干中間層次的摳像方法與本文方法進行比較,以驗證本文方法對上述2 個層次的摳像結果的有效性.最后,本文對后續探索方向進行了展望,以推進下一步的工作.

致謝

感謝趙世杰教授、徐耀群教授和白世貞教授在本文寫作過程中的支持和幫助.