基于SLIC與APMMD結合的圖像分割算法研究

摘 要：超像素是由一系列特征相似且位置相鄰的像素點組成的小區域。采用超像素分割既能降低圖像分割的復雜度，又能更好地保留局部信息及邊緣信息。針對管壁污漬識別和零件盒零件分類的要求，將SLIC與基于近鄰傳播最大-最小距離算法（APMMD）結合使用來達到更好的圖像分割效果。該方法根據傳統SLIC算法的步驟，在顏色空間轉換時通過數據類型轉換來優化內存；在均勻分配初始種子點之前，增加APMMD算法來解決初始聚類中心不合理導致聚類結果局部最優的問題，可在一定范圍內防止種子點落在梯度較大的輪廓邊界上。通過邊界召回率和欠分割錯誤率驗證了所提算法，發現其顏色空間轉換時內存減少1.5 M，聚類時準確率提高了8.1%。

關鍵詞：超像素；聚類；SLIC；APMMD

中圖分類號：TP181文獻標志碼：A文章編號：1671-5276（2024）03-0141-05

Research on Image Segmentation Algorithm Based on Combination of SLIC and APMMD

Abstract：A superpixel is a small region consisting of a series of pixel points with similar features and adjacent positions. The use of superpixel segmentation can both reduce the complexity of image segmentation and better preserve local information and edge information. For the requirements of tube wall stain recognition and parts box part classification， SLIC is used in combination with the nearest neighbor propagation based maximum minimum distance algorithm （APMMD） to achieve better image segmentation results. The method optimizes memory by data type conversion during color space conversion according to the steps of traditional SLIC algorithm. Before uniform assignment of initial seed points， the APMMD algorithm is added to solve the problem of unreasonable initial clustering centers leading to locally optimal clustering results， which can prevent seed points from falling on contour boundaries with large gradients within a certain range. The proposed algorithm is verified by the boundary recall rate and under-segmentation error rate， and it is found that its memory is reduced by 1.5 M during color space conversion， and the accuracy rate is improved by 8.1 percentage points during clustering.

Keywords：superpixel；clustering；SLIC；APMMD

0 引言

2003年，REN等［1］在研究中第一次提出了超像素的概念。簡單的線性迭代聚類算法SLIC采用k均值方法高效地生成超像素。k均值方法采用距離作為相似性指標，將數據分為k組，隨機選取k個對象作為初始的聚類中心，然后計算每個對象與各個種子聚類中心的距離，把每個對象獨立地分配給距離它最近的聚類中心［2］。此時，聚類中心和它的對象就是一個聚類。但是該方法使用聚類中所有點的均值作為新的中心點，如果簇中存在異常點將導致均值偏差較為嚴重，并且可能只能收斂到局部最優［3］。分析上述兩種缺點，發現傳統的k均值聚類算法對管壁污漬識別和零件盒零件分類并不能實現很好的分割效果。

近年來，在圖像分割、目標檢測識別方面的超像素分割方法得到了快速發展，特別是在工業視覺方面。本文采用王美琪等［4］提出的近鄰傳播最大-最小距離算法來代替SLIC的Kmeans聚類方法。該算法考慮了近鄰傳播算法，具有更高的魯棒性及能夠保證收斂到全局最優的特點，用其來獲取K1個候選中心點；然后再從K1個候選中心點中通過最大-最小距離算法選取K個點作為初始聚類中心，很好地避免了隨機性，對更復雜的聚類形狀適應性好。通過實驗發現將該方法用于SLIC算法較傳統SLIC算法有著更好的分割結果，迭代次數減少，邊緣分割更為明顯且分割效果更好；缺點是會在單個物體內部產生一些無關邊界，主要是由于連通性較差引起的，但該邊界對分割結果的準確率不會產生太大影響。

1 傳統SLIC算法

2010年，ACHANTA等［5］提出了局部聚類算法SLIC，該算法基于Lab顏色距離dc和空間距離ds，能很好地保留下一步的有效信息，并且對圖像的邊界信息保留很好。SLIC的三大要素分別是：RGB圖像空間轉換至Lab顏色空間、初始化種子點選取及調整、顏色距離和空間距離的計算。SLIC分割的效果主要受這三大要素的影響，特別是種子點的選取和調整。

1.1 顏色空間轉換

Lab相對于RGB空間來說有著更寬闊的色域和豐富的色彩，彌補了RGB模型從藍色到綠色之間的過渡色彩過多和從綠色到紅色之間缺少黃色及其他色彩的缺點。

1.2 種子點選取和調整

種子點是SLIC聚類的起點。現有的種子點選取是基于半自動的，可人為設定圖像分割時所需的聚類中心個數，然后根據圖像的大小均勻分配種子點。假設圖片高h、寬w，人為設定種子點個數k，則超像素的尺寸為h×w/k，兩相鄰種子點距離為sqrt（h×w/k）。該半自動方式雖然適用范圍廣，但是對經驗知識要求高，容易局部收斂。

