碎紙片拼接復(fù)原數(shù)模論文B

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

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

3、0XX年X月XX日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽 編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）： 賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）： 全國評閱編號（由全國組委會評閱前進(jìn)行編號）：碎紙片的拼接復(fù)原摘要圖像碎片自動拼接復(fù)原是需要借助計算機把大量碎片重新拼接復(fù)原成初始圖像的 完整模型，這一研究在考古、刑偵犯罪、古生物學(xué)、醫(yī)學(xué)圖像分析、遙感圖像處理以及 壁畫保存復(fù)原等方面具有廣泛、實際的應(yīng)用1本文主要解決碎紙機破碎文檔的自動拼接復(fù)原問題.我們利用圖像數(shù)字化技術(shù)，借 助Matlab軟件

4、將圖像轉(zhuǎn)化為矩陣.通過建立數(shù)學(xué)模型，運用矩陣論、聚類分析方法、自 定義相似度方法、遺傳算法、字符分割和字符識別等方法，對數(shù)據(jù)進(jìn)行處理，實現(xiàn)對圖 像碎片自動拼接，從而將所給碎片拼接復(fù)原為完整圖像.問題一，我們首先把碎片圖形進(jìn)行二值化處理，根據(jù)所給縱切黑白碎片邊緣的像素 關(guān)系（相鄰兩張碎片，一張碎片矩陣右邊的像素與另一張碎片左邊的像素相同），我們采 和自定義相似度算法，利用附件一和附件二求出碎片間的相似度，然后根據(jù)所需要滿足 的條件即相似度最大原則，建立了縱切碎片拼接模型一及其算法，運用Matlab編程實 現(xiàn)該模型，并得到碎片復(fù)原結(jié)果（見表一表二）.問題二，要實現(xiàn)快速準(zhǔn)確的拼接復(fù)原縱橫切碎片，在問

5、題一的思路基礎(chǔ)上，我們采 用了模糊C的均值聚類方法，先對附件三所有碎片進(jìn)行初步的分類，然后在自定義相似 度算法上增加了約束條件，以此來排除有若干碎片在匹配時相似度相同的情形，建立了 改進(jìn)的中文縱橫切碎片拼接模型二，同樣利用Matlab軟件求得碎片的復(fù)原結(jié)果（見表 三）.對于英文縱橫切碎片的拼接問題，我們采用了字符切割和字符識別思想，即在碎片 的二值化矩陣中選取適當(dāng)大小的行與列，對碎片邊緣的英文字母進(jìn)行切割，與其他圖片 匹配合并，提取切割字母的特征（統(tǒng)計特征或結(jié)構(gòu)特征），再利用字符識別的方法從得 到的特征庫中找到與待識別字符相似度高的字符，將兩張碎片拼接在一起，先一行一行 地進(jìn)行拼接，再利用模型

6、二橫切碎片方法，利用Matlab軟件求得碎片的復(fù)原結(jié)果（見 表四）.問題三，在處理雙面打印縱橫切碎片時，經(jīng)分析發(fā)現(xiàn)兩面圖片最大的區(qū)別在于光滑 度的不同，紙張的正面比反面要光滑，因此在模型二的基礎(chǔ)上還需增加一步篩選工作， 就是采用傅里葉變換將圖像的二值矩陣從“空域”變?yōu)椤邦l域”，再根據(jù)不同頁面的頻 率范圍，設(shè)定一段頻率值，借助計算機將雙面打印的碎片進(jìn)行分類，分離出在同一頁面 的碎片.分離成功后再采用模型二對于英文碎片的拼接方法將碎片進(jìn)行復(fù)原即可，通過 這種方法求得碎片的復(fù)原結(jié)果.關(guān)鍵詞：碎片拼接均值聚類方法相似度模型傅里葉變換一、問題重述1.1背景：破碎文件的拼接和復(fù)原對于司法物證復(fù)原、歷史文獻(xiàn)

