基于超像素和隨機游走的交互式分割算法

收稿日期：2021-10-29；修回日期：2021-12-15

基金項目：國家自然科學基金青年科學資助項目（61502065）；重慶市科委基礎科學與前沿技術研究資助項目（cstc2018jcyjAX0287，cstc2015jcyjBX0127）；重慶市教委人文社科研究重點資助項目（17SKG136）；重慶理工大學研究生創新資助項目（clgycx2020090，clgycx2020096，clgycx20203112）

作者簡介：龍建武（1984-），男，湖北恩施人，副教授，碩導，博士，主要研究方向為圖像處理、機器學習；栗童（1997-），男（通信作者），河北邯鄲人，碩士研究生，主要研究方向為數字圖像處理、圖像摳圖（907822778@qq.com）；朱江洲（1994-），男，湖南長沙人，碩士研究生，主要研究方向為數字圖像處理、圖像平滑；宋鑫磊（1995-），男，山東菏澤人，碩士研究生，主要研究方向為數字圖像處理、醫學圖像分割；石美鳳（1989-），女，湖南湘西人，碩導，博士，主要研究方向為智能計算.

摘 要：交互式圖像分割通過先驗信息指導獲取圖像中人們感興趣的部分，但是現有算法無法在效率和精度上實現平衡。為了解決此問題，提出了一種基于超像素和隨機游走的快速交互式分割算法（random walk on superpixel，SPRW）。首先，將圖像預分割為具有局部相似性的超像素區域，使用像素顏色均值對超像素區域表示；其次，根據人工標記的先驗信息建立F-B圖結構，擴展隨機游走的范圍，并使用隨機游走的方法求解，獲得硬分割結果；最后，針對分割結果的邊界不光滑問題，提出改進的摳圖算法（fast robust matting，FRB）進行二次處理，得到軟分割結果。在BSD500和MSRC數據集上的實驗證實，所提出的硬分割方法與其他算法在時間和平均交并比等指標上有較大優勢；在Alpha Matting數據集上的實驗充分證實所提出的軟算法在提高效率的同時精度也有一定的提升；此外，在生活照更換背景的實驗上展現了該算法的應用價值。

關鍵詞：超像素； 交互式圖像分割； 隨機游走； 窄帶區域

中圖分類號：TP391.41"" 文獻標志碼：A

文章編號：1001-3695（2022）06-050-1891-06

doi：10.19734/j.issn.1001-3695.2021.10.0456

Interactive segmentation algorithm based on superpixel and random walk

Long Jianwu， Li Tong， Zhu Jiangzhou， Song Xinlei， Shi Meifeng

（College of Computer Science amp; Engineering， Chongqing University of Technology， Chongqing 400054， China）

Abstract：Interactive image segmentation uses a priori information to guide the acquisition of the people’s interesting parts of an image， but existing algorithms cannot balance efficiency and accuracy. To solve this problem， this paper proposed a fast interactive segmentation algorithm based on superpixel and random walk（random walk on superpixel， SPRW）. Firstly， it pre-segmented the image into superpixel regions with local similarity and used pixel colour averages to represent the superpixel regions. Secondly， it built the F-B graph structure based on manually labelled a priori information and extended the range of the random walk， obtained the hard segmentation results using the random walk solution. Finally， this paper proposed the improved matting algorithm （fast robust matting， FRB） for the unsmooth boundaries of segmentation results and performed the secondary process to obtain soft segmentation results. Experiments on the BSD500 and MSRC datasets confirm that the proposed hard method is superior to other algorithms in terms of time and average intersection ratio， while experiments on the Alpha Matting dataset demonstrate that the proposed soft algorithm improves efficiency and accuracy. In addition， the experiment of replacing the background of a life photograph demonstrates the application value of the proposed algorithm.

Key words：superpixel; interactive image segmentation; random walk; narrow band area

0 引言

圖像分割是圖像處理中的關鍵一環，在增強對圖像的理解上起著重要作用，并且已經在醫學圖像處理［1～5］、機器視覺［6～8］、目標追蹤［9，10］中得到了廣泛的應用。根據是否使用先驗信息可以將圖像分割算法分為有監督和無監督兩類。由于組成自然圖像物體的復雜性和內容的多樣性，再加上人們在獲取圖像前景區域時有著強烈的主觀性，所以有監督的方式比無監督的方式有更強的現實使用價值。

