李超 于飛 康曉軍

（北京空間機電研究所，北京 100094）

一種模板匹配的快速實現(xiàn)方法

李超 于飛 康曉軍

（北京空間機電研究所，北京 100094）

文章主要研究視頻圖像運動中目標軌跡的準確預測和快速定位，從而能夠為光電跟蹤控制系統(tǒng)提供可靠的位置數(shù)據(jù)和運動參數(shù)。光電跟蹤控制系統(tǒng)要求對運動目標有較快的響應速度，響應時間越短，系統(tǒng)的實時性就越好，因此快速而準確的目標跟蹤算法顯得尤為重要。高幀頻的跟蹤控制系統(tǒng)限制了圖像處理的計算時間，實時性與計算精度很難兼顧，傳統(tǒng)的目標跟蹤方法難以適用。針對這一問題，文章提出基于Kalman濾波軌跡預測的模板匹配方法，通過建立目標的運動模型，給出了Kalman濾波的過程方程與測量方程。在目標跟蹤過程中，對當前幀匹配得到的目標運動數(shù)據(jù)進行濾波處理，預測下一幀目標的運動參數(shù)。文章方法的優(yōu)點是可以利用匹配值不斷地修正預測值，同時修正系統(tǒng)模型參數(shù)和噪聲統(tǒng)計參數(shù)，保證計算的快速性與跟蹤的準確性。文章方法的優(yōu)勢在于摒棄了遍歷搜索目標的盲目性，使目標跟蹤更具有針對性，在保證精度的同時節(jié)省了時間。通過多次運動測試，仿真結果表明：算法具有良好的實時性和一定的適應環(huán)境變化的能力。

目標跟蹤 模板匹配 卡爾曼濾波 卡爾曼預測

0 引言

在跟蹤技術領域，光電跟蹤控制系統(tǒng)是涉及多項關鍵技術的復雜系統(tǒng)工程，主要對高速攝像機拍攝的序列圖像目標進行實時跟蹤。目標跟蹤算法[1]近幾年發(fā)展十分迅速，而模板匹配算法具有不完全依賴圖像分割效果的特點，并且對場景圖像品質要求不高，可在低信噪比條件下穩(wěn)定工作。模板匹配算法在成像跟蹤中有著重要地位，但是現(xiàn)有模板匹配算法運算量大，計算速度在現(xiàn)有技術條件下受到制約，導致匹配速度無法達到實時性的要求，因此無法應用于光電跟蹤控制系統(tǒng)中。如何兼顧計算速度與精度的要求，一直是國內外研究學者思考的問題[2-8]。

很多方法如FFT相關算法、序貫相似性檢測算法、變分辨率相關算法等大多存在著適用范圍窄、精度低、速度提高不明顯等缺點，無法滿足工程實際要求。本文介紹一種利用 Kalman濾波器的預測與修正兩種功能對模板匹配算法進行優(yōu)化，使算法更有針對性和有效性，以減少計算量、提高匹配速度為目的進行改進，建立了適當?shù)臄?shù)學模型?；贙alman濾波給出相應的濾波方程，根據(jù)前一時刻Kalman濾波得到的目標修正位置信息，采用 Kalman一步預測算法估計目標在當前時刻的可能位置，以預測的位置為中心，搜索范圍匹配確定目標在當前圖像中的準確位置，仿真結果表明，本文所采取的方法能夠縮小目標搜索范圍，減小計算量，提高目標跟蹤精度。

1 模板匹配

基于匹配的目標跟蹤方法的依據(jù)為圖像灰度互相關準則。常用的匹配方法如基于特征點的匹配，其要求被跟蹤目標明確或具有某類特征[9]，基于模板匹配的方法注重模板圖像的相關性，對目標沒有限定，故本文選用模板匹配實現(xiàn)運動目標跟蹤。模板的選取基于人機交互，操作員選取視頻圖像中一定區(qū)域作為目標模板，跟蹤目標過程由計算機自動實時處理作為支持[10]。在運動目標跟蹤的過程中，將已知的目標模板與待匹配子圖像進行匹配，在視頻圖像中通過計算目標模板與待匹配子圖像的互相關值。如圖1所示，整個區(qū)域為待匹配子圖像，M與N為模板圖像的列與行，(m,n)是當前匹配位置，t(i,j)是模板圖像上的第i行和第j列的像素的灰度值。選擇具有最大互相關值的當前匹配位置作為目標在當前幀圖像中的實際位置，從而實現(xiàn)運動目標的跟蹤定位[11]。

