遺傳算法對圖像模板匹配的優化

劉德華 呼家龍

（馬鞍山職業技術學院，安徽 馬鞍山 243000）

遺傳算法對圖像模板匹配的優化

劉德華 呼家龍

（馬鞍山職業技術學院，安徽 馬鞍山 243000）

本文分析了常見標志物的特征模板匹配過程，并通過遺傳算法對十字絲匹配進行優化，在給定參數下，繪制了平均適應度和最大適應度曲線。通過固定代數和不固定代數情況下的實驗，分析匹配結果值，得出遺傳算法對模板匹配有極強的全局尋優能力，能夠大大減少匹配計算量。

圖像處理；模板匹配；遺傳算法

圖像模板匹配在圖像處理的研究中是一個很重要的研究方向，在機器識別的過程中，常需要把不同傳感器在不同時間，不同成像條件下對同一景物獲取的兩幅或是多幅圖像在空間上對準，或是根據己知的模式到另一幅圖找到相應的模式，這就需要用到圖像匹配。圖像匹配就是將模板與待檢測的圖像進行比較匹配，并給出一個描述匹配程度的計算結果。如果算法的運算結果顯示圖像中的某一部分與模板相同或是相似性大于設定的閾值，則認為匹配成功[1][2]。

1 常見標志物模板匹配方法

1.1 標志物選擇

研究特定目標運動時，常在目標的某些位置貼上特定的識別標志，其中最簡單的標志是圓標志和十字絲標志，如圖1所示。然后根據目標的已知特征，建立相應的數學模型，最后用模式識別方法對目標特征進行提取和匹配。這種方法稱為模式識別匹配跟蹤法。其主要優點是：可靠性較高，受背景環境干擾小，計算量小等[3]。

圖1 標志物

1.2 圓標志的識別定位法

以下是一種對圓標志識別定位算法的主要步驟：

1.2.1 對圖像進行預處理，如濾除噪聲，線性增強；

1.2.2 對圓標志進行二值化或提取邊緣，得到圖像中可能目標的特征，如區域的面積S和周長L；

1.2.3 根據得到的目標特征對目標進行模式識別，并用亞像素方法定位。

1.3 十字絲標志的識別與定位

對十字絲標志進行識別與定位通常可采用如下步驟：

1.3.1 對圖像進行預處理，如濾除噪聲，線性增強；

1.3.2 對圖像進行分割，得到二值目標，然后用Hough變換檢測十字絲兩交叉直線的方位，可以對二值目標進行濾波和細化運算來減少運算量；

1.3.3 以兩條直線的交點為十字絲的粗略搜索區域中心點，選取一個搜索區域，然后根據十字絲的角度和線寬度制作理想的相關模板，在目標搜索區域進行亞象素相關運算對目標進行亞像素定位。

1.4 十子線的灰度投影法匹配規則

根據圖像特征(十字線)，對模板圖像分別進行在 x、y 方向的灰度投影。 圖 2（a）、2（b）分別是投影曲線的斜率圖，此圖的特征非常明顯。對投影圖像進行數值處理，求出投影曲線斜率最大值及其所在位置，構成特征向量CT[TxV，TxP，TyV，TyP]。其中：CTxP和CTxP為模板圖像在x向投影的最大值及其所在位置；CTyP和CTyP為模板圖像在y向投影的最大值及其所在位置；然后對原圖像中左上角坐標為（i，j），大小為模板T的子圖像Sij進行相同的運算，求出其特征向量CS[SxV，SxP，SyV，SyP]。其中 SxV 和 SxP 為子圖像在x向投影的最大值及其所在位置；SyV和SyP為子圖像在y向投影的最大值及其所在位置。定義匹配距離為：

距離最小且小于閾值者即為匹配點。運算中，首先進行x向的距離運算，若結果小于閾值，再進行y向的距離運算；否則，認為此處為非匹配點，搜索下一個子圖像。這樣，就加快了搜索速度。因匹配過程是根據圖像的特征進行的，而不是簡單的像素灰度差值判斷，故適應于一定的噪聲、縮放、旋轉和變形圖像。

圖2 （a）模版圖像垂直投影梯度

圖2 （b）模版圖像水平投影梯度

2 遺傳算法優化

在灰度投影法匹配過程中，如果采用逐點匹配，計算量很大。遺傳算法是非常出色的優化算法。

遺傳算法是模仿自然界生物進化機制發展起來的隨機全局搜索和優化方法，它借鑒了達爾文的進化論和孟德爾的遺傳學說。其本質是一種高效、并行、全局搜索的方法，它能在搜索過程中自動獲取和積累有關搜索空間的知識，并自適應地控制搜索過程以求得最優解。遺傳算法操作使用適者生存原則，在潛在的解決方案種群中逐次產生一個近似最優的方案。在遺傳算法的每一代中，根據個體在問題域中的適應度值和從自然遺傳學中借鑒來的再造方法進行個體選擇，產生一個新的近似解。這個過程導致種群中個體的進化，得到新個體比原個體更能適應環境，就像自然界中的改造一樣[4]。

2.1 遺傳算法特點

遺傳算法是一類可用于復雜系統優化計算的魯棒搜索算法，與傳統的優化算法相比，它有以下特點：

2.1.1 傳統的優化算法往往利用決策變量的實際值本身來進行優化計算，但是遺傳算法并不是直接利用決策變量的值，而是以決策變量的編碼作為研究對象。

