一种基于形状匹配的碎纸片拼接系统设计

1、    一种基于形状匹配的碎纸片拼接系统设计    李旭茹+韩冬+刘德磊摘要：碎片自动拼接技术主要使用于五大领域：考古研究、刑侦、自动装配、古生物学和壁画保存中，在图象处理与模式识别中是一个非常经典的应用。该文的主要工作是利用边界链码提取碎片的轮廓特征，研究碎片拼接的形状匹配算法，进而完成碎纸片的拼接。最后，利用matlab软件，做出gui界面，实现了碎片的自动拼接。实验结果表明，该算法简单，易于实现，并可以得到更好的结果。关键词：碎片拼接；边界链码；轮廓提取；形状匹配；应用1概述目前，大部分的拼接工作都是手工完成的，虽然国外已经做了一些研究，但是由于技

2、术应用的特殊背景，基本没有可供参考的资料，主要研究在文物的自动修复、考古研究、自动装配与失效分析以及古生物学、医学分析等领域。在计算机视觉领域，轮廓特征包含对象的重要信息，成为一个非常重要的“介质”，在碎片复原的各种算法中，基于轮廓的形状匹配技术一直是研究热点。该文讨论了一种改进的应用于碎纸拼接的形状匹配算法，对一种壁画碎片的形状匹配方法-引进行了改进，并把它应用于碎纸拼接，达到了比较好的效果。2形状匹配算法研究本文的主要工作是研究基于形状匹配的数字图像处理方法，并利用计算机进行图像处理。在阅读大量文献的基础上，完成了基于图像处理的碎片拼接方法的研究。算法的流程图如图1所示：2.1碎片的获取采

3、用了扫描仪获取碎片，将扫描结果以图片的形式保存下来。如图2扫描的破碎发票图片。经过一系列的图像灰度化、二值化、轮廓提取等预处理后，我们可以得到碎片图像的外轮廓，为后面的形状匹配奠定基础。挑选三个碎片的轮廓为例，如图3所示。2.2形状匹配算法研究碎纸片外轮廓提取出来以后，在所有的碎片轮廓中，首先任意选定一个碎片轮廓，称之为固定碎片，并把它放在参考坐标系中，其余的都是旋转碎片。给定两个碎片，想知道轮廓是否匹配以及在哪里匹配，總体思路就是将碎片用差分链码表示出来，进而找待匹配碎片。当碎片进行匹配时，两个曲线会有间隙部分，间隙部分统计出的黑色像素点的个数最少时，有可能匹配；当不匹配的时候，统计出的黑色

4、像素点的个数很多，远远超过我们所设定的阈值范围。具体可描述如下：第一步，在固定碎片上取长度为comp_len的比较像素，在待匹配碎片上也取同样长的长度进行比较匹配。如图4所示.匹配过程归纳为四个步骤：（1）将碎片a和b用差分链码表示出来，差分链码具有旋转不变性的特点。f21在碎片a上面取一定长comp_len的像素，称为目标边界，l1，l1。是一系列数字组成的链码，记为l1=a1，a2，a3an；（3）在待匹配碎片b上面是遍历搜索，同样取一定长comp_len的像素，称为待匹配边界，l2，l2：同样是一系列数字组成的链码，记为，l2=b1，b2，b3bn；（4）将l1，l2：相减求平均值q，如

5、果q=0，则将碎片b记录为一个可能匹配碎片，记录该段链码的中心点位置，作为下一步旋转的待匹配点，这样就会找到多个可能匹配的曲线，接下来用面积准则判断。全部遍历后，如果没有找到匹配段，那么继续寻找下一个碎片。第二步，利用面积匹配准则判断化，即考虑固定碎片和旋转碎片曲线所封闭的像素数目的变化。如下图5所示，要计算出属于封闭部分的黑色像素数目。浅灰：a和b重叠部分黑色：a和b之间的间隙部分假设两个碎片轮廓称为a和b，在像素#pa和#pb之间进行匹配。如果是在两个相对应的曲线之间进行匹配，那么轮廓封闭之间的黑色像素数目一定小于某个设定值，我们称之为max_area，最合适的max_area不是人为设定

6、，而是根据碎片的受损程度来决定。对于每一个旋转碎片的位置，匹配精度会随着max_area值的增大而下降，可能会出现错误匹配。所以，选择合适的max_area值，降低错误匹配的发生率。本文中，我们是这样选择max_area的：max_area=（0.20-3）*comp_len2.3拼接结果分析将该算法应用于碎纸拼接过程中，取得了较好的效果，我们还可以通过控制比较长度、封闭面积等参数来优化算法，使匹配效率进一步提高。在本文中，令比较长度comp_len=80像素，max_area=20像素，以下是对拼接过程的具体分析。为了表示方便，先将这十块碎片进行编号。将碎纸图像的上层碎片从左到右编号为1、2

7、、3、4、5，同理，下层碎片从左到右编号为6、7、8、9、10。假设固定碎片选为1号碎片，其他碎片均为待匹配碎片，然后进行拼接。如表1所示，这是碎片拼接中的匹配顺序。上面的表格显示了碎片的拼接顺序，最后的拼接结果图如下图6所示。图6是一幅拼接好的图形，白色是在拼接的过程中像素的叠加，从实用的角度来看，对原内容的识别没有影响。由图可知，最后一个碎片的拼接相比较其他碎片，存在匹配误差，但是这个误差在预期范围内，不可能所有的碎片拼接后，都能恢复成原来的样子，总有一些客观因素存在。最后，设计一个完整的图形用户界面（gui）的matlab应用程序，从读入碎片开始，完整的显示了碎片拼接的过程。如图7所示。3结论仿真结果表明，形状匹配算法是可