碎紙片的拼接復原2

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

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

3、號（由賽區(qū)組委會評閱前進行編號）：2013高教社杯全國大學生數(shù)學建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：碎紙片的拼接復原摘要碎紙片的拼接復原中，我們將圖片拼接分為初步拼接和最終拼接兩大步，即計算機處理和人工干預。針對問題一：首先讀取圖像對碎片進行直觀分析，分析其縱切輪廓、切面長、縱向像素點等特點。再將每個碎片都進行灰度化處理即將圖片的像素范圍設定為0-255，黑色的為0，白色的為255，把0與255之間的灰度按對數(shù)關(guān)系分為若干等

4、級，處理后的圖像只有灰度等級而無顏色變化。接著用Matlab軟件中的graythresh函數(shù)獲得圖像的閾值T，用im2bw函數(shù)將灰度圖轉(zhuǎn)化為二值圖像即可得取二值化表，隨后提取每個碎片的二值化表邊緣部分組成兩個列矩陣。利用Matlab中的corr()函數(shù)對固定碎片與其余碎片的邊緣列矩陣進行相似度對比，從而能夠準確得出固定碎片與各個碎片邊緣的相似度值。為了直觀清新的的反應比值的大小我們用圖表等表示比較結(jié)果。接著將比較結(jié)果依次排列初步確定拼接順序，用Matlab進行無縫連接，并分析不同圖表的優(yōu)點。為了提高結(jié)果的準確性，我們對連接后的圖片進行人工干預。根據(jù)自身所擁有的知識，人工判斷其正確性并觀察拼接正

5、確率。從而我們?nèi)斯づ袛鄦栴}一的正確率為100%。最后我們可以確定最終拼接順序與初步拼接順序相同，這樣問題一就得以解決了。針對問題二：此問所給碎片量大，單個碎片邊緣像素點少。在同問題一的解決基礎上，利用邊緣相似度進行比較時，先進行橫向比較，同時給出固定碎片各個碎片間的相似度排列順序，篩選出相似度大的幾個碎片，再進行人工干預，得出兩兩相鄰的碎片，從而得出橫向被切割的11行碎片。隨后在進行縱向比較，確定其整體拼接順序。人工干預，確定最終復原結(jié)果。問題二也迎刃而解。針對問題三：此題本質(zhì)與前兩問相同，我們可以沿用上面的方法。此問我們先進行一面的拼接，背面則為與之對應的圖片號。拼接中的數(shù)據(jù)處理我們可以用M

6、atlab軟件，將兩兩圖片進行相似度比較，逐步減少碎片的數(shù)量，知道得出最后的拼接結(jié)果。計算機處理與人工干預兩者是“焦不離孟，孟不離焦”。只有兩者相結(jié)合才能更高速率的實現(xiàn)碎片的拼接復原。關(guān)鍵字：Matlab函數(shù)灰度二值化相似度篩選人工干預一、問題的重述1.1背景分析破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用。傳統(tǒng)上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復原效率。1.2問題提出1. 對于給定的來自同一頁印刷文字文件的碎紙機破碎紙

7、片（僅縱切），建立碎紙片拼接復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結(jié)果以圖片形式及表格形式表達（結(jié)果表達格式說明）。2. 對于碎紙機既縱切又橫切的情形，請設計碎紙片拼接復原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結(jié)果表達要求同上。3. 上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。

8、請嘗試設計相應的碎紙片拼接復原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復原結(jié)果，結(jié)果表達要求同上。1.3說明1.數(shù)據(jù)文件說明(1) 每一附件為同一頁紙的碎片數(shù)據(jù)。(2) 附件1、附件2為縱切碎片數(shù)據(jù)，每頁紙被切為19條碎片。(3) 附件3、附件4為縱橫切碎片數(shù)據(jù)，每頁紙被切為11×19個碎片。(4) 附件5為縱橫切碎片數(shù)據(jù)，每頁紙被切為11×19個碎片，每個碎片有正反兩面。該附件中每一碎片對應兩個文件，共有2×11×19個文件，例如，第一個碎片的兩面分別對應文件000a、000b。2.結(jié)果表達格式說明復原圖片放入附錄中，表格表達格式如下：(1) 附件1、

