碎紙片還原技術(shù)

李凡

摘 要：碎紙片的還原在司法物證復(fù)原、歷史文獻修復(fù)以及軍事情報獲取等領(lǐng)域都有重要應(yīng)用。本文考慮到由于計算機無法自動辨別碎紙片中原有的文字，因此對碎紙片進行了灰度處理，計算出圖像中每一個像素點的灰度值，實現(xiàn)了文字信息向數(shù)字信息的轉(zhuǎn)化。因為文件的白紙黑字存在明顯的區(qū)分度，所以運用0-1整數(shù)規(guī)劃模型將切碎片邊緣兩側(cè)的灰度值之差的絕對值之和最小為目標，利用貪心算法逐步計算，從而復(fù)原原有的文件，此技術(shù)在文獻修復(fù)、證物復(fù)原等方面存在良好的應(yīng)用前景。

關(guān)鍵詞：灰度處理;貪心算法;0-1整數(shù)規(guī)劃

人工拼接很難在短時間內(nèi)實現(xiàn)碎紙片文件的復(fù)原。近年來計算機技術(shù)的開發(fā)與運用日漸成熟，人們嘗試開發(fā)碎紙片的自動拼接技術(shù)，用來提高拼接復(fù)原效率?；谒榧埰凶舟E斷線同文字的匹配程度考慮，本文利用0-1整數(shù)規(guī)劃、灰度處理、貪心算法等方法解決該問題，達到了預(yù)期的良好結(jié)果。建立的模型在漢字識別系統(tǒng)、文物碎片的自動修復(fù)、虛擬考古、醫(yī)學(xué)分析等領(lǐng)域都將有很好的應(yīng)用前景。

1 前期準備

1.1 基于0-1整數(shù)規(guī)劃的圖片處理

對碎紙片的圖像進行灰度處理，得出圖像中每一個像素點的灰度值。為了簡化數(shù)據(jù)處理及其運算，采用0-1整數(shù)規(guī)劃對圖像進行二值化處理，利用閾值變換法[1]把灰度圖像轉(zhuǎn)換成二值圖像。在灰度化處理中，MATLAB默認運用的加權(quán)平均法，因此，按下式進行加權(quán)計算可得到較合理的灰度圖像。

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

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

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

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

基于碎紙片原圖損壞前的內(nèi)容具有一定的關(guān)聯(lián)性，采用貪心算

法[3]的思想用A1、A2代表兩個灰度矩陣，分別對應(yīng)任一兩個碎紙片，則A1矩陣的最后一列元素與A2矩陣的第一列元素之間的偏差距離函數(shù)可用下式表示：

2 中文文件的拼接復(fù)原

2.1 歐氏距離排出邊緣紙片

基于中文文件損毀的原紙張邊緣的空白間距大于內(nèi)部行間距的空白間距的特性，可先根據(jù)此特性求出原紙張四周碎紙片的編號，以左側(cè)碎紙片為例。采用0-1整數(shù)規(guī)劃將紙片二值化處理，計算其邊界的歐氏距離[4]：

在灰度圖像中，一張碎片的圖像可以表示為一個二維數(shù)組，其中（i，j）對應(yīng)像素點的灰度值，設(shè)為目標點集合，計算邊界的歐氏距離。取其距離為0的左側(cè)圖形，對每張碎紙片圖像的上下邊緣進行歐氏距離的比較，準確地排出原紙張四個邊緣的碎紙片的順序，得到邊緣復(fù)原結(jié)果。

2.2 內(nèi)部紙片的拼接

根據(jù)上述已經(jīng)準確排出原紙張四個邊緣的碎紙片的排列順序，從左上角開始，取碎紙片A1灰度矩陣的最后一列元素與A2灰度矩陣的第一列元素之間的偏差距離最小的作為下一張碎紙片拼接，以此類推。為了確保碎紙片的拼接準確率，內(nèi)部紙片的排序需要綜合上側(cè)碎紙片的下邊緣灰度值和左側(cè)紙片的右邊緣灰度值[5]，依據(jù)公式計算其三張碎紙片間的歐氏距離之和：

選取距離最小的匹配紙片，做下記錄，并利用貪心算法的思想，以此為新的已知碎片進行下一步的搜索匹配。根據(jù)上述模型，基本不需要外界輔助，基本實現(xiàn)了中文文件橫縱切割碎紙片的自動拼接復(fù)原。

1.3 英文文件的拼接復(fù)原

由于英文的四線三格的特殊書寫模式導(dǎo)致其邊緣的灰度值數(shù)據(jù)不足[6]，不能夠精確的搜索到正確的碎紙片來進行匹配，因此選取一個右上角的碎片作為試驗匹配樣本，

為確保得到的碎紙片是合理位置，對碎紙片進行聚類分析從而進一步篩選。為使英文文件的拼接復(fù)原更好地解決，本文首先參照中文文件的建模方法，準確找出完整文件周圍四個損毀紙片的正確順序，以左上角為切入點，計算上側(cè)紙片的下邊緣灰度值和左側(cè)紙片的右邊緣灰度值，依據(jù)公式求解其碎紙片間的歐氏距離之和，將歐氏距離之和升序排序，篩選最小的十個碎紙片作為一個解集，并依據(jù)確定的最左側(cè)邊緣碎片的上邊距及其下邊距進行聚類分析，在解集范圍內(nèi)尋求最優(yōu)解。以此類推完成第二列的排序。由模擬仿真所驗算，此類先確定解集范圍，再進行優(yōu)化聚類確定正解的數(shù)學(xué)模型，深度優(yōu)化了全局篩選出正確的碎紙片的時間復(fù)雜度和空間復(fù)雜度[5]。

2 結(jié)論

在橫縱切的碎紙片中，我們分別依據(jù)中文、英文的結(jié)構(gòu)特征，選取了先確定邊緣，后雙變量匹配搜索的數(shù)學(xué)模型。先邊界后內(nèi)部的逐漸填充的列向排列的方式，省去了橫向合并的步驟，并在英文拼接過程中，引入聚類優(yōu)化的二步篩選過程，在局部內(nèi)尋求正解，減少了模型的算法復(fù)雜性且正確率理想，實現(xiàn)了碎紙片的橫縱切割的拼接復(fù)原。可推廣應(yīng)用于文字識別系統(tǒng)、文物碎片的修復(fù)、虛擬考古、醫(yī)學(xué)分析等領(lǐng)域。此方法資源消耗少、識別速度快，有著很好的應(yīng)用前景。

參考文獻

[1]楊治平.基于自適應(yīng)多閾值變換編碼的圖像二值化處理[J].重慶師范學(xué)院學(xué)報：自然科學(xué)版（3）：77-80.

[2]齊麗娜，張博，王戰(zhàn)凱.最大類間方差法在圖像處理中的應(yīng)用[J].無線電工程，2006（07）：29-30+48.

[3]李金旭，朱景立，黃悅悅.求解TSP的隨機貪心算法[J].漯河職業(yè)技術(shù)學(xué)院學(xué)報，2015（05）：32-35.

[4]黃文奇，劉景發(fā).基于歐氏距離的矩形Packing問題的確定性啟發(fā)式求解算法[J].計算機學(xué)報，2006，029（005）：734-739.

[5]徐菲.淺析算法及算法復(fù)雜性[J].科技信息，2012，000（033）：247，256.

[6]王文遠.基于灰度值數(shù)學(xué)形態(tài)算子處理的各向異性擴散[J].復(fù)旦學(xué)報：自然科學(xué)版，2004，43（5）：884-888.