碎紙片的拼接復(fù)原分析模型

1、碎紙片拼接復(fù)原的設(shè)計(jì)與實(shí)現(xiàn)摘要 破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。由于人工拼接效率較低，我們利用MATLAB軟件編寫程序，實(shí)現(xiàn)碎紙片拼接技術(shù)的計(jì)算機(jī)化，實(shí)現(xiàn)批量拼接，以節(jié)省人力和時(shí)間。（一）為尋找最吻合拼接方案，利用MATLAB軟件中的imread函數(shù)，實(shí)現(xiàn)了碎紙片與矩陣之間的形式轉(zhuǎn)化以便于碎紙圖片的拼接比對(duì)。數(shù)值0至255表示圖中某一像素點(diǎn)由黑到白的變化程度。再根據(jù)紙張的邊界留白較多，通過計(jì)算每個(gè)矩陣第一列中各向量的元素和，可將所得和數(shù)值最大的列向量所在矩陣對(duì)應(yīng)的碎紙片確定為左邊界。經(jīng)計(jì)算知：008圖為整體圖片的左邊界。根據(jù)使吻合參數(shù)最小的原則

2、，可計(jì)算出下一張圖片。重復(fù)此步驟，以此類推，每次都挑選出剩余圖片中與前一幅圖片吻合參數(shù)最小的作為與之相連接的碎紙圖片。最后可得到附件1的答案矩陣為：008014012015003010002016001004005009013018011007017000006附件2與附件1的模型求解方法相同，最后得到：附件2的答案矩陣為：003006002007015018011000005001009013010008012014017016004（二）由于每片獨(dú)立的拼接無法達(dá)到最佳效果。故我們以縮小比對(duì)范圍的形式來進(jìn)行優(yōu)化。附件3類比于問題一，用相同的方法找到所有碎紙片的左邊界，共11張，分別04906

3、1168038071014094125029007089根據(jù)行特征篩選出每行的碎紙圖片以保證全部圖片均得到分類。此時(shí)選取數(shù)量最少一行作為入手點(diǎn)，利用MATLAB軟件進(jìn)行圖片拼接。但由于碎紙圖片的行特征值有誤差，故圖片大塊拼接正確，但與實(shí)際情況有細(xì)微差別。通過簡單的人工檢測得到準(zhǔn)確行的排列順序，由于行信息充足，借用第一問最終達(dá)到正確拼接效果。結(jié)果矩陣如 表12 所示。第二種情況的關(guān)鍵點(diǎn)是找出準(zhǔn)確的行特征，由于漢字與英文書寫格式不同，漢字均為方塊字，易于定位。而英文由于特殊的書寫方式，上下位置不同，不易于找到行特征值。如：英文字母最為密集行中點(diǎn)位置。需將附件4圖片對(duì)應(yīng)的矩陣轉(zhuǎn)化為0-1列向量（空白

4、行為0，反之則為1）。利用此方法篩選出位于同一行的碎紙片并進(jìn)行紙片拼接。后續(xù)拼接方法同附件3。結(jié)果矩陣如 表13 所示。（三）結(jié)合雙面信息處理邊界，得到邊界特點(diǎn)。根據(jù)元音字母中心位置得出行高，從而更準(zhǔn)確篩選同行圖片。雙面信息同時(shí)校準(zhǔn)，更容易得到拼接順序，人工干預(yù)少。結(jié)果矩陣如 表5 所示。模型一簡單易處理，適用于含大量信息的碎紙片拼接且準(zhǔn)確度高；模型二針對(duì)文字內(nèi)容的中英文差異分別利用吻合參數(shù)和行高作為標(biāo)準(zhǔn)來篩選圖片；模型三深入生活實(shí)際，考慮日常生活中反正面印刷情況并結(jié)合英文印刷特點(diǎn)，實(shí)用性高，雙面信息同時(shí)校準(zhǔn)，人工干預(yù)少。關(guān)鍵字：碎紙拼接 MATLAB 吻合參數(shù) 灰度一、問題重述破碎文件的拼接

5、在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們試圖開發(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ì)碎紙

