碎纸片拼接问题的数学模型与方法【字数：12183】
摘 要碎纸片拼接问题即利用各种方法实现文件复原的问题，该问题在多个领域都有很重要的应用。人工拼接虽然准确度较高，但存在很多问题，例如会耗费大量的人力物力，且当纸片碎度更加细小时，人工拼接几乎是不可行的，因此我们需要计算机来解决这个问题。首先，本文揭示了用计算机研究此问题的必要性，简述了解决碎纸片问题的一些方法。接着，文章通过提取碎纸片的文字特征及边缘特征，着重建立了两种碎纸片拼接复原的模型，即基于文字特征的匹配模型和基于灰度的形状匹配模型。前者主要利用在碎纸机切割后，碎片和文字本身的特点进行匹配，其步骤是先排列行，再组页成行，实现拼接。而后者主要将碎纸片通过计算机处理成灰度矩阵，再根据相邻碎纸片的灰度矩阵利用边缘相似性进行匹配。最后,文章分别评价了上述两种碎纸片拼接模型，通过比较其各自的优点以及不足，希望可以实现可行、高效的碎纸片拼接技术。
目 录
1.引言 1
1.1 研究碎纸片拼接复原的目的和意义 1
1.2 问题分析 2
2.基于文字特征的匹配模型 4
2.1模型假设 4
2.2建立基于文字特征的匹配模型 4
2.2.1模型分析 4
2.2.2图像预处理 6
2.3模型求解 7
2.3.1 碎纸片行分类 7
2.3.2 行内排列 8
2.3.3 组行成页 9
2.3.4 文件的拼接复原 9
2.4模型拼接结果 9
2.4.1 不考虑边缘留白 10
2.4.2考虑边缘留白 12
3.基于灰度的形状匹配模型 14
3.1建立基于灰度的形状匹配模型 14
3.1.1模型分析 14
3.1.2图像的预处理 14
3.2模型求解 15
3.2.1 匹配步骤 15
3.2.2 拼接复原模型 15
3.2.3 改进拼接复原模型 17
3.3模型拼接结果 21
4.总结 23
致谢 24
参考文献 25
附录 26
1.基于文字特征的匹配模型的核心 *好棒文|www.hbsrm.com +Q: ￥351916072￥
代码 26
2.基于灰度的形状匹配模型的核心代码 27
1.引言
1.1 研究碎纸片拼接复原的目的和意义
碎纸片拼接问题是指将被处理后的破碎纸片通过一定的方法恢复成完整文件的问题。该问题如今主要应用于历史文物的修复工作、司法物证的复原及军事情报的获取等多个领域，比如文献[1]针对兵马俑的自动修复问题进行了一些研究, 文献[2]则针对壁画碎片的修复问题做出了相关的研究。过去，人们常利用人工进行碎纸片拼接，虽然较为准确，但容易对重要文献造成一定的破坏，并且效率较低，工作量大，浪费了大量珍贵的人力物力，因此研究碎纸片自动拼接问题具有非常重要的意义。
碎纸片拼接问题的目的在于尽量减少人工干预，运用先进的计算机技术及一些优秀的算法实现碎纸片的自动拼接复原。在对图片进行人工拼接时，人们可以先在脑中对比图片的边缘色彩，形状，文字等多方面的信息，再经过大脑的分析整合，实现拼接复原。然而，计算机作为由数字构成的系统，并没有如此多的想法，它所能处理的归根到底只是数字。因此，当今人们对此问题研究的中心问题实际在于，如何将人脑的思考及图片本身的信息通过数字传达给计算机，教计算机自己实现拼接。
碎片分为规则碎纸片和不规则碎纸片，针对不同的碎纸片，有着不同的处理方法。对于规则碎纸片，罗智中在文献[3]中，在基于几何特征的碎纸片自动拼接的不足之上，提出了以碎片文字特征和表格线特征为基础，进行碎片半自动化拼接的算法设计。该设计不依赖于几何特征，实现较为简单，但计算规模较大。庄思发,付喜梅在文献[4]中，提出了横向复原算法，针对横切碎纸片和竖切碎纸片进行分类，大大的提高了准确率，但存在对英文碎片不适应，复原效果不统一的问题。对于不规则碎纸片，何鹏飞在文献[5]中，通过蚁群优化算法，设计了碎纸片拼接系统。他利用局部拼接实现候选匹配迭代，通过欧式变换进行组合，最终实现了全局拼接。此外有许多研究利用边界检测算法，角点检测算法，遗传退火算法等实现了碎纸片的拼接。
除了一些较为传统的方法以外，还出现了许多优秀的设计研究，如刘铁在文献[6]中借助数字图像的处理技术，建立了匹配度函数，提出了针对打印文件可行性较高的算法设计。廖敏瑜等人则在文献[7]中创新的利用改进的遗传算法（GA）及光学字符识别技术（OCR）,根据文字基线，采用贪心算法，实现了碎纸片的全自动拼接。
1.2 问题分析
人工拼接主要是通过肉眼识别，在脑中汇聚信息，快速提取图像边缘特征，通过有意识的选择操作，实现拼接。其中图像边缘的特征主要如下：
图片边缘的形状
边缘文字的内容
边缘图像的颜色
图像的纹路，材质
如今，各种研究追根究底都是对这几方面的碎纸片信息进行提取，通过一定的方法向电脑传达出图像的特征，再进行匹配。大量的研究不是通过研究其中一个方面实现复原，就是通过研究多个方面结合起来实现复原。以下针对不同的特征，我进行了一定的分析。
通过图像边缘的形状进行匹配：很多人按照此思路进行了研究分析。当碎纸片是规则碎纸片时，该方法较为简单，因为规则纸片的形状大小完全相同。然而，当碎纸片是不规则碎纸片时，形状的信息则会有些复杂。在该情况下，虽然可以利用一些方法确定拼接图像，但是相对而言，拼接的速度可能较慢。
通过图片的内容进行匹配：针对手写稿而言，该方法说到底也是根据文字或图片的颜色或是形状进行匹配。而针对打印稿而言，由于其内容具有很多特点，我们可以根据其特点实现碎片拼接，因而较为简便。
通过图像的颜色进行匹配：计算机存在着不同的描述方式，如RGB,HSI,HSV等，利用不同的描述方式描述碎纸片边缘的颜色，再通过颜色的匹配实现碎纸片的拼接复原，相对而言是一种较为可靠的方式。有大量学者也按照此思路进行了实验，然而研究发现，根据不同的描述方式，碎纸片复原往往会得到不同的拼接结果。其中，由于HSI最为接近人类的肉眼识别效果，因而复原的准确度较高。
目 录
1.引言 1
1.1 研究碎纸片拼接复原的目的和意义 1
1.2 问题分析 2
2.基于文字特征的匹配模型 4
2.1模型假设 4
2.2建立基于文字特征的匹配模型 4
2.2.1模型分析 4
2.2.2图像预处理 6
2.3模型求解 7
2.3.1 碎纸片行分类 7
2.3.2 行内排列 8
2.3.3 组行成页 9
2.3.4 文件的拼接复原 9
2.4模型拼接结果 9
2.4.1 不考虑边缘留白 10
2.4.2考虑边缘留白 12
3.基于灰度的形状匹配模型 14
3.1建立基于灰度的形状匹配模型 14
3.1.1模型分析 14
3.1.2图像的预处理 14
3.2模型求解 15
3.2.1 匹配步骤 15
3.2.2 拼接复原模型 15
3.2.3 改进拼接复原模型 17
3.3模型拼接结果 21
4.总结 23
致谢 24
参考文献 25
附录 26
1.基于文字特征的匹配模型的核心 *好棒文|www.hbsrm.com +Q: ￥351916072￥
代码 26
2.基于灰度的形状匹配模型的核心代码 27
1.引言
1.1 研究碎纸片拼接复原的目的和意义
碎纸片拼接问题是指将被处理后的破碎纸片通过一定的方法恢复成完整文件的问题。该问题如今主要应用于历史文物的修复工作、司法物证的复原及军事情报的获取等多个领域，比如文献[1]针对兵马俑的自动修复问题进行了一些研究, 文献[2]则针对壁画碎片的修复问题做出了相关的研究。过去，人们常利用人工进行碎纸片拼接，虽然较为准确，但容易对重要文献造成一定的破坏，并且效率较低，工作量大，浪费了大量珍贵的人力物力，因此研究碎纸片自动拼接问题具有非常重要的意义。
碎纸片拼接问题的目的在于尽量减少人工干预，运用先进的计算机技术及一些优秀的算法实现碎纸片的自动拼接复原。在对图片进行人工拼接时，人们可以先在脑中对比图片的边缘色彩，形状，文字等多方面的信息，再经过大脑的分析整合，实现拼接复原。然而，计算机作为由数字构成的系统，并没有如此多的想法，它所能处理的归根到底只是数字。因此，当今人们对此问题研究的中心问题实际在于，如何将人脑的思考及图片本身的信息通过数字传达给计算机，教计算机自己实现拼接。
碎片分为规则碎纸片和不规则碎纸片，针对不同的碎纸片，有着不同的处理方法。对于规则碎纸片，罗智中在文献[3]中，在基于几何特征的碎纸片自动拼接的不足之上，提出了以碎片文字特征和表格线特征为基础，进行碎片半自动化拼接的算法设计。该设计不依赖于几何特征，实现较为简单，但计算规模较大。庄思发,付喜梅在文献[4]中，提出了横向复原算法，针对横切碎纸片和竖切碎纸片进行分类，大大的提高了准确率，但存在对英文碎片不适应，复原效果不统一的问题。对于不规则碎纸片，何鹏飞在文献[5]中，通过蚁群优化算法，设计了碎纸片拼接系统。他利用局部拼接实现候选匹配迭代，通过欧式变换进行组合，最终实现了全局拼接。此外有许多研究利用边界检测算法，角点检测算法，遗传退火算法等实现了碎纸片的拼接。
除了一些较为传统的方法以外，还出现了许多优秀的设计研究，如刘铁在文献[6]中借助数字图像的处理技术，建立了匹配度函数，提出了针对打印文件可行性较高的算法设计。廖敏瑜等人则在文献[7]中创新的利用改进的遗传算法（GA）及光学字符识别技术（OCR）,根据文字基线，采用贪心算法，实现了碎纸片的全自动拼接。
1.2 问题分析
人工拼接主要是通过肉眼识别，在脑中汇聚信息，快速提取图像边缘特征，通过有意识的选择操作，实现拼接。其中图像边缘的特征主要如下：
图片边缘的形状
边缘文字的内容
边缘图像的颜色
图像的纹路，材质
如今，各种研究追根究底都是对这几方面的碎纸片信息进行提取，通过一定的方法向电脑传达出图像的特征，再进行匹配。大量的研究不是通过研究其中一个方面实现复原，就是通过研究多个方面结合起来实现复原。以下针对不同的特征，我进行了一定的分析。
通过图像边缘的形状进行匹配：很多人按照此思路进行了研究分析。当碎纸片是规则碎纸片时，该方法较为简单，因为规则纸片的形状大小完全相同。然而，当碎纸片是不规则碎纸片时，形状的信息则会有些复杂。在该情况下，虽然可以利用一些方法确定拼接图像，但是相对而言，拼接的速度可能较慢。
通过图片的内容进行匹配：针对手写稿而言，该方法说到底也是根据文字或图片的颜色或是形状进行匹配。而针对打印稿而言，由于其内容具有很多特点，我们可以根据其特点实现碎片拼接，因而较为简便。
通过图像的颜色进行匹配：计算机存在着不同的描述方式，如RGB,HSI,HSV等，利用不同的描述方式描述碎纸片边缘的颜色，再通过颜色的匹配实现碎纸片的拼接复原，相对而言是一种较为可靠的方式。有大量学者也按照此思路进行了实验，然而研究发现，根据不同的描述方式，碎纸片复原往往会得到不同的拼接结果。其中，由于HSI最为接近人类的肉眼识别效果，因而复原的准确度较高。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/qrs/85.html
