碎紙片還原技術(shù)

李凡

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

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

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

1 前期準(zhǔn)備

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

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

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

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

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

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

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

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

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

2.1 歐氏距離排出邊緣紙片

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

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

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

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

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

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

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

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

2 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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