向婭玲，楊衛(wèi)英，謝志峰

（上海大學 影視藝術技術學院，上海 200072）

自然圖像摳取[1-2]是圖像處理和影視后期制作的關鍵技術之一，它的目的是對圖像未知像素的透明度進行摳取以實現(xiàn)前景的準確提取。為了得到良好的摳取效果，大多數(shù)現(xiàn)有的軟摳取方法需要用戶輸入三分圖或涂鴉作為額外標記。

現(xiàn)有的軟摳取算法大致可以歸類為基于采樣和基于傳播的方法?；诓蓸覽3-5]是應用不同參數(shù)或非參數(shù)模型，從未知像素附近選取確定的前景、背景樣本估計得出未知像素的值。當采樣的樣本包含真實前景背景像素時，這種方法才能得到好的摳取結果?；趥鞑6-9]通常假設圖像在特征空間是局部平滑的，將已知區(qū)域的約束標記傳播到未知區(qū)域來求解透明度值。當這類方法包含平滑假設，才會得到較好的實驗結果。

為了使軟摳取算法對圖像包含平滑區(qū)域或是孔洞、紋理區(qū)域都能有好的摳取效果，本文提出了一種改進的基于KNN顏色線性模型軟摳取算法[10]。首先，在特征向量參數(shù)選取上增加了一個參數(shù)——焦點信息；然后使用基于KNN的顏色線性模型將非局部原理和平滑假設相結合，使本文改進算法適用上述場景。本文采用針對大型圖的譜聚類算法，減少用戶的標記輸入。用戶只需要在聚類后的結果中選擇確定的前景、背景區(qū)域中的某一像素，就能生成三分圖。同時也可將生成的三分圖應用到本文的摳圖算法或者文獻[6-8]的算法中。

1 相關工作

圖像I可表示為前景圖像F和背景圖像B的線性組合[11-12]

式中：i（x，y）代表圖像像素i的坐標；αi代表像素i的透明度。圖像摳取算法的關鍵是精確估計透明度α值。在現(xiàn)有的眾多圖像摳取算法中，主要介紹與本文密切相關的兩個算法：閉形式軟摳取和KNN軟摳取。

1.1 閉形式軟摳取

閉形式軟摳取算法假設圖像的前景背景顏色局部平滑并且滿足顏色線性模型假設，即在一個很小的局部窗內透明度α值可由RGB空間內圖像的3個顏色通道線性表示

式中：a=1/(F -B)，b=-B/(F -B )。這個模型使得每個像素被若干重疊的局部窗覆蓋，從而用戶的輸入可以有效地進行傳播。有了這一假設，就可以定義關于透明度α的代價函數(shù)，即

目標函數(shù)對于每個未知變量都是二次型的，消除ac和b，得到了只含有未知量為α的二次目標函數(shù)

式中：L是一個N×N的摳圖拉普拉斯矩陣（N表示像素總和），可以通過閉形式對該函數(shù)求解。

1.2KNN軟摳取

2 ESCG算法對圖像進行譜聚類

目前絕大多數(shù)自然圖像軟摳取算法都是聚焦在如何得到更好的摳取結果，但求解圖像α值是一個欠約束問題，需要額外的用戶標記。這就引出一個問題：什么樣的輸入是好的用戶輸入，使得該算法能給出最精確的結果？

本 文 使 用 ESCG[13]（Efficient Spectral Clustering on Graphs）算法對圖進行譜聚類，將源圖像映射為圖G，連接其中像素節(jié)點i，j的邊的權重由核函數(shù)k（i，j）[1]給出

隨機挑選G中的d個種子點作為超級節(jié)點，計算這些節(jié)點到G中剩余點的最短距離，在運用Dijkstra算法求解最短路徑之前，首先對W矩陣中邊的權重進行如下轉化

根據(jù)最短路徑將G中所有節(jié)點分成d個子集，這些子集與d個超級節(jié)點的關系便可建立二值矩陣R∈ ?d×n，接著通過公式W?=RW 將圖像G對應的圖轉化為二分圖。二分圖對應的拉普拉斯矩陣為

將矩陣U每一行中的項看作k維空間的一個點后，可用k-means算法將所有節(jié)點劃分為k個類。

