2013全國大學(xué)生數(shù)學(xué)建模比賽B題-答案(總45頁)

1、2013全國大學(xué)生數(shù)學(xué)建模比賽B題-答案2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承 諾 書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫）

2、： B 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?重慶郵電大學(xué) 參賽隊(duì)員 (打印并簽名) ：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期： 2013 年 9 月 13 日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號(hào) 專 用 頁賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國前編號(hào)）：全國評(píng)閱編號(hào)（由全國組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：碎紙片的拼接復(fù)原摘要本文研究的是碎紙片的拼接復(fù)原問題。由于人工做殘片復(fù)原雖然準(zhǔn)確度高，

3、但有著效率低的缺點(diǎn)，僅由計(jì)算機(jī)處理復(fù)原，會(huì)由于各類條件的限制造成誤差與錯(cuò)誤，所以為了解決題目中給定的碎紙片復(fù)原問題，我們采用人機(jī)結(jié)合的方法建立碎紙片的計(jì)算機(jī)復(fù)原模型解決殘片復(fù)原問題， 并把計(jì)算機(jī)通過算法復(fù)原的結(jié)果優(yōu)劣情況作為評(píng)價(jià)復(fù)原模型好壞的標(biāo)準(zhǔn)，通過人工后期的處理得到最佳結(jié)果。面對(duì)題目中給出的BMP格式的黑白文字圖片，我們使用matlab軟件的圖像處理功能把圖像轉(zhuǎn)化為矩陣形式，矩陣中的元素表示圖中該位置像素的灰度值，再對(duì)元素進(jìn)行二值化處理得到新的矩陣。題目每一個(gè)附件中的碎紙片均為來自同一頁的文件，所以不需考慮殘片中含有未知紙張的殘片以及殘片中不會(huì)含有公共部分。鑒于殘片形狀分為“長條形”與“小

4、長方形”，殘片內(nèi)容分為中文、英文，紙張的打印類型分為“單面型”、“雙面型”，所以我們根據(jù)殘片的類型對(duì)矩陣做不同處理。針對(duì)問題一中給出的“長條形”碎紙片：對(duì)圖片轉(zhuǎn)化后的矩陣進(jìn)行邊緣檢測，發(fā)現(xiàn)每一張圖片的兩短邊在一定范圍內(nèi)全是白色，而僅有2張圖片的長邊在一定范圍內(nèi)全是白色，說明我們需要對(duì)長邊進(jìn)行拼接，一邊包含全白的長邊是原文件紙張的兩端。由于考慮到模型應(yīng)用的推廣，我們?cè)诖藛栔械哪Ｐ桶藞D片倒置的情況（僅在問題一中考慮倒置情況，鑒于問題二、三中數(shù)據(jù)量的增多，二三問不再考慮倒置情況），對(duì)圖片的長邊及矩陣中的第一列和最后一列與其他矩陣的第一列和最后一列進(jìn)行邊緣匹配，根據(jù)邊緣匹配度來確定圖片復(fù)原，最后若

5、發(fā)現(xiàn)拼接效果有偏差，在進(jìn)行人工操作。針對(duì)問題二中的“小長方形”碎紙片：由于數(shù)據(jù)量變多，盲目使用問題一中的方法不能保證準(zhǔn)確度，所以這里要進(jìn)一步約束使當(dāng)前圖片與少量圖片進(jìn)行匹配。觀察兩種文字的特點(diǎn)，我們可以發(fā)現(xiàn)中英文在位置上均有一定的特性，我們利用這種特性將有相同位置特性的碎紙片歸類為一組，在問題一方法的基礎(chǔ)上做少許修改后代入有相同位置特性的一組碎紙片中，根據(jù)邊緣匹配度將他們連接、檢查并做人工處理可得拼接后的橫行紙片，再將橫行紙片的長邊用同樣的方法做邊緣匹配可將行與行之間拼接起來，再做人工調(diào)整得到最優(yōu)結(jié)果。通過模型的建立求解過程可以發(fā)現(xiàn)中英文在本問題的求解方法中有著一定的不同，英文需要更多地人工判

6、斷處理。針對(duì)問題三考慮到雙面問題以及問題二中英文碎紙片的情況，我們把碎紙片兩面匹配度之和作為判斷碎紙片是否連接的評(píng)價(jià)標(biāo)準(zhǔn)，在問題一方法的基礎(chǔ)上，在計(jì)算機(jī)每一步的匹配結(jié)果加以人工選擇與判斷，這樣再次處理得到的結(jié)果，可以得到同問題二中一樣的橫行碎紙片，在根據(jù)新的橫行碎紙片的兩面邊緣匹配度之和進(jìn)行同樣的操作處理可以將原紙張拼接復(fù)原。關(guān)鍵詞： 殘片復(fù)原 matlab圖像處理 二值化 邊緣匹配度 倒置情況 位置特性 人工處理一 問題重述B題 碎紙片的拼接復(fù)原破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)

