數(shù)學(xué)建模碎紙片的拼接復(fù)原模型

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

2、規(guī)則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國大學(xué)生數(shù)學(xué)建模競賽組委會，可將我們的論文以任何形式進(jìn)行公開展示（包括進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等）。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）： B 我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜?參賽隊員 (打印并簽名) ：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： （論文紙質(zhì)版與電子版中的以上信息必須一致，只是電子版中無需簽名。以上內(nèi)容請仔細(xì)核對，提交后將不再允許做任何修改。如填寫錯誤，論文可能被取消評獎資格。） 日期： 2013 年 9 月 10 日賽

3、區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進(jìn)行編號）：碎紙片的拼接復(fù)原模型摘 要： 本文針對碎紙片的拼接復(fù)原問題，提出了互相關(guān)匹配模型。首先對附件圖片數(shù)值化處理并建立矩陣；然后根據(jù)圖像頁邊距特點(diǎn)定位最左邊和最右邊的碎片；按照每張碎片中的文字部分所在位置，提取同一行碎片，利用互相關(guān)函數(shù)橫向拼合。在第一問中，附件一、二僅作橫向相關(guān)性比較即可；在第二、三問中，需要提取同一行碎片

4、橫向拼接，并將橫向拼合完整的碎片進(jìn)行豎向拼合，經(jīng)過人工干預(yù)得到結(jié)果。最終結(jié)果見附錄。 關(guān)鍵詞：拼接復(fù)原；互相關(guān)；矩陣；數(shù)值化；人工干預(yù) 一、問題重述在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報獲取等領(lǐng)域的破碎文件的拼接上，傳統(tǒng)的拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。尤其是當(dāng)碎片數(shù)量巨大時，人工拼接很難在短時間內(nèi)完成任務(wù)。隨著計算機(jī)技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。我們需要用算法分別設(shè)計出附件1至附件5的拼接方法及拼接結(jié)果。二、模型假設(shè)1. 忽略實際拼接中邊緣的整齊性；2. 不需要考慮實際拼接中破碎文件大小是否一致；3. 忽略碎片邊緣的損耗，認(rèn)為拼接后是完

5、整的圖片；4. 在模型的建立過程中重視算法與建模思想，淡化程序的編寫；5. 文字的行間距一定。三、符號說明 互相關(guān)系數(shù)（） 相關(guān)像素數(shù)組1 相關(guān)像素數(shù)組2 圖像像素值矩陣 處理后圖像像素值矩陣 矩陣元素四、問題的分析1. 已知條件的分析第一，對碎片尺寸和數(shù)量的分析。附件1和附件2的圖片尺寸均為，碎片數(shù)量均為19；附件3、附件4和附件5的圖片尺寸均為，碎片數(shù)量均為。由于縱列有11個，像素值180，總值，因此，所有拼接后的圖像尺寸一致，均為。第二，對碎片邊界的分析。對于附件1、2，所有碎片上行和下行像素值為白。其中，一張碎片位于最左端，最左列像素值均為白；一張碎片位于最右端，最右列像素值均為白。對

6、于附件3、4、5，拼接后圖像四邊像素值為白，碎片也存在邊像素值全為白的情況，因此需要分類討論。切割線為長度完全相等的直線，因此切割線兩邊應(yīng)有很大的相似度，灰度值相似。第三，對碎片正反性的分析。附件5存在正反面情況，同一塊用a、b，但根據(jù)題意分析，我們無法確定碎片的正反，即a可能是正面，也可能是反面。因此拼合時，應(yīng)當(dāng)注意統(tǒng)一序號在同一平面出現(xiàn)的單一性，例如，000a在設(shè)定正面出現(xiàn)以后，000b一定在反面。第四，對碎片像素白色行的分析對于中文，同一行的所有碎片文字是橫向?qū)R的，因此白色開始的位置是一樣的。因此可以提取出同一行的碎片。2. 拼接方法的分析由于碎片是長方形，有四條邊，因此邊的拼接有優(yōu)先

