基于目标特征提取的改进型压缩跟踪算法

庄哲民， 龚家铭， 谢光成， 袁 野

(汕头大学 电子工程系， 广东 汕头 515063)

基于目标特征提取的改进型压缩跟踪算法

庄哲民， 龚家铭， 谢光成， 袁 野

(汕头大学 电子工程系， 广东 汕头 515063)

本文在传统的尺度不变特征子(Scale Invariant Feature Transform， SIFT)算法的基础上， 提出了一种新的基于改进的SIFT 压缩感知跟踪算法. 该方法一方面通过改进压缩跟踪算法中分类器的更新策略来提高算法的实时性； 另一方面， 通过改进SIFT向量邻域的选取方法来实现降低向量维度， 从而减少计算复杂度. 仿真实验表明， 该方法不仅可以提高跟踪目标的实时性， 而且能够在发生目标尺度变化、 遮挡、 漂移的情况下对运动目标进行准确跟踪.

运动目标跟踪； 特征提取； SIFT； 压缩感知

0 引 言

在视频图像处理技术日益成熟以及相关应用领域日益广泛的背景下， 视频跟踪技术已成为当前研究与关注的热点[1]. 由于视频内容的复杂性、 多变性以及场景的变化， 实时跟踪某个运动的对象具有一定的难度， 特别是当对象发生形变以及对象被严重遮挡时， 实时跟踪将变得更为困难. 目前常用的视频跟踪方法主要有均值偏移算法[2]、 卡尔曼滤波、 粒子滤波、 基于模板匹配[3]以及尺度不变性特征子(Scale Invariant Feature Transform， SIFT)算法[4]等.

SIFT作为图像的一个局部特征算子， 最早是David Lowe在1999年提出的. 由于SIFT算法具备对图像变换较强的适应能力， 在图像匹配以及重建中都有着很好的应用， 但因为SIFT算法的复杂性， 导致匹配过程中花费的时间较长. 因此， 本文提出了SIFT的改进算法， 其核心一方面是在进行特征提取过程中改进SIFT的处理邻域， 精简生成的SIFT算子的维度， 从而减轻计算的复杂度； 另一方面将压缩感知技术[5]用于视频数据的压缩， 并改进压缩感知中分类器学习因子的更新策略， 从而提高了整个算法的实时性.

仿真实验结果表明， 在处理运动目标发生尺度变化、 旋转、 遮挡等的情况下， 基于目标特征提取的改进型压缩跟踪算法能够准确并且高效率地追踪运动目标， 而且能够自适应应对光照改变引起的问题.

1 基于压缩感知的SIFT视频跟踪算法

1.1 改进的SIFT视频跟踪算法

标准SIFT算法利用目标的尺度不变性的特征， 整合相应的特征点来锁定目标并加以跟踪. 针对SIFT算子维度过高的缺点， 本文提出从特征算子的生成邻域入手， 对SIFT算子进行改进. 为了保证生成的描述算子具有旋转不变性， 该邻域是以SIFT特征点为圆心， 以8个像素单位为半径绘制的圆形邻域D. 我们将整个圆形领域划分为4个部分， 半径为2个像素单位的内圆D1以及环宽为2个像素单位的3个圆环D2，D3，D4， 圆形邻域D的数学表达如式(1)所示

D=(D1,D2,D3,D4).

(1)

改进后的SIFT圆形邻域D如图 1(a) 所示.

图 1 改进型SIFT特征算子的生成Fig.1 Generation of improved SIFT descriptor

图1(a)表示的是一个16×16像素单位的局部圆形邻域图， 其中不同的区域代表不同的子区域Di(其中i=1， 2， 3， 4)， 图中每一个小方格代表一个像素.

传统SIFT算子首先记录0°， 45°， 90°， 135°， 180°， 225°， 270°， 315°这8个方向的子向量， 通过整合2×2的像素子单元生成一个8维向量， 最后生成一个高达128维的向量. 而在本文中， 指定圆形邻域D对应4个部分， 其中每个部分Di分别由10个子向量构成， 这些子向量的方向分别是 0°， 36°， 72°， 108°， 144°， 180°， 216°， 252°， 288°， 324°. 因此， 圆形邻域任意一部分Di的构成可由式(2)表示

