結合局部線性嵌入與種子信息流的交互式圖像分割算法

摘 要：交互式圖像分割是指在分割過程中引入少量的用戶指引分割出目標對象，是圖像處理最基本的任務之一。現有方法通常需要構建非二次能量函數，并且普遍存在缺乏唯一解、分割精度低等問題。為進一步提高分割質量，提出一種結合局部線性嵌入和種子信息的交互式圖像分割算法（seed information combined with local linear embedding，SILLE）。該算法考慮像素點的局部信息以及先驗信息，將標記種子點的信息融入到新構建的能量函數中，以一種有效且快速的最小化方案得到能量函數的唯一且最優解，從而獲得更加準確的分割結果。最后在不同數據集上，與不同方法進行多種指標的對比，驗證了算法的有效性和可行性。

關鍵詞：局部線性嵌入；種子信息；交互式圖像分割

中圖分類號：TP391.41

文獻標志碼：A

文章編號：1001-3695（2023）07-048-2235-06

doi：10.19734/j.issn.1001-3695.2022.10.0525

Interactive image segmentation algorithm combining

local linear embedding and global information

Long Jianwu，Hu Xujun^?

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

Abstract：Interactive image segmentation refers to bringing in a small number of user guidelines to segment the target object during the segmentation process and is one of the most fundamental tasks in image processing.Existing methods usually require the construction of non-quadratic energy functions and generally suffer from the lack of unique solutions and low segmentation accuracy.To further improve the segmentation quality，this paper proposed an interactive image segmentation algorithm combining local linear embedding and seed information （SILLE）.The algorithm toke into account the local and a priori information of the pixel points and incorporated the information of the labeled seed points into the newly constructed energy function to obtain a unique and optimal solution of the energy function with an efficient and fast minimization scheme，thus obtaining more accurate segmentation results.Finally，comparison of different methods on different datasets verifies the effectiveness and feasibility of the algorithm.

Key words：local linear embedding；seed information；interactive image segmentation

0 引言

圖像分割是計算機視覺中的一個基本問題，是把圖像劃分成具有獨特性質區域的過程，是計算機視覺中備受關注的研究熱點，在許多計算機視覺任務中起到了非常關鍵的作用，如醫學圖像分割^［1～5］、視頻處理^［6～8］和目標跟蹤^［9～11］等。快速且準確的分割結果是這些研究順利開展的前提條件和基礎工作。

目前，已經有學者提出了許多圖像分割算法，如能量最小化模型^{［12～14］}、數值優化方案^［15］等。文獻［16］介紹了圖像分割算法的發展，并指出基于圖的圖像分割方法具有堅實的數學基礎，許多構建好的圖理論可以直接用于圖像分割。基于圖的方法通常是先構建一個由節點集和邊集組成的圖結構，每個像素點表示一個節點，構成節點集，像素之間的關系用圖中的邊進行表示構成邊集，然后將分割問題轉換成在特定圖上尋找最小割或者最優路徑。如現在經常使用的切割工具智能剪刀^［17］和利用圖理論改進隨機游走的方法^［18］等。基于圖的方法利用圖像親和圖的特征結構完成了圖像分割任務，通過在分割過程中對于圖的連通性以及圖邊緣分配權值可以作出調整，增加了靈活性，使基于圖理論完成圖像分割成為一種更具有吸引力的方法。

利用圖理論來完成圖像分割能夠提升前景分割完整性，但對于前景/背景特征相似性較高或者圖像紋理較復雜的圖像，分割結果通常不夠理想。為此，在分割過程中增加標記像素（種子）的交互式圖像分割算法^{［19～22］}被提出。這一類算法通常依賴于一組給定的標記像素和親和性加權圖。圖節點對應于圖像像素點，邊對應于圖像像素點間的鄰域結構，邊緣權值對圖像紋理、顏色、或者梯度進行編碼，用于標簽在圖像中的傳播。這一類算法標記種子點方式簡單，分割結果出色，是完成分割任務的熱門研究算法之一。但分割結果對種子數量依賴度較高，不同的種子信息可能會造成不同的分割結果。