7、順序。由于長邊特征較為明顯，采樣點(diǎn)多，因此優(yōu)先橫向拼接，然后縱向拼接。當(dāng)電腦拼接無法完成時，采取人工干預(yù)。五、模型的分析與求解1. 方法的確立根據(jù)對問題的分析，我們得知此問題需要計算離散序列之間的相關(guān)性，因此我們需要使用互相關(guān)系數(shù)計算和矩陣的計算。2. 模型的建立1. 1圖像數(shù)字化由于電腦中圖像的大小是由像素數(shù)量表示，而每個像素點(diǎn)均由一個數(shù)值表示，因此利用matlab讀取灰度圖像的像素值，第n副圖用矩陣表示為：在第一問中，n=72，m=1980；在第二問、第三問中，n=72，m=180。1. 2數(shù)據(jù)預(yù)處理由于互相關(guān)函數(shù)需要比較正負(fù)范圍相等的數(shù)組，因此我們將的每個數(shù)值減去，使在 -，范圍內(nèi)，即1

8、. 3相關(guān)性的計算由于碎片大小完全一致，切割線完全豎直且交界處長度完全相等，并且切割線無損，圖像可以完全拼接，因此相鄰兩個圖形交接處相似。由于圖像已經(jīng)數(shù)字化處理，因此可以由邊界相應(yīng)像素數(shù)值的相關(guān)性來確定兩張圖是否相鄰。對于相關(guān)性的計算，我們使用互相關(guān)函數(shù)。互相關(guān)函數(shù)公式為：公式中，分子表示的是兩組離散數(shù)值的相似程度，分母則起到歸一化作用，相鄰兩邊的數(shù)組分別為序列。當(dāng)時，兩組數(shù)相似程度最大，即兩張圖片最有可能相鄰；當(dāng)時，兩組數(shù)相似程度最小，即兩張圖片不相鄰。根據(jù)這個公式，即可算出兩個圖邊緣的相關(guān)度。1. 4圖像的拼接1. 4. 1 第一問附件一：首先，根據(jù)圖像頁邊距白邊特點(diǎn)定位最左邊為白色的碎片

9、，的第一列列向量為，將i=1,2，19分別帶入計算，僅當(dāng)i=15時，因此，最左邊碎片為014。然后，令，將014矩陣數(shù)據(jù)帶入中分別計算，當(dāng)取得取時，i-1即為相鄰碎片。同理，即可拼接整幅圖。結(jié)果見附錄。同理可得附件二結(jié)果。Matlab 附件一 拼接圖1. 4. 2 第二問首先，確定最左邊碎片。因為碎片存在非左邊仍有白邊的情況，例如附件4的圖，如下圖所示。（由于底色是白色與文檔背景相同，進(jìn)行了對比度降低處理。）附件因此，需要提取多組行向量，根據(jù)是否均為0確定最左碎片，同理可確定最右碎片。左碎片滿足條件如下：式中，r的大小由實際圖像左邊緣白邊像素數(shù)量決定。在附件3中，r取15時，滿足條件的碎片數(shù)量

10、為11。利用同一行碎片文字垂直位置相同的特點(diǎn)，根據(jù)最左邊碎片的文字的垂直位置特點(diǎn)，確定圖像所在行。同第二問，分別計算同一行序列的互相關(guān)系數(shù)，取最大值拼合。然而，這樣只能拼接出11個橫行碎片，用互相關(guān)函數(shù)拼接部分碎片后，最后用人工干預(yù)完成白邊部分的拼合。結(jié)果如附件所示。1. 4. 3 第三問由于是兩面混合，首先忽視兩面性，認(rèn)為所有碎片是在同一平面上，進(jìn)行整體拼接，則圖像應(yīng)該為個碎片，在進(jìn)行最左邊和最右邊計算時會出現(xiàn)22個碎片。然后根據(jù)第二問方法，進(jìn)行橫向碎片的拼接，縱向碎片的拼接。最后進(jìn)行人工干預(yù)。由于圖像是由兩面組成的，因此兩張圖片的對稱點(diǎn)（第n列和第20-n列對稱）數(shù)字相同字母不同，例如19

11、9b在一個面的第4行、第19列，那么199a就在另一面的第4行、第1列。因此正反兩面的對應(yīng)行所在位置一致，可以人工將圖拼合完整。效果如如下，結(jié)果見附件。Matlab 附件五 拼接圖六、模型評價模型優(yōu)點(diǎn)：1、模型具有堅實可靠的數(shù)學(xué)基礎(chǔ)，經(jīng)過實踐數(shù)據(jù)分析證明，互相關(guān)函數(shù)在本題中應(yīng)用的可行性，簡化了對模型問題的分析；2、模型能較好的優(yōu)化人工干預(yù)次數(shù)。模型缺點(diǎn)：1、附件3、4、5在拼接時沒有完全脫離人工干預(yù)；2、在實際推算中，模型會產(chǎn)生較大的運(yùn)算量；3、模型在現(xiàn)實生活中的應(yīng)用有待優(yōu)化，因為現(xiàn)實中很少有完全規(guī)則的文字碎片。參考文獻(xiàn)：1屈婉玲等編,離散數(shù)學(xué),北京：高等教育出版社 ,20082同濟(jì)大學(xué)數(shù)學(xué)系

