上傳人：活***

認(rèn)證信息

認(rèn)證類型：機(jī)構(gòu)認(rèn)證

認(rèn)證主體：寧夏凱米世紀(jì)網(wǎng)絡(luò)科技有限公司

IP屬地：寧夏

統(tǒng)一社會(huì)信用代碼/組織機(jī)構(gòu)代碼

91640100MA774ECW4K

IP屬地：寧夏 上傳時(shí)間：2021-10-18 格式：DOC 頁數(shù)：40 大?。?.68MB 積分：15 舉報(bào) 版權(quán)申訴

1、碎紙片的拼接復(fù)原摘要破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。但是人工完成效率很低，所以引入計(jì)算機(jī)復(fù)原，計(jì)算機(jī)雖然準(zhǔn)確率不及人工高，但是可以大大減輕工作強(qiáng)度。本論文主要是對(duì)紙張形狀為矩形切割規(guī)范并且紙張上的文字標(biāo)準(zhǔn)的碎紙片的拼接復(fù)原的研究。問題一：首先根據(jù)圖片的灰度矩陣找出第一張（最左側(cè)）圖片，根據(jù)小差值優(yōu)先匹配依次排出相鄰圖片。碎紙片復(fù)原后的順序如附件一、二所示。問題二：首先根據(jù)圖片的灰度矩陣最左側(cè)n列灰度值求和最大，可找出第一列（最左側(cè)）圖片，共11張。根據(jù) “行間”的位置特征作為凝聚點(diǎn)進(jìn)行聚類分析，將所有圖片分為11類，即11行。應(yīng)用小差值優(yōu)先匹配

2、將這每行的圖片進(jìn)行拼接，得到11個(gè)行圖片，再次應(yīng)用小差值優(yōu)先匹配把這11個(gè)行圖片拼接成完整的圖片。碎紙片復(fù)原后的順序如附件三、四所示。問題三：同問題二方法一致，找出第一列（最左側(cè)）圖片（正反兩面共有22張圖片），將這些“行間”的位置特征作為凝聚點(diǎn)進(jìn)行聚類分析，所有的圖片分為11“大行”，將這些圖片配對(duì)的正反面進(jìn)行上邊緣“粘接”處理，按照小差值優(yōu)先匹配將這每行的粘接形成的19圖片（如圖一所示）進(jìn)行拼接，得到11個(gè)行圖片之后，再次應(yīng)用小差值優(yōu)先匹配把這11個(gè)行圖片拼接成完整的圖片。碎紙片復(fù)原后的順序如附件五所示。觀察上述三個(gè)問題的處理方法可知，三個(gè)問題的解決辦法主干思想完全相同，都是小差值優(yōu)先匹配

3、解決，并且清晰簡(jiǎn)練。但是由于問題的逐漸深入和復(fù)雜程度的增加，僅靠這一個(gè)簡(jiǎn)單的方法并不能在實(shí)際中解決問題，于是增加約束條件減小搜索范圍，如：找出“行間”位置，并作為凝聚點(diǎn)進(jìn)行聚類分析，然后就可以很大程度上減小出錯(cuò)的概率。關(guān)鍵詞：聚類分析、matlab r2012a、小差值優(yōu)先匹配、灰度矩陣 1、問題重述破碎文件的拼接在司法物證復(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ā)展，人們?cè)噲D開發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。請(qǐng)討論以下問題：（1）. 對(duì)

