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

謝 行 王文博 易繼榮

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

謝 行1王文博2易繼榮3

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

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

灰度匹配；邊緣檢測(cè)；碎紙拼接；Matlab

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

1 模型的建立

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

1.1 灰度匹配模型的建立

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

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

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

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

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

而考慮到所謂的“噪聲”的影響［2］，我們?cè)诖瞬捎靡粋€(gè)閾值加以控制，此閾值可根據(jù)灰度數(shù)以及實(shí)驗(yàn)的結(jié)果進(jìn)行調(diào)整，我們?cè)诖巳棣痢?/p>

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

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

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

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

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

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

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

圖2 不同對(duì)齊位置碎片

2 模型的求解

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

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

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

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

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

2.2 縱橫向碎紙的拼接

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

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

圖3 算法流程圖

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

3 結(jié)語(yǔ)

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

此時(shí)我們無(wú)法判定與Si最接近的碎片即失效，但是總體上來(lái)看，此方法有一定的優(yōu)越性。對(duì)于文字行高進(jìn)行匹配時(shí)，不能達(dá)到完全的自動(dòng)化，需要適當(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)樂(lè)，康耀紅，伍小芹.基于顏色特征圖像檢索方法的研究［J］.信息技術(shù)，2008（11）：4-7.

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

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

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

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

［8］ 張素，蘇和，陸雪松，等.基于形狀匹配的快速圖像配準(zhǔn)［J］.天津大學(xué)學(xué)報(bào)，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è)計(jì)方法和水動(dòng)力研究。