局部自適應(yīng)輸入控制的隨機(jī)游走摳圖

陳秋鳳，申群太

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

摳圖是按照不透明度將感興趣物體，從圖像或視頻序列中精確分離出來的一種圖像處理技術(shù)[1-2]。摳圖是一個高病態(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)建不同層級的圖像，雖能夠提高算法運(yùn)算速度，但受超像素預(yù)分割精度的影響，高層計算出的結(jié)果在向下層傳遞標(biāo)注時也會造成錯誤的初始值。而視頻摳圖是單幀摳圖在圖像序列流上的擴(kuò)展[14-18]，幀間標(biāo)注信息的傳遞尤為重要。目前視頻摳圖多數(shù)采用半自動標(biāo)注的方式，通過幀間傳播策略將關(guān)鍵幀上的標(biāo)注信息依次向后續(xù)幀傳遞。雖有學(xué)者[15,18]利用光流信息提高了幀間連續(xù)性，但依然采用的是硬約束的方式，因此要求傳播產(chǎn)生的三分圖對前景邊界有良好的包圍性并嚴(yán)格正確，這使得后續(xù)幀的三分圖產(chǎn)生過程復(fù)雜，影響了算法的可擴(kuò)充性和快速性。針對三分圖標(biāo)注的產(chǎn)生方法，不少學(xué)者也作了進(jìn)一步的研究，但仍然是建立在初始標(biāo)注完全正確的基礎(chǔ)上[19-20]。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 單幀圖片摳圖

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

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

5 視頻摳圖

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

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

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

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

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

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

6 實驗結(jié)果

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

6.1 單幀摳圖實驗結(jié)果與分析

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

2)容錯性

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

圖3 容錯性比較Fig. 3 Comparison of fault tolerances

3)定量比較

在圖4(a)中，三分圖1是原始三分圖，三分圖2～三分圖5是原三分圖的未知區(qū)域向外擴(kuò)展10、15、20、25個像素點而得，筆畫式標(biāo)注則是手動標(biāo)注(白色前景，黑色背景)，圖4(a)的用戶標(biāo)注信息從左至右依次減少。圖4(b)、(c)為各算法在不同的用戶標(biāo)注下的MSE誤差及運(yùn)算時間。由圖4(b)知，在三分圖比較緊湊的情況下，未知區(qū)域中的點距離已知區(qū)域近，不需遠(yuǎn)距離的信息傳播就能獲得引導(dǎo)信息，CF、LB算法的MSE誤差反而比較小；但隨著用戶標(biāo)注區(qū)域的減少，CF、LB算法由于缺乏遠(yuǎn)距傳播，未知區(qū)域中的部分點得不到引導(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時的運(yùn)算時間最短，但其相應(yīng)的誤差最大，是以犧牲準(zhǔn)確度來降低運(yùn)算時間；除此之外，隨著未知區(qū)域的增加，各算法的運(yùn)算時間出現(xiàn)不同程度的增加，但本文算法的增量最小，運(yùn)算時間基本在10 s左右。

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

6.2 視頻摳圖實驗結(jié)果與分析

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

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

7 結(jié)束語

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