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

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

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

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

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

二、實現過程

（一）預處理

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

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

1.碎片的聚類分析模型

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

2.聚類的人工干預

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

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

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

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

（三）TSP復原優化算法

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

（四）碎片復原過程

1.按聚類橫向復原

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

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

2.碎紙條的縱向復原

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

3.人工干預及復查

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

【參考文獻】

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

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

[3]碎紙片的拼接復原.

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

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

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

[6]張甜.Stata統計分析語行業應用案例詳解[M].清華大學出版社，2014.

[7]汪曉銀.周保平.數學建模與數學實驗[M].北京：科學出版社，2012.

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