基于文檔結(jié)構(gòu)特征的碎紙片拼接復原畢業(yè)論文模板-免費閱讀
【正文】 內(nèi)江師范學院本科畢業(yè)論文 2 本文是以 20xx 年全國高教社杯大學生數(shù)學建模競賽 B 題為背景，根據(jù)文字特征和文檔結(jié)構(gòu)計算碎紙片間的匹配度， 通過構(gòu)造以碎片為節(jié)點的排列，建立 匹配度最大的 優(yōu)化模型，利用貪心算法尋求 最佳 路徑 ，復原得到原文檔． 碎紙片 的拼接在軍事情報獲取 、 司法物證復原 及 歷史文獻修復等領域都有著 非常 重要的應用 [1]．傳統(tǒng)上， 碎片的 拼接復原工作 一般由 人工完成，準確率較高，但效率很低． 尤其 是碎 紙 片數(shù)量巨大時，人工拼接 難度較大且很難在 短時間內(nèi)完 成任務．因此，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復原效率． 碎紙片的拼接復原技術(shù) [1]是計算機模式識別 [2]和圖像處理領域的一個較新且典型的問題，它通過對圖片進行預處理，將圖片上的信息處理成便于計算機識別的值，并依次對碎片進行相應的自動或半自動拼接復原．現(xiàn)有方法大多為針對手撕碎片的拼接復原，通過計算機識別其邊緣輪廓進行拼接，但當碎片數(shù)量龐大且碎片邊緣輪廓相似 或由碎紙機絞碎后的紙片時， 輪廓識別方法則變得不再可行． 本文結(jié)合筆畫的連續(xù)性、光滑性等文字特點及 字高、字寬 、行間距等 文 檔 結(jié)構(gòu)特征 設計關(guān)于規(guī)則碎紙 片的高效率復原方法． 2 問題分析 二 值處 理匹 配 度 計算結(jié) 構(gòu) 控 制校 正 匹 配 度拼 接準 確 性 檢驗紙 片復 原 圖 1 碎片的拼接復原 碎片的拼接復原過程可由上述流程圖表示：首先，對所給碎片進行二值化處理，將文字圖像轉(zhuǎn)化為便于計算機識別的 01 值； 接著 ， 根據(jù)文字特征 進行邊緣像素點的匹配度計算；再由文字行間距、字間距、字高和字寬相似等 文檔 特征 校正匹配度；然后，以碎片間的最大匹配度為目標建立優(yōu)化模型；之后，設計 貪心算法 以 每次尋求最優(yōu)解的思想，選擇與碎片邊緣匹配度最高的另一碎片進行拼接，在拼接過程中可對結(jié)果的準確性進行檢驗 (可配合人工 檢驗 )，若檢驗不通過，則找出錯誤拼接碎片重新拼接，最后，所有碎片拼接完成，得到文件的復原圖． 邊緣像素點匹配 （ 小四號黑體不加粗 ） （二級標題小四號黑體不加粗，段前斷后不空行．） 由文字內(nèi)部特征和書寫習慣可知，文字文件為橫向書寫，每一文字的所有筆畫均連續(xù)且外邊緣像素點圍成封閉圖形．因此，通過構(gòu)造匹配度函數(shù)，計算任意兩碎片邊緣的文字匹配度，便可清楚地反映出這兩條碎片是否能夠正確拼接． 匹配度的計算方法并不唯一，由筆畫的連續(xù)性：若被切割的兩張碎片邊緣同一水平內(nèi)江師范學院本科畢業(yè)論文 3 線上 的像素點灰度值相同，則兩像素點可能相匹配，即可能同屬于 文字的一個筆畫，這樣便可通過統(tǒng)計匹配像素點個數(shù)來刻畫匹配度；由筆畫的光滑性：同一筆畫的外邊緣像素點構(gòu)成一個封閉的光滑曲線，因此可以連接碎片邊緣任意兩像素點，統(tǒng)計其中能構(gòu)成圈，且內(nèi)部有像素點填充的個數(shù)，以此來刻畫碎片邊緣的匹配度；綜合筆畫的連續(xù)性和光滑性： 若兩碎片邊緣 像素點斜率相同，則表示像素點走向一致，同屬于一個筆畫． 以下內(nèi)容省略 ?? ． 3 數(shù)據(jù)預處理 （ 1） 讀取灰度值 由于題目所給原始圖片不便于計算機識別，在計算匹配度之前需要對圖片進行預處理．本文在 ， 內(nèi)存， 20xx 版本的硬件環(huán)境和 的軟件環(huán)境下利用 Imread 命令將附件中的所有圖片讀取為灰度矩陣，矩陣中的值為 0~255 的數(shù)． （ 2） 二值化處理 對灰度矩陣進行二值化處理：即在灰度矩陣中將值大于 220 的像素點賦值為 1，小于 220 的像素點賦值為 0，則經(jīng)二值化處理后的圖片空白處像素點灰度值為 0，文字處像素點灰度值為 1. 4 基于像素點 覆蓋 的匹配度計算方法 橫一匹配 (1) 基本原理 根據(jù)文字筆畫的連續(xù)性，對經(jīng)過二值化處理后的任意兩張碎片，可比較一張碎片左邊緣（上邊緣）與另一張碎片右邊緣（下邊緣）像素點的灰度值．若同一水平線上（同一垂直線上）的 灰度值相等，則認為像素點可能相匹配 [3]，即碎片邊緣的像素點可能為同一筆畫內(nèi)的像素點，匹配過程見圖 2． p = 0p = 0p = 0p = 1p = 0p = 1p = 1p = 1 圖 2 橫一匹配過程示意圖 圖 2 中， P 表示同一水平線上的像素點灰度值是否相匹配，其值為 1 代表像素點能內(nèi)江師范學院本科畢業(yè)論文 4 匹配，值為 0 代表不能匹配． (2) 匹配度計算模型 由橫一匹配原理，引入匹配度 P 來刻畫碎片邊緣之間的匹配程度，將待匹配的兩張碎片邊緣灰度值作差，相匹配的像素點坐標灰度差值為 0，不匹配的像素點坐標灰度差值絕對值為 1，則任意兩張碎片的邊緣匹配度 ijP 為： 1 (1 ( ) ( ) )mij i jkP E k E k?? ? ?? (1) (1)式中 ijP 為任意第 i 張碎片和第 j 張碎片的邊緣匹配度， ()iEk為第 i 張碎片邊緣的第 k 個像素點坐標灰度值． 針對左右拼接的情況，匹配度可進一步表示為： 1 (1 ( ) ( ) )mij ir jlkP E k E k?? ? ?? 1 (1 ( ) ( ) )mji il jrkP E k E k?? ? ?? 其中 ijP 表示第 i 張碎片的右邊緣和第 j 張碎片的左邊緣拼接的匹配度， ()irEk表示第i 張碎片右邊緣第 k 個像素點坐標灰度值， ()jlEk表示第 j 張碎片左邊緣第 k 個像素點坐標灰度值．類似地， jiP 表示第 j 張碎片右邊緣和第 i 張碎片左邊緣拼接的匹配度， ()ilEk表示第 i 張碎片左邊緣第 k 個像素點坐標灰度值， ()jrEk表示第 j 張碎片右邊緣第 k 個像素點坐標灰度值． 同理，上下邊緣拼接的匹配度可表示為： 1 (1 ( ) ( ) )mij id jukQ E k E k?? ? ?? 1 (1 ( ) ( ) )mji iu jdkQ E k E k?? ? ?? 其中， ijQ 為碎片 i 下邊緣與碎片 j 上邊緣的匹配度， jiQ 為碎片 j 下邊緣與碎片 i 上邊緣的匹配度， u 代表上邊緣， d 代表下邊緣． 以下內(nèi)容省略 ?? 方向場匹配 (1) 基本原理 由文字筆畫的連續(xù)性可知筆畫的外邊緣輪廓線也是光滑的，為描述筆畫外邊緣輪廓線的光滑性，引入斜率的概念，若邊緣上相匹配的像素點有相同的斜率（如圖 3 中 b 若12kk? ，表示有相同的斜率 ），則認為該組像素點屬于同一筆畫． 內(nèi)江師范學院本科畢業(yè)論文 5 DCBA 圖 3 方向場匹配過程示意圖 在判斷斜率是否相同之前首先應判斷像素點是否匹配，如圖 3 中像素點 A 分別與對應碎片的像素點 B C D、 、 的灰度值進行比較，只有在灰度值相同的情況下，才進一步計算兩對應像素點的斜率，如在圖 3 中僅判斷 A 點斜率與 ,BC點的斜率是否相同． 以下內(nèi)容省略 ?? 5 碎紙片拼接復原模型的建立 縱切碎片的單一橫向拼接 建模思路 匹配度形象的反映了碎片拼接時的契合程度，因此可利用匹配度的高低表示碎片拼接復原的效果．哈密頓通路是經(jīng)過圖中所有頂點一次且僅一次的通路，而碎片的拼接復原過程就是根據(jù)起始碎片與其余各碎片的匹配度將其依次排列的過程，則以碎片為點，碎片之間的匹配度為邊的權(quán)值，縱切碎片的拼接復原問題可轉(zhuǎn)化為尋找該有向完全圖的哈密頓通路問題． 始末碎片 根據(jù)書寫或打印規(guī)律，縱切碎片的左右邊緣有空白列，即灰度值全為 0．則可將左邊緣灰度值全為 0 的碎片作為候選的起始碎片，右邊緣灰度值全為 0 的碎片作為候選的末尾碎片，當根據(jù)灰度值全為 1 的原則選擇始末碎片時，可分為兩種情況： (1) 若邊緣灰度值全為 0 的碎片恰為兩片，則分別以這兩片為始末
研究報告相關(guān)推薦
鄂ICP備17016276號-1