王煜琪

【摘要】 在諸多領(lǐng)域中，經(jīng)常需要把大量文件碎片拼接成一個(gè)或幾個(gè)完整文件。若通過(guò)手工進(jìn)行拼接，費(fèi)時(shí)費(fèi)力，并且也不能保證得到較好的復(fù)原物體。因此，結(jié)合圖像處理技術(shù)完成文件碎片復(fù)原，既具有極大的理論意義，又有廣泛的應(yīng)用背景。

【關(guān)鍵字】 圖像處理 文件碎片復(fù)原 拼接 邊界匹配 像素提取

一、引言

隨著研究深入，對(duì)于文件碎片拼接也涌現(xiàn)出了許多研究方法，一些文獻(xiàn)也進(jìn)行了描述。本文主要討論的是結(jié)合圖像處理技術(shù)完成文件碎片復(fù)原，主要涉及圖像分割、輪廓特征提取、輪廓表示方法等相關(guān)領(lǐng)域，并且將計(jì)算機(jī)視覺(jué)、多維信號(hào)處理和圖像處理技術(shù)等緊密結(jié)合在一起。闡述了對(duì)于不同類(lèi)型文件碎片復(fù)原的處理方法，并在一些方法中加入文字特征的分類(lèi)算法和像素匹配算法，結(jié)合最優(yōu)化思想，使復(fù)原程度盡可能高，人工干預(yù)盡可能少。

二、基于文字的文件碎片處理方法

對(duì)碎片進(jìn)行預(yù)處理掃描：對(duì)于單面印刷的文件碎片，保證碎紙片被掃描的一面在原始位置中屬于同一面。對(duì)于雙面印刷的文件碎片，要掃描碎片兩面的信息，并且信息對(duì)應(yīng)于哪面要標(biāo)記清楚。為處理方便，同一次掃描使用相同的背景顏色。

1、針對(duì)縱切的規(guī)則的單面印刷文件碎片

①法一：

將圖片格式的碎紙片圖以灰度值矩陣A（k）的形式存儲(chǔ)，

目標(biāo)函數(shù)為minf（π），這樣一來(lái)哈密爾頓路徑求得的是全局最優(yōu)解，即最佳匹配。

2、針對(duì)既橫切又縱切的單面印刷文件碎片

①法一：由于橫切縱切切割了兩次，所以采用二層篩選的方法，并加入了k-means聚類(lèi)算法（即接受輸入量 k ，將n個(gè)數(shù)據(jù)對(duì)象劃分為 k個(gè)聚類(lèi)，使所獲得的聚類(lèi)滿足同一聚類(lèi)中對(duì)象相似度較高，不同聚類(lèi)相似度較小）

第一層做行位置篩選，讀取圖片的像素行，存入碎片的特征列向量中，并將此列向量作為行特征的唯一標(biāo)識(shí)，將列向量元素差異最小的圖片聚類(lèi)，分別將中文和英文的歸類(lèi)。然后通過(guò)人為干預(yù)實(shí)現(xiàn)類(lèi)的合并，將中英文都聚成同樣數(shù)目的類(lèi)，每一類(lèi)包含相同張數(shù)的碎片。構(gòu)建行內(nèi)碎片的左右邊界匹配模型，最終確定出每類(lèi)內(nèi)部碎片的排序。第二層做列位置篩選，建立上下邊界匹配模型（與左右邊界匹配法類(lèi)似）得出各行的上下位置序列，經(jīng)過(guò)兩層篩選，得出原碎片序列。

除前方法外，需要構(gòu)建中文特征灰度條向量

當(dāng)特征值屬于合適小的置信區(qū)間時(shí)，即Wk，s∈[a，b]時(shí)，認(rèn)為兩碎片在同一行。

②法二：法二則需加入基于文本行特征的碎片行分組，行分組方法類(lèi)似于法一中對(duì)英文的分組方法，對(duì)行分組碎片進(jìn)行橫向拼接得到復(fù)原的碎片行，再對(duì)碎片行進(jìn)行縱向拼接，得到復(fù)原結(jié)果。

3、針對(duì)既橫切又縱切的雙面印刷文件碎片

①法（一）：由于雙面我們需要進(jìn)行兩次特征匹配，一次是碎片k與s的a面，另一次是碎片k的b面與碎片s的a面。得到a面和b面的特征列向量。綜合兩次特征匹配結(jié)果，以及左右和上下邊界匹配模型，加入人工干預(yù)，根據(jù)文件碎片內(nèi)容以及文字邊緣是否契合，得到正確碎片匹配序列。

