遺傳算法對(duì)圖像模板匹配的優(yōu)化

劉德華 呼家龍

（馬鞍山職業(yè)技術(shù)學(xué)院，安徽 馬鞍山 243000）

遺傳算法對(duì)圖像模板匹配的優(yōu)化

劉德華 呼家龍

（馬鞍山職業(yè)技術(shù)學(xué)院，安徽 馬鞍山 243000）

本文分析了常見(jiàn)標(biāo)志物的特征模板匹配過(guò)程，并通過(guò)遺傳算法對(duì)十字絲匹配進(jìn)行優(yōu)化，在給定參數(shù)下，繪制了平均適應(yīng)度和最大適應(yīng)度曲線。通過(guò)固定代數(shù)和不固定代數(shù)情況下的實(shí)驗(yàn)，分析匹配結(jié)果值，得出遺傳算法對(duì)模板匹配有極強(qiáng)的全局尋優(yōu)能力，能夠大大減少匹配計(jì)算量。

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

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

1 常見(jiàn)標(biāo)志物模板匹配方法

1.1 標(biāo)志物選擇

研究特定目標(biāo)運(yùn)動(dòng)時(shí)，常在目標(biāo)的某些位置貼上特定的識(shí)別標(biāo)志，其中最簡(jiǎn)單的標(biāo)志是圓標(biāo)志和十字絲標(biāo)志，如圖1所示。然后根據(jù)目標(biāo)的已知特征，建立相應(yīng)的數(shù)學(xué)模型，最后用模式識(shí)別方法對(duì)目標(biāo)特征進(jìn)行提取和匹配。這種方法稱為模式識(shí)別匹配跟蹤法。其主要優(yōu)點(diǎn)是：可靠性較高，受背景環(huán)境干擾小，計(jì)算量小等[3]。

圖1 標(biāo)志物

1.2 圓標(biāo)志的識(shí)別定位法

以下是一種對(duì)圓標(biāo)志識(shí)別定位算法的主要步驟：

1.2.1 對(duì)圖像進(jìn)行預(yù)處理，如濾除噪聲，線性增強(qiáng)；

1.2.2 對(duì)圓標(biāo)志進(jìn)行二值化或提取邊緣，得到圖像中可能目標(biāo)的特征，如區(qū)域的面積S和周長(zhǎng)L；

1.2.3 根據(jù)得到的目標(biāo)特征對(duì)目標(biāo)進(jìn)行模式識(shí)別，并用亞像素方法定位。

1.3 十字絲標(biāo)志的識(shí)別與定位

對(duì)十字絲標(biāo)志進(jìn)行識(shí)別與定位通?？刹捎萌缦虏襟E：

1.3.1 對(duì)圖像進(jìn)行預(yù)處理，如濾除噪聲，線性增強(qiáng)；

1.3.2 對(duì)圖像進(jìn)行分割，得到二值目標(biāo)，然后用Hough變換檢測(cè)十字絲兩交叉直線的方位，可以對(duì)二值目標(biāo)進(jìn)行濾波和細(xì)化運(yùn)算來(lái)減少運(yùn)算量；

1.3.3 以兩條直線的交點(diǎn)為十字絲的粗略搜索區(qū)域中心點(diǎn)，選取一個(gè)搜索區(qū)域，然后根據(jù)十字絲的角度和線寬度制作理想的相關(guān)模板，在目標(biāo)搜索區(qū)域進(jìn)行亞象素相關(guān)運(yùn)算對(duì)目標(biāo)進(jìn)行亞像素定位。

1.4 十子線的灰度投影法匹配規(guī)則

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

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

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

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

2 遺傳算法優(yōu)化

在灰度投影法匹配過(guò)程中，如果采用逐點(diǎn)匹配，計(jì)算量很大。遺傳算法是非常出色的優(yōu)化算法。

遺傳算法是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來(lái)的隨機(jī)全局搜索和優(yōu)化方法，它借鑒了達(dá)爾文的進(jìn)化論和孟德?tīng)柕倪z傳學(xué)說(shuō)。其本質(zhì)是一種高效、并行、全局搜索的方法，它能在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自適應(yīng)地控制搜索過(guò)程以求得最優(yōu)解。遺傳算法操作使用適者生存原則，在潛在的解決方案種群中逐次產(chǎn)生一個(gè)近似最優(yōu)的方案。在遺傳算法的每一代中，根據(jù)個(gè)體在問(wèn)題域中的適應(yīng)度值和從自然遺傳學(xué)中借鑒來(lái)的再造方法進(jìn)行個(gè)體選擇，產(chǎn)生一個(gè)新的近似解。這個(gè)過(guò)程導(dǎo)致種群中個(gè)體的進(jìn)化，得到新個(gè)體比原個(gè)體更能適應(yīng)環(huán)境，就像自然界中的改造一樣[4]。

