陳瑞南，劉秉瀚

（福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 福州350108）

基于圖論的分割算法是近年來圖像分割領(lǐng)域的研究熱點(diǎn)[1-2]?；趫D論的圖像分割方法通過像素圖像構(gòu)造為帶權(quán)無向圖，通過將圖像映射為加權(quán)的無向圖，再把圖像分割的問題轉(zhuǎn)換成圖的最優(yōu)劃分的問題?；趫D論的分割準(zhǔn)則[2]包括規(guī)范割Ncut(Normalize cut)準(zhǔn)則和最小生成樹MST(Minimum Spanning Tree)準(zhǔn)則等，其中較為常用的是Ncut準(zhǔn)則，其屬于NP難問題。

使用Ncut準(zhǔn)則存在兩個難點(diǎn)：(1)當(dāng)圖像尺寸很大時,使用像素構(gòu)造無向帶權(quán)圖將導(dǎo)致相似矩陣規(guī)模很大，內(nèi)存消耗嚴(yán)重；(2)Ncut準(zhǔn)則屬于NP難問題，并沒有精確求出Ncut最優(yōu)解的算法。針對第一個問題出現(xiàn)了很多改進(jìn)方法:有的方法先將圖像劃分為若干塊區(qū)域，再使用Ncut方法進(jìn)行分割，例如將分水嶺算法與Ncut結(jié)合[3]；參考文獻(xiàn)[4]將圖像分為若干小塊后每塊使用Ncut方法進(jìn)行分割之后對分割出的塊再用Ncut方法進(jìn)行分割。這些方法的目的都是通過減少圖中的節(jié)點(diǎn)數(shù)從而縮減權(quán)值矩陣，以降低計算復(fù)雜度，提高算法效率。而對于第二個問題，在實際應(yīng)用中常常采用近似的求解算法。Shi和Malik[1]提出的SM算法考慮了問題的連續(xù)放松形式，將原問題轉(zhuǎn)換成求解相似矩陣或拉普拉斯矩陣的譜分解，通過求解廣義特征方程,得到對圖劃分準(zhǔn)則的逼近，但是SM算法求得的解也只是近似解。

針對使用Ncut準(zhǔn)則圖像分割的兩個難點(diǎn)，參考文獻(xiàn)[5]提出一種基于遺傳算法優(yōu)化Ncut準(zhǔn)則的灰色圖像分割算法。受此啟發(fā)，本文提出一種基于Ncut方法的彩色圖像分割算法：首先用爬山法對彩色圖像進(jìn)行初次分類，將像素聚類成c類，初次分類縮減了權(quán)值矩陣的規(guī)模；之后求出c類區(qū)域的相似矩陣，采用在求解NP-hard問題上具有更強(qiáng)尋優(yōu)能力的二進(jìn)制差分演化算法代替SM算法尋求最優(yōu)Ncut值的圖二分。實驗結(jié)果表明，在同等預(yù)處理的條件下，本文的算法相比SM能夠更精確地將目標(biāo)分割出來。

1 背景知識

1.1 Ncut準(zhǔn)則與SM算法[1]

一幅無向圖G=(V;E)可以劃分為兩個不連接的頂點(diǎn)集C1和 C2。C1和 C2的不相似程度可以用如式(1)計算：

其中，權(quán)重w(u,v)表示節(jié)點(diǎn)u和v的相似性程度。圖的最優(yōu)二劃分的目的是找到一個最小化cut(C1,C2)。然而,以式(1)為標(biāo)準(zhǔn)的分割方法存在偏向小區(qū)域的情形，如圖1所示其容易劃分出孤立點(diǎn)。

為了克服上述缺點(diǎn)，Shi和Malik提出了一種新的衡量相似性劃分準(zhǔn)則，即為正則化(Ncut)劃分：

其中 assoc(C1,V)=Σu∈A,t∈Vw(u,v)表示頂點(diǎn)集 C1與 V 之間的連接邊的權(quán)值總和。同理，assoc(C2,V)表示為頂點(diǎn)集C2與V之間連接邊的權(quán)值總和。

求最優(yōu)Ncut最優(yōu)值是一個NP難問題,為此,Shi和Malik[1]將這一NP難問題轉(zhuǎn)化為銳利問題（SM算法），從而求得有效的近似解。設(shè)N為頂點(diǎn)數(shù)總和，d(i)=Σjw(i,j)為節(jié)點(diǎn)i與其他頂點(diǎn)的連接權(quán)之和，D是d的對角矩陣；W為 N×N的對稱矩陣且 W(i,j)=w(i,j)。則Ncut最小值的問題近似地轉(zhuǎn)化為如下形式：

如果將y的取值放松至實數(shù)范圍，式(3)的最優(yōu)化問題相當(dāng)于求解如下矩陣方程：

