⽬标跟踪：CamShift算法
1.前⾔
camshift利⽤⽬标的颜⾊直⽅图模型将图像转换为颜⾊概率分布图，初始化⼀个搜索窗的⼤⼩和位置，并根据上⼀帧得到的结果⾃适应调整搜索窗⼝的位置和⼤⼩，从⽽定位出当前图像中⽬标的中⼼位置。
camshift的核⼼步骤仍然是Meanshift，只是在距离相似性度量的基础之上，⼜增加了图像灰度相似性的度量。两者共同作⽤，实现了⽬标的跟踪。
2.MeanShift
Meanshift作为⼀种有效地特征空间分析⽅法，在图像滤波，图像分割，物体跟踪等⽅⾯都有⼴泛的应⽤。Meanshift算法的详细介绍，可以参见PAMI 2002的paper[1]。
给定d维空间R的n个样本点 ,i=1,…,n，在空间中任选⼀点x，那么Mean Shift向量的基本形式定义为:
Sk是⼀个半径为h的⾼维球区域，满⾜以下关系的y点的集合:
kraft
k表⽰在这n个样本点xi中，有k个点落⼊Sk区域中.
简单的理解就是，在d维空间中，任选⼀个点，然后以这个点为圆⼼，h为半径做⼀个⾼维球，因为有d维，d可能⼤于2，所以是⾼维球。落在这个球内的所有点和圆⼼都会产⽣⼀个向量，向量是以圆⼼为起点落在球内的点位终点。然后把这些向量都相加。相加的结果就是Meanshift向量。
具体如下图所⽰。其中黄⾊箭头就是Mh（meanshift向量）。
再以meanshift向量的终点为圆⼼，再做⼀个⾼维的球。如下图所以，重复以上步骤，就可得到⼀个meanshift向量。如此重复下去，meanshift算法可以收敛到概率密度最⼤得地⽅。也就是最稠密的地⽅。
unusual的最高级
最终的结果如下：
当然，⽬前Meanshift研究多集中在⾮线性领域（核函数），基本推到可以参考博客[2]。
3.CamShift⽤于⽬标跟踪的原理与MATLAB仿真
camshift利⽤⽬标的颜⾊直⽅图模型将图像转换为颜⾊概率分布图，初始化⼀个搜索窗的⼤⼩和位置，并根据上⼀帧得到的结果⾃适应调整搜索窗⼝的位置和⼤⼩，从⽽定位出当前图像中⽬标的中⼼位置。其具体步骤可以理解为三步：
1.⾊彩投影图（反向投影）
(1)RGB颜⾊空间对光照亮度变化较敏感，为了减少此变化对跟踪效果的影响，将图像从RGB空间转换到HSV空间。
(2)对其中的H分量作直⽅图，在直⽅图中代表了不同H分量值出现的概率或者像素个数，就是说可以查找出H分量⼤⼩
为h的概率或者像素个数，即得到了颜⾊概率查找表。
(3)将图像中每个像素的值⽤其颜⾊出现的概率对替换，就得到了颜⾊概率分布图。这个过程就叫反向投影，颜⾊概率分
(3)将图像中每个像素的值⽤其颜⾊出现的概率对替换，就得到了颜⾊概率分布图。这个过程就叫反向投影，颜⾊概率分布图是⼀个灰度图像。
allotment
meanshift算法是⼀种密度函数梯度估计的⾮参数⽅法，通过迭代寻优找到概率分布的极值来定位⽬标。计算搜索窗的质⼼：
(4)调整搜索窗⼤⼩，移动搜索窗的中⼼到质⼼，如果移动距离⼤于预设的固定阈值，则重复，直到搜索窗的中⼼与质⼼间的移动距离⼩于预设的固定阈值，或者循环运算的次数达到某⼀最⼤值，停⽌计算。关于meanshift的收敛性证明可以google相关⽂献。
3.camshift
将meanshift算法扩展到连续图像序列，就是camshift算法。它将视频的所有帧做meanshift运算，并将上⼀帧的结果，即搜索窗的⼤⼩和中⼼，作为下⼀帧meanshift算法搜索窗的初始值。如此迭代下去，就可以实现对⽬标的跟踪。
算法过程为：
(1).初始化搜索窗
(2).计算搜索窗的颜⾊概率分布（反向投影）
(3).运⾏meanshift算法，获得搜索窗新的⼤⼩和位置。
(4).在下⼀帧视频图像中⽤(3)中的值重新初始化搜索窗的⼤⼩和位置，再跳转到(2)继续进⾏。
ppgou
camshift能有效解决⽬标变形和遮挡的问题，对系统资源要求不⾼，时间复杂度低，在简单背景下能够取得良好的跟踪效果。但当背景较为复杂，或者有许多与⽬标颜⾊相似像素⼲扰的情况下，会导致跟踪失败。因为它单纯的考虑颜⾊直⽅图，忽略了⽬标的空间分布特性，所以这种情况下需加⼊对跟踪⽬标的预测算法。
4.matlab仿真
%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Author: Ziheng H. Shen @Tsinghua Univ.
%ObjectTrangking by CamShift @Digital Image Process Practice
%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function camshift()
clc; clo all; clear;
L = [150 116];
W = [100 73];
% For plotting motion
Xpoints = []; Ypoints = [];
binNum=128;
NFrames = length(dir('./videoImage/*.jpg')); %计算图⽚的数⽬
for frame = 1:NFrames
filename = sprintf('./videoImage/%02d.jpg', frame); %读根⽬录下的图像名
R = imread(filename);
I = rgb2hsv(R);
hue = I(:,:,1); % 提取⾊调信息
hueDiscrete= uint8( hue/ max(hue(:))*(binNum-1));
if frame==1
pHist = calHistOfROI(hueDiscrete,L,W); %第⼀帧初始化，可以⽤交互
el
lambda = 0.9;
pHist= pHist*lambda+(1-lambda)* calHistOfROI(hueDiscrete,L,W);%更新直⽅图
end
%反投影
probImage = Projection(hueDiscrete,pHist);
probImage = probImage/max(probImage(:));
%标记矩形框
probImage=drawRect( probImage,L,W);
%imshow(probImage,[]); title(num2str(frame)); pau(0.1);
%MeanShift
[L,W] = Meanshift(probImage, L,W);
[L,W] = Meanshift(probImage, L,W);
t=L+W/2;
xc=round(t(1));
yc=round(t(2));
% Output the centroid's coordinates
%disp(sprintf('%3i: %3i, %3i', frame, xc, yc));
Xpoints = [Xpoints xc];
Ypoints = [Ypoints yc];
S = drawRect(R,L,W);imshow(S);title(num2str(frame));
pau(0.1);
end
plot(Xpoints,Ypoints, 'go' , Xpoints, Ypoints);
axis([0 320 0 240]);
end
%% 计算ROI区域的直⽅图
function probabilityHist = calHistOfROI(hue,L,W)
minY = max([L(2),1]);
maxY = min([L(2)+W(2)-1, size(hue,1)]);
minX = max([L(1),1]);
criticalctionmaxX = min([L(1)+W(1)-1, size(hue,2)]);
roiVal = hue(minY:maxY,minX:maxX);
probabilityHist = hist( double(roiVal(:)),double(0:max(hue(:))));
probabilityHist = probabilityHist/sum(probabilityHist);
end
%% 反向投影，将 hue 的像素映射为对应的概率
function probImage = Projection(hue,pHist) %⾊调图 ROI直⽅图
probImage=zeros(size(hue));
[M,N]=size(hue);
for r=1:M
for c=1:N
probImage(r,c) = pHist(hue(r,c)+1); %⾊调值对应的概率
end
end
end
function [newLocation,newWndSize] = Meanshift(pImage,location,wndSize) %% meanshift L = location;
W = wndSize;
count=0;
while 1
count = count+1;
minY = max([L(2),1]);
maxY = min([L(2)+W(2)-1, size(pImage,1)]);
minX = max([L(1),1]);
maxX = min([L(1)+W(1)-1, size(pImage,2)]);
roiVal = pImage(minY:maxY,minX:maxX);
[newLocation,isConverged,~,~,M00] = calCenterOfMax(roiVal,L);
L = newLocation;
if(isConverged )
break
end
end
% 调整窗的⼤⼩
%s = round(1.8 * sqrt(M00));
%newWndSize = [floor(1.2*s) s];
newWndSize = wndSize;
disp('mean shift converged');
end
梦境美眉function [newLocation,isConverged,M01,M10,M00]=calCenterOfMax(roiVal,location)
function [newLocation,isConverged,M01,M10,M00]=calCenterOfMax(roiVal,location) % 计算roiVal区域的质⼼，从⽽计算出新的窗⼝位置
M01=0; M10=0; M00=0;
[M,N]=size(roiVal);
for r=1:M
for c=1:N
val=roiVal(r,c);
M01=M01+r*val;
M10=M10+c*val;
M00=M00+val;
end
美宣布放宽旅行限制
end
xCenter = M10 / M00;
yCenter =M01 / M00;
xCenterOld = (size(roiVal,2)+1)/2;
yCenterOld = (size(roiVal,1)+1)/2;
displacement = [xCenter yCenter]-[xCenterOld yCenterOld];
t=abs(displacement)<2;
isConverged = all(t);
newLocation = location+round(displacement);
end
function imNew = drawRect(im,L,W)% 绘制矩形框
minY = max([L(2),1]);
maxY = min([L(2)+W(2)-1, size(im,1)]);varian
minX = max([L(1),1]);
maxX = min([L(1)+W(1)-1, size(im,2)]);
imNew = im;
imNew(minY:minY+2,minX:maxX,:) = 0;
imNew(maxY-2:maxY,minX:maxX,:) = 0;
imNew(minY:maxY,minX:minX+2,:) = 0;
imNew(minY:maxY,maxX-2:maxX,:) = 0;
end
输出结果（0,1,10,20,30,40,50,60帧）：
mamiMeanShift重⼼移动轨迹为：
village什么意思
