傅超斌，南開來

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

基于改進(jìn)遺傳算法的圖像匹配定位

傅超斌，南開來

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

為了提高彩色圖形匹配效率，提出一種針對(duì)大圖搜索匹配的改進(jìn)遺傳算法搜索策略。針對(duì)圖像匹配問題的特點(diǎn)，以及根據(jù)遺傳算法的優(yōu)化策略，對(duì)其初始種群及交叉變異操作進(jìn)行改進(jìn)，從而加快圖形匹配定位速度，提高其結(jié)果的可靠性。

遺傳算法；優(yōu)化策略；圖像匹配定位

0 引言

遺傳算法在邊界搜索(Blind Search)、組合優(yōu)化(Combine Optimization)、機(jī)器學(xué)習(xí)(Machine Learning)領(lǐng)域有不少的應(yīng)用[1]。圖像匹配是計(jì)算機(jī)視覺的一個(gè)關(guān)鍵技術(shù)，遺傳算法搜索法是圖像匹配中一種常用的搜索法，通過圖像匹配可以快速確定待匹配大圖像中是否有目標(biāo)圖像，若有則可同時(shí)確定其位置。

1 遺傳算法的基本原理[2]

1.1 遺傳算法概念

遺傳算法(Genetic Algorithm，GA)是模擬生物進(jìn)化過程的遺傳選擇和自然淘汰的計(jì)算模型，是由美國學(xué)者Holland于1975年首先提出[3]。其基本思想很簡單：一個(gè)原始問題的參數(shù)被轉(zhuǎn)換成一些基因編碼，通常被表示為二進(jìn)制染色體。初始的染色體個(gè)體都是隨機(jī)生成的，然后根據(jù)一些標(biāo)準(zhǔn)來評(píng)判其個(gè)體的適應(yīng)度。個(gè)體適應(yīng)度的優(yōu)劣決定了其染色體繼續(xù)影響搜索的機(jī)會(huì)。適應(yīng)度越優(yōu)的個(gè)體也越有可能被選擇作為創(chuàng)建下一代的一部分，通過不同個(gè)體間的隨機(jī)信息交換，使得優(yōu)秀個(gè)體不斷被保留遺傳，從而不斷產(chǎn)生更優(yōu)的染色體。后代繼承了直系祖先的大部分基因信息，且整體優(yōu)于祖先群體，進(jìn)而使其種群不斷往優(yōu)發(fā)展。

1.2 理論基礎(chǔ)

Holland提出的模式定理奠定了遺傳算法的數(shù)學(xué)基礎(chǔ)，其數(shù)學(xué)表達(dá)形式為：

(1)

積木塊假設(shè)：由模式定理可看出，具有低階、短定義矩以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將以指數(shù)級(jí)增長。而通過短定義矩、低階以及高平均適應(yīng)度的模式，在遺傳操作下接近全局最優(yōu)解，即積木塊假設(shè)。

1.3 基本遺傳算法

基本的遺傳算法根據(jù)問題選擇編碼方式，把參數(shù)集合域映射到位串空間；確定適應(yīng)度函數(shù)；確定種群規(guī)模N、交叉概率Pc和變異概率Pm等算法參數(shù)。主要有以下幾個(gè)步驟：(1)初始化隨機(jī)生成的初始種群；(2)根據(jù)適應(yīng)度函數(shù)，計(jì)算種群個(gè)體適應(yīng)度；若已達(dá)最大迭代次數(shù)，則跳出結(jié)束遺傳算法，否則繼續(xù)執(zhí)行；(3)執(zhí)行輪盤賭選擇操作；(4)根據(jù)交叉算子生成新的后代；(5)根據(jù)變異算子對(duì)新后代進(jìn)行變異操作，然后重新執(zhí)行步驟(2)。

圖1 基本遺傳算法流程圖

算法流程圖如圖1所示。

2 算法應(yīng)用[4-5]

2.1 匹配問題描述

假設(shè)搜索圖為N×M像素的圖像P和n×m像素的模板T，令Pij為以(i,j)為左頂點(diǎn)坐標(biāo)的n×m像素的子圖。圖像匹配搜素即通過在待搜索圖P中移動(dòng)n×m像素的模板T尋找與T一致的子圖Pij，可用類間方差來衡量其模板T和子圖Pij之間的相似度判別函數(shù)：

