基于聚类分析和灰度值匹配的碎片文件拼接复原

电子技术与软件工程Electronic Technology&Software Engineering数据库技术Database Technology基于聚类分析与欧氏距离模型的碎纸片拼接复原谢亚旗'缪杨2梁伟彳王韵"安秋平'（1.深圳市建设工程造价管理站广东省深圳市518031 2.海口经济学院海南省海口市571127）（3.贵州数联铭品科技有限公司贵州省贵阳市5500054.中交一航局生态工程有限公司广东省深圳市518000）摘要：本文基于相关性分析与图像匹配算法结合系统聚类法与欧氏距离数学模型研究碎纸片的拼装复原问题。

首先使用Matlab编程提取出图片关键位置的灰度值矩阵，然后利用spss软件进行图片边缘矩阵的相关分析，得到了各图片边缘特征的连接关系，找出与各矩阵最相似的对应矩阵，得到了各图片最佳匹配对象及相关系数表，最后建立相关性分析在匹配聚类分析的系统聚类法与欧氏距离数学模型，通过图片特征进行匹配排序，利用Matlab绘制出了各图片文字拼接结果。

关键词：拼接；聚类分析；灰度值矩阵；欧氏距离模型；人工干预1引言破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域也存在类似的问题，大量的纸质物证复原工作目前基本上都是以手工方式完成的。

一旦碎纸的数量增大到几百甚至上千块的时候，如果仍然依靠手工完成，不但耗费大量的人力、物力，而且还可能对物证造成一定的损坏。

目前，在国际上，德国等发达国家对破碎文件的自动修复技术己经进行了相当长时间的研究。

但是由于技术封锁的原因，我们所能够搜集的资料非常有限。

而在国内，还没有类似的研究成果问世。

因此，结合碎纸自动拼接在司法物证复原、历史文献修复以及军事情报获取等领域的应用这一背景，把计算机视觉和模式识别应用于碎片复原，开展对碎纸自动拼接技术的研究具有重要的现实意义。

本文研究如下问题：对于碎纸机既纵切又横切的情形，每页纸被切为11x19个碎片，设计碎纸片拼接复原模型和算法，并针对给出的中、英文各一页文件的416块碎片数据进行拼接复原。

基于灰度像素理论的碎纸片拼接方法摘要常规的二维碎片拼接技术一直受到科研领域重视，它在司法鉴定、文物修复、图像处理等领域有着广泛的应用。

本文研究的是二维碎片拼接技术中最典型的文档类碎纸片拼接问题。

基于文档纸片色彩明确、方向一致、无重叠等特点，利用灰度理论对问题作出解决。

通过图形扫描得到图像，然后通过二值化，Sobel[]3梯度算进行预处理，并运用皮尔逊相关性度量及方差分析算法进行匹配，以实现对纸片进行还原。

本文通过MATLAB程序模型，以及图片像素灰度理论实现文档碎片的重新拼接。

对于问题1，应用图像处理技术中的灰度理论建立了灰度模型I。

在对得到灰度模型进行Sobel梯度边缘化预处理的方法进行模型改进，建立了边缘灰度模型II。

然后借助于皮尔逊相关系数算法和MATLAB软件，对附件中所提供的碎片进行排列拼接。

对于问题2，采用化归思想，将二维问题渐变为一维问题。

首先归纳碎片特征运用MATLAB软件对碎片进行同行分类，得到11行19列的元素；采用方差分析算法和人工干预对各行中元素进行排列，得到11条横切的图形；采用方差分析算法和人工干预对其进行排列，得以还原。

本文的亮点在于对各行中元素采用方差分析算法进行左侧到右侧匹配后，同时增加了右侧到左侧的匹配检验，大大减少了人工干预的工作。

关键字：灰度理论；皮尔逊相关系数算法；Sobel梯度边缘化；方差分析算法；人工干预一、问题的重述问题一、对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果以图片形式及表格形式表达。

问题二、对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

碎纸片拼接复原的数学方法拼图游戏，一种看似简单却富含深度的游戏，给人们带来了无穷的乐趣。

然而，大家是否想过，这样的游戏其实与数学有着密切的？让我们一起探索碎纸片拼接复原背后的数学方法。

碎纸片拼接复原，其实就是一个计算几何问题。

