数学建模2013B题优秀论文.doc

融入FFT的综合评价的碎纸片拼接复原 摘要 破碎文件的拼接有很广阔的应用前景，如今计算机技术已逐步取代传统的人工拼接，成熟的碎纸片自动拼接技术能大幅提高拼接复原效率，尤其在文件数目较多的情况下，其优势愈加明显。本文建立了一种碎纸半自动拼接算法，在中英文单面纵向切片、乱序中英文单面纵向切片、中英文单面纵横切片及英文双面纵横切片上都有不错的表现。 问题一：对于中英文单面纵向切片的恢复，本文首先分别用基于0-1二值矩阵的边缘比对法和基于FFT信号处理的互相关系数模型对给定的附件1、2进行了匹配，再发掘了第二种方法的优势，对上下顺序不定的中英文单面纵向切面进行了正确的匹配。这三次自动匹配的准确率均为100%，且用时均小于1秒。 法一：本文首先用MATLAB对附件1、2中的碎片编码，转为二值矩阵。之后利用边缘列碎片的空白确定最左边的一列碎片，之后利用边缘比对一致的像素点数目的多少，按照数目最多的原则匹配出其相邻碎片，逐步实现了中英文单面纵向切片的碎纸拼接。 法二：编码方式同上，本文将二值矩阵的左右边缘自上到下看作一列时域中的数字信号，通过FFT快速傅里叶变换算法得到该信号的频谱特征，利用归一化互相关系数衡量出信号的频谱特征的相关性，按照相关性最大的原则对边缘碎片依次匹配。最终该方法全自动地完全正确地实现了中英文单面纵向切片的碎纸拼接。 对于上下顺序不定中英文单面纵向切片，本文利用了傅里叶变换的物理特性。因为频域中的信号不受扫描顺序的先后影响。所以方案二可以对乱序的碎片进行快速排序，优于方案一。 问题二：对于中英文单面横纵切片的恢复，本文利用综合评价法分别进行行与列的匹配，这两次的结束均进行了一次人工干预，两种算法的运行时间分别为5.5s与5.7s，最终正确率分别为90.4%和82.8%。 对于上述两种方法，本文均先确定出图像左右边缘列的碎片，之后从中随机选择碎片作为行匹配的标志。对于中文，行的划分依据是汉字的中心纵坐标；对于英文，行的划分依据是字母的下端基线。利用行匹配将所有的碎片分行。此处的评价指标为问题一中两种方案评价结果的综合，对待匹配的碎片时域和频域均提出了较高要求，提高了匹配率。按照这个指标对碎片进行行匹配。用每个碎片的左右两个边分别与左右边缘的两边进行匹配，选取其中得分最高的完成匹配，重复直至完成行匹配。对其结果进行人工干预。之后进行间排序，对结果再进行一次人工干预，完成碎片的复原。 问题三：对于英文双面横纵切片的恢复，本文主要沿用了问题二的解法，并进行了适当修改，同样的两次人工干预。其匹配时间为20.3s，准确率为84.7%。 对附件5进行观察，发现同一碎片的a、b两面字母的基线完全相同，因此在列匹配后，仅对所有末位为a的碎片进行行分类。之后从任意一侧开始匹配，分别计算正正与反反、正反与反正，这两种情况的综合评价值之和，选取最高的进行匹配，并利用综合评价值的大小做出正反匹配。行匹配结束后，进行一次人工干预。随后按照之前的方法进行行间排序，随后再进行一次人工干预，得出预期结果。 最后，本文指出了实际中碎纸恢复的拓展，它们均可通过本文算法的改进去实现。 关键字：边缘比对法 FFT 互相关系数 综合评价 问题重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。 问题一：单面印刷文字文件纵切碎片的复原 对于给定的来自同一页印刷文字文件的碎纸机纵切纸片，建立碎纸片拼接复原模型和算法 针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。 问题二：单面印刷文字文件横纵切碎片的复原 (1)对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法 (2)针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 问题三：双面印刷文字文件横纵切碎片的复原 (1)上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。对此，请尝试设计相应的碎纸片拼接复原模型与算法。 (2)就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 问题分析 本题需要我们建立模型设计出算法，实现几类破碎文档的拼接。主要有以下几类问题需要解决：中英文文档仅被纵切、中英文文档分别被横切和纵切以及双面英文文档被横纵切割。 要解决本问题，主要的思