基于MeanShift算法的目标跟踪.doc

基于MeanShift算法的目标跟踪
1 算法描述
meanshift算法背景
meanShift这个概念最早是由Fukunage在1975年提出的,Fukunage等人在一篇关于概率密度梯度函数的估计中提出这一概念。其最初的含义正如其名:偏移的均值向量;但随着理论的发展,meanShift的含义已经发生了很多变化。如今,我们说的meanShift算法,一般是指一个迭代的步骤,即先算出当前点的偏移均值,然后以此为新的起始点,继续移动,直到满足一定的结束条件。
在很长一段时间内,meanShift算法都没有得到足够的重视,直到1995年另一篇重要论文的发表。该论文的作者Yizong Cheng定义了一族核函数,使得随着样本与被偏移点的距离不同,其偏移量对均值偏移向量的贡献也不同。其次,他还设定了一个权重系数,使得不同样本点的重要性不一样,这大大扩展了meanShift的应用范围。此外,还有研究人员将非刚体的跟踪问题近似为一个meanShift的最优化问题,使得跟踪可以实时进行。目前,利用meanShift进行跟踪已经相当成熟。
meanshift算法原理
Meanshift可以应用在很多领域,比如聚类,图像平滑,图像分割,还在目标跟踪领域有重要的应用。Meanshift跟踪算法是通过计算候选目标与目标模板之间相似度的概率密度分布,然后利用概率密度梯度下降的方向来获取匹配搜索的最佳路径,加速运动目标的定位和降低搜索的时间,因此其在目标实时跟踪领域有着很高的应用价值。
该算法由于采用了统计特征,因此对噪声具有很好的鲁棒性;由于是一个蛋参数算法,容易作为一个模块和其他算法集成;采用核函数直方图建模,对边缘阻挡、目标的旋转、变形以及背景运动都不敏感;同时该算法构造了一个可以用meanshift算法进行寻优的相似度函数。Meanshift本质上是最陡下降法,因此其求解过程收敛速度快,使得该算法具有很好的实用性。
Meanshift算法的思想是利用概率密度的梯度爬升来寻找局部最优。它要做的就是输入一个在图像的范围,然后一直朝着重心迭代,直到满足你的要求或者达到迭代最大次数结束。在opencv中,进行meanshift其实很简单,输入一张图像(imgProb),再输入一个开始迭代的方框(windowIn)和一个迭代条件(criteria),p )。
这是函数原型:
int cvMeanShift( const void* imgProb, CvRect windowIn,
CvTermCriteria criteria, p* comp )
参数介绍:
imgProb:目标直方图的反向投影
windowIn:初试的搜索框
Criteria:确定搜索窗口的终止条件
Comp:生成的结构,包含收敛的搜索窗口坐标(comp->rect 字段) 与窗口内部所有像素的和(comp->area 字段)
meanshift算法跟踪目标实现步骤
首先从摄像头或者本地文件读入视频
选择要跟踪的物体,程序读取一帧视频
计算视频帧的色调直方图
计算视频帧的反向投影图
输入反向投影图和跟踪矩形框,调用meanshift算法迭代,寻找局部最优解。根据重心的移动,调整跟踪矩形框
读取下一帧视频,用当前矩形框作为输入,重复执行步骤2-5
meanshift算法实现过程
1 在颜色概率分布图中选取搜索窗W
2 计算零阶距:
计算一阶距:
计算搜索窗的质心:
3 调整搜索窗大小
宽度为


4 移动搜索窗的中心到质心,如果移动距离大于预设的固定阈值,则重复2)3)4),直到搜索窗的中心与质心间的移动距离小于预设的固定阈值,或者循环运算的次数达到某一最大值,停止计算。
meanshift算法跟踪效果
。
图
。
图
。
图
从以上效果图可以发现,meanshift算法处理的是HSV中的色调分量。换句话说,就是通过追踪相同的颜色,而达到追踪物体的功能。程序首先计算点选框里的有效像素点,通过统计获得像素点分布直方图;然后计算出视频的反向投影图,即是像素点的概率分布图。,越亮的点就是与原物体越匹配的点,大量的亮点的聚集处就极有可能是需要跟踪的物体;最后用矩形框框住当前帧中带跟踪的物体,。
当被跟踪的物体的色调与背景相似时,跟踪就会失效,。
图
显然,当背景与被跟踪物体颜色难以区分时跟踪会失败