(2)

采用歸一化衡量相似度判別函數(shù)：

(3)

其中0≤Z(i,j)≤1，Z(i,j)越大表示其子圖Pij與模板T的相似程度越高，當(dāng)Z(i,j)=1時(shí)，Pij與T完全匹配。

2.2 優(yōu)化改進(jìn)策略

遺傳算法的主要操作就是選擇、交叉、變異，因此這三個(gè)步驟是主要優(yōu)化的方向；同時(shí)，對(duì)于具體的問題，初始化種群的選擇也是一個(gè)關(guān)鍵。

(1)優(yōu)化初始種群：對(duì)于無先驗(yàn)知識(shí)的搜索匹配問題，基本遺傳算法是采取完全隨機(jī)生成初始種群，此方法得到的種群隨機(jī)性太強(qiáng)，所擁有的最優(yōu)信息少。本文針對(duì)模板目標(biāo)快速定位的問題，采用離散間隔中心點(diǎn)法來提高搜索定位效率，即將初始點(diǎn)按照n×m像素的模板T大小作為最小間隔尺度生成種群個(gè)體，以增加可行域覆蓋率。

(2)優(yōu)化選擇操作：對(duì)于大圖搜索單一目標(biāo)來說，在保持快速收斂的同時(shí)需要保證種群的多樣性，因此在選擇過程中，高于一定適應(yīng)度閾值Th的個(gè)體可以直接選擇保留加入交叉變異后代，低于一定適應(yīng)度閾值Tl的個(gè)體直接淘汰。為了確保種群多樣性，保持高于適應(yīng)度閾值Th的較優(yōu)個(gè)體不大于1/3種群規(guī)模，如果大于這個(gè)上限，將部分個(gè)體重置為隨機(jī)生成的新個(gè)體。

(3)優(yōu)化交叉操作：根據(jù)全圖搜索的單目標(biāo)稀疏性特點(diǎn)，將低于適應(yīng)度閾值Tl的個(gè)體由1/5較優(yōu)個(gè)體中某兩條交叉生成，從而使其能夠快速收斂，交叉段數(shù)為2段，交叉點(diǎn)位隨機(jī)生成，增加交叉的可能性。

選擇交叉方式示意圖如圖2所示。

圖2 選擇交叉操作示意圖

(4)優(yōu)化變異操作：根據(jù)全圖搜索的規(guī)律，可知當(dāng)適應(yīng)度大于一定值時(shí)，很可能此個(gè)體已經(jīng)在標(biāo)準(zhǔn)圖附近，因此調(diào)整其變異區(qū)間，將其左頂點(diǎn)坐標(biāo)(x,y)變異范圍控制在x1-n≤x≤x1+n和y1-m≤y≤y1+m，其中(x1,y1)為當(dāng)前個(gè)體左頂點(diǎn)坐標(biāo)，從而提高變異的可靠性。當(dāng)種群整體優(yōu)于Th的比例大于2/3時(shí)，將其部分進(jìn)行隨機(jī)化變異，從而確保種群的多樣性。

2.3 問題建模

首先，將N×M像素按照二進(jìn)制編碼分別將坐標(biāo)(x,y)編碼長度定為：lx=log2N+1和ly=log2M+1。其次，適應(yīng)度函數(shù)使用歸一化的類間方差Z(x,y)作為個(gè)體適應(yīng)度評(píng)判標(biāo)準(zhǔn)，將模板圖與實(shí)際個(gè)體圖像素點(diǎn)的ARGB值作為計(jì)算類間方差的參數(shù)，從而實(shí)現(xiàn)對(duì)彩色圖的匹配定位。最后，確定迭代次數(shù)Dt、交叉概率Pc和變異概率Pm。

3 實(shí)驗(yàn)示例及結(jié)果

