视频序列中目标的检测与跟踪

蔡睿妍，田 全

(大连大学信息工程学院，辽宁大连116622)

目标的检测与跟踪涉及到人工智能、机器视觉、生物医学、自动控制等多个学科，近年来，随着计算机技术的发展，得到了广泛的研究与应用［1］。目前比较流行的目标检测算法包括帧间运动估计和背景差分的方法，帧间运动估的方法是利用图像序列中相邻帧图像之间的差来提取图像的运动区域的。该方法实现简单，但只能检测相对运动的目标，并且检测出目标的位置不够精确。背景差分法首先定义视频图像的特定帧为背景，然后将当前帧和背景进行差分比较，如果同位置的像素特征、像素区域特征或其他特征的差别大于选定的阈值，则当前帧中该位置的像素区域就判定为前景目标区域，反之则为背景。该方法容易受到光线亮度变化的影响［2］。基于上述原因，本文提出了一种基于时间序列的编码建模算法，该算法能够解决像素剧烈变化的问题，可以提高复杂背景下目标检测的稳健性。目标的跟踪是通过算法获得目标在特定时间段上的运动轨迹，包括目标的产生、运动和销毁三个过程。由于算法中涉及到帧间目标空间位置的测量，在传统的跟踪算法中，当目标数目增加的时候，算法的时间复杂度呈指数形式增加。本文在分析上述问题基础上，将KD-Tree方法［3］引入目标跟踪算法之中，降低了算法的时间复杂度，同时降低了算法对目标数目的敏感程度，实现了高精度、高效率的目标检测与跟踪。

1 目标检测

很多场景都包含复杂的运动目标，诸如摇曳在风中的树、转动的风扇、摆动的窗帘等。通常这种场景中还有光线的变化。解决这个问题最好的方法是采用基于时间序列的编码建模算法，对每个像素或者一组像素建立时间序列模型，在每个像素点进行抽样，根据颜色扭曲尺度和亮度边界聚类获得编码本的集合，并不是所有像素点拥有相同数量的编码本数量。通过编码本表示的聚类子不需要对应单个高斯分布或者其他参数的分布，因此该编码方式是以像素为基础的。

归一化颜色算子是用来处理全局和局部亮度变化的方法，该技术在图像的暗色区域效果不理想，因为颜色比率的不确定性与亮度相关，所以灰度级低的像素点相对与灰度级高的像素点不确定性更高。这些不确定性使灰度级低的区域变得不稳定，在可能聚集在低灰度级的区域造成无检测［4］。本文通过建立颜色模型来估计颜色的亮度和扭曲，该模型依赖于编码元素主轴界定在亮度值高低边界的背景像素值。对于输入像素点pixi=(B，G，R)和编码本 ci，定义 Vi=(Bi，Gi，Ri) ，可得

由式(1)和式(2)可得

颜色扭曲度为

u2可以由式(5)求解

此外，统计地分配亮度变化的最大和最小值，将其赋给一个编码本，在特定的范围内限制阴影水平和焦点水平，能够有效地适应亮度的变化。为了去除图像中引入的噪声，首先对目标检测完成的图像进行3×3的中值滤波，然后进行形态学处理，使待检测的目标形成一个完整的连通域，并在一定程度上消除中值滤波无法消除的噪声，最终得到比较理想的目标图像。

不同处理阶段目标检测的结果如图1所示。可以看到，在经过上述处理，得到了完整的目标。

图1 目标检测

2 目标跟踪

目标跟踪是建立在目标检测的基础上的，即确定实时视频帧中检测到的目标的运动轨迹，这种轨迹的建立可以通过目标特征的匹配来实现，通常采用的特征信息有目标的位置、尺度、形状以及颜色等。本文采用目标的位置(即每个目标的质心坐标)建立运动模型，实现目标轨迹的精确匹配。

将每帧图像检测出的多个目标同上一帧图像检测出的目标进行比较并分类，主要有3种情况：1)当前目标是由上一帧中某个目标运动得到的(运动速度大于或等于0);2)当前目标在上一帧中没有出现，是新增加的目标;3)某些目标在上一帧中出现过，但在当前帧消失了。

在跟踪用摄像机完整标定的情况下，视场中的目标的运动速度会保持在某个区间之内，即可以通过实验的方法确定某一类别目标的最大运动速度，因为摄像系统的帧率是一定的，所以可以确定目标在两帧之间的时间间隔内的最大位移，定义为D_max，以此作为阈值条件。然后把上一帧的所有目标的质心坐标放在一个数组中，作为一个待遍历的集合Vec。将当前帧的每一个目标的质心坐标在集合Vec中寻找出与之几何距离最近的对应目标A，然后计算该距离d与D_max的关系：1)如果d≤D_max，当前帧的目标是从上一帧的目标A运动得到的;2)如果d＞D_max，当前帧的目标是新增加的目标;3)如果在上一帧的目标中存在没有和当前帧目标相对应的，则说明没有对应的这些目标在当前帧中消失了。

