基于MeanShift的目标跟踪算法及实现

这次将介绍基于MeanShift的目标跟踪算法，首先谈谈简介，然后给出算法实现流程，最后实现了一个单目标跟踪的MeanShift算法【matlab/c两个版本】

csdn贴公式比较烦，原谅我直接截图了…

一、简介

首先扯扯无参密度估计理论，无参密度估计也叫做非参数估计，属于数理统计的一个分支，和参数密度估计共同构成了概率密度估计方法。参数密度估计方法要求特征空间服从一个已知的概率密度函数，在实际的应用中这个条件很难达到。而无参数密度估计方法对先验知识要求最少，完全依靠训练数据进行估计，并且可以用于任意形状的密度估计。所以依靠无参密度估计方法，即不事先规定概率密度函数的结构形式，在某一连续点处的密度函数值可由该点邻域中的若干样本点估计得出。常用的无参密度估计方法有：直方图法、最近邻域法和核密度估计法。

MeanShift算法正是属于核密度估计法，它不需要任何先验知识而完全依靠特征空间中样本点的计算其密度函数值。对于一组采样数据，直方图法通常把数据的值域分成若干相等的区间，数据按区间分成若干组，每组数据的个数与总参数个数的比率就是每个单元的概率值；核密度估计法的原理相似于直方图法，只是多了一个用于平滑数据的核函数。采用核函数估计法，在采样充分的情况下，能够渐进地收敛于任意的密度函数，即可以对服从任何分布的数据进行密度估计。

然后谈谈MeanShift的基本思想及物理含义：

此外，从公式1中可以看到，只要是落入S_h的采样点，无论其离中心x的远近，对最终的M_h(x)计算的贡献是一样的。然而在现实跟踪过程中，当跟踪目标出现遮挡等影响时，由于外层的像素值容易受遮挡或背景的影响，所以目标模型中心附近的像素比靠外的像素更可靠。因此，对于所有采样点，每个样本点的重要性应该是不同的，离中心点越远，其权值应该越小。故引入核函数和权重系数来提高跟踪算法的鲁棒性并增加搜索跟踪能力。

接下来，谈谈核函数：

核函数也叫窗口函数，在核估计中起到平滑的作用。常用的核函数有：Uniform，Epannechnikov，Gaussian等。本文算法只用到了Epannechnikov，它数序定义如下：

二、基于MeanShift的目标跟踪算法

基于均值漂移的目标跟踪算法通过分别计算目标区域和候选区域内像素的特征值概率得到关于目标模型和候选模型的描述，然后利用相似函数度量初始帧目标模型和当前帧的候选模版的相似性，选择使相似函数最大的候选模型并得到关于目标模型的Meanshift向量，这个向量正是目标由初始位置向正确位置移动的向量。由于均值漂移算法的快速收敛性，通过不断迭代计算Meanshift向量，算法最终将收敛到目标的真实位置，达到跟踪的目的。

下面通过图示直观的说明MeanShift跟踪算法的基本原理。如下图所示：目标跟踪开始于数据点x_i⁰（空心圆点x_i⁰，x_i¹，…，x_i^N表示的是中心点，上标表示的是的迭代次数，周围的黑色圆点表示不断移动中的窗口样本点，虚线圆圈代表的是密度估计窗口的大小）。箭头表示样本点相对于核函数中心点的漂移向量，平均的漂移向量会指向样本点最密集的方向，也就是梯度方向。因为 Meanshift 算法是收敛的，因此在当前帧中通过反复迭代搜索特征空间中样本点最密集的区域，搜索点沿着样本点密度增加的方向“漂移”到局部密度极大点点x_i^N，也就是被认为的目标位置，从而达到跟踪的目的，MeanShift 跟踪过程结束。

运动目标的实现过程【具体算法】：

三、代码实现

说明：

1.       RGB颜色空间刨分，采用16*16*16的直方图

2.       目标模型和候选模型的概率密度计算公式参照上文