通過式(4)的第二小特征值對應(yīng)的特征向量y=(y1,y2,…,yN)即為該問題的解。之后需要從y中取得一個分割值 yi將 頂 點(diǎn) 集 劃 分 為 C1和 C2(C1={Vi｜yi＞0},C2={Vi｜yi≤0}))，通常取向量 yi=0或 y的中值。

1.2 二進(jìn)制混合差分演化算法

差分演化算法(DE)是一種基于實數(shù)編碼的具有保優(yōu)思想的貪婪遺傳算法。算法主要有變異、交叉和選擇3個操作，由于這3個算子簡單有效，使得DE比粒子群和遺傳算法的收斂速度更快，全局收斂性能更優(yōu)。賀毅朝等學(xué)者[6]通過引入了“輔助搜索空間”和“個體混合編碼”等概念而提出了第一個二進(jìn)制DE算法，并稱之為二進(jìn)制混合差分演化算法(HBDE)。HBDE已被證明完全收斂，具有DE所有的優(yōu)點(diǎn)，非常適用于求解離散域上的最優(yōu)化問題。

HBDE將個體混合編碼為(X,B)，其中X是d維實數(shù)型搜索向量，B是d維二進(jìn)制評價向量。設(shè)種群規(guī)模為NP，第t代中間種群中第i個中間個體的編碼為(Xi(t),Bi(t)),其中:

差異算子：

其中，p1≠p2≠p3≠i，1≤i≤NP,1≤j≤d,參數(shù) F∈[0,2]為縮放因子，通常F=0.5是一個較好的初始值；r是[0,1]之間的隨機(jī)數(shù)；CR∈[0,1]是交叉概率，大的 CR通常會加速收斂；R(i)是[1,n]上的一個隨機(jī)整數(shù)用以保證至少有一個個體產(chǎn)生變異；Sig(x)=1/(1+e-x)。

選擇算子：

其中 f(·)是個體評價函數(shù)。

2 優(yōu)化Ncut準(zhǔn)則的圖像分割方法

以像素為單位構(gòu)造權(quán)值矩陣再采用Ncut準(zhǔn)則對圖像進(jìn)行分割，矩陣規(guī)模很大，耗時嚴(yán)重。為此本文提出一種解決策略，先用爬山法對彩色圖像預(yù)先分成c類區(qū)域，之后采用彩色向量均值作為區(qū)域的描述向量。由于圖像被壓縮為c類，將c類一分為二的NP難最優(yōu)化問題可采用二進(jìn)制混合差分演化算法求得最優(yōu)解。

2.1 基于爬山法的彩色圖像初始化分割[7-8]

爬山法通過兩個步驟在RGB色彩空間下將圖像分割為具有較好一致性的數(shù)個圖像區(qū)域。該方法首先求出整幅圖像的三維RGB彩色直方圖的局部極大值；然后將c個局部極大值作為聚類中心，通過k-means算法將圖像聚類為c個一致性保持得較好區(qū)域。整個算法控制參數(shù)僅有每個通道的直方圖柱數(shù)BinNum。

2.2 構(gòu)造無向帶權(quán)圖

通過爬山法處理，圖像I將劃分為c類區(qū)域，即I=I1∪I2…∪Ic。將每一塊的區(qū)域作為圖G的節(jié)點(diǎn)。

2.3 使用差分演化算法優(yōu)化Ncut準(zhǔn)則

以式(2)為評價函數(shù)，采用通過二進(jìn)制差分演化算法將2.2節(jié)構(gòu)造出的c類區(qū)域分為兩類(C1和C2)的組合尋優(yōu)算法，具體步驟如下：

(1)初始化種群。初始化HBDE的種群大小為NP，交叉概率為CR，縮放因子為F，輔助搜索空間為[-a,a]d。隨機(jī)產(chǎn)生 NP個體，每個個體為(X,B)，其中 X=(x1,x2,…,xc)為實數(shù)編碼對應(yīng)于輔助空間，B=(b1,b2,…,bc)為對應(yīng)的二進(jìn)制編碼。

(2)適應(yīng)度函數(shù)的設(shè)計。采用式（2）的Ncut準(zhǔn)則作為個體的適應(yīng)值。

(3)評價個體。種群的單個個體對應(yīng)的二進(jìn)制編碼B=(b1,b2,…,bc)的取為1和為0的基因分別代表圖G的頂點(diǎn)屬于C1和C2，查找權(quán)值矩陣 Wc求得個體對應(yīng)的cut(C1,V)、和 cut(C1,C2)，之后通過式（2）求得個體的適應(yīng)值。

(4)變異與選擇。采用式(5)、(6)對種群的個體進(jìn)行變異，采用式(7)進(jìn)行選擇操作。

(5)變異與選擇是否達(dá)到指定的迭代次數(shù)tmax，若達(dá)到，則當(dāng)前最優(yōu)適應(yīng)值個體對應(yīng)的分類結(jié)果為最佳的分割效果，否則重復(fù)步驟(4)。

