基于文字特征的规则碎纸片自动拼接.pdfVIP

2014年 5月 汕头大学学报 (自然科学版) 第29卷 第2期 May．2014 JournalofShantouUniversity(NaturalScience) V01．29 NO．2 文章编号：1001—4217(2014)02—0004—08 基于文字特征的规则碎纸片 自动拼接 马俊明，赖楚廷，l、尚明，李 健 (汕头大学理学数学系，广东 汕头 515063) 摘 要：通过分析具有规范版式的中文文档，以2013年全国大学牛数学建模竞赛 B题附件 3的数据为样本，提出基于文字特征的规则碎纸片的自动拼接算法．该算法通过研究文字行 高 、间距等特征构建一系列分类准则对碎纸片进行分类 ，并将分类后的同一行碎纸片排列问 题转化为旅行商问题进行求解，最后将组行成页问题再次转化为旅行商问题进行求解，实现 规则碎纸片的自动拼接．根据该算法编写MATLAB和LINGO的程序对规则切割形成的碎纸 片进行_『拼接试验，试验结果表明该算法效果较好． 关键词：规则碎纸片拼接；不匹配程度；旅行商问题 中图分类号：TP301；O29 文献标志码：A 0 引 言 碎纸片的拼接r泛地应用在司法物证修复、历史文献修复以及军事情报的获取等诸 多领域，故利用计算机拼接碎纸片的方法成为人们研究的热点．针对非规则的碎纸片， 利用碎片边缘的尖点特征、尖角特征、面积特征等几何特征，有哪些信誉好的足球投注网站与之 配的相邻碎纸 片并进行拼接 1．但是对于形状相似或者相 同的碎纸片，这类拼接方法并不适用． 对于形状规则的碎纸片，文献[6]研究了通过碎纸片内的文字行特征和表格特征来进 行拼接．这种方法提高了拼接效率和降低了拼接难度，但是仍需较多的人丁于预进行拼 接．本文通过研究碎纸片中文字所在行的几何特征信息，对中文文档被纵切和横切后所 形成的规则碎纸片构建准确的行分类准则．具体来说 ，行分类准则是通过分析碎片文字 所在行文字的高度 、文字的间距等几何特征信息来构建的．对于完成行分类的碎纸片， 构建碎纸片间的不匹配程度将 同一行的碎纸片排列问题转化为旅行商 问题进行求解．对 于完成行内排列的碎纸片，同样将组行成页的排列问题转化为旅行商问题进行求解，从 而完成整个文档的复原． 本文采用2013年全国大学生数学建模竞赛B题附件 3的数据(http：／w／ww ：m．edl1． cn／problem／2013／2013．htm1)作为研究样本，以此寻找规则碎片拼接 的一些方法和规律． 该数据是 由一个 A4大小的中文文档经碎纸机纵切和横切形成 11×19个规则的、大小 收稿 日期 ：2Ol3一ll～l5 作者简介 ：马俊明 (1992一)，男，广东惠州人．汕头大学数学系 2010级本科生； 通讯作者 ：李 健 (1985一)，男，博 ，讲师。研究方向：动力系统．数学建模．E-mail：lijian@stu．edun 基金项 目：汕头大学青年科研基金资助项 目(YR13001) 第 2期 马俊明等 ：基于文字特征的规则碎纸片 自动拼接 5 相 同的碎纸片得到．碎纸片是编号为 000—208的209个 bmp文件 1 规则碎片拼接原理 1．1 文档行分类 在所有样本碎纸片中，由中文排版格式要求可知，每个碎纸片中的文字方向都是沿 水平方向的．通过观察可知，每个碎纸片包含 2—3行文字，每行包含 1-2个文字．每个 文字行具有水平的上基线和下基线．下面基于文字行基线的信息确定碎纸片行分类准则． 准则一：如果丽个碎纸片中所有文字行基线的位置都相同，则这两个碎纸片位于同 一 行． 例如，图1中的000．bmp和 137．bmp，它们所有的文字行基线的位置都相同，故它 们位于同一行． 准则二：对于两个碎纸片，如果其中一个碎纸片的第一个文字行上基线的上方全是 空 白，除去这个空 白部分 ，其剩下部分的所有文字行基线的位置都与另一个碎纸片相 同，则这两个碎纸片位于同一行． 例如 ，在图2中，014．bmp第一个文字行上基线的上方全是空 白．除了其上方空 白 部分，014．bmp所有的文字行基线的位置都与 128．bmp相同，故它们位于同一行． 准则三：对于两