基于多代表點(diǎn)近鄰傳播的大數(shù)據(jù)圖像分割算法

許曉麗

(安徽財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，安徽 蚌埠 233030)

基于多代表點(diǎn)近鄰傳播的大數(shù)據(jù)圖像分割算法

許曉麗

(安徽財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，安徽 蚌埠 233030)

基于多代表點(diǎn)近鄰傳播聚類算法，提出一種有效的大數(shù)據(jù)圖像的快速分割算法。該算法首先運(yùn)用均值漂移算法將彩色圖像分割成很多小的同質(zhì)區(qū)域，然后計(jì)算每個區(qū)域中所有像素的顏色向量平均值，并用區(qū)域數(shù)目代替原圖像像素點(diǎn)數(shù)目，選用區(qū)域間的距離作為相似度的測度指標(biāo)，最后應(yīng)用多代表點(diǎn)近鄰傳播聚類算法在區(qū)域相似度矩陣上進(jìn)行二次聚類，得到最終的圖像分割結(jié)果。實(shí)驗(yàn)結(jié)果證明，提出的算法在大數(shù)據(jù)圖像的分割中取得了較為滿意的分割效果，且分割效率較高。

多代表點(diǎn)近鄰傳播；大數(shù)據(jù)；圖像分割

2007年，F(xiàn)rey等[1-2]提出近鄰傳播(affinity propagation，AP)聚類算法，該算法通過點(diǎn)與點(diǎn)之間的消息傳遞和迭代，收斂到穩(wěn)定的類的劃分。其優(yōu)點(diǎn)在于：不需要事先給定類的個數(shù)，可以對各種數(shù)據(jù)進(jìn)行聚類分析；利用簇的代表點(diǎn)對數(shù)據(jù)進(jìn)行分組，對噪聲點(diǎn)和離群點(diǎn)不敏感，聚類結(jié)果穩(wěn)定，聚類效果更優(yōu)。AP算法用于圖像分割時，根據(jù)像素點(diǎn)間的相似度矩陣進(jìn)行迭代更新運(yùn)算，能夠獲得高質(zhì)量的圖像分割結(jié)果。然而AP算法也存在一些缺點(diǎn)，如計(jì)算復(fù)雜度較高，運(yùn)行時需要調(diào)節(jié)參數(shù)p和λ才能得到想要的類別數(shù)。針對這些不足，很多學(xué)者進(jìn)行了研究，提出了自適應(yīng) AP[3]，軟約束 AP[4]，半監(jiān)督AP[5]，KAP[6]，層次AP(HAP)[7]，多級快速AP(FAP)[8]，多代表點(diǎn)AP(MEAP)[9]等諸多改進(jìn)的算法。

Wang等[9]提出多代表近鄰傳播聚類(multiexemplar affinity propagation，MEAP)，該算法將AP算法的單代表點(diǎn)模型擴(kuò)展到多代表點(diǎn)模型，聚類結(jié)果優(yōu)于AP算法。多代表點(diǎn)模型中的每一個數(shù)據(jù)被分配給最適合的代表點(diǎn)，每個代表點(diǎn)被分配給最適合的超代表點(diǎn)，每一個類都有一個超代表點(diǎn)。該算法采用了最大和置信傳播算法求解多中心點(diǎn)模型的最優(yōu)化問題，無需事先指定聚類數(shù)目，算法可以自動確定代表點(diǎn)數(shù)目，也無需調(diào)節(jié)任何參數(shù)即可實(shí)現(xiàn)自動估計(jì)，利用稀疏性可以進(jìn)一步降低算法的計(jì)算時間和存儲空間。然而MEAP中變量與函數(shù)之間包含7種消息傳遞的計(jì)算，因此MEAP算法的時間和空間復(fù)雜度仍然較高，這就嚴(yán)重限制了該算法在大數(shù)據(jù)圖像分割中的應(yīng)用。

