自适应遗传视频运动对象分割算法*

王燕妮 ， 樊养余

（1.西安建筑科技大学 信息与控制工程学院，陕西 西安 710055；2.西北工业大学 电子信息学院，陕西 西安 710072）

1 引言

在视频序列分析中，由于运动目标在视频序列中所占的信息量最大，经常成为被分割提取的视频对象[1]，因此在分割提取动态的视频对象时，重要的是区分出运动目标和背景的范围。遗传算法是模拟生物进化过程而建立的一种最优化方法，在此提出一种新的自适应遗传视频运动对象分割算法，确定自适应遗传机制、自适应初代个体、选择算子和结束判断等。由于遗传机制合理，并且自适应调整交叉率和变异率，该算法在取得良好分割效果的同时降低了算法的复杂度，较好地提高了算法的收敛速度。

2 遗传算法

一般的遗传算法（Genetic Algorithm，GA）[2]分为 4 部分：编码机制（encoding mechanism）、控制参数、适应度函数（fitness function）、遗传算子（genetic operator）。 编码机制是GA的基础，GA不是对研究对象直接进行讨论，而是通过某种编码机制将对象统一赋予按一定顺序排列成串的特定符号（字母）。在GA中适应度函数描述每个个体的适宜程度。遗传算子中最重要的有3种：选择（selection）、交换 （crossover）和变异 （mutation）。通过选择使适应度大即优良的个体有较大的存在机会，而适应度小即低劣的个体继续存在的机会也较小。交换算子有多种形式，最简单的是单点交换（single point crossover），即从群体中随机取出2个字符串，随机确定交叉点，2个字符串互换再重新连接得到2个新字符串。得到的新字符串不一定都能保留在下一代，需和原来的字符串进行比较，保留适应度大的，交换后可进行突变。遗传算子用来改变字符串的某个位置上的字符。

3 自适应遗传视频运动对象分割算法

自适应算法的基本步骤如下：1）自适应初代个体；2）自适应选择算子；3）交换变异算子；4）自适应终止准则；5）重复步骤1）～4），直到进化结束满足条件为止。

3.1 适应度评估

在遗传算法中，适应度是衡量个体优劣的标志，优胜劣汰是以个体适应度的大小为依据的。适应度函数决定了个体遗传到下一代机会的大小，设计一个好的适应度函数可提高遗传算法的分割效率[3－4]。由于在视频分割中通常采用均方误差（Mean Square Error，MSE）和绝对误差总和（Sum of Absolute Difference，SAD）作为目标函数[5]，遗传自适应分割算法则采用与绝对误差总和相关的函数作为适应度函数，保证误差越小的染色体适应度值相应越高。

算法中的适应度函数F定义为

式中：si为当前群体中第i个染色体的绝对误差总和，F（si）为其适应度值，N是当前群体包含的个体数目，median（）为中值函数。适应度函数值较大的存在机会大，为优秀个体，继续存在的机会也较大。这样就可以节省适应度评估的时间，提高算法的运行速度。

3.2 自适应初代个体选择

由于初代个体的优劣影响到整个进化过程的收敛速度。现有的遗传分割算法通常采用随机或中心偏离的方法来选择初代个体，在此采用二者相结合的方法。

首先在视频图像区域内随机选取一些位置的对应块作为初代子个体，然后选取其区域中心及附近位置的对应块作为初代个体群，其中包括区域中心子个体及周围上、下、左和右方4个位置对应的5个块作为初代个体群。中心偏离方法利用视频图像的时间相关性，当图像运动较为缓慢时，优秀个体大多分布在中心区域，因而可保证初代个体的质量。当图像剧烈运动时，在初代个体群的选择中进一步利用视频图像的时空相关性[6－7]，以保证初代个体的质量。计算当前选择块周围上、下、左和右方4个块的SAD值，分别与当前块的SAD值求绝对差。根据经验值，若差值小于阈值450，则选出作为初始个体；否则遗弃，作为下次选择的对象。

3.3 自适应选择算子

选择算子是将当前群体中适应度较高的个体按照某种规则遗传到下一代群体中的操作，在选择中，优势个体以较大的概率被复制到下一代，而劣势个体则要面对一定的压力。选择的目标就在于使种群中个体的适应度值增大。但由于在遗传算法执行的不同阶段，个体间差异也不同，若用相同的选择策略可能会导致如下问题：当个体差异较大时，选择概率大的个体可能在淘汰掉劣势个体的同时，也遗失了存在于劣势个体中的部分优良基因；当个体差异很小时，可能会由于选择概率不够而使搜索趋于随机化，导致收敛速度慢。因此，采用一种随着算法的执行和个体的变化而不断变化的自适应选择方案。

采用与适应度成一定正比比例的概率。首先计算出群体中所有个体适应度的总和，其次计算出每个个体的相对适应度大小，即每个个体在所有个体适应度总和中所占的比例。根据适应度以某种概率选择个体，适应度越高，它被重复选择的可能性越大，而适应度小的个体往往未能选中，从而实现优胜劣汰。若相对适应度大于80%，则将此个体遗传到下一代群体中；若相对适应度为70%～80%，则将它留下来，继续组合新的群体并跟踪；若相对适应度小于70%，则认为此个体适应度较小，选择概率小，甚至丢弃。

3.4 交换算子和变异算子

在遗传算法中，交叉是产生新个体的主要手段。交叉算子的好坏直接影响算法的收敛性能。以某个概率p随机互换两个个体之间的基因片段，产生新的基因型。运算过程为：首先对群体中的个体进行两两随机配对，然后对每一对相互配对的个体，随机设置一个基因位置为交叉点，交叉概率为0.6～0.8。若染色体的长度为L，则共有L－1个可能的交叉点位置。最后对每一对相互配对的个体，依设定的交叉概率p在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。

