碎紙片的拼接復(fù)原數(shù)學(xué)建模

楊蒙

問題一中，本文用傅里葉變換來分析碎片圖像之間的相關(guān)性，首先選取某圖像作為模板圖像，并在其一側(cè)上選取字母圖像作為臨時(shí)圖像，將臨時(shí)圖像與所有碎片圖像進(jìn)行傅里葉變換，并得到極限相關(guān)圖;然后通過極限相關(guān)圖得到其間的相關(guān)程度，將相關(guān)程度最接近的圖像作為模板圖像對(duì)應(yīng)邊緣的拼接圖像;如果存在多個(gè)圖像與模板圖像相關(guān)程度接近，則重新選擇模板圖像邊緣的字母，直到發(fā)現(xiàn)唯一的拼接圖像。

問題二中，首先采用基于拉普拉斯算子的Canny法提取出各個(gè)碎片文件的邊緣特征，然后通過檢測(cè)隨機(jī)二個(gè)碎片文件接縫處像素的灰度值是否是連續(xù)變化來確定這二個(gè)碎片文件是否可以拼接在一起。將碎片文件拼接的問題轉(zhuǎn)換為檢測(cè)碎片文件接縫處灰度值的連續(xù)性，當(dāng)所像素間距足夠小時(shí)，文字的曲線近似看做直線;最后將問題變成檢驗(yàn)接縫處像素點(diǎn)灰度值是否在同一條直線上，并用Hough變換實(shí)現(xiàn)該過程。

問題三中，在對(duì)雙面碎片文件進(jìn)行拼接時(shí)，首先選取二張碎片文件圖像作為原圖像和目標(biāo)圖像，分別用SIFT來描述這二個(gè)圖像，提取他們的特征點(diǎn)，將二者的特征點(diǎn)進(jìn)行匹配，同時(shí)完成匹配點(diǎn)的矯正，最后通過圖像的匹配點(diǎn)完成圖像的融合，實(shí)現(xiàn)圖像拼接。

一、問題重述

破碎文件的拼接在司法物證復(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)。

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á)要求同上。

二、問題分析

問題一中，在對(duì)英文碎片文件進(jìn)行拼接時(shí)，本文用傅里葉變換來分析碎片圖像之間的相干性，具體操作為選取某個(gè)碎片文件作為模板圖像，選取該圖像一側(cè)上的字母圖像作為臨時(shí)圖像，將該字母圖像與所有字母圖像進(jìn)行傅里葉變換，并得到極限相關(guān)圖，通過極限相關(guān)圖可以得到所有圖像與臨時(shí)圖像的相關(guān)程度，將相關(guān)程度與模板圖像相關(guān)程度最接近的圖像作為模板圖像對(duì)應(yīng)邊緣的拼接圖像;如果存在多個(gè)圖像與模板圖像相關(guān)程度接近，則重新選擇模板圖像邊緣的字母，直到發(fā)現(xiàn)唯一的拼接圖像為止。同理在對(duì)中文碎片文件進(jìn)行拼接時(shí)采用相同的方法，由于漢字偏旁部首較多，因此在拼接時(shí)有別于英文碎片文件拼接的是在選取臨時(shí)圖像時(shí)，需要盡量選取能夠根據(jù)偏旁部首可以推斷出來的漢字作為臨時(shí)圖像，而且該漢字所在的碎片中應(yīng)該最好只顯示一半，這樣在進(jìn)行傅里葉變換的圖像匹配時(shí)，該漢字能夠均衡的分在二個(gè)碎片文件中，進(jìn)而能夠較容易地找出可以拼接的二個(gè)碎片文件。