圖1 模板匹配示意圖Fig.1 Sketch map of template matching

1.1 互相關計算優(yōu)化

模板匹配算法的核心就是在序列圖像內搜索與所選模板最相似的匹配位置，本文研究的匹配準則為歸一化積相關(NPROD)匹配準則，為了盡可能降低噪聲對匹配結果的影響，采用去均值歸一化積相關(NNPROD)匹配準則[12]?；ハ嚓P運算公式如下：

式中 目標模板大小為M×N； R( m, n)表示目標模板與待匹配子圖像在(m, n)點上的互相關值，且滿足0 ≤ R( m, n )≤1；f( i+ m, j+ n)表示的是待匹配子圖像中第i+m行與第 j+n列交叉點的像素的灰度值；t( i, j)是模板圖像上的第i行與第j列交叉點的像素的灰度值；表示的是目標模板灰度值的平均值；表示的是待匹配子圖像實時子區(qū)間灰度值的平均值，其計算方法為：

隨著目標模板大小的增加，上述算法的計算量成倍增加。為了解決上述問題，需要針對算法進行優(yōu)化，提出合理的減小計算量的算法。

因為相似度匹配含卷積運算，故而可采用快速傅里葉變換進行簡化計算。而NPROD算法實際上是將待匹配子圖像與目標模板的灰度值按矢量計算，求兩者夾角的余弦值。只有當矢量相等時，互相關值才有等于1的情況，因此NPROD算法不受乘性灰度誤差影響，但對于加性誤差卻非常敏感。而NNPROD算法不僅不受乘性灰度誤差影響，而且可以抑制加性誤差的影響，這也是本文采用NNPROD的主要原因。

光電跟蹤控制系統(tǒng)的實時性很強，建議搜索窗不能開的太大。這就導致搜索窗內圖像與參考模板圖像的相似度很接近，這樣相關系數(shù)值比較大，匹配點周圍的相關系數(shù)值比較接近，不容易得到真正的匹配點。為了放大相關系數(shù)值的差別，本文把公式（1）的分母去掉，變成：

將公式（2）、（3）代入公式（4）式展開得到：

為了簡化處理，本文認為圖像灰度值滿足均勻分布，用均值代替各個點像素值，可以得到近似關系：

將公式（6）帶入公式（5）化簡得到：

公式（7）稱之為快速NNPROD匹配準則。

1.2 計算量分析

在同樣大小M×N像素的模板，對公式（1）與公式（7）匹配運算比較，NNPROD互相關計算量與快速NNPROD互相關計算量如表1所示：

表1 計算量對比Tab.1 Comparison of calculation between NNPROD and fast NNPROD

由表1數(shù)據(jù)可以得到，快速NNPROD較NNPROD而言，總的計算次數(shù)約為NNPROD算法的1/4，提高了的匹配速度。上述快速 NNPROD用于模板匹配算法的準則。在圖像匹配跟蹤過程中，目標模板在當前幀待匹配子圖像內滑動，并與待匹配子圖像作如公式（7）的互相關運算， R＇( m, n)的最大值對應的當前匹配位置作為最佳的匹配點。

2 Kalman濾波器設計

實現(xiàn)快速模板匹配的主要入手方向有如下兩點：

1）減少每次模板互相關運算的計算量；

2）優(yōu)化搜索策略，減少搜索像素點數(shù)。

在已經(jīng)對模板匹配的計算量做出優(yōu)化后，接下來是考慮如何優(yōu)化搜索策略。本文采用預測跟蹤處理技術[13-16]，根據(jù)目標之前的位置信息和運動狀態(tài)，估計出目標下一步可能的位置，可以實現(xiàn)在相對較小的區(qū)域內進行匹配運算，大大降低了尋找目標的時間。

2.1 軌跡線性預測算法

假設相鄰幀間圖像相似度大，位置變化小，可近似認為目標做直線運動，即系統(tǒng)觀測方程滿足線性。假設噪聲滿足高斯分布，則可以采用線性Kalman預測方法實現(xiàn)對運動目標的軌跡預測。

Kalman濾波是一種線性最優(yōu)濾波算法，濾波準則是均方誤差最小。把圖像處理技術與Kalman濾波算法結合起來[17]，利用 Kalman濾波的最優(yōu)估計結果預測目標運動狀態(tài)，從而預測目標運動軌跡，系統(tǒng)的狀態(tài)方程和觀測方程為：

