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

摘 要

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

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

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

二、问题分析

我们从附件中的碎片数据可知由于碎纸机产生的碎纸片边缘是规则的，此时碎纸片计算机拼接方法就不能利用碎片边缘的尖点特征、尖角特征、面积特征等基于边界几何特征的拼接方法，而要利用碎片内的字迹断线或碎片内的文字内容是否匹配搜索与之匹配的相邻碎纸片并进行拼接。首先，我们对碎片内图像进行数据化处理，得到对应的像素值矩阵；然后，我们设置阈值对像素值矩阵进行二值化处理得到相应的数值矩阵；最后，由于曼哈顿距离公式计算快、数值小，数值矩阵与数值矩阵之间应用最小曼哈顿距离对碎纸片进行拼接复原。

问题一中碎纸机破碎纸片只有纵切，每页纸被切为19条碎片，经过处理可以得到19个数值矩阵。对于每个数值矩阵，我们依次取出最左边一列从上至下各格的值组成一个向量，同样我们依次取出最右边一列从上至下各格的值组成一

2

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

问题二是对碎纸机既纵切又横切的情形进行讨论，比问题一多了横切条件，此时每页纸被切为209个碎片。首先，我们利用文件最左边碎片与最上面碎片的特殊性对这209个碎片进行聚类，得到两类特殊的碎片，分别是文件最左边一列碎片和最上面一行碎片，然后类似于问题一的处理方法，应用最小曼哈顿距离对每一类碎片按正确顺序拼接，此后对其余碎片再应用最小曼哈顿距离逐一进行拼接，直至剩余所有的碎片都拼接上。

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

三、模型假设

1. 假设碎纸机破碎纸片（纵切或横切）得到的碎纸片是规则且边缘是整齐的等大的矩形；

2.假设我们对文档碎纸片拼接复原不考虑碎片边缘的尖点特征、尖角特征、面积特征等基于边界几何特征；

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

四、符号说明

3

序号 1 2 3 4 5 符号 符号说明 数值矩阵 数值矩阵数值矩阵Ai Xi Yi Ai的最左边列向量 Ai的最右边列向量 d(Xi,Yj) 曼哈顿距离 隶属函数中的阀值  五、模型建立与求解

5.1 问题一（曼哈顿距离）

➢ 模型一的建立

题目要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切）建立碎纸片拼接复原模型和算法，并且要对中、英文各一页文件的碎片数据分别进行拼接复原。首先，我们利用数学软件MATLAB软件将19条碎片数据化，得到19个像素值矩阵，像素值的变化范围是从0变化到255，此时我们设置127为阈值对像素值矩阵进行二值化处理，当矩阵某位置像素值小于等于时，则将对应位置的数值设为0；当矩阵某位置像素值大于时，则将对应位置的数值设为127。这样我们就得到19个二值化了的数值矩阵

Ai，对于每个数值矩阵

Ai，我

们依次取出最左边一列从上至下各格的值组成一个向量，记为

Xi，同样的我们

依次取出最右边一列从上至下各格的值组成一个向量，记为Yi。计算出每一数值矩阵的左边向量与所有非同源数值矩阵的右边向量的曼哈顿距离

➢ 模型一的求解

d(Xi,Yj)。

对于得到的向量

Xi(xi1,xi2,...,xik)T(k1,2,...,n)(k1,2,...,m)和向量

Yi(yi1,yi2,...,yik)T，两向量的曼哈顿距离为

4

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 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 1 145 92 174 117 186 19 18 105 202 203 97 109 201 68 40 2 67 26 1 152 169 47 21 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

表7 附件4的乱序矩阵

191 201 86 19 159 20 208 70 132 171 81 147 80 59 121 203 136 1 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 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 1 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 54 19 100 148 156 128 34 13 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 1 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 1 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 1 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 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 1 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 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 0a 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 1b 056b 080b 070b 093a 101a 188a 130a 0b 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 1b 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 0a 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 1b 014a 056b 093a 070b 0b 130a 188a 080b 101a 100b 081b 059a 131b 072b 139b 208a 163a 127a 027a 015b 055b 1b 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

型二只考虑根据每个碎片顶部的空白高度和文字高度对碎片进行区间分类，分为11组矩阵。而没有综合考虑每个碎片顶部与底部的空白高度和文字高度对碎片进行区间分类，因此分类准确率降低。

