差分演化優化Ncut準則的彩色圖像分割*

陳瑞南，劉秉瀚

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

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

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

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

1 背景知識

1.1 Ncut準則與SM算法[1]

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

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

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

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

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

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

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

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

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

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

差異算子：

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

選擇算子：

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

2 優化Ncut準則的圖像分割方法

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

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

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

2.2 構造無向帶權圖

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

2.3 使用差分演化算法優化Ncut準則

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

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

(2)適應度函數的設計。采用式（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)變異與選擇是否達到指定的迭代次數tmax，若達到，則當前最優適應值個體對應的分類結果為最佳的分割效果，否則重復步驟(4)。

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

2.4 算法流程

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

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

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

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

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

3 實驗結果及分析

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

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

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

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

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

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

實驗結果表明，采用本文的二進制差分演化優化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]翟艷鵬，郭敏,馬苗，等.遺傳算法優化歸一化劃分準則的圖像分割[J].計算機工程與應用，2010,46(33):148-150，157.

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