关于碎纸片自动拼接的数学模型_数学建模竞赛优秀论文

关于碎纸片自动拼接的数学模型 1 大学生数学建模竞赛优秀论文

关于碎纸片自动拼接的数学模型 摘要 本文针对生活中破碎文件的拼接难度大，效率低等现象，从题目所给的情形出发，利用计算机软件把碎纸片图像转化为数字图像，综合运用matlab软件中的数字图像处理方法，建立了以图与图之间的相似程度为基准的数学模型。这个模型的评价标准很简单，就是相似度函数的值。通过比较图像与图像之间的相似度函数的值的大小，就可以得出碎纸片的具体拼接序列。 对于问题（1），首先，用matlab软件的imread函数对图像的进行读取，得

到数据矩阵为),(yxFi。其次，根据模型的假设（1），找到最右端的碎纸片，并

记为),(1yxF。然后，以数据矩阵),(yxFi为基础，引入相似度函数)(bsim，并求 出相似度函数值。最后，用matlab工具箱中的sort函数把所得到的相似度函数值进行排序，所得到的相似度函数值最小的图像即为与最右端的碎纸片匹配的图像。如此重复18次，即可得附件1的中文图像的排列序号，结果如表1所示。同理可得附件2的英文图像排列序号，结果如表2所示。复原结果图片见论文附件的图1和图2。 对于问题（2），同样先找到最右端的11张图像和最上方的19张图像，根据图像的页边距特性确定原图像右上角的第1张图像。利用问题（1）的算法可得最右端的11张图像和最上方的19张图像的排列序号。然后，在问题（1）的算法的基础上，利用图像中的文字的固定间距去改进算法，缩小搜索范围，并在拼接完一行后显示一次结果，由于近似距离计算公式与人主观视觉差异，所以需要人机交互调整结果。如此重复18次，即可得附件3的中文图像的排列序号，结果如表3所示。同理可得附件4的英文图像排列序号，结果如表3所示。 对于问题（3），与问题（2）相似，只是碎纸片由单面变为双面。因此在匹

配图像时，引入两重相似度函数)(Qsim，以确保正反两面能同时匹配。同时每匹配5张图像显示一次结果，以增加人工干预次数。如此重复若干次，即可得最终的复原图像。

关键字 相似度函数 matlab软件 数字图像处理 关于碎纸片自动拼接的数学模型

2 一、 问题的重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 【数据文件说明】 (1) 每一附件为同一页纸的碎片数据。 (2) 附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。 (3) 附件3、附件4为纵横切碎片数据，每页纸被切为11×19个碎片。 (4) 附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对应文件000a、000b。 【结果表达格式说明】 复原图片放入附录中，表格表达格式如下： (1) 附件1、附件2的结果：将碎片序号按复原后顺序填入1×19的表格； (2) 附件3、附件4的结果：将碎片序号按复原后顺序填入11×19的表格； (3) 附件5的结果：将碎片序号按复原后顺序填入两个11×19的表格； (4) 不能确定复原位置的碎片，可不填入上述表格，单独列表。

二、 问题的分析 碎纸，即一张纸在外力的作用下被分开的几个小分块。而在实际生活中，往往需要我们把这几个碎纸块还原成一张纸，这就需要用到碎纸拼接技术。随着科学技术的迅速发展，我们可以把碎纸的一些特征用平面扫描仪、数码相机、摄像机等设备记录下来。而如何把一张张图像的特征转化成数字特征，并根据这些数据特征去建立相关的数学模型或计算机算法，从而借用计算机来帮助我们拼接图像，提高效率，就是问题的关键点了。 传统的图像碎片自动拼接算法有蚁群优化算法、遗传算法等，我们通过分析数据文件发现这些算法并不适合于本题。原因是以上的算法是基于碎片有不规则边缘的基础上的，而本题中碎纸图像的切痕是规则的，且无文字识别能力。 第1步，把所给的图像的数字信息(即像素)用matlab软件读取出来，得到了图像的数据矩阵，通过分析数据后发现，相邻两张图片的边缘像素具有较大的相似度。第2步，利用数字图像处理的方法，结合题目所给数据文件的说明，得到了图与图之间的灰度相关关系的相似度函数，即取出数据矩阵的边缘列与其他图像的数据矩阵边缘列进行最短距离运算。第3步，建立以图与图之间的相似程度为基准的数学模型。这个模型的评价标准很简单，就是相似度函数的值。相似度函数的值越小，就认为两张图像越靠近，即匹配的概率就越大。第4步，通过求相似度函数值，对所得到的函数值进行排序，从中寻找到相似度函数值最小的图像，就得到了最佳匹配图。第5步，每匹配若干张图，显示一次结果，若发现有文字不连续或意思不通的，则进行人工干预。 对于问题（1），由于题中给出的碎纸片是由碎纸机纵向切割而得到的，于是碎片边缘的尖点特征尖角特征，面积特征等几何特点几乎一样，导致无法运用以碎纸片有不规则边缘为基础的传统计算机算法进行拼接。因为边缘相似的碎纸片的拼接，理想的计算机拼接不仅要考虑边缘的匹配还要满足字迹断线或碎片内的内容的相符。然而这种理想方法很难实现，于是利用数字图像处理的方法，建立了以图与图之间的相似程度为基准的数学模型。首先，用matlab软件的imread

函数进行图像的读取，得到数据矩阵为),(yxFi。其次，根据问题的假设（1）可

以知道当灰度图中后n列灰度值),(yxfi恒等于255时即可认为这一碎纸为最右端的碎纸片，并记为),(1yxF。然后，以数据矩阵),(yxFi为基础，引入相似度函数)(bsim。最后，用matlab工具箱中的sort函数把所得到的相似度函数值进行排序，所得到的相似度函数值最小的图像即为与最右端的碎纸片匹配的图像。如此重复18次，就可以得到附件1的所有图像的排列序号。附件2的图像拼接算法与附件1 的图像拼接算法一致。由此问题（1）的算法模型确定完毕。 对于问题（2），附件3和附件4的碎片图像是碎纸机采用横切与纵切所得到的，与问题（1）相似的碎纸边缘的特点是一致的，无法采用几何特性拼接。于是可以利用问题（1）的模型，设计出以图像灰度系数相关的算法进行图像的拼接。同样采用matlab软件的imread函数进行图像的读取，转化为灰度图即可得到一个MN的数据矩阵。由于所被碎纸机纵横切割的是标准纸张，其具有页边距的特性。可以首先在209张碎纸片中寻找到应该位于页面最右端或者最左端的11张碎纸条，因为有页边距的原因，此时它们的灰度图像第后n列灰度值全为255，并且具有相同的边距（即从后n+1行开始均不全为255）。采用同样的方法我们也可以得到位于页面上方的19张碎片。 根据所得到的图像我们可以人工寻找到位于最右端的那一列的第一张碎纸片序号。根据问题（1）的模型的图像拼接的灰度相关方法，我们将位于最右端的那一列的第一张碎纸片与剩余的10张碎片独立进行纵向拼接。得到被碎纸机纵向切割的最右端的一整列碎纸条。但是，在运用灰度度相关关系进行图片的匹配时，将会出现多个与第一张图像匹配的图像。于是我们采用人工干预，在符合条件的若干张（不超过5张）图像中找到能把文字信息完整拼接上的图像。可知最右端的一张碎纸片，以此碎纸条为基准链，从右往左寻找可匹配横向（即第一行）方向图像，除了要根据灰度值相关关系，还要人工干预判断行距是否一致。 在此过程中除了问题（1）的模型基础上运用相关算法外，人工干预也起到关键性作用。附件4的图像拼接算法与附件3的图像拼接算法一致。由此问题（2）算法模型确定完毕。 问题（3）中所给出的碎纸是由碎纸机切割一页英文印刷文字双面打印文件而得到的。一张碎片有正反两面，并且所给数据中并不能把正反面分开，导致在寻找匹配图像时难度增加。但是，依然可以运用印刷纸张的页边距特性寻找位于最右边碎纸。通过计算机搜索可以找到22张位于页面最右端和最左端的碎片图像。再次运用标准纸的性质，计算机搜索位于页面上方的38张碎纸图像。我们可以通过以找出的碎片图像中找到两幅即位于页面上方与最右边的图像，于是可

以得到位于正面右上端的正面的一幅图像，用矩阵表示为),(119yxF，另一幅图像

为反面的左上端的图像用矩阵表示为),(01yxF。可以进行人工干预，找到了位于原文件最左端的第1个碎纸图像和最右端的第一个图像。运用模型一的算法寻找与之匹配的图像：第一步，将所得碎片图像分别从上往下纵向寻找匹配图像，因为正反面图像往下搜寻匹配的图像是同一张的，通过两个相似度函数寻找到匹配图像。通过拼接即可得到碎纸机纵向切割的最右的一张碎纸。第二步，以最右端的拼接而成的碎纸图像为基准链从右往左寻找匹配图像。按照解决问题（2）的算法寻找匹配图。在此过程中，会有人工干预从满足灰度值要求的情况下找到行距与基准链相同的匹配图像。通过matlab软件编程可得原文件。

三、 模型的假设与符号的说明

3.1 模型的假设 （1）假设完整的图像是一张有边界的标准纸张纸，即有明显的边界特性。 （2）假设完整的图像在切割时和切割后边界整齐，没有不规则的边缘。 （3）假设完整的图像的像素点录入过程没有噪声干扰。 （4）假设完整的图像中的文字是规则的，即大小一致。

3.2 符号的说明

处理后对应数据矩阵张碎纸反面图像在图像表示第处理后对应数据矩阵张碎纸正面图像在图像表示第值。张图像的最小相似函数张与第表示第。张图像的相似度函数值张与第表示第）处的灰度值。对应矩阵在点（张碎纸图像在图像处理表示第后对应的数据矩阵。张碎纸图像在图像处理表示第iyxFiyxFjijibyxiyxfiyxFiiijjiii),(),(,),(),(