圖像的像素分割問題本身就是一個大規(guī)模樣本集的聚類問題，在目前的硬件條件下，尋求降低MEAP聚類算法復(fù)雜度，減少內(nèi)存消耗的方法和策略顯得尤為重要。計(jì)算機(jī)視覺任務(wù)對復(fù)雜的、大規(guī)模數(shù)據(jù)的圖像進(jìn)行分割時，常常將包含上百萬像素的大圖像轉(zhuǎn)換為幾百或幾千的超像素圖像，然后再對超像素圖像做進(jìn)一步的分割處理，以降低圖像運(yùn)算處理總的復(fù)雜度。本文采用這種分割策略，將MEAP算法應(yīng)用于圖像分割問題中，并在MEAP算法基礎(chǔ)上進(jìn)一步結(jié)合均值漂移(mean shift，MS)算法，提出MSMEAP算法，實(shí)驗(yàn)結(jié)果證明該算法能有效實(shí)現(xiàn)大規(guī)模圖像數(shù)據(jù)的快速分割，分割效果更優(yōu)。

1　多代表點(diǎn)近鄰傳播聚類算法

在MEAP聚類算法中，設(shè)[sij]N×N為擬定義的相似度矩陣，sij表示點(diǎn)i與潛在的代表點(diǎn)j之間的相似度。[lij]N×N為鏈接矩陣，lij表示代表點(diǎn)i與其潛在的超代表點(diǎn)j之間的鏈接度。定義多代表點(diǎn)模型為尋找兩個映射的過程，如下：ψ1:{1,…,N}→{1,…,N}分配點(diǎn)i到代表點(diǎn)ψ1(i)和ψ2:{ψ1(1),…,ψ1(N )}→{ψ1(1),…,ψ1(N)}分配代表點(diǎn)ψ1(i)到超代表點(diǎn)ψ2(ψ1(i))。該模型的目標(biāo)是最大化S1+S2，其中S1為數(shù)據(jù)點(diǎn)與相應(yīng)代表點(diǎn)間所有相似度之和，S2為代表點(diǎn)和相應(yīng)超代表點(diǎn)間所有鏈接度之和。

設(shè)C=[cij]N×N為類分配矩陣，如果cij=1，即ψ1(i)=j ，則非對角元素cij∈{0,1}(j≠i )表示點(diǎn)j是點(diǎn)i的代表點(diǎn)；如果cii={1,…,N}即ψ2(i)=cii，則對角元素cii∈{0,…,N}表示點(diǎn)cii是代表點(diǎn)i的超代表點(diǎn)。即：

數(shù)據(jù)點(diǎn)與相應(yīng)代表點(diǎn)間的相似度之和S1以及代表點(diǎn)與相應(yīng)超代表點(diǎn)間的鏈接度之和S2可以分別表示為：。定義函數(shù)矩陣[Sij(cij)]N×N，其非對角元素是數(shù)據(jù)點(diǎn)i與潛在代表點(diǎn) j間的相似度sij，其對角元素是代表點(diǎn)優(yōu)先權(quán)sii加上代表點(diǎn)i和超代表點(diǎn)cii間的鏈接度 licii，即：

其中，Ii(ci1,…,ciN)為樣本點(diǎn)的N選1約束，Ej(c1j,…,cNj)為代表點(diǎn)的一致性約束，F(xiàn)k(c11,…,cNN)為超代表點(diǎn)一致性約束。多代表點(diǎn)模型在滿足生成有效聚類劃分的條件下(滿足約束I,E,F)，最大化S1+S2能夠有效地刻畫具有多子類結(jié)構(gòu)的類。

2　MSMEAP算法

本文基于MEAP聚類算法和MS算法，提出MSMEAP算法，可以有效實(shí)現(xiàn)大數(shù)據(jù)圖像的快速分割。MSMEAP算法首先應(yīng)用MS算法對原圖像進(jìn)行預(yù)分割，MS算法是指一個迭代的計(jì)算過程[10]。該算法先計(jì)算當(dāng)前點(diǎn)的偏移均值，并移動該點(diǎn)到其偏移均值，然后以此為新的起始點(diǎn)，繼續(xù)移動，直到滿足收斂條件后結(jié)束。MS算法的基本原理如下：