2.1.2 傳統的算法不僅需要目標函數值，而且往往需要目標函數值的導數等其它一些輔助信息才能確定搜索方向。而遺傳算法直接以目標函數值作為搜索信息，具有通用性。

2.1.3傳統的優化方法往往是從解空間中的一個初始點開始最優解的迭代搜索過程。

2.1.4 傳統的算法使用是確定的搜索方法，遺傳算法屬于一種自適應概率搜索技術。

2.1.5 全局最優性，魯棒性，兼容性。

2.2 遺傳算法基本過程

圖3是遺傳算法的基本過程[7]。

圖3 遺傳算法的基本過程

不同的編碼方案、選擇策略和遺傳算子相結合構成了不同的遺傳算法，但不同遺傳算法在計算中的迭代過程大體相同，都包含了編碼、選擇、交叉、變異和解碼等五個階段[5][6]。

2.3 遺傳算法優化流程[7]

2.3.1 對模板圖像 進行 方向的灰度投影，生成特征向量 ；

2.3.2 對待匹配空間 生成初始種群，即初始化待匹配點；

2.3.3 根據待匹配點確定待匹配子圖像 ，求出其特征向量 CS[SxV，SxP，SyV，SyP]，及與 TS 的匹配距離D[SM，TS]，從而求出群體的適應度；

2.3.4 對該群體進行最優保存的選擇操作；

2.3.5 進行交叉和變異操作；

2.3.6 計算群體的適應度；

2.3.7 若符合匹配條件就結束，求出匹配點；否則，返回3)繼續進行。

3 匹配計算量分析

在主頻1.7G、1G內存的酷睿雙核主機上，用Matlab編寫測量軟件，進行實驗。待匹配圖像為CCD采集到的現場實驗圖像，大小為640×480，模板圖像為從中取出的76×76的包含十字線定位特征的圖像。

傳統自相關匹配中由歸一化相關函數知：對M×N的模板圖像，計算1次相關函數需要的計算量約為 3×M×N×4（4 次減法+1 次乘法）；而對相同大小的子圖像進行1次灰度投影所需要的計算量約為2×M×N加法。可見，采用灰度投影大大降低了運算量。

GA能夠大幅度減少圖像匹配中模板匹配的次數。對圖像進行逐點匹配法匹配次數=（640-76+1）×（480-76+1）=228825。 而 GA 相關匹配的匹配次數=~ （進化代數）×（種群數）=（80）×（40）=3200，兩者計算效率比為228825/3200>71倍，可見計算效率有了明顯提高。

4 實驗結果分析

用GA對取自自身的模板進行匹配，初始種群為40，最大代數為80，交叉概率為0.6，變異概率為0.001。在某次匹配過程中其平均適應度如圖4（a）所示，最大適應度曲線如圖 4（b）所示。 圖中，GA的最大值適應度值逐漸變大，種群平均值適應值有一個比較平緩的增長后，出現抖動現象，表明種群的多樣性得到了保持。如果種群快速收斂，則可能造成早熟現象，造成最大適應度解在最優解附近抖動。

圖5 匹配結果

表1 遺傳算法匹配結果

圖5為程序運行時匹配圖像，其中矩形框為匹配的結果，目視情況下，匹配正確。矩形框的左邊十字絲標記是為了試驗誤匹配情況，圖5中沒有出現誤匹配。

為了研究遺傳算法全局尋優能力和早熟現象，在一副圖像上截取模板，然后與此圖像在固定代數和不固定代數情況下分別進行匹配，結果數據如表1。上表結果表明，遺傳算法的全局尋優能力較強，極大的減少了匹配過程中的計算量，通常能在80代內尋找到最優值，但是同時也能看到，由于早熟而出現的抖動現象。這對定位標志物非常不利，有必要在粗定位后進行精確定位。

[1]葉聲華,王仲,楊學友.視覺檢測技術及應用[J].中國工程科學.1999(1):49～52.

[2]王紅梅,張科.圖像匹配研究進展[J].計算機工程與應用.2004 Vol.40 No.19 ：42～44

[3]楊光,田地.基于投影特征的快速圖像匹配方法[J].吉林大學學報(工學版).2010(5)：1340～1344

[4]席裕庚,柴天佑.遺傳算法綜述[J].控制理論與應用.1996(6):697～708

[5]張曉繢,方浩.遺傳算法的編碼機制研究[J].信息與控制.1997(2):55～60

[6]鄭力新.利用遺傳算法實現模板匹配的瓷磚分選[J].華僑大學學報(自然科學版).2010(6):632～635

[7]ZHANG Lei,HU Jia-long,QIAN Ya-ping.Research of Online Weighing System of Molten-iron Based on Image Processing.SPIE Vol.6623:66231F

OPTIMIZATION OF IMAGE TEMPLATE MATCHING BASED ON GENETIC ALGORITHM

LIU De-hua HU Jia-long
(Maanshan Technical College,Maanshan Anhui243000)

This paper analyzes feature template matching process of the common markers,and optimizes the cross-wire matching by genetic algorithm,draws the average fitness and maximum fitness curve under the given parameters.Through experiments under a fixed and not fixed algebraic,analysis of the value of matching results,genetic algorithms have a strong global optimization to match the template and can greatly reduce the amount of matching calculation.

image Processing； template matching；genetic Algorithm

A

1672－2868（2011）03－0057－04

2010-12-16

劉德華（1966-），男，安徽霍邱人。碩士，研究方向：圖形圖像處理

責任編輯：宏 彬