7、再現(xiàn)和軍事情報獲取等 方面都有極其重要的作用.于是碎紙片的拼接復(fù)原技術(shù)便成為圖像處理與模式識別領(lǐng)域 中的一個嶄新典型的應(yīng)用.圖像配準(zhǔn)是圖像拼接復(fù)原的基礎(chǔ)，而且圖像配準(zhǔn)算法的計算 量一般非常大，因此圖像拼接復(fù)原技術(shù)的發(fā)展很大程度上取決于圖像配準(zhǔn)技術(shù)的創(chuàng)新. 本文將通過圖像提取技術(shù)獲取一組碎紙片的形狀、顏色、文字等信息，然后利用計算機 進(jìn)行相應(yīng)的處理從而實現(xiàn)對這些碎紙片的自動拼接復(fù)原.1.2重述：該題研究的是如何對碎紙片進(jìn)行拼接復(fù)原.傳統(tǒng)上，拼接復(fù)原工作需由人工完 成，準(zhǔn)確率較高，但是效率低.隨著計算機技術(shù)的發(fā)展，當(dāng)碎紙片數(shù)量巨大的時候，人 們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原的效率.問

8、題1對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片(僅縱切)，建立碎 紙片拼接復(fù)原模型和算法，并針對附件1、2給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn) 行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，寫出干預(yù)方式及干預(yù)的時間節(jié)點.問題2對于碎紙機既縱切又橫切的情形，請設(shè)計碎紙片拼接復(fù)原模型和算法，并針 對附件3、4給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原.如果復(fù)原過程需要人 工干預(yù)，寫出干預(yù)方式及干預(yù)的時間節(jié)點.問題3對于雙面打印文件的碎紙片拼接復(fù)原問題設(shè)計碎紙片拼接復(fù)原模型和算法， 并針對附件5給出的一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原，結(jié)果表 達(dá)同上.二、問題分析碎紙機破碎紙片的拼

9、接復(fù)原，都需要經(jīng)過獲取圖像，導(dǎo)入圖像，圖像預(yù)處理，圖像 配準(zhǔn)，和圖像的拼接復(fù)原步驟.其中圖像配準(zhǔn)是碎紙片拼接復(fù)原技術(shù)中最重要的環(huán)節(jié)之 一.針對本題中給出的三種不同的情況，需采用不同的模型和算法來提高拼接復(fù)原的效 率和準(zhǔn)確度對于問題1所需要拼接復(fù)原的碎紙片為縱向切割的小紙條，通過Matlab軟件將所 給圖片轉(zhuǎn)換成為1980 x72的二值矩陣，先隨機選擇一個碎片的矩陣作為基本矩陣，將剩 余矩陣與基本矩陣作比較，通過matlab軟件計算出相比較矩陣的相似度，再根據(jù)模型 一的匹配方法將碎紙片進(jìn)行拼接復(fù)原，此拼接模型不需要人工干預(yù).對于問題2對于碎紙機既橫切又縱切的情形，所得碎片的像素較低，采用模型一的

10、 算法無法完全拼接復(fù)原11x 19個碎片，需要先對碎片進(jìn)行聚類分析，篩選出特征相同的 碎片，再根據(jù)二重判別標(biāo)準(zhǔn)的相似度刻畫原則，將碎片進(jìn)行橫向和縱向的拼接復(fù)原.對中文碎片進(jìn)行拼接時，先通過二值矩陣找出字間距和一個字的間距，通過聚類分析法 先將所有碎片分行找出，把橫縱切拼接問題轉(zhuǎn)化為橫切碎片拼接，再利用行間距和字的 行高約束條件，運用遺傳算法拼接復(fù)原整個圖片.英文碎片拼接與中文碎片拼接不同，在拼接碎片時，需要采用字符切割的方法，提 取英文字母的特征，根據(jù)碎片邊緣字母的特征，再利用字符識別的方法，尋找相匹配的 碎片，根據(jù)這一原則運用遺傳算法的匹配方法拼接復(fù)原英文碎片.對于問題3要想拼接復(fù)原雙面打印

11、碎片，必須先將所有碎片進(jìn)行分類.把同一頁的 碎片分離出來.經(jīng)過分析可得，兩面打印的紙張的粗糙度不同，正面比反面光滑，根據(jù) 這一特征，需要采用傅里葉變換處理圖像，從而得到碎紙片的“頻率”圖.高頻代表圖 像的細(xì)節(jié)、紋理信息，低頻代表圖像的輪廓信息對所有碎紙片進(jìn)行高頻濾波.濾波后可 得圖像的紋理信息.運用Matlab軟件計算若干碎紙片的頻率信息，設(shè)定頻率范圍，將所 有碎紙片分為正反頁面圖片兩類.再采用模型二的算法拼接復(fù)原整個圖片.三、基本假設(shè)1、碎紙機破碎的每個紙片的長、寬和厚度均相同；2、所有碎片是黑白圖片，圖片清晰；3、碎片完整沒有缺損缺失，可以完全拼接復(fù)原；4、碎紙片的正反兩方面的印刷效果都一