式中 xk是k時刻的狀態(tài)向量；xk-1為k-1時刻的狀態(tài)向量；A是狀態(tài)轉移矩陣；B為控制矩陣；uk-1為控制量，由于本文跟蹤系統(tǒng)沒有控制量即uk-1=0；zk為觀測向量；H是觀測矩陣；wk-1和γk是相互獨立的高斯白噪聲。

Kalman濾波器的系統(tǒng)狀態(tài)預測方程：

2.2建立目標運動模型

式中 Δt為幀頻的倒數(shù)。

為了修正目標狀態(tài)參數(shù)，進行目標信息的準確估計，本文的觀測向量是包含位置與速度信息的4維向量，速度修正一方面使位置信息更為準確，另一方面為目標搜索提供依據(jù)。

2.3 運動目標搜索策略

模板匹配算法要從視頻的每一幀圖像中遍歷搜索檢測出目標位置，計算量很大?？梢岳?Kalman濾波器，在 k-1時刻獲得的修正目標信息基礎上，對k時刻目標的信息進行預測。但是該預測值存在誤差，所以在k時刻，以預測值為圓心，以目標尺寸L加時間段內目標的預計運動距離為半徑，如圖2所示，確定k時刻目標搜索范圍Sk：

式中 vk為k時刻目標運動合速度，滿足。

在k時刻，由Kalman 預測方程得到運動目標預測目標狀態(tài)向量，得到目標的預測位置，在以預測位置為圓心，搜索范圍Sk為半徑的圓形區(qū)域內采用優(yōu)化NNPROD的模板匹配算法尋找目標最優(yōu)位置，重新計算速度信息，構成k時刻的觀測向量zk，并將匹配得到的最優(yōu)位置作為最終目標位置保存下來。

利用k時刻的觀測向量zk與Kalman濾波器的修正方程，得到 k時刻的修正目標狀態(tài)xk，用于k+1時刻目標狀態(tài)向量的預測。

圖2 搜索范圍示意圖Fig.2 Sketch map of searching area

3 仿真分析

為了驗證本文提出的基于Kalman 濾波的模板匹配快速算法，進行了計算機Matlab仿真分析。應用處理器為Intel(R) Core(TM) i5-3470 PC機，在Matlab2008a軟件平臺進行仿真實驗，得到NNPROD與快速NNROD的幀間計算時間比較如表2所示。

可以看出，在模板尺寸為30×30像素的情況下，NNPROD算法平均計算時間為0.07s，為14幀頻，再考慮幀間數(shù)據(jù)傳輸與轉換，計算時間是不能容忍的?？焖貼NPROD算法的平均計算時間為0.004s，為250幀頻。對于高幀頻跟蹤有足夠的計算時間余量。并且隨著模板尺寸的增大，NNPROD算法平均計算時間迅速增大，在模板尺寸為100×100時，已經(jīng)不到4幀頻，而快速NNPROD算法隨著模板增大，計算時間增量很小，仍可以用于高幀頻光電跟蹤控制系統(tǒng)中。

表2 不同算法與幀計算時間比較Tab. 2 Comparison of frame calculating time between NNPROD and fast NNPROD

在進行仿真時，假設系統(tǒng)的過程噪聲、量測噪聲均為零均值高斯白噪聲，初始誤差協(xié)方差矩陣取。如圖3是目標跟蹤的展示圖，在含高斯噪聲的背景下對目標進行跟蹤試驗，綠框代表了選取的目標模板，目標為綠框內的白色圓形。用目標模板的中心代表白色圓形的等效位置，初始位置為（100,47），近似勻速運動。如圖4所示，采用線性Kalman 濾波的模板匹配算法得到目標運動的匹配軌跡與Kalman濾波器的預測軌跡。

用線性模型近似代替非線性運動模型，用Kalman濾波器預測的位置必然存在誤差，只要Kalman濾波器的修正結果在最終匹配位置附近，即可保證本算法在最快的時間內找到最終的位置。目標的運動速度大小存在±10%的隨機變動，通過統(tǒng)計坐標數(shù)據(jù)計算匹配軌跡與預測軌跡的誤差在±5個像素之內，認為相差5個像素之內的預測點為跟蹤準確點，相差5個像素以上的預測點為跟蹤漂移點，如表3所示，展示了本算法的跟蹤性能。

