技术领域

本发明涉及图像处理领域，尤其涉及视频序列的运动目标跟踪领 域，具体是一种运动目标跟踪方法。

背景技术

目前，视频监控技术迅速发展，视频运动目标跟踪技术也随之成 为研究的热门课题之一，它融合了模式识别、人工智能、图像处理等 较多领域的先进技术。视频运动目标跟踪通过对摄像机获得的图像序 列进行分析，得到目标的运动参数，并且反馈给跟踪系统，为视频序 列的分析和理解提供依据和基础。运动目标跟踪是跟踪系统的重要环 节，它的精确度直接影响到高层视频序列分析和理解的准确性。

基于统计理论的粒子滤波跟踪算法适用于任何非高斯分布、非线 性的场景，它通过粒子概率来估计并逼近真实目标，在复杂背景以及 短时间部分遮挡的情况下有比较好的跟踪效果。所以，近年来，粒子 滤波跟踪算法得到了很大的发展。但是，研究发现，粒子滤波算法的计 算比较复杂，计算量大，这也一直是制约粒子滤波算法进一步发展和 应用的重要原因，如果用较多的粒子来实现跟踪，会影响跟踪的实时 性，而如果用较少的粒子来跟踪，则会造成较大的目标估计偏差，跟 踪误差大，跟踪效果不理想。针对粒子滤波算法本身的这个缺陷，很 多学者都进行了深入研究，提出了一些改进方法。Canfeng Shan等人 结合mean-shift和粒子滤波跟踪算法，对每个粒子都运用mean-shift 算法找到相应的局部峰值，它能很好的解决粒子滤波跟踪算法计算量 大的问题，但是，粒子的多样性很难保证，特别是有遮挡的情况下， 会出现“过优化”现象，导致跟踪难以恢复。D.Ross等人提出一种基于 本征空间模型的方法进行视觉跟踪，但算法需要采用数量较大的粒子， 影响了其在实时跟踪系统中的应用。

发明内容

为了克服已有粒子滤波目标跟踪方法中当采用粒子数较多时跟踪 实时性差，而采用粒子数较少时跟踪误差大的不足，本发明提供了一种 当粒子数较少时具有良好的准确性和实时性的基于粒子位置调整的粒 子滤波视频运动目标跟踪方法。

本发明解决其技术问题所采用的技术方案是：

一种基于粒子位置调整的粒子滤波视频运动目标跟踪方法，所述 方法包括以下步骤：

第一步，在目标跟踪前，用目标检测算法确定目标的初始位置。 然后，根据目标的中心坐标位置(x，y)和目标的范围，所述目标范围包 括目标宽度block_width和目标高度block_hight，计算得到目标累加直 方图accu_histogram，即累加直方图的初始化；

根据目标的中心位置在x轴、y轴方向上的随机化扩散得到各个粒 子的初始位置，即粒子的初始化。

第二步，读取下一帧图像，以前一帧的目标位置及目标范围为基 础，计算当前帧的目标累加直方图accu_histogram_origin；将目标宽度 block_width左右各减1个像素、各加1个像素，计算两个新的累加直 方图accu_histogram_width_dec、accu_histogram_width_inc，分别计算 accu_histogram_origin、accu_histogram_width_dec和 accu_histogram_width_inc这三个直方图与前一帧的累加直方图 accu_histogram之间的欧式距离D1、D2、D3，距离公式为： 其中，accu_h代表 accu_histogram_origin、accu_histogram_width_dec或 accu_histogram_width_inc，i为累加直方图横坐标的值，若D2＞D3且 D2＞D1，则block_width减2个像素；若D3＞D2且D3＞D1，则bloc_width 加2个像素；否则block_width不变，在目标高度block_hight方向上执 行相同的操作，只是此时的block_width为刚刚更新过的目标宽度，经 过上述操作后，即得到新的目标范围；

第三步，根据新的目标范围，以每个粒子的坐标为中心点，计算 得到临时的累加直方图accu_histogram_temp，然后，计算每个粒子的权 重并进行权重归一化：

①根据第三步得到的新的目标范围，把每个粒子的坐标 (particles_x(p)，particles_y(p))作为中心点计算得到累加直方图 accu_histogram_temp；