4、于給定的來自同一頁印刷文字文件的碎紙機(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ì)碎紙片拼接復(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、決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。請(qǐng)嘗試設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果，結(jié)果表達(dá)要求同上。2、問題分析分析本問題可知，第一問是解決此類問題的基本方法，第二問及第三問相比第一問逐漸變得復(fù)雜，但主要解決思路與第一問相同，只是在第一問的基礎(chǔ)上需要應(yīng)用其他方法縮小搜索范圍，但主體方法并未改變。針對(duì)問題一：對(duì)于給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法。在matlab軟件12中應(yīng)用imread函數(shù)讀取附件一及附件二中的圖片，可以獲得相應(yīng)的灰度矩陣，從矩陣中可以清楚地看到圖片中每個(gè)像素的灰度值。觀察

6、圖片邊緣及灰度矩陣邊緣可以得出：圖片被切割后會(huì)在這張圖片被切割兩側(cè)生成相似的兩個(gè)列矩陣，可以猜測(cè)這兩個(gè)列矩陣相似程度越高則這兩張圖片可以拼接復(fù)原的概率就越大。為表示兩列矩陣的相似程度，對(duì)這兩列矩陣進(jìn)行對(duì)應(yīng)行相減取絕對(duì)值最后求和，所求得的和越小兩矩陣越相似即復(fù)原概率越大。最左邊一張圖片的最左側(cè)全為空白，即最左側(cè)矩陣所有行求和值最大，可以得到最左側(cè)的圖片，然后可以拼接出整張圖片。針對(duì)問題二：對(duì)于碎紙機(jī)既縱切又橫切的情形，請(qǐng)?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法。方法一：應(yīng)用第一問中的小差值優(yōu)先匹配，求出所有圖片邊緣矩陣的對(duì)應(yīng)行相減取絕對(duì)值最后求和，然后逐個(gè)比較，此時(shí)會(huì)發(fā)現(xiàn)由于圖片小且圖片中字?jǐn)?shù)較少，灰度矩陣

7、所給出的信息就會(huì)比較少，并且應(yīng)用小差值優(yōu)先匹配所求和會(huì)有大量數(shù)值相差不是很大圖片出現(xiàn)，出現(xiàn)過多的候選項(xiàng)，這會(huì)對(duì)判斷哪張圖片可以復(fù)原產(chǎn)生很大的影響，甚至?xí)霈F(xiàn)無法選擇，因?yàn)椴糠謭D片是正好沒有切割文字，此時(shí)計(jì)算機(jī)是無法判斷哪張可以復(fù)原的，就需要對(duì)方法一進(jìn)行補(bǔ)充提供更多的約束條件或是進(jìn)行人工干預(yù)，所以得出了以下的方法二。方法二：此方法主體方法也是應(yīng)用小差值優(yōu)先匹配，針對(duì)上述出現(xiàn)過多的候選項(xiàng)情況，觀察附件三及附件四中的圖片會(huì)發(fā)現(xiàn)，雖然所給的圖片小且文字?jǐn)?shù)目少，但是觀察可知這些圖片全部大小一致但是“行間”（兩行文字之間的空白處）所出現(xiàn)的位置是不同的，記錄這幾行的位置，將其余圖片所生成的矩陣對(duì)比，若特殊的

8、幾行出現(xiàn)在相同的位置，則可將這些圖片分為一“大行”（這些圖片的行間距出現(xiàn)的位置相同）。然后將“大行”內(nèi)的圖片應(yīng)用第一問中的小差值優(yōu)先匹配進(jìn)行拼接，可將這些行拼出。緊接著人工干預(yù)將所得的行分為11行（如果所得到的行多余11行），最后將這是11行轉(zhuǎn)置成11列，按照第一問的方法進(jìn)行即可拼出完整的圖片。針對(duì)問題三：該問題比第二問更復(fù)雜，但是更貼合于實(shí)際情況，即實(shí)用性很強(qiáng)。仔細(xì)觀察附件5中的圖片，可以觀察到，每張圖片的a面和b面，“行間”所處的位置是相同的。這樣，可以“行間”所處的位置進(jìn)行聚類，聚為11類，同第二問方法一樣，先分行，然后再每行拼接出來，轉(zhuǎn)置成列，應(yīng)用小差值優(yōu)先匹配將這11列拼接，即可得出

9、完整圖片。但是行分完后，猜測(cè)每行有英語碎紙片，由于英文字母本身所能獲得的信息量較少，且每行的圖片過多，在按照第二種方法處理時(shí)，會(huì)出現(xiàn)過多接近值，甚至?xí)霈F(xiàn)錯(cuò)誤排列， 再仔細(xì)觀察及閱讀題意可以得出，一行圖片的正面確定且結(jié)果正確時(shí)，反面是自然形成的，這樣就只用到了一面數(shù)據(jù)量，若此時(shí)將兩張圖片的正反面以上邊緣相接展開，形成高度是原高兩倍的行圖片，這樣就會(huì)同時(shí)應(yīng)用到正反兩面的邊緣數(shù)據(jù)，提高篩選時(shí)的準(zhǔn)確率。同理，在每一行都拼完后，在進(jìn)行“大行”相拼的時(shí)候，可以將這個(gè)行的正反兩面以右邊緣相接展開，又會(huì)形成長(zhǎng)度是原長(zhǎng)兩倍的行，也同時(shí)應(yīng)用到正反兩面的邊緣數(shù)據(jù)提高篩選時(shí)的準(zhǔn)確率。得到圖形如一所示：a a（b）a