12、樣，互不影響；5、掃描圖片沒有變異，文字與圖片上邊界平行；6、文件頁邊距和行距固定；7、碎片中的文字方向相同，不需要考慮碎片拼接時需要旋轉(zhuǎn)拼接復(fù)原.四、符號說明符號含義表示第(i=1 19)個碎紙片的像素矩陣表示所選碎紙片像素矩陣中參與比較的行數(shù)表示兩個碎紙片像素邊界矩陣兀素相同的數(shù)目b表示兩個碎紙片像素邊緣矩陣的相似度（b = i） n表示二值矩陣的聚類中心表示矩陣的向量空間五、模型的建立與求解通過我們建立的自動拼接模型，在圖片拼湊過程中，我們可以預(yù)測圖片的拼接大致需進(jìn) 行圖片處理、邊界比較、圖片輸出等步驟.通過我們所得的模型預(yù)測，可以得出預(yù)測方程.具體流程圖如圖5-1所示：圖5-1模型方法

13、預(yù)測（一）問題一模型的建立與求解5.1.1圖像的導(dǎo)入運用Matlab軟件采用二值法原理將碎片的圖像轉(zhuǎn)換成為1980乂72的 （0,1）矩陣，記為 A . = （1,2, ,19）.5.1.2圖像的去噪邊緣處理采用中值濾波的原理對圖像邊緣進(jìn)行去噪.中值濾波就是用 相鄰像素的中值來替代該像素的值，利用Matlab對圖像所成二值矩陣進(jìn)行光滑處理， 以此提高碎片匹配時的相似度.中值濾波法是一種非線性平滑技術(shù)，它將每一象素點的灰度值設(shè)置為該點某鄰域 窗口內(nèi)的所有象素點灰度值的中值.中值濾波是基于排序統(tǒng)計理論的一種能有效抑制噪聲的非線性信號處理技術(shù)，中 值濾波的基本原理是把數(shù)字圖像或數(shù)字序列中一點的值用該

14、點的一個拎域中各點 值的中值代替，讓周圍的像素值接近的真實值，從而消除孤立的噪聲點。方法是 去某種結(jié)構(gòu)的二維滑動模板，將板內(nèi)像素按照像素值的大小進(jìn)行排序，生成單調(diào) 上升（或下降）的為二維數(shù)據(jù)序列。二維中值濾波輸出為g （x, y） = med f （x - k, y -1 ）,（k, l e w），其中，f （x, y），g （x, y）分別為原始圖像和處 理后圖像。叩為二維模板，通常為2x2,3x3區(qū)域，也可以是不同的的形狀，如線狀， 圓形，十字形，圓環(huán)形等中值濾波的函數(shù)為：5.1.3圖像的配準(zhǔn)1）遺傳算法是一種基于生物自然選擇與遺傳機理的隨機搜索算法，是一種有效的 解最優(yōu)化問題的方法.借助

15、計算機選取第一張碎片作為第一張圖，采用遺傳算法，將該 圖片的右邊緣矩陣與剩下的18張圖的相對應(yīng)的左邊緣矩陣隨機的根據(jù)相似度進(jìn)行比較， 然后把相似度最高的圖片作為第二張圖并與第一張圖片拼接起來.將第一張圖作為基準(zhǔn) 圖，向右匹配，若右方向的匹配完成，再朝左方向匹配，以此類推，直到將所有圖片拼 接復(fù)原完成.問題一不需要進(jìn)行人工干預(yù).圖5-2遺傳算法流程圖2）相似度的計算方法：計算機自動選擇一張碎片為第一張碎片（此處就以000.bmp 為第一張），具體實現(xiàn)算法為用嵌套循環(huán)，第一重循環(huán)取出每張圖片最右邊（第72列）的像素矩陣，第二重循環(huán)取出每張圖片最左邊（第1列）的像素矩陣，然后作這兩個矩 陣的比較，結(jié)

