基于0-1邊緣灰度匹配的英文碎紙片復(fù)原

趙靜文 馬毓華 張新雨 王淑萍 郭珈琿

【摘 要】破碎文件拼接復(fù)原在許多領(lǐng)域內(nèi)有著極為重要的應(yīng)用，成為新的“黑科技”。為代替古老的人工復(fù)原方法，嘗試實(shí)現(xiàn)機(jī)器化操作提高復(fù)原效率，本文基于碎紙片邊緣灰度向量（矩陣）的匹配度計(jì)算進(jìn)行拼接復(fù)原。對雙面英文紙片縱、橫切的情況，首先仍采用k均值聚類算法進(jìn)行聚類，將處在同一行的正反兩面碎片劃為一類，其次利用鏡像原理處理得到新型碎片，對新型碎片采用0-1邊緣灰度匹配完成橫向拼接，然后基于0-1灰度值匹配度的基礎(chǔ)上，利用特殊化的TSP復(fù)原優(yōu)化模型優(yōu)化縱向拼接，從而使碎圖復(fù)原。

【關(guān)鍵詞】0-1兩值化處理;匹配度K均值聚類;灰度垂直投影;鏡像原理 一、背景提出

破碎文件的拼接復(fù)原技術(shù)在應(yīng)用層面起著極為重要的作用，不管是司法物證、歷史文獻(xiàn)修復(fù)或者是軍事情報(bào)獲取等都扮演著重要角色。在以往，復(fù)原工作往往由人工來完成，雖然說人工復(fù)原文件準(zhǔn)確率較高，但效率很低。尤其在文件被嚴(yán)重破碎分割的情況下，短時間內(nèi)想通過人工來復(fù)原，更是難上加難。伴隨現(xiàn)代技術(shù)發(fā)展，本文試論述切割后碎片的復(fù)原方法。

二、實(shí)現(xiàn)過程

（一）預(yù)處理

通過觀察被切割的雙面英文碎紙片圖片可知，碎紙片之間的切割長度一致，并且碎片正反面的英文字母是在相同的位置上。因此可利用此現(xiàn)象進(jìn)行聚類分析，將處在同一行的英文碎片的正反面劃分到一類，從而簡化對比的復(fù)雜度。

（二）碎片的聚類以及鏡像處理

1.碎片的聚類分析模型

首先對雙面英文碎片進(jìn)行劃分，由于英文字符是完全按照四線三格印刷的，所以首先定義a為英文四線三格中間一格的寬度，由于a為常量，故通過MATLAB可以求出a的確定值;其次通過MATLAB將碎片全部導(dǎo)入，求出碎片的灰度圖像的水平投影，根據(jù)投影圖像的特征，可以觀察出英文的四線三格的每一條線都會對應(yīng)一個圖像峰值，取較明顯的峰值與峰值之間的間距;然后令Wi為峰值間距極度接近a的條形塊的位置，此位置便為四線三格的中間一格位置。最后通過k均值聚類算法依據(jù)Wi來劃分碎片。k均值聚類算法是一種多次選擇迭代的分類算法，所以能夠最大程度的完成劃分。

2.聚類的人工干預(yù)

理想的劃分結(jié)果是將416個碎片劃分聚類劃分為11組，但是MATLAB實(shí)際操作起來并達(dá)不到這么高的準(zhǔn)確度，所以此處需要加入人工干預(yù)。根據(jù)MATLAB的實(shí)際分組來找出不應(yīng)該出現(xiàn)的組別和不應(yīng)該出現(xiàn)在某一組的其他碎片，通過肉眼的觀察來盡可能的分成11個組，每一組19個碎片。

3.碎片的鏡像化處理模型

由聚類劃分得到的碎片雖都是同一行的，但是其中包括正反a，b兩面的碎片，所以組內(nèi)拼接時仍需要匹配很多次，這樣會大大降低碎片的復(fù)原準(zhǔn)確率。據(jù)此，提出鏡像化處理優(yōu)化模型，根據(jù)觀察以及空間立體特征可得出，從碎片的正面看到的反面，其實(shí)是反面的鏡像，故據(jù)此將一張碎片的反面鏡像提取到正面上。