10、（b）a（b）a（b）bb（a）b（a）b（a）b（a）圖一（正反面粘接）按照如上圖片正反連接在一起后應(yīng)用小差值優(yōu)先匹配加以適當(dāng)?shù)娜斯じ深A(yù)，拼出完整行圖片。這樣可以確定11張行圖片，將這11張圖片轉(zhuǎn)置成11個(gè)列圖片，之后再次應(yīng)用小差值優(yōu)先匹配拼出完整圖片。3、模型假設(shè)（1）假設(shè)所有復(fù)原圖片中位于同一面的文字的行間距相同。（2）假設(shè)頁面上的文字全部是統(tǒng)一字體且頁面排版相同。（3）假設(shè)頁面整潔干凈無黑點(diǎn)等干擾項(xiàng)。（4）第一列文字距離紙張左邊緣的距離大于兩相鄰文字間的距離。4、符號(hào)說明及名詞定義符號(hào)說明：k: 第k張圖片n: 圖片具有n行i： 兩張圖片邊緣拼接能力，值越小，越容易拼接。：第k張圖片所

11、對(duì)應(yīng)的灰度矩陣。; 矩陣的第i行第j列所對(duì)應(yīng)的元素。名詞定義：“行間”： 相鄰兩行文字之間固定存在的空白區(qū)域，即文字排版時(shí)所設(shè)計(jì)的隔開每行的空白區(qū)域。它與這行中是否存在文字無關(guān)。小差值優(yōu)先匹配： 在n張圖片中取出每張圖片的最左和最右側(cè)的兩個(gè)列灰度矩陣，然后任一兩張圖片進(jìn)行下列運(yùn)算：第一張圖片的最右側(cè)矩陣與第二張圖片的最左側(cè)灰度矩陣對(duì)應(yīng)行相減，取絕對(duì)值最后求和，這個(gè)值越小，表明這兩張圖片邊緣灰度值越接近，即兩張圖片的邊緣小差值優(yōu)先匹配，拼接的概率越大。5、模型建立與求解5.1第一問模型建立與求解：對(duì)于給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法。在matl

12、ab軟件中應(yīng)用imread函數(shù)1 2讀取附件一中的19張圖片，得到19個(gè)灰度矩陣。建立目標(biāo)函數(shù)為：（1） 按算法如下：（1） 找出第一張圖片： （2）因?yàn)橐粡埻暾垙埳系淖煮w第一列都會(huì)距離頁面最左端有一定的距離以方便閱讀和美觀，所有最左邊的圖片最左端會(huì)對(duì)應(yīng)一列全白，即所生成的矩陣第一列全為255，此時(shí)對(duì)該矩陣所有行求和會(huì)得到最大值504900。應(yīng)用以上結(jié)論，對(duì)所有圖片的灰度矩陣第一列進(jìn)行求和，所得值最大的即為最左邊一張照片，即 。對(duì)所有圖片的灰度矩陣第一列進(jìn)行求最大值的結(jié)果為第008張圖片為最左邊一張圖片。（2） 找出第k張照片： （3）觀察圖片邊緣及灰度矩陣邊緣可以得出：圖片被切割后會(huì)在這張

