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

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

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

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

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

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

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

1.1 TSP問題

TSP問題就是旅行商問題，它是最基本的求解線路問題。這個問題簡單的來說，就是“假設(shè)有一個旅行商要拜訪n個城市，他必須選擇好要走的路徑，路徑的限制條件是每個城市只能拜訪一次，而且商人最后要回到從開始出發(fā)的那個城市?！甭窂降倪x擇目標(biāo)是求選擇的路徑的路程是所有路徑路程中的最小值[5]。

1.2 模擬退火算法

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

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

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

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

2.1 信息的提取

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

2.2 復(fù)原 TSP 問題

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

圖 2 TSP問題示意圖

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

圖 3 碎紙片拼接示意圖

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

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

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

2.3.1 編碼選擇

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

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

3 結(jié)論

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

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

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

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

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

參考文獻(xiàn)：

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

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