12、編，工程數(shù)學(xué)線性代數(shù) 同濟(jì)第五版,北京：高等教育出版社 ，20073(美)奧本海姆等著 劉樹棠譯,信號與系統(tǒng)（第二版）,北京：電子工業(yè)出版社 20134張志涌等編著,精通MATLAB R2011a,北京：北京航空航天大學(xué)出版社 ,20115(美)穆爾 著，高會生，劉童娜，李聰聰 譯,MATLAB實用教程（第二版）,北京：電子工業(yè)出版社 ,20106(美)莫勒（Moler,）著 喻文健譯,MATLAB數(shù)值計算,北京：機(jī)械工業(yè)出版社,20067(美)岡薩雷斯（）等著 阮秋琦等譯,數(shù)字圖像處理（MATLAB版）,北京：電子工業(yè)出版社 ,20058(美)岡薩雷斯等著 阮秋琦譯,數(shù)字圖像處理的MATLA

13、B實現(xiàn)（第2版）,北京：清華大學(xué)出版社 ,20139(美)羅森著 袁崇義等譯,離散數(shù)學(xué)及其應(yīng)用,北京：機(jī)械工業(yè)出版社 ,2011附錄附錄一 模型結(jié)果附件1結(jié)果：列數(shù)12345678910111213141516171819序號008014012015003010002016001004005009013018011007017000006附件一效果圖 附件二效果圖附件2結(jié)果：列數(shù)12345678910111213141516171819序號003006002007015018011000005001009013010008012014017016004附件3結(jié)果：行列1234567891011

14、121314151617181910490540651431860020571921781181900950110221290280911881412061019078067069099162096131079063116163072006177020052036316810007606214203004102314719105017912008619502600108701840381480461610240350811891221031301930881670250080091050745071156083132200017080033202198015133170205085152165

15、027060601412800315908219913501207316020316913403903105110711517670940340841830900471210421241440771121490971361641270580438125013182109197016184110187066106150021173157181204139145902906411120100509218004803707505504420601010409817217105910007208138158126068175045174000137053056093153070166032196110

16、89146102154114040151207155140185108117004101113194119123附件4結(jié)果：行列12345678910111213141516171819119107501115419018400210418006410600414903220406503906714722011481701961980941131640781030910801010261000060170281463086051107029040158186098024117150005059058092030037046127401919409314108812112610515511417

17、618215102205720207116508251591390011290631381530530381231201750850501601870972030316020041108116136073036207135015076043199045173079161179143720802100704906111903314216806216905419213311818916219711280700840600140681741371950080471721560960230991220901851099132181095069167163166188111144206003130034

18、0131100250271781017104206620501015707414508313405501805603501600918315204411081077128200131052125140193087089048072012177124000102115附件5結(jié)果：行列123456789101112131415161718191136a047b020b164a081a189a029b018a108b066b110b174a183a150b155b140b125b111a078a2005b152b147b060a059b014b079b144b120a022b124a192b025a

19、044b178b076a036b010a089b3143a200a086a187a131a056a138b045b137a061a094a098b121b038b030b042a084a153b186a4083b039a097b175b072a093b132a087b198a181a034b156b206a173a194a169a161b011a199a5090b203a162a002b139a070a041b170a151a001a166a115a065a191b037a180b149a107b088a6013b024b057b142b208b064a102a017a012b028a154a

20、197b158b058b207b116a179a184a114b7035b159b073a193a163b130b021a202b053a177a015a019a092a190a050b201b031b171a146b8172b122b182a040b127b188b068a008a117a167b075a063a067b046b168b157b128b195b165a9105b204a141b135a027b080a000a185b176b126a074a032b069b004b077b148a085a007a003a10009a145b082a205b015a101b118a129a062