3.       opencv版本运行：按P停止，截取目标，再按P，进行单目标跟踪

4.       Matlab版本，将视频改为图片序列，第一帧停止，手工标定目标，双击目标区域，进行单目标跟踪。

matlab版本：

1. function [] = select()
2. close all;
3. clear all;
4. %%%%%%%%%%%%%%%%%%根据一幅目标全可见的图像圈定跟踪目标%%%%%%%%%%%%%%%%%%%%%%%
5. I=imread('result72.jpg');
6. figure(1);
7. imshow(I);
8. [temp,rect]=imcrop(I);
9. [a,b,c]=size(temp);         %a:row,b:col
10. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%计算目标图像的权值矩阵%%%%%%%%%%%%%%%%%%%%%%%
11. y(1)=a/2;
12. y(2)=b/2;
13. tic_x=rect(1)+rect(3)/2;
14. tic_y=rect(2)+rect(4)/2;
15. m_wei=zeros(a,b);%权值矩阵
16. h=y(1)^2+y(2)^2 ;%带宽
17. for i=1:a
18. for j=1:b
19. dist=(i-y(1))^2+(j-y(2))^2;
20. m_wei(i,j)=1-dist/h; %epanechnikov profile
21. end
22. end
23. C=1/sum(sum(m_wei));%归一化系数
24. %计算目标权值直方图qu
25. %hist1=C*wei_hist(temp,m_wei,a,b);%target model
26. hist1=zeros(1,4096);
27. for i=1:a
28. for j=1:b
29. %rgb颜色空间量化为16*16*16 bins
30. q_r=fix(double(temp(i,j,1))/16);  %fix为趋近0取整函数
31. q_g=fix(double(temp(i,j,2))/16);
32. q_b=fix(double(temp(i,j,3))/16);
33. q_temp=q_r*256+q_g*16+q_b;            %设置每个像素点红色、绿色、蓝色分量所占比重
34. hist1(q_temp+1)= hist1(q_temp+1)+m_wei(i,j);    %计算直方图统计中每个像素点占的权重
35. end
36. end
37. hist1=hist1*C;
38. rect(3)=ceil(rect(3));
39. rect(4)=ceil(rect(4));
40. %%%%%%%%%%%%%%%%%%%%%%%%%读取序列图像
41. myfile=dir('D:\matlab7\work\mean shift\image\*.jpg');
42. lengthfile=length(myfile);
43. for l=1:lengthfile
44. Im=imread(myfile(l).name);
45. num=0;
46. Y=[2,2];
47. %%%%%%%mean shift迭代
48. while((Y(1)^2+Y(2)^2>0.5)&num<20)   %迭代条件
49. num=num+1;
50. temp1=imcrop(Im,rect);
51. %计算侯选区域直方图
52. %hist2=C*wei_hist(temp1,m_wei,a,b);%target candidates pu
53. hist2=zeros(1,4096);
54. for i=1:a
55. for j=1:b
56. q_r=fix(double(temp1(i,j,1))/16);
57. q_g=fix(double(temp1(i,j,2))/16);
58. q_b=fix(double(temp1(i,j,3))/16);
59. q_temp1(i,j)=q_r*256+q_g*16+q_b;
60. hist2(q_temp1(i,j)+1)= hist2(q_temp1(i,j)+1)+m_wei(i,j);
61. end
62. end
63. hist2=hist2*C;
64. figure(2);
65. subplot(1,2,1);
66. plot(hist2);
67. hold on;
68. w=zeros(1,4096);
69. for i=1:4096
70. if(hist2(i)~=0) %不等于
71. w(i)=sqrt(hist1(i)/hist2(i));
72. else
73. w(i)=0;
74. end
75. end
76. %变量初始化
77. sum_w=0;
78. xw=[0,0];
79. for i=1:a;
80. for j=1:b
81. sum_w=sum_w+w(uint32(q_temp1(i,j))+1);
82. xw=xw+w(uint32(q_temp1(i,j))+1)*[i-y(1)-0.5,j-y(2)-0.5];
83. end
84. end
85. Y=xw/sum_w;
86. %中心点位置更新
87. rect(1)=rect(1)+Y(2);
88. rect(2)=rect(2)+Y(1);
89. end
90. %%%跟踪轨迹矩阵%%%
91. tic_x=[tic_x;rect(1)+rect(3)/2];
92. tic_y=[tic_y;rect(2)+rect(4)/2];
93. v1=rect(1);
94. v2=rect(2);
95. v3=rect(3);
96. v4=rect(4);
97. %%%显示跟踪结果%%%
98. subplot(1,2,2);
99. imshow(uint8(Im));
100. title('目标跟踪结果及其运动轨迹');
101. hold on;
102. plot([v1,v1+v3],[v2,v2],[v1,v1],[v2,v2+v4],[v1,v1+v3],[v2+v4,v2+v4],[v1+v3,v1+v3],[v2,v2+v4],'LineWidth',2,'Color','r');
103. plot(tic_x,tic_y,'LineWidth',2,'Color','b');
104. end