13、圖片被切割兩側(cè)生成兩個(gè)相似的列矩陣，即這兩個(gè)列矩陣相似程度越高則這兩張圖片可以拼接復(fù)原的概率就越大，這里將此方法命名為小差值優(yōu)先匹配。為比較圖片邊緣相似程度，將所有圖片的最左側(cè)及最右側(cè)矩陣取出，即和對(duì)這兩列矩陣進(jìn)行對(duì)應(yīng)行相減取絕對(duì)值最后求和，所求得的和越小兩矩陣越相似，即匹配概率越大，即（k=2）。3此時(shí)和最小的即為第2張圖片。以此類推，應(yīng)用程序1即可求出第3、4、519張圖片。順序如表格一所示：8141215310216145913181171706表格一（3）matlab拼接19張圖片由程序2所求出圖片順序在matlab中用imtool函數(shù)4將圖片按順序合并。完整圖片的排列順序即完整圖如附

14、件一所示。第一問中的英文圖片按上述（1）（2）（3）操作即可得出合并后的圖片。完整圖片的排列順序即完整圖如表格二所示。表格二3627151811051913108121417164運(yùn)行程序二即為按照上述步驟操作后得出的完整圖片。5.2第二問模型建立與求解： 對(duì)于碎紙機(jī)既縱切又橫切的情形，請(qǐng)?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對(duì)附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。根據(jù)第一問模型改進(jìn)后建立第二問目標(biāo)函數(shù)為： （4）要解決這個(gè)問題，要將這些碎紙片首先按照一定特征聚類，縮小搜索范圍，應(yīng)用到的這種方法叫做聚類分析。5.2.1聚類分析5：聚類分析(cluster analysis)

15、是一組將研究對(duì)象分為相對(duì)同質(zhì)的群組(clusters)的統(tǒng)計(jì)分析技術(shù)。 聚類分析區(qū)別于分類分析(classification analysis) ，后者是有監(jiān)督的學(xué)習(xí)。選取若干個(gè)樣品作為凝聚點(diǎn)，計(jì)算每個(gè)樣品和凝聚點(diǎn)的距離，進(jìn)行初始分類，然后根據(jù)初始分類計(jì)算其重心，再進(jìn)行第二次分類，一直到所有樣品不再調(diào)整為止。動(dòng)態(tài)聚類法計(jì)算簡(jiǎn)單，分類迅速，占用計(jì)算機(jī)內(nèi)存少，特別是當(dāng)樣品數(shù)較大時(shí)，采用動(dòng)態(tài)聚類法比較有利；但動(dòng)態(tài)聚類法的分類結(jié)果與最初凝聚點(diǎn)的選擇有關(guān)，有較大的不確定性。聚類過程如圖二所示：選凝聚點(diǎn)初始分類分類是否合理最終分類修改分類圖二本題中所應(yīng)用到的聚類方法為：最短距離法，此論文中，為便于理解，將

16、最短距離理解為灰度值接近，即兩邊緣小差值優(yōu)先匹配，記為小差值優(yōu)先匹配。以下用表示樣品與之間距離，用表示類與之間的距離。定義類與之間的距離為兩類最近樣品的距離，即 （4）設(shè)類與合并成一個(gè)新類記為，則任一類與的距離是： （5）最短距離法聚類的步驟如下：（1）定義樣品之間距離，計(jì)算樣品兩兩距離，得一距離陣記為，開始每個(gè)樣品自成一類，顯然這時(shí)。（2）找出的非對(duì)角線最小元素，設(shè)為，則將和合并成一個(gè)新類，記為，即。（3）給出計(jì)算新類與其它類的距離公式： （6）將中第p、q行及p、q列用上面公式并成一個(gè)新行新列，新行新列對(duì)應(yīng)，所得到的矩陣記為。（4）對(duì)重復(fù)上述對(duì)的（2）、（3）兩步得；如此下去，直到所有的元

17、素并成一類為止。如果某一步中非對(duì)角線最小的元素不止一個(gè)，則對(duì)應(yīng)這些最小元素的類可以同時(shí)合并。最短距離法也可用于指標(biāo)（變量）分類，分類時(shí)可以用距離，也可以用相似系數(shù)。但用相似系數(shù)時(shí)應(yīng)找最大的元素并類，也就是把公式中的min換成max。按算法解決步驟如下：5.2.2對(duì)于碎紙機(jī)既縱切又橫切的情形，請(qǐng)?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法，觀察附件三中的圖片，可以發(fā)現(xiàn)這些圖片存在以下兩個(gè)規(guī)律：（1）一些圖片的整個(gè)左端有很大一部分空白，初步參測(cè)這幾張圖片為整張圖片的第一列。將附件三中的209張圖片用matlab用imread函數(shù)讀出209個(gè)灰度矩陣，因?yàn)檫@些圖片的整個(gè)左端有很大一部分空白，所以這幾張圖片前11列都

