年數(shù)學建模b題

1、碎紙片的拼接復原【摘要】：碎紙片拼接技術是數(shù)字圖像處理領域的一個重要研究方向，把計算機視覺 和程序識別應用于碎紙片的復原，在考古、司法、古生物學等方面具有廣泛的應用，具有 重要的現(xiàn)實意義。本文主要結合各種實際應用背景，針對碎紙機絞碎的碎紙片，基于計算 機輔助對碎紙片進行自動拼接復原研究。針對問題1,依據(jù)圖像預處理理論，通過 matlab程序處理圖像，將圖像轉化成適合于 計算機處理的數(shù)字圖像，進行灰度分析，提取灰度矩陣。對于僅縱切的碎紙片，根據(jù)矩陣 的行提取理論，將每個灰度矩陣的第一列提取，作為新矩陣 Ai,提取每個灰度矩陣的最后 一列，生成新矩陣Bi。建立碎紙片匹配模型：?-1G i 2d(?

2、 = VE (?- ?)，其中 i, j = 0,?n- 1?=0P= 0w?1?聞?)0< ?< ?-1將矩陣Ai中的任一列與矩陣B1中的每一列帶入模型，所彳4 P值對應的i ,j值，即為所拼 接的碎片序列號。將程序進行循環(huán)操作，得到最終的碎片自動拼接結果。針對問題2,首先將圖像信息進行灰度分析，提取灰度矩陣。基于既縱切又橫切的碎 紙片，根據(jù)矩陣的行列提取理論，分別提取每個灰度矩陣的第一列和最后一列，分別生成 新矩陣A2、B2；提取所有灰度矩陣的第一行和最后一行，分別作為新生成的矩陣C2、D2。由于紙質文件邊緣空白處的灰度值為常量，通過對灰度矩陣的檢驗提取，確定最左列的碎 紙片排