其中，G (y)為核函數(shù)，一般常用高斯函數(shù)作為核函數(shù)。yi,i=1,2,…,n 為d維空間Rd中的樣本點(diǎn)，y表示核函數(shù)的中心，h是帶寬，分為空域帶寬和值域帶寬。MS算法進(jìn)行圖像平滑和分割時，核函數(shù)帶寬是一個重要的參數(shù)，其不但決定了參與迭代的采樣點(diǎn)數(shù)量，而且還會影響算法的收斂速度和準(zhǔn)確性。

MEAP聚類算法是根據(jù)數(shù)據(jù)點(diǎn)之間的相似度進(jìn)行聚類的，在處理圖像數(shù)據(jù)時，計(jì)算相似度矩陣之前需要先定義特征空間。圖像的特征可以選擇顏色、紋理、統(tǒng)計(jì)特性以及形狀等。本文選擇顏色信息作為主要特征，對于彩色圖像，每個點(diǎn)的顏色用一個三維向量表示。MSMEAP算法中，利用 Luv顏色空間定義原圖像中每個像素的顏色向量。設(shè)經(jīng)MS算法預(yù)分割后的圖像被劃分為 N個區(qū)域，每個區(qū)域?qū)?yīng)的顏色向量為，其中分別是第i個區(qū)域內(nèi)所有像素的對應(yīng)顏色分量的平均值，區(qū)域間的相似度定義為：

相似度取負(fù)的歐氏距離，可以理解為距離越小，相似度越大。在圖像分割時，定義MSMEAP算法中的鏈接度矩陣[lij]N×N為 lij=sij/N。根據(jù)已定義的圖像區(qū)域的相似度矩陣和鏈接度矩陣，并通過式(4)的最大化目標(biāo)函數(shù)來求解最優(yōu)的類分配矩陣C。本文采用最大和置信傳播算法來求解這個最優(yōu)問題。

多代表點(diǎn)模型中的消息傳播特性如圖1所示，其中與cij(i≠j)有關(guān)的變量和函數(shù)之間有5種類型的消息傳播(如圖1左)，與cij(i=j)有關(guān)的有7種類型的消息傳播(如圖1右)。將這些消息進(jìn)行系列簡化，可得到如下消息傳播公式：

圖1　多代表點(diǎn)模型的消息傳播

這些消息初始化值均為0，然后應(yīng)用上述消息傳播公式不斷迭代更新，直到收斂。為了估計(jì)類分配矩陣C中的每個元素cij，將輸入到cij的消息值進(jìn)行累加，最優(yōu)的cij就是這個最大化的消息累加值。根據(jù)這個最優(yōu)的類分配矩陣，可以得到兩個映射，從而獲得不依賴于初始化并收斂到近鄰最優(yōu)的聚類結(jié)果。

綜上，本文提出的MSMEAP算法實(shí)現(xiàn)圖像分割的步驟如下：

(1) 利用Luv顏色空間定義原圖像中每個像素的顏色向量，應(yīng)用MS算法對原圖像進(jìn)行預(yù)分割，根據(jù)預(yù)分割的結(jié)果，計(jì)算所有區(qū)域顏色的平均值，將其作為MEAP算法輸入的數(shù)據(jù)點(diǎn)；

(2) 計(jì)算每個同質(zhì)區(qū)域顏色均值的負(fù)的歐氏距離，得到相似度矩陣和鏈接度矩陣；

(3) 消息初始化，設(shè)置MEAP算法迭代參數(shù)：最大迭代次數(shù) tmax=1000，聚類中心連續(xù)迭代不發(fā)生改變次數(shù)；

(4) 根據(jù)相似度矩陣和鏈接度矩陣，應(yīng)用消息傳遞公式進(jìn)行消息的迭代更新，采用最大和信念傳播最大化目標(biāo)函數(shù)直到收斂，得到最優(yōu)的聚類標(biāo)簽(判斷消息迭代的終止條件為：迭代次數(shù)超過設(shè)置的最大迭代次數(shù)或聚類中心連續(xù)多少次迭代不發(fā)生改變)，在每次迭代過程中，cij,i≠j有 5種消息傳播，cij,i=j存在7種消息傳播；

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

3　實(shí)驗(yàn)結(jié)果及分析