21、b052b071a033a119b160a095b051a048b133b023a11054b196a112b103b055a100a106a091b049a026a113b134b104b006b123b109b096a043b099b行列123456789101112131415161718191078b111b125a140a155a150a183b174b110a066a108a018b029a189b081b164b020a047a136b2089a010b036a076b178a044a025b192a124b022a120b144a079a014a059a060b147a152a

22、005a3186b153a084b042b030a038a121a098a094b061b137b045a138a056b131b187b086b200b143b4199b011b161a169b194b173b206b156a034a181b198b087a132b093a072b175a097a039b083a5088b107a149b180a037b191a065b115b166b001b151b170b041a070b139b002a162b203b090a6114a184b179b116b207a058a158a197a154b028b012a017b102b064b208a142a

23、057a024a013a7146a171b031a201a050a190b092b019b015b177b053b202a021b130a163a193b073b159a035a8165b195a128a157a168a046a067a063b075b167a117b008b068b188a127a040a182b122a172a9003b007b085b148b077a004a069a032a074b126b176a185a000b080b027a135b141a204b105a10023b133a048a051b095a160b119a033b071b052a062a129b118b101

24、a015b205a082b145a009b11099a043a096b109a123a006a104a134a113a026b049b091a106b100b055b103a112a196b054a附錄三效果圖 附錄四效果圖附錄五效果圖1 附錄五效果圖2附錄二 部分源程序（由于源程序篇幅過長，打印不便，因此只附上部分程序）使用軟件:MatlabI000=imread('')I001=imread('')I002=imread('')I003=imread('')I004=imread('')I005=imread(

25、'')I006=imread('')I007=imread('')I008=imread('')I009=imread('')I010=imread('')I011=imread('')I012=imread('')I013=imread('')I014=imread('')I015=imread('')I016=imread('')I017=imread('')I018=imread(&

26、#39;')P=I000,I001,I002,I003,I004,I005,I006,I007,I008,I009,I010,I011,I012,I013,I014,I015,I016,I017,I018% 最左計算函數(shù)function F=borderright(x)for j=1:1:19 y(j)=0 for i=1:1:1980 if(x(i,72*(j-1)+1)=255) y(j)=y(j)+0 else y(j)=y(j)+1 end end if(y(j)=0) F=j endendendfunction d=split(x,y,m)maxx=0,0for j=1:1:

27、19 z(j)=0 if(j=(m(1)+1)&&(j=(m(2)+1)&&(j=(m(3)+1)&&(j=(m(4)+1)&&(j=(m(5)+1)&&(j=(m(6)+1)&&(j=(m(7)+1)&&(j=(m(8)+1)&&(j=(m(9)+1)&&(j=(m(10)+1)&&(j=(m(11)+1)&&(j=(m(12)+1)&&(j=(m(13)+1)&&(j=(m(14)+1

28、)&&(j=(m(15)+1)&&(j=(m(16)+1)&&(j=(m(17)+1)&&(j=(m(18)+1)&&(j=(m(19)+1) for i=1:1:1980 if(x(i,72*y)<255)&&(x(i,72*(j-1)+1)<255) z(j)=z(j)+1 else z(j)=z(j)+0 end end else z(j)=0 end if(z(j)>maxx(1) maxx=z(j),j endendd=maxx(2)endfunction two(x,a

29、,b)for i=1:1:a for j=1:1:b if(x(i,j)<255) x(i,j)=0 end endendf3=0f4=0f5=0f3=double(f3)f4=double(f4)f5=double(f5)p=0bai=0 HENG=19,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 20,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 70,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-

30、1; 81,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 86,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 132,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 145,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 159,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 171,

31、-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 191,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 201,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1;for k=1:1:11 a=HENG(k,1)for i=2:1:19for b=1:1:208 f3=0 f4=0 f5=0 for c=1:1:180 f1=Q(c+a*180,72) f2=Q(c+b*180,1) f3=f3+Q(c+a*180,

32、72)*Q(c+b*180,1) f4=f4+f1*f1 f5=f5+f2*f2 end r(b)=f3/sqrt(f4*f5) if r(b)>p p=r(b) h=b end r(b)=0endp=0HENG(k,i)=ha=hfor c=1:1:180 bai=bai+Q(c+a*180,72)endif (bai=22950)&&(i=19)msgbox('àTà2')endif (bai=22950)&&(i<19)msgbox('1t1t?è?1¤?é?¤°é') breakendbai=0endend f3=0f4=0f5=0f3=double(f3)f4=double(f4)f5=double(f5)p=0bai=0% 初始化數(shù)組