飞鸟视频跟踪的局部特征点融合Meanshift方法

文/周玉成 陈业明 程新蕾 张梦雨 汪沛

1 引言

运动目标跟踪是基于特定算法的一种用于检测视频序列中移动目标的技术。目前，常用的目标跟踪算法可分为两类，分别是基于生成式模型和基于判别式模型的目标跟踪算法[1]。生成式模型跟踪算法通常将模型建立在当前帧目标区域，在下一帧中检测具有最高近似程度的区域。基于判别模型的检测方法应用目标范围作为正样本，将背景区域作为当前帧中的负样本。使用特征提取和特征选择训练分类器，并将其应用到下一帧中以找到最优区域。

鸟类的种类和数量繁多,几乎分布于各种生态环境，其在维持自然界的生态平衡方面有着特殊的贡献。作为动态目标跟踪的一个研究分支，对视频序列中鸟类的跟踪常被用来探索鸟类的飞行规律、并在此基础上进一步延伸出各类研究。分析视频序列中的鸟类行为，首先需要在复杂的野外监控视频中清晰地监测以及跟踪要研究的目标鸟类[2]。检测及跟踪的高效性与准确性对于进一步地鸟类行为分析具有重要的意义。近年来，学者们对于相关领域进行了大量的研究[3-7]。2011年，C.Qing等人[8]通过结合方向梯度直方图特征与二值模式特征检测跟踪鸟类，但该方法使用了静态背景，在实际应用中准确率并不高。2014年，Q.Xu和X.Shi[9]提出了一种基于飞鸟骨架结构种内相似性和种间差异性的飞鸟检测跟踪方法，以简化的骨架特征为分类标准，通过支持向量机分类。但该方法仅适用于检测侧视图中的飞鸟，对其他视角下的检测效果并不好。2015年，R.Yoshihashi[10]也使用了方向梯度直方图特征，在一个新的鸟类数据集上与基于卷积神经网络[11]进行比较，验证了方法的有效性。

图1：Surf-Meanshift跟踪算法流程图

图2：匹配点筛选前后效果对比图

图3：当前帧Roi区域内的特征点匹配结果

为寻找适用于野外观测视频中鸟类运动目标的跟踪算法，我们对目前常用的目标跟踪方法如Kalman、Condensation、Camshift和Meanshift等方法进行了调研：Kalman滤波器过于依赖过去时间点的数据，在遮挡物长时间存在的情况下无法保证跟踪效果[12]；Condensation粒子滤波器对目标物体有较好的跟踪性，但由于计算量大和采用颜色空间直方图进行目标特征表示[13]，制约了算法的鲁棒性；Camshift在均值漂移算法的基础上改进，具有自适应目标大小的功能，但在光照变化明显或目标与背景色相似时，跟踪效果并不理想。[14-15]，不适于野外观测中对鸟类的跟踪。作为无参概率密度估计方法，Meanshift（均值漂移）算法属于计算密集型算法，使用核函数直方图模型，计算量较小。但对于边缘遮挡、目标转动、形变和环境运动不敏感，且由于其迭代搜索的工作原理，当目标运动速度较快时跟踪效果欠佳，为了进一步减少均值漂移算法的搜索时间，降低计算复杂度，需要引入合适的位置变化预测机制。

综合各种算法的优缺点分析，并考虑到鸟类运动的特征以及野外观测视频拍摄条件，本文提出一种融合局部特征点匹配和Meanshift方法的鸟类目标跟踪算法。该方法对视频序列执行Surf特征点提取，通过Lowe’s算法筛选出有效特征点，结合预测公式得到目标在下一帧中的最有可能出现的理想位置，在此基础上进行Meanshift向量的迭代，通过具体实验，并通过实验验证了该方法的有效性和可行性。

2 Meanshift方法简介

Meanshift算法[16-17]描述了基于核函数和加权颜色直方图的目标特征，通过巴塔恰里雅距离测量目标模型与候选模型之间的相似性，转化相似度量的局部极值问题为核密度估计问题，多次算法的迭代后确定局部最大值。其主要步骤为：目标锁定、目标模型和候选模型描述、相似性度量、迭代。

2.1 目标模型的建立

2.2 候选模型的建立

依据前一帧的跟踪物体中心位置f0，得到备选目标中心位置f，计算目前帧的备选目标区域直方图。同构建目标模型，候选模型的概率密度表达式如下：

其中h为核函数窗口大小，决定权重分布，其他参数同目标模型。

2.3 相似性度量

Bhattacharyya系数是表示目标模型与候选模型之间的相似度的函数。

函数的值越大，两个模型之间的相似性就越高，将前一帧的中心作为搜索窗口的中心，找到最大化相似函数值的候选区域，即当前帧中目标的位置。为了最大化函数值，对上式进行泰勒展开得到：

2.4 Meanshift迭代方程

