基于NCC匹配的Camshift目標跟蹤算法

基于NCC匹配的Camshift目標跟蹤算法

鄭朝暉

(武漢鐵路職業技術學院公共課部, 武漢430205)

摘要：目標跟蹤一直以來都是機器視覺的熱點問題，通常目標跟蹤主要是通過尋找上下幀的相似特征來確定目標位置。Camshift算法在目標跟蹤過程中一般利用的是目標的顏色信息，但在目標受到類似顏色干擾時容易跟蹤失敗，而NCC算法能夠利用目標的結構特征。提出了一種結合Camshift與NCC的跟蹤算法，使用Camshift對目標位置進行定位，同時在定位區域利用縮放比例進行NCC匹配得到目標的最終位置。實驗結果表明該算法是可行有效的，對比當前傳統跟蹤算法其跟蹤性能有著顯著的提高。

關鍵詞：Camshift;NCC;目標跟蹤

文章編號：1673-1549(2015)04-0037-04

DOI:10.11863/j.suse.2015.04.08

收稿日期:2015-05-27

基金項目:武漢鐵路職業技術學院院級課題

作者簡介:鄭朝暉(1985-)，男，湖北黃岡人，講師，碩士，主要從事數字圖像處理與模式識別方面的研究，(E-mail)zhengzhaohui@sina．cn

中圖分類號：TP391.4

文獻標志碼：A

引言

目標跟蹤在機器視覺中一直是一個熱門課題。目前有很多的目標跟蹤方法，但是它們都有各自的優點和缺點。而目標跟蹤的關鍵在于目標特征提取的合理性和識別目標的準確性，同時要考慮算法的時間，確保實時性。Camshift算法[1-2]是一種有效的目標跟蹤算法，它是MeanShift跟蹤方法的改進。該算法通過使用梯度優化方法來完成目標定位，對目標的旋轉、變形等變化有較好的適應能力，同時算法的運算速度快。Camshift算法對單一色調的目標及背景和目標顏色不同的情況跟蹤效果顯著，但是當周圍環境存在顏色干擾時，只使用Camshift算法容易丟失目標。NCC算法(歸一化互相關算法)[3-5]是一種經典的圖像匹配算法，它通過計算模板圖像和搜索圖像的互相關值來進行匹配。NCC 算法適用于幾何畸變及灰度變化不大的情況，同時它具有抗白噪聲能力，但該方法容易受到目標旋轉、變形的影響，且匹配速度較慢。

考慮到目標運動過程中可能會受到場景中諸如形變、遮擋和運算速度等因素的影響，本文在采用基于顏色直方圖的Camshift跟蹤算法的同時，結合了NCC 算法對目標空間運動位置進行進一步匹配，在保證匹配精度的前提下，提高NCC匹配算法的速度，增強算法對實際應用的適應性。

1Camshift跟蹤

近年來，MeanShift算法[6]因其結構簡單、效率高的特點已被廣泛應用于目標跟蹤領域。但是MeanShift算法缺乏必要的模型更新，因此只適用于靜態分布，這將影響跟蹤的精度。而作為一種改進MeanShift算法的方法，Camshift(連續自適應MeanShift)算法[7-8]可以應用于動態概率分布情況。在跟蹤過程中，Camshift利用目標的顏色直方圖模型得到每幀圖像的顏色投影圖，并根據上一幀的結果自適應調整搜索窗口的位置和大小，從而得到當前圖像中目標的尺寸和中心位置。

顏色直方圖作為Camshift所采用的顏色特征。它所描述的是不同色彩在圖像中所占的比例，而并不關心每種色彩所處的空間位置。圖像中顏色范圍分為N個相等但不相交的區間，統計顏色為n的像素個數為h(n)，這些h(n)矩形依次排列就得到顏色直方圖。

顏色概率分布表示為：

(1)

其中，n為顏色像素值，作為顏色直方圖得橫坐標；h(n)為顏色像素個數，作為顏色直方圖的縱坐標；p(n)為h(n)的歸一化取值。直方圖中的h(n)由p(n)代替，就得到目標的顏色直方圖模型。

對于一幅圖像I(x,y)來說，Camshift算法需要通過下列公式計算出下一幅圖像的初始搜索窗口的長和寬。

圖像零階矩：

圖像一階距為：

圖像二階矩：

搜索窗的質心：

目標主軸方向角為：

自適應計算出的下一次搜索窗口的寬w和高h分別為：

