陳秋鳳，申群太

（1. 福建農(nóng)林大學(xué) 計(jì)算機(jī)與信息學(xué)院，福建 福州 350002; 2. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙410083）

摳圖是按照不透明度將感興趣物體，從圖像或視頻序列中精確分離出來的一種圖像處理技術(shù)[1-2]。摳圖是一個(gè)高病態(tài)問題，需要用戶提供一定的標(biāo)注信息進(jìn)行求解。目前的單幀摳圖算法都要求用戶輸入的標(biāo)注信息完全正確，并采用大數(shù)值的輸入控制參數(shù)，以迫使輸出值與用戶標(biāo)注值嚴(yán)格相同[3-12]。然而過強(qiáng)的輸入約束，使得信息傳播只與標(biāo)注區(qū)域的邊界相關(guān)，傳播距離有限；在多層摳圖算法中[13]，通過超像素來構(gòu)建不同層級(jí)的圖像，雖能夠提高算法運(yùn)算速度，但受超像素預(yù)分割精度的影響，高層計(jì)算出的結(jié)果在向下層傳遞標(biāo)注時(shí)也會(huì)造成錯(cuò)誤的初始值。而視頻摳圖是單幀摳圖在圖像序列流上的擴(kuò)展[14-18]，幀間標(biāo)注信息的傳遞尤為重要。目前視頻摳圖多數(shù)采用半自動(dòng)標(biāo)注的方式，通過幀間傳播策略將關(guān)鍵幀上的標(biāo)注信息依次向后續(xù)幀傳遞。雖有學(xué)者[15,18]利用光流信息提高了幀間連續(xù)性，但依然采用的是硬約束的方式，因此要求傳播產(chǎn)生的三分圖對(duì)前景邊界有良好的包圍性并嚴(yán)格正確，這使得后續(xù)幀的三分圖產(chǎn)生過程復(fù)雜，影響了算法的可擴(kuò)充性和快速性。針對(duì)三分圖標(biāo)注的產(chǎn)生方法，不少學(xué)者也作了進(jìn)一步的研究，但仍然是建立在初始標(biāo)注完全正確的基礎(chǔ)上[19-20]。

綜上可知，傳統(tǒng)算法采用的硬約束方式使得摳圖效果嚴(yán)重依賴于所采用標(biāo)記的準(zhǔn)確性，對(duì)用戶輸入要求高。為此，本文在隨機(jī)游走算法基礎(chǔ)上，提出了軟約束隨機(jī)游走算法(soft-constrained random walk, SCRW)，使得輸入控制矩陣能夠根據(jù)圖像顏色分布特性進(jìn)行自適應(yīng)調(diào)整。

1 隨機(jī)游走分割算法

隨機(jī)游走是一種具有馬爾科夫鏈性質(zhì)的特殊布朗運(yùn)動(dòng)，在給定的圖和一個(gè)出發(fā)點(diǎn)上，信息以一定的概率隨機(jī)地移動(dòng)到鄰居節(jié)點(diǎn)上。借助電勢(shì)理論，Grady[21]指出圖像分割過程實(shí)際上是求解帶邊界條件的Dirichlet問題。首先建立一張自然圖像對(duì)應(yīng)的無向圖模型，節(jié)點(diǎn)表示圖像中的像素點(diǎn)，表示連接兩個(gè)節(jié)點(diǎn)的邊，為相似度矩陣，表示節(jié)點(diǎn) i 與節(jié)點(diǎn)的相∑似度，定義節(jié)點(diǎn)的度矩陣，其對(duì)角元素為。給定有個(gè)像素的數(shù)據(jù)集，圖像分割的目標(biāo)是將數(shù)據(jù)集分成類。設(shè)為用戶預(yù)先指定的種子點(diǎn)集(每一類至少有一個(gè)已標(biāo)注的種子[點(diǎn))，]為未標(biāo)注點(diǎn)集，則原數(shù)據(jù)集可表示為。從每個(gè)未標(biāo)注點(diǎn)出發(fā)，分別計(jì)算該未知點(diǎn)到類標(biāo)注點(diǎn)的首達(dá)概率，并根據(jù)最大概率將該點(diǎn)劃分到相應(yīng)的類別，從而實(shí)現(xiàn)圖像的分割。記圖的拉普拉斯矩陣為 L=D-W，則

由文獻(xiàn)[21]知，隨機(jī)游走分割算法的Dirichlet問題也可寫成兩頂點(diǎn)概率差值的加權(quán)和形式：

2 帶輸入控制的隨機(jī)游走摳圖算法

2.1 目標(biāo)函數(shù)規(guī)則化約束與輸入控制

