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

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

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

3、2013高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編號(hào)專用頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：碎紙片的拼接復(fù)原模型摘要：本文針對(duì)碎紙片的拼接復(fù)原問(wèn)題，提出了互相關(guān)匹配模型。首先對(duì)附件圖片數(shù)值化處理并建立矩陣；然后根據(jù)圖像頁(yè)邊距特點(diǎn)定位最左邊和最右邊的碎片；按照每張碎片中的文字部分所在位置，提取同一行碎片，利用互相關(guān)函數(shù)橫向拼合。在第一問(wèn)中，附件一、二僅作橫向相關(guān)性比較即可；在第二、三問(wèn)中，需要提取同一行碎片橫向拼接，并將橫向拼合完整的碎片進(jìn)行豎向拼合，經(jīng)過(guò)人工干預(yù)得到結(jié)果。最終結(jié)果見(jiàn)附錄。關(guān)鍵詞：拼接復(fù)原；互相關(guān)；矩

4、陣；數(shù)值化；人工干預(yù)一、問(wèn)題重述在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域的破碎文件的拼接上，傳統(tǒng)的拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。尤其是當(dāng)碎片數(shù)量巨大時(shí)，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開(kāi)發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。我們需要用算法分別設(shè)計(jì)出附件1至附件5的拼接方法及拼接結(jié)果。二、模型假設(shè)1,忽略實(shí)際拼接中邊緣的整齊性；2 .不需要考慮實(shí)際拼接中破碎文件大小是否一致；3,忽略碎片邊緣的損耗，認(rèn)為拼接后是完整的圖片；4 .在模型的建立過(guò)程中重視算法與建模思想，淡化程序的編寫；5 .文字的行間距一定。三、符號(hào)說(shuō)明jk互相關(guān)系數(shù)

5、(1jk1)fj(t)相關(guān)像素?cái)?shù)組1fk(t)相關(guān)像素?cái)?shù)組2P圖像像素值矩陣Qi處理后圖像像素值矩陣amn,bmn矩陣兀素四、問(wèn)題的分析1.已知條件的分析第一，對(duì)碎片尺寸和數(shù)量的分析。附件1和附件2的圖片尺寸均為721980,碎片數(shù)量均為19;附件3、附件4和附件5的圖片尺寸均為72180,碎片數(shù)量均為1119。由于縱列有11個(gè)，像素值180,總111801980,因此，所有拼接后的圖像尺寸一致，均為。第二，對(duì)碎片邊界的分析。對(duì)于附件1、2,所有碎片上行和下行像素值為白。其中，一張碎片位于最左端，最左列像素值均為白；一張碎片位于最右端，最右列像素值均為白。對(duì)于附件3、4、5,拼接后圖像四邊像素

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

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

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

9、11255a255Pi的第一列列向量為(0a255),將i=1,2,19分別市人計(jì)算，僅當(dāng)i=15時(shí)，am1255a11255a212550,因此，最左邊碎片為014。a255然后，令fj(t)bj72fk(t)bj1,將014矩陣數(shù)據(jù)帶入fj(t)中分別計(jì)算i.k,當(dāng)取得取max時(shí)，jki-1即為相鄰碎片。同理，即可拼接整幅圖。結(jié)果見(jiàn)附錄。同理可得附件二結(jié)果。Matlab附件一拼接圖1.4.2第二問(wèn)首先，確定最左邊碎片。因?yàn)樗槠嬖诜亲筮吶杂邪走叺那闆r，例如附件4的圖，如下圖所示。（由于底色是白色與文檔背景相同，進(jìn)行了對(duì)比度降低處理。）附件因此，需要提取多組行向量，根據(jù)是否均為0確定最左碎片

10、，同理可確定最右碎片。左碎片滿足條件如下：式中，r的大小由實(shí)際圖像左邊緣白邊像素?cái)?shù)量決定。在附件3中，r取15時(shí)，滿足條件的碎片數(shù)量為11。利用同一行碎片文字垂直位置相同的特點(diǎn)，根據(jù)最左邊碎片的文字的垂直位置特點(diǎn)，確定圖像所在行。同第二問(wèn)，分別計(jì)算同一行序列的互相關(guān)系數(shù)，取最大值拼合。然而，這樣只能拼接出11個(gè)橫行碎片，用互相關(guān)函數(shù)拼接部分碎片后，最后用人工干預(yù)完成白邊部分的拼合。結(jié)果如附件所示。1.4. 3第三問(wèn)由于是兩面混合，首先忽視兩面性，認(rèn)為所有碎片是在同一平面上，進(jìn)行整體拼接，則圖像應(yīng)該為2219個(gè)碎片，在進(jìn)行最左邊和最右邊計(jì)算時(shí)會(huì)出現(xiàn)22個(gè)碎片。然后根據(jù)第二問(wèn)方法，進(jìn)行橫向碎片的拼

