王 潔，沈 洋，包艷霞，謝志峰，林 曉

(1.麗水學(xué)院工學(xué)院，浙江 麗水 323000；2.上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200240；3.洛陽師范學(xué)院 計(jì)算機(jī)科學(xué)與工程系，河南 洛陽 471022)

最小移動二乘摳圖

王 潔1，沈 洋1，包艷霞1，謝志峰2，林 曉3

(1.麗水學(xué)院工學(xué)院，浙江 麗水 323000；2.上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200240；3.洛陽師范學(xué)院 計(jì)算機(jī)科學(xué)與工程系，河南 洛陽 471022)

交互式摳圖技術(shù)在有限的用戶交互下?lián)溉D像的前景，被廣泛地應(yīng)用在圖像及視頻編輯、三維重建等領(lǐng)域中，有極高的應(yīng)用價(jià)值。近年來的摳圖技術(shù)中，拉氏矩陣給出alpha圖上像素間的線性關(guān)系，對alpha圖的估計(jì)起到了重要作用。提出了一種改進(jìn)拉普拉斯矩陣的方法，使用移動最小二乘法替代最小二乘法，結(jié)合最近鄰(KNN)方法給出移動拉氏矩陣，并使用移動拉氏矩陣計(jì)算alpha圖。實(shí)驗(yàn)結(jié)果證明了移動拉氏矩陣的有效性。

圖像摳圖；拉氏矩陣；最小移動二乘

交互式摳圖是在有限的用戶交互下，計(jì)算前景的alpha圖，從而將前景從背景中分離出來。摳圖問題的輸入是原圖像I和用戶提供的三分圖，輸出是alpha圖及前景F、背景B，因此是典型的病態(tài)問題，需要引入假設(shè)條件求解alpha圖。

摳圖算法可分為3類：基于采樣的方法、基于傳播的方法、采樣和傳播結(jié)合的方法。其中，基于傳播的方法有著舉足輕重的作用，Levin等根據(jù)局部線性模型[1]推導(dǎo)出的拉氏矩陣給出鄰域像素的alpha值間的線性關(guān)系，被廣泛應(yīng)用在摳圖算法中。拉氏矩陣有其局限性，拉氏矩陣表示空間鄰域內(nèi)像素間的關(guān)系，但不能體現(xiàn)非鄰域間像素間的關(guān)系。拉氏矩陣建立在空間連續(xù)的假設(shè)基礎(chǔ)上，在某些前景和背景分量突變的區(qū)域，拉氏矩陣難以得到理想的效果。

本文提出一種改進(jìn)的拉氏矩陣計(jì)算方法，使用最小移動二乘法替代最小二乘法推導(dǎo)出移動拉氏矩陣。相對于最小二乘法，移動最小二乘法求解的線性條件更為準(zhǔn)確。筆者使用KNN鄰域替代空間鄰域，使得拉氏矩陣可以反映非鄰域間像素的alpha值的關(guān)系。試驗(yàn)結(jié)果表明本文方法是有效的。

1 相關(guān)工作

早期的摳圖算法例如貝葉斯摳圖基于顏色空間上的采樣，對任意未知像素，基于采樣的方法在三分圖的已知前景和背景區(qū)域中尋找最優(yōu)的前景和背景對匹配當(dāng)前像素，像素對應(yīng)的alpha值與像素的空間位置無關(guān)，該類方法不能保持alpha圖的空間連續(xù)性。在前景和背景顏色混雜時，未知像素可能和多個的前景背景顏色匹配，導(dǎo)致生成錯誤的alpha圖。近年來發(fā)展的基于采樣的方法如共享式采樣[2]假定在小鄰域內(nèi)前背景分量一致。共享式采樣為了保證結(jié)果的光滑性，并提高正確率，改進(jìn)了信任度計(jì)算方法，并對結(jié)果進(jìn)行多次平滑操作，

