引言

图像分割是计算机视觉技术的关键任务之一，是许多图像处理任务的预处理步骤。图像分割的目的是将图像分割成人们感兴趣的，具有一致特性的区域。图像分割具有目标物体的灰度值、边缘信息等特点，为图像语义理解等图像处理提供条件。从20世纪60年代开始，图像分割一直是图像处理领域的研究热点之一，它广泛应用于医学图像分析、工件无损分析、雷达图像分析、地质勘探等领域。

传统的图像分割方法包括基于阈值的分割方法^[1-2]、基于边缘检测的分割方法^[3-6]和基于区域的分割方法^[7]等。其中阈值分割方法因其实现简单，性能较稳定而成为最广泛的分割技术。阈值分割是通过选择合适的阈值将目标与背景分离，为了得到最优阈值，OTSU^[1]提出了最大类间方差阈值分割算法; KESAVAN等人^[7]提出了最大熵阈值法; DOLYE^[8]提出的基于灰度直方图的阈值分割方法，这是一种基于灰度直方图的自动阈值选择方法，该方法具有较好的抗噪声性能，但需预先知道目标物体与图像的面积百分比，所以这种方法在面积百分比未知或随图像变化而变化将无法得到准确的分割图像。基于边缘检测的图像分割方法通过大幅度减少数据量，同时保存目标边界的结构信息来从而简化图像分析。基于区域的图像方法能有效地利用图像区域信息。然而，这些方法选取阈值时仅仅考虑了像素的灰度值，并没有进行考虑像素之间的相互关系，当图像的信噪比下降时，图像的分割效果将会急剧下降。为了解决这一问题，ABUTALEB^[9]提出了基于2维最大熵的图像分割方法, 结果表明，在低信噪比条件下，2维最大熵方法的分割性能上优于1维最大熵分割方法。但是，这种改进只是把1维寻优扩展为2维寻优，简单的扩展将导致计算量大幅增涨，耗费大量时间，不利于图像的实时处理。

简单遗传算法存在收敛性差、早熟等问题，很难找到最优阈值^[11]。如何提高收敛速度、解决早熟问题已成为关键问题。为了解决2维阈值法计算量大的问题，本文中提出了一种基于改进遗传算法的自动阈值图像分割方法。将遗传算法应用于获得最优阈值，可以大大提高图像阈值分割的效率^[10]。作者通过适当改进遗传算法的变异操作，将最大熵分割方法与遗传算法相结合，在改进遗传算法的基础上对2维阈值进行优化，从而得到可以在2维空间中快速寻优的图像自动阈值分割方法。

1.   2维最大熵阈值分割

2维最大熵阈值分割综合了点灰度值和相邻区域像素点平均值的信息得到分割图像的阈值。首先，假设输入图像大小为M×N，那么像素点的灰度值f(x, y)的取值范围为0≤f(x, y)≤L－1，其中L一般取值为256, (x, y)为图像中取样点的坐标，且1≤x≤M，1≤y≤N。通过计算像素点g(x, y)的四领域像素点的灰度平均值得到平滑图像，其像素点灰度值记为0≤g(x, y)≤L－1，那么，图像中的每一个像素点将对应一个由点灰度和区域灰度均值构成的2维向量。设n_ij为图像点灰度值f(x, y)=i、区域灰度均值g(x, y)=j的像素点出现的频数，p_ij为对应(i, j)发生的概率，记为${p_{ij}} = \frac{{{n_{ij}}}}{{M \times N}}$，所得到的{p_iji, j=0, 1, …, L－1}构成输入图像的点灰度和区域灰度值的2维直方图。从图 1、图 2中可以看出，p_ij的高峰主要集中分布在平面图的对角线附近，因为图像中的目标像素点和背景像素点占图像像素比例最大，并且其内部像素灰度值较均匀，点灰度值与区域灰度值相差不大，所以集中在对角线附近。图 2中的2维直方图呈现出近似双峰的状态，分别对应图像中的目标与背景。图 1是一般的2维直方图的平面图，其中A代表目标、B代表背景、C代表边界, D代表噪声。因为图像中的边界和噪声像素比例小，所以此处不考虑C区域和D区域^[12-16]。

