碎纸片的拼接复原摘要本题旨在解决碎纸片拼接问题。

在本题中我们使用 MATLAB软件，首先对图像进行数据化处理和标准化处理。

一：只有纵切情况，且所有的切口都切到了字，建立差和法检验模型，应用枚举法，用MATLAB计算任意两张碎纸片灰度矩阵中最左、最右列灰度值的差方和，将差方和最小的两张碎纸片拼接在一起.中间不经过人工干预。

最后得到中英文碎纸片的排列顺序，从左到右依次为：中文：08,14,12,15,03,10,02,16,01,04,05,09,13,18,11,07,17,11,06;英文：03,06,02,7,15,18,11,00,05,01,09，13,10,08,12,14,17,16,04。

二：首先对中英文碎纸片分别提取行间距相同和英文字符三线分割后空白带宽相同的特征，根据这些特征我们初步筛选出可能处于同一“行”的碎纸片，为了不与原文中书写的字的“行”发生误会，我们称其为组，然后分别依次进行“组内调整和组间拼接”工作。

中文文件拼接复原过程中采用差方法计算出关联度，然后利用改进的匈牙利算法选出全局中的局部最佳拼接，再结合人工干预，实现组内拼接和组间拼接；英文文件拼接复原与中文的略有不同，首先分析图像选出可能成为最左边的碎纸片，采用以相关系数法，，从而从左向右拼接，最后完成拼接复原。

下面分别选取中英文碎纸片拼接复原后的第一行碎纸片的序号作为样品。

按照从左到右的顺序：中文：49，54，65，143，186，2，57，192,178,118,190,95,11,22,129,28,91,188,141；英文：191，75,11，154,190,184,2,104,180,64,106,4,149,32,204,65,39,67,147。

三：考虑到问题二中对英文碎纸片的拼接所提取的特征在大量数据时会产生分组效果不佳的问题，采用新的方法重新提取行间距特征：靠近碎片底端最近的一行中完整字母集中分布的最低点到碎纸片底端的距离。

并在求解模型基础上通过定义匹配错误率。

建立利用双面打印文件的其中一面作为拼接面，另一面作为验证面对分组结果交叉检验的拼接检验交互模型，从而有效完成并验证拼接双面打印文件的拼接复原任务。

关键字：差方法匈牙利算法相关系数行间距特征拼接检验交互模型1一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

当碎片数量巨大，人工拼接很难在短时间内完成任务。

随着计算机机术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。

1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件 1、附件 2给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果以图片形式及表格形式表达。

2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果表达要求同上。

3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。

附件 5给出的是一页英文印刷文字双面打印文件的碎片数据。

请尝试设计相应的碎纸片拼接复原模型与算法，并就附件 5的碎片数据给出拼接复原结果，结果表达要求同上。

二、问题分析本题属于图像处理类问题。

可以采用 MATLAB工具处理图像的灰度矩阵或二值矩阵。

问题一，问题要求我们复原碎纸机仅在纵切情况下破碎的纸片，分析附件中所给的碎纸片图像，发现经纵切后，所有的碎纸片纵切都有被切开的字，碎片没有只有空白的接口，而且碎纸片复原后上、下、左、右边框为白色。

于是可以先找出所有纵切碎片中左边框或右边框为空白碎片的个数。

在确立左边框后采用差和法依据该碎片右边界与其他碎片左边界的相关程度进行匹配拼接。

问题二，与问题一不同，问题二中既有纵切又有横切，常规的差和法不能满足碎片多，相关程度比较小的问题二的求解要求。

此外，中英文的特征差别在碎片变小时也会逐渐突出，因此，文字特征提取、参考点的选取以及如何建立模型计算图片边界相似程度和求解至关重要。

由于碎片中字与字之间有固定间距，可以采用合理的方法构建间距特征提取模型确定各行包括的碎片，对于行内 19 个碎片利用相关性检测得出表征碎片左右边界的相关系数大小是一种有效解决问题的方法。

匈牙利算法是解决图论问题中的常用算法，此处对匈牙利算法加以改进可以方便的调整各行内碎片的连接形式。

在确定各行碎片连接形式后再考虑上下边框、段间间距等因素进行行间的排列。

问题三，在第二问的基础上要求我们实现双面打印文件碎纸片的拼接复原，考虑到问题二中针对英文碎纸片的拼接所提取的特征，沿用问题二的求解思路，将英文碎纸片中的字母分割成三格，计算各格之间的比例关系即像素长度，从而确定英文字体的行间距。

据此特征检测碎纸片之间的匹配程度，并加以拼接，我们考虑利用双面打印文件的其中一面作为拼接面，另一面作为验证面完成复原工作及对复原结果的检验。

三、基本假设1、假设碎片是理想的，没有遗失和磨损2、假设图像数值化像素采样误差可以忽略3、假设正反面文字是对齐的4、假设对于同一个文件行间距是固定的5、假设边距大于段间距，段间距大于行间距6、假设人工干预不会导致错误的结果四、符号说明D 最佳匹配值Xj每行中某个碎纸片灰度矩阵的最右列yj每行中某个碎纸片灰度矩阵的最左列mi各行中第 i 个碎纸片二值矩阵中全为零的行pj每行某碎纸片二值矩阵中第 j 个行的所有值N 误差度量值d 左边距，单位：像素W 匹配准确率K 一次分组后拼接面与检验面重复的碎纸片个数V 一次分组后拼接面与检验面包含的碎纸片个数五、图像的预处理5.1数值化由于目前的计算机只能处理数字信号，我们得到的照片，图纸等原始信息都是连续的模拟信号，必须将图像进行预处理，即把连续的图像信息转化为数字形式。

