基于聚類分析的雙面文檔半自動拼接

梁慧超　于紅斌　喬路遙　崔玉亮

摘 要：針對雙面規格碎片，提出了一種基于聚類分析的半自動拼接方法。根據碎片邊緣的文字特征，構造碎片的相似性判別函數，進行最大相似性判別并聚類分析，找到同一行的碎片排列，最終實現了文檔的橫向、縱向拼接，在MATLAB下的實驗表明該算法效率高，相對人工干預少。

關鍵詞：聚類分析；邊緣特征提取；碎紙片拼接

碎紙片的人工拼接復工作效率很低，隨著計算機技術的發展，人們試圖開發碎紙片的自動拼接技術，以提高拼接復原效率。目前，國內外在碎片拼接技術的研究中已經取得了一定的成就，如：Ying Shan等提出了一種概率框架的曲線匹配算法[1]，李軍等人提出一種改進Harris算子的圖像拼接方法[2]，何鵬飛等人提出了基于蟻群優化算法的碎片拼接技術[3]，但這些算法主要解決單面不規則碎片的輪廓提取及匹配上，對于碎片雙面均有文字且碎片數量巨大的情況難以適用。

針對當前圖像拼接技術的缺陷，本文充分利用文字行的行高、文字行的間距等信息，對碎片進行分類，并綜合采用相似性判別函數和聚類分析，最終將同一行的碎片劃為一類，拼接時利用碎紙片的邊界矩陣，進行最小絕對值距離判別，從形狀相似的多碎片中挑選出相鄰碎片。該方法便于理解，利用MATLAB軟件，容易實現。

1 拼接原理

碎片拼接由于碎片數目過多，故不能人為的進行全過程拼接。首先要將根據碎片特征利用相似性判別函數分進行分類，然后利用聚類分析將屬于同一面同一行的碎片聚成一類，在人工篩選劃錯行的圖片后，對碎紙片進行橫向和縱向拼接即可。

聚類分析是一組將研究對象分為相對同質的群組的統計分析技術，其依據研究對象（樣品或指標）的特征，對研究對象進行分類，達到減少研究對象的數目的目的。因為文檔的行高、字間距具有一定規律性，因此可以依據每張碎片的特征，進行聚類分析。

2 拼接步驟

2.1 觀察碎片特征

通過觀察碎片，根據碎片中完整文字行數、完整空白行數，碎片上方是否為空白、碎片下方是否為空白等特征人工將碎片分為N類。以文獻[5]中數據為例，a有3行完整文字、兩行完整空白、上方為空白、下方為空白；b有兩行完整文字、兩行完整空白、碎片上方為空白、碎片下方不為空白；c有兩行完整文字、兩行完整空白、碎片上方不為空白、碎片下方為空白，這3張碎片分別屬于3大類。

人為地將文檔分為N類后，挑選出屬于每一類的碎片一張作為比較對象，任意碎片Si的特征矢量，求每一個碎片在第i類碎片上的矢量與該矢量上的特征矢量的距離，進行最大相似性判別，為每一碎片分類。但由于文檔的雙面性，可能會存在差錯，為了讓位于同一面同一行的碎片聚在一起，在劃分好的每一類中，提取各個碎片的反面進行聚類分析，將這些碎片分為m類后，仍需要人工將少數不屬于該行的碎片劃分開來。

2.2 相鄰碎片拼接

若想要找出其左鄰碎紙片，只需提取每個碎紙片像素矩陣最左邊的一列和最右邊的一列，記每個碎紙片的像素矩陣中的最左邊一列為ιi，同理，提取每個碎紙片的最右邊一列為ri，計算兩碎片的相關程度時，可以用絕對值距離[3]表示，此時的目標函數即求下式的最小值：

其中，xik表示像素矩陣第k行的ιi的值，yik表示ri的第k行的值。當k從第1行取到第最后一行時，若此差值的絕對值和最小，則表示兩個左右兩個邊緣的相似性越高，即可認為這兩個矩陣是左右相鄰的即可確定每個碎紙片左右相鄰的碎紙片，從而獲得橫向同一行上各碎片的排列順序，同理，用同樣方法可獲得縱向各行的排列順序，從而得到拼接復原的完整圖像。

3 拼接試驗

根據該算法研制了MATLAB程序，并對一實際碎紙片進行了拼接試驗。將碎紙片平均切割為418塊，根據文字行的分布形式及空白行高人為的將碎紙片分為5類，用MATLAB中的相似度函數對418張碎片做相似處理并用SPSS對該矩陣做聚類分析，然后施加人工干預，將這些圖片插入到正確的行類中，最后進行橫向縱向拼接。拼接結果的部分圖像見圖2。

試驗表明本文提出的半自動拼接算法誤差率較小。

4 結束語

本文提出了基于聚類分析的雙面文檔碎片半自動拼接方法，實現簡單，但只適用于橫向、縱向切割的文檔碎紙片的拼接，需要加入兩次人工干預。

碎片文件的拼接在現實生活中有著廣泛的應用，在司法物證復原、歷史文獻修復、軍事情報獲取、虛擬仿真培訓、工業制造設計等領域，有一定的指導意義。

[參考文獻]

[1]Ying Shan etc.New Measurements and Corner一Guidance for Curve Matching With Probabilistic Relaxation[J].International Journal of Computer Vision.2002，46（2）：157-171.

[2]李軍，吳潔明.一種改進圖像拼接算法的仿真研究[J].計算機仿真，2012，29（2）：273-313.

[3]何鵬飛.基于蟻群優化算法的碎紙拼接[D].國防科學技術大學，2005.

[4]程永清，莊永明，楊靜宇.基于矩陣相似度的圖像特征抽取和識別[J].計算機研究與發展，1992，14（5）：42-48.

[5]全國大學生數學建模（官網）.2013賽題：[DB/OL]，教育部高等教育司和中國工業與應用數學協會，2013[2013-9-11].http：//www.mcm.edu.cn/problem/2013/2013.html.

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