基于混沌優化和二值互信息的快速模板匹配

田 斐，李海軍

(1.南陽理工學院電子系，河南 南陽 473004;2.中國電工技術學會，北京 100823)

0 引言

模板匹配技術是數字圖像處理領域的一項重要研究，已在計算機視覺、虛擬現實、場景生成、航空航天遙感測量、醫學影像分析、光學和雷達跟蹤、景物制導等領域得到了廣泛的應用。模板匹配技術可以分成基于灰度的方法以及基于特征的方法兩大類。

基于灰度的方法簡單易行，但是，此類方法普遍存在的缺陷是精度不高，對圖像尺寸、光照敏感等。常用的這類算法主要有歸一化交叉相關算法(NCC)，序貫相似性檢測(SSDA)等。文獻［1］提出了一種新的基于圖像灰度值編碼表示的方法，但該方法沒有對模板T不能與搜索圖S完全匹配的情況給出解決方案。文獻［2］提出了一種順序排除算法及其多級算法MSEA，但實驗表明，MSEA算法選擇合適的閾值Tn對計算量影響較大，閾值如果過小，則得不到準確的匹配結果;而太大，又會增加匹配運算量。文獻［3］在積分圖像基礎上，提出了應用平方積分圖像的方法，實現了一種計算速度與圖像窗口大小無關的快速灰度均值和方差算法，但該方法同樣對灰度變化敏感，匹配結果魯棒性很差。文獻［4］提出了變形模板和AAM反向合成算法用于模板匹配，由于變形模板和AAM等算法是梯度算法，很容易受到圖像中噪聲、遮擋和光照等因素的影響，而導致匹配失敗。

本文提出一種新的基于改進變尺度混沌優化和二值互信息的模板匹配算法，算法主要內容是:1)對互信息的計算方法進行了改進，就120×40的模板而言，新的互信息計算量減少為原來的1/14.7;2)對EMSCOA算法［5］進行改進，并將其應用到匹配值的尋優過程中，就模板匹配而言，改進后算法收斂時間是原算法的1/9。大量實驗表明本文所提算法能夠有效地克服傾斜、形變、遮擋等干擾，計算量小，收斂速度快。

1 基于互信息的模板匹配

互信息是信息理論中的一個基本概念，通常用于描述兩個系統間的統計相關性。假定X，Y為離散的隨機變量，如果H(X|Y)表示已知系統Y時X的條件熵，那么H(X)與H(X|Y)的差值，就代表了系統Y中所包含的X的信息，即互信息定義為

如果隨機變量X的熵為

X，Y的聯合熵為

互信息模板匹配算法具有匹配精度高，魯棒性強，抗遮擋等諸多優點，因此成為模板匹配領域事實上的準則［6－7］，特別是近年來，互信息在圖像分割領域也取得了成功的應用［8－9］。一般情況下，互信息的計算量為

圖像的二值化有很多種方法，針對不同的目的，選擇的二值化方法也不同。在圖像分割領域，圖像二值化的目的是為了把圖像分割為有意義的區域;在特征提取領域，二值化的目的是提取出角點、線段、邊緣等特征。在本文中，二值化的方法是為了減少互信息的計算量，為保證結果的魯棒性，應要求二值化后的圖像能夠保留原圖像的絕大部分局部特征。因此，圖像分割和特征提取中使用的二值化方法一般不能滿足本文的要求。為此，作者提出了基于二維插值理論的Lagrange算子，后來發現OPENCV提供的cvAdaptiveThreshold函數可以滿足這一要求，另外，將OPENCV提供的canny邊緣檢測算子的閾值設為一個較小的值，也能滿足這一要求，因此，這里就不再贅述作者的Lagrange算子了。

2 新的改進的變尺度混沌優化算法(EMSCOA)

互信息配準一般使用Powell算法來加快尋優速度，但Powell算法是一種局部尋優算法，而互信息的分布是多峰值的，因此難以找到最優值。文獻［5］提出了一種改進的變尺度混沌優化算法(EMSCOA)，該算法比模擬退火算法、遺傳算法、蟻群算法等其他一些尋優算法的尋優能力更強，文獻［10］將該算法應用到攝像機的自標定中，達到了實時的攝像機自標定效果。