現有方法通常是將分割任務形式化為能量函數，利用能量泛函最小化完成圖像分割。根據定義最優解的方式不同，能量函數最小化的方法主要分為圖割^［19］、隨機游走^［20］以及區域生長^［21］三類。

圖割算法使用最大流最小割算法優化能量泛函，通過解決馬爾可夫隨機場中的圖像標注問題完成圖像分割。GrabCut^［22］使用GMM代替了圖割中的直方圖模型，改進圖割只能在灰度圖上進行分割的缺點。文獻［23］將測地距離信息、邊緣信息與圖割框架進行了融合，提升了算法魯棒性。朱志娟等人^［24］將多尺度模型與圖割算法進行結合，進一步提升圖割算法性能。隨機游走算法通過構建一個無向圖，找到節點的概率集合，得到圖像分割結果。文獻［25］在將用戶涂鴉提供的約束作為拉普拉斯能量融入到能量函數中，并采用加速策略來減少算法的運行時間。為進一步提升算法性能，文獻［26］引入了圖像非局部親和信息，并結合超像素，在不犧牲分割精度的情況下大大節省計算成本。區域生長是從用戶種子提供的標簽開始，根據同質性準則合并相似的相鄰區域。文獻［27］利用簡單線性迭代聚類，結合紋理特征和顏色特征，改進區域生長的單一策略，提升算法魯棒性。文獻［28］是一種結合似然比檢驗的區域合并方法（RGLT），該方法利用統計概率分布通過似然比檢驗得到高亮區域和陰影區域的種子點，然后根據相似性準則生長它們，縮短分割時間，提升分割精度。隨著CNN在計算機視覺中的應用，許多基于深度學習的交互式圖像分割算法^{［29～31］}已經被提出，該類算法盡管能獲得較好的性能，但在模型訓練階段耗時長，資源消耗大，且對于參數較為敏感。

盡管能量泛函最小化方法在一定程度上提升了圖像分割質量，但仍存在以下問題：a）現有方法大多數依賴于非二次能量，求解復雜，計算成本高；b）對種子點位置敏感，并且種子點信息不能夠充分傳播；c）目標函數很難保證獲得全局最優解。為解決上述問題，本文提出了結合局部線性嵌入和種子信息流的算法，該算法定義了依賴于親和圖的二次能量函數。大多數現有方法都只是尋找最小化兩個相鄰像素點對之間距離的解，與之不同本文目標是最小化多個像素點之間的平均距離，像素點的標簽能夠在各向傳播，并且由于種子信息流的引入，增加標簽傳播的準確性。此外，本文二次能量函數最小化是在約束稀疏線性系統下完成，編碼方式簡單，計算效率高，得到的解不會陷入局部最小值，能夠保證全局最優解。

1 拉普拉斯算法

局部線性嵌入^［32］認為在多維空間中任意一個樣本點和它的鄰居樣本點近似位于一個超平面上，因此該樣本點可以通過其鄰居樣本點線性組合重構出來。同理在數字圖像中，任意一個像素點可以由鄰域像素點的線性組合重構。在圖像分割中，根據每一像素點不同的權重傳播標簽，文獻［33］利用該思想，提出了一種全新的交互式圖像分割算法，稱為拉普拉斯坐標系（LC）圖像分割算法。該算法依賴于由親和圖定義的二次能量函數式，標簽可以在各向進行傳播同時最小化距離的平均值，并且能夠保證有唯一解。

LC方法能夠獲取優良的分割，相較于其他方法計算方式更簡單，標簽傳播效果和魯棒性更好，處理圖像分割問題有顯著的改進，由于該算法在傳播標簽時，僅考慮像素點八鄰域信息，未充分利用種子信息，使其仍存在一定的局限性。

2 本文算法

