謝 行 王文博 易繼榮

碎紙片拼接復(fù)原的灰度匹配技術(shù)研究

謝 行1王文博2易繼榮3

（1.哈爾濱工程大學(xué) 船舶工程學(xué)院，哈爾濱 150001；2.哈爾濱工程大學(xué) 水聲工程學(xué)院，哈爾濱 150001；3.哈爾濱工程大學(xué) 理學(xué)院，哈爾濱 150001）

鑒于破碎的文獻(xiàn)資料在諸多領(lǐng)域里有著廣泛的應(yīng)用，本文通過對兩種主要而又典型的破碎文獻(xiàn)資料——縱向（橫向）破碎、縱橫向破碎的文獻(xiàn)資料的拼接與復(fù)原問題進(jìn)行分析，根據(jù)破碎紙張的大小，文字的間距等信息建立灰度匹配模型和邊緣檢測模型，并通過相關(guān)的算法，編寫Matlab程序來解決碎紙片拼接復(fù)原問題。

灰度匹配；邊緣檢測；碎紙拼接；Matlab

破碎文獻(xiàn)資料的復(fù)原在當(dāng)今社會諸多領(lǐng)域有著重要作用，傳統(tǒng)意義上的拼接復(fù)原方法由于低效高耗等缺點(diǎn)對于當(dāng)今社會而言已不是最佳選擇。超多的破碎文件的碎片、人們對于高效率的追求、計算機(jī)圖像處理技術(shù)的迅速發(fā)展都呼喚著新的拼接復(fù)原方法的出現(xiàn)?？紤]到對于文字資料（即使是純粹的黑白版的），其圖像是具有一定的數(shù)字或數(shù)量特征的，例如像素值、強(qiáng)度曲線、等值曲線等，通過對這些數(shù)學(xué)特征的分析，可以提供文字資料拼接與復(fù)原的依據(jù)，因而總體上可以采用圖像處理的相關(guān)理論及分析與處理方法予以解決。

1 模型的建立

基于當(dāng)代圖像處理技術(shù)的相關(guān)理論，對于破碎的文字資料可以通過將其做成電子資料，進(jìn)而借助圖像處理軟件如Matlab得到表征圖像特征的數(shù)量特征例如像素值、強(qiáng)度曲線、輪廓曲線等，這樣就可以以其中的某些數(shù)量特征來作為匹配的條件對破碎的文字資料進(jìn)行匹配，建立灰度匹配模型。

1.1 灰度匹配模型的建立

對于任意第i塊碎片，通過Matlab圖像處理工具得到其灰度矩陣［1］：

對于任意縱橫切割的文字資料碎片，均存在四個切割邊緣特征函數(shù)分別對應(yīng)上下左右四個切割邊緣，這里以式（1）-（4）成立：

對于任意兩塊碎片，當(dāng)其以任意方式匹配時，這里不妨以第i塊碎片的左邊緣與第j塊碎片的右邊緣匹配，則其距離函數(shù)為：

規(guī)范化并且化簡，同時按“1”為完全相似，“0”為完全不相似來確定匹配的正確性，那么可以以（6）式描述：

其中n為灰度級數(shù)，sik，sjk均為非負(fù)。由上分析知若Sim靠近1，則說明兩碎片拼接情況較好，否則不好。

而考慮到所謂的“噪聲”的影響［2］，我們在此采用一個閾值加以控制，此閾值可根據(jù)灰度數(shù)以及實(shí)驗(yàn)的結(jié)果進(jìn)行調(diào)整，我們在此取為α。

同時考慮到對任意邊緣上不同的灰度級的重要性活優(yōu)先級是不同的，因而我們采用權(quán)重因子Wi( 0≤Wi≤1)，i的取值為1、2、3、…、n，從而（6）式轉(zhuǎn)化為：

然而由于Wi(0≤Wi≤1)，導(dǎo)致Sim（的下降，沒有反應(yīng)出重要成分的地位，為此我們將（7）式調(diào)整為（8）式：

即從n個顏色級中選取m個最大的單元值進(jìn)行求和平均。由此公式，結(jié)合相似性方法，可確定重要特征或特征的組合，最終實(shí)現(xiàn)碎片的拼接與復(fù)原［3-4］。

1.2 文字行高與行間距匹配模型的建立

拼接碎片前，先對圖像進(jìn)行二值化處理，不妨借助Sobel梯度算子或其他算子［5］對碎片進(jìn)行處理以獲取文字邊界，進(jìn)而獲取碎片內(nèi)文字行方向、高度、行間距等文字行特征，同時以特殊標(biāo)志標(biāo)記大于給定閾值的點(diǎn)和不大于閾值的點(diǎn)。