11、接，縱向碎片的拼接。最后進(jìn)行人工干預(yù)。由于圖像是由兩面組成的，因此兩張圖片的對(duì)稱點(diǎn)（第n列和第20-n列對(duì)稱）數(shù)字相同字母不同，例如199b在一個(gè)面的第4行、第19列，那么199a就在另一面的第4行、第1歹因此正反兩面的對(duì)應(yīng)行所在位置一致，可以人工將圖拼合完整。效果如如下，結(jié)果見(jiàn)附件。Matlab附件五拼接圖六、模型評(píng)價(jià)模型優(yōu)點(diǎn)：1、模型具有堅(jiān)實(shí)可靠的數(shù)學(xué)基礎(chǔ)，經(jīng)過(guò)實(shí)踐數(shù)據(jù)分析證明，互相關(guān)函數(shù)在本題中應(yīng)用的可行性，簡(jiǎn)化了對(duì)模型問(wèn)題的分析；2、模型能較好的優(yōu)化人工干預(yù)次數(shù)。模型缺點(diǎn)：1、附件3、4、5在拼接時(shí)沒(méi)有完全脫離人工干預(yù)；2、在實(shí)際推算中，模型會(huì)產(chǎn)生較大的運(yùn)算量；3、模型在現(xiàn)實(shí)生活中的應(yīng)

12、用有待優(yōu)化，因?yàn)楝F(xiàn)實(shí)中很少有完全規(guī)則的文字碎片參考文獻(xiàn)：1屈婉玲等編，離散數(shù)學(xué)，北京：高等教育出版社,20082同濟(jì)大學(xué)數(shù)學(xué)系編，工程數(shù)學(xué)一一線性代數(shù)同濟(jì)第五版，北京：高等教育出版社，20073（美）奧本海姆等著劉樹(shù)棠譯，信號(hào)與系統(tǒng)（第二版），北京：電子工業(yè)出版社20134張志涌等編著，精通MATLABR2011H匕京：北京航空航天大學(xué)出版社,20115（美）穆?tīng)栔?，高?huì)生，劉童娜，李聰聰譯,MATLA改用教程（第二版），北京：電子工業(yè)出版社,20106（美）莫勒（Moler,）著喻文健譯,MATLAB©計(jì)算，北京：機(jī)械工業(yè)出版社，20067（美）岡薩雷斯（）等著阮秋琦等譯，數(shù)字圖像

13、處理（MATLABS），北京：電子工業(yè)出版社，20058（美）岡薩雷斯等著阮秋琦譯，數(shù)字圖像處理的MATLA4現(xiàn)（第2版），北京：清華大學(xué)出版社,20139（美）羅森著袁崇義等譯，離散數(shù)學(xué)及其應(yīng)用，北京：機(jī)械工業(yè)出版社,2011附錄附錄一模型結(jié)果附件1結(jié)果：列數(shù)12345678910111213141516171819序號(hào)008014012015003010002016001004005009013018011007017000006附件二效果圖附件一效果圖附件2結(jié)果:列數(shù)12345678910111213141516171819序號(hào)003006002007015018011000005001

14、009013010008012014017016004附件3結(jié)果:行列1234567891011121314151617181910490540651431860020571921781181900950110221290280911881412061019078067069099162096131079063116163072006177020052036316810007606214203004102314719105017912008619502600108701840381480461610240350811891221031301930881670250080091050745071

15、156083132200017080033202198015133170205085152165027060601412800315908219913501207316020316913403903105110711517670940340841830900471210421241440771121490971361641270580438125013182109197016184110187066106150021173157181204139145902906411120100509218004803707505504420601010409817217105910007208138158

16、12606817504517400013705305609315307016603219611089146102154114040151207155140185108117004101113194119123附件4結(jié)果:行列12345678910111213141516171819119107501115419018400210418006410600414903220406503906714722011481701961980941131640781030910801010261000060170281463086051107029040158186098024117150005059058

17、092030037046127401919409314108812112610515511417618215102205720207116508251591390011290631381530530381231201750850501601870972030316020041108116136073036207135015076043199045173079161179143720802100704906111903314216806216905419213311818916219711280700840600140681741371950080471721560960230991220901

18、8510991321810950691671631661881111442060031300340131100250271781017104206620501015707414508313405501805603501600918315204411081077128200131052125140193087089048072012177124000102115附件5結(jié)果:行列123456789101112131415161718191136a047b020b164a081a189a029b018a108b066b110b174a183a150b155b140b125b111a078a2005b

