【文章內(nèi)容簡介】 行預(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 張碎片右邊緣和第 i 張碎片左邊緣拼接的匹配度， ()ilEk表示第 i 張碎片左邊緣第 k 個(gè)像素點(diǎn)坐標(biāo)灰度值， ()jrEk表示第 j 張碎片右邊緣第 k 個(gè)像素點(diǎn)坐標(biāo)灰度值． 同理，上下邊緣拼接的匹配度可表示為： 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)容省略 ?? 方向場(chǎng)匹配 (1) 基本原理 由文字筆畫的連續(xù)性可知筆畫的外邊緣輪廓線也是光滑的，為描述筆畫外邊緣輪廓線的光滑性，引入斜率的概念，若邊緣上相匹配的像素點(diǎn)有相同的斜率（如圖 3 中 b 若12kk? ，表示有相同的斜率 ），則認(rèn)為該組像素點(diǎn)屬于同一筆畫． 內(nèi)江師范學(xué)院本科畢業(yè)論文 5 DCBA 圖 3 方向場(chǎng)匹配過程示意圖 在判斷斜率是否相同之前首先應(yīng)判斷像素點(diǎn)是否匹配，如圖 3 中像素點(diǎn) A 分別與對(duì)應(yīng)碎片的像素點(diǎn) B C D、 、 的灰度值進(jìn)行比較，只有在灰度值相同的情況下，才進(jìn)一步計(jì)算兩對(duì)應(yīng)像素點(diǎn)的斜率，如在圖 3 中僅判斷 A 點(diǎn)斜率與 ,BC點(diǎn)的斜率是否相同． 以下內(nèi)容省略 ?? 5 碎紙片拼接復(fù)原模型的建立 縱切碎片的單一橫向拼接 建模思路 匹配度形象的反映了碎片拼接時(shí)的契合程度，因此可利用匹配度的高低表示碎片拼接復(fù)原的效果．哈密頓通路是經(jīng)過圖中所有頂點(diǎn)一次且僅一次的通路，而碎片的拼接復(fù)原過程就是根據(jù)起始碎片與其余各碎片的匹配度將其依次排列的過程，則以碎片為點(diǎn)，碎片之間的匹配度為邊的權(quán)值，縱切碎片的拼接復(fù)原問題可轉(zhuǎn)化為尋找該有向完全圖的哈密頓通路問題． 始末碎片 根據(jù)書寫或打印規(guī)律，縱切碎片的左右邊緣有空白列，即灰度值全為 0．則可將左邊緣灰度值全為 0 的碎片作為候選的起始碎片，右邊緣灰度值全為 0 的碎片作為候選的末尾碎片，當(dāng)根據(jù)灰度值全為 1 的原則選擇始末碎片時(shí)，可分為兩種情況： (1) 若邊緣灰度值全為 0 的碎片恰為兩片，則分別以這兩片為始末碎片； (2) 若邊緣灰度值全為 0 的碎片超過兩片，則將始末碎片兩兩組合，并選出所有組合進(jìn)行拼接復(fù)原，得到多個(gè)復(fù)原結(jié)果； 特別地，若縱切碎片的邊緣無空白列，即無灰度值全為 0 的邊緣，則選擇左邊緣與其他碎片邊緣匹配度總和最低的碎片為起始碎片，選擇右邊緣與 其他碎片邊緣匹配度總和最低的碎片為末尾碎片．若匹配度最低的碎片有兩片以上，仍采取兩兩組合的方式． 模型建立 假設(shè)文件僅為完全縱向切割，以碎片為點(diǎn)，碎片之間的匹配度為邊的權(quán)值建立有向a b 內(nèi)江師范學(xué)院本科畢業(yè)論文 6 完全圖 ( , )G V E? ，如圖 7 所示： DECBA 圖 8 以碎片為頂點(diǎn)的有向完全圖 其中 {1,2,...,