一种基于遗传算法和卡尔曼滤波的运动目标跟踪方法

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于遗传算法和卡尔曼滤波的运动目标跟踪方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：提出了一种基于遗传算法和卡尔曼滤波的运动目标跟踪方法。该方法利用卡尔曼滤波预测目标中心在下一帧图像中可能出现的位置，以该位置为中心，建立候选的目标搜索区域。以跟踪目标的灰度统计特征为模板，以Bhattacharyya系数来度量目标模板与候选目标区域的相似性，并以此相似性作为遗传算法适应度函数，以候选目标中心坐标作为参数编码，利用遗传算法进行匹配搜索，最终获得最佳候选区域中心位置，同时以该位置作为观测值，进行下一帧预测。实验结果表明，该方法具有较好的实时性和鲁棒性。

关键词：遗传算法；卡尔曼滤波；目标跟踪

中图分类号：TP391.41文献标识码：A

文章编号：1001-9081(2007)04-0916-03

0引言

运动目标跟踪是计算机视觉领域一个富有挑战性的课题，在视觉监控、视频编码、军事、交通等领域有着重要而广泛应用[1,2]。跟踪的实质是在下一帧图像中寻找目标所在的位置，一般利用全局搜索的方法总能找到。由于跟踪过程中要求能够实时地跟踪视场范围内运动目标，而被跟踪的目标往往运动速度快，受周围环境干扰强，因此如何获得具有满意效果的跟踪方法，具有较好的实时性和鲁棒性是比较困难的。

目标跟踪时，目标本身以及目标所处的环境差别很大，例如目标的大小，目标是否是刚体或非刚体，目标大小是否变化，运动是平缓还是剧烈，背景是否复杂，摄像机是否运动，是多目标还是单目标跟踪等。根据不同情况，有多种不同的图像跟踪算法被提出，主要分为基于模型的方法，基于区域的方法，基于特征的方法和基于变形模板的方法等四类[3]。这些方法都各有自己的优点和缺点，在一定条件下可以获得较好的跟踪效果。

遗传算法是一种应用广泛的寻优方法，具有很强的鲁棒性以及全局优化特性，在图像的分割、识别等方面已获得了初步的应用[4―6]。卡尔曼滤波通常被用来对被跟踪目标运动状态进行预测，可以减少搜索区域的大小，提高跟踪的实时性[7,8]。本文利用了这两种技术的优越性能，根据跟踪目标的灰度特征，利用卡尔曼滤波预测确定目标匹配的候选区域，然后采用遗传算法对候选区域进行搜索匹配，提高跟踪的实时性和鲁棒性。搜索时利用目标的灰度特征进行匹配，并且在候选区域具有全局最优的特点，提高了跟踪的准确性，对目标部分遮挡也能很好地处理。

1卡尔曼滤波

卡尔曼滤波由消息过程，测量过程和滤波过程组成，是一套线性无偏最小均方误差的递推公式，可以证明，一定条件下，在最小均方误差准则下得到的最佳线性系统是所有系统的最佳者[7]。卡尔曼滤波器算法包含的两个模型：

2基于遗传算法和卡尔曼滤波的目标跟踪

2.1遗传算法

遗传算法是一类基于自然选择和遗传学原理的有效搜索方法，它从一个初始种群开始，利用选择、交叉和变异等遗传算子对种群进行不断进化，最后得到全局最优解[4]。在遗传算法中将问题的求解表示成类似生物遗传物质“染色体”，通常是二进制字符串表示，其本身不一定是解。遗传算法的基本步骤是首先随机产生一个初始种群，然后使用一个适应度函数对该种群中个体进行评价，根据评价的结果进行选择产生新种群，对新种群进行交叉和变异操作。交叉和变异操作的目的是挖掘种群中个体的多样性，避免有可能陷入局部解。经过上述运算产生的染色体称为后代。最后，对新的种群（即后代）重复进行选择、交叉和变异操作，经过给定次数的迭代处理以后，把最好的个体作为优化问题的最优解。

遗传算法应用过程中通常包含五个基本要素：1）参数编码。遗传算法是采用问题参数的编码集进行工作的，而不是采用问题参数本身，通常采用二进制编码。2）初始种群设定。遗传算法随机产生一个由N个个体（染色体）组成的初始种群，也可根据一定的限制条件来产生。种群规模是指种群中所含染色体的数目。3）适应度函数的设定。适值度函数是用来区分种群中个体好坏的标准，是进行选择的唯一依据。可以通过目标函数映射成适值度函数。4）遗传操作设计。遗传算子是模拟生物基因遗传的操作，遗传操作的任务是对种群的个体按照它们对环境适应的程度施加一定的算子，从而实现优胜劣汰的进化过程。遗传基本算子包括：选择算子，交叉算子，变异算子和其他高级遗传算子。5）控制参数设定。在遗传算法的应用中，要首先给定一组控制参数：种群规模，杂交率，变异率和进化代数等。

2.2目标特征和遗传适应度函数

图像灰度特征对目标的形变、旋转等不敏感，具有良好的稳定性。在目标图像和候选图像匹配过程中，我们采用图像的灰度特征进行匹配。

2.3候选目标中心的坐标编码

