碎片拼接復(fù)原技術(shù)研究

詹 燁 陸佳浩

（杭州師范大學(xué)，浙江 杭州 311121）

1 研究背景與意義

傳統(tǒng)的拼接復(fù)原工作需要由人工完成，雖然準(zhǔn)確率較高，但效率很低，不適合運(yùn)用于大量拼接。隨著計(jì)算機(jī)技術(shù)的發(fā)展，破碎紙片的自動(dòng)拼接技術(shù)運(yùn)用而生，使其在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域獲得更加廣泛、便捷的應(yīng)用。但是，目前研究較多的自動(dòng)化拼接一般都是利用碎片邊緣的面積特征、尖點(diǎn)特征、尖角特征等幾何特征，探索與之相匹配的相鄰碎紙片進(jìn)行拼接。這種基于邊界形狀的拼接方法并不適用于邊緣形狀相似的碎紙片。由于規(guī)則碎片其每一片碎片的大小、形狀都是相同的，因此，利用形狀、輪廓進(jìn)行拼接不是很實(shí)際。通常情況下，文檔是被手或者碎紙機(jī)撕碎的。其中手撕的文件將會(huì)產(chǎn)生不規(guī)則的碎紙片。而一種碎紙機(jī)將文件切成成條狀,在這種情況下,產(chǎn)生的文檔被稱為條形文檔。當(dāng)然也有從水平和垂直方向來(lái)進(jìn)行的碎紙機(jī)，這種類型的機(jī)器就會(huì)產(chǎn)生正交分解文檔。關(guān)于重建的問(wèn)題,這些文件可以被認(rèn)為是一個(gè)特殊的拼圖。給定N 碎片，每個(gè)二進(jìn)制位圖的大小都是W×H 像素,并假設(shè)碎片放在正確的方向，重構(gòu)分解文檔就是找到這些碎片的正確定位使得它們組成原始文檔。在重建條形文檔的這個(gè)問(wèn)題所能參考的研究很少。Prandtstetter 和Raidl 提出鄰域搜索方法,它使用一個(gè)特定的變量的方法來(lái)重建文件，涉及用戶在過(guò)程中進(jìn)行人工干預(yù)從而提高正確率。Ukovich 等人提出了一個(gè)算法重建條形粉碎文件，特別重視使用MPEG7 描述符的可能性。如Marques 和Freitas 使用邊界顏色和利用最近鄰算法來(lái)計(jì)算對(duì)應(yīng)的特征向量之間的歐幾里得距離等特征。

通過(guò)建立的模型，我們能夠研究利用計(jì)算機(jī)進(jìn)行不規(guī)則和規(guī)則碎片的拼接，幫助人們快速地獲得大致的拼接結(jié)果。在此基礎(chǔ)上，再加以人工干預(yù)，更快得到拼接的結(jié)果，提高拼接的速率和正確率。

2 碎紙片拼接模型的建立

中文規(guī)則碎紙片的拼接模型：

在對(duì)碎紙片進(jìn)行了二值化處理之后，我們?cè)囍⒁粋€(gè)碎紙片拼接的數(shù)學(xué)模型來(lái)解決這個(gè)問(wèn)題。在此之前，我們先給出模型的基本假設(shè)：

假設(shè)一：整張紙張切割完整，碎片內(nèi)沒有丟失部分像素并且在切割之后所得碎紙片都全等；

假設(shè)二：字與字之間的行間距都是相等的，沒有發(fā)生突變的行為。

在建立模型之前，我們需要看一下實(shí)際的問(wèn)題：對(duì)于給定的來(lái)自同一頁(yè)印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對(duì)附件1 給出的中文文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過(guò)程需要人工干預(yù)，請(qǐng)寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果以圖片形式及表格形式表達(dá)。①

