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

（河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，新鄉(xiāng)453007）

基于模擬退火的空白填補(bǔ)碎片自動(dòng)拼接算法?

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

（河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，新鄉(xiāng)453007）

針對(duì)形狀規(guī)則的雙面灰度碎片，建立了一種基于模擬退火的依次空白填補(bǔ)的拼接復(fù)原算法。以碎片的灰度矩陣建立距離矩陣，通過降溫退火，逐次填補(bǔ)空白，得到碎片的大概排序結(jié)果，然后依據(jù)文意進(jìn)行適當(dāng)?shù)娜斯じ深A(yù)，得到最終的拼接結(jié)果。逐次空白填補(bǔ)過程中對(duì)碎片不斷進(jìn)行修正檢驗(yàn)，保證了拼接的準(zhǔn)確性。仿真模擬證明了算法能完成對(duì)碎片的自動(dòng)拼接，對(duì)比試驗(yàn)證明算法是相對(duì)高效和有效的。

空白填補(bǔ)；模擬退火；自動(dòng)拼接

1 引 言

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

源于統(tǒng)計(jì)力學(xué)的模擬退火算法通過不同溫控改變粒子的能量，從而使粒子可以自由運(yùn)動(dòng)和重新排列。高溫粒子的緩慢降溫（即退火），使得不同溫度下粒子熱平衡點(diǎn)不同，系統(tǒng)完全冷卻后，粒子將成為處于低能狀態(tài)的晶體。

根據(jù)Metropolis算法描述的退火過程。當(dāng)材料由高溫轉(zhuǎn)換為低溫時(shí)，以概率1全部接受；而由低溫轉(zhuǎn)換為高溫時(shí)，以概率接受轉(zhuǎn)換。

2 基于模擬退火算法的碎片自動(dòng)拼接復(fù)原

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

2.1 數(shù)據(jù)處理

（1）碎片數(shù)據(jù)采集

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

其中aij是每個(gè)碎片相應(yīng)點(diǎn)的灰度值。

（2）邊界灰度矩陣

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

2.2 算法思想

根據(jù)印刷習(xí)慣，紙張邊緣會(huì)有一定空白，據(jù)此特點(diǎn)可以首先提取出邊界碎片以提高算法自動(dòng)搜索效率。

（1）定義距離矩陣

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

定義：距離矩陣d：

d（i，j）表示第i個(gè)碎片的尾端接第j個(gè)碎片的首端時(shí)的相似度。

（2）確定解空間和目標(biāo)函數(shù)

假設(shè)規(guī)則有k個(gè)碎片，則一個(gè)有效的解空間具有如下結(jié)構(gòu)：

使得該排列下，滿足：

（3）代價(jià)差函數(shù)

任選序號(hào)m，n（m＜n）交換其順序，產(chǎn)生新解：

則有代價(jià)差函數(shù)：

（4）接受準(zhǔn)則

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

（5）降溫與退火過程結(jié)束

利用降溫系數(shù)進(jìn)行降溫，即T＝aT，用選定的終止溫度來判斷退火過程是否結(jié)束。

（6）人工干預(yù)

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

2.3 算法流程圖

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

圖1 算法流程圖

3 仿真結(jié)果

依據(jù)上述提出的算法，通過MATLAB實(shí)現(xiàn)了對(duì)文獻(xiàn)［7］中實(shí)驗(yàn)數(shù)據(jù)的分析，文獻(xiàn)為雙面英文碎片，橫切11片，縱切19片，共形成規(guī)則碎片2×11× 19＝418個(gè)。

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

表1 a不同值的人工干預(yù)和對(duì)比降溫時(shí)間

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

圖2 上述算法的部分拼接結(jié)果

圖3 基于文字信息的部分拼接結(jié)果

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

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

表2 算法時(shí)間對(duì)比

4 結(jié)束語

通過碎片數(shù)字化處理，采用基于模擬退火算法的空白填補(bǔ)方法，借助計(jì)算機(jī)實(shí)現(xiàn)了碎片的自動(dòng)拼接復(fù)原。但由于碎片數(shù)量大，需加入適當(dāng)?shù)娜斯じ深A(yù)來進(jìn)一步提高其準(zhǔn)確性，但相較于其他算法，效率和準(zhǔn)確性相對(duì)較高。

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

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

［3］汪劍，皮佑國(guó)，劉明友.基于Freeman鏈碼的漢字圖像輪廓曲線拐角點(diǎn)檢測(cè)方法［J］.自動(dòng)化技術(shù)與應(yīng)用，2009，28（1）：88-92.

［4］鄭蓓蓓，郭立本.改進(jìn)的遺傳算法應(yīng)用于碎片拼接［J］.計(jì)算機(jī)與現(xiàn)代化，2011（5）：52-56.

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

［6］全國(guó)大學(xué)生數(shù)學(xué)建模（官網(wǎng)）.2013賽題：［DB／OL］.教育部高等教育司和中國(guó)工業(yè)與應(yīng)用數(shù)學(xué)協(xié)會(huì)，2013［2013-9-11］.http：／／www.mcm.edu.cn／problem／2013／2013.html.

［7］羅智中.基于文字特征的文檔碎紙片半自動(dòng)拼接［J］.計(jì)算機(jī)工程與應(yīng)用，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

河南師范大學(xué)青年科學(xué)基金（2013QK19）

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

2013-12-04