碎紙片的拼接復(fù)原

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

摘 要：破碎文件拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用，本文將碎紙片拼接轉(zhuǎn)化為基于邊緣字跡斷線識(shí)別法的圖像拼接。圖像拼接可以應(yīng)用到計(jì)算機(jī)視覺、模式識(shí)別、生物醫(yī)學(xué)等各個(gè)領(lǐng)域，故研究碎紙片拼接及其相關(guān)技術(shù)有著重要的意義。

針對(duì)問題，根據(jù)灰度圖像的形成原理，列出提取每張圖像兩邊緣的灰度矩陣G，對(duì)此矩陣每?jī)闪兄g做Pearson相關(guān)系數(shù)分析，取每列相關(guān)系數(shù)的最大值即向量范數(shù)，反求出圖像編號(hào)，由此建立按列拼接模型。中文拼接順序表及其拼接圖見表3、 圖2，英文拼接順序表及其拼接圖見表4、圖3，人工干預(yù)節(jié)點(diǎn)數(shù)為0。

關(guān)鍵詞：灰度矩陣；Pearson相關(guān)系數(shù)；Best-First搜索算法；Q系數(shù)評(píng)價(jià)法

1 問題重述

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。請(qǐng)討論以下問題：

1. 對(duì)于給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對(duì)附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請(qǐng)寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果以圖片形式及表格形式表達(dá)。

2. 對(duì)于碎紙機(jī)既縱切又橫切的情形，請(qǐng)?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對(duì)附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請(qǐng)寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果表達(dá)要求同上。

3. 上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實(shí)情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復(fù)原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。請(qǐng)嘗試設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果，結(jié)果表達(dá)要求同上。

2 問題分析

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

2.1 問題

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

用SPSS軟件對(duì)該矩陣做Pearson相關(guān)系數(shù)分析，得到一個(gè)相關(guān)系數(shù)矩陣，該矩陣中的元素為每?jī)闪谢叶戎档南嚓P(guān)系數(shù)，找出每一列的相關(guān)系數(shù)的最大值即向量范數(shù)，根據(jù)奇偶性與左右邊緣的關(guān)系反求出碎紙片的序號(hào)，用Matlab將關(guān)聯(lián)系數(shù)最大的兩個(gè)碎紙片拼接在一起。

3 模型假設(shè)

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

2. 假設(shè)灰度矩陣每列數(shù)據(jù)均服從正態(tài)分布。

3. 假設(shè)圖像邊緣規(guī)則，連接十分契合。

4. 假設(shè)人工干預(yù)節(jié)點(diǎn)連接時(shí)誤差為0。

4 模型建立與求解

4.1 問題

1. 對(duì)于給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對(duì)附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請(qǐng)寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果以圖片形式及表格形式表達(dá)。

4.1.1 按列拼接模型準(zhǔn)備

1.灰度[1]

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

2.向量的無窮范數(shù)[2]

參考文獻(xiàn)

[1] 司周奎，孫璽菁，數(shù)學(xué)建模算法與應(yīng)用，北京：國防工業(yè)出版社，2011，13（1）：319-320

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

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

[4] 賈海燕，碎紙自動(dòng)拼接關(guān)鍵技術(shù)研究，國防科技大學(xué)研究生論文，2005，4（5）：40-41