1.基于MeanShift的Camshift算法原理詳解(整理)

meanshift算法思想其實很簡單：利用概率密度的梯度爬升來尋找局部最優。它要做的就是輸入一個在圖像的范圍，然后一直迭代（朝著重心迭代）直到滿足你的要求為止。但是他是怎么用于做圖像跟蹤的呢？這是我自從學習meanshift以來，一直的困惑。而且網上也沒有合理的解釋。經過這幾天的思考，和對反向投影的理解使得我對它的原理有了大致的認識。 在opencv中，進行meanshift其實很簡單，輸入一張圖像（imgPRob），再輸入一個開始迭代的方框（windowIn）和一個迭代條件（criteria），輸出的是迭代完成的位置（comp ）。 這是函數原型： int cvMeanShift( const void* imgProb, CvRect windowIn, CvTermCriteria criteria, CvConnectedComp* comp ) 但是當它用于跟蹤時，這張輸入的圖像就必須是反向投影圖了。 為什么必須是反向投影圖呢？首先我們要理解什么是反向投影圖。 簡單理解它其實實際上是一張概率密度圖。經過反向投影時的輸入是一個目標圖像的直方圖（也可以認為是目標圖像），還一個輸入是當前圖像就是你要跟蹤的全圖，輸出大小與全圖一樣大，它上像素點表征著一種概率，就是全圖上這個點是目標圖像一部分的概率。如果這個點越亮，就說明這個點屬于物體的概率越大。現在我們明白了這原來是一張概率圖了。當用meanshift跟蹤時，輸入的原來是這樣一幅圖像，那也不難怪它可以進行跟蹤了。 半自動跟蹤思路：輸入視頻，用畫筆圈出要跟蹤的目標，然后對物體跟蹤。 用過opencv的都知道，這其實是camshiftdemo的工作過程。 第一步：選中物體，記錄你輸入的方框和物體。 第二步：求出視頻中有關物體的反向投影圖。 第三步：根據反向投影圖和輸入的方框進行meanshift迭代，由于它是向重心移動，即向反向投影圖中概率大的地方移動，所以始終會移動到目標上。 第四步：然后下一幀圖像時用上一幀輸出的方框來迭代即可。 全自動跟蹤思路：輸入視頻，對運動物體進行跟蹤。 第一步：運用運動檢測算法將運動的物體與背景分割開來。 第二步：提取運動物體的輪廓，并從原圖中獲取運動圖像的信息。 第三步：對這個信息進行反向投影，獲取反向投影圖。 第四步：根據反向投影圖和物體的輪廓（也就是輸入的方框）進行meanshift迭代，由于它是向重心移 動，即向反向投影圖中概率大的地方移動，所以始終會移動到物體上。 第五步：然后下一幀圖像時用上一幀輸出的方框來迭代即可。 總結：用meanshift進行跟蹤最重要的一點是輸入圖像的把握，也就是要讓它的迭代能越來越迭代到目標上。這種圖像也不一定就是反向投影圖，只要是一幅反映當前圖像中每個像素點含有目標概率圖就可以了，其實反向投影圖就是這樣的一幅圖而已。

CamShift算法，即”Continuously Apative Mean-Shift”算法，是一種運動跟蹤算法。它主要通過視頻圖像中運動物體的顏色信息來達到跟蹤的目的。

camshift利用目標的顏色直方圖模型將圖像轉換為顏色概率分布圖，初始化一個搜索窗的大小和位置，并根據上一幀得到的結果自適應調整搜索窗口的位置和大小，從而定位出當前圖像中目標的中心位置。該算法分為三個部分：

1) Back Projection計算

2) Mean Shift算法

3) CamShift算法

具體實現是：

1–色彩投影圖（反向投影）

(1)RGB顏色空間對光照亮度變化較為敏感，為了減少此變化對跟蹤效果的影響，首先將圖像從RGB空間轉換到HSV空間。

(2)然后對其中的H分量作直方圖，在直方圖中代表了不同H分量值出現的概率或者像素個數，就是說可以查找出H分量大小為h的概率或者像素個數，即得到了顏色概率查找表。

(3)將圖像中每個像素的值用其顏色出現的概率對替換，就得到了顏色概率分布圖。這個過程就叫反向投影，顏色概率分布圖是一個灰度圖像。

2–meanshift

meanshift算法是一種密度函數梯度估計的非參數方法，通過迭代尋優找到概率分布的極值來定位目標。算法過程為：

(1).在顏色概率分布圖中選取搜索窗W

(2).計算零階距：

計算一階距：

計算搜索窗的質心：

(3).調整搜索窗大小：寬度為；長度為1.2s；

(4).移動搜索窗的中心到質心，如果移動距離大于預設的固定閾值，則重復2)3)4)，直到搜索窗的中心與質心間的移動距離小于預設的固定閾值，或者循環運算的次數達到某一最大值，停止計算。

算法過程也可以描述如下：

(1) 選擇搜索窗口

a.窗口的初始位置 b.窗口的類型（均勻、多項式、指數或者高斯類型） c.窗口的形狀（對稱的或歪斜的，可能旋轉的，圓形或矩形） d.窗口的大小（超出寬口大小被截去）

(2) 計算窗口（可能是帶權重的）的重心

(3) 將窗口的中心設置在計算出的重心處。移動搜索窗的中心到質心，如果移動距離大于預設的固定閾值，則重復2)3)4)，直到搜索窗的中心與質心間的移動距離小于預設的固定閾值，或者循環運算的次數達到某一最大值，停止計算。

(4) 返回（2），直到窗口的位置不再變化（通常會變化，直至最后迭代收斂）

3–camshift

將meanshift算法擴展到連續圖像序列，就是camshift算法。它將視頻的所有幀做meanshift運算，并將上一幀的結果，即搜索窗的大小和中心，作為下一幀meanshift算法搜索窗的初始值。如此迭代下去，就可以實現對目標的跟蹤。算法過程為：

(1).初始化搜索窗

(2).計算搜索窗的顏色概率分布（反向投影）

(3).運行meanshift算法，獲得搜索窗新的大小和位置。

(4).在下一幀視頻圖像中用(3)中的值重新初始化搜索窗的大小和位置，再跳轉到(2)繼續進行。

計算被跟蹤目標的色彩直方圖。在各種色彩空間中，只有HSI空間(或與HSI類似的色彩空間)中的H分量可以表示顏色信息。所以在具體的計算過程中，首先將其他的色彩空間的值轉化到HSI空間，然后會其中的H分量做1D直方圖計算。

根據獲得的色彩直方圖將原始圖像轉化成色彩概率分布圖像，這個過程就被稱作”Back Projection”。在OpenCV中的直方圖函數中，包含Back Projection的函數，函數原型是：void cvCalcBackProject(iplImage** img, CvArr** backproject, const CvHistogram* hist);

傳遞給這個函數的參數有三個：

IplImage** img:存放原始圖像，輸入。

CvArr** backproject:存放Back Projection結果，輸出。

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]。

(3).計算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);

(4). result即為我們需要的.

Mean Shift算法的質心可以通過以下公式來計算：

(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

在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)。

CamShift算法的具體步驟分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繼續運行。

在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接口的攝像頭。然后可以用鼠標選定欲跟蹤目標。