Figure  1.  Planar graph of 2-D histogram

下载: 全尺寸图片 幻灯片

Figure  2.  Schematic diagram of 2-D histogram

下载: 全尺寸图片 幻灯片

2维熵算法中的符号如表 1所示。

Table  1.  Symbol definition of the algorithm

symbol	meaning
s	point gray threshold
t	gray mean value threshold of region
pij	probability of occurrence of vector (i, j)
pA	the posterior probability of object region A
pB	the posterior probability of background region B
H(A)	the 2-D entropy of object region A
H(B)	the 2-D entropy of background region B

下载: 导出CSV 

| 显示表格

2维熵算法的步骤如下：设A区和B区具有不同的概率分布，用A区和B区的后验概率分别对A区和B区的概率p_ij进行归一化处理，当阈值为向量(s, t)时，则:

式中, i=0, 1, …, s; j=0, 1, …, t。

式中, i=s+1, s+2, …, L－1;j=t+1, t+2, …, L－1。那么A区和B区的2维熵分别是：

式中, ${H_A} =-\sum\limits_i {\sum\limits_j {{p_{ij}}\lg {p_{ij}}} }$, 且式中条件满足i=0, 1，…, s; j=0, 1, …, t。

式中, ${H_B} =-\sum\limits_i {\sum\limits_j {{p_{ij}}\lg {p_{ij}}} }$, 且i=s+1, s+2, …, L－1;j=t+1, …, L－1。

则熵的判别式为：

由于此处不考虑C区和D区，则可以简化判别式：

式中, ${H_L} =-\sum\limits_i {\sum\limits_j {{p_{ij}}\lg{p_{ij}}} }$, 且i=0, 1, …, L－1;j=0, 1, …, L－1。则有：

则熵的判别式可以写为：

通过下式可以得到最佳阈值向量(s, t)：

2.   基于改进遗传算法的最大熵阈值算法

进化算法是人工智能领域的研究热点之一，其灵感源于达尔文的生物进化论。进化算法包含了许多经典算法，如遗传算法(genetic algorithm, GA)、遗传编程(genetic programming, GP)、进化规划(evolutionary programming, EP)等，这些算法利用了启发式方法寻找问题的最优解。

遗传算法是模拟了自然界生物进化过程，最初由密歇根大学的HOLLAND^[17]提出，其基本思想是借鉴了生物在自然环境中是通过自然选择和有性繁殖两个基本过程不断的进化，使群体适应环境的变化。研究者把组合优化问题的解空间中的每个解视为一个生物个体，将解的搜索过程模拟为一个生物进化过程，通过目标函数模拟自然环境，那么较优解的获得就如同生物的优胜劣汰所得的优势个体。遗传算法是一种独立于问题的高效优化算法，与粒子群和人工鱼群等现代优化算法相比，具有明显的优势。然而，传统的遗传算法存在明显的局限性，如算法的收敛速度和算法容易陷入局部最优解等问题。为此，许多研究者通常在传统遗传算法的基础上对遗传算法进行改进或是引入一些优化算法对遗传算法进行优化。

遗传算法由3个重要的操作组成, 即选择、交叉和变异，如图 3所示。

Figure  3.  Three important operations of genetic algorithm

下载: 全尺寸图片 幻灯片

选择：选择最大适应值染色体和另一个随机选择的染色体用于后续的交叉和变异。

交叉：对两个染色体进行交叉重组，并产生新的染色体。

变异：将变异过程引入种群中，使得种群能发生随机变化，目的在于引导算法从局部最大值中跳出，从而找到问题的全局解。

本文中目的是利用改进的遗传算法优化2维熵的计算速度，那么就要求改进后的遗传算法收敛速度尽量的快。所以，作者提出了一种方案，具体如图 4所示，这种方案极大地提高了遗传算法的收敛速度和寻优能力。

