張大偉 張婷婷 秦瑜

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

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

0 前言

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

1 遺傳算法的原理

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

作者簡(jiǎn)介：

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