近年來，通過人工標記部分前景背景，為圖像分割提供先驗信息然后進行圖像分割的機器學習方法相繼提出。Boykov等人［11］提出基于圖割的交互式圖像分割算法graph cut，將圖論知識引入到分割中，通過設置邊界約束和區域約束并利用能量函數實現全局最優的圖像分割；Grady［12］提出在圖像分割領域的隨機游走算法，使用人工標記的種子點在圖像上進行隨機游走最終得到分割結果；Li等人［13］提出基于區域的交互式分割算法，先將圖像預處理為多個同質區域，將標記的區域通過聚類算法聚類成64簇，分別對每個區域計算局部相似性和到標記區域的相似權重，最后使用graph cut進行求解；Blake等人［14］使用混合高斯模型代替灰度直方圖對前景背景進行建模，充分利用了彩色圖像中的顏色信息；Rother等人［15］提出的GrabCut算法通過迭代更新高斯模型參數并且改進了交互式標記方式，使用矩形框標記目標對象區域使得分割結果更加準確；Hua等人［16］在GrabCut的基礎上改進提供先驗信息的方式，在人工標注的基礎上添加了感興趣區域的選擇，避免人工標注框中背景的影響；Price等人［17］在交互式分割中通過使用邊緣信息降低了種子點選取的重要性，在提高分割精度的同時減少了用戶的交互信息；Jian等人［18］通過引入自適應的約束傳播，使得人工提供的先驗信息可以更加有效地傳播到整個圖像中；韓守東等人［19］使用超像素替代像素點，并建立類似GrabCut的圖結構進行圖像分割；Cerrone等人［20］設計正反饋系統迭代地從有限的用戶標記中學習先驗信息；Casaca等人［21］提出基于拉普拉斯的方法，保持局部像素標簽相似，并在圖像區域邊界進行跳躍連接，以此來增大擴散過程。

基于深度學習的交互式分割［22～26］方法由于其出色的性能在近些年較流行，但是高昂的訓練成本和對硬件設備的高要求等缺點無法避免，而傳統的機器學習方法在對少量圖片處理時則展現了巨大的優勢。通過分析發現，以上方法主要呈現以下三方面不足：a）對人工標記信息的利用不夠充分，缺乏考慮標記信息對局部和全局的影響；b）大多以像素點為基本單元，導致計算效率低下；c）所得分割結果都為離散結果，對邊界模糊的圖片處理效果較差。針對以上問題，本文提出一種基于超像素的交互式硬分割算法。首先使用超像素分割預處理，得到超像素塊代替像素點；然后利用交互式標記超像素塊的方式為圖像提供前景背景的先驗信息，建立F-B圖結構；最后使用隨機游走的方法求解未知點的標簽。為了處理模糊邊界分割不準確的問題，本文提出一種改進的魯棒性摳圖算法對硬分割結果進行細化和修正，得到更加平滑的軟分割結果。

本文的主要貢獻是：提出了一種基于超像素的交互式快速圖像分割算法，提高了分割的效率；提出了一種使用超像素建立F-B圖結構的方法，使標記信息可以影響到全圖；改進了魯棒性摳圖的搜索范圍，使用KD樹在相關范圍內查找，在效率和精度上有著較好的表現。

1 隨機游走算法

1.1 基于隨機游走的圖像分割算法

隨機游走的圖像分割算法以像素點為基本處理單元，使用用戶標記提供先驗信息進行交互式分割。該方法將圖像建模成一幅加權無向圖G=（V，E），V為圖像中的像素點集，E為圖像中相鄰像素點構成的邊集。Wij為相鄰像素點i和j相似性權重，使用高斯函數進行計算可得

Wij=exp－‖gi－gj‖22σ2（1）

其中：gi表示像素點i的灰度值或顏色值;σ為參數。隨機游走在經過每個像素點的概率可以轉換成求解狄克雷問題，狄克雷積分公式如下：

D［xn］=12∑（i，j）∈EWij（xi－xj）2=12xTLx（2）

