2013年全國大學(xué)生數(shù)學(xué)建模競賽國家一等獎?wù)撐?b題碎紙片的拼接復(fù)原的研究

1、碎紙片的拼接復(fù)原摘要本文運(yùn)用左右邊界匹配、圖片特征匹配、上下邊界匹配等方法研究單頁打印縱切紙片、單頁打印橫、縱切紙片以及雙頁打印橫、縱切紙片的拼接與復(fù)原問題。針對問題一，首先對圖像進(jìn)行數(shù)據(jù)處理，讀取圖片的灰度信息，構(gòu)建灰度矩陣，并將灰度矩陣轉(zhuǎn)化為01矩陣，從而將二維圖片數(shù)值化。接著，提取出01矩陣的第一列與最后一列，存儲在圖片的左右邊界矩陣中，通過建立兩張圖片的左右邊界匹配度模型，探究圖片的左右鄰接關(guān)系。計(jì)算結(jié)果為：漢字圖片從左到右依次

2、為：008、014、012、015、003、010、002、016、001、004、005、009、013、018、011、007、017、000、006，英文的排序結(jié)果為：003、006、002、007、015、018、011、000、005、001、009、013、010、008、012、014、017、016、004。問題二，采用二層篩選的方法，第一層做行位置篩選，讀取圖片的前100個(gè)像素行，存入圖片的特征列向量中，并將此列向量作

3、為行特征的唯一標(biāo)識，建立圖片的特征匹配模型，將列向量元素差異最小的圖片聚類，中文確定出15類，英文歸為16類。然后通過人為干預(yù)，實(shí)現(xiàn)類的合并，使每類中的圖片個(gè)數(shù)相同，將中英文都聚成11類，每一類包含19張圖片。構(gòu)建行內(nèi)圖片的左右邊界匹配模型，最終確定出每類內(nèi)部圖片的排序；第二層做列位置篩選，建立每行上下邊界匹配模型，得出在各行的上下位置序列，經(jīng)過兩層篩選，得出原文件圖片序列。最后，視人工干預(yù)后的最終結(jié)果為正確答案，檢驗(yàn)未加入人工干預(yù)計(jì)算

4、機(jī)排序結(jié)果，得到中文的拼接正確率為90.4%，英文的拼接正確率為65.1%。對于問題三，建立兩次特征匹配模型將圖片聚類，即首先任取一碎片的一面依次與其他碎片的兩個(gè)面分別作第一次特征匹配，尋得與該面特征匹配程度高的另一碎片的一面，再將這兩個(gè)碎片的另一面做第二次特征匹配，在兩者匹配很好的前提下，探求出兩碎片的確定面屬于同一類。加入人工干預(yù)，對類的個(gè)數(shù)降維，并保證每類中圖片的數(shù)量相同。再利用問題二中的模型構(gòu)建方法，通過左右邊界匹配模型的求解、

5、上下邊界匹配模型的構(gòu)建方法，完成了本問的研究。最后，我們從問題二的模型多增加一層特征匹配約束可得到問題三的模型這一角度出發(fā)，得出了模型三的拼接精度更高這一結(jié)論。本文綜合各種匹配方法，根據(jù)問題的深入，對匹配模型加以不斷的改進(jìn)，結(jié)合matlab編程、wd拼圖等手段，對碎紙片的拼接復(fù)原做了逐步深入分析，并給出了基于邊界灰度、圖片行特征灰度的匹配模型。在文章的最后對模型的適用范圍做出了推廣，在實(shí)際應(yīng)用中有較大的參考價(jià)值。關(guān)鍵詞：左右邊界匹配特征

6、匹配上下邊界匹配matlab兩層篩選1kijijksks度。通過觀察圖片的平行切割特點(diǎn)，發(fā)現(xiàn)來自原文件同一行的文字切割后的圖片一般在相同的行位置上。所以可以考慮，先進(jìn)行行位置篩選，通過構(gòu)建圖片的特征列向量作為唯一標(biāo)識，建立特征匹配模型，得到具有相同行特征的圖片，聚成同一類。考慮到每類包含的圖片個(gè)數(shù)不一致，可加入人工干預(yù)，對類的個(gè)數(shù)降維，使得行集合包含的碎片個(gè)數(shù)一致。而利用左右邊界匹配模型可以確定同一行的圖片的序列；可采用相同的原理，建立

7、上下邊界匹配模型來解決縱向圖片的定序問題。這樣一來，可以拼接出本問的原文件，完成問題二的求解。問題三的分析問題三在前兩問的基礎(chǔ)上，加入了雙面打印這一條件。本問中圖片的個(gè)數(shù)相較于問題二增大了一倍，達(dá)2?11?19??418個(gè)，較前兩問復(fù)雜度最高。由于從單面看問題二和問題三沒有任何區(qū)別，所以可以采取相似的方法對問題三求解。但我們思考總結(jié)出如下兩方面：一方面不能思維定勢，也就是說所有編號中帶有a的圖不一定都來自同一面，即有可能是碎紙片的正面也

8、有可能是碎紙片的反面。另一方面如果采用問題二中相同的處理方法對附件5中所有的圖片排序的話，可能會發(fā)生一個(gè)圖片的匹配圖片過多，或者出現(xiàn)將一個(gè)碎紙片的正反面歸為同一類的錯(cuò)誤。綜合以上兩方面的思考，問題三的求解過程的特點(diǎn)在于：先對一張碎紙片構(gòu)建其對應(yīng)的特征匹配模型，若得到另外一張碎紙片與這張碎紙片匹配，則隨后對它們的反面進(jìn)行匹配以檢驗(yàn)。三、模型假設(shè)1.假設(shè)附件中每張碎紙片都是大小相等的矩形，切割邊緣光滑；2.假設(shè)附件中編號為000的圖片為第一

9、張圖片，編號為001的圖片為第二張圖片，依此類推；3.假設(shè)附件中每張圖片無傾斜，即底邊水平；4.假設(shè)附件中的每張圖片是無噪的，僅考慮圖像的拼接無須考慮圖像的修補(bǔ)；5.假設(shè)每一附件為同一頁紙的碎片數(shù)據(jù)；6.假設(shè)包含000a圖片的那頁為原文件的正面4.1符號說明四、符號說明與名稱解釋A(k)：第k張圖片的灰度值矩陣a(k)：第k張圖片的灰度值矩陣的第i行第j列的元素C(k)：第k張圖片的灰度值矩陣轉(zhuǎn)化的01矩陣c(k)：第k張圖片01矩陣的