碎纸片拼接复原(国一).doc

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

1、基于分治算法碎纸片的拼接复原模型摘要本文针对不同切割方式碎纸片的拼接问题，通过对图像数字化处理得到灰度矩阵，建立了复原模型并得到复原后的图像。针对单面仅纵切碎纸片的拼接问题，根据完整文件最左边部分无文字的特点，运用matlab编程可确定出第一碎纸片。随后，根据贪婪算法的思想，以确定位置的碎纸片与剩余未拼接碎纸片相邻边缘灰度值的平方欧氏距离最短为目标函数，可逐步求得碎纸片的拼接顺序,进而将其复原.中文碎纸片顺序为：8、14、12、15、3、10、2、16、1、4、5、9、13、18、11、7、17、0、6；英文碎纸片顺序为：3、6、2、7、15、18、

2、11、0、5、1、9、13、10、8、12、14、17、16、4。本问碎纸片拼接过程没有人工干预，实现了全自动化的拼接。对于既横切又纵切碎纸片拼接问题，本问采用分治算法的思想，先对中、英文碎纸片分别层次聚类分析，将最可能位于同一行的碎纸片归为同一类，其中中文碎纸片分为11类，英文碎纸片分为10类；再对分类后的碎纸片使用编程加人工干预的半自动拼接方式，得到11块仅横切的碎纸片块；最终对得到的11块仅横切的碎纸片块进行类间拼接，实现文件的复原。中文碎纸片第一列顺序为：49、61、168、38、71、14、94、125、29、7、89；英文碎纸片第一列顺序

3、为：191、201、86、19、159、20、208、70、132、171、81。此问中有两次人工干预的过程，第一次位于类拼接处，第二次位于类间拼接处。中文文件总共干预了33块，英文文件总共干预了40块。考虑双面碎纸片拼接问题时，本问延续了分治算法的思想。由于每碎纸片含有正反两面，在聚类分析时，可将正反两面的灰度值相加为一列特征值作为它们是否可能位于同一行的依据，进而将双面碎纸片分为9类。再对这9类碎纸片使用编程加人工干预的半自动拼接方式，得到22块仅横切的碎纸片块；最终对这22块仅横切的碎纸片块进行类间拼接，实现文件的复原。复原后文件第1面第一列顺

4、序为：136a、5b、143a、83b、90b、13b、35b、172b、105b、9a、54b；复原后文件第2面碎纸片第一列顺序为：78b、89a、186b、199b、88b、114a、146a、165b、3b、23b、99a。此问中有两次人工干预的过程，第一次位于类拼接处，第二次位于类间拼接处。【关键词】：碎纸片复原贪婪算法平方欧氏距离分治算法层次聚类分析一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间

5、完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下三个问题：问题一：对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达，表格为复原后碎片序号。问题二：对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出

6、干预方式及干预的时间节点。复原结果表达要求同上。问题三：上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、问题分析本文针对的是形状相似碎纸片的拼接问题，需提出相应的拼接模型与算法并对给定的碎纸片进行复原。常规文档碎纸片计算机拼接方法一般利用碎片边缘的尖点特征、尖角特征、面积特征等几何特征，搜索与之匹配的相邻碎纸片并进行拼接，根据题意可知，本文所研究

7、的碎纸片形状相似，这种基于边界几何特征的拼接方法并不适用于边缘形状相似的碎纸片。碎纸片拼接时如果只利用碎片的边界特征，拼接效果并不理想。本文在实行拼接过程时，不但考虑了待拼接碎纸片边缘是否匹配，还考虑了碎片字迹断线与文字是否匹配【3】。问题一是解决来自同一页且被纵向切断的碎纸片拼接问题。该问题本质上属于碎纸片组合优化问题。如何实现碎纸片的最优组合成为本问以及本文的一个难点。可考虑碎纸片文字的特点。由于大多数文字文档的文字行方向和表格线方向平行且单一，如果碎片的文字行或表格在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行或表

8、格，凭此特征可以很容易地从形状相似的多碎片中挑选出相邻碎片。因文字行或表格线的高度特征、间距特征的识别比字迹