【正文】 志鵬 , 一 種基于 特征區(qū)域 分割的 圖像拼接 算法 [J], 西安 電子科技 大學(xué) 學(xué)報(bào) ,29(6):763771,20xx． [4] 羅智中 ,基于文字特征的文檔碎紙片半自動(dòng)拼接 [J],計(jì)算機(jī)工程與應(yīng)用 .48(5):207210,20xx． [5] 姜群 ,晏雨 ,改進(jìn)的遺傳算法在 TSP 問題中的應(yīng)用 [J],重慶理工大學(xué)學(xué)報(bào) ,26(09):9699,20xx． [6] 20xx 高教社杯全國大學(xué)生數(shù)學(xué)建 模競(jìng)賽賽題 B 題 [EB/OL].[ 20xx117. problem/20xx/． [7] 司小江 ,吳禮發(fā) ,胡谷雨 ,數(shù)據(jù)鏈問題的貪心算法 [J],國防科技大學(xué)學(xué)報(bào) ,25(6):4549,20xx． [8] 李根強(qiáng) ,倪飛舟 ,鐘志水等 ,數(shù)據(jù)結(jié)構(gòu) [M],北京 :中國水利水電出版社 ,20xx． [9] 陳瑞兵 ,黃文奇 ,求解矩形 packing 問題的貪心算法 [J],計(jì)算機(jī)工程 ,33(04):160162,20xx． [10] Zheng Zhang, Scott Schwartz, Lukas Wagner, Webb Miller, A Greedy Algorithm for Aligning DNA Sequences[J],7: 203–214,20xx． [11] 吳志芳 ,何橋 ,動(dòng)態(tài)模式匹配算法在地層對(duì)比中的應(yīng)用 [J],世界地質(zhì) ,22(2):181184,20xx. （注：參考文獻(xiàn)各條目用五號(hào)宋體字，各條目的序號(hào)應(yīng)正文中尾注的序號(hào)相一致） 內(nèi)江師范學(xué)院本科畢業(yè)論文 12 致謝 （注：①“致謝”內(nèi)容單獨(dú)用一個(gè)版面； ②在“致謝”中主要敘述自己寫作本文的真實(shí)經(jīng)歷、感受、收獲等，表達(dá)對(duì)指導(dǎo)老師或幫助者的感謝之意．不能簡(jiǎn) 單拷貝?；谖臋n結(jié)構(gòu)特征的碎紙片拼接復(fù)原 數(shù)學(xué)與信息科學(xué)學(xué)院 信息與計(jì)算科學(xué) xxxxx，指導(dǎo)教師： xxxx （按教務(wù)處要求，本次畢業(yè)論文電子文檔將使用‘中國知網(wǎng)’大學(xué)生論文抄襲檢測(cè)系統(tǒng)進(jìn)行檢測(cè)。） 注：本模版中紅色字體是說明部分，在具體操作時(shí)應(yīng)將其刪除． 未盡事宜按《內(nèi)江師范學(xué)院畢業(yè)論文（設(shè)計(jì) ） 指導(dǎo)手冊(cè)》實(shí)施． 。為此給各位指導(dǎo)老師帶來的不便表示歉意。 內(nèi)江師范學(xué)院本科畢業(yè)論文 2 本文是以 20xx 年全國高教社杯大學(xué)生數(shù)學(xué)建模競(jìng)賽 B 題為背景，根據(jù)文字特征和文檔結(jié)構(gòu)計(jì)算碎紙片間的匹配度， 通過構(gòu)造以碎片為節(jié)點(diǎn)的排列，建立 匹配度最大的 優(yōu)化模型，利用貪心算法尋求 最佳 路徑 ，復(fù)原得到原文檔． 碎紙片 的拼接在軍事情報(bào)獲取 、 司法物證復(fù)原 及 歷史文獻(xiàn)修復(fù)等領(lǐng)域都有著 非常 重要的應(yīng)用 [1]．傳統(tǒng)上， 碎片的 拼接復(fù)原工作 一般由 人工完成，準(zhǔn)確率較高，但效率很低． 尤其 是碎 紙 片數(shù)量巨大時(shí)，人工拼接 難度較大且很難在 短時(shí)間內(nèi)完 成任務(wù)．因此，人們?cè)噲D開發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率． 碎紙片的拼接復(fù)原技術(shù) [1]是計(jì)算機(jī)模式識(shí)別 [2]和圖像處理領(lǐng)域的一個(gè)較新且典型的問題，它通過對(duì)圖片進(jìn)行預(yù)處理，將圖片上的信息處理成便于計(jì)算機(jī)識(shí)別的值，并依次對(duì)碎片進(jìn)行相應(yīng)的自動(dòng)或半自動(dòng)拼接復(fù)原．現(xiàn)有方法大多為針對(duì)手撕碎片的拼接復(fù)原，通過計(jì)算機(jī)識(shí)別其邊緣輪廓進(jìn)行拼接，但當(dāng)碎片數(shù)量龐大且碎片邊緣輪廓相似 或由碎紙機(jī)絞碎后的紙片時(shí)， 輪廓識(shí)別方法則變得不再可行． 本文結(jié)合筆畫的連續(xù)性、光滑性等文字特點(diǎn)及 字高、字寬 、行間距等 文 檔 結(jié)構(gòu)特征 設(shè)計(jì)關(guān)于規(guī)則碎紙 片的高效率復(fù)原方法． 2 問題分析 二 值處 理匹 配 度 計(jì)算結(jié) 構(gòu) 控 制校 正 匹 配 度拼 接準(zhǔn) 確 性 檢驗(yàn)紙 片復(fù) 原 圖 1 碎片的拼接復(fù)原 碎片的拼接復(fù)原過程可由上述流程圖表示：首先，對(duì)所給碎片進(jìn)行二值化處理，將文字圖像轉(zhuǎn)化為便于計(jì)算機(jī)識(shí)別的 01 值； 接著 ， 根據(jù)文字特征 進(jìn)行邊緣像素點(diǎn)的匹配度計(jì)算；再由文字行間距、字間距、字高和字寬相似等 文檔 特征 校正匹配度；然后，以碎片間的最大匹配度為目標(biāo)建立優(yōu)化模型；之后，設(shè)計(jì) 貪心算法 以 每次尋求最優(yōu)解的思想，選擇與碎片邊緣匹配度最高的另一碎片進(jìn)行拼接，在拼接過程中可對(duì)結(jié)果的準(zhǔn)確性進(jìn)行檢驗(yàn) (可配合人工 檢驗(yàn) )，若檢驗(yàn)不通過，則找出錯(cuò)誤拼接碎片重新拼接，最后，所有碎片拼接完成，得到文件的復(fù)原圖． 邊緣像素點(diǎn)匹配 （ 小四號(hào)黑體不加粗 ） （二級(jí)標(biāo)題小四號(hào)黑體不加粗，段前斷后不空行．） 由文字內(nèi)部特征和書寫習(xí)慣可知，文字文件為橫向書寫，每一文字的所有筆畫均連續(xù)且外邊緣像素點(diǎn)圍成封閉圖形．因此，通過構(gòu)造匹配度函數(shù)，計(jì)算任意兩碎片邊緣的文字匹配度，便可清楚地反映出這兩條碎片是否能夠正確拼接． 匹配度的計(jì)算方法并不唯一，由筆畫的連續(xù)性：若被切割的兩張碎片邊緣同一水平內(nèi)江師范學(xué)院本科畢業(yè)論文 3 線上 的像素點(diǎn)灰度值相同，則兩像素點(diǎn)可能相匹配，即可能同屬于 文字的一個(gè)筆畫，這樣便可通過統(tǒng)計(jì)匹配像素點(diǎn)個(gè)數(shù)來刻畫匹配度；由筆畫的光滑性：同一筆畫的外邊緣像素點(diǎn)構(gòu)成一個(gè)封閉的光滑曲線，因此可以連接碎片邊緣任意兩像素點(diǎn)，統(tǒng)計(jì)其中能構(gòu)成圈，且內(nèi)部有像素點(diǎn)填充的個(gè)數(shù)，以此來刻畫碎片邊緣的匹配度；綜合筆畫的連續(xù)性和光滑性： 若兩碎片邊緣 像素點(diǎn)斜率相同，則表示像素點(diǎn)走向一致，同屬于一個(gè)筆畫． 以下內(nèi)容省略 ?? ． 3 數(shù)據(jù)預(yù)處理 （ 1） 讀取灰度值 由于題目所給原始圖片不便于計(jì)算機(jī)識(shí)別，在計(jì)算匹配度之前需要對(duì)圖片進(jìn)行預(yù)處理．本文在 ， 內(nèi)存， 20xx 版本的硬件環(huán)境和 的軟件環(huán)境下利用 Imread 命令將附件中的所有圖片讀取為灰度矩陣，矩陣中的值為 0~255 的數(shù)． （ 2） 二值化處理 對(duì)灰度矩陣進(jìn)行二值化處理：即在灰度矩陣中將值大于 220 的像素點(diǎn)賦值為 1，小于 220 的像素點(diǎn)賦值為 0，則經(jīng)二值化處理后的圖片空白處像素點(diǎn)灰度值為 0，文字處像素點(diǎn)灰度值為 1. 4 基于像素點(diǎn) 覆蓋 的匹配度計(jì)算方法 橫一匹配 (1) 基本原理 根據(jù)文字筆畫的連續(xù)性，對(duì)經(jīng)過二值化處理后的任意兩張碎片，可比較一張碎片左邊緣（上邊緣）與另一張碎片右邊緣（下邊緣）像素點(diǎn)的灰度值．若同一水平線上（同一垂直線上）的 灰度值相等，則認(rèn)為像素點(diǎn)可能相匹配 [3]，即碎片邊緣的像素點(diǎn)可能為同一筆畫內(nèi)的像素點(diǎn)，匹配過程見圖 2． p = 0p = 0p = 0p = 1p = 0p = 1p = 1p = 1 圖 2 橫一匹配過程示意圖 圖 2 中， P 表示同一水平線上的像素點(diǎn)灰度值是否相匹配，其值為 1 代表像素點(diǎn)能內(nèi)江師范學(xué)院本科畢業(yè)論文 4 匹配，值為 0 代表不能匹配． (2) 匹配度計(jì)算模型 由橫一匹配原理，引入匹配度 P 來刻畫碎片邊緣之間的匹配程度，將待匹配的兩張碎片邊緣灰度值作差，相匹配的像素點(diǎn)坐標(biāo)灰度差值為 0，不匹配的像素點(diǎn)坐標(biāo)灰度差值絕對(duì)值為 1，則任意兩張碎片的邊緣匹配度 ijP 為： 1 (1 ( ) ( ) )mij i jkP E k E k?? ? ?? (1) (1)式中 ijP 為任意第 i 張碎片和第 j 張碎片的邊緣匹配度， ()iEk為第 i 張碎片邊緣的第 k 個(gè)像素點(diǎn)坐標(biāo)灰度值． 針對(duì)左右拼接的情況，匹配度可進(jìn)一步表示為： 1 (1 ( ) ( ) )mij ir jlkP E k E k?? ? ?? 1 (1 ( ) ( ) )mji il jrkP E k E k?? ? ?? 其中 ijP 表示第 i 張碎片的右邊緣和第 j 張碎片的左邊緣拼接的匹配度， ()irEk表示第i 張碎片右邊緣第 k 個(gè)像素點(diǎn)坐標(biāo)灰度值， ()jlEk表示第 j 張碎片左邊緣第 k 個(gè)像素點(diǎn)坐標(biāo)灰度值．類似地， jiP 表示第 j 張碎片右邊緣和