3、序。在此基礎上，采用從局部到整體，從左到右的方法，建立匹配篩選模型：?-12d(? = VE (?- ?)，其中 i, j = 0,?n- 1?=0?-1，其中 i, j= 0,?m- 1。d(? = VS (?- ?%)?=0P= 0V?(?,0v ?v ?-1q = 0v ?"(?)0v ?v ?-1將矩陣A2中的任一列分別與矩陣B2中每一列代入模型，所彳4 P值對應的i ,j值即為橫排 序；將矩陣C2中的任一行分別于矩陣D2中的任一行代入模型，所得q值對應的i ,j值即為 列排序。循環(huán)進行此程序，得計算機的最終運行結果。所得結果有少許誤差，需人工調制， 更正排列順序，得最終拼接

4、結果。針對問題3,基于碎紙片的文字行列特征，采用遺傳算法，將所有的可能性拼接進行 比較，進行擇優(yōu)性選擇。反面的排序結果用于對正面排序的檢驗， 發(fā)現(xiàn)結果有誤差，此時， 進行人工干預，調換碎紙片的排序?！娟P鍵詞】：灰度矩陣歐式距離圖像匹配自動拼接人工干預一、問題重述破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用。傳統(tǒng)上，大量的紙質物證復原工作都是以人工的方式完成的，準確率較高，但效率很低。特別是當碎片數(shù)量巨大，人工拼接不但耗費大量的人力、物力，而且還可能對物證造成一定的損壞。 隨著計算機技術的發(fā)展， 人們試圖把計算機視覺和模式識別應用于碎紙片復原，開展對碎紙片自動

5、拼接技術的研究，以提高拼接復原效率。試討論一下問題，并根據(jù)題目要求建立相應的模型和算法：1. 對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片(僅縱切) ，建立碎紙片拼接復原模型和算法，并針對附件 1、附件 2 給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結果以圖片形式及表格形式表達。2. 對于碎紙機既縱切又橫切的情形，請設計碎紙片拼接復原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結果表達要求同上。3. 上述所給碎片數(shù)據(jù)均為單面打

6、印文件，從現(xiàn)實情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復原問題需要解決。 附件 5 給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。 請嘗試設計相應的碎紙片拼接復原模型與算法， 并就附件 5 的碎片數(shù)據(jù)給出拼接復原結果，結果表達要求同上。結果表達格式說明：復原圖片放入附錄中，表格表達格式如下：(1)附件1、附件2的結果：將碎片序號按復原后順序填入1X19的表格；(2)附件3、附件4的結果：將碎片序號按復原后順序填入11X19的表格；(3)附件5的結果：將碎片序號按復原后順序填入兩個11 X 19的表格；4. ) 不能確定復原位置的碎片，可不填入上述表格，單獨列表。二、問題分析碎紙片自動拼接技

7、術是圖像處理與識別領域中的一個較新但很典型的應用，是通過掃描和圖像提取技術獲取一組碎紙片的信息，然后利用計算機進行相應的處理，從而實現(xiàn)對這些碎紙片的全自動或半自動的拼接復原。碎紙片的自動拼接可以近似地看作是一個拼圖問題。在機器人和計算機視覺領域中，很早就有學者對自動拼圖進行了研究1 ， 2 。但是這些技術都利用了拼圖游戲中的一些特殊特征及一些先驗知識， 而在許多實際應用中都不能滿足這些條件。根據(jù)待拼接圖像(輸入)與拼接圖像(輸出)的不同類型3 ，可以將圖像拼接分為四類：基于靜態(tài)圖像的靜態(tài)圖像拼接、基于靜態(tài)圖像的動態(tài)圖像拼接、基于視頻的序列的靜態(tài)圖像拼接和基于視頻序列的動態(tài)圖像拼接。 本文主要致

8、力于靜態(tài)圖像的靜態(tài)圖像拼接，即碎紙機絞碎的規(guī)則的碎紙片的自動拼接。問題 1：根據(jù)圖像預處理理論，通過程序語言將圖像導入 matlab 程序，對圖像進行預處理，將碎紙片轉換成適合于計算機處理的數(shù)字圖像形式， 并對數(shù)字圖像進行灰度分析， 提取灰度矩陣。對于僅縱切的碎紙片，根據(jù)矩陣的行提取理論，將每個灰度矩陣的第一列提取，作為新矩陣A,提取每個灰度矩陣的最后一列，作為新矩陣B。建立碎紙片匹配模型。根據(jù)遺傳算法的思想， 將矩陣 A 中的任一行與矩陣B 中的每一行帶入模型， 由最大相似性原理得 s 值對應的 i ,j 值， 即為所拼接的碎片序列號。 將程序進行循環(huán)操作， 并最終建立對輸入的解釋。問題 2

9、：首先對碎紙片圖像進行預處理，通過matlab 程序將圖像信息進行灰度分析，提取灰度矩陣?；诩瓤v切又橫切的碎紙片，根據(jù)矩陣的行列提取理論，分別提取每個灰度矩陣的第一列，生成新矩陣A2,提取最后一列，結合生成新矩陣B2；提取所有灰度矩陣的第一 行，作為新生成的矩陣C2,提取最后一行，作為新矩陣D2。由于紙質文件邊緣空白處的灰 度值為常量，通過對灰度矩陣的檢驗提取，確定最左列的碎紙片排序。在此基礎上，采用 從局部到整體，從左到右的方法，建立匹配篩選模型。將矩陣A2中的任一列分別與矩陣B2 中每一列代入模型，所彳4 P值對應的i ,j值即為橫排序；將矩陣C2中的任一行分別于矩陣D2 中的任一行代入

10、模型，所彳4q值對應的i值即為列排序。循環(huán)進行此程序，得計算機的最 終運行結果。所得結果有少許誤差，需人工調制，更正排列順序，得最終拼接結果。問題3:針對雙面打印文件的碎紙片拼接處理，首先要對碎紙片兩面的圖像信息都進行圖像預 處理，運用matlab程序提取圖像的灰度矩陣。基于碎紙機絞碎的碎紙片，每個碎紙片的 大小是一樣的，采用差距度量法。取矩陣中特征值從第一行中開始到限制條件取i行，限制條件是當取到i行時滿足每行都是特征值的矩陣還有 2m個矩陣，則這2m個矩陣為同一 行碎片所產(chǎn)生的矩陣。包括正反面碎紙片。然后取其中矩陣左邊列向量滿足，此行矩陣所 剩兩個矩陣，此過程雖然誤差較小，針對其他問題可能

11、要產(chǎn)生誤差，需要人工干預，剔除 多余矩陣。然后取出兩個中的一個矩陣，與產(chǎn)生的這一行矩陣進行匹配，獲取一行排序較 優(yōu)的碎片鏈接。運用嵌套循環(huán)實現(xiàn)每行的排序連接。三、符號說明m提取灰度矩陣行（列）生成的新矩陣的行數(shù)n提取灰度矩陣行（列）生成的新矩陣的列數(shù)A提取灰度矩陣第一列生成的新矩陣B提取灰度矩陣最舟-列生成的新矩陣C提取灰度矩陣第一行生成的新矩陣D提取灰度矩陣最舟-行生成的新矩陣d(?2?矩陣A中第i列與矩陣B中第j列的歐氏距離d(?矩陣C中第i行與矩陣D中第j行的歐氏距離四、模型假設1）同一切線處的兩條邊界灰度值的差別在誤差范圍之內(nèi)。2）所有的待拼接的碎紙片都是規(guī)則的。3）假設不存在文件缺失

12、、人為因素等意外因素。4）假設所有的數(shù)字圖像文件都是已整理好的，不需要再進行旋轉、剪裁等操作。五、模型建立與問題解決首先，對碎紙片圖像進行預處理。由于基于文字的數(shù)字圖像中文字和背景的灰度值存 在明顯差異，運用程序把已整理好的數(shù)字圖像依次導入 matlab軟件，根據(jù)圖像顯示技術, 提取其灰度矩陣，改變數(shù)字圖像的視覺效果，將數(shù)字圖像轉化成一種更適合于計算機進行 分析處理的數(shù)據(jù)形式。再者，本文涉及的是無重疊的規(guī)則碎紙片拼接，因此只需處理每一 張碎紙片的邊緣交界處的數(shù)據(jù)，應用 matlab程序對灰度矩陣進行邊界數(shù)據(jù)的提取，減少 了數(shù)據(jù)的處理量，為碎紙片的自動拼接節(jié)省了時間。然后，對所提取的每組數(shù)據(jù)進行

13、相似 性度量，采用二維歐式距離，即：?-1d(?a? = VE (?- ?)2 ，其中 i, j = 0,?n- 1?=0根據(jù)遺傳算法，將提取的所有待拼接碎紙片的邊界數(shù)據(jù)進行分別左右、上下交叉的兩兩匹配，根據(jù)最大相似性原則，建立匹配準則：p= 0V?物（?溜0V ? V ?-1所彳導p值對應的i ,j值即為拼接序列。5.1問題一我們依據(jù)圖像預處理理論，通過 matlab程序處理圖像，將圖像轉化成適合于計算機 處理的數(shù)字圖像，并對數(shù)字圖像進行灰度分析，提取灰度矩陣。對于僅縱切的碎紙片，根 據(jù)矩陣的行提取理論，將每個灰度矩陣的第一列提取，作為新矩陣Ai,提取每個灰度矩陣的最后一列，生成新矩陣Bi。

14、建立碎紙片匹配模型：?-iG i 2d(? = VE (?- ?)，其中 i, j = 0,?n- 1?=0P= 0v?物（?溜0v ? v ?-1將矩陣Ai中的任一列與矩陣Bi中的每一列帶入模型，所彳4 P值對應的i ,j值，即為所拼 接的碎片序列號。將程序進行循環(huán)操作，得到最終的碎片自動拼接結果。附件i的碎紙片復原結果為：表-i0080i40i20i50030i00020i600i0040050090i30i80ii0070i7000006附件2的碎紙片復原結果為：表-20030060020070i50i80ii00000500i009 0i30i0 0080i20i4 0i70i6 00

15、45.2問題二根據(jù)圖像預處理理論，首先將圖像信息進行灰度分析，提取灰度矩陣。基于既縱切又 橫切的碎紙片，根據(jù)矩陣的行列提取理論，分別提取每個灰度矩陣的第一列，生成新矩陣 A2,提取最后一列，結合生成新矩陣B2；提取所有灰度矩陣的第一行，作為新生成的矩陣 C2,提取最后一行，作為新矩陣D2。由于紙質文件邊緣空白處的灰度值為常量，通過對灰 度矩陣的檢驗提取，確定最左列的碎紙片排序。在此基礎上，采用從局部到整體，從左到 右的方法，建立匹配篩選模型：?-iii 2d(? = VE (?- ?)，其中 i, j = 0,?n- i?=0?-i/ce sc 2d(? = VE (?- ?),其中 i, j

16、= 0,?m- i?=0P= ov?；?(?, q= ov?電(?羽?) 0v?v?-i0v?v?-i將矩陣A2中的任一列分別與矩陣B2中每一列代入模型，所彳4 P值對應的i ,j值即為橫排 序；將矩陣C2中的任一行分別于矩陣D2中的任一行代入模型，所得q值對應的i ,j值即為 列排序。循環(huán)進行此程序，得計算機的最終運行結果。所得結果有少許誤差，需人工調制， 更正排列順序，得最終拼接結果。附件3的碎紙片復原結果為：表-3049054065143186002057192178118190095011022129028091188141061019：078067069：09916209613107

17、9:063116163r 072006177020052036168100076062142030041023147191050179120086195026 0010870180381480461610240350811891221031301930881670250080091050740711561 083132200。170800332021981 0151331701 205085152165027060014128003159082199135012073160203169134039031051107115176094034084183090：047121042124144:07

18、7112149r 097136164127058043125013182109197：016184110187066106150021I173157181204139145029064111201005092180048037075055044206010104098172171059007208：138158126068175045174000：1370530561093153070166032196089146102154114040151207155140185108117004101113194119123附件4的碎紙片復原結果為:表-4191075011154190184002104

19、180064106004149032204065 0390671472011481701961981094113164078103:091080101r 026100006 017028146086051107029040158186098024117150005059058092030037046127019194093141088121126105155114176182151022057202:0711650821591391 0011290631 1381530530381231 1201750851 050160187097203031020041108116136073036207

20、13501507604319904517307916117914320802110070490611119033142168062r 169054192r 1331181891621971120700840600140681 174137195008047172156096I 02309912210901851091321810950691671631661881111442060031300340131100250271781710421066205010P157074145083134r 055018056r 0350160091831520440810771282001310521251

21、401930870890480720121771240001021155.3問題三針對雙面打印文件的碎紙片拼接處理，首先要對碎紙片兩面的圖像信息都進行圖像預 處理，運用matlab程序提取圖像的灰度矩陣。基于碎紙機絞碎的碎紙片，每個碎紙片的 大小是一樣的，采用差距度量法。取矩陣中特征值從第一行中開始到限制條件取i行，限制條件是當取到i行時滿足每行都是特征值的矩陣還有 2m個矩陣，則這2m個矩陣為同一 行碎片所產(chǎn)生的矩陣。包括正反面碎紙片。然后取其中矩陣左邊列向量滿足，此行矩陣所 剩兩個矩陣，此過程雖然誤差較小，針對其他問題可能要產(chǎn)生誤差，需要人工干預，剔除 多余矩陣。然后取出兩個中的一個矩陣，

22、與產(chǎn)生的這一行矩陣進行匹配，獲取一行排序較 優(yōu)的碎片鏈接。運用嵌套循環(huán)實現(xiàn)每行的排序連接。附件5的碎紙片復原結果為：正面結果：表-5136a047b020b164a081a189ao29b018a108b066b110b174a183a150b155)b140b125ib1a078a005b152b147b060a059b014b079b144b120a022b124a192 b025a044b178)b076a036ib01()a089b143a200a086a187a131a056a138b045b137a061a094a098 b121b038b030b042a084a153；b18&#

23、163;a083b039a097b175b072a093b132a087b198a181S034b156 b206a173a194Ia169a161b011a199a090b203a162S002b139a070a041b170a151a001a166a115a065a191b037'a180b149)a107'b088a013b024b057b142b208b064a102a017a012b028a154a197 b158b058b207'b116a179)a184a114b035b159b073a193a163b130 b021a202b053a177S016a01

24、Sa092a190a050b201b031b171a146b172b122b182S040b127b188b068a008a117a167b075a063a067b046b168；b157b128；b195ib165105b204a141b135a027b080a00Ca185b176b126S074a032b069b004b077b148a085is007'a003009a145b082a205b015a101b118a129a062b052b071a033a119b160a095ib051a048ib13-；b023054a196a112b103b055a100a106a091b0

25、49a026a113b134b104b066b123；b109b096M43；b099反面結果：表-6078b111b125a140a155a150a183b174b110a066a108a018b029a189b081b164b020)0047a136089a010b036S076b178S044a025b192a124b022a120b144S079a014S059a060b147'a152Ia005186b153a084b042b030S038a121a098S094b061b137b045a138a056b131b187b086it20()b143199b011b161a169

26、b194b173b206b156S034a181b198b087a132b093a072b175a097'S039Ib083088b107a149b180a037b191a065b115b166b001b151b170b041a070b139b002a162!b20-；b09(114a184b179b116b207S058a158a197a154b028b012a017b102b064b208a142a057'S024a013146a171b031s201a050a190b092b019b016b177b053b202S021b130a163a193b073；b159)a035

27、165b195a128a157a168S046a067a063b075b167a117b008b068b188a127a040a182!b122Ia17：003b007b085b148b077S004a069a032S074b126b076027a135b141a204b105023b133a048S051b095a160b119a033b071b052a062a129b118b101S015b205a082!b145ia009099弓43a096b109a123S006a104a134a113a026b049b091a106b100b055b103a112!a196

28、ib054六、模型檢驗與推廣碎紙片自動拼接是計算機視覺和模式識別的一個基本問題，圖形預處理和碎片匹配是 其中的關鍵技術。雖然我們本次實驗的仿真所涉及的碎紙片的數(shù)量及種類不多，但是它充分表明了所進行的碎紙片自動拼接復原技術研究的可行性。目前，系統(tǒng)還在進一步完善階段，主要有一下幾個問題：1）邊緣灰度值的精確提取從實驗分析可看出，邊緣灰度值的精度對減少匹配的計算量和提高匹配的準確性都非 常重要。它在很大程度上決定了紙片匹配的排序問題，有時甚至會導致某些匹配的失敗。2）數(shù)據(jù)庫的開發(fā)管理在實際應用中，由于設備等條件的限制，一次的處理往往不能解決全部的拼接問題。因此，必須開發(fā)合理的數(shù)據(jù)庫，以充分利用每一次

29、的拼接結果。3）程序優(yōu)化雖然在進行簡單的拼接復原工作時，該系統(tǒng)可以滿足要求。但是在實際的應用中，通常會涉及對大量不規(guī)則紙片或彩色碎片數(shù)據(jù)進行管理和處理工作。因此，必須繼續(xù)優(yōu)化程序結構，提高程序的交互能力，真正實現(xiàn)快速有效的計算機輔助碎紙片自動拼接復原。本文基于計算機輔助對碎紙機絞碎的碎紙片實現(xiàn)自動快速拼接，從圖形顯示技術中提 取圖形的灰度信息，并提出歐氏距離的配準方法，對圖像中的誤匹配點產(chǎn)生極大的抑制， 求解的變換矩陣精度得到提高，大大縮短了匹配時間，在現(xiàn)實應用中具有重要意義，類似 的研究可廣泛應用到文物碎片的自動修復、司法物證修復、計算機輔助設計等領域。七、參考文獻1WolfsonH , K

30、alvinA , SchonbergE, LambdanY Solvingjigsawpuzzlesbycomputer , AnnalesofOperationResearch , 1988, 12:51-642FreemanH, GarderL,Apictorialjigsawpuzzles:thecomputersolutionofaprobleminpatternrecognition,IEEE, 1964,13:118-1273 余宏生，金偉其，散字圖像拼接方法研究進展口 J ，紅外技術， 2009,31 ( 6) ： 348-3534 楊帆，數(shù)字圖像處理與分析(第 2 版) ，北京

31、：北京航空航天大學出版社，2010.8:205-2085 何曉群，應用多元統(tǒng)計分析，北京：中國統(tǒng)計出版社， 2010.6:179-1826 張文修，梁怡，遺傳算法的數(shù)學基礎，西安：西安交通大學出版社， 2000.5:13-337 方賢勇，圖像拼接技術研究D ，杭州：浙江大學計算機學院， 20058 楊翠，圖像融合與配準方法研究D ，西安：西安電子科技大學， 20089 葉耘愷，基于邊緣特征的圖像配準方法研究D ，重慶：重慶大學， 200910 蘇彥華，數(shù)字圖像識別技術典型案例，人民郵電出版社， 200411FischlerM,BollesR,Randomsampleconsensus:Apar

32、adigmformodelfittingwithapplicationtoimageanalysisandautomatedcartographyJ,CommunicationsoftheACM,19 81,24(6):381-395附錄：附件 1 的復原圖片：附件 2 的復原圖片：附件3 的復原圖片：附件4 的復原圖片：附件 5 的復原圖片：正面： 反面： 源程序如下：附件 1');files=dir('*.bmp'); fori=1:19s(:,:,i)=imread(files(i).name);end;%等所有碎片導入一個三維數(shù)組forj=1:19 n=0;fo

33、ri=1:1980ifs(i,1,j)=255 n=n+1;end;end;ifn=1980 disp(j);% 找出最左邊的碎片 break;end;end;Figure1 clearall clccell1=imread('000.bmp');cell2=imread('001.bmp');cell3=imread('002.bmp');cell4=imread('003.bmp');cell5=imread('004.bmp');cell6=imread('005.bmp');cell7=im

34、read('006.bmp');cell8=imread('007.bmp');cell9=imread('008.bmp');cell10=imread('009.bmp');cell11=imread('010.bmp');cell12=imread('011.bmp');cell13=imread('012.bmp');cell14=imread('013.bmp');cell15=imread('014.bmp');cell16=imread(

35、'015.bmp');cell17=imread('016.bmp');cell18=imread('017.bmp');cell19=imread('018.bmp');fori=1:19cell2i=im2bw(celli,0.5);endt=8forx=1:18x=sum(sqrt(cell2t(:,72)-cell2i(:,1).'*(cell2t(:,72)-cell2i(:,1);j=1;fori=1:19ifi=tcontinue;endx1=sum(sqrt(cell2t(:,72)-cell2i(:,1)

36、.'*(cell2t(:,72)-cell2i(:,1) ;ifx1<xx=x1;j=i;endendt=j;end結果t=8j=18j=1j=7j=9j=15j=13j=16j=4j=11j=3j=17j=2j=5j=6j=10j=14j=1j=7figure2IV1=imread('008.bmp');IV2=imread('014.bmp');IV3=imread('012.bmp');IV4=imread('015.bmp');IV5=imread('003.bmp');IV6=imread(

37、'010.bmp');IV7=imread('002.bmp');IV8=imread('016.bmp');IV9=imread('001.bmp');IV10=imread('004.bmp')IV11=imread('005.bmp')IV12=imread('009.bmp')IV13=imread('013.bmp')IV14=imread('018.bmp')IV15=imread('011.bmp')IV16=imread

38、('007.bmp')IV17=imread('017.bmp');IV18=imread('000.bmp');IV19=imread('006.bmp');PicData=IV1,IV2,IV3,IV4,IV5,IV6,IV7,IV8,IV9,IV10,IV11,IV12,IV13,IV14,IV15,IV16,IV17,IV18,IV19;imshow(PicData);附件 2figure1clearallclccell1=imread('000.bmp');cell2=imread('001.bm

39、p');cell3=imread('002.bmp');cell4=imread('003.bmp');cell5=imread('004.bmp');cell6=imread('005.bmp');cell7=imread('006.bmp');cell8=imread('007.bmp');cell9=imread('008.bmp');cell10=imread('009.bmp');cell11=imread('010.bmp');ce

40、ll12=imread('011.bmp');cell13=imread('012.bmp');cell14=imread('013.bmp');cell15=imread('014.bmp');cell16=imread('015.bmp');cell17=imread('016.bmp');cell18=imread('017.bmp');cell19=imread('018.bmp');fori=1:19cell2i=im2bw(celli,0.5);endt=7forx=1:18x=sum(abs(cell2t(:,72)-cell21(:,1);