文档介绍：碎纸片的拼接复原
摘要
本文主要解决碎纸片拼接复原问题。利用附件所给碎纸片的数据,运用蚁群优化算法、Adaboost算法、Harris角点检测算法,利用Matlab软件编程求解,得到碎纸片拼接复原结果。
针对问题一,依据文字所在行的几何特征,先将文字进行二值化处理,得到文字的数据信息。运用蚁群优化全局匹配方案完成整体匹配,利用回溯的Best-First搜索算法,得到最佳候选匹配对,由于碎纸片形状相似,Best-First搜索算法会大大降低拼接效率,最后建立蚁群优化算法模型对复原结果进行优化,得到中、英文拼接复原图(见附录一)及顺序表(见表2、表3)。
针对问题二,先对附件3、附件4中的碎纸片进行像素特征分析,将每一个矩形像素特征区域的白色区域设为0、黑色区域设为1,利用Adaboost算法对碎纸片进行分类处理,再依据矩形像素特征进行匹配,得到拼接复原中文、英文图片。对每次匹配循环进行人工干预得出碎纸片的拼接复原顺序图(见附录二)及顺序表(见表4、表6)。
针对问题三,在对比经典角点检测算法的基础上,利用附件5中图片的信息,运用Harris角点检测的多层匹配图像拼接算法,得到图片的角点信息。采用标准互相关联法和互信息法对Harris角点进行粗匹配,之后根据特征点周围的边缘信息过滤为匹配点,再用RANSAC进行精确匹配,得到一幅完整的拼接复原图像。最后,运用神经网络边缘检测算法进行优化,快速的获取准确的碎纸片的拼接复原顺序图(见附录三)及顺序表(见表8、表9)。
关键词: 蚁群优化算法 Adaboost算法 Harris角点检测神经网络

1 问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上,拼接复原工作需由人工完成,准确率较高,但效率很低。特别是当碎片数量巨大,人工拼接很难在短时间内完成任务。随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。请讨论以下问题:
(1)对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预,请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达(见【结果表达格式说明】)。(2)对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原并针对附件过程需要人工干预,请写出干预方式及干预的时间节点。复原结果表达要求同上。
(3)上述所给碎片数据均为单面打印文件,从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果,结果表达要求同上。
2 问题分析

若对中、英文各一页文件的纵切碎纸片拼接复原,需考虑复原的碎纸片之间的边界衔接、字迹线条、图片属性、文字的行高、文字行间距及文字断线等信息。利用碎纸片文字所在行的几何特征,先对文字进行二值化处理。借助蚁群优化算法的全局匹配方案,完成整体匹配。再运用回溯Best-First搜索算法,得到最佳候选匹配对。考虑到碎片形状特征相似度高等原因,不合理的候选匹配对可能大量存在,导致拼接效率大大降低。再建立蚁群优化算法进行优化,利用Matlab编程得到碎纸片拼接复原结果。

若将中、英文各一页文件的纵切碎纸片拼接复原,利用Adaboost算法,先将附件3、附件4中给出的碎纸片分别进行编号,再将所有待匹配碎纸片进行初始化,然后进行错误率分析,根据误差分析结果来调整权重,得到分类结果。对所有碎片分类结果进行矩形像素特征分析,最后由矩形像素特征匹配出碎纸片的原图,对于匹配的循环进行人工干预得出碎纸片的排列顺序表。

若对双面打印文件的碎纸片拼接复原,需考虑正反面文字的对应情况,先用人工干预的方式对文件的部分碎纸片拼接复原。图像拼接复原需考虑图像特征,本文基于碎纸片的角点特征,利用附件5给出的一页英文印刷文字双面打印文件的碎纸片数据,在对比经典角点检测算法的基础上,运用Harris角点检测的多层匹配的图像拼接算法,采用标准互相关联法对Harris
角点进行粗匹配,之后根据特征点周围的边缘信息过滤为匹配点,再用RANSAC进行精确匹配,得到一幅完整的拼接复原图像。出于对结果准确性以及拼接快速性的考虑,运用BP神经网络边缘检测算法将结果进行优化。最后,利用数学期望、方差等统计特性参数对检测出来的边缘图像进行质量评价。
3模型假设
(1)假设碎纸片在复原过程中没有损坏