运行结果：

opencv版本：

1. #include "stdafx.h"
2. #include "cv.h"
3. #include "highgui.h"
4. #define  u_char unsigned char
5. #define  DIST 0.5
6. #define  NUM 20
7. //全局变量
8. bool pause = false;
9. bool is_tracking = false;
10. CvRect drawing_box;
11. IplImage *current;
12. double *hist1, *hist2;
13. double *m_wei;                                                                  //权值矩阵
14. double C = 0.0;                                                                //归一化系数
15. void init_target(double *hist1, double *m_wei, IplImage *current)
16. {
17. IplImage *pic_hist = 0;
18. int t_h, t_w, t_x, t_y;
19. double h, dist;
20. int i, j;
21. int q_r, q_g, q_b, q_temp;
22. t_h = drawing_box.height;
23. t_w = drawing_box.width;
24. t_x = drawing_box.x;
25. t_y = drawing_box.y;
26. h = pow(((double)t_w)/2,2) + pow(((double)t_h)/2,2);            //带宽
27. pic_hist = cvCreateImage(cvSize(300,200),IPL_DEPTH_8U,3);     //生成直方图图像
28. //初始化权值矩阵和目标直方图
29. for (i = 0;i < t_w*t_h;i++)
30. {
31. m_wei[i] = 0.0;
32. }
33. for (i=0;i<4096;i++)
34. {
35. hist1[i] = 0.0;
36. }
37. for (i = 0;i < t_h; i++)
38. {
39. for (j = 0;j < t_w; j++)
40. {
41. dist = pow(i - (double)t_h/2,2) + pow(j - (double)t_w/2,2);
42. m_wei[i * t_w + j] = 1 - dist / h;
43. //printf("%f\n",m_wei[i * t_w + j]);
44. C += m_wei[i * t_w + j] ;
45. }
46. }
47. //计算目标权值直方
48. for (i = t_y;i < t_y + t_h; i++)
49. {
50. for (j = t_x;j < t_x + t_w; j++)
51. {
52. //rgb颜色空间量化为16*16*16 bins
53. q_r = ((u_char)current->imageData[i * current->widthStep + j * 3 + 2]) / 16;
54. q_g = ((u_char)current->imageData[i * current->widthStep + j * 3 + 1]) / 16;
55. q_b = ((u_char)current->imageData[i * current->widthStep + j * 3 + 0]) / 16;
56. q_temp = q_r * 256 + q_g * 16 + q_b;
57. hist1[q_temp] =  hist1[q_temp] +  m_wei[(i - t_y) * t_w + (j - t_x)] ;
58. }
59. }
60. //归一化直方图
61. for (i=0;i<4096;i++)
62. {
63. hist1[i] = hist1[i] / C;
64. //printf("%f\n",hist1[i]);
65. }
66. //生成目标直方图
67. double temp_max=0.0;
68. for (i = 0;i < 4096;i++)         //求直方图最大值，为了归一化
69. {
70. //printf("%f\n",val_hist[i]);
71. if (temp_max < hist1[i])
72. {
73. temp_max = hist1[i];
74. }
75. }
76. //画直方图
77. CvPoint p1,p2;
78. double bin_width=(double)pic_hist->width/4096;
79. double bin_unith=(double)pic_hist->height/temp_max;
80. for (i = 0;i < 4096; i++)
81. {
82. p1.x = i * bin_width;
83. p1.y = pic_hist->height;
84. p2.x = (i + 1)*bin_width;
85. p2.y = pic_hist->height - hist1[i] * bin_unith;
86. //printf("%d,%d,%d,%d\n",p1.x,p1.y,p2.x,p2.y);
87. cvRectangle(pic_hist,p1,p2,cvScalar(0,255,0),-1,8,0);
88. }
89. cvSaveImage("hist1.jpg",pic_hist);
90. cvReleaseImage(&pic_hist);
91. }
92. void MeanShift_Tracking(IplImage *current)
93. {
94. int num = 0, i = 0, j = 0;
95. int t_w = 0, t_h = 0, t_x = 0, t_y = 0;
96. double *w = 0, *hist2 = 0;
97. double sum_w = 0, x1 = 0, x2 = 0,y1 = 2.0, y2 = 2.0;
98. int q_r, q_g, q_b;
99. int *q_temp;
100. IplImage *pic_hist = 0;
101. t_w = drawing_box.width;
102. t_h = drawing_box.height;
103. pic_hist = cvCreateImage(cvSize(300,200),IPL_DEPTH_8U,3);     //生成直方图图像
104. hist2 = (double *)malloc(sizeof(double)*4096);
105. w = (double *)malloc(sizeof(double)*4096);
106. q_temp = (int *)malloc(sizeof(int)*t_w*t_h);
107. while ((pow(y2,2) + pow(y1,2) > 0.5)&& (num < NUM))
108. {
109. num++;
110. t_x = drawing_box.x;
111. t_y = drawing_box.y;
112. memset(q_temp,0,sizeof(int)*t_w*t_h);
113. for (i = 0;i<4096;i++)
114. {
115. w[i] = 0.0;
116. hist2[i] = 0.0;
117. }
118. for (i = t_y;i < t_h + t_y;i++)
119. {
120. for (j = t_x;j < t_w + t_x;j++)
121. {
122. //rgb颜色空间量化为16*16*16 bins
123. q_r = ((u_char)current->imageData[i * current->widthStep + j * 3 + 2]) / 16;
124. q_g = ((u_char)current->imageData[i * current->widthStep + j * 3 + 1]) / 16;
125. q_b = ((u_char)current->imageData[i * current->widthStep + j * 3 + 0]) / 16;
126. q_temp[(i - t_y) *t_w + j - t_x] = q_r * 256 + q_g * 16 + q_b;
127. hist2[q_temp[(i - t_y) *t_w + j - t_x]] =  hist2[q_temp[(i - t_y) *t_w + j - t_x]] +  m_wei[(i - t_y) * t_w + j - t_x] ;
128. }
129. }
130. //归一化直方图
131. for (i=0;i<4096;i++)
132. {
133. hist2[i] = hist2[i] / C;
134. //printf("%f\n",hist2[i]);
135. }
136. //生成目标直方图
137. double temp_max=0.0;
138. for (i=0;i<4096;i++)         //求直方图最大值，为了归一化
139. {
140. if (temp_max < hist2[i])
141. {
142. temp_max = hist2[i];
143. }
144. }
145. //画直方图
146. CvPoint p1,p2;
147. double bin_width=(double)pic_hist->width/(4368);
148. double bin_unith=(double)pic_hist->height/temp_max;
149. for (i = 0;i < 4096; i++)
150. {
151. p1.x = i * bin_width;
152. p1.y = pic_hist->height;
153. p2.x = (i + 1)*bin_width;
154. p2.y = pic_hist->height - hist2[i] * bin_unith;
155. cvRectangle(pic_hist,p1,p2,cvScalar(0,255,0),-1,8,0);
156. }
157. cvSaveImage("hist2.jpg",pic_hist);
158. for (i = 0;i < 4096;i++)
159. {
160. if (hist2[i] != 0)
161. {
162. w[i] = sqrt(hist1[i]/hist2[i]);
163. }else
164. {
165. w[i] = 0;
166. }
167. }
168. sum_w = 0.0;
169. x1 = 0.0;
170. x2 = 0.0;
171. for (i = 0;i < t_h; i++)
172. {
173. for (j = 0;j < t_w; j++)
174. {
175. //printf("%d\n",q_temp[i * t_w + j]);
176. sum_w = sum_w + w[q_temp[i * t_w + j]];
177. x1 = x1 + w[q_temp[i * t_w + j]] * (i - t_h/2);
178. x2 = x2 + w[q_temp[i * t_w + j]] * (j - t_w/2);
179. }
180. }
181. y1 = x1 / sum_w;
182. y2 = x2 / sum_w;
183. //中心点位置更新
184. drawing_box.x += y2;
185. drawing_box.y += y1;
186. //printf("%d,%d\n",drawing_box.x,drawing_box.y);
187. }
188. free(hist2);
189. free(w);
190. free(q_temp);
191. //显示跟踪结果
192. cvRectangle(current,cvPoint(drawing_box.x,drawing_box.y),cvPoint(drawing_box.x+drawing_box.width,drawing_box.y+drawing_box.height),CV_RGB(255,0,0),2);
193. cvShowImage("Meanshift",current);
194. //cvSaveImage("result.jpg",current);
195. cvReleaseImage(&pic_hist);
196. }
197. void onMouse( int event, int x, int y, int flags, void *param )
198. {
199. if (pause)
200. {
201. switch(event)
202. {
203. case CV_EVENT_LBUTTONDOWN:
204. //the left up point of the rect
205. drawing_box.x=x;
206. drawing_box.y=y;
207. break;
208. case CV_EVENT_LBUTTONUP:
209. //finish drawing the rect (use color green for finish)
210. drawing_box.width=x-drawing_box.x;
211. drawing_box.height=y-drawing_box.y;
212. cvRectangle(current,cvPoint(drawing_box.x,drawing_box.y),cvPoint(drawing_box.x+drawing_box.width,drawing_box.y+drawing_box.height),CV_RGB(255,0,0),2);
213. cvShowImage("Meanshift",current);
214. //目标初始化
215. hist1 = (double *)malloc(sizeof(double)*16*16*16);
216. m_wei =  (double *)malloc(sizeof(double)*drawing_box.height*drawing_box.width);
217. init_target(hist1, m_wei, current);
218. is_tracking = true;
219. break;
220. }
221. return;
222. }
223. }
224. int _tmain(int argc, _TCHAR* argv[])
225. {
226. CvCapture *capture=cvCreateFileCapture("test.avi");
227. current = cvQueryFrame(capture);
228. char res[20];
229. int nframe = 0;
230. while (1)
231. {
232. /*  sprintf(res,"result%d.jpg",nframe);
233. cvSaveImage(res,current);
234. nframe++;*/
235. if(is_tracking)
236. {
237. MeanShift_Tracking(current);
238. }
239. int c=cvWaitKey(1);
240. //暂停
241. if(c == 'p')
242. {
243. pause = true;
244. cvSetMouseCallback( "Meanshift", onMouse, 0 );
245. }
246. while(pause){
247. if(cvWaitKey(0) == 'p')
248. pause = false;
249. }
250. cvShowImage("Meanshift",current);
251. current = cvQueryFrame(capture); //抓取一帧
252. }
253. cvNamedWindow("Meanshift",1);
254. cvReleaseCapture(&capture);
255. cvDestroyWindow("Meanshift");
256. return 0;
257. }

运行结果：

 

初始目标直方图：

候选目标直方图：