圖3 目標跟蹤圖像Fig. 3 Image of target tracking

圖4 匹配軌跡與預測軌跡Fig. 4 Tracks of matching and Prediction

表3 目標跟蹤性能分析Tab.3 Analysis of the target tracking performance

結合表2與表3的實驗結果可以看出，在目標跟蹤過程中，模板大小一定，運動形式一定時，本文采用基于Kalman 濾波的模板匹配算法確定的目標搜索范圍，都能夠包含目標，同時使得搜索范圍縮小。模板匹配與 Kalman濾波預測相結合，對目標運動狀態(tài)進行預測跟蹤，將圖像處理的范圍縮小。本算法基于NNPROD，而與NNPROD相比，在保證精度的同時減少了計算時間。

4 結束語

本文采用基于Kalman 濾波的模板匹配算法確定視頻圖像中目標的運動軌跡，避免對全幀圖像的遍歷搜索，減小了目標匹配的計算量，實現(xiàn)了一種“預測一匹配—修正—預測”的反饋形式。仿真結果表明，本文所采用的基于 Kalman濾波的模板匹配算法，能夠有效減小目標跟蹤時的計算量，具有較好的目標跟蹤精度。

References)

[1]邵文坤, 黃愛民, 韋慶. 目標跟蹤方法綜述[J]. 影像技術, 2006(1): 271-275. SHAO Wenkun, HUANG Aimin, WEI Qing. Research on Object Tracking[J]. Image Technology, 2006(1): 271-275. (in Chinese)

[2] VRABEL M J. A Target-Tracking Algorithm[R]. Army Research Lab Adelphi MD, 2000.

[3] MARCHAND E, CHAUMETTE F. Feature Tracking for Visual Servoing Purposes[J]. Robotics and Autonomous Systems, 2005, 52(1): 53-70.

[4] LUO Xiaobo, FAN Hongqi, SONG Zhiyong, et al. Passive Target Tracking with Intermittent Measurement Based on Random Finite Set[J]. Journal of Central South University, 2014, (6): 2282-2291.

[5] SHI Xiaoping, WANG Yuzhe. Enhancement of Target Tracking Using Target Orientation Information[C]. The 25thChinese Control and Decision Conference, Gui Yang, Chinese Society of Aeronautics and Astronautics, 2013.

[6]陳沈軼, 錢徽, 吳錚, 等. 模板圖像匹配中互相關的一種快速算法[J]. 傳感技術學報, 2007, 20(6): 1326-1327. CHEN Shenyi, QIAN Hui, WU Zheng, et al. Fast Normalized Cross-Correlation for Template Matching[J]. Chinese Journal of Sensors and Actuators, 2007, 20(6): 1326-1327. (in Chinese)

[7] LOTSPEICH J T. Tracking Subpixel Targets with Critically Sampled Optical Sensors[R]. Naval Postgraduate School Monterey CA, 2012.

[8] WANG Huilin, WANG Ying, AN Ru, et al. Fast Image Matching Algorithm Based on Key Points[C]. Remote Sensing of the Environment: 18th National Symposium on Remote Sensing of China. Wuhan: Nanjing University, 2014.

[9]耿蕾蕾, 林軍, 龍小祥, 等. “資源三號”衛(wèi)星圖像影像特征匹配方法研究[J]. 航天返回與遙感, 2012, 33(3): 94-96. GENG Leilei, LIN Jun, LONG Xiaoxiang, et al. Research on Feature Matching Algorithm for ZY-3 Image[J]. Spacecraft Recovery & Remote Sensing, 2012, 33(3): 94-96. (in Chinese)

[10]楊文, 孫洪, 曹永鋒. 合成孔徑雷達圖像目標識別問題研究[J]. 航天返回與遙感, 2004, 25(1): 39-41. YANG Wen, SUN Hong, CAO Yongfeng. Study on Automatic Target Recognition in SAR Imagery[J]. Spacecraft Recovery & Remote Sensing, 2004, 25(1): 39-41. (in Chinese)

[11]陳翔, 陳鵬. 基于改進模板匹配的模板跟蹤算法[J]. 計算機應用, 2011, 31(z2): 127-128. CHEN Xiang, CHEN Peng. Object Tracking Algorithm Based on Improved Template Matching[J]. Journal of ComputerApplications, 2011, 31(z2): 127-128. (in Chinese)