Rajan等人[3]提出了顏色及紋理采樣方法，不僅考慮到了像素的信息，還考慮紋理的信息，從而使得采樣更為可靠魯棒。但基于采樣的方法不能很好的保證alpha圖在空間上的連續(xù)性，也不能有效的利用空間連續(xù)性計(jì)算alpha圖，不同于基于采樣的方法基于傳播的方法充分考慮相鄰像素間的空間關(guān)系，基于傳播的方法構(gòu)造像素在alpha圖上的關(guān)系，alpha值的求解類似于alpha值從已知區(qū)域向未知區(qū)域傳播的過程，例如如泊松摳圖、隨機(jī)游走摳圖[4]、閉形式摳圖[1]等。

由于摳圖問題是典型的病態(tài)問題，因此需要alpha圖滿足一定的假定條件才可求出唯一解，例如泊松摳圖假定像素對應(yīng)的前景分量和背景分量是光滑的，在此基礎(chǔ)上閉形式算法使用，并由此給出相鄰像素間alpha圖的變化信息。閉形式摳圖假定像素對應(yīng)的前景分量和背景分量在局部小鄰域內(nèi)是不變，從而根據(jù)局部線性假設(shè)得到alpha值在局部鄰域空間上的線性關(guān)系，從而以拉氏矩陣的形式給出alpha圖在空間上的關(guān)系。舊的傳播方法如泊松摳圖隨機(jī)游走摳圖需要調(diào)整局部或全局參數(shù)，相比之下，閉形式方法不需要調(diào)整參數(shù)且效果更佳，因此被廣泛的應(yīng)用的現(xiàn)有的摳圖算法中。

閉形式摳圖方法需要求解大型稀疏線性方程，因此效率不高。閉形式方法由于基于小鄰域下的傳播模型，在某些前背景分量無法傳播到的區(qū)域無法取得良好的效果。何凱明等提出了大核摳圖方法[5]，何等發(fā)現(xiàn)拉氏矩陣在大核情況下運(yùn)用共軛梯度法求解收斂更快，而且大鄰域可以覆蓋更多的前景和背景區(qū)域，從而可以傳播更多的前景和背景分量，從而在某些有洞的區(qū)域得到較好的效果。大核方法假設(shè)內(nèi)像素的alpha值在相對較大的鄰域內(nèi)保持線性關(guān)系，其假定條件對比于小核更不易成立，因此在復(fù)雜紋理處效果不佳。Zheng等人[6]提出了基于學(xué)習(xí)的摳圖方法，將局部線性模型擴(kuò)展為局部非線性模型，從而在非線性關(guān)系下也能取得較好的效果。

由于閉形式方法獲取鄰域上像素的alpha值關(guān)系，本質(zhì)上屬于鄰域方法，不能獲取像素在非鄰域上的關(guān)系。近幾年的基于傳播的方法側(cè)重于從非鄰域上獲取alpha值的關(guān)系，Lee等人[7]提出了非鄰域摳圖方法，從非鄰域方法構(gòu)造拉氏矩陣。KNN(K Nearest Neighbor)方法[8-9]使用KNN鄰域替代空間鄰域。Chen等則提出了鄰域和非鄰域結(jié)合[10]的方法，該方法假定alpha圖能保持圖像空間上的流形結(jié)構(gòu)，從而得出alpha圖在圖像流形上的非鄰域結(jié)構(gòu)關(guān)系，再和鄰域上的拉氏矩陣結(jié)合，從鄰域和非鄰域二個方面得出新的傳播模型。

拉氏矩陣在圖像編輯中有大量的應(yīng)用[11-12]，從現(xiàn)有的摳圖方法來看，閉形式對應(yīng)的拉氏矩陣仍然在現(xiàn)有摳圖方法中起到重要的作用，而摳圖方法在一系列應(yīng)用中有著基礎(chǔ)性的應(yīng)用價(jià)值[13-14]。本文使用KNN鄰域替代空間鄰域，從而可以獲取非鄰域像素在alpha圖上的線性關(guān)系，并用移動最小二乘替代最小二乘，從而計(jì)算出移動拉氏矩陣，并得到alpha圖，實(shí)驗(yàn)結(jié)果表明移動拉氏矩陣更為有效。