16、果相同為1不同為0，對其結(jié)果矩陣求和作為刻畫相似度的標(biāo)準(zhǔn)，如果是 自身比較則置為0，當(dāng)結(jié)果中出現(xiàn)1980 （說明兩張圖片是100%匹配，可以判斷出第一張 和最后一張），用這種方法就可以得到完整的拼接圖像，剩余圖片的矩陣隨機編號為A， 利用Matlab軟件選取矩陣中的n行運用同或運算法則進(jìn)行相似度的計算.一00 一一 00110假設(shè)A =10. .11. .1=A_i0 二00 二1讓A的最右列與A的最左列的元素對應(yīng)作比較，同行的兩元素相同則為,1，1i不同記為0，從第一行開始累加，累加的結(jié)果記為初.i相似度記為：b =二x 100%（n=1980）.n5.1.4圖像的導(dǎo)出1）根據(jù)配準(zhǔn)結(jié)果進(jìn)行矩

17、陣的拼接.2）運用Matlab軟件編程實現(xiàn)圖像的導(dǎo)出.表一附件一圖片排序008014012015003010002016001004005009013018011007017000006表二附件二圖片排序003006002007015018011000005001009013010008012014017016004（二）問題二模型的建立與求解問題二為縱橫切有11 x 19個碎片，每個碎紙片的邊緣像素相對于問題一來說要少很 多，無法直接利用模型一求解問題二.在模型一的基礎(chǔ)上，我們首先對中文碎片進(jìn)行拼 接復(fù)原，根據(jù)圖片的特征對圖片進(jìn)行分類，然后再采用雙重標(biāo)準(zhǔn)定義相似度的算法來進(jìn) 行圖片的拼接.拼

18、接英文碎片時，采用字符切割和字符識別的方法，問題二需要人工介 入.5.2.1圖像導(dǎo)入同樣采用二值法，運用Matlab軟件將碎紙片的圖像轉(zhuǎn)換為180 x72的（0,1）矩陣 5.2.2圖像邊緣處理采用模型一的中值濾波的方法對209張圖片的邊緣進(jìn)行光滑處理，以提高圖片在匹 配時的相似度，排除噪聲對圖片的影響.5.2.3圖像配準(zhǔn)（拼接中文碎片）1）采用模糊C均值聚類方法根據(jù)同行圖片的特征，同一行圖片的同列字間的間距 相同，缺損字的上邊緣或下邊緣與碎片的邊緣之間的距離相同.還可以根據(jù)字的最左端 到圖片邊緣之間的距離相等篩選出文章最左列碎片，運用Matlab軟件編程將209張碎 片進(jìn)行初步分類，再利用M

19、atlab軟件建立元胞數(shù)組，將碎片分行導(dǎo)入元胞數(shù)組，同行 碎片不分順序3模糊c均值聚類:設(shè)X = X 1,X2，.,XjuRp, R尸表示P維實數(shù)向量空間.令七 表示第k個樣本屬于第i類的隸屬度，0 u 1，u =1，0 lLu N，i =1k =11 k N,1 i c。記v為第i類的聚類中心.則X的一個模糊C均值聚類就是求如下目 標(biāo)函數(shù)的最小值： j （u ,v）=藝 （uik ）m （d ik ）2.k = 1 i = 1其中d =iix -v ii為第k個序列到第i類中心的歐式距離。聚類準(zhǔn)則取為求j（u,v） 的極小值：m inJ（ U,V）.求模糊C均值聚類的具體步驟如下：（1）（2

