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

李旭茹+韩冬+刘德磊

摘要：碎片自动拼接技术主要使用于五大领域：考古研究、刑侦、自动装配、古生物学和壁画保存中，在图象处理与模式识别中是一个非常经典的应用。该文的主要工作是利用边界链码提取碎片的轮廓特征，研究碎片拼接的形状匹配算法，进而完成碎纸片的拼接。最后，利用matlab软件，做出GUI界面，实现了碎片的自动拼接。实验结果表明，该算法简单，易于实现，并可以得到更好的结果。

关键词：碎片拼接；边界链码；轮廓提取；形状匹配；应用

1概述

目前，大部分的拼接工作都是手工完成的，虽然国外已经做了一些研究，但是由于技术应用的特殊背景，基本没有可供参考的资料，主要研究在文物的自动修复、考古研究、自动装配与失效分析以及古生物学、医学分析等领域。在计算机视觉领域，轮廓特征包含对象的重要信息，成为一个非常重要的“介质”，在碎片复原的各种算法中，基于轮廓的形状匹配技术一直是研究热点。该文讨论了一种改进的应用于碎纸拼接的形状匹配算法，对一种壁画碎片的形状匹配方法-引进行了改进，并把它应用于碎纸拼接，达到了比较好的效果。

2形状匹配算法研究

本文的主要工作是研究基于形状匹配的数字图像处理方法，并利用计算机进行图像处理。在阅读大量文献的基础上，完成了基于图像处理的碎片拼接方法的研究。算法的流程图如图1所示：

2.1碎片的获取

采用了扫描仪获取碎片，将扫描结果以图片的形式保存下来。如图2扫描的破碎发票图片。

经过一系列的图像灰度化、二值化、轮廓提取等预处理后，我们可以得到碎片图像的外轮廓，为后面的形状匹配奠定基础。挑选三个碎片的轮廓为例，如图3所示。

2.2形状匹配算法研究

碎纸片外轮廓提取出来以后，在所有的碎片轮廓中，首先任意选定一个碎片轮廓，称之为固定碎片，并把它放在参考坐标系中，其余的都是旋转碎片。给定两个碎片，想知道轮廓是否匹配以及在哪里匹配，總体思路就是将碎片用差分链码表示出来，进而找待匹配碎片。当碎片进行匹配时，两个曲线会有间隙部分，间隙部分统计出的黑色像素点的个数最少时，有可能匹配；当不匹配的时候，统计出的黑色像素点的个数很多，远远超过我们所设定的阈值范围。具体可描述如下：

第一步，在固定碎片上取长度为COMP_LEN的比较像素，在待匹配碎片上也取同样长的长度进行比较匹配。如图4所示.

匹配过程归纳为四个步骤：

（1）将碎片A和B用差分链码表示出来，差分链码具有旋转不变性的特点。

f21在碎片A上面取一定长COMP_LEN的像素，称为目标边界，L₁，L₁。是一系列数字组成的链码，记为L₁={a1，a2，a3…an}；

（3）在待匹配碎片B上面是遍历搜索，同样取一定长COMP_LEN的像素，称为待匹配边界，L₂，L₂：同样是一系列数字组成的链码，记为，L₂={b1，b2，b3…bn}；

（4）将L₁，L₂：相减求平均值Q，如果Q=0，则将碎片B记录为一个可能匹配碎片，记录该段链码的中心点位置，作为下一步旋转的待匹配点，这样就会找到多个可能匹配的曲线，接下来用面积准则判断。全部遍历后，如果没有找到匹配段，那么继续寻找下一个碎片。

第二步，利用面积匹配准则判断化，即考虑固定碎片和旋转碎片曲线所封闭的像素数目的变化。如下图5所示，要计算出属于封闭部分的黑色像素数目。

浅灰：A和B重叠部分黑色：A和B之间的间隙部分

假设两个碎片轮廓称为A和B，在像素#P_A和#P_B之间进行匹配。如果是在两个相对应的曲线之间进行匹配，那么轮廓封闭之间的黑色像素数目一定小于某个设定值，我们称之为MAX_AREA，最合适的MAX_AREA不是人为设定，而是根据碎片的受损程度来决定。对于每一个旋转碎片的位置，匹配精度会随着MAX_AREA值的增大而下降，可能会出现错误匹配。所以，选择合适的MAX_AREA值，降低错误匹配的发生率。本文中，我们是这样选择MAX_AREA的：

MAX_AREA=（0.2～0-3）*COMP_LEN

2.3拼接结果分析

将该算法应用于碎纸拼接过程中，取得了较好的效果，我们还可以通过控制比较长度、封闭面积等参数来优化算法，使匹配效率进一步提高。在本文中，令比较长度COMP_LEN=80像素，MAX_AREA=20像素，以下是对拼接过程的具体分析。

为了表示方便，先将这十块碎片进行编号。将碎纸图像的上层碎片从左到右编号为1、2、3、4、5，同理，下层碎片从左到右编号为6、7、8、9、10。假设固定碎片选为1号碎片，其他碎片均为待匹配碎片，然后进行拼接。如表1所示，这是碎片拼接中的匹配顺序。

上面的表格显示了碎片的拼接顺序，最后的拼接结果图如下图6所示。

图6是一幅拼接好的图形，白色是在拼接的过程中像素的叠加，从实用的角度来看，对原内容的识别没有影响。由图可知，最后一个碎片的拼接相比较其他碎片，存在匹配误差，但是这个误差在预期范围内，不可能所有的碎片拼接后，都能恢复成原来的样子，总有一些客观因素存在。

最后，设计一个完整的图形用户界面（GUI）的MATLAB应用程序，从读入碎片开始，完整的显示了碎片拼接的过程。如图7所示。

3结论

仿真结果表明，形状匹配算法是可行的、快速的。本次实验所采用的碎纸片数量不多。但最后也拼接成功，这表明复原碎片拼接技术的可行性，接下来的方向就是增加碎片的数量，看算法是否还可行，并做出进一步的调整，加快拼接速度，使适用范围更广。