差分演化優(yōu)化Ncut準則的彩色圖像分割*

陳瑞南，劉秉瀚

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

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

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

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

1 背景知識

1.1 Ncut準則與SM算法[1]

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

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

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

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

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

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

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

1.2 二進制混合差分演化算法

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

HBDE將個體混合編碼為(X,B)，其中X是d維實數(shù)型搜索向量，B是d維二進制評價向量。設種群規(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]之間的隨機數(shù)；CR∈[0,1]是交叉概率，大的 CR通常會加速收斂；R(i)是[1,n]上的一個隨機整數(shù)用以保證至少有一個個體產(chǎn)生變異；Sig(x)=1/(1+e-x)。

選擇算子：

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

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

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

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

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

2.2 構造無向帶權圖

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

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

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

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

(2)適應度函數(shù)的設計。采用式（2）的Ncut準則作為個體的適應值。

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

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

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

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

2.4 算法流程

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

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

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

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

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

3 實驗結果及分析

本文的實驗平臺為Microsoft Windows XP professional、Matlab2010b，CPU 為 Intel Core 1.86 GHz,內(nèi)存為2 GB，選取2幅來自公共數(shù)據(jù)集[9]的真彩色圖像,分別采用本文算法和SM算法進行分割,效果如圖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。

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

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

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

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

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

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

[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].儀器儀表學報，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)化歸一化劃分準則的圖像分割[J].計算機工程與應用，2010,46(33):148-150，157.

[6]賀朝毅,王熙照，冠應展，等.一種具有混合編碼的二進制差分演化算法[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.