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

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

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

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

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

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

1.1 圖像預(yù)處理

由于碎片通常都是手動使用掃描儀將文檔碎片傳輸?shù)接?jì)算機(jī)中，因此要對得到的碎片進(jìn)行預(yù)處理.對于碎片的預(yù)處理包括提取灰度值及二值化.

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

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

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

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

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

圖1 算法流程圖

1.3 計(jì)算邊緣相似性，根據(jù)最大匹配原則，確定其右側(cè)拼接碎片

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

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

計(jì)算當(dāng)前碎片的右邊緣與其它所有碎片的左邊緣的相似性，從中找到與當(dāng)前碎片右邊緣最相似性的左邊緣所對應(yīng)的碎片，將兩個(gè)碎片進(jìn)行拼接.

1.4 判斷當(dāng)前碎片是否為文檔最右側(cè)碎片

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

2 實(shí)驗(yàn)結(jié)果

本文將提出的算法利用數(shù)學(xué)應(yīng)用軟件Matlab進(jìn)行編程實(shí)現(xiàn).以一張被縱切成19條碎片的印刷文字文件為例，應(yīng)用本文提出的方法對其進(jìn)行拼接，其中縱切后的碎片如圖2所示.

圖2 待拼接的文檔碎片

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

圖3 文檔拼接結(jié)果

3 結(jié) 論

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

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

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

［3］ 鐘家強(qiáng)，王潤生.基于邊緣的圖像配準(zhǔn)改進(jìn)算法［J］.計(jì)算機(jī)工程與科學(xué).2001，23(6):25-29.

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

［5］ 周鵬，譚勇，徐守時(shí).基于角點(diǎn)檢測圖像配準(zhǔn)的一種新算法［J］.中國科學(xué)技術(shù)大學(xué)學(xué)報(bào).2002，32(4):455-461.

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

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

［8］ H.Chang，F(xiàn).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ì)釗.向量相似度測度方法［J］.聲學(xué)技術(shù)，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.