其中：L為使用相似性權重Wij構建的拉普拉斯矩陣。對于用戶標記信息，記M為標記點集，U為未標記點集，可以將拉普拉斯矩陣分解成如下形式：

L= LMRRTLU（3）

結合式（2）（3），可以將狄克雷積分公式變換成

D［xn］=12 ［xTM xTU］ LMR

RTLUxMxU（4）

對式（4）求微分并令導數為0，可得

LUxU=－RTxM（5）

其中：xU表示待求的所有未標記像素點到已標記像素點的概率值。通過對比未標記點到達已標記前景和背景點的概率值即可分配標簽，完成圖像分割。

1.2 基于隨機游走的魯棒性摳圖算法

在摳圖中，將一幅圖像建模成前景和背景的線性組合［27］，如式（6）所示，其中針對圖像中的一個像素點i，所觀察到的顏色Ci是由前景顏色Fi和背景顏色Bi的凸組合形成的，ai為凸組合的權值，ai∈［0，1］，被稱為前景的半透明度。對一幅彩色圖像，已知Ci、未知FR，G，Bi和BR，G，Bi，求解ai，但是此問題是欠定的，即不可解的。現有的方法通過取樣的方式從前景和背景中選取樣本來估計未知點的a值。

Ci=aiFi+（1-ai）Bi（6）

Wang等人［28］提出了基于隨機游走的摳圖算法，其使用原圖和三分圖作為輸入，三分圖是由前景、背景和邊緣不確定區域組成的提供先驗信息的圖像，并在三分圖中靠近不確定區域的前景和背景內分別隨機挑選N個樣本，形成N×N個樣本對;對于未知像素點顏色C，使用取樣的前景點Fi和背景點Bj估計該未知點的值。

=（C－Bj）（Fi－Bj）‖Fi－Bj‖2（7）

使用下式計算樣本對的估計誤差：

Rd（Fi，Bj）=‖C－（Fi+（1－）Bj）‖‖Fi－Bj‖（8）

為了評估所選樣本對，首先使用w（Fi）=exp{－‖Fi－C‖2/D2F}和w（Bj）=exp{－‖Bj－C‖2/D2B}計算樣本點權重，D2F和D2B分別為所選樣本點到未知像素點的最大歐氏距離，其次使用式（9）計算所選擇樣本對的置信度f。選擇置信度較高的前三個樣本計算出的半透明度值作為未知點估計的值。

f（Fi，Bj）=exp－Rd（Fi－Bj）2·w（Fi）·w（Bj）σ2（9）

為了獲取最后的結果，對未知區域建立F-B圖。設置數據項和平滑項，數據項中的權重計算如下：

W（i，F）=γ［fii+（1-fi）δ（igt;0.5）］（10）

W（i，B）=γ［fi（1－i）+（1-fj）δ（ilt;0.5）］（11）

其中：f為權重系數;定義δ（·）為指示函數，若igt;0.5，則δ（igt;0.5）為1，反之為0。平滑項中的權重計算如下：

W（i，j）=∑（i，j）∈wkk19（1+（Ci－μk）T（Σk+ε9I）－1（Cj－μk））（12）

其中：wk為3×3鄰域;μk和Σk分別為鄰域的顏色均值和協方差矩陣。

2 SPRW和FRB算法

為了提高交互式分割的性能和效率，準確且高效地從一幅圖像中提取感興趣目標，本文設計出一種基于超像素和隨機游走的交互式硬分割算法SPRW和軟分割算法FRB，算法流程如圖1所示。首先通過預分割將圖像處理成超像素塊；然后交互式標記部分前景背景，建立F-B圖結構，定義硬分割能量函數；最后對能量函數化簡，解稀疏矩陣得到硬分割結果。在目標物邊界模糊的圖片上，硬分割的結果無法準確地進行表示，且在邊界上略顯粗糙。因此針對上述情況的邊界部分進行二次處理，首先使用形態學操作對硬分割的結果進行膨脹腐蝕形成一個窄帶區域；其次在窄帶區域建立F-B圖結構，定義軟分割能量函數；最后對能量函數進行化簡，解稀疏矩陣，計算出窄帶區域像素點的前景半透明度值，得到軟分割結果。