EMSCOA算法主要使用兩個循環，外循環用來縮小尋優區域，內循環用來在給定區域內尋優。本文詳細研究了該算法，發現其主要思想是通過縮小搜索區間來找到最優值，應該具有較強的局部搜索能力，雖然這樣做能夠加快收斂速度，但算法仍舊具有以下缺點:

1)在最好的情況下，算法需要計算目標函數M*A次，最壞的情況下，算法需要計算目標函數M*N次，其中M表示外循環次數，N表示內循環次數，A是一個閾值，表示內循環中設定的搜索到較優值的次數，由于A和N差別較大，因此算法的運行時間不確定性太強，導致算法在一些實時應用中不能很好地發揮作用;

2)在EMSCOA算法中，隨著搜索次數的增加和搜索區間的減小，當前最優和全局最優的差值會越來越小，因此搜索到較優值的次數大于等于A的概率會越來越小。此時，由于“搜索到較優值的次數大于等于A”這一條件得不到滿足，所以內循環會在一個很小的尋優區間內達到其執行次數的極大值N，這就導致算法不能快速收斂。

實際上，由于EMSCOA算法中閾值A較小(這是文獻［5］的建議)，所以，算法往往在大的區間進行較少次的混沌尋優，而在小區間卻進行了較多次、甚至N次的混沌尋優，這就是該算法的運行時間瓶頸和最大的缺點。綜上所述，這些缺點導致本文將其應用到的模板匹配中時，匹配成功率幾乎為零。

為了解決這個問題，本文針對以上缺點，再次對EMSCOA算法進行改進，改進后的算法稱為 EEMSCOA，算法的主要思想是在大區間進行多次搜索，小區間進行較少次搜索。算法實現形式上仍舊是采用兩個循環，外環用來縮小尋優區間，內環用來在給定區域尋優，相對文獻［5］，本文算法主要的改進有:

1)本文算法設閾值A為一個較大的值，將A設為一個較大的值有兩個好處，一是可以加大在大區間的尋優次數，二是可以避免搜索區間在混沌優化初期，由于搜索不充分而造成的不恰當的縮小(即恰好將全局最小值排除在新區間之外);

2)設A為一個較大的值，將會導致算法收斂速度慢，為了克服這個缺點，本文采用遞減內循環次數N這一策略，加速算法的收斂。

本文算法既避免了文獻［5］算法可能收斂到局部極值的缺點，又減少了算法調用目標函數的次數，從而減小了運算量。文中使用幾百幅圖片，做了幾百次模板匹配的實驗，結果表明，針對模板匹配問題，本文算法所花費的時間大約是文獻［5］算法的1/9，見表1。

表1 本文EEMSCOA算法和文獻［5］算法在模板匹配中的對比Table 1 Comparison of EEMSCOA in this paper and EMSCOA in paper［5］

EEMSCOA算法主要步驟如下:

1)初始化，分別設置外循環數N和內循環次數M，優化變量區間為［ai，bi］;

2)在(0，1)區間隨機取 i個相異的初始值 xi，1，令，找到較優值的次數 time=0，設目標函數的初始值f*(x)為一較大的數，設定搜索到較優值的次數為A;

3)對于 m=1:M 和 n=1:N*exp(－m+1)，把xi，n分別映射到所對應的定義域中ai);

5)將 xi，n代入 Logistic 式中:=4xi，n(1－xi，n);

6)令 xi，n=，n=n+1，如果 n

8)m=m+1，如果 m

9)滿足搜索停止條件，從最小f*(x)中得到最優參數值。

為了能夠快速地找到二值互信息的最佳匹配點，將EEMSCOA算法引入到二值互信息匹配中。文中用到的模板大小為120×40，原圖大小為752×480，EEMSCOA算法的尋優參數為兩個離散整數量，取值范圍分別為［0，652］，［0，440］;算法中的其他參數 i=2，M=10，N=800，A為大于30的任意值，大量實驗證明新的EMSCOA算法在模板匹配中收斂到最優值附近的概率大于99%(見表1)。

3 實驗結果

