耦合先驗拉普拉斯坐標的半監督圖像分割算法

曹昀煬 王濤

摘 要：針對傳統半監督圖像分割方法難以精確分割分散或細小區域的缺陷，提出了一種耦合標簽先驗和拉普拉斯坐標模型的半監督圖像分割算法。首先，擴展拉普拉斯坐標（LC）模型，通過引入標簽先驗項進一步精確表征未標記像素點與已標記像素點之間的關系。然后，基于矩陣方程的求導優化，有效估計像素屬于標簽的后驗概率，以實現圖像目標分割的任務。得益于標簽先驗的引入，所提算法對分散或細小區域的分割更加魯棒。最后，在多個公開的半監督分割數據集上實驗結果表明，相比拉普拉斯坐標算法，所提算法的分割準確率獲得了顯著提升，驗證了所提算法的有效性。

關鍵詞：圖像分割;彩色圖像;半監督圖像分割;拉普拉斯坐標;先驗概率

中圖分類號：TP391.413

文獻標志碼：A

Semi-supervised image segmentation based on prior Laplacian coordinates

CAO Yunyang1， WANG Tao2*

1.School of Statistics， East China Normal University， Shanghai 200241， China;

2.College of Computer Science and Engineering， Nanjing University of Science and Technology， Nanjing Jiangsu 210094， China

Abstract：

Focusing on the issue that classic semi-supervised image segmentation methods have difficulty in accurately segmenting scattered or small regions， a semi-supervised segmentation algorithm based on label prior and Laplacian Coordinates （LC） was proposed. Firstly， the Laplacian coordinates model was extended， and further the relationship between unlabeled pixels and labeled pixels accurately characterized by introducing the label prior. Secondly， based on the derivation of matrix equation， the posterior probability that the pixel belongs to the label was able to be effectively estimated， thus achieving the segmentation of the image. Thanks to the introduction of the label prior， the algorithm was more robust to the segmentation of scattered and small regions. Lastly， the experimental results on several public semi-supervised segmentation datasets show that the segmentation accuracy of the proposed algorithm is significantly improved compared with that of the Laplacian coordinates algorithm， which verifies the effectiveness of the proposed algorithm.

Key words：

image segmentation; color image; semi-supervised image segmentation; Laplacian Coordinates （LC）; prior probability

0 引言

圖像分割是指在特定的相似性準則下將用戶感興趣的圖像目標從復雜的背景環境中分離出來[1]。圖像分割是從圖像處理到圖像分析的關鍵步驟，分割出的圖像目標具有高維語義性，是后續圖像應用的基礎[2]。按照標簽先驗的獲取方式，現有的圖像分割方法一般可以分為三類：無監督方法[3-4]、半監督方法[5]和全監督方法[6]。無監督圖像分割方法基于預先設定的相似性準則對圖像特征進行聚類分析，可以實現自動的圖像分割。然而，此類方法由于缺乏足夠的用戶先驗指導，往往缺乏通用性與準確性。全監督圖像分割方法基于全標記的圖像樣本序列進行模型參數訓練，可以實現圖像的語義層分割。典型的此類方法包括當下流行的卷積神經網絡方法等[7]。此類方法的分割性能一般依賴于足夠多的訓練樣本數據。此外，當出現訓練樣本中未包含的新類別時，往往無法獲得正確的目標分割，導致此類方法缺乏一定的靈活性。半監督圖像分割方法允許用戶提供初始種子點或目標輪廓來表征標簽先驗信息，可以獲得滿足用戶需求的分割結果。用戶可以通過簡單的人機交互方式，實現對分割過程的控制和對錯誤分割的有效修正，因此，半監督分割模式具有更強的通用性和靈活性。本文主要集中于半監督的分割模式展開研究工作。