7、碎片數(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)。復(fù)原結(jié)果以圖片形式及表格形式表達(dá)（見【結(jié)果表達(dá)格式說明】）。 2. 對(duì)于碎紙機(jī)既縱切又橫切的情形，請(qǐng)?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對(duì)附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請(qǐng)寫出干預(yù)方式及

8、干預(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á)要求同上?！緮?shù)據(jù)文件說明】（1） 每一附件為同一頁紙的碎片數(shù)據(jù)。（2） 附件1、附件2為縱切碎片數(shù)據(jù)，每頁紙被切為19條碎片。（3） 附件3、附件4為縱橫切碎片數(shù)據(jù)，每頁紙被切為1119個(gè)碎片。（4） 附件5為縱橫切碎片數(shù)據(jù)，每頁紙被切為1119個(gè)碎片，每個(gè)碎片有正反兩面。該附件中每一碎片對(duì)應(yīng)兩個(gè)文件，共有211

9、19個(gè)文件，例如，第一個(gè)碎片的兩面分別對(duì)應(yīng)文件000a、000b?！窘Y(jié)果表達(dá)格式說明】復(fù)原圖片放入附錄中，表格表達(dá)格式如下：(1) 附件1、附件2的結(jié)果：將碎片序號(hào)按復(fù)原后順序填入119的表格；(2) 附件3、附件4的結(jié)果：將碎片序號(hào)按復(fù)原后順序填入1119的表格；(3) 附件5的結(jié)果：將碎片序號(hào)按復(fù)原后順序填入兩個(gè)1119的表格；(4) 不能確定復(fù)原位置的碎片，可不填入上述表格，單獨(dú)列表。二、模型假設(shè)假設(shè)題目中的碎紙圖片與真實(shí)文件紙張大小、顏色、邊緣情況相同。假設(shè)題目中的碎紙照片邊緣完整，不存在破損。假設(shè)所有碎紙片的掃描情況相同。假設(shè)人工干預(yù)后可以得到正確結(jié)果。假設(shè)原文件紙張的內(nèi)容具有意義。

10、三、符號(hào)說明符號(hào)符號(hào)意義編號(hào)為的圖片的灰度矩陣編號(hào)為的圖片經(jīng)二值化處理后的矩陣編號(hào)為的圖片的二維邊緣矩陣、邊緣匹配度矩陣編號(hào)為i的圖片在此處理后的二值化矩陣邊緣匹配度之和矩陣*其他未提及的符號(hào)會(huì)在文章中說明。四、問題分析4.1問題一的分析4.11 中文碎紙片的復(fù)原分析問題1、2、3附件1、2、3、4、5中的碎紙片均為一份紙張撕裂所得，所以碎紙片中不會(huì)存在含有相同信息的公共部分，這里進(jìn)行強(qiáng)調(diào)，下面不再重述。附件1中所給的圖片為5掃描原紙張碎片后得到的BMP格式的圖片，圖片像素均為，使用1matlab中的iamread函數(shù)可以做出圖片的灰度矩陣，舉例如下（由于該像素圖片轉(zhuǎn)換后為的矩陣，論文中無法放

11、置，所以僅簡單舉例說明，論文中若還出現(xiàn)龐大的矩陣，同本說明）：矩陣的中元素表示該位置圖片的灰度，255表示為白，0為黑，圖片中信息為黑白文字信息，但由于文字信息會(huì)存在陰影，所以矩陣中出現(xiàn)了介于0-255的元素。為了方便應(yīng)用，并查閱相關(guān)資料所得，可以對(duì)于本題中的黑白圖片做2二值化處理，可將上面例子中的轉(zhuǎn)化為如下的矩陣：其中白色用0值表示，非白色用1表示。將附件1中的19張圖片做如上處理得到各自的二值化后的矩陣Bi，矩陣均為的矩陣，這里我們分別將每張圖片的Bi矩陣第1列和第72列提取出來做一新的二維邊緣矩陣Ci，它是的矩陣。通過對(duì)所有圖片矩陣的分析可以發(fā)現(xiàn)C6、C8矩陣中均有一列為0，所以可以認(rèn)為

12、編號(hào)為006和008的圖片為原完整文件的一端，在做題過程中無需考慮會(huì)存在其他白邊與白邊拼接的情況。兩張圖片匹配的原則可以根據(jù)下面的圖1、圖2來表示。 圖1.圖片未倒置 圖2.圖片倒置如圖1，當(dāng)圖片未出現(xiàn)倒置情況時(shí)，即題目中的圖片均是正常擺放，將左邊矩陣的第二列元素與右邊矩陣的第一列元素進(jìn)行兩兩匹配。記錄元素相同的個(gè)數(shù)，個(gè)數(shù)除以1980為左邊矩陣第二列對(duì)右邊矩陣第一列的邊緣匹配度，記為：將所有碎紙片的二值化矩陣做如上匹配可依次選取與其匹配的碎紙片。圖1中左邊矩陣第一列與右邊矩陣第二列匹配的原則與上述相同，不再重述。如圖2，當(dāng)圖片出現(xiàn)倒置情況時(shí)，正常情況下應(yīng)是左邊矩陣的第二列元素與右邊矩陣的第一列

