碎纸片的拼接复原摘要本文利用Manhattan距离，聚类分析，图像处理等方法解决了碎纸片的拼接复原问题。

由于碎纸机产生的碎纸片是边缘规则且等大的矩形，此时碎纸片拼接方法就不能利用碎片边缘的尖角特征等基于边界几何特征的拼接方法，而要利用碎片内的字迹断线或碎片内的文字位置搜索与之匹配的相邻碎纸片。

拼接碎片前利用数学软件MATLAB软件对碎片图像进行数据化处理，得到对应的像素矩阵，后设置阈值对像素矩阵进行二值化处理，得到相应的0-1矩阵。

下面分别对三个问题的解决方法和算法实现做简单的阐述：问题一，分别对附件1和附件2的碎片数据进行处理得到相应的0-1矩阵，依次计算某个0-1矩阵最右边一列组成向量与其他所有0-1矩阵的最左边向量的Manhattan距离，可以得到某个最小距离值、说明最小距离值对应的碎片是可与基准碎片拼接的，最终得到碎片拼接完整的图像。

问题二，同样对于附件3和附件4中的碎片数据进行处理得到相应的数值矩阵，并计算得到每个碎片顶部空白高度和文字高度，即指每行像素点都为255的行数、一行中存在像素点为非255的行数，根据空白高度和文字高度对碎片进行聚类分类，聚类阀值取3像素，得到11组像素矩阵，进而得到11类可能在同一行的碎片类。

其中对附件4中的英文的处理中，我们还采用水平像素投影累积的方法，进一步分类出可能在同一行的碎片类。

用问题一的方法，计算Manhattan 距离可以对每一类碎片按次序排列好，得到11行已经排列好的碎片，再应用曼哈顿距离在竖直方向上进行聚合得到完整的图像。

问题三，首先，对于附件5中的碎片数据我们采用正反相接，本文将b面最左边的一列像素拼接到a面最右边的一列像素的下面，构成360×1的向量，再把其他的碎片采用相同的办法得到360×1的向量，再用问题一的方法，计算出各碎片之间的Manhattan距离。

其次，根据每个碎片顶部的空白高度或者文字高度对碎片进行区间分类，得到22组矩阵，然后应用曼哈顿距离将得到的22组矩阵聚成两类，每类各包含两面的11组矩阵，最后利用Manhattan距离在竖直方向上进行聚合得到完整的图像。

本文最后，我们根据算法的效率实现进行了改进和优化，实现算法的移植性、灵活性、运行效率等得以提升。

关键词：曼哈顿距离，聚类分析，二值化处理一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。

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

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

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

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

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

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

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

复原结果表达要求同上。

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

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

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

二、问题分析我们从附件中的碎片数据可知由于碎纸机产生的碎纸片边缘是规则的，此时碎纸片计算机拼接方法就不能利用碎片边缘的尖点特征、尖角特征、面积特征等基于边界几何特征的拼接方法，而要利用碎片内的字迹断线或碎片内的文字内容是否匹配搜索与之匹配的相邻碎纸片并进行拼接。

首先，我们对碎片内图像进行数据化处理，得到对应的像素值矩阵；然后，我们设置阈值对像素值矩阵进行二值化处理得到相应的数值矩阵；最后，由于曼哈顿距离公式计算快、数值小，数值矩阵与数值矩阵之间应用最小曼哈顿距离对碎纸片进行拼接复原。

问题一中碎纸机破碎纸片只有纵切，每页纸被切为19条碎片，经过处理可以得到19个数值矩阵。

对于每个数值矩阵，我们依次取出最左边一列从上至下各格的值组成一个向量，同样我们依次取出最右边一列从上至下各格的值组成一个向量。

计算出每一数值矩阵的左边向量与所有非同源数值矩阵的右边向量的曼哈顿距离，再将得到的距离值进行排序，当某个距离值最小时、说明相应的左边向量与右边向量的匹配率最大，则该距离对应的左、右边认为是可拼接的。

若得到的最小距离值不止一个，则此时需要进行人工干预。

问题二是对碎纸机既纵切又横切的情形进行讨论，比问题一多了横切条件，此时每页纸被切为209个碎片。

首先，我们利用文件最左边碎片与最上面碎片的特殊性对这209个碎片进行聚类，得到两类特殊的碎片，分别是文件最左边一列碎片和最上面一行碎片，然后类似于问题一的处理方法，应用最小曼哈顿距离对每一类碎片按正确顺序拼接，此后对其余碎片再应用最小曼哈顿距离逐一进行拼接，直至剩余所有的碎片都拼接上。

问题三中，题目要求考虑双面打印文件的碎纸拼接复原问题的解决方案，此时每页纸虽然也是被切为209个碎片，但每个碎片却有正反两面，因此经过处理得到418个数值矩阵，，此时我们分别对每一面各自进行类似问题一的处理，然后综合每一面的聚类情况再应用最小曼哈顿距离对双面碎纸片进行拼接复原。

三、模型假设1. 假设碎纸机破碎纸片（纵切或横切）得到的碎纸片是规则且边缘是整齐的等大的矩形；2.假设我们对文档碎纸片拼接复原不考虑碎片边缘的尖点特征、尖角特征、面积特征等基于边界几何特征；3.假设附件中给出的所有中、英文文件中的文字排版是按标准格式排版的。

4.假设附件中给出的所有中、英文字符都是统一格式，且内容为普通文章。

