數(shù)學(xué)建模拼圖問題論文

1、2014年河北工業(yè)大學(xué)數(shù)學(xué)建模競賽題目： 圖片拼接問題 參賽隊員信息： 姓 名所在學(xué)院班級學(xué)號參賽隊員1寇如意計算機(jī)學(xué)院軟件121122070參賽隊員2焦孟云經(jīng)管學(xué)院會計123121577參賽隊員3楊航經(jīng)管學(xué)院信管121121697圖片拼接問題摘要 本題是圖片拼接問題，主要運(yùn)用MATLAB軟件對碎片上下左右邊界的拼接關(guān)系進(jìn)行處理。首先是給出的圖片為彩色圖片，需要對圖片進(jìn)行灰度處理。其次是需要提取處理后的灰度圖的像素點(diǎn)矩陣，方便分析碎片邊界之間的銜接關(guān)系。由于問題一中給出了原始圖而問題二中沒有給出，所以對于問題一與問題二建立的模型是不相同的。 對于問題一，原始圖片不能均等的分割出相等的16份碎片

2、，因此使得碎片的像素不同但是差別不是很大。因此為了方便以后的的相似度對比，我們可以將原始圖以及碎片的大小利用imresize函數(shù)進(jìn)行像素改變，將原始圖片尺寸改變成，將16個碎片的大小都改變成。利用imread函數(shù)提取灰度處理后的原始圖片以及附件一中碎片的像素點(diǎn)矩陣。將原始圖的像素點(diǎn)矩陣平均分成16個子矩陣，將這16個子矩陣與附件一中給出的16個碎片提取的矩陣進(jìn)行相似的對比，最終確定各碎片在原始圖中的位置。得出復(fù)原結(jié)果。 對于問題二，沒有給出原始圖，因此不能用與原始圖比對的方法建立模型和拼接。在這一問中首先我們通過進(jìn)行像素點(diǎn)矩陣的提取得到。然后該問題需要進(jìn)行兩層篩選排序，第一層是進(jìn)行行處理，得出

3、按行分類的四類碎片集合，在進(jìn)行內(nèi)部行排序。取出第張碎片的第一列存入矩陣中；取剩余的碎片的最后一列存入到矩陣中，計算與的相似度并從中選出最大值即為在同一層并且相鄰的兩張碎片，得到每層的鄰接矩陣。第二層是列處理，對第選出已排好的四層的最左碎片的第一行行向量存入以及最后一行行向量存入中，分別進(jìn)行相似度比較，排好上下關(guān)系。綜合一二兩步就可以復(fù)原圖片。關(guān)鍵詞：MATLAB軟件 灰度處理 像素點(diǎn)矩陣 imresize函數(shù) 相似度 兩層篩選排序 鄰接矩陣1、問題重述破碎圖像的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率雖較高，但效率很低。當(dāng)

4、碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)，有時甚至無法完成。隨著計算機(jī)技術(shù)的發(fā)展，人們試圖開發(fā)破碎圖像的自動拼接技術(shù)，以提高拼接復(fù)原效率。對于一張圖片破碎后的各張圖像的拼接，需建立圖像的拼接復(fù)原模型和算法，并針對附件中的圖像數(shù)據(jù)進(jìn)行拼接復(fù)原。本文主要討論：首先，對于給定原始圖像的碎片，如何對附件1中整齊劃割的圖像進(jìn)行拼接復(fù)原。復(fù)原過程不需要進(jìn)行人工干預(yù)。復(fù)原結(jié)果以圖片形式及表格形式表達(dá)。然后，對于未給定原始圖像的碎片，如何對附件2中整齊劃割的圖像進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請寫出干預(yù)方式及干預(yù)的時間節(jié)點(diǎn)。復(fù)原結(jié)果表達(dá)要求同上。2、問題分析破碎圖像的復(fù)原，最直接而精確的辦法就是人

5、工拼接，但是當(dāng)碎片的數(shù)量巨大時，人工方式就顯得效率低下，有時無法完成。所以，需要考慮把破碎圖像的信息量化，運(yùn)用計算機(jī)技術(shù)來幫助人們進(jìn)行破碎圖像的篩選，必要時加入適當(dāng)?shù)娜斯げ僮?，用以完成破碎圖像的拼接復(fù)原。問題一與問題二都是碎片復(fù)原問題，兩個問題的區(qū)別就在于：問題一中有原始圖，問題二中沒有原始圖，因此兩個問題模型的建立也有一定的差異。 1、問題一題一是對于給定原始圖像的碎片進(jìn)行拼接復(fù)原。首先是利用MATLAB軟件對給的碎片以及原始圖轉(zhuǎn)換成.png格式并進(jìn)行灰度處理。將新處理出來的灰色圖像的大小利用MATLAB中的imresize函數(shù)將原始圖片尺寸改變成，將16個碎片的大小都改變成，這時新的原始圖