近年來，大量的半監督分割方法[8-14]被提出。典型的方法包括圖割（Graph Cut， GC）[8]和隨機游走（Random Walk，RW）[9]。在上述方法中，用戶需要首先標記一些像素點作為種子點，然后算法可以基于種子點自動地估計未標記像素點的標簽。Boykov等[8]首次提出了半監督圖割算法，并應用于醫學圖像分割中，利用像素之間的相似程度定義能量，將能量函數定義為區域能量和邊界能量之和。該算法添加了兩個虛擬的終端點，用區域能量衡量像素點和終端點之間的相似程

度，邊界能量衡量相鄰像素點之間的相似程度，將圖像分割問題轉化為求取圖的最小割集問題，通過最大流算法獲取全局的最優解。但是傳統的圖割算法是在統計直方圖的基礎上，由于直方圖的局限性，圖割算法較難準確地分割包含復雜背景的圖像。Grady[9]提出隨機游走算法，通過構建從未標記像素點出發到種子點終止的隨機游走模型，求解帶有邊界約束的Dirichlet問題，估計出每一個未標記像素點到種子點的到達概率。將未標記的像素點與其到達概率最大的種子點合并為目標區域。傳統的隨機游走算法完全依賴種子點的質量和位置，因此當種子點較少時，該算法的分割結果錯誤率較高。此外，隨機游走算法忽視了標簽的各向異性傳播，對區域邊界不敏感，容易出現邊界擬合較差的問題。針對這些問題，Casaca等[10]提出結合拉普拉斯坐標（Laplacian_Coordinates，LC）的半監督圖像分割算法改進隨機游走模型。該算法對每個像素點賦值，求出最小化能量函數的最優解，之后將最優解轉化為像素點屬于前景或背景的概率，將像素點與其概率最大的標簽合并為目標區域。相比于傳統的隨機游走算法最小化相鄰像素點之間的距離的做法，拉普拉斯坐標算法通過最小化所有相鄰像素點距離的均值來更好地控制標簽的各向異性傳播，同時也提高了邊界擬合的準確性。此外，拉普拉斯坐標算法的能量函數包含二次型矩陣，能夠降低計算成本，并確保分割結果的準確性和平滑性。但是由于忽視未標記像素點與種子點之間的特征，只依賴相鄰像素點的特征，拉普拉斯坐標算法仍難以分割出分散或細小的區域。此外，近些年來為了提升隨機游走模型的分割準確度，Bampis等[11]提出歸一化隨機游走（Normalized Random Walk， NRW）算法;Dong等[12]提出亞馬爾可夫隨機游走（Sub-Markov Random Walk， SMRW）算法。但是歸一化隨機游走算法仍難以分割出分散或細小的區域，亞馬爾可夫隨機游走算法會存在過度分割的問題。

受現有標簽先驗建模方法[8，15-18]的啟發，本文基于拉普拉斯坐標模型[10]提出了一種半監督圖像分割算法，針對拉普拉斯坐標算法難以分割分散或細小區域等缺陷，通過引入標簽先驗來精確表征未標記像素點與種子點之間的關系。在傳統拉普拉斯坐標模型能量項中引入標簽先驗概率項，并有效優化各能量項之間的參數，充分利用用戶交互知識，彌補傳統模型的缺陷。本文提出的耦合先驗拉普拉斯坐標的半監督圖像分割算法從以下兩個方面提升了圖像分割性能：1）在分割過程中引入先驗概率，對分散或細小的區域更魯棒;2）通過合理優化參數，平衡各項約束的影響，在分割小目標區域的同時保持分割區域的邊界更平滑。

1 相關研究

圖像可以用圖G=（P，W）來表示，其中P={pi}Ni=1為所有像素點的集合，W=[Wij]N×N為像素之間的相似性矩陣，Wij∈[0，1]表示像素pi和pj之間的相似性，N為像素點的個數。圖像分割問題實質是標簽劃分問題，即給定一個標簽集合L，一個圖像像素集合P，圖像分割的目標是給每一個像素點pi∈P賦予對應的標簽值li∈L。因此圖像的分割結果即為從圖像像素集合P到標簽集合L的一組映射，表示為l={li|li∈L}。前景和背景的半監督圖像分割問題可以看作是二值標簽問題，即L={lF，lB}，其中lF代表前景的標簽值，lB代表背景的標簽值，一般賦值為lF=1，lB=0。