實驗通過本文算法與非局部軟摳取中使用的譜聚類算法結果比較，發(fā)現(xiàn)聚類個數(shù)選擇在12～15之間便能很好地將圖像歸類到前景/背景區(qū)域。對于比較簡單的圖像，聚類個數(shù)設置在8～10即可。而對于那些前景背景非常復雜的圖像，k值往往需要選取較大，一般在30左右。譜聚類之后，只需用戶選擇確定的前景、背景區(qū)域中某一像素來進行手動標記，那些未被標記的視為未知區(qū)域。通過這一步驟生成的三分圖以及將本文及非局部軟摳取算法生成三分圖分別作為KNN軟摳取、非局部軟摳取算法的輸入得到的結果如圖1所示。分別將本文和非局部軟摳取中譜生成的三分圖作為額外的輸入，采用相同的摳取算法得到結果為圖1d與圖1e，可以看出圖1d的摳取結果要優(yōu)于圖1e。

由上述實驗結果可知，本文的譜聚類算法比Nonlocal譜聚類算法生成三分圖的未知像素區(qū)域縮小，尤其對樹葉等包含孔洞的圖像未知區(qū)域的標注更精確，從而降低了后續(xù)估算α值的計算量。

圖1 本文與非局部軟摳取算法生成三分圖及摳圖結果比較

3 改進的基于KNN顏色線性模型摳圖算法流程

本文假設改進算法在特征空間內符合顏色線性模型。下文中主要討論特征向量的選取、使用基于KNN顏色線性模型[10]構造目標函數(shù)求解透明度α值。

3.1 特征選取

受文獻[15]的啟發(fā)，本文使用的特征矢量包括顏色、空間坐標以及焦點信息，對于一個給定的像素點i，它的特征矢量X（i）可以表示為

3.2 二次目標函數(shù)求解

閉形式軟摳取算法采用的線性模型假設像素i的前景F和背景B在局部窗內位于RGB顏色空間某一直線上，滿足這一假設的圖像才能得到好的摳取效果。而KNN算法在摳取圖像場景包括毛發(fā)等效果欠佳的原因也是因為沒有局部平滑假設。為了改善摳取結果，本文使用文獻[10]提出的基于KNN的線性顏色模型摳圖算法來進行圖像摳取。

式中：I是輸入源圖像；C是顏色通道。為了估算透明度α值，通過消除式（11）中的參數(shù)ac和b后目標函數(shù)可表示成如下閉形式函數(shù)

這是一個關于α的二次式，通過求解線性系統(tǒng)得到其值。其中，α 是一個 N×1的矩陣，L是N×N的矩陣，第（j，k）項[10]元素表示如下

式中：N是像素的數(shù)目；Σi是3×3的協(xié)方差矩陣；μi是一個3×1的矩陣，指像素i最鄰近像素Ni的顏色平均值；ε為一個數(shù)值很小的系數(shù)，本文實驗中設為10-7。當用戶提供額外的標注信息，透明度α值求解通過最小化如下帶約束的代價函數(shù)

式中：λ為一常數(shù)，在本文中取值為100；Ds是一個對角矩陣，標記了的像素在Ds對角元素中的值為1，其他像素對應的值為0；bS是一個矢量，標記了的像素對應其α值，其他未知像素對應的值為0。式（14）是二次的，它的最小化通過求解一個稀疏線性方程來實現(xiàn)。為了減少求解稀疏方程的時間復雜度，本文使用共軛梯度法。α的最優(yōu)解為

4 實驗結果

為了評估本文所提算法的摳圖性能，本文對閉形式軟摳取、KNN軟摳取以及本文改進算法的摳圖準確度進行比較。所有用于實驗的源圖像、三分圖、ground-truth等數(shù)據(jù)集都來自文獻[17]提供的網站。

表1 3種摳圖算法的性能比較

選擇文獻[18]中的4幅圖像（見圖2）進行實驗，這些圖像包含毛發(fā)、孔洞以及前背景顏色近似等場景。由表1可以看出，本文算法與其他實驗算法相比在前述場景都能得到較小的誤差值，而其他算法只能在各種適用的場景取得較好結果。

圖2 4種摳圖算法結果比較

