全國大學生數(shù)學建模競賽-B題-碎紙片的拼接復原

2013高教社杯全國大學生數(shù)學建模競賽

承諾書

我們仔細閱讀了《全國大學生數(shù)學建模競賽章程》和《全國大學生數(shù)學建模競賽參賽規(guī)則》（以下簡稱為“競賽章程和參賽規(guī)則”，可從全國大學生數(shù)學建模競賽網站下載）。

我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。

我們知道，抄襲別人的成果是違反競賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。

我們鄭重承諾，嚴格遵守競賽章程和參賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽章程和參賽規(guī)則的行為，我們將受到嚴肅處理。

我們授權全國大學生數(shù)學建模競賽組委會，可將我們的論文以任何形式進行公開展示（包括進行網上公示，在書籍、期刊和其他媒體進行正式或非正式發(fā)表等）。

我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）：B我們的參賽報名號為（如果賽區(qū)設置報名號的話）：

所屬學校（請?zhí)顚懲暾娜何魅A大學參賽隊員(打印并簽名)：1.楊尚安

指導教師或指導教師組負責人(打印并簽名)：（論文紙質版與電子版中的以上信息必須一致，只是電子版中無需簽名。以上內容請仔細核對，提交后將不再允許做任何修改。如填寫錯誤，論文可能被取消評獎資格。）

日期：2013年09月15日

賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：

2013高教社杯全國大學生數(shù)學建模競賽

編號專用頁

賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：

全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：

全國評閱編號（由全國組委會評閱前進行編號）：

碎紙片的拼接復原

摘要

針對問題一，首先將題中所給圖片導入matlab軟件，利用imread函數(shù)得到每張圖片的文字灰度像素矩陣，再取出所有矩陣左、右列，建立像素絕對差擬配模型，得到擬配程度最高的兩幅圖片，進行拼接，出現(xiàn)不合理拼接情況則進行人工干預，最后重復上述過程，完成全部拼接并導出圖像。

針對問題二，首先將全部碎片導入matlab軟件，經過處理得到每張碎片中符號距離碎片上下端的像素位，再根據分類聚類思想，利用excel表格處理，將所有具有“相同”像素位的圖片分為一組，得到11個分組，然后在每一個分組中建立左右連接點數(shù)目最匹配模型，再配合人工干預，將所有碎片拼接為一行圖像，最后將這11行圖像利用問題一中模型拼接為最終圖像并打印結果。

針對問題三，首先建立一種基于K-Means局部最優(yōu)性的高效聚類模型，然后根據模型利用matlab，將所給圖片全部導入分類，分好類并人工調整補充后再利用matlab在每一組分類中利用問題二模型在人工干預情況下得出原始圖像并打印結果。

關鍵詞：像素絕對差擬配模型左右連接點數(shù)目最匹配模型人工干預

1

一、問題重述

破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用。傳統(tǒng)上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數(shù)量巨大，人工拼接很難在短時間內完成任務。隨著計算機技術的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術，以提高拼接復原效率。請討論以下問題：

1.對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結果以圖片形式及表格形式表達（見【結果表達格式說明】）。

2.對于碎紙機既縱切又橫切的情形，請設計碎紙片拼接復原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結果表達要求同上。

3.上述所給碎片數(shù)據均為單面打印文件，從現(xiàn)實情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據。請嘗試設計相應的碎紙片拼接復原模型與算法，并就附件5的碎片數(shù)據給出拼接復原結果，結果表達要求同上。

二、模型假設

1、假設全部碎紙片邊緣光滑

2、假設字符色調一致

3、假設字符間距相同，沒有特殊情況

4、假設除字符外，頁面沒有其他地方具有任何色彩

5、假設英文字符書寫標準，大小寫字號均相同

三、符號說明

ai表示灰色像素矩陣

n表示灰色像素矩陣的列數(shù)

m表示灰色像素矩陣的行數(shù)

i表示第幾個碎片

ai

mn表示某個像素點

b表示某灰度像素點為黑色還是白色

right(i)表示灰色像素矩陣最右邊列

left(k)表示灰色像素矩陣最左邊列

w表示某個碎片灰色像素矩陣最左列與另一個碎片灰色像素矩陣最右列的差的絕對值的和

四、模型建立與求解

4.1問題一

4.1.1問題分析