5.1 问题一（曼哈顿距离）➢ 模型一的建立题目要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切）建立碎纸片拼接复原模型和算法，并且要对中、英文各一页文件的碎片数据分别进行拼接复原。

首先，我们利用数学软件MATLAB 软件将19条碎片数据化，得到19个像素值矩阵，像素值的变化范围是从0变化到255，此时我们设置127τ=为阈值对像素值矩阵进行二值化处理，当矩阵某位置像素值小于等于τ时，则将对应位置的数值设为0；当矩阵某位置像素值大于τ时，则将对应位置的数值设为127。

这样我们就得到19个二值化了的数值矩阵iA ，对于每个数值矩阵iA ，我们依次取出最左边一列从上至下各格的值组成一个向量，记为iX ，同样的我们依次取出最右边一列从上至下各格的值组成一个向量，记为i Y 。

计算出每一数值矩阵的左边向量与所有非同源数值矩阵的右边向量的曼哈顿距离(,)i j d X Y 。

➢ 模型一的求解 对于得到的向量12(,,...,)(1,2,...,)Ti i i ik X x x x k m ==和向量12(,,...,)(1,2,...,)Ti i i ik Y y y y k n ==，两向量的曼哈顿距离为1(,)||(,1,2,...,)ni j ik jk k d X Y x y i j m i j ==-=≠∑且。

可求出附件1碎片与碎片之间的曼哈顿距离，如下表所示。

表1 附件1碎片与碎片间的曼哈顿距离从而可得到附件1碎片序号按复原后顺序如下表所示。

表2 附件1碎片序号复原后顺序附件1碎片复原图片如附录中图8.1所示。

同法可求出附件2碎片与碎片之间的曼哈顿距离，如下表所示。

表3 附件2碎片与碎片间的曼哈顿距离从而可得到附件2碎片序号按复原后顺序如下表所示。

附件2碎片复原图片如附录中图8.2所示。

问题一人工干预情况如下表所示。

5.2 问题二（Manhattan 距离）➢ 模型二的建立在中文文件中，两个连续的汉字中间的空白间隔所占像素宽度与其左边或者右边的汉字所占像素宽度的比值最大的约为213，则对于每一行文字，碎纸机纵切未切到文字的概率为213，对于每两行文字碎纸机纵切未切到文字的概率为4169，而对于每三行文字碎纸机纵切未切到文字的概率更小，可以忽略不计，所以对于总共209个碎片，每个碎片上面的文字至少有两行（碎片上不完整的一行也算一行），所以出现某个碎片上面的文字完全没被碎纸机切割到（即文字完整无缺）的概率至多为4169，我们把这样的碎片称之为干扰碎片。

我们知道，整篇文件的最上面一行字的上边缘是空白的，我们可以利用此特殊性对209个碎纸片进行聚类，可以得到一个特殊的类，即碎纸片上边缘为空白的类，此类碎纸片个数大于等于11；出现个数大于11的情形即为混入上面提到的干扰碎片，此概率最大不超过4169，可知此类碎纸片应该拼接在文件最上面一行，应用最小曼哈顿距离对此类碎片按正确顺序拼接。

同理可聚类出另一个特殊的类，即碎纸片左边缘为空白、拼接在文件最左边一列的类，并且也应用最小曼哈顿距离对此类碎片按正确顺序拼接。

然后以此拼接好的第一行和第一列碎片为基准，再应用最小曼哈顿距离拼接其余剩下的碎片，最后拼接复原出原中文文件。

在英文文件中，一个英文单词中两个连续的英文字母中间的空白间隔所占像素宽度与其左边或者右边的英文字母所占像素宽度的比值最大的约为111，则对于每一行英文单词，碎纸机纵切未切到英文单词的概率为111，对于每两行英文单词碎纸机纵切未切到英文单词的概率为1121，而对于每三行英文单词碎纸机纵切未切到英文单词的概率为，然后同上述中文文件的分析过程可知，此时对拼接在文件最左边一列归类时混入上面提到的干扰碎片的概率最大不超过，最后拼接复原出原英文文件。

➢模型二的求解我们利用SPSS软件根据每个碎片顶部空白高度或者文字高度的不同，应用聚类分析方法将碎片聚成11类，结果如下图所示。

图1 根据碎片顶部文字高度聚类图2 根据碎片顶部空白高度聚类结合上面的聚类图，可得出附件3的乱序矩阵，如下表所示。

表6 附件3的乱序矩阵49 22 129 178 118 143 188 192 57 141 91 190 28 186 2 54 11 95 65 61 79 116 78 72 20 69 52 163 177 36 99 96 19 67 63 162 131 6 168 179 1 30 23 142 191 87 147 62 76 86 195 18 26 120 100 41 50 38 167 74 46 103 148 88 35 9 8 24 193 161 105 189 25 130 122 81 71 205 27 200 60 85 15 33 156 170 198 132 17 202 152 83 165 133 80 14 115 159 128 199 12 107 176 82 160 73 31 51 203 169 3 135 39 134 94 58 90 149 77 42 34 112 144 136 124 84 164 97 47 127 121 183 43 125 13 187 173 139 66 150 197 182 16 106 181 145 109 21 110 184 157 204 29 10 104 172 55 48 171 5 98 37 206 59 92 201 64 44 180 111 757 0 93 32 56 175 153 166 196 137 45 208 174 68 158 138 53 70 126 89 151 114 140 102 207 155 101 146 194 119 4 117 40 123 108 154 185 113同样的方法可得出附件4的乱序矩阵，如下表所示。