对于问题三，由于每个碎片都有正反两面，而且模型三对碎片聚类时只对每一面单独进行分析，所以模型三解决问题时错误匹配的数量明显多于前面两题。因此，我们除了挖掘算法潜力，还能对模型三做出进一步的改进，比如对碎片聚类时综合对两面进行分析以及对某面分析时综合考虑已经排好顺序的第一行与第一列碎片等都能进一步优化模型，减少错误匹配的数量，提高效率，增加模型的适应性。

2.模型的推广

我们建立的模型在处理碎纸片较大且碎纸片数量不是很多的时候，模型可以较好的解决问题，但在实际应用中，通常会涉及碎纸片被切割得很细很小，并且要对大量碎纸片数据进行管理和处理工作。所以我们要进一步优化算法和程序结构，改善模型，真正建立起快速有效的计算机辅助碎纸片自动拼接复原模型，从而才能将此模型广泛地应用到我们的实际生活中。

七、参考文献

[1]. 张翠. 基于点线的文档图片数字水印与碎片拼接[D]. 青岛:中国海洋大学, 2011. [26-34]。 [2]. 张艳. 图像拼接技术在文档图像扭曲识别中的应用与研究[D]. 北京:北方工业大学, 2011. [23-29]。

[3]. 贾海燕, 朱良家, 周宗潭, 胡德文. 一种碎纸自动拼接中的形状匹配方法[J]. 计算机仿真, 2006, 23(11): [180-183]。

[4]. 汪晓银, 邹庭荣. 数学软件与数学实验[M]. 北京: 科学出版社,2008. [1-27]。

[5]. 张铮,杨文平,石博强,李海鹏. Matlab程序设计与实例应用[M]. 北京: 中国铁道出版社,2003.[276-306]。

[6]. 姚文敏. 数字图像处理[M]. 北京:机械工业出版社, 2006. [24-45]。

13

八、附录

图像拼接结果

图8.1 附件1碎片复原图片

14

图8.2 附件2碎片复原图片

15

图8.3 附件3碎片初次拼接结果图

16

图8.4 附件3碎片复原图片

17

图8.5 附件4碎片初次拼接结果图

18

图8.6 附件4碎片复原图片

19

图8.7 附件5碎片复原图片一面

20

图8.8 附件5碎片复原图片另一面

21

程序源代码

问题一

function Q1() %处理问题1的相关程序

clear all; close all；

clc; %清理显示屏幕 var=0; N=18; m=0; n=0; pi=0; pj=0;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %导入图像部分 for i=0:N if(i<10)

filename=sprintf('00%d.bmp',i); %构造需要导入的文件名字

else %而相应的文件存放在工作目录中

filename=sprintf('0%d.bmp',i); %构造需要导入的文件 end

I=imread(filename); %导入图片文件 Im{i+1}=I; %将变量Im用cell格式存放数据，后续调用这个变量

end

[m n]=size(I); %提取矩阵的行与列 for i=0:N

IM{i+1}=im2bw(Im{i+1}); %Im变量中所有的图像数据进行二值化

i=i+1; end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% for i=0:N

subplot(1,N+1,i+1)

imshow(Im{i+1}); %显示没有经过处理时候的情况 end %}

for i=0:N var=-1; for j=0:N

22

if(i~=j)

if(var==-1)

var=sum(abs(IM{i+1}(:,72)-IM{j+1}(:,1))); pi=i; pj=j; else