6、片拼接復(fù)原模型和算法，并針對(duì)附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請(qǐng)寫出干預(yù)方式及干預(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ù)，每頁紙被切為11

7、19個(gè)碎片。(4) 附件5為縱橫切碎片數(shù)據(jù)，每頁紙被切為1119個(gè)碎片，每個(gè)碎片有正反兩面。該附件中每一碎片對(duì)應(yīng)兩個(gè)文件，共有21119個(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è)1、 每張碎紙片的形狀都是完全相同的長方形且每張碎紙片形狀規(guī)則

8、；2、 文字打印清晰，無缺墨斷墨情況；3、 紙片邊緣整齊，無重疊，無損耗；4、 掃描過程中每張碎紙片的位置都是完全平行的，不會(huì)出現(xiàn)傾斜的情況；5、 假設(shè)恰好能完全拼接，即碎片無缺失，也沒有其他碎片混雜；6、 紙片無倒轉(zhuǎn)；7、 碎片文字均為相同字號(hào)，字號(hào)大小適中；8、 文字印刷體行高、行間距相同；9、 頁邊距非0，但較小。三、字符說明1、表示第張圖片所轉(zhuǎn)化得到的矩陣；2、表示第個(gè)圖所形成的矩陣的第行列對(duì)應(yīng)灰度值；3、表示第個(gè)圖所形成的矩陣的第列；4、表示第個(gè)圖和第個(gè)圖之間的吻合參數(shù)（其含義在模型分析中說明），其中兩張圖的吻合參數(shù)越低表示這兩張圖越吻合；5、表示圖的0-1列向量四、模型分析本文針對(duì)

9、三種碎片拼接類型分別建立數(shù)學(xué)模型。模型一簡單易處理，適用于單片含大量信息的碎紙片拼接且準(zhǔn)確度高；模型二針對(duì)文字內(nèi)容的中英文差異分別利用吻合參數(shù)和行高作為標(biāo)準(zhǔn)來篩選圖片，且以縮小比對(duì)范圍的形式應(yīng)用于龐大數(shù)據(jù)量的整理進(jìn)而進(jìn)行碎片拼接復(fù)原；模型三深入生活實(shí)際，考慮日常生活中反正面印刷情況并結(jié)合英文印刷特點(diǎn)，實(shí)用性高，準(zhǔn)確度大。問題一： 利用MATLAB程序中的imread函數(shù)將附件1的19張碎紙片分別轉(zhuǎn)化成矩陣形式，每一張碎紙片都可轉(zhuǎn)化為一個(gè)的矩陣。for循環(huán)的使用可以很大程度上節(jié)省時(shí)間、人力，再根據(jù)邊界準(zhǔn)則通過計(jì)算首列數(shù)字變化來確定其邊界。最后根據(jù)吻合參數(shù)的大小確定最后的碎紙片拼接順序。求解步驟如

10、下：確定最后整體圖片的左邊界將碎紙片轉(zhuǎn)換為數(shù)字矩陣求出其他圖片與左邊界圖片的吻合系數(shù)比較所有吻合系數(shù)，系數(shù)最小所對(duì)應(yīng)的圖片為第二張圖片重復(fù)步驟3，求出其他矩陣與第二張圖片的吻合系數(shù)，吻合系數(shù)最小的為第三張圖片依照上述方法，求得最后所有圖片的拼接順序完成拼接效果圖（圖1：問題一求解思路圖）問題二：同樣利用第一問中求得圖片左邊界的方法，附件3、附件4中兩幅圖片的左邊界。找出與左邊界11張圖片同行的其余碎紙圖片。編程篩選出每行的圖片，利用問題一中的方法進(jìn)行計(jì)算機(jī)拼接，但由于拼接存在一定的誤差，所以部分圖片拼接不完整正確，在此情況之下進(jìn)行人工干預(yù)，觀察圖片內(nèi)容，根據(jù)內(nèi)容手動(dòng)移動(dòng)碎紙圖片進(jìn)行拼接。求解步

