全國大學(xué)生數(shù)學(xué)建模大賽B優(yōu)秀論文

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

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

3、16 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）： 14 碎 紙 片 的 拼 接 復(fù) 原 摘要 破碎文件的拼接在歷史文獻修復(fù)和軍事情報獲取等領(lǐng)域中都發(fā)揮著重要作用，由于撕裂、切碎、污染或自然衰老等原因，原始文件的信息可能會丟失。盡管用手或某些化學(xué)過程，可能將一些原始文件恢復(fù)，但是基于圖像技術(shù)的文件恢復(fù)是一種非侵入性的和高效率的方法，所以它被普遍采用。傳統(tǒng)上，

4、拼接復(fù)原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。 本文中針對問題1，讀入附件所給出的圖片，用自定義閾值法實現(xiàn)圖像的二值化，得出碎紙片的匹配矩陣，根據(jù)歐氏距離計算圖片之間重疊部分的相似度，再利用matlab軟件進行該算法相關(guān)計算，得到碎紙片的拼接順序，復(fù)原破碎圖片。針對問題2，讀入附件所給出的圖片，用自定義閾值法實現(xiàn)圖像的二值化，得出碎紙片拼接的匹配矩陣，任取一碎片并判斷：（1）若被判斷為圖像左（右）邊緣的碎片，則從該碎片右（左）邊緣開始進行拼接，計算與其他碎片之間

5、重疊部分的相似度，再利用matlab軟件進行矩陣的相關(guān)計算，得到碎紙片的拼接順序，把塊狀復(fù)原拼接成條狀。（2）若為圖像中間部分的碎片，則分別從左右兩個方向進行拼接。再按問題1的方法，計算這排列好的11行碎紙條重疊部分的相似度，即用matlab軟件進行此算法的相關(guān)計算，得到碎紙片的拼接順序，復(fù)原破碎圖片，問題2的相似度的計算與問題1一樣，用求歐式距離的方法。針對問題3，讀入附件所給出的圖片，用自定義閾值法實現(xiàn)圖像的二值化，得出碎紙片拼接的匹配矩陣，任取一碎片再進行如同問題2中拼接，即求最小歐式距離的方法，發(fā)現(xiàn)滿足此條件的候選被拼接的碎片不唯一，則我們再用相關(guān)系數(shù)法求得該系數(shù)最接近1的碎片是我們的

6、最佳選擇，最后用matlab軟件進行這個算法實現(xiàn)的相關(guān)計算，得到碎紙片的拼接順序，復(fù)原破碎圖片。關(guān)鍵詞： 圖像碎片拼接 二值化法 歐氏距離 相似度 人工干預(yù) 相關(guān)系數(shù) 1.問題重述破碎文件的拼接在司法物證復(fù)原、歷史文獻修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。1.1破碎紙片為同一頁印刷文字文件的碎紙機僅縱切得到的，建立碎紙片拼接復(fù)原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復(fù)

7、原。如果復(fù)原過程需要人工干預(yù)，則寫出干預(yù)方式及干預(yù)的時間節(jié)點。復(fù)原結(jié)果以圖片形式及表格形式表達。1. 2破碎紙片為碎紙機既縱切又橫切的得到，建立碎紙片拼接復(fù)原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，則寫出干預(yù)方式及干預(yù)的時間節(jié)點。復(fù)原結(jié)果表達要求同上。1. 3從現(xiàn)實情形出發(fā)，破碎紙片為雙面打印文件的碎紙片，建立碎紙片拼接復(fù)原模型。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果，結(jié)果表達要求同上。 2.問題分析 此題針對破碎文件的拼接，在問題1中，對給定的來自同一頁印刷文字的碎紙機破碎紙

