碎纸片的拼接复原.pdf

《碎纸片的拼接复原.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2第01335年卷12月第6期Journalo台f州T学aiz院ho学u报UniversityV01．35．No．6Dee．2013碎纸片的拼接复原王勇勇，赵锋，曹晨雅，李韶伟(台州学院数学与信息工程学院，浙江,16海317000)摘要：根据“文档文字单一，行高和行间距固定”的碎纸片文字的几何特征，建立数学模型，进而设计相应算法程序实现了自动化或半自动化地碎纸片的拼接和复原目的。关键词：最佳匹配；投影映射；行高中图分类号：029文献标识码：A文章编号：1672—3708(2013)06—0005—051引言破碎文件的拼接在司法物证复原、历史文献修

2、复以及军事情报获取等领域都有着重要的应用。然而，大量的纸质物证复原工作目前基本上都是以手工方式完成的，准确率较高，但效率很低。目前，德国等发达国家对破碎文件的自动修复技术已经进行了相当长的研究。而在国内，还没有类似研究成果问世。因此，通过设计相应的算法软件，开展对碎纸自动拼接技术的研究具有重要的现实意义。本文的目标是利用复原模型设计算法辅助的方法对碎纸机切碎的纸片进行拼接、复原。本文主要讨论以下问题：问题1．对于来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切)，建立碎纸片拼接复原模型和算法。问题2．设计既纵切又横切的碎纸片拼接复原模型和算法。问题

3、3．设计双面打印文件的碎纸片的拼接复原模型与算法。本文数据来源于2013年全国大学生数学建模竞赛的A题。2变量说明和名词解释二值化：由于本题中所有碎纸片都是黑白的，因此将图片中灰度值>200的像素点的灰度值赋值为0，即确定该像素点是白色的。将图片中灰度值<200的像素点的灰度值赋值为1，即确定该像素点是黑色的。最佳匹配：根据所有图片的左右两侧边缘像素形成2个列向量，元素逐个进行比较是否相同，一直进行到最后一对元素，找到匹配最好的一对边缘。匹配系数：对所有图片的两个边缘灰度值的列矩阵中的元素，进行逐个比较，相同记为1，否则记为0，取l的总数称为匹配

4、系数。人工干预：在程序实现最佳匹配过程中，可能出现一个对多个的情况，此时需要进行人工干预。行首(尾)图片：每一行的左(右)侧首张图片。收稿日期：2013—12—02基金项目：2013年台州学院校学生科研项目(13xs13)通讯作者简介：李韶伟(1979～)，男，浙江fJIl居人，讲师，硕：L，丰要从事数学建模指导E作。6台州学院学报第35卷找左边：根据纸张左侧空白的特点，查找碎片左侧空白像素点，从而确定行首图片。找右边：根据纸张右侧空白的特点，查找碎片右侧空白像素点，从而确定行尾图片。3问题分析与求解3．1问题一的算法设计问题一的数据量较大，仅考

5、虑纵向匹配，中英文的碎纸张拼接复原都可按以下步骤程序自动匹配完成：第一步：读取所有图片左、右两侧像素点的灰度值。第二步：将图片像素点的灰度值进行二值化处理得到像素。由图片的左、右两侧像素确定的左列矩阵Ill和右列矩阵I22。第三步：分别将图片左列矩阵Ill中的元素与分别于其余18个图片右列矩阵I22中的元素．进行逐个点比较，相同的记录为1，不同的记录为0，一直进行到最后一对元素。记录得到一个新的矩阵I31。同理将图片右列矩阵与其余18个图片进行匹配，从而确定匹配系数。第四步：根据第三步得到的匹配系数可以得到一个19x19的矩阵M。根据矩阵M中行向

6、量每个元素都为0可以确定行首图片。第五步：根据第四步确定的行首图片，通过矩阵M的元素(即各个图片间的匹配系数)确定剩余图片的顺序。从而，完成19个碎纸片的纵向拼接。3．2问题二算法设计3．2．1“行高”的定义1．中文字体“行高”的定义：纵向投影一张图片得到一列像素点的灰度值，将灰度值进行二值化处理，得后一个列向量L，根据以下流程，确定中文字体“行高”h的值：注：70为图片中文字距与行距按上述处理后，在列向量L中元素的个数L(i)为L列向量第i个元素。图l确定中文行高的算法流程图8台州学院学报第35卷拼接出l1行完整的文字图片。第五步：通过程序的运

7、行，可匹配出若干行碎块。加一次人工干预，可获得11行完整图片。第六步：根据纵向拼接得到的1l行的图片的进行横向拼接。由于图片上下边缘的像素点为可能0，所以在进行横向拼接时，需要再次人工干预。3．3问题三的算法设计“二维行高”的定义：设a面的“行高”为X，b面的“行高”为Y。第一步：提取所有图片每行像素点的灰度值并进行二值化处理。第二步：用matlab软件计算依次对每张图片进行“找左边”，同时将提取出来的这些图片的反面“找右边”，如O03a、O09b等图片，并比较它们找的左边与右边是否相等；若提取出来的图片的a、b面的边相等，那么，可以确定满足找左

8、边的图片作为完整图片的最左侧，相应的，满足找右边的图片可以作为完整图片背面的最右侧；最终的到11张“行首图片”。第三步：从第二步提取出来