一種基于超像素的快速聚類圖像分割算法

許曉麗　趙明濤　高玲

摘要：本文提出一種基于超像素的快速聚類圖像分割算法。該算法采用超像素分割策略，將多代表點近鄰傳播聚類算法應用于大規模圖像數據的分割中，并與簡單線性迭代聚類結合，實現快速圖像分割。從結果看，提出的算法在進行大規模圖像數據分割時，可以獲得較好的分割效果，且分割效率較高。

關鍵詞：超像素;快速聚類;圖像分割

中圖分類號： TP18? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）25-0235-02

Abstract： This paper proposes a fast clustering image segmentation algorithm based on superpixels. The proposed algorithm uses the superpixels segmentation strategy， and employs multi-exemplar affinity propagation clustering algorithm to large-scale image data segmentation. The proposed algorithm combines with a simple linear iterative clustering and obtains fast image segmentation effect. Experimental results illustrate that the proposed algorithm has superior performance and less computational costs compared for big data image segmentation.

Key words： superpixels; fast clustering; image segmentation

1 引言

圖像分割是一種基本的計算機視覺技術，是圖像預處理的關鍵步驟。在實際應用中，圖像分割結果的好壞將直接影響到后續圖像理解、識別和分類的精度。目前，超像素分割已成為一種重要圖像預處理工具，深受國內外研究者的普遍關注。超像素利用像素間的相似性特征對像素點進行分組，用少量超像素描述圖像總體特征，使圖像后處理的復雜度降低，算法后續執行效率大幅提升。

簡單線性迭代聚類（simple linear iterative clustering，SLIC）是一種超像素分割方法，SLIC基于顏色和距離相似性進行分割，生成形狀規則且大小均勻的超像素。多代表點近鄰傳播（multi-exemplar affinity propagation，MEAP）聚類根據數據間相似度進行聚類，可以獲得很好的聚類結果，但由于其具有很高的計算復雜度而難以用于大規模圖像數據的快速分割。本文提出一種基于超像素的快速聚類圖像分割算法—SLICMEAP算法，該算法采用超像素分割策略，將多代表點近鄰傳播（MEAP）聚類應用于大規模圖像數據的分割中，并與簡單線性迭代（SLIC）聚類結合，實現圖像快速分割。從結果看，提出的算法在進行大規模圖像數據分割時，可以獲得較好的分割效果，且分割效率較高。

2 算法實現

2.1超像素圖像的生成

SLIC算法是近年來流行的超像素分割算法，SLIC依據像素點空間距離和顏色相似特征進行局部迭代聚類。該算法首先初始化[K]個聚類中心，這些聚類中心在圖像上均勻分布;然后遍歷所有像素點，并將每一個像素點分配給與其距離最近的聚類中心，最后采用K-means聚類方法高效地生成超像素。SLIC有兩種距離：空間距離和顏色距離。當遍歷每個像素點時，分別計算該像素點和中心點的距離。距離計算包括以下幾個公式。

其中，[ds]是空間距離，[dc]是顏色距離，[Ns]是類內最大空間距離，定義為[Ns=S=sqrt（N/K）]， 對每個聚類均適用。圖像不同，聚類不同，則最大的顏色距離[Nc]也隨之變化。

2.2 多代表點近鄰傳播聚類

多代表點近鄰傳播聚類模型定義了代表點和超代表點，遍歷每個數據，將數據分配給最適合的代表點，每個代表點又分配給最適合的超代表點。在多代表點近鄰傳播（Multi-exemplar affinity propagation，MEAP）聚類中，設相似度矩陣為[[sij]N×N]，其含義是點[i]與潛在的代表點[j]之間的相似度。設鏈接矩陣為[[lij]N×N]，其含義是點[i]與其潛在的超代表點[j]之間的鏈接度。多代表點模型是尋找兩個映射的過程，最大化[S1+S2]是該模型的目標，這里數據點與相應代表點間所有相似度之和是[S1]，代表點和相應超代表點間所有鏈接度之和是[S2]。