2.1 基于超像素和隨機游走硬分割算法

2.1.1 超像素預處理

超像素是像素的一種超集，是圖像具有局部相似性的集合。本文通過超像素分割將圖像劃分成具有相似性質的區域，使用超像素代替整個區域中的所有像素點。超像素的使用不僅簡化了圖像內容，而且降低了后續處理步驟的復雜程度。在本文中使用兼具高效性和準確性的SLIC［29］算法來提取超像素，在進行超像素預處理后，圖像I由超像素表示，即I=（S1，S2，…，SK），K表示超像素塊數，Si表示超像素塊i;每個超像素塊使用塊內像素點的顏色均值進行表示，記為Si=（i，i，i）。圖2（a）（b）為一測試圖像及其超像素分割結果。

2.1.2 用戶標記

在超像素圖上進行標記，很大程度上減少了用戶進行交互的難度，標記超像素塊內的一個像素點即可對一個超像素塊進行劃分，并且在同等標記下，超像素圖所標記的信息量要遠遠大于在像素圖中所標記的信息量。圖2（c）為人工交互式標記前景背景的結果，其中紅色標記部分為前景，藍色標記部分為背景（參見電子版）。令前景標簽為1，背景標簽為0，得到前景超像素集和背景超像素集，分別記為ΩF和ΩB，其中ΩF∪ΩB=ΩM，并應滿足條件ΩM∩ΩU=，ΩM∪ΩU=I。

2.1.3 建立F-B圖結構

在進行超像素預處理后，圖像分割問題可以從對像素點的二分類問題上升為對超像素塊的二分類問題，本文將超像素圖映射為無向加權圖G=（V，E，W），其中V為超像素點集合，E表示相鄰超像素之間無向邊集合，W為相鄰超像素的相似性權重矩陣。為了更好地融合超像素圖的區域信息和標記信息，定義能量函數為

J（x）=J1（x）+J2（x）（13）

其中：J1為超像素平滑項，用于約束超像素鄰居區域標簽一致；J2為超像素區域數據項，用以約束超像素塊與最相近的標記點標簽一致。如圖3所示，建立與平滑項和數據項對應的圖結構。

在相鄰超像素塊之間計算超像素平滑項J1：

J1（x）=12∑（i，j）∈EWij（xi－xj）2（14）

其中：Wij為相鄰超像素塊的相似性權重，使用式（15）計算。

Wij=exp－‖Si－Sj‖22σ2（15）

其中：Wii=∑j∈υWij，υ為i的鄰域集合。為了使標記信息傳播到每個超像素點，對每個未標記的超像素點都建立與最相似標記點之間的聯系，使用式（16）選擇前景點集和背景點集中最相似的點并建立連接關系。

dmi=minm∈{F，B}‖Si－Sm‖2（16）

其中：i∈ΩU;dmi計算未標記點到標記點的最短距離，并建立連接關系，由此可得超像素數據項為

J2（x）=12∑i∈V，m∈{F，B}Gim（xi－bm）2（17）

其中：bm為標記點的標簽，令bF=1，bB=0。結合式（16）計算未知點i到標記點的相似性權重Gim：

Gim=exp－dmi2σ2（18）

2.1.4 隨機游走求解

聯合式（13）（16），可以將式（12）的能量項寫成

J（x）=12∑（i，j）∈EWij（xi－xj）2+12∑i∈V，m∈{F，B}Gim（xi－bm）2

s.t. xi=1 i∈ΩF

0i∈ΩB （19）

使用約束條件構建拉格朗日函數，經矩陣表示并化簡為

J（x）=12xTLx+12（x－1）TGF（x－1）+

12xTGBx+12λ（x－b）TD（x－b）（20）

其中：L為在平滑項中使用局部相似性構建的拉普拉斯矩陣，如式（21）所示;Gm是使用相似性權重Gim構建的對角矩陣，1是全部為1的向量。

Lij=Wii" i=j

-Wiji，j∈E

0others（21）

D=diag（d1，d2，d3，…，dK）為標記向量，且

di=1 i∈ΩM

0i∈ΩU（22）

令J（x）x=0可得

（L+λD+GF+GB）x=λDb+GF1（23）

