基于NCC匹配的Camshift目標(biāo)跟蹤算法

基于NCC匹配的Camshift目標(biāo)跟蹤算法

鄭朝暉

(武漢鐵路職業(yè)技術(shù)學(xué)院公共課部, 武漢430205)

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

關(guān)鍵詞：Camshift;NCC;目標(biāo)跟蹤

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

DOI:10.11863/j.suse.2015.04.08

收稿日期:2015-05-27

基金項(xiàng)目:武漢鐵路職業(yè)技術(shù)學(xué)院院級課題

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

中圖分類號：TP391.4

文獻(xiàn)標(biāo)志碼：A

引言

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

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

1Camshift跟蹤

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

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

顏色概率分布表示為：

(1)

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

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

圖像零階矩：

圖像一階距為：

圖像二階矩：

搜索窗的質(zhì)心：

目標(biāo)主軸方向角為：

自適應(yīng)計(jì)算出的下一次搜索窗口的寬w和高h(yuǎn)分別為：

其中：

Camshift算法跟蹤步驟為：

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

(2) 計(jì)算該區(qū)域的顏色直方圖作為目標(biāo)模型。

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

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

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

2NCC匹配

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

NCC 算法具有較高的適應(yīng)性和準(zhǔn)確性，對圖像灰度值的線性變換具有“免疫性”，即所求的NCC 值不受灰度值的線性變換影響，但計(jì)算量太大，導(dǎo)致匹配效率低。

3結(jié)合Camshift與NCC的跟蹤算法

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

3.1　利用Camshift算法進(jìn)行目標(biāo)區(qū)域定位

運(yùn)動目標(biāo)的定位是目標(biāo)準(zhǔn)確跟蹤的關(guān)鍵組成部分。它主要是通過目標(biāo)特征來確定視頻中目標(biāo)圖像所對應(yīng)的位置區(qū)域，從而實(shí)現(xiàn)運(yùn)動目標(biāo)的跟蹤。

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

3.2　利用NCC算法進(jìn)行目標(biāo)匹配

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

基于NCC匹配的Camshift目標(biāo)跟蹤算法不僅提高了傳統(tǒng)跟蹤算法的準(zhǔn)確性，又實(shí)現(xiàn)了連續(xù)跟蹤的速度。其過程如圖1所示。

圖1　基于NCC匹配的Camshift目標(biāo)跟蹤算法

3實(shí)驗(yàn)結(jié)果與分析

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

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

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

表1　對若干視頻序列圖像下各算法的準(zhǔn)確性及耗時(shí)

4結(jié)束語

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

參 考 文 獻(xiàn)：

[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]吳慧敏,鄭曉勢.改進(jìn)的高效Camshift跟蹤算法.計(jì)算機(jī)工程與應(yīng)用,2009,45(27):178-180.

[3]孫祖鑫,吳強(qiáng).一種基于TS201的歸一化互相關(guān)快速算法.現(xiàn)代電子技術(shù),2010(10):125-127.

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

[5]郭偉,趙亦工,謝振華.一種改進(jìn)的紅外圖像歸一化互相關(guān)匹配算法.光子學(xué)報(bào),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預(yù)測器的改進(jìn)的CAMShift目標(biāo)跟蹤.中國慣性技術(shù)學(xué)報(bào),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]劉艷麗,唐先琪,陳躍東.基于改進(jìn)Camshift的運(yùn)動目標(biāo)跟蹤算法應(yīng)用研究.安徽工程大學(xué)學(xué)報(bào),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