13、元素進(jìn)行兩兩匹配，若倒置后，則應(yīng)該是左邊矩陣的第二列元素與右邊矩陣的第二列元素倒置順序進(jìn)行比較，同樣記錄相同元素的個(gè)數(shù)并計(jì)算匹配度。圖2中左邊矩陣第一列元素與右邊矩陣第一列元素的匹配原則與上述相同，不再重述。綜合圖一圖二我們可以做出4個(gè)邊緣匹配度的矩陣，即未倒置時(shí)矩陣第一列與其他矩陣第二列的邊緣匹配度、未倒置時(shí)矩陣第二列與其他矩陣第一列的邊緣匹配度、倒置時(shí)矩陣第一列與其他矩陣第一列的邊緣匹配度、倒置時(shí)矩陣第二列與其他矩陣第二列的邊緣匹配度。由于（未）倒置時(shí)矩陣第一列與其他矩陣第二列匹配在思想上同（未）倒置時(shí)矩陣第二列與其他矩陣第一列匹配相同，所以這里只需考慮其中一種情況即可。任選其中一例說明，

14、由于碎紙片倒置情況未知，需要考慮未倒置時(shí)的情況與倒置式的情況，未倒置時(shí)矩陣第一列與其他矩陣第二列的邊緣匹配度矩陣第一行最大值與倒置時(shí)矩陣第一列與其他矩陣第一列的邊緣匹配度第一行的最大值進(jìn)行比較，選取匹配度大的作為拼接的紙片，即編號(hào)為000的碎紙片要與該紙片拼接。以此類推把19張碎紙片拼接完成后做人工處理。4.1.2英文碎紙片的復(fù)原分析將附件2的19張圖片做4.11中處理得到二值化后的矩陣Bi，矩陣均為的矩陣，這里我們分別將每張圖片的Bi矩陣第1列和第72列提取出來做一新的二維邊緣矩陣Ci，它是的矩陣。通過對(duì)所有圖片矩陣的分析可以發(fā)現(xiàn)C3 、C4矩陣中均有一列為0，所以可以認(rèn)為編號(hào)為003和00

15、4的圖片為原完整文件的一端，在做題過程中無需考慮會(huì)存在其他白邊與白邊拼接的情況。做如上判斷后解題過程同4.11。4.2問題二的分析4.21中文碎紙片的分析此問中同4.1的圖片處理方法，也需要將209張碎紙片進(jìn)行同樣的圖像處理轉(zhuǎn)化為灰度矩陣后進(jìn)行二值化處理得到處理后的矩陣。根據(jù)結(jié)果知此問中的圖片轉(zhuǎn)化后的矩陣為的矩陣，列數(shù)由第一問中的1980變?yōu)?80，雖然數(shù)量變少，但是圖片數(shù)量由19張變?yōu)榱?09張。若同樣使用4.1中的邊緣匹配的方法，一張碎紙片對(duì)應(yīng)其他208張碎紙片的邊緣匹配相同的像素點(diǎn)有208種情況，變化范圍為0-180，可知若直接采用4.1中的方法得到的結(jié)果可能出現(xiàn)多個(gè)相同或無法判斷的情況

16、，所以這里我們先考慮附件3中碎紙片的特性。觀察下面的圖3可以發(fā)現(xiàn)，通過查閱資料分析2基于文字特征的文檔碎紙片半自動(dòng)拼接，每一行的絕大多數(shù)中文文字均可認(rèn)為擁有同一上界、同一下界（圖3最右端出現(xiàn)了“一”字，但是同行還存在其他文字，可以認(rèn)為同一行文字有同一上界與同一下界），我們可以根據(jù)這一特性使用軟件將3匹配度高及位置相同的碎紙片歸類為一組。方法為：搜索每一張碎紙片轉(zhuǎn)化后二值化矩陣的每一行，若矩陣該行中存在數(shù)值1，則將該行全部賦值為1，若這一行元素全為0，則將該行全部賦值為0，其中1表示本行存在灰度小于255的像素，0表示不存在灰度小于255的像素，這樣將209張碎紙片做出4新的二值化矩陣，之后同4

