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

1、碎紙片的拼接復(fù)原摘要本文運(yùn)用左右邊界匹配、圖片特征匹配、上下邊界匹配等方法研究單頁(yè)打印縱切紙片、單頁(yè)打印橫、縱切紙片以及雙頁(yè)打印橫、縱切紙片的拼接與復(fù)原問(wèn)題。針對(duì)問(wèn)題一，首先對(duì)圖像進(jìn)行數(shù)據(jù)處理，讀取圖片的灰度信息，構(gòu)建灰度矩陣，并將灰度矩陣轉(zhuǎn)化為01矩陣，從而將二維圖片數(shù)值化。接著，提取出01矩陣的第一列與最后一列，存儲(chǔ)在圖片的左右邊界矩陣中，通過(guò)建立兩張圖片的左右邊界匹配度模型，探究圖片的左右鄰接關(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。問(wèn)題二，采用二層篩選的方法，第一層做行位置篩選，讀取圖片的前100個(gè)像素行，存入圖片的特征列向量中，并將此列向量作

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

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

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

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

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

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

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