Figure  4.  Flow diagram of the improved GA algorithm

下载: 全尺寸图片 幻灯片

2.1   编码机制

遗传算法采用二进制编码时，进行交叉操作时的搜索能力比十进制编码的搜索能力强，且随着群体规模的扩大这种差别会越来越明显^[18]。因此，本文中采用二进制编码对解进行编码。图像灰度值的范围为0~255，则以00000000~11111111之间的某个二进制代码作为分割阈值。2维熵的分割阈值可以用16位的二进制进行表示，前8位表示为s，后8位表示为t。

2.2   初始化群体

如果种群的规模设置过大，个体适应度评价次数增多，遗传算法的收敛速度降低; 种群规模设置过小，会导致早熟现象的发生，所得解为局部最优解，并且小群体容易产生遗传漂变现象^[19]。本文中采用种群规模M=20，在(0, 0)~(255, 255)间随机产生20个个体，所有个体用二进制进行表示，构成原始种群。

2.3   适应度评价

二进制个体由十进制解码得到(s, t)，上述2维熵计算公式为适应度评价函数，将(s, t)代入适应度评价函数得到对应的适应度函数值。个体适应度评价函数的值越大，越有可能被选中。

2.4   选择

本文中首先采用精英保留策略，选择上代种群中最优秀的个体，直接成为下一代的第21位特殊个体。这保证了每次遗传繁殖时，最优个体不受交叉和变异操作破坏。换言之，每次的遗传繁殖得到的个体不可能比上一代时的个体差。然后，利用蒙特卡洛方法选择出20个繁殖备选父体。

2.5   交叉

交叉是遗传算法的至关重要的一步操作。传统遗传算法多采用简单的单点交叉操作，随着人们对遗传算法的深入研究，提出了许多不同的交叉操作，如两点交叉、多点交叉、均匀交叉。根据SRINIVAS等人^[20-22]的研究证明了均匀交叉要优于多点交叉，更加广义化，所以本文中采用均匀交叉。均匀交叉将每个点都作为了潜在的交叉点^[23-26]，所以，这里不设置交叉率。从繁殖备选父体中随机抽取出两个个体，通过均匀交叉操作算子得到下一代的两个个体。

2.6   变异

变异算子的目的是更新现有种群，并在不同区域中获得新个体，从而避免局部最优解的快速出现，因此，能够使得遗传算法克服早熟现象^[27]。优化问题中的最优解中的每个个体上的基因称为有效基因，POTTS等人^[28]认为有效等位基因的缺损是早熟现象产生的主要原因，经过上述的选择策略得到的群体中，优秀基因位会迅速占据群体等位基因。然而，交叉不会在等位基因上产生新的基因，从而导致有效基因的丢失。为了防止早熟现象的产生，遗传算法必须保持等位基因多样性。大多数的遗传算法采用了单基因单点取反的变异方法。事实上，这种方法很难避免早熟现象的产生。针对这一问题，YANG等人^[29]提出了二元变异操作。然而，对于2维阈值分割问题，从不同阈值所得的熵可能是相同的，那么经过蒙特卡罗选择法所得的种群将会具有大量相似基因个体，即最优个体占据群体。如果继续使用二元变异操作会造成全0以及全1个体的大量出现，导致遗传算法无法收敛。

基于上述问题，本文中提出了一种结合一元和二元变异操作的多重变异操作方法。具体实施步骤如下：(1)设置变异概率。这里的变异概率具有两种功能, 首先，生物变异在自然环境中是不确定的, 每个个体对应随机产生一个0~1之间的数，将变异概率与随机数相比较，如果随机数小于变异概率时，则相应个体将执行变异操作; 其次，在确定变异个体后，变异概率的作用转化为对变异点数的确定, 确定后变异点数后，随机产生变异位，并进行取反操作; (2)对非完全相似个体，通过比较随机产生数来确定出需要执行二元变异操作的个体。然后两两进行同或与异或运算，所得两个个体取代原有个体作为下一代个体。

