基于改進遺傳算法的圖像匹配定位

傅超斌，南開來

(杭州電子科技大學 計算機學院，浙江 杭州 310018)

基于改進遺傳算法的圖像匹配定位

傅超斌，南開來

(杭州電子科技大學 計算機學院，浙江 杭州 310018)

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

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

0 引言

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

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

1.1 遺傳算法概念

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

1.2 理論基礎(chǔ)

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

(1)

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

1.3 基本遺傳算法

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

圖1 基本遺傳算法流程圖

算法流程圖如圖1所示。

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

2.1 匹配問題描述

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

(2)

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

(3)

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

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

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

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

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

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

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

圖2 選擇交叉操作示意圖

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

2.3 問題建模

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

3 實驗示例及結(jié)果

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

3.1 實驗示例

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

3.2 實驗結(jié)果

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

圖3 實驗示例

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

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

4 結(jié)論

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

[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].成都：西南交通大學,1996.

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

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

[5] 嚴國榮, 趙亦工. 基于改進的遺傳算法的快速圖像相關(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].微型機與應(yīng)用，2017,36(23)：44-45,49.

2017-05-02)

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

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