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

關(guān)鍵詞：超像素；聚類；SLIC；APMMD

中圖分類號：TP181文獻(xiàn)標(biāo)志碼：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均值方法采用距離作為相似性指標(biāo)，將數(shù)據(jù)分為k組，隨機(jī)選取k個(gè)對象作為初始的聚類中心，然后計(jì)算每個(gè)對象與各個(gè)種子聚類中心的距離，把每個(gè)對象獨(dú)立地分配給距離它最近的聚類中心［2］。此時(shí)，聚類中心和它的對象就是一個(gè)聚類。但是該方法使用聚類中所有點(diǎn)的均值作為新的中心點(diǎn)，如果簇中存在異常點(diǎn)將導(dǎo)致均值偏差較為嚴(yán)重，并且可能只能收斂到局部最優(yōu)［3］。分析上述兩種缺點(diǎn)，發(fā)現(xiàn)傳統(tǒng)的k均值聚類算法對管壁污漬識別和零件盒零件分類并不能實(shí)現(xiàn)很好的分割效果。

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

1 傳統(tǒng)SLIC算法

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

1.1 顏色空間轉(zhuǎn)換

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

1.2 種子點(diǎn)選取和調(diào)整

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

種子點(diǎn)的調(diào)整與聚類的準(zhǔn)確性息息相關(guān)。初始化種子點(diǎn)時(shí)，存在種子點(diǎn)落于輪廓邊界的可能性；當(dāng)該可能性發(fā)生時(shí)，聚類的效果和準(zhǔn)確性將直線下降，故需對種子點(diǎn)進(jìn)行調(diào)整。調(diào)整方式一般是將圖片均分為多個(gè)3×3區(qū)域，然后計(jì)算每個(gè)3×3區(qū)域內(nèi)的像素點(diǎn)的梯度值，找到梯度最小的位置，將種子點(diǎn)移動(dòng)到該位置進(jìn)行更新。

1.3 計(jì)算顏色距離和空間距離

顏色距離和空間距離主要用來判斷該像素點(diǎn)屬于哪個(gè)種子點(diǎn)，將其規(guī)劃到距離最近的種子點(diǎn)，即：

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

2 本文算法

本文算法的主要是從顏色空間轉(zhuǎn)換時(shí)保存的數(shù)據(jù)類型和種子點(diǎn)的初始化選取兩個(gè)方面考慮。主要方法是用APMMD算法來代替Kmeans算法的隨機(jī)選取。

2.1 具體優(yōu)化方向

1）顏色空間數(shù)據(jù)類型優(yōu)化

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

a）RGB轉(zhuǎn)XYZ空間，理論轉(zhuǎn)換公式如下：

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分量的轉(zhuǎn)換系數(shù)和分別是0.950 456和1.088 754，兩者都不為1，因此需對其進(jìn)行歸一化處理來修正系數(shù)，修正后X的轉(zhuǎn)換系數(shù)為0.433 953、0.376 219、0.189 828；Z的轉(zhuǎn)換系數(shù)為0.017 758、0.109 477、0.872 765。由于公式里面存在大量小數(shù)系數(shù)，固X、Y、Z理論上都應(yīng)該是浮點(diǎn)數(shù)，此時(shí)通過類型強(qiáng)制轉(zhuǎn)換成整型可能會(huì)導(dǎo)致內(nèi)存暴增并且效率十分低下。本文采用放大系數(shù)然后將結(jié)果右移的方法，很好地避免了類型強(qiáng)制轉(zhuǎn)換和效率較低的缺點(diǎn)。值得注意的是，放大后的系數(shù)在保證不超過Int的最大范圍時(shí)取值越大越好。最后，本文采用的轉(zhuǎn)換公式為：

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轉(zhuǎn)Lab空間。由于前文通過公式求出XYZ分量的取值范圍為［0，255］，并且f（t）中的變量t的取值范圍是［0，1］，因此需將其歸一化映射到［0，1］范圍。最后XYZ到Lab的轉(zhuǎn)換公式為：

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為參考白點(diǎn)的XYZ三色刺激值；f（t）為計(jì)算顏色空間轉(zhuǎn)換的函數(shù)，將其分為兩段是為了避免在t=0處出現(xiàn)無限斜率。

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

2）初始化種子點(diǎn)優(yōu)化

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

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

2.2 算法流程圖

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

3 圖像分割驗(yàn)證實(shí)驗(yàn)

3.1 實(shí)驗(yàn)結(jié)果圖分析

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

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

3.2 評價(jià)指標(biāo)

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

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

4 結(jié)語

本文通過對經(jīng)典SLIC算法的實(shí)現(xiàn)步驟進(jìn)行分析，從RGB轉(zhuǎn)Lab顏色空間和采用APMMD算法初始化種子點(diǎn)兩方面對其進(jìn)行優(yōu)化，進(jìn)行了實(shí)驗(yàn)驗(yàn)證，證明了顏色空間轉(zhuǎn)換時(shí)速度和內(nèi)存都有進(jìn)步；種子點(diǎn)聚類時(shí)，聚類準(zhǔn)確率提高、迭代次數(shù)下降。

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

參考文獻(xiàn)：

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

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

［3］ 程艷云，周鵬. 動(dòng)態(tài)分配聚類中心的改進(jìn)K均值聚類算法［J］. 計(jì)算機(jī)技術(shù)與發(fā)展，2017，27（2）：33-36.

［4］ 王美琪，李建. 一種改進(jìn)K-means聚類的近鄰傳播最大最小距離算法［J］. 計(jì)算機(jī)應(yīng)用與軟件，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主題模型的文本檢索方法及有效性驗(yàn)證［J］. 情報(bào)科學(xué)，2017，35（2）：16-21，26.

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

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