將本文提出的新算法應用到基于立體視覺的自動焊接中，立體視覺系統采用了兩個同樣型號的維視MV－VD036SM黑白工業攝像機，分辨率為752×480;選擇模板大小為120×40，如圖1所示。為了提高定位的速度，這里使用了立體視覺中的共極線約束，即:如果點A和點B是同名像點，則校正后的像點A，B一定位于同一條極線上。利用這一原理，可以首先在左(右)圖上尋找到像點A(B)，然后，利用共極線約束，在右(左)圖的對應極線上尋找點B(A)，即可完成同名像點對的尋找。為簡單明了，下文只給出左圖上像點A的尋找結果。

圖1 實驗用到的模板Fig.1 The module used in experiment

圖2、圖3為攝像機傾斜時的匹配結果，圖4、圖5為攝像機水平移動和光線變化時的匹配結果。為了進一步驗證算法的抗噪聲能力，在特征點附近添加一較嚴重的人工噪聲，算法的檢測結果如圖6所示。從實驗結果看，算法用一個模板分別在不同角度、不同光照、不同傾斜角和遮擋噪聲的情況下對圖像進行匹配，匹配精度都比較高，匹配結果表明本文算法能夠有效地克服光照、形變、噪聲等影響，具有較強的魯棒性和穩定性。文中還做了其他大量的模板匹配實驗，結果同樣表明本文算法的有效性，限于篇幅，這里不再具體說明。

圖2 攝像機向右傾斜時的檢測結果Fig.2 Detected result when camera tilts to right

圖3 攝像機向左傾斜時的檢測結果Fig.3 Detected result when camera tilts to left

圖4 光源傾斜時的檢測結果Fig.4 Detected result when the light source tilts

圖5 攝像機平移后的檢測結果Fig.5 Detected result when camera moves horizontally

圖6 在圖5中添加人工噪聲時的檢測結果Fig.6 Detected result with added artificial noise

4 結論及存在的問題

互信息匹配是一種統計相關的非參數匹配方法，其魯棒性強，匹配結果穩定，本文的創新點在于:1)文中針對最大互信息匹配計算量大的問題，提出了相應的二值圖像的互信息匹配，有效減少了算法的計算量;2)為了加快最大互信息值的尋找，對EMSCOA算法進行了改進，使得算法針對模板匹配這一問題的尋優速度比原算法提高了約9倍。以焊接實驗為代表的大量模板匹配實驗，證明了本文所提算法能夠有效地克服傾斜、形變和遮擋等干擾，具有較強的實時性和準確性。

存在的問題:針對文獻［5］中的5個典型復雜測試函數，比較本文提出的新的改進的變尺度混沌優化算法和文獻［5］算法，結果表明兩種算法的結果很近似，但本文算法在模板匹配這一領域卻大大領先于文獻［5］算法，初步的解釋是基于二值互信息的模板匹配問題的解域是離散的，文獻［5］算法不適合處理這種情況，更詳細的解釋需要進一步的討論。

［1］LI Qiang，ZHANG Bo.A fast matching algorithm based on image gray value［J］.Journal of Software，2006，17(2):216-222.

［2］楊靜，丘江，劉波.MSEA及其在模板匹配中的應用［J］.光子學報，2001，30(4):451-454.

［3］邵平，楊路明，黃海濱，等.基于積分圖像的快速模板匹配［J］.計算機科學，2006，133(12):225-229.

［4］劉繼敏，王偉，史忠植.一個新的變形模板匹配方法［J］.計算機學報，1999，22(4):359-363.

［5］鄒恩，陳建國，李祥飛.一種改進的變尺度混沌優化算法及其仿真研究［J］.系統仿真學報，2006，18(9):2426-2428.

［6］VANDENELSEN P A，POL E J D，VIERGEVER M A，et al.Medical image matching a review of classification［J］.IEEE Engineering in Medical and Biology，1993，12(1):26-39.

［7］劉松濤，楊紹清.圖像配準技術研究進展［J］.電光與控制，2007，14(6):99-105.

［8］閔小平，王博亮，戴培山，等.基于主動形變模型的醫學序列圖像的分割［J］.系統仿真學報，2007，19(22):5331-5335.

［9］呂慶文，陳武凡.基于互信息量的圖像分割［J］.計算機學報，2006，29(2):296-300.

［10］劉丁，吳雄君，楊延西，等.基于改進變尺度混沌優化的自標定位置視覺伺服［J］.自動化學報，2008，34(6):623-631.