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

郭 偉，崔艷星

（長(zhǎng)治學(xué)院 數(shù)學(xué)系,山西 長(zhǎng)治 046011）

1 引言

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上,拼接復(fù)原工作需由人工完成，準(zhǔn)確性較高,但效率較低。當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開(kāi)發(fā)研究碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。現(xiàn)對(duì)以下問(wèn)題進(jìn)行討論：對(duì)給定的來(lái)自同一頁(yè)印刷文字文件的碎紙機(jī)破碎紙片（僅縱切）,建立碎紙片拼接復(fù)原模型和算法,并對(duì)附件1給出的一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。復(fù)原結(jié)果表達(dá)以圖片形式表達(dá)。

2 復(fù)原算法思想描述

對(duì)于給定的來(lái)自同一頁(yè)印刷文字文件的碎紙機(jī)破碎紙片（僅縱切）；首先，通過(guò)觀察這些字的特點(diǎn),可以通過(guò)人工干預(yù)[1]將紙條左邊全是整字、符號(hào)的碎紙條找出來(lái),這就找出了這些紙條中的第一條。同樣，我們可以確定出最后一條碎片。因?yàn)槊織l碎紙片中離邊緣最近的那些字，有的是整字，有的是半字,有的是符號(hào),有的是空格,所以對(duì)碎片的拼接有一定的難度.為了使問(wèn)題簡(jiǎn)單化,我們聯(lián)想到把文字轉(zhuǎn)化為數(shù)字,其中這些數(shù)字用“0”或者“1”來(lái)代替；半個(gè)字用0表示,整個(gè)字、符號(hào)、空格都用1表示。

其次,我們把紙條中最左邊轉(zhuǎn)化成的數(shù)字按所在行形成左向量,同樣最右邊的那些文字形成一個(gè)右向量。這樣每個(gè)碎紙條都可以用兩個(gè)向量來(lái)表示。進(jìn)而我們就把碎紙片文字的拼接問(wèn)題轉(zhuǎn)化為向量是否相等的問(wèn)題了。如果一個(gè)紙條的左向量和另一個(gè)紙條的右向量相等,說(shuō)明這兩條紙條可拼接到一起，這個(gè)過(guò)程可利用c#編程完成排序[2]。

最后,根據(jù)上述排序結(jié)果,利用MATLAB程序可以檢驗(yàn)c#編程運(yùn)行結(jié)果并實(shí)現(xiàn)紙片的復(fù)原[3,4]。

3 復(fù)原算法的實(shí)現(xiàn)

首先,從對(duì)于給定的來(lái)自同一頁(yè)印刷文字文件的碎紙機(jī)破碎紙片（僅縱切）的向量中找出初始向量。因?yàn)槠扑榍凹埰淖钭筮叺淖侄际钦?我們可以通過(guò)人工干預(yù),很容易把都是整字的碎紙條找出來(lái),即左向量是[0,0,…,0,0]的紙條找出來(lái)。這樣我們就找出了初始向量。假如找到的初始向量為L(zhǎng)i,則初始向量所在紙條的右向量為。

其次，尋找與Ri相等的向量Lj（其中i 不等于j）。假如Ri-Lj=0,即Ri與Lj相等,則第i-1條碎片與第j-1條碎片拼接成功.成功后再用Rj尋找下一條。假如Rj-Lk≠0,則說(shuō)明Rj與Lk不相等,則第j-1條碎片與第k-1條碎片拼接不成功,不成功的話再用Rj-Lk是否等于0來(lái)尋找下一條,{其中,k≠j}；假如Ri-Lj≠0則假如有Ri-Lh=0,則拼接成功.假如Ri-Lh≠0,則依次類推。

最后,由Rm-Ln=0.則碎紙片排序完成。對(duì)于上述過(guò)程。我們建立了如下的流程圖：

例如：下圖是給定碎片，共19支(從左至右編號(hào)000～018)，現(xiàn)將其復(fù)原。

首先，找到其中左側(cè)為整字的碎片，向量表示結(jié)果見(jiàn)附錄1,上圖中第一條碎片是第8條碎片,最后一條碎片是第6條碎片,所以在用該流程時(shí),i=9,n=7。然后,利用MATLAB程序,檢驗(yàn)結(jié)果并將碎紙片拼接復(fù)原。具體程序見(jiàn)附錄2.復(fù)原圖片結(jié)果分別見(jiàn)附錄3。

4 附錄

附錄1

L1=[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1]

R1=[0,0,0,0,0,0,1,1,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1]

L2=[1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0]

R2=[0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0]

L3=[0,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1]

R3=[0,1,0,0,0,0,0,0,1,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0]

L4=[0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0]

R4=[0,0,0,1,0,0,0,1,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0]

L5=[0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0]

R5=[0,0,0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,1,1,1,1,0,0,0,0,0,0,0]

L6=[0,0,0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,1,1,1,1,0,0,0,0,0,0,0]

R6=[0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,1,1,0,0]

L7=[0,0,0,0,0,0,1,1,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1]

R7=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

L8=[1,1,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0]

R8=[0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,1]

L9=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

R9=[1,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0]

L10=[0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,1,1,0,0]

R10=[0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0]

L11=[0,0,0,1,0,0,0,1,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0]

R11=[0,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1]

L12=[0,0,1,1,1,1,1,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0]

R12=[1,1,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0]

L13=[1,0,0,1,0,0,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,0,0,1]

R13=[0,0,1,0,1,1,1,0,1,0,1,1,0,1,1,0,0,1,0,1,1,1,0,1,1,1,1,1]

L14=[0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0]

R14=[1,0,1,0,1,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0]

L15=[1,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0]

R15=[1,0,0,1,0,0,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,0,0,1]

L16=[0,0,1,0,1,1,1,0,1,0,1,1,0,1,1,0,0,1,0,1,1,1,0,1,1,1,1,1]

R16=[0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0]

L17=[0,1,0,0,0,0,0,0,1,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0]

R17=[1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0]

L18=[0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,1]

R18=[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1]

L19=[1,0,1,0,1,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0]

R19=[0,0,1,1,1,1,1,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0]

附錄2

I1=imread ('008.bmp');

I2=imread ('014.bmp');

I3=imread ('012.bmp');

I4=imread ('015.bmp');

I5=imread ('003.bmp');

I6=imread ('010.bmp');

I7=imread ('002.bmp');

I8=imread ('016.bmp');

I9=imread ('001.bmp');

I10=imread ('004.bmp');

I11=imread ('005.bmp');

I12=imread ('009.bmp');

I13=imread ('013.bmp');

I14=imread ('018.bmp');

I15=imread ('011.bmp');

I16=imread ('007.bmp');

I17=imread ('017.bmp');

I18=imread ('000.bmp');

I19=imread ('006.bmp');

I=[I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I18,I19];imshow（I）

附錄3

［1］韓中庚,數(shù)學(xué)建模方法及其應(yīng)用,第二版［M］.北京：高等教育出版社,2009.

［2］王聚豐,楊啟帆.數(shù)學(xué)建模案例集［M］.北京:高等教育出版社,2003.

［3］司守奎,孫璽菁.數(shù)學(xué)建模算法與應(yīng)用［M］.北京：國(guó)防工業(yè)出版社,2011.

［4］賈海燕,碎紙自動(dòng)拼接,http://www.docin.com,2013年9月15日［DB/OL］.