種子點的調整與聚類的準確性息息相關。初始化種子點時，存在種子點落于輪廓邊界的可能性；當該可能性發生時，聚類的效果和準確性將直線下降，故需對種子點進行調整。調整方式一般是將圖片均分為多個3×3區域，然后計算每個3×3區域內的像素點的梯度值，找到梯度最小的位置，將種子點移動到該位置進行更新。

1.3 計算顏色距離和空間距離

顏色距離和空間距離主要用來判斷該像素點屬于哪個種子點，將其規劃到距離最近的種子點，即：

式中：dc代表顏色距離；ds代表空間距離；Ns是類內最大空間距離；Nc表示最大顏色距離；D則為計算出來的最終聚類度量。

2 本文算法

本文算法的主要是從顏色空間轉換時保存的數據類型和種子點的初始化選取兩個方面考慮。主要方法是用APMMD算法來代替Kmeans算法的隨機選取。

2.1 具體優化方向

1）顏色空間數據類型優化

Lab是由兩個顏色通道（a代表綠色到紅色的分量，b代表藍色到黃色的分量）和一個亮度通道L組成的，是基于人類的視覺來設計的。相對于RGB空間來說，Lab有著更精確的顏色平衡，人眼對其感知也更加均勻［6］。在原始SLIC論文中，顏色空間轉換時是采用double類型來保存轉換結果，最后強制轉換成整型，導致內存空間占用是直接用整型類型來存儲的8倍。因此是RGB到Lab顏色空間的數據優化。本文采用直接將公式系數放大來避免double類型的方法，共分為兩步：

a）RGB轉XYZ空間，理論轉換公式如下：

X=0.412 453×R+0.357 580×G+0.180 423×B（6）

Y=0.212 671×R+0.715 16×G+0.072 169×B（7）

Z=0.019 334×R+0.119 193×G+0.950 227×B（8）

上述公式中，由于原始X、Z分量的轉換系數和分別是0.950 456和1.088 754，兩者都不為1，因此需對其進行歸一化處理來修正系數，修正后X的轉換系數為0.433 953、0.376 219、0.189 828；Z的轉換系數為0.017 758、0.109 477、0.872 765。由于公式里面存在大量小數系數，固X、Y、Z理論上都應該是浮點數，此時通過類型強制轉換成整型可能會導致內存暴增并且效率十分低下。本文采用放大系數然后將結果右移的方法，很好地避免了類型強制轉換和效率較低的缺點。值得注意的是，放大后的系數在保證不超過Int的最大范圍時取值越大越好。最后，本文采用的轉換公式為：

X=（455 033×R+394 494×G+199 049×B+524 288）20（9）

Y=（223 002×R+749 900×G+75 675×B+524 288）20（10）

Z=（18 621×R+114 795×G+915 161×B+524 288）20（11）

b）XYZ轉Lab空間。由于前文通過公式求出XYZ分量的取值范圍為［0，255］，并且f（t）中的變量t的取值范圍是［0，1］，因此需將其歸一化映射到［0，1］范圍。最后XYZ到Lab的轉換公式為：

Xn=Yn=Zn=1（12）

f（t）=t1/3， tgt;（6/29）3（13）

f（t）=1/3×（29/6）2×t+4/29， t≤（6/29）3（14）

L=116f Y/Yn-16（15）

a=500f X/Xn-f Y/Yn（16）

b=200f Y/Yn-f Z/Zn（17）

式中：Xn、Yn、Zn為參考白點的XYZ三色刺激值；f（t）為計算顏色空間轉換的函數，將其分為兩段是為了避免在t=0處出現無限斜率。

根據上述的理論分析，將本文方法與原始論文中采用的轉換方法對比，對一幅480 px×640 px的圖片進行RGB轉Lab，從表1可以看出，通過python運行其速度和內存都有很大的進步。

2）初始化種子點優化

Kmeans算法是一種十分典型的基于距離的算法，它認為兩個點之間距離越小就越有可能屬于同一個樣本［7］。本文為了去除Kmeans隨機性而導致的局部收斂，在SLIC的種子點均勻選取之前增加近鄰傳播最大-最小距離算法。該方法首先通過AP算法獲得K1個具有代表性的候選中心點；該候選點是從全局尋找的最優點，它對數據的初始樣本是不敏感的，并且不會存在遠離聚類的異常點。然后再通過最大-最小距離算法從K1中選出K個初始種子點。選取原則為：①選取距離最遠的兩個候選點作為前兩個聚類中心Z1、Z2；②計算其余所有點分別與Z1、Z2的距離Di1、Di2，比較Di1、Di2，選擇其中較小的一個；③將上一步獲取的所有值進行比較，選擇最大值對應的點作為第三個聚類中心Z3；4）若Z3存在，則計算剩余的點分別與Z1、Z2、Z3的距離Di1、Di2、Di3，重復②、③，選擇出第四個聚類中心；⑤以此類推，直到聚類中心數量滿足要求為止。最后，將獲得的初始聚類中心采用Kmeans的迭代方法更新聚類中心點，直至聚類收斂。