2 最小移動二乘摳圖

閉形式方法基于局部線性假設(shè)，表示如下

αi=aIi+b,i∈wi

(1)

當(dāng)局部鄰域內(nèi)假設(shè)條件不成立時，特別是鄰域比較大且紋理復(fù)雜的情況下效果不佳。假設(shè)在鄰域內(nèi)alpha值滿足線性條件，不同于閉形式方法[1]使用最小二乘法求解局部線性關(guān)系，在窗口wi內(nèi)使用移動最小二乘法求解局部線性關(guān)系，表示如下

(2)

(3)

與閉形式摳圖不同處在于：在最小化式(2)和式(3)中增加了權(quán)值ω，移動最小二乘在距離當(dāng)前像素越遠(yuǎn)的地方權(quán)值ω越小，因此移動最小二乘法能求解出更準(zhǔn)確的局部線性關(guān)系，比最小二乘法求解的線性關(guān)系更為有效。ωi是鄰域wk中的權(quán)值。式(2)和式(3)可以表示為以下矩陣的形式

(4)

系數(shù)ak，bk求解如下

(5)

(6)

(7)

(8)

2.1 彩色模型下的移動最小二乘摳圖

彩色模型下類似于閉形式算法， 用式(9)表示彩色圖像各通道間的線性關(guān)系

(9)

式中：c為彩色圖像的通道數(shù)，在考慮各個通道信息后，式(2)和式(3)轉(zhuǎn)化為

(10)

對式(10)進(jìn)行化簡后，解得彩色模型下移動拉氏矩陣如下

J(α)=αLαT

(11)

(12)

式中：I為小鄰域內(nèi)所有像素對應(yīng)3×1顏色向量組成的矩陣；μk為I的Wk加權(quán)平均；Σk是I在Wk加權(quán)下的協(xié)方差矩陣。

2.2 KNN鄰域

由于拉氏矩陣不能反映像素的非鄰域關(guān)系， 在此借鑒KNN摳圖引入KNN鄰域，將拉氏矩陣中的空間鄰域擴(kuò)展到KNN鄰域，KNN空間的點(diǎn)由(R，G，B，X，Y)五維共同決定。使用KD-TREE實(shí)現(xiàn)KNN鄰域的高效查找。由于KNN鄰域反映空間非鄰域上像素間的關(guān)系。因此本文方法結(jié)合了非鄰域摳圖的優(yōu)點(diǎn)。

3 移動二乘摳圖中的大核求解

由于移動摳圖算法中，設(shè)核的大小為r，圖像像素個數(shù)為imagesize，存儲拉氏矩陣L所需要的空間復(fù)雜度為imagesize×r2，計(jì)算空間復(fù)雜度隨著核的增大而急劇增大。借鑒大核方法中[5]的計(jì)算技巧，使用改進(jìn)的共軛梯度法求解alpha值。

對于方程Lx=b，共軛梯度法的關(guān)鍵在于構(gòu)造共軛向量p，并求其對應(yīng)的殘差。共軛梯度法可以用迭代方法求解。在每次迭代過程中，新共軛向量由求解如下

(13)

共軛方向的系數(shù)求解如下

(14)

新的x值與殘差用求解如下

xk=xk-1+skpk

(15)

rk=rk-1+skLpk

(16)

在共軛梯度求解過程中關(guān)鍵的步驟在于求解向量Lp，直接求解L的空間復(fù)雜度過大，但Lp的維數(shù)為imagesize，因此需要避免直接求解L，而直接用下式求解Lp向量中點(diǎn)i對應(yīng)的元素qi

(17)

(18)

(19)

(20)

(Lp)i計(jì)算公式的正確性由以下定理保證：

定理1：式(17)計(jì)算得出的(Lp)i與利用式(12)計(jì)算出的(Lp)i是等價(jià)的。

證明：

令q=Lp，由于q與p為線性關(guān)系，因此只需要證明式(21)

(21)

(22)