其中：

Camshift算法跟蹤步驟為：

(1) 選擇感興趣的初始區域，其中包含要跟蹤的目標。

(2) 計算該區域的顏色直方圖作為目標模型。

(3) 計算搜索窗的顏色概率分布(反向投影)。

(4) 基于概率分布的圖像，找到搜索窗的質心。

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

2NCC匹配

NCC匹配算法也稱為歸一化互相關匹配算法[9-10]，它適用于沒有幾何誤差的情況。該算法計算模板與待匹配圖像的互相關值來確定匹配的相似度。簡單而言，模板就是預先選擇感興趣的目標圖像，匹配就是在待匹配圖像中尋找該目標圖像，這要求圖像中存在目標圖像，同時該目標圖像與模板存在較小角度的旋轉或者形變，通過計算出的互相關值來確定目標的坐標位置。假設搜索圖像S的尺寸為M×M，模板T的尺寸為N×N，其中M>N，單位為像素。模板T在搜索圖像S上平移，Si,j為模板在搜索圖像所覆蓋的子圖，子圖在搜索圖像S中左上角頂點的坐標為(i,j)。在實際匹配中，模板和搜索圖像的相似性通過度量函數來衡量，則歸一化互相關匹配度量定義為:

NCC 算法具有較高的適應性和準確性，對圖像灰度值的線性變換具有“免疫性”，即所求的NCC 值不受灰度值的線性變換影響，但計算量太大，導致匹配效率低。

3結合Camshift與NCC的跟蹤算法

Camshift算法適合于非線性運動目標的跟蹤，具有快速有效的特點[11]；NCC 算法可以利用結構特征準確地定位運動目標的位置。因此本文將兩種算法相結合，采用基于顏色的Camshift算法的同時利用NCC 算法考慮目標的結構信息。該算法對場景中存在的諸如顏色干擾、光照變化等因素的影響不敏感。

3.1　利用Camshift算法進行目標區域定位

運動目標的定位是目標準確跟蹤的關鍵組成部分。它主要是通過目標特征來確定視頻中目標圖像所對應的位置區域，從而實現運動目標的跟蹤。

在目標跟蹤前，先確定初始目標圖像的顏色概率分布圖和目標跟蹤模板，然后利用Camshift算法計算出目標包圍窗口，快速獲取目標質心和大小，從而定位出相似目標顏色特征的區域。由于在Camshift算法中，目標跟蹤只是簡單地以顏色概率作為其跟蹤模式，當它用于背景中有類似顏色區域的目標跟蹤時，必然會忽略了目標所特有的外觀而出現跟蹤失誤，所以獲取的目標位置及大小需要利用NCC算法進行目標模板匹配。

3.2　利用NCC算法進行目標匹配

以獲取到的類似目標質心為中心、目標大小為半徑(可以適當增大，本文設置為5個像素)作一個矩形為待匹配區域，利用NCC算法將目標跟蹤模板和待匹配區域進行匹配。若最大互相關值大于閾值則匹配成功，更新目標的中心和大小，同時更新顏色概率分布圖和目標跟蹤模板；反之匹配失敗，不更新目標的中心和大小。

基于NCC匹配的Camshift目標跟蹤算法不僅提高了傳統跟蹤算法的準確性，又實現了連續跟蹤的速度。其過程如圖1所示。

圖1　基于NCC匹配的Camshift目標跟蹤算法

3實驗結果與分析

為了檢測算法的有效性，依照本文的算法對多只同類動物水面奔跑視頻圖像序列進行了目標跟蹤測試(圖2(分別為第1、13、37、64幀))，取得了較好的跟蹤效果。圖2(a)是采用Camshift算法的跟蹤情況，由圖2(a)可以看出，Camshift算法的跟蹤窗口向著目標點集中的方向漂移，但在第13幀時目標受到另一個同類顏色所干擾，跟蹤窗口漂移到附近與目標顏色相近的背景上。直到第37幀時，目標背景變得單一，跟蹤窗口重新回到目標身上，而在第64幀時，目標部分超出視頻區域，跟蹤窗口出現下移，只包含一部分目標；圖2(b)是結合NCC 算法的跟蹤結果，通過模板的結構比較，判斷是否為目標，干擾前后均實現了準確的跟蹤。

