基于文檔內(nèi)容的碎紙拼接技術(shù)

陳黎黎，國紅軍

(宿州學(xué)院 信息工程學(xué)院，安徽 宿州 234000)

破碎文件的拼接技術(shù)在刑偵案件中的物證復(fù)原、考古研究中的歷史文件和壁畫修復(fù)以及軍事情報獲取等領(lǐng)域發(fā)揮著極其重要的作用.早期，碎片拼接復(fù)原工作是由人通過手工操作完成的，盡管拼接復(fù)原的準(zhǔn)確率較高，但工作效率極低，特別是當(dāng)碎片數(shù)量巨大時，手工拼接過程費時費力，一般很難在較短的時間內(nèi)完成.隨著計算機技術(shù)的飛速發(fā)展，為提高破碎文件的拼接和復(fù)原效率，人們逐步開始研究文件碎紙片自動拼接技術(shù)，即從許多散亂的文件碎片中，借助計算機通過特征匹配技術(shù)來識別出相鄰的碎片，進(jìn)而重現(xiàn)整個文件的原貌.

1 問題的提出

目前，國內(nèi)外有關(guān)碎片拼接的方法有很多種.根據(jù)碎片特征可分為基于輪廓、色彩、紋理等特征的圖像碎片拼接；根據(jù)碎片形狀可分為規(guī)則碎片和不規(guī)則碎片的拼接；根據(jù)碎片的空間特征可分為二維和三維圖像碎片的拼接等.

大部分對碎片拼接復(fù)原方法的研究主要集中在碎片輪廓的匹配上，即基于輪廓的碎片拼接技術(shù)研究.許多學(xué)者提出了大量的算法，如，Helena Cristina da Gama Leitao etc[1]提出了一種典型的解決平面圖像碎片匹配算法.H.J.Wolfson等[2]運用串匹配的技術(shù)查詢最大匹配子串，解決了平面曲線匹配的問題.Ying Shan等[3]提出了一種概率框架的曲線匹配算法.朱良家等[4]對碎紙輪廓提取技術(shù)進(jìn)行研究，通過對候選集評分的方式實現(xiàn)了對圖像碎片的拼接.朱延娟等[5]提出基于Hausdorff距離的多尺度輪廓匹配算法等.這些算法實現(xiàn)了對碎片輪廓的匹配，已取得了一定的成果.但是，通常被碎紙機切碎的帶有文字或圖像信息的文檔，其邊緣是規(guī)則的，以上算法對這類碎片進(jìn)行拼接復(fù)原時顯然會失效[6].因此，研究基于文檔內(nèi)容的規(guī)則碎紙拼接技術(shù)是十分必要的.本文討論的是被碎紙機橫向或縱向規(guī)則切開的碎片的拼接復(fù)原技術(shù)，并在研究過程中做如下假設(shè)：

假設(shè)一：任意兩碎紙片的長度、寬度相等.

假設(shè)二：任意兩碎紙片間的厚度與紙張材料相同.

假設(shè)三：任意碎紙片在切割后無信息丟失(即無破損).

假設(shè)四：所有碎紙片無丟失、無多余、無沾污.

2 碎片預(yù)處理

為方便計算機對文件碎片進(jìn)行拼接處理，首先將每張碎片通過掃描儀轉(zhuǎn)換為bmp格式的圖片并傳輸?shù)接嬎銠C中，然后再對碎片圖像進(jìn)行預(yù)處理.

由于掃描文件碎片的時候可能會發(fā)生傾斜現(xiàn)象，為此需要對傾斜圖像進(jìn)行調(diào)整.首先，找到傾斜圖像的1至50列每一列最上面像素值為0的點，從這50個點中選出最上面的點.按此方法找出第51至100列(碎片圖像的寬度總列數(shù)大于100)中處于最上面的像素值為0的點.利用這兩個點找出平行于碎片中文字的直線，如圖1.

圖1 發(fā)生傾斜的碎片

然后根據(jù)直線的斜率進(jìn)行碎片角度的調(diào)整，調(diào)整后的碎片圖像如圖2所示.

圖2 調(diào)整方向后的碎片

本文以每頁打印紙被縱切19條碎片為例，其中的某一條文件碎片經(jīng)預(yù)處理后如圖3所示.

圖3 預(yù)處理后的縱切碎片

3 碎片的特征提取與匹配

經(jīng)過預(yù)處理后的圖像，按其圖像的行數(shù)構(gòu)建一個長度與之相等的一維數(shù)組.對圖像進(jìn)行逐行掃描，若此行含有像素值為0的點，則將對應(yīng)此行的數(shù)組元素值設(shè)置為0，否則為1.圖3對應(yīng)的縱切碎片經(jīng)上述轉(zhuǎn)換后提取出的匹配特征如圖4所示.

