基于meanshift算法的图像处理

MeanShift，我们翻译为“均值飘移”。其在聚类，图像平滑。图像分割和跟踪方面得到了比较广泛的应用。由于本人目前研究跟踪方面的东西，故此主要介绍利用MeanShift方法进行目标跟踪，从而对MeanShift有一个比较全面的介绍。（以下某些部分转载常峰学长的“MeanShift概述”）MeanShift这个概念最早是由Fukunaga等人于1975年在一篇关于概率密度梯度函数的估计（TheEstimationoftheGradientofaDensityFunction,withApplicationsinPatternRecognition）中提出来的,其最初含义正如其名,就是偏移的均值向量,在这里MeanShift是一个名词,它指代的是一个向量,但随着MeanShift理论的发展,MeanShift的含义也发生了变化,如果我们说MeanShift算法,一般是指一个迭代的步骤,即先算出当前点的偏移均值,移动该点到其偏移均值,然后以此为新的起始点,继续移动,直到满足一定的条件结束.然而在以后的很长一段时间内MeanShift并没有引起人们的注意,直到20年以后,也就是1995年,另外一篇关于MeanShift的重要文献（Meanshift,modeseeking,andclustering）才发表.在这篇重要的文献中,YizongCheng对基本的MeanShift算法在以下两个方面做了推广,首先YizongCheng定义了一族核函数,使得随着样本与被偏移点的距离不同,其偏移量对均值偏移向量的贡献也不同,其次YizongCheng还设定了一个权重系数,使得不同的样本点重要性不一样,这大大扩大了MeanShift的适用范围.另外YizongCheng指出了MeanShift可能应用的领域,并给出了具体的例子。Comaniciu等人在还（Mean-shiftBlobTrackingthroughScaleSpace）中把非刚体的跟踪问题近似为一个MeanShift最优化问题,使得跟踪可以实时的进行。目前，利用MeanShift进行跟踪已经相当成熟。目标跟踪不是一个新的问题，目前在计算机视觉领域内有不少人在研究。所谓跟踪，就是通过已知的图像帧中的目标位置找到目标在下一帧中的位置。下面主要以代码形式展现MeanShift在跟踪中的应用。voidCObjectTracker::ObjeckTrackerHandlerByUser(IplImage*frame)//跟踪函数{m_cActiveObject=0;if(m_sTrackingObjectTable[m_cActiveObject].Status){if(!m_sTrackingObjectTable[m_cActiveObject].assignedAnObject){FindHistogram(frame,m_sTrackingObjectTable[m_cActiveObject].initHistogram);m_sTrackingObjectTable[m_cActiveObject].assignedAnObject=true;}else{FindNextLocation(frame);//利用meanshift迭代找出目标下一个位置点DrawObjectBox(frame);}}}voidCObjectTracker::FindNextLocation(IplImage*frame){inti,j,opti,optj;SINT16scale[3]={-3,3,0};FLOAT32dist,optdist;SINT16h,w,optX,optY;//tryno-scalingFindNextFixScale(frame);//找出目标的下一个大致范围optdist=LastDist;optX=m_sTrackingObjectTable[m_cActiveObject].X;optY=m_sTrackingObjectTable[m_cActiveObject].Y;//tryoneofthe9possiblescalingi=rand()*2/RAND_MAX;j=rand()*2/RAND_MAX;h=m_sTrackingObjectTable[m_cActiveObject].H;w=m_sTrackingObjectTable[m_cActiveObject].W;if(h+scale[i]10&&w+scale[j]10&&h+scale[i]m_nImageHeight/2&&w+scale[j]m_nImageWidth/2){m_sTrackingObjectTable[m_cActiveObject].H=h+scale[i];m_sTrackingObjectTable[m_cActiveObject].W=w+scale[j];FindNextFixScale(frame);if((dist=LastDist)optdist)//scalingisbetter{optdist=dist;//printf(Next%f-\n,dist);}else//noscalingisbetter{m_sTrackingObjectTable[m_cActiveObject].X=optX;m_sTrackingObjectTable[m_cActiveObject].Y=optY;m_sTrackingObjectTable[m_cActiveObject].H=h;m_sTrackingObjectTable[m_cActiveObject].W=w;}};TotalDist+=optdist;//thelatestdistance//printf(\n);}这里仍然在跟踪的基础上讲解meanshift。首先还是把meanshift的原理用数学公式说一下吧。1、目标模型，算法采用的是特征值的加权概率分布来描述目标模型。这应该是模式识别中主要描述目标的模型，不同于自动控制理论中采用的状态方程。目标模型共m个特征值（可以理解为像素灰度值）其中X0是窗口中心点向量值（可能为RBG向量或者灰度值），Xi是窗口内第i点向量值。C为归一化常数，保障q1+q2+q3+……qm=1，H为核函数的带宽向量。M为特征值的个数，对应于图像处理可以理解为灰度等级划分的个数，从而特征值u为对应的灰度等级。d函数为脉冲函数，保证只有具有u特征值的像素才对概率分布作出贡献。从而k函数可以理解为u灰度值的一个加权频数。2、匹配对象，也采用特征值加权概率分布其中，Y为匹配对象的中心，Xi是匹配窗口内第i点向量值，Hh为匹配窗口的核函数带宽向量。Ch为匹配窗口特征向量的归一化常数。3、匹配对象与目标模型的相似程度，相似函数可采用Bhattacharyya函数4、匹配过程就是寻找相似函数最大值的寻优过程，Mean-Shift采用的是梯度下降法。首先将(Y)在（Y0）附近进行泰勒级数展开，取前两项。即：要使得(Y)向最大值迭代，只要Y的搜索方向与梯度方向一致即可，通过求导可得到Y0的梯度方向为：为权值。因此如果如下确定Y1，那么Y1-Y0将与梯度方向一致。以上为meanshift的数学原理。有关文字的叙述已经在上一篇中提到了。用meanshift来跟踪属于确定性算法，粒子滤波器属于统计学方法。meanshift跟踪算法相对于粒子滤波器来说可能实时性更好一些，但是跟踪的准确性在理论上还是略逊于粒子滤波器的。meanshift跟踪的的实质就是通过对应的模板来确定目标的下一个位置。通过迭代找到新的中心点（即是目标的新的位置点）。有关跟踪的code如下所示：/**********************************************************************BilkentUniversity:Mean-shiftTrackerbasedMovingObjectTrackerinVideoVersion:1.0Compiler:MicrosoftVisualC++6.0(testedinbothdebugandreleasemode)ModifiedbyMrZhou**********************************************************************/#includeObjectTracker.h#includeutils.h#includemath.h#includestdio.h#includestdlib.h/*#defineGetRValue(rgb)((UBYTE8)(rgb))#defineGetGValue(rgb)((UBYTE8)(((ULONG_32)(rgb))8))#defineGetBValue(rgb)((UBYTE8)((rgb)16))*///#defineRGB(r,g,b)((ULONG_32)(((UBYTE8)(r)|((UBYTE8)(g)8))|(((ULONG_32)(UBYTE8)(b))16)))#definemin(a,b)(((a)(b))?(a):(b))#definemax(a,b)(((a)(b))?(a):(b))#defineMEANSHIFT_ITARATION_NO5#defineDISTANCE_ITARATION_NO1#defineALPHA1#defineEDGE_DETECT_TRESHOLD32///////////////////////////////////////////////////*1给定目标的初始位置和尺寸,计算目标在图像中的直方图;2输入新图像,迭代直到收敛:计算图像上对应区域的新直方图;新直方图与目标直方图比较,计算权重;根据权重,计算图像上对应区域的形心/质心;根据形心,修正目标位置;直方图分为两部分,每部分大小4096,RGB的256*256*256种组合,缩减为16*16*16=4096种组合.如果目标区域的点是边缘点,则计入直方图的后一部分,否则计入直方图的前一部分.*///////////////////////////////////////////////////CObjectTracker::CObjectTracker(INT32imW,INT32imH,IMAGE_TYPEeImageType){m_nImageWidth=imW;m_nImageHeight=imH;m_eIMAGE_TYPE=eImageType;m_cSkipValue=0;for(UBYTE8i=0;iMAX_OBJECT_TRACK_NUMBER;i++)//初始化各个目标{m_sTrackingObjectTable[i].Status=false;for(SINT16j=0;jHISTOGRAM_LENGTH;j++)m_sTrackingObjectTable[i].initHistogram[j]=0;}m_nFrameCtr=0;m_uTotalTime=0;m_nMaxEstimationTime=0;m_cActiveObject=0;TotalDist=0.0;LastDist=0.0;switch(eImageType){caseMD_RGBA:m_cSkipValue=4;break;caseMD_RGB:m_cSkipValue=3;break;};};CObjectTracker::~CObjectTracker(){}//returnspixelvaluesinformat|0|B|G|R|wrtto(x.y)/*ULONG_32CObjectTracker::GetPixelValues(UBYTE8*frame,SINT16x,SINT16y){ULONG_32pixelValues=0;pixelValues=*(