1.1 圖割算法

基于圖割的圖像分割算法將標簽劃分問題轉化為能量函數最小化的問題。能量函數一般可以表示為：

E（l）= Er（l）+ λEb（l）（1）

其中：能量函數E （l）由區域能量項Er和邊界能量項Eb組成。λ>0為平衡區域項和邊界項的參數。該能量函數可以采用最大流/最小割算法來優化，有效地尋找圖中的最小割集，從而獲得全局最優解。其中，區域能量項表示像素點和標簽之間的相似程度，是關于種子點屬于前景或背景的概率的函數。文獻[19]提出了使用高斯混合模型（Gaussian Mixture Model， GMM）估計像素點屬于前景和背景的概率的方法，基于GMM的區域能量項定義如下：

Er（l）=∑Ni=1（-ln（PGMM（Ci，li）））（2）

其中：PGMM（Ci，li）表示像素點pi屬于標簽li的概率。Ci表示像素點pi的特征強度向量，對于彩色圖像分割，用RGB特征定義像素點pi的特征強度向量Ci=（Ri，Gi，Bi）;對于灰度圖像分割，用灰度值代表像素點pi的特征強度向量Ci。

圖割算法在分割背景環境較為簡單的圖像時一般能獲得較好的結果，當圖像的背景環境較為復雜時，容易出現分割速度緩慢，錯誤分割小區域目標等缺陷，導致分割結果不夠精確和魯棒。

1.2 隨機游走算法

基于隨機游走的圖像分割算法是另一種實用的半監督圖像分割算法。該算法基于隨機游走者從每個未標記像素點到種子點的轉移概率，定義未標記像素點屬于種子點對應標簽的概率。在基于隨機游走的圖像分割算法中，通常用高斯函數定義像素pi和pj之間的相似性Wij，表達式如下：

Wij=exp（-β‖Ci-Cj‖2）， pj∈Ai

0，其他（3）

其中：Ci表示像素pi的特征強度向量，Ai表示像素pi的鄰域像素集合， β為控制參數。進而可以根據像素屬于標簽l∈{lF，lB}的概率構造能量函數，表達式如下：

E（πl）=12∑Ni， j=1Wij（πil-πjl）2=12πTlLπl（4）

其中，πl=[πil]N×1為像素屬于標簽l的概率向量，πil為像素pi屬于標簽l的概率。L=D-W為拉普拉斯矩陣，其中D=diag（d1，d2，…，dN），di=∑Nj=1Wij，W=[Wij]N×N。為了降低計算復雜度，可以將拉普拉斯矩陣轉變為分塊矩陣，僅計算未標記的像素屬于標簽l的概率。將像素集合P劃分為標記的像素集合PM和未標記的像素集合PU滿足PM∩PU=，PM∪PU=P。因此未標記像素屬于標簽l的概率向量表達式如下：

li=1， πi≥0.5

0，πi<0.5（13）

對于多目標分割問題，需要分別計算所有像素屬于各個標簽的后驗概率向量，其后驗概率計算公式為前景和背景分割計算公式的高維推廣，表達式如下：

πq=（K+L2）-1KYq（14）

其中：πq=[πiq]N×1表示所有像素屬于標簽lq的后驗概率向量，Yq=[yiq]N×1表示所有像素屬于標簽lq先驗概率向量，當pi為未標記像素時，yiq=iq=PGMM（Ci，lq），當pi為屬于標簽lq的種子點時，yiq=1，當pi為不屬于標簽lq的種子點時，yiq=0。q=1，2，…，n，n為標簽總數。矩陣K和L的含義保持不變。最后，將像素分配給后驗概率最大的標簽。