17、.1的分析取邊緣做邊緣匹配得修改后的6邊緣匹配度矩陣，匹配度高則說明碎紙片的文字信息處于同一水平位置，見下圖圖4，之后再人工干預(yù)，得到較優(yōu)的結(jié)果。圖3.處理的圖片 圖4.再次處理后的圖片得到很多組有相同位置的的碎紙片后，在每一組內(nèi)采用4.1的中的邊緣匹配方法，這里為了防止出現(xiàn)兩白邊匹配造成碎紙片連接混亂的現(xiàn)象，要加以限制。方法為：若在組內(nèi)做邊緣匹配出現(xiàn)匹配度為1的情況，則暫時(shí)不連接此碎紙片，從剩余的碎紙片出發(fā)做邊緣匹配與其他碎紙片連接，直到組內(nèi)所有碎紙片均已覆蓋。這樣再通過一定的人工干預(yù)可以得到拼接復(fù)原后的的11橫行碎紙片，在同樣使用4.1的邊緣匹配方法，7將得到的11行的碎紙條的長邊進(jìn)行邊緣

18、匹配做出的匹配度矩陣后找最大匹配度作為連接的碎紙條，同樣為了防止出現(xiàn)兩白邊匹配造成碎紙片連接混亂的現(xiàn)象，要加以限制。方法為：若在組內(nèi)做邊緣匹配出現(xiàn)匹配度為1的情況，則暫時(shí)不連接此碎紙片，從剩余的碎紙片出發(fā)做邊緣匹配與其他碎紙片連接，直到11張拼接后的碎紙片均已覆蓋。最后加以人工處理，得到完整的原文件。4.2.2英文碎紙片的分析同4.2.1中的分析相同，通過觀察我們可以發(fā)現(xiàn)碎紙片的英文在位置上也有一定的規(guī)則可循。如下圖圖5。圖5.演示的圖片可以發(fā)現(xiàn)英文字母的主要的部分擁有同一上界和同一下界，但是跟中文不同，英文中會(huì)出現(xiàn)一些“y”、“b”之類的字母，為了同樣使用4.2.1中的方法我們通過觀察附件4

19、中圖片的像素情況，將圖片中每一行中黑色像素?cái)?shù)少于13的及字母的次要部分轉(zhuǎn)變?yōu)槎祷仃囍械?，將每一行中黑色像素大于等于13的及字母的主要部分轉(zhuǎn)化為二值化矩陣中的1，這樣得到的新的二值化矩陣，可認(rèn)為圖像轉(zhuǎn)變?yōu)閳D6的方式，同樣使用4.2.1中的分析方法將新的二值化矩陣做邊緣匹配，匹配度高的可以認(rèn)為兩碎紙片在原紙張中位于同一行，把匹配度高于0.9的元素分為一組后，對(duì)每一組進(jìn)行邊緣匹配。由于考慮到英文字符的情況，在4.1的基礎(chǔ)上，我們對(duì)于組內(nèi)圖片原始二值化矩陣的邊緣匹配度矩陣每一行的搜索，在這里我們?nèi)艟仃嚨娜我庖恍兄谐霈F(xiàn)匹配度大于0.9的元素個(gè)數(shù)超過2個(gè)，我們加以人工干預(yù)，根據(jù)文章的格式、內(nèi)容選擇應(yīng)

20、該連接的碎紙片，其他過程與4.1相同，區(qū)別僅為本文中需要對(duì)軟件執(zhí)行過程進(jìn)行人工干預(yù)，其他相同的步驟不在重述。圖6.演示圖片4.3問題三的分析本問在問題二英文碎紙片的基礎(chǔ)上還需要考慮紙片是否處于同一面，雖然數(shù)據(jù)量增加了一倍，但是判斷碎紙片是否連接的標(biāo)準(zhǔn)由一面增加到了兩面。本不對(duì)應(yīng)的兩張碎紙片一面的拼接復(fù)原情況好而令一面復(fù)原情況也好的情況只是個(gè)別的案例，所以可以將碎紙片兩面邊緣匹配度之和作為評(píng)判兩張是否匹配的標(biāo)準(zhǔn)建立邊緣匹配度之和矩陣，在這里可以先認(rèn)為匹配度之和高于1.9的情況為匹配結(jié)果優(yōu)秀。若僅將匹配度之和作為評(píng)判標(biāo)準(zhǔn)，基于4.2.2中的求解過程，英文碎紙片的純計(jì)算機(jī)復(fù)原結(jié)果較差，所以還需要在計(jì)

21、算機(jī)匹配碎紙片的過程中每一步都要進(jìn)行人工干預(yù)判斷、選擇。以紙片000與001為例，匹配方式可能為： 為了找出碎紙片如何對(duì)應(yīng)，則將的邊緣匹配度相加得到邊緣匹配度之和，將的邊緣匹配度相加得邊緣緣匹配度之和，兩者的和做出比較。若僅有一個(gè)大于等于1.9，則計(jì)算機(jī)輸出該匹配度，人工判斷是否碎紙片是否匹配；若兩者均大于等于1.9，計(jì)算機(jī)把兩個(gè)匹配度之和輸出，人工選擇判斷碎紙片應(yīng)是否匹配與如何匹配；若兩者均小于1.9，則計(jì)算輸出最大者，人工判斷碎紙片是否匹配。若出現(xiàn)計(jì)算機(jī)給出的結(jié)果人工判斷后發(fā)現(xiàn)匹配錯(cuò)誤，則記錄當(dāng)前匹配成功的碎紙片信息并在剩下的碎紙片中重新開始計(jì)算機(jī)匹配與人工判斷。上述的結(jié)果可以得到一些在同