拼接碎片時先將兩個碎片按文字行方向線位置對齊，然后計算文字行方向線或表格線與碎片邊界的交點(diǎn)與處于同一水平位置的另一個碎片交點(diǎn)的距離，見圖1，分別計算點(diǎn)A、B、C、D、E與另一個碎片邊界對應(yīng)交點(diǎn)的距離。計算兩點(diǎn)距離時所采用的點(diǎn)坐標(biāo)可用局部坐標(biāo)，即取碎片內(nèi)某固定點(diǎn)作為參考點(diǎn)，其他點(diǎn)的坐標(biāo)取對該點(diǎn)的相對坐標(biāo)。如果兩碎片在拼接位置對齊，則點(diǎn)A、B、C、D與對方交點(diǎn)距離相等，拼接后與對方對應(yīng)點(diǎn)變?yōu)橥稽c(diǎn)。如果碎片沒有對齊，則距離相等的連續(xù)點(diǎn)的個數(shù)比對齊位置的距離相等連續(xù)點(diǎn)的個數(shù)要少，見圖2上下部分，其中的水平線為參考水平線，垂直線段表示文字行方向線，圖2下部分中距離相等的連續(xù)點(diǎn)的個數(shù)比圖2上部分中距離相等的連續(xù)點(diǎn)的個數(shù)少，表明圖2上部分的對齊位置比圖2下部分對齊位置更符合實(shí)際拼接位置［6］。

圖1 對齊碎片邊界交點(diǎn)距離

圖2 不同對齊位置碎片

2 模型的求解

本文以縱向和縱橫向碎片為例進(jìn)行分析求解，對模型的正確性及合理性進(jìn)行驗(yàn)證。

2.1 縱向（橫向）碎紙的拼接

對于縱（橫）向碎紙的拼接，本文選取編號000，001，…，018的19個縱向碎紙片作為拼接材料。本文先通過Matlab生成灰度矩陣，取每個矩陣的第一列和最后一列作為其特征屬性，再找出最左邊的紙片作為拼接的起點(diǎn)，通過相應(yīng)的灰度算法找出匹配最好的一列，與拼接起點(diǎn)的紙片相連接，最后再將被匹配的紙片作為拼接的起點(diǎn)，進(jìn)行匹配，如此循環(huán)直至匹配完成。

依據(jù)Matlab尋找給定碎片中從左向右匹配的初始生成碎片的程序運(yùn)行得到如下結(jié)果中只有008編號的數(shù)據(jù)列有全為255的一列（即白邊）。事實(shí)上對于給定的碎片，發(fā)現(xiàn)除去碎片序列008其余所有的碎片均有雙邊切割的痕跡且序列008只有右單側(cè)的切割痕跡，故而容易得到其最左邊碎片的序列號為008。

通過Matlab的圖形處理工具易得到所有19條碎片的左右兩側(cè)邊緣灰度矩陣共38個。結(jié)合灰度矩陣以及最初生成碎片，我們可以開始進(jìn)行匹配計算，比較上述結(jié)果發(fā)現(xiàn)序列008與序列014的距離函數(shù)值最小，故而此二者為正確的拼接方式，即序列008為初始生成碎片，序列014是第二號。同理可以得到其后正確的序列號排序應(yīng)當(dāng)為012，015，003，010，002，016，001，004，005，009，013，018，011，007，017，000，006。經(jīng)過拼接合成，可以看到對于縱（橫）向碎紙，該方法準(zhǔn)確率達(dá)到100%。

2.2 縱橫向碎紙的拼接

對于縱橫向碎紙的拼接，本文選取縱向?yàn)?9列橫向?yàn)?1行的編號從1到209的碎紙片作為拼接材料。本文先通過Matlab生成灰度矩陣，取每個縱向碎紙片的灰度矩陣的第一列和最后一列作為其特征屬性，設(shè)碎片像素高度為L，每一行的像素寬度保存在數(shù)組pntCnt（k）（k=1，2，3，…，L）內(nèi)，每行的行間距保存在數(shù)組blankCnt（k）（k=1，2，…，L）中，總的圖像文字個數(shù)設(shè)為CharSum，文字行高和變量為Char-Height，令其初值為0，則文字圖像個數(shù)與文字行高和可按圖3中算法求解［7］。