11、驟如下：找到與每幅邊界圖片同行的剩余圖片找出左邊界中的圖片（共11張）選取所有行中圖片數(shù)量最少的一行進(jìn)行圖片拼接，若拼接不準(zhǔn)確則引入人工干預(yù)確定第行的圖片拼接順序，并在其他行刪除在第行中出現(xiàn)的圖片在剩余行中重復(fù)步驟3和步驟4，直至所有行圖片拼接結(jié)束將每行看做整體，進(jìn)而完成完成拼接效果圖將碎紙片轉(zhuǎn)化為數(shù)字矩陣（圖2：問題二求解思路圖）問題三：對(duì)于有雙面打印的碎紙片，根據(jù)邊緣留白情況，可篩選出22個(gè)左邊界，并根據(jù)字母中點(diǎn)所在行的行高分為11類。并根據(jù)行高對(duì)其他圖片進(jìn)行篩選分類。引入人工干預(yù)，完成效果拼接。求解步驟如下：找出左邊界中的圖片（共22張）將邊界圖片進(jìn)行分類，共分為11類由所在行的兩張邊界

12、圖片篩選出所在行的其他碎紙圖片將每行碎紙圖片利用程序進(jìn)行計(jì)算機(jī)拼接，拼接不完全，引入大量人工干預(yù)完成拼接效果圖將碎紙片轉(zhuǎn)化為數(shù)字矩陣同時(shí)考慮正反兩面。加大拼接的正確性（圖3：問題三求解思路圖）五、模型建立與求解5.1附件1中碎紙片拼接圖片是否能拼接，重點(diǎn)要看邊緣的吻合程度，于是我們首先給出定義：表示第個(gè)圖所形成的矩陣的第行列對(duì)應(yīng)灰度值，則第個(gè)圖與第個(gè)圖所分別形成矩陣的第行列的差的絕對(duì)值，即記為第個(gè)圖與第個(gè)圖在邊緣點(diǎn)的吻合參數(shù)，其中兩張圖在該點(diǎn)的吻合參數(shù)越低表示這兩張圖該點(diǎn)越吻合。對(duì)于兩圖邊緣列，則有，為邊緣的吻合參數(shù)，其中兩張圖邊緣的吻合參數(shù)越低表示這兩張圖越吻合；故，我們用作為全局的吻合參數(shù)

13、，其中的限定條件為具體求解過程如下：1）為將19張碎紙片拼湊成一幅完整圖片，需對(duì)由每一張碎紙片轉(zhuǎn)化得到的數(shù)字矩陣進(jìn)行處理。其中000圖轉(zhuǎn)化為矩陣,001圖轉(zhuǎn)化為矩陣， ，018圖轉(zhuǎn)化為矩陣。（見數(shù)據(jù)表1）2）第個(gè)圖所形成的矩陣的第1列就是第個(gè)圖的左邊界，第72列表示第個(gè)圖的右邊界，列中數(shù)字的變化表示圖邊緣文字的灰度變化?；叶仁侵负诎讏D像中點(diǎn)的顏色深度，范圍一般從0到255。白色為255，黑色為0。將每個(gè)矩陣首列向量的每個(gè)元素相加求和，因?yàn)橥暾麍D片的左右邊界均為空白，故求和數(shù)值越大代表空白越多，通過計(jì)算找出19個(gè)矩陣中，首列數(shù)字無變化的（即首列向量和最大的）矩陣為由008圖所形成矩陣。則可確定0

14、08圖為最后完整圖的左邊界。3）再利用for循環(huán)語句將矩陣的最后一個(gè)列向量與另外每個(gè)矩陣的第一個(gè)列向量元素對(duì)應(yīng)相減，會(huì)得到由每個(gè)元素差值組成的新向量。再將得到的新向量中的每個(gè)元素的絕對(duì)值相加求和得到一個(gè)數(shù)值。不妨將此求和所得數(shù)值稱為兩向量的吻合參數(shù)，記為。4）吻合參數(shù)最小的矩陣所對(duì)應(yīng)的碎紙片即為第二張。從而我們得到數(shù)學(xué)模型：第二個(gè)圖為：達(dá)到該最小值時(shí)所對(duì)應(yīng)的矩陣為第個(gè)矩陣，我們用表示為所選出的第個(gè)矩陣的標(biāo)碼，以便后續(xù)求解；5）依據(jù)第二張碎紙片所對(duì)應(yīng)矩陣的最后一列與其他矩陣第一列對(duì)應(yīng)元素相減，再絕對(duì)值求和進(jìn)行吻合參數(shù)的比較，從而第三個(gè)圖為：達(dá)到該最小值時(shí)所對(duì)應(yīng)的矩陣為第個(gè)矩陣，我們用表示為所選出