[12]ZHUO Yang. Fast Template Matching Based on Normalized Cross Correlation With Centroid Bounding[C]. International Conference on Measuring Technology and Mechatronics Automation. Changsha: Institutes of Technology of Changsha & Central South University, 2010.

[13]仝曉龍, 竇騰飛, 劉艷紅. 運動目標跟蹤技術綜述[J]. 科技創(chuàng)新與應, 2014, (18): 18-19. TONG Xiaolong, DOU Tengfei, LIU Yanhong. Survey of Moving Target Tracking Technology[J]. Technology Innovation and Application, 2014, (18): 18-19. (in Chinese)

[14]ZHAO Xiafu, YAN Han. Centroid Weighted Kalman Filter for Visual Object Tracking[J]. Measurement, 2012, 45(4): 650-655.

[15]TANG Xinhua, GIANLUCA F, EMANUELA F, et al. Theoretical Analysis and Turning Criteria of Kalman Filter-based Tracking Loop[J]. GPS Solutions, 2015, 19(3): 489-503.

[16]ABHARI S Q, ERSHADI T Z. Target Tracking Based on Mean Shift and KALMAN Filter with Kernel Histogram Filtering[J]. Computer and Information Science, 2011, 4(2): 152-160.

[17]譚菊. 基于Kalman濾波的目標軌跡預測[J]. 重慶文理學院學報, 2009, 28(5): 28-29. TAN Ju. Target Track Prediction Based on Kalman Filter[J]. Journal of Chongqing University of Arts and Sciences, 2009, 28(5): 28-29. (in Chinese)

[18]SINHA A, KIRUBARAJAN T, BAE-SHALORM Y. Application of the Kalman-Levy Filter for Tracking Maneuvering Targets[J]. 2007, 43(3): 1099-1107.

[19]趙其杰, 屠大維, 高健. 基于Kalman濾波的視覺預測模板跟蹤及其應用[J]. 光學精密工程, 2008, 16(5): 937-941. ZHAO Qijie, TU Dawei, GAO Jian. Kalman Filter Based Vision Predicting and Object Tracking Method and its Application[J]. Optics and Precision Engineering, 2008, 16(5): 937-941. (in Chinese)

[20]陳少華, 閆鈞華, 朱智超, 等. 基于 Kalman濾波和自適應模板的目標相關跟蹤研究[J]. 電子設計工程, 2011, 19(23): 189-191. CHEN Shaohua, YAN Junhua, ZHU Zhichao, et al. Correlation-based Target Tracking Algorithm Based on Kalman Prediction and Adaptive Template[J]. Electronic Design Engineering, 2011, 19(23): 189-191. (in Chinese)

A Fast Method of Template Matching

LI Chao YU Fei KANG Xiaojun

（Beijing Institute of Mechanics & Electricity, Beijing 100094, China）

Accurate motion predicting and quick positioning of moving target in video images are mainly studied in this paper. In order to it is required that provide credible position data and motion parameters of target in electro-optical tracking control system, the electro-optical tracking and control system should have a faster response. The shorter the response time of the tracking system is, the better the real-time performance of the system is. Therefore, a fast and accurate algorithm of target tracking is very important. Aracking control system of high frame rate limits the computing time of image processing. It is difficult to take into real time and calculation cost account. The simultane-ously traditional target tracking methods are difficult to apply. To solve this problem, a template matching method based on Kalman filter is proposed in this paper. The target motion model is established, and the Kalman filtering process and measure equations are given. During tracking, the target motion data received in current frame are used in filtering processing and predicting the motion parameters of target in the next frame. This method can use matching value to modify the predicted values, the parameters of system model and statistics noise at the same time, which makes sure the speed of calculation and the accuracy of tracking. The advantages of this method are to abandon the blind searching for target, ensure the target tracking algorithm more individualized, make sure both accuracy of tracking and reduction of time.Through many test of moving target, the simulation results show that the novel algorithm has the cap ability of real time and adapting to changes of environment.

target tracking; template matching; Kalman filter; Kalman prediction

TP751

: A

: 1009-8518(2016)01-0063-08

10.3969/j.issn.1009-8518.2016.01.008

李超，男，1989年生，現(xiàn)在中國空間技術研究院光學工程專業(yè)攻讀碩士學位。研究方向為精密光電儀器控制技術。E-mail：IhIc2992650@163.com。

（編輯：劉穎）

2015-07-19