碎紙片的拼接復原模型及其算法研究

姚光督，沈景鳳，王文東，滕 泉

(1.上海理工大學 機械工程學院，上海 200093；2.上海材料研究所，上海 200437)

碎紙片的拼接復原模型及其算法研究

姚光督1，沈景鳳1，王文東2，滕 泉1

(1.上海理工大學 機械工程學院，上海 200093；2.上海材料研究所，上海 200437)

針對目前司法物證復原、歷史文獻修復以及軍事情報獲取等領(lǐng)域就如何快速高效的對破碎紙片進行修復的問題。利用Matlab算法對碎紙片進行處理并得出其灰度矩陣，再通過分析矩陣間的關(guān)系，利用Matlab編程并建立數(shù)學模型，對具有輪廓形狀規(guī)則、字符顏色相同、字符間距和行間距相同的碎紙片進行自動拼接復原。在此模型和算法的基礎上，加入對不同字符的識別技術(shù)，能有效減少拼接錯誤的概率以及拼接過程中的人工干預，進一步提高碎紙片拼接復原的效率，在碎紙片拼接復原的研究中具有一定的創(chuàng)新性。

破碎文件的拼接；灰度矩陣；Matlab編程；字符識別技術(shù)

常規(guī)碎紙片拼接復原方法一般利用碎片邊緣的尖點特征、尖角特征、面積特征等幾何特征，搜索與之匹配的相鄰碎紙片并進行拼接，這種基于邊界幾何特征的拼接方法并不適用于邊緣形狀相似的碎紙片，當然也不適用解決通過破碎機破碎紙片的拼接與復原問題。因此，對這類邊緣相似的碎紙片的拼接，理想的計算機拼接過程應與人工拼接過程類似，即拼接時不但要考慮待拼接碎紙片邊緣是否匹配，還要判斷碎片內(nèi)的字跡斷線或碎片內(nèi)的文字內(nèi)容是否匹配。本文以2013年全國大學生數(shù)學建模競賽B題為數(shù)據(jù)來源，模型假設：(1)假設碎紙機切割的小碎片的大小相同且形狀規(guī)則；(2)假設文件被切割后的所有碎紙片均齊全；(3)假設碎紙片正反兩面的內(nèi)容有差異；(4)假設碎紙片沒有材質(zhì)以及顏色方面的差異。利用現(xiàn)有的技術(shù)，完全可以獲取碎片文字圖片的數(shù)字信息，拼接碎片時利用這些信息并適時結(jié)合人工干預進行拼接，就能在保證準確率較高的前提下，提高拼接復原的效率。

1 問題分析

由于題目中所給的圖片不存在破損，經(jīng)碎紙機切割后，掃描入計算機的文件可近似成矩形，因此可將圖片導入Matlab處理，得出其灰度矩陣，以此來表示碎紙片中字的位置以及分布。觀察第一張紙條左邊沿有較多的空白邊，因此在灰度矩陣中挑選出第1列全等于255的矩陣的則為第一張紙條。與此相對應，原來相對應的兩張紙片A、B對應的灰度矩陣a的最右列和灰度矩陣b的最左列是可以完全吻合的。采用此兩列的差的平方和作為相似度判定依據(jù)，從后18個灰度矩陣的第一列依次與第一張紙片的灰度矩陣的最后一列作相似度比較，則差的平方和最小的值其所在的列為第二張紙片。依次連接可得到修復圖片矩陣，再由Matlab生成修復圖片，照此模型進行排序，來檢驗模型是否具有普適性。

2 建模與求解

經(jīng)觀察檢驗所給的圖片不存在破損，經(jīng)碎紙機切割后，文字的每一部分都會出現(xiàn)在分割后紙條片上，圖片中相連文字、標點被分割后，兩塊墨跡能夠相互對應，根據(jù)對應灰度矩陣分布來確定碎紙片中字、殘缺字的位置及分布。若A、B原為兩相接的碎紙片，則A、B對應的灰度矩陣a的最右列和灰度矩陣b的最左列具有較高的相似度，即a與b差的平方和是最小的?，F(xiàn)選取紙條T，將紙條T的最左列t與其它所有紙條的最右列分別求其差方，得到與t差的平方和最小的即為與T最吻合的那一條，依次求解直至所有紙條用完。

2.1 建立模型

(1)建立灰度矩陣模型，將給出的19張碎紙條寫入Matlab，轉(zhuǎn)換生成19個1 980×72的灰度矩陣，在此灰度矩陣中，0代表墨跡，255表示空白，介于0～255之間的為墨跡邊沿灰度；

(2)因為第一張紙條左邊沿有較多的空白邊，因此在灰度矩陣中挑選出第1列全為255矩陣的則為第一張紙條；