整體來看，本問題要求利用數(shù)學模型，改原有手動拼接技術為自動或半自動拼接技術，完成題中所給的相應碎紙片的拼接復原工作。

具體操作，考慮所給碎紙片內容僅有漢字或英文，而沒有顏色、大小、字形之分。

2

因此，只能利用碎紙片中相應的文字特征進行操作，考慮碎紙片掃描進入在計算機后是以圖片的形式存在，而圖片又是以像素的情況組成。所以，首先可將圖片導入matlab中，以其像素為基點，得到每個圖片的像素矩陣，每一像素矩陣即可表示該圖片的特征。為了利用圖片像素矩陣完成圖片的拼接，考慮問題一只是將原圖分為了19列，每一列具有1980像素，首先可根據左端全為空白，找出原圖最左一列碎片，然后利用拼接好的圖片最右列像素點去匹配未拼接圖片的最左列像素點，使得拼接最為吻合的即為需要拼接的圖片，然后拼接，再重復上述過程，直到拼接完成。具體操作流程如下：

圖1問題一解答流程圖

4.1.2數(shù)據處理

將圖片導入matlab中，然后編寫程序（具體代碼見附錄1），可得每個碎紙片灰度像素矩陣（碎片000局部像素點如下）。

圖2碎片000局部灰度像素點列

3

4.1.3像素絕對差擬配模型建立

令碎片導入matlab編程計算所得的灰色像素矩陣為：

iia11a12a1iniiia22a2naai21,n72,m1980,1i19

iiaiaam2mnm1

由于碎片像素為72*1980，因此矩陣ai也是72*1980的，矩陣每一列數(shù)據即為碎片相應列像素值，其中每個像素點ai

mn表示此處為黑色或白色，用b表示某灰度像素點為黑色

還是白色，即：

0表示此處為黑色即有圖像b0amn255表示此處在有圖像與沒圖像之間255表示此處為白色即無圖像

其中0m1980,0n72

令right(i)表示灰色像素矩陣最右邊列，那么

a1iniaright(i)2n,n72,m1980,1i19

aimn

令left(k)表示灰色像素矩陣最左邊列，則

ka11kaleft(k)21,n72,m1980,1k19

akm1

令w表示某個碎片灰色像素矩陣最左列與另一個碎片灰色像素矩陣最右列的差的絕對值的和。那么有

wright(i)left(k)

119800i19,0k19

根據上述模型即可確定某一碎片灰度像素矩陣最右邊列與其余未拼接碎片最左邊列的絕對差值，下面討論因差值不同而產生的匹配問題。

1、最左列的確定：當出現(xiàn)某一碎片灰度像素矩陣最左列均為255時，那么說明該碎片為原始圖像的最左列。

2、假設出現(xiàn)w1w2w3wk情況，那么首先將wk對應的碎片與該基準碎片進行拼接，若拼接不合適，這時就需要人工干預，換wk1對應的碎片與基準碎片進行拼接。情況如下：

4

這是不確定的，而進行人工干預選擇wk1對應的碎片后，將會出現(xiàn)下面情況：

這樣就能正確的完成兩個碎片的拼接。

3、假設出現(xiàn)w1w2w3wk情況，這與上述情況相同。因此，人工干預方式及時

間選擇也相同。

4.1.4像素絕對差擬配模型求解

對于附件一中碎片復原，根據上述模型，利用matlab軟件，求解可得008碎片最

255左端矩陣列與006碎片最右端矩陣列均為：，因此，可知008碎片為復原圖最左

255

一個碎片，006碎片為復原圖最右端碎片。其余求得所有最小的距離w的值，根據w的

值，可將碎片進行復原。復原結果如下表，復原圖像見附錄2。

對于附錄二英文復原，與上求解過程雷同，利用matlab可得復原結果如下表，復原圖

4.1.5問題一綜合分析

綜上所述，對于問題一的求解過程，未使用人工干預。

碎片進行復原外，同時對具有相同屬性的其他圖形碎片也進行了復原，效果良好，模型

穩(wěn)定，可推廣到所有只進行豎切的文檔恢復。

5

4.2問題二——中文碎片復原

4.2.1問題分析

