摘   要： 針對(duì)解Ncut準(zhǔn)則的SM算法尋優(yōu)能力不足的問題，提出一種基于差分演化優(yōu)化歸一化準(zhǔn)則的彩色圖像分割算法。首先對(duì)彩色圖像進(jìn)行爬山法預(yù)分割為多類，并構(gòu)造類級(jí)間的無向完全圖，之后再使用二進(jìn)制差分演化算法求得Ncut準(zhǔn)則最小化的圖二分，最后通過映射獲得圖像的二值分割。實(shí)驗(yàn)結(jié)果表明，在相同預(yù)處理情況下，本文的尋優(yōu)算法與SM算法相比，分割效果更為精準(zhǔn)。
關(guān)鍵詞： 彩色圖像分割； 差分演化； Ncut準(zhǔn)則； 爬山法

    基于圖論的分割算法是近年來圖像分割領(lǐng)域的研究熱點(diǎn)[1-2]?；趫D論的圖像分割方法通過像素圖像構(gòu)造為帶權(quán)無向圖，通過將圖像映射為加權(quán)的無向圖，再把圖像分割的問題轉(zhuǎn)換成圖的最優(yōu)劃分的問題。基于圖論的分割準(zhǔn)則[2]包括規(guī)范割Ncut(Normalize cut)準(zhǔn)則和最小生成樹MST(Minimum Spanning Tree)準(zhǔn)則等，其中較為常用的是Ncut準(zhǔn)則，其屬于NP難問題。
    使用Ncut準(zhǔn)則存在兩個(gè)難點(diǎn)： (1)當(dāng)圖像尺寸很大時(shí),使用像素構(gòu)造無向帶權(quán)圖將導(dǎo)致相似矩陣規(guī)模很大，內(nèi)存消耗嚴(yán)重； (2)Ncut準(zhǔn)則屬于NP難問題，并沒有精確求出Ncut最優(yōu)解的算法。針對(duì)第一個(gè)問題出現(xiàn)了很多改進(jìn)方法:有的方法先將圖像劃分為若干塊區(qū)域，再使用Ncut方法進(jìn)行分割，例如將分水嶺算法與Ncut結(jié)合[3]；參考文獻(xiàn)[4]將圖像分為若干小塊后每塊使用Ncut方法進(jìn)行分割之后對(duì)分割出的塊再用Ncut方法進(jìn)行分割。這些方法的目的都是通過減少圖中的節(jié)點(diǎn)數(shù)從而縮減權(quán)值矩陣，以降低計(jì)算復(fù)雜度，提高算法效率。而對(duì)于第二個(gè)問題，在實(shí)際應(yīng)用中常常采用近似的求解算法。Shi和Malik[1]提出的SM算法考慮了問題的連續(xù)放松形式，將原問題轉(zhuǎn)換成求解相似矩陣或拉普拉斯矩陣的譜分解，通過求解廣義特征方程,得到對(duì)圖劃分準(zhǔn)則的逼近，但是SM算法求得的解也只是近似解。
    針對(duì)使用Ncut準(zhǔn)則圖像分割的兩個(gè)難點(diǎn)，參考文獻(xiàn)[5]提出一種基于遺傳算法優(yōu)化Ncut準(zhǔn)則的灰色圖像分割算法。受此啟發(fā)，本文提出一種基于Ncut方法的彩色圖像分割算法：首先用爬山法對(duì)彩色圖像進(jìn)行初次分類，將像素聚類成c類，初次分類縮減了權(quán)值矩陣的規(guī)模；之后求出c類區(qū)域的相似矩陣，采用在求解NP-hard問題上具有更強(qiáng)尋優(yōu)能力的二進(jìn)制差分演化算法代替SM算法尋求最優(yōu)Ncut值的圖二分。實(shí)驗(yàn)結(jié)果表明，在同等預(yù)處理的條件下，本文的算法相比SM能夠更精確地將目標(biāo)分割出來。

    實(shí)驗(yàn)結(jié)果表明，采用本文的二進(jìn)制差分演化優(yōu)化Ncut準(zhǔn)則的彩色圖像分割算法相比SM算法在運(yùn)行時(shí)間略高的情況下能夠得到有更為精確的分割出目標(biāo)。
參考文獻(xiàn)
[1] Shi Jiaobo， MALIK J． Normalized cuts and image segmen tation[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é)報(bào)， 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ì)算機(jī)工程與應(yīng)用， 2010,46(33):148-150，157.
[6] 賀朝毅,王熙照，冠應(yīng)展，等.一種具有混合編碼的二進(jìn)制差分演化算法[J].計(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.