求解上述稀疏線性系統，根據屬于前景或者背景的概率的大小分配標簽，即可得到硬分割結果。

2.2 邊界窄帶區域的軟分割算法

在一些圖像上由于目標物運動或邊界為毛發，邊界像素點大多為混合像素，即前景和背景的混合，所以在邊界上應使用軟分割進行處理，使用離散的0-1分割必然會導致在邊界上不平滑。圖4為一例圖的硬分割與軟分割結果對比，硬分割結果中的邊緣細節處理較為粗糙。因此在這些圖像上采用硬分割的方式無法有效地表示圖像。本文提出了基于魯棒性摳圖的軟分割算法FRB對邊界進行精細化處理。

魯棒性摳圖算法［27］在前景背景中隨機地選取樣本對，使用大量的計算進行挑選，嚴重影響了摳圖的效率，而且挑選樣本的隨機性制約了像素點半透明度值的準確性。本文對取樣方式和范圍進行了改進，以此來提高算法的運行效率。

首先對2.1.4節的結果提取邊界，使用形態學操作擴充邊界區域，如圖5（a）所示，使其邊界區域至少包含所有的邊界混合像素部分。針對分割結果可能存在漏分導致無法覆蓋所有邊界的情況，可以手工增加未知區域，形成新的窄帶區域。從靠近窄帶區域的前景和背景中構造前景點集和背景點集，如圖5（b）中紅色為前景點集，藍色為背景點集（見電子版），并將其作為先驗信息。為了充分利用像素點的顏色信息和空間信息，使用［l，a，b，x，y］五維特征分別在前景和背景點集上建立KD樹。對于每個窄帶區域的像素點，在KD樹上查詢與其在顏色與空間位置上最相似的點，作為其取樣的前景背景點對，并對窄帶區域建圖，如圖5（c）所示。定義未知點到前景和背景點的權重如下：

g（Fi）=exp－‖Fi－Ci‖22σ2（24）

g（Bi）=exp－‖Bi－Ci‖22σ2（25）

其中：Ci為未知像素點i的顏色特征;Fi和Bi是Ci經過KD樹查找的在顏色—空間特征上最相似的點的顏色特征，使用式（9）計算所選擇樣本的置信度。為了更好地解決邊界混合像素的軟分割問題，定義如下能量函數：

J（a）=J1（a）+J2（a）（26）

其中：J1和J2分別為平滑項和數據項，平滑項J1保證局部半透明度值平滑，使用式（27）計算。

J1（a）=12∑（i，j）∈EWij（ai－aj）2（27）

其中：Wij為相鄰像素點之間的相似性權重，使用式（12）計算。數據項J2約束像素點的半透明度值和估計值一致，使用式（28）計算。

J2（a）=12∑i∈VU，m∈{F，B}Gim（ai－bm）2（28）

其中：VU為窄帶區域像素點;Gim為使用式（9）（24）（25）結合式（10）（11）計算所得的相似性權重。式（26）經整理可得

J（a）=12∑（i，j）∈EWij（ai－aj）2+12∑i∈VU，m∈{F，B}Gim（ai－bm）2

s.t. ai=1 i∈ΩF

0i∈ΩB（29）

使用約束條件構建拉格朗日函數，經矩陣表示并化簡為

J（a）=12aTLa+12（a－1）TGF（a－1）+

12aTGBa+12λ（a－b）TD（a－b）（30）

其中：L為使用Wij構建的拉普拉斯矩陣;G是使用Gim構建的對角矩陣;D為標記向量，與上節含義一致。

令J（a）a=0可得

（L+λD+GF+GB）a=λDb+GF1（31）

求解此線性稀疏系統即可得出最終軟分割結果，本節軟分割的計算和硬分割的計算基本一致，主要區別在于圖模型的建立、權重的計算方法上。

3 實驗結果和分析

3.1 實驗環境

本文算法在Core i5 四核3.40 GHz 的 CPU 以及8 GB 內存的 PC 機上實現，使用Visual Studio 2017 結合 OpenCV開源視覺庫和Eigen庫并使用C++語言實現。其中在超像素預分割階段，為了使得超像素分割可以更好地適合圖像，設置超像素個數為C/400，C為圖像大小。