綜合分析。由于考慮問題二在問題一的基礎上將碎片分的更加的細小，那么碎片的灰色像素矩陣數(shù)據在原有的基礎上將會變得少很多，考慮使用問題一方法及模型，那么首先就要構造出與問題一相同的19個豎碎片，因此考慮將所有碎片分為19組，但經過試驗分為19組后，由于空白出現(xiàn)太多，在每組中將11個碎片拼接在一起是相當困難的。因此，轉變思想，考慮將所給所有碎片分為11個組，在每個分組中將19張碎片拼接在一起，然后在將11個分組拼接在一起完成最后解答。

具體操作。要想將11*19張圖片分為11組，考慮文字具有行高的性質，分組中所拼接的19張碎片，所有文字具有的行高應該都是相同的。根據這一思想，可將所有碎片導入matlab中，編程計算可得每張碎片符號距離碎片上下端的像素位，并將所有結果導入excel中，然后根據分類與聚類思想，利用excel表格處理，將碎片符號距離碎片上下端的像素位“相同”（不是絕對相等，允許誤差前后波動兩個像素）的點分為一組，對于出現(xiàn)空白位置誤差較大的點可根據單邊距離進行分類與聚類，若根據單邊無法確定具體分入那組，那么就同時分入可能的分組中。分組完成后那么每個分組中的圖片定能拼接為一行圖片，那么我們可建立左右連接點數(shù)目最匹配模型，結合人工干預，將每個分組中圖片拼接在一起。最后利用問題一中模型可將11個分組拼接在一起得到原圖。具體流程如下圖：

圖3問題二解答流程圖

4.2.2數(shù)據處理

將209張碎片導入matlab中，編程得到每張碎片灰色像素矩陣，然后在利用矩陣編寫程序得到每張碎片字符距離上下邊界的像素位，并將其導入excel中（具體代碼見

6

得到像素位上下邊緣距離后可根據上下距離“相等”（不是絕對相等，允許誤差前后波動兩個像素）原則，利用excel表格處理將所給數(shù)據分為11組。其中距上邊緣距離為0，

在每一分組內，再利用matlab編程計算每張碎片左端與右端具有的可連接點數(shù)目（采用四舍五入原則）(具體代碼見附錄7)，下表為上一分組數(shù)據的左右連接點數(shù)目：（其

4.2.3左右連接點數(shù)目最匹配模型[1]

本模型屬于半自動模型，需人工干預，具體步驟如下：

1、選取任一分組左右連接點數(shù)目情況表，觀察左右連接點數(shù)；

2、選取左端連接點數(shù)目為0的碎片作為最左端碎片，并將該圖片作為基準圖片；

3、觀察基準圖片右端連接點數(shù)目，從未拼接圖片左端連接點數(shù)目中找尋與該數(shù)目最接近的碎片，人工控制，觀察是否可連接。若可連接則拼接上，并將新拼接上碎片作為基本圖片，若不可連接，則重新找尋符合要求的碎片，觀察是否可連接；

4、重復3步驟，直到將圖片全部連接完成。

4.2.4模型求解

以上述模型為標準，考慮數(shù)據處理中那行連接過程。首先，尋找19個點鐘左端連

接數(shù)為0的點，找到（94）號碎片，將其作為基準圖片，觀察其右邊連接點數(shù)為4，從其余碎片中找尋發(fā)現(xiàn)（34）（43）（77）左端連接數(shù)均為4，因此，通過人工干預，觀察圖片字樣走勢發(fā)現(xiàn)只有（34）號碎片符合要求，再將（34）號圖片作為基準圖片，其右端連接點數(shù)為7，從未連接碎片中找尋發(fā)現(xiàn)（84）（149）號均為7，同理（84）碎片作為基準圖片，以此類推即可得到該分組圖片排序為：（94）（34）（84）（183）（90）（47）（121）（42）（124）（144）（77）（112）（149）（97）（136）（164）（127）（58）（43）其具體碎片拼接圖形如下：

然后根據上述模型，以相同的辦法結合附錄6中分組情況即可將全部11個分組中

7

圖片的連接情況找出，然后利用問題一中像素絕對差擬配模型即可拼接處原圖，得到原

4.2.5中文碎片恢復綜合分析

由于解決本問題使用的左右連接點數(shù)目最匹配模型，屬于半自動模型。因此，對

干預方式為：終止程序繼續(xù)運行，將程序拼接過程恢復至上一步（出現(xiàn)碎片拼接不吻合時的前一步），然后將程序用于拼接的碎片導出，再恢復程序繼續(xù)運行，找到該步拼接吻合碎片并拼接后，再將導出碎片重新導入繼續(xù)運行程序。