(3)原來連接的兩張紙片對應的灰度矩陣,A矩陣的最右列和B矩陣的最左列具有較高的相似度。將依次將后18個灰度矩陣Zk·i與第一個矩陣Yki的最左列分別做差的平方和

(1)

當s取最小值時，此時s所在的灰度矩陣對應的紙片為第二張紙片；

(4)找到第二張圖片后，依次執(zhí)行步驟(3)循環(huán)，依次求出第3,4…張紙片，直到求出矩陣排列順序。

2.2 建立模型

步驟1算法將圖像寫入Matlab轉(zhuǎn)化為灰度矩陣。將附件1中000.bmp～019.bmp等19張碎紙條用Matlab轉(zhuǎn)化成19個灰度矩陣Ckj,將這19個矩陣定義成一個k行，j列的19層三維矩陣Akji(i=1,2,3,…,19),并求出這19個行列數(shù)均為1 980×72的灰度矩陣，為簡化算法運算，方便矩陣的調(diào)用，將上述19個灰度矩陣Ckj的第一列和最后一列分別提取出來，組成新矩陣?；叶染仃嚨挠疫呇兀喝kji第i層矩陣的最后1列定義新矩陣Zkj

(2)

灰度矩陣的左邊沿：取Akji第i個矩陣的最后一列定義新矩陣Ykj

(3)

步驟2選出第一張紙條所在的灰度矩陣，在此問題中，由于紙條第一張有特殊性，最左端邊沿存在一段白色邊沿，19個灰度矩陣中第一列全為255的為第一張紙片，即滿足Zkj=255。求得i=9，即008.bmp為第一張圖片，記第一張紙片d(1)=9；

步驟3通過矩陣邊沿相似度大小比較進行圖片拼接，原本連接的兩張紙片切割后，原來相連文字、標點可以根據(jù)其墨跡進行對應。對應到灰度矩陣即原來相連的兩張紙片A、B對應的灰度矩陣a的最右列和灰度矩陣b的最左列具有較高的相似度，即其差的平方和的值最小。得到第一條紙片為第9條后，將第一條紙片的最右列Zkj依次與剩下的18個矩陣的最左列Ykj做差的平方和

(4)

求得s最小時，Zki與Yki相似度最高，此時的Zki為第2條紙片，然后選取第2條同理得到第3條紙片，直至最后一條紙，由此依次計算得到后18張圖片排列順序，記d(n)=i,n=1，2，3，…，19；

步驟4在第三步算法運算中，為減少算法循環(huán)時重復選取已選紙條，減小算法的時間和空間復雜度，在第一步算法執(zhí)行前增加一項判斷去除命令，定義行向量zz(n)= 1,2,3,…,19。在第n次循環(huán)中選中第n張紙片為i后，定義zz(n)=0，再做算法循環(huán)時判斷，如果zz(n)=0，則不執(zhí)行此操作并自動循環(huán)至下一個數(shù),如果前面已選定某一張并進行排序，那么在下一次篩選時不會將這條紙片列入比較范圍，可減少運算的量；

步驟5生成復原圖片并對圖片進行分析檢驗，第3步中循環(huán)結(jié)束得到19個矩陣排列順序，依據(jù)該順序?qū)⑦@19個灰度矩陣按每列拼成一個1 908×1 386的大矩陣，該矩陣即反應了原紙片所有字符的矩陣。最后用Matlab將這個大矩陣轉(zhuǎn)換為圖片，則這張圖片即為所得復原拼貼圖片結(jié)果。如果拼接完成的圖順序正確則說明模型比較適合碎紙拼接問題，如拼接圖片出現(xiàn)些許差錯則進行人工干預，手工對圖片進行調(diào)整，如出現(xiàn)問題較大，拼出的圖片明顯錯誤則對模型進行改進。

3 模型算法求解結(jié)果

在Matlab中將19張圖片轉(zhuǎn)化成19個灰度矩陣，并將上述模型算法進行編程，得到19個灰度矩陣排列的順序為i=9,15,13,16,4,11,317,2,5,6,10,14,19,12,8,18,17。圖片復原后順序矩陣為

000101010001000100000000010101000100008425302614593817706

同理，對附件2中英文圖片進行復原排序，得到灰度矩陣排列的順序為i=4,7,2,9,16,19,12,1,6,2,10,14,11,19,13,15,18,17,5。圖片復原后順序矩陣

000000000101010000000001010101010101003627581051930824764

4 模型的檢驗與分析