問題二中，首先提取出各個(gè)碎片文件的邊緣特征，即邊緣處的漢字形狀，如果二個(gè)碎片文件是可以拼接在一起的，那么它們邊緣特征圖像的接縫處的灰度值應(yīng)該是連續(xù)變化的，由此，可以通過檢測(cè)二個(gè)碎片文件接縫處像素的灰度值是否是連續(xù)變化來確定這二個(gè)碎片文件是否可以拼接在一起。因此，碎片文件拼接的問題就變?yōu)槿绾螜z測(cè)二個(gè)碎片文件接縫處灰度值是否連續(xù)的問題，無論是漢字還是字母，都可以看做是曲線，當(dāng)所分析的距離足夠小時(shí)，可以將曲線近似看做直線，這樣問題就變成了檢驗(yàn)接縫處像素點(diǎn)灰度值是否在同一條直線上。該過程可以用Hough變換實(shí)現(xiàn)。

問題三中，利用SIFT提取碎片文件局部特征，建立尺度空間，尋找候選點(diǎn)、精確確定關(guān)鍵點(diǎn)，剔除不穩(wěn)定點(diǎn)、確定關(guān)鍵點(diǎn)的方向、提取特征描述符，在對(duì)雙面碎片文件進(jìn)行拼接時(shí)，首先選取一張碎片文件圖像作為原圖像，選取另一張碎片文件圖像作為目標(biāo)圖像，然和分別用SIFT來描述這二個(gè)圖像，提取他們的特征點(diǎn)，接著將二者的特征點(diǎn)進(jìn)行匹配，同時(shí)完成匹配點(diǎn)的矯正，最后通過圖像的匹配點(diǎn)完成圖像的融合，即圖像的拼接。

三、模型優(yōu)缺點(diǎn)分析

在模型一中，將碎片文件圖像進(jìn)行傅里葉圖像變換，經(jīng)過變換后的圖像更為方便、容易地處理和操作。通過傅里葉卷積圖像、極限相關(guān)圖像可以得到臨時(shí)圖像與碎片文件的相關(guān)程度，選取相關(guān)程度最接近的二個(gè)碎片文件進(jìn)行拼接。模型存在的不足是有時(shí)會(huì)存在多張碎片文件圖像的相關(guān)程度均接近，此時(shí)需要重新選取臨時(shí)圖像，重新進(jìn)行操作。因此增加了程序的復(fù)雜度。

在模型二中，利用Canny方法對(duì)圖片進(jìn)行基于拉普拉斯算子的邊緣特征分析，旨在找出各個(gè)碎片文件圖像邊緣部分的文字形狀，然后利用Hough變換檢驗(yàn)二個(gè)碎片文件接縫處像素點(diǎn)的灰度值是否連續(xù)來判斷這二個(gè)圖片是否可以拼接，在此過程中將短距離內(nèi)文字圖像的曲線近似為直線，這樣講拼接問題轉(zhuǎn)化為尋找二個(gè)碎片文件接縫處像素點(diǎn)灰度值是否在通一條直線上，模型在不失正確解決問題的情況下，更加容易理解。模型存在的缺點(diǎn)即是需要將所有碎片文件進(jìn)行拼接搜索，這使得程序的執(zhí)行效率有所降低。

在模型三中，首先選取一張碎片文件圖像作為原圖像，選取另一張碎片文件圖像作為目標(biāo)圖像，然和分別用SIFT來描述這二個(gè)圖像，提取他們的特征點(diǎn)，接著將二者的特征點(diǎn)進(jìn)行匹配，同時(shí)完成匹配點(diǎn)的矯正，最后通過圖像的匹配點(diǎn)完成圖像的融合，即圖像的拼接。模型存在的缺點(diǎn)是在進(jìn)行匹配時(shí)采用窮舉匹配法，需要將所有碎片文件與原圖像進(jìn)行匹配，在算法上削弱了程序的執(zhí)行效率。

參考文獻(xiàn)：

[1] 羅智中，基于線段掃描的碎紙片邊界檢測(cè)算法研究，儀器儀表學(xué)報(bào)，第32卷 第2期，2011年2月

[2] 趙書蘭，《MATLAB數(shù)字圖像處理與分析實(shí)例教程》，化學(xué)工業(yè)出版社，2009年6月