碎紙片還原技術(shù)的研究

張立臣 肖松平 王國(guó)慶 謝冬雪 周旭

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

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

0引言

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

1.前期準(zhǔn)備過程

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

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

在灰度化處理中，MATLAB 默認(rèn)運(yùn)用的加權(quán)平均法，即加權(quán)平均法根據(jù)重要性及其它指標(biāo)，將三個(gè)分量以不同的權(quán)值進(jìn)行加權(quán)平均。因此，按下式對(duì)RGB 三分量進(jìn)行加權(quán)平均能得到較合理的灰度圖像。

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

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

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

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

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

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

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

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

2.1.1歐氏距離排出邊緣紙片

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

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

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

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

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

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

3. 結(jié)論

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

參考文獻(xiàn)：

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

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