式中： 向量组(di1，di2,...,di10)是由改进后SIFT邻域所生成的10个子向量构成， 由于整个圆形邻域D生成的SIFT算子向量维度仅为40维， 大大地降低了计算复杂度.

我们以整个圆形邻域中的D1部分作为示例， 在图1(b)中的向量d11～d110就是构成向量D1的10个子向量， 显然向量D1的维度为10维， 而D2，D3，D43个向量的生成步骤与D1一致， 改进后的SIFT算子通过将圆形邻域的4个部分整合在一起后， 最终算子的维度为40维.

之所以选定圆形邻域， 是由于其对旋转不敏感， 从而减少一些特殊状况对跟踪结果的影响. 为了能够进一步处理复杂场景中目标发生较大尺度的旋转的问题， 则需要在邻域的每个部分Di中寻找幅值最大的那个子向量dij(i=1， 2， 3， 4；j=1， 2， ...， 10)， 并将dij以及之后的所有子向量同时进行相应的左移. 假设在D1找到其中最大的子向量， 假设该子向量就是d11, 那么D1则不需要进行左移， 因为该向量集的第一个子向量即为本向量集中幅值最大的一个. 否则就需要把幅值最大的这个子向量以及其后的所有向量提前， 相应地， 在该幅值最大的子向量之前的所有子向量右移到后部分. 也就是说假设D1中最大的子向量是d14, 那么前面3个向量则右移到最后， 其他子向量全部一致性地左移. 最后结果如式(3)所示

D=(di4,di5,…,di9,di10,di1,di2,di3)i∈[1,4].

(3)

在传统SIFT算法中， 只将特征点(极值点)梯度的相角作为旋转角度， 而不是把邻域内其他点的相角作为旋转角度， 故在本文中， 只将子向量集中第一个子向量作为左移的参考来处理发生旋转的状况.

实际的跟踪过程中很容易发生光照的骤变或者渐变， 为了减轻相应的影响， 故在生成完整的特征算子之前对其进行归一化处理

(4)

在处理非线性光照的情况时， 根据实验经验设置临界值为0.2， 当向量中某子向量的幅值超过了临界值， 则重置为0.2， 相应地再重新进行归一化处理使得每个子向量符合要求.

可见对SIFT算子的生成邻域进行改进后， 优化后的SIFT算子不仅能够保留传统算子的优秀性能， 而且大大降低了算子的维度， 从而降低了算法的计算复杂度， 为了进一步提高整个算法的实时性， 将引入压缩感知理论， 将视频目标跟踪结果进行优化.

1.2 基于特征提取的压缩跟踪算法的实现

压缩感知理论在视频跟踪的应用当中最大的优点即为减少计算复杂度， 本文将压缩感知理论与特征提取算法相结合， 一方面利用压缩感知使算法降低计算量， 另一方面利用特征提取来优化跟踪效果. 同时针对传统的压缩跟踪算法和特征提取算子存在的缺点， 分别对SIFT算子以及压缩跟踪算法中分类器的更新参数进行优化， 提高跟踪算法的实时性以获取更好的跟踪结果.

基于压缩感知理论， 可以利用满足RIP条件的测量矩阵R=Rn×m， 将数据从较高维度的信号x∈Rm投影到较低维度的信号v∈Rn， 如式(5)所示

式中：n≪m， 在理想情况下， 稀疏矩阵R能够保留下每个点对的初始距离， 并且满足Johnson-Lindenstrauss定律， 测量矩阵由式(6)的规则生成

在此设置s=m/4， 通常情况下s=2或3， 可以获取一个非常稀疏的随机矩阵. 之后利用测量矩阵就可获取一个低维的特征集v(v1,v2,v3,…,vn)，n≪m, 同时为了能够更高效地进行建模， 采用贝叶斯分类器对候选者进行分类跟踪， 分类器生成方式如下[6-8]

