濟(jì)南大學(xué)數(shù)學(xué)科學(xué)學(xué)院 段玉潔 郭 蓉

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

濟(jì)南大學(xué)數(shù)學(xué)科學(xué)學(xué)院 段玉潔 郭 蓉

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

一、問(wèn)題背景

破碎文件的拼接，復(fù)原和修復(fù)在多個(gè)領(lǐng)域都有重大的作用，以前都由人工拼接，準(zhǔn)確率雖高，但卻耗時(shí)耗力，當(dāng)碎片量巨大時(shí)，人工操作可能難以按時(shí)完成，但運(yùn)用計(jì)算機(jī)開(kāi)發(fā)自動(dòng)拼接技術(shù)，可很大程度的提高拼接復(fù)原效率。

對(duì)于同一頁(yè)僅縱切的破碎紙片，建立拼接復(fù)原模型和算法，并運(yùn)用建立的模型和算法將碎片進(jìn)行拼接復(fù)原，如果在進(jìn)行拼接的過(guò)程中需要人工干預(yù)，要求寫(xiě)出是怎樣干預(yù)的以及進(jìn)行干預(yù)的時(shí)間點(diǎn)，并要把復(fù)原的碎片以圖片及表格形式表達(dá)出來(lái)。

二、問(wèn)題分析

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

三、模型建立與求解

利用MATLAB建立每張圖片的灰度矩陣，如圖一所示為其中一張碎片的灰度矩陣[1]的部分?jǐn)?shù)據(jù)：

圖一 灰度矩陣的部分?jǐn)?shù)據(jù)

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

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

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

表一 附件一的碎片復(fù)原順序

表二 附件二的碎片復(fù)原順序

表一，表二中的各個(gè)數(shù)字就是原碎片的標(biāo)號(hào)，表一和表二給出的就是運(yùn)用模型求解后給出的文件拼接復(fù)原后對(duì)應(yīng)的碎片的順序。

根據(jù)上述順序?qū)⑽募M(jìn)行拼接復(fù)原即可得到復(fù)原后的文件圖片。

四、模型檢驗(yàn)

根據(jù)第一問(wèn)所編寫(xiě)的程序，我們用MATLAB軟件輸出附件一和附件二的破碎文件復(fù)原后的碎片順序。如下圖二和圖三所示：

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

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

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

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

[2]百度文庫(kù).相關(guān)系數(shù).http://wenku.baidu.com/view/9e5ad1956 bec0975f465e21c.html.

段玉潔，女，現(xiàn)就讀于濟(jì)南大學(xué)數(shù)學(xué)科學(xué)學(xué)院，研究方向：金融數(shù)學(xué)。

郭蓉【通訊作者】，女，現(xiàn)就讀于濟(jì)南大學(xué)數(shù)學(xué)科學(xué)學(xué)院，研究方向：金融數(shù)學(xué)。