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

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

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

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

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

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

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

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

1 問(wèn)題分析

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

2 建模與求解

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

2.1 建立模型

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

(2)因?yàn)榈谝粡埣垪l左邊沿有較多的空白邊，因此在灰度矩陣中挑選出第1列全為255矩陣的則為第一張紙條；

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

(1)

當(dāng)s取最小值時(shí)，此時(shí)s所在的灰度矩陣對(duì)應(yīng)的紙片為第二張紙片；

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

2.2 建立模型

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

(2)

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

(3)

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

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

(4)

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

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

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

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

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

000101010001000100000000010101000100008425302614593817706

同理，對(duì)附件2中英文圖片進(jìn)行復(fù)原排序，得到灰度矩陣排列的順序?yàn)閕=4,7,2,9,16,19,12,1,6,2,10,14,11,19,13,15,18,17,5。圖片復(fù)原后順序矩陣

000000000101010000000001010101010101003627581051930824764

4 模型的檢驗(yàn)與分析

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

5 結(jié)束語(yǔ)

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

[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] 羅智中.基于文字特征的文檔碎紙片半自動(dòng)拼接[J].華東交通大學(xué),2012,48(5):207-210.

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

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

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

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

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

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

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

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

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

[12] 樓順天.Matlab 7.x程序設(shè)計(jì)語(yǔ)言[M].西安:西安電子科技大學(xué)出版社,2007.

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

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

[15] 劉孟娟.基于聚類(lèi)分析和灰度值匹配的碎片文件拼接復(fù)原[J].價(jià)值工程,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)化設(shè)計(jì)。沈景鳳(1968-)，女，博士，副教授。研究方向：機(jī)械設(shè)計(jì)與理論等。

10.16180/j.cnki.issn1007-7820.2017.11.027