2013高教社杯全国大学生数学建模竞赛题目

《2013高教社杯全国大学生数学建模竞赛题目》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于最小匹配误差的碎纸片拼接复原模型摘要对碎片的拼接复原工作在司法、军情获取、历史文献修复等方面具有举足轻重的地位。人们为了使碎片的拼接复原工作效率更为高效，尝试开发利用计算机拼接碎片技术。这往往需要人为的对碎片进行一些加工处理，然后再结合计算机技术，来实现对碎片的拼接复原工作。针对问题一，首先对碎片进行灰度处理，然后对数据进行二值化处理。问题一是对纵切碎片的拼接复原问题，碎片边缘信息较多，故我们只需要考虑每张碎片的边缘信息，使其生成边缘矩阵就好。对碎片进行二值化处理，用{0,1}来表示边缘像素点的值，大大简化了问题一的求解。利用二值化处理出的数据，建立旅行商问题模型，即TSP

2、模型，使得碎片匹配误差最小，从而完成碎片的拼接复原。针对问题二，考虑到是在问题一的基础上对纸张再进行横切的碎片的拼接复原问题。首先我们还是对碎片进行灰度处理和数据二值化处理，由于纵切和横切使得碎片变小，碎片所含信息变少，故我们提取碎片四周的边缘信息。附件3、4中所给碎片数量多，碎片的边缘信息总量比较大，所以我们利用SPSS软件对碎片上边缘进行聚类分析，想要达到简化问题二求解的目的。通过对附件3、4中大量碎片进行观察，我们根据碎片上边缘的空白截距、文字截距和行间距，将碎片大致分为三类，然后利用碎片上边缘的裁截距对碎片进行聚类分析，从而将大量碎片进行分类，简化问题的求解。首次聚类并

3、未得到理想的分类，故我们在第一次聚类的基础上，根据上边缘是否为文字，对碎片再次进行分类，并借助一定程度的人工干预，使得碎片平均分为12组。根据得到的12组碎片，利用问题一建立的模型使得碎片之间匹配误差最小，分别对12组内的碎片进行拼接。然后利用问题一的求解方法，对12组间的碎片进行拼接复原，问题二碎片的具体拼接复原结果详见附录。针对问题三，考虑到对双面打印文件的纵切和横切的到碎片的拼接复原问题，我们采用一步步简化的思想，把该问题分解为在问题二的求解基础上增加难度和复杂度的双面打印文件碎片的拼接复原问题。首先还是要对附件中碎片进行灰度处理和数据二值化处理。由于问题三中碎片面积太小

4、，所含边缘信息太少，故我们同问题二一样，利用SPSS软件对碎片进行聚类分析。然而第一次的分类结果却不是很理想，故我们考虑下边缘信息，再次进行聚类分析。加以一定的人工干预，直至将碎片平均分为11组。再利用模型二中匹配误差最小原则，寻找每张碎片的最优匹配的碎片，最终结果详见附录。关键字：灰度处理二值化处理TSP聚类分析匹配误差一.问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术

5、，以提高拼接复原效率。请建立以下问题模型：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，要求写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。要求同问题一。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面

6、打印文件的碎片数据。设计相应的碎纸片拼接复原模型与算法，要求同上。二．问题分析2.1问题一的分析由于考虑纵切碎片的拼接复原问题，碎纸片的边缘信息量比较大，因此仅利用边缘信息进行求解。在本题中，我们将每一个碎片看做一个完全图的顶点，将问题转化为一个旅行商的模型，即TSP问题模型。寻找一条经过每个顶点（仅经过一次），不回到原点的最短路径，使得边权值之和达到最小。其中，边权值为相邻两个碎片之间的匹配误差。对碎片进行二值化处理，可以大大简化该问题的求解。首先我们根据数据二值化处理结果，可以找到纸张最左边的碎片，而后以最左边的碎片为起点，利用遍历法求解出第二张碎片。依次进行下去，我们可以

7、得到纸张碎片的整体排序。对于为正确处理的碎片，我们要采取一定的人工干预进行调整求解。2.2问题二的分析由于问题二考虑的是对碎纸片既纵切又横切拼接复原问题，根据附件信息可知，纸张被分别切成12×24个碎片和10×18个碎片，碎片太小，所含边缘信息量太少。所以利用SPSS软件，采用聚类分析方法，对大量的碎片进行分类。其中，纵切碎片的拼接复原问题的求解同问题一，在此基础上，我们只考虑碎片的横切拼接复原问题。提取碎片四周的边缘信息，首先，根据上下边缘信息对碎片进行分类，对于其中未正确处理的碎片进行一