22、一橫行的碎紙片的拼接，再次根據(jù)這些新的碎紙片的邊緣匹配度之和的情況通過上述人機(jī)結(jié)合的方法拼出11張橫行的碎紙片，剩下的就是應(yīng)該如何把11張橫行的碎紙片拼接成完整的一份紙張，這里將11張橫行碎紙片的上下長邊進(jìn)行兩兩匹配，以兩面邊緣匹配度之和的方法按照上述的方法將11橫行的碎紙片拼接完畢。五、模型的建立與求解5.1問題一的模型建立與求解 5.1.1 中文碎紙片的拼接復(fù)原根據(jù)4.1.1中的分析，做出的矩陣D、矩陣D、矩陣D、矩陣D（這里僅做出D與D，其他兩個(gè)矩陣僅在下面的說明中會(huì)提及，但不會(huì)使用），元素Dij為碎紙片圖像未倒置時(shí)矩陣i的第二列與矩陣j第一列的邊緣匹配度，元素Dij為碎紙片圖像倒置時(shí)矩

23、陣i的第二列與矩陣j的第二列的邊緣匹配度，元素Dij為碎紙片圖像倒置時(shí)矩陣i的第一列與矩陣j第一列的邊緣匹配度，元素Dij為碎紙片圖像未倒置時(shí)矩陣i的第一列與矩陣j第二列的邊緣匹配度。對(duì)于得到的兩個(gè)矩陣、，從i=0即第0行（為方便說明）開始，找到這一行中最大的匹配度，兩者進(jìn)行大小比較：1） 若大于等于，把所處列數(shù)賦值為新的i，找到這一行中的最大匹配度，兩者進(jìn)行大小比較，重復(fù)上述過程直到i重新變?yōu)?。若i經(jīng)過19次后返回0，則可以認(rèn)為所有的碎紙片已拼接在一起，僅需把兩個(gè)空白端分開后再做人工調(diào)整，則可得到結(jié)果；若i少于19次變化后變?yōu)?，則認(rèn)為部分碎紙片未拼在一起，要把剩余的紙片拼接在一起后做人工

24、調(diào)整。2） 若小于，把所處的列數(shù)賦值為新的i，找到矩陣、這一行中的最大匹配度，兩者進(jìn)行大小比較，其他過程與上述分析類似，不再進(jìn)行說明，重復(fù)上述過程直到i重新變?yōu)?。若i經(jīng)過19次后返回0，則可以認(rèn)為所有的碎紙片已拼接在一起，僅需把兩個(gè)空白端分開后再做人工調(diào)整，則可得到結(jié)果；若i少于19次變化后變?yōu)?，則認(rèn)為部分碎紙片未拼在一起，要把剩余的紙片拼接在一起后做人工調(diào)整。根據(jù)所得兩個(gè)矩陣、的情況，發(fā)現(xiàn)任意一行的大于，可以一定程度說明碎紙片中不存在倒置的情況，僅按上述大于等于的情況做分析即可。 該方法可以用圖7的matlab軟件編程流程圖來表示?？梢钥闯鲇捎趩栴}一中的數(shù)據(jù)量較小，為了方便我們僅對(duì)計(jì)算機(jī)

25、的編程結(jié)果進(jìn)行人工干預(yù)，而不對(duì)過程做人工干預(yù)。i=0 maxDi=maxDi?記錄i并重新賦值i是i=0?否i經(jīng)過19次變化（若重新進(jìn)行了搜索，此處為19-n次）是結(jié)束并輸出結(jié)果人工處理是本次搜索結(jié)束，記錄i并記錄搜索次數(shù)n并重新賦值i開始新的搜索記錄i并重新賦值i否maxDi=maxDi?圖7.流程圖得到的結(jié)果見表1： 表1.計(jì)算機(jī)拼圖位置表格1000006008014012015003010002016001004005009013018011007001根據(jù)表種情況可已發(fā)現(xiàn)碎紙片006和碎紙片008連接在一起，發(fā)生這種情況的原因是兩白邊邊緣匹配度為1.0，所以他們匹配在了一起，根據(jù)實(shí)際情