根據局部線性原理，每一個像素點可由相鄰像素點線性表示，與鄰域像素點相似度越高，標簽一致可能性越大，即像素點標簽僅由與鄰域像素之間相似度決定。許多分割方法中未知像素點都是通過相鄰像素獲取標簽信息，而沒有利用鄰域像素之外的信息，如LC僅考慮圖像中像素點八鄰域的相似性，而忽略像素點與八鄰域像素之外的相似性，是圖像標簽并不能得到完整傳播的主要原因之一。如圖1所示，A～D四個像素點為非鄰域像素點，A點與B、C相似性較高，與D點相似性較低，若B～D像素點已標記為前景點或者背景點，由于B～D像素點不在A的八鄰域之中，則A像素點不能從B～D種子點獲取標簽信息。

為使種子信息能夠直接流向每一個未知像素點，本文算法將每一個未知像素點與F和B中的像素點連接起來，利用高斯混合模型為連接邊分配權值，作為種子信息流引導像素標簽的傳播。再結合局部線性嵌入思想構建的拉普拉斯坐標系，定義新的二次能量函數并求解完成圖像分割。加入種子信息流，能夠實現標簽信息遠距離傳播，即像素點標簽值由相鄰像素和已標記的種子點共同決定，如圖1中A像素點標簽值由鄰域像素點以及B～D決定。算法模型如圖2所示，紅色虛線表示像素點與八鄰域的邊連接，用于構建平滑項，藍色虛線表示像素點到前景、背景的連接，用于構建數據項，圖2（a）表示算法為每幅圖像構建的圖模型，圖2（b）表示分割結果。

本文方法與圖割方法在圖模型的表示上看起來一致，但本文所設計的目標函數以及求解方式與之均不同。圖割需要利用最大流最小割算法進行離散化求解，且通常只能獲得局部最優解，本文模型直接對目標函數進行優化，可獲得全局最優解。

2.1 種子點信息流構建

在RGB顏色空間中，圖像由n個像素點組成，本文使用GMM構建顏色數據模型。考慮到圖像中的不同顏色信息，為了盡可能地使每一個未知像素點在已標記數據中尋找到與自己最相似的像素點，本文分別為前景和背景進行混合高斯建模，并設置各自高斯分量為K、F以及B的高斯混合模型概率分布式的表達如下：

求解上述稀疏線性系統即可得能量函數全局最優解XU，最后根據式（4）可獲得圖像標簽值，完成圖像分割。整個過程如算法1所示。

算法1 結合局部線性嵌入與種子信息流的交互式圖像分割算法

輸入：圖像I。

輸出：分割結果。

在圖像I標記前景點F、背景點B；

根據式（13）求拉普拉斯矩陣L，根據式（16）（17）求D_B、D_F；

根據式（21）求解稀疏線性系統得到XU；

根據式（4）為像素點分配標簽，完成圖像分割。

3 實驗評估

3.1 實驗環境以及評價指標

本實驗在Core^TM i5-3.10 GHz的8 GB內存的PC機上完成，將本文方法與經典方法以及較新的方法進行了全面的實驗評估，這些方法分別是LC^［33］、RW^［20］、GWO^［34］、NRW^［35］、RITM^［36］、Semi-S^［37］以及ERAC^［38］，并使用IoU、MSE、NMI、BDE、RI、RVD及PR曲線從不同角度對每種方法進行了對比分析。各指標計算方式如下：

交并比IoU，用來計算分割結果p與GroundTruth g交集與并集的比值。

均方誤差MSE，像素點的真實值與預測值的差值均方和，m為圖像的像素點總數。

圖像信息熵NMI，I（·）計算相對熵，H（·）計算信息熵。

RVD度量表示圖像體積差異，|·|度量體積。

蘭德系數RI，a表示分割結果中同屬于一類的像素點數，b表示都不屬于同一類的像素點數量，Cⁿ_s^amples₂表示所有可能的像素點對。