if(sum(abs(double(IM{i+1}(:,72))-double(IM{j+1}(:,1))))var=sum(abs(double(IM{i+1}(:,72))-double(IM{j+1}(:,1))));

%断

pi=i; % pj=j; % end end end end

res(i+1,:)=[pi pj var]; end

res %编号，右边位置图片编号，曼哈顿距离值k=0;

for i=0:N

if(res(i+1,3)==0) %面

sq(k+1)=res(i+1,2); end end

for i=0:N-1 for j=0:N

if(sq(i+1)==res(j+1,1))

sq(i+2)=res(j+1,2); % end end end

sq %ResIm=Im{sq(1)+1}; for i=1:N

ResIm=[ResIm,Im{sq(i+1)+1}]; %接 end

hold off

imshow(ResIm) %hold on

23

通过残差绝对值再求和判左边位置的图片编号右边位置的图片编号显示的结果为：左边位置图片将误差为0的编号放在最前对序列进行排序 显示排列的顺序 将图片比编号按顺序进行拼显示图片拼接结果 %title('附件1拼接结果图')

问题二—函数1

function Q21() clear all; close all; clc; N=208; var=0; m=0; n=0; pi=0; pj=0; R=11; C=19;

for i=0:N if(i<10)

filename=sprintf('00%d.bmp',i); %件的名字

else if(i<100)

filename=sprintf('0%d.bmp',i); else

filename=sprintf('%d.bmp',i); end; end

I=imread(filename); %文件读入程序 [m n]=size(I); Im{i+1}=I; end

for i=0:N

IM{i+1}=im2bw(Im{i+1}); %阵二值化 end

for i=1:N+1

[H(i) B(i)]=LocateHeight(IM{i}); %LocateHeight函数求一张图片中最上方白色部分的宽度 L(i)=i-1; end

RE(:,1)=L; %L识位置

RE(:,2)=H; %H24

构造文将像素像素矩调用表示图像标表示

图片中顶部的空白宽度或是文字宽度

RE(:,3)=B; OUT=sortrows(RE,3); temp=sum(OUT(:,3)); O1=OUT(1:(N+1-temp),:); O2=OUT((N+2-temp):N,:);

sortrows(O1,2) %按照图像中顶部空白的图像高度进行排序

sortrows(O2,2) %按照图像中顶部黑色的图像高度进行排序

function [res1 res2]=LocateHeight(II) %LocateHeight函数，计算图像顶部文字高度或者空白位置，为.m内部函数 t1=-1; t2=-1;

for i=0:179

if(i==0&&sum(II(i+1,:))==72) t1=i; end

if(i==0&&sum(II(i+1,:))~=72) t2=i; end

if(t1~=-1&&i>t1&&sum(II(i+1,:))~=72) res1=i-t1; res2=1; break; end

if(t2~=-1&&i>t1&&sum(II(i+1,:))==72) res1=i-t2; res2=0; break; end end

问题二—函数2

function Q22()

clear all; close all; clc;

N=208; %图像数量 var=0; %方差 m=0; n=0;

25

pi=0; pj=0; R=11; C=19;

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

filename=sprintf('00%d.bmp',i); else if(i<100)

filename=sprintf('0%d.bmp',i); else

filename=sprintf('%d.bmp',i); end; end

I=imread(filename); [m n]=size(I); Im{i+1}=I; end

for i=0:N

IM{i+1}=im2bw(Im{i+1}); %将导入的像素矩阵进行二极值化变换，得到0-1矩阵 end

26

a=1; S=Z;

[m,n]=size(S);

for i=1:R for j=1:C

IMG{i,j}=IM{S(i,j)+1}; %将同一行的像素矩阵放置在一个4维数组中 end end

for r=1:R %在水平方向上根据两个矩阵的曼哈顿距离进行拼接

for j=2:C-1 var=-1; for i=j:C

if(var==-1)

var=sum(abs(IMG{r,j-1}(:,72)-IMG{r,i}(:,1))); p=i;

else if(sum(abs(IMG{r,j-1}(:,72)-IMG{r,i}(:,1)))temp1=IMG{r,p}; IMG{r,p}=IMG{r,j}; IMG{r,j}=temp1; end end

for i=1:R

ResIm{i}=IMG{i,1}; for j=2:C

ResIm{i}=[ResIm{i},IMG{i,j}]; %在水平方向对矩阵进行合并 end end

RES=ResIm{1}; for i=2:R

RES=[RES;ResIm{i}]; %在竖直方向将矩阵合并成大矩阵 end

27

%hold off

imshow(RES); %显示结果图 %hold on

title('附件4的初次拼接效果')

怎样写作数学建模竞赛论文

一 如何建立数学模型—建立数学模型的涉骤和方法

建立数学模型没有固定的模式，通常它与实际问题的性质、建模的目的等有关。当然，建模的过程也有共性，一般说来大致可以分以下几个步骤：

1. 形成问题 要建立现实问题的数学模型，首先要对所要解决的问题有一个十分明晰的提法。只有明确问题的背景，尽量弄清对象的特征，掌握有关的数据，确切地了解建立数学模型要达到的目的，才能形成一个比较明晰的“问题”。

2. 假设和简化

根据对象的特征和建模的目的，对问题进行必要的、合理的假设和简化。现实问题通常是纷繁复杂的，我们必须紧紧抓住本质的因素(起支配作用的因素)，忽略次要的因素。此外，一般地说，一个现实问题不经过假设和简化，很难归结为数学问题。因此，有必要对现实问题作一些简化，有时甚至是理想化

3 .模型的构建 根据所作的假设，分析对象的因果关系，用适当的数学语言刻画对象的内在规律，构建现实问题中各个量之间的数学结构，得到相应的数学模型。这里，有一个应遵循的原则：即尽量采用简单的数学工具。

4. 检验和评价

数学模型能否反映厡来的现实问题，必须经受多种途径的检验。这里包括：(1).数学结构的正确性，即有没有逻辑上自相矛盾的地方；(2).适合求解，即是否有多解或无解的情况出现；(3).数学方法的可行性，即迭代方法是否收敛，以及算法的复杂性等。而更重要和最困难的问题是检验模型是否真正反映厡来的现实问题。模型必须反映现实，但又不等同于现实；模型必须简化，但过分的简化则使模型远离现实，无法解决现实问题。因此，检验模型的合理性和适用性，对于建模的成败是非常重要的。评价模型的根本标准是看它能否准确地反映现实问题和解决现实问题。此外，是否容易求解也是评价模型的一个重要标准。

5. 模型的改进

模型在不断检验过程中经过不断修正，逐步趋向完善，这是建模必须遵循的重要规律。一旦在检验中发现问题，人们必须重新审视在建模时所作的假设和简化的合理性，检查是否正确刻画对象内在的量之间的相互关系和服从的客观规律。针对发现的问题作出相应的修正。然后，再次重复上述检验、修改的过程，直到获得某种程度的满意模型为止。

6. 模型的求解

28

经过检验，能比较好地反映厡来现实问题的数学模型，最后将通过求解得到数学上的结果；再通过“翻译”回到现实问题，得到相应的结论。模型若能获得解的确切表达式固然最好，但现实中多数场合需依靠电子计算机数值求解。电子计算机技术的飞速发展，使数学模型这一有效的工具得以发扬光大。

数学建模的过程是一种创造性思维的过程，对于实际工作者来说，除了需要具有想象力、洞察力、判断力这些属于形象思维、逻辑思维范畴的能力外，直觉和灵感往往不可忽视，这就是人们对新事物的敏锐的领悟、理解、推理和判断。它要求人们具有丰富的知识，实惯用不同的思维方式对问题进行艰苦探索和反复思考。这种能力的培养要依靠长期的积累。

此外，用数学模型解决现际问题，还应当注意两方面的情况。

一方面，对于不同的实际问题，通常会使用不同的数学模型。但是，有的时候，同一数学模型，往往可以用来解释表面上看来毫不相关的实际问题。

另一方面，对于同一实际问题要求不同，则构建的数学模型可能完全不同。 二 写作数学建模竞赛论文应注意的问题： 1. 论文格式

论文的封面： 题目 ………

参赛队员： … … … 指导教师：…… 单位：………

论文的第一页是摘要，第二页开始是论文的正文，论文要有以下几方面的内容：

一. 问题的提出 二. 问题的分析 三. 模型的假设 四. 模型的建立 五. 模型的求解 六. 模型的检验 七. 模型的修正 八. 模型的评估 九. 附录

以上各部分内容应该都是要具备的，但有些步骤可以合并在一起。例如：问题的提出与问题的分析，模型的假设与模型的建立，模型的检验与模型的修正等。下面就每一步以及建模过程中应注意的几个问题作一简要介绍。

2. 审题：赛题一般有两道(研究生的竞赛有4道题)，我们可以从中任选一道，这就面临选哪道题合适的问题。因此，首先必需弄清题目的意义。数学建模的题目有时很长，有时很复杂。不易弄懂它的意义，一般要用几个钟头的时间才能弄清楚它的含义。因此我们要求：

29

(1). 深刻理解题意

(2). 弄清题目的实际背景

(3) 正确选择题目，根据自身的特长和优势作出决定。要注意不要被题目的繁长的叙述哧住，碰到长的题目要有耐心，要仔细的分析题目的各部分内容、条件和要求。

3. 当选定题目后，接下来就应该是对题目进进一步的分析。下面的几项工作是必需要做的：

(1). 在弄清问题的背景下，说清事情的来龙去脉。

(2). 列出必要的数据，题目所给的数据往往是不够的，还要寻找题目以外的数据。

(3). 列出和题目相关的各种条件和变量，分清各变量之间的主从关系。 (4). 给出研究对象的关键信息内容。

4 . 在分析问题的基础上，提出合理的假设

模型是在假设的前提下建立起来的。对情景的说明不可能也不必要提供问题的每一个细节。由题目所提供的假设来建立数学模型还是不够的，还要补充一些假设。假设是建立数学模型很关键的一步，关系到模型的成败和优劣。所以应该仔细地分析实际问题，从大量的变量中筛选出最能表现问题本质的变量，并简化它们的关系。这部分内容就应该在论文的问题的假设部分中体现。由于假设不是实际问题直接提供的，它因人而异，所以，在撰写这部分内容时要注意以下几个方面：

(1) 论文中的假设要以严格、确切的数学语言来表达，使读者不致产生任何曲解。

(2) 所提出的假设确实是建立数学模型所必需的，与建立数学模型无关的假设只会扰乱读者的思考

(3) 假设应该是合理的；怎样的假设才是合理的呢？a .假设应合乎生活常识。b. 假设不能与已知的科学定律相悖。c. 假设必需是对建模有用的。d. 尽量使用数学的语言。e. 假设不要超出题目要求的范围。

假设这一步是数学建模的一个难点，它关系到建模的成败和优劣，数学建模的假设就是要发挥每个人的想象力和创造力，提出适当的、合理的、有创新的见解。如果这一步成功了，那么你的整个建模过程也就成功了一半。

5 在假设的基础上下一步当然就是模型的建立。在建立模型之前要引进变量及其记号。每个字母所表达的确切含义。

经过抽象，确切表达各变量之间的关系，用一定的数学方法，建立起方程式或归纳为其它形式的数学关系式，如图形、表格等。在建模过程中要注意以下几个问题：

(1) 要用分析和论证的方法，让读者清楚地了解得到建模的过程。 (2) 上下文之间切忌逻辑推理过程中跃度过大，影响论文的说服力。

(3) 需要推理和论证的地方，应该有推导过程且应该力求严谨。引用现成定

30

理时，要先验证满足定理的条件。论文中用到的各种数学符号，必须在第一次出现时加以说明。 6. 模型的求解

把实际问题归结为一定的数学问题后，就要求解或进行分析，数学模型的求解多数是数值求解。在求解时应对计算方法有所说明。使用何种数学软件，给出计算程序(通常以附录形式给出)。有时还用图形或表格形式表出计算结果。有些模型还要作稳定性或灵敏度分折。 7. 模型的检验

数学模型未必都是正确的，这就需要检验，如何检验 (1) 检验是否符合生活常识； (2) 用己给的数据检验； (3) 用分析推理检验。 8. 模型的评估

(1) 模型的优缺点 对自已建立的模型要有正确的评价，既要实事求是，不要过分谦虚，也不要过分誇张。

(2) 模型的推广,模型的适用范围。

对所作的模型，可以作多方面的讨论，例如可以就不同的情景，探索模型将如何变化；也可以根据实际情况，改变文章中的某些假设，指出由此引起数学模型的变化。还可以用不同的数值方法进行计算，并比较所得结果。甚至可以拓广思路，考虑由于建模方法的不同选择而引起的变化。 9. 论文写作中语言表述应注意的问题。

语言是构成论文的基本元素，数学模型论文的语言与其他科学论文的语言一样，要求达意、精炼，不要把一个句子写得太长，使人不甚辛读。语言中应多用客观陈述句，切忌使用你、我、他等代名词和带主观意向的语句。要特别注意以下几点：

(1) 语言要简炼清晰，不要用含糊不清、莫临两可的语言。 (2) 不要随意造句。 (3) 不要用倒装句 (4) 要通俗易懂

10. 如何写论文摘要

竞赛论文要求写论文摘要，摘要放在论文写完最后写。摘要不是提纲，摘要应把论文的主要思想方法、结论和模型的特色讲清楚。让人看到论文的新意。摘要是给读者和评阅专家的第一印象，直接影响到能否获奖的重要因素。从98年开始，由于参赛规模的不断扩大，为了节省阅卷时间和质量，规定论文摘要写祥细一些(研究生的也一样)。即评阅论文时，先看摘要，如果看了你论文的摘要, 认为这篇文章不值得参加评奖，则就被打掉。因此希望大家要十分重视论文摘要的写作。

最后论文要用计算机打印出来，装订好连同电子版上缴，论文一律用A4打印。

31

数学建模竞赛为大学生(研究生)提供了一个表达聪明才智的舞台。你们有这样的机会应该感到高兴。希望大家发扬赶想、赶干，勇于创新，不畏困难的精神。多用形象思维的方法。

什么是形象思维，李大潜院士举了两个非常生动有趣的例子：一个是毛诗词的“渔家傲”词的最后一句“换起工农千百万，同心干，不周山下红旗乱”用了共工头触不周山的故事。

毛的原词是：

渔家傲 反第一次大“围剿” 一九三一年春 万木霜天红烂漫，天兵怒气冲霄汉。

雾满龙冈千嶂暗，齐声唤，前头捉了张辉瓒。 二十万军重入赣，风烟滚滚来天半。

唤起工农千百万，同心干，不周山下红旗乱。 《关于共工头触不周山的故事：“淮南子.天文训”：“昔者共工与颛顼(zhuanxu)争为帝，怒而触不周之山，天柱拆，地维绝。天倾西北，故日月星辰移焉；地不满东南，故水潦尘埃归焉。”》…………。毛按：诸说不同。我取《淮南子.天文训》，共工是胜利的英雄。你看“怒而触不周之山，天柱拆，地维绝。………。”他死了没有呢？没有说。看来是没有死，共工是确实胜利了。》

毛亲自加了按语，说他用了《维南子.天文训》的典故：“怒而触不周山，天柱折，地维绝”。毛写道：“他死了没有呢？没有说。看来是没有死，共工是确实胜利了。”这就完全是一种形象思维。若按形式逻辑，“他死了没有呢？”没有说，就存在两种可能性：一是死，一是活：如果再细分一下，活的当中还可分为未受伤、受轻伤、受重伤、伤重垂危等等情况。这样一来，诗味就完全没有了。而毛用形象思维，从“没有死”，到“看来没有死”，到“确实胜利了”， 思维大踏步跳跃前进，为他的诗作提供了依据，也充分表现了对一个英雄的歌颂和崇敬的心情，使诗意得到了升华。

李大潜院士说：在文学与诗的境界里，如果滥用逻辑思维，就会失去诗的意境，味同嚼蜡。他举了另一个例子，李商隐(晚唐时期著名诗人，特别专长写爱情诗)的爱情诗是很有名的，他的一首“无题”是这样写的：

相见时难别亦难，东风无力百花残。 春蚕到老丝方尽，蜡炬成灰泪始干。 晓镜但愁云鬓改，夜吟应觉月光寒。 逢山此去无多路，青鸟殷勤为探看。

对首句“相见时难别亦难”。一本唐诗三百首中是这样解释的：“无见也无别。正因为相见不易，所以离别也觉难得了。实有互文意”。李大替院士说，这位先生于其说是诗家，还不如说是形式逻辑的信徒。按他的说法，对这句诗可以写出一个数学模型：离别次数=相见次数，因为相见次数少(难)，故离别次数也同样少(难)。这哪里还有诗味，哪里看得到那种难分难舍而又刻骨铭心的离别之情。一句好诗给他这么一解释就被破坏无遗了。数学家要重视逻辑思维，又要看到逻辑

32

思维的的不足，注意从形象思维中汲取营养。这不仅是为了做诗作文，更重要的，在数学上要作出出色的创造，要提出新的数学思想、概念、理论和方法，不能单靠简单的逻辑思维，而要有思维的跳跃，要有发散的思维，要敢于想象，大胆猜想，突破前人的成果及思维模式，才能有大的发明创造。数学建模竞赛要鼓励形象思维，发扬同学的创造精神和创造力，几年来通过开展数学建模教育和数学建模竞赛出现了大量的优秀成果和人才。我也希望我们同学在思维数学模型的时候，多从形象思维的方式去考虑问题，这样才会写出有新创意的好文章。

最后再谈一个问题，就是如何入手？很多人都提出这个问题。我的回答非常简单就是四个字“模仿借鉴”。模仿是所有科学研究工作的最基本的方法之一。模仿不是抄袭，在前人成功的基础上，借鉴别人的经验知识，结合当前的实际，加以修正、提高，提出新的看法和论点，这就是创新。当问题出现后，如果你还不具备相关的知识和解决问题的办法，而又没有时间获得这些知识时，最好的办法就是查找相关的科学文献资料，借鉴别人的做法和思想。当然不能生搬硬套照抄，要结合自己的实际进行修改创新，要注明文献资料的出处(在附录中标明)。所以希望大家要学会又快又好地查找资料的方法，现在大多在网上查找，但要注意辩别真伪，要采用有一定知名度、权威性的刊物和人物的文章。

33