本實(shí)驗(yàn)是在MATLAB2008b環(huán)境下進(jìn)行的，計(jì)算機(jī)配置為2.40 GHz Intel core i5-3230M CPU，4 GB內(nèi)存。本文所用圖像均取自Berkeley標(biāo)準(zhǔn)彩色圖像庫BSDS500，圖像大小均為321×481。

實(shí)驗(yàn)內(nèi)容包括3部分：本文提出的MSMEAP算法與K-means算法分割結(jié)果的對比，與MSNcut方法[11]、MSAP[12]在分割效果的對比，以及與人工分割結(jié)果的對比。人工分割標(biāo)注基準(zhǔn)來自于Berkeley標(biāo)準(zhǔn)彩色圖像庫BSDS500。

實(shí)驗(yàn)1. MSMEAP算法與K-means算法分割結(jié)果的比較(如圖2所示)。K-means采用簇成員的均值作為中心，需要事先隨機(jī)設(shè)定K個初始的簇中心，受初值的影響，且分割結(jié)果很不穩(wěn)定，而且 K-means算法對離群點(diǎn)或噪聲點(diǎn)非常敏感[13]。從圖2(b)可以看出，K-means對于3幅圖像的分割，都存在很多噪聲點(diǎn)和離群點(diǎn)，分割效果不理想。而本文提出的MSMEAP算法，分割效果明顯優(yōu)于K-means分割結(jié)果，在抗噪聲點(diǎn)和離群點(diǎn)方面更具有優(yōu)勢。

圖2　與K-means算法圖像分割結(jié)果的對比

實(shí)驗(yàn)2. MSMEAP算法與MSNcut和MSAP方法在分割效果上的對比。圖3為圖像庫中的圖像應(yīng)用本文MSMEAP算法與MSNcut和MSAP方法在分割效果上的對比。MSNcut、MSAP和本文的MSMEAP算法均采用MS算法進(jìn)行預(yù)分割。實(shí)驗(yàn)中MS算法的參數(shù)設(shè)置為h=(hr, hs)=(6, 8)，M=50，hr為值域帶寬，hs為空域帶寬。這樣設(shè)置后，對于文中所用圖像的尺寸來說，MS算法預(yù)分割后的圖像的區(qū)域數(shù)目基本上都在幾百左右，遠(yuǎn)小于圖像像素點(diǎn)的數(shù)目。這樣既有效保留了圖像的細(xì)節(jié)信息，又有效降低了二次聚類的數(shù)據(jù)規(guī)模，大大提高分割效率。MS算法在圖像的Luv顏色空間實(shí)現(xiàn)預(yù)分割，如圖3(b)所示。

從圖 3不同算法分割結(jié)果的對比看，MSNcut算法分割后得到的圖像邊緣呈明顯的鋸齒狀，分割效果不理想，誤差大。MSAP算法比MSNcut算法分割得到的圖像邊緣平滑很多，分割效果要優(yōu)于MSNcut的分割方法。MSAP算法中AP聚類過程最大迭代次數(shù)設(shè)置為 tmax=1 000，連續(xù)迭代過程不發(fā)生改變的次數(shù)設(shè)置為 tconv=50，阻尼系數(shù)λ=0.9。MSAP算法在執(zhí)行時，對于不同的圖像，為了獲得較好的分割效果，需不斷調(diào)整偏向參數(shù)p的取值。對圖3的3幅原始圖像進(jìn)行分割時，MSAP算法中的 p值依次設(shè)置為 p=2×min(sij)，p=0.5×min(sij)，p=0.1×min(sij)。MSMEAP算法中的 p值均設(shè)置為p=0.1×min(sij)，無需調(diào)節(jié)。從圖3(c)～(e)分割結(jié)果看，本文方法分割效果要優(yōu)于MSNcut和MSAP算法。例如圖3中的第2行原始圖像，對于圖中教堂球形頂部的分割，MSNcut和MSAP算法分割的結(jié)果都不夠準(zhǔn)確，而MSMEAP算法分割的結(jié)果就非常理想。又如圖3中的第3行原始圖像，MSNcut和MSAP都沒有分割出山峰頂部的起伏，而 MSMEAP算法卻很好地分了出來，并與人工分割結(jié)果基本一致。

