1--Back Projection
CamShift算法，即"Continuously Apative Mean-Shift"算法，是一种运动跟踪算法。它主要通过视频图像中运动物体的颜色信息来达到跟踪的目的。我把这个算法分解成三个部分，便于理解：
1) Back Projection计算
2) Mean Shift算法
3) CamShift算法
在这里主要讨论Back Projection,在随后的文章中继续讨论后面两个算法。
Back Projection
计算Back Projection的步骤是这样的：
1. 计算被跟踪目标的色彩直方图。在各种色彩空间中，只有HSI空间(或与HSI类似的色彩空间)中的H分量可以表示颜色信息。所以在具体的计算过程中，首先将其他的色彩空间的值转化到HSI空间，然后会其中的H分量做1D直方图计算。
2. 根据获得的色彩直方图将原始图像转化成色彩概率分布图像，这个过程就被称作"Back Projection"。
在OpenCV中的直方图函数中，包含Back Projection的函数，函数原型是：
void cvCalcBackProject(IplImage** img, CvArr** backproject, const CvHistogram* hist);
传递给这个函数的参数有三个：
1. IplImage** img:存放原始图像，输入。
2. CvArr** backproject:存放Back Projection结果，输出。
3. CvHistogram* hist:存放直方图，输入
下面就给出计算Back Projection的OpenCV代码。
1.准备一张只包含被跟踪目标的图片，将色彩空间转化到HSI空间，获得其中的H分量：
IplImage* target=cvLoadImage("target.bmp",-1); //装载图片
IplImage* target_hsv=cvCreateImage( cvGetSize(target), IPL_DEPTH_8U, 3 );
IplImage* target_hue=cvCreateImage( cvGetSize(target), IPL_DEPTH_8U, 3 );
cvCvtColor(target,target_hsv,CV_BGR2HSV); //转化到HSV空间
cvSplit( target_hsv, target_hue, NULL, NULL, NULL ); //获得H分量
2.计算H分量的直方图，即1D直方图：
IplImage* h_plane=cvCreateImage( cvGetSize(target_hsv),IPL_DEPTH_8U,1 );
int hist_size[]={255}; //将H分量的值量化到[0,255]
float* ranges[]={ {0,360} }; //H分量的取值范围是[0,360)
CvHistogram* hist=cvCreateHist(1, hist_size, ranges, 1);
cvCalcHist(&target_hue, hist, 0, NULL);
在这里需要考虑H分量的取值范围的问题，H分量的取值范围是[0,360),这个取值范围的值不能用一个byte来表示，为了能用一个byte表示，需要将H值做适当的量化处理,在这里我们将H分量的范围量化到[0,255].
4.计算Back Projection：
IplImage* rawImage;
//----------------------------------------------
//get from video frame,unsigned byte,one channel
//----------------------------------------------
IplImage* result=cvCreateImage(cvGetSize(rawImage),IPL_DEPTH_8U,1);
cvCalcBackProject(&rawImage,result,hist);
5.结果：result即为我们需要的.
2--Mean Shift算法
这里来到了CamShift算法，OpenCV实现的第二部分，这一次重点讨论Mean Shift算法。
在讨论Mean Shift算法之前，首先讨论在2D概率分布图像中，如何计算某个区域的重心(Mass Center)的问题，重心可以通过以下公式来计算：
1.计算区域内0阶矩
for(int i=0;i< height;i++)
for(int j=0;j< width;j++)
M00+=I(i,j)
2.区域内1阶矩：
for(int i=0;i< height;i++)
for(int j=0;j< width;j++)
{
M10+=i*I(i,j);
M01+=j*I(i,j);
}
3.则Mass Center为：
Xc=M10/M00; Yc=M01/M00
接下来，讨论Mean Shift算法的具体步骤，Mean Shift算法可以分为以下4步：
1.选择窗的大小和初始位置.
2.计算此时窗口内的Mass Center.
3.调整窗口的中心到Mass Center.
4.重复2和3，直到窗口中心"会聚"，即每次窗口移动的距离小于一定的阈值。
在OpenCV中，提供Mean Shift算法的函数，函数的原型是：
int cvMeanShift(IplImage* imgprob,CvRect windowIn,
CvTermCriteria criteria,CvConnectedComp* out);
需要的参数为：
1.IplImage* imgprob：2D概率分布图像，传入；
2.CvRect windowIn：初始的窗口，传入；
3.CvTermCriteria criteria：停止迭代的标准，传入；
4.CvConnectedComp* out:查询结果，传出。
(注：构造CvTermCriteria变量需要三个参数，一个是类型，另一个是迭代的最大次数，最后一个表示特定的阈值。例如可以这样构造 criteria：criteria=cvTermCriteria(CV_TERMCRIT_ITER|CV_TERMCRIT_EPS,10,0.1)。)
返回的参数：
1.int：迭代的次数。
3--CamShift算法
1.原理
在了解了MeanShift算法以后，我们将MeanShift算法扩展到连续图像序列（一般都是指视频图像序列），这样就形成了CamShift算法。CamShift算法的全称是"Continuously Apaptive Mean-SHIFT"，它的基本思想是视频图像的所有帧作MeanShift运算，并将上一帧的结果（即Search Window的中心和大小）作为下一帧MeanShift算法的Search Window的初始值，如此迭代下去，就可以实现对目标的跟踪。整个算法的具体步骤分5步：
Step 1：将整个图像设为搜寻区域。
Step 2：初始话Search Window的大小和位置。
Step 3：计算Search Window内的彩色概率分布，此区域的大小比Search Window要稍微大一点。
Step 4：运行MeanShift。获得Search Window新的位置和大小。
Step 5：在下一帧视频图像中，用Step 3获得的值初始化Search Window的位置和大小。跳转到Step 3继续运行。
2.实现
在OpenCV中，有实现CamShift算法的函数，此函数的原型是：
cvCamShift(IplImage* imgprob, CvRect windowIn,
CvTermCriteria criteria,
CvConnectedComp* out, CvBox2D* box=0);
其中：
imgprob：色彩概率分布图像。
windowIn：Search Window的初始值。
Criteria：用来判断搜寻是否停止的一个标准。
out：保存运算结果,包括新的Search Window的位置和面积。
box：包含被跟踪物体的最小矩形。
说明：
1.在OpenCV 4.0 beta的目录中，有CamShift的例子。遗憾的是这个例子目标的跟踪是半自动的，即需要人手工选定一个目标。我正在努力尝试全自动的目标跟踪，希望可以和大家能在这方面与大家交流。
5.
运动目标跟踪与检测的源代码（CAMSHIFT 算法）
From http://blog.csdn.net/hunnish/archive/2004/09/07/97049.aspx
采用 CAMSHIFT 算法快速跟踪和检测运动目标的 C/C++ 源代码，OPENCV BETA 4.0 版本在其 SAMPLE 中给出了这个例子。算法的简单描述如下（英文）：
This application demonstrates a fast, simple color tracking algorithm that can be used to track faces, hands . The CAMSHIFT algorithm is a modification of the Meanshift algorithm which is a robust statistical method of finding the mode (top) of a probability distribution. Both CAMSHIFT and Meanshift algorithms exist in the library. While it is a very fast and simple method of tracking, because CAMSHIFT tracks the center and size of the probability distribution of an object, it is only as good as the probability distribution that you produce for the object. Typically the probability distribution is derived from color via a histogram, although it could be produced from correlation, recognition scores or bolstered by frame differencing or motion detection schemes, or joint probabilities of different colors/motions etc.
In this application, we use only the most simplistic approach: A 1-D Hue histogram is sampled from the object in an HSV color space version of the image. To produce the probability image to track, histogram "back projection" (we replace image pixels by their histogram hue value) is used.
算法的详细情况，请看论文：
http://www.assuredigit.com/incoming/camshift.pdf
关于OPENCV B4.0 库的使用方法以及相关问题，请查阅下面的相关文章：
http://forum.assuredigit.com/display_topic_threads.asp?ForumID=11&TopicID=3471
运行文件下载：
http://www.assuredigit.com/product_tech/Demo_Download_files/camshiftdemo.exe
该运行文件在VC6.0环境下编译通过，是一个 stand-alone 运行程序，不需要OPENCV的DLL库支持。在运行之前，请先连接好USB接口的摄像头。然后可以用鼠标选定欲跟踪目标。
＝＝＝＝＝
#ifdef _CH_
#pragma package
#endif
#ifndef _EiC
#include "cv.h"
#include "highgui.h"
#include
#include
#endif
IplImage *image = 0, *hsv = 0, *hue = 0, *mask = 0, *backproject = 0, *histimg = 0;
CvHistogram *hist = 0;
int backproject_mode = 0;
int select_object = 0;
int track_object = 0;
int show_hist = 1;
CvPoint origin;
CvRect selection;
CvRect track_window;
CvBox2D track_box; // tracking 返回的区域 box，带角度
CvConnectedComp track_comp;
int hdims = 48; // 划分HIST的个数，越高越精确
float hranges_arr[] = {0,180};
float* hranges = hranges_arr;
int vmin = 10, vmax = 256, smin = 30;
void on_mouse( int event, int x, int y, int flags )
{
if( !image )
return;
if( image->origin )
y = image->height - y;
if( select_object )
{
selection.x = MIN(x,origin.x);
selection.y = MIN(y,origin.y);
selection.width = selection.x + CV_IABS(x - origin.x);
selection.height = selection.y + CV_IABS(y - origin.y);
selection.x = MAX( selection.x, 0 );
selection.y = MAX( selection.y, 0 );
selection.width = MIN( selection.width, image->width );
selection.height = MIN( selection.height, image->height );
selection.width -= selection.x;
selection.height -= selection.y;
}
switch( event )
{
case CV_EVENT_LBUTTONDOWN:
origin = cvPoint(x,y);
selection = cvRect(x,y,0,0);
select_object = 1;
break;
case CV_EVENT_LBUTTONUP:
select_object = 0;
if( selection.width > 0 && selection.height > 0 )
track_object = -1;
#ifdef _DEBUG
printf("\n # 鼠标的选择区域：");
printf("\n X = %d, Y = %d, Width = %d, Height = %d",
selection.x, selection.y, selection.width, selection.height);
#endif
break;
}
}
CvScalar hsv2rgb( float hue )
{
int rgb[3], p, sector;
static const int sector_data[][3]=
{{0,2,1}, {1,2,0}, {1,0,2}, {2,0,1}, {2,1,0}, {0,1,2}};
hue *= 0.033333333333333333333333333333333f;
sector = cvFloor(hue);
p = cvRound(255*(hue - sector));
p ^= sector & 1 ? 255 : 0;
rgb[sector_data[sector][0]] = 255;
rgb[sector_data[sector][1]] = 0;
rgb[sector_data[sector][2]] = p;
#ifdef _DEBUG
printf("\n # Convert HSV to RGB：");
printf("\n HUE = %f", hue);
printf("\n R = %d, G = %d, B = %d", rgb[0],rgb[1],rgb[2]);
#endif
return cvScalar(rgb[2], rgb[1], rgb[0],0);
}
int main( int argc, char** argv )
{
CvCapture* capture = 0;
IplImage* frame = 0;
if( argc == 1 || (argc == 2 && strlen(argv[1]) == 1 && isdigit(argv[1][0])))
capture = cvCaptureFromCAM( argc == 2 ? argv[1][0] - '0' : 0 );
else if( argc == 2 )
capture = cvCaptureFromAVI( argv[1] );
if( !capture )
{
fprintf(stderr,"Could not initialize capturing...\n");
return -1;
}
printf( "Hot keys: \n"
"\tESC - quit the program\n"
"\tc - stop the tracking\n"
"\tb - switch to/from backprojection view\n"
"\th - show/hide object histogram\n"
"To initialize tracking, select the object with mouse\n" );
//cvNamedWindow( "Histogram", 1 );
cvNamedWindow( "CamShiftDemo", 1 );
cvSetMouseCallback( "CamShiftDemo", on_mouse ); // on_mouse 自定义事件
cvCreateTrackbar( "Vmin", "CamShiftDemo", &vmin, 256, 0 );
cvCreateTrackbar( "Vmax", "CamShiftDemo", &vmax, 256, 0 );
cvCreateTrackbar( "Smin", "CamShiftDemo", &smin, 256, 0 );
for(;;)
{
int i, bin_w, c;
frame = cvQueryFrame( capture );
if( !frame )
break;
if( !image )
{
/* allocate all the buffers */
image = cvCreateImage( cvGetSize(frame), 8, 3 );
image->origin = frame->origin;
hsv = cvCreateImage( cvGetSize(frame), 8, 3 );
hue = cvCreateImage( cvGetSize(frame), 8, 1 );
mask = cvCreateImage( cvGetSize(frame), 8, 1 );
backproject = cvCreateImage( cvGetSize(frame), 8, 1 );
hist = cvCreateHist( 1, &hdims, CV_HIST_ARRAY, &hranges, 1 ); // 计算直方图
histimg = cvCreateImage( cvSize(320,200), 8, 3 );
cvZero( histimg );
}
cvCopy( frame, image, 0 );
cvCvtColor( image, hsv, CV_BGR2HSV ); // 彩色空间转换 BGR to HSV
if( track_object )
{
int _vmin = vmin, _vmax = vmax;
cvInRangeS( hsv, cvScalar(0,smin,MIN(_vmin,_vmax),0),
cvScalar(180,256,MAX(_vmin,_vmax),0), mask ); // 得到二值的MASK
cvSplit( hsv, hue, 0, 0, 0 ); // 只提取 HUE 分量
if( track_object < 0 )
{
float max_val = 0.f;
cvSetImageROI( hue, selection ); // 得到选择区域 for ROI
cvSetImageROI( mask, selection ); // 得到选择区域 for mask
cvCalcHist( &hue, hist, 0, mask ); // 计算直方图
cvGetMinMaxHistValue( hist, 0, &max_val, 0, 0 ); // 只找最大值
cvConvertScale( hist->bins, hist->bins, max_val ? 255. / max_val : 0., 0 ); // 缩放 bin 到区间 [0,255]
cvResetImageROI( hue ); // remove ROI
cvResetImageROI( mask );
track_window = selection;
track_object = 1;
cvZero( histimg );
bin_w = histimg->width / hdims; // hdims: 条的个数，则 bin_w 为条的宽度
// 画直方图
for( i = 0; i < hdims; i++ )
{
int val = cvRound( cvGetReal1D(hist->bins,i)*histimg->height/255 );
CvScalar color = hsv2rgb(i*180.f/hdims);
cvRectangle( histimg, cvPoint(i*bin_w,histimg->height),
cvPoint((i+1)*bin_w,histimg->height - val),
color, -1, 8, 0 );
}
}
cvCalcBackProject( &hue, backproject, hist ); // 使用 back project 方法
cvAnd( backproject, mask, backproject, 0 );
// calling CAMSHIFT 算法模块
cvCamShift( backproject, track_window,
cvTermCriteria( CV_TERMCRIT_EPS | CV_TERMCRIT_ITER, 10, 1 ),
&track_comp, &track_box );
track_window = track_comp.rect;
if( backproject_mode )
cvCvtColor( backproject, image, CV_GRAY2BGR ); // 使用backproject灰度图像
if( image->origin )
track_box.angle = -track_box.angle;
cvEllipseBox( image, track_box, CV_RGB(255,0,0), 3, CV_AA, 0 );
}
if( select_object && selection.width > 0 && selection.height > 0 )
{
cvSetImageROI( image, selection );
cvXorS( image, cvScalarAll(255), image, 0 );
cvResetImageROI( image );
}
cvShowImage( "CamShiftDemo", image );
cvShowImage( "Histogram", histimg );
c = cvWaitKey(10);
if( c == 27 )
break; // exit from for-loop
switch( c )
{
case 'b':
backproject_mode ^= 1;
break;
case 'c':
track_object = 0;
cvZero( histimg );
break;
case 'h':
show_hist ^= 1;
if( !show_hist )
cvDestroyWindow( "Histogram" );
else
cvNamedWindow( "Histogram", 1 );
break;
default:
;
}
}
cvReleaseCapture( &capture );
cvDestroyWindow("CamShiftDemo");
return 0;
}
#ifdef _EiC
main(1,"camshiftdemo.c");
#endif
，
，则： 1、当F(M)<0时，m在圆内(圆弧a)，这说明点e距离圆更近，应取点e作为下一象素点；
，这时新的决策变量为：
，这时新的决策变量为：
，所以：
（1）
（3）
