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

張大偉 張婷婷 秦瑜

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

關鍵詞：自動拼圖；遺傳算法；歸一化；閾值

0 前言

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

1 遺傳算法的原理

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

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

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

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

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

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

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

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

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

3 實驗結果

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

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

4 結語

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

參考文獻：

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

[2] 曹戴. 智能數字拼圖算法研究及其應用[D]. 江南大學碩士學位論文. 2017，6.

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

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

作者簡介：

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