3.2 定性分析

為了驗證所提出硬分割算法的有效性，本文選取BSD500數據集進行實驗，BSD500數據集是伯克利大學提供的用于圖像多目標分割和邊緣檢測的數據。使用文獻［19］的方式進行人工填充標記構建真值，圖6為人工標記真值過程。

為了展現所提出算法的優勢，使用GrabCut［16］、Graph Cut［11］、LS ［13］、RW［12］、NRW［30］、f-BRS［25］、RITM［26］、LC［21］交互式算法在相同的環境下與本文硬分割算法進行視覺和定量指標的對比。在使用GrabCut算法時，在圖像中目標真值的最外側使用矩形框標記;在使用f-BRS和RITM算法時，對前景和背景交互式標記像素點，交互標記直到結果收斂。圖7是與其他算法在相同標記下的分割結果，通過觀察可以得出，本文的硬算法相比其他算法可以更好地保留圖像中目標物的細節，并且保證目標物體分割的完整性。

3.3 定量分析

為了能夠定量地評價所提出的硬分割算法，本文使用像素準確率（pixel accuracy，PA）、類別平均像素準確率（mean accuracy precision，MAP）、平均交并比（mean intersection over union， mIoU）和時間復雜度指標來定量分析實驗結果。由于對前景背景都進行了標記，所以分別計算前景分類平均像素準確率（CPA（FG））和背景的平均像素準確率（CPA（BG））。表1是在BSD500數據集上進行測試的定量結果。其中在使用超像素分割階段，進行處理的平均時間為0.24 s。由于圖片大小不一致，導致處理時間有差異，但在每張圖片上的處理時間，本文方法對比于其他方法仍有較大優勢。

表2是在BSD500數據集上與其他算法的對比結果，可以觀察到本文算法在運行時間上較其他算法有了大幅度的降低，算法運行時間可以達到0.056 s，并且在PA、CPA（FG）和mIoU指標比較上優于其他算法，在CPA（BG）指標的比較上與RW算法接近，實現了在效率和精度上的統一。

另外，為了進一步驗證本文算法相比其他經典算法的優勢，本文使用MSRC［11］數據集進行實驗。MSRC是微軟公司提供的50張涵蓋范圍較廣且有精細標注的分割數據集。在MSRC數據集上的平均超像素預處理時間為0.28 s。如表3所示，本文硬分割算法在保持了較快處理速度的情況下，在PA、CPA（BG）和mIoU的指標比較上仍高于其他算法。

3.4 針對窄帶區域的軟分割實驗

目標物體的邊界處理一直都是圖像分割中重點研究的問題，而硬分割的結果無法精確地表示邊界的混合像素部分，本文提出了改進的魯棒性摳圖算法，使其效率大幅度提高，能夠對圖像邊界進行更加高效的處理。從圖4和8可以看到，本文所提出的軟分割算法不僅可以糾正由于超像素預處理累積的分割錯誤或者硬分割造成的誤分區域，還可以優化分割結果，使得邊界在視覺感知上更加平滑。

為了更好地驗證本文所改進摳圖算法的有效性，首先使用本文的硬分割獲取圖像中目標物的主體，然后使用改進的摳圖算法對邊界部分處理，得到軟分割結果。在使用單張圖片輸入的情況下，克服了以往摳圖算法需要輸入三分圖的弊端。圖9為本文算法在Alpha Matting［31］數據集的結果，可以觀察到目標物的主體被完整地提取，并且很好地保留了目標物體的細節和紋理特征，在毛發部分的處理結果上有著不錯的表現。為了能夠定量地分析所提出算法的優勢，使用絕對誤差（SAD）、均方誤差（MSE）和運行時間（time）指標對算法進行定量實驗。從表4可以觀察到，與Closed Form Matting［32］、KNN Matting［33］、Information Flow Matting［34］相比，本文的軟分割算法在大幅度降低時間的基礎上，絕對誤差和均方誤差指標仍低于其他算法，并且本文提出的分割算法使用一張圖片輸入即可完成摳圖，無須三分圖的輸入。

3.5 其他應用