6、片就可以均勻的分成16塊大小的碎片。利用imread函數(shù)提取灰度處理后的原始圖片以及附件一中碎片的像素點(diǎn)矩陣參考文獻(xiàn)：1 汪曉銀. 數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗M. 北京：科學(xué)出版社，2009.。將原始圖的像素點(diǎn)矩陣平均分成16個子矩陣，將這16個子矩陣與附件一中給出的16個碎片提取的矩陣進(jìn)行相似的對比，最終確定各碎片在原始圖中的位置。拼接出最后的圖像與原始圖進(jìn)行對比檢驗?zāi)Ｐ偷慕Y(jié)果。充分利用了給出的原始圖，沒有人工干預(yù)。 2、問題二是分析附件二所給的16片圖像碎片，既有橫向切割，又有縱向切割，且16片圖像為規(guī)則的正方形。那么在拼接圖像時需要兩個方面的考慮，即橫向的匹配拼接和縱向的匹配拼接?；叶忍幚砻恳粡?/p>

7、碎片并進(jìn)行像素點(diǎn)矩陣的提取得到。該問題需要進(jìn)行兩層篩選排序，第一層是篩選出在同一行的碎片并進(jìn)行行內(nèi)部的排序。任意選取一張碎片，取出第張碎片的第一列存入矩陣中；取剩余的碎片的最后一列存入到矩陣中，計算與的相似度并從中選出最大值即為在同一曾并且相鄰的兩張碎片。循環(huán)上述過程，找出在同一層的四張圖片并且左右相接關(guān)系拍好。在進(jìn)行第二層的排序，選出已排好的四層的最左碎片的第一行行向量存入以及最后一行行向量存入中，分別進(jìn)行相似度比較，排好上下關(guān)系。綜合第一層和第二層的排序就可以得到最終的復(fù)原圖形。在這一問中，需要人工干預(yù)選出一張碎片讓其他碎片進(jìn)行比對排序。3、問題假設(shè)1、 假設(shè)圖片的碎片四邊都是直線，無折損

8、和缺口；相鄰的兩個碎片可以完全重合。2、 假設(shè)圖片的方向已經(jīng)確定，按照閱讀習(xí)慣，從左向右，自上而下，不考慮碎片圖像的旋轉(zhuǎn)問題。3、 假設(shè)圖片是由原圖4*4切割的；即同一行的碎片等寬，同一列的碎片等長。3、假設(shè)附件一中的16塊碎片大小相近，改變圖片尺寸不會影響最終結(jié)果。4、假設(shè)附件二中的16塊碎片的大小完全一樣。5、假設(shè)原始圖的像素改變一個較小的值不會影響最終的復(fù)原圖。4、符號含義 ： 從第張圖片中提取出來的像素點(diǎn)矩陣（為原始圖）； ： 從處理完的原始圖分割的16張圖中提取出來的像素點(diǎn)矩陣； ： 相似度系數(shù)，兩個等維矩陣的相似程度；5、模型的建立5.1模型建立的準(zhǔn)備1、將附件一和附件二中給出的給

9、圖片有.bmp格式轉(zhuǎn)換成.png格式。對新轉(zhuǎn)換成的圖片進(jìn)行灰度處理即，將給出的彩色圖片轉(zhuǎn)換成灰度圖。灰度圖像在黑色與白色之間還有許多級的顏色深度，這些顏色深度在矩陣中體現(xiàn)在矩陣的元素值在0-255之間。2、對于問題一將第一步中已經(jīng)轉(zhuǎn)化成灰度圖的圖片或碎片進(jìn)行大小的改變。由于附件一給出的碎片的像素各不相同，原始圖不是均勻的分成等大的16份，而且改變的像素相對于整體像素而言很小。所以在不影響最終結(jié)果的前提下我們可以簡單的改變一下灰度處理以后的原始圖以及碎片圖片的大小。使原始圖改變?yōu)橄袼氐幕叶葓D像，使16張不等大的碎片都變成像素的碎片。3、利用MATLAB中的imread函數(shù)算法，從處理完的灰度圖片