圖4 圖片的匹配特征

某一頁面被縱切成的19條文件碎片按如上方法提取出對應(yīng)的匹配特征后，將每條碎片的特征與其余的18條碎片的特征進(jìn)行比較，以尋找匹配的碎片，具體步驟為：

1) 為每條碎片i建立一個匹配數(shù)組number(i,19);

2) 碎片i與其余每條碎片j進(jìn)行特征比較.如果兩碎片相應(yīng)位置的特征值相等，則進(jìn)行umber(i, j) = number(i, j) + 1;

3) 找出碎片i的匹配數(shù)組number(i, 19)中的最大值number(i, k),則對應(yīng)這個最大值number(i, k)的碎片k即為碎片i的匹配碎片.

從實驗結(jié)果來看，在實驗中出現(xiàn)了許多碎片與某一條碎片匹配度極高的情況.究其原因，是因為在碎片匹配特征提取的時候，僅考慮了碎片在一整行上的總體特征，忽略了每行左右切割邊界處特征的相異性，提取的特征比較粗糙，所以造成了匹配效率較低的現(xiàn)象.

4 碎片匹配算法改進(jìn)

為提高碎片的配準(zhǔn)率，同時確保能夠準(zhǔn)確分辨出兩碎片的左右關(guān)系，需要對上述匹配算法進(jìn)行改進(jìn).在對碎片特征進(jìn)行提取時，分別考慮每條碎片的左右邊界特征，將每條碎片的右邊界(最后一列)特征與其余碎片的左邊界(第一列)特征進(jìn)行對比，以此確定是否匹配，對應(yīng)的算法流程如圖5：

5 實驗結(jié)果

我們將來自同一頁面，內(nèi)容為英文的19條縱切文件碎片(圖6所示)進(jìn)行隨機編號，即000號-018號，對這些碎片建立拼接復(fù)原模型，并按如上算法進(jìn)行了拼接實驗，結(jié)果如下：

英文碎片拼接順序編號：003，006，002，007，015，018，011，000，005，001，009，013，010，008，012，014，017，016，004.

經(jīng)過與原文對比，上述實驗結(jié)果完全正確.

文檔碎片拼接復(fù)原技術(shù)是信息安全中的重要技術(shù)，它在警方獲取證物及其他重要信息的獲取等方面擔(dān)負(fù)重要角色.鑒于文檔碎片拼接復(fù)原技術(shù)的重要性，世界上已經(jīng)開展了相關(guān)研究，但能夠查閱到的資料相對比較少.目前在文檔碎片拼接方面主要使用曲線的特征來進(jìn)行碎片拼接，計算量非常大.本文在借鑒基于曲線特征的碎片匹配相關(guān)技術(shù)的基礎(chǔ)上提出了對沿文字方向縱向規(guī)則切開的碎片拼接方法.最后通過實驗對本人提出的算法和方法進(jìn)行了驗證.實驗結(jié)果說明，該方法具有簡單、方便、快速、高效的特點.

但本文在許多方面仍有待進(jìn)一步研究，主要包括以下幾點：

1) 本文提出的文檔碎片拼接技術(shù)面向的對象過于理想化，應(yīng)用的領(lǐng)域有局限性.

2) 本算法僅適用于單面規(guī)則縱切的碎片的拼接復(fù)原，對于縱橫切碎的文檔碎片，以及雙面縱橫切碎的文檔碎片在拼接時需要考慮的因素較為復(fù)雜，其拼接復(fù)原算法還有待研究.

圖5 碎片匹配算法流程

圖6 英文縱切碎片

圖7 碎片拼接結(jié)果

[1] LEITAO H C G, STOLFI J.A Multiscale Method for the Reassembly of Two-Dimensional Fagmented Ojects[J].IEEE Trans Patt Anal Machine Intell,2002,24(9):1239-1251.

[2] WOLFSON H J. On Curve Matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence.1990,12(5):483-489.

[3] SHAN Ying, ZHANG Zhengyou.New Measurements and Corner-Guidance for Curve Matching with Probabilistic Relaxation[J].International journal of Computer Vision.2002,46(2):157-171.

[4] ZHU Liangjia, ZHOU Zongtan, HU Dewen.Globally Consistent Reconstruction of Ripped-Up Documents[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(1):1-13.

[5] 朱延娟,周來水,張麗艷,等.基于Hausdorff距離的多尺度輪廓匹配算法[J].中國機械工程,2004,15(17):1553-1561.

[6] 羅智中.基于文字特征的文檔碎紙片半自動拼接[J].計算機工程與應(yīng)用,2012,48(5):207-210.