實(shí)驗(yàn)3. MSMEAP算法與人工分割結(jié)果的對比(圖4)。從圖3和圖4的分割結(jié)果綜合比較看，本文方法分割效果良好，與其他算法相比，本文算法的分割結(jié)果更接近于人工分割的結(jié)果。

圖3　不同算法圖像分割結(jié)果的對比

圖4　與人工分割結(jié)果的對比

表 1給出了各算法運(yùn)行時間的比較(運(yùn)行時間為算法運(yùn)行 10次的平均時間)。不難看出，傳統(tǒng)K-means算法由于其具有線性復(fù)雜度，所以與其他算法相比，分割過程中耗時較少，但其分割效果不理想。MSNcut、MSAP和MSMEAP 3種算法都先經(jīng)過MS算法進(jìn)行預(yù)分割，且MS預(yù)分割后的區(qū)域數(shù)目相同(見表1的第二列MS分割區(qū)域數(shù)目)。在此條件下MSNcut、MSAP和MSMEAP 3種算法再經(jīng)Ncut算法、AP算法和MEAP算法分別進(jìn)行二次聚類分割。表1中的3種算法大部分時間都消耗在MS預(yù)處理的過程之中，而二次聚類時，數(shù)據(jù)規(guī)模大幅減小，所以總的耗時都很少。Ncut，AP和MEAP完成二次聚類的時間分別見表1的第6～8列。3種算法實(shí)現(xiàn)區(qū)域合并消耗的時間 Ncut小于 1 s，AP算法在1 s左右，而MEAP耗時略大于1 s，MEAP二次聚類過程時間相對較長。由于MEAP算法中存在7中消息傳播，而AP算法在聚類過程中存在3種消息傳播，所以從算法復(fù)雜度看，MEAP算法耗時是要略大于AP算法的，但也僅在1 s左右?？傮w來看，3種算法總的時間消耗相差不多。

表1　各算法運(yùn)行時間對比

圖像大小為481×321，像素點(diǎn)個數(shù)為154 401，若以單個像素為數(shù)據(jù)點(diǎn)，則聚類前計(jì)算求得的相似度矩陣大小將達(dá)154401×154401。對于如此大的矩陣，若直接應(yīng)用譜聚類、AP聚類或MEAP聚類算法進(jìn)行聚類分割，是相當(dāng)耗時且需要很大的內(nèi)存空間，普通的PC機(jī)可能無法完成，而本文提出的算法中用MS算法預(yù)分割后得到的區(qū)域數(shù)目代替原圖像像素點(diǎn)的數(shù)目，有效地降低了多代表點(diǎn)近鄰傳播聚類算法輸入數(shù)據(jù)的規(guī)模，大大減少了多代表點(diǎn)近鄰傳播聚類算法中計(jì)算相似度矩陣的時間和空間復(fù)雜度，使分割效率得到大幅度的提高，這更充分說明本文算法具有處理大規(guī)模圖像數(shù)據(jù)集的能力。

綜上可見，與 MSNcut，MSAP算法相比，MSMEAP算法應(yīng)用于大數(shù)據(jù)圖像分割是較高效的，且分割效果更優(yōu)。

4　結(jié) 束 語

本文提出一種結(jié)合MS和MEAP的大數(shù)據(jù)圖像快速分割算法。MS計(jì)算復(fù)雜度較低，圖像分割的執(zhí)行效率較高，因此將其用于圖像分割的預(yù)處理。在預(yù)處理的結(jié)果上應(yīng)用 MEAP聚類算法進(jìn)行二次聚類，給出最終的圖像分割結(jié)果。MS與MEAP算法的結(jié)合既保留了 MS的高效率特點(diǎn)，又保留了MEAP 算法聚類質(zhì)量高的特點(diǎn)，取得了雙贏效果。

在來自Berkeley大學(xué)的標(biāo)準(zhǔn)彩色圖像庫的多幅圖像的分割實(shí)驗(yàn)中，MEAP與MS結(jié)合的新分割方法都給出了超越對比分割方法的結(jié)果，再次表明MEAP聚類算法是有效的，同時也表明結(jié)合MS算法設(shè)計(jì)的圖像分割方案是切實(shí)可行的。