干預時間節(jié)點:干預時間節(jié)點即對每行碎片單獨拼接時，出現(xiàn)碎片拼接不吻合情況時的節(jié)點。

4.3問題二——英文碎片復原4.3.1問題分析

對于附錄四英語碎片恢復，由于英文與漢字寫法不同，英語中弧線居多，而漢字中直線居多。因此，可以采用另一種方式對英文碎片進行拼接，依然考慮問題一中的像素絕對差擬配模型，可首先任意選擇一張基礎碎片，然后利用該模型進行適應性匹配，匹圖4英文碎片復原流程圖

8

4.3.2模型建立

1.1像素絕對值擬配模型

令碎片導入matlab編程計算所得的灰色像素矩陣為：

iia11a12a1iniiia21a22a2nai,n72,m180,1i19iiaim1am2amn

由于碎片像素為72*180，因此矩陣ai也是72*180的，矩陣每一列數(shù)據即為碎片相應列像素值，其中每個像素點ai

mn表示此處為黑色或白色。

令right(i)表示灰色像素矩陣最右邊列，那么

a1iniaright(i)2n,n72,m180,1i19

aimn

令left(k)表示灰色像素矩陣最左邊列，則

ka11kaleft(k)21,n72,m180,1k19

akm1

令w表示某個碎片灰色像素矩陣最左列與另一個碎片灰色像素矩陣最右列的差的絕對值的和。那么有

wright(i)left(k)

1180

其中0i19,0k19

根據上述模型即可確定某一碎片灰度像素矩陣最右邊列與其余未拼接碎片最左邊列的絕對差值，下面討論因差值不同而產生的匹配問題。

1、最左列的確定：當出現(xiàn)某一碎片灰度像素矩陣最左列均為255時，那么說明該碎片為原始圖像的最左列。

2、假設出現(xiàn)w1w2w3wk情況，那么首先將wk對應的碎片與該基準碎片進行拼接，若拼接不合適，這時就需要人工干預，換wk1對應的碎片與基準碎片進行拼接。情況如下：

這是不確定的，而進行人工干預后將會出現(xiàn)下面情況：

9

這樣就能正確的完成兩個碎片的拼接。

3、假設出現(xiàn)w1w2w3wk情況，這與上述情況相同。因此，人工干預方式及時

間選擇也相同。

1.2人工干預

在進行像素絕對值擬配模型計算后，將會得到與基準碎片拼接度最大的幾個碎片，

然后利用這幾個碎片可進行人工干預，具體人工干預模型如下：

1、首先將程序計算得到的擬配程度最大的碎片與基準碎片進行拼接；

2、人工判斷拼接是否合理；

3、若拼接合理則進行下一次擬配模型計算，若拼接不合理則找尋第一步中與基準碎片

擬配差一點的碎片進行拼接；

4、直到找到拼接成功的點才結束本次拼接，并將新拼接上的圖片作為基本圖片利用模

型尋找擬配度最高的碎片，返回第一步。

4.3.3模型求解

結合上述模型1.1及1.2可計算得到問題二英文碎片復原圖表格如下，具體圖像見

4.2.4英文碎片恢復綜合分析

由于英文碎片相似程度高于中文圖片。所以每一次以基準圖片找尋最佳匹配圖形時

很多時候出現(xiàn)多張圖片符合匹配，因此，對此英文碎片的恢復進行了人工干預。恢復此

英文文檔，本模型一共進行了39次人工干預。

干預方式為：終止程序繼續(xù)運行，將程序拼接過程恢復至上一步（出現(xiàn)碎片拼接不

10

吻合時的前一步），然后將該步程序用于拼接的碎片導出，再恢復程序繼續(xù)運行，直到找到與該基準碎片拼接吻合碎片并拼接完成。

干預時間節(jié)點:當出現(xiàn)與基準碎片匹配不吻合時。

4.3問題三

4.3.1問題分析

考慮問題三附錄中所給圖片具有正反面，卻不知每一個序號中a是正面還是b是正面，這也真是問題二英語復原與問題三雙面復原的區(qū)別。因此，問題二中所用的分類與聚類的方法不能完成分組。為了完成分組，我們可考慮使用一種更加嚴密，嚴苛的分類方法，只要分類完成，那么再使用問題二連接圖片的辦法即可實現(xiàn)圖片的復原。