圖像合成在現實生活中有著廣泛的應用，如在影視制作中的特效制作等，其中關鍵的一步就是將圖像中所感興趣的部分提取，再與其他背景進行融合。為了展示本文算法的現實應用價值，對DIM［35］數據中的人像數據進行實驗，結合本文所提出的硬分割與軟分割算法，實現了使用單張圖片完成摳圖的任務。首先使用本文算法進行人像前景半透明度遮罩的提取，然后與其他背景進行融合，最終完成“換底”操作。圖10展示了經過本文算法處理而實現“換底”的圖像，可以觀察到在目標人像的主體部分和頭發部分提取比較完整，合成圖像在視覺感知上也較為平滑。

4 結束語

基于超像素和隨機游走算法，本文提出一種快速交互式分割算法，使用超像素預分割將圖像用超像素塊表示，根據超像素塊顏色特征進行相似度度量，結合人工標記的先驗信息構建F-B圖結構，未知點與標記點直接連接，降低傳播誤差。針對邊界硬分割不準確的問題，使用改進的魯棒性摳圖算法細化并修正硬分割的結果，得到軟分割的結果。通過實驗表明，本文算法與其他算法相比有較大提升，在一定程度上實現了效率和精度的平衡，并在生活照“換底”實驗中表明本文算法有較大的現實應用價值。在未來的工作中，將從增加超像素分割的準確性和改進超像素塊之間的相似性度量出發，增強算法的泛化能力。

參考文獻：

[1]Suzuki C T N， Gomes J F， Falcao A X， et al. Automatic segmentation and classification of human intestinal parasites from microscopy images［J］.IEEE Trans on Biomedical Engineering，2013，60（3）：803-812.

［2]Huang Robin， Li Ang， Bi Lei， et al. A locally constrained statistical shape model for robust nasal cavity segmentation in computed tomography［C］//Proc of the 13th International Symposium on Biomedical Imaging.Piscataway，NJ：IEEE Press，2016：1334-1337.

［3]Dong Chunhua， Zeng Xiangyan， Lin Lanfen， et al. An improved random walker with Bayes model for volumetric medical image segmentation［J］.Journal of Healthcare Engineering，2017，2017（10）：6506049.

［4]Chen Xinjian， Pan Lingjiao. A survey of graph cuts/graph search based medical image segmentation［J］.IEEE Reviews in Biomedical Engineering，2018，11（1）：112-124.

［5]南麗麗，鄧小英.幾何距優化質心結合隸屬度約束RFCM的腦MRI圖像分割算法［J］.計算機應用研究，2019，36（11）：3516-3520.（Nan Lili， Deng Xiaoying. RFCM magnetic resonance brain image segmentation algorithm based on geometric distance optimization of centroid and membership constraints［J］.Application Research of Computers，2019，36（11）：3516-3520.）

［6]Garcia-Rodriguez J， Quevedo M A C. Robotic vision： technologies for machine learning and vision applications［M］.Hershey，PA：IGC Global，2012.

［7]Casaca W， Motta D， Taubin G， et al. A user-friendly interactive image inpainting framework using Laplacian coordinates［C］//Proc of IEEE International Conference on Image Processing.Piscataway，NJ：IEEE Press，2015：862-866.

［8]Karayev S， Fritz M， Darrell T. Anytime recognition of objects and scenes［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Washington DC：IEEE Computer Society，2014：572-579.

［9]Redmon J， Divvala S， Girshick R， et al. You only look once：unified， real-time object detection［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Washington DC：IEEE Computer Society，2016：779-788.

［10]Dai Lingzheng， Yang Jian， Chen Liang， et al. Category-specific object segmentation via unsupervised discriminant shape［J］.Pattern Recognition，2017，64（4）：202-214.

［11]Boykov Y， Veksler O， Zabih R. Fast approximate energy minimization via graph cuts［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2001，23（11）：1222-1239.

［12]Grady L. Random walks for image segmentation［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2006，28（11）：1768-1783.

［13]Li Yin， Sun Jian， Tang C K， et al. Lazy snapping［J］.ACM Trans on Graphics，2004，23（3）：303-308.

［14]Blake A， Rother C， Brown M， et al. Interactive image segmentation using an adaptive GMMRF model［C］//Proc of the 8th European Conference on Computer Vision.Berlin：Springer，2004：428-441.