10、中提取像素點(diǎn)矩陣存入到中。并且將問題一中的原始圖的像素點(diǎn)矩陣平均分成16份。5.2 問題一模型的建立1、首先需要對給出的圖片進(jìn)行灰度處理，將給出的彩色圖片轉(zhuǎn)換成灰度圖。在MATLAB中灰度處理的函數(shù)為： 2、灰度處理后的圖片需要改變大小方便進(jìn)行相似度的對比。原始圖片不能均等的分割出相等的16份碎片，因此使得碎片的像素不同但是差別不是很大。因此為了方便以后的的相似度對比，我們可以將原始圖以及碎片的大小利用函數(shù)進(jìn)行改變，使得原始圖可以均等的分成16份，而碎片的像素也變成相同的以便以后的對比處理。 在MATLAB中改變圖片的大小的函數(shù)： numrows和numcols分別指定目標(biāo)圖像的高度和寬度。

11、顯而易見， 由于這種格式允許圖像縮放后長寬比例和源圖像長寬比例不相同，因此所產(chǎn)生的圖像有可能發(fā)生畸變。但是由于減少的像素值相對于總的像素值而言比較小，所以這種改變不會對最終的結(jié)果產(chǎn)生影響。3、處理好的碎片中提取出的像素點(diǎn)矩陣與由平均分成的16份兩兩進(jìn)行相似度的計算。用MATLAB中的相似度求取的函數(shù)： ：相似度系數(shù)。其中的與矩陣行數(shù)與列數(shù)都是相同的。求出的相似度系數(shù)大小可以衡量與矩陣的相似程度，從而知道碎片與從原始圖中切割出的圖片的相似程度，確定出碎片在原始圖中的位置。代表完全不相關(guān)，代表完全相關(guān)。的值越小代表兩矩陣之間的相似程度越差，反之則越好2 相關(guān)系數(shù)百度百科 2014年8月20日2。5

12、.3 問題一模型求解 應(yīng)用MATLAB軟件，先用rbg2gry()函數(shù)將彩圖處理成灰度圖像，再用imresize（）函數(shù)改變原始圖以及碎片的大小。最后用imread（）讀取修改大小后的圖片的像素點(diǎn)矩陣=。對原始圖讀取的矩陣進(jìn)行均勻分割成16個子矩陣（等大的碎片）即：=其中、。從附件一中給出的碎片中讀出的矩陣與進(jìn)行相似度計算。例如：附件一中01-01讀出的矩陣與切割出的16個子矩陣進(jìn)行比較（運(yùn)行程序見附件一），得出的結(jié)果如下表一：12345678 -0.0056-0.4115-0.4490-0.26320.6820-0.37020.1484-0.04929101112131415160.8668

13、-0.4008-0.04260.72240.48810.37480.9789-0.0872中是分割原始圖得到的分別與的相似度系數(shù)從表中我們可以看出附件一給出的碎片01-01與切割原始圖得到的碎片中的第十五塊的相似度最大，也就是說碎片01-01在原始圖的第十五塊所在的位置。用同樣的方法可以算出每一個碎片在原始圖中的位置（程序見附見二）。通過對比得到附件一中的碎片與原始圖的切割碎片的對應(yīng)關(guān)系（運(yùn)算結(jié)果見附錄一），得到如下結(jié)果：表二：1234501-1501-0901-1201-0401-0567891001-1101-0701-0801-0201-10111213141501-0601-0301-

14、1301-1401-011601-16根據(jù)表二可以得到圖片的復(fù)原結(jié)果：表格形式：01-1501-0901-1201-0401-0501-1101-0701-0801-0201-1001-0601-0301-1301-1401-0101-16圖片形式：5.4問題二模型的建立 將轉(zhuǎn)化好格式的碎片進(jìn)行灰度處理并提取其像素點(diǎn)矩陣存入中，從提取出來的每一個矩陣的第一列以及最后一列存入到和中。利用（3）式分別進(jìn)行兩兩相似度對比，按行進(jìn)行分類和行內(nèi)部的排序。排好的碎片取出第一行行向量存入以及最后一行行向量存入中，分別進(jìn)行相似度比較，排好上下關(guān)系。具體流程圖如下：5.5問題二模型求解 1、在進(jìn)行按行的分類以及

