碎紙片的拼接復原

濟南大學數學科學學院 段玉潔 郭 蓉

碎紙片的拼接復原

濟南大學數學科學學院 段玉潔 郭 蓉

碎片拼接；圖片匹配；灰度值矩陣

一、問題背景

破碎文件的拼接，復原和修復在多個領域都有重大的作用，以前都由人工拼接，準確率雖高，但卻耗時耗力，當碎片量巨大時，人工操作可能難以按時完成，但運用計算機開發自動拼接技術，可很大程度的提高拼接復原效率。

對于同一頁僅縱切的破碎紙片，建立拼接復原模型和算法，并運用建立的模型和算法將碎片進行拼接復原，如果在進行拼接的過程中需要人工干預，要求寫出是怎樣干預的以及進行干預的時間點，并要把復原的碎片以圖片及表格形式表達出來。

二、問題分析

對于文件碎片僅縱切的情況，根據圖片成像的的原理，圖片是由m*n個像素點組成的，因此可以用MATLAB對每張碎片建立它的灰度矩陣。其中文件的最左側碎片一定是可以找出的（因為最左側的文件碎片的第一列字一定是完整的），根據灰度矩陣的原理，它的最左側碎片所城的灰度矩陣一定是全部為255的一列數。找出第一張之后，我們可以利用相關系數的方法，求出剩下的碎片的最右側的列和找出的文件碎片的第一張的最左側的列的相關系數，其中相關系數最大的則可認為兩張圖片可以進行拼接。用此方法，依次往下循環執行，則可將所有的碎片順序輸出。

三、模型建立與求解

利用MATLAB建立每張圖片的灰度矩陣，如圖一所示為其中一張碎片的灰度矩陣[1]的部分數據：

圖一 灰度矩陣的部分數據

其中圖中灰度矩陣的值為介于0-255之間的數，表示亮度從深到淺，圖像中的顏色從黑到白，即0為純黑，255為純白，0到255之間的數字為其中間值，介于純黑和純白之間的灰度色。[1]

其中ρ為由矩陣A和矩陣B中任意兩列的相關系數，maxρ為當固定其中的ai時，求使ρ最大的bj，則bj所在的碎片就是ai所在的碎片的下一張，即兩張碎片可以進行拼接。

首先根據建立的模型可以找出和b0（b0所在的碎片就是破碎文件的最左側的碎片上述以說明，這里不在敘述）所在的碎片進行拼接的下一張，依次往下重復循環，便可輸出破碎文件的正確順序。結果如下表一、表二。

表一 附件一的碎片復原順序

表二 附件二的碎片復原順序

表一，表二中的各個數字就是原碎片的標號，表一和表二給出的就是運用模型求解后給出的文件拼接復原后對應的碎片的順序。

根據上述順序將文件進行拼接復原即可得到復原后的文件圖片。

四、模型檢驗

根據第一問所編寫的程序，我們用MATLAB軟件輸出附件一和附件二的破碎文件復原后的碎片順序。如下圖二和圖三所示：

圖二 附件一的碎片輸出順序

圖三 附件二的碎片輸出順序

其中圖二和圖三中的數字在圖中的排列順序即代表碎片在文件中的位置。由圖片可驗證上述碎片的輸出順序是正確的，驗證了模型的正確性。

[1]卓金武,李必文,魏永生,秦健.MATLAB在數學建模中的應用(第二版)[M].北京航空航天大學出版社.

[2]百度文庫.相關系數.http://wenku.baidu.com/view/9e5ad1956 bec0975f465e21c.html.

段玉潔，女，現就讀于濟南大學數學科學學院，研究方向：金融數學。

郭蓉【通訊作者】，女，現就讀于濟南大學數學科學學院，研究方向：金融數學。