圖2列出圖像的摳取結果，閉形式軟摳取算法在對如GT09所示的絨毛物品，包含平滑過渡的區(qū)域摳取效果在輸入的4幅圖像中是最佳，因為這區(qū)域平滑假設是適用的。KNN軟摳取算法在摳取包含孔洞的物體時性能優(yōu)于其他算法，但在計算相鄰像素的相似度時，使用數(shù)值很小的特征差值來衡量，這就導致絕大部分像素的α值趨近0或1，摳取得到的結果更接近硬分割。本文改進的算法在摳取毛發(fā)、孔洞區(qū)域的性能接近或優(yōu)于閉形式、KNN軟摳取算法，在前景、背景相似的區(qū)域摳取效果在這4種算法中是最佳的。圖3為使用本文算法對GT16圖像摳取結果的放大顯示，它在這4種算法得到的結果是最佳的。

圖3 本文算法更清晰實驗結果

5 結論

本文在基于KNN顏色線性模型摳圖算法的基礎上提出了一種改進算法。該方法通過譜聚類生成三分圖，減少用戶輸入；考慮了非局部原理，對孔洞、紋理區(qū)域能得到很好的摳取結果；在特征空間考慮平滑因素，對毛發(fā)區(qū)域也能取得平滑的效果。由于構造特征向量時添加了焦點特征，這在圖像前景背景某些局域顏色信息近似時十分有效。上述實驗表明所提算法能比本文實驗的其他幾種算法得到更好的結果。

[1] 于晏平.基于能量和取樣的圖像摳取算法研究[D].北京：北京交通大學，2012.

[2] 關宇東，韓媞.復雜背景下基于分割逼近法的摳像技術研究[J].電視技術，2007，31（7）：75-76.

[3] 呂巨建，戰(zhàn)蔭偉.一種改進的Bayes摳圖算法[J].計算機工程，2010，36（3）：213-214.

[4]SHAHRIAN E，RAJAN D.Weighted color and texture sample se?lection for iamge matting[C]//Proc.2012 IEEE Conference on Computer Vision and Pattern Recognition.Washington，DC：IEEE Computer Society，2012：718-725.

[5] 黃睿，王翔.改進的自然圖像魯棒摳圖算法[J].計算機工程與應用，2013，49（12）：136-139.

[6] LEE P，WU Y.Nonlocal matting[C]//Proc.2011 IEEE Conference on Computer Vision and Pattern Recognition.Washington，DC：IEEE Computer Society，2011：2193-2200.

[7]CHEN Q F，LI D，TANG C K.KNN matting[J].IEEE Trans.Pat?tern Analysis and Machine Intelligence，2013，35（9）：2175-2188.

[8] LEVIN A，LISCHINSKI D，WEISS Y.A closed form solution to natural image matting[J].IEEE Trans.Pattern Analysis and Ma?chine Intelligence，2008，30（2）：228-242.

[9] SUN J，JIA J，TANG C K.Poisson matting[J].ACM Trans.Graph?ics，2004，23（3）：315-321.

[10] JIN M，KIM B K，SONG W J.KNN-based color line model for image matting[C]//Proc.2013 IEEE International Conference on Image Processing.Melbourne：IEEE Press，2013：2480-2483.

[11] 高正偉.圖像前景提取技術研究[D].杭州：浙江大學，2008.

[12] 彭宏京，陳松燦，張道強.一種基于局部學習的自然圖像景物提取方法[J].軟件學報，2009，20（4）：834-844.

[13] LIU J，WANG C，DANILEVSKY M，et al.Large-scale spectral clustering on graphs[C]//Proc.23rd International Joint Confer?ence on Artificial Intelligence.Barcelona：AAAI Press，2013：1486-1492.

[14]SUBBARAO M，CHOI T S，NIKZAD A.Focusing techniques[J].Optical Engineering，1993，32（11）：2824-2836.

[15] SHI Y，AU O C，PANG J，et al.Color clustering matting[C]//Proc.2013 IEEE International Conference on Mutimedia and Ex?po（ICME）.[S.l.]：IEEE Press，2013：1-6.

[16] MUJA M，LOWE D G.Fast approximate nearest neighbors with automatic algorithm configuration[C]//Proc.4th International Con?ference on Computer Vision Theory and Applications.[S.l]：IN?STICC Press，2009：331-340.

[17]RHEMANN C，ROTHER C，WANG J，et al.A perceptually moti?vated online benchmark for image matting[C]//Proc.2009 IEEE Conference on Computer Vision and Pattern Recognition.Wash?ington，DC：IEEE Computer Society，2009：1826-1833.