15、行內(nèi)排序時因為數(shù)據(jù)比較多（具體數(shù)據(jù)見附錄二），取其中的一個為例。例如：取出第一張碎片的第一列存入中，取其他幾張碎片的最后一列存入中。和的相似度如下表所示：表三：02-0202-0302-0402-0502-06-0.75870.7613-0.71160.5089-0.359002-0702-0802-0902-1002-110.9851-0.19290.030702223-0.799902-1202-1302-1402-1502-160.27620.3144-0.53230.42000.5249從表格中篩選出相似度最大，由表格三可以看出第一張碎片像素點(diǎn)矩陣的第一列與第七張碎片像素點(diǎn)矩陣的最后一

16、列相似度最大。所以02-01與02-07在同一層且07在01的左側(cè)。用同樣的方法處理十六張碎片就可以的出如下的對應(yīng)關(guān)系：（其中表格中第一行和第三行表示每張碎片的第一列；第二行與第三行表示沒張碎片的最后一列）表四：02-0102-0202-0302-0402-0502-0602-0702-08最大相似度0.98510.89650.93450.97690.55560.96740.95630.8933對應(yīng)碎片7814102412402-0902-1002-1102-1202-1302-1402-1502-16最大相似度0.83320.70260.97380.91060.53790.77940.985

17、30.9787對應(yīng)碎片4915591323表中數(shù)據(jù)出現(xiàn)重復(fù)的情況，此時進(jìn)行人工干預(yù)。根據(jù)表格中最大相似度可以看出：02-05、02-08、02-09、02-13的最大相似度比較小，因此這四張碎片位于原圖的第一列。行內(nèi)根據(jù)上述表格中的對應(yīng)關(guān)系可以構(gòu)成鄰接矩陣：表五：02-0502-1202-0702-0102-0802-0202-1502-1102-0902-1002-0402-0602-1302-1402-0302-162、進(jìn)行列排序時： 將02-05、02-08、02-09、02-13四張碎片的第一行和最后一行向量分別存入和中，對和進(jìn)行相似度計算得出四張碎片上下鄰接關(guān)系（相似度計算結(jié)果見附錄

18、）。取與的相似度計算結(jié)果表格為例：表六：02-0802-0902-130.98950.67660.4766 從表中可以看出02-05這張碎片的上邊與02-08的下邊的相似度很高，所以第五張與第八張為上下鄰接關(guān)系。根據(jù)其他的上下邊的相似度得出四張圖片的上下鄰接關(guān)系（運(yùn)算結(jié)果見附錄三）通過四張碎片兩兩比較就可以得到四張碎片的上下鄰接關(guān)系為：02-0802-0502-0902-13 對比上述兩步的結(jié)果就可以得出圖片的復(fù)原結(jié)果：表格形式02-0802-0202-1502-1102-0502-1202-0702-0102-0902-1002-0402-0602-1302-1402-0302-16圖片形式

19、6、模型結(jié)果檢驗 本題建立的模型成功的將問題一與問題二的碎片拼接復(fù)原。我們將這一模型應(yīng)用到其他的碎片拼接上，同樣的到了最終的復(fù)原圖。因此本題建立的模型是正確的。7、模型的優(yōu)點(diǎn)與不足7.1、優(yōu)點(diǎn)：（1）、充分的運(yùn)用了計算機(jī)技術(shù)，大大節(jié)約了用人工拼接的時間和資源。用MATLAB軟件碎片進(jìn)行拼接復(fù)原不僅可以節(jié)約人力物力，而且使運(yùn)算變得簡便、快捷。3 姜啟源. 數(shù)學(xué)模型（第四版）M. 北京：高等教育出版社，2010 年. 附錄一：1234567801-01 -0.0056-0.4115-0.4490-0.26320.6820-0.37020.1484-0.049201-020.0287-0.2351-

20、0.4058-0.41170.6845-0.13280.2297-0.231301-03-0.20340.89930.2333-0.09650.68140.4441-0.05150.008901-040.0728-0.1884-0.3906-0.5037-0.4074-0.31610.2746-0.121801-050.0287-0.2351-0.4058-0.41170.9814-0.13280.2297-0.231301-060.0285-0.5170-0.4245-0.20380.0388-0.47060.1194-0.076901-07-0.01650.0421-0.1968-0.26

21、490.2571-0.02400.4013-0.068901-08-0.1759 0.32990.27420.0509-0.23600.5743-0.1240-0.096701-090.0399-0.3469-0.2281-0.2178-0.2470-0.17500.2170-0.110301-10 0.0539-0.4243 -0.3742-0.1410-0.2645-0.33270.0976-0.097901-11-0.0154-0.0515-0.2344-0.3079-0.1339-0.09370.9438-0.064601-12 -0.11210.42840.2016-0.0230-0