式中：p(·)表征的是测量值y=1或者y=0时的概率值或是基于不同的y的测量值时的条件概率.

当运动目标发生漂移时， 由于压缩跟踪算法无法控制不断累计的误差， 最终很容易导致失败， 为了能够满足实时性要求， 并且控制在跟踪过程中累加的误差， 我们引入学习率来权衡分类器中高斯参数的比重[9]

式中：d和b分别表示采样特征集的前一帧与新的采样值的参数(均值μ以及协方差σ)的差值， 学习率λ就是影响分类器函数内高斯参数权重的因子[10,11]. 由于分类器的参数分为两个部分， 一部分是前一帧中目标特征的模版参数， 另一部分是当前帧中搜寻位置处新的模版参数. 当相邻两帧中运动物体运动量较小时， 那么由于新的模版参数改变量很少， 则将学习率设置得大一点， 使得分类器参数基本维持上一帧时的状态； 如果相邻两帧中的运动目标发生了剧烈运动， 则需要将λ设置得小一点， 毕竟最新的跟踪结果更加依赖于新的一帧中的信息. 综合来说， 学习率λ间接反应了运动目标的实时状况.

为了使学习率λ反映运动目标的实时状况， 需要一个能够自适应调整的学习率来权衡相邻帧的变动情况， 从而控制分类器的效果. 为了更好地表征相邻帧图片的“距离”， 首先计算出每幅图片中我们感兴趣的追踪区域的归一化直方图， 并利用巴氏系数来度量两帧图片的“距离”， 如式(10)所示

式中：pi为前一帧图像追踪区域直方图的离散分布概率， 而qi表征当前帧所追踪区域最可能的预测目标区域直方图的离散分布概率. 距离ρ就是前后两帧图像之间差异的度量， 根据设定好的阈值来确定是否对分类器相应参数进行更新， 判定规则如式(11)所示

新的学习率可定义为

学习率λ′的取值范围是(0， 1)， 它与两帧距离ρ成反比， 在实际的跟踪过程中， 首帧与末帧图像变化不大时， 学习率λ′的取值会较小； 相应的， 若是首帧与末帧中运动目标的位置情况相差甚大， 则λ′会被调整变大. 因此， 自适应的学习率能够有效地控制误差的累积， 当发生漂移和旋转的情况时， 能较好地避免跟踪失败， 采用自适应的学习率不仅没有给整个解决方案增加很多的计算量， 且能改善复杂场景下的运动目标跟踪效率.

改进的SIFT特征集是从前一帧的目标区域采样获得， 然后从初始特征点里面随机选择固定数量的特征点作为初始特征点库， 其中随机选取的特征点数量f事先会设置好. 本文的式(13)～式(15)为各个特征库内是互不影响的特征点， 分别以u,v,w进行表示， 其中第一级特征点库Sf表示为

Sf=(u1,u2,u3,…,uf).

(13)

提取当前帧的特征点集， 与前一帧所提取获得特征点库Sf进行匹配， 匹配之后的特征点集则可表示为

Sm=(v1,v2,v3,…,vm).

(14)

显而易见， 匹配的数量m一定不会超过f.

RANSC(Random Sample Concensus) 优化算法则用来将现有匹配之后的特征点进行优化， 除去错误匹配的特征点， 然后获得更准确的特征点集Sp， 如式(15)所示

Sp=(w1,w2,w3,…,wp).

(15)

此外， 还可以利用已经获取的特征点集求取变换矩阵中的未知数， 然后用来求解前一帧与当前帧目标尺寸的缩放比例和角度. 选取已经净化获得的特征点集， 并在当前帧中随机选择若干数量的特征点， 最终构成固定数量f的新的特征点库. 将上述步骤从初始帧到最后一帧， 往复地在相邻两帧中施行， 就可以求得目标尺寸的缩放比例， 算法就可以自适应地调整追踪窗口的大小， 减小跟踪误差.

2 算法仿真实现与分析

