1 均值漂移算法简介

  均值漂移算法是一种基于密度梯度上升的非参数方法，通过迭代运算找到目标位置，实现目标跟踪。所谓跟踪，就是通过已知的图像帧中的目标位置找到目标在下一帧中的位置。均值漂移算法显著的优点是算法计算量小，简单易实现,很适合于实时跟踪场合；但是跟踪小目标和快速移动目标时常常失败，而且在全部遮挡情况下不能自我恢复跟踪。通过实验提出应用核直方图来计算目标分布，证明了均值漂移算法具有很好的实时性特点。均值漂移在聚类、图像平滑、分割、跟踪等方面有着广泛的应用。

2 均值漂移算法中的非参数估计方法

  非参数估计和参数估计（即，监督参数估计和非监督参数估计）共同构成了概率密度估计方法。非参数估计也有人将其称之为无参密度估计，它是一种对先验知识要求最少，完全依靠训练数据进行估计，而且可以用于任意形状密度估计的方法。常见的非参数估计方法有以下几种：
  A.直方图：把数据的值域分为若干相等的区间，数据按照区间分为若干组，每组形成一个矩形，矩形的高和该组数据的多少成正比，其底为所属区间，将这些矩形依次排列组成的图形就是直方图。它提供给数据一个直观的形象，但只适合低维数据的情况，当维数较高时，直方图所需的空间将随着维数的增加呈指数级增加。
  B.核密度估计(Kernel Density Estimates，简称KDE)：就是采用平滑的峰值函数(“核”)来拟合观察到的数据点，从而对真实的概率分布曲线进行模拟。原理和直方图有些类似，是一种平滑的无参密度估计方法。对于一组采样数据，把数据的值域分为若干相等的区间，每个区间称为一个bin，数据就按区间分为若干组，每组数据的个数和总参数个数的比率就是每个bin的概率值。相对于直方图法，它多了一个用于平滑数据的核函数。核密度估计方法适用于中小规模的数据集，可以很快地产生一个渐近无偏的密度估计，有良好的概率统计性质。具体来说，如果数据为x1,x2,…,xn，在任意点x的一种核密度估计为：

  绘制成直方图是这样的：

  而使用KDE则是：

  其中 K(*)称为核函数,满足对称性及 ，h称为带宽，一般，h越大，估计的密度函数就越光滑，但偏差可能较大，如果h选的较小，那么估计的密度曲线和样本拟合的较好，但可能很不光滑，选择的原则是使得均方误差最小为宜(交叉验证法，直接插入法)。该估计利用数据点xi到x的距离来决定xi在估计点x的 密度时所起的作用，距离x越近的样本点所起的作用就越大，其权值也就越大。常用的核函数有：矩形、Epanechnikov曲线、高斯曲线等。
  C.局部多项式密度估计：目前最流行，效果很好的密度估计 方法。对每一个点x拟合一个局部多项式来估计该点的密度。
  D.K近邻估计：核密度估计的加权是以数据点到x的欧式距离为基准来进行的，而K近邻估计是无论欧氏距离多少，只要是x点的最近的k个点的其中之一就可参与加权。一种具体的k近邻密度估计：

  令d1<=…<=dn表示按升幂排列的x到所有n个样本点的欧氏距离。K的取值决定了估计密度曲线的光滑程度，k越大越光滑。与核估计结合起来定义广义的k近邻估计:

E.多元密度估计：上述的几种估计方法都是一元密度估计方法。假定x为d维向量,则多元密度估计可以为 ：

其中，。

3 OpenCV中的均值漂移算法

  均值漂移算法以迭代的方式锁定概率函数的局部最大值。比如有一个矩形窗口将一幅图像的某个部分框住，原理就是寻找预定义窗口中数据点的重心，或者说加权平均值。该算法将窗口中心移动到数据点的重心处,并重复这个过程直到窗口重心收敛到一个稳定点。在OpenCV中，该算法的运行有两种终止条件：达到最大迭代次数终止MAX_ITER和迭代到阈值终止EPS。

    //终止条件：第二个参数为迭代的最大次数，最后一个参数是特定的阈值
    TermCriteria criteria(TermCriteria::MAX_ITER,10,0.01);
    //result为HSV中H通道对原图的直方图反投影图像，rect为预定义窗口
    meanShift(result,rect,criteria);

  因此，迭代完成的结果的好与坏取决于输入的概率图(上述中的预定义窗口)和它的初始位置。
  整个跟踪步骤：

• 设置初始跟踪目标，即框住待跟踪目标
• 获取待跟踪目标的HSV中的色度H通道图像的直方图
• 待跟踪直方图归一化
• 到新的数据帧图像中反投影待跟踪直方图
• 均值漂移，更新跟踪位置

  在这之前，我们还需要了解怎么通过反投影直方图以检测特定的图像内容：
  OpenCV【5】—通过反投影直方图以检测特定的图像内容

4 测试程序

#include <iostream>
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <opencv2/video/video.hpp>
#include "colorhistogram.h"
#include "contentfinder.h"

