残缺碎纸片半自动可视化拼接算法.pdf

《残缺碎纸片半自动可视化拼接算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内江师范学院学报第3o卷第6期·18·J0URNAIoFNEIJIANGNORMALUNlVERSITYNo．6Vo1．30残缺碎纸片半自动可视化拼接算法牟廉明。，罗开宝，陈琳，罗仕明(1．内江师范学院数学与信息科学学院，四川内江641199；2．数据恢复四川省重点实验室，四川内江641199)摘要：针对在实际应用中往往存在部分残缺碎纸片的情况，首先根据碎纸片的边缘特征和文档的结构特征设计了综合匹配度计算方法；然后根据贪心原则设计了一种向四周扩展和绕回的有效拼接算法，并根据碎纸片拼接特点制定了人工干预准则，开发了可视化的人机交互拼接系统；最后通过比较实

2、验验证该方法的有效性，有效地解决了残缺碎纸片的拼接复原问题．关键词：残缺碎纸片；边缘特征；结构特征；匹配度；贪心算法DOI：10．13603／j．cnki．51—1621／z．2015．06．004中图分类号：TP301文献标志码：A文章编号：1671—1785(2015)06—0018一O6碎纸片的拼接在破碎文件恢复、司法物证复原、回的方式进行拼接复原，有效地解决了存在残缺碎历史文献修复以及军事、商业情报获取等领域都有纸片的问题．第三，设计了人工干预准则和可视化实着重要的应用r]]．目前对碎纸片拼接的研究主要有现方法．最后，利用碎纸片的拼接复原数据_

3、g]进行实以下方法：第一种是针对碎纸片形状不规则的情况：验，验证了该方法解决残缺碎纸片拼接复原问题的通过提取碎纸片的轮廓，利用外形特征进行拼有效性．接l2]．第二种是针对碎纸片形状规则的情况：通过1碎纸片匹配度计算方法提取并利用碎纸片的文字特征进行拼接刮；以及通过聚类l7先按行拼接再按列拼接，将二维拼接问题1．1基于碎纸片边缘特征的匹配度计算方法转化为一维拼接来解决．以上这些方法对无残缺的根据碎纸片的边缘特征，采用碎纸片边缘像素规范的碎纸片拼接具有一定效果，但在实际应用中的灰度值矩阵和二值化L1叩后的0—1矩阵共同刻画往往存在部分残缺和丢失的碎纸片，特

4、别是对于多碎纸片之间的匹配关系．处残缺的复杂文档无能为力．1．1．1曼哈顿距离针对这类边缘形状规则、存在部分残缺和丢失首先对碎片进行预处理，提取每张碎片灰度矩的碎纸片拼接复原问题，设计了向四周扩散和绕回阵的上、下、左、右边缘向量．记两碎片边缘向量为：的方式来解决．主要做了三方面的工作：第一，通过X一(zl，2，⋯，z)，Y一(1，Y2，⋯，Y)，其中，碎纸片的文档结构特征来衡量两碎片之间的结构匹Y∈I-o，255]，则两向量的曼哈顿距离【1d(x，y)配度，通过边缘像素匹配和黑点匹配来确定边缘匹为配度，并综合两种匹配度来提高匹配效果．第二，设d(x，y

5、)一∑—YI．计了贪心拼接算法，对碎纸片采取向四周扩散和绕收稿日期：2015—04—25基金项目：四川省科技厅应用基础研究项目(2015JY0120)，四川省教育厅自然科学重点项目(13ZAOO08)，内江师范学院自然科学重点项目(12NJZO3)，教育部大学生创新创业训练计划项目(X2o14o6)作者简介：牟廉明(1971一)，男，重庆万州人，内江师范学院教授，硕士．研究方向：计算智能、机器学习与数据挖掘·20·内江师范学院学报第3O卷第6期wh与第J张碎纸片的下边缘黑色区域的字体高度外扩展的碎片编号和方向时，利用已拼接碎片且可之和，与固定字高的相对

6、偏差为继续扩展的边缘黑点所占百分比最大的边缘来确定△一±×1oo下一次拼接．，贪心原则2：综合匹配度最大优先．在寻找匹配第i张碎纸片的上边缘白色区域的高度rs与第J的碎片时，利用两碎纸片之间综合匹配度来确定，即张碎纸片的下边缘白色区域的高度rsf之和，与固选择与之综合匹配度最大的碎片进行拼接．定行间距的相对偏差为在拼接过程中，首先利用贪心原则1确定待匹Arso一上±二l×100配碎片的位置和方向．然后，利用贪心原则2确定能，与之匹配的碎片．因此，拼接时是可从上下左右四个其中，相对偏差的数值越小，表示第i，J两张碎片上方向逐步向四周扩展拼接．下能拼接的可

7、能性越大．1．5扩展绕回拼接算法设计1．2．3中文文档结构匹配度的计算在实际应用中，碎片残缺有两种情况：一是缺失左右拼接时，使用字宽和字间距的相对偏差计一整块碎片；二是缺失一块碎片的某一部分(如图2算左右结构匹配度△s，即字高和行间距的相对所示)．偏差的平均值．△s一(Awb-I-Aws)／2．同理，上下拼接时，使用字高和行间距的相对偏差计算上下结构匹配度△S，即字高和行间距的相对偏差的平均值．A缺—，失▲A△S一(Awh+Ars)／2缺失其中，结构匹配度的数值越小，表示第i，J两张碎片能拼接的可能性越大．1．3综合匹配度若拼接后的内容中形成的是字，则

8、需要判断形图2碎片残缺的情况成的字是否满足字高和字宽的标准；若形成的是空1．5．1设计思想白区