在傳統(tǒng)雙層摳圖中，其求解的目標(biāo)函數(shù)不但要求兩近鄰像素點(diǎn)間的值最大程度地符合建立的圖模型，保持局部相似性，也要求輸出值與原始給定值相一致[3-12]。因而其目標(biāo)函數(shù)通常包含有平滑項(xiàng)和數(shù)據(jù)項(xiàng)兩個(gè)部分：

結(jié)合原始的隨機(jī)游走算法，將傳統(tǒng)雙層摳圖算法擴(kuò)展為多圖層摳圖，像素點(diǎn)到類種子的首達(dá)概率定義為第個(gè)圖層的不透明度，并與式(3)的相區(qū)別，此處為每個(gè)點(diǎn)取不同的輸入控制參數(shù)，將摳圖目標(biāo)函數(shù)轉(zhuǎn)化成帶規(guī)則化輸入信息約束的擴(kuò)展Dirichlet問題，則

1)標(biāo)注信息從已知區(qū)域向未知區(qū)域擴(kuò)散時(shí)，未知區(qū)域只能接受已標(biāo)注區(qū)域的邊界信息，擴(kuò)散過程只依賴于局部相似關(guān)系建立的圖模型，而與已知區(qū)域內(nèi)部的其他信息無關(guān)。尤其是標(biāo)注信息不足時(shí)，局部模型的小窗口特性限制了輸入信息的傳播距離。

2.2 輸入控制參數(shù) 取小值時(shí)轉(zhuǎn)移概率分析

將式(4)寫成矩陣形式，則有

由文獻(xiàn)[22]可知，式(8)、式(9)正是部分吸收隨機(jī)游走算法(partial absorption random walk,PARW)的基本形式，故為吸收概率矩陣，表示信息在節(jié)點(diǎn) i 的自吸收概率，表示節(jié)點(diǎn) i 的信息被近鄰節(jié)點(diǎn)吸收的概率。根據(jù)式(8)、式(9)的分析，可得到結(jié)論1和結(jié)論2。

由于本文所提帶軟性約束條件的隨機(jī)游走SCRW與部分吸收式隨機(jī)游走算法PARW本質(zhì)上是相同的，此時(shí)圖中節(jié)點(diǎn) i 到節(jié)點(diǎn)的轉(zhuǎn)移概率為

3 輸入控制矩陣設(shè)計(jì)

3.1 信息流擴(kuò)散與圖像局部模型

在非歸一化圖模型中，若各點(diǎn)的輸入控制參數(shù)取為相同的值，即(為常量)時(shí)，圖像點(diǎn)i 的自轉(zhuǎn)移概率為，隨單調(diào)遞減。由于在圖像邊界內(nèi)部像素點(diǎn)間相似度高，節(jié)點(diǎn)在邊界內(nèi)的值比邊界處大，導(dǎo)致在邊界內(nèi)的吸收概率低于邊界，當(dāng)信息流到邊界處時(shí)將會(huì)被節(jié)點(diǎn)高概率地吸收，從而防止標(biāo)注信息的擴(kuò)散超過邊界。非歸一化矩陣之所以能保持信息大部分在邊界內(nèi)被吸收，主要得益于圖結(jié)構(gòu)上各節(jié)點(diǎn)度的差異性。

根據(jù)圖像特性[23]，在圍繞圖像點(diǎn) i 的窗口中，可將前景顏色和背景顏色的關(guān)系分為4種模型：

2)點(diǎn)-線模型：前景或是背景其中之一退化為點(diǎn)模型，在窗口內(nèi)取值為常數(shù)，不妨設(shè)前(景為)常量，背景呈線性，則、，代入線性組合公式得

3.2 局部自適應(yīng)輸入控制矩陣設(shè)計(jì)

式中：t 為預(yù)先設(shè)定的閾值，參考文獻(xiàn)[23]取值為0.002 5。式(12)表示轉(zhuǎn)換空間中方差大于閾值t的維數(shù)。

4 單幀圖片摳圖

為了提高算法的快速性，單幀摳圖采用雙層的形式。首先對(duì)圖像進(jìn)行SLIC超像素[24]分割，構(gòu)建基于超像素的圖模型，對(duì)初始的用戶輸入進(jìn)行信息擴(kuò)散得到高層摳圖結(jié)果，接著將高層結(jié)果作為低層摳圖的輸入標(biāo)注信息，在基于像素的圖模型上進(jìn)行擴(kuò)散，求得細(xì)化后的結(jié)果。本文在高層和低層都采用具有軟約束的隨機(jī)游走算法SCRW，二者的區(qū)別在于圖模型的構(gòu)造和控制矩陣H的設(shè)計(jì)上。

在低層中，圖模型按照傳統(tǒng)的CF算法[10]建立，相似度函數(shù)為

5 視頻摳圖