针对上述3种情况，本文采用KD-Tree算法［5］实现目标跟踪。KD-Tree算法是一种由二叉搜索树推广而来的用于多维检索的树的结构形式(K即为空间的维数，此处定义K=2)。与二叉搜索树不同的是，它的每个结点表示k维空间的一个点，并且每一层都根据该层的分辨器对相应对象做出分枝决策。顶层结点按由分辨器决定的一个维度进行划分，第二层则按照该层的分辨器决定的另一个维度进行划分，以此类推在余下各维之间不断地划分。直至一个结点中的点数少于给定的最大点数时，结束划分。

如图2 所示，在二维空间内存在点A，B，C，D，E，首先以A点的y维度为起始点，将点集分为2个部分，然后在左右2个子树中以B点和C点的x维度将左右2个子树分为2个部分，以此类推，在B点、C点各自的子树当中，以D点、E点的y维度对其子树划分，遍历集合当中的每一个点，就可以得到1个完整的KD-Tree。目标轨迹建立的过程就是在KD-Tree中搜索最近点的过程，采用KDTree进行最近点搜索可以提高系统的工作效率。

图2 KD-Tree算法原理图

算法流程如下：

1)定义目标质心点坐标存储结构体，即

其中ID为每个目标对应的序号，x和y分别为每个目标质心坐标的横、纵坐标值。

2)将第i帧的每个目标(定义为Blobi，其中i=1，2，3，…，N)的横纵坐标按照Blob2D32f结构体形式进行存储，ID号从0开始顺次排列，然后存放在起始帧数组ArrayL中。

图3 目标检测与跟踪流程

3)将第i+1帧的每个目标的横纵坐标按照Blob2D32f结构体形式进行存储，ID号不填充，然后存放在当前帧数组ArrayN中。

4)对起始帧数组ArrayL建立KD-Tree。

5)定义D_max。

6)遍历当前帧数组ArrayN中的每个Blobi，搜索其在KD-Tree中最短距离元素，定义最短距离为d。

7)如果d＞D_max，则该Blobi为新当前帧新增加的目标，将其赋予一个新的ID;如果d≤D_max，则该Blobi为由上一帧的目标运动得到的，将其ID更新为ArrayL数组中与其距离最短的目标的ID，并将其对应元素在ArrayL数组中删除。

8)遍历结束后，ArrayL数组中余下的Blobi即为上一帧存在但当前帧消失的目标，将其删除。

9)将当前帧数组ArrayN中的元素更新到ArrayN数组中。

10)循环执行步骤3)～9)过程，直到程序结束。

随着视频帧数据的不断采集，循环进行上述过程，即实现了目标的检测与跟踪。流程图如图3所示。

3 目标跟踪实验

采用三轴云台固定摄像机进行实验，视频图像分辨力为640×480，背景模型建立过程累积了35帧图像，在普通PC上目标检测与跟踪的速度可以达到25 f/s(帧/秒)。

图4分别为第4，6，26，150帧时目标跟踪的情况，可以看到，目标被完整地检测出来，在目标物像素尺寸相对整个视频帧图像的比例较大的时候，没有出现单一目标被误检测成多个目标的现象，且目标的运动能够被较好地跟踪。

图4 目标跟踪结果

4 结论

本文讨论了几种目标检测中背景建模的方法，并重点说明了背景差分的建模方法，对差分后的图像进行滤波和形态学处理之后，可以得到较完整的目标轮廓，并且通过KD-Tree算法对目标进行跟踪，大幅度提高了跟踪效率。

［1］蔡荣太，吴元昊，王明佳，等.视频目标跟踪算法综述［J］.电视技术，2010，34(12)：125-127.

［2］潘翔鹤，赵曙光，柳宗浦，等.一种基于梯度图像帧间差分和背景差分的运动目标检测新方法［J］.光电子技术，2009，29(1)：34-36.

［3］SPROULL R F.Refinements to nearest-neighbor searching in K-dimensional trees［J］.Algorithmica，1991，6(4)：579-589.

［4］KIM K，CHALIDABHONGSE T H，HARWOOD D，et al.Real-time foreground-background segmentation using codebook model［J］.Real-Time Image，2005，11(3)：172-185.

［5］刘宇，熊有伦.基于有界k-d树的最近点搜索算法［J］.华中科技大学学报：自然科学版，2008，36(7)：73-76.