碎紙片的拼接復原

于龍洋　馮宇辰　張帆　張曉彤　鄭智聰

摘 要：破碎文件拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用，本文將碎紙片拼接轉化為基于邊緣字跡斷線識別法的圖像拼接。圖像拼接可以應用到計算機視覺、模式識別、生物醫學等各個領域，故研究碎紙片拼接及其相關技術有著重要的意義。

針對問題，根據灰度圖像的形成原理，列出提取每張圖像兩邊緣的灰度矩陣G，對此矩陣每兩列之間做Pearson相關系數分析，取每列相關系數的最大值即向量范數，反求出圖像編號，由此建立按列拼接模型。中文拼接順序表及其拼接圖見表3、 圖2，英文拼接順序表及其拼接圖見表4、圖3，人工干預節點數為0。

關鍵詞：灰度矩陣；Pearson相關系數；Best-First搜索算法；Q系數評價法

1 問題重述

破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用。傳統上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數量巨大，人工拼接很難在短時間內完成任務。隨著計算機技術的發展，人們試圖開發碎紙片的自動拼接技術，以提高拼接復原效率。請討論以下問題：

1. 對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數據進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節點。復原結果以圖片形式及表格形式表達。

2. 對于碎紙機既縱切又橫切的情形，請設計碎紙片拼接復原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數據進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節點。復原結果表達要求同上。

3. 上述所給碎片數據均為單面打印文件，從現實情形出發，還可能有雙面打印文件的碎紙片拼接復原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數據。請嘗試設計相應的碎紙片拼接復原模型與算法，并就附件5的碎片數據給出拼接復原結果，結果表達要求同上。

2 問題分析

通常碎紙片復原方法一般分為兩種，第一種方法是利用碎紙片的破碎邊緣的曲線進行匹配，第二種方法則是利用邊緣字跡斷線識別的方法進行匹配。附件所給的碎紙片的邊緣均為規則的直線，故采用第二種方法，也就是邊緣字跡斷線識別的方法。

2.1 問題

由于附件文件上的顏色只有黑白兩色，我們考慮利用灰度圖像的形成原理，用Matlab提取出各個碎紙片的灰度矩陣（i=0，1，…18），取每個碎紙條的灰度矩陣的第一列和最后一列，將它們按附件給出的圖像順序合并到同一個矩陣中。

用SPSS軟件對該矩陣做Pearson相關系數分析，得到一個相關系數矩陣，該矩陣中的元素為每兩列灰度值的相關系數，找出每一列的相關系數的最大值即向量范數，根據奇偶性與左右邊緣的關系反求出碎紙片的序號，用Matlab將關聯系數最大的兩個碎紙片拼接在一起。

3 模型假設

1. 假設碎紙片拼接好后的文章是完整通順的。

2. 假設灰度矩陣每列數據均服從正態分布。

3. 假設圖像邊緣規則，連接十分契合。

4. 假設人工干預節點連接時誤差為0。

4 模型建立與求解

4.1 問題

1. 對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數據進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節點。復原結果以圖片形式及表格形式表達。

4.1.1 按列拼接模型準備

1.灰度[1]

指黑白圖像中點的顏色深度，范圍一般從0到225，黑色為0，白色為225，故黑白圖像也稱為灰度圖像，它可以量化為一個二維陣列，陣列的元素則為灰度值。

2.向量的無窮范數[2]

參考文獻

[1] 司周奎，孫璽菁，數學建模算法與應用，北京：國防工業出版社，2011，13（1）：319-320

[2] 邢志棟，曹建榮，矩陣數值分析（第二版），陜西：科學技術出版社，2005，1（1）：2-3

[3] 劉震，吳廣，丁維岱，張召明，SPSS統計分析與應用，北京：電子工業出版社，2010，7（1）：181-182

[4] 賈海燕，碎紙自動拼接關鍵技術研究，國防科技大學研究生論文，2005，4（5）：40-41