二维碎片拼接的局部匹配

房然然，黄发忠，辛化梅

（山东师范大学物理与电子科学学院，山东济南250014）

二维碎片拼接的局部匹配

房然然，黄发忠，辛化梅

（山东师范大学物理与电子科学学院，山东济南250014）

基于轮廓的二维非规则碎片拼接问题，通常分为局部匹配和全局匹配两个步骤，这里提出一种新的局部匹配的方法，首先对轮廓进行多边形逼近得到多边形顶点序列，然后获取多边形顶点的转角序列特征并计算相邻顶点间长度，对该转角序列使用改进过的“坦克算法”，应用一定筛选规则，寻找到多边形顶点的若干候选匹配信息。改进的算法可降低时间复杂度，提高匹配效率。

碎片拼接；多边形逼近；旋转角度；局部匹配

0 引言

在考古文物复原（如破碎壁画、瓷片等）、司法物证鉴定、破碎人民币拼合等领域普遍存在碎片拼接问题，当碎片数量较大时，人工比对实现拼合是一项重复而繁琐的任务，耗费大量时间和精力，还可能对物件造成二次损坏。计算机技术的发展使得用计算机实现碎片复原成为可能。二维碎片自动拼接的相关研究，具有较强的理论和实际意义。

按照碎片特征，二维非规则碎片拼接可分为基于轮廓和基于内容（色彩、纹理等）的碎片拼接，还可以分为有基准图像和无基准图像的拼接。基于轮廓的二维碎片拼接研究较多，可分两个步骤：

（1）根据碎片的轮廓信息进行两两匹配，找到任意两个碎片之间可能的匹配部分，即局部匹配；

（2）全局匹配重建。

本文提出的方法主要针对基于轮廓的二维碎片拼接的局部匹配部分。

目前，国内外针对二维碎片局部轮廓匹配的研究较多。Wolfson H提出一种基于曲线累积转角串的轮廓曲线匹配方法[1]。Leita o H C等人给出一种多尺度的二维碎片拼接方法[2]，通过对轮廓采样点的曲率串进行多尺度分析，利用动态规划技术对匹配对进行精化处理。Kimia B等学者提出了一种先粗尺度后精尺度的动态规划局部匹配[3]，可以提高匹配效率，但对两对应曲线的采样分布有较强的依赖性。Amigoni等人提出一种新的基于局部曲率和色彩的局部匹配方法[4]，有较好的容错性。朱良家等提出一种对弧长-累积转角序列差进行直方图分析的局部匹配方法[5]。国内也有较多学者进行了相关研究。朱延娟等提出了一种基于Hausdorff距离的多尺度轮廓匹配算法[6]。周丰等人提出了一种基于角序列并与多尺度空间相结合的轮廓匹配算法[7]。饶芮菱等人也提出了一种基于链码的轮廓匹配算法[8]。

本文的方法是先对碎片轮廓进行多边形逼近，并计算多边形的转角，再用基于文献[4]方法的改进算法，寻找碎片多边形的候选匹配对。

1 预处理

图像碎片预处理步骤如下：

（1）采用扫描仪获取碎片灰度图像，如图1所示。

（2）对得到的灰度图像进行直方图分析，把灰度图像转换为二值图，其中1表示碎片，0表示背景，然后提取二值图像的边缘，碎片的边缘像素就是与背景像素相邻但属于碎片的元素，顺时针逐一顺次寻找八连通的碎片边缘像素，得到碎片边缘，如图2所示，碎片边缘表示为顺时针的坐标序列。

图1 原始碎片

图2 边缘及近似多边形顶点

2 轮廓曲线的表示

在提取到边缘轮廓后，对轮廓曲线进行多边形逼近，用得到的多边形顶点序列表示轮廓曲线，并且计算多边形的转角，用于后面的匹配。多边形逼近可分为基于参数的[9]和非参数的[10]，本文采用阈值法迭代获得多边形顶点。每个碎片的多边形顶点个数大约为8～20个。

