基于邊界序列數(shù)據(jù)匹配的一種拼合算法*

孔靈柱 劉玉峰

(1:吉林建筑大學(xué)基礎(chǔ)科學(xué)部,長春 130118; 2:內(nèi)蒙古伊圖里河森林公安局,呼倫貝爾 022150)

0 引言

在很多領(lǐng)域碎片復(fù)原問題具有較大實用價值,如在考古、刑偵等方面.該問題可以分為多類:按特征可分為基于色彩、紋理、材質(zhì)、輪廓等進行匹配復(fù)原;按空間可分為二維和三維的復(fù)原[1].現(xiàn)有研究多集中于非規(guī)則的碎片,并基于碎片輪廓的幾何特征進行拼接[2-3];Da Gama Leitao H.C.研究了二維碎片復(fù)原中不匹配對的剔除條件,但并未提出拼合算法[4].針對規(guī)則碎紙片(碎紙機切割而成)的拼接復(fù)原問題,基于邊緣幾何特征的思路并不可行.考慮到碎紙片記載了文字,若對表示其邊界文字信息的序列數(shù)據(jù)進行提取,設(shè)計算法進行匹配,可以實現(xiàn)拼接復(fù)原目的.根據(jù)上述思路,本文設(shè)計了相應(yīng)算法,并利用2013年高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題提供的碎紙圖片(下載網(wǎng)址:http://www.mcm.edu.cn/problem/2013/cumcm 2013 problems.rar),對算法和模型進行了驗證.

1 算法設(shè)計

1.1 圖片轉(zhuǎn)化二值化圖像矩陣

利用Matlab軟件編制程序[5-6],把碎紙圖片循環(huán)導(dǎo)入并二值化為圖像矩陣A(k)=(aij)m×n(k),其中:k為碎紙圖片編號;m×n為矩陣規(guī)格;aij取值為0或1,0代表像素為黑色(有字部分),1代表像素為白色(無字部分).

1.2 邊界序列數(shù)據(jù)信息提取

由于紙片邊緣部分為空白,所以可以對矩陣A(k)邊界數(shù)行(列)的序列數(shù)據(jù)進行分析和計算,尋找碎紙塊中處于原紙張邊緣的部分,以此作為拼接的起點.

1.3 拼接匹配原則

原紙片切割為若干碎片時,由于字跡筆畫的連續(xù)性,所以能夠拼接的碎片具有邊界行(列)對應(yīng)元素差距較小的特征.據(jù)此,可以寫出類似式(1)的公式,計算哪些碎紙片可以拼接到一起.

(1)

式(1)的含義在于:以第k張碎片作為起點,向右拼接,即計算矩陣A(k)最右側(cè)一列(ain)(k)與所有矩陣A(s)(s≠k)最左側(cè)一列(ail)(s)對應(yīng)行元素差的絕對值之和,并尋找和最小的那塊碎片作為匹配對象.向其他方向拼接類似,其過程如圖1所示.

圖1 碎片拼接過程示意 圖2 重復(fù)字符串示意(下方均為“ing”) 圖3 邊界為空白行、列示意(左側(cè)列)

1.4 人工干預(yù)問題

由于特定漢字筆畫或英文字符串可能在碎片中重復(fù)出現(xiàn),以及多個碎片邊界為空白行(列),所以在匹配過程中會出現(xiàn)重復(fù)匹配的現(xiàn)象,如圖2，圖3所示;另外,由于字跡的筆畫和字形問題,在匹配過程中也會出現(xiàn)錯誤匹配的情形,例如“二”字左端與“口”字右端,按照算法可能實現(xiàn)最優(yōu)匹配,但事實上是錯誤匹配.由于上述原因,在完成部分碎片拼接工作后,需要人工試讀驗證,若出現(xiàn)錯誤需進行糾錯干預(yù).

2 算例演示

以2013年高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題提供的碎紙圖片為例,利用Matlab軟件編制程序執(zhí)行上述算法,相關(guān)結(jié)果如下.

2.1 條狀碎片

對19條中、英文碎紙片的拼接復(fù)原結(jié)果代碼見表1.經(jīng)人工驗證,準確率為100 %,且匹配過程未施加人工干預(yù).由于版面限制,這里沒有給出復(fù)原后圖片,讀者可根據(jù)文中提供的網(wǎng)址下載相應(yīng)數(shù)據(jù),并按表1所示次序進行拼接.

表1 19條中、英文碎紙片拼接復(fù)原代碼(自左至右為拼接次序)

2.2 塊狀碎片

首先,篩選209塊中、英文碎紙片處于原紙張最左側(cè)的若干塊;其次,以這些塊為起點,向右拼接成若干條;最后,把這些條拼接為原始紙張.限于篇幅問題,這里只列出其中的1條拼接代碼和復(fù)原圖片,人工干預(yù)位置出現(xiàn)在078→067，099→162和131→079,詳見表2和圖4.

表2 1條塊狀碎片拼接復(fù)原代碼(自左至右為拼接次序)

圖4 表2對應(yīng)的文字復(fù)原結(jié)果

3 結(jié)論

本文的算法和程序能夠?qū)崿F(xiàn)規(guī)則碎紙片的拼接復(fù)原工作.在條形碎片(縱切形成)復(fù)原方面,效率很高,未實施人工干預(yù);在塊狀碎片(縱切和橫切綜合而成)復(fù)原方面,人工干預(yù)較多,可以在算法上繼續(xù)深入考慮,增加不匹配的剔除條件,以期實現(xiàn)減少人工干預(yù)次數(shù),提高復(fù)原效率的目的.

參 考 文 獻

[1] 趙彩虹,盧章平,魯金忠.基于匹配對的非規(guī)則碎片拼合算法[J].計算機應(yīng)用,2005,25(3):596-598.

[2] 呂 科,耿國華,周明全.基于哈希方法的空間曲線匹配[J].電子學(xué)報,2003,31(2):294-296.

[3] 呂 科,耿國華,康寶生,周明全.三維輪廓曲線的快速匹配方法[J].工程圖學(xué)學(xué)報,2002,23(4):54-59.

[4] Da Gama Leitao H.C.,Stolfi J.,A Multiscale Method for the Reassembly of Two-dimensional Fragmented Objects[J].Pattern Analysis and Machine Intelligence,2002,24(9):1239-1251.

[5] 高展宏,許文波.基于MATLAB的圖像處理案例教程[M].北京:清華大學(xué)出版社,2011:120-125.

[6] 郝文化,董秀芳.MATLAB圖形圖像處理應(yīng)用教程[M].北京:中國水利水電出版社,2004:58-62.