上式中只有第二项随候选模型的中心变化，通过候选区域中心向真实区域中心的Meanshift迭代方程为：

通过Meanshift迭代来实现相似性函数的极大化，以初始帧位置迭代计算下一帧位置，直至收敛或达到收敛停止条件。

3 算法改进

3.1 算法设计

基于前文的分析，均值漂移算法代码重构性高。其跟踪过程中可以保证实时性，然而由于缺乏对下一帧目标位置的预测，在鸟类飞行速度过快以及有障碍物遮挡时难以取得预期效果。针对目标位置的预测，基于灰度处理，Surf特征点提取和匹配技术，文章提出了一种基于鸟类局部特征点的Meanshift运动目标跟踪算法。算法流程如图1所示：

表1：测试视频参数

表2：迭代次数对比表

图4：预测目标位置方法原理示意图

图5：Meanshift方法迭代过程图示

图6：Surf-Meanshift算法迭代过程图示

步骤1 读取当前帧图像和下一帧图像；

步骤2 对图像进行灰度化处理；

步骤3 利用Surf算法对当前帧和下一帧图像进行特征点提取；

步骤4 使用Flann算法针对当前帧图像Roi区域范围内的特征点进行匹配；

步骤5 使用Lowe’s算法过滤出优秀的匹配点；

步骤6 利用局部特征点匹配的结果预测目标在下一帧中的位置；

步骤7 以预测值为迭代初始值，迭代Meanshift向量以确定跟踪目标在下一帧中的位置；

步骤8 重复上述过程，直到视频结束。

3.2 局部特征匹配

Meanshift跟踪算法在目标移动速度快、噪声干扰严重的情况下，相似函数极大值的计算结果会受到影响。因此，很容易导致丢失跟踪目标。通过对图像特征点进行提取可以得到有效的图像纹理信息，对两个连续帧图像中的特征点进行匹配，可以基于当前帧的目标位置来预测下一帧的目标位置。利用该预测值作为均值漂移算法的初始迭代值，可以缩小搜索范围，从而在一定程度上克服原始算法的局限性。

3.2.1 特征点检测

常见的特征点提取算子有：Harris算子、Susan算子、Sift算子和Surf算子。其中常用的Surf特征点检测方法在Sift算子的基础上加以改进，提高了算法速度，更加适应实时的特征检查任务。该算子稳定性较高，不受尺度、旋转等因素影响，本文选取Surf算法对视频图像序列进行特征点提取。

Surf算法[18]的核心思想是使用Hessian矩阵检测局部极值点，进而锁定特征点坐标。首先定义Hessian矩阵：

其中f(x,y)为二阶可微函数，H函数表示Hessian。

Hessian矩阵的判别式如下：

为使图像具有尺度不变性，算法通过构建尺度空间进行SURF特征点的提取。通过Hessian矩阵求出极值后，比对在3x3x3的立体邻域内的非极大值，若极值点为最大值或最小值，则认为该点为候选特征点，然后在尺度和图像空间中进行插值运算，获得稳定的特征点位置和像素点尺度数值。

3.2.2 特征点匹配

可见光连续视频序列的特征点生成后，匹配策略的选择直接决定了图像匹配的准确率。本文选择使用Flann匹配器[19]，以欧氏距离作为度量标准建立前后两帧图片的对应关系，匹配过程分为粗匹配S和筛选优秀匹配点两个过程。

3.2.3 粗匹配

特征匹配中涉及到两个特征集合，分别为训练集和查询集，匹配结束后会得到两个特征集合的对应关系表。本文使用快速近似最近邻搜索算法Flann[19]来寻找匹配点，最终查询集中的每个特征点在训练集中找到一个最优匹配点。

3.3 筛选优秀匹配点

Sift算法的作者Lowe提出了一种筛选匹配点的Sift匹配方式，目的是为了消去由于障碍遮挡和环境混乱而产生的误匹配点。Lowe’s算法[20]的基本思想是选择图像中的一个关键点，在下一帧图像中找出与其欧几里得距离最近的前两个特征点，得到两个距离d1，d2，其中d1小于d2。距离之比可用以下公式进行计算。

由于特征空间的高维性，当两个候选点与当前特征点的距离非常接近，即ratio值较高时，可能同时存在着大量的误匹配点，此时该匹配点的可信度较低。若将ratio值限制在小于某个阈值，则会得到优秀的匹配点，达到对匹配点进行筛选的效果。为在保证匹配点的数量的同时尽可能消除错误匹配点，本文通过初步实验，设定阈值为0.6。

图2所示是全图特征点检测及匹配的效果示意图，可以看出使用Lowe’s算法对匹配点进行筛选后，有效剔除了其中的误匹配点。

将特征点检测与匹配的范围限定在当前帧的Roi区域内，使用上述匹配及筛选算法，得到如图3所示的匹配结果。