18、是灰度值255，對(duì)這11列所有的元素進(jìn)行求和可得255*11*180=504900，然后對(duì)所有圖片的前11列求和78，并篩選出數(shù)值為504900的所有圖片， （7）并將這些圖片作為第一列。篩選結(jié)果如下007、014、029、038、049、061、071、089、094、125、168（.bmp）這11張圖片構(gòu)成了完整圖片的第一列。（2）這209圖片全部大小一致但是行間距（兩行文字之間的空白）所出現(xiàn)的位置是不同的，“行間”出現(xiàn)的位置不同且只有固定的幾種。表現(xiàn)在灰度矩陣中就是整個(gè)同一行的圖片會(huì)出現(xiàn)相同的某幾行數(shù)值全為255，對(duì)這些矩陣進(jìn)行行求和，利用matlab將值為19*255=4854的行記

19、為1 9，值小于4854的記為0，可以清晰的得出“行間”的位置，在此處記錄兩個(gè)完整的“行間”，利用這些位置特征將這209張圖片分為11類，即11“大行”。matlab實(shí)現(xiàn)分“大行”過程：將附件3中求出的209圖片，全部進(jìn)行每行求和，并利用matlab將值為19*255=4854的行記為1，值小于4854的記為0，可以得出這209張圖片的“行間”位置記錄矩陣。將以上11張圖片的“行間”位置作為參考，利用這些圖片分成11行。由于圖片較小從中能獲取的數(shù)據(jù)量較少，所以再用小差值優(yōu)先匹配后會(huì)的發(fā)現(xiàn)拼錯(cuò)的概率比較大，所以在此對(duì)模型進(jìn)行改進(jìn)，同上，找出圖片最右側(cè)一列，然后從右往左開始拼接，最后將這兩列圖片合

20、并選取各種準(zhǔn)確的排列，如此，可以降低排列出錯(cuò)的概率。（3）對(duì)這11行中的19張圖片，進(jìn)行行方向上的拼接。應(yīng)用上述聚類分析最短距離分析中提出的小差值優(yōu)先匹配進(jìn)行拼接，由于紙片較小可以獲得的信息量非常少，盡管已經(jīng)將范圍縮小到19張，但是仍然會(huì)出現(xiàn)拼接錯(cuò)誤出現(xiàn)如下圖一所示情況：圖一 然后，按照上述方法找出最右側(cè)圖片，從右往左拼接圖片如圖二所示圖二觀察可以看出圖一圖二均出現(xiàn)了四處拼接錯(cuò)誤，但兩張可以拼出完整的一行，即此時(shí)需要進(jìn)行人工干預(yù)，干預(yù)方式：比較兩張圖片，排出正確的順序。后面生成的圖片中有少量會(huì)出現(xiàn)錯(cuò)誤，干預(yù)方式及干預(yù)時(shí)間與上述圖片相似，這里不再重復(fù)敘述（4）對(duì)折11張“行紙片”進(jìn)行列方向上的拼

21、接。對(duì)這是一個(gè)行紙片轉(zhuǎn)置又形成11個(gè)列紙片，再次應(yīng)用小差值優(yōu)先匹配，即可將這11列紙片拼接為完整的一張紙。完整圖片的排列順序即完整圖如附件三所示。運(yùn)行程序四即為按照上述步驟操作后得出的完整圖片。（5）附件4中的英文紙片重復(fù)上述步驟（1）（2）（3（4），即可得出復(fù)原后的圖片。完整圖片的排列順序即完整圖如表格三和表格四所示。表格三495465143186257192178118190951122129289118814461197867699916296131796311616372617720523616810076621423041231471915017912086195261871838

22、148461612435811891221031301938816725891057414128315982199135127316020316913439315110711517694348418390471214212414477112149971361641275843125131821091971618411018766106150211731571812041391452964111201592180483775554420610104981721715972081381581266817545174013753569315370166321967115683132200178033