针对发生遮挡、 光照以及旋转的场景中的目标跟踪， 我们分别从公共目标跟踪视频库中选取face片段与coke片段， 并在i7-4710MQ， 8G主机上进行调试， 获取如图 2 的跟踪结果， 其中a矩形框为原始压缩跟踪算法的跟踪结果， b矩形框则是基于特征提取改进型压缩感知跟踪算法的追踪结果. 从整个跟踪过程当中随机抽取6帧出来进行对比， 可见人脸在从未遮挡到遮住部分再到完整再现整个过程中两种方法的跟踪结果.

图 2 face人脸跟踪效果对比Fig.2 Face contrast experiment

如图 2 所示， 第1帧为初始化跟踪目标， 在发生遮挡以前， a框与b框的效果基本一致， 然后从第22帧开始有书籍分别从各种角度遮挡住人脸， 在第27帧、 第92帧、 第157帧时a框都不能像b那样稳定地追踪运动目标， 而且在最后目标重新暴露在视频中的时候， a框也无法恢复跟踪. 我们可以看出b框不论在哪种遮挡的情况下都能稳定地追踪到目标， 而采用原始压缩跟踪算法的a框跟踪效果并不理想. 其原因一是在改进型的压缩跟踪算法的分类器参数λ是实时更新的， 而在传统算法中该学习率的值是设置为固定的0.85； 二是改进型的算法融合了优化的特征提取算法SIFT来强化跟踪效果， 能在复杂的场景下跟踪目标.

图 3 coke可乐罐跟踪效果对比Fig.3 Coke cans contrast experiment

在第二个场景中， 视频流中会出现光照、 遮挡和旋转这几种常见的问题， 同样采用传统的压缩跟踪算法与改进型压缩跟踪算法分别进行实验， 随机选取其中的6帧进行对比， 其中b框代表的是采用基于特征提取的改进型压缩跟踪算法的实验结果， a框代表的是传统压缩跟踪算法的跟踪结果， 具体见图 3.

如图 3 所示， 同样第一帧为初始化选定跟踪目标， 当人拿着罐头在灯泡以及植被附近运动且罐头仅仅自身旋转时， 我们可以看到在第16帧附近时两种算法的跟踪效果基本一致； 但在第34帧时， 当罐头在移至离灯泡较远处并被植被的叶子所遮挡的时候， a框已经部分脱离了要跟踪的物体； 第102帧时罐头自身发生旋转， 此时的a框依然脱离了想要跟踪的目标； 再到第274帧时， a框完全脱离目标， 无法再跟上运动目标的节奏， 然后b框却从始至终稳定地将目标跟踪在框内.

可见由于物体的运动不可预测， 跟踪过程中的分类器参数如果只单凭借经验设置固定值而不随物体实际运动实时更新的话， 则跟踪效果总是不能如意； 再则就是在复杂场景中， 对运动目标进行高效率的特征提取， 那样才能保证在发生了光照变化、 遮挡、 目标旋转等情况下仍然能稳定追踪到前景目标.

为了数值化测量本方法的计算复杂度， 显示其优越性， 故将改进型压缩感知跟踪算法与传统压缩跟踪算法(CT)分别在同一PC机上重复进行调试运行20遍， 取各个过程的均值记录如表 1 所示.

表 1 改进型压缩跟踪算法与传统压缩跟踪算法的运行耗时对比

本文算法除了具有较高的实时性的优点之外， 经过改进后的SIFT算子与压缩感知理论融合后的算法还能够在跟踪的准确度上有较高的优越性. 中心位置错误率是用来定量评估追踪矩形的中心和实际目标中心的欧几里德距离. 为了提高该数据的准确性， 在软-硬件平台分别进行仿真本文的算法、 传统的CT算法、 TLD算法以及OAB(Online AdaBoost)算法20遍， 分别取中心位置错误率的平均值进行对比.

表 2 中心位置错误率对比(以单个像素为单位)

通过观察表 2 中的数据， 相比于其他算法， 本文算法在两个视频流中的跟踪具有较强的鲁棒性.

3 结 论

