表7 附件4的乱序矩阵

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

表8 附件3碎片序号复原后顺序

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

同法我们再求出附件4碎片与碎片之间的曼哈顿距离，从而得到附件4碎片序号按复原后顺序如下表所示。

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

191 201 86 19 159 20 208 70 132 75 11 154 190 184 2 104 148 170 196 198 94 113 164 51 107 29 40 158 186 98 194 93 141 88 121 126 105 139 1 129 63 138 153 53 41 108 116 136 73 36 207 21 7 49 61 119 33 142 84 60 14 68 174 137 195 181 95 69 167 163 166 188

180 78 24 155 38 135 168 8 111 64 103 117 114 123 15 62 47 144 9

106 4 149 32 91 80 101 26 150 5 59 58 176 182 151 22 120 175 85 50 76 43 199 45 169 54 192 133 172 156 96 23 206 3 130 34 204 100 92 57 160 173 118 99 13 65 39 67 147 6 17 28 146 30 37 46 127 202 71 165 82 187 97 203 31 79 161 179 143 189 162 197 112 122 90 185 109 110 25 27 178 171 81 42 66 205 10 157 74 145 83 134 77 128 200 131 52 125 140 193 87

55 89 18 48 56 72 35 16 9 183 152 44 12 177 124 0 102 115 附件4碎片复原图片如附录中图8.4所示。 问题二人工干预情况如下表所示。

表10 问题二人工干预情况

人工干预 图像 附件3图像 干预时间 干预方式 1 干预次数 初始化最左边一图像的最左边一列纸片需要人工排序 列排序出错的地方进 行调整 初次拼接结束后一小部分位置在水平方向出错 在程序运行初始化中强制将出错的一个图像安排在水平方向的正确位置 2 附件4图像 初始化最左边一图像的最左边一列纸片需要人工排序 列排序出错的地方进 行调整 初次拼接结束后小部分位置在水平方向出错 在程序运行初始化中强制将出错的一个图像安排在水平方向正确位置 1 4

5.3 问题三（曼哈顿距离）

? 模型三的建立

问题三在问题二的基础上继续加大碎片拼接复原难度，此时我们对双面碎纸片进行类似问题一的处理，得到418个数值矩阵，我们根据每个碎片顶部的空白高度或者文字高度对碎片进行区间分类，得到22组矩阵，再根据曼哈顿距离将得到的22组矩阵聚成两类，每类各包含某一面的11组矩阵，然后综合每一面的聚类情况再应用最小曼哈顿距离对双面碎纸片进行拼接复原。然后再利用曼哈顿距离对碎纸片在竖直方向上进行聚合得到最终图像。

? 模型三的求解

问题三的解决方法与问题二的类似，不过我们分两步进行聚类分析。第一步，我们根据每个碎片顶部空白高度的不同进行聚类，第二步，我们根据每个碎片底部空白高度的不同进行聚类。然后我们选取第一、二步聚类产生的公共类，若得

10

到的公共类数量小于22类，则再从单独由第一步聚类产生的类中选取，直到数量达到22类。对于这22类碎纸片，我们再利用问题二的方法聚成两组，每组数量都为11类。后面类似模型二的处理过程，结果顺序如下表所示。

表11 附件5某一面碎纸的初次拼接位置 078b 165b 186b 199b 088b 114a 146a 089a 033b 023b 099a 053b 108a 198b 137b 062a 176a 120b 049b 151b 117b 012a 153a 043a 184b 195a 010b 007b 107a 011b 171b 111b 133a 091a 017b 087a 185a 144a 018b 129b 008b 202a 045a 170b 036a 096b 161a 048a 085b 149b 179b 031a 084b 128a 125a 102b 029a 079a 021b 132b 068b 000b 041a 118b 138a 106b 157a 051b 042b 169b 140a 148b 180a 076b 109a 116b 201a 189b 056b 080b 070b 093a 101a 188a 130a 064b 014a 100b 030a 194b 050a 095a 155a 037b 123a 077a 178a 207a 168a 131b 055b 139b 059a 208a 081b 027a 127a 015b 163a 072b 058a 160b 150a 173b 006a 191a 038a 046a 044a 004a 190b 142a 175a 002a 164b 205a 193b 103a 060b 135b 187b 040a 025b 069a 065b 158a 121a 067a 104a 206b 183b 119a 092b 162b 182b 097a 057a 086b 141a 112a 020a 147a 082b 073b 179a 115b 174b 033b 098a 134a 192a 063b 156a 019b 032a 122a 159a 024a 145a 200b 152a 203b 196b 039b 047a 204b 166b 071b 074b 034a 113a 094b 124b 075b 110a 016b 154b 172a 005a 090a 013a 143b 136b 105a 009b 083a 054b 035a 061b 077b 026b 066a 001b 028b 181b 022a 052a 167a 126b 表12 问题三最终拼接结果 078b 089a 186b 199b 088b 114a 146a 165b 003b 023b 099a 111b 010b 153a 011b 107a 184b 171b 195a 007b 133a 043a 125a 036a 084b 161a 149b 179b 031a 128a 085b 048a 096b 140a 076b 042b 169b 180a 116b 201a 157a 148b 051b 109a 155a 178a 030a 194b 037b 207a 050a 168a 077a 095a 123a 150a 044a 038a 173b 191a 058a 190b 046a 004a 160b 006a 183b 025b 121a 206b 065b 158a 092b 067a 069a 119a 104a 174b 192a 098a 156a 115b 197a 019b 063b 032a 033b 134a 110a 124b 094b 034a 166b 154b 016b 075b 074b 071b 113a 066a 022a 061b 181b 001b 028b 177b 167a 126b 052a 026b 11

108a 120b 137b 198b 151b 012a 053b 117b 176a 062a 049b 018b 144a 045a 087a 170b 017b 202a 008b 185a 129b 091a 029a 079a 138a 132b 041a 102b 021b 068b 000b 118b 106b 189b 014a 056b 093a 070b 064b 130a 188a 080b 101a 100b 081b 059a 131b 072b 139b 208a 163a 127a 027a 015b 055b 164b 060b 187b 175a 002a 142a 193b 040a 135b 205a 103a 020a 147a 086b 097a 162b 057a 073b 182b 141a 082b 112a 047a 152a 200b 039b 203b 024a 159a 122a 204b 145a 196b 136b 005a 143b 083a 090a 013a 035a 172a 105a 009b 054b 同理，剩余的图像矩阵可以组成另一面的文章。

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

表13 问题三人工干预情况 人工干预 图像 附件5图像 干预时间 初始化最左边一列纸片需要人工排序 初次拼接中间，一小部分位置在竖直方式方向出错 图像的最左边一列排序出错的地方进行调整 在程序初始化时强制将出错的一个图像安排在竖直方向正确位置 4 9 干预方式 干预次数 初次拼接结在程序初始化时束后小部分位置强制将出错的一个图在水平方向出错 像安排在水平方向正确位置

3

六、模型的评价与推广

1.模型的评价

对于问题一，由于题目中给的样本较为简单，所以模型一能很好的解决附件1、附件2给出的中、英文文件碎纸片拼接复原问题。

对于问题二，模型二也能较好的解决问题，但模型二也有不足之处。比如模

12