基于边界序列数据匹配的一种拼合算法*

孔灵柱 刘玉峰

(1:吉林建筑大学基础科学部,长春 130118; 2:内蒙古伊图里河森林公安局,呼伦贝尔 022150)

0 引言

在很多领域碎片复原问题具有较大实用价值,如在考古、刑侦等方面.该问题可以分为多类:按特征可分为基于色彩、纹理、材质、轮廓等进行匹配复原;按空间可分为二维和三维的复原[1].现有研究多集中于非规则的碎片,并基于碎片轮廓的几何特征进行拼接[2-3];Da Gama Leitao H.C.研究了二维碎片复原中不匹配对的剔除条件,但并未提出拼合算法[4].针对规则碎纸片(碎纸机切割而成)的拼接复原问题,基于边缘几何特征的思路并不可行.考虑到碎纸片记载了文字,若对表示其边界文字信息的序列数据进行提取,设计算法进行匹配,可以实现拼接复原目的.根据上述思路,本文设计了相应算法,并利用2013年高教社杯全国大学生数学建模竞赛B题提供的碎纸图片(下载网址:http://www.mcm.edu.cn/problem/2013/cumcm 2013 problems.rar),对算法和模型进行了验证.

1 算法设计

1.1 图片转化二值化图像矩阵

利用Matlab软件编制程序[5-6],把碎纸图片循环导入并二值化为图像矩阵A(k)=(aij)m×n(k),其中:k为碎纸图片编号;m×n为矩阵规格;aij取值为0或1,0代表像素为黑色(有字部分),1代表像素为白色(无字部分).

1.2 边界序列数据信息提取

由于纸片边缘部分为空白,所以可以对矩阵A(k)边界数行(列)的序列数据进行分析和计算,寻找碎纸块中处于原纸张边缘的部分,以此作为拼接的起点.

1.3 拼接匹配原则

原纸片切割为若干碎片时,由于字迹笔画的连续性,所以能够拼接的碎片具有边界行(列)对应元素差距较小的特征.据此,可以写出类似式(1)的公式,计算哪些碎纸片可以拼接到一起.

(1)

式(1)的含义在于:以第k张碎片作为起点,向右拼接,即计算矩阵A(k)最右侧一列(ain)(k)与所有矩阵A(s)(s≠k)最左侧一列(ail)(s)对应行元素差的绝对值之和,并寻找和最小的那块碎片作为匹配对象.向其他方向拼接类似,其过程如图1所示.

图1 碎片拼接过程示意 图2 重复字符串示意(下方均为“ing”) 图3 边界为空白行、列示意(左侧列)

1.4 人工干预问题

由于特定汉字笔画或英文字符串可能在碎片中重复出现,以及多个碎片边界为空白行(列),所以在匹配过程中会出现重复匹配的现象,如图2，图3所示;另外,由于字迹的笔画和字形问题,在匹配过程中也会出现错误匹配的情形,例如“二”字左端与“口”字右端,按照算法可能实现最优匹配,但事实上是错误匹配.由于上述原因,在完成部分碎片拼接工作后,需要人工试读验证,若出现错误需进行纠错干预.

2 算例演示

以2013年高教社杯全国大学生数学建模竞赛B题提供的碎纸图片为例,利用Matlab软件编制程序执行上述算法,相关结果如下.

2.1 条状碎片

对19条中、英文碎纸片的拼接复原结果代码见表1.经人工验证,准确率为100 %,且匹配过程未施加人工干预.由于版面限制,这里没有给出复原后图片,读者可根据文中提供的网址下载相应数据,并按表1所示次序进行拼接.

表1 19条中、英文碎纸片拼接复原代码(自左至右为拼接次序)

2.2 块状碎片

首先,筛选209块中、英文碎纸片处于原纸张最左侧的若干块;其次,以这些块为起点,向右拼接成若干条;最后,把这些条拼接为原始纸张.限于篇幅问题,这里只列出其中的1条拼接代码和复原图片,人工干预位置出现在078→067，099→162和131→079,详见表2和图4.

表2 1条块状碎片拼接复原代码(自左至右为拼接次序)

图4 表2对应的文字复原结果

3 结论

本文的算法和程序能够实现规则碎纸片的拼接复原工作.在条形碎片(纵切形成)复原方面,效率很高,未实施人工干预;在块状碎片(纵切和横切综合而成)复原方面,人工干预较多,可以在算法上继续深入考虑,增加不匹配的剔除条件,以期实现减少人工干预次数,提高复原效率的目的.

参 考 文 献

[1] 赵彩虹,卢章平,鲁金忠.基于匹配对的非规则碎片拼合算法[J].计算机应用,2005,25(3):596-598.

[2] 吕 科,耿国华,周明全.基于哈希方法的空间曲线匹配[J].电子学报,2003,31(2):294-296.

[3] 吕 科,耿国华,康宝生,周明全.三维轮廓曲线的快速匹配方法[J].工程图学学报,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].北京:清华大学出版社,2011:120-125.

[6] 郝文化,董秀芳.MATLAB图形图像处理应用教程[M].北京:中国水利水电出版社,2004:58-62.