張大偉 張婷婷 秦瑜

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

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

0 前言

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

1 遺傳算法的原理

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果

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

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

4 結(jié)語

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

參考文獻：

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

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

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

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

作者簡介：

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