王煜琪

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

【關鍵字】 圖像處理 文件碎片復原 拼接 邊界匹配 像素提取

一、引言

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

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

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

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

①法一：

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

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

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

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

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

除前方法外，需要構建中文特征灰度條向量

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

②法二：法二則需加入基于文本行特征的碎片行分組，行分組方法類似于法一中對英文的分組方法，對行分組碎片進行橫向拼接得到復原的碎片行，再對碎片行進行縱向拼接，得到復原結果。

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

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

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

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

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

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

Step1：固定碎片從最高點象素開始取一組長度的象素作為固定鏈，在另一個將要進行比較的碎片上最高點開始取相同定長叫做旋轉鏈，將旋轉鏈剩余象素進行旋轉和平移，固定鏈所取定長上最后幾個象素的垂線和旋轉鏈相交。重復步驟，直到每個象素都進行過匹配。

Step2：再進行碎片旋轉。一個碎片在任意旋轉一定角度之后，這個碎片的輪廓保持和它的方位相對應。假如選擇一度一旋轉，那么這個碎片必須在參考坐標系里旋轉360個位置，每個輪廓都是有可能匹配的位置。

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

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

Step5：依次進行直到復原完整。

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

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

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

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

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

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

參 考 文 獻

[1] 賈海燕，朱良家，周宗潭，胡德文，一種碎紙自動拼接中的形狀匹配方法 ，（國防科學技術大學機電工程與自動化學院自動控制系，長沙湖南410073）

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

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