②权重计算公式为weight(p)＝η*exp(-λd²)，其中， η＝(1/sqrt((particles_x(p)-x)²+(particles_y(p)-y)²+1))为调节因子， weight(p)为第p个粒子的权重，λ为一个常系数，d为直方图 accu_histogram和第p个粒子对应的累加直方图accu_histogram_temp间 的欧式距离，particles_x(p)为第p个粒子在x轴上的位置， particles_y(p)为第p个粒子在y轴上的位置，(x，y)为目标的中心点坐 标；

得到权重值后，进行权重的归一化，归一化公式为： weight(p)′＝weight(p)/∑weight(j)，其中，weight(p)′为第p个粒子的归一 化权重，∑weight(j)为所有粒子权重之和；

第四步，把上一步得到的粒子权重weight(p)′按从小到大的顺序进 行排序，粒子权重与粒子坐标(particles_x(p)，particles_y(p))要一一对应；

第五步，如果权重小于指定的权重阈值ε，或权重的排序在总排序 的前面μ％，则调整该粒子的坐标，使它们相对于目标中心点(x，y)的 距离缩小，这样，在下一步计算权重时，就能更充分的利用每个粒子， 使它们都能更真实的反应目标的实际位置，距离调整公式为：

particles_X(p)＝x+α(x-(particles_x(p))

particles_Y(p)＝y+α(y-(particles_y(p))

其中，(particles_X(p)，particles_Y(p))为调整后第p个粒子的坐标；α为 调整因子，设为0～1之间的常数，α越大表示距离调整幅度越小；

对于不需要调整距离的粒子，直接把原来的粒子坐标 (particles_x(p)，particles_y(p))赋给(particles_X(p)，particles_Y(p))即可；

第六步，把每个粒子的新坐标(particles_X(p)，particles_Y(p))作为 中心点计算得到临时累加直方图accu_histogram_temp；接着，重新计算 各粒子的权重并进行归一化处理，得到新的归一化粒子权重 weight(p)″；

第七步，根据得到的归一化权重weight(p)″，估计新的目标中心点 的位置，公式为：

x＝∑weight(p)"*particles_X(p)

y＝∑weight(p)"*particles_Y(p)

然后，根据新的中心点坐标以及目标宽度block_width和目标高度 block_hight，计算出新的目标累加直方图accu_histogram_new；

第八步，计算累加直方图accu_histogram和accu_histogram_new之间 的欧式距离，如果距离大于阈值thrd，累加直方图accu_histogram更新 为accu_histogram_new；如果距离小于或等于阈值thrd，则维持原来的 累加直方图accu_histogram。第九步，采用替换选择算法进行重采样， 筛选得到有效的粒子，同时，权重较大的粒子衍生出相对较多的后代 粒子，而权重较小的粒子衍生出较少的后代粒子；

第十步，经过重采样的粒子，在x、y方向上分别扩散得到新的对 应粒子，作为下一帧中粒子的初始分布。

所述第九步中，重采样的过程如下：以0到1/N之间产生的随机 数为起点、1/N为差值组成等差序列，构造两个数列U(j)、C(i)， j＝1，2，...，N，i＝1，2，...，N，N为粒子数目，其中，U(1)为0～1/N之间的 随机数，U(j)＝U(1)+(j-1)/N；C(1)＝w(1)，C(i)＝C(i-1)+w(i)，w(i)为 第i个粒子的权重，如果U(j)＞C(i)j＝1，2，...，N，则i＝i+1，即如果w(i) 太小，则为无效粒子；如果U(j)＞C(i-1)，U(j)＜C(i)，则j＝j+1，第i 个粒子的复制次数为数列U中介于C(i-1)和C(i)之间的项的数目。

本发明的技术构思为：

该方法的一个递推过程包括以下基本步骤：

1)累加直方图和粒子的初始化。根据目标的中心点坐标(x，y)和 目标的范围(目标宽度block_width，目标高度block_hight)计算可以 得到累加直方图accu_histogram。根据目标的中心位置在x轴、y轴方 向上的随机化扩散得到各个粒子的初始位置。

2)读取下一帧图像，更新目标的范围。分别在目标宽度和目标高 度上，对目标范围进行调节，更新目标范围。

3)根据新的目标范围，以每个粒子的坐标(particles_x(p)， particles_y(p))为中心点，计算临时的累加直方图 accu_histogram_temp，如果有p个粒子，则可以得到p个累加直方图。 然后，计算每个粒子的权重并进行权重归一化。

