基于改進遺傳算法的自動拼圖

張大偉 張婷婷 秦瑜

摘 要：針對傳統(tǒng)自動拼圖算法在處理過程中出現(xiàn)還原速度慢和匹配精度低的問題，利用遺傳算法有效搜索全局最優(yōu)解的特點，提出一種基于改進遺傳算法的自動拼圖方案。由于圖像數(shù)據(jù)信息的特殊性，在使用遺傳算法處理圖像時出現(xiàn)收斂速度慢和奇異數(shù)據(jù)導(dǎo)致無法收斂的情況。所提方案通過對圖像邊緣數(shù)據(jù)差進行歸一化處理，加速遺傳算法的收斂速度；通過增添閾值，控制所得最小度量值與次度量值的比值來提高自動拼圖的準(zhǔn)確率。實驗結(jié)果表明，改進遺傳算法在自動拼圖中計算速度和匹配準(zhǔn)確度方面都有明顯的提高。

關(guān)鍵詞：自動拼圖；遺傳算法；歸一化；閾值

0 前言

拼圖源于將一張完整的圖像，按一定規(guī)則隨機切塊（包括有幾何形狀的碎片和方形碎片兩種），各碎片互相不重疊，并且可以按照一定的鏈接方式，將其還原成未切塊前的完整圖像。隨著計算機技術(shù)的發(fā)展，可以借助計算機強大的計算能力進行智能還原圖片，因此拼圖算法如何設(shè)計顯得尤為重要。為了實現(xiàn)拼圖誤差最小化和提高圖像匹配的速度，本文在Pomeranz和Gallagher算法的基礎(chǔ)上作了改進，并結(jié)合GA是全局搜索最優(yōu)解的算法，提出一種邊緣度量信息的歸一化和最優(yōu)選擇閾值的方法，可以快速全自動的還原拼圖。

1 遺傳算法的原理

首先對具體的問題進行分析，嘗試去建立表現(xiàn)型與基因型的潛在關(guān)系，制定一套針對具體問題的“數(shù)字化”編碼的方案；然后根據(jù)實際情況設(shè)定一個數(shù)值，作為初始化種群，種群里面的個體信息映射出的就是方案中數(shù)字化的編碼信息；最后，使用合理的的解碼方式，用適應(yīng)性函數(shù)按照某種規(guī)定擇優(yōu)選擇，讓個體基因交叉變異，得到新的種群。

GA的優(yōu)點：1）整體搜索，并行化處理簡單，更容易得到最優(yōu)解；2）不是盲目窮舉，而是啟發(fā)式搜索；3）適應(yīng)度函數(shù)不受約束，適用范圍很廣；4）容易實現(xiàn)，對于處理一個新的問題，只需要一套合適的基因編碼方案，以及合理準(zhǔn)確的適應(yīng)度函數(shù)，對遺傳算法的程序稍微的做改動就可以。

終止條件：在程序中是采用了兩個停止準(zhǔn)則。1）最大代數(shù)為20，為了防止出現(xiàn)不收斂或者迭代次數(shù)過多的現(xiàn)象，所以設(shè)定最大的執(zhí)行次數(shù)。2）當(dāng)適應(yīng)度函數(shù)值變化小于設(shè)定的閾值時，運算將停止，如果始終達不到這個條件，就達到最大迭代次數(shù)時停止進化迭代。

2 基于遺傳算法的智能拼圖

拼圖問題的解決主要經(jīng)歷了三個階段，第一階段是完全使用碎片的形狀信息，第二階段是利用碎片的形狀信息以及顏色信息的混合信息，第三階段是方形碎片的拼圖算法研究，方形碎片可以任意旋轉(zhuǎn)，沒有可用的形狀信息，只能使用顏色信息。

將使用碎片差異度量SSD（Sum of Squared Distance Scoring）來進行選擇相鄰碎片，這是最簡單的度量方式，僅使用碎片邊緣的像素信息之間的差異計算。計算速度快，但是不夠準(zhǔn)確，如果直接使用還原圖像往往無法達到預(yù)期的效果。SDD的公式為