②法（二）：因?yàn)閮擅?，故匹配距離需替換為兩面的匹配距離之和。在對(duì)碎片行做縱向拼接minfk（π） k=1，2，...，nr時(shí)，將基于旅行商問(wèn)題的拼接策略擴(kuò)展為多旅行商（兩個(gè)旅行商）問(wèn)題的拼接策略，即一條旅行商路徑代表紙張一面，另一條代表另一面，目標(biāo)函數(shù)變?yōu)?img src="https://cimg.fx361.com/images/2016/02/09/qkimageszgxtzgxt201613zgxt201613123-5-l.jpg"/>

二、對(duì)于文字的不規(guī)則的文件碎片拼接方法

1、斜切情況。我們?cè)O(shè)想找到平行于碎片中文字的直線斜率，找到圖片1-x列，每一列最上面像素值為0的點(diǎn)，從x個(gè)點(diǎn)中選出最上面的點(diǎn)。同理得到個(gè)（m-x）-m（m為碎片圖的寬度）列中處于最上面像素值為0的點(diǎn)。由這兩個(gè)點(diǎn)得到平行于碎片中文字方向直線，再根據(jù)找到直線的斜率對(duì)碎片進(jìn)行角度調(diào)整，最后用同規(guī)則碎片的方法進(jìn)行匹配。

2、無(wú)規(guī)則情況。利用形狀匹配法，提取碎紙片輪廓線，通過(guò)邊界和面積準(zhǔn)則判斷兩輪廓是否匹配。在這里我們參考了賈海燕[1]女士研究的一種碎紙自動(dòng)拼接中的形狀匹配方法。設(shè)想給定兩個(gè)碎片，確定兩碎片輪廓形狀之間是否存在匹配部分，選擇任意一個(gè)碎片，把它放在參考坐標(biāo)系中，稱(chēng)為固定碎片，并選定一個(gè)比較長(zhǎng)度。

Step1：固定碎片從最高點(diǎn)象素開(kāi)始取一組長(zhǎng)度的象素作為固定鏈，在另一個(gè)將要進(jìn)行比較的碎片上最高點(diǎn)開(kāi)始取相同定長(zhǎng)叫做旋轉(zhuǎn)鏈，將旋轉(zhuǎn)鏈?zhǔn)Ｓ嘞笏剡M(jìn)行旋轉(zhuǎn)和平移，固定鏈所取定長(zhǎng)上最后幾個(gè)象素的垂線和旋轉(zhuǎn)鏈相交。重復(fù)步驟，直到每個(gè)象素都進(jìn)行過(guò)匹配。

Step2：再進(jìn)行碎片旋轉(zhuǎn)。一個(gè)碎片在任意旋轉(zhuǎn)一定角度之后，這個(gè)碎片的輪廓保持和它的方位相對(duì)應(yīng)。假如選擇一度一旋轉(zhuǎn)，那么這個(gè)碎片必須在參考坐標(biāo)系里旋轉(zhuǎn)360個(gè)位置，每個(gè)輪廓都是有可能匹配的位置。

Step3：運(yùn)用最優(yōu)匹配算法，即先取定一個(gè)碎片確定固定鏈，長(zhǎng)度m，再取另一碎片確定旋轉(zhuǎn)鏈，長(zhǎng)度仍為m。經(jīng)過(guò)旋轉(zhuǎn)和平移，使這兩個(gè)碎片滿足邊界和面積匹配準(zhǔn)則。

Step4：進(jìn)行文件碎片拼接優(yōu)化，將這兩個(gè)已經(jīng)匹配好的碎片作為一個(gè)新的固定碎片，用第三個(gè)碎片進(jìn)行匹配，方法同上，并微調(diào)第二個(gè)碎片，使其位置更合理。

Step5：依次進(jìn)行直到復(fù)原完整。

三、對(duì)于圖片的不規(guī)則文件碎片拼接[3]