23、2021981513317020585152165276089146102154114401512071551401851081174101113194119123表格四19107501115419018400210418006410600414903220406503906714720114817019619809411316407810309108010102610000601702814608605110702904015818609802411715000505905809203003704612701919409314108812112610515511417618215102205

24、720207116508215913900112906313815305303812312017508505016018709720303102004110811613607303620713501507604319904517307916117914320802100704906111903314216806216905419213311818916219711207008406001406817413719500804717215619602309912209018510913218109506916716316618811114420600313003401311002502717817

25、1042066205010157074145083134055018056035016009183152044081077128200131052125140193087089048072012177124000102115運(yùn)行程序五即為按照上述步驟操作后得出的完整圖片。（見附錄）5.3第三問模型建立與求解：上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實(shí)情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復(fù)原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。請(qǐng)嘗試設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法根據(jù)前兩問的模型改進(jìn)優(yōu)化后建立第三問目標(biāo)函數(shù)： （8） （9） () （10）()（11）該問題

26、比第二問更復(fù)雜，但是更貼合于實(shí)際情況，所以實(shí)用性很強(qiáng)。仔細(xì)觀察附件5中的圖片，可以觀察到，每張圖片的a面和b面，“行間”所處的位置是相同的，對(duì)每一張圖片的a、b面讀取灰度矩陣，對(duì)比可知“行間”出現(xiàn)的位置相同。即在不知正反面的情況下，可先將正反面分為同一行。按算法解決步驟如下：（1）找出最左側(cè)一列的圖片觀察附件。所有最左邊的圖片最左端會(huì)對(duì)應(yīng)一列全白，即所生成的矩陣通過灰度矩陣圖可知最多前11列全為255，此時(shí)對(duì)該矩陣所有行求和會(huì)得到最大值504900。應(yīng)用以上結(jié)論，對(duì)所有圖片的灰度矩陣第一列進(jìn)行求和，所得值最大的即為最左邊一列照片 （2）所以在進(jìn)行聚類分析的時(shí)候可以先將這些“行間”相同的圖片分為

27、一“大行”。matlab實(shí)現(xiàn)分“大行”過程：將附件5中求出的518圖片，全部進(jìn)行灰度矩陣每行求和，并利用matlab將值為19*255=4854的行記為1，值小于4854的記為0，可以得出這508張圖片的“行間”位置記錄矩陣。將（1）中求出的最左側(cè)的11個(gè)圖片的“行間”位置作為凝聚點(diǎn)，聚類分析將所有的圖片分成11“大行”，每行包含19x2=38張圖片。這38張圖片“行間”位置是相同的，并且這38張包括19張正反面。將每一張圖片的正反面通過上邊緣粘接就會(huì)形成一個(gè)二倍高的紙片，這樣就會(huì)從邊緣獲取更多的信息量。（3）每一“大行”的拼接應(yīng)用上述聚類分析最短距離分析中提出的小差值優(yōu)先匹配進(jìn)行拼接，依次即

28、可排出11個(gè)行圖片。（4）行與行相連拼出完整圖片應(yīng)用方法同樣是小差值優(yōu)先匹配，即可以拼出完整的圖片。正反面順序如表格五、表格六所示表格五（正面）078a111a125b140b155b150b183a174a110b066b108b018a029b189a081a164a020b047b136a089b010a036b076a178b044b025a192b124a022b120a144b079b014b059b060a147b152b005b186a153b084b042a030b038b121b098b094a061a137a045b138b056a131a187a086a200a143a

29、199a011a161b169a194a173a206a156b034b181a198a087b132a093b072a175b097b039a083b088a107b149a180b037a191b065a115a166a001a151a170a041b070a139a002b162a203a090b114b184a179a116a207b058b158b197b154a028a012b017a102a064a208b142b057b024b013b146b171a031b201b050b190a092a019a016a177a053a202b021a130b163b193a073a159b

30、035b165a195b128b157b168b046b067b063a075a167b117a008a068a188b127b040b182a122b172b003a007a085a148a077b004b069b032b074a126a176b185b000a080a027b135a141b204a106b023a133b048b051a095b160a119b033a071a052b062b129a118a101b015a205b082a145b009a099b043b096a109b123b006b104b134b113b026a049a091b106a100a055a103b112b

