碎纸片的拼接复原

《碎纸片的拼接复原》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、碎纸片的拼接复原摘要本题目中提供了若干碎纸片的图片，需要利用数学软件进行拼接复原。对本文中的三个问题，利用R语言软件(由新西兰奥克兰大学的RossIhaka和RobertGentleman联合开发，因此简称为R，详细介绍请见附录11)，对图片进行灰度分析，转化为像素矩阵，并通过对贪心算法和拓扑排序的编程，在R语言中选出最优解，最后利用R语言绘图，实现碎纸片的拼接复原。本文根据题目所给知识，利用运筹学基础理论、相关的数学建模知识以及相应的计算机软件，解决了如下问题：问题1：纵切同一页印刷文字文件的破碎纸片，建立碎纸片拼接复原模型和算法。针对中文碎片：利用R

2、语言对图片进行导入，然后将图片数据化，变为像素矩阵，其中255代表白色，0代表黑色，0~255中间数字代表灰色。找到矩阵最右一列为255的图片，即为最后一张碎纸片。利用贪心算法（详细介绍请见附录11），使用R语言程序统计出剩下图片像素矩阵最右一列和最后一张碎纸片的最左边一列同为0的个数，个数越多，说明相邻的可能性越大。建立拓扑排序（详细介绍请见附录11）的数学模型，附件1的19张中文图片分别为，，……，，取出相邻可能性最大的一张为，则与最后一张相邻的为，再重复利用上述算法，找出和的顺序。针对英文碎片：在对图片预处理之后，要对碎纸片的灰度矩阵中的灰度轮廓进

3、行母线相似度的匹配。匹配的相似度越大，说明两张碎片相邻的可能性越大。针对这种情况，我们先将母线进行离散化处理（详细介绍请见附录11），根据母线上的曲率信息计算出母线的相似度，并以此进行比较，类似于中文碎片的处理方法，得出图片的排列顺序。问题2：先对碎片进行与问题1相同的纵切相似度的匹配。但由于进行横、纵切后，碎片较多，每个碎片信息量较小，在拼接的时候应考虑更多的拼接信息。这里除了比较碎片之间灰度矩阵相似度外，另外引用关联度这个概念进行再次验证，以减小误差。最后再对得到的碎片拼接复原的图片进行人工验证(人工干预)，最大程度减小误差。问题3：先进行问题2中的

4、对碎片横、纵切后正面的文字拼接复原，但由于碎片信息量小，误差较大，则利用对关联度最优的选择，选出最适合的拼接排序。然后对结果进行人工验证，对没通过验证的碎片，利用反面再次进行上述操作，直到通过人工验证，得到需要的拼接复原图片。关键词：R语言、灰度矩阵、母线离散化、贪心算法、拓扑排序、关联度32一、问题分析和基础知识介绍破碎文件的拼接在司法物证复原、历史文献修复、军事情报获取以及图像处理等领域都有着重要的应用[1-4]。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们

5、试图开发碎纸片的自动拼接技术，以提高拼接复原效率，得到了众多的研究成果[5-8,11]。然而，目前的结果很少给出具体的数学模型，针对性比较强，没有统一的算法，如何建立数学模型方法[9,10]利用在拼接技术上是本文的主要工作。针对本题目给出的问题，给出了如下分析问题1：要求对纵切的中、英文各一页文件的碎片数据，建立相应的算法进行拼接复原。分析:a、若要对文件碎片拼接复原，首先要对图片进行获取，所以要用相应的软件进行图片导入，我们这里利用R语言实现这一操作，并将图片数字化为灰度矩阵。之所以选择R语言进行，是因为R有特殊的统计技术、绘图功能，以及编程介面和数据

6、输出/输入功能。它是一套完整的数据处理、计算和制图软件系统。其功能包括：数据存储和处理系统；数组运算工具（其向量、矩阵运算方面功能尤其强大）；而且还具有优秀的统计制图功能，编程语言简单而又强大。R还有强大的绘图功能，制图具有印刷的素质，也可加入数学符号。b、中英文碎片数据差别：中文碎片：首先找出图片灰度矩阵最右边一列全为255的图片，即为最后一张图片。再用剩下图片灰度矩阵最右边一列（设为）分别对最后一张图片最左边一列（设为g(x,y)）做差，分别统计结果为0的个数（设为Z），0的个数越多，即Z越大，与最后一张图片相似度越大，相邻的可能性越大。英文碎片：由

7、于中文与英文的文字结构不同，所以在对图片预处理之后，要对碎纸片的灰度矩阵中的灰度轮廓进行母线相似度的匹配。匹配的相似度越大，说明两张碎片相邻的可能性越大。针对这种情况，先将母线进行离散化处理，根据母线上的曲率信息计算出母线的相似度，并以此进行比较。c、因为需要比较的数据组比较多，利用贪心算法和拓扑排序去求需要的最优解。本文利用的拓扑排序树状图，见图1：问题2：要求对横、纵切的中、英文各一页文件的碎片数据，建立相应的算法进行拼接复原。a、我们先运用与问题1同样的方法，将碎片的纵切方向进行匹配，得出最优匹配。b、在问题1基础上又增加了横切的问题。所以碎片变得

8、更小，进行灰度矩阵的匹配后，由于误差较大，得出的匹配会有错误。我们再用同样灰度矩