19、152b147b060a059b014b079b144b120a022b124a192b025a044b178b076a036b010a089b3143a200a086a187a131a056a138b045b137a061a094a098b121b038b030b042a084a153b186a4083b039a097b175b072a093b132a087b198a181a034b156b206a173a194a169a161b011a199a5090b203a162a002b139a070a041b170a151a001a166a115a065a191b037a180b149a107b0

20、88a6013b024b057b142b208b064a102a017a012b028a154a197b158b058b207b116a179a184a114b7035b159b073a193a163b130b021a202b053a177a015a019a092a190a050b201b031b171a146b8172b122b182a040b127b188b068a008a117a167b075a063a067b046b168b157b128b195b165a9105b204a141b135a027b080a000a185b176b126a074a032b069b004b077b148a0

21、85a007a003a10009a145b082a205b015a101b118a129a062b052b071a033a119b160a095b051a048b133b023a11054b196a112b103b055a100a106a091b049a026a113b134b104b006b123b109b096a043b099b行列123456789101112131415161718191078b111b125a140a155a150a183b174b110a066a108a018b029a189b081b164b020a047a136b2089a010b036a076b178a044a

22、025b192a124b022a120b144a079a014a059a060b147a152a005a3186b153a084b042b030a038a121a098a094b061b137b045a138a056b131b187b086b200b143b4199b011b161a169b194b173b206b156a034a181b198b087a132b093a072b175a097a039b083a5088b107a149b180a037b191a065b115b166b001b151b170b041a070b139b002a162b203b090a6114a184b179b116b

23、207a058a158a197a154b028b012a017b102b064b208a142a057a024a013a7146a171b031a201a050a190b092b019b015b177b053b202a021b130a163a193b073b159a035a8165b195a128a157a168a046a067a063b075b167a117b008b068b188a127a040a182b122a172a9003b007b085b148b077a004a069a032a074b126b176a185a000b080b027a135b141a204b105a10023b133

24、a048a051b095a160b119a033b071b052a062a129b118b101a015b205a082b145a009b11099a043a096b109a123a006a104a134a113a026b049b091a106b100b055b103a112a196b054a附錄三效果圖附錄四效果圖附錄五效果圖1附錄五效果圖2附錄二部分源程序(由于源程序篇幅過(guò)長(zhǎng)，打印不便，因此只附上部分程序)使用軟件:MatlabI000=imread('')I001=imread('')I002=imread('')I003=imread(&

25、#39;')I004=imread('')I005=imread('')I006=imread('')I007=imread('')I008=imread('')I009=imread('')I010=imread('')I011=imread('')I012=imread('')I013=imread('')I014=imread('')I015=imread('')I016=imread(&#

26、39;')I017=imread('')I018=imread('')P=I000,I001,I002,I003,I004,I005,I006,I007,I008,I009,I010,I011,I012,I013,I014,I015,I016,I017,I018%最左計(jì)算函數(shù)functionF=borderright(x)forj=1:1:19y(j)=0fori=1:1:1980if(x(i,72*(j-1)+1)=255)y(j)=y(j)+0elsey(j)=y(j)+1endendif(y(j)=0)F=jendendendfunctiond=s

27、plit(x,y,m)maxx=0,0forj=1:1:19z(j)=0if(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(1

28、3)+1)&&(j=(m(14)+1)&&(j=(m(15)+1)&&(j=(m(16)+1)&&(j=(m(17)+1)&&(j=(m(18)+1)&&(j=(m(19)+1)fori=1:1:1980if(x(i,72*y)<255)&&(x(i,72*(j-1)+1)<255)z(j)=z(j)+1elsez(j)=z(j)+0endendelsez(j)=0endif(z(j)>maxx(1)maxx=z(j),jendendd=maxx(2)endfunc

29、tiontwo(x,a,b)fori=1:1:aforj=1:1:bif(x(i,j)<255)x(i,j)=0endendendf3=0f4=0f5=0f3=double(f3)f4=double(f4)f5=double(f5)p=0bai=0HENG=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,-1145,-1159,-1171,-1191,-1201,-1fork=1:1:11a=HENG(k,1)fori=2:1:19forb=1:1:208f3=0f4=0f5=0forc=1:1:180f1=Q(c+a*180,72)f2=Q(c+b*180,1)f3=f3+Q(c+a*180,72)*Q(c+b*180,1)f4=f4+f1*f1f5=f5+f2*f2endr(b)=f3/sqrt(f4*f5)ifr(b)>pP=r(b)h=bendr(b)=0endp=0HENG(k,i)=ha=hforc=1:1:180bai=bai+Q(c+a*180,72)endif(bai=22950)&&(i=19)msgbox(aTa2'endif(bai=22950)&&(i<19)msgbox(1t1t£?e?1O?e?O°)/breakendbai=0endendf3=0f4=0f5=0f3=double(f3)f4=double(f4)f5=doub