31、196a054a表格六（反面）136b047a020a164b081b189b029a018b108a066a110a174b183b150a155a140a125a111b078b005a152a147a060b059a014a079a144a120b022a124b192a025b044a178a076b036a010b089a143b200b086b187b131b056b138a045a137b061b094b098a121a038a030a042b084b153a186b083a039b097a175a072b093a132b087a198b181b034a156a206b173b1

32、94b169b161a011b199b090a203b162b002a139b070b041a170b151b001b166b115b065b191a037b180a149b107a088b013a024a057a142a208a064b102b017b012a028b154b197a158a058a207a116b179b184b114a035a159a073b193b163a130a021b202a053b177b016b019b092b190b050a201a031a171b146a172a122a182b040a127a188a068b008b117b167a075b063b067a0

33、46a168a157a128a195a165b106a204b141a135b027a080b000b185a176a126b074b032a069a004a077a148b085b007b003b009b145a082b205a015b101a118b129b062a052a071b033b119a160b095a051b048a133a023b054b196b112a103a055b100b106b091a049b026b113a134a104a006a123a109a096b043a099a運(yùn)行程序六即為按照上述步驟操作后得出的完整圖片模型總結(jié)：縱觀以上三個(gè)問題，可以發(fā)現(xiàn)，題目的復(fù)雜性越

34、來越高，也越來越接近與現(xiàn)實(shí)生活中碰到的情況，即實(shí)用性增強(qiáng)，但是論文中解決三個(gè)問題所應(yīng)用的主體方法小差值優(yōu)先匹配沒有改變。小差值優(yōu)先匹配如圖四：復(fù)原圖11行左側(cè)空白列大行第一列圖片灰度矩陣“行間”聚類分析小差值優(yōu)先匹配小差值優(yōu)先匹配圖四第一問問題直接應(yīng)用上述模型進(jìn)行求解，第二問和第三問稍微復(fù)雜需要先進(jìn)行預(yù)處理，第二問中利用“行間”位置特征先進(jìn)行聚類分出行，第三問同樣分出行之后還要分出正反面。其余步驟均是按照小差值優(yōu)先匹配來解決?？梢娔Ｐ偷闹黧w清晰有利于模型進(jìn)化已解決更復(fù)雜的同類問題。6、 模型優(yōu)缺點(diǎn)模型優(yōu)點(diǎn)：（1） 模型主體部分簡(jiǎn)潔清晰，程序簡(jiǎn)潔干練。（2） 模型實(shí)用性較強(qiáng)，易于向更復(fù)雜的現(xiàn)實(shí)情

35、況推廣。復(fù)雜問題只要根據(jù)實(shí)際情況增加聚類分析的凝聚點(diǎn)或者挖掘?qū)嶋H情況中所隱含的條件，在小差值優(yōu)先匹配模型上增加約束條件就可以簡(jiǎn)化分類，提高排序正確率，所以模型易于推廣。（3） 在“分行”的關(guān)鍵問題上抓住“行間”這個(gè)決定性的影響因素，使每張圖片所處的行唯一確定，提高篩選的準(zhǔn)確度。（4） 充分挖掘了題目中所提供的一切數(shù)據(jù)條件，如最左端和最右端都考慮，正反面同時(shí)考慮。模型缺點(diǎn)：（1） 模型在碎片邊緣較短且數(shù)量較多的情況下，獲得數(shù)據(jù)太少，其準(zhǔn)確度下降，需要太多人工干預(yù)。（2） 模型不具有一般普遍性，它僅適用于邊緣為直線的且紙片上文字書寫規(guī)范的矩形碎片復(fù)原情況，對(duì)邊緣為是特殊形狀的碎片或是文字書寫不規(guī)范