4.3.2模型建立[2]

許多聚類算法的基本框架是搜索與合并。如在層次方法中需要搜索兩個距離最近的類簇然后合并；而基于密度的聚類算法則不斷地搜索高密子區(qū)域，然后利用連通性將其合并到當前聚類結果中。很明顯，搜索過程需要面對整個樣本集合，通常會導致算法低效。如DBSCAN需要測試每個對象是否是核心對象，并對每個核心對象搜索其直接密度可達的對象，如果沒有空間索引的輔助，DBSCAN算法的復雜度為O(n2)。實際上，現(xiàn)有的很多聚類算法已經關注到這個問題，如CURE算法利用采樣方法減小搜索空間，而Chameleon算法則通過圖劃分算法將樣本對象聚類為大量相對較小的子簇。具體到

K-Means算法實質上是一種將聚類視為密度估計問題的概率方法。在概率方法中，假設樣本來自于如下形式的混合模型:

p(x|)jkp(cj)pj(x|j,cj)

式中，(1,,k)是待估計的參數(shù)向量；條件概率密度p(x|j,cj)，稱為分量密度，表示類別j的概率密度形式，且參數(shù)向量j未知；先驗概率p(cj)稱為混合因子。為了簡化問題，K-Means算法進一步假設:(1)每個類別的概率密度形式為球形高斯分布，即j(j,)且122，j,2未知，（2）每個樣本唯一地屬于一個類別；(3)假設所有類別的混合因子相等。于是,混合模型簡化為

112p(x|)max(x|j,,cj)maxexp(||x||)(1)j2d/222j1:kj1:k(2)

該簡化模型可以通過最大似然方法求解,對于觀測樣本X(x1,,xn)X=(x1,?,xn),相應的對數(shù)似然函數(shù)為：

xicj

最大化該對數(shù)似然函數(shù)等價于最小化上式的歐氏距離平方項,即得到K-Means的誤差平方和準則:i1j1l(X)lnp(xi)nln[(2)n2d/2]122k||2||xij(2)

11

Jck

j1xjcj||xij||2(3)

通過迭代優(yōu)化上述的誤差平方和準則,K-Means算法最終可以估計出每個高斯分量的均值向量和協(xié)方差矩陣2I。式中,nj是類簇cj的樣本數(shù)目。

Jc1k2||x||ijndj1xjcjnd2(4)

要獲得更有效的樣本密度估計,Je的值自然是越小越好.但是,Je的值不僅取決于樣本的分類情況,而且與類別數(shù)目k有關.當類別數(shù)目k給定時,Je的值由樣本的分類情況所決定,且存在一個最小值Jkmin對應于最優(yōu)的樣本類別劃分.如果類別數(shù)目k和高斯混合模型假設與實際問題相匹配時,最小值Jkmin必定很小,從而可以很好地近似樣本密度;而如果模型假設不合理,則最小值Jkmin可能依然很大,對樣本分布的近似效果較差。

對于任意形狀的類簇,很明顯不能直接要求數(shù)據分布滿足高斯混合模型的假設,否則會導致最小的誤差平方和Jkmin很大.實際上,高斯混合模型具有很強的表達能力,如果高斯分量密度的數(shù)目k足夠大,則高斯混合模型幾乎可以近似任意一種概率分布。換言之,隨著類別數(shù)目k的增加,相應的Jkmin會減小。簡單證明如下:

類別數(shù)目k的增加,必然導致最終每個類簇的形狀縮小,對應于高斯分量的2減小；而從公式(3)和公式(4)可以得出Jkminnd2,即最小的誤差平方和正比于2；因此,k的增加會導致最小的誤差平方和Jkmin的減小。極端情況下,kn,則每個樣本點都是一個類簇,即Jkmin0,說明此時的經驗誤差為0,但是此時,模型的推廣能力極差。根據統(tǒng)計學習理論,經驗誤差最小并不等于期望誤差最小,經驗風險只有在樣本數(shù)無窮大時才趨近于期望風險.因此,經驗誤差最小不能保證分類器的推廣能力,需要找到經驗風險最小和推廣能力最大的平衡點。同樣,利用足夠多的高斯分量組成的混合模型來描述數(shù)據會導致過擬合的問題,影響模型的推廣能力。因此,在K-MeanSCAN算法中,我們采用過擬合-剪枝的策略進行聚類,即首先使用分量足夠多的高斯混合模型來較好地近似樣本分布,然后通過合并一些高斯分量的剪枝策略來處理過擬合問題。