26、況，可以判定碎紙片008為正常放置情況下原紙張的左端，所以重新指定表格，以碎紙片008作為紙片的開端，表格見表2，在使用matlab中的imshow（）函數(shù)，得到人機(jī)結(jié)合后的復(fù)原圖片。 表2.修改后的拼圖位置表格20080140120150030100020160010040050090130180110070010000065.1.2 英文碎紙片的拼接復(fù)原根據(jù)4.1.1與4.1.2的分析，模型建立求解同5.1.1。使用計(jì)算求解的結(jié)果見表3。 表3.計(jì)算機(jī)拼圖位置表格3000005001009013010008012014017016004003006002007015018011根據(jù)表種情況

27、可已發(fā)現(xiàn)碎紙片003和碎紙片004連接在一起，發(fā)生這種情況的原因是兩白邊邊緣匹配度為1.0，所以他們匹配在了一起，根據(jù)實(shí)際情況，可以判定碎紙片003為正常放置情況下原紙張的左端，所以重新指定表格，以碎紙片003作為紙片的開端，表格見表3，在使用matlab中的imshow（）函數(shù)，人機(jī)結(jié)合后的復(fù)原圖片見圖片5。 表4.修改后的拼圖位置表格40030060020070150180110000050010090130100080120140170160045.2 問題二模型的建立與求解5.21 中文碎紙片復(fù)原的模型建立與求解搜索每一張碎紙片轉(zhuǎn)化后二值化矩陣的每一行，若存在黑色即矩陣該行中存在數(shù)值1

28、，則將該行全部賦值為1，若這一行不存在黑即此行元素全為0，則將該行全部賦值為0，這樣將209張碎紙片做出新的二值化矩陣，之后同5.1的求解過程做邊緣匹配，做出矩陣大小為邊緣匹配度矩陣（由于矩陣太大，在論文中不作出），元素為處理后的碎紙片邊緣二值化矩陣i的第二列與處理后的碎紙片邊緣二值化矩陣j第一列的邊緣匹配度，匹配度高則說明碎紙片的文字信息處于同一水平位置。在矩陣中每一行選取匹配度大于0.9的元素，進(jìn)行統(tǒng)計(jì)分組，可得結(jié)果如下表表5. 表5.分組情況序號(hào)碎紙片編號(hào)10 7 45 53 68 126 137 138 158 174 175 20821 18 23 26 30 41 50 62 76

29、 86 87 100 120 142 147 168 179 191 19532 11 22 28 49 54 57 65 91 95 118 129 141 143 178 186 188 190 19243 12 31 39 51 73 82 107 115 128 134 135 159 160 169 176 199 20354 40 101 108 113 114 117 119 123 140 146 151 154 155 185 194 20765 10 29 37 44 48 55 59 64 75 92 98 104 111 171 172 180 201 20676 19

30、 20 36 52 61 63 67 69 72 78 79 96 99 116 131 162 163 17788 9 25 74 1059182 131015 17 3380831321331561982002021116 21 66 106 109 110 139 145 150 157 173 181 184 187 197 2041224 35 38 46 81 88 103 122 130 148 161 167 189 1931327 60 85 152 165 170 2051432 56 70 93 153 166 1961534 42 43 47 58 77 84 90 9

31、4 97 112 121 124 127 136 144 149 164 1831614177118891910220125可以看出在取匹配度為0.9及以上時(shí)，分出了20個(gè)組，其中組內(nèi)元素最多的為19，組內(nèi)元素最少的為1。而最后的結(jié)果應(yīng)該為11行，我們需要對(duì)這些組中的元素進(jìn)行合并后得到11行，所以我們要先考慮元素?cái)?shù)量為19的組，再考慮其他元素?cái)?shù)多的組，對(duì)組內(nèi)圖片進(jìn)行5.1中的邊緣匹配，匹配后的結(jié)果在與元素?cái)?shù)少的組做匹配與人工處理。以序號(hào)2的組為例，該組包含19個(gè)元素，對(duì)于組內(nèi)的19個(gè)元素的原始二值化矩陣進(jìn)行上述中的邊緣匹配，通過結(jié)果觀察本題模型第一步確定模型的的可行性，其他的組的處理情況相同，

32、不再重述。結(jié)果如下，見表6。表6.內(nèi)部分組序號(hào)分組2062-142-030-041-023-147-191-050-179-120-086-195-026-001-087-018168-100-076分別復(fù)原得到圖片，觀察下面的圖8、圖9。 圖8 圖9對(duì)于第二問中文碎紙片的復(fù)原問題，通過上面的結(jié)果發(fā)現(xiàn)匹配結(jié)果較好，對(duì)于中文的碎紙片的拼接復(fù)原即使過程中未加入人工干預(yù)也可以得到較優(yōu)的結(jié)果?？梢园l(fā)現(xiàn)該組中文字的位置符合我們的想象，及同一行中的文字擁有同一上界和同一下界，在這一組中matlab軟件很好的將碎紙片拼接出來，思考為什么會(huì)出現(xiàn)上面圖9圖10兩者不能匹配在一起的原因?？梢园l(fā)現(xiàn)拼接復(fù)原后的圖8、

