基于模擬退火的空白填補碎片自動拼接算法?

侯蓓蓓，于紅斌，王鮮芳，王 鑫，孫廣月，陳林林

（河南師范大學計算機與信息工程學院，新鄉453007）

基于模擬退火的空白填補碎片自動拼接算法?

侯蓓蓓，于紅斌，王鮮芳，王 鑫，孫廣月，陳林林

（河南師范大學計算機與信息工程學院，新鄉453007）

針對形狀規則的雙面灰度碎片，建立了一種基于模擬退火的依次空白填補的拼接復原算法。以碎片的灰度矩陣建立距離矩陣，通過降溫退火，逐次填補空白，得到碎片的大概排序結果，然后依據文意進行適當的人工干預，得到最終的拼接結果。逐次空白填補過程中對碎片不斷進行修正檢驗，保證了拼接的準確性。仿真模擬證明了算法能完成對碎片的自動拼接，對比試驗證明算法是相對高效和有效的。

空白填補；模擬退火；自動拼接

1 引 言

碎片拼接在日常生活中應用廣泛，如考古工作，情報獲取，司法取證等，自動拼接算法已經成為研究熱點。如基于OpenCV和圖像角點的拼接算法［1］，可以完成對二維不規則圖像碎片的輪廓檢測、角點提取、角點序列匹配、圖像拼接及缺失修復；基于尺度不變特征的自動拼接技術［2］實現傳感器網絡中的圖像拼接；基于Freeman練碼的二維碎片拼接［3］，降低了算法的時間和空間復雜度；改進的遺傳算法［4］和蟻群優化算法［5］，實現了碎片的全局拼接，提高了算法效率。在此采用基于物理統計力學的模擬退火算法，通過依次空白填補，實現了二維規則碎片的全局拼接，算法簡單易于實現，相對其他算法人工干預減少，提高了算法性能。

源于統計力學的模擬退火算法通過不同溫控改變粒子的能量，從而使粒子可以自由運動和重新排列。高溫粒子的緩慢降溫（即退火），使得不同溫度下粒子熱平衡點不同，系統完全冷卻后，粒子將成為處于低能狀態的晶體。

根據Metropolis算法描述的退火過程。當材料由高溫轉換為低溫時，以概率1全部接受；而由低溫轉換為高溫時，以概率接受轉換。

2 基于模擬退火算法的碎片自動拼接復原

規則的雙面碎片，無法確定碎片所屬（正、反面），所以假設拼接目標是一張雙倍大小單面紙，即由兩張單面紙首尾相接而成。

2.1 數據處理

（1）碎片數據采集

每張碎片的數字圖像信息可以矩陣A來表示：

其中aij是每個碎片相應點的灰度值。

（2）邊界灰度矩陣

兩片相連碎片必然具有相似的邊緣，因此邊界灰度值將是確定碎片順序的重要參考，于是可以根據A矩陣構造碎片的首列信息矩陣Cs，尾列信息矩陣Cw，首行信息矩陣Rs，尾行信息矩陣Rw，即相應邊界灰度矩陣。

2.2 算法思想

根據印刷習慣，紙張邊緣會有一定空白，據此特點可以首先提取出邊界碎片以提高算法自動搜索效率。

（1）定義距離矩陣

原本屬于一體的兩個碎片必然具有相似的邊緣，因此可以基于碎片的邊界灰度值確定碎片的順序。

定義：距離矩陣d：

d（i，j）表示第i個碎片的尾端接第j個碎片的首端時的相似度。

（2）確定解空間和目標函數

假設規則有k個碎片，則一個有效的解空間具有如下結構：

使得該排列下，滿足：

（3）代價差函數

任選序號m，n（m＜n）交換其順序，產生新解：

則有代價差函數：

（4）接受準則

根據模擬退火思想，若Δf小于0，則以概率1接受新路徑；否則，以概率e-Δf／T接受新路徑，即：

（5）降溫與退火過程結束

利用降溫系數進行降溫，即T＝aT，用選定的終止溫度來判斷退火過程是否結束。

（6）人工干預

將填補出來的紙張按照其文意，及正反面特征將其復原成雙面。

2.3 算法流程圖

算法流程圖，如圖1所示。

