基于TSP和模擬退火算法的碎紙拼接模型

肖松平 張立臣 冉慶波 張麗穎 王立亞

摘 要：本文圍繞碎紙片拼接問(wèn)題，建立了碎紙片復(fù)原模型、復(fù)原 TSP 模型、降維模型、改進(jìn)的模擬退火算法模型并成功的運(yùn)用到了紙片的拼接問(wèn)題中，利用降維的思想將問(wèn)題二維問(wèn)題轉(zhuǎn)化成一維問(wèn)題，并運(yùn)用 MATLAB 編程求解出最終結(jié)果。

針對(duì)一維問(wèn)題，設(shè)計(jì)了一維碎紙片復(fù)原算法，首先提取出圖像的像素矩陣，根據(jù)像素矩陣特征建立識(shí)別數(shù)字a ，分別求出最左和最右識(shí)別數(shù)字，然后將碎紙片復(fù)原問(wèn)題轉(zhuǎn)化為復(fù)原 TSP 問(wèn)題。針對(duì)二維問(wèn)題，運(yùn)用降維的思想設(shè)計(jì)了二維碎紙復(fù)原法，由于漢字的字高和字寬是確定的，而英文字母的高度不一致，所以先對(duì)英文的碎紙片進(jìn)行標(biāo)準(zhǔn)化，人工對(duì)標(biāo)準(zhǔn)化有誤的圖片進(jìn)行修正，然后分別提取碎紙片的像素矩陣，用 MATLAB 編程對(duì)他們進(jìn)行初步分類(lèi)，得到 11 類(lèi)特征相同的碎紙片，然后將問(wèn)題轉(zhuǎn)化為 11 個(gè)一維碎紙片問(wèn)題的求解，帶入到模擬退火算法中得到正確的復(fù)原圖形及序列。

最后，本文對(duì)所建模型進(jìn)行了客觀的評(píng)價(jià)，并結(jié)合實(shí)際對(duì)模型的推廣加以分析。

關(guān)鍵詞：碎紙片拼接；復(fù)原TSP模型；改進(jìn)的模擬退火算法模型；降維模型

1.算法方法理論基礎(chǔ)

1.1 TSP問(wèn)題

TSP問(wèn)題就是旅行商問(wèn)題，它是最基本的求解線(xiàn)路問(wèn)題。這個(gè)問(wèn)題簡(jiǎn)單的來(lái)說(shuō)，就是“假設(shè)有一個(gè)旅行商要拜訪(fǎng)n個(gè)城市，他必須選擇好要走的路徑，路徑的限制條件是每個(gè)城市只能拜訪(fǎng)一次，而且商人最后要回到從開(kāi)始出發(fā)的那個(gè)城市。”路徑的選擇目標(biāo)是求選擇的路徑的路程是所有路徑路程中的最小值[5]。

1.2 模擬退火算法

模擬退火算法原理來(lái)自于固體退火原理，是一種通用的隨機(jī)搜索算法。其原理是將固體加熱是溫度上升到到充分高，再讓其慢慢冷卻，加溫的時(shí)候，隨著溫度的升高固體內(nèi)部的粒子會(huì)變?yōu)闊o(wú)序狀，內(nèi)能增大，而慢慢冷卻時(shí)粒子漸漸趨向有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。優(yōu)化問(wèn)題和固體退火過(guò)程之間有一定的相似性。把對(duì)用固體在恒定問(wèn)題下達(dá)到熱平衡過(guò)程的模擬引入優(yōu)化過(guò)程中。即如果：

則接受新的狀態(tài)，否則按概率 接受新的狀態(tài)。

為一個(gè)隨時(shí)間t增加而下降的參變量，相當(dāng)于退火過(guò)程中的溫度。這種利用優(yōu)化問(wèn)題求解與物理系統(tǒng)退火過(guò)程的相似性，使用Metropolis算法，適當(dāng)?shù)乜刂茰囟鹊南陆颠^(guò)程，實(shí)現(xiàn)模擬退火，達(dá)到求解全局優(yōu)化問(wèn)題的隨機(jī)方法稱(chēng)為“模擬退火算法”[6]。

2.算法方法理論基礎(chǔ)

2.1 信息的提取

