摘? 要: 介紹一種優化的快速模板匹配" title="模板匹配">模板匹配算法,可實現目標實時提取、識別和跟蹤,并成功應用于紅外熱成像" title="紅外熱成像">紅外熱成像跟蹤技術的研究,解決了復雜背景條件下目標跟蹤穩定度差的技術難點。該算法用Visual C++編寫,可方便地移植到其它操作平臺或嵌入式系統。
關鍵詞: 模板匹配? 粗匹配? 精匹配? 亂序匹配? Visual C++
?
紅外熱成像跟蹤技術是一種被動式目標檢測、跟蹤技術,用于對紅外視頻信號進行目標檢測、提取和跟蹤。對比度特征鑒別是比較常用的目標提取方法。它無法記憶、識別目標形態特征,在復雜背景下提取效果、跟蹤穩定性較差。而模板匹配算法以目標特征數據為模板,在搜索區域里尋找匹配點,即以目標形態特征為判據實現目標檢索和跟蹤。即便在復雜背景狀態下,跟蹤靈敏度和穩定度都極高,非常適用于復雜背景下的目標跟蹤。
模板匹配算法由于計算量龐大,應用成本較高。經過多方優化、簡化后,可用工控機實現實時模板匹配處理。在沒有增加成本、耽誤工程進度的前提下,增強了復雜背景下的跟蹤靈敏度和穩定度,提高了產品的綜合競爭能力。為模板匹配算法的低成本應用開辟了一條新路。
????本文介紹的模板匹配算法在Windows 2000下用Visual C++編制,可方便地移植到多種操作平臺。
1 模板匹配原理
模板匹配是數字圖像處理的重要組成部分之一。把不同傳感器或同一傳感器在不同時間、不同成像條件下對同一景物獲取的兩幅或多幅圖像在空間上對準,或根據已知模式到另一幅圖中尋找相應模式的處理方法就叫做模板匹配。
假設要在搜索區域中尋找與模板圖像相關程度最大" title="最大">最大的位置,可以通過模板匹配來計算兩者的相關程度。圖1是模板匹配算法的示意圖。假設模板(b)疊放在搜索圖(a)上平移,模板覆蓋下的部分記作子圖Si,j,其中i,j是這塊子圖的左上角像點在S圖中的坐標。從圖1中可得出i,j的取值范圍:1≤i≤K-M+1、1≤j≤L-N+1。
?
衡量模板T和子圖Si,j的匹配程度,可用下列兩種測度:
或者
展開前一個式子,有:
(3)式右邊的第三項表示模板的總能量,是一個常數,與(i,j)無關。第一項是模板覆蓋下那塊子圖像的能量,它隨(i,j)位置而緩慢改變。第二項是子圖像和模板的互相關函數,隨(i,j)變化而迅速改變。模板T和子圖Si,j匹配時這一項的值最大,因此可以用下列相關函數來反應匹配程度:
???? 
2 建立數學模型
2.1 計算公式
模板匹配算法計算模板和匹配區域的相似程度,以最相似位置為匹配點。由于模板需要在匹配區域上逐次匹配,運算量很大。所以選擇匹配公式對整個匹配的效率有極大的影響。
工控機的數據處理能力有限,需要針對紅外熱成像跟蹤技術的特點來簡化數學模型" title="數學模型">數學模型,選定計算量最小的計算公式。目標跟蹤算法用來確定目標位置,可以用匹配誤差的相對大小作為目標判別的依據,誤差最小的位置就是目標位置,不需要考慮絕對相似程度。
公式(1)～(5)都能夠真實反應模板的相對匹配程度,選擇計算量最小、效率最高的公式(1)作為原始數學模型。匹配點位置算法完成整個匹配區域內的最小匹配誤差點檢索,表示為公式(6):
??? 
變量K、L為匹配區域尺寸;M、N為模板尺寸。
2.2 模板尺寸
模板尺寸對系統性能和計算量的影響不容小覷。模板過大導致動態特性" title="動態特性">動態特性變差；過小又會減少目標的特征數據量,降低匹配的敏感程度,增大目標檢測難度。實際操作中,模板尺寸設置為32×16時效果非常理想。
2.3 匹配區域
不同的應用環境下,對匹配區域和實時性要求也不盡相同。光電探測設備需要在視頻圖像采集周期內(20ms)完成數據實時處理。由于目標在兩場視頻圖像之間的移動量較小、特征變化不大,匹配區域可以大大縮小。
匹配區域太小會導致目標動態特性變差,過大又會導致計算量大幅度增加,具體選擇需要權衡設備參數來決定。由于CCIR制式視頻信號是隔行掃描,系統出于實時性考慮,數據以場為單位處理,導致圖像比例為2:1狀態。為了保持水平、垂直方向的動態特性一致,圖像匹配區域也按2:1比例選擇。
在滿足實時性要求的情況下,選擇相對較大的匹配范圍,可提高設備的動態特性。從表1實測數據可以看出,選擇匹配區域100×50點、模板32×16點時,動態范圍為69×35,時間消耗為13ms。光電探測設備系統目標動態特性要求處理區域不小于40×20點?？梢娨陨线x擇可以很好地滿足動態特性和實時性要求。
?
?
3 數學模型優化方法
數學模型結合選擇的模板和搜索區域大小,可以知道模板最佳匹配點計算公式如下:
由公式(7)可以看出,程序需要進行大量的循環計算,整體運算量仍然不小,需要進一步優化,減少處理時間。運用如下優化算法進一步減少實際運算量。
3.1 粗精匹配結合
觀察實際模板匹配運算結果可以發現,匹配點附近的匹配誤差迅速下降,明顯區別于其它位置。針對這一特點,采用粗精匹配結合的算法迅速鎖定匹配點大致區域,可大大降低整體匹配次數。
具體實現方法:先跳動著隔幾個點進行一次粗匹配,大致框定匹配區域,然后在附近區域逐一檢索獲得最佳匹配點。運算量可減少到三分之一以下，且目標提取效果相當好。
3.2 限制最大匹配誤差
因為只需找到最小匹配誤差的位置,不必完整計算每一位置的絕對匹配誤差,而以已經計算的最小匹配誤差作為最大允許誤差。若計算誤差大于該最大允許誤差,就肯定不是最佳匹配點,可以提前結束計算,進入下一匹配位置的計算;如果匹配完成后仍小于最大允許誤差,就用當前誤差替換最大允許誤差,并把該點作為潛在的匹配位置記錄下來。
匹配點和非匹配點的誤差常常相差2~3個數量級。經過這種處理后,匹配點后剩余的計算量可以大大降低。
3.3 亂序匹配
目標出現在匹配區域中的位置不確定。不固定順序算法可以更快地檢索到匹配區域,迅速降低最大匹配誤差,減少剩余非匹配點的計算量,降低整體運算量。
針對光電探測設備的實際工作情況,在跟蹤狀態下,目標位移角速度和角加速度有限,導致目標常處于匹配區域中心附近。選擇由中心向周圍輻射匹配的方式效果最理想。
4 程序樣本
以下程序樣本綜合使用了上面的優化算法,成功應用于紅外熱成像跟蹤技術的原理樣機,達到了預期效果。
該函數用于圖像模板匹配運算,適用于256灰度值的黑白圖像數據。
Deal_With：：TemplateMatch(unsigned char* lpSource， LONG lWidth， LONG lHeight，? unsigned char*lpTemplate， LONG
lTemplateWidth，LONG lTemplateHeight，)
{????
???? ?? unsigned char*?????? Source；?????? ? //指向待處理圖像的指針
?????? unsigned char*?????? Template；??????????? //指向模板圖像的指針
?????? int???????????????????????? i，j，m，n； //循環變量
?????? unsigned char??????? lMaxWidth， lMaxHeight，
??????????????????????????????? lMaxWidthExact，lMaxHeightExact
??????????? ????????????????????????????????????? //匹配位置
?????? unsigned long?????? D；?? ?????? //相似誤差
?????? unsigned long?????? MaxD；? //最大允許相似誤差
//粗相關
???? ?? MaxD =0x10000000；???? ??? //約定最大匹配誤差
?????? for (j = 0；j < lHeight - lTemplateHeight +1 ；j+=2){
???? ? for(i = 0；i < lWidth - lTemplateWidth + 1；i+=2){
???????? ?????? D=0；
?????????????????? ?? Source=(unsigned char *)lpSource+lWidth*j+i；
???????????????????? Template=(unsigned char *)lpTemplate ；
???????????????????? for (n=0；n < lTemplateHeight && D ????????????????????????? for(m=0；m ?????????????????????????????????? D+=(*Source++-*Template++)*(*Source++ ????????????????????????????????????? -*Template++)； ??????????????????????????? Source+=lWidth-lTemplateWidth； ???????????????????? } ???????????????????? if (D ???????????????????????? ??? MaxD=D； ??????????????????????????? lMaxWidth=i； ??????????????????????????? lMaxHeight=j； ???????????????????? } ????????????? } ?????? } ?????? //精相關 ?????? lMaxWidthExact = lMaxWidth； ?????? lMaxHeightExact = lMaxHeight； ?????? for (j = lMaxHeight-2；j <= lMaxHeight+2 ；j++){ ???????????for(i = lMaxWidth-2；i <= lMaxWidth+2；i++){ ???????????????????? D=0； ???????????????????? Source=(unsigned char *)lpSource+lWidth*j+i； ???????????????????? Template=(unsigned char *)lpTemplate ； ???????????????????? for(n=0；n ???????????????????? for(m = 0；m < lTemplateWidth && D ???? ??????????????????? D+=(*Source++-*Template++)*(*Source++ ??????????????????????????? -*Template++)； ???????? ???????????? Source+=lWidth-lTemplateWidth； ???????????? } ????????????? if (D ???????????????????? MaxD=D； ???????????????????? lMaxWidthExact=i； ??? ?//x方向最佳匹配點位置 ???????????????????? lMaxHeightExact=j；? //y方向最佳匹配點位置 ???????????????????} ????????????? } ??? ???? } ? } ? ? 參考文獻 1章毓晉. 圖像理解與計算機視覺. 北京：清華大學出版社,2000. 2劉忠偉,章毓晉. 基于特征的圖像查詢和檢索系統. 應用基礎及工程學報,2000:8(1):69～77 3 David J. Kruglinski， Scot Wingo，George Shepherd. 1999.?Programming Visual C++ 6.0技術內幕.北京:北京希望電腦公司出版社，2002