圖1 算法流程圖

3 仿真結果

依據上述提出的算法，通過MATLAB實現了對文獻［7］中實驗數據的分析，文獻為雙面英文碎片，橫切11片，縱切19片，共形成規則碎片2×11× 19＝418個。

模擬退火要滿足在每一溫度下都達到熱平衡，則降溫過程需足夠緩慢。在取值上，通過仿真實驗發現，如果降溫過程過慢，即a接近1，得到的結果比較精確，但效率太低，較其它搜索算法并不占優勢；如果降溫速度過快，即a接近0，則很可能得不到全局最優解。表1為a取0.999和0.95時，10次相同情況下降溫的人工干預情況和降溫時間對比。

表1 a不同值的人工干預和對比降溫時間

為了提高精確度，仿真時采用降溫系數a＝0.999，終止溫度e＝10-30進行降溫。通過模擬退火，得到最左端碎片的大概排序為：009a、083b、003b、143a、054a……114a、146a、165b、199b、088b，接著按空白填補算法依次填補拼接，并在適當位置進行人工干預，則最終拼接結果如圖2所示。同時，將數據應用于文獻的基于文字信息的拼接算法［8］，其拼接結果如圖3所示。

圖2 上述算法的部分拼接結果

圖3 基于文字信息的部分拼接結果

在文意銜接上，可以直接看出，該算法更加準確。

表2是兩種算法的時間對比，可以看出基于模擬退火算法的空白填補模型速度相對較快，效率較高。

表2 算法時間對比

4 結束語

通過碎片數字化處理，采用基于模擬退火算法的空白填補方法，借助計算機實現了碎片的自動拼接復原。但由于碎片數量大，需加入適當的人工干預來進一步提高其準確性，但相較于其他算法，效率和準確性相對較高。

［1］董乾，黃曉鳴.基于OpenCV的圖像碎片拼接［J］.科學技術與工程，2010，10（22）：5429-5432.

［2］李鐵軍，陳哲，王任享.基于尺度不變特征變換的圖像快速拼接算法［J］.微計算機信息，2008，24（4-3）：282-283，259.

［3］汪劍，皮佑國，劉明友.基于Freeman鏈碼的漢字圖像輪廓曲線拐角點檢測方法［J］.自動化技術與應用，2009，28（1）：88-92.

［4］鄭蓓蓓，郭立本.改進的遺傳算法應用于碎片拼接［J］.計算機與現代化，2011（5）：52-56.

［5］何鵬飛，周宗潭，胡德文.基于蟻群優化算法的碎紙拼接［J］.計算機工程與科學，2011，33（7）：69-73.

［6］全國大學生數學建模（官網）.2013賽題：［DB／OL］.教育部高等教育司和中國工業與應用數學協會，2013［2013-9-11］.http：／／www.mcm.edu.cn／problem／2013／2013.html.

［7］羅智中.基于文字特征的文檔碎紙片半自動拼接［J］.計算機工程與應用，2012，48（5）：207-210.

Automatic Stitching Algorithm of Debris by Gap-filling Based on Simulated Annealing

HOU Bei-bei，YU Hong-bin，WANG Xian-fang，WANG Xin，SUN Guang-yue，CHEN Lin-lin
（College of Computer and Information Engineering，Henan Normal University，Xinxiang 453007，China）

In order to stitch double gray debriswith regular shape，an automatic algorithm based on simulated annealing is proposed.It gives a distance matrix based on the gray matrix of the debris，fills the gaps through successive cooling annealing，and obtains the approximate order of the debris accordingly.Then，appropriate artificial intervention is performed according to the text to generate the final result of stitching.During the process of gap filling，the debris＇order is constantly revised to ensure the veracity of stitching.The simulation proves that the algorithm can achieve the automatic stitching of debris and the contrast experiment shows that the algorithm is efficient and effective.

Automatic stitching；Filled gaps；Simulated annealing

10.3969／j.issn.1002-2279.2014.03.010

TP301

：A

：1002-2279（2014）03-0033-03

河南師范大學青年科學基金（2013QK19）

侯蓓蓓（1993-），女，河南武陟人，本科生，主研方向：數字圖像處理。

2013-12-04