將本文算法與傳統算法進行準確性與運算速度進行比較，結果見表1。從表1可知，相較于傳統NCC算法與Camshift算法，在相同的目標模板情況下，本文的算法在運算速度上改善非常明顯，尤其是相對于傳統NCC算法來說，運算速度提高了近一倍；另外，匹配準確率也高于傳統算法。

圖2　多只同類動物水面奔跑視頻圖像序列

表1　對若干視頻序列圖像下各算法的準確性及耗時

4結束語

本文提出了基于NCC匹配的Camshift目標跟蹤算法，采用基于顏色的Camshift算法的同時利用NCC 算法考慮目標的結構信息，解決了場景中存在大面積類似顏色干擾導致跟蹤失敗的問題，并且在減少跟蹤失敗的同時最大限度地保證算法的實時性。與直接在圖片上進行模板匹配確定目標的算法相比，本文方法因以Camshift算法為主導，其速度大大提高；而與原始的CamShift算法相比，其準確性又有所改善。當模板過大或者出現旋轉時，基于NCC匹配，可以采用比例縮放和角度旋轉關系，或者采用基于金字塔結構的模板匹配算法完成匹配，能夠有效提高運算速度。

參 考 文 獻：

[1]Comanciu D,Ramesh V,Meer R.Real-time tracking of non-rigid objects using mean shift//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition,Dublin,Ireland,June 13-15,2000:142-149.

[2]吳慧敏,鄭曉勢.改進的高效Camshift跟蹤算法.計算機工程與應用,2009,45(27):178-180.

[3]孫祖鑫,吳強.一種基于TS201的歸一化互相關快速算法.現代電子技術,2010(10):125-127.

[4]韓冰,王永明,劉楊.一種基于積分圖像的快速歸一化積相關算法.彈箭與制導學報,2009,29(5):283-286.

[5]郭偉,趙亦工,謝振華.一種改進的紅外圖像歸一化互相關匹配算法.光子學報,2009,38(1):189-193.

[6]Chen Y Z.Mean shift,mode seeking and clustering.IEEE Transactions on Pattern Analysis and Machine Intelligence,1995(8):790-799.

[7]Comanciu D,Meer R.Mean shift:a robust approach toward feature space analysis.IEEE Transactions on Pattern Analysis and Machine Intelligence,2002(5):603-619.

[8]Mazinan A H,Amir-Latifi A.Applying mean shift,motion information and Kalman filtering approaches to object tracking.ISA Transactions,2012(5):485-497.

[9]Hidayatullah P,Konik H.CAMSHIFT improvement on multi-hue and multi-object tracking//Proceedings of International Conference on Electrical Engineering and Informatics,Bandung,Indonesia,July 17-19,2011:17-19.

[10]Wu Lianhui,Zhang Guoyun,Guo Longyuan.Study the improved CAMSHIFT algorithm to detect the moving object in fisheye image//Proceedings of 2013 International Conference on Mechatronic Sciences,Electric Engineering and Computer(MEC),Shenyang,December 14-16,2013:1017-1020.

[11]閆鈞華,陳少華,艾淑芳.基于Kalman預測器的改進的CAMShift目標跟蹤.中國慣性技術學報,2014,22(4):536-542.

[12]Ali P,Sajad P,Saeed K.Scene matching NCC value improvement based on contrast matching//Proceedings of 2013 8th Iranian Conference on Machine Vision and Image Processing(MVIP),Zanjan,Iran,September 10-12,2013:296-299.

[13]劉艷麗,唐先琪,陳躍東.基于改進Camshift的運動目標跟蹤算法應用研究.安徽工程大學學報,2012,27(2):74-77.

Camshift Target Tracking Algorithm Based on NCC Matching

ZHENGZhaohui

(Department of Public Courses, Wuhan Railway Vocational College of Technology, Wuhan 430205, China)

Abstract:Target tracking is always a hot topic of machine vision, usually target tracking determines the position of target by searching the similarity of upper and lower frames. Camshift algorithm commonly utilizes the color information of the target in the target tracking process, but the target tracking is easily failed when exists interference of similar color. While the NCC algorithm can use the structure features of target. Therefore, a tracking algorithm which combines Camshift with NCC is proposed, in which Camshift is used to locate the positioning of target, meantime, NCC matching is conducted by using the scaling in location area, then the final position of target is obtained. The experimental results show that the algorithm is feasible and effective, and the tracking performance is improved significantly compared with the traditional tracking algorithm.

Key words: Camshift; NCC; target tracking