通過以上算法，借助Matlab程序得到按文字的行高行間距匹配模型求解，實(shí)際情況下在匹配的同時仍然剩余未匹配的碎片，但此處先不考慮這些單個碎片。在上述求得的多條一次級行帶中，再對每一行帶在帶內(nèi)采用灰度匹配模型進(jìn)行求解.同樣得到在此第二次級的匹配中無法滿足條件的碎片35，67，98，136，147，183，201，203，但此時先不考慮它。對這些滿足正確排序的條帶采用顏色（灰度）模型中縱向匹配的方式予以匹配。通過合成統(tǒng)計，拼接正確的有189，無正確拼接的有20，準(zhǔn)確率達(dá)到了94.5%。到此為了正確拼接的拼接可以采用人工的方法將其補(bǔ)入所得圖片中，即可得到結(jié)果如表1所示：

圖3 算法流程圖

表1 縱橫自碎紙拼接結(jié)果計表

3 結(jié)語

顏色（灰度）匹配模型對于快速匹配的圖像的取得較好的結(jié)果，能夠準(zhǔn)確的將碎紙片進(jìn)行拼接復(fù)原，文字行高行間距模型并不依賴于碎片的幾何特征，具有實(shí)現(xiàn)簡單，可靠性好等特點(diǎn)［8］。實(shí)際問題求解中，發(fā)現(xiàn)當(dāng)碎片總數(shù)小于400時，計算量都是在可接受范圍內(nèi)，可以對算法改進(jìn)來簡化計算量。當(dāng)然模型也存在不足，例如說一旦存在諸多灰度值極為接近的情況，此法的效用會因此受到影響，因?yàn)榇藭r存在多個碎片Sk，Sj，Sl等同時與Si的歐式距離相近甚至相等即

此時我們無法判定與Si最接近的碎片即失效，但是總體上來看，此方法有一定的優(yōu)越性。對于文字行高進(jìn)行匹配時，不能達(dá)到完全的自動化，需要適當(dāng)?shù)倪M(jìn)行人工干預(yù)，人工干預(yù)的頻數(shù)的減少將有待繼續(xù)研究。

［1］ 周孝寬，曹曉光，等.實(shí)用微機(jī)圖像處理［M］.北京：北航出版社，1995：37-45.

［2］ 丁慧珍，周紹光，馬文.一種改進(jìn)的灰度匹配新算法［J］.資源環(huán)境與工程，2006（1）：52-55.

［3］ 高進(jìn)樂，康耀紅，伍小芹.基于顏色特征圖像檢索方法的研究［J］.信息技術(shù)，2008（11）：4-7.

［4］ 舒付祥，孫繼銀.一種基于灰度特征的圖象匹配算法設(shè)計與研究［J］.計算機(jī)工程與應(yīng)用，2002（9）：5-7.

［5］ 吳小艷，王維慶，楊春祥，等.幾種基于模板匹配法的數(shù)字圖像識別算法分析［J］.計量技術(shù)，2005（6）：27-30.

［6］ 胡曉峰，劉毅.基于內(nèi)容檢索的顏色特征匹配方法［J］.小型微型計算機(jī)系統(tǒng)，1996（17）：6-11.

［7］ 羅鐘鉉，劉成明.灰度圖像匹配的快速算法［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2005（5）：966-977.

［8］ 張素，蘇和，陸雪松，等.基于形狀匹配的快速圖像配準(zhǔn)［J］.天津大學(xué)學(xué)報，2008（4）：433-438.

Research on Gray Matching Technology ofScrap Paper Restoration Recovery

XIE Hang1WANG Wen-bo2YI Ji-rong3

（1.College of Shipbuilding Engineering，Harbin Engineering University，Harbin 150001，China；2.College of Underwater Acoustic Engineering，Harbin Engineering University，Harbin 150001，China；3.College of Science，Harbin Engineering University，Harbin 150001，China）

Since the broken of the literature has been widely used in many fields，this article uses two main and typical broken literatures，namely，vertical and horizontal broken literatures，analyzing the joining together of literature and recovery problem. According to the size of the broken paper，text information such as the spacing，the gray matching model and edge detection model is established，and through the relevant algorithm，We write thematlab program to solve the scraps of paper splicing recovery problem.

splicing graymatching；edge detection；shredding；Matlab

O13

A

1009—0312（2014）03—0021—04

2014-03-14

謝行（1992—），男，河南駐馬店人，碩士研究生，主要從事現(xiàn)代船舶設(shè)計方法和水動力研究。