條狀碎片文件自動復(fù)原的探討與研究

劉俊瑋 王子豪 宋嵩燾

【摘要】破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用.有關(guān)碎片文件復(fù)原的研究已很多，而本文提出的條狀碎片文件復(fù)原無法用幾何形狀的方法，文中通過提取碎片剪裁邊緣的像素特征，構(gòu)建了基于其灰度值的相似指標(biāo)，并針對漢字與英文的不同特點(diǎn)，建立了普適較高的碎片復(fù)原數(shù)學(xué)模型，設(shè)計了相應(yīng)的算法，完成了對不同碎片的半自主拼接.

【關(guān)鍵詞】條狀碎片；文件復(fù)原；灰度；像素匹配

一、引 言

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用.傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低.特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù).隨著計算機(jī)技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率.但由于目前計算機(jī)數(shù)字分析圖像能力的限制，讓計算機(jī)對碎片進(jìn)行完全意義上的自動化拼接也幾乎不太可能.在以往的碎片文件復(fù)原中，由于碎片形狀都是不規(guī)則的，所以可以按幾何形狀匹配的方法使文件復(fù)原.在本文中對于條狀碎片文件復(fù)原問題，由于對應(yīng)的是規(guī)則碎片，無法采用常用的幾何形狀匹配的方法，筆者通過改進(jìn)只能用于規(guī)則碎片的zhegean復(fù)原方法，應(yīng)用于條狀碎片的匹配，通過采集碎片剪裁邊的像素點(diǎn)信息，建立一維匹配數(shù)學(xué)模型.由于單一條狀碎片能夠提供足夠多的匹配信息，利用該模型，無須進(jìn)行人為調(diào)整即可達(dá)到條狀碎片的完美拼接.

二、問題提出

對于給定的來自同一頁印刷文字僅縱切的碎紙片，并假定：

（1）剪裁后的碎片在邊緣處無像素?fù)p失；

（2）碎片不存在倒置或側(cè)置的拼接情況；

（3）所提供碎片能夠拼湊為完整文段，不存在錯誤碎片.

由于碎紙片均為條狀碎片或大小相同、形狀規(guī)則的矩形塊狀，因此無法采用典型的基于碎片邊緣幾何特征的拼接方法，也無法使用基于強(qiáng)大數(shù)據(jù)庫文字識別算法，只能依據(jù)圖形的像素分布特征進(jìn)行匹配.因此，本文依據(jù)圖像邊緣每一像素點(diǎn)的灰度值構(gòu)建匹配向量，引入相似性指標(biāo)，并建立像素點(diǎn)灰度匹配機(jī)制，同時輔以人工調(diào)整，最終完成匹配.

三、模型的建立與求解

任意一張圖片都相當(dāng)于是由一個個像素平鋪構(gòu)成的面，因此在碎片的邊緣分布著這樣一列像素點(diǎn)，它記錄了剪裁邊緣每一點(diǎn)的灰度值.若兩張碎片是相鄰的，當(dāng)有文字在剪裁邊緣被截斷時，其中一張碎片的左邊緣與另一張碎片的右邊緣在對應(yīng)的同一個像素點(diǎn)處的灰度值應(yīng)該十分接近，即當(dāng)有一黑色“橫”被截斷時，邊緣將有一系列像素點(diǎn)的灰度值均為0，因此也應(yīng)有另一碎片在對應(yīng)位置有一列像素點(diǎn)的灰度值為0去與之匹配，從而補(bǔ)全這一“橫”.

而在問題的假設(shè)中是針對完成條狀碎片的拼接，因而無須考慮上下邊緣的像素特征，而由于條狀碎片的左右邊緣較長，像素點(diǎn)分布較多，而不能匹配的任意兩塊碎片在左右邊緣處的像素應(yīng)該是差異明顯的，只需通過灰度值構(gòu)建匹配向量，比較像素點(diǎn)灰度值相似程度，即可完成匹配.

1.像素點(diǎn)灰度值相似性指標(biāo)的構(gòu)建

對于一張編號為i，由m×n個像素組成的碎片，取其邊緣每個像素點(diǎn)的灰度值r1，r2，…，rk（其中k=m，n），將其構(gòu)建為一匹配向量：

Ri=（r1，r2，…，rk）.1

圖1 匹配向量位置示意圖選取編號分別為i和j的兩塊碎片，在相同長度的剪裁處分別有各自像素點(diǎn)灰度值的匹配向量Ri和Rj，如圖1所示.

由于相鄰碎片在剪裁邊緣匹配向量近乎相同，為對比任意兩塊碎片邊緣處像素的相似程度，基于Euclidean距離，構(gòu)造像素灰度相似評價指標(biāo)：

fij=-∑ni，j=1

i≠j（Ri-Rj）2.2

