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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金青年科學(xué)資助項(xiàng)目（61502065）；重慶市科委基礎(chǔ)科學(xué)與前沿技術(shù)研究資助項(xiàng)目（cstc2018jcyjAX0287，cstc2015jcyjBX0127）；重慶市教委人文社科研究重點(diǎn)資助項(xiàng)目（17SKG136）；重慶理工大學(xué)研究生創(chuàng)新資助項(xiàng)目（clgycx2020090，clgycx2020096，clgycx20203112）

作者簡(jiǎn)介：龍建武（1984-），男，湖北恩施人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)閳D像處理、機(jī)器學(xué)習(xí)；栗童（1997-），男（通信作者），河北邯鄲人，碩士研究生，主要研究方向?yàn)閿?shù)字圖像處理、圖像摳圖（907822778@qq.com）；朱江洲（1994-），男，湖南長(zhǎng)沙人，碩士研究生，主要研究方向?yàn)閿?shù)字圖像處理、圖像平滑；宋鑫磊（1995-），男，山東菏澤人，碩士研究生，主要研究方向?yàn)閿?shù)字圖像處理、醫(yī)學(xué)圖像分割；石美鳳（1989-），女，湖南湘西人，碩導(dǎo)，博士，主要研究方向?yàn)橹悄苡?jì)算.

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

關(guān)鍵詞：超像素； 交互式圖像分割； 隨機(jī)游走； 窄帶區(qū)域

中圖分類號(hào)：TP391.41"" 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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 引言

圖像分割是圖像處理中的關(guān)鍵一環(huán)，在增強(qiáng)對(duì)圖像的理解上起著重要作用，并且已經(jīng)在醫(yī)學(xué)圖像處理［1～5］、機(jī)器視覺(jué)［6～8］、目標(biāo)追蹤［9，10］中得到了廣泛的應(yīng)用。根據(jù)是否使用先驗(yàn)信息可以將圖像分割算法分為有監(jiān)督和無(wú)監(jiān)督兩類。由于組成自然圖像物體的復(fù)雜性和內(nèi)容的多樣性，再加上人們?cè)讷@取圖像前景區(qū)域時(shí)有著強(qiáng)烈的主觀性，所以有監(jiān)督的方式比無(wú)監(jiān)督的方式有更強(qiáng)的現(xiàn)實(shí)使用價(jià)值。

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

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

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

1 隨機(jī)游走算法

1.1 基于隨機(jī)游走的圖像分割算法

隨機(jī)游走的圖像分割算法以像素點(diǎn)為基本處理單元，使用用戶標(biāo)記提供先驗(yàn)信息進(jìn)行交互式分割。該方法將圖像建模成一幅加權(quán)無(wú)向圖G=（V，E），V為圖像中的像素點(diǎn)集，E為圖像中相鄰像素點(diǎn)構(gòu)成的邊集。Wij為相鄰像素點(diǎn)i和j相似性權(quán)重，使用高斯函數(shù)進(jìn)行計(jì)算可得

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

其中：gi表示像素點(diǎn)i的灰度值或顏色值;σ為參數(shù)。隨機(jī)游走在經(jīng)過(guò)每個(gè)像素點(diǎn)的概率可以轉(zhuǎn)換成求解狄克雷問(wèn)題，狄克雷積分公式如下：

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

其中：L為使用相似性權(quán)重Wij構(gòu)建的拉普拉斯矩陣。對(duì)于用戶標(biāo)記信息，記M為標(biāo)記點(diǎn)集，U為未標(biāo)記點(diǎn)集，可以將拉普拉斯矩陣分解成如下形式：

L= LMRRTLU（3）

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

D［xn］=12 ［xTM xTU］ LMR

RTLUxMxU（4）

對(duì)式（4）求微分并令導(dǎo)數(shù)為0，可得

LUxU=－RTxM（5）

其中：xU表示待求的所有未標(biāo)記像素點(diǎn)到已標(biāo)記像素點(diǎn)的概率值。通過(guò)對(duì)比未標(biāo)記點(diǎn)到達(dá)已標(biāo)記前景和背景點(diǎn)的概率值即可分配標(biāo)簽，完成圖像分割。

1.2 基于隨機(jī)游走的魯棒性摳圖算法

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

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

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

=（C－Bj）（Fi－Bj）‖F(xiàn)i－Bj‖2（7）

使用下式計(jì)算樣本對(duì)的估計(jì)誤差：

Rd（Fi，Bj）=‖C－（Fi+（1－）Bj）‖‖F(xiàn)i－Bj‖（8）