此外，有

(23)

根據(jù)式(18)，并對pj做偏導(dǎo)，可得

(24)

將式(23)和式(24)代入式(22)，可得到

(25)

式(25)即式(12)中對應(yīng)的拉氏矩陣L。

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

當(dāng)前的摳圖方法中，大多使用了基于傳播和基于采樣結(jié)合的方式提高算法的準(zhǔn)確性，在此將最常見的幾種傳播方法：閉形式方法、KNN方法、基于學(xué)習(xí)的方法、大核方法進(jìn)行了比較。

從圖1可知，閉形式算法對細(xì)節(jié)處理較好，由于其傳播模型只考慮到了空間小鄰域間的信息，而Doll毛發(fā)附近的字符間有間隔，是空間上的非鄰域關(guān)系，因此alpha值不能在字符間順利傳播，也無法干凈的摳除這些字符。在plant圖中，由于植物樹葉間的空洞與三分圖中的背景分量并沒有空間上的鄰域關(guān)系，因?yàn)殚]形式方法同樣難以將背景分量傳播至植物中的空洞中。

圖1 不同算法比較

在大核方法中，由于傳播模型在相對較大的鄰域內(nèi)進(jìn)行傳播。在大核情況下，毛發(fā)附近的字符是鄰域關(guān)系，因此算法成功的摳除了毛發(fā)附近的字符，但由于植物樹葉間的空洞與背景空間距離較遠(yuǎn)，所以大核仍然無法解決植物中的空洞問題。此外，局部線性假設(shè)不易在大核時成立，因此算法對復(fù)雜紋理處理的效果不好。

由于KNN方法建立在非鄰域的基礎(chǔ)上，因此KNN方法可以在非鄰域上進(jìn)行alpha值的傳播。KNN方法因此可以在植物的空洞以及Doll毛發(fā)附近的字符處取得良好的效果。

相對于閉形式方法，KNN方法對應(yīng)的拉氏矩陣建立在全局統(tǒng)一的參數(shù)基礎(chǔ)上，因此細(xì)節(jié)處理不好。在Doll圖片中，KNN方法使得毛發(fā)周圍較為模糊，不能較好地提取毛發(fā)，毛發(fā)左邊的英文字母也沒有清除干凈。在plant圖中算法在葉子周邊沒有摳除干凈。在Plastic bag圖片中，KNN方法同樣在繩子附近留下大量噪聲。而本文方法在Doll周邊的毛發(fā)處理較為干凈，特別是英文字符全部被干凈的清除，在Plastic bag中，繩子附近處理也較為干凈。Tree圖中在有洞的區(qū)域同樣得到較好的效果。從表1的參數(shù)可以看到，net圖中的方法效果明顯好于其他方法，由于net圖中的未知區(qū)域非常大，而本文方法提供了更為準(zhǔn)確的拉氏矩陣，因此得出了較好的結(jié)果。

表1 主要摳圖方法性能對比

算法SADTrollDollElephantPlantPlasticbagNet閉形式方法1727767370135731333350大核方法1990840510118030303417學(xué)習(xí)方法1890710290138322404143KNN方法1757930480106018233347MLS方法186393039098018932027

[1] LEVIN A，LISCHINSKI D， WEISS Y. A closed form solution to natural image matting[C]//Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Los Alamitos：IEEE Press，2006：61-68.

[2] GASTAL E S L，OLIVEIRA M M. Shared sampling for real-time alpha matting[J]. Computer Graphics Forum，2010，29(2)：575-584.

[3] SHAHRIAN E，RAJAN D，PRICE B，et.al. Improving image matting using comprehensive sampling sets[C]//Proc. IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos：IEEE Press，2013：636-643.

[4] GRADY L，SCHIWIETZ T，AHARON S，et.al. Randomwalks for interactive alpha-matting[C]//Proc. 5th IASTED International Conference on Visualization，Imaging and Image Processing. Calgary：ACTA Press，2005：423-429.