除去文字本身，我們可以把每張碎紙片看出只有黑白兩種顏色的圖像。通常遇到這種情景的圖像可以用二值法來(lái)表示圖像。一幅二值圖像[3]的二維矩陣僅有{0，1}兩個(gè)值構(gòu)成，“0”代表黑色，“1”代表白色。將圖像中的像素點(diǎn)分別用{0，1}表示，把文字圖像數(shù)字化，便于拼接修復(fù)。二值圖像通常用于文字,線條圖的掃描識(shí)別OCR，本文嘗試運(yùn)用二值圖像修復(fù)碎紙片。

本文定義每個(gè)像素點(diǎn)的顏色δij，1≤i，j≤1980，其中：

在中文文章中，我們一般會(huì)在文章的四周留下頁(yè)邊距，則完整的文章周圍應(yīng)該全是白色，用{0，1}表示文章的邊界處應(yīng)該全為1。那么在尋找邊界紙片時(shí)，我們是否可以認(rèn)為：當(dāng)碎紙片的某條邊界全為1時(shí)，此碎紙片可能位于文章的邊界處。

（1）建立E 矩陣

為了存儲(chǔ)碎紙片的邊緣特征，我們建立一個(gè)19×n 的矩陣E[i，j]。其中i 表示碎片的編號(hào)，當(dāng)表示左側(cè)的像素點(diǎn)時(shí)j=1，當(dāng)表示右側(cè)的信息時(shí)j=2。例如，E[i，j]儲(chǔ)存001 號(hào)碎片左側(cè)邊緣像素點(diǎn)信息。

（2）建立S 矩陣

根據(jù)已經(jīng)建立的E[i，j]矩陣，我們通過(guò)計(jì)算得到一個(gè)19×2 的S[i，j]矩陣，這個(gè)矩陣儲(chǔ)存的是每一條碎片邊緣取值為0 的像素點(diǎn)（即為黑色的像素）的數(shù)量。例如，S[i，j]=350 表示001 號(hào)碎片的左側(cè)邊緣有350 個(gè)黑色像素點(diǎn)。

（3）選取shred with white left

根據(jù)S 矩陣，若S[i,1]=0，即在這個(gè)碎片的最左端沒有任何的像素點(diǎn)，那么我們就認(rèn)為該碎片在原始文件中處最左端，即為選取的shred with white left。

（4）提取碎片的行特征

根據(jù)觀察，原始圖像的文字特征較為明顯，尤其是行特征，因此我們采取提取碎片的行特征的形式（具體的我們?cè)谙旅骊U述）。首先我們需要確定一個(gè)上界，確定依次向下取w 為行寬（調(diào)整結(jié)果發(fā)現(xiàn)取w=40 pixels 可以較好的保證能容納每一個(gè) 文字，也不至于太寬）直至下邊緣，得到每條碎片的行數(shù)為{n1，n2，…，n19}；然后取n=max{n1，n2，…，n19}確定為最終的行數(shù)，然后以該條碎片的行化方式為基準(zhǔn)，來(lái)對(duì)每一條碎片進(jìn)行行化，最終每一條碎片被劃分為28 行。

（5）匹配度的建立

基于上述的分析和操作過(guò)程，得到的S 矩陣已經(jīng)提取了一個(gè)碎紙片邊緣蘊(yùn)含的大部分文字信息。據(jù)此我們建立兩個(gè)碎紙片的匹配度，其計(jì)算公式如下所示：

這里的n 就是上文的總行數(shù)，而mijk表示碎片i 和碎片j 第k 行之間的匹配度；Mij表示碎片i 和碎片j 之間的匹配度。我們之所以不采用全部像素點(diǎn)進(jìn)行匹配的原因是因?yàn)闊o(wú)法體現(xiàn)行之間的差別，會(huì)造成部分信息的流失，影響匹配質(zhì)量。

（6）數(shù)學(xué)模型的建立

根據(jù)上述定義的匹配度，我們可以計(jì)算得到19 個(gè)矩陣兩兩匹配的匹配度，所以拼接碎紙片的問(wèn)題就演變成下列模型的求解：尋求一個(gè)序列，使得這個(gè)序列的匹配度在所有序列中最大。如右圖1 所示：

