2013數(shù)學(xué)建模論文

21關(guān)于碎紙片拼接復(fù)原技術(shù)模型的探究摘要圖像拼接技術(shù)是計算機視覺領(lǐng)域的一個重要分支。它是一種將多幅相關(guān)的重疊圖像進行無縫拼接從而獲得寬視角全景圖像的技術(shù)。本文針對關(guān)于碎紙片拼接復(fù)原問題，建立了基于邊緣的相位相關(guān)圖像匹配算法模型以及Hausdorff距離算法模型，在一定程度上對碎紙片進行了拼接復(fù)原工作。解決了傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低的問題。針對問題一，運用基于邊緣的相位相關(guān)圖像最優(yōu)匹配模型算法，利用matlab軟件中的imread函數(shù)讀取被切邊緣像素索引值，根據(jù)圖片像素灰度值，通過Hausdorff距離算法進行圖像配準(zhǔn)，涉及相關(guān)算法，解決問題一中規(guī)則的碎紙片拼接問題。針對問題二，所給碎紙片相對于在問題一基礎(chǔ)上又進行橫切處理先運用問題一的數(shù)學(xué)建模思想，把碎紙片左右兩端首先進行拼接復(fù)原，完成之后再進行上下邊緣的拼接復(fù)原工作，所需原理與問題一相同。然后人工干預(yù)，把未能拼接的碎紙片用人工拼接復(fù)原。針對問題三，所給的碎紙片為A,B正反對應(yīng)，首先對B進行旋轉(zhuǎn)處理，旋轉(zhuǎn)之后將B的上沿與相應(yīng)的A的下沿進行黏合，形成新的圖像。之后讀取新圖像的邊緣像素索引值，按照上述問題二的方法進行拼接。關(guān)鍵字：規(guī)則圖像拼接基于邊緣相位相關(guān)Hausdorff距離灰度值一、問題的重述圖像拼接技術(shù)是計算機視覺領(lǐng)域的一個重要分支，它是一種將多幅相關(guān)的重疊圖像進行無縫拼接從而獲得寬視角全景圖像的技術(shù)。在現(xiàn)在社會中破碎文件的拼接在司法物證復(fù)原、歷史文獻修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。本文嘗試解決以下問題：（1）對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請寫出干預(yù)方式及干預(yù)的時間節(jié)點。復(fù)原結(jié)果以圖片形式及表格形式表達。（2）對于碎紙機既縱切又橫切的情形，請設(shè)計碎紙片拼接復(fù)原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請寫出干預(yù)方式及干預(yù)的時間節(jié)點。（3）上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復(fù)原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。請嘗試設(shè)計相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果。二、模型假設(shè)（1）模型中假設(shè)本題中每個附件的文字部分完整，字跡清晰，沒有陰影重疊或斷片情況。（2）假設(shè)每個附件的紙張圖片無破損。（3）圖片位置沒有上下顛倒（即文字是正向）（4）如果紙張在油墨覆蓋的部位切斷，附著在紙上的油墨也會被扯開，模型假設(shè)在斷裂處排除油墨丟失的情況。（5）模型中假設(shè)不考慮碎紙片被切邊緣的噪聲因素。三、符號說明M：表示每個碎片四周的灰度值特征；H：表示圖像左側(cè)的灰度值向量；D：表示右側(cè)灰度值向量；T：表示上側(cè)灰度值向量；B：表示下側(cè)灰度值向量；S：表示灰度值向量差的絕對值。模型建立以及求解4.1問題一的模型建立和求解對于問題一給出的碎紙機破碎文件（縱切）的拼接復(fù)原問題，目前應(yīng)用最廣泛的是圖像拼接技術(shù)，圖像的拼接只要處理相鄰兩幅圖像樣本之間的重疊部分，圖像拼接技術(shù)有多種方法，其中最為常用的是基于圖像特征的方法，考慮到問題一中碎紙片是由碎紙機破碎的規(guī)則文本，被切邊緣無論是從文本字體特征上還是紙張?zhí)卣魃蟻碚f應(yīng)該在某些方面具有一定的相似性。為此我們采用基于邊緣特征灰度值分析的方法。4.1.1基于邊緣的相位相關(guān)圖像匹配算法：邊緣相位相關(guān)圖像匹配算法在本文中指：分別提取19個碎紙片中保持不變的特征M，它的特征是由這個圖片上下左右四個邊緣的灰度值來決定的，則M可表示為:M={Hx,Dx,Tm,Bx}(n為第n個碎片)其中H表示碎片左側(cè)灰度值向量；D表示右側(cè)灰度值向量；T表示上側(cè)邊緣灰度值向量；B表示下側(cè)灰度值向量。然后用這些特征點集進行匹配對應(yīng)，生成一組對應(yīng)特征點集，我們通過距離識別中的一個基本概念，具有幾何度量的絕對性和相似度量的相對性。本文中是通過計算圖像的灰度值距離來反映碎紙片的匹配程度。我們通過計算像素數(shù)組之間的距離差的絕對值，絕對值越小，兩個碎紙片的匹配度就越高?，F(xiàn)定義兩個特征點集之間的Hausdorff距離，為H（A,B）=min[(h(A,B)，h(B,A)]；h(A,B)=max（a∈A）min（b∈B）‖a-b‖；有向部分Hausdorff距離hK(A,B)由A中與B的距離第K遠的那個點決定：hK（A,B）=Kthmax（a∈A）min（b∈B）‖a-b‖。圖像的傳統(tǒng)歐式距離：兩幅圖像想，x,y間距離為：d(x,y)=,m*n被看作圖像一個點，每個坐標(biāo)值對應(yīng)一個像素的灰度值4.1.2邊緣特殊點的相位尋找算法：由于我們實際要拼接復(fù)原的碎紙是由一個個像素點組成的，并且這里是邊緣規(guī)則拼接，故僅需考慮碎紙左右邊緣的像素點，那么我們需要根據(jù)像素明暗程度的變化，提取出每個碎片邊緣的信息。圖像預(yù)處理由于本題的特殊性，被切邊緣是規(guī)則的，所以我們只需對碎片邊緣像素值進行匹配處理，（由于整個圖像像素的明暗程度差別很大，不考慮邊界噪聲因素。）首先讀取19個縱切碎片的左側(cè)邊緣灰度值，生成的矩陣M=｛H1,H2,…,H19｝，再讀取19個縱切碎片的右側(cè)邊緣灰度值，生成的矩陣N=｛D1,D2,…,D19｝，因此我們可以得到每個碎片左右兩列邊緣像素值，即從H1到H19這19組左側(cè)像素數(shù)組和D1到D19右側(cè)像素數(shù)組。將得到的邊緣像素值矩陣化,把所有碎紙片左側(cè)像素值H1到H19放入同一矩陣H中，得到如下矩陣：H1...H19H=h把所有碎紙片右側(cè)像素值D1到D19放入同一矩陣D中，得到如下矩陣：D1…D19D=（2）圖像配準(zhǔn)圖像配準(zhǔn)是一種確定待拼接圖像間的重疊區(qū)域以及重疊位置的技術(shù)，是整個圖像拼接的核心。圖像配準(zhǔn)本文采用的是基于邊緣特征的圖像配準(zhǔn)方法，即通過像素點對構(gòu)建圖像序列之間的變換矩陣，從而完成全景圖像的拼接。為了提高碎片配準(zhǔn)的精度，本文采用Hausdorff距離的算法對碎片的變換矩陣進行求解與精煉，此算法是描述兩組點集之間相似程度的一種度量。記H1點到D點集中距離的最小距離SD(H1)，即SD(H1)=min‖Hi-Di‖，假設(shè)一個圖片最左邊的像素向量為H1，待匹配的一組圖像最右邊的像素向量組（從D1到D19）為D，可以用SD(H1)，來度量H1和D的匹配程度。例如S(1,1)=(H1-D1)S(1,2)=(H1-D2)…S(1,19)=(H1-D19)得出第一列數(shù)據(jù)，然后將H中的其他數(shù)組作如上運算，得出其他各組數(shù)據(jù)如下：H1H2H3H4H5H6H7H8H9D11138931309451161031414481009421119552566110609785949D21234231324191265891256523361610002711242311989593527D3127946114084119516105035104745969281224149025682744D41062531276299594512956411333010691111130510320383887D5110732116398100076115677999832230011879210500657564D6120399113365105551124588114916995831226938746581403D78441010634674468114079867094938097898628100D81116071132051091371369761023621113091076059417184629D997181110965116889124112107114786011118839898359823D1011148411862010928812147111806910447212446410150090152D11131031119975221371235861293041063391200879587385307D12100548108018101008123909109337915301136902182862728D13852421192709907411871197789768001066248050635370D1498457115469109007122480117370903871034099571565199D1597912119254758101289518763980236981248316041196D1612306812793411987824331125039110982143326122008110000D1712919029574131162128869131923108750143744111690113372D182699312589111888513491812656610601313060910081589733D191038141212301036701240971227819070811582610456275636H10H11H12H13H14H15H16H17H18H191111189980511830790941122140105724987431200281060589157811160410472112411596125121618105686102069105624119906135541016731048341021461028981080831158638542214639111999153871128103138311206782415114328100510103449114430104020117821040879978082790942161154977537180758103853123565896392465011049311532994013108758105452906751007201139101049280369797626102450346846475530932592813619022966655112936107423116475911951093321093149326510448833594109021113941015939290198493119446275448412511246811162686740115477124432925581049202613112329195686111057115257120771003581046231074359140710819811322610382711780012030211292945671074129498688324103125990977762693299100795944258271598026737348368493927784751222890319928438428310729811013991993106077115402911687474511159811019221352100259745149238618222956978342971984991899562598667126161122828111462119734117695123377114988109707138933127649117107132184121446130916124453113537120944113823131065118371206761180979881310477710207699300908371279921103081093810720511174227268107564105183998477696410529712436798947圖表4.1.1（3）圖像融合圖像融合是圖像拼接的另一個關(guān)鍵技術(shù)。圖像融合是將兩幅已配準(zhǔn)圖像中有用信息綜合到一幅圖像中并以可視化方法顯示的技術(shù)。配準(zhǔn)后的圖像由于分辨率和視角的不同以及光照等因素的影響,有時甚至是多光譜圖像之間進行的拼接,在圖像拼接的重疊部分有時會產(chǎn)生模糊、鬼影或噪聲點,邊界處也可能形成明顯的拼縫。為了改善拼接圖像的視覺效果和客觀質(zhì)量,需要對拼接后的圖像進行融合。人工干預(yù):首先分析S矩陣內(nèi)的數(shù)據(jù)，發(fā)現(xiàn)出現(xiàn)了s中有一個元素為0，此位置是（D7,H9），它所代表的是第七個原始碎片右側(cè)與第九個原始碎片左側(cè)，而從原始碎片可以看出第七個原始碎片為文章最左側(cè)邊緣，第九個原始碎片為文章最右側(cè)邊緣，詳圖如下：圖表4.1.2根據(jù)表格中數(shù)據(jù)，在每一列比較選取最小值,該最小值所對應(yīng)的行和列即為左右邊緣像素值很相似的兩組像素值，則這兩個邊緣可運用圖像融合技術(shù)進行拼接復(fù)原，按照上表數(shù)據(jù)可得出碎紙片標(biāo)號的拼接復(fù)原順序：附件一的結(jié)果：附件一碎紙片從左到右19列正確排列順序如下圖所示:008014012015013010002016001004005009013018011015017000006圖表4.1.3附件二的結(jié)果：附件二碎紙片從左到右19列正確排列順序如下圖所示：003006002007015018011000005001009013010008012014017016004圖表4.1.4運用Matlab軟件中imshow方法，通過編寫及運行程序能夠生成全景碎紙片還原圖，其中程序代碼如附錄所示。生成的碎紙片還原全景圖如下圖所示:圖表4.1.5針對問題一給出的英文縱切碎紙片，其原理與中文碎紙片相同，生成的碎紙片還原全景圖見附錄2所示：圖表4.1.64.2對模型一的分析及改進模型二針對問題二所提出的對于既橫切又縱切的碎紙片進行拼接復(fù)原，實際上是對于問題一的深化，因此我們的整體思路依然是運用基于邊緣的相位相關(guān)圖像匹配算法和Hausdorff距離算法模型來進行。由于計算機數(shù)字分析能力具有一定的缺陷，讓計算機對碎片進行完全意義上的自動化拼接也幾乎不太可能。為保證拼接的準(zhǔn)確性，需要在拼接過程中加入人工干預(yù)過程。所謂的人工干預(yù)過程在本題中即指：因為碎紙片是經(jīng)過碎紙機既橫切又縱切得到的，總共為11*19=209個碎紙片，要想把這209張碎紙片進行拼接復(fù)原，我們可以參照問題一所建立的數(shù)學(xué)模型，運用Hausdorff距離算法模型先對這209個碎紙片進行左右的拼接復(fù)原，得到片段的橫向條，然后再通過橫向條上下邊緣的匹配進行縱向復(fù)原，最終完成碎紙片的拼接復(fù)原，其間可能會出現(xiàn)一些誤差，使部分碎片無法拼接復(fù)原，此時我們要進行人工干預(yù)。模型二的建立及分析具體流程如下所示：4.2.1經(jīng)過碎紙機既縱切又橫切的文件被破碎成11*19個碎紙片，首先對圖片預(yù)處理，運用matlab軟件中的imread函數(shù)讀取所有碎片四周的像素索引值，不同于問題一的是，要對每個圖片讀取四個邊緣的像素值，分別把四個邊緣的數(shù)據(jù)放入同一矩陣中有：左邊緣矩陣H右邊緣矩陣D上邊緣矩陣T下邊緣矩陣B運用模型一的基于邊緣的相位相關(guān)圖像匹配算法模型和Hausdorff算法模型得到如下矩陣：H=D=d1,1首先，我們先要進行碎紙片左右兩側(cè)的拼接復(fù)原，同樣用到Hausdorff算法模型?，F(xiàn)在令模版為H1，待匹配圖像為D，可以用h（H1,D）來度量H1和D的匹配程度。S(1,1)=(H1-D1)S(1,2)=(H1-D2)…S(1,19)=(H1-D19)得出第一列數(shù)據(jù)，然后將H中的其他數(shù)組作如上運算，得到各步數(shù)據(jù)。根據(jù)表格中數(shù)據(jù)，在每一列比較選取最小值,該最小值所對應(yīng)的行和列即為左右邊緣像素值很相似的兩組像素值，則這兩個邊緣可運用圖像融合技術(shù)進行拼接復(fù)原。拼接完成后得到了拼接片段，以下是拼接片段中的兩個：圖表4.2.1這些片段都沒能拼接成完整的文本信息，所以每個拼接片段的一端碎片成為此片段的斷點處，共有32處。此斷點需人工完成，將剩下的未拼接的碎片進行人工拼接。然后，我們再進行碎紙片上下邊緣的拼接復(fù)原?，F(xiàn)在我們定義T,B分別為碎紙片進行左右拼接融合之后形成的橫行上下邊緣的像素索引值矩陣，令模版為T1，待匹配圖像為B，可以用t（T1,B）來度量T1到B的匹配程度。S(1,1)=(T1-B1)S(1,2)=(T1-B2)…S(1,19)=(T1-B19)得出第一行數(shù)據(jù)，然后將T中的其他數(shù)組作如上運算，得到各步數(shù)據(jù)。根據(jù)表格中數(shù)據(jù)，在每一列比較選取最小值,該最小值所對應(yīng)的行和列即為上下邊緣像素值很相似的兩組像素值，則這兩個邊緣可運用圖像融合技術(shù)進行拼接復(fù)原。由于此過程不能使全部碎紙片復(fù)原，按照上述方法即可得到最終附件三的拼接復(fù)原順序表為：049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018X1148X2X3X4X5081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115176094034X6183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108X7004101113194119123圖表4.2.2上表中標(biāo)注的紅色數(shù)據(jù)為未能拼接完整，需由人工進行拼接還原剩余的7個碎紙片,經(jīng)人工拼接完成后可以得到完整的碎紙片還原圖像：圖表4.2.3對于英文的附件4來說，由最終形成的斷點數(shù)據(jù)來說，最終是有29個斷點，這些斷點需有人工拼接完成，最終拼接完整的還原圖見附錄。4.3模型三的建立及求解在模型三中，給出的是一頁英文印刷文字雙面打印文件的碎片，一個切割邊緣的灰度值則有A,B兩面的兩組，將000B選轉(zhuǎn)之后，得到000B’，則它之前的最左側(cè)數(shù)組變?yōu)樽钣覀?cè)數(shù)組，那么000A與000B’按如圖連接，得到一個新的用圖象00AB，則00AB最右側(cè)的數(shù)組即為000說明如下：旋轉(zhuǎn)旋轉(zhuǎn) 000A000B000B’000A000A000B圖表4.3.1將附件5中的處于正反兩面的（a,b）都進行上述處理，同樣每組正反兩面的兩個碎片可得到一個新的圖像，每個新圖像最右側(cè)的灰度值即為向量K。然后讀取每個新圖像的矩陣，之后結(jié)合問題一和問題二的模型進行處理如下：用矩陣H儲存每個新圖像矩陣左邊緣數(shù)列（即第一列）用矩陣D儲存每個新圖像矩陣右邊緣數(shù)列（即最后一列）然后運用Hausdorff距離的算法對碎片的變換矩陣進行求解與精煉/r