2.1 遺傳算法特點(diǎn)

遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化計(jì)算的魯棒搜索算法，與傳統(tǒng)的優(yōu)化算法相比，它有以下特點(diǎn)：

2.1.1 傳統(tǒng)的優(yōu)化算法往往利用決策變量的實(shí)際值本身來(lái)進(jìn)行優(yōu)化計(jì)算，但是遺傳算法并不是直接利用決策變量的值，而是以決策變量的編碼作為研究對(duì)象。

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

2.1.3傳統(tǒng)的優(yōu)化方法往往是從解空間中的一個(gè)初始點(diǎn)開(kāi)始最優(yōu)解的迭代搜索過(guò)程。

2.1.4 傳統(tǒng)的算法使用是確定的搜索方法，遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)。

2.1.5 全局最優(yōu)性，魯棒性，兼容性。

2.2 遺傳算法基本過(guò)程

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

圖3 遺傳算法的基本過(guò)程

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

2.3 遺傳算法優(yōu)化流程[7]

2.3.1 對(duì)模板圖像 進(jìn)行 方向的灰度投影，生成特征向量 ；

2.3.2 對(duì)待匹配空間 生成初始種群，即初始化待匹配點(diǎn)；

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

2.3.4 對(duì)該群體進(jìn)行最優(yōu)保存的選擇操作；

2.3.5 進(jìn)行交叉和變異操作；

2.3.6 計(jì)算群體的適應(yīng)度；

2.3.7 若符合匹配條件就結(jié)束，求出匹配點(diǎn)；否則，返回3)繼續(xù)進(jìn)行。

3 匹配計(jì)算量分析

在主頻1.7G、1G內(nèi)存的酷睿雙核主機(jī)上，用Matlab編寫(xiě)測(cè)量軟件，進(jìn)行實(shí)驗(yàn)。待匹配圖像為CCD采集到的現(xiàn)場(chǎng)實(shí)驗(yàn)圖像，大小為640×480，模板圖像為從中取出的76×76的包含十字線定位特征的圖像。

傳統(tǒng)自相關(guān)匹配中由歸一化相關(guān)函數(shù)知：對(duì)M×N的模板圖像，計(jì)算1次相關(guān)函數(shù)需要的計(jì)算量約為 3×M×N×4（4 次減法+1 次乘法）；而對(duì)相同大小的子圖像進(jìn)行1次灰度投影所需要的計(jì)算量約為2×M×N加法?？梢?jiàn)，采用灰度投影大大降低了運(yùn)算量。

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

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

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

圖5 匹配結(jié)果

表1 遺傳算法匹配結(jié)果

圖5為程序運(yùn)行時(shí)匹配圖像，其中矩形框?yàn)槠ヅ涞慕Y(jié)果，目視情況下，匹配正確。矩形框的左邊十字絲標(biāo)記是為了試驗(yàn)誤匹配情況，圖5中沒(méi)有出現(xiàn)誤匹配。

為了研究遺傳算法全局尋優(yōu)能力和早熟現(xiàn)象，在一副圖像上截取模板，然后與此圖像在固定代數(shù)和不固定代數(shù)情況下分別進(jìn)行匹配，結(jié)果數(shù)據(jù)如表1。上表結(jié)果表明，遺傳算法的全局尋優(yōu)能力較強(qiáng)，極大的減少了匹配過(guò)程中的計(jì)算量，通常能在80代內(nèi)尋找到最優(yōu)值，但是同時(shí)也能看到，由于早熟而出現(xiàn)的抖動(dòng)現(xiàn)象。這對(duì)定位標(biāo)志物非常不利，有必要在粗定位后進(jìn)行精確定位。

[1]葉聲華,王仲,楊學(xué)友.視覺(jué)檢測(cè)技術(shù)及應(yīng)用[J].中國(guó)工程科學(xué).1999(1):49～52.

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

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

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

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

[6]鄭力新.利用遺傳算法實(shí)現(xiàn)模板匹配的瓷磚分選[J].華僑大學(xué)學(xué)報(bào)(自然科學(xué)版).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-），男，安徽霍邱人。碩士，研究方向：圖形圖像處理

責(zé)任編輯：宏 彬