可以把图像看作是一个连续变化的函数，这就要经过数字化的采样与量化。

图像采样就是按照图像空间的坐标测量该位置上像素的灰度值。

方法如下：对连续图像f(ݔ, ݔ)进行等间隔采样在(ݔ, ݔ)平面上，将图像分成均匀的小网格，每个小网格的位置可以用整数坐标表示，于是采样值就对应了这个位置上网格的灰度值。

若采样结果每行像素为 M个，每列像素为 N个，则整幅图像对应一个 M*N 数字矩阵。

这样就获得了数字图像中关于像素的两个属性：位置和灰度。

位置有采样点的两个坐标确定，也就对应了网格的行和列，而灰度表明了该像素的明暗程度。

应用 MATLAB 可以自然的得到如下形式的数字矩阵：g(1,1) ⋯g(1, N)g = [ ⋮⋱⋮]g(, 1) ⋯g(M,N)矩阵中的元素称为像素，每个像素都有x 和y 两个坐标，表示其在图像中的位置，其值称为灰度值，对应原始模拟图像在该点处的亮度。

量化后的灰度值代表了相应的色彩浓淡程度，本题中我们使用 256 色灰度等级，“0”表示纯黑色，“255”表示纯白色，中间的整数数字从小到大表示由黑到白的过渡色。

5.2标准化将图像数值化后的灰度值采用 256 灰度等级，“0”表示纯黑色，“255”表示纯白色。

由于图像在获取中灰度值将受影响，故我们需要对图像进行标准化。

六、问题一6.1模型的建立1.灰度相关匹配理论依据：如果是一个整体分裂成的两个碎片，那么两个碎片裂口对应的部分的颜(对灰度图像而言，就是灰度信息)会有很强的相关性，这是碎片间除轮廓信息外最重要的信息之一。

灰度矩距离最短的两条边之间的相似性最高，相似度最大的两边可以作为匹配边，同时排除其他干扰匹配对。

问题一中我们采用如下差方和公式：MD = min ∑(xj−yj )2j=1其中ݔ௝表示单个碎纸片图像的灰度矩阵的最右列，ݔ௝表示其余任意一个碎纸片图像的灰度矩阵中的最左列，D为最佳匹配值。

2.模型流程图分析附件中所给的碎纸片图像，发现经纵切后，所有的碎纸片纵切都有被切开的文字，碎片没有只有空白相接的接口，而且碎纸片复原后上、下、左、右边框为白色，于是可以根据灰度值的大小判断出纵切碎片中左边框和右边框。

如在确立左边框后采用差和法，依据该碎片右边界与其他碎片左边界的相关程度进行匹配拼接。

可建立如下的模型流程图：6.2模型的求解及结果1.求解过程第一步：图像预处理，应用 MATLAB 软件将碎纸片图像转变为 19 个 1980*72 灰度矩阵。

矩阵中元素值为 0 至 255，代表由黑到白的颜色变化，其中，“0”表示纯黑色，“255”表示纯白色。

第二步：取出每个灰度矩阵的最左边一列，判断该列元素值是否全为 255，若其值全为 255，即其最左边全为空白，则说明此碎纸片应在原文件的最左边。

第三步：以上述碎纸片的右边界为依据，根据如下公式计算其他碎纸片左边界与之的最小差方和 D1980D = min ∑ (xj−yj)2j=1得到其排列顺序，从左到右依次为8，14，12，15，03，10，02，16，01，04，05，09，13，18，11，07，17，00，06。

由于在仅有纵切情况下中英文打印文件字体特征基本相同，可以采用相同的采取方法，因此此方法也同样适用于处理附件 2 中的英文文件碎纸片。

2.求解结果表 1：中文碎片复原顺序表格：08 14 12 15 03 10 02 16 01 04 05 09 13 18 11 07 17 00 06表 2：英文碎片复原顺序表格03 06 02 07 15 18 11 00 05 01 09 13 10 08 12 14 17 16 04图 1，中文拼接复原图片图 2，英文拼接复原图片6.3模型的结果分析1. 准确率因为所给的碎片是一列一列的，所以我们只需要验证第一行是对的就可以说明拼接结果的正确的。

对于中文碎片拼接后第一行为“城上层楼叠巘。

城下清淮古汴。

举手揖吴云，人与暮天俱远。

魂断。

”出自宋代大词人苏轼的《如梦令●题淮山楼》，根据内容判断拼接是正确的。

对于英文碎片拼接后通过阅读其内容，可以确定拼接是正确的。

所以，对于在这一问中我们建立的模型是准确可行的。

2.不需人工干预的原因分析(1)文件仅纵切，且均切割到文字，所以各列有较大的相关性，匹配成功率较高。

(2)最左边为空白的碎纸片只有一个，且容易确定。

(3)匹配过程中最小差方和 D可唯一确定。

七、问题二7.1中文文件碎纸片的拼接复原7.1.1问题分析问题二，与问题一不同，问题二中既有纵切又有横切，常规的逐个比对不能满足碎片多，相关程度比较小的问题二的求解要求。

因此，文字特征提取、参考点的选取以及如何建立模型计算图片边界相似程度和求解至关重要。