碎片拼接復原技術研究

詹 燁 陸佳浩

（杭州師范大學，浙江 杭州 311121）

1 研究背景與意義

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

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

2 碎紙片拼接模型的建立

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

在對碎紙片進行了二值化處理之后，我們試著建立一個碎紙片拼接的數(shù)學模型來解決這個問題。在此之前，我們先給出模型的基本假設：

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

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

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

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

本文定義每個像素點的顏色δij，1≤i，j≤1980，其中：

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

（1）建立E 矩陣

為了存儲碎紙片的邊緣特征，我們建立一個19×n 的矩陣E[i，j]。其中i 表示碎片的編號，當表示左側的像素點時j=1，當表示右側的信息時j=2。例如，E[i，j]儲存001 號碎片左側邊緣像素點信息。

（2）建立S 矩陣

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

（3）選取shred with white left

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

（4）提取碎片的行特征

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

（5）匹配度的建立

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

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

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

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

這是一個典型的TSP 問題，權值就是我們上部分求出的匹配度，所以

圖1 TSP 模型示意圖

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

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

總結整個過程，圖中（i，j）邊的權重為wij，設決策變量為xij＝1 說明?。╥，j）已經(jīng)在當前的Hamilton 回路中，則線性規(guī)劃模型可表達我們給出下列的線性規(guī)劃方程：

（7）模型的求解

模型的求解過程如下所示：

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

2）選取shred with white left 作為基準碎片，記為Si，記錄下編號，然后將其從Q 中剔除；

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

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

5）重復過程3）-4）使得Q 為空集；

由此過程得到的編號序列即為所求的最終解。

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

表1 中文紙片拼接順序

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

圖2 Matlab 拼接

圖3 Photoshop 拼接

（8）模型分析

此模型在碎紙片邊緣信息量較為豐富之時，應用效果令人滿意。此次進行19 張碎片的復原，耗時簡短，復原效果能達到100%，完全不需要人工干預。此模型同樣試用于單進行橫向切割的碎紙片復原。

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

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

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

［3］占君,張倩,滿謙,等.MATLAB 函數(shù)查詢手冊[M].北京：機械工業(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 高教社杯全國大學生數(shù)學建模競賽B 題.