15、的第個(gè)矩陣的標(biāo)碼，以便后續(xù)求解；以此類推:排序后的第個(gè)圖為：，達(dá)到該最小值時(shí)所對(duì)應(yīng)的矩陣為第個(gè)矩陣，我們用表示為所選出的第個(gè)矩陣的標(biāo)碼；6）以此類推，第18個(gè)圖為：，達(dá)到該最小值時(shí)所對(duì)應(yīng)的矩陣為第個(gè)矩陣，對(duì)應(yīng)第個(gè)圖為排序后第18個(gè)圖，剩余的一個(gè)自然為最后一圖即圖片右邊界。通過實(shí)際拼接實(shí)踐，我們可以知道，局部拼接復(fù)原結(jié)果即全局最優(yōu)拼接復(fù)原結(jié)果。最后我們得到附件1的拼接順序：表1：008014012015003010002016001004005009013018011007017000006（復(fù)原圖片見附錄1.1）5.2附件2中碎紙片拼接附件2的處理辦法與附件1相同，利用所有矩陣的第一列先找到所

16、有碎紙片中的左邊界，再根據(jù)吻合參數(shù)確定碎紙片的拼接順序。最后我們得到附件2的拼接順序：表2：003006002007015018011000005001009013010008012014017016004（復(fù)原圖片見附錄1.2）由于附件1和附件2中碎紙片的行高較高，所以在吻合參數(shù)的計(jì)算過程中相對(duì)誤差很小，利用在MATLAB軟件中編寫的程序即可求出附件1和附件2所有碎紙片的正確拼接順序，故在此問中不涉及人工干預(yù)。5.3附件3中碎紙片拼接1）利用第一問在MATLAB中編寫程序求出位于左邊界的圖片的思想，運(yùn)行程序可以找到附件3中位于第一列中的圖片共有11張，分別為049圖，061圖，168圖，03

17、8圖，071圖，014圖，094圖，125圖，029圖，007圖，089圖。恰好符合矩陣的格式要求。即說明這11張圖片為整體圖片第一列的所有組成部分。2）用MATLAB編寫循環(huán)語句，以已經(jīng)確定的第一列的11張圖片為標(biāo)準(zhǔn)分為11類，分別找出與第一列11個(gè)圖空白行位置相近似的圖片歸為一類（此時(shí)可認(rèn)為同一類中圖片的文字行是對(duì)齊的，即同類圖片理論上應(yīng)處在相同水平位置）與圖007（標(biāo)號(hào)為8）空白位置相近的圖片有22個(gè)，編號(hào)為 8115334654576971729094127138139154159167175176197209與圖014（標(biāo)號(hào)為15）空白位置相近的圖片有57個(gè)，編號(hào)為 15459101

18、3262832334041526171747583869094102103106108109114115116118120124126129135136141147152153154155156160161166167170171177186195197200204206208與圖029（標(biāo)號(hào)為30）空白位置相近的圖片有35個(gè)，編號(hào)為 30611172238454956606567769399105107110111112140146151158172173174181182185188198202205207與圖038（標(biāo)號(hào)為39）空白位置相近的圖片有22個(gè)，編號(hào)為3991015252636

19、477275828990104106123131149162168190194與圖049（標(biāo)號(hào)為50）空白位置相近的圖片有35個(gè)，編號(hào)為 5031217222329555866679296107110111119130140142144146151158174179182185187188189191193198205與圖061（標(biāo)號(hào)為62）空白位置相近的圖片有22個(gè)，編號(hào)為 6271520213753646870727379809097100117132163164178與圖071（標(biāo)號(hào)為72）空白位置相近的圖片編號(hào)有47個(gè)7291016171822262833345761677175818

