局部自適應輸入控制的隨機游走摳圖

陳秋鳳，申群太

（1. 福建農林大學 計算機與信息學院，福建 福州 350002; 2. 中南大學 信息科學與工程學院，湖南 長沙410083）

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

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

1 隨機游走分割算法

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

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

2 帶輸入控制的隨機游走摳圖算法

2.1 目標函數規則化約束與輸入控制

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

結合原始的隨機游走算法，將傳統雙層摳圖算法擴展為多圖層摳圖，像素點到類種子的首達概率定義為第個圖層的不透明度，并與式(3)的相區別，此處為每個點取不同的輸入控制參數，將摳圖目標函數轉化成帶規則化輸入信息約束的擴展Dirichlet問題，則

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

2.2 輸入控制參數 取小值時轉移概率分析

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

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

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

3 輸入控制矩陣設計

3.1 信息流擴散與圖像局部模型

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

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

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

3.2 局部自適應輸入控制矩陣設計

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

4 單幀圖片摳圖

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

在低層中，圖模型按照傳統的CF算法[10]建立，相似度函數為

5 視頻摳圖

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

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

式中：Fk為顏色特征；Fl為運動向量特征，取值為

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

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

7)判斷視頻是否處理完畢或到預定處理幀數，否則轉到2)。

6 實驗結果

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

6.1 單幀摳圖實驗結果與分析

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

2)容錯性

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

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

3)定量比較

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

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

6.2 視頻摳圖實驗結果與分析

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

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

7 結束語

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