4)对粒子权重进行排序。把上一步得到的粒子权重weight(p)′按从 小到大的顺序进行排序，粒子权重与粒子坐标(particles_x(p)， particles_y(p))要一一对应。

5)调整粒子位置。如果权重小于一个指定的权重阈值ε，或权重 的排序在前面μ％，则根据距离调整公式来调整该粒子的坐标，使它 们相对于目标中心点(x，y)的距离缩小，这样，在下一步计算权重时， 就能更充分的利用每个粒子，使它们都能更真实的反应目标的实际位 置。

6)重新计算粒子权重。把每个粒子的新坐标 (particles_X(p)，particles_Y(p))作为中心点可以计算得到临时累加直方 图accu_histogram_temp。接着，重新计算各粒子的权重并进行归一化处 理，可以得到新的归一化粒子权重weight(p)″。

7)根据上一步得到的权重，估计目标中心点的位置，结合目标的 宽度block_width和高度block_hight，计算得到新的目标累加直方图 accu_histogram_new。

8)计算累加直方图accu_histogram和accu_histogram_new之间的欧 式距离，如果距离大于阈值thrd(thrd根据实际情况来定)，则累加 直方图accu_histogram更新为accu_histogram_new；如果距离小于或等于 阈值，则维持原来的累加直方图accu_histogram。

9)采用替换选择算法对粒子进行重采样，基本原理为以0到1/N 之间产生的随机数为起点、1/N为差值组成等差序列，来处理粒子的 权重，从而确定它们的取舍。

10)粒子传播，经过重采样的粒子，在x、y方向上分别扩散得到 新的对应粒子，作为下一帧中粒子的初始分布。

该方法在计算得到粒子权重之后，对权重进行排序，如果权重小于 指定的权重阈值，或权重的排序在比较前面，则调整该粒子的坐标， 使它们靠近目标中心；得到新的粒子分布后，重新计算粒子权重，得 到最终的目标中心点坐标，实现运动目标跟踪。相对于基本粒子滤波 跟踪方法，该方法可以更充分地利用每个粒子，使它们能更真实的反 映目标的位置，用更少的粒子来实现较好的跟踪效果，提高粒子滤波 跟踪的准确性和实时性。

本发明基于粒子位置调整，在基本粒子滤波算法的基础上进行改 进，对运动目标进行跟踪，具有较高的实时性和可靠性，跟踪效果较 好。

本发明具有以下优点：在粒子滤波跟踪方法中，融入粒子位置调 整算法，可以更充分的利用每个粒子，使它们能更真实的反映目标的 真实位置，可用更少的粒子数来实现较好的跟踪效果，提高粒子滤波 跟踪算法的实时性和准确性，提高跟踪效率。

附图说明

图1为一种基于粒子位置调整的粒子滤波视频运动目标跟踪方法 的流程图。

图2为粒子数为300时，基于粒子位置调整的粒子滤波视频运动 目标跟踪方法和基本粒子滤波跟踪方法对目标中心点的跟踪结果比较 示意图。

图3为粒子数为100时，基于粒子位置调整的粒子滤波视频运动 目标跟踪方法和基本粒子滤波跟踪方法对目标中心点的跟踪结果比较 示意图。

图4为粒子数为50时，基于粒子位置调整的粒子滤波视频运动目 标跟踪方法和基本粒子滤波跟踪方法对目标中心点的跟踪结果比较示 意图。

具体实施方式

下面结合附图对本发明作进一步说明。

参照图1，一种基于粒子位置调整的粒子滤波视频运动目标跟踪 方法，首先根据运动目标检测结果，确定目标中心和目标的范围。然 后进入目标跟踪过程，包括以下步骤：

第一步，在目标跟踪前，用目标检测算法确定目标的初始位置。 然后，根据目标的中心坐标位置(x，y)和目标的范围(目标宽度 block_width，目标高度block_hight)，计算得到目标累加直方图 accu_histogram，即累加直方图的初始化。

根据目标的中心位置在x轴、y轴方向上的随机化扩散得到各个粒 子的初始位置，即粒子的初始化。

