碎紙片還原技術的研究

張立臣 肖松平 王國慶 謝冬雪 周旭

摘 要：碎紙片的還原在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有重要應用。本文考慮到計算機不能自動識別圖片中的文字所以對文字進行了灰度處理得出圖像中每一個像素點的灰度值，將文字信息轉化為數字信息，得到一個1980×72的數字矩陣。而切割處的灰度值應該是近似相等的。由于白紙黑字的區分度是比較好的，因此采用0-1整數規劃模型以及聚類分析，以切割處左右兩端的灰度值相差絕對值之和最小為目標，利用貪心算法逐步搜索，最終拼出完整的印刷文字文件。準確還原碎紙片對文獻修復、證物復原等都提供了良好的理論基礎。

關鍵詞：灰度處理；0-1整數規劃；貪心算法；

0引言

破碎文件的拼接以及漢字識別應用的領域越來越廣泛，更高的要求了識別資源的實時性。本文建立的模型可推廣應用于漢字識別系統，資源消耗少、識別速度快，有著很好的應用前景。還可以推廣到類似的研究方向如在文物碎片的自動修復、虛擬考古、醫學分析等領域。

1.前期準備過程

1.1基于0-1整數規劃的圖片處理

選取格式為MBP且位圖數據為8的材料，對數據進行灰度化處理過程中，需要將其轉化為RGB三通道顏色格式，使用24位來表示一個像素點。同時考慮到JPEG格式的圖形具有容量小，處理穩定的特點，因此將其轉化為24位深度的JPEG格式。之后，對碎紙片的圖像進行灰度處理，得出圖像中每一個像素點的灰度值。而灰度值本身的大小則取決于像素點中所含的紅、綠、藍三種成分。為了簡化數據處理及其運算，采用0-1整數規劃對圖像進行二值化處理，將使用閾值變換法[1]把灰度圖像轉換成二值圖像。所謂二值圖像， 一般意義上是指只有純黑（0）、純白（255）兩種顏色的圖像。

在灰度化處理中，MATLAB 默認運用的加權平均法，即加權平均法根據重要性及其它指標，將三個分量以不同的權值進行加權平均。因此，按下式對RGB 三分量進行加權平均能得到較合理的灰度圖像。

采用最大類間方差法[2]來求閾值，最大類間方差的基本思想是使用一個閾值將整個數據分成兩個類，方差的定義如下：

如果兩個類之間的方差最大，那么這個閾值就是最佳的閾值。其閾值將由系統自帶的函數處理而得來：

描述碎片的模型為圖像的各個灰度值所組成的灰度矩陣，即圖像上的每個像素點都可以對應到灰度矩陣的每個元素。每個碎紙片均可以確定一個同型的灰度矩陣，因此灰度矩陣的特征可以反映圖像的特征，其每一列構成了一個描述局部特征的列向量。

1.2基于貪心算法思想的搜索

由于附件中所給碎紙片均為白紙黑字，因此原圖切割前的信息具有一定的連續性，本文對于問題一的拼接過程使用貪心算法的思想[3]。問題一只考慮縱切的情況，因此設 、 分別左右的表示兩個碎紙片所對應的灰度矩陣，則 矩陣的最后一列元素與 矩陣的第一列元素之間的偏差距離函數可以表示為：

其中，A1（n，72） 代表A1 矩陣的第72列，An（n，1） 代表An 矩陣的第一列，若存在An 使得y（A1，An） 達到最小，則An 代表的碎紙片即可與A1 代表的碎紙片拼接，通過MATLAB 來實現。最初得出的結果為大體碎片均可以成功拼接復原，但就整張紙而言，從中間位置處左右顛倒，由于給定的來自同一頁印刷文字文件左右兩端均為空白由上述函數求值很容易可以求得最小值，因此在貪心算法搜索過程中優先把左右兩端進行了拼接。本文首先確定出最左側的碎片即左側空白最寬，然后從剩下的樣本中尋找與碎紙片的邊界差異度最小的碎片作為下一個碎片，再尋找與第2個碎片配對的第3個碎片，以此類推，解決了碎紙片整篇存在左右顛倒的情況，并且減少了計算量。最終，在沒有進行人工干預，成功地將附件1、2碎紙片分別拼接復原，模型簡單操作簡單，準確率高達100%。

2.橫、縱切的單面碎紙片的拼接復原模型

2.1中文文件的拼接復原

2.1.1歐氏距離排出邊緣紙片

由題意及附件所給信息可知，對于中文的文件，撕碎的原紙張四周的空白間距大于行間距的空白間距，因此可先根據空白間距較大的特點求出原紙張四周碎紙片的編號，以左側為例。考慮到節約算法的空間復雜度，本問舍棄了全局搜索的貪心算法，巧妙利用題一中擬合的思想，采用0-1整數規劃對109張圖進行二值化處理后，求其邊界的歐式距離[4]：

在灰度圖像中，一張紙張的圖像可以表示為一個二維數組，其中（i，j） 對應的像素點的灰度值，設 為目標點集合，計算邊界的歐氏距離。取其距離為0的左側圖形，對每張碎紙片圖像的上下邊緣進行歐氏距離的比較，得出可在無人工干擾的情況下自動排出左側的紙片順序，按照上述方法計算歐式距離，可以較快地自動排出原紙張右側、上側、下側的碎紙片的拼接順序。

在無人工干預的情況下，準確地排出原紙張四個邊緣的碎紙片的順序，得到邊緣復原結果，并在一定程度上節約了算法的空間復雜度[5]。

2.1.2內部紙片的拼接

根據上述已經準確排出原紙張四個邊緣的碎紙片的排列順序，從左上角開始，在問題一中取碎紙片A1灰度矩陣的最后一列元素與A2 灰度矩陣的第一列元素之間的偏差距離[12]最小的作為下一張碎紙片拼接，以此類推。在問題二中，采取上述的方法進行模擬運行，發現由于碎紙片的數目增多，匹配率達不到預期的目標，往往需要人工干預進行調整，故為了確保碎紙片的拼接準確率，需要考慮引入更多的有關變量來進行匹配搜索。經過演繹推理，碎紙片由于橫縱切，因此內部紙片的排序需要綜合上側碎紙片的下邊緣灰度值和左側紙片的右邊緣灰度值，依據公式計算其三張碎紙片間的歐氏距離之和：

選取距離最小的匹配紙片，做下記錄，并利用貪心算法的思想，以此為新的已知碎片進行下一步的搜索匹配。根據上述模型，經過仿真模擬大大減少了人工干預，基本不需要外界輔助，基本實現了中文文件橫縱切割碎紙片的自動拼接復原。

3. 結論

在橫縱切的碎紙片中，我們分別依據中文、英文的結構特征，選取了先確定邊緣，后雙變量匹配搜索的數學模型。先邊界后內部的逐漸填充的列向排列的方式，省去了橫向合并的步驟，并在英文拼接過程中，引入聚類優化的二步篩選過程，在局部內尋求正解，減少了模型的算法復雜性且正確率理想，實現了碎紙片的橫縱切割的拼接復原。可推廣應用于漢字識別系統，資源消耗少、識別速度快，有著很好的應用前景。還可以推廣到類似的研究方向如在文物碎片的自動修復、虛擬考古、醫學分析等領域。為準確還原碎紙片對文獻修復、證物復原等都提供了良好的理論基礎。

參考文獻：

[1]楊治平.基于自適應多閾值變換編碼的圖象二值化處理[J].重慶師范學院學 報 （自然科學版），2001

[2]齊麗娜，張博，王戰凱.最大類間方差法在圖像處理中的應用[J].無線電工 程，2006，（07）