using namespace cv;
using namespace std;

bool pause = false;
bool is_tracking = false;
Rect drawing_box;
Mat current;
MatND colorhist;
ContentFinder finder;


void meanShiftTracking(Mat current)
{
    //设置跟踪直方图
    finder.setHistogram(colorhist);
    //转换到HSV空间
    Mat hsv;
    vector<Mat> v;
    cvtColor(current,hsv,CV_BGR2HSV);
    //分割图像
    split(hsv,v);
    //识别低饱和度(S)的像素
    int minSat = 65;
    threshold(v[1],v[1],minSat,255,THRESH_BINARY);
    //获取直方图的反投影
    Mat result;
    int ch[1]={0};
    result = finder.find(hsv,0.0f,180.0f,ch,1);
    //去除低饱和度的像素
    //result（根据H色度反投影的图像）和v[1]是一样大小,此时的result受饱和度S影响较大
    bitwise_and(result,v[1],result);
    //使用meanShift算法更新矩形位置
    //迭代算法的终止条件：达到最大迭代次数终止MAX_ITER，迭代到阈值终止EPS
    //第二个参数为迭代的最大次数，最后一个参数是特定的阈值
    TermCriteria criteria(TermCriteria::MAX_ITER,10,0.01);
    //使用CamShift算法，改进版的均值漂移算法，搜索窗口的尺寸和朝向会发生改变
    CamShift(result,drawing_box,criteria);    
    meanShift(result,drawing_box,criteria);

    //更新矩形位置显示
    cv::rectangle(current, drawing_box, cv::Scalar(0,0,255),2);
    imshow("VideoCapture Mean Shift Track Object",current);
}

void onMouse( int event, int x, int y, int flags, void *param )
{
    if (pause)
    {
        Mat imageROI;
        ColorHistogram hc;
        int minSat = 65;
        switch(event)
        {
        case CV_EVENT_LBUTTONDOWN:            
            drawing_box.x = x;
            drawing_box.y = y;
            break;
        case CV_EVENT_LBUTTONUP:            
            drawing_box.width = x - drawing_box.x;
            drawing_box.height = y - drawing_box.y;
            imageROI = current(drawing_box).clone();
            //显示鼠标画的目标框
            rectangle(current,drawing_box,Scalar(0,0,255),2);
            imshow("VideoCapture Mean Shift Track Object",current);
            //获取色调通道的直方图
            //最小阈值：小于等于65为0，大于65为255
            colorhist = hc.getHueHistogram(imageROI,minSat);
            is_tracking = true;
            break;
        default:
            break;
        }
    }
}

int main(int, char**)
{
    //打开PC默认摄像头
    VideoCapture cap(0);
    if(!cap.isOpened())
        return -1;

    while(1){
        Mat frame;
        //从摄像头获取一帧图像
        cap >> frame;
        current = frame;
        if(is_tracking){
            meanShiftTracking(current);
        }

        uchar cmd = waitKey(1);
        //暂停
        if(cmd == 'p')
        {
            pause = true;
            // 第一个参数跟窗口的名字有关
            // 即回调函数需要注册到的窗口名字，即产生事件的窗口。
            setMouseCallback("VideoCapture Mean Shift Track Object",onMouse,0);
        }
        //退出
        else if(cmd == 'b'){
            break;
        }
        while(pause){
            if(waitKey(0) == 'p')
                pause = false;
        }
        imshow("VideoCapture Mean Shift Track Object",current);        
    }
    //camera 将会随着程序的结束在析构函数中自动释放内存
    return 0;
}

效果截图：

使用改进版的均值漂移算法CamShift效果：

  meanShift算法用于视频目标跟踪时，采用目标的颜色直方图作为搜索特征，通过不断迭代meanShift向量使得算法收敛于目标的真实位置，从而达到跟踪的目的。传统的meanShift算法在跟踪中有几个优势：
（1）算法计算量不大，在目标区域已知的情况下完全可以做到实时跟踪；
（2）采用核函数直方图模型，对边缘遮挡、目标旋转、变形和背景运动不敏感。
同时，meanShift算法也存在着以下一些缺点：
（1）缺乏必要的模板更新；
（2）跟踪过程中由于窗口宽度大小保持不变，当目标尺度有所变化时，跟踪就会失败；
（3）当目标速度较快时，跟踪效果不好；
（4）直方图特征在目标颜色特征描述方面略显匮乏，缺少空间信息；
由于其计算速度快，对目标变形和遮挡有一定的鲁棒性，所以，在目标跟踪领域，meanShift算法目前依然受到大家的重视。但考虑到其缺点，在工程实际中也可以对其作出一些改进和调整；例如：
（1）引入一定的目标位置变化的预测机制，从而更进一步减少meanShift跟踪的搜索时间，降低计算量；
（2）可以采用一定的方式来增加用于目标匹配的“特征”；
（3）将传统meanShift算法中的核函数固定带宽改为动态变化的带宽；
（4）采用一定的方式对整体模板进行学习和更新；