由于視頻摳圖處理數(shù)據(jù)量大，一般無法對(duì)每幀圖像進(jìn)行標(biāo)注，但圖像序列間具有連續(xù)性與相似性，充分利用圖像的幀間信息可以獲得單張圖像不具備的特征。本文在單幀雙層SCRW算法的基礎(chǔ)上，采用軟硬兩種約束相結(jié)合的方式進(jìn)行視頻摳圖。圖1為視頻摳圖的示意圖：左側(cè)為輸入的第幀、第 i 幀圖像及相應(yīng)的三分圖區(qū)域(背景B，前景F，未知區(qū)域U)。連續(xù)兩幀圖像間的信息傳導(dǎo)有兩種：光流映射與流形最近鄰映射。

首先計(jì)算圖像的前向與后向運(yùn)動(dòng)向量[26-27]流映射到當(dāng)前幀，并對(duì)其進(jìn)行形態(tài)學(xué)操作去除部分雜點(diǎn)，確保新產(chǎn)生的三分圖的準(zhǔn)確性。而后對(duì)圖像進(jìn)行超像素劃分進(jìn)行高層SCRW運(yùn)算，將已知區(qū)域向未知區(qū)域擴(kuò)散得到初步摳圖結(jié)果。與式(13)不同，此時(shí)具有邊連接的兩超像素相似度的計(jì)算中包含了前向、后向光流場(chǎng)向量：

式中：Fk為顏色特征；Fl為運(yùn)動(dòng)向量特征，取值為

上述FLANN搜索特征中未加入光流向量是因?yàn)椴煌瑤g的光流特征不具有可比性。與傳統(tǒng)視頻摳圖要求三分圖密實(shí)圍繞前景物體、寬度較窄不同，本文只需要勾畫前景與背景的大致區(qū)域，即只需要前背景的稀疏輸入，因而未知區(qū)域的范圍較寬。然而未知區(qū)域通常包含復(fù)雜的圖像細(xì)節(jié)，如毛發(fā)、孔洞等，且由于圖像運(yùn)動(dòng)造成的前景物體遮擋、新增前景等原因，當(dāng)前幀未知區(qū)域中的點(diǎn)與前一幀的流形匹配點(diǎn)有可能差別較大，置信度低。設(shè)為當(dāng)前幀中的點(diǎn)與其前幀最優(yōu)匹配點(diǎn)間的歐式距離，對(duì)向量取閾值，丟棄距離大于的點(diǎn)則得到流形約束圖。此時(shí)除了式(11)的兩種輸入控制參數(shù)外，流形約束對(duì)應(yīng)的輸入控制矩陣設(shè)計(jì)為

1)用光流法計(jì)算(視頻序列)中每一幀的前向、后向光流運(yùn)動(dòng)向量；

7)判斷視頻是否處理完畢或到預(yù)定處理幀數(shù)，否則轉(zhuǎn)到2)。

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

實(shí)驗(yàn)的運(yùn)行環(huán)境為：Intel Core i3雙核3.3 GHz CPU，編程環(huán)境為Matlab 2016。對(duì)比算法有CF[10]、LB[11]、KNN[12]摳圖算法。由于 CF 算法在層數(shù)大于5時(shí)，程序無法正常運(yùn)行，因此取層數(shù)level=1及l(fā)evel=5兩種水平下的結(jié)果與本文算法進(jìn)行對(duì)比，文中超像素?cái)?shù)取1 000。實(shí)驗(yàn)中定量分析圖片源于摳圖標(biāo)準(zhǔn)網(wǎng)站http://www.alphamatting.com[28]。

6.1 單幀摳圖實(shí)驗(yàn)結(jié)果與分析

圖2 全局輸入控制參數(shù)、 的影響Fig. 2 Influence of global input control parameters,

2)容錯(cuò)性

圖3是不完全正確標(biāo)注情況下，傳統(tǒng)CF算法和本文所提SCRW算法的容錯(cuò)性比較。在圖3(b)中，白色畫線為前景標(biāo)注，黑色畫線為背景標(biāo)注，中間圓圈區(qū)域內(nèi)，用戶錯(cuò)誤地將中間背景布標(biāo)注為前景。圖3(c)的傳統(tǒng)CF摳圖算法，因?yàn)椴捎脼榇笾档挠残约s束，輸出嚴(yán)格遵從輸入，最終結(jié)果仍然將中間的背景布摳選了出來；而在圖3(d)中，因?yàn)镾CRW采用為小值的軟性約束，各節(jié)點(diǎn)局部自適應(yīng)的設(shè)計(jì)使得輸入信息能夠根據(jù)圖像特征進(jìn)行自適應(yīng)擴(kuò)散，可對(duì)一些非正確的輸入進(jìn)行校正，使其符合圖像內(nèi)容，因此本文算法的容錯(cuò)性更強(qiáng)。

圖3 容錯(cuò)性比較Fig. 3 Comparison of fault tolerances