圖2 任意碎片相似程度計算示意圖fij越大表明相似程度越高，Ri與Rj各個元素間越接近，即各個像素點(diǎn)灰度值越接近，從而說明兩塊碎片越有可能相鄰.由此可計算出任意一塊碎片左右兩個邊緣f1、 f2與其他碎片某一邊的相似程度，如圖2所示.

最終可以得到任意兩塊碎片間的相似程度，并得到相似矩陣：

F=f1，2…f1，n

fn-1…fn，n-1 .3

2.像素點(diǎn)灰度值的一維匹配模型的建立

令集合為復(fù)原前的碎片集合，并規(guī)定：

titj=1，ti與tj相鄰

0，ti與tj不相鄰4

從而建立一維像素灰度值匹配的規(guī)劃模型，即：

max a=∑fij

s.t. ti，tj∈S 5

titj=1

一維像素灰度匹配算法中，首先構(gòu)造像素灰度值構(gòu)成的向量，然后計算兩向量間的距離，距離越小則說明兩張碎片越有可能匹配，公式2中的距離fij表示兩個碎片相鄰像素點(diǎn)的灰度差，公式2是用來衡量整個剪裁邊緣的整體差異的.

（1）掃描讀取條狀碎片左右列邊緣的灰度值，并記錄得到匹配向量R=（r1，r2，…，rm），并確定起始碎片；

（2）記最后歸入的紙片為ti，遍歷所有的fij，tjS，選擇使fij的紙片tmax，令tmax∈S，使其排在ti的左側(cè)；

（3）重復(fù)（2），直至所有ti都屬于S；

（4）判斷結(jié)果是否正確.若正確，算法結(jié)束；否則，返回發(fā)生錯誤的節(jié)點(diǎn)進(jìn)行人工干預(yù)后繼續(xù)進(jìn)行.

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

實(shí)驗(yàn)材料用一個頁面的漢字紙質(zhì)材料，從縱向裁剪為成18條長條碎片，并給予隨機(jī)編號，部分漢字碎片如圖3（a）所示.同理英文紙質(zhì)材料，也從縱向裁剪為成18條長條碎片，并給予隨機(jī)編號，部分英文碎片如圖3（b）所示.分別把漢字與英文字母的條形碎片通過掃描后形成圖像文件，然后根據(jù)所建立的像素點(diǎn)灰度值的一維匹配模型公式5，應(yīng)用Matlab程序分別進(jìn)行求解，求解的最后結(jié)果是根據(jù)模型計算出各碎片復(fù)原后的編號排列.圖4、圖5所示分別是復(fù)原后漢字碎片圖像與英文碎片圖像.

圖3 復(fù)原前的漢字碎片圖像及英文碎片圖圖4 復(fù)原后的漢字圖像五、結(jié) 論

文中針對條狀碎紙的文件復(fù)原進(jìn)行研究，由于條狀碎紙的復(fù)原無法采用幾何形狀的圖像特征算法，而對于規(guī)則碎片而言只能通過采集碎片剪裁邊的像素點(diǎn)信息，建立一維像素灰度匹配碎紙片拼接復(fù)原數(shù)學(xué)模型，并針對給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原.由于單一條狀碎片能夠提供足夠多的匹配信息，利用該模型，無須進(jìn)行人為調(diào)整即可達(dá)到條狀碎片的完美拼接，這表明本文設(shè)計的算法是切實(shí)可行的.

圖5 復(fù)原后的英文圖像

【參考文獻(xiàn)】

[1]樊少榮，周明全，姬利艷.考古文物的數(shù)字化過程研究[J].微機(jī)發(fā)展，2004，12：21-23.

[2]李春龍，周明全，成欣.軸對稱破碎文物的虛擬復(fù)原方法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2006，5：620-624.

[3]王輝，吳欽章.基于圖像質(zhì)量評價的自動圖像復(fù)原技術(shù)[J].傳感技術(shù)學(xué)報，2012， 25（7）：930- 935.

[4]方帥，王勇，曹洋等.單幅霧天圖像復(fù)原[J].電子學(xué)報，2010， 38（10）：2279-2284.

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

[6]Mark M.Meershchaert.Mathematical Modeling （Third Edition）.北京：機(jī)械工業(yè)出版社，2010.

[7]劉金根，吳志鵬.一種基于特征區(qū)域分割的圖像拼接算法[J].西安電子科技大學(xué)學(xué)報，2002（6）： 768-771.

[8]羅智中.基于線段掃描的碎紙片邊界檢測算法研究[J].儀器儀表學(xué)報，2011（2）：289-294.

[9]Elsasser B，Hoschek J.Approximation of digitized points by surfaces of revolution [J].Computers & Graphics，1996，20（1）：85-94.

[10]Calio F，Moroni G，Rasella M.A particular class of soline in reconstruction of revolution surfaces from 3D data measured by CMM[J].Robotics and Computer Integrated Manufacturing， 2003， 19（1/2）：219-224.