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

傅超斌，南開來

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

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

傅超斌，南開來

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

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

遺傳算法；優化策略；圖像匹配定位

0 引言

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

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

1.1 遺傳算法概念

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

1.2 理論基礎

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

(1)

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

1.3 基本遺傳算法

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

圖1 基本遺傳算法流程圖

算法流程圖如圖1所示。

2 算法應用[4-5]

2.1 匹配問題描述

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

(2)

采用歸一化衡量相似度判別函數：

(3)

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

2.2 優化改進策略

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

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

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

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

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

圖2 選擇交叉操作示意圖

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

2.3 問題建模

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

3 實驗示例及結果

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

3.1 實驗示例

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

3.2 實驗結果

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

圖3 實驗示例

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

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

4 結論

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

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

[2] 金希東.遺傳算法及其應用[D].成都：西南交通大學,1996.

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

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

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

2017-05-02)

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

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