9、附件2的結(jié)果：將碎片序號按復原后順序填入1×19的表格；(2) 附件3、附件4的結(jié)果：將碎片序號按復原后順序填入11×19的表格；(3) 附件5的結(jié)果：將碎片序號按復原后順序填入兩個11×19的表格；(4) 不能確定復原位置的碎片，可不填入上述表格，單獨列表。二、問題分析首先從表面上看，這個問題用我們現(xiàn)學的知識很難解決。為了將其轉(zhuǎn)化為數(shù)學知識我們必須借助于Matlab等軟件來將碎片轉(zhuǎn)化為數(shù)據(jù)。這樣才方便我們將其轉(zhuǎn)化為數(shù)學知識，從而較好的去解決這個難題。使用人工拼接的方式，若是需要拼接的碎片少還比較簡便但對于問題二、三等碎片較多的情況則會十分的困難。所以，我們只能借

10、助軟件程序來化簡碎片復原這個問題。在實際運用中，考慮到一些外界因素對圖片像素的影響，我們需將其進行灰度化處理找出閾值后二值化，然后用Matlab程序求出各個圖片間的相似度，再用Excel對數(shù)據(jù)進行處理畫出折線圖從而比較其大小確定拼接順序，實現(xiàn)碎片復原。而閾值的確定若用公式法則十分的復雜，所以我們需借助Matlab進行確定。三、模型假設1、假設是在光照均勻、無噪聲、無干擾的理想情況下。2、忽略個別異常數(shù)據(jù)對模型的影響即舍去異常對象。3、假設碎片沒有丟失、破損的情況。4、忽略人工干預的影響。5、假設規(guī)定所有數(shù)據(jù)結(jié)果最多保留4位小數(shù)。6、假定粗閾值的誤差為10個像素點左右。四、符號說明C:方差T1:

11、粗閾值T:為閾值Y:灰度值g1:字符灰度g2:背景灰度M:灰度圖像均值R、G、B:像素分量r1:字符像素點所占比例r2:背景像素點所占比例Ua:A圖平均灰度Ub:B圖平均灰度五、模型的建立及求解為了使所建立模型的思路簡單清新，特給出建模流程圖如下所示：讀取圖像灰度化處理確定閾值，圖像二值化相似度比較確定相匹配圖像部分概念介紹無縫拼接，復原圖像5.1概念在建立模型的過程中我們運用了一些相對比較生疏的概念、方法。而它們是我們建立模型最主要的思路方法。具體介紹如下：(1) 最大類間方差法（即Otsu法）：它是由日本學者大津(Nobuyuki Otsu)于1979年提出的。它按圖像的灰度特性,將圖像分

12、成背景和字符兩部分。背景和字符之間的類間方差越大,說明構(gòu)成圖像的兩部分的差別越大,當部分字符錯分為背景或部分背景錯分為字符都會導致兩部分差別變小。因此,使類間方差最大的分割意味著錯分概率最小。使用該方法可以找到圖片的一個合適的閾值。(2) 灰度化、二值化：前者是將圖片的像素范圍設定為0-255，黑色的為255，白色的為0，把0與255之間的灰度按對數(shù)關(guān)系分為若干等級，處理后的圖像只有灰度等級而無顏色變化。而后者就是在前者的基礎上，運用公式或軟件算出一個合適的閾值，深度大于閾值則為1，小于的則取0。這兩個圖像處理使得復雜圖像簡便化，更易結(jié)果的得出。5.2圖像的讀取及灰度二值化處理在對圖像進行處理

13、前我們必須先讀取圖片，分析圖片的外輪廓、顏色變化強度等，忽略光照、噪聲等對模型建立的影響，從而方便之后圖片的處理。圖片讀取后我們則要對其進行灰度化處理。在現(xiàn)實生活中，某些需要拼接復原的圖片也許就其表面來看只有黑白兩色，但若我們用Matlab等軟件將其進行灰度化處理后會發(fā)現(xiàn)其本質(zhì)并非如此，如歷史文獻等。在數(shù)學領域我們對灰度及閾值的求解(參考文獻1)如下：已知則該碎片的灰度圖像均值為方差為由(1)式得出將(3)式帶入(2)式得出所以字符灰度為背景灰度為所以，對于碎片選取的粗閾值為在實際運用中，往往使用以下簡化計算公式求得灰度:然而，在計算機領域我們用Matlab中的graythresh函數(shù)獲得圖像

