無重疊的文檔碎片拼接方法

(吉林化工學院理學院，吉林吉林132022)

在文物修復、司法物證鑒定等領域普遍存在著碎片拼接問題，但目前碎片拼接工作幾乎都是以手工方式完成的.當碎片的數量增大到一定程度時，如果仍然依靠手工完成，不但耗費大量的人力、物力，而且還可能對物件造成一定的損壞.很多碎片拼接問題都可以歸結為或近似為二維碎片的拼接問題，碎紙拼接是其中的典型問題.對二維碎片自動拼接問題的研究，不僅具有廣闊的應用前景，而且具有很強的理論意義.

常規文檔碎紙片計算機拼接方法一般利用碎片邊緣的尖點特征、尖角特征、面積特征等幾何特征，搜索與之匹配的相鄰碎紙片并進行拼接［-6］，這種基于邊界幾何特征的拼接方法并不適用于邊緣形狀相似的碎紙片.如果碎片內的文字在碎片邊緣斷裂，那么與它相鄰的碎片在邊緣處一定具有相似的灰度值，并且針對橫向切割的碎片具有相同的文字寬度，憑以上特征可以找到與其相鄰碎片.基于上述思想，本文針對縱切的文檔圖片提出一個簡單的方法來實現碎片的完整拼接.

1 無重疊的文檔碎片拼接方法

針對存在重合區域的碎片拼接問題，已取得了顯著的成果，其中使用較多的是基于特征的圖像拼接方法.然而對于無重疊的碎片拼接問題，現有的技術并不成熟.本文提出一個簡單易行的方法來完成這項看似復雜的工作.算法的具體流程如下:

1.1 圖像預處理

由于碎片通常都是手動使用掃描儀將文檔碎片傳輸到計算機中，因此要對得到的碎片進行預處理.對于碎片的預處理包括提取灰度值及二值化.

碎片文件屬于bmp位圖文件，灰度化的目的是將24位顏色圖像轉換成8位灰度圖像.由于光照不均勻的原因，碎片的文字可能會出現部分較暗或較亮的情況，因此需要將碎片的灰度值進行二值化.對碎片的像素點做如下處理:

Step 1:計算整幅圖像的全局平均灰度值M.

Step 2:比較所有像素點灰度值和全局平均灰度值M的大小，如果像素灰度值大于或等于M，則直接將像素點置為255，如果像素灰度值小于M，則直接將像素點置為0.

1.2 提取圖片邊緣，確定文檔最左邊碎片

將碎片的灰度值矩陣的最左邊和最右邊的兩列分別作為碎片的左右邊緣.通常碎片內的文字會在碎片邊緣斷裂，這樣就可以有理由認為如果碎片的左邊緣的灰度值都為255，則此幅圖片為文檔的最左側碎片，見圖1.

圖1 算法流程圖

1.3 計算邊緣相似性，根據最大匹配原則，確定其右側拼接碎片

首先利用夾角余弦來度量當前碎片的右邊緣與其它碎片左邊緣的相似性，其中夾角余弦法定義如下［7］:

夾角余弦取值越大表明兩向量夾角越小，兩者越接近，值為1時，兩向量完全相同.另外，夾角余弦規范化了向量長度，這意味著在計算相似度時，不會放大數據對象重要部分的作用［8］.

計算當前碎片的右邊緣與其它所有碎片的左邊緣的相似性，從中找到與當前碎片右邊緣最相似性的左邊緣所對應的碎片，將兩個碎片進行拼接.

1.4 判斷當前碎片是否為文檔最右側碎片

基于與2.2部分類似的分析，則如果碎片的右邊緣灰度值均為255，則此幅圖片為文檔的最右側碎片.

2 實驗結果

本文將提出的算法利用數學應用軟件Matlab進行編程實現.以一張被縱切成19條碎片的印刷文字文件為例，應用本文提出的方法對其進行拼接，其中縱切后的碎片如圖2所示.

圖2 待拼接的文檔碎片

首先將碎片進行圖像預處理，然后判斷出此類碎片為無重疊區域，利用本文提出的方法找到第9個碎片為最左邊碎片，根據邊緣相似性找到與該碎片右邊緣最大匹配的左邊緣所在的碎片作為鄰接碎片進行拼接，以此類推直至拼接到最右邊碎片(第7個碎片)，拼接結果如圖3所示.

圖3 文檔拼接結果

3 結 論

本文針對無有效重疊區域的文檔碎片的拼接問題進行了探索性的研究，給出了一個簡單有效的方法用以解決此類問題.但是本文僅提出針對縱切的文檔碎片拼接方法，而對于縱切與橫切結合以及文檔中含有圖片等特殊情況將作為下一步的研究重點.

［1］ 王磊，莫玉龍，戚飛虎.基于Canny理論的邊緣提取改善方法［J］.中國圖象圖形學報.1996，1(3):191-195.

［2］ 陶波，于志偉，鄭筱祥.圖像的自動拼接［J］.中國生物醫學工程學報.1997，16(4):29-35.

［3］ 鐘家強，王潤生.基于邊緣的圖像配準改進算法［J］.計算機工程與科學.2001，23(6):25-29.

［4］ 劉金根，吳志鵬.一種基于特征區域分割的圖像拼接算法［J］.西安電子科技大學學報.2002，29(6):768-771.

［5］ 周鵬，譚勇，徐守時.基于角點檢測圖像配準的一種新算法［J］.中國科學技術大學學報.2002，32(4):455-461.

［6］ 朱延娟，周來水.二維非規則碎片的匹配算法［J］.計算機工程.2007，33(24):7-9.

［7］ 牛小兵，林玉池，趙美蓉，等.基于特征的二維圖像拼接法測量幾何量［J］.天津大學學報.2001.34(3):369-399.

［8］ H.Chang，F.H.Cheng，W.H.Hsu，GZ.WU.Fast algorithm for Point Pattem matching:Invariant to translations rotations and seale changes［J］，Pattern Reeognition.1997，30(2):311-320.

［9］ H.GBaJow，J.M.Tenenbaum，R.C.Bolles，H.C.Wolf.Parametric correspondence and Chamfer matching:Two new techniques for image matching［J］.Proceedings of the Fifth Intemational Joint Conference on Artificial Ihtelligence， Cambridge， Massachusetts，1977，1:659-670.

［10］ A，Goshtasby，G.C.Stockman，C.VPage.A regionbased approach to digital image Registration with subpixel aceuracy［J］，IEEE Transactions on Geoscience and Remote Sensing，1986，24(3):390-399.

［11］張宇，劉雨東，計釗.向量相似度測度方法［J］.聲學技術，2009，28(4):532-536.

［12］ TIAN Runtao，XIE Peishan.Study on the standardization of similarity evaluation method of chromatographic fingerprints(Part I)［J］.Traditional Chinese Drug Research ＆ Clinical Pharmacology，2006，17(1):40-42.