22、.41490.9358-0.0857-0.169301-130.7326-0.2026-0.05510.15270.6057-0.14510.0074-0.016701-14 0.1610-0.0989 0.18880.74210.4302-0.0136-0.26840.105601-15-0.01280.01090.10350.10720.0414-0.1550-0.06260.498501-16-0.06070.2204 0.64590.1914-0.21920.2558-0.21590.0673 91011121314151601-010.8668-0.4008-0.04260.7224

23、0.48810.37480.9789-0.087201-020.6797-0.25460.03110.67810.58860.42590.6860-0.243001-03-0.53500.35570.0478-0.4376-0.1734-0.3407-0.4292-0.162201-040.4941-0.34310.28960.41160.94490.40250.52440.024601-050.6797-0.25460.03110.67810.58860.42590.6860-0.243001-060.9872-0.4816-0.12110.77840.46810.48330.87930.0

24、42201-07-0.10830.00240.9451-0.18050.29880.0478-0.03540.123601-08-0.49210.82710.0023-0.4162-0.3331-0.2299-0.4176-0.192601-090.4970-0.24350.02820.46030.38080.82690.3907-0.023801-100.7788-0.3993-0.18290.97220.39200.45590.73290.151001-110.1337-0.13110.43350.10620.30300.22330.17190.074501-12-0.47740.5591

25、-0.0153-0.3337-0.2956-0.1724-0.3833-0.281001-130.0416-0.1808-0.01510.07170.08240.05390.00760.151001-14-0.20400.0364-0.2659-0.1263-0.5123-0.1994-0.26800.136701-15-0.0871-0.0768-0.0617-0.0948-0.1339-0.1024-0.05780.100301-16-0.44910.3043-0.1585-0.3907-0.4130-0.2704-0.46940.1059（表格的行代表由原始圖切割形成的矩陣，列代表碎片提

26、取出來的像素點(diǎn)矩陣）附錄二：02-0102-0202-0302-0402-0502-0602-0702-0802-01NaN-0.75870.7613-0.71160.5089-0.35900.9851-0.192902-020.8965-0.6701NaN-0.42070.50790.0861-0.2748-0.244902-030.0101-0.35030.5184NaN0.2950-0.26640.4979-0.498702-04-0.20940.03980.13090.1808NaN0.04100.6925-0.158002-05-0.1349-0.23610.5556-0.35000

27、.1454NaN0.3426-0.378102-060.3182-0.57200.6258-0.86170.9674-0.7272NaN-0.792602-070.17490.0614-0.3716-0.05520.2862-0.1376-0.2302NaN02-08NaN0.5973-0.48940.6930-0.89330.46130.00710.571702-09-0.44600.7133-0.71580.7429-0.83320.3815-0.22180.807102-100.1235-0.0736-0.00590.0833-0.15740.3784-0.20210.262502-11

28、0.10780.0271-0.42670.4775-0.49380.2746-0.35620.409102-120.08680.1056-0.26220.5845-0.66580.9106-0.02960.411602-13-0.04590.2091-0.34380.2204-0.0767-0.1236-0.10260.359302-140.5441-0.1579-0.37750.08230.02750.2309-0.19390.319802-150.1614-0.50010.9853-0.66590.6060-0.38360.3539-0.761302-16-0.37320.5388-0.6

29、1030.9787-0.84130.6432-0.06960.756902-0102-0202-0302-0402-0502-0602-0702-0802-010.030702223-0.79990.27620.3144-0.53230.42000.524902-020.0657-0.15840.30900.27140.50400.0838-0.17110.087202-03-0.04390.40920.2246-0.3264-0.27660.9345-0.22520.001502-040.00280.9769-0.1628-0.3149-0.10610.4191-0.03410.364602

30、-050.07160.12040.3000-0.5464-0.39110.4837-0.0650-0.294102-06-0.1392-0.05510.88480.2214-0.08550.3547-0.5632-0.545202-07-0.2255-0.32370.03010.95630.5111-0.3179-0.35340.012902-080.08770.0896-0.6807-0.4964-0.1427-0.26970.62140.313302-09NaN-0.1797-0.7172-0.05490.1582-0.53610.54400.304102-100.7026NaN-0.1355-0.0037-0.0981-0.07870.00930.053502-11-0.1426-0.0400NaN-0.3116-0.0216-0.24920.97380.553002-120.33030.1930-0.6006NaN0.0677-0.16380.25640.483102-13-0.5379-0.2318-0.14780.4703NaN-0.25780.08090.145602-14-0.1044-0.0704-0.14630.50360.7794NaN0.