14、的閾值，用im2bw函數(shù)將灰度圖轉(zhuǎn)化為二值圖像。我們大部分的建模都是依靠Matlab和Excel來實現(xiàn)的。從而實現(xiàn)數(shù)據(jù)處理的計算機化，人為計算減少了。從而減少了因人的疏忽而造成結(jié)果的誤差。5.3邊緣矩陣的相似度比較相似度的比較在拼接技術(shù)中是非常常見的。固定某一塊碎片，將剩下的碎片一次與其進行邊緣相似度比較從中取得最大值，初步確定拼接順序，之后運用一些生活常識及已有的知識來判定結(jié)果是否正確，從而實現(xiàn)最后的拼接復原。在Matlab中的corr()函數(shù)求出兩個比較圖的二值化邊緣矩陣的相似度，從而節(jié)省大量的人力計算。具體編程見附錄 （參考文獻234）。5.4問題的解決三個問題的解決均離不開以上幾個步驟

15、，要順利的解決這些問題我們必須掌握上述過程算法和計算機軟件，人工的干預，5.4.1問題一的解決對于縱向切割，我們直接用Matlab將附件1、2的十九個碎紙片進行處理（見附錄3）后得到每個小碎片的二值化表，取出每個碎紙片的左右邊緣二值化結(jié)果分別構(gòu)成一個矩陣。因為問題一中給出的碎紙片數(shù)目比較少，所以我們可以很快的人工確定出首和尾列。而我們只要固定了首或尾，就能以它們中的一個為起始值，利用計算機確定其旁邊拼接的碎片的序號。1、附件1的解決：從給出的十九列碎片中我們可以很快的確定008圖為首列，006圖為尾列。之后用Matlab將首列的左邊緣的二值化矩陣與剩下的碎紙片的右邊緣二值化矩陣進行相似度比較，

16、并用Excel將所得結(jié)果用圖表方式表示，從而確定初步的拼接順序。，因為數(shù)據(jù)的個數(shù)越來越少，所以我們要根據(jù)數(shù)據(jù)個數(shù)的變化決定采用哪種圖表表示相似度，輸出的圖表如圖(1)到(16)。注：圖(1)、(2)、(11)、和表(1)、(2)如下，其余圖表見附錄4圖（1）與008圖的相似度圖該圖將008圖固定，取其右邊緣的二值化后的矩陣依次和其余的圖片左邊緣的二值化后的矩陣，利用Matlab中的corr2()函數(shù)進行相似度比較，得出數(shù)值后用Excel畫出折線圖，觀察峰值。則峰值對應的點即為相似度最大的點，所以可以得出008圖右邊與014圖左邊拼接。由圖(1)到(10)的折線圖可以知道折線圖能較好的看出峰值，

17、清楚的找出最大值、最小值。對于找某個點的值來說，其簡單而直觀。圖(2)到圖(10)的原理與圖(1)相同，只需重復上述操作。所以對于圖(1)到圖(10)的折線圖觀察可以得出拼接順序為014、012、015、003、010、002、016、001。圖(11)與005圖的相似度散點圖比較適用于找某個區(qū)域的值的分布情況，從而確定各個點的分布區(qū)域。在點過多時還可通過觀察來縮小搜索范圍，有力的節(jié)省了時間。如上圖所示可以找打到相似度最大的區(qū)域在(3,4)之間，從而比較區(qū)域內(nèi)的點可以知道相似度值最大的是004圖。同理可得出圖(12)到圖(14)的相似度最大值分別為011、005、009、013圖。表(1)與0

18、11圖相似度表比較號000006007017相似度0.20.15750.8130.2058表(1)是剩余的碎片的左邊緣逐個與011圖的右邊緣進行相似度計算，得出相似度值。從表中可以看出相似度值最大的是007圖。表(2)與007圖相似度表比較號000006相似度0.81940.1284與表一同理，可以得出與007圖右側(cè)相拼接的是000圖。表格對于數(shù)據(jù)比較少的情況而言是個明智的選擇，既節(jié)約空間又簡單明了。而且對應的值得具體值十分容易確定。所以，最終的碎片從左到右依次拼接的順序為008,014,012,015,003,010,002,016,001,004,005,009,013,018,011,0

