运动目标跟踪,是当今计算机视觉与图像处理领域的重要的研究方向之一,也是当前该领域下的一个热门课题。它往往是以运动目标检测为基础,是基于运动物体检测的一种后续的延伸处理。它的基本原理是通过对目标对象进行建模,根据对象的特点——包括外形、颜色特征、边缘特性等因素进行不间断跟踪,进而获取目标的实时运动轨迹及动态参数[1]。以此为基础,为后续的进一步发掘和识别目标提供数据支撑。现阶段,视频序列中的目标跟踪算法在交通运输、电子监控、智能设备交互、军事等领域都有着很大的发展空间。
当前来说,常见的跟踪算法往往可以按照如下分类来进行划分,比如基于目标轮廓的跟踪算法、基于区域匹配的跟踪算法、基于特征匹配的跟踪算法以及核方法等。针对不同的场景,众多学者也提出了多种目标跟踪算法。其中,Meanshift算法[2-3]由于其跟踪效果优良,寻优过程收敛速度快、耗时短等优点受到广泛应用,但是由于该算法缺少应有的模型更新,当待跟踪目标存在尺寸变化时,检测效果可能会大打折扣,甚至丢失目标。针对以上缺点,Bradski在其基础上提出了Camshift(连续自适应均值漂移)算法[4-5],它可以根据目标的大小自适应地调整搜索窗口尺寸,大大加强了跟踪效果。
但是当目标颜色与周围背景的颜色之间发生干扰作用时或者视频帧中的背景相对比较复杂多变时,基于颜色特征进行跟踪的原始Camshift算法很可能会失去效果。所以,针对此不足,为了可以做到持续跟踪目标,本文提出一种基于ORB特征点匹配的改进Camshift目标跟踪算法,以提高跟踪的实用性与鲁棒性。
1 Camshift跟踪算法 1.1 Meanshift目标跟踪的基本原理已知集合{xi}i=1,2,…,n,该集合是在d维空间Rd,若包含n个这样的集合,那么点x处的概率密度可以表示为
(1) |
式中核函数用K(x)来表示,窗宽用h表示,那么
(2) |
式中:ck,d要能使得K(x)的积分值为1,而k(x)则要满足以下三点:非负、递减、分段连续且可积分。其中,在Meanshift算法中使用的k(x)表达式为
(3) |
那么点x处的概率密度可以改写为
(4) |
如果想要求得均值漂移算法中特征值所对应的概率密度,那么就需要式(4) 了。如果再对结果进行梯度估计,那么就可以获知所有数据信息中最大密度数据的分布。具体方法是先设g(x)=-k′(x),第二步定义一个核函数G(x)=Cg(‖x‖2),其中归一化常数用C表示,对式(4) 求取梯度整理之后可得:
(5) |
该表达式就是Meanshift矢量,也就是均值平移矢量。利用核函数G(x)计算点x处的概率密度为
(6) |
利用式(5)、(6)以及归一化密度梯度估计$\hat{\nabla }$fK(x)的定义可以得到如下关系式:
(7) |
可以看出,通过核函数G(x)计算得到的点x处的Meanshift矢量mh,G(x)与通过核函数K(x)得到的归一化密度梯度估计$\hat{\nabla }$fK(x)之间呈线性关系,可以看出,Meanshift向量总是指向密度变化最大的方向。在这里均值平移的过程也就是计算Meanshift矢量mh,G(x)并且根据mh,G(x)来更新核函数G(x)中心的一个递归的过程。
那么用集合{yi}i=1,2,…,n来表示连续序列核G的位置,该核的初始位置中心在y1,yj+1是以yj为自变量的核G上的加权平均值,那么
(8) |
只要核函数k(x)满足上文中提到的非递增等3个性质,而且g(x)=-k′(x),那么这个连续序列yii=1,2,…,n就可以收敛于局部最大值,如果设y1是所要搜索目标的初始位置,那么Meanshift算法就会不断地计算均值平移矢量,迭代更新目标位置,直至收敛于最优匹配点[12]。
1.2 Camshift目标跟踪算法Camshift算法是由Bradski提出的基于Meanshift的改进算法,该算法的整体流程如图 1所示,其算法步骤如下。
1) 将图像序列从RGB颜色空间转换到HSV空间,这是因为HSV空间的3个分量色度(hue)、饱和度 (saturation)和亮度(value)之间是相互独立的,可以减少光线亮度变化对跟踪效果的影响。
2) 对序列的起始帧的跟踪区域进行预处理,进而求出待跟踪物体的色度分量H并绘制直方图。
3) 将各个像素点作为独立的特征点进行处理,并且其值要用在直方图上的H分量的概率值做调换,这样子就可以将反向投影图求出,并且计算出各个点在该范围内出现的可能性大小。
4) 因为可以从反向投影图上看出图像中针对待跟踪物体的颜色特征的变化分布,其中亮度值数据就是这一具体的像素点的权重。这一算法不仅在投影图上反复循环计算,而且其强大的自适应能力能够快速又准确地确定搜索窗口的范围,确定最理想的搜索区域。那么,目标搜索窗口的零阶距为
(9) |
式中I(x,y)是搜索窗范围内坐标(x,y)的像素值。搜索窗内的一阶距和二阶距以及搜索窗口的质心分别为
(10) |
(11) |
(12) |
在使用均值漂移算法时,得出式(12) 质心位置会被当作搜索窗的正中央,然后不断循环这个过程,搜索窗要不停地移动位置,进行迭代计算,一直要到触发迭代中止的条件才会跳出循环。
5) 重新调整搜索窗尺寸,并且通过式(13) 得出下一帧当中该搜索窗的宽度w和高度h。
(13) |
式中:
6) 如果当前帧没有达到序列的末尾位置,就可以利用重新计算得出的搜索窗对下一帧的目标图形继续进行迭代运算。同样的,迭代的过程依旧采用Meanshift算法[5]。
目前现有的Camshift算法是通过提取待跟踪物体的色彩值进行跟踪的。由于其不仅可以根据待跟踪物体的边缘特征的变化自适应地调节搜索窗口的范围,从而使这一算法的输出结果更为精准。图 2使用的“多人”序列中将对颜色特征比较鲜明的身穿蓝色衬衫的人物进行跟踪。可以看到,在这种情况下,跟踪的效果比较好,轻微的遮挡对跟踪的效果的影响也并不大。
然而该算法以待跟踪物体的色彩特征进行跟踪,也同样基于这一原因,使得背景干扰成了这一算法的最大的挑战。当目标颜色与周围背景的颜色之间发生干扰作用时或者视频帧中的背景相对比较复杂多变时,Camshift算法很可能会失去效果,严重时甚至可能丢失目标从而导致目标跟踪失败。下面用两组试验来进行说明。
如图 3所示,这些帧图像选自“行人”序列,如果将待跟踪目标的腿部作为目标模型,则会实现对该目标的跟踪;而如果将目标的全部信息或者上半部的信息作为目标模型,由于背景干扰发生了跟踪失败的现象,Camshift的搜索窗由于受到背景的干扰会迅速扩大,而一般正常情况下跟踪窗口发生的形变在相邻两帧之间应该是缓变的。
如图 4所示,这些帧图像选自“摩托车”序列,由于视频是以一辆正在行驶的摩托车的视角进行拍摄的,因此背景的变化会比较剧烈,使用Camshift算法跟踪目标时往往不能做到准确的跟踪,很容易就会导致目标丢失的现象。图 2~4中,矩形框代表待跟踪的目标所处的位置。
针对目标跟踪中产生的这些问题,大量学者也进行了相关的研究,并提出了许多改进的方法。
文献[6]提出了一种结合帧差与Camshift的改进方法,利用跟踪区域帧差去除背景的干扰作用,对背景颜色干扰目标跟踪的情况起到了一定的改善作用。文献[7]提出了一种用于跟踪的改进的基于金字塔的光流匹配算法,解决了匹配后存在不稳定特征点的问题,但是计算量相对较大,要耗费大量的计算资源。文献[8]以其中待跟踪物体无法自动更新模型算法以及整体上的模型更新易出现漂移等现象,提出了一种选择性模型更新的MeanShift运动目标跟踪算法,但该方法对于背景干扰等问题并没有涉及。
所以针对传统的Camshift算法上的不足,使之可以更加准确地跟踪运动目标,可以采取鲁棒性较好的特征点匹配算法与传统的Camshift算法相结合的方法,本章中选用的特征点匹配算法就是ORB特征点匹配。
2 ORB特征点匹配ORB特征点匹配算法使用了耗时极短的FAST角点并为前面得到的角点添加方向信息,同时为了能够描述该角点,又使用了十分明了的带有角度的BRIEF二进制位串,最后的特征匹配又加入了汉明距离。该算法具有良好的鲁棒性和匹配性能。
2.1 特征点提取ORB算法使用的特征点就是通过FAST算法得到的,如果在图像中某个点周围空间具有一定数量的像素点的灰度值与这个点有很大不同,则这个点就是FAST角点。若是用数学语言来描述,就是先确定中心为待确定特征点P,然后将点P与其周围空间上的点的灰度值作对比,如果该点周围具有了超过一定数量的灰度值差超过所设定阈值的点,那么待确定特征点P就可以确定为特征点。这个过程如下所示,首先设定一个阈值t,用Ip表示中心像素的灰度值,Ip→x表示中心像素周围圆周上像素的灰度值,用一种缓慢的方法分别测试p点周围的16个像素点,如图 5,对于在圆周上的每一个像素点x∈(1,2,…,16) ,相比p点可以表示为3种状态:
(14) |
如果想要确定中心点是一个角点,那么图中所示的圆圈上一定要出现超过预先设定的阈值数量的接连出现的满足亮点或暗点条件的像素点。FAST算法只是对灰度值进行比较,具有计算过程容易、耗时短的优势[9]。
为了使原始的FAST角点具有方向特征,可以以特征点为中心,在其邻域内计算质心的位置,然后定义指向质心位置的偏移矢量,该矢量的指向就是特征点的方向,角点邻域的各阶距为
(15) |
式中图像的灰度值用I(x,y)来表示,那么该区域的质心坐标和该偏移矢量方向角为
(16) |
ORB特征点的描述子是二进制码串结构的,那么图像特征点的邻域便可用较少的像素强度对比来表示,使得计算更加简捷,在特征点周围S×S的邻域空间P中,随机选取nd对像素点,并且定义准则τ为
(17) |
式中p(x)表示滤波处理后邻域P在点x=(u,v)T的灰度值。一组点对能够确定一个二进制检测τ。因此定义nd维的二进制字符串如式(18) ,为BRIEF的描述符。
(18) |
式中nd可以为128、256、512等,根据具体需求来设定。
BRIEF描述子本身并没有方向,没有旋转不变性,不过可以加入在2.1节中介绍的偏移矢量的方向,那么在每个特征点周围选取的nd个点对(xi,yi)处,定义如下的2×nd的矩阵:
(19) |
根据求出的偏移矢量方向角θ及其对应的旋转矩阵Rθ,可以将矩阵P变换为
(20) |
再根据式(20) 计算出具有旋转校正BRIEF描述子向量
(21) |
最后通过贪婪搜索,搜索获得相关度最低的256个点对,就可以获得ORB所拥有的局部特征点描述子[10]。
3 改进的Camshift目标跟踪算法原始Camshift算法通过提取目标的颜色特征能够有效地对视频中的运动目标进行持续跟踪,并且可以自动调节搜索窗大小,从而提高运动目标跟踪的准确性。但是,当背景与运动目标颜色相近或者背景复杂多变的情况下,很容易发生跟踪失败的情况,ORB算法具有良好的匹配性能和鲁棒性,所以当应用传统Camshift算法跟踪失败时,可以利用ORB算法进行特征点匹配,找到在上一帧中跟踪失败的目标,然后再回到Camshift算法达到对目标连续跟踪的目的。
3.1 改进Camshift算法的流程巴氏系数[11] (Bhattacharyya系数)是用来判别图像的相似程度的量纲,那么它便可以用于目标跟踪这个领域中,它可以用来判别视频的前后两帧中跟踪的目标是否一致,进而可以进一步判断目标是否发生丢失。巴氏系数的数学意义是2个矢量间夹角的余弦值,即
(22) |
而实际上是矢量间的内积,而这2个矢量分别是(
(23) |
当待跟踪目标与候选目标完全一致时,ρ(y)的值会达到1,所以可以通过设定一个检测阈值来判别是否发生目标丢失、跟踪失败的情况。
本文结合了ORB特征点匹配来改进传统的跟踪算法。在一般的情况下,使用原始的Camshift算法,当出现待跟踪物体丢失的情况时,使用ORB特征点匹配来重新捕获运动目标所在的区域,然后再持续跟踪。这样便可以大大增强目标跟踪的准确性,图 6为改进算法流程图。
1) 初始化待跟踪目标的初始区域,并作为Camshift算法的初始搜索窗;
2) 利用原始的Camshift算法对当前帧跟踪所选目标,计算初始搜索窗的颜色直方图,然后重新计算搜索窗的质心坐标以及宽度和高度等参数,这一步便将待定的运动目标位置确定了下来;
3) 计算候选目标区域的颜色直方图,结合第2) 步得出的直方图共同计算巴氏系数;
4) 如果巴氏系数大于等于设定的检测阈值,那么说明该候选区域就是跟踪目标所在位置,将之确定为目标区域;
5) 如果巴氏系数小于设定的检测阈值,那么说明发生了跟踪失败的情况,使用ORB特征点匹配算法将初始搜索窗的待跟踪目标与当前帧图像进行匹配,找到图像中丢失的目标,重新确定目标所在的位置,最后再通过Camshift算法继续跟踪得到最终的跟踪结果;
6) 利用得到的结果作为搜索窗继续下一帧图像的跟踪。
3.2 实验分析这里将通过几组仿真实验来验证改进算法的性能,本次仿真实验是在处理器型号为Intel-i5-4200H,主频为2.80 GHz,内存为4 GB,操作系统为Windows 8.1中文版的PC机上使用Visual Studio 2005以及OpenCV 2.4.3 版本实现。首先验证常规场景下该改进算法的性能。
在视频序列中间曾出现轻微的遮挡问题,一般情况下改进算法中通过引入的ORB算法也能识别出所要跟踪的目标,图 7中的第4,106,114,160帧就是通过引入的ORB算法来确定目标区域的。第106,114,160帧都是由于待跟踪目标被轻微遮挡而使得巴氏系数下降到检测阈值以下,从而通过特征点匹配去找寻目标完成跟踪,取得了很好的效果。图中矩形框代表待跟踪的目标所处的位置。
接下来讨论当背景颜色发生干扰时改进算法的性能。前面已经用“行人”序列验证过原始算法的跟踪特性,使用原始算法时,当目标经过时,Camshift的搜索窗由于受到背景的干扰会迅速扩大,甚至最后遍布整个屏幕,使得跟踪失败,而一般正常情况下跟踪窗口发生的形变在相邻两帧之间应该是缓变的。而改进算法尽管在初始阶段也发生了搜索窗扩大的现象,如图 8(a)、(b)所示,但是后来当巴氏系数到达检测阈值,跟踪即将发生失败时,通过结合的ORB算法对搜索窗的范围和大小等参数进行校正,可以找寻到丢失的跟踪目标,再通过Camshift算法得到最终的跟踪结果,实现准确的跟踪。实验结果显示,该算法对于背景发生干扰的情况有很好的抑制作用。除此之外,基于ORB的Camshift改进算法也能在背景变化比较剧烈的情况下完成跟踪。
如图 9所示,由于“摩托车”视频序列背景变化比较剧烈,当使用原始Camshift算法时往往不能准确地跟踪目标,导致跟踪失败,而使用本文的改进算法则可以通过ORB特征点匹配迅速地找到丢失的目标,完成跟踪过程,提高了跟踪的准确性。尽管在一部分帧图像中仍然不能准确跟踪,比如在摩托车腾空时有时会发生丢失目标的情况,但是依靠结合的特征点匹配很快就会重新找寻到目标,继续完成跟踪过程。
表 1、2是对这2组仿真实验所做的数据对比,各个表中的对比数据为了保证数据的可靠性和普遍性,均是经过多次仿真测量后得到的数据,用以减弱误差造成的影响。
表 1是原始算法与改进算法在不同视频序列中目标跟踪准确性的数据对比,为了保证仿真结果的稳定可靠,A、B、C是对同一视频序列所做的3组仿真实验,在“多人”序列中,从表 1中可以看出数据值相差不大,说明2种算法在常规场景下都具有良好的跟踪性能;在“行人”序列中,由于背景的干扰,使得原Camshift算法发生了跟踪失败的现象,而改进算法则在巴氏系数低于检测阈值的情况下引入ORB算法,从而提高了跟踪的准确率;而在“摩托车”序列中,原始Camshift算法的跟踪准确率特别低,这是因为Camshift算法尽管在一定程度上能够适应背景发生变动的场景,但是如果背景变动比较剧烈,例如在此视频序列中,由于该视频的视角是在一辆正在行驶的摩托车上拍摄的,待跟踪目标在连续两帧间的位置变化也可能会比较大,那么原算法在不经过校正的情况下可能很快(即仅仅经过短短几帧)就跟踪失败,而且很难再重新搜索到目标,从而跟踪到的帧数可能会很少,因此在该序列中的跟踪准确率非常低。而改进算法中引入的ORB特征点匹配可以在目标丢失的情况下重新校正并搜索目标,使得持续跟踪得到了保证,从而提高了跟踪的准确率。这也是在类似场景下2种算法跟踪准确率相差较大的原因。而表 2中的数据则是通过多次仿真测量求取均值得到的结果。
视频序列 | 总帧数 | Camshift算法跟踪准确的帧数 | 改进算法跟踪准确的帧数 | |||||||||
A | B | C | 平均值 | 准确率 | A | B | C | 平均值 | 准确率 | |||
“多人” | 486 | 430 | 438 | 439 | 436 | 0.897 | 415 | 420 | 426 | 420 | 0.864 | |
“行人” | 80 | 31 | 33 | 34 | 33 | 0.413 | 65 | 69 | 69 | 68 | 0.850 | |
“摩托车” | 1 000 | 13 | 15 | 18 | 15 | 0.015 | 729 | 733 | 735 | 732 | 0.732 |
视频序列 | 分辨率 | 总帧数 | 原始算法平均帧率/(f·s-1) | 改进算法平均帧率/(f·s-1) |
“多人” | 720×576 | 486 | 20.30 | 11.58 |
“行人” | 320×240 | 80 | 25.80 | 15.20 |
“摩托车” | 470×310 | 1 000 | 26.45 | 18.91 |
表 2是不同视频序列中各算法平均帧率的数据对比,可以看出,对于分辨率较小的视频来说,改进算法尽管引入了ORB特征点匹配和巴氏系数判别,但是平均帧率与原算法的差距并不大,而且依然达到了实时性的要求。
4 结论本文主要研究了当前在目标跟踪领域应用比较广泛的算法之一——Camshift算法,并在此基础之上,针对传统算法易产生目标丢失的情况,提出一种基于ORB特征点匹配的改进算法,引入巴氏系数用来判别是否发生了目标丢失,该改进算法具有以下优势:
1) 当由于目标颜色与周围背景的颜色之间发生干扰作用时或者视频帧中的背景复杂多变而造成目标丢失的情况时,可以由引入的ORB算法对运动目标进行匹配,具有重新寻找并获得目标的机制。
2) 这个改进策略大大增强了Camshift算法的通用性,使得该算法适用于更多的场景。
本文所做的仿真实验表明,改进算法具有明显优于原算法的跟踪性能,不过由于该算法引入的ORB特征点匹配加大了一部分的计算量,在时间复杂度上要略高于原算法。
[1] | 贾艳丽. 基于视频图像序列的运动目标检测与跟踪[D].哈尔滨: 哈尔滨工程大学, 2012: 3-4. http://epub.cnki.net/kns/detail/detail.aspx?QueryID=0&CurRec=1&recid=&FileName=1012517506.nh&DbName=CMFD201301&DbCode=CMFD&pr= |
[2] | 高琳. 特征匹配的对象跟踪与支持向量机对象行为识别[D]. 长春: 吉林大学, 2013: 18-26. http://epub.cnki.net/kns/detail/detail.aspx?QueryID=4&CurRec=1&recid=&FileName=1013196399.nh&DbName=CMFD201302&DbCode=CMFD&pr= |
[3] | 朱胜利. Meanshift 及相关算法在视频跟踪中的研究[D]. 杭州: 浙江大学, 2006: 20-32. http://epub.cnki.net/kns/detail/detail.aspx?QueryID=8&CurRec=1&recid=&FileName=2006073632.nh&DbName=CDFD9908&DbCode=CDFD&pr= |
[4] | BRADSKI G. Real time face and object tracking as a component of a perceptual user interface[C]. Proceedings of the 4th IEEE Workshop on Applications of Computer Vision. Princeton, USA: IEEE, 1998: 214-219. http://cn.bing.com/academic/profile?id=2121836097&encoded=0&v=paper_preview&mkt=zh-cn |
[5] | BRADSKI G R. Computer video face tracking for use in a perceptual user interface[J]. Intel technology journal , 1998, Q2 : 214-219 |
[6] | 基于Camshift和Kalman滤波的多目标跟踪算法研究[D]. 武汉: 中南民族大学, 2010: 12-27. http://cdmd.cnki.com.cn/article/cdmd-10524-1011256512.htm |
[7] | 丁尤蓉. 基于特征点的目标跟踪算法研究[D]. 南京: 南京航空航天大学, 2013:19-26. http://epub.cnki.net/kns/detail/detail.aspx?QueryID=12&CurRec=1&recid=&FileName=1014005516.nh&DbName=CMFD201401&DbCode=CMFD&pr= |
[8] | 彭艳芳. 视频运动目标检测与跟踪算法研究[D]. 武汉: 武汉理工大学, 2010: 3-16. http://cdmd.cnki.com.cn/article/cdmd-10497-2010164540.htm |
[9] | 许宏科, 秦严严, 陈会茹. 基于改进ORB的图像特征点匹配[J]. 科学技术与工程 , 2014, 14 (18) : 105-109 |
[10] | 智金波. 基于局部特征点的图像配准算法及应用研究[D]. 北京: 北京印刷学院, 2015: 18-34. http://epub.cnki.net/kns/detail/detail.aspx?QueryID=16&CurRec=1&recid=&FileName=1015523988.nh&DbName=CMFD201501&DbCode=CMFD&pr= |
[11] | COMANICIU D, RAMESH V, MEER P. Kernel-based object tracking[J]. IEEE transactions on pattern analysis and machine intelligence , 2003, 25 (5) : 564-577 DOI:10.1109/TPAMI.2003.1195991 |
[12] | BRADSKI G, KAEBLER A. Learning OpenCV[M]. 北京: 清华大学出版社, 2009 . |