通過上述二進(jìn)制差分演化算法迭代多次優(yōu)化后得到的最優(yōu)適應(yīng)值個體所對應(yīng)的個體Bbest即為使圖最小化的分割。 將最優(yōu)個體的二進(jìn)制編碼中為0和為1的區(qū)域分為兩組C1和C2即可得到最終的圖像二值化分割結(jié)果。

2.4 算法流程

綜上所述，本文所提出基于HBDE優(yōu)化的Ncut準(zhǔn)則的圖像分割算法整體流程為：

(1)采用爬山法將彩色圖像聚為c類，從而使得圖像I=I1∪I2…∪Ic。

(2)按照式(8)，用區(qū)域的彩色分量均值向量計算兩兩區(qū)域的相似性，從而構(gòu)造出無向帶權(quán)完全圖Gc=(Vc,Wc)。

(3)使用二進(jìn)制混合差分演化算法，迭代選擇、變異操作多次到指定次數(shù)tmax，從而求得使Ncut準(zhǔn)則最小化的圖兩類分割的最優(yōu)個體。

(4)將最優(yōu)個體對應(yīng)的二進(jìn)制編碼的分類結(jié)果重新映射到原圖像，使圖像二值化。

3 實驗結(jié)果及分析

本文的實驗平臺為Microsoft Windows XP professional、Matlab2010b，CPU 為 Intel Core 1.86 GHz,內(nèi)存為2 GB，選取2幅來自公共數(shù)據(jù)集[9]的真彩色圖像,分別采用本文算法和SM算法進(jìn)行分割,效果如圖2、圖3所示。實驗中的參數(shù)為：爬山法的參數(shù)BinNum=20；經(jīng)過多次實驗,相似性計算式(8)中的參數(shù)σ=5;差分演化算法種群大小 NP=10 c,采用 DE/r/1/bin模式,輔助空間向量 a=5，最大迭代次數(shù)tmax=200;SM算法的分割值取yi=0。

為了對比二進(jìn)制差分演化優(yōu)化最小化Ncut準(zhǔn)則與SM算法的分割效果，現(xiàn)將實驗結(jié)果分析如下：

(1)船。由于水波的色彩與船身相近，SM算法在水面波紋方面過分割，對比SM算法，本文算法能夠更為清晰地的分割出船身。

(2)鸚鵡。背景的4個外角偏暗，使用SM算法受此干擾使得背景欠分割。采用本文的算法能夠較為準(zhǔn)確地分割出鸚鵡的整體，效果優(yōu)于SM算法。

從表1的Ncut值可以看出，二進(jìn)制差分演化算法比SM算法有更好的尋優(yōu)能力。SM算法采用近似解法難免出現(xiàn)分割效果不佳的情況，二進(jìn)制差分演化算法有較強(qiáng)的尋優(yōu)能力因而能夠找到更為理想的分割解。表1亦可使用差分演化算法尋優(yōu),運(yùn)行時間略多于SM算法。

表1 兩種分割算法的得到的時間對比

實驗結(jié)果表明，采用本文的二進(jìn)制差分演化優(yōu)化Ncut準(zhǔn)則的彩色圖像分割算法相比SM算法在運(yùn)行時間略高的情況下能夠得到有更為精確的分割出目標(biāo)。

[1]Shi Jiaobo， MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22(8)：888-905.

[2]SOUNDARARAJAN P,SARKAR S.Analysis of mincut,average cut and normalized cut measures[C].Proceedings of the 3rd Workshop on Perceptual Organization in Computer Vision.Vancouver，Canada，2001：1-4.

[3]馮林,孫燾，吳振宇，等.基于分水嶺變換和圖論的圖像分割方法[J].儀器儀表學(xué)報，2008，29(3):649-653.

[4]TUNG F,WONG A.Enabling scalable spectral clustering for image segmentation[J].Pattern Recognition，2010(43):4069-4076.

[5]翟艷鵬，郭敏,馬苗，等.遺傳算法優(yōu)化歸一化劃分準(zhǔn)則的圖像分割[J].計算機(jī)工程與應(yīng)用，2010,46(33):148-150，157.

[6]賀朝毅,王熙照，冠應(yīng)展，等.一種具有混合編碼的二進(jìn)制差分演化算法[J].計算機(jī)研究與發(fā)展，2007，44(9):1476-1484.

[7]OHASHI T,AGHBARI Z,MAKINOUCHI A.Hill-climbing algorithm for efficient color-based image segmentation[C].IASTED International Conference on Signal Processing,Pattern Recognition,and Applications(SPPRA 2003),2003:17-22.

[8]ACHANTA R,ESTRADA F,WILS P,et al.Salient region detection and segmentation[C].International Conference on Computer Vision Systems(ICVS 2008),2008:66-75.

[9]MARTIN D,FOWLKES C,MALIK D T J.A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[C].Proceedings of IEEE International Conference on Computer Vision,2001,1(2):416-423.