此处的变异概率前期设置为p_f=0.2，进化代数超过10后变异概率改为p_b=0.4，前期设置低突变概率是为了能尽可能在同一地区搜索更久。后期，同一地区几乎已经收敛到了区域最优，因此，需要更高的变异率使搜索区域更新更快。

2.7   终止准则

当算法执行达到设置的最大迭代次数或是群体中的最高适应度值变化不大时，算法终止，然后对所得最优个体进行解码，从而得到最佳2维熵分割阈值，否则继续循环进化。

3.   实验结果及分析

本文中将输入的灰度图像大小调整为280×272。遗传算法的参量包括：群体规模M=20，最大遗传代数G=1000，变异概率p_f=0.2，p_b=0.4。

当图像被熵分割时，每个候选的阈值都需要经过一次熵的计算。假设一次熵的计算时间是一个固定值T。对于灰度级为256的灰度图像，进行1维熵分割时需要进行256次熵的计算，因此，总的计算时间为256T。在2维熵分割时需要进行256×256次熵的计算，总的计算时间为256×256T=65536T。当采用普通遗传法与2维熵结合时，通过进行250次实验，得出其进化代数均值为104代，由于设置的种群数为20，所以实际总的计算时间为104×20T=2080T。采用改进遗传算法与2维熵结合时，同样进行250次实验，得出其进化代数均值为60代，由于种群数仍然为20，所以实际计算时间为60×20T=1200T。从表 2中的平均时间对比可知，无论是普通的遗传算法，还是经过改进的遗传算法都优于通过穷尽法计算的2维熵算法。然而，这些方法仍然比1维熵所用时间长，并且对于未加噪声的原始图像，使用1维熵分割图像的效果和用2维熵算法分割图像的效果是很接近的，这从图 5中就可以发现。但是，当图像添加噪声后，采用2维熵算法分割图像明显优于使用1维熵算法分割图像，分析图 6即可得出这一结论。

Table  2.  Performance comparison of segmentation algorithms

	s	t	average values of evolutionary algebra	averagetime/s
1-D entropy(exhaustion)	66			0.479241
2-D entropy(exhaustion)	66	62		491.4612
2-D entropy(common GA)	65	141	104	9.35342
2-D entropy(modified GA)	71	105	60	0.958795

下载: 导出CSV 

| 显示表格

Figure  5.  a—segmented by 1-D entropy without noise b—segmented by 2-D entropy without noise

下载: 全尺寸图片 幻灯片

Figure  6.  a—segmented by 1-D entropy with noise b—segmented by 2-D entropy with noise

下载: 全尺寸图片 幻灯片

基于改进遗传算法的图像分割实验可视化为图 7和图 8。从这些结果图可知，1维和2维熵的结果接近于穷举法(对于有噪声或无噪声的图像)。通过实验证明了基于改进遗传算法最大2维熵分割是可行的。

Figure  7.  a—segmented by combining 1-D entropy and GA without noise b—segmented by combining 2-D entropy and GA without noise

下载: 全尺寸图片 幻灯片

Figure  8.  a—segmented by combining 1-D entropy and GA with noise b—segmented by combining 2-D entropy and GA with noise

下载: 全尺寸图片 幻灯片

需要说明的是：本文中采用MATLAB语言对遗传算法进行改进并实现。实验环境为：Window7系统，4G内存，MATLAB R2010b平台。

4.   结论

遗传算法对于问题的依赖性小，适用于大多数优化问题，使用遗传算法可以很好的解决2维最大熵计算量大的问题。本文中提出了一种将一元和二元变异相结合的遗传算法，在提高普通遗传算法的收敛速度的同时，保证了种群的多样性，避免了局部最优解的大量出现。将改进遗传算法和最大2维熵的结合可以得到理想的分割图像。遗传算法为解决复杂优化问题提供了一个通用的框架，这不取决于问题的特定领域。遗传算法因其具有很强的鲁棒性，在许多学科中得到了广泛的应用, 在未来具有很大的研究价值。