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

許曉麗　趙明濤　高玲

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

關(guān)鍵詞：超像素;快速聚類;圖像分割

中圖分類號： 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 引言

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

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

2 算法實現(xiàn)

2.1超像素圖像的生成

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

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

2.2 多代表點近鄰傳播聚類

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

2.3 相似度矩陣的構(gòu)建

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

2.4 算法實現(xiàn)步驟

本文提出的SLICMEAP算法實現(xiàn)圖像分割的步驟如下。

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

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

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

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

（5）根據(jù)最終輸出的聚類標簽和圖像像素點的映射關(guān)系，得到圖像分割結(jié)果。

3仿真結(jié)果與分析

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

4 結(jié)論

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

參考文獻：

[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] 劉漢強，趙靜.基于半監(jiān)督的超像素譜聚類彩色圖像分割算法[J].計算機工程與應(yīng)用， 2018， 54（14）： 186-190.

【通聯(lián)編輯：唐一東】