4.3.3模型求解

根據上述K-Means局部最優(yōu)性的高效聚類模型，利用matlab編程計算后結合人為

4.3.4最終求解

上述模型求解結束后，結合問題二英文求解模型及人工干預時機，可將原圖還原，其具體還原圖像見附錄12，具體還原圖像表格如下：

12

4.3.5問題三綜合分析

對于本問題，由于英語碎片出現(xiàn)正反兩面，分類時情況復雜。因此，恢復原文時進行了多次人工干預。

干預方式：對正反英文碎片進行分類結束后，對未歸類的碎片，采用人工歸類方法，進行多次干預。在每一類中進行碎片拼接時，出現(xiàn)拼接不匹配時，終止程序繼續(xù)運行，將程序拼接過程恢復至上一步（出現(xiàn)碎片拼接不吻合時的前一步），然后將程序用于拼接的碎片導出，再恢復程序繼續(xù)運行，找到該步拼接吻合碎片并拼接后，再將導出碎片重新導入繼續(xù)運行程序。

干預時間節(jié)點：分類完成后，對未進行歸類的碎片進行人工分類時，還有當進行拼接出現(xiàn)拼接碎片不吻合時。

五、模型評價與推廣

5.1模型的優(yōu)點

使用該模型，可以很好的提高工作效率，將原來使用純手工拼接過程變得簡單合理，而且拼接過程全部在計算機上進行，使得結果更加準確，從碎片出發(fā)復原原圖像，以點代面的做法，使思路更加簡單明了；運用matlab計算及繪出圖形，用數(shù)形結合的方法來進行分析，模型思路更加清晰，更有說服力。5.2模型的缺點

模型求解過程中，很多地方使用了人工干預，使得整個過程不能實現(xiàn)完全的智能化。有時的四舍五入也可能是結果有些偏差。5.3模型的推廣

該題所建模型求解的是與相似圖形的匹配問題，在實際生活中，與圖像相似，匹配，識別相關的問題，均可以使用該模型進行運算。

對于本題問題三，我們也可從另一方面入手考慮，由于每個碎片為180*72像素的，所含信息量較少，因此，使用問題一的方法直接求解不行。如果我們在保證圖片大小不變的情況下，增加圖片的像素或者尋求另一種模式使碎片分組更加細，那么直接運用方法一求解規(guī)則碎片復原將變得相當?shù)娜菀住?/p>

六、參考文獻

[1]/view/5c6a7fc8102de2bd96058886.html.2013.09.15[2]/1000-9825/19/1683.pdf.2013.09.15

14

七、附錄

附錄1，使用軟件名稱：matlab(daima1)A=imread(‘附件1\000.bmp’);%區(qū)圖片的相對路徑

附錄2，使用軟件名稱：matlab(daima2)functionPho1

clc

clearall

A=imread(‘附件1\000.bmp’);%區(qū)圖片的相對路徑

[m,n]=size(A);

pho=ones(m,1)*255;

sort=zeros(1,19);

x=0;

15

left=zeros(m,1);

right=zeros(m,1);

local=0;

Used=zeros(19,1);

B=zeros(1,19);

fori=1:19%首先找到最左兩邊的碎片

ifi<11

str=strcat(‘附件1\00’,num2str(i-1),’.bmp’);

else

str=strcat(‘附件1\0’,num2str(i-1),’.bmp’);

end

a=imread(str);

left=a(:,1);%取第一列

iflength(find(left>250))>1700%當?shù)谝涣兴袛?shù)據為白色時，就定義為這個碎片在圖片的最左邊

pho=cat(2,pho,a);

Used(i)=1;

x=x+1;%圖片的順序

sort(x)=i-1;

right=a(:,n);%取最后一列

break;

end

end

fori=1:18

min=999999999999999999;

fork=1:19

ifUsed(k)~=1

ifk<11

str=strcat(‘附件1\00’,num2str(k-1),’.bmp’);%拼接圖片路徑

else

str=strcat(‘附件1\0’,num2str(k-1),’.bmp’);

end

a=imread(str);

left=a(:,1);%取第一列

distance=abs(right-left);

temp=sum(sum(distance));

iftemp<min

max=temp;

local=k;

end

end

ifUsed(local)~=1&&k==19

iflocal<11

