碎纸片的拼接复原-2013高教社杯全国大学生数学建模竞赛B题论文 下载本文

d(Xi,Yj)??|xik?yjk|k?1n(i,j?1,2,...,m且i?j)。可求出附件1碎片与碎片

之间的曼哈顿距离,如下表所示。

表1 附件1碎片与碎片间的曼哈顿距离

编号 0 1 2 3 10 4 5 5 9 113 6 7 8 17 8 14 9 13 10 11 2 7 12 15 34 13 18 77 14 12 78 15 3 97 16 1 17 0 18 11 4 16 编号 6 距离 102 117 48

128 81 0 159 112 120 82 84 124 102 105 从而可得到附件1碎片序号按复原后顺序如下表所示。

表2 附件1碎片序号复原后顺序

8 14 12 15 3 10 2 16 1 4 5 9 13 18 11 7 17 0 6 附件1碎片复原图片如附录中图8.1所示。

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

表3 附件2碎片与碎片间的曼哈顿距离

编号 编号 距离

从而可得到附件2碎片序号按复原后顺序如下表所示。

表4 附件2碎片序号复原后顺序

0 5 1 9 2 7 3 6 4 5 3 1 6 2 7 15 8 9 10 11 12 13 8 0 14 10 14 17 15 16 17 18 18 4 16 11 12 13 96 65 82 102 0 71 67 120 87 128 82 54 75 133 107 54 93 52 90 3 6 2 7 15 18 11 0 5 1 9 13 10 8 12 14 17 16 4 附件2碎片复原图片如附录中图8.2所示。 问题一人工干预情况如下表所示。

表5 问题一人工干预情况 人工干预 图像 干预时间 干预方式 无 无 干预次数 附件1图像 无 附件2图像 无

0 0 5.2 问题二(Manhattan距离)

? 模型二的建立

在中文文件中,两个连续的汉字中间的空白间隔所占像素宽度与其左边或者

5

2右边的汉字所占像素宽度的比值最大的约为13,则对于每一行文字,碎纸机纵2切未切到文字的概率为13,对于每两行文字碎纸机纵切未切到文字的概率为

4169,而对于每三行文字碎纸机纵切未切到文字的概率更小,可以忽略不计,所

以对于总共209个碎片,每个碎片上面的文字至少有两行(碎片上不完整的一行也算一行),所以出现某个碎片上面的文字完全没被碎纸机切割到(即文字完整

4无缺)的概率至多为169,我们把这样的碎片称之为干扰碎片。

我们知道,整篇文件的最上面一行字的上边缘是空白的,我们可以利用此特殊性对209个碎纸片进行聚类,可以得到一个特殊的类,即碎纸片上边缘为空白的类,此类碎纸片个数大于等于11;出现个数大于11的情形即为混入上面提到

4的干扰碎片,此概率最大不超过169,可知此类碎纸片应该拼接在文件最上面一

行,应用最小曼哈顿距离对此类碎片按正确顺序拼接。同理可聚类出另一个特殊的类,即碎纸片左边缘为空白、拼接在文件最左边一列的类,并且也应用最小曼哈顿距离对此类碎片按正确顺序拼接。然后以此拼接好的第一行和第一列碎片为基准,再应用最小曼哈顿距离拼接其余剩下的碎片,最后拼接复原出原中文文件。

在英文文件中,一个英文单词中两个连续的英文字母中间的空白间隔所占像

1素宽度与其左边或者右边的英文字母所占像素宽度的比值最大的约为11,则对

1于每一行英文单词,碎纸机纵切未切到英文单词的概率为11,对于每两行英文

1单词碎纸机纵切未切到英文单词的概率为121,而对于每三行英文单词碎纸机纵

切未切到英文单词的概率为, 然后同上述中文文件的分析过程可知,此时对拼接在文件最左边一列归类时混入上面提到的干扰碎片的概率最大不超过

,最后拼接复原出原英文文件。

? 模型二的求解

6

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

图1 根据碎片顶部文字高度聚类

7

图2 根据碎片顶部空白高度聚类

结合上面的聚类图,可得出附件3的乱序矩阵,如下表所示。

表6 附件3的乱序矩阵

49 61 168 38 71 14 94 125 29 7 89 22 79 179 167 205 115 58 13 10 0 151

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

8