利用Kalman滤波可以预测跟踪目标在下一帧图像中位置，其中心点设为（x0,y0)，以该点为中心，取宽度为w，高度为h的区域为搜索区域（如图1），也就是要在该区域中找到和目标模板最相似的候选目标区域中心点。

为了使遗传算法顺利进行，对搜索区域的位置坐标进行二进制编码，根据搜索区域大小，X轴方向宽取lw位，Y轴方向高取lh，则总编码长度为l=lw+lh，具体形式为：

2.4遗传操作

遗传算法开始时，初始种群选择可以采用确定性选择或随机性选择两种方法，确定性选择就是在搜索窗口中根据某些先验知识指定N个点，如中心点(x0,y0)，以及图像中均匀分布的几个点作为初始种群。

遗传过程首先进行选择操作，根据由(7)式确定的适应度函数计算种群中各个个体的适应度，也就是目标模板特征和以该个体所对应的点为中心的候选区域特征相似度大小，确定其被选中的概率，相似度越大，其被选中的概率也就越大。然后对被选择保留下来的个体点进行两两配对，进行交叉操作，即对配对的个体部分基因进行交换，最后根据某个概率，对个体某个随机的基因位进行变异，就是0变1，1变0。交叉和变异操作的目的是增加种群中个体的多样性，避免有可能陷入局部解。经过这样一系列的遗传操作，得到了新一代种群，然后可以进行下一次的遗传搜索过程。

在遗传算法中，设定搜索迭代的总次数，决定迭代结束时间。也可以设定一个阈值T，当某代的最优个体其适应度函数值达到该阈值时，就可以认为已找到最优候选中心点，停止搜索。把遗传算法获得最佳候选区域中心点作为最终卡尔曼滤波的观测值，进行下一帧目标的跟踪。

3实验结果与分析

本文利用处理器为AMD3000，内存为512M，在VC++6.0环境下，采用CAVIAR数据集[10]中ThreePastShop1cor一段视频图像为实验对象，视频的分辨率为384×288，跟踪目标为视频中出现的一个行人，跟踪从175帧开始到275帧结束，在175帧中由人手工选定模板，大小为32×120像素，用矩形框来定位表示。实验中目标搜索区域的宽w设为32个像素大小，高h设为32个像素大小。遗传算法的二进制编码长度为10位，前5位表示目标中心的水平x坐标，后5位表示纵向y坐标。遗传算法的种群大小设定为8，其中初始种群中一个点为卡尔曼滤波预测的目标区域中心位置点，其他7个个体随机产生。遗传迭代总代数为30，交叉概率为0.6，变异概率为0.01。设定在一代群体中，如果适应度最高的个体其适应度函数值达到设定的阈值T=0.85就停止迭代，表示已搜索到目标。当遗传算法迭代次数达到最大迭代次数时，如果所有个体表示相似程度的适应度函数比较低，低于阈值0.75但大于0.65，结合卡尔曼滤波预测的结果和遗传算法获得的最优值进行平均。当最优个体适应度函数的值低于0.65，实际上可以推测目标被严重遮挡，直接可以把卡尔曼滤波预测的结果作为实际值处理。图3是部分帧跟踪的结果。

图4是每帧中遗传算法迭代次数。从图4可以看出，从215帧开始，当目标被遮挡时，迭代次数明显增大，甚至到达迭代的最大次数。

与穷举搜索方法相比，尽管遗传算法得到的可能是次优解，但遗传算法的匹配次数大大降低。在遗传算法中，目标模板与搜索区域进行匹配比较次数为迭代次数乘以种群数，本实验在最坏的情况下，即在目标被完全遮挡的情况下，比较次数为240次。而如果采用穷举法，必须比较32×32＝1024次。在目标不被频繁遮挡的一般情况下，穷举法平均仍需要比较512次，而本文方法只要比较大约20次。实验中，平均每秒可以处理15帧的图像，可以满足跟踪实时性的要求。

当目标完全遮挡或速度很快时，Mean―shift[9]方法很容易丢失跟踪目标，而本文方法由于结合了卡尔曼滤波预测的方法，设置了范围较大的搜索区域，即使目标被短暂的完全遮挡，也能保证跟踪能继续下去。

实验中还发现，除了遗传算法中的参数会影响算法的性能外，还有两个因素会影响本方法的跟踪结果：一个是搜索区域的大小，显然合适的搜索区域大小是很关键的因素，一般当运动目标运动速度较快，方向变换较频繁时，搜索区域设置要大；另外一个因素是目标模板中背景像素的影响，因为采用矩形模板，背景可能会被包含到目标模板中，影响匹配的准确度，因此在设定初始跟踪模板时，应尽量排除背景的干扰。

4结语

由于遗传算法是一种新的全局优化搜索算法，采用非遍历寻优策略，结合卡尔曼滤波对目标可能出现的区域进行预测，运算速度快；从算法的过程可以看出，能够解决运动目标突然变向而造成的跟踪目标丢失；并且由于匹配特征采用的是灰度特征，对目标的形变和旋转等不敏感，当出现目标部分被遮挡甚至全部遮挡时也能够继续跟踪下去。因此本文提出的方法能够满足运动目标跟踪的实时性和鲁棒性的要求。

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。