這是一個(gè)典型的TSP 問(wèn)題，權(quán)值就是我們上部分求出的匹配度，所以

圖1 TSP 模型示意圖

（1）用圖中的節(jié)點(diǎn)表示碎片，其中的有向線段wij，且wij＝1－Mij，箭頭的由A 指向B 就是將A 的右邊緣和B 的左邊緣進(jìn)行匹配的費(fèi)用。

（3）現(xiàn)需要尋找一條回路遍歷所有的節(jié)點(diǎn)使得總費(fèi)用最小。回路的開端是我們之前尋找的shred with white left。

總結(jié)整個(gè)過(guò)程，圖中（i，j）邊的權(quán)重為wij，設(shè)決策變量為xij＝1 說(shuō)明弧（i，j）已經(jīng)在當(dāng)前的Hamilton 回路中，則線性規(guī)劃模型可表達(dá)我們給出下列的線性規(guī)劃方程：

（7）模型的求解

模型的求解過(guò)程如下所示：

1）將所有碎片放入地址池中組成集合Q；

2）選取shred with white left 作為基準(zhǔn)碎片，記為Si，記錄下編號(hào)，然后將其從Q 中剔除；

3）分別計(jì)算Si右側(cè)邊緣與Q 其他碎片Sj左側(cè)邊緣的匹配度Mij；

4）選取使得Mij最大的那個(gè)碎片St作為Si的右側(cè)碎片，記錄下編號(hào)，從Q 中剔除Si后令i＝t；

5）重復(fù)過(guò)程3）-4）使得Q 為空集；

由此過(guò)程得到的編號(hào)序列即為所求的最終解。

現(xiàn)在將此算法應(yīng)用于2.2.1 開頭所提的問(wèn)題，得到如下序列。

表1 中文紙片拼接順序

利用matlab 設(shè)計(jì)程序得到下列的拼接圖像，考慮其清晰度，利用photoshop 進(jìn)行了更為清楚的還原，原文是蘇軾的《題淮山樓》，具體如下所示。

圖2 Matlab 拼接

圖3 Photoshop 拼接

（8）模型分析

此模型在碎紙片邊緣信息量較為豐富之時(shí)，應(yīng)用效果令人滿意。此次進(jìn)行19 張碎片的復(fù)原，耗時(shí)簡(jiǎn)短，復(fù)原效果能達(dá)到100%，完全不需要人工干預(yù)。此模型同樣試用于單進(jìn)行橫向切割的碎紙片復(fù)原。

當(dāng)邊緣信息量減少，即碎紙片的數(shù)量變多，切割的方式變得復(fù)雜時(shí)，模型的滿意度就會(huì)下降，可能會(huì)需要人工干預(yù)。當(dāng)邊緣信息量繼續(xù)減少，模型的求解會(huì)變得繁瑣，導(dǎo)致人工干預(yù)的大量增加。

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

［2］姜啟源,謝金星,葉俊.數(shù)學(xué)模型[M].北京：高等教育出版社,1987,04：13-16.

［3］占君,張倩,滿謙,等.MATLAB 函數(shù)查詢手冊(cè)[M].北京：機(jī)械工業(yè)出版社,2011,1：19-20,74-152.

［4］Christian Schauer,Matthias Prandtstetter,and Günther R.Raidl.A Memetic Algorithm for Reconstructing Cross-Cut Shredded Text Documents[J].Institute of Computer Graphics and Algorithms Vienna University of Technology,Vienna,Austria.

［5］Johannes Perl,Markus Diem,Florian Kleber,and Robert Sablatnig.Strip Shredded Document Reconstruction Using Optical Character Recognition[C]//Imagingfor Crime Detection and Prevention 2011(ICDP 2011),4th International Conference on,pages 1-6,nov.2011.

［6］Azzam Sleit·Yacoub Massad.An alternative clustering approach for reconstructing cross cut shredded text documents[J].Telecommun Syst(2013).

注釋：

①2013 高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B 題.