2013年b題全國數(shù)學(xué)建模二等獎(jiǎng)?wù)撐?原創(chuàng))

1、1碎紙片的拼接復(fù)原碎紙片的拼接復(fù)原摘要摘要破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。但是人工完成效率很低，所以引入計(jì)算機(jī)復(fù)原，計(jì)算機(jī)雖然準(zhǔn)確率不及人工高，但是可以大大減輕工作強(qiáng)度。本論文主要是對(duì)紙張形狀為矩形切割規(guī)范并且紙張上的文字標(biāo)準(zhǔn)的碎紙片的拼接復(fù)原的研究。問題一：首先根據(jù)圖片的灰度矩陣找出第一張（最左側(cè)）圖片，根據(jù)小差值優(yōu)先匹配依次排出相鄰圖片。碎紙片復(fù)原后的順序如附件一、二所示。問題二：首

2、先根據(jù)圖片的灰度矩陣最左側(cè)n列灰度值求和最大，可找出第一列（最左側(cè)）圖片，共11張。根據(jù)“行間”的位置特征作為凝聚點(diǎn)進(jìn)行聚類分析，將所有圖片分為11類，即11行。應(yīng)用小差值優(yōu)先匹配將這每行的圖片進(jìn)行拼接，得到11個(gè)行圖片，再次應(yīng)用小差值優(yōu)先匹配把這11個(gè)行圖片拼接成完整的圖片。碎紙片復(fù)原后的順序如附件三、四所示。問題三：同問題二方法一致，找出第一列（最左側(cè)）圖片（正反兩面共有22張圖片），將這些“行間”的位置特征作為凝聚點(diǎn)進(jìn)行聚類分析，

3、所有的圖片分為11“大行”，將這些圖片配對(duì)的正反面進(jìn)行上邊緣“粘接”處理，按照小差值優(yōu)先匹配將這每行的粘接形成的19圖片（如圖一所示）進(jìn)行拼接，得到11個(gè)行圖片之后，再次應(yīng)用小差值優(yōu)先匹配把這11個(gè)行圖片拼接成完整的圖片。碎紙片復(fù)原后的順序如附件五所示。觀察上述三個(gè)問題的處理方法可知，三個(gè)問題的解決辦法主干思想完全相同，都是小差值優(yōu)先匹配解決，并且清晰簡練。但是由于問題的逐漸深入和復(fù)雜程度的增加，僅靠這一個(gè)簡單的方法并不能在實(shí)際中解決問

4、題，于是增加約束條件減小搜索范圍，如：找出“行間”位置，并作為凝聚點(diǎn)進(jìn)行聚類分析，然后就可以很大程度上減小出錯(cuò)的概率。關(guān)鍵詞：關(guān)鍵詞：聚類分析、MATLABR2012a、小差值優(yōu)先匹配、灰度矩陣3即最左側(cè)矩陣所有行求和值最大，可以得到最左側(cè)的圖片，然后可以拼接出整張圖片。針對(duì)問題二針對(duì)問題二：對(duì)于碎紙機(jī)既縱切又橫切的情形，請(qǐng)?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法。方法一：方法一：應(yīng)用第一問中的小差值優(yōu)先匹配，求出所有圖片邊緣矩陣的對(duì)應(yīng)行相減取絕對(duì)

5、值最后求和，然后逐個(gè)比較，此時(shí)會(huì)發(fā)現(xiàn)由于圖片小且圖片中字?jǐn)?shù)較少，灰度矩陣所給出的信息就會(huì)比較少，并且應(yīng)用小差值優(yōu)先匹配所求和會(huì)有大量數(shù)值相差不是很大圖片出現(xiàn)，出現(xiàn)過多的候選項(xiàng)，這會(huì)對(duì)判斷哪張圖片可以復(fù)原產(chǎn)生很大的影響，甚至?xí)霈F(xiàn)無法選擇，因?yàn)椴糠謭D片是正好沒有切割文字，此時(shí)計(jì)算機(jī)是無法判斷哪張可以復(fù)原的，就需要對(duì)方法一進(jìn)行補(bǔ)充提供更多的約束條件或是進(jìn)行人工干預(yù)，所以得出了以下的方法二。方法二：方法二：此方法主體方法也是應(yīng)用小差值優(yōu)先匹配

6、，針對(duì)上述出現(xiàn)過多的候選項(xiàng)情況，觀察附件三及附件四中的圖片會(huì)發(fā)現(xiàn)，雖然所給的圖片小且文字?jǐn)?shù)目少，但是觀察可知這些圖片全部大小一致但是“行間”（兩行文字之間的空白處）所出現(xiàn)的位置是不同的，記錄這幾行的位置，將其余圖片所生成的矩陣對(duì)比，若特殊的幾行出現(xiàn)在相同的位置，則可將這些圖片分為一“大行”（這些圖片的行間距出現(xiàn)的位置相同）。然后將“大行”內(nèi)的圖片應(yīng)用第一問中的小差值優(yōu)先匹配進(jìn)行拼接，可將這些行拼出。緊接著人工干預(yù)將所得的行分為11行（如

7、果所得到的行多余11行），最后將這是11行轉(zhuǎn)置成11列，按照第一問的方法進(jìn)行即可拼出完整的圖片。針對(duì)問題三：針對(duì)問題三：該問題比第二問更復(fù)雜，但是更貼合于實(shí)際情況，即實(shí)用性很強(qiáng)。仔細(xì)觀察附件5中的圖片，可以觀察到，每張圖片的a面和b面，“行間”所處的位置是相同的。這樣，可以“行間”所處的位置進(jìn)行聚類，聚為11類，同第二問方法一樣，先分行，然后再每行拼接出來，轉(zhuǎn)置成列，應(yīng)用小差值優(yōu)先匹配將這11列拼接，即可得出完整圖片。但是行分完后，猜測

8、每行有英語碎紙片，由于英文字母本身所能獲得的信息量較少，且每行的圖片過多，在按照第二種方法處理時(shí)，會(huì)出現(xiàn)過多接近值，甚至?xí)霈F(xiàn)錯(cuò)誤排列，再仔細(xì)觀察及閱讀題意可以得出，一行圖片的正面確定且結(jié)果正確時(shí)，反面是自然形成的，這樣就只用到了一面數(shù)據(jù)量，若此時(shí)將兩張圖片的正反面以上邊緣相接展開，形成高度是原高兩倍的行圖片，這樣就會(huì)同時(shí)應(yīng)用到正反兩面的邊緣數(shù)據(jù)，提高篩選時(shí)的準(zhǔn)確率。同理，在每一行都拼完后，在進(jìn)行“大行”相拼的時(shí)候，可以將這個(gè)行的正反兩