第二步，读取下一帧图像，以前一帧的目标位置及目标范围为基 础，计算当前帧的目标累加直方图accu_histogram_origin；将目标宽度 block_width左右各减1个像素、各加1个像素，计算两个新的累加直 方图accu_histogram_width_dec、accu_histogram_width_inc。分别计算 accu_histogram_origin、accu_histogram_width_dec和 accu_histogram_width_inc这三个直方图与前一帧的累加直方图 accu_histogram之间的欧式距离D1、D2、D3，距离公式为： 其中，accu_h代表 accu_histogram_origin、accu_histogram_width_dec或 accu_histogram_width_inc，i为累加直方图横坐标的值。若D2＞D3且 D2＞D1，则block_width减2个像素；若D3＞D2且D3＞D1，则block_width 加2个像素；否则block_width不变。在目标高度block_hight方向上执 行相同的操作，只是此时的block_width为刚刚更新过的目标宽度。经 过上述操作后，即可得到新的目标范围。

第三步，根据新的目标范围，以每个粒子的坐标为中心点，计算 得到临时的累加直方图accu_histogram_temp，然后，计算每个粒子的权 重并进行权重归一化：

①根据第三步得到的新的目标范围，把每个粒子的坐标 (particles_x(p)，particles_y(p))作为中心点计算得到累加直方图 accu_histogram_temp；

②权重计算公式为weight(p)＝η*exp(-λd²)，其中， η＝(1/sqrt((particles_x(p)-x)²+(particles_y(p)-y)²+1))为调节因子， weight(p)为第p个粒子的权重，λ为一个常系数，d为直方图 accu_histogram和第p个粒子对应的累加直方图accu_histogram_temp间 的欧式距离，particles_x(p)为第p个粒子在x轴上的位置， particles_y(p)为第p个粒子在y轴上的位置，(x，y)为目标的中心点坐 标；

得到权重值后，进行权重的归一化，归一化公式为： weight(p)′＝weight(p)/∑weight(j)，其中，weight(p)′为第p个粒子的归一 化权重，∑weight(j)为所有粒子权重之和；

第四步，把上一步得到的粒子权重weight(p)′按从小到大的顺序进 行排序，粒子权重与粒子坐标(particles_x(p)，particles_y(p))要一一对应。

第五步，如果权重小于指定的权重阈值ε，或权重的排序在前面 μ％，则调整该粒子的坐标，使它们相对于目标中心点(x，y)的距离缩 小，这样，在下一步计算权重时，就能更充分的利用每个粒子，使它 们都能更真实的反应目标的实际位置。距离调整公式为：

