基于聚类分析与欧氏距离模型的碎纸片拼接复原

谢亚旗 缪杨 梁伟 王韵 安秋平

（1.深圳市建设工程造价管理站 广东省深圳市 518031 2.海口经济学院 海南省海口市 571127）

（3.贵州数联铭品科技有限公司 贵州省贵阳市 550005 4.中交一航局生态工程有限公司 广东省深圳市 518000）

1 引言

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域也存在类似的问题，大量的纸质物证复原工作目前基本上都是以手工方式完成的。一旦碎纸的数量增大到几百甚至上千块的时候，如果仍然依靠手工完成，不但耗费大量的人力、物力，而且还可能对物证造成一定的损坏。目前，在国际上，德国等发达国家对破碎文件的自动修复技术已经进行了相当长时间的研究。但是由于技术封锁的原因，我们所能够搜集的资料非常有限。而在国内，还没有类似的研究成果问世。因此，结合碎纸自动拼接在司法物证复原、历史文献修复以及军事情报获取等领域的应用这一背景，把计算机视觉和模式识别应用于碎片复原，开展对碎纸自动拼接技术的研究具有重要的现实意义。

本文研究如下问题：对于碎纸机既纵切又横切的情形，每页纸被切为11×19 个碎片，设计碎纸片拼接复原模型和算法，并针对给出的中、英文各一页文件的416 块碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。

2 问题的思路分析

2.1 问题的分析

对于此问题图片数量较多，图片匹配除了横向的匹配拼接还有纵向的匹配拼接。采用利用图片边缘灰度矩阵进行匹配时会产生庞大的数据人工难以处理。所以我们重新建立了一个欧氏距离模型。首先，运用图片边缘灰度矩阵进行匹配的手段，使用Matlab 提取相关的图片信息；然后，根据匹配的横向和纵向，利用聚类分析的系统聚类法模型进行了数据分类，得到了初步的数据分析的结果，通过spss 软件对各组数据采用标准值代替，得到了标准值散点图，使用人工干预横向和纵向匹配得出了比较优化的数据分析结果；最后，运用欧氏距离进行相关性分析与匹配数学模型验证了spss 的最优化的数据分析结果，解决碎纸片拼接复原。

3 模型的建立与求解

对于此问题图片数量较多，图片匹配除了横向的匹配拼接还有纵向的匹配拼接。采用利用图片边缘灰度矩阵进行匹配时会产生庞大的数据人工难以处理。因此我们引入了系统聚类法对数据进行分类，使问题简化。

3.1 运用系统聚类法模型对数据进行分类

系统聚类法基本思想：首先，把每个变量（每个样品）看作一类，并规定定量间的相似性测度换算成的距离（其中cij表示变量i 和变量j 之间的相关系数，或样品i 和样品j 之间的相似系数）（或样品之间的距离）看作类与类之间的距离，然后将距离最近的两类合成新的一类，每次减少一类，重新进行最近类的合并，直至所有的变量（或样品）合并成一类。

图1：z，y 矩阵各列标准值散点图

图2：人工干预界面

图3：ab 之间的欧氏距离

图4：中文碎片复原图

图5：英文碎片复原图

系统聚类法方法：类与类之间的距离的定义如同样品间的距离定义一样，有各种各样不同的方法。其中，系统聚类方法是用的最多的一种方法。

设dij表示样品i 与样品j 之间的距离，G1,G2,...表示类，Dij表示Gi与Gj的距离。

最短距离法：定义类Gi与Gj之间的距离为两类最近样品（或指标）的距离，即

设Gp与Gq合并成一个新类，记为Gr，则任一类Gk与Gr的距离是

运用Matlab 提取出来的各组数据太多不能直接使用系统聚类法进行分类。所以我们先使用spss 软件对各组数据采用标准值代替，从而使用系统聚类法来进行分类处理。

得出的标准值散点图如图1所示。

由于系统聚类法进行的是模糊分类，造成了分类的不准确性，而且运用欧氏距离匹配时方案众多，为确保最后拼接的准确性需采用人工干预的方式对spss 处理得出的标准值数据，进行人为干预和处理。干预时间节点为，数据分类后进行匹配时。干预方式如图2。

3.2 运用欧氏距离模型进行相关性分析与匹配

对众多数据采用系统聚类法进行分类得到11组不同特征矩阵。再接着使用欧式距离模型对11 组矩阵进行横向匹配拼接，形成新的11 组矩阵后再进行纵向拼接。

如图3，欧式距离（ Euclidean distance）也称欧几里得距离，它是一个通常采用的距离定义，源自欧氏空间中两点间的距离公式。它是在m 维空间中两个点之间的真实距离，欧氏距离是最易于理解的一种距离计算方法。

（1）二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：

（2）三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：

（3）两个n 维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离：

也可以用表示成向量运算的形式：

但是欧氏距离也有其局限性：即数据各维分量的分布不一样。所以我们引用标准化欧氏距离。

标准欧氏距离的思路：既然数据各维分量的分布不一样，先将各个分量都“标准化”到均值、方差相等。假设样本集X的均值(mean)为m，标准差(standard deviation)为s，而且标准化变量的数学期望为0，方差为1。因此样本集的标准化过程(standardization)那么用X 的“标准化变量”模型表示为：

标准化后的值= （标准化前的值-分量的均值） /分量的标准差.

经过简单的推导就可以得到两个n 维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的标准化欧氏距离的公式：

如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离。

将各组经过人工干预后的数据带入加权欧氏距离模型即得到各图片之间的匹配顺序。复原416 块碎纸片得到完整的图像如图4 和图5所示。

4 结语

本模型针对图片数量庞大，图片匹配除了横向的匹配拼接还有纵向的匹配拼接。利用图片边缘灰度值矩阵进行匹配时会产生庞大的数据人工难以处理。因而我们针对问题在用Matlab 提取的图片信息后先运用聚类分析的系统聚类法模型进行数据分类，用人工干预对数据先左右匹配再进行上下匹配。继而再对人工干预后的数据运用欧氏距离分析方法找出各图片的最佳匹配对象，从而得到碎纸片复原顺序，得到完整的碎纸片复原图，为司法物证复原、历史文献修复以及军事情报获取等领域提供参考。