19、07,017,000,006附件1的復原結(jié)果用1*19的表格表示為：表(3)008014012015003010002016001004005009013018011007017000006復原圖片見附錄1（2）附件2的解決與附錄一的解決原理基本相同，首先確定出首尾分別為圖003、004。輸出的圖表為表(4)到表(11)和圖(15)、(16)同樣取出個別圖表，如圖表(4)、圖(16)，剩余的圖表見附錄5。表(4)與003圖相似度表比較號000001002004005006相似度0.0970.20560.25920.12760.21790.7625表格的優(yōu)點上面已經(jīng)描述，這里不再贅述。由此，我們

20、可以快速的得出相似度值最大的是006圖。圖(16)與015圖的相似度圖條形圖和折線圖的功能差不多。因此可以看出相似度最大的是018圖。所以，可以得出附件2的碎片拼接次序為：003、006、002、007、015、018、011、000、005、001、009、013、010、008、012、014、017、016、004附件2的復原結(jié)果用1*19的表格表示為：表(12)003006002007015018011000005001009013010008012014017016004復原圖片見附錄2總結(jié)，我們用計算機軟件將圖像數(shù)字化輸出用圖表的形式表示，簡單明了。節(jié)省了大量的人為計算，也極大程度

21、的減少了人為誤差而問題一也得到了好的解決。當然，得出結(jié)果又是并非正確結(jié)果，有時還需要根據(jù)我們已有的知識去檢驗判斷其是否符合邏輯、空間思維。經(jīng)我們?nèi)藶闄z驗得出的結(jié)論是：計算得出的結(jié)果是正確的。所以我們可以開始著手下一題的解決了。5.4.2問題二的解決對于附件3、附件4這種既縱向切又橫向切割的情況，若是我們沿用問題一的解決方案，則會出現(xiàn)特別冗雜的計算。問題一中只有兩個邊緣，而此題中的碎片有四個邊緣，這樣就造成需要計算的情況太多，需要記錄的數(shù)據(jù)太多容易造成漏記，錯記等情況。從而可能會影響拼接結(jié)果的正確性，而且太浪費時間，我們根本沒有那么多的時間去反復驗證。為了解決計算量過大的問題，我們查詢了相關(guān)資料

22、，確定用Matlab軟件編寫程序來實現(xiàn)。當然在進行拼接之前我們?nèi)艘獙λ槠M行預處理、灰度化、二值化。因為情況太多，所以我們考慮先橫向拼湊得出是十一個橫向切的碎片，然后再進行是一塊碎片的拼接，從而實現(xiàn)復原圖像。在二值化處理后仍然是先進行邊緣提取，然后從000圖開始到208圖每次取一個圖片分別與給出的209個圖片的右邊緣進行相似度計算（具體程序見附錄8），比對結(jié)果相當于一個209*209的矩陣，部分截圖如下為了減小誤差需要選出其中的幾個相似度值較大的比較圖片依次與選定的圖片左面邊緣進行人工比對，根據(jù)我們的常識選取其中可能性最大的一個圖片。若有的圖片無法確定，則單獨放置，當209個圖片均比對完后，在

23、進行人工的觀察、判定、插入。然后，再用同樣的方法對這105個組進行相似度計算，這樣不斷地重復，直到不能再分組為止，最后得出十一個橫向切割的碎片，然后用Matlab編程對每組數(shù)據(jù)進行計算機碎片連接（詳細程序見附錄9），例如部分程序：a=Iunnamed11(1); %附件三中第一個圖片049b=Iunnamed11(2); %附件三中第二個圖片054z=a b;for i=3:209 %依次拼接x=unnamed11(i);y=Ix;z=z y;endimshow(z)輸出結(jié)果為：每組碎片的原圖連接編編程均如上，重復操作從而得出十一組原圖碎片。最后，對這十一組數(shù)據(jù)進行如題一方法的相似度比較，最后

24、得出拼接的順序，進行無縫連接得出原圖。對附件3的拼接的結(jié)果表格圖如下表：表（13）0490540651431860020571921781181900950110221290280911881410670690991620961310790631161630720061770200520360610190781681000760621420300410231471910501791200861950260010870180381480461610240350811891221031301930881670250080091050740711560831322000170800332021980

25、151331702050851521650270600141280031590821991350120731602031691340390310511071151760940340841830900471210421241440771121490971361641270580431250131821091970161841101870661061500211731571812041391450290641112010050921800480370750550442060101040981721710590072031381581260681750451740001370530560931530