8、片（僅縱切），建立碎紙片，拼接復(fù)原模型和算法。問題2中，來自同一頁印刷文字的碎紙機破碎紙片（縱橫切），建立碎紙片拼接復(fù)原模型和算法。問題3中，從現(xiàn)實情形出發(fā)，針對雙面打印文件的碎紙片拼接復(fù)原問題的解決。設(shè)計相應(yīng)的碎紙片拼接復(fù)原模型與算法。問題1：針對此題，讀入附件所給的灰度圖，用自定義閾值法實現(xiàn)圖像的二值化。對于每一個碎紙片的灰度矩陣進行二值化處理。計算匹配矩陣，得出碎紙片拼接的匹配矩陣，找一張碎片的右邊分別于其他碎片的左邊進行匹配，直到找到相匹配的碎片為止，再把找到的碎片左邊與其他碎片的右邊進行匹配，直到找到相匹配的碎片為止，依次循環(huán)下去，直到拼接完成。問題2：針對此題，讀入附件所給的灰度圖

9、，用自定義閾值法實現(xiàn)圖像的二值化。對于每一個碎紙片的灰度矩陣進行二值化處理。計算匹配矩陣，得出碎紙片拼接的匹配矩陣， 這時我們需要判斷碎片是左邊緣還是右邊緣，還是上下邊緣，中心邊緣，從而進行拼接，先拼行再拼列，從左往右拼，最后復(fù)原破碎圖片。問題3：讀入附件所給出的圖片，用自定義閾值法實現(xiàn)圖像的二值化，得出碎紙片拼接的匹配矩陣，任取一碎片再進行如同問題2中拼接，即求最小歐式距離的方法，發(fā)現(xiàn)滿足此條件的候選被拼接的碎片不唯一，則我們再用相關(guān)系數(shù)法求得該系數(shù)最接近1的碎片是我們的最佳選擇，最后用matlab軟件進行這個算法實現(xiàn)的相關(guān)計算，得到碎紙片的拼接順序，復(fù)原破碎圖片。 3.模型假設(shè)3.1假設(shè)所

10、研究碎紙片規(guī)則且形狀大小完全相同。3.2假設(shè)所研究碎紙片為平滑的。3.3假設(shè)所研究碎紙片文字方向一致。4.變量說明i表示碎紙片灰度矩陣行數(shù)j表示碎紙片灰度矩陣列數(shù)p表示碎紙片灰度矩陣p表示二值化灰度矩陣d表示歐式距離表示改點的灰度值表示灰度矩陣第j列的k維坐標表示灰度矩陣第1列的k維坐標表示灰度矩陣第j列的k維坐標表示被選碎紙片第j列的i個指標所組成的向量表示匹配碎紙片第1列的i個指標所組成的向量c（x,y）表示相關(guān)系數(shù),x,y表示兩個向量5.模型的建立與求解問題一：碎紙片灰度矩陣的行列： i=1980 j=72.碎紙片灰度矩陣類型： 二值化處理后的灰度矩陣： 處理后的灰度矩陣第j列為： 處理

11、后的灰度矩陣第1列為： 運用歐氏距離得到相似度： d=d值越小，表明這兩個碎紙片相似度越高，從而可以進行拼接，依次類推可得結(jié)果。 1、將附件1中所有圖片進行預(yù)處理得到灰色矩陣，再將各個矩陣的第一列和最后一列拿出，構(gòu)成新的72*2的列矩陣，對此進行初始編號。 2、用其中一個列矩陣的第二列與其他18個列矩陣的第一列做歐氏距離，在這十八個距離中，取最小值作為與它相似度最高的矩陣；再將取得最小值的列距陣的第二列與其他17個列矩陣的第一列做歐氏距離，在這十八個距離中，取最小值作為與它相似度最高的矩陣；依次循環(huán)直到拼接完成。matlab編程如下：imname = dir(.*.bmp);%讀入文件夾下的全

