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

    基于圖論的分割算法是近年來圖像分割領域的研究熱點[1-2]?；趫D論的圖像分割方法通過像素圖像構造為帶權無向圖，通過將圖像映射為加權的無向圖，再把圖像分割的問題轉換成圖的最優劃分的問題。基于圖論的分割準則[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能夠更精確地將目標分割出來。

    實驗結果表明，采用本文的二進制差分演化優化Ncut準則的彩色圖像分割算法相比SM算法在運行時間略高的情況下能夠得到有更為精確的分割出目標。
參考文獻
[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]. 儀器儀表學報， 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.