碎纸片的拼接复原

于龙洋　冯宇辰　张帆　张晓彤　郑智聪

摘 要：破碎文件拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用，本文将碎纸片拼接转化为基于边缘字迹断线识别法的图像拼接。图像拼接可以应用到计算机视觉、模式识别、生物医学等各个领域，故研究碎纸片拼接及其相关技术有着重要的意义。

针对问题，根据灰度图像的形成原理，列出提取每张图像两边缘的灰度矩阵G，对此矩阵每两列之间做Pearson相关系数分析，取每列相关系数的最大值即向量范数，反求出图像编号，由此建立按列拼接模型。中文拼接顺序表及其拼接图见表3、 图2，英文拼接顺序表及其拼接图见表4、图3，人工干预节点数为0。

关键词：灰度矩阵；Pearson相关系数；Best-First搜索算法；Q系数评价法

1 问题重述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：

1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。

2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。

3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。

2 问题分析

通常碎纸片复原方法一般分为两种，第一种方法是利用碎纸片的破碎边缘的曲线进行匹配，第二种方法则是利用边缘字迹断线识别的方法进行匹配。附件所给的碎纸片的边缘均为规则的直线，故采用第二种方法，也就是边缘字迹断线识别的方法。

2.1 问题

由于附件文件上的颜色只有黑白两色，我们考虑利用灰度图像的形成原理，用Matlab提取出各个碎纸片的灰度矩阵（i=0，1，…18），取每个碎纸条的灰度矩阵的第一列和最后一列，将它们按附件给出的图像顺序合并到同一个矩阵中。

用SPSS软件对该矩阵做Pearson相关系数分析，得到一个相关系数矩阵，该矩阵中的元素为每两列灰度值的相关系数，找出每一列的相关系数的最大值即向量范数，根据奇偶性与左右边缘的关系反求出碎纸片的序号，用Matlab将关联系数最大的两个碎纸片拼接在一起。

3 模型假设

1. 假设碎纸片拼接好后的文章是完整通顺的。

2. 假设灰度矩阵每列数据均服从正态分布。

3. 假设图像边缘规则，连接十分契合。

4. 假设人工干预节点连接时误差为0。

4 模型建立与求解

4.1 问题

1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。

4.1.1 按列拼接模型准备

1.灰度[1]

指黑白图像中点的颜色深度，范围一般从0到225，黑色为0，白色为225，故黑白图像也称为灰度图像，它可以量化为一个二维阵列，阵列的元素则为灰度值。

2.向量的无穷范数[2]

参考文献

[1] 司周奎，孙玺菁，数学建模算法与应用，北京：国防工业出版社，2011，13（1）：319-320

[2] 邢志栋，曹建荣，矩阵数值分析（第二版），陕西：科学技术出版社，2005，1（1）：2-3

[3] 刘震，吴广，丁维岱，张召明，SPSS统计分析与应用，北京：电子工业出版社，2010，7（1）：181-182

[4] 贾海燕，碎纸自动拼接关键技术研究，国防科技大学研究生论文，2005，4（5）：40-41