33、圖9左右兩側(cè)均存在白邊，僅從計(jì)算機(jī)的角度出發(fā)，無法認(rèn)出兩者的先后，所以這里我們要加以人工干預(yù)，通過對(duì)文章的內(nèi)容、文章的結(jié)構(gòu)、文章的形式的觀察人工拼接，得出結(jié)果。改進(jìn)后的圖片排序見表7，復(fù)原圖片見圖10。 表7. 人工干預(yù)序號(hào)分組2168-100-076-062-142-030-041-023-147-191-050-179-120-086-195-026-001-087-018 圖10通過結(jié)果可以發(fā)現(xiàn)拼接程度較好，所以也驗(yàn)證了本問題中碎紙片拼接復(fù)原模型的可行性。其他組做相同處理，這樣可得到拼接好的11橫行的碎紙條，對(duì)11橫行的碎紙條的長邊進(jìn)行邊緣匹配，建立新的邊緣匹配矩陣，方法同上，做出結(jié)果如

34、下，見表9。 表9一014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043二125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196三049

35、054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036四168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074五089146102154114040151207155140185108117004101113194119123六071156083132200

36、017080033202198015133170205085152165027060以上做出的表格把一些橫行碎紙片拼接在一起，未能拼接的原因是由于拼接后的橫行碎紙片兩端都存在白邊，計(jì)算機(jī)無法做出順序的判斷，所以我們要根據(jù)文字內(nèi)容、規(guī)格、形式等因素人工將它們結(jié)合起來，人機(jī)結(jié)合后的原文件以下面的表格10。 表10.附件3的復(fù)原049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023

37、147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021

38、173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123觀察發(fā)現(xiàn)拼接復(fù)原后結(jié)果較好。5.22英文碎紙片復(fù)原的模型建立與求解搜索每一張碎紙片轉(zhuǎn)化后二值化矩陣的每一行，若存在黑色像素?cái)?shù)量大于等于13即矩陣該行中數(shù)值1的數(shù)量大于等于13，則將該行全部賦值為1，若這一行黑色像素?cái)?shù)量小于

39、13，則將該行全部賦值為0，這樣將209張碎紙片做出新的二值化矩陣，之后同5.1的求解過程做邊緣匹配，做出矩陣大小為邊緣匹配度矩陣（由于矩陣太大，在論文中不作出），元素為處理后的碎紙片邊緣二值化矩陣i的第二列與處理后的碎紙片邊緣二值化矩陣j第一列的邊緣匹配度，匹配度高則說明碎紙片的文字信息處于同一水平位置。同樣在矩陣中每一行選取匹配度大于0.9的元素，進(jìn)行統(tǒng)計(jì)分組。在這里需要強(qiáng)調(diào)的是，若分完組后的組內(nèi)元素進(jìn)行5.2.1中的邊緣匹配進(jìn)行殘片復(fù)原，小組成員發(fā)現(xiàn)結(jié)果十分的不理想，任舉一例，見下圖11。圖11根據(jù)圖12可以發(fā)現(xiàn)對(duì)于本文中的英文殘紙片的文字信息主要內(nèi)容處于相同水平位置，文字信息處于同一水

40、平位置，結(jié)合5.2.1可以認(rèn)為首先判斷文字信息未知的方法是正確的。但是組內(nèi)英文碎紙片的拼接復(fù)原程度結(jié)果差，圖中部分碎紙片得到了復(fù)原，而大部分卻進(jìn)行了錯(cuò)誤的拼接。對(duì)比5.2.1的中文復(fù)原結(jié)果，可以認(rèn)為英文相對(duì)中文會(huì)有一定的特殊性。分析產(chǎn)生問題的原因，由于碎紙片的連接是按照組內(nèi)圖片兩兩邊緣匹配的的大小來決定的，發(fā)生如圖的情況說明：實(shí)際的對(duì)應(yīng)的碎紙片的邊緣匹配度一般在0.9以上，英文碎紙片實(shí)際對(duì)應(yīng)的碎紙片的邊緣匹配度會(huì)出現(xiàn)比其他碎紙片的邊緣匹配對(duì)小的情況。面對(duì)這種問題，我們需要對(duì)檢測邊緣匹配度的程序的過程進(jìn)行人工干預(yù)，方法為：其他圖片對(duì)當(dāng)前圖片的邊緣匹配度若出現(xiàn)兩個(gè)及兩個(gè)以上大于0.9的匹配度，則進(jìn)