我們主要研究運(yùn)用特征點(diǎn)匹配的快速圖像拼接算法。首先對(duì)圖像進(jìn)行預(yù)處理。然后，采用Harris特征點(diǎn)提取的方法，對(duì)待拼接圖像進(jìn)行特征點(diǎn)的提取，利用基于灰度互相關(guān)的方法對(duì)圖像進(jìn)行初匹配。其次，用基于歐氏距離的聚類(lèi)預(yù)篩選算法，主要依據(jù)匹配點(diǎn)對(duì)之間的歐氏距離相同或相近這一特點(diǎn)，通過(guò)簡(jiǎn)單聚類(lèi)的方法篩選出包含歐氏距離值點(diǎn)最多的鄰域，則可認(rèn)為該鄰域內(nèi)的距離值是匹配點(diǎn)對(duì)；反之，則認(rèn)為是不匹配點(diǎn)對(duì)從候選匹配點(diǎn)對(duì)集中剔除，并運(yùn)用RANSAC算法對(duì)匹配點(diǎn)集進(jìn)行精確匹配。最后運(yùn)用基于LM加權(quán)融合與拉普拉斯金字塔相結(jié)合的圖像融合算法，有效消除拼接縫及亮度突變現(xiàn)象，以實(shí)現(xiàn)圖像的無(wú)縫平滑拼接。

四、對(duì)于含表格線的不規(guī)則文件碎片拼接方法

我們希望利用文字行特征[2]和表格線的方向來(lái)拼接形狀相似的文件碎片。先對(duì)文件碎片進(jìn)行二值化處理，獲取文字邊界，進(jìn)而獲取文字行方向、間距、高度等文字行特征。如果有英文漢字，應(yīng)將英文單詞圖像拆分成類(lèi)漢字圖像，即將英文單詞圖像分割成寬度與高度近似的類(lèi)漢字圖像。

以碎片某點(diǎn)作為坐標(biāo)原點(diǎn)，水平方向作為X軸方向，垂直方向作為Y軸方向，在[-90°，90°]范圍內(nèi)等角取60個(gè)方向，再將每個(gè)選定方向作為新坐標(biāo)系的X軸方向，求原像素點(diǎn)。坐標(biāo)變換后新坐標(biāo)如果不是整數(shù)，則按4舍5入法取值。像素點(diǎn)在新坐標(biāo)系下只改變坐標(biāo)值，其顏色屬性不變。再求新坐標(biāo)系下碎紙片邊緣的最高點(diǎn)和最低點(diǎn)坐標(biāo)，從最低點(diǎn)開(kāi)始給每行（具有相同Y坐標(biāo)）從1開(kāi)始編號(hào)，計(jì)算每行的白點(diǎn)個(gè)數(shù)、紅點(diǎn)個(gè)數(shù)、寬度（像素個(gè)數(shù)）。根據(jù)每行的紅點(diǎn)、白點(diǎn)個(gè)數(shù)及碎片寬度計(jì)算該方向的文字圖像個(gè)數(shù)總數(shù)以及文字行行高總和，并按從大到小排列，選文字圖像個(gè)數(shù)最多、文字行行高和最小的方向作為碎片的文字行方向。

一般碎片內(nèi)表格線的方向與文字行方向平行，且只沿一個(gè)方向分布，可采用類(lèi)似于文字行方向的掃描方法獲取表格線方向。再將碎片按此方向重新放置，此后文字方向可能朝上或朝下，故加入人工干預(yù)進(jìn)行圖片翻轉(zhuǎn)。將兩碎片按文字行方向線位置對(duì)齊，然后計(jì)算文字行方向線或表格線與碎片邊界的交點(diǎn)與處于同一水平位置的另一個(gè)碎片交點(diǎn)的距離。若兩碎片在拼接位置對(duì)齊，則點(diǎn)與對(duì)應(yīng)點(diǎn)距離相等，拼接后與對(duì)應(yīng)點(diǎn)變?yōu)橥稽c(diǎn)。若未對(duì)齊，則其距離相等的連續(xù)點(diǎn)的個(gè)數(shù)比對(duì)齊位置的要少。

參 考 文 獻(xiàn)

[1] 賈海燕，朱良家，周宗潭，胡德文，一種碎紙自動(dòng)拼接中的形狀匹配方法 ，（國(guó)防科學(xué)技術(shù)大學(xué)機(jī)電工程與自動(dòng)化學(xué)院自動(dòng)控制系，長(zhǎng)沙湖南410073）

[2]羅智中，基于文字特征的文檔碎紙片半自動(dòng)拼接，計(jì)算機(jī)工程與應(yīng)用，2012，48（5），207

[3]韓松衛(wèi)，于明，運(yùn)用特征點(diǎn)匹配的圖像快速拼接算法研究，河北工業(yè)大學(xué)，控制科學(xué)與工程