與現有的半監督圖像分割算法相比，本文算法增加了標簽先驗項，利用了種子點與未標記像素的特征關系，在保證標簽各向異性傳播的同時，使得分割結果對分散或細小的區域更加敏感。

3 實驗與結果分析

本文實驗選用的圖像來自于MSRC數據集[19]、Graz數據集[20]和LHI數據集[21]。MSRC、Graz、LHI數據集提供了用戶交互信息和正確分割結果，是評價半監督圖像分割方法最常用的數據集。本文選用錯誤率、重疊度（Intersection over Union， IoU）和運行時間作為評價分割結果的定量指標。錯誤率的定義如下：

錯誤率=錯分類像素點數未標記像素點數（15）

其中，錯分類像素點和未標記像素點均不包括種子點。IoU是分割問題中常用的標準性能度量指標，表示估計結果與真實結果的重疊度，IoU值越大表示分割效果越好。本文實驗基于英特爾酷睿I5 CPU以2.0GHz的頻率在Matlab進行，在同等情況下測算運行時間。本文算法將與一系列隨機游走算法進行比較實驗，包括隨機游走（RW）算法、拉普拉斯坐標（LC）算法、歸一化隨機游走（NRW）算法、亞馬爾可夫隨機游走（SMRW）算法。根據文獻[10]，LC算法的控制參數k1、k2、k3均設為1;本文算法的常數m設為105，控制參數k設為10-7。

3.1 定性比較

本文根據分割結果的可視化對4種經典算法和本文算法進行定性評估。圖1所示為5種算法的分割結果。

圖1（b）表示種子點信息，白色的像素被標記為前景種子點，黑色的像素被標記為背景種子點，其余為未標記像素。本文基于未標記像素點的分割錯誤率比較分割結果。從圖中可以看出，由于忽視了標簽傳播的各向異性，RW算法和NRW算法對細小和分散的區域不敏感。由于依賴相鄰像素點之間特征強度的關系，在相鄰像素點之間特征強度相差較大時，LC算法容易停止分割，從而導致錯誤分割邊界。SMRW算法對細小區域過于敏感，分割出的邊界很不平滑。本文算法改善了已有隨機游走算法的缺陷，對分散或細小的目標更加敏感，獲得了較好的分割結果。以第一幅圖“cross”為例，十字架與立柱連接處的像素顏色特征與其鄰域內像素的顏色特征相差較大，因此傳統算法僅以連接處為目標的邊界。SMRW算法雖然正確分割出十字架，但是房屋邊界的分割結果非常不平滑。然而，本文算法引入了標簽先驗信息，因為十字架的顏色特征與前景種子點的顏色特征非常接近，所以十字架被分割成前景目標。因此本文算法對分散的目標更加敏感。以第二幅圖“sheep”為例，由于綿羊腿部顏色與身體顏色相差較大，并且羊腿與身體距離較遠，因此RW算法和NRW算法無法分割出羊腿。LC算法雖然考慮了標簽的各項異性傳播，能夠分割出部分羊腿，但是由于羊腿區域細長并且顏色特征與鄰域內像素的顏色特征相差較大，因此LC算法仍無法分割出全部的羊腿。由于羊腿的顏色特征與前景標簽中綿羊面部的顏色特征近似，所以本文算法分割羊腿的效果更好，因此本文算法對細小的目標更加敏感。

3.2 定量比較

本文在MSRC、Graz、LHI數據集上對5種算法作定量評估，以分割的平均錯誤率、平均IoU和平均運行時間為評估指標。對于MSRC數據集上的50幅測試圖像，RW算法的平均錯誤率為7.46%，LC算法的平均錯誤率為5.06%，NRW算法的平均錯誤率為5.92%，SMRW算法的平均錯誤率為4.62%，本文算法的平均錯誤率為4.02%?？梢钥闯霰疚乃惴ǖ腻e誤率相對于RW算法和LC算法具有顯著下降，并明顯優于近年來提出的NRW算法和SMRW算法。表1為在三種數據集上五種算法的平均IoU和平均運行時間，可以看出本文算法的平均IoU約為0.85，在各個數據集上明顯高于其余四種算法，分割結果更準確。同時，本文算法每幅圖的平均運行時間約3.1s，明顯快于近年來提出的NRW算法和SMRW算法。因此，本文算法引入標簽先驗項，能夠進一步提升拉普拉斯坐標的算法分割的準確度，提升運算速度，具有可行性。