BDE測量邊界的平均位移誤差，N₁、N₂分別表示在g和p上邊界像素點總數，d表示邊界到最近像素點的距離。

本文算法使用兩個常用的公開圖像分割數據集進行對比實驗，MSRC以及BSD500數據集中的50張圖像。MSRC包含50張原型圖像，以及通過人工分割獲取的GroundTruth。數據集中每張圖片包含Trimap圖和GroundTruth圖，該數據集可以在微軟劍橋網站上獲取。BSD500包含大量的分割圖像，圖像中的復雜紋理以及不同程度的光照會對分割任務造成不小的挑戰。由于兩個數據集的GroundTruth是一個多分類圖，本實驗需要使用文獻［38］進行GroundTruth的重構，重構過程如圖3所示。

3.2 模塊有效性分析

為驗證本文算法所做的技術改動有效性，在BSD500上對不同類型種子信息流進行了分析，設置式（10）中w_iB=0，驗證前景信息流的有效性，設定w_iF=0，驗證背景信息流的有效性，w_iF、w_iB同時設置為0，表示不加任何信息流，作為驗證對比。在圖4中可以看出在四種分割結果中，圖4（e）分割結果更完整。信息流對比如表1所示，加粗數據為指標最優，對比不加任何種子信息流，前景信息流以及背景信息流指標更優。對比僅加前景或背景種子信息，本文算法指標最優。

3.3 定量分析

為客觀地評價算法，本文首先在MSRC上對各指標比較分析，設置實驗參數K=5，在RITM和Semi-S上交互標記像素點，ERAC在前景外輪廓使用矩形框標記。其余方法均采用相同標記，分析表2，本文算法在MSE、RI、BDE、RVD指標最優，在IoU指標下為次優。在曲線圖5中，本文算法和NRW曲線優于其他算法。

為進一步驗證算法的有效性，本文在BSD500上對每種方法的指標進行了測試。表3測試統計數據，加粗數據部分是各評價指標得分最優值。從表3中可以看出，本文方法僅在RVD指標上非最優值。圖6是PR曲線，評估分割方法在邊界擬合的能力，由于PR曲線會受到樣本比例的影響，在該指標下，LC算法曲線最優，本文算法為次優。

由于本文方法加入了似然項，計算了未知像素點與已知像素點的標簽匹配度，每一個像素點都能直接獲取標記種子點信息，彌補了相鄰像素在傳播標簽時的信息流失。特別是在當標記信息少，標記種子點到未知像素點距離遠時，本文方法優勢更明顯，分割結果更為完整，指標能夠得到提升。但考慮到不同圖像中像素特征不同，參數K=5的設定不適用于每一副圖像，因此在MSRC上IoU、NMI值以及BSD500上的RVD值并不是最優。

3.4 定性分析

為從另一個角度進一步研究這些先進方法對于圖像的分割效果，本文在圖7、8中展示了這些方法在BSD500和MSRC數據集上的分割結果。總的來說，許多方法都產生了類似的分割結果，但在一些微小差異上值得強調。例如在海星圖像當中，本文方法與其他三種方法相比較而言，產生了最完整的海星分割結果，這是由于在Scribbles標記圖像中，缺少對于圖像下方的海星分支標記，前景像素點的標簽沒有完整傳播，導致分割失敗。由于本文方法增加了信息流的傳播，提升了象分割的完整性。在圖像中，也可以看出本文方法在邊緣更加清晰準確。

4 結束語

本文方法在拉普拉斯坐標系基礎之上，融合了像素的前景和背景信息，構建了新的二次能量最小化函數。在求解時能保證全局最優解。在求解過程中，通過矩陣的變換，減少重復求解。將求解的簡單性、唯一性和易于編碼的特性結合到一個新的圖像分割算法之中。本文算法整個過程只需四個步驟，首先標記種子點，其次構建親和圖，計算參數值，再次求解能量函數，最后分配標簽完成圖像分割。在處理復雜圖像、標簽傳播的良好結果證明所提方法的有效性。從實驗中可以看出，本文方法促進了處理圖像分割問題的顯著改進。盡管具有良好性能和結果，仍存在局限性，例如當圖像中存在煙霧等特別透明的像素時，該方法產生的分割結果不是特別理想，為了改善以上缺點，下一步工作將考慮結合摳圖算法提升分割性能。