particles_X(p)＝x+α(x-(particles_x(p))

particles_Y(p)＝y+α(y-(particles_y(p))

其中，(particles_X(p)，particles_Y(p))为调整后第p个粒子的坐标；α为 调整因子，可以设为0～1之间的常数，α越大表示距离调整幅度越小。

对于不需要调整距离的粒子，直接把原来的粒子坐标 (particles_x(p)，particles_y(p))赋给(particles_X(p)，particles_Y(p))即可。

第六步，把每个粒子的新坐标(particles_X(p)，particles_Y(p))作为 中心点计算得到临时累加直方图accu_histogram_temp。接着，重新计算 各粒子的权重并进行归一化处理，可以得到新的归一化粒子权重 weight(p)″。

第七步，根据得到的归一化权重weight(p)″，可以估计新的目标中 心点的位置，公式为：

x＝∑weight(p)"*particles_X(p)

y＝∑weight(p)"*particles_Y(p)

然后，根据新的中心点坐标以及目标宽度block_width和目标高度 block_hight，就可以计算出新的目标累加直方图accu_histogram_new。

第八步，计算累加直方图accu_histogram和accu_histogram_new之间 的欧式距离，如果距离大于阈值thrd，累加直方图accu_histogram更新 为accu_histogram_new；如果距离小于或等于阈值thrd，则维持原来的 累加直方图accu_histogram；

第九步，采用替换选择算法进行重采样，筛选得到有效的粒子， 同时，权重较大的粒子衍生出相对较多的后代粒子，而权重较小的粒 子衍生出较少的后代粒子；

第十步，经过重采样的粒子，在x、y方向上分别扩散得到新的对 应粒子，作为下一帧中粒子的初始分布。

本实施例用基于粒子位置调整的粒子滤波视频运动目标跟踪方法 对视频中的运动目标进行跟踪，并比较本发明和基本粒子滤波方法的 跟踪精度和运行速度。

图1为一种基于粒子位置调整的粒子滤波视频运动目标跟踪方法 的流程图。

步骤110，根据运动目标检测结果，确定目标中心和目标的范围。

步骤120，进行累加直方图和粒子的初始化，可以得到目标的初 始累加直方图accu_histogram和粒子的初始分布。

步骤210，读取下一帧图像，用于后续的操作。

步骤220，在当前帧中，分别在目标宽度和目标高度上，对目标 范围进行调节，更新目标的范围。

步骤310，根据权重计算公式weight(p)＝η*exp(-λd²)，计算每个 粒子的权重，并对其进行归一化处理。

步骤410，把上一步得到的粒子权重按从小到大的顺序进行排序， 粒子权重与粒子坐标(particles_x(p)，particles_y(p))要一一对应。

步骤510，调整粒子位置。如果权重小于指定的权重阈值ε，或权 重的排序在前面μ％，则根据距离调整公式来调整该粒子的坐标，使 它们相对于目标中心点(x，y)的距离缩小。

步骤610，重新计算粒子权重，得到归一化后的新的粒子权重 weight(p)″。

步骤710，根据公式x＝∑weight(p)″*particles_X(p)和 y＝∑weight(p)″*particles_Y(p)，估计目标中心点的位置。

步骤810，计算并更新目标累加直方图。

步骤910，采用替换选择算法对粒子进行重采样，基本原理为以0 到1/N之间产生的随机数为起点、1/N为差值组成等差序列，来处理 粒子的权重，从而确定它们的取舍。

步骤1010，粒子传播，经过重采样的粒子，在x、y方向上分别 扩散得到新的对应粒子，作为下一帧中粒子的初始分布。

本实施例中，设权重系数λ＝0.2，距离阈值为0.98，权重阈值ε为 1/N，μ％取20％，α取0.5，其中，N为实验中目标的粒子数，直方 图中涉及的特征值均为图像的灰度值。本发明采用欧式距离 来衡量两种方法的目标中心点跟踪误差，其中， (x₁，y₁)为运动目标实际中心坐标，(x₂，y₂)为跟踪方法测得的中心坐标。 分别计算比较两种跟踪方法的目标中心点跟踪误差，结果如表1、表2 和表3所示。其中，表1是粒子数为300时，基于粒子位置调整的粒 子滤波视频运动目标跟踪方法和基本粒子滤波目标跟踪方法对目标中 心点的跟踪误差比较表，表2是粒子数为100时，基于粒子位置调整 的粒子滤波视频运动目标跟踪方法和基本粒子滤波目标跟踪方法对目 标中心点的跟踪误差比较表，表3是粒子数为50时，基于粒子位置调 整的粒子滤波视频运动目标跟踪方法和基本粒子滤波目标跟踪方法对 目标中心点的跟踪误差比较表。

表1

表2

表3

同时，本发明采用来衡量两种方法的目标外 接矩形框与实际目标外接矩形框之间的误差，其中，(w₁，h₁)为运动目 标实际外接矩形框的宽和高，(w₂，h₂)为跟踪方法测得的目标外接矩形 框的宽和高。分别计算比较两种跟踪方法的目标外接矩形框跟踪误差， 结果如表4、表5和表6所示，其中，表4是粒子数为300时的目标 外接矩形框跟踪误差，表5是粒子数为100时的目标外接矩形框跟踪 误差，表6是粒子数为50时的目标外接矩形框跟踪误差。

表4

表5

表6

从表1至表6可知，总体上，基于粒子位置调整的粒子滤波跟踪 方法的目标中心点跟踪误差和目标外接矩形框跟踪误差都比基本粒子 滤波跟踪方法小。当粒子数为300时，两种方法的误差相差不多；当 粒子数减少到100个时，基本粒子滤波方法的目标中心点跟踪误差和 目标外接矩形框跟踪误差变大，跟踪出现不稳定状态，而基于粒子位 置调整的粒子滤波跟踪方法的目标中心点跟踪误差和目标外接矩形框 跟踪误差保持在较小范围之内；当粒子数进一步减少到50个时，基本 粒子滤波方法的目标中心点跟踪误差和目标外接矩形框跟踪误差增加 迅速，跟踪非常不稳定，甚至出现跟踪丢失状态，而此时，基于粒子 位置调整的粒子滤波跟踪方法的目标中心点跟踪误差和目标外接矩形 框跟踪误差仍然比较小，跟踪鲁棒性强。

为了进一步直观的比较两种方法的跟踪效果，本发明把表1、表2 和表3中各帧的目标中心点坐标放入图中，形成跟踪中心点位置比较 示意图，如图2、图3和图4所示。图中，运动目标中心点从视频的 右边向左边移动。坐标原点(0，0)为视频图像左上角像素点的坐标值， 视频图像的宽度方向为x轴方向，其中右为x轴正方向；视频图像的 高度方向为y轴方向，其中下为y轴的正方向。每个像素点根据其所处 在视频图像中的位置决定其坐标值。“+”型曲线中的点表示每一帧中 运动目标真实的中心点坐标；“○”型曲线中的点表示对应帧中，用基 于粒子位置调整的粒子滤波视频运动目标跟踪方法跟踪到的运动目标 的中心点；“△”型曲线中的点表示对应帧中，用基本粒子滤波目标 跟踪方法跟踪到的运动目标的中心点。从图中可以看出，粒子数为300 时，基本粒子滤波跟踪方法的跟踪效果与基于粒子位置调整的粒子滤 波视频运动目标跟踪方法差不多；粒子数为100时，基本粒子滤波跟 踪方法跟踪效果变差；当粒子数为50时，基本粒子滤波跟踪方法的跟 踪效果明显比基于粒子位置调整的粒子滤波视频运动目标跟踪方法差 很多，出现了跟踪丢失情况，而基于粒子位置调整的粒子滤波视频运 动目标跟踪方法可进行鲁棒的目标跟踪。

为了验证本发明算法的实时性，我们提取基本粒子滤波跟踪算法 和基于粒子位置调整的粒子滤波跟踪算法的运行时间，并计算出每帧 所需的平均时间，计算结果如表7所示。

表7

从表7中的运行时间可知，相同粒子数目下，基于粒子位置调整 的粒子滤波算法的运行时间比基本粒子滤波算法稍大一些，因为改进 算法中需要对粒子的权重进行排序，并调整粒子的位置，且要进行两 次权重的计算。当使用的粒子数较多(如粒子数300个)时，改进算法 的优越性并没有很好的体现，但是，当粒子数减少到一定量(如粒子数 50个)时，结合表3、表6和图4可以看出，此时，基本粒子滤波算法 不能进行稳定的目标跟踪，而基于粒子位置调整的粒子滤波跟踪算法 仍然能进行稳定的跟踪，具有比较好的跟踪效果。因此，我们将能实 现稳定目标跟踪的粒子数取100个时的基本粒子滤波算法和粒子数取 50个时的基于粒子位置调整的粒子滤波跟踪算法进行比较。从表2、 表3、表5、表6可知，粒子数为100时的基本粒子滤波跟踪方法的目 标中心点跟踪误差和目标外接矩形框跟踪误差均比粒子数为50时的 基于粒子位置调整的粒子滤波跟踪方法大；而从表7可知，粒子数为 100时的基本粒子滤波跟踪方法每帧的平均运行时间是70.2584ms，而 粒子数为50时的基于粒子位置调整的粒子滤波跟踪方法每帧的平均 运行时间是69.9355ms。由此可见，基于粒子位置调整的粒子滤波跟 踪方法可以用较少的粒子数，实现比基本粒子滤波更稳定的跟踪效果， 且运行跟踪算法所需要的时间也更少。因此，本发明算法在提高基本 粒子滤波算法跟踪效果的基础上进一步提高了算法的实时性能。

综上所述，基于粒子位置调整的粒子滤波跟踪方法充分利用每个 粒子来体现真实的运动目标，可以用少量的粒子实现稳定的运动目标 跟踪，兼顾了跟踪实时性和跟踪准确性，是一种有效的目标跟踪方法。

显而易见，在不偏离本发明的真实精神和范围的前提下，在此描 述的本发明可以有许多变化。因此，所有对于本领域技术人员来说显 而易见的改变，都应包括在本权利要求书所涵盖的范围之内。本发明 所要求保护的范围仅由所述的权利要求书进行限定。