基于旅行商规划模型的碎纸片拼接复原问题研究.docxVIP

第30卷增刊1 第30卷增刊1 工 程 数 学 学 报 voL 30 supp．1 2013年12月 CHINESE JOURNAL OF ENGINEERlNG MATHEMATICS Dec．2013 doi：10．3969／j．issn．1005-3085．2013．07．007 文章编号：1005-3085(2013)o’卜0099-14 基于旅行商规划模型的碎纸片拼接复原问题研究 向航，王帆，郭树璇 指导教师：王丹 (国防科学技术大学，长沙410073) 编者按：本文在特征选取、碎片分行、行内排序、人工干预等几个建模关键环节均有较深入的讨论，是一篇较为完整 的参赛论文，在特征选取方面做得尤其出色，体现出作者具有较深厚的建模素养．本文在行内排序时，没有 使用文中建立的线性规划模型求全局最优解，而是使用贪心算法求局部最优解，这是本文的主要不足之处， 另外，在模型检验方面的讨论还欠深入． 摘要：本文首先对RSSTD问题，建立了基于二值匹配度的TSP模型，并将其转化为线性规划模型求解：然后对 于RCCSTD问题，根据中、英文字的差别，分别建立了基于改进误差评估的汉字拼接模型和基于文字基 线的误差评估的英文字拼接模型；随后针对T、jlro-Sides RCCSTD问题，利用基线匹配的方法将该问题转 化为RCCSTD问题．本文利用误差评估匹配算法，使用贪心策略实现了碎片复原．文中设计并实现了基 于Matlab的GUl人机交互干预方式，提高了结果的可靠性和完整性． 美键词： 碎片复原：TSP；误差评估匹配；基线误差；人工干预 分类号： AMS(2000)65K05 中图分类号：029；TP391 文献标识码：A 1 问题重述(略) 2 问题分析 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应 用．传统上，拼接复原工作需由人工完成，准确率较高，但效率很低．特别是当碎片数量巨 大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动 拼接技术【1】，以提高拼接复原效率． 本文就单面纵切、单面正交横纵切、双面正交横纵切三种碎纸片复原问题，根据边缘像素 点信息、匹配误差度以及基线误差评估等信息，将这类问题转化为一个TSP模型，最后利用 纸片分组、组内排序、组间排序、人工干预等方法，完成对中、英文碎纸片的复原． 3 问题假设 假设1 需要复原的碎片是来自同一张纸，且对于该张纸具有完备性．我们假设等待复原的 碎纸片都是来自同一张纸，是为了确保我们的拼接是能够完成的，并且我们为了简化问题，认 为碎纸片是完整的，是没有信息缺失的． 假设2同一页中，文字的种类、行间距和段落分布情况是相同的．我们为了简化问题，认 为同一张纸上的文字具有相同的文字字体、字号、行间距等基本文本信息，以确保算法的针对 性和有效性． 100 工 100 工 程 数 学 学 报 第30卷 4 问题1：基于匹配度的RSSTD问题研究 Reconstruction of Strip Shredded Text Documents(RSSTD)【2]：碎片的长度和原始文件的 长度相等，同时所有碎纸片都是等宽的长方形． 为了便于对图像数据进行分析，我们首先需要对其进行数字化处理以及文字行特征的提 取，而后再建立基于匹配度的模型． 4．1图像数字化处理 图像的数字化处理主要包括以下几个方面： 1)二值化处理 由于纵切碎纸片的长度特征(碎片长度与原始文件长度相等)，其边缘像素点信息量丰 富．因此我们采取二值化而非灰度对图像进行了处理，得到每条碎片像素大小为72× 1980(长×宽)，像素点值取{0，1)，其中0和1分别表示颜色的黑与白． 2)edge矩阵的建立 edge k州为19×2的矩阵，储存每一条碎片的边缘像素点信息．其中t表示碎片的编 号，J=o表示左侧边缘像素点信息，J=1表示右侧边缘像素点信息．例如，edge【0，0】储 存001号碎片左侧边缘像素点信息． 3)count矩阵的建立 根据edge p，歹]矩阵，我们可以计算得到一个19×2的count【t，J】矩阵，该矩阵储存每一条碎 片边缘取值为0的像素点的数量．例如，count『O，01=350表示001号碎片左侧边缘共有350个 黑色像素点． 4) shred with blank 1eR的选取 根据count矩阵，若edge[t，o】=o，那么我们就认为该碎片在原始文件中处于最左端，即为 选取的shred with blank lefc． 51碎片行特征的提取 由于原始文件文字行特征明显，因此需要提取碎片的行特征(其具体的原因见匹配度的 定义)．首先确定碎片顶端取值为O的像素点的位置，以此