圖2為5種算法在MSRC數據集50幅測試圖像的分割錯誤率的比較，其中圖像ID根據本文算法的錯誤率由低到高排序，可以看出本文算法在大部分測試圖像中獲得了最優的結果。表2為本文算法在MSRC數據集50幅測試圖像上的分割錯誤率。

3.3 多目標分割

對于多目標分割問題，本文選取2幅測試圖像的分割結果，定性分析本文算法的準確度。圖3為多目標分割結果，測試圖像的種子點需要用戶手動地標記。如圖3（a）所示，紅色、綠色和藍色的像素分別表示三種不同標簽的種子點。如圖3（b）所示，在多目標分割中，本文算法分割結果仍比較準確，并且對細小的目標敏感。以第一幅圖“201080”為例，盡管種子點沒有直接標記建筑物頂端的裝飾，但是本文算法仍將細小的裝飾正確分割，從而驗證了在多目標分割問題中本文算法的有效性和可行性。

4 參數設置

本文通過設定合適的參數k來控制標簽先驗項的約束強度。圖4為不同參數k下的分割結果。由圖可以看出，當參數較大時，如圖4（c）和（d）所示k=10-1，k=10-4時，過度考慮了未標記像素點與種子點之間的特征強度關系，導致分割結果中出現雜質點、目標區域不連通等缺陷。當參數較小時，如圖4（f）和（g）所示k=10-10，k=0時，標簽先驗項作用不明顯，分割結果更接近于拉普拉斯坐標算法的結果，容易錯誤分割細長的區域。當k=10-7時，本文算法在50幅測試圖像上得到了較好的分割結果。為了更精確地比較不同參數下的分割精度，本文選用平均錯誤率定量評估。表3為不同參數下分割結果的平均錯誤率?？梢钥闯鲈趉=10-7時，平均錯誤率最小，分割精度最高。因此本文選擇控制參數k=10-7。

5 結語

本文在傳統的拉普拉斯坐標算法中引入標簽先驗項，考慮了未標記像素點和種子點之間的特征強度關系，構造了含有二次型矩陣的能量函數，通過求解能量函數的最小值獲得像素屬于標簽的后驗概率，然后根據后驗概率分割區域。本文解決了經典算法中分割結果不平滑、錯誤分割細小和分散的目標區域的問題。為了提高分割的精度，本文通過設置合適的控制參數平衡各項約束的影響，在分割出小目標區域的同時使分割區域的邊界更平滑。最后通過對比實驗以及在數據集上的定性和定量評估證實了本文算法的實用性和通用性。本文算法仍存在一些缺陷，如種子點較少時分割精度較低、控制參數需要憑經驗手動設定等。如何根據不同的圖像環境設定參數值，將是今后的研究工作。

參考文獻

[1]SONKA M， HLAVAC V， BOYLE R. Image Processing， Analysis and Machine Vision [M]. Berlin： Springer， 2003： 175-176.

[2]XIA G， SUN H， FENG L， et al. Human motion segmentation via robust kernel sparse subspace clustering [J]. IEEE Transactions on Image Processing， 2018， 27（1）： 135-150.

[3]JI Z， XIA Y， CHEN Q， et al. Fuzzy c-means clustering with weighted image patch for image segmentation [J]. Applied Soft Computing， 2012， 12（6）： 1659-1667.

[4]JI Z， XIA Y， SUN Q， et al. Fuzzy local Gaussian mixture model for brain MR image segmentation [J]. IEEE Transactions on Information Technology in Biomedicine， 2012， 16（3）： 339-347.