MGC（Mahalanobis Gradient Compatibility）將馬氏距離運用到碎片之間，不僅考慮最邊緣的像素信息，還加入了邊緣的梯度信息，使度量更準(zhǔn)確，該方法雖然提高了準(zhǔn)確率，但同時大大的增加了運算時間。MGC的公式為

為了后面數(shù)據(jù)處理的方便，加速GA 的收斂速度，對圖像RGB三個通道的邊緣數(shù)據(jù)的差進行歸一化處理，使得所得到的均值都在0-1之間。改進的適應(yīng)度函數(shù)為

交叉算子引入了“best buddies”概念，如果最優(yōu)的碎片存在，則選擇最優(yōu)碎片；如果不存在最優(yōu)的碎片則挑選滿足“best buddies”關(guān)系的碎片；如果不存在則隨機選擇。 “best buddies”關(guān)系式為

3 實驗結(jié)果

本文以Pycharm為軟件開發(fā)平臺，基于python語言來模擬以上拼圖算法，所有的參數(shù)都相同，初始種群設(shè)定為600，最大迭代次數(shù)設(shè)定為20。改進的遺傳算法（Improved Genetic Algorithm，IGA）即：同時添加歸一化和閾值。在不同改進算法下還原拼圖所用的平均速率和準(zhǔn)確率的比較結(jié)果。通過比較分析，當(dāng)對數(shù)據(jù)進行歸一化處理時加快了還原速度，但準(zhǔn)確率不變；添加閾值之后，還原速度基本不變，但準(zhǔn)確率明顯提高；采用AGA，自動拼圖在還原速度和準(zhǔn)確率上都明顯的改善。使用不同算法還原拼圖的準(zhǔn)確率的對比。從圖可知，本文所使用的IGA算法在碎片尺寸小于30*30的時候，準(zhǔn)確率比MGC算法要略低；但是碎片尺寸大于30*30時，準(zhǔn)確率明顯優(yōu)于其他方法。

解決智能拼圖的過程中，最重要的是解決碎片之間的信息度量和最優(yōu)匹配的問題。本文使用歸一化和增添閾值結(jié)合的方案，有效的解決了這兩個問題，從而提高拼圖速度和質(zhì)量。

4 結(jié)語

本文介紹改進的遺傳算法主要是對適應(yīng)度函數(shù)和交叉算子進行改進。GA的早熟現(xiàn)象主要表現(xiàn)為當(dāng)還未達到全局最優(yōu)解，群體中不能產(chǎn)生超越父代的子代，把局部的最優(yōu)解作為全局解，故添加了歸一化處理和最優(yōu)閾值相結(jié)合可以更好地找到全局最優(yōu)解。將改進GA運用到自動拼圖不僅加快了還原拼圖的速度，還提高了準(zhǔn)確率。目前，拼塊的尺寸越小，準(zhǔn)確率也會直線下降，并且對于有部分信息缺失的圖片，還是做不到百分之百的準(zhǔn)確，為了更好的提高自動拼圖的速度和準(zhǔn)確度，后期會結(jié)合機器學(xué)習(xí)和深度學(xué)習(xí)的知識，搭建一個神經(jīng)網(wǎng)絡(luò)，利用深度網(wǎng)絡(luò)去進行測試，或許會有更好的結(jié)果。相信不久的將來，可以做到百分之百的準(zhǔn)確拼圖。

參考文獻：

[1] 魚濱，張善文，郭竟等.基于MATLAB 和遺傳算法的圖像處理 [M]. 西安 ： 西安電子科技大學(xué)出，2015.

[2] 曹戴. 智能數(shù)字拼圖算法研究及其應(yīng)用[D]. 江南大學(xué)碩士學(xué)位論文. 2017，6.

[3] 田瑩，苑瑋琦.遺傳算法在圖像處理上的應(yīng)用[J].中國圖象圖形學(xué)報.2007，12（3）：389～396.

[4] 朱陳柔玲，張達敏，張慕雪，楊菊蜻. 遺傳算法在圖像處理上的應(yīng)用* [J]. 通信技術(shù).

作者簡介：

姓名：張大偉 （1992.04--） 性別：男，山西省運城市人，學(xué)歷：碩士，專業(yè)：信息與通信工程。