12、部圖像im_num = length(imname);% 文件夾中圖像的個數(shù)ininum = 0;for s = 1:im_num img = imread(imname(s).name,bmp); if norm(double(img(:,1) - 255) 0.0001 ininum = s; endendindex = 1:ininum-1,ininum+1:im_num;img1 = imread(imname(ininum).name,bmp);%讀入第一幅圖像height1,width1 = size(img1);%得到圖像的尺寸xunxu = zeros(1,im_num); %

13、存儲最終序列號xunxu(1) = ininum;result = img1;for a = 2:im_num error = zeros(1,length(index); for tt=1:length(index) img2 = imread(imname(index(tt).name,bmp);%讀入第一幅圖像 height2,width2 = size(img2);%得到圖像的尺寸 error(tt) = norm(double(img1(:,end)-img2(:,1),2); end tm,tn=min(error); temp = imread(imname(index(tn).

14、name,bmp); result = result,temp; img1 = imread(imname(index(tn).name,bmp);xunxu(a) = index(tn); index = index(1:tn-1),index(tn+1:end); end% result = uint8(result);% xunxu附件1的輸出結(jié)果如表1 8 14 12 15 3 10 2 16 1 4 5 9 13 18 11 7 17 0 6得到拼接圖1： 附件2輸出結(jié)果表2： 3 6 2 7 15 18 11 0 5 1 9 13 10 8 12 14 17 16 4得到拼接圖2：

15、問題二：圖像拼接技術(shù)主要有以下三個步驟：圖像預(yù)處理、圖像配準、圖像融合與邊界平滑?？瞻椎乃槠ǔ３霈F(xiàn)在邊界或分離的多個列的文檔。最左邊的分解特點是左邊附近沒有紋理或右邊界有紋理，反之亦然，是最右邊的邊界。很明顯,這兩種類型的碎片可以方便驗證通過檢查直方圖的垂直預(yù)測(即沿分解方向)。因此,他們首先,他們作為始端和終端，再建立如問題一的模型進行拼接，即求最小歐式距離的方法，用matlab軟件進行此算法的相關(guān)計算，得到碎紙片的拼接順序，復(fù)原破碎圖片。1 2 1圖是具有左邊緣特征的圖，2圖具有右邊緣特征的圖 具體算法步驟 ： 1、將附件3中所有圖片進行預(yù)處理得到灰色矩陣，再將各個矩陣的第一列和最后一列

16、拿出，構(gòu)成新的列矩陣，對此進行初始編號。2、任取一列矩陣并判斷是左邊緣圖還是右邊緣圖，若為左邊緣圖則從該碎片第二列開始與其他的列矩陣的第一列做歐氏距離，在這209個距離中，取最小值作為與它相似度最高的矩陣；再將取得最小值的列距陣與其他的列矩陣的第一列做歐氏距離，一次循環(huán)到該行拼接完成，直到把行都拼接完，再用問題1的方法拼接完成；若為右邊緣圖則從該碎片第一列開始與其他的列矩陣的第二列做歐氏距離，在這209個距離中，取最小值作它相似度最高的矩陣，將取得最小值的列距陣的第一列與其他的列矩陣的第二列做歐氏距離，一次循環(huán)到該列拼接完成，直到把列都拼接完；再用問題1的方法拼接完成。matlab編程如下：f

17、unction judgelinespaceam=cell(1,209);dd=zeros(2,209); for i=1:209 if i10 & i101) imgname = d:b30, num2str(i-1), .bmp; am1,i = imread(imgname, bmp); else imgname = d:b3, num2str(i-1), .bmp; am1,i = imread(imgname, bmp); end endend for k=1:209 flag=0; for i=1:180 for j=1:72 if am1,k(i,j) =255 flag=1;

18、break; end end if flag=1; dd(1,k)=i-1; break; end end end for k=1:209 flag=0; for i=180:-1:1 for j=1:72 if am1,k(i,j) =255 flag=1; break; end end if flag=1; dd(2,k)=180-i; break; end end enddd輸出函數(shù)如下：function re = mat2pic(mat) imname = dir(.*.bmp); im_num = length(imname);img = imread(imname(1).name,

19、bmp);height,width = size(img); r,c = size(mat)re = zeros(r*height,c*width,uint8);for tr = 1:r for ts = 1:c img = imread(imname(mat(tr,ts).name,bmp);re(tr-1)*height+1:tr*height,(ts-1)*width+1:ts*width)=img; endendimshow(re);附件3的輸出結(jié)果如表3049 054 065 143 186 002 057 192 178 118 190 095 011 022 129 028 09

20、1 188 141 061 019 078 067 069 099 162 096 131 079 063 116 163 072 006 177 120 052 036168 100 076 062 142 030 041 023 147 050 179 191 120 086 195 026 001 087 018038 148 046 161 024 035 081 189 122 103 130 193 088 167 025 008 009 105 074071 156 083 132 200 017 080 073 202 198 015 133 170 205 085 152 1

21、65 027 060014 128 003 159 082 199 012 073 160 135 203 169 134 039 031 051 107 115 176094 034 084 183 077 090 047 121 042 124 144 112 149 097 136 164 127 058 045125 013 182 109 197 016 184 110 187 066 106 150 021 175 157 181 204 139 145029 064 111 201 005 092 180 048 037 075 055 044 206 010 104 098 1

22、72 171 059007 208 138 158 126 068 175 045 174 000 137 053 056 093 155 070 166 052 196 089 146 102 154 114 040 151 207 155 140 185 108 117 004 101 113 194 119 123得到拼接圖3：得到拼接圖4：問題三：先建立如問題二的模型，即求最小歐式距離的方法，發(fā)現(xiàn)滿足此條件的候選被拼接的碎片不唯一。基于區(qū)域的配準方法是從待拼接圖像的灰度值出發(fā)，對待配準圖像中一塊區(qū)域與參考圖像中的相同尺寸的區(qū)域使用最小二乘法或者其它數(shù)學(xué)方法計算其灰度值的差異，對此差異比

23、較后來判斷待拼接圖像重疊區(qū)域的相似程度，由此得到待拼接圖像重疊區(qū)域的范圍和位置，從而實現(xiàn)圖像拼接，而本文用計算兩塊區(qū)域的對應(yīng)像素點灰度值的相關(guān)系數(shù)，相關(guān)系數(shù)越接近于1，則兩塊圖像的匹配程度越高。該方法的拼接效果要好一些，成功率有所提高.附件5的輸出結(jié)果如表56.模型的推廣與改進該模型把規(guī)則且形狀大小完全相同破碎紙片復(fù)原拼接，而且程序簡單容易操作，建模過程用到的圖像拼接技術(shù)具有一般性，容易做出推廣，但是在碎片數(shù)量龐大時，我們需要用水平投影和垂直投影的方法將圖片進行聚類，然后分類后再進行拼接，這樣會減少計算機的運行時間，空間，也就同時提高了拼接效率。7.參考文獻1羅智中，基于文字特征的文檔碎紙片半

24、自動拼接，計算機工程與應(yīng)用，05期：2012。2王磊，莫玉龍，戚飛虎，基于canny 理論的邊緣提取改善方法j，中國圖象圖形學(xué)報，03期：191-195，1996。3陶波，于志偉，鄭筱祥，圖像的自動拼接j，中國生物醫(yī)學(xué)工程學(xué)報，04期：29-35，1997。4劉金根，吳志鵬，一種基于特征區(qū)域分割的圖像拼接算法j，西安電子科技大學(xué)報，06期：768-771，2002。5周鵬，譚勇，徐守時，基于角點檢測圖像配準的一種新算法j，中國科學(xué)技術(shù)大學(xué)學(xué)報，04期：455-461，2002。6朱延娟，周來水,二維非規(guī)則碎片的匹配算法j，計算機工程，24期:7-9，20077羅智中.基于線段掃描的碎紙片邊界檢

25、測算法研究j，儀器儀表學(xué)報，02期：289-294，2011。8de smet p.semi-automatic forensic reconstruction of ripped-up documentsc.international conference on document analysis and recognition，10th，703-707，2009。9 biswas a, bhowmick p, bhattacharya b, reconstruction of torn documents using contour maps，in international conference on image processing,3th：517520，2005。10 brassil j，trac