拼圖時可能存在的問題比較多，例如兩張原本不能匹配的紙條，由于一張最左列與不匹配紙條的最右列都有較多的空白，因此可能會出現(xiàn)兩張甚至多張都可以進行匹配的情況。如果最后得到復原圖片在句法、語義、邏輯性上出現(xiàn)較大偏差，在不合適的拼貼圖片處，進行人工干預選擇。通過相似度分析，取最小的3個s值，作為3張備選圖片，然后根據(jù)句法、語義選擇出最合適的一張圖片，標記此圖片對應的灰度矩陣i，將此值帶入初始值，然后繼續(xù)執(zhí)行程序，反復執(zhí)行直到得出合適的修復圖片。

5 結(jié)束語

隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，本文提出的模型和相應求解算法可以在盡量少人工干預的情況下，對具有輪廓形狀規(guī)則、字符顏色相同、字符間距和行間距相同的特點的碎紙片進行自動拼接還原。但在實際自動拼接過程中，如果出現(xiàn)一次相鄰碎紙片拼接錯誤，那么就有可能導致后續(xù)一系列的拼接錯誤。因此，如何能夠及時發(fā)現(xiàn)拼接錯誤，以及提高拼接的準確率是本文所提出的模型需要繼續(xù)改進的地方。綜合上述問題，在本文提出的模型和算法的基礎上，加入對字符的識別技術(shù)，則能夠有效減少拼接的錯誤概率，并減少拼接過程中的人工干預。

[1] Ester M,Kriegel H P,Sander J.A density based algorithm for discovering clusters in large spatial databases with noise[C].Portland,Oregon:Proceeding of 2nd International Conference on Knowledge Discovery and Data Mining,1996.

[2] 羅智中.基于文字特征的文檔碎紙片半自動拼接[J].華東交通大學,2012,48(5):207-210.

[3] 徐少帥,劉奧強,毛思奇.基于Matlab的碎紙片拼接問題的數(shù)學模型[J].科協(xié)論壇,2013(12):232-233.

[4] 趙玉峰.計算機圖形學的發(fā)展及應用[J].科技信息,2008(16):68-71.

[5] 王斌,舒華忠,施朝健.一種基于輪廓線的形狀描述和匹配方法[J].電子與信息學報,2008,30(4):949-952.

[6] 劉金根,吳志鵬.一種基于特征區(qū)域分割的圖像拼接算法[J].西安電子科技大學學報,2002,29(6):768-771.

[7] 賈海燕,朱良家,周宗潭,等.一種碎紙自動拼接中的形狀匹配方法[J].計算機仿真,2007,23(11):180-183.

[8] 朱延娟,周來水.二維非規(guī)則碎片的匹配算法[J].計算機工程,2007,33(24):7-9.

[9] 徐雅平,王運生,董淵文,等.碎紙片的拼接復原[J].上海商學院學報,2013,14(5):79-84.

[10] 王俊杰.圖像配準的方法[EB/OL].(2013-09-14)[2016-11-15]http://www.docin.com/p-211110983.

[11] 何正風.Matlab概率與數(shù)理統(tǒng)計分析[M].北京:機械工業(yè)出版社,2012.

[12] 樓順天.Matlab 7.x程序設計語言[M].西安:西安電子科技大學出版社,2007.

[13] 李航.統(tǒng)計學習方法[M].北京:清華大學出版社,2012.

[14] 史程鵬,王明泉,侯慧玲,等.基于像素相關(guān)度的射線圖像拼接改進算法研究[J].核電子學與探測技術(shù),2009,29(6):1501-1503.

[15] 劉孟娟.基于聚類分析和灰度值匹配的碎片文件拼接復原[J].價值工程,2013,32(32):209-211.

Scraps of Paper Splicing Model and Algorithm Research

YAO Guangdu1,SHEN Jingfeng1,WANG Wendong2,TENG Quan1

(1. School of Mechanical Engineering,Shanghai University of Science and Technology,Shanghai 200093,China;2.Shanghai Research Institute of Materials,Shanghai 200437,China)

In order to solve the problem of how to reconstruct the broken paper pieces quickly and efficiently in the fields of judicial evidence restoration,historical document restoration and military information acquisition,the paper uses the Matlab algorithm to deal with the shredding and gets the gray matrix,and then analyze the inter and the mathematic model was built by using Matlab. The paper was automatically reconstructed with the contour rule,the same character color,the same spacing between characters and the line spacing. Based on this model and algorithm,the recognition technology of different characters can be added to reduce the probability of mosaic errors and human intervention in the process of splicing,and further improve the efficiency of splicing recovery,it has some innovation in the study of splicing restoration.

fractal file stitching; gray matrix; Matlab programming; character recognition technology

TP301.6

A

1007-7820(2017)11-100-03

2016- 12- 04

姚光督(1992-)，男，碩士研究生。研究方向：優(yōu)化設計。沈景鳳(1968-)，女，博士，副教授。研究方向：機械設計與理論等。

10.16180/j.cnki.issn1007-7820.2017.11.027