3)定量比較

在圖4(a)中，三分圖1是原始三分圖，三分圖2～三分圖5是原三分圖的未知區(qū)域向外擴(kuò)展10、15、20、25個(gè)像素點(diǎn)而得，筆畫式標(biāo)注則是手動(dòng)標(biāo)注(白色前景，黑色背景)，圖4(a)的用戶標(biāo)注信息從左至右依次減少。圖4(b)、(c)為各算法在不同的用戶標(biāo)注下的MSE誤差及運(yùn)算時(shí)間。由圖4(b)知，在三分圖比較緊湊的情況下，未知區(qū)域中的點(diǎn)距離已知區(qū)域近，不需遠(yuǎn)距離的信息傳播就能獲得引導(dǎo)信息，CF、LB算法的MSE誤差反而比較??；但隨著用戶標(biāo)注區(qū)域的減少，CF、LB算法由于缺乏遠(yuǎn)距傳播，未知區(qū)域中的部分點(diǎn)得不到引導(dǎo)信息，產(chǎn)生了較大的誤差，雖然CF算法隨著降采樣水平的增高，也具有一定的遠(yuǎn)距傳播能力，但其過強(qiáng)的輸入控制使高層中不夠準(zhǔn)確的結(jié)果在低層中產(chǎn)生誤擴(kuò)散，故其MSE誤差在高level的情況下反而更大；KNN算法雖采用非局部近鄰，但其流形近鄰的搜索特征包含空間信息，傳播距離也有限；而本文算法的高層遠(yuǎn)距離傳播及低層細(xì)節(jié)恢復(fù)能力使得算法的整體誤差最小，尤其是在用戶輸入信息不夠充分的情況下能夠取得更好的結(jié)果。在圖4(c)中，CF算法在level=5時(shí)的運(yùn)算時(shí)間最短，但其相應(yīng)的誤差最大，是以犧牲準(zhǔn)確度來降低運(yùn)算時(shí)間；除此之外，隨著未知區(qū)域的增加，各算法的運(yùn)算時(shí)間出現(xiàn)不同程度的增加，但本文算法的增量最小，運(yùn)算時(shí)間基本在10 s左右。

圖4 不同用戶輸入下各算法準(zhǔn)確率及運(yùn)算時(shí)間對(duì)比Fig. 4 Comparison of algorithm accuracy and operation time with different user inputs

6.2 視頻摳圖實(shí)驗(yàn)結(jié)果與分析

如圖5所示，是Amira視頻第79幀到第82幀的各算法運(yùn)行結(jié)果。圖5(b) 的三分圖為前幀通過光流匹配得到的，圖5(a)前背景邊界線與圖5(b)中的三分圖對(duì)應(yīng)。由圖5(a)知，隨著前景圖像的運(yùn)動(dòng)，匹配的三分圖雖然大致劃分了前景背景區(qū)域，但并沒有很好地貼近前景邊界，雖然圖5(d)中的高層軟約束SCRW能夠增加輸入信息的遠(yuǎn)距傳播能力，但因前景物體與背景的顏色存在一定的相似度，因此Amira圖像的灰色外套及眼部沒有完全地被摳選出來(圖中箭頭所示)。在圖5(e)中，由于CF算法的局部窗口作用會(huì)使得算法在確定的前景和背景間平滑過渡，未知區(qū)域中的前景物體出現(xiàn)了半透明的摳圖結(jié)果。本文所提出的帶流形匹配的SCRW算法由于存在三分圖和前幀值傳遞的軟約束，能在較大未知區(qū)域中提供引導(dǎo)信息，因此能夠取得時(shí)空更加一致的摳圖結(jié)果。

圖5 Amira視頻序列摳圖結(jié)果Fig. 5 Matting results of Amira video sequence

7 結(jié)束語(yǔ)

本文針對(duì)摳圖算法標(biāo)注準(zhǔn)確性問題，根據(jù)帶約束隨機(jī)游走算法信息流的傳播特性，提出了一種帶軟性約束的隨機(jī)游走算法，并將其應(yīng)用到單幀圖像摳圖和視頻摳圖中。實(shí)驗(yàn)結(jié)果表明，輸入控制參數(shù)對(duì)標(biāo)注信息的擴(kuò)散距離具有直接的影響，軟性約束下隨機(jī)游走具有更加優(yōu)良的容錯(cuò)特性，所提算法避免了視頻摳圖中獲取三分圖標(biāo)注的繁雜計(jì)算，為提高摳圖算法的精度提供了新的思考方向。但本文算法在大尺寸圖像和視頻上運(yùn)行緩慢，對(duì)邊界模糊圖像的處理效果不夠理想，如何進(jìn)一步提高算法的快速性和復(fù)雜圖像的處理能力仍將是未來努力的方向。