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

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

    實(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.