本文在传统SIFT 算法的基础上， 通过将改进的SIFT算法与压缩感知理论进行融合， 获得基于改进SIFT特征提取的压缩跟踪算法. 该算法一方面利用SIFT算子对目标进行实时检测跟踪的优秀性能， 并且克服了原算子高维度的缺点； 另一方面将压缩感知理论引入到视频跟踪算法中来， 进一步优化跟踪结果， 提高实时性能， 从而在复杂的环境下， 能够鲁棒地跟踪运动目标.

[1] Kalal Z, Mikolajczyk K, Matas J. Tracking-learning-detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7)： 1409-1422.

[2] David G. Lowe. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2)： 91-110.

[3] Grabner H, Leistner C, Bischof H. Semi-supervised on-line boosting for robust tracking[C]. European Conference on Computer Vision, Marseille, France, October 12-18, 2008： 234-247.

[4] 李新德， 刘苗苗， 徐叶帆. 一种基于2D和3D SIFT特征级融合的一般物体识别算法[J]. 电子学报， 2015， 43(11)： 2277-2283. Li Xinde, Liu Miaomiao, Xu Yefan. A recognition algorithm of generic objects based on feature-level fusion of 2D and 3D SIFT descriptors[J]. Acta Electronica Sinica, 2015, 43(11)： 2277-2283. (in Chinese)

[5] 石光明， 刘丹华， 高大化， 等. 压缩感知理论及其研究进展[J]. 电子学报， 2009， 37(5)： 1070-1081. Shi Guangming, Liu Danhua, Gao Dahua, et al. Advances in theory and application of compressed sensing[J]. Acta Electronica Sinica, 2009, 37(5)： 1070-1081. (in Chinese)

[6] 谢昕， 徐殷， 熊焕东， 等. 基于压缩感知的SIFT图像匹配算法的研究[J]. 华东交通大学学报， 2015， 32(6)： 115-121. Xie Xin, Xu Yin, Xiong Huandong, et al. Research on SIFT image matching algorithm based on compressed sensing[J]. Journal of East China Jiaotong University, 2015， 32(6)： 115-121. (in Chinese)

[7] Babu R, Patrick P, fez, et al. Robust tracking with motion estimation and local Kernel-based color modeling[J]. Image Vision Computing, 2007, 25(8)： 1205-1216.

[8] Kim T K, Woodley T, Stenger B, et al. Online multiple classifier boosting for object tracking[C]. Computer Vision and Pattern Recognition Workshops (CVPRW), IEEE Xplore, 2010： 1-6.

[9] Matthews I, Ishikawa T, Baker S. The template update problem[J]. IEEE transactions on pattern analysis and machine intelligence, 2004, 26( 6)： 810-815.

[10] Javed O, Ali S, Shah M. Online detection and classification of moving objects using progressively improving detectors[C]. Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2005： 696-701.

[11] Williams O, Blake A, Cipolla R. Sparse bayesian learning for efficient visual tracking[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2005, 27( 8)： 1292-1304.

The Improved Compression Tracking Algorithm Based on Video Target Feature Extraction

ZHUANG Zhemin, GONG Jiaming, XIE Guangcheng, YUAN Ye

(Dept. of Electronic Engineering, Shantou University, Shantou 515063, China)

An improved SIFT target tracking algorithm based on compressed sensing is proposed in this paper. The real-time performanceis improved by improving updating strategy of the classifier in the compressive theory.On the other hand, The vector neighborhood of SIFT has been improved to decrease the vector dimension and the complexity of calculation. Simulations and experiments show that this method not only can improve the real-time performance of tracking target, but also can carry on the tracking of moving target accurately in the event of a target scale variation, occlusion shelter, drifting.

video target tracking; feature extraction; SIFT; compressive sensing

1671-7449(2017)02-0093-07

2016-12-20

国家自然科学基金资助项目(61471228)； 广东省应用型科技研发专项项目(2015B020233018)

庄哲民(1965-)， 男， 教授， 博士， 主要从事图像处理， 无线传感网络方面研究

TN911.73

A

10.3969/j.issn.1671-7449.2017.02.001