str1=strcat(‘附件1\00’,num2str(local-1),’.bmp’);

else

str1=strcat(‘附件1\0’,num2str(local-1),’.bmp’);

end

goal=imread(str1);

pho=cat(2,pho,goal);%將得到的碎片加入到圖片中

right=goal(:,n);%取右邊

16

Used(local)=1;%將這個碎片設置為已經使用x=x+1;%圖片的順序

sort(x)=local-1;

end

end

end

pho(:,1)=[];

imshow(pho)

imwrite(pho,’附件1\true1.bmp’,’bmp’)

sort

end

附件3，使用軟件名稱：matlab(daima3)

17

%--------附件一拼接---------%

functionPho2

A=imread(‘附件2\000.bmp’);%取圖片的相對路徑

[m,n]=size(A);

pho=ones(m,1)*255;

sort=zeros(1,19);

x=0;

left=zeros(m,1);

right=zeros(m,1);

local=0;

Used=zeros(19,1);

fori=1:19%首先找到最左兩邊的碎片

ifi<11

str=strcat(‘附件2\00’,num2str(i-1),’.bmp’);

else

str=strcat(‘附件2\0’,num2str(i-1),’.bmp’);

end

a=imread(str);

left=a(:,1);%取第一列

iflength(find(left>250))>1900%當?shù)谝涣兴袛?shù)據為白色時，就定義為這個碎片在圖片的最左邊

pho=cat(2,pho,a);

Used(i)=1;

x=x+1;%圖片的順序

sort(x)=i-1;

right=a(:,n);%取最后一列

break;

end

end

x

fori=1:18

min=999999999999999;

fork=1:19

ifUsed(k)~=1

ifk<11

str=strcat(‘附件2\00’,num2str(k-1),’.bmp’);%拼接圖片路徑

else

str=strcat(‘附件2\0’,num2str(k-1),’.bmp’);

end

a=imread(str);

left=a(:,1);%取第一列

distance=abs(right-left);

temp=sum(sum(distance));

iftemp<min

min=temp;

local=k;

end

end

ifUsed(local)~=1&&k==19

iflocal<11

str1=strcat(‘附件2\00’,num2str(local-1),’.bmp’);

else

18

str1=strcat(‘附件2\0’,num2str(local-1),’.bmp’);end

goal=imread(str1);

pho=cat(2,pho,goal);%將得到的碎片加入到圖片中right=goal(:,n);%取右邊

Used(local)=1;%將這個碎片設置為已經使用x=x+1;%圖片的順序

sort(x)=local-1;

end

end

end

pho(:,1)=[];

imshow(pho)

imwrite(pho,’附件2\true.bmp’,’bmp’)

sort

附錄4，使用軟件：matlab（daima4）

%-----對應圖片上下邊緣的高度---------%

functionread_height

clc

TotleUD=zeros(3,208);

TotleLR=zeros(3,208);

Up_H=zeros(2,208);

Dw_H=zeros(2,208);

L_H=zeros(2,208);

R_H=zeros(2,208);

A=imread(‘附件3\003.bmp’);

[m,n]=size(A);

temp=ones(1,n)*255;

temp1=ones(m,1)*255;

fori=1:209

Up_height=0;

Dw_height=0;

L_height=0;

R_height=0;

ifi<11

str=strcat(‘附件3\00’,num2str(i-1),’.bmp’);elseifi>=11&i<101

str=strcat(‘附件3\0’,num2str(i-1),’.bmp’);else

str=strcat(‘附件3\’,num2str(i-1),’.bmp’);end

a=imread(str);

%計算上方高度

k=1;

whilea(k,:)==temp

Up_height=Up_height+1;

k=k+1;

end

%計算下方高度

19

x=m;

whilex~=0&a(x,:)==tempDw_height=Dw_height+1;x=x-1;end

%計算左邊高度forj=1:n

ifa(:,j)==temp1

L_height=L_height+1;else

break;endendj=n;

whilej~=0&a(:,j)==temp1;R_height=R_height+1;j=j-1;end

Dw_H(1,i)=i-1;

Dw_H(2,i)=Dw_height;Up_H(1,i)=i-1;

Up_H(2,i)=Up_height;L_H(1,i)=i-1;

L_H(2,i)=L_height;R_H(1,i)=R_height;R_H(2,i)=R_height;TotleUD(1,i)=i-1;