20、48694106107110111133134140146151153154157158166167171174182185188197198199201203205206與圖089（標(biāo)號(hào)為90）空白位置相近的圖片編號(hào)有69個(gè)9059101416171822262833344120857616771727581848694102103106107109110111114115118120124126133134140141146147151152153154155156157158166167171174182183185186188195197198199201203205206與圖094（

21、標(biāo)號(hào)為95）空白位置相近的圖片編號(hào)有22個(gè) 95153543444859727885909198113122125128137145150165184與圖125（標(biāo)號(hào)為126）空白位置相近的圖片編號(hào)有19個(gè) 126141517226790107110111146158174182183185188198205與圖168（標(biāo)號(hào)為169）空白位置相近的圖片編號(hào)有37個(gè) 16921517192224273142516367778788101103107110111121140143146148151158174180182185188192196198205由于圖片的切割都不完整導(dǎo)致空行較多，故通過

22、程序運(yùn)行出的結(jié)果每一行的符合要求的圖片都張。3）有一組恰為19塊圖，但通過第一問的模型對(duì)這19塊進(jìn)行橫向拼接時(shí)，發(fā)現(xiàn)有三塊明顯不位于同一行，將這三塊拿出，分別為,圖014，圖016，圖089。再找相對(duì)較少（22塊）的幾行，發(fā)現(xiàn)其中重復(fù)的恰為首列中的某3個(gè)圖，刪去后，得到這幾列的19個(gè)圖分別進(jìn)行拼接，其中首圖為007圖的拼接結(jié)果為：圖4（人工干預(yù)）我們發(fā)現(xiàn)所選圖片恰為該行圖片，但拼接結(jié)果由于碎片邊緣筆劃變化導(dǎo)致相連部分誤差較大，從而出現(xiàn)計(jì)算機(jī)拼接錯(cuò)誤，人工干預(yù)將錯(cuò)誤部分進(jìn)行更改后，該行順序?yàn)椋罕?：0072081381581260681750451740001370530560931530701

23、66032196同理，可得到其余行向找出為22塊行的拼接順序，分別為表4：038148046161024035081189122103130193088167025008009105074061019078067069099162096131079063116163072006177020052036再處理行中找出35或37個(gè)圖片的行，首先通過程序?qū)⒅耙咽褂眠^的圖片排除，則首圖為圖029的行，剩余圖片為表5：029005010037044048055059064076092098104111139151171172180201206用問題一中模型對(duì)該21塊圖進(jìn)行拼接，發(fā)現(xiàn)圖139和圖150不

24、屬于該行，將兩圖刪除后，再次進(jìn)行拼接，得到上一步中情況（有個(gè)別拼接不準(zhǔn)確），（人工干預(yù)）將其調(diào)換位置，得到該行順序?yàn)楸?：029064111201005092180048037075055044206010104098172171059同理，得到首圖為圖049，圖168的兩行排列為表7：049054065143186002057192178118190095011022129028091188141168100076062142030041023147191050179120086195026001087018再用以上結(jié)果篩選47個(gè)圖的行，剩余圖片為表8：0710080090150170250

25、27032033060074080083085105132133152156165170198200202205用問題一中模型對(duì)該25塊圖進(jìn)行拼接，發(fā)現(xiàn)圖008、圖009、圖025、圖032、圖074、圖105不屬于該行，將兩圖刪除后，再次進(jìn)行拼接，得到上一步中情況（有個(gè)別拼接不準(zhǔn)確），（人工干預(yù)）將其調(diào)換位置，得到該行順序?yàn)?表9：071156083132200017080033202198015133170205085152165027060而對(duì)于一行中出現(xiàn)69塊和67塊的兩行，重復(fù)較多，于是我們選用另一種方式篩選。當(dāng)?shù)玫矫繅K圖所對(duì)應(yīng)矩陣后，我們將有全空白行記為0，存在黑色部分行記為1，則