41、行人工干預(yù)，根據(jù)文章的內(nèi)容、格式等進(jìn)行人工拼接復(fù)原，其他步驟同5.2.1。對(duì)于本文中對(duì)于英文碎紙片的拼接復(fù)原問題可用下面圖12的流程圖表示。開 始對(duì)灰度矩陣進(jìn)行5.2.2中的二值化處理對(duì)二值化矩陣Ei做邊緣匹配選取每一個(gè)元素對(duì)應(yīng)匹配度大于0.9的元素存于一組中，即將對(duì)應(yīng)的圖片歸為一組對(duì)于每一組內(nèi)圖片做5.1中的邊緣匹配當(dāng)前碎紙片對(duì)應(yīng)其他碎紙片的匹配度為0.9以上的碎紙片張數(shù)大于等于2張人工干預(yù)選擇碎紙片并判斷是重復(fù)判斷過程多次直到結(jié)束否人工干預(yù)處理結(jié)果計(jì)算機(jī)給出最大的結(jié)果后人工判斷 圖12.流程圖通過上述步驟可一把相同行的紙片先拼接好，得到新的11張橫行碎紙片，這里拼接11張碎紙片的方法同5.

42、2.1，不再重述，得到的結(jié)果見下表11。 表11.附件4的復(fù)原19175111541901842104180641064149322046539671472011481701961989411316478103918010126100617281468651107294015818698241171505595892303746127191949314188121126105155114176182151225720271165821591391129631381535338123120175855016018797203312041108116136733620713515764319945

43、173791611791432082174961119331421686216954192133118189162197112708460146817413719584717215696239912290185109132181956916716316618811114420631303413110252717817142662051015774145831345518563516918315244817712820013152125140193878948721217712401021155.3問題三模型的建立與求解本問我們可以先將所有的圖片用matlab的圖像處理得到灰度矩陣后二值化處理得

44、到每一個(gè)圖像的二值化矩陣，通過對(duì)圖片的觀察與對(duì)矩陣的判斷，編號(hào)為i的碎紙片a面右端（或左端）與b面左端（或右端）邊緣全是白色的圖片一共有22張，考慮到所有的碎紙片應(yīng)被拼接為11行，而左右個(gè)兩端，乘以2就是22，所以136、005、143、083、090、013、035、172、105、009、054、078、089、186、199、088、114、146、165、003、023、099這22張碎紙片應(yīng)是原文件紙張的兩端。為了方便可以將可以選擇這22張碎紙片作為開端匹配對(duì)應(yīng)的紙片。以紙片000與001為例，匹配方式可能為： 為了找出碎紙片如何對(duì)應(yīng)，則將的邊緣匹配度相加得到邊緣匹配度之和，將的邊緣

45、匹配度相加得邊緣緣匹配度之和，兩者的和做出比較。若僅有一個(gè)大于等于1.9，則計(jì)算機(jī)輸出該匹配度，人工判斷是否碎紙片是否匹配；若兩者均大于等于1.9，計(jì)算機(jī)把兩個(gè)匹配度之和輸出，人工選擇判斷碎紙片應(yīng)是否匹配與如何匹配；若兩者均小于1.9，則計(jì)算輸出最大者，人工判斷碎紙片是否匹配。綜上先建立邊緣匹配度之和矩陣，然后按照上面的匹配原則開始匹配。若出現(xiàn)計(jì)算機(jī)給出的結(jié)果人工判斷后發(fā)現(xiàn)匹配錯(cuò)誤，則記錄當(dāng)前匹配成功的碎紙片信息并在剩下的碎紙片中重新開始計(jì)算機(jī)匹配與人工判斷。該過程可以用下面的流程圖圖13來表示。 開始數(shù)據(jù)初始化（邊緣匹配度矩陣）找出當(dāng)前節(jié)點(diǎn)所有較優(yōu)匹配最佳匹配個(gè)數(shù)為三個(gè)或以上最佳匹配個(gè)數(shù)在兩

46、個(gè)或以下人工干預(yù)節(jié)點(diǎn)選擇最佳匹配算法自動(dòng)選擇最佳匹配是否還有待添加節(jié)點(diǎn)輸出結(jié)果，進(jìn)行最后調(diào)整否是 圖13.流程圖根據(jù)上面的流程圖17，以009碎紙片為例（它是22個(gè)邊緣碎紙片之一）作為起始的圖片，進(jìn)行拼接，拼接結(jié)果如下：該題中人工干預(yù)占了總過程的35%，按上面的原則做出一些拼接好的碎紙片后，按照5.2.2中的方法，可以將碎紙片拼接成為11橫行的碎紙片，然后繼續(xù)使用本問題三中的方法將11橫行的碎紙片拼接完成并做人工判斷與人工處理。附件5的還原后的表格見下表12、表13。表1278b111b125a140a155a150a183b174b110a66a108a18b29a189b81b164b20a47a136b89a10b36a76b178a44a25b192a124b22a120b144a79a14a59a60b147a152a5a186b153a84b42b30a38a121a98a94b61b137b45a138a56b131b187b86b200b143b199b11b161a169b194b173b206b156a34a181b198b87a132b