26、70166032196089146102154114040151207155140185108117004101113194119123復原圖見附錄6對附件4的拼接的結(jié)果如下表：表（14）19107501115419018400210418006410600414903220406503906714720114817019619809411316407810309108010102610000601702814608605110702904015818609802411715000505905809203003704612701919409314108812112610515511417618

27、215102205720207116508215913900112906313815305303812312017508505016018709720303102004110811613607303620713501507604319904517309716117914320802100704906111903314216806216905419213311818916219711207008406001406817413719500804717215609602309912209018510913218109506916716316618811114420600313003401311002

28、5027178171042066205010157074145083134055018056035016009183152044081077128200131052125140193087089048072012177124000102115復原圖見附錄75.4.3問題三的解決現(xiàn)今社會，大部分的圖片、文字的記錄都是雙面的。針對于雙面打印文件的碎紙片拼接復原問題，其本質(zhì)與單面打印文件的拼接復原原理基本相同。首先要進行的也是灰度二值化處理，程序與題一類似。此題共有418個碎片，這些碎紙片不但橫縱向都切割而且是雙面的，每一面有209個，題中的正反面都是打亂的。雖然可以確定每一片紙片的兩面，但是不能確

29、定它的正反。對此，用解決問題二的思路，針對問題三我們需要處理的數(shù)據(jù)量就大了很多。而且每片紙中得到的數(shù)據(jù)量較少，無疑會讓結(jié)果準確性降低。鑒于一二問中提取邊緣二值矩陣然后對比相似度的方法得到的結(jié)果正確率高，我們決定繼續(xù)沿用此思路來解決第三問。對于雙面紙片，在用電子設備導入并數(shù)字化時，其背面可能會影響正面的灰度值。但是實際應用中，處理好拍攝角度等外界因素，完全可以將背面對正面灰度值的影響忽略。我們需要對圖片進行初步處理：導入圖像，灰度化，二值化，圖片邊緣信息提取得到邊緣二值矩陣。提取完信息后我們就著手進行圖片的相似度比較。由于處理的數(shù)據(jù)量比之前的要大很多，我們在用Matlab處理時，程序上做了較大改

30、動。我們注意到每張紙片與其他紙片進相似度比較后都可以找出與之相連接的紙片的序號。那么被找出的紙片其背面就不需要再做相似度比較了。所以每完成一組相似度比較就會減少兩個項。這樣，我們就避免了同一張紙片的重復比較，大大減少了運算的數(shù)據(jù)量，也省去了再判斷正反的步驟。相似度比較程序（程序見附錄12）運行完后我們得到了與各個紙片相似度最高的紙片的序號，部分截圖如下： 然后編程（程序見附錄12）將這些紙片序號進行排序，再通過人工的篩選，修改最終得到正確的制片拼接順序。最后，我們?nèi)匀挥胢atlab編程（程序見附錄13）實現(xiàn)紙片的無縫連接，最后的碎紙片的復原圖。對附件5的拼接的結(jié)果如下表(15)(16):表(1

31、5)78b111b125a140a155a150a183b174b110a66a108a18b29a189b81b164b20a47a136b89a10b36a76b178a44a25b192a124b22a120b144a79a14a59a60b147a152a5a186b153a84b42b30a38a121a98a94b61b137b45a138a56b131b187b86b200b143b199b11b161a169b194b173b206b156a34a181b198b87a132b93a72b175a97a39b83a88b107a149b180a37b191a65b115b166

32、b1b151b170b41a70b139b2a162b203b90a114a184b179b116b207a58a158a197a154b28b12a17b102b64b208a142a57a24a13a146a171b31a201a50a190b92b19b16b177b53b202a21b130a163a193b73b159a35a165b195a128a157a168a46a67a63b75b167a117b8b68b188a127a40a182b122a172a3b7b85b148b77a4a69a32a74b126b176a185a0b80b27a135b141a204b105a23

33、b133a48a51b95a160b119a33b71b52a62a129b118b101a15b205a82b145a9b99a43a96b109a123a6a104a134a113a26b49b91a106b100b55b103a112a196b54b表(16)136a47b20b140b164a81a189a29b18a108b66b110b174a183a150b155b125b111a78a5b152b147b76a60a59b14b79b144b120a22b124a192b25a44b178b36b10a89b143a200a86a42a187a131a56a138b45b137a61a94a98b121b38b30b84a153b186a83b39a97b169a175b72a93b132a87b198a181a34b156b206a173a194a161b11a199a90b203a162a180b2b139a7