26、用mathematica得到該圖片的一個(gè)0-1列向量，例如圖089的對(duì)應(yīng)0-1列向量為：其中，我們挑選出幾列進(jìn)行部分對(duì)比，左側(cè)為其對(duì)應(yīng)上部幾行對(duì)比，右側(cè)為其對(duì)應(yīng)中部幾行對(duì)比。與左邊對(duì)應(yīng)中間行位置00000111100000011110000001111000000111100000011110000001111000000111100000011111000001111100000111110000011111000001111100011111110011111110001111111000111111100011111110001111111000111111101011111110101

27、1111111101111111110111111111011111111101111111110111111111011111111101111111110111111111011111111101111111110111100111011110000101111000010111100001011110000觀察所選出對(duì)應(yīng)圖片的0-1列向量對(duì)比，不難發(fā)現(xiàn)，其1-1對(duì)應(yīng)，0-0對(duì)應(yīng)較準(zhǔn)確。若兩個(gè)圖片屬于同一行，則其空白位置高度應(yīng)對(duì)應(yīng)相等，字體高度對(duì)應(yīng)相等，針對(duì)這一特性，我們對(duì)兩個(gè)列向量做內(nèi)積后，同行的內(nèi)積不變，建立模型得：與圖089同行的圖片應(yīng)滿足：盡量小，我們將結(jié)果由小到大排列，前10個(gè)即

28、為與圖089同行的圖片同樣的與圖014同行的圖片應(yīng)滿足：盡量小，我們將結(jié)果由小到大排列，前10個(gè)即為與圖014同行的圖片從而對(duì)首圖為圖089和圖014的兩行又做了篩選，得到表10：089146102154114040151207155140185108117004101113194119123014128003159082199135012073160203169134039031051107115176則剩余為首圖為圖125一行中圖片，用問題一中模型排序?yàn)楸?1：1250131821091970161841101870661061500211731571812041391453）完成行圖片的

29、拼接，后續(xù)只相當(dāng)于拼接矩陣，此時(shí)所有圖片僅有橫切情況，類似于第一問中僅縱切情況，利用MATLAB變成完成最后拼接效果。附件3的拼接順序： 表12：04905406514318600205719217811819009501102212902809118814106101907806706909916209613107906311616307200617702005203616810007606214203004102314719105017912008619502600108701803814804616102403508118912210313019308816702500800910507

30、407115608313220001708003320219801513317020508515216502706001412800315908219913501207316020316913403903105110711517609403408418309004712104212414407711214909713616412705804312501318210919701618411018706610615002117315718120413914502906411120100509218004803707505504420601010409817217105900720813815812

31、6068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123該模型雖能準(zhǔn)確拼出復(fù)原后圖片，但在每一行挑選過程中不能分別準(zhǔn)確的找出對(duì)應(yīng)的19個(gè)圖片，若對(duì)的每個(gè)列矩陣進(jìn)行調(diào)整，相信可以更準(zhǔn)確地快速地拼出圖片。5.4附件4中碎紙片拼接 我們首先希望同樣通過附件3的方法，即通過碎紙片左邊界留白的情況，篩選出11張圖片作為第一列。但是由于英語文章的特殊性，每個(gè)單詞之間都有一定的間隔，加之碎紙片的高度較小，以至于不止11張紙條的左邊界是空白，于是我們引入一種新的方法。

32、首先，當(dāng)?shù)玫矫繅K圖所對(duì)應(yīng)矩陣后，如果某行全為空白，則將該行記為0，否則記為1，則用mathematica將該圖片轉(zhuǎn)化為一個(gè)0-1列向量。從而篩選1元素較多的即英文字母密集的圖片，由這些圖片（人工干預(yù)）逐次篩選后，所留英文字母密集且行位置不同的，作為我們拼接的起點(diǎn)。再由其確定原因字母的中心行，進(jìn)而確定出行高，由密集圖片行高的不同位置，兩邊延伸，進(jìn)行拼接，由于某些行為段落結(jié)尾處，其后空白較多，需人工干預(yù)，同樣可拼接出11行英文字母，最后同附件3的處理方式，對(duì)11個(gè)行轉(zhuǎn)化成矩陣進(jìn)行拼接。附件4的拼接順序表13：191075011154190184002104180064106004149032204