[5] HE K M，SUN J，TANG X O. Fast matting using large kernel matting laplacian matrices[C]//Proc. IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos：IEEE Press，2010：2165-2172.

[6] ZHANG Z P， ZHU Q S， XIE Y Q，Learning based alpha matting using support vector regression[C]//Proc. 19th IEEE Conference on International Image Processing. Los Alamitos：IEEE Press，2012：2109-2112.

[7] LEE P，WU Y. Nonlocal matting[C]//Proc. IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos：IEEE Press，2011：2193-2200.

[8] CHEN Q F， LI D Z Y， TANG C K. Knn matting[C]//Proc. IEEE CVPR (2012). Los Alamitos：IEEE Press，2012：869-876.

[9] 沈皓.基于改進(jìn)KNN算法的AVS到H.264/AVC 快速轉(zhuǎn)碼方法[J].電視技術(shù)，2015，39(8)：35-39.

[10] CHEN X W， ZHOU D Q， ZHOU Z Y， et.al. Image matting with local and nonlocal smooth priors[C]//Proc. IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos：IEEE Press，2013：1902-1907.

[11] HE K M， SUN J，TANG X O. Guided image filtering[C]//Proc. 11th European conference on Computer vision. Aire-la-Ville：Eurographics Association Press，2010：1-14.

[12] 蔡宇文，盛斌，馬利莊.優(yōu)化分割的手繪圖像彩色化技術(shù)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2013，25(6)：774-781.

[13] 盧勝男，段沛沛，馮建利，等.基于塊匹配置信度的隧道交通背景提取算法[J].電視技術(shù)，2015，39(8)：59-63.

[14] 楊如林，丑修建，李慶，等.一種快速魯棒的紅外圖像分割方法[J].電視技術(shù)，2015，39(3)：11-15.

責(zé)任編輯：時 雯

Moving Least Square Matting

WANG Jie1，SHEN Yang1，BAO Yanxia1，XIE Zhifeng2，LIN Xiao3

(1.InstituteofTechnology，LishuiUniversity，ZhejiangLishui323000，China；2.DepartmentofComputerScienceandEngineering，ShanghaiJiaoTongUniversity，Shanghai200240，China;3.AcademyofInformationTechnology，LuoyangNormalUniversity，HenanLoyang471022，China)

Interactive alpha matting technique extracts the foreground of image with limited interaction. It is widely applied to image editing，3D construction，and has high applicative value.In recent years，the Matting Laplace matrix gives the linear relation on alpha matte，and takes important roles in alpha matting. In this paper， the Moving Matting Matrix is given， which use moving least square instead of least square method， use KNN(K nearest neighbor) model instead of local neighbor model. We solve the alpha matte by Moving Matting Matrix. Experiments prove this method is effective.

image matting； matting laplace matrix； moving least square

浙江省自然科學(xué)基金面上項(xiàng)目(LY13F020019)；國家自然科學(xué)基金重點(diǎn)項(xiàng)目(61133009)；浙江省大學(xué)生科技創(chuàng)新活動計(jì)劃項(xiàng)目(新苗人才計(jì)劃)(2013R429004)

TP391

A

10.16280/j.videoe.2015.19.006

王 潔(1992— )，女，本科，研究方向?yàn)橛?jì)算機(jī)視覺及仿真；

沈 洋(1975— )，博士，講師，本文通訊作者，研究方向?yàn)閯赢嬛谱?、圖像處理、虛擬現(xiàn)實(shí)；

包艷霞(1980— )，女，碩士，研究方向?yàn)橛?jì)算機(jī)仿真；

謝志峰(1982— )，博士，研究方向?yàn)閳D像及視頻編輯、計(jì)算機(jī)視覺、數(shù)字媒體技術(shù)；

林 曉(1978— )，女，博士，副教授，研究方向?yàn)橐曨l編輯、計(jì)算機(jī)視覺、數(shù)字媒體處理。

2015-02-22

【本文獻(xiàn)信息】王潔，沈洋，包艷霞,等.最小移動二乘摳圖[J].電視技術(shù),2015，39(19).