数学建模论文学习心得.docx

学习2013全国大学生数学模型竞赛B题二等奖论文心得 碎纸片的拼接复原一、 竞赛题目破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。2对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上3上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、论文来源1/mathmodel/2013全国大学生数学模型竞赛B题二等奖碎纸片的拼接复原，作者： 三、学习心得论文的研究目的是解决对纸张形状规整的汉子和细纹碎纸片文档的拼接复原问题。作者主要采用灰色相关度匹配，聚类分析，匈牙利算法，模拟退火等方法来完成碎纸拼接问题。论文一共分为以下几个部分：摘要，问题重述，问题分析，模型假设，问题一的建模与求解，问题二的建模与求解，问题三的建模与求解，模型的评价与改进，参考文献，附录。文章的摘要部分主要对论文的研究目的及研究方法进行了阐述，思路清楚，方法较为科学，但是我认为，作者把摘要分成几步骤来写，不是很科学，而且很遗憾的是我在里面发现了错别字，我认为这是一种不严谨的态度的体现，问题重述部分主要是把原题目写了上去，问题分析部分将原问题转化成了数学问题，我觉得问题重述和分析应该放在一块写会比较好。模型假设部分将问题理想化更方便解决与求解。问题一里，作者对数据进行了预处理，并建立了灰色相关匹配模型，进行求解；问题二里，作者对数据进行二值化预处理，并建立了聚类分析模型，采用匈牙利算法解决问题，这里作者画出了一个流程图，十分清楚地展现了他们的求解过程。对于问题三，作者建立了模拟退火算法模型，得到结论。最后作者附上了自己对于模型的分析以及模型的不足，以及参考文献和求解算法。四、论文改写改写：摘要对破碎文件的拼接复原在现代社会中的作用越来越重要。其涉及领域十分广泛，涵盖司法物证复原，军事情报复原以及历史文物复原等。本文主要通过灰色相关匹配，用聚类分析的方法判断出相邻的纸片，利用匈牙利算法根据上下边缘灰度信息将相邻碎纸片进行匹配，并采用模拟退火算法，最终达到拼接复原成原页面的目的。针对问题一我们要将单面打印的仅纵切的碎纸片进行拼接匹配。首先将图片读入matlab转化为灰度图像，又易知相邻纸片左右边缘自上而下对应格点的灰度值有极大的相似性，根据这一特点我们建立灰度相关匹配模型对碎纸片进行匹配拼接。扫描并记录碎片左、右边缘的灰度值矩阵，我们先利用文档文件页边距特点找到首列碎片，然后将其余下碎纸片进行灰度值对比判断出与其相邻的纸片。重复该步骤得到碎纸片的拼接方案。针对问题二我们需要将单面打印的既横切又纵切的碎纸片进行拼接匹配。由于文档在列方向上有文字行与行间之分，我们照着标准将碎纸片按行等分为11份。首先将灰度图像的信息提取并进行二值化处理，得到能够定位文字行与行间的特征向量。考虑到西文字符高度不一，我们舍去字符上下信息，取字符中央作为比较的基准。然后根据不同碎片的特征向量，我们将碎片按照特征向量的相似程度并加入人工干涉，成功将碎片分为11类，即分别为不同的11行。再利用页边距找到首行与首列。然后利用匈牙利算法根据上、下边缘灰度信息，将相邻两行碎纸片进行拼接匹配。由于存在切割边缘无文字信息的情况，这时我们仿照第一问的方法对碎片进行行内的灰色相关匹配。最终综合两种匹配方案的结果，从而得到碎纸片的拼接方案。 针对问题三我们需要将双面打印的既横切又纵切的碎纸片进行拼接匹配。考虑到刻画碎纸片拼接决策的变量有三个，我们建立了整数规划下的优化模型，采用模拟退火算法进行碎片匹配，以避免采用确定性方法求解时陷入局部最优解的困境。由于碎纸片的像素点较少，英文字符在边缘处的灰度信息也较少，该问中容易出现较大误差。最后综合模拟退火算法与人工干涉两种方式得到了碎纸片的拼接方案。改写问题的重述与分析破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。现要求建立相应的碎纸片拼接复原模型与算法讨论下列问题：1.问题一要求我们对附件一、二中的一系列碎纸片（仅纵切）的信息进行预处理和数字化，从而提取出这类碎纸片的有效特征信息，来将文件拼接复原。如果复原过程需要人工干预，写出干预的方式及干预的时间节点。并用图片形式及表格形式将结果表达出来。由于所给碎纸片的形状均为矩形，对图像碎片进行轮廓特征提取这种方法不可行。而图像碎片为白底黑字，不同碎片的字体形状不同，携带了大量的特征信息。所以，我们拟建立基于内容相关性的图像碎片匹配。图像碎片为黑白两色，可视为灰度图，因此可以利用matlab软件直接对碎纸片进行像素点的提取。显然，相邻两个碎片的连接处字体发生断裂，我们发现，连接处的灰度信息会有较强的相关性，两个图像碎片的相关性大小由像素点构成的列向量的距离来刻画。首先根据页边距得到首行，以首行作为起点，从剩余的图像碎片中挑出左边缘与首行右侧相关性最大的作为第二列进行拼接，再以第二行作为新起点，以此类推，直至拼接完成。2.问题二将研究碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。并将结果用图片及表格形式表达出来。解决问题的关键在于如何对附件三、四中的一系列碎纸片（纵切和横切）的信息进行提取，并以此进行拼接匹配。由于涉及到二维灰度信息匹配，我们首先需要对图像数据进行聚类分析。由于同一行的图像碎片的像素点在竖直方向上分布相似，即文字行、行间行分别一致，我们先通过聚类分析将分为数目相同的不同类别，每种类别作为一行。再根据匈牙利算法的用增广路径求二分图最大匹配的思想，依次求得不同行的列顺序，最后再调整行内部不同图像碎片的顺序。考虑到存在边缘处是空白的情况，我们对于这种情况在行内部进行灰度相关匹配。最后综合两者匹配结果得到最终的拼接顺序。3.问题三是问题二的进一步加深和复杂化从现实情形出