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

許曉麗　趙明濤　高玲

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

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

中圖分類號(hào)： TP18? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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 引言

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

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

2 算法實(shí)現(xiàn)

2.1超像素圖像的生成

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

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

2.2 多代表點(diǎn)近鄰傳播聚類

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

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

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

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

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

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

（2）計(jì)算每個(gè)超像素顏色均值，并求得超像素間顏色均值的負(fù)的歐氏距離作為超像素的相似度，構(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]及消息傳遞公式，完成消息的迭代更新，采用最大和信念傳播最大化目標(biāo)函數(shù)直到收斂，得到最優(yōu)的聚類標(biāo)簽;

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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