全国大学生数学建模大赛安徽赛区二等奖.pdf

碎纸片的拼接复原 摘要 碎纸片自动拼接技术是碎纸片处理与模式识别领域中一个较新的且典型的应用。 文为了解决碎纸片的拼接复原问题，建立了相似度匹配、图像灰度的数值化角点匹配和 SIFT特征的拼接等三种碎纸片拼接复原模型及相应的算法，得出了附件中碎纸片的拼 接复原碎纸片与对应碎纸片的编号顺序。 对于问题一，首先对碎纸片进行二值化处理，使碎纸片转化为各像素值为0或1的 矩阵。人工干预选出即将复原碎纸片的第一列，依次计算剩余碎纸片与该列碎纸片的相 似性度量，将相似性度量最大的碎纸片与其拼接。然后，建立基于相似性度量的相似度 匹配模型，并利用序列相似度检验方法对该模型进行了验证，通过快速匹配迭代，找到 基于下一幅二值碎纸片的像素矩阵与上一幅二值碎纸片的像素矩阵的最佳匹配碎纸片。 利用回溯有哪些信誉好的足球投注网站算法对此模型进行求解，得到中文碎纸片的顺序为(复原图片见附录1)： 008014012015003010002016001004005009013018011007017000006； 英文碎纸片的顺序为(复原图片见附录1)： 004003006002007015018011000005001009013010008012014017016。 对于问题二，利用问题一中对碎纸片的二值化处理以及碎纸片匹配相似程度，初始 化每列碎纸片的相似性度量，并以此作为匹配依据，在选出第一列的碎纸片（无序）的 基础上，根据行相似性度量和二值碎纸片的像素矩阵来建立图像灰度的数值化角点匹配 模型和算法分析。依据每张碎纸片中每两行文字之间的距离相等为约束条件，筛选出可 进行匹配的碎纸片，同问题一，通过列相似性度量将各行纸片进行拼接。最后，人工干 预选出第一行图片，依据行相似性度量对各行纸片进行拼接，所有的二值碎纸片依次进 行迭代，最终输出完整的匹配碎纸片。（中文、英文的复原碎纸片见附录2） 对于问题三，首先需要对碎纸片进行二值化处理，依据尺度不变特征变换原理，找 出各碎纸片的特征点，并依照此原理，将具有相同特征点的碎纸片进行两两匹配，配对 的结果放入特征匹配的集合中。然后利用随机一致性抽样算法，使用采样和验证的方法， 得到大部分特征点都能满足的数学模型的参数。不断找出特征匹配集合的各匹配结果的 内点，内点数量最大的匹配即为此匹配的最优解，并将结果进行同样组合，不断匹配直 至所有碎纸片拼接完成。 最后，对本文模型的算法进行改进，并对模型进行评价与推广。 关键词：相似度 角点匹配 尺度不变特征变换 回溯有哪些信誉好的足球投注网站 随机抽样一致 1 一、问题重述 1.1问题背景 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重 要的应用。传统上的人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们 试图开发碎纸片的自动拼接技术，以提高拼接复原效率。 在我们的日常生活中会碰到很多需要将碎片拼起来而将原物复原的情形。例如：文 物考古领域中，需要将发掘到的古代的陶瓷碎片拼接成器物；情报工作领域中，需要将 破碎的文件拼接还原，以便得到文件上的信息；刑侦领域中也存在类似的任务如要将破 碎的证物拼接还原的问题，如将指纹片段拼成完整的指纹。这些碎片拼接目前仍依赖于 人力，是十分费时费力的。因此，找到一种机器方法对这些碎片进行拼接是十分必要的。 1.2研究问题 问题一：对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立 1 2 碎纸片拼接复原模型和算法，并针对附件 、附件 给出的中、英文各一页文件的碎片 数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。 问题二：对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并 3 4 针对附件 、附件 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过 程需要人工干预，请写出干预方式及干预的时间节点。 问题三：上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打 印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文 件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的