摘 要： 针对解Ncut准则的SM算法寻优能力不足的问题，提出一种基于差分演化优化归一化准则的彩色图像分割算法。首先对彩色图像进行爬山法预分割为多类，并构造类级间的无向完全图，之后再使用二进制差分演化算法求得Ncut准则最小化的图二分，最后通过映射获得图像的二值分割。实验结果表明，在相同预处理情况下，本文的寻优算法与SM算法相比，分割效果更为精准。
关键词： 彩色图像分割； 差分演化； Ncut准则； 爬山法
基于图论的分割算法是近年来图像分割领域的研究热点[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能够更精确地将目标分割出来。
实验结果表明，采用本文的二进制差分演化优化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.