根據(jù)計(jì)算機(jī)圖形的相關(guān)知識(shí)，劃分空白位置和字符位置前，需要對(duì)圖片像素進(jìn)行處理，通過(guò)灰度化，將圖片像素定位為[0，255]區(qū)間內(nèi)，再通過(guò)設(shè)定閥指，區(qū)分空白位置和字體， 為了更加準(zhǔn)確的識(shí)別出每幅圖片的最大像素之和a，只取最大像素 255 作為計(jì)數(shù)點(diǎn)，其他像素不予考慮。因?yàn)閳D片是非彩色的所以?xún)H需考慮空白和非空白情況。為了使圖片能夠清晰的描述空白位置和字符位置，利用數(shù)學(xué)軟件 MATLAB 對(duì)圖像進(jìn)行預(yù)處理，將圖片導(dǎo)入 MATLAB，得到對(duì)應(yīng)的像素矩陣，由計(jì)算機(jī)圖形學(xué)知識(shí)可知，空白位置的像素值為 255，為了使像素矩陣更明顯，能更加清晰的看出像素之間的區(qū)別， 我們將矩陣中 0 和 255 的顏色進(jìn)行互換，得到的一系列的像素矩陣，可用于像素的特征提取。

2.2 復(fù)原 TSP 問(wèn)題

TSP 問(wèn)題即旅行商問(wèn)題是數(shù)學(xué)領(lǐng)域中最著名的問(wèn)題之一。“假設(shè)有一個(gè)旅行商人要連續(xù)拜訪(fǎng) n 個(gè)城市，他需要選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪(fǎng)一次，而且最后要回到開(kāi)始出發(fā)的城市。” 路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。示意圖如下：

圖 2 TSP問(wèn)題示意圖

若將每個(gè)碎紙看成一個(gè)城市，碎片和碎片之間存在吻合度，如果兩張碎紙的吻合度低，那么他們對(duì)應(yīng)的距離也大，當(dāng)吻合度為0時(shí)，所對(duì)應(yīng)距離為 。所以尋找吻合率最高的的碎紙片組合方式，其實(shí)質(zhì)就是尋找總距離最小的路徑，也就是找尋一條最佳TSP商旅路徑，只不過(guò)最后不再要求回到最初的城市（即第一張紙片）。示意圖如下：

圖 3 碎紙片拼接示意圖

將碎紙片復(fù)原抽象成復(fù)原TSP問(wèn)題，總的距離（符合度）公式如下：

其中R（i） 第i 塊碎紙片的右識(shí)別數(shù)字，L（i+1） 代表第i 塊碎紙片的左識(shí)別數(shù)字。

2.3 改進(jìn)模擬退火算法模型的建立

2.3.1 編碼選擇

TPS 的編碼策略上有近鄰編碼，次序編碼，二進(jìn)制編碼，和路徑編碼等。近鄰編碼必須考慮算法的合理性；次序編碼不利于全局優(yōu)化；二進(jìn)制編碼不自然，且需附加修正算子來(lái)保證解得合法性。基于此，路徑編碼最符合本文環(huán)境。為了算法的簡(jiǎn)便，對(duì)圖片重新進(jìn)行編號(hào)，將 000 號(hào)改為 19 號(hào)，其余不變。編碼類(lèi)似于 1-2-3-4？？？ -17-18-19。

通過(guò)求解復(fù)原TSP問(wèn)題，可以得到每個(gè)碎紙片的訪(fǎng)問(wèn)順序，即碎紙片的拼接序列，利用改進(jìn)模擬退火算法得到復(fù)原紙片[6]。

3 結(jié)論

本文對(duì)碎紙片拼接技術(shù)的背景及現(xiàn)狀進(jìn)行了簡(jiǎn)單的介紹，探討了對(duì)于碎紙片拼接技術(shù)研究的重要性和現(xiàn)實(shí)意義，提出了一種基于TSP模型和改進(jìn)的模擬退火算法相結(jié)合的拼接模型。可以為有關(guān)部門(mén)進(jìn)行紙片拼接時(shí)提供科學(xué)的參考，縮短拼接時(shí)間，提高拼接準(zhǔn)確率。

本文的主要工作和創(chuàng)新點(diǎn)有：

（1）將碎紙片拼接和TSP商旅模型聯(lián)系在一起，找出二者之間的聯(lián)系，建立復(fù)原TSP模型，縮小計(jì)算量。

（2）對(duì)于復(fù)原的TSP模型，采用改進(jìn)的模擬退火算法進(jìn)行求解，改變新解的產(chǎn)生方式，加快收斂的速度，縮短計(jì)算時(shí)間，提高了計(jì)算精度。

（3）對(duì)于高維問(wèn)題，提出降維模型，使得本文中的模型可以處理數(shù)量更多，更復(fù)雜的復(fù)原問(wèn)題，從而拓展了本文的適用范圍。

參考文獻(xiàn)：

[1] 劉令， 劉元， 孟凡清. 淺談基于矩陣運(yùn)算的碎紙片拼接問(wèn)題[J]. 山東工業(yè)技術(shù)， 2014（12）：202-202.

[2] 羅智中. 基于文字特征的文檔碎紙片半自動(dòng)拼接[J]. 計(jì)算機(jī)工程與應(yīng)用， 2012， 48（5）：207-210.