為了評(píng)估所選樣本對(duì)，首先使用w（Fi）=exp{－‖F(xiàn)i－C‖2/D2F}和w（Bj）=exp{－‖Bj－C‖2/D2B}計(jì)算樣本點(diǎn)權(quán)重，D2F和D2B分別為所選樣本點(diǎn)到未知像素點(diǎn)的最大歐氏距離，其次使用式（9）計(jì)算所選擇樣本對(duì)的置信度f(wàn)。選擇置信度較高的前三個(gè)樣本計(jì)算出的半透明度值作為未知點(diǎn)估計(jì)的值。

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

為了獲取最后的結(jié)果，對(duì)未知區(qū)域建立F-B圖。設(shè)置數(shù)據(jù)項(xiàng)和平滑項(xiàng)，數(shù)據(jù)項(xiàng)中的權(quán)重計(jì)算如下：

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

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

其中：f為權(quán)重系數(shù);定義δ（·）為指示函數(shù)，若igt;0.5，則δ（igt;0.5）為1，反之為0。平滑項(xiàng)中的權(quán)重計(jì)算如下：

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

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

2 SPRW和FRB算法

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

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

2.1.1 超像素預(yù)處理

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

2.1.2 用戶標(biāo)記

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

2.1.3 建立F-B圖結(jié)構(gòu)

在進(jìn)行超像素預(yù)處理后，圖像分割問(wèn)題可以從對(duì)像素點(diǎn)的二分類問(wèn)題上升為對(duì)超像素塊的二分類問(wèn)題，本文將超像素圖映射為無(wú)向加權(quán)圖G=（V，E，W），其中V為超像素點(diǎn)集合，E表示相鄰超像素之間無(wú)向邊集合，W為相鄰超像素的相似性權(quán)重矩陣。為了更好地融合超像素圖的區(qū)域信息和標(biāo)記信息，定義能量函數(shù)為

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

其中：J1為超像素平滑項(xiàng)，用于約束超像素鄰居區(qū)域標(biāo)簽一致；J2為超像素區(qū)域數(shù)據(jù)項(xiàng)，用以約束超像素塊與最相近的標(biāo)記點(diǎn)標(biāo)簽一致。如圖3所示，建立與平滑項(xiàng)和數(shù)據(jù)項(xiàng)對(duì)應(yīng)的圖結(jié)構(gòu)。

在相鄰超像素塊之間計(jì)算超像素平滑項(xiàng)J1：

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

其中：Wij為相鄰超像素塊的相似性權(quán)重，使用式（15）計(jì)算。

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

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

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

其中：i∈ΩU;dmi計(jì)算未標(biāo)記點(diǎn)到標(biāo)記點(diǎn)的最短距離，并建立連接關(guān)系，由此可得超像素?cái)?shù)據(jù)項(xiàng)為

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

其中：bm為標(biāo)記點(diǎn)的標(biāo)簽，令bF=1，bB=0。結(jié)合式（16）計(jì)算未知點(diǎn)i到標(biāo)記點(diǎn)的相似性權(quán)重Gim：

Gim=exp－dmi2σ2（18）

2.1.4 隨機(jī)游走求解

聯(lián)合式（13）（16），可以將式（12）的能量項(xiàng)寫(xiě)成

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）

使用約束條件構(gòu)建拉格朗日函數(shù)，經(jīng)矩陣表示并化簡(jiǎn)為

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

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

其中：L為在平滑項(xiàng)中使用局部相似性構(gòu)建的拉普拉斯矩陣，如式（21）所示;Gm是使用相似性權(quán)重Gim構(gòu)建的對(duì)角矩陣，1是全部為1的向量。

Lij=Wii" i=j

-Wiji，j∈E

0others（21）

D=diag（d1，d2，d3，…，dK）為標(biāo)記向量，且

di=1 i∈ΩM

0i∈ΩU（22）

令J（x）x=0可得

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

求解上述稀疏線性系統(tǒng)，根據(jù)屬于前景或者背景的概率的大小分配標(biāo)簽，即可得到硬分割結(jié)果。

2.2 邊界窄帶區(qū)域的軟分割算法

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

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

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

g（Fi）=exp－‖F(xiàn)i－Ci‖22σ2（24）

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

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

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

其中：J1和J2分別為平滑項(xiàng)和數(shù)據(jù)項(xiàng)，平滑項(xiàng)J1保證局部半透明度值平滑，使用式（27）計(jì)算。

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

其中：Wij為相鄰像素點(diǎn)之間的相似性權(quán)重，使用式（12）計(jì)算。數(shù)據(jù)項(xiàng)J2約束像素點(diǎn)的半透明度值和估計(jì)值一致，使用式（28）計(jì)算。

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