33、065039067147201148170196198094113164078103091080101026100006017028146086051107029040158186098024117150005059058092030037046127019194093141088121126105155114176182151022057202071165082159139001129063138153053038123120175085050160187097203031020041108116136073036207135015076043199045173079161179143208

34、0210070490611190331421680621690541921331181891621971120700840600140681741371950080471721560960230991220901851091321810950691671631661881111442060031300340131100250271781710421662050101570741450831340550180560350160091831520440810771282001310521251401930870890480720121771240001021155.5 附件5的拼接復(fù)原對(duì)于雙面打印

35、的英文印刷圖片 1）將碎紙圖片轉(zhuǎn)化為的數(shù)字矩陣2）確定附件5中所有碎紙圖片中的邊界圖片，依據(jù)為紙張的邊界留白更多這一準(zhǔn)則，計(jì)算每個(gè)矩陣對(duì)應(yīng)列向量和，形成行向量，可將所得行向量元素一次達(dá)到最大值的向量所在矩陣對(duì)應(yīng)的碎紙片確定為左邊界。3）又由于所有碎紙圖片分為正反兩面，每頁紙被切為個(gè)碎片，故經(jīng)過篩選之后共得到邊界圖片22張。其中有11張邊界圖片為反面的右邊界。則這22張碎紙圖片可分為11類。每一類的分類標(biāo)準(zhǔn)為兩張碎紙圖片中字母所在行灰度吻合度最高。依此標(biāo)準(zhǔn)得到的這11類邊界分布。4）每一類的邊界有正反兩個(gè)邊界，依據(jù)這兩張邊界圖片中字母所占行灰度，在其他剩余碎紙圖片中尋找與之灰度吻合參數(shù)最小的作為

36、同一行。由于英文字母本身占格位置的特殊性，誤差較漢字來說要大。在進(jìn)行同行碎紙圖片拼接時(shí)準(zhǔn)確率不高。此時(shí)，需引入大量的人工干預(yù)來進(jìn)行拼接工作。5）經(jīng)過大量的人工干預(yù)，最后我們可以得到：附件5的拼接順序?yàn)楸?4：136b047a020a164b081b189b029a018b108a066a110a174b183b150a155a140a125a111b078b005a152a147a60b059a014a079a144a120b022a124b192a025b044a178a076b036a010b089a143b200b086b187b131b056b138a045a137b061b094b0

37、98a121a038a030a042b084b153a186b083a039b097a175a072b093a132b087a198b181b034a156a206b173b194b169b161a011b199b090a203b162b002a139b070b041a170b151b001b166b115b065b191a037b180a149b107a088b013a024a057a142a208a064b102b017b012a028b154b197a158a058a207a116b179b184b114a035a159a073b193b163a130a021b202a053b177b0

38、16b019b092b190b050a201a031a171b146a172a122a182b040a127a188a068b008b117b167a075b063b067a046a168a157a128a195a165b105a204b141a135b027a080b000b185a176a126b074b032a069a004a077a148b085b007b003b009b145a082b205a015b101a118b129b062a052a071b033b119a160b095a051b048a133a023b054b196b112a103a055b100b106b091a049b0

39、26b113a134a104a006a123a109a096b043a099a復(fù)原圖片見附錄圖3.1和圖3.2六、模型評(píng)價(jià)與改進(jìn)優(yōu)點(diǎn)：1問題一模型，簡單、易操作。適用于單張碎片所含文字信息量大的圖片拼接復(fù)原；2問題二模型，對(duì)于碎片上信息量較少，但數(shù)量龐大的情況，以減少比對(duì)范圍來達(dá)到理想拼接復(fù)原效果，且效率較高；3問題三中模型，考慮了現(xiàn)實(shí)生活中的所有考慮因素，并運(yùn)用MATLAB軟件編程得出了結(jié)果，應(yīng)此結(jié)果準(zhǔn)確性高，誤差小，切合生活實(shí)際；4實(shí)現(xiàn)碎紙片拼接技術(shù)的計(jì)算機(jī)化，實(shí)現(xiàn)批量拼接，以節(jié)省人力和時(shí)間。5假設(shè)合理，模型具有堅(jiān)實(shí)可靠的數(shù)學(xué)基礎(chǔ)。缺點(diǎn)：1.假設(shè)條件很多，這就直接導(dǎo)致與實(shí)際情況仍有一定的差