[5]WANG T， JI Z， SUN Q， et al. Label propagation and higher-order constraint-based segmentation of fluid-associated regions in retinal SD-OCT images [J]. Information Sciences， 2016， 358（C）： 92-111.

[6]KUNTIMAD G， RANGANATH H S. Perfect image segmentation using pulse coupled neural networks [J]. IEEE Transactions on Neural Networks， 1999， 10（3）： 591-598.

[7]SHELHAMER E， LONG J， DARRELL T. Fully convolutional networks for semantic segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2017， 39（4）： 640-651.

[8]BOYKOV Y Y， JOLLY M. Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images [C]// Proceedings of the 8th IEEE International Conference on Computer Vision. Piscataway， NJ： IEEE， 2001： 105-112.

[9]GRADY L. Random walks for image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2006， 28（11）： 1768-1783.

[10]CASACA W， NONATO L G， TAUBIN G. Laplacian coordinates for seeded image segmentation [C]// Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2014： 384-391.

[11]BAMPIS C G， MARAGOS P， BOVIK A C. Graph-driven diffusion and random walk schemes for image segmentation [J]. IEEE Transactions on Image Processing， 2017： 26（1）： 35-50.

[12]DONG X， SHEN J， SHAO L， et al. Sub-Markov random walk for image segmentation [J]. IEEE Transactions on Image Processing， 2016， 25（2）： 516-527.

[13]HEIMOWITZ A， KELLER Y. Image segmentation via probabilistic graph matching [J]. IEEE Transactions on Image Processing， 2016， 25（10）： 4743-4752.

[14]JIAN M， JUNG C. Interactive image segmentation using adaptive constraint propagation [J]. IEEE Transactions on Image Processing， 2016， 25（3）： 1301-1311.

[15]ZEMENE E， PELILLO M. Interactive image segmentation using constrained dominant sets [C]// Proceedings of the 2016 European Conference on Computer Vision， LNCS 9912. Berlin： Springer， 2016： 278-294.

[16]WANG T， SUN Q， JI Z， et al. Multi-layer graph constraints for interactive image segmentation via game theory [J]. Pattern Recognition， 2016， 55（C）： 28-44.

[17]BAI S， BAI X， TIAN Q， et al. Regularized diffusion process for visual retrieval [C]// Proceedings of the 31st AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2017： 3967-3973.

[18]WANG T， YANG J， JI Z， et al. Probabilistic diffusion for interactive image segmentation [J]. IEEE Transactions on Image Processing， 2019， 28（1）： 330-342.

[19]ROTHER C， KOLMOGOROV V， BLAKE A. Grabcut： interactive foreground extraction using iterated graph cuts [C]// Proceedings of the 2004 ACM SIGGRAPH Conference. New York： ACM， 2004： 309-314.

[20]SANTNER J， POCK T， BISCHOF H. Interactive multi-label segmentation [C]// Proceedings of the 2010 Asian Conference on Computer Vision， LNCS 6492. Berlin： Springer， 2010： 397-410.

[21]YAO B， YANG X， ZHU S. Introduction to a large-scale general purpose ground truth database： methodology， annotation tool and benchmarks [C]// Proceedings of the 2007 International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition， LNCS 4679. Berlin： Springer， 2007： 169-183.

[22]王濤.特征度量與信息傳遞的交互式圖論分割方法研究[D].南京：南京理工大學，2017：17-29. （WANG T. Research on graph theory based interactive segmentation via feature measurement and information propagation [D]. Nanjing： Nanjing University of Science and Technology， 2017： 17-29.）

This work is partially supported by the National Natural Science Foundation of China （61802188）， the Natural Science Foundation of Jiangsu Province （BK20180458）， the Jiangsu Planned Project for Postdoctoral Research Fund.

CAO Yunyang， born in 1998. His research interests include applied statistics， image segmentation.

WANG Tao， born in 1990， Ph. D.， associate professor. His research interests include computer vision， image segmentation.