2.3 相似度矩陣的構建

多代表點近鄰傳播聚類根據數據點間的相似度進行聚類，由相似度形成相似度矩陣，求解相似度矩陣時，對于圖像我們需定義其特征空間。本文圖像特征選取顏色信息，在彩色圖像中，每點的顏色用三維向量表示。本文提出的算法中，設輸入圖像經SLIC預分割后得到[N]個超像素區域[Ri（i=1，2，…，N）]，每個超像素的顏色向量為[ZRi=（z1i，z2i，z3i）]，其中[z1i，z2i，z3i]分別是第[i]個超像素區域內所有像素顏色均值。定義超像素間的相似度為[sij=-||ZRi-ZRj||2]，取負的歐氏距離作為相似度，即距離越小，相似度越大。在圖像分割時，定義本文算法的鏈接度矩陣[[lij]N×N]為[lij=sijN]。 根據定義的超像素相似度矩陣和鏈接度矩陣，本文算法求解最優的類分配矩陣[C]采用目標函數最大化，并進一步采用最大和置信傳播算法求這個最優問題。

2.4 算法實現步驟

本文提出的SLICMEAP算法實現圖像分割的步驟如下。

（1） 應用SLIC算法對原圖像進行預分割，得到超像素圖像。該步驟中對SLIC算法參數進行合理設置，得到超像素區域大概在幾百左右。

（2）計算每個超像素顏色均值，并求得超像素間顏色均值的負的歐氏距離作為超像素的相似度，構建相似度矩陣和鏈接度矩陣，即[[sij]N×N]和[[lij]N×N];

（3）MEAP算法消息初始化及其參數設置：最大迭代次數[tmax=1000]，連續迭代直到聚類中心不發生改變的次數[tconv=100]，[λ=0.9];

（4）根據[[sij]N×N]、[[lij]N×N]及消息傳遞公式，完成消息的迭代更新，采用最大和信念傳播最大化目標函數直到收斂，得到最優的聚類標簽;

（5）根據最終輸出的聚類標簽和圖像像素點的映射關系，得到圖像分割結果。

3仿真結果與分析

本實驗實現環境為MATLAB2014b，選擇Berkeley大學的標準彩色圖像庫的多幅圖像進行仿真實驗，圖像大小為481×321。圖1是本文SLICMEAP算法，SLICDBSCAN方法及人工分割結果在分割效果上的對比。原始圖像首先經SLIC預分割得到超像素圖像，如圖1（b）所示。預分割后的超像素個數基本在幾百左右，遠小于圖像像素點的個數，這樣圖像細節信息有效保留的同時，很好地降低了后續聚類處理的數據規模，分割效率大幅提升。后處理算法分別采用DBSCAN和MEAP獲得的分割結果如圖1（c）（d）所示，人工分割結果如圖（e）所示，可以看出本文算法分割效果更優。從算法運行時間看，SLIC預處理時間相對較長，大約10s， DBSCAN和MEAP兩種算法后續處理時間很短，約0.2s。因此，可以知道，算法中SLIC預處理過程消耗大部分時間，到二次聚類時，數據規模大幅度減小，總耗時很少。

4 結論

本文提出一種基于超像素的快速聚類圖像分割算法，選擇Berkeley大學的標準彩色圖像庫的多幅圖像進行仿真實驗，實驗結果表明該方法獲得了較好的分割效果，且分割效率較高。

參考文獻：

[1] R. Achanta， A. Shaji， K. Smith， 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.

[2] C. D. Wang， J. H. Lai， C. Y. Suen， et al. Multi-exemplar affinity propagation[J]. IEEE transactions on Pattern Analysis and MachineIntelligence， 2013， 35（9）： 2223-2237.

[3] 劉漢強，趙靜.基于半監督的超像素譜聚類彩色圖像分割算法[J].計算機工程與應用， 2018， 54（14）： 186-190.

【通聯編輯：唐一東】