對于一張雙面英文碎片，現(xiàn)無法確定正反面，故需討論兩種情況，一種是000a為正面，那么把000b作為反面，將其鏡像附在000a下方;另一種是000b為正面，那么把000a作為反面，將其鏡像附在000b下方，即可得到兩種新的碎片。

（三）TSP復(fù)原優(yōu)化算法

由初步的復(fù)原效果，可以發(fā)現(xiàn)縱向拼接時會因?yàn)檫吘墰]有字母的切割點(diǎn)而造成拼接困難，基于此，提出TSP復(fù)原優(yōu)化模型。此模型的原型是旅行商問題，在某種限定下，求得optimization解，使得總路徑最短。本題利用此算法來優(yōu)化0-1灰度值匹配復(fù)原模型，使得那些邊緣沒有切割點(diǎn)的片段找到最佳匹配，具體算法如下：

（四）碎片復(fù)原過程

1.按聚類橫向復(fù)原

把經(jīng)過處理的碎片，通過MATLAB重新讀入，可以得出新碎片的邊緣灰度矩陣，然后將其根據(jù)灰度值的閾值來0-1化，最終得到灰度0-1矩陣。仍先根據(jù)碎片最左側(cè)的灰度分布值的特點(diǎn)，利用算法找出最左側(cè)的碎片，根據(jù)匹配度依次尋找能與前一碎片的右側(cè)邊緣匹配度最高的碎片進(jìn)行逐個拼接。

在拼接時，我們是抽象出了一個量——匹配度，來衡量碎片是否相鄰，由于此題中已經(jīng)通過鏡像法，在對圖片進(jìn)行匹配拼接時，同時考慮了正反兩面的匹配度，不僅增大了檢測的邊緣長度，還一次性檢驗(yàn)了兩個面。大大的降低了失誤率，所以當(dāng)匹配度低于90%的時候檢驗(yàn)就可以。其余地方的匹配則無需干預(yù)。

2.碎紙條的縱向復(fù)原

經(jīng)過橫向拼接好的碎紙條已經(jīng)可以看得出正反面，我們只取正面的初步復(fù)原的圖來進(jìn)行縱向拼接，利用0-1化的灰度矩陣先把邊緣有切割到字母的圖拼接在一起，得到e個新的片段，這e個片段的上下邊緣至少有一個邊緣是空白的，然后根據(jù)提出的TSP復(fù)原優(yōu)化模型來尋求e個片段的最優(yōu)化匹配方式。

3.人工干預(yù)及復(fù)查

可再進(jìn)行一步人工干預(yù)，看每個字母是否完整，最后閱讀全文看是否是一篇完整的文章。

【參考文獻(xiàn)】

[1]蔡志杰.碎紙片拼接復(fù)原的數(shù)學(xué)模型與方法[J].高等數(shù)學(xué)研究，2016（04）.

[2]陶佳琪，鄭路通，楊雯雯，買阿麗，孫國偉.單頁單面英文縱切橫切碎片拼接復(fù)原算法[J].運(yùn)城學(xué)院學(xué)報(bào).2013（5）.

[3]碎紙片的拼接復(fù)原.

https：//blog.csdn.net/z1143709608/article/details/60139479.2017

[4]羅智中.基于文字特征的文檔碎紙片半自動化拼接[J].計(jì)算機(jī)工程與應(yīng)用，2012（5）.

[5]沈恒范.詳解MATLAB數(shù)字圖像處理[M].電子工業(yè)出版社，2010.

[6]張?zhí)?Stata統(tǒng)計(jì)分析語行業(yè)應(yīng)用案例詳解[M].清華大學(xué)出版社，2014.

[7]汪曉銀.周保平.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M].北京：科學(xué)出版社，2012.

作者簡介：趙靜文（1999—），女，山東棗莊人，漢族，本科，單位：青島理工大學(xué)，研究方向：數(shù)學(xué)與應(yīng)用數(shù)學(xué)。