差分演化优化Ncut准则的彩色图像分割*
2012-08-08陈瑞南刘秉瀚
陈瑞南,刘秉瀚
(福州大学 数学与计算机科学学院,福建 福州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类,初次分类缩减了权值矩阵的规模;……