其中：VU為窄帶區(qū)域像素點(diǎn);Gim為使用式（9）（24）（25）結(jié)合式（10）（11）計(jì)算所得的相似性權(quán)重。式（26）經(jīng)整理可得

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）

使用約束條件構(gòu)建拉格朗日函數(shù)，經(jīng)矩陣表示并化簡(jiǎn)為

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

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

其中：L為使用Wij構(gòu)建的拉普拉斯矩陣;G是使用Gim構(gòu)建的對(duì)角矩陣;D為標(biāo)記向量，與上節(jié)含義一致。

令J（a）a=0可得

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

求解此線性稀疏系統(tǒng)即可得出最終軟分割結(jié)果，本節(jié)軟分割的計(jì)算和硬分割的計(jì)算基本一致，主要區(qū)別在于圖模型的建立、權(quán)重的計(jì)算方法上。

3 實(shí)驗(yàn)結(jié)果和分析

3.1 實(shí)驗(yàn)環(huán)境

本文算法在Core i5 四核3.40 GHz 的 CPU 以及8 GB 內(nèi)存的 PC 機(jī)上實(shí)現(xiàn)，使用Visual Studio 2017 結(jié)合 OpenCV開(kāi)源視覺(jué)庫(kù)和Eigen庫(kù)并使用C++語(yǔ)言實(shí)現(xiàn)。其中在超像素預(yù)分割階段，為了使得超像素分割可以更好地適合圖像，設(shè)置超像素個(gè)數(shù)為C/400，C為圖像大小。

3.2 定性分析

為了驗(yàn)證所提出硬分割算法的有效性，本文選取BSD500數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，BSD500數(shù)據(jù)集是伯克利大學(xué)提供的用于圖像多目標(biāo)分割和邊緣檢測(cè)的數(shù)據(jù)。使用文獻(xiàn)［19］的方式進(jìn)行人工填充標(biāo)記構(gòu)建真值，圖6為人工標(biāo)記真值過(guò)程。

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

3.3 定量分析

為了能夠定量地評(píng)價(jià)所提出的硬分割算法，本文使用像素準(zhǔn)確率（pixel accuracy，PA）、類別平均像素準(zhǔn)確率（mean accuracy precision，MAP）、平均交并比（mean intersection over union， mIoU）和時(shí)間復(fù)雜度指標(biāo)來(lái)定量分析實(shí)驗(yàn)結(jié)果。由于對(duì)前景背景都進(jìn)行了標(biāo)記，所以分別計(jì)算前景分類平均像素準(zhǔn)確率（CPA（FG））和背景的平均像素準(zhǔn)確率（CPA（BG））。表1是在BSD500數(shù)據(jù)集上進(jìn)行測(cè)試的定量結(jié)果。其中在使用超像素分割階段，進(jìn)行處理的平均時(shí)間為0.24 s。由于圖片大小不一致，導(dǎo)致處理時(shí)間有差異，但在每張圖片上的處理時(shí)間，本文方法對(duì)比于其他方法仍有較大優(yōu)勢(shì)。

表2是在BSD500數(shù)據(jù)集上與其他算法的對(duì)比結(jié)果，可以觀察到本文算法在運(yùn)行時(shí)間上較其他算法有了大幅度的降低，算法運(yùn)行時(shí)間可以達(dá)到0.056 s，并且在PA、CPA（FG）和mIoU指標(biāo)比較上優(yōu)于其他算法，在CPA（BG）指標(biāo)的比較上與RW算法接近，實(shí)現(xiàn)了在效率和精度上的統(tǒng)一。

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

3.4 針對(duì)窄帶區(qū)域的軟分割實(shí)驗(yàn)

目標(biāo)物體的邊界處理一直都是圖像分割中重點(diǎn)研究的問(wèn)題，而硬分割的結(jié)果無(wú)法精確地表示邊界的混合像素部分，本文提出了改進(jìn)的魯棒性摳圖算法，使其效率大幅度提高，能夠?qū)D像邊界進(jìn)行更加高效的處理。從圖4和8可以看到，本文所提出的軟分割算法不僅可以糾正由于超像素預(yù)處理累積的分割錯(cuò)誤或者硬分割造成的誤分區(qū)域，還可以優(yōu)化分割結(jié)果，使得邊界在視覺(jué)感知上更加平滑。

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

3.5 其他應(yīng)用

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

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

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

參考文獻(xiàn)：

[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]南麗麗，鄧小英.幾何距優(yōu)化質(zhì)心結(jié)合隸屬度約束RFCM的腦MRI圖像分割算法［J］.計(jì)算機(jī)應(yīng)用研究，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］.自動(dòng)化學(xué)報(bào)，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.