36、的紙片將不再適用。7、 模型改進(jìn)及推廣模型在對(duì)數(shù)據(jù)較少的圖片拼接識(shí)別準(zhǔn)確率不高，顯然模型不能對(duì)兩張圖片是否相鄰做出很好的判斷，改進(jìn)可從以下兩反面進(jìn)行：(1)從圖片的最左端和最右端同時(shí)開始拼接，使拼接正確的圖片盡可能多的出現(xiàn)在這行中。(2)僅使用一個(gè)來判斷下一張圖片，在圖片較小數(shù)據(jù)量少的情況下容易誤判，所以需要再增加約束條件，如同時(shí)考慮類平均法、離差平方和法（ward法）等較復(fù)雜的算法，可提高準(zhǔn)確性。8、參考文獻(xiàn)1 沈恒范. 詳解matlab數(shù)字圖像處理.北京：電子工業(yè)出版社，20102 張德豐等. matlab數(shù)字圖像處理.北京：機(jī)械工業(yè)出版社，20093 汪曉銀.周保平.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn).

37、北京：科學(xué)出版社，20124 藍(lán)章禮 李益才 李艾星.數(shù)字圖像處理與圖像通信.北京：清華大學(xué)出版社，2009 5 zhx19870705，聚類分析2013年9月15日6 陳剛 于丹 吳迪.matlab基礎(chǔ)與實(shí)例進(jìn)階.北京：清華大學(xué)出版社，20127 于萬波.基于matlab的圖像處理.北京：清華大學(xué)出版社，20118 蔣先剛.數(shù)字圖像模式識(shí)別工程軟件設(shè)計(jì).北京：中國(guó)水利水電出版社，20089 趙書蘭.matlab數(shù)字圖像處理與分析實(shí)例教程.北京：化學(xué)工業(yè)出版社，2009附錄8141215310216145913181171706附件1中碎片復(fù)原后的順序及圖片：附件2中碎片復(fù)原后的順序及圖片：3

38、627151811051913108121417164附件3中碎片復(fù)原后的順序及圖片：附件3行排序（只列了兩行的圖）第一行：第二行：復(fù)原后的順序495465143186257192178118190951122129289118814461197867699916296131796311616372617720523616810076621423041231471915017912086195261871838148461612435811891221031301938816725891057414128315982199135127316020316913439315110711517694

39、3484183904712142124144771121499713616412758431251318210919716184110187661061502117315718120413914529641112015921804837755544206101049817217159720813815812668175451740137535693153701663219671156831322001780332021981513317020585152165276089146102154114401512071551401851081174101113194119123附件4中碎片復(fù)原后的順

40、序及圖片：1910750111541901840021041800641060041490322040650390671472011481701961980941131640781030910801010261000060170281460860511070290401581860980241171500050590580920300370461270191940931410881211261051551141761821510220572020711650821591390011290631381530530381231201750850501601870972030310200411081

41、161360730362071350150760431990451730791611791432080210070490611190331421680621690541921331181891621971120700840600140681741371950080471721561960230991220901851091321810950691671631661881111442060031300340131100250271781710420662050101570741450831340550180560350160091831520440810771282001310521251401

42、93087089048072012177124000102115附件3的行排序（只列了兩行的圖）附件五中碎片復(fù)原后的順序及圖片：正面順序：078a111a125b140b155b150b183a174a110b066b108b018a029b189a081a164a020b047b136a089b010a036b076a178b044b025a192b124a022b120a144b079b014b059b060a147b152b005b186a153b084b042a030b038b121b098b094a061a137a045b138b056a131a187a086a200a143a199

43、a011a161b169a194a173a206a156b034b181a198a087b132a093b072a175b097b039a083b088a107b149a180b037a191b065a115a166a001a151a170a041b070a139a002b162a203a090b114b184a179a116a207b058b158b197b154a028a012b017a102a064a208b142b057b024b013b146b171a031b201b050b190a092a019a016a177a053a202b021a130b163b193a073a159b035

44、b165a195b128b157b168b046b067b063a075a167b117a008a068a188b127b040b182a122b172b003a007a085a148a077b004b069b032b074a126a176b185b000a080a027b135a141b204a106b023a133b048b051a095b160a119b033a071a052b062b129a118a101b015a205b082a145b009a099b043b096a109b123b006b104b134b113b026a049a091b106a100a055a103b112b196a054a反面順序：136b047a020a164b081b189b029a018b108a066a110a174b183b150a155a140a125a111b078b005a152a147a060b059a014a079a144a120b022a124b192a025b044a178a076b036a010b089a143b200b086b187b131b056b138a045a137b061b094b098a121a0