40、距，同時(shí)許多實(shí)際因素尚未納入考慮的范圍之內(nèi)，沒有考慮周全，因此導(dǎo)致一系列計(jì)算數(shù)據(jù)誤差較大。2.因?yàn)槿狈δ承┈F(xiàn)實(shí)統(tǒng)計(jì)數(shù)據(jù)的支持，導(dǎo)致人為主觀因素在模型的建立計(jì)算過程中的影響舉足輕重，因此在選擇處理方法時(shí)也受到條件上的眾多限制。故此模型并不完全貼合實(shí)際，不利于實(shí)際的應(yīng)用。3.由于時(shí)間關(guān)系，一些改進(jìn)思路來不及實(shí)現(xiàn)。模型改進(jìn)：1.對(duì)于分類不夠精確這一問題，我們應(yīng)用mathematica軟件對(duì)英文字母進(jìn)行識(shí)別（程序見附錄末），已識(shí)別出這些在英文書寫中出現(xiàn)頻率較高且僅占用中間行的字母，以此易于定位，可以提高分類的精確度，從而解決了這一問題。七、參考文獻(xiàn)1.蔡旭輝劉衛(wèi)國蔡立燕，MATLAB基礎(chǔ)與應(yīng)用教程，人

41、民郵電出版社，2009.8;2.尚明姝，基于特征點(diǎn)約束關(guān)系的圖像拼接算法J，電視技術(shù)，第36卷第13期:2012;3.姜麗鳳鞏建學(xué),基于特征點(diǎn)的圖像拼接算法研究與實(shí)現(xiàn),電腦開發(fā)與應(yīng)用,第24卷 第6期： 2011年; 4.姜啟源，數(shù)學(xué)模型（第四版），北京：高等教育出版社，2003.8;5.羅智中，基于文字特征的文檔碎紙片半自動(dòng)拼接，計(jì)算機(jī)工程與應(yīng)用，2012;6.方靜，基于特征點(diǎn)的圖像拼接算法優(yōu)缺點(diǎn)比較，電腦知識(shí)與技術(shù)，第9卷，第07期：2013.3。附錄一：（針對(duì)問題一）附件1圖片生成程序：clcclearp=cell(1,18);for i=1:10 imageName=strcat(I:

42、題目附件100,num2str(i-1),.BMP); pi = imread(imageName);endfor i=11:19 imageName=strcat(I:題目附件10,num2str(i-1),.BMP); pi = imread(imageName);endsump=;Answer=;for i=1:19 Answer(i)=i;endfor i=1:19 sump(i)=(sum(pi(:,1)+sum(pi(:,2);endA=find(sump=max(sump);C=Answer(A);Answer(A)=1;Answer(1)=C;B=pA;pA=p1;p1=B;f

43、or i=2:19 sump=; for j=i:19 a=pi-1(:,72); b=pj(:,1); s=abs(a-b); sump(j)=sum(s); for k=1:(i-1) sump(k)=9999999; end endA=find(sump=min(sump);C=Answer(A);Answer(A)=Answer(i);Answer(i)=C;B=pA;pA=pi;pi=B;endAnswer-1q=p1;for i=2:19q=q,pi;end imshow(q)附件1復(fù)原結(jié)果圖片：圖1.1附件2圖片生成程序：clcclearp=cell(1,18);for i=1:10 imageName=strcat(I:題目附件200,num2str(i-1),.BMP); pi = imread(imageName);endfor i=11:19 imageName=strcat(I:題目附件20,num2str(i-1),.BMP); pi = imread(imageName);endsump=;Answer=;for i=1:19 Answer(i)=i;endfor i=1:19 sump(i)=(sum(pi(:,1)+sum(pi(:,2);endA=find(sump=max(sump);C=Answer