在数学领域，欧几里得几何和非欧几里得几何是两个基本而又重要的分支。

欧几里得几何主要研究的是在平面上两点之间的最短距离，这是我们日常生活中常见的几何学。

而非欧几里得几何则研究的是曲面上的几何学，这种几何学并不符合我们日常生活中的直觉。

碎纸片拼接复原的问题就是一种非欧几里得几何问题。

在计算机科学中，图论是研究图形和网络的基本理论。

其中，图形遍历算法可以用来解决碎纸片拼接复原问题。

这种算法的基本思想是：从一点出发，尽可能多地遍历整个图形，并在遍历的过程中对图形进行重建。

对于碎纸片拼接复原问题，我们可以将每一张碎纸片看作是图中的一个节点，当两张碎纸片拼接在一起时，它们就形成了一个边。

通过这种方式，我们可以将所有的碎纸片连接起来，形成一个完整的图形。

在计算机科学中，碎纸片拼接复原问题被广泛应用于图像处理、数据恢复等领域。

例如，在数字图像处理中，如果一张图片被切割成若干块，我们可以通过类似的方法来恢复原始的图片。

在数据恢复领域，当一个文件被删除或格式化时，我们也可以通过类似的方法来恢复文件。

碎纸片拼接复原的问题不仅是一个有趣的拼图游戏，更是一个涉及计算几何、图论等多个领域的数学问题。

通过运用这些数学方法，我们可以有效地解决这个问题，从而更好地理解和应用这些数学理论。

在我们的日常生活中，我们经常会遇到一些破碎的物品，例如碎镜子、破碎的瓷器，或是碎纸片等。

这些物品的复原过程都需要一种科学的方法来帮助他们重新拼接起来。

这种科学方法就是碎纸片拼接复原技术。

碎纸片拼接复原技术是一种基于数学模型的方法，它通过比较碎纸片边缘的形状、纹理、颜色等特征，来找到碎纸片之间的相似性和关联性，从而将它们拼接起来。

基于聚类分析和贪心算法的文件碎片拼接复原【摘要】针对文献修复中均匀碎片，以特征位置为基准，采用K-means算法进行聚类分析，对于每一类碎片运用贪心算法不断地取匹配度最高的碎片进行拼接，逐步自动复原整个文献。

经计算机仿真证明：此方法能实现文献的快速拼接，有效地提高物证修复，碎片复原的工作效率。

【关键词】聚类分析；匹配度；贪心算法；均匀碎片；特征0.引言破碎文件的拼接在司法物证复原?、历史文献修复以及军事情报获取等领域都有着重要的应用。

目前在文件碎片复原这一领域，国内研究涉及到的都只是不规则的碎片[1-4]，碎片物理性质、几何形状、颜色、纹理等外在特征都无疑给拼接复原的工作带来了便利[5]。

但是在实际应用中，并不是所有的碎片都存在易于区分的外在特征，虽然计算机有超强的计算能力，但目前很难对碎片边缘上的文字分布走势特征进行智能地识别，均匀规则的碎片复原就会遇到难点。

对于来自同一页印刷文字文件的均匀破碎纸片（以2013年全国大学生数学建模竞赛B题所给的中英文碎片为例[6]），这些碎片形状大小规则，计算机显然无法从利用碎片外在特征进行匹配。

仔细分析这些碎片，可以发现碎片上文字呈现的特征规律，不同碎片上的文字出现的位置特征是不一样的，利用碎片上文字的位置特征，对碎片先按行聚类，对每一类碎片的边缘灰度进行分析比对，运用贪心算法的处理思想每次都将灰度相似度最高的碎片拼接在一起，辅之以少量的人工干预，最后即可逐步自动拼接完成整个文档。

计算机仿真实验证明，上述拼接方法快速有效，在处理均匀碎片的拼接问题上能发挥出巨大的作用。

1.假设及数据的预处理为了能比较好地去阐述拼接模型，现做出以下假设：（1）所有的碎纸片大小一致、形状规则、边缘整齐。

（2）原中英文文献页边距、行距不变，字符间隔、大小保持不变。

将图像转化为对应的像素矩阵存放在计算机中，矩阵中的元素称为像素，像素的取值在0到255之间，所有的碎片和矩阵都是一一对应。