參考文獻：

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

［2］Dong Chunhua，Zeng Xianyan，Lin Lanfen，et al.An improved random walker with Bayes model for volumetric medical image segmentation［J］.Journal of Health care Engineering，2017，2017：article ID 6506049.

［3］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.

［4］高紅霞，郜偉.融合密集連接與自適應加權損失的血管壁圖像分割［J］.計算機應用研究，2022，39（6）：1905-1961.（Gao Hong-xia，Gao Wei.Image segmentation of vascular wall based on dense connection and adaptive weighted loss［J］.Application Research of Computers，2022，39（6）：1905-1961.）

［5］Li Ruizhe，Chen Xin.An efficient interactive multi-label segmentation tool for 2D and 3D medical images using fully connected conditional random field［J］.Computer Methods and Programs in Biomedicine，2022，213（C）：106534.

［6］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.

［7］黃清，豐洪才，劉立.基于卷積神經網絡的多模態視頻場景分割優化算法［J］.計算機應用研究，2022，39（5）：1596-1700.（Huang Qing，Feng Hongcai，Liu Li.Multi-modal video scene segmentation optimization algorithm based on convolutional neural network［J］.Application Research of Computers，2022，39（5）：1596-1700.）

［8］Heo Y，Koh Y J，Kim C S.Guided interactive video object segmentation using reliability-based attention maps［C］//Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2021：7318-7326.

［9］Karayev S，Fritz M，Darrell T.Anytime recognition of objects and scenes［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2014：572-579.

［10］Susmitha A V V.Smart recognition system for business predictions （you only look once-V3） unified，real time object detection［M］//Kanagachidambaresan G，Anand R，Balasubramanian E，et al.Internet of Things for Industry 4.0.Cham：Springer，2020：137-146.

［11］桑高麗，鄭增國，閆超.基于區域分割的表情魯棒三維人臉識別方法［J］.計算機應用研究，2020，37（3）：914-918.（Sang Gaoli，Zheng Zengguo，Yan Chao.Robust expression 3-D face recognition method based on region segmentation［J］.Application Research of Computers，2020，37（3）：914-918.）

［12］Dai Linzheng，Yang Jian，Chen Liang，et al.Category-specific object segmentation via unsupervised discriminant shape［J］.Pattern Re-cognition，2017，64：202-214.

［13］Kolmogorov V，Zabin R.What energy functions can be minimized via graph cuts？［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2004，26（2）：147-159.

［14］Delong A T.Advances in graph-cut optimization：multisurface models，label costs，and hierarchical costs［D］.Canada：University of Western Ontario，2011.

［15］Koutis I，Miller G L，Tolliver D.Combinatorial preconditioners and multilevel solvers for problems in computer vision and image proces-sing［J］.Computer Vision and Image Understanding，2011，115（12）：1638-1646.

［16］Nascimento M C V，de Carvalho A C P L F.Spectral methods for graph clustering—a survey［J］.European Journal of Operational Research，2011，211（2）：221-231.

［17］Mortensen E N，Barrett W A.Interactive segmentation with intelligent scissors［J］.Graphical Models amp; Image Processing，1998，60（5）：349-384.

［18］Wang Linbo，Li Meng，Fang Xianyong，et al.Improving random walker segmentation using a nonlocal bipartite graph［J］.Biomedical Signal Processing and Control，2022，71（A）：103154.

［19］Boykov Y，Funka-Lea G.Graph cuts and efficient N-D image segmentation［J］.International Journal of Computer Vision，2006，70：109-131.

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

［21］Cousty J，Bertrand G，Najman L，et al.Watershed cuts：minimum spanning forests and the drop of water principle［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2009，31（8）：1362-1374.

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

