图1 自适应遗传算法流程图
Fig.1 Flow chart of adaptive genetic algorithm
激光图像处理是指通过特定方式对激光图像进行变换，使其满足人或者机器对图像进行理解使用的要求.激`光图像处理包括图像分割、图像边缘提取、图像增强和图像降噪[1-4]等多个方面，其中图像分割是激光图像处理中重要而基础的处理环节，能够为后续的目标识别等操作提供基础图像.图像分割是指根据图像本身的灰度、颜色和纹理等特征将图像分成特定的区域块并提取出所需目标的技术.目前对图像进行分割处理的普遍思想是对图像分块建立数学模型，找出所需目标与背景之间的差异，然后依据该差异将图像分成所需的两部分或多个部分.具体的方法包括区域跟踪分割法、膨胀和腐蚀分割法、阈值化分割法、边缘检测分割法和最大类间方差分割法[5-7]等.而最大类间方差分割法由于其出色的性能，成为了一种经典的图像分割方法.
传统的最大类间方差法利用图像类间方差最大时所对应的灰度值来对图像进行分割.阈值的计算是通过遍历搜索的方式实现，当图像较大时，存在运算量大、计算效率低的缺陷.而自适应遗传算法[8-11]由于具有并行运算、适应能力强和搜索能力强等特点，可以从全局角度出发，并行计算找出最优阈值.此外自适应性可以动态调整算法执行过程中的变异概率和交叉概率，使算法在快速全局搜索的同时提高局部搜索的准确性.本文提出了一种基于自适应遗传算法的激光图像处理算法，利用自适应遗传算法求取图像的最优阈值，再利用最大类间方差法对图像进行分割，能够准确迅速地实现对激光图像的分割处理.
自适应遗传算法是在遗传算法的基础上发展起来的.遗传算法通过对染色体个体进行选择、交叉和变异等操作得到满足要求的最优个体，但是其不能客观真实地反映在种群进化过程中染色体个体对环境的适能力，忽略了染色体个体随环境的改变而产生的遗传学上的自适应性，因此在算法的性能和执行效率等方面存在改进的空间.为了解决遗传算法的不足，产生了更加高效可靠的自适应遗传算法.
自适应遗传算法从提高算法执行效率和结果准确性的角度考虑，当种群中个体的适应度值差异比较大时，说明种群中的基因类型很丰富，需要给予个体大的交叉概率和小的变异概率；反之个体之间适应度值差异较小时，说明种群中的基因类型比较单一，需要给予个体小的交叉概率和大的变异概率.因此在种群进化的初期，需要通过大范围的搜索来保证全局进化并避免算法过早收敛到局部最优，在种群进化的后期通过加强局部搜索来对重要数据进行重点进化，加快进化的速度并收敛于最优解.由于遗传算法所得结果主要由丰富有效的进化和保存好的进化结果两方面决定，所以自适应遗传算法从进化过程自适应调整和优等进化结果保留两个方面进行改进.在进化过程自适应方面，自适应遗传算法结合个体的适应度值和进化代数来设计交叉概率和变异概率的自适应调节公式，动态得出个体在进化过程中的交叉概率和变异概率；在优等进化结果保留方面，根据执行交叉和变异操作后个体适应度值来决定个体的去留.
自适应遗传算法的工作步骤分为确定适应度函数、种群复制及选择、种群变异和交叉及执行进度控制4个方面，其实现流程如图1所示.
图1 自适应遗传算法流程图
Fig.1 Flow chart of adaptive genetic algorithm
图1中每个步骤的具体内容为：
1) 根据实际求解问题的需要明确目标函数，按照取值非负和越大越优的原则将目标函数变换成适应度函数.自适应遗传算法就是求使适应度函数最大的个体值.设定迭代的最大次数、迭代结束的条件及其他相关参数的数值，然后将所有解空间的数据按照特定的规则表示成基因型数据串结构数据.产生所需的M个串结构数据构成种群，其中每个串结构数据代表一个个体.
2) 利用适应度函数计算种群中所有个体的适应度值.对适应度值高的N个个体进行复制，形成新的种群.将其余适应度值低的个体剔除.
3) 按照配对原则和交叉概率对种群中个体的相应位数进行交叉操作，再按照变异原则和变异概率对种群中个体的相应位数进行变异操作，将变换过后的个体组成新的种群.交叉概率和变异概率由相应的调节公式计算得到.
由前述分析可知，交叉概率和变异概率需要满足以下规则：
① 适应度值较小的个体需要较大的交叉概率和较小的变异概率.
② 适应度值较大的个体需要根据适应度值的情况和迭代次数赋予相应的交叉概率和变异概率.
③ 随着迭代次数的增加，个体的交叉概率应减小，变异概率应增大，交叉概率和变异概率的调节公式可定义为
(1)
(2)
式中：pc为交叉概率；pm为变异概率；k1、k2为固定常数；φ为相似系数，用于衡量种群中个体之间适应度值的相似程度，其定义为
(3)
式中：EX为种群中个体适应度值的均值；DX为种群中个体适应度值的方差，两者定义式为
(4)
(5)
式中：Num为种群中个体的数量；fi为个体的适应度值.由相似系数、均值和方差的定义可知，要使相似系数值增大，需要具有大的均值和小的方差.当算法的迭代过程不断进行时，种群中个体的适应度值不断增大，并且个体之间的适应度值越来越相似.此时均值增大，方差减小，从而相似系数增大，进而交叉概率减小，变异概率增大，算法逐渐趋于最优解.
4) 当迭代次数小于最大迭代次数并且不满足迭代停止条件时，跳转到步骤2)继续执行；否则停止迭代，适应度值最大的个体即为所需的最优解.
最大类间方差法通过对图像的灰度直方图进行处理，基于目标与背景之间的方差最大值来寻找图像分割的阈值.其不需要附加先验知识，仅利用了图像灰度直方图的0阶和1阶矩，具有广泛的适应性，是激光图像分割的一种重要方法.
假设图像中像素点个数为M，像素点的灰度等级为L，灰度值为i的像素点的个数为ni，则图像中各个灰度值的概率可表示为pi=ni/M.如果以灰度值t为界限将图像的像素点分成两部分，灰度值小于t的像素点为区域A，灰度值大于t的像素点为区域B，则两个区域的概率分别表示为
(6)
(7)
两类区域的灰度均值、图像的灰度均值及图像的类间方差分别为
(8)
(9)
ω=pAωA+pBωB
(10)
σ2=pA(ωA-ω)2+pB(ωB-ω)2
(11)
图像类间方差是图像灰度分布均匀性的度量，方差越大说明图像的两个区域之间差别越大.当把区域A的像素点划归到区域B或者将区域B的像素点划归到区域A时都会导致图像类间方差减小，所以类间方差最大就意味着错误划分的概率最小.而类间方差与划分的灰度阈值t有关，可以通过使类间方差最大来求得划分的最佳阈值.
最大类间方差法同样可以用于多阈值的图像分割处理.假设需要将图像分成k+1类，参照上述推导过程，k个阈值的类间方差公式可表示为
(12)
最优阈值可以表示为
(13)
式中：ui和uT分别为各类区域的条件概率灰度均值和图像的灰度均值，表达式为
(14)
(15)
传统的最大类间方差法需要通过穷尽的方式来求解最佳阈值.在图像比较大时其运算量急剧增加，该缺点限制了最大类间方差法的应用范围.自适应遗传算法通过选择、交叉和变异等遗传学操作来生成新的优化样本群体，能够很快地求得满足要求的解.将自适应遗传算法与最大类间方差法相结合，利用自适应遗传算法求解最大类间方差法的最优阈值，然后利用最大类间方差法对激光图像进行分割是一种可行高效的方法.该方法的运行流程如下：
1) 对图像的灰度值进行编码.由于图像的灰度值在0～255之间变化，可以采用二进制编码的方法对图像像素点的灰度值进行编码，每个灰度值用8位二进制表示.定义每个个体的染色体由10位组成，其中前8位为该个体的灰度值，后2位分别为阈值和适应度值.初始时随机产生所有阈值的数值和相关的适应度值.
2) 确定适应度函数及初始化种群.采用最大类间方差法的类间方差函数作为算法的适应度函数.根据需要设定初始种群的大小以及初始种群的个体值，种群规模要与图像的具体大小有关.规模过小会影响搜索空间，容易收敛到局部最优解，规模过大会影响算法的复杂度，降低算法运算效率.
3) 采用自适应遗传算法求解最优阈值，并按照最优阈值对图像进行分割.
为了衡量本文算法的处理效果，分别采用本文算法和传统的最大类间方差图像分割算法对Lena图像进行处理，处理结果如图2所示.其中图2a为原图像，图2b为传统的最大类间方差图像分割算法处理结果，图2c为本文所提算法的处理结果.
图2 处理结果对比图
Fig.2 Comparison in treatment results
为了客观衡量算法的优劣，采用基于区域一致性测度U、形状测度S和区域对比度R的综合测度CI作为评价指标，综合指标的定义为
CI=USR
(16)
该值越大，说明分割的效果越好.分别计算两种算法所得结果的CI值，传统最大类间方差法的CI值为0.273，本文算法的CI值为0.417，这说明本文算法的分割效果优于传统最大类间方差法.
对比处理结果可知：本文算法比传统的最大类间方差法的处理效果更好.本文算法对人物面部特征的分割更加清楚，对头发和帽子等渐变比较严重、细节比较复杂部分的分割也比较准确，错误分割的部分较少，因此具有更好的分割效果.为了衡量算法的执行效率，分别记录两种算法的执行时间和所得的分割阈值，结果如表1所示.
表1 阈值及运算时间数据
Tab.1 Threshold and operation time data
序号最大类间方差算法阈值时间/ms本文算法阈值时间/ms17214.78798.8627214.63818.9137214.33818.8847214.21809.0157114.86829.0767214.62818.98
由表1可知，本文算法的运行时间要小于最大类间方差分割算法的运行时间，这是因为本文算法采用自适应遗传算法计算图像分割的阈值.自适应遗传算法的并行性计算等特征提高了计算效率，此外采用本文算法对图像进行处理时，每次实验的阈值都有所变化，这是由于自适应遗传算法中群体的初始化参数和算法运算过程中选择、交叉和变异等过程的随机性造成的.这种阈值的小范围变化对图像处理的最终结果影响不大，不会使处理结果产生巨大变化，因此是可以接受的.
本文提出了一种基于自适应遗传算法的激光图像处理方法.该方法针对传统最大类间方差图像分割方法中计算分割阈值运算量大、计算效率低等缺点，结合自适应遗传算法的运算并行性，有效利用全局信息等优点，采用自适应遗传算法计算图像分割所需的最优阈值.研究了自适应遗传算法的数学模型，分析了基于自适应遗传算法的激光图像处理方法的处理流程.实验结果表明，该算法较传统的最大类间方差图像分割方法具有更快的处理速度和更准确的分割结果，具有较高的实用价值.
由于该激光图像处理算法对于灰度值渐变的图像边缘分割效果不够好，存在边缘图像信息部分缺失的情况，后续拟采用与神经网络算法相结合的混合式算法解决此问题.同时，将仿真代码移植到数字信号处理芯片，希望能够研制出图像实时处理系统.
[1]许新征，丁世飞，史忠植，等.图像分割的新理论新方法 [J].电子学报，2010，38(2)：76-82.
(XU Xin-zheng，DING Shi-fei，SHI Zhong-zhi，et al.New theories and methods of image segmentation [J].Acta Electronic Sinica，2010，38(2)：76-82.)
[2]Olivier L，Frederic T.A nonlinear derivative scheme applied to edgedetection [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(2)：242-257.
[3]Jobin C M C，Parvathi R M S.Segmentation of medical image using K-means clustering and marker controlled watershed algorithm [J].Euro Journals Publishing，2012，71(2)：190-194.
[4]Li C M，Huang R，Ding Z，et al.A level setmethod for image segmentation in the presence of intensity inhomogeneities withapplication to MRI [J].IEEE Tran-sactions on Image Processing，2011，20(7)：2007-2016.
[5]胡敏，李梅，汪荣贵.改进的OTSU算法在图像分割中的应用 [J].电子测量与仪器学报，2010，24(5)：443-449.
(HU Min，LI Mei，WANG Rong-gui.Application of an improved OTSU algorithm in image segmentation [J].Journal of Electronic Measurement and Instrument，2010，24(5)：443-449.)
[6]吴一全，张金矿.二维直方图θ划分最大平均离差阈值分割算法 [J].自动化学报，2010，36(5)：635-643.
(WU Yi-quan，ZHANG Jin-kuang.Image thresholding based on two-dimensional histogram θ division and maximum between-cluster deviation criterion [J].Acta Automatic Sinica，2010，36(5)：635-643.)
[7]李俊英，江西莉.一种新的大规模复杂图像分割的谱聚类方法 [J].计算机应用研究，2011，28(5)：1994-1997.
(LI Jun-ying，WANG Xi-li.New spectral clustering method for large-scale complex image segmentation [J].Application Research of Computers，2011，28(5)：1994-1997.)
[8]王毅，牛奕龙，田云，等.基于改进遗传算法的最佳熵多阈值三维医学图像分割算法 [J].西北工业大学学报，2007，25(3)：442-445.
(WANG Yi，NIU Yi-long，TIAN Yun，et al.A more stable and accurate genetic algorithm for segmentation of 3D medical images [J].Journal of Northwestern Polytechnical University，2007，25(3)：442-445.)
[9]刘朔，武红敢，温庆可.基于遗传和蚁群组合算法优化的遥感图像分割 [J].武汉大学学报(信息科学版)，2009，34(6)：679-683.
(LIU Shuo，WU Hong-gan，WEN Qing-ke.Segmentation of remote sensing image based on a combination of genetic algorithm and ant colony algorithm [J].Geomatics and Information Science of Wuhan University，2009，34(6)：679-683.)
[10]王秋芬，梁道雷.一种求解0-1背包问题的启发式遗传算法 [J].计算机应用与软件，2013，30(2)：33-37.
(WANG Qiu-fen，LIANG Dao-lei.A heuristic genetic algorithm for solving 0-1 knapsack problem [J].Computer Applications and Software，2013，30(2)：33-37.)
[11]崔宝侠，田佳，段勇，等.基于图论分割的肺部 CT图像的三维重建 [J].沈阳工业大学学报，2015，37(6)：667-672.
(CUI Bao-xia，TIAN Jia，DUAN Yong，et al.Three-dimensional reconstruction of lung CT images based on graph theory segmentation [J].Journal of Shen-yang University of Technology，2015，37(6)：667-672.)