20、）取定c,m和初始隸屬度矩陣U 0，迭代步數(shù)I=0.計算聚類中心V為：（3）修正U： (u (l )mxv(i)=lk kik=1(i = 1,2,，c;1 0， maxl Ut 一Utt | ， 如：Vi, Vk.d ( ik )m-1T：j=1 jk實際計算時應(yīng)對取定的初始值進(jìn)行迭代計算直至則算法終止，并得到結(jié)果。若U , = maxUj，則X代第j類.圖5-3圖片5-4圖片5-5其中可判定圖片5-3與5-4為同一行，圖片5-3與圖片5-5不在同一行.2）因用人工干預(yù)找出完整圖片的左下角的碎片，先只拼接這一行，由于明確了方 向兩兩圖片只需單向作比較，可將已確定的圖片標(biāo)記為1不再被比較。因圖

21、片可能有孤 立兩點和黑點，為忽略像素間的比較那些點的影響，采用絕對值來控制同行或同列像素 間其比較結(jié)果取值范圍。有采用模型一的貪婪算法和每張圖片做相似度的大小比較并在 此基礎(chǔ)上加上這張圖片的特性約束及深度比較和中途的人工干預(yù)可正確篩選出一行完 整圖片。以此思想繼而課求出此圖片的縱列，以后以縱列的每張圖片再進(jìn)行此算法的類 推可拼接完整圖片.例：（1）中文版確定007.bmp為開頭的所在行確定029.bmp為開頭的所在行（2）英文版確定081.bmp為開頭的所在行確定191.bmp為開頭的所在行3）定義相似度：約束一：與模型一的相似度算法近似.約束二：用以上得出的字與字，字與頁邊距的規(guī)律求出要拼接

22、的這行為首圖片的特 征來加以約束要比較的圖片.約束三：當(dāng)有多個像素相似度值很接近和相等時再精確深入作比較，利用同一行碎 片的二值矩陣的特征即上下兩個字的間距為28個像素點，左右兩個字6個像素點，進(jìn) 一步比較.如果出現(xiàn)異常情況，人工干預(yù)進(jìn)行修正.在對英文碎片進(jìn)行拼接時采用同樣的方法， 只是需要改變它們之間的行間距與字間距的約束條件.4）通過以上步驟將每行的碎片拼接完成，并確定了最后一行的圖片，將11 19個 碎片拼接復(fù)原問題轉(zhuǎn)換為11個碎片拼接問題.橫切碎片比縱切碎片拼接復(fù)原的要復(fù)雜， 所以還需另一種二重約束的相似度算法.取約束一條件下相似度最高的碎片，如有相同 的再運用約束二的條件進(jìn)行匹配，橫

23、向拼接的方法為模型一的遺傳算法，從完整圖片的 最后一行向上進(jìn)行拼接。如果出現(xiàn)異常情況，人工干預(yù)進(jìn)行修正.5.2.4圖像配準(zhǔn)（拼接英文碎片）1、字符切割：選取碎片二值矩陣邊緣的若干列（一個字符間距加一個字母的像素）， 分離出單個字符，選取的若干列中會有一個或多個完整或不完整的字符，這就相當(dāng)于多 個約束條件的匹配.2、特征提?。簭那懈畹淖址刑崛〗y(tǒng)計特征或結(jié)構(gòu)特征，進(jìn)行歸一化、細(xì)化處理.3、字符識別：先借助計算機構(gòu)建52個字母（大小寫）的特征庫（用1,0矩陣構(gòu)造的字 母圖樣），根據(jù)特征庫的信息，對于同一字母進(jìn)行識別，從而挑選出相匹配的拼接碎片.4、拼接算法：采用中文拼接的方法（遺傳算法），即先拼接

24、行，再拼接列.5）圖像的導(dǎo)出表三附件三的復(fù)原結(jié)果495465143186257192178118190951122129289118814161197867699916296131796311616372617720523616810076621423041231471915017912086195261871838148461612435811891221031301938816725891057414128315982199135127316020316913439315110711517694348418390471214212414477112149971361641275843125

25、1318210919716184110187661061502117315718120413914529641112015921804837755544206101049817217159720813815812668175451740137535693153701663219671156831322001780332021981513317020585152165276089146102154114401512071551401851081174101113194119123表四附件四的復(fù)原結(jié)果1917511154190184210418064106414932204653967147201

26、148170196198941131647810391801012610061728146865110729401581869824117150559589230374612719194931418812112610515511417618215122572027116582159139112963138153533812312017585501601879720331204110811613673362071351576431994517379161179143208217496161331421686216954192133118189162197112708460146868137195

27、8471721569623991229018510913218195691671631661881111442063130341311025271781714266205101577414583134551856351691831524481771282001315212514019387894872121771240102115(三)問題三的求解5.3.1傅里葉變換處理圖像通過對問題三的分析可得雙面印刷碎片的特征，即為不同面的碎紙片的光滑度不 同，所以需要利用傅里葉變換將圖像從“空域”變?yōu)椤邦l率”，再根據(jù)不同頁面的頻率 范圍，設(shè)定一段頻率值，借助計算機將雙面打印的碎片進(jìn)行分類，分離出在同一頁

28、面的 碎片，以此降低碎片拼接復(fù)原的難度.快速傅里葉變換(FFT)是計算離散傅里葉變換(DFT)的快速算法.離散傅里葉變換運 算量巨大，計算時間長，即運算時間很長.而快速傅里葉變換的提出將傅里葉變換的復(fù) 雜度由降到了，很大程度上減少了計算量.=lb!粉(21)2 x) + 上粉(21 + 1)皿(2 3. TOC o 1-5 h z x=0 x=0令 F (u) = E f (2x)Wux，x=0則 F (u) = 2 F (u) + F (u )Wm2，M-1.F (u) = M f (2x +1，u=0，1，M omF (u + M) = - F (u) - F (u)Wu 12 eo2 M

29、5.3.2采用模型二拼接英文碎片的算法借助Mat lab軟件將所有碎片分為兩類，分類完成后就與問題二拼接英文碎片相同 了，因此可采用模型二拼接因為碎片的方法將碎片一頁一頁地拼接完成.六、誤差分析雖然我們建立了針對不同情況碎片拼接的模型，也得到了碎片的復(fù)原結(jié)果， 但是模型是建立在理想的假設(shè)基礎(chǔ)之上的，實際上碎片不全是非常清晰的， 也有不明朗的模糊灰色區(qū)域，特別是在碎片的邊緣處，在對這些區(qū)域計算 相似度時會由于閥值的不穩(wěn)定性產(chǎn)生一些誤差，可能導(dǎo)致圖像拼接時出現(xiàn) 錯誤拼接現(xiàn)象.除此之外，在問題二、三中采用聚類分析法對碎片分類時， 可能得到的結(jié)果與主成分分析的結(jié)果有一定差異，就會導(dǎo)致分類時有些行 的碎

30、片會有多余的情況出現(xiàn)，從而無法完整拼接復(fù)原圖片，所以實際與理 論之間總會存在一定的誤差，這是難以避免的.七、模型的優(yōu)缺點討論7.1模型的優(yōu)點通過對模型的分析，驗證了模型的可靠性，模型過程清晰明了，并且可用Matlab 軟件快速求解，為此類碎片的拼接復(fù)原提供了方便可行的設(shè)計方法，具有重要的實際意 義和較高的應(yīng)用價值.模型一研究的是對縱切碎片的拼接復(fù)原，該模型簡單方便，誤差小，在沒有異常情 況下，無需人工干預(yù)，并且拼接效果優(yōu)良.自定義的相似度算法簡單可靠，還考慮到噪 聲對碎片邊緣的影響，采用中值濾波方法對碎片邊緣進(jìn)行光滑處理能提高匹配的相似 度，采用這種方法更符合實際情況.模型二研究的是對橫縱切碎

31、片的拼接復(fù)原，該模型較模型稍復(fù)雜，考慮到碎片匹配 時可能有多個碎片與之匹配的相似度相同，從而計算機無法選擇的情況，采用了先分類 后匹配的方法，不僅可以排除這種計算機無法選擇的情況，還提高碎片拼接的效率.在 現(xiàn)實生活中，碎紙機破碎文件時常為縱橫切碎片，所以模型二具有更大實際意義.模型三研究的是對雙面打印的縱橫切碎片的拼接復(fù)原，借助傅里葉變換將圖像由 “空域”轉(zhuǎn)換為“頻域”，經(jīng)過分析提取出圖像的紋理特征，這種方法可靠性強，能夠 較強地判別出不同頁面的碎片.模型三采用二次分類的算法，提高了碎片配準(zhǔn)的精確度 和效率.7.2模型的缺點三個模型在對碎片拼接復(fù)原時都沒有考慮碎片的方向問題，沒有采用坐標(biāo)旋轉(zhuǎn)的

32、方 法來拼接碎片.模型二中采用的模糊C均值聚類方法，可能得到的結(jié)果與主成分分析綜 合的結(jié)果有一定的差異，導(dǎo)致分類不夠精確，并且模型二、三步驟較多，程序較為復(fù)雜， 在碎片拼接時具有一定的難度.八、模型的改進(jìn)與推廣8.1模型的改進(jìn)在實際生活中，一方面，碎紙片中文字的方向是不定的而且紙片數(shù)量大，所以在建 模拼接碎片時應(yīng)考慮將碎片旋轉(zhuǎn)拼接.在解決實際問題的過程中，我們可能發(fā)現(xiàn)利用經(jīng) 典的模糊C均值聚類所得到的結(jié)果與主成分分析綜合的結(jié)果有一定的差異，故我們在此 可對模糊C均值聚類加以改進(jìn)，使得聚類的結(jié)果與主成分分析的效果基本一致，將聚類 迭代公式中的歐式距離改為加權(quán)歐式距離，其中的權(quán)向量采取主成分分析的

33、方法計算， 采用這種加權(quán)模糊C均值聚類的迭代算法可使分類更加精確.另一方面，圖像的拼接不僅僅限制于文檔型，可以運用于真彩型圖片拼接.在建模 時可以考慮基于模板彩色圖像拼接模型.對兩幅具有重疊區(qū)域的彩色圖像，先利用圖像 特征信息從一幅圖像的重疊區(qū)域中自動尋找一小塊模塊圖像，然后根據(jù)最大相似性準(zhǔn)則 在另一幅圖像中重疊區(qū)域里搜索,找到最佳圖像配準(zhǔn)點，最后利用平滑因子對兩幅圖像 的重疊區(qū)域圖像數(shù)據(jù)進(jìn)行數(shù)據(jù)融合操作，去掉重疊部分，以實現(xiàn)彩色圖像自動快速地?zé)o 縫拼接.8.2模型的推廣所有模型的建立、方案的確定、碎片的分析，數(shù)據(jù)量較大（碎片多）。對于碎片的 拼接復(fù)原問題的解決，我們考慮了多方面因素，同時也對

34、一些因素做了假設(shè)通過改進(jìn)， 該模型的拼接復(fù)原精確度就越高。我們可將該方法推廣到醫(yī)學(xué)圖像分析，遙感圖像處理， 彩色圖像復(fù)原和視頻監(jiān)控等領(lǐng)域，具有重要的實際意義.參考文獻(xiàn)1蔡麗歡，廖英豪，郭東輝，圖像拼接方法及其關(guān)鍵技術(shù)研究J，計算機技術(shù)與發(fā)展，2008/03： 67-81,2008 年.2余宏生，金偉其，數(shù)字圖像拼接方法與研究進(jìn)展J，紅外技術(shù)，2009/06:74-102,2009年.3楊桂元，黃幾立，數(shù)學(xué)建模M，合肥：中國科學(xué)技術(shù)大學(xué)出版社，2008年.4薛毅，數(shù)學(xué)建?；A(chǔ)M，北京：北京工業(yè)大學(xué)出版社，2004年.5謝兆鴻，范正森，王艮遠(yuǎn)，數(shù)學(xué)建模技術(shù)M，北京：中國水利水電出版社，2003年.

35、6景振毅，張澤兵，董霖，MATLAB7.0實用寶典M，北京：中國鐵道出版社，2009年.7楊啟帆，何勇，數(shù)學(xué)建模競賽M，杭州：浙江大學(xué)出版社，2005年.8張錚，王艷平，薛桂香，數(shù)字圖像處理與機器視覺一一VisualC+與Matlab實現(xiàn)M，北京：人民郵電出版社.9張躍輝，矩陣?yán)碚撆c應(yīng)用M，北京：科學(xué)出版社，2011年.10吳石林，誤差分析與數(shù)據(jù)處理M，北京：清華大學(xué)出版社，2010年.11王，任嘉辰，圖論算法理論、實現(xiàn)及應(yīng)用M，北京：北京大學(xué)出版社，2011年.附錄附錄1求解問題一的相關(guān)程序clcclearfori=0:18imagei + 1=imread(F:B 附件2,sprintf(

36、%03d,i),.bmp,bmp);imagei+1=im2bw(imagei+1);endrelat=zeros(19);forx=1:19fory=1:19imagey(:,1);endimagex(:,72);forz=1:19if(x=z)relat(x,z)=0;elsebef_back=imagex(:,72)=imagez(:,1);bef_like_back=sum(bef_back);relat(x,z)=bef_like_back;endendendSUCCESS=xlswrite(C:UserslenovoDocumentsMATLABEmach2.xls,relat,A2:S20)globalmaxclorow;result=zeros(1,19);for(x=1:19)for(y=1:19)if(relat(x,y)=1980)max=relat(x,y);row=x;clo=y;endendif(max=1980)fprintf(圖片d為最后一張圖片n ,row);fprintf(圖片d為第一張圖片n ,clo);result(1,1)=clo;result(1,19)