此外，實(shí)驗(yàn)對比結(jié)果也充分說明 MEAP結(jié)合MS的新分割方法不僅效果良好，而且執(zhí)行效率也相對較高，適用于大數(shù)據(jù)圖像的分割處理。

[1] Frey B J, Dueck D. Clustering by passing messages between data points [J]. Science, 2007, 315(5814): 972-976.

[2] Mézard M. Computer science. Where are the exemplars? [J]. Science, 2007, 315(5814): 949-951.

[3] 王開軍, 張軍英, 李丹, 等. 自適應(yīng)仿射傳播聚類[J].自動化學(xué)報, 2007, 33(12): 1242-1246.

[4] Sumedha M L, Weigt M. Unsupervised and semi-supervised clustering by message passing: soft-constraint affinity propagation [J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2008, 66(1): 125-135.

[5] Givoni I E, Frey B J. Semi-supervised affinity propagation with instance-level constraints [C]// International Conference on Artificial Intelligence and Statistics. Clearwater Beach, Florida, USA, 2009: 161-168.

[6] Zhang X L, Wang W, N?rvag K, et al. K-AP: generating specified K clusters by efficient affinity propagation [C]// Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010: 1187-1192.

[7] Givoni I, Chung C, Frey B J. Hierarchical affinity propagation [C]//Proceedings of24th Conference Uncertainty in Artificial Intelligence. Barclona, Spain, 2011: 238-246.

[8] Shang F H, Jiao L C, Shi J R, et al. Fast affinity propagation clustering: a multilevel approach [J]. Pattern Recognition, 2012, 45(1): 474-486.

[9] Wang C D, Lai J H, Suen C Y, et al. Multi-exemplar affinity propagation [J]. IEEE Transactions on Pattern Analysis and MachineIntelligence, 2013, 35(9): 2223-2237.

[10] Comaniciu D, Meer P. Mean shift: a robust approach toward feature space analysis [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.

[11] Tao W B, Jin H, Zhang Y M. Color image segmentation based on mean shift and normalized cuts [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2007, 37(5): 1382-1389.

[12] 許曉麗, 盧志茂, 張格森, 等. 改進(jìn)近鄰傳播聚類的彩色圖像分割[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報, 2012, 24(4): 514-519.

[13] 李海洋, 文永革, 何紅洲, 等. 基于隨機(jī)權(quán)重粒子群和K-均值聚類的圖像分割[J]. 圖學(xué)學(xué)報, 2014, 35(5): 755-761.

Big Data Image Segmentation Based on Multi-exemplar Affinity Propagation

Xu Xiaoli

(School of Management Science and Engineering, Anhui University of Finance & Economics, Bengbu Anhui 233030, China)

Based on multi-exemplar affinity propagation clustering, a fast segmentation algorithm is proposed for big data images. The proposed algorithm preprocesses an input big data image by mean shift algorithm to form segmented regions that preserve the desirable discontinuity characteristics of images. The numbers of segmented regions, instead of the numbers of image pixels, are considered as the input data scale of multi-exemplar affinity propagation clustering algorithm. The average of the color vectors in each region is calculated and considered as an input data point of multi-exemplar affinity propagation clustering algorithm. Euclidean distances between regions are regards as similarity measure index, and then the multi-exemplar affinity propagation clustering algorithm is applied to perform globally optimized clustering and segmentation based on similarity matrix. Experimental results illustrate that the proposed algorithm has superior performance and less computational costs compared for big data image segmentation.

multi-exemplar affinity propagation; big data; image segmentation

TP 391.41

10.11996/JG.j.2095-302X.2016010091

A

2095-302X(2016)01-0091-06

2015-09-24；定稿日期：2015-10-10

國家自然科學(xué)基金項(xiàng)目(61102118)；安徽省高校自然科學(xué)研究一般項(xiàng)目(ACKJ2015B01，ACKJ2015B02)

許曉麗(1980–)，女，黑龍江海林人，講師，博士。主要研究方向?yàn)閳D像處理與模式識別。E-mail：xuxlily@126.com