TotleUD(2,i)=Up_height;TotleUD(3,i)=Dw_height;TotleLR(1,i)=i-1;

TotleLR(2,i)=L_height;TotleLR(3,i)=R_height;end

TotleUD;TotleLR;

%xlswrite(‘附件3\上下邊界.xls’,TotleUD);%xlswrite(‘附件3\左右邊界.xls’,TotleLR);End

20

21

附錄7，使用軟件：matlab(daima5)%計算左右節(jié)點clc;clearall;

22

A=imread(‘附件3\000.bmp’);

[m,n]=size(A);

countTotle=0;%黑色點的總個數(shù)

countSame=0;%相同點的個數(shù)

Used=zeros(209,1);

x=0;

pho=ones(m,n)*255;

sort=zeros(1,209);

local=0;

Left=zeros(1,209);

Right=zeros(1,209);

b=zeros(209,1);

fori=1:209;

ifi<11

str=strcat(‘附件3\00’,num2str(i-1),’.bmp’);

elseifi>=11&&i<101

str=strcat(‘附件3\0’,num2str(i-1),’.bmp’);

elsei>=101

str=strcat(‘附件3\’,num2str(i-1),’.bmp’);

end

a(:,:,i)=imread(str);%第i張圖片的像素矩陣

left(:,1,i)=a(:,1,i);%第i張圖片的左邊第一列

right(:,1,i)=a(:,n,i);%第i張圖片的右邊第一列

Left(1,i)=length(find(left(:,1,i)==0))/3.2;

Right(1,i)=length(find(right(:,1,i)==0))/3.2;

end

Left

Right

left(:,1,1)’;

right(:,1,1)’;

pic=cat(2,a(:,:,1),a(:,:,2));

%imshow(pic)

附錄8，使用軟件：matlab所有節(jié)點左右節(jié)點數(shù)目

Left=

Columns1through9

7.18759.37505.31251.25000.93753.12503.437501.8750Columns10through18

2.18759.06250.937512.18755.000002.50009.68758.1250Columns19through27

5.312513.12502.81252.18755.62500.937511.25008.437517.1875Columns28through36

13.75007.187503.43755.00003.125010.31254.68752.1875Columns37through45

3.75008.125007.187510.625012.500012.500011.87507.5000Columns46through54

9.06250.31254.687513.437502.18755.000014.062512.5000Columns55through63

5.93754.06252.50002.812516.25001.87503.437500Columns64through72

5.00005.31254.68752.1875010.62505.62503.12500Columns73through81

23

5.62502.81254.375012.18756.87503.43752.18756.87500Columns82through90

1.87507.50001.25004.06255.31252.81256.56254.37500Columns91through99

8.75005.62504.375012.500008.43754.375015.31254.0625Columns100through108

8.43756.25004.687506.87500.93752.187505.3125Columns109through117

5.93752.812515.31251.25005.31256.25002.500010.62506.5625Columns118through126

1.56250.62501.87502.18753.43752.81250.93756.87500Columns127through135

5.00003.75004.062508.750019.37502.50006.87501.5625Columns136through144

01.875013.12500.31251.25001.56254.37509.06250Columns145through153

9.06251.87500.62505.00005.00006.56254.37503.437512.1875Columns154through162

2.50004.06253.125010.31256.56253.12504.06256.56251.8750Columns163through171

3.43751.56259.37505.31254.06250.625009.06259.0625Columns172through180

3.75004.06252.812511.87501.25002.18754.687514.06258.4375Columns181through189

3.750012.8125000.62503.12507.50003.12505.0000Columns190through198

5.31254.06259.68758.12504.37503.43753.12506.56254.0625Columns199through207

5.62501.87509.68758.125012.187515.31253.12503.750010.0000Columns208through209

0.62504.3750

Right=

Columns1through9

15.93754.37504.06253.75004.06252.18754.68755.31251.5625Columns10through18

2.18751.25008.43751.875003.43756.56250.62500Columns19through27

02.187512.50002.81251.25004.68752.81251.87505.0000Columns28through36

3.43755.31253.750011.25006.87502.187514.68754.06252.1875Columns37through45

012.81259.06255.93752.500012.18755.625009.6875Columns46through54

22.50001.87503.12505.00004.37508.43759.68753.12503.4375Columns55through63

4.68757.18753.43758.43753.4375003.43758.7500Columns64through72

6.25000.625