沈鴻平,章毅鵬,王義康
(中國計(jì)量學(xué)院 理學(xué)院,浙江 杭州 310018)
破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域均有著重要的應(yīng)用[1]。傳統(tǒng)的拼接復(fù)原工作需由人工完成,雖準(zhǔn)確率較高,但效率較低。尤其是當(dāng)碎片數(shù)量巨大時(shí),人工拼接難以在短時(shí)間內(nèi)完成。隨著計(jì)算機(jī)技術(shù)的發(fā)展,人們試圖開發(fā)碎片自動(dòng)拼接技術(shù),以提高拼接復(fù)原效率。目前二維碎片拼接研究主要集中在兩方面:一是基于不規(guī)則碎片的輪廓拼接研究[2-6],不規(guī)則碎片研究在拼接過程中可利用邊界輪廓信息進(jìn)行形狀匹配;另一方面是基于碎片文本信息及其特征的拼接研究[7-9],由于漢字復(fù)雜多樣,語義識別較為復(fù)雜,在解決拼接問題的同時(shí)會(huì)帶來諸多新問題。以上兩者比較而言,由于輪廓邊界幾何特征信息量較少,對其數(shù)學(xué)模型的研究便顯得更為困難。
本文在基于碎片邊界輪廓無明顯幾何匹配特征信息的情況下,通過對碎片內(nèi)文字行平面分布特征以及行特征信息獲取方法的研究,建立基于0-1 規(guī)劃的中文規(guī)則碎片拼接模型??紤]到模型本身的復(fù)雜性和求精確解的困難性,提出利用貪婪算法進(jìn)行求解,并對某一碎片文件進(jìn)行了拼接模擬仿真,結(jié)果表明該方法效果良好。
樣本數(shù)據(jù)為某一中文文件的規(guī)則碎片,來自同一頁印刷文字文件,一共209 張矩形碎片,每張矩形碎片大小相同,長與高分別是6.35 cm 和2.96 cm,碎片內(nèi)文字均為簡體中文,且行間距、字間距均相同。圖1 為部分碎片圖樣。
圖1 部分碎片圖樣(6 張)
為了從數(shù)字處理角度來進(jìn)行匹配分析,需應(yīng)用計(jì)算機(jī)圖像處理技術(shù)對碎片進(jìn)行處理、修飾或轉(zhuǎn)換,從而產(chǎn)生一張數(shù)字化的碎片。本文采用圖像灰度化方法[10],將樣本中的209 張碎片進(jìn)行灰度化,每張碎片均產(chǎn)生一個(gè)180×72 的矩陣,矩陣的元素為像素點(diǎn)的灰度值,介于0 ~255 之間,其中0 表示黑色,255 表示白色,越接近0 則黑色越深,越接近255 則白色越明顯。
碎片上的主要信息由黑白兩種顏色構(gòu)成,為將整個(gè)碎片呈現(xiàn)出明顯的黑白視覺效果,盡量排除其他色彩噪聲的干擾,利用圖像二值化的方法[10],將每張碎片的灰度矩陣二值化,通常采用設(shè)置閾值的方法,這里設(shè)置閾值為128,即將灰度值<128 的變成0,否則灰度值為255。將碎片進(jìn)行灰度化和二值化處理,每張碎片均對應(yīng)于一個(gè)由0 和255 元素構(gòu)成的數(shù)字矩陣。若對二值化的數(shù)字矩陣進(jìn)行圖像逆變換處理則可還原成原有碎片圖樣。碎片數(shù)字化處理及反演的全過程如圖2 所示。
圖2 碎片數(shù)字化處理及反演過程示意圖
對于拼接復(fù)原該中文文件碎片,考慮到碎片拼接的唯一性,設(shè)定若兩片碎片可拼接則取值為1,否則取為0,從而可設(shè)0-1 變量為
對于每個(gè)碎片的左端而言,至多只有一個(gè)碎片與其進(jìn)行右鄰拼接;而對于每個(gè)碎片的上端而言,至多只有一個(gè)碎片與其下鄰拼接。因此可得到拼接約束為
假設(shè)209 張碎片樣本構(gòu)成的文本為a 行b 列,即每一行的碎片為b 張,每一列為a 張。則每一行有(b-1)對碎片匹配,同樣每一列有(a-1)對碎片匹配,從而可得到總匹配拼接約束為
由式(2)~式(4)得到碎片拼接的0-1 規(guī)劃模型為
假設(shè)有N 張碎片,根據(jù)自由拼接方式,則有N!種拼接情形,對于每一種情況計(jì)算每張碎片和其近鄰碎片的歐氏距離,從而得到總體匹配度,再對其進(jìn)行比較,則計(jì)算量過大,難以實(shí)現(xiàn)。因而對于式(5)所描述的0-1 規(guī)劃拼接模型,當(dāng)碎片數(shù)量較多時(shí),求其精確解較為困難。故本文提出了一種貪婪算法,能夠較快地實(shí)現(xiàn)碎片拼接復(fù)原。
貪婪算法[11],其基本思想是對所有碎片先按行拼接,待每行均拼接完成后,再按列拼接復(fù)原成完整的圖片文件。對于行拼接過程,則按行向歐氏距離總和最小進(jìn)行匹配,考慮左右兩張碎片的拼接。仍采用模型(5)中兩兩歐氏距離ρ 作為指標(biāo),以任意一張碎片開始,先按向右方向進(jìn)行拼接,若左右碎片的歐氏距離ρlr最小時(shí)恰好是相鄰關(guān)系,則將其拼接在一起,否則將進(jìn)行人工干預(yù),即將歐氏距離次小的碎片作為右端碎片,再與左端碎片進(jìn)行拼接并進(jìn)行文本內(nèi)容判別,直到找到最符合該端碎片的右端碎片。如此循環(huán),直到將所有碎片按行進(jìn)行拼接完成。得到行碎片后再進(jìn)行列拼接,按縱向歐氏距離總和最小進(jìn)行匹配,從而最終拼接出完整的圖片文件。
為減少計(jì)算量,本文首先采用聚類分析的方法對碎片進(jìn)行分類。將碎片的每行文字看作一條粗線,稱之為粗基線。分類的標(biāo)準(zhǔn)是將粗基線平面位置一致的碎片歸于一類,粗基線的寬度為文字在碎片中的高度,碎片粗基線特征提取示意圖如圖3 所示。
圖3 某張碎片與其粗基線對照圖
對于每張碎片,可提取碎片特征向量δ=(h1,h2,…,hk,H)來描述其每行文字到該碎片頂端的距離,直接反映了其文字分布特征。其中hk表示第k 行文字底部到該碎片頂端的距離,H 表示碎片高度,由H 和hk可得到碎片下端空白的高度。
在聚類分析的基礎(chǔ)上,通過人工判別,對誤分類的碎片適當(dāng)?shù)匾肴斯て唇?,從而完成整張紙片的拼接?fù)原。基于貪婪算法的碎片拼接復(fù)原流程如圖4所示。
圖4 基于貪婪算法的碎片拼接復(fù)原流程圖
將樣本數(shù)據(jù)中的每張碎片進(jìn)行隨機(jī)編號,編號為0,1,2,…,208。首先對碎片進(jìn)行聚類,在209 張碎片中找到任意一張碎片δ=(h1,h2,…,hk,H),以該碎片向量作為聚類中心,以碎片邊界向量間歐氏距離為匹配度量,并設(shè)定樣本距離的適當(dāng)閾值,再進(jìn)行聚類,則將可能位于同一行的碎片聚為一類。其次,在余下的碎片中再任選一張碎片δ″,同理用上述方法找出與其同類的碎片。如此循環(huán),直到將碎片聚成若干類。
試驗(yàn)結(jié)果表明,對本文的樣本文件歸類,粗基線位置上下波動(dòng)范圍閾值可設(shè)為±2,即在粗基線位置附近2 個(gè)像素點(diǎn)的位置偏差均視為同一類。經(jīng)過聚類后得到的分類結(jié)果如表1 所示。
表1 基于聚類分析的碎片分類結(jié)果
從表1 中可看出,特征明顯聚在一起的有11 類,如第1 類中共有19 張碎片,其編號分別為:0,7,32,…,208;而對于某些類中僅有較少碎片的視作未歸類碎片,即表1 中最后一列編號為60,102,114,…,185的碎片,這些碎片數(shù)量較少,將可能通過人工干預(yù)的方式進(jìn)行分類到前面的11 類中。歸類結(jié)果中有9 類各分到19 張碎片,而第7 類、第8 類不到19 張,第12 列為未被歸入任何類的碎片,從而可推測拼接過程每行可能有19 個(gè)碎片。
利用上述貪婪算法進(jìn)行計(jì)算,結(jié)果表明,上述9 類中,每一類碎片恰好組成了原文件中某一行碎片塊。對于第7 類,首先按照上述算法將已歸類好的碎片進(jìn)行拼接,然后對缺少的碎片利用人工干預(yù)的方法在未歸類中尋找相匹配的碎片即可。對于第8 類,將未歸類中剩余的碎片也歸為第8 類,并采用上述算法對第8 類進(jìn)行拼接。從而得到該文件是由11×19 張小矩形碎片組成,并已將11 行碎片拼接完成。再將11 張碎片塊按列進(jìn)行人工拼接,得到一張完整的原文件。
試驗(yàn)結(jié)果表明,對于209 張碎片進(jìn)行完全拼接復(fù)原,人工干預(yù)的次數(shù)為30 次,算法的行拼接計(jì)算量是21 945 次,列拼接計(jì)算量是55 次,總計(jì)算量為22 000次,相比自由拼接方式下的N!種組合方法的計(jì)算量有大幅減少。圖5 為某相鄰兩行的拼接結(jié)果。
圖5 某兩行的拼接結(jié)果
本文通過碎片文件進(jìn)行分析,并考慮了其他色彩噪音的干擾,建立了0-1 規(guī)劃拼接復(fù)原的數(shù)學(xué)模型,并提出利用貪婪算法進(jìn)行模型求解,同時(shí)利用由209張碎片組成的文件數(shù)據(jù)進(jìn)行模擬仿真。仿真結(jié)果表明,模型對碎片拼接問題進(jìn)行了準(zhǔn)確的數(shù)學(xué)描述,隨著碎片數(shù)量的增加,模型計(jì)算量快速增大,而提出的貪婪算法能夠較好地解決計(jì)算量問題,并能實(shí)現(xiàn)碎片快速分類和拼接。本文的結(jié)果是基于規(guī)則邊界且大小相同的矩形碎片,實(shí)際中受破碎方式、碎片形狀、色彩污染等各種因素的影響,碎片拼接復(fù)原異常復(fù)雜,深入考慮碎片拼接機(jī)制,建立更精確的模型,將可能取得更好的結(jié)果。
[1] 楊洛斌.形狀匹配技術(shù)在文物復(fù)原中的研究與應(yīng)用[D].西安:西北大學(xué),2002.
[2] 賈海燕,朱良家,周宗潭,等.一種碎片自動(dòng)拼接中的形狀匹配方法[J].計(jì)算機(jī)仿真,2006,23(11):180-183.
[3] 羅智中.基于線段掃描的碎片邊界檢測算法研究[J].儀器儀表學(xué)報(bào),2011,23(2):289-294.
[4] 謝萍,馬小勇,張憲民,等.一種快速的復(fù)雜多邊形匹配算法[J].計(jì)算機(jī)工程,2003,29(16):177-181.
[5] 朱延娟,周來水.二維非規(guī)則碎片的匹配算法[J].計(jì)算機(jī)工程,2007,33(24):7-9.
[6] 張欣卜,彥龍,朱良家,等.物證復(fù)原系統(tǒng)中的碎紙輪廓提取技術(shù)研究[J].計(jì)算機(jī)仿真,2006,23(11):184-187.
[7] EFTHYMIA T,IOANNIS P.Automatic color based reassembly of fragmented images and paintings[J].IEEE Transactions on Image Processing,2009,19(3):680-690.
[8] NASIR M,ANANDABRATA P.Automated reassembly of file fragmented images using greedy algorithms[J].IEEE Transactions on Image Processing,2006,15(2):385-393.
[9] 羅智中.基于文字特征的文檔碎紙片半自動(dòng)拼接[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(5):207-210.
[10]阮秋琦.數(shù)字圖像處理學(xué)[M].北京:電子工業(yè)出版社,2001.
[11]楊克昌.計(jì)算機(jī)常用算法與程序設(shè)計(jì)案例教程[M].北京:清華大學(xué)出版社,2011.