陳黎黎，國(guó)紅軍

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

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

1 問(wèn)題的提出

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

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

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

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

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

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

2 碎片預(yù)處理

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

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

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

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

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

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

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

3 碎片的特征提取與匹配

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

圖4 圖片的匹配特征

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

1) 為每條碎片i建立一個(gè)匹配數(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),則對(duì)應(yīng)這個(gè)最大值number(i, k)的碎片k即為碎片i的匹配碎片.

從實(shí)驗(yàn)結(jié)果來(lái)看，在實(shí)驗(yàn)中出現(xiàn)了許多碎片與某一條碎片匹配度極高的情況.究其原因，是因?yàn)樵谒槠ヅ涮卣魈崛〉臅r(shí)候，僅考慮了碎片在一整行上的總體特征，忽略了每行左右切割邊界處特征的相異性，提取的特征比較粗糙，所以造成了匹配效率較低的現(xiàn)象.

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

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

5 實(shí)驗(yàn)結(jié)果

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

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

經(jīng)過(guò)與原文對(duì)比，上述實(shí)驗(yàn)結(jié)果完全正確.

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

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

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

2) 本算法僅適用于單面規(guī)則縱切的碎片的拼接復(fù)原，對(duì)于縱橫切碎的文檔碎片，以及雙面縱橫切碎的文檔碎片在拼接時(shí)需要考慮的因素較為復(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] 朱延娟,周來(lái)水,張麗艷,等.基于Hausdorff距離的多尺度輪廓匹配算法[J].中國(guó)機(jī)械工程,2004,15(17):1553-1561.

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