［23］Peng Zili，Qu Shaojun，Li Qiaoliang.Interactive image segmentation using geodesic appearance overlap graph cut［J］.Signal Processing Image Communication，2019，78：159-170.

［24］朱志娟，何坤.基于多尺度特征的Graph Cut圖像分割［J］.現代計算機，2021，27（13）：49-54.（Zhu Zhijuan，He Kun.Graph Cut image segmentation based on multi-scale features［J］.Modern Computer，2021，27（13）：49-54）.

［25］Shen Jianbing，Du Yunfan，Li Xuelong.Interactive segmentation using constrained Laplacian optimization［J］.IEEE Trans on Circuits and Systems for Video Technology，2014，24（7）：1088-1100.

［26］Wang Linbo，Li Meng，Fang Xianyong，et al.Improving random walker segmentation using a nonlocal bipartite graph［J］.Biomedical Signal Processing and Control，2022，71（1）：103154.

［27］Dong Ranran，Wang Bo，Li Shuai，et al.Interactive image segmentation with color and texture information by region merging［C］//Proc of Chinese Control and Decision Conference.Piscataway，NJ：IEEE Press，2016：777-783.

［28］Wang Xuyang，Wang Luyu，Li Guolin.et al.A robust and fast method for sidescan sonar-image segmentation based on region growing［J］.Sensors，2021，21（21）：article ID 6960.

［29］Hao Yuying，Liu Yi，Peng Juncai，et al.RAIS：robust and accurate interactive segmentation via continual learning［EB/OL］.（2022-10-20）.https：//arxiv.org/abs/2210.10984.

［30］Asad M，Fidon L，Vercauteren T.ECONet：efficient convolutional online likelihood network for scribble-based interactive segmentation［EB/OL］.（2022-01-12）.https：//arxiv.org/abs/2201.04584.

［31］Minaee S，Boykov Y，Porikli F，et al.Image segmentation using deep learning：a survey［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2022，44（7）：3523-3542.

［32］Roweis S，Saul L.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2000，290（5500）：2323-2326.

［33］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.

［34］Vezhnevets V，Konouchine V.“GrowCut”：interactive multi-label N-D image segmentation by cellular automata［C］//Proc of Graphicon.2005：150-156.

［35］Bampis C G，Maragos P.Unifying the random walker algorithm and the SIR model for graph clustering and image segmentation［C］//Proc of IEEE International Conference on Image Processing.Piscataway，NJ：IEEE Press，2015：2265-2269.

［36］Sofiiuk K，Petrov I A，Konushin A.Reviving iterative training with mask guidance for interactive segmentation［C］//Proc of IEEE International Conference on Image Processing.Piscataway，NJ：IEEE Press，2022：3141-3145.

［37］Kline A，Chung H J，Rahmani W，et al.Semi-supervised segmentation of renal pathology：an alternative to manual segmentation and input to deep learning training［C］//Proc of the 43rd Annual International Conference of IEEE Engineering in Medicine amp; Biology Society.Piscataway，NJ：IEEE Press，2021：2688-2691.

［38］韓守東，趙勇，陶文兵，等.基于高斯超像素的快速Graph-Cuts圖像分割方法［J］.自動化學報，2011，37（1）：11-20.（Han Shou-dong，Zhao Yong，Tao Wenbing，et al.Fast Graph-Cuts image segmentation method based on Gaussian superpixel［J］.Automatica，2011，37（1）：11-20.）

［39］Kim K I，Tompkin J，Pfister H，et al.Context-guided diffusion for label propagation on graphs［C］//Proc of IEEE International Conference on Computer Vision.Piscataway，NJ：IEEE Press，2015：2776-2784.

［40］Liu Huaxian，Fang Jianxiong，Zhang Zijian，et al.Localised edge-region-based active contour for medical image segmentation［J］.IET Image Processing，2021，15（7）：1567-1582.