如图2中，轮廓上的星号表示碎片边缘的近似多边形顶点。假设得到多边形的顶点坐标序列v1v2…vn，每个顶点用横坐标和纵坐标表示。从第一个顶点开始计算旋转角度。顶点vi(1

图3 计算多边形旋转角

如果两个多边形匹配，由于凸角跟凹角匹配，则匹配顶点处的旋转角度是大小相同、正负相反的。

3 局部匹配

为了使用“坦克算法”比较两个碎片轮廓的旋转角度序列从而找到匹配部分，本文对“坦克算法”进行了改进：

（1）将两序列视为环形，不需要进行序列的复制，也不再要求移动的序列短于不移动的序列；

（2）两序列中的对应元素采用相加的方式计算误差；

（3）用匹配度量Match_Deg来表示每个匹配段的匹配程度。

首先，由于旋转角度序列都是按顺时针获得的，而两个序列要从相反的方向来比较，所以要将其中一个序列逆序排列；其次，考虑到碎片边缘是闭合的，所以要将两个旋转角度序列看做环状，再进行比较。由于匹配顶点的旋转角度是大小相同、正负相反的，所以在“坦克算法”中，比较两个序列的对应元素时，计算两者和的绝对值|e|，如果|e|=0，则认为这两个元素对应的多边形顶角是匹配的。由于扫描噪声等的影响，旋转角度序列匹配部分不是完全一样，有一定误差，所以需要给定一个阈值ε（ε>0）来容忍|e|，即如果两个元素的绝对误差|e|在ε范围内，则认定它们对应的顶角是匹配的。对得到的匹配段，为便于比较匹配程度，计算其匹配度量：

其中：L1，L2分别为两匹配段边长和；Dif为L1，L2之差；Commonside为一个匹配段的匹配对应边的个数；Commonvertice为匹配对应转角个数；c1,c2为两常数。Match_Deg≥0，两段边长差越小，累积角度误差越小，匹配长度越长，则Match_Deg越接近于0，其匹配程度越高。

假设待比较的两序列为shape1，shape2，其中shape2序列是逆序排列的。shape2从对应shape1第一个元素的位置开始，每次移动一个位置，一直移动到shape1的最后一个元素。当shape2移动到shape1的某个位置时，shape1和shape2的对应元素将进行从左到右的比较，若发现某两个对应元素匹配，则将这两个元素视为匹配段的起始点，从这两点开始一段匹配，并计算累积总误差：

继续向右比较，直到某两个元素的|e|超出ε，或ErrorTank超出阈值ErrorTankCapacity，这个匹配段就结束，计算该段的匹配度量Match_Deg。把该匹配的起始点、终止点及匹配度量信息记录下来，最后会得到若干个匹配信息，选取匹配程度最高的即Match_Deg最小的匹配段，作为shape2此次移动的最佳匹配，存入结果中。当shape1每个位置都被shape2移动到后，再从每次移动的匹配结果中选择匹配程度最高的一个匹配，作为这两个碎片最可能的匹配，称为候选匹配。

假设shape1，shape2长度分别为M，N，文献[4]中坦克算法要进行M次位移，每次位移要比较2N次，会导致重复比较，从而产生重复的匹配结果，而改进后的算法，shape2共移动M个位置，每次位移进行N次比较，提高了效率。由于本文的算法过程是基于近似多边形的，一般多边形顶点数约为8～20个，而“坦克算法”是基于像素的，故本文算法的时间复杂度远远小于文献[4]中曲率串的“坦克算法”。

本文的实验最终返回了如图4（a）中的一个候选匹配，Match_Deg=0.095 25，图4（b）显示了这两片碎片的真实匹配，结果表明，实验返回的候选匹配是真实匹配。

图4 碎片局部匹配结果

4 结语

本文提出的方法是基于多边形逼近的，提取出多边形的转角和边长，并对转角序列和边长进行比较，由于多边形顶点数远小于实际像素数，所以基于多边形的方法相对于基于像素的方法可减少计算量，提高效率。下一步可将这种方法应用于多片碎片的局部匹配和全局匹配，从而实现拼接。

[1]WOLFSON H.On curve matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1990，12（5）：483⁃489.

[2]DA GAMA LEITAO H C，STOLFI J.A multiscale method for the reassembly of two⁃dimensional fragmented objects[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（9）：1239⁃1251.

[3]KONG Wei⁃xin，KIMIA B B.On solving 2D and 3D puzzles using curve matching[C]//Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recogni⁃tion.[S.l.]：IEEE，2001，2：583⁃590.

[4]AMIGONI F，GAZZANI S，PODICO S.A method for reassem⁃bling fragments in image reconstruction[C]//Proceedings of 2003 International Conference on Image Processing.[S.l.]：IEEE，2003，2：581⁃584.

[5]ZHU Liang⁃jia，ZHOU Zong⁃tan，HU De⁃wen.Globally consistent reconstruction of ripped⁃up documents[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（1）：1⁃13.

[6]朱延娟，周来水，张丽艳，等.基于Hausdorff距离的多尺度轮廓匹配算法[J].中国机械工程，2004，15（17）：1553⁃1561.

[7]周丰，黄晓鸣.基于角序列的二维碎片轮廓匹配算法[J].科学技术与工程，2007，7（15）：3757⁃3760.

[8]饶芮菱，金雪峰，鲁怀伟.基于链码的二维碎片轮廓匹配算法[J].计算技术与自动化，2007，26（2）：34⁃37.

[9]JUSTINO E，OLIVEIRA L S，FREITAS C.Reconstructing shredded documents through feature matching[J].Forensic Science International，2006，160（2）：140⁃147.

[10]ROSIN P L，WEST G A W.Non⁃parametric segmentation of curves into various representations[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1995，17（2）：1140⁃1153.

Local matching for 2⁃D fragments reassembling

FANG Ran⁃ran，HUANG Fa⁃zhong，XIN Hua⁃mei
（College of Physics and Electronics，Shandong Normal University，Jinan 250014，China）

The 2⁃D irregular fragments reassembling issue based on contour is usually divided into two steps：local matching and global matching.A new local matching method based on improved Tank algorithm is proposed.Firstly the sequence of polygon vertices is obtained by polygonal approximation to the contour，then the corner sequence signature of the polygon is acquired，the distance between two adjacent vertices is calculated.The improved Tank algorithm is applied in the corner sequence to find some candidate matching information of the polygon vertices by some screening rules.The improved algorithm can reduce time complexity and improve matching efficiency.

fragment reassembling；polygon approximation；rotation angle；local matching

TN911.73⁃34；TP391

A

1004⁃373X（2015）09⁃0054⁃03

房然然（1990—），女，山东济宁人，硕士研究生。主要研究方向为信号与信息处理。

2014⁃11⁃19

教育部留学回国人员科研启动基金项目（教外司留2009⁃36）；山东省优秀中青年科学家科研奖励基金（BS2013DX035）；国家自然科学基金（61401259）

黄发忠，男，山东济南人，副教授。主要研究方向为信号与信息处理。

辛化梅，女，山东青岛人，博士，副教授。主要研究方向为信号与信息处理。