基于MeanShift算法的目标跟踪

基于MeanShift算法的目标跟踪1算法描述1.1meanshift算法背景meanShift这个概念最早是由Fukunage在1975年提出的，Fukunage等人在一篇关于概率密度梯度函数的估计中提出这一概念。其最初的含义正如其名：偏移的均值向量；但随着理论的发展，meanShift的含义已经发生了很多变化。如今，我们说的meanShift算法，一般是指一个迭代的步骤，即先算出当前点的偏移均值，然后以此为新的起始点，继续移动，直到满足一定的结束条件。在很长一段时间内，meanShift算法都没有得到足够的重视，直到1995年另一篇重要论文的发表。该论文的作者YizongCheng定义了一族核函数，使得随着样本与被偏移点的距离不同，其偏移量对均值偏移向量的贡献也不同。其次，他还设定了一个权重系数，使得不同样本点的重要性不一样，这大大扩展了meanShift的应用范围。此外，还有研究人员将非刚体的跟踪问题近似为一个meanShift的最优化问题，使得跟踪可以实时进行。目前，利用meanShift进行跟踪已经相当成熟。1.2meanshift算法原理Meanshift可以应用在很多领域，比如聚类，图像平滑，图像分割，还在目标跟踪领域有重要的应用。Meanshift跟踪算法是通过计算候选目标与目标模板之间相似度的概率密度分布，然后利用概率密度梯度下降的方向来获取匹配搜索的最佳路径，加速运动目标的定位和降低搜索的时间，因此其在目标实时跟踪领域有着很高的应用价值。该算法由于采用了统计特征，因此对噪声具有很好的鲁棒性；由于是一个蛋参数算法，容易作为一个模块和其他算法集成；采用核函数直方图建模，对边缘阻挡、目标的旋转、变形以及背景运动都不敏感；同时该算法构造了一个可以用meanshift算法进行寻优的相似度函数。Meanshift本质上是最陡下降法，因此其求解过程收敛速度快，使得该算法具有很好的实用性。Meanshift算法的思想是利用概率密度的梯度爬升来寻找局部最优。它要做的就是输入一个在图像的范围，然后一直朝着重心迭代，直到满足你的要求或者达到迭代最大次数结束。在opencv中，进行meanshift其实很简单，输入一张图像（imgProb），再输入一个开始迭代的方框（windowIn）和一个迭代条件（criteria），输出的是迭代完成的位置（comp）。这是函数原型：intcvMeanShift(constvoid*imgProb,CvRectwindowIn,CvTermCriteriacriteria,CvConnectedComp*comp)参数介绍：imgProb：目标直方图的反向投影windowIn：初试的搜索框Criteria：确定搜索窗口的终止条件Comp：生成的结构，包含收敛的搜索窗口坐标(comp-rect字段)与窗口内部所有像素的和(comp-area字段)1.3meanshift算法跟踪目标实现步骤1.首先从摄像头或者本地文件读入视频2.选择要跟踪的物体，程序读取一帧视频3.计算视频帧的色调直方图4.计算视频帧的反向投影图5.输入反向投影图和跟踪矩形框，调用meanshift算法迭代，寻找局部最优解。根据重心的移动，调整跟踪矩形框6.读取下一帧视频，用当前矩形框作为输入，重复执行步骤2-51.4meanshift算法实现过程1在颜色概率分布图中选取搜索窗W2计算零阶距：计算一阶距：计算搜索窗的质心：3调整搜索窗大小宽度为长度为1.2s4移动搜索窗的中心到质心，如果移动距离大于预设的固定阈值，则重复2)3)4)，直到搜索窗的中心与质心间的移动距离小于预设的固定阈值，或者循环运算的次数达到某一最大值，停止计算。1.5meanshift算法跟踪效果使用摄像头跟踪人的肤色效果如图1.5.1所示。图1.5.1对应于图1.5.1的反向投影图如下图1.5.2所示。图1.5.2点选区域的像素点直方图如图1.5.3所示。图1.5.3从以上效果图可以发现，meanshift算法处理的是HSV中的色调分量。换句话说，就是通过追踪相同的颜色，而达到追踪物体的功能。程序首先计算点选框里的有效像素点，通过统计获得像素点分布直方图；然后计算出视频的反向投影图，即是像素点的概率分布图。如上图1.5.2所示，越亮的点就是与原物体越匹配的点，大量的亮点的聚集处就极有可能是需要跟踪的物体；最后用矩形框框住当前帧中带跟踪的物体，如上图1.5.1所示的结果。当被跟踪的物体的色调与背景相似时，跟踪就会失效，如图1.5.4所示。图1.5.4显然，当背景与被跟踪物体颜色难以区分时跟踪会失败。原因很简单，meanshift算法实现跟踪的原理就是通过计算色调的概率分布达到跟踪的效果，所以待跟踪的物体一定要与背景在色调上有区分度。类似的，本程序也可以通过设置：调试-命令参数，使用本地的视频文件来实现视频中特定物体的跟踪，具体方法如图1.5.5所示。由于实验的效果与使用摄像头跟踪物体差不多，所以就不一一截图显示了。图1.5.52程序源码与数据结构#includestdlib.h#includestdafx.h#ifdef_CH_#pragmapackageopencv#endif#ifndef_EiC#includestdio.h#includecv.h#includehighgui.h#includectype.h#endifIplImage*image=0,*hsv=0,*hue=0,*mask=0,*backproject=0,*histimg=0;//用HSV中的Hue分量进行跟踪CvHistogram*hist=0;//直方图类intbackproject_mode=0;intselect_object=0;inttrack_object=0;intshow_hist=1;CvPointorigin;CvRectselection;CvRecttrack_window;CvBox2Dtrack_box;//Meanshift跟踪算法返回的Box类//typedefstructCvBox2D{//CvPoint2D32fcenter;/*盒子的中心*///CvSize2D32fsize;/*盒子的长和宽*///floatangle;/*水平轴与第一个边的夹角，用弧度表示*///}CvBox2D;CvConnectedComptrack_comp;//连接部件//typedefstructCvConnectedComp{//doublearea;/*连通域的面积*///floatvalue;/*分割域的灰度缩放值*///CvRectrect;/*分割域的ROI*///}CvConnectedComp;inthdims=32;//划分直方图bins的个数，越多越精确floathranges_arr[]={0,180};//像素值的范围float*hranges=hranges_arr;//用于初始化CvHistogram类intvmin=10,vmax=256,smin=30;//用于设置滑动条intcvmeanshift(constvoid*imgProb,CvRectwindowIn,CvTermCriteriacriteria,CvConnectedComp*comp)//实现meanshift算法{CvMomentsmoments;//CvMoments用来计算矩形的重心，面积等形状特征inti=0,eps;CvMatstub,*mat=(CvMat*)imgProb;CvMatcur_win;CvRectcur_rect=windowIn;//当前矩形框CV_FUNCNAME(cvmeanshift);if(comp)//初始化跟踪矩形{comp-rect=windowIn;}moments.m00=moments.m01=moments.m10=0;//将阶矩和阶矩置__BEGIN__;CV_CALL(mat=cvGetMat(mat,&stub));if(CV_MAT_CN(mat-type)1)//通道数选择出错{CV_ERROR(CV_BadNumChannels,cvUnsupportedFormat);}if(windowIn.height=0||windowIn.width=0)//点选的窗口无效{CV_ERROR(CV_StsBadArg,Inputwindowhasnon-positivesizes);}if(windowIn.x0||windowIn.x+windowIn.widthmat-cols||windowIn.y0||windowIn.y+windowIn.heightmat-rows){CV_ERROR(CV_StsBadArg,InitialwindowisnotinsidetheimageROI);}CV_CALL(criteria=cvCheckTermCriteria(criteria,1.,100));//迭代的标准，精度=1.0，迭代次数=100eps=cvRound(criteria.epsilon*criteria.epsilon);//精度eps=1for(i=0;icriteria.max_iter;i++){intdx,dy,nx,ny;doubleinv_m00;//选取搜索区域，对该矩形区域计算它的,1阶矩CV_CALL(cvGetSubRect(mat,&cur_win,cur_rect));CV_CALL(cvMoments(&cur_win,&moments));/*Calculatingcenterofmass*/if(fabs(moments.m00)DBL_EPSILON){break;}//搜索区域的质量m00inv_m00=moments.inv_sqrt_m00*moments.inv_sqrt_m00;//搜索区域的水平重心偏移dxdx=cvRound(moments.m10*inv_m00-windowIn.width*0.5);//搜索区域的垂直重心偏移dydy=cvRound(moments.m01*inv_m00-windowIn.height*0.5);//搜索区域的重心坐标(nx,ny)nx=cur_rect.x+dx;ny=cur_rect.y+dy;//跟踪目标处于图像边缘时进行一些对应的处理if(nx0){nx=0;}elseif(nx+cur_rect.widthmat-cols){nx=mat-cols-cur_rect.width;}if(ny0){ny=0;}elseif(ny+cur_rect.heightmat-rows){ny=mat-rows-cur_rect.height;}dx=nx-cur_rect.x;dy=ny-cur_rect.y;cur_rect.x=nx;cur_rect.y=ny;/*Checkforcoveragecentersmass&window*///精度达到要求时就可以退出循环if(dx*dx+dy*dyeps){break;}}__END__;if(comp){comp-rect=cur_rect;comp-area=(float)moments.m00;//图像面积}returni;}voidon_mouse(intevent,intx,inty,intflags,void*param)//鼠标回调函数,该函数用鼠标进行跟踪目标的选择{if(!image)return;if(image-origin)y=image-height-y;//如果图像原点坐标在左下,则将其改为左上if(select_object)//select_object为,表示在用鼠标进行目标选择//此时对矩形类selection用当前的鼠标位置进行设置{selection.x=MIN(x,origin.x);selection.y=MIN(y,o