变异操作采用自适应变异算子来随机改变个体某一位的值，按照一定的概率从中选取若干个体，按一定的策略进行变异操作，即改变码值某一位的值。变异运算增加了群体的多样性，避免算法过早陷入局部最优解。进行取反运算，1变0或0变1，或者采用同或或异或算子，这是一种二元变异操作，需要两个染色体个体参与。

当两个染色体进行同或操作时，若两个染色体同一基因位上的等位基因相同，则变异后的染色体该基因位取1，否则取0。对于异或算子则正好与同或相反，若两个染色体同一基因位上的等位基因相同，则变异后的染色体该基因位取0，否则取1。同或或异或算子使同一基因位上的基因经过变异后，至少有一个0和一个1同时存在，可以有效地保持同一基因位上等位基因的多样性，从而最大限度地避免遗传算法早熟现象的发生。

自适应变异操作对于适应度值高于70%的个体，变异算子设置较小值为0.3%，这样可以使其较小变异，从而进入下一代。而对于适应度值低于70%的个体，变异算子设置较大值为3%，使该个体被淘汰掉。在保持群体多样性的同时，保证了算法的收敛性。

3.5 自适应终止准则

为了避免算法发生“过早收敛”和搜索过程中的“停滞现象”，当算法执行到最大迭代次数G，群体的最高适应度值仍未发生变化时，具有最高适应度值的个体灰度值为最佳阈值，算法结束。否则重复以上过程，并用找到的最佳阈值分割视频图像。

3.6 其他参数

设染色体长度L为8，种群数P为12，繁衍代数G为20，交叉概率和变异概率根据个体的适应度自适应调节。算法流程图如图1所示。

4 仿真分析

为验证算法的有效性，在配置为P4 CPU 3.0 GHz，512 Mbyte内存以上的计算机上分别采用最大类间方差法（Otsu）和AGS对视频图像进行分割实验。

实验1：视频序列forman分割图像结果的比较。

AGS算法中设置参数为：染色体长度L为8，种群数P为12，繁衍代数G为20，交叉概率和变异概率分别采用自适应调节。对于视频序列forman（352×288）的第5帧，分别使用灰度阈值（threshold）分割法、Otsu算法和AGS算法，分割实验结果如图2所示。

实验2：视频序列football分割图像结果的比较。

AGS算法中设置参数为：染色体长度L为8，种群数P为12，繁衍代数G分别为5，10和20，交叉概率和变异概率自适应调节，采用视频序列football（352×240）的第1帧，分割实验结果如图3所示。

实验3：分割时间的比较。

采用视频序列missamerica的第1帧，分别用OTSU和改进的AGS方法对运行时间进行比较。其中AGS算法的参数为：染色体长度L为8，种群数P为12，交叉概率和变异概率采用自适应调节，分割时间如表1所示。

表1 序列missamerica分割时间

在实验1中，对视频序列forman进行分割比较，结果表明：当AGS算法参数选择合适的情况下，灰度阈值法和OTSU算法的分割结果均不如AGS算法分割效果好。在实验2中，对视频序列football进行分割，改变AGS算法的繁衍代数，分别取5，10和20。通过比较可以看出，繁衍代数越多，分割效果越好。在实验3中，分别用OTSU算法和AGS算法分割视频序列missamerica的第1帧，AGS算法进化12代左右就能得到最佳阈值，分割时间也减少了约0.05 s。

5 小结

视频对象分割是视频压缩编码中的重要环节，其优劣直接决定整个编码性能，研究视频分割具有重要意义。提出一种自适应遗传视频运动对象分割算法，引入自适应进化机制，包括初代个体的选择，进化算子及进化结束判决，利用视频图像的内在相关性来加速进化过程，能够与不确定性的进化过程较好地匹配。仿真结果表明提出的算法可以实现较为精确的视频图像分割，同时保持较低的运算复杂度。

[1] LIU Lijie，FAN Guoliang.Combined key-frame extraction and objectbased video segmentation[J].IEEE Trans.Circuit and System for Video Technology，2005，15（7）：869-884.

[2] HUA Gang，ZHENG Nanning，XUE Jianru.An approach based on improved genetic algorithm to selecting the threshold automatically in edge detection and its application in computer vision system[J].Mini-micro System，2002，23（3）：318-321.

[3] MO Xiaoran，WILSON R.Video modelling and segmentation using Gaussian mixture models[C]//Proc.IEEE International Conference on Pattern Recognition.Cambridge，UK：Institute of ElectricalandElectronics Engineers Inc，2004：854-857.

[4]BLEKAS K，LIKAS A，GALATSANOS N P，et al.A spatially constrained mixture model for image segmentation[J].IEEE Trans.Neural Networks，2005，16（2）：494-498.

[5] 高韬，于明.背景渐变的视频对象分割算法研究及实现[J].电视技术，2006，30（7）：84-86.

[6] HAYIT G，JACOB G，ARNALDO M.A probabilistic framework for spatio-temporal video representation and indexing[C]//Proc.the 7th European Conference on Computer Vision.New York： Springer，2002：461-475.

[7] HAYIT G， JACOB G，ARNALDO M.Probabilistic spacetime video modeling via piecewise GMM[J].IEEE Trans.Pattern Analysis and Machine Intelligence，2004，26（3）：384-396.

樊养余（1960-），教授，博士生导师，主要从事强噪声中信号检测与恢复、数据压缩、信息安全、目标识别等方面的研究。