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

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

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

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

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

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

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

7、碎片數量巨大，人工拼接很難在短時間內完成任務。隨著計算機技術的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術，以提高拼接復原效率。請討論以下問題：1. 對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數據進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結果以圖片形式及表格形式表達（見【結果表達格式說明】）。 2. 對于碎紙機既縱切又橫切的情形，請設計碎紙片拼接復原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數據進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及

8、干預的時間節(jié)點。復原結果表達要求同上。3. 上述所給碎片數據均為單面打印文件，從現實情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數據。請嘗試設計相應的碎紙片拼接復原模型與算法，并就附件5的碎片數據給出拼接復原結果，結果表達要求同上?！緮祿募f明】（1） 每一附件為同一頁紙的碎片數據。（2） 附件1、附件2為縱切碎片數據，每頁紙被切為19條碎片。（3） 附件3、附件4為縱橫切碎片數據，每頁紙被切為1119個碎片。（4） 附件5為縱橫切碎片數據，每頁紙被切為1119個碎片，每個碎片有正反兩面。該附件中每一碎片對應兩個文件，共有211

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

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

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

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

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

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

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

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

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

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

19、中圖片的像素情況，將圖片中每一行中黑色像素數少于13的及字母的次要部分轉變?yōu)槎祷仃囍械?，將每一行中黑色像素大于等于13的及字母的主要部分轉化為二值化矩陣中的1，這樣得到的新的二值化矩陣，可認為圖像轉變?yōu)閳D6的方式，同樣使用4.2.1中的分析方法將新的二值化矩陣做邊緣匹配，匹配度高的可以認為兩碎紙片在原紙張中位于同一行，把匹配度高于0.9的元素分為一組后，對每一組進行邊緣匹配。由于考慮到英文字符的情況，在4.1的基礎上，我們對于組內圖片原始二值化矩陣的邊緣匹配度矩陣每一行的搜索，在這里我們若矩陣的任意一行中出現匹配度大于0.9的元素個數超過2個，我們加以人工干預，根據文章的格式、內容選擇應

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

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

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

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

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

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

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

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

28、，則將該行全部賦值為1，若這一行不存在黑即此行元素全為0，則將該行全部賦值為0，這樣將209張碎紙片做出新的二值化矩陣，之后同5.1的求解過程做邊緣匹配，做出矩陣大小為邊緣匹配度矩陣（由于矩陣太大，在論文中不作出），元素為處理后的碎紙片邊緣二值化矩陣i的第二列與處理后的碎紙片邊緣二值化矩陣j第一列的邊緣匹配度，匹配度高則說明碎紙片的文字信息處于同一水平位置。在矩陣中每一行選取匹配度大于0.9的元素，進行統(tǒng)計分組，可得結果如下表表5. 表5.分組情況序號碎紙片編號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及以上時，分出了20個組，其中組內元素最多的為19，組內元素最少的為1。而最后的結果應該為11行，我們需要對這些組中的元素進行合并后得到11行，所以我們要先考慮元素數量為19的組，再考慮其他元素數多的組，對組內圖片進行5.1中的邊緣匹配，匹配后的結果在與元素數少的組做匹配與人工處理。以序號2的組為例，該組包含19個元素，對于組內的19個元素的原始二值化矩陣進行上述中的邊緣匹配，通過結果觀察本題模型第一步確定模型的的可行性，其他的組的處理情況相同，

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

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

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

35、054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036四168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074五089146102154114040151207155140185108117004101113194119123六071156083132200

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

37、147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021

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

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

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

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

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

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

44、到每一個圖像的二值化矩陣，通過對圖片的觀察與對矩陣的判斷，編號為i的碎紙片a面右端（或左端）與b面左端（或右端）邊緣全是白色的圖片一共有22張，考慮到所有的碎紙片應被拼接為11行，而左右個兩端，乘以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張碎紙片應是原文件紙張的兩端。為了方便可以將可以選擇這22張碎紙片作為開端匹配對應的紙片。以紙片000與001為例，匹配方式可能為： 為了找出碎紙片如何對應，則將的邊緣匹配度相加得到邊緣匹配度之和，將的邊緣

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

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