［15]Rother C， Kolmogorov V， Blake A. GrabCut： interactive foreground extraction using iterated graph cuts［J］.ACM Trans on Graphics，2004，23（3）：309-314.

［16]Hua Siyang， Shi Ping. GrabCut color image segmentation based on region of interest［C］//Proc of the 7th International Congress on Image and Signal Processing.Piscataway，NJ：IEEE Press，2014：392-396.

［17]Price B L， Morse B， Cohen S. Geodesic graph cut for interactive image segmentation［C］//Proc of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington DC：IEEE Computer Society，2010：3161-3168.

［18]Jian Meng， Jung C. Interactive image segmentation using adaptive constraint propagation［J］.IEEE Trans on Image Processing，2016，25（3）：1301-1311.

［19]韓守東，趙勇，陶文兵，等.基于高斯超像素的快速Graph Cuts圖像分割方法［J］.自動化學報，2011，37（1）：11-20.（Han Shou-dong， Zhao Yong， Tao Wenbin， et al. Gaussian super-pixel based fast image segmentation using Graph Cuts［J］.Acta Automatica Si-nica，2011，37（1）：11-20.）

［20]Cerrone L， Zeilmann A， Hamprecht F A. End-to-end learned random walker for seeded image segmentation［C］//Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2019：12551-12560.

［21]Casaca W， Gois J P， Batagelo H C， et al. Laplacian coordinates： theory and methods for seeded image segmentation［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2021，43（8）：2665-2681.

［22]Xu Ning， Price B， Cohen S， et al. Deep interactive object selection［C］//Proc of IEEE Conference on Computer Vision and Pattern Re-cognition. Washington DC：IEEE Computer Society，2016：373-381.

［23]Wang Guotai， Zuluaga M A， Li Wenqi， et al. DeepIGeoS： a deep interactive geodesic framework for medical image segmentation［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2018，41（7）：1559-1572.

［24]Wang Guotai， Li Wenqi， Zuluaga M A， et al. Interactive medical image segmentation using deep learning with image specific fine tuning［J］.IEEE Trans on Medical Imaging，2018，37（7）：1562-1573.

［25]Sofiiuk K， Petrov I， Barinova O， et al. f-BRS： rethinking back propa-gating refinement for interactive segmentation［C］//Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition. Pisca-taway，NJ：IEEE Press，2020：8623-8632.

［26]Sofiiuk K， Petrov I A， Konushin A. Reviving iterative training with mask guidance for interactive segmentation［EB/OL］.（2021-02-12）.https：//arxiv.org/pdf/2102.06583.pdf.

［27]Porter T， Duff T. Compositing digital images［C］//Proc of the 11th Annual Conference on Computer Graphics and Interactive Techniques.Washington DCfjp：IEEE Computer Society，1984：253-259.

［28]Wang Jue， Cohen M F. Optimized color sampling for robust matting［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Washington DC：IEEE Computer Society，2007：1-8.

［29]Achanta R， Shaji A， Smith K， et al. SLIC superpixels compared to state-of-the-art superpixel methods［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2012，34（11）：2274-2282.

［30]Bampis C G， Maragos P， Bovik A C. Graph-driven diffusion and random walk schemes for image segmentation［J］.IEEE Trans on Image Processing，2017，26（1）：35-50.

［31]Rhemann C， Rother C， Wang Jue， et al. A perceptually motivated online benchmark for image matting［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Washington DC：IEEE Computer Society，2009：1826-1833.

［32]Levin A， Lischinski D， Weiss Y. A closed-form solution to natural image matting［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2008，30（2）：228-242.

［33]Chen Qifeng，Li Dingzeyu， Tang C K. KNN matting［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2013，35（9）：2175-2188.

［34]Aksoy Y， Aydin T O， Pollefeys M. Designing effective interpixel information flow for natural image matting［C］//Proc of IEEE Confe-rence on Computer Vision and Pattern Recognition.Washington DC：IEEE Computer Society，2017：29-37.

［35]Xu Ning， Price B， Cohen S， et al. Deep image matting［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Washington DC：IEEE Computer Society，2017：2970-2979.