一種改進(jìn)的基于KNN顏色線性模型摳圖算法

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

（上海大學(xué) 影視藝術(shù)技術(shù)學(xué)院，上海 200072）

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

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

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

1 相關(guān)工作

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

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

1.1 閉形式軟摳取

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

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

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

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

1.2KNN軟摳取

2 ESCG算法對圖像進(jìn)行譜聚類

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

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

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

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

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

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

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

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

3 改進(jìn)的基于KNN顏色線性模型摳圖算法流程

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

3.1 特征選取

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

圖2 4種摳圖算法結(jié)果比較

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

圖3 本文算法更清晰實(shí)驗(yàn)結(jié)果

5 結(jié)論

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

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

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

[3] 呂巨建，戰(zhàn)蔭偉.一種改進(jìn)的Bayes摳圖算法[J].計算機(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ìn)的自然圖像魯棒摳圖算法[J].計算機(jī)工程與應(yīng)用，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] 高正偉.圖像前景提取技術(shù)研究[D].杭州：浙江大學(xué)，2008.

[12] 彭宏京，陳松燦，張道強(qiáng).一種基于局部學(xué)習(xí)的自然圖像景物提取方法[J].軟件學(xué)報，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.