资源描述：
《碎纸片拼接问题(2013B)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、碎纸片的拼接复原1、问题介绍2、建模分析3、总结一、问题介绍：碎纸片的拼接复原（2013B题）破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干
2、预的时间节点。复原结果以图片形式及表格形式表达。附附件件122.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。附件3附件4二、建模分析（1）审题：找出关键语句目标：开
3、发碎纸片的自动拼接技术，以提高拼接复原效率。任务：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法。3.双面打印文件的碎纸片拼接复原问题。尝试设计相应的碎纸片拼接复原模型与算法。（2）主要任务•如何拼接复原一组碎纸片？•怎样自动完成拼接？（1）如何拼接完成一组碎纸片？初步分析：将所有的纸片都放在正确的位置上。位置：（1）如何描述一张纸片的位置？（2）如何判断一张纸片应该在哪个位置？效果：如何衡量一个拼接方案的效果？
4、纸片位置的表示：已知一张纸被切割成了M行、N列，则每张纸片可用其所在的行、列编号来表示其位置。•将纸片依次编号为1,2，……，MN，则可令,1第k张纸片放在第i行第j列xi,j,k,0否则i,2,1,M;j,2,1,N;k,2,1,MN效果：如何衡量一个拼接方案的效果？分析：如果所有纸片都正确拼接了，那么应该使得和其有关的某些指标达到最优。问题：构造什么样的指标？可能的方案：（1）整体的文字拼接正确度；不易衡量。（2）纸片两两之间的拼接正确度。•如何计算纸片两两之间的拼接正确度？分析：假设纸片i和j拼接在一起，i左j右，则应该可以计算出一个相关的正确度指标。怎
5、么计算？•利用什么信息计算？利用Matlab软件读取碎片，生成相对应的灰度值数字矩阵A。i怎么利用这些信息？1）只利用纸片的边缘信息。2）利用整张纸片的信息。分析：显然，能从图片中找到的信息越多，计算可能就越准确。但是从中能找到哪些信息呢？例：行距、中心位置、文字所在行……差异度指标：令ci,j表示碎片i和j左右拼接（i左j右）的差异度指标值，令di,j表示碎片i和j上下拼接（i上j下）的差异度指标值。如何确定碎纸片的位置？方法一：一次性确定所有碎纸片的位置。方法二：分组确定碎纸片的位置。方法三：逐一确定碎纸片的位置。方法一：一次性确定所有碎纸片的位置。目标函数：所有碎片的左右
6、和上下差异度指标值之和。MN1MNMNminzck,lxi,j,kxi,j,1li1j11,kl1lkM1NMNMNdk,lxi,j,kxi,1,lji111,jkl1lk约束条件：（1）每个碎片只能放在一个位置上。MNxi,j,k,1k,2,1,MNi11j（2）每个位置上也只能放置一张碎片。MNxi,j,k,1i,2,1,M;j,2,1,Nk1数学模型：MN1MNMNminzck,lxi,j,kxi,j,1li1j11,kl1lkM1NMNMNdk,l
7、xi,j,kxi,1,lji111,jkl1lkMNs.t.xi,j,k,1k,2,1,MNi11jMNxi,j,k,1i,2,1,M;j,2,1,Nk1缺点：•整数规划问题不易求解；规模增大，计算量指数增加。•整体效果依赖于差异度指标，容易出错。方法二：分组确定碎纸片的位置。基本思路：三步走，分行，行内排序，行间排序。第一步：分行方法1：直接利用行距信息分组。普遍做法，精度略差（尤其是英文），成功率80%左右，技术含量不足。方法2：聚类