本文實(shí)驗(yàn)采用的是仿真足球機(jī)器人界面的足球圖形以及隊(duì)員圖形，示例使用黃底棕色三角形、粉底綠色倒三角形、灰底藍(lán)色球分別表示A球隊(duì)隊(duì)員、B球隊(duì)隊(duì)員以及足球，以此來模擬標(biāo)識(shí)一個(gè)足球機(jī)器人界面。用不同的顏色作為區(qū)別，后期采集到的圖像根據(jù)此標(biāo)準(zhǔn)圖片來進(jìn)行分析快速定位，即圖片快速匹配定位。

3.1 實(shí)驗(yàn)示例

圖3所示是一個(gè)實(shí)驗(yàn)demo，測試軟件界面可選擇遺傳算法的一些基本參數(shù)：迭代次數(shù)、交叉率、變異率、種群規(guī)模；根據(jù)下拉框的選擇來確定需要尋找匹配的圖片類型，其中當(dāng)匹配定位到一張圖片時(shí)，將其圖片標(biāo)記并顯示GA搜索耗時(shí)，以及定位到的位置坐標(biāo)點(diǎn)。示例中的輸入坐標(biāo)點(diǎn)代表的是待匹配定位圖實(shí)際位置，找到的最優(yōu)坐標(biāo)代表的是實(shí)際匹配定位到的位置。

3.2 實(shí)驗(yàn)結(jié)果

在同樣GA參數(shù)，迭代次數(shù)為500，交叉率0.8，變異率0.05，種群規(guī)模100代的情況下，得到的基本遺傳算法和改進(jìn)遺傳算法的結(jié)果比較如表1。

圖3 實(shí)驗(yàn)示例

算法實(shí)驗(yàn)次數(shù)單個(gè)平均匹配時(shí)間/s正確匹配次數(shù)匹配精度/%基本遺傳算法505.12836.0改進(jìn)遺傳算法500.3624692.0

從實(shí)驗(yàn)結(jié)果可以看到，改進(jìn)的遺傳算法匹配定位效率明顯要高于基本遺傳算法。

4 結(jié)論

本文通過改進(jìn)的遺傳算法實(shí)現(xiàn)了快速圖片匹配定位，根據(jù)遺傳算法的特點(diǎn)，優(yōu)化了初始種群選擇策略、交叉策略以及變異策略，在快速收斂的同時(shí)保證了種群的多樣性。實(shí)驗(yàn)示例結(jié)果表明，這些策略的改進(jìn)有效地提高了其搜索效率，改善了其搜索的可靠性。

[1] ROOKER T. Review of genetic algorithms in search, optimization, and machine learning[J].AI Magazine, 1991, 12(1):102-103.

[2] 金希東.遺傳算法及其應(yīng)用[D].成都：西南交通大學(xué),1996.

[3] HOLLAND J H.Adaptation in natural and artificial systems[D]. MIT Press, 1992.

[4] 朱紅, 趙亦工. 基于遺傳算法的快速圖像相關(guān)匹配[J]. 紅外與毫米波學(xué)報(bào), 1999,2(2):145-150.

[5] 嚴(yán)國榮, 趙亦工. 基于改進(jìn)的遺傳算法的快速圖像相關(guān)匹配技術(shù)[J]. 電訊技術(shù), 2002, 42(5):96-99.

Image matching and location based on improved genetic algorithm

Fu Chaobin, Nan Kailai

(College of Computer, Hangzhou Dianzi University, Hangzhou 310018, China)

In order to improve the efficiency of color image matching, an improved genetic algorithm search strategy is proposed. According to the characteristics of the image matching problem, and according to the optimization strategy of genetic algorithm, the initial population and crossover and mutation operation are improved, thus to speed up the matching positioning speed and improve the reliability of the results.

genetic algorithm; optimization strategy; image matching and localization

TP391

A

10.19358/j.issn.1674- 7720.2017.23.013

傅超斌，南開來.基于改進(jìn)遺傳算法的圖像匹配定位[J].微型機(jī)與應(yīng)用，2017,36(23)：44-45,49.

2017-05-02)

傅超斌(1993-)，通信作者，男，碩士研究生，主要研究方向：LD-VHDL的并行編譯。E-mail：610519112@qq.com。

南開來(1992-)，男，碩士研究生，主要研究方向：基于可編程邏輯陣列的圖像處理。