3.4 预测目标位置

根据连续两帧图像局部特征点的匹配情况，在已知当前帧Roi区域的情况下，还需要后续处理来预测下一帧中目标的位置。预测目标位置方法原理示意图如图4所示。

3.5 预置Meanshift迭代初始值

Meanshift算法通过手动绘制视频序列中的感兴趣区域，将区域中心作为第一次迭代的中心，并在此基础上逐步迭代，直至找出相似函数最大的候选区域，即为本帧中目标的位置。鸟类目标跟踪任务中，由于运动目标速度较快，常使得连续两帧之间的目标位置差异变大，导致了定位目标时迭代次数的增多。这种情况直接影响了跟踪的速度和准确度，最终引发了目标丢失的情况。

图7：目标与背景差别较大的跟踪结果

图8：树枝干扰情况下的跟踪

图9：背景干扰情况下的跟踪结果

图10：曝光情况下的跟踪结果

为了解决这一问题，本文提出了一种融合局部特征点匹配和Meanshift方法的自动跟踪算法。利用局部特征点匹配的结果预测目标在下一帧中的位置，将此位置作为下一帧目标跟踪时Meanshift向量迭代的初始值。这种方法在Meanshift迭代之前预先将中心点置为目标最有可能分布的位置，可以有效减小搜索范围。在野外检测视频中实时跟踪鸟类目标时，缩小检测范围意味着能够使用更少的迭代次数找到目标位置，或者在迭代次数阈值一定的情况下，尽可能地锁定离目标更近的位置，提高跟踪的效率。图5展现了Meanshift方法（图5）和本文提出的Surf-Meanshift算法（图6）的迭代路径，在该帧图像中，两种方法经过迭代最终确定了同样的目标位置坐标，由图可以看出原始的Meanshift方法到达目标位置经过了7次迭代，而本文提出的Surf-Meanshift算法通过预测目标在下一帧的位置，将迭代初始值预置为了离目标更近的位置（图中0’），再经过2次迭代，即锁定了目标位置。

4 实验结果

为检测算法效果，实验中选取了三段鸟类飞行视频1，2进行测试。三段视频的具体参数如表1所示。

4.1 跟踪结果

效果图中，统一图7右图为Surf-Meanshift算法的跟踪结果。图7所示是目标与背景差别较大的情况Meanshift算法和Surf-Meanshift算法的跟踪结果，在这种情况下，原始的算法和改进算法跟踪效果的差别不大。

图8所示是在有树枝干扰情况下Meanshift算法和Surf-Meanshift算法的跟踪结果。鸟类目标与背景颜色仍有一定的差异，此时Meanshift算法能够大致锁定鸟的位置，但是由于目标与树枝颜色非常相近，树枝的干扰使跟踪发生一定的偏移，在这种情况下，本文提出的Surf-Meanshift算法具有更高的准确率。

图9所示是目标和背景颜色相近情况下Meanshift算法和Surf-Meanshift算法的跟踪结果。在背景的干扰下，鸟类运动速度较快时，Meanshift算法的跟踪性能随着目标的快速运动越来越差，最终跟丢，而Surf-Meanshift算法由于在迭代起始时通过局部特征点匹配将Roi区域拉向了目标最可能出现的位置，依然保持较好的跟踪性能。

图10所示是曝光情况下Meanshift算法和Surf-Meanshift算法的跟踪结果。在自然光线较亮时，背景和光照的因素干扰加强，此时Meanshift算法无法有效捕捉目标，而Surf-Meanshift算法的跟踪结果虽然有所偏移，但仍然能够锁定目标的大致位置。

4.2 结果评价

4.2.1 评价指标

为验证本文算法的有效性，采用迭代次数来评估不同方法实现鸟类目标检测的性能。定义总迭代次数S：

式中N为视频帧数，i表示视频的第i帧，Si为每一帧的迭代次数。

4.2.2 比较分析

与Meanshift算法相比，本文方法有效减少了寻找跟踪目标中心点过程的迭代次数（如表2所示），提高了算法效率。

5 结束语

本文研究了野外观测视频中鸟类目标的跟踪方法，考虑鸟类运动的自然环境等实际应用因素，提出了一种融合局部特征点匹配和Meanshift方法的Surf-Meanshift跟踪算法，并通过四个视频进行了测试实验。实验结果证明，该方法有效缩小了目标的搜索范围，减少了迭代次数，提高了跟踪的效率和准确度。在背景与目标相似且目标运动速度较快时优势更为明显，具有一定的应用价值。

在实际应用中，由于视频质量容易受到野外观测条件和设备状态等因素的影响，该方法应用于飞鸟检测时也还有很多问题需要进一步分析和研究。比如视频中有可能出现其它物体遮挡飞鸟从而干扰轮廓提取造成跟踪失败。要解决这些具体问题，还需要进一步深入开展研究工作。