對Iris數據集采用Kmeans聚類算法和近鄰傳播最大-最小距離算法。從圖 1可以看出，Kmeans聚類算法由于初始聚類中心是隨機選擇的，初始誤差較大，導致其后續迭代次數增加，而迭代次數增加必定導致時間消耗和內存占用增加，聚類中心更改的范圍較大；而近鄰傳播最大-最小距離算法獲得的初始聚類中心對Iris數據集是基本適用的，并且該適用性也增加了每次迭代收斂的速度，APMMD獲得的初始聚類中心與最終聚類中心也較為接近。最后對兩種算法的準確率ACC進行比較：ACC，Kmeans=0.892，ACC，APMMD=0.973。

2.2 算法流程圖

綜上所述，算法流程圖如圖 2所示。

3 圖像分割驗證實驗

3.1 實驗結果圖分析

圖像分割是指按照一定的相似性準則將圖像劃分成具有特殊語義的不同區域［8］；具體可分為3類：基于圖論的方法、基于梯度下降的聚類方法和基于深度語義的方法。而SLIC就是基于梯度下降的聚類方法中的一種，除此之外還有分水嶺方法和Mean-shift方法［9］。

本文采用基于LY公司數字化裝配項目實拍的零件盒及其內零件的數據集來驗證SLIC與APMMD算法結合的圖像分割結果。如圖 3所示，本文算法的效果明顯優于原始SLIC算法。譬如在超像素平均尺寸為20時，第1行圖像中零件盒里第1列中第2個零件和第3個零件的輪廓在本文算法中清晰完整地呈現出來了；而在SLIC算法中，第2個零件和第3個零件的輪廓就沒能完全分割出來。第2行圖像中也是本文算法輪廓分割較好；但其中也顯示了兩個算法都具備的一個缺點：連通性較差，易將兩個像素差距較小的零件分配給同一超像素。第3行圖像用來證明該結合方法的適用性，從圖中可以看出，SLIC會將天鵝翅膀的羽毛棱角分配給湖面的超像素，而天鵝翅膀輪廓在本文算法中清晰可見。如圖 4所示，發現當超像素平均尺寸減少時，本文結合算法和原始SLIC算法分割效果都有一定的改善；但是不宜過小，會導致超像素塊變成為像素點，其無關邊界會增加，失去了超像素更好的特征表達能力。因此，建議超像素平均尺寸的大小控制在20左右，這樣不會產生較多的過分割輪廓，分割效果也符合期望值。

3.2 評價指標

對結果圖像的分析，可以從視覺方面發現兩者的優劣，但缺少有效性方面的證明。因此，通過計算兩者的邊界召回率和欠分割錯誤率來對有效性進行證明（圖5）。邊界召回率指的是正確預測為邊界的值占所有邊界的比重；欠分割錯誤率指的是前景目標誤識別為背景的部分占前景目標整體的比重。

由圖 5可以明顯看出，采用APMMD初始聚類中心的方法分割效果明顯優于Kmenas的隨機選取方法。

4 結語

本文通過對經典SLIC算法的實現步驟進行分析，從RGB轉Lab顏色空間和采用APMMD算法初始化種子點兩方面對其進行優化，進行了實驗驗證，證明了顏色空間轉換時速度和內存都有進步；種子點聚類時，聚類準確率提高、迭代次數下降。

實驗中也發現：本文算法存在過分割的可能性，且容易生成無關邊界，特別是對亮度高的物品生成的無關邊界更多。因此，下一步的研究方向可以從增強連通性、去除無關邊界兩方面考慮。

參考文獻：

［1］ REN X F ， MALIK J. Learning a classification model for segmentation［C］//Proceedings Ninth IEEE International Conference on Computer Vision. Nice，France：IEEE，2008：10-17.

［2］ 周麗娟，王慧，王文伯，等. 面向海量數據的并行Kmeans算法［J］. 華中科技大學學報（自然科學版），2012，40（增刊1）：150-152.

［3］ 程艷云，周鵬. 動態分配聚類中心的改進K均值聚類算法［J］. 計算機技術與發展，2017，27（2）：33-36.

［4］ 王美琪，李建. 一種改進K-means聚類的近鄰傳播最大最小距離算法［J］. 計算機應用與軟件，2021，38（7）：240-245.

［5］ ACHANTA R，SHAJI A，SMITH K，et al. SLIC superpixels compared to state-of-the-art superpixel methods［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（11）：2274-2282.

［6］ DONG L L ， ZHANG W D ， XU W H. Underwater image enhancement via integrated RGB and LAB color models［J］. Signal Processing：Image Communication，2022，104：116684.

［7］ 劉江華. 一種基于kmeans聚類算法和LDA主題模型的文本檢索方法及有效性驗證［J］. 情報科學，2017，35（2）：16-21，26.

［8］ 宋熙煜，周利莉，李中國，等. 圖像分割中的超像素方法研究綜述［J］. 中國圖象圖形學報，2015，20（5）：599-608.

［9］ 王春瑤，陳俊周，李煒. 超像素分割算法研究綜述［J］. 計算機應用研究，2014，31（1）：6-12.