当前位置:首页 >> 学科竞赛 >>

2013全国数学建模竞赛B题优秀论文


基于最小二乘法的碎纸片拼接复原数学模型 摘要

首先对图片进行灰度化处理,然后转化为 0-1 二值矩阵,利用矩阵行(列)偏差函 数,建立了基于最小二乘法的碎纸片拼接数学模型,并利用模型对图片进行拼接复原。 针对问题一,当两个数字矩阵列向量的偏差函数最小时,对应两张图片可以左右拼 接。经计算,得到附件 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。 针对问题二,首先根据每张纸片内容的不同特性,对图片进行聚类分析,将 209 张 图片分为 11 类;对于每一类图片,按照问题一的模型与算法,即列偏差函数最小则进 行左右拼接,对于没有拼接到组合里的碎纸片进行人工干预,我们得到了 11 组碎纸片拼 接而成的图片;对于拼接好的 11 张图片,按照问题一的模型与算法,即行偏差函数最 小则进行上下拼接,对于没有拼接到组合里的碎纸片进行人工干预。我们最终经计算, 附件 3 的拼接结果见表 9,附件 4 的拼接结果见表 10。 针对问题三,由于图片区分正反两面,在问题二的基础上,增加图片从下到上的裁 截距信息,然后进行两次聚类,从而将所有图片进行分类,利用计算机自动拼接与人工 干预相结合,对所有图片进行拼接复原。经计算,附件 5 的拼接结果见表 14 和表 15 该模型的优点是将图片分为具体的几类,大大的减少了工作量,缺点是针对英文文 章的误差比较大。

关键字:灰度处理,图像二值化,最小二乘法,聚类分析,碎纸片拼接

1

一、问题重述

碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情报获取以及故障 分析等领域都有着广泛的应用。近年来,随着德国“斯塔西”文件的恢复工程的公布, 碎纸文件复原技术的研究引起了人们的广泛关注。 传统上, 拼接复原工作需由人工完成, 准确率较高, 但效率很低。 特别是当碎片数量巨大, 人工拼接很难在短时间内完成任务。 随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。 对于一页印刷文档,针对不同的破碎方法,讨论下列三个问题: (1)将给定的一页印刷文字文件纵切,建立碎纸片拼接复原模型和算法,并针对附 件 1、附件 2 给出的中、英文各一页文件的碎片数据进行拼接复原。 (2)对于碎纸机既纵切又横切的情形,设计碎纸片拼接复原模型和算法,并针对附 件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。 (3)对于双面打印文档,研究如何进行碎纸片的拼接复原问题。附件 5 给出的是一 页英文印刷文字双面打印文件的碎片数据。要求尝试设计相应的碎纸片拼接复原模型与 算法,并就附件 5 的碎片数据给出拼接复原结果。

二、模型的基本假设

(1) 待拼接的碎纸片来自同一页印刷文字文件。 (2) 待拼接复原的碎纸片是规整的矩形。 (3) 模型中的碎纸片长度、宽度和面积都相等。 (4) 附件中照片都是同标准拍摄。

三、符号说明

表 1 符号说明

符号
Gray

符号说明 灰度值 红色 绿色 蓝色
2

r
g
b

A, B

矩阵 裁截距 (i =1,2,?, 209) 裁截文字长度 (i =1,2,?, 209) 行间距 (i =1,2,?, 209) 裁截空白距离 (i =1,2,?, 209) 字体高度 (i =1,2,?, 209)

D a b c d
i

i

i

i

i

四、问题分析

将不规则的文档碎纸片进行拼接,一般是利用碎纸片的边缘曲线,尖点、尖角、面 积等几何特征,搜索与之匹配的相邻碎纸片。但对于边缘形状相似的碎纸片,这种基于 边界几何特征的拼接方法失效,拼接时不但要考虑待拼接碎纸片边缘是否匹配,还要判 断碎片内的字迹断线或碎片内的文字内容是否匹配。 本问题给定的碎纸片有以下几个特点: 1、每一张碎纸片都是规整的矩形; 2、所有的碎纸片的长度、宽度都相等,形状是完全一样的; 3、每一张碎纸片里都包含着文字(汉字、英文) ,不存在空白的碎纸片; 4、不同的碎纸片之间没有重叠部分。 由于碎纸片的形状相同,因而不能针对碎纸片的几何特征建立数学模型;碎纸片间无 重叠,也不能利用图像融合技术进行图像配准。 根据上述分析,我们考虑将图片进行数字化处理,根据每张碎纸片上的边缘文字特征 进行匹配,也就是利用图片边缘文字的像素进行最优化匹配。

五、模型的建立与求解

5.1 问题一的建模与算法 由于碎纸片本身不具有体现其拼接特性的数字特征, 我们需要将其数字化、 矩阵化, 将问题转化为矩阵之间的相关性。

3

5.1.1 图片的灰度处理 利用 photoshop 软件,将附件中所给的 BMP 格式的图片转化成 JPG 格式 ,去除图 片的多彩性。为了对碎纸片进行数字化,我们将图像进行灰度处理,取出图像中每一个 像素点的灰度值,灰度值的大小与像素点颜色的红绿蓝成分有关。 根据文献[1],每个像素点的 灰度值=红色 ? 0.30+绿色 ? 0.59+蓝色 ? 0.11 ,即
Gray ? r ? 0.30 ? g ? 0.59 ? b ? 0.11 ,

其中, r , g , b 的取值范围是 0~255 。 问题一将同一页印刷文字文件纵切为 19 张图片(见图 1) ,根据实际情况,我们将 每张图片设置为 1980 ? 72 格式,于是,每张图片对应一个 1980 ? 72 的灰度矩阵。

图 1 附件 1 未进行拼接的 19 张碎纸片

4

5.1.2 图片的二值化处理 将图片进行灰度处理以后,每个像素的灰度值介于 0~255 之间。灰度值不能直接用 于文字图片的拼接,还须进行二值化处理。 将图片放入直角坐标系,规定:若 ( x, y ) 点的像素灰度值大于或等于 T ,该点用数值 1表示,并将其设定为白色;若 ( x, y ) 点的像素灰度值小于 T ,该点用数值 0 表示,并将 其设定为黑色。由此得到像素点的二值化函数:

?1, Gray ( x, y ) ? T , w( x, y ) ? ? ?0, Gray ( x, y ) ? T ,
其中, T 为预先设定的全局灰度阈值。于是,每张图片的灰度矩阵转化为下列 1980 ? 72 的 0,1 数字矩阵:

? a11 ? a1?72 ? ? ? A?? ? ? ? ? , ?a ? ? 1980?1 ? a1980?72 ?
其中

? 1, 1代表空白的像素点, aij ? ? ? 0, 0代表有文字的像素点.
5.1.3 最小二乘法 1、图片左右拼接的数学模型 设 A, B 分别表示左右放置的两张图片对应的数字矩阵,定义前一个矩阵的最后一 列与后一个矩阵的第一列之间的偏差函数为:

f ( A, B) ? ?
i ?1

1980

? A(i, 72) ? B(i,1) ?

2

,

其中, A(i, 72),B(i,1) 分别表示矩阵 A, B 第 72 列和第 1 列的元素。 对于给定的矩阵 A ,若存在矩阵 B ,使得 A 与 B 之间的偏差函数 f ( A, B) 达 到最小,则称 A 与 B 可以匹配,此时 A 与 B 对应的图片可以左右拼接。 2、图片上下拼接的数学模型 类似地,设 C , D 分别表示上下放置的两张图片对应的数字矩阵,定义上面矩阵的 最后一行与下面矩阵的第一行之间的偏差函数为:

h(C , D) ? ?
j ?1

72

? C (1980, j ) ? D(1, j ) ?

2

,

其中, C (1980, j ), D(1, j ) 分别表示矩阵 C , D 第 1980 行和第 1 行的元素。 对于给定的矩阵 C ,若存在矩阵 D ,使得 C 与 D 之间的偏差函数 h(C , D) 达
5

到最小,则称 C 与 D 可以匹配,此时 C 与 D 对应的图片可以上下拼接。 我们称上述基于数字矩阵之间列(或行)距离的图片拼接模型为最小二乘法拼接复 原模型。 5.1.4 算法与求解 (一)算法思想 第一步,对附件中的 19 幅图片分别进行灰度处理,然后取灰度阈值 T ? 125 ,进行 二值化,得到 19 个 0,1 数字矩阵,即图片的数字化。 第二步, 对上述 19 个数字矩阵进行检测, 若存在一个矩阵的最左侧一列元素全是 1, 根据破碎图片的特点,则该图片即为从左边起第一张碎纸片,记为 A1 。 第三步,计算 A1 与其余 18 张图片对应矩阵的列偏差值。

f ( A1 , B) ? ?
i ?1

1980

? A1 (i, 72) ? B(i,1) ?

2

,

若存在 A2 ,使得 f ( A , A2 ) 达到最小,则 A2 即位第二张图片。 1 重复上述的步骤,依次得到所有碎纸片的排列,即可拼接成完整图片。 (二)附件 1、2 的拼接复原结果 附件 1 和附件 2 的拼接顺序如下表: (附件 1 的算法程序见附录一,复原图片见附录二; 附件 2 的算法程序见附录三,复原图片见附录四)
表2 附件 1 拼接顺序

8

14 12 15 3

10 2

16 1
表3

4

5

9

13 18 11

7

17 0

6

附件 2 拼接顺序

3

6

2

7

15 18 11

0

5

1

9

13 10

8

12 14 17 16

4

5.2 问题二的模型建立与算法 5.2.1 图片的数字化处理 步骤一:将附件所给的 BMP 格式图片转换成 JPG 格式的图片; 步骤二:对图片进行灰度处理; 步骤三:然后进行二值化处理; 最后,得到 209 张图片的数字化矩阵。 5.2.2 聚类分析 对于碎纸机既纵切又横切的情形,与问题一仅纵切相比,图片变小,因而每张图片
6

包含的信息量明显变小,如果仅利用最小二乘法,碎片之间的匹配不唯一。为了解决这 个问题,我们利用聚类分析法,对碎片先进行分类。 经观察测试,原始文档碎片具有下列特点: (1)字体大小:字体的最大高度和最大宽度一致。 (2)切割的均匀性:同方向的切割线平行,图片大小均相等,沿纵横方向按直线 切割。 (3)文字的行距:文字的行间距等同,段落间距为定值。 为了对 209 幅图片进行聚类分析,如图 2 所示,我们定义聚类指标如下:

ai 表示图片上端裁接处的字体长度,我们称之为裁截文字长度; bi 为行间距;ci
表示图片上端文字与切割线之间的空白距离,我们称之为裁截空白距离; d i 为字体高 度,其中, i =1,2,?, 209 。

图 2 图片聚类指标示意图

令 Di

? ai ? bi 或 Di ? ci ? di ,称 Di 为第 i 张图片的裁截距 (i =1,2,?, 209) ,

由图 2,如 a1 ? a2 , b1 ? b2 ,则 D1 ? D2 。一般地,图片从上往下看,不同的裁截线形成的 裁截文字长度不同,文字间的行间距相同,所以,如果裁接处的文字长度不相等,那么 文字与空白间距之和就不相等。根据 Di 的不同取值,下面对图片进行分类。 根据二值化矩阵的特点以及文字的特征,只要存在文字,则矩阵的某一行元素一定 存在 0 元素,且在文字之间的元素为 1。如下图所示:

图 3 文字特征图

利用 matlab 软件进行编程,将每个图片的裁截文字长度、行间距、裁截空白距离、 字体高度以及裁截距的结果以 excel 的形式输出到表格之中。 (程序见附录五) 按裁接距进行聚类分析, 使用 spss 软件分析处理后, 得到聚类中心分布图如下所示:

7

表 4 聚类中心
聚类中心 聚类 1 V1 7 2 52 3 32 4 120 5 44 6 58 7 133 8 64 9 109 10 69 11 78

根据表 4 所示的聚类中心,对表格中裁截距进行初步分类。得到聚类结果如下表 所示:
表 5 每个聚类中的案例数
每个聚类中的案例数 聚类 1 2 3 4 5 6 7 8 9 10 11 有效 缺失 2.000 36.000 18.000 1.000 46.000 38.000 1.000 36.000 1.000 11.000 19.000 209.000 .000

根据聚类结果发现,并不能将图片平均分成 11 个组。这时需要增加信息量来更好 地进行分类,进一步观察图 2,我们可以发现:图片的上端裁截处可能是文字,也可能 为空白。 但是裁截距 Di 可能相等, 此时通过图片上端裁截处是空白还是文字加以人工分 类。 用 matlab 将数据导出到 excel 中并进行分析,结果如下:

50 0 高度 0 -50 -100

50

100

150

200

250

图片数量
图 4 分析结果 8

由图 4 可以看出: 图片大体分为 11 个组别, 为了得到更精确地聚类结果, 通过 spss 软件,我们再次确立聚类中心如下图所示:
表 6 第二次聚类中心
最终聚类中心 聚类 1 V1 25 2 2 3 40 4 -38 5 -93 6 -69 7 -84 8 15 9 34 10 -23 11 -10

通过上面两次聚类,确立了两个不同聚类中心。利用第一次确立的裁接距的聚类中 心对图片进行初步分类,然后利用裁截文字或者裁接空白再次进行判别,最终将图片分 成了 11 组。如下表所示: (以上的算法都是在 matlab 软件下操作,程序见附件六)
表 7 各组图片数量 组别 图片 数量 0 3 1 18 2 8 3 19 4 19 5 18 6 18 7 19 8 18 9 18 10 18 11 10 12 19 13 3

由上表可以看出大部分图片已经分出组别,其中有 4 个组达到了 19 张图片,有 6 个组有 18 张图片,仅缺少一张图片。此时我们进行人工干预,根据每组图片总数目应 为 19, 且每类都应存在可作为文件左右边缘的碎纸片, 我们对少量图片进行归类可得到 如下分组结果。如下表:
表 8 聚类后的结果

组别

1
2 11 22 28 49 54 57 65 91 95 118 129 141 143 178 186 188 190 192

2
6 19 20 36 52 61 63 67 69 72 78 79 96 99 116 131 162 163 177

3
1 18 23 26 30 41 50 62 76 86 87 100 120 142 147 168 179 191 195

4
8 9 24 25 35 38 46 74 81 88 103 105 122 130 148 161 167 189 193

5
3 12 14 31 39 51 73 82 107 115 128 134 135 159 160 169 176 199 203 9

6
34 42 43 47 58 77 84 90 94 97 112 121 124 127 136 144 149 164 183

7
13 16 21 66 106 109 110 125 139 145 150 157 173 181 182 184 187 197 204

8
5 10 29 37 44 48 55 59 64 75 92 98 104 111 171 172 180 201 206

9
0 7 32 45 53 56 68 70 93 126 137 138 153 158 166 174 175 196 208

10
15 17 27 33 60 71 80 83 85 132 133 152 156 165 170 198 200 202 205

11
4 40 89 101 102 108 113 114 117 119 123 140 146 151 154 155 185 194 207

图 片 编 号

5.2.3 图片的拼接模型、算法与求解 (一)算法思想 下面我们分两步来做,第一步,对每组碎纸片进行拼接;第二步,将各组进行拼接。 最终完成文件复原。 在已知文件切为 11×19 的碎纸片情况下,将图片进行聚类分析得到了 11 个组后。 利用碎纸片左右边缘为空白的特点判断出文件左侧 11 个碎纸片,再利用问题一模型和 算法,对每个组进行匹配拼接,可得到 11 个拼接好的图片,之后仍然按照问题一的模 型和算法将这 11 张图片拼接成完整的图片。 (二)图片的左边缘确定 根据碎纸片边缘特征, 利用 matlab 对图片处理后得到数字化矩阵, 根据最小二乘法 进行分析得到 16 个可作为文件左边缘的碎纸片,编号如下: (程序详见附录七) 7,14,29,38,49,61,62,67,71,80,89,94,125,135,143,168。 已知文件分为 11×19 的碎纸片,那么存在 5 个不是左边缘碎纸片。 根据文件页边距 一定的特点,此时进行人工筛选,明显排除了编号分别 62,67,80,135,143 的图片 作为文件左边缘的可能。此刻,我们也得到了左边缘碎纸片的序号: 7,14,29,38,49,61, 71,80,89,94,125,168。 (三)图片的各组拼接 第一步,计算机处理,利用问题一的列偏差函数进行图片拼接,现在我们以表 4 中 的第 9 组为例, ,得到如下结果: (程序详见附录八)

图6

以第 9 组为例的拼接结果 1

第二步,人工干预,由于每组有 19 个图片,可以明显观察到排序的时候有一个图 片没有出现,而且另一个图片重复出现了两次。此时我们进行人工拼接。得到正确的拼 接结果,图片如下:

图7

以第 9 组为例的拼接最终结果

其余分组按照相同方法可得到 11 组的拼接结果,这里我们不在一一赘述,发现每 组的拼接均无误,这说明我们的分类达到了预期的效果。
10

(四)图片的整体拼接 上一步骤中我们得到了 11×19 的碎纸片拼接而成的 11 个等大小的纸片,那么接 下来,根据行偏差函数,判断 11 个纸片的上下拼接顺序,可以得到以下编号的图片可 以上下拼接:

?

30 8

?

169 39

?

15 95

?

50 62

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

对于附件 4,我们按照与处理附件 3 相同的模型和算法进行处理,得到拼接结果表 格如下, (复原图片详见附录十) :
表 10 附件 4 拼接顺序 191 201 086 019 159 020 208 070 132 171 081 075 148 051 194 139 041 021 084 181 042 077 011 170 107 093 001 108 007 060 095 066 128 154 196 029 141 129 116 049 014 069 205 200 190 198 040 088 063 136 061 068 167 010 131 184 094 158 121 138 073 119 174 163 157 052 002 113 186 126 153 036 033 137 166 074 125 104 164 098 105 053 207 142 195 188 145 140 180 078 024 155 038 135 168 008 111 083 193 064 103 117 114 123 015 062 047 144 134 087 106 091 150 176 120 076 169 172 206 055 089 004 080 005 182 175 043 054 156 003 018 048 149 101 059 151 085 199 192 096 130 056 072 032 026 058 022 050 045 133 023 034 035 012 204 100 092 057 160 173 118 099 013 016 177 065 006 030 202 187 079 189 122 110 009 124 039 017 037 071 097 161 162 090 025 183 000 067 028 046 165 203 179 197 185 027 152 102 147 146 127 082 031 143 112 109 178 044 115

5.3 问题三的模型建立与算法 对于第三个问题,图片的数量成倍的增长,我们不能单纯的利用图片边缘的特征进 行拼接与复原,在问题二按上边缘裁截距进行聚类分析的基础上,增加图片下边缘裁截
11

距,综合进行聚类分析。具体流程图如下所示: 输入图片 将图片灰度处理

将灰度处理后的图片二值化处理 自上而下计算图片的裁接距与裁截 空白间距(或裁截文字长度)

N
高 度 是 否相似? 标注备选 自 上 图 裁 与 空 距 下 计 片 截 裁 白 而 算 的 距 截 间

Y
运用问题二的方法进行匹配

N
匹配成 功? 加入备选图 片进行匹配

Y
备存 匹配成功,备存

完成组图

图 8 算法流程图

5.3.1 图片的初次聚类 运用问题二的聚类方法,利用 matlab 进行数据处理(程序见附录十一) ,将所得结 果导入 excel ,做出图片上边缘的裁截文字长度(或者裁截空白长度)的分布图
12

60 40 20

裁截文字的长度

0 -20 -40 -60 -80 -100 -120 图片
图 9 附件 5 图片的裁截文字长度分布图

1

26 51 76 101 126 151 176 201 226 251 276 301 326 351 376 401 系列1

用 spss 进行快速聚类分析,可以看出能将一部分图片进行准确的分类,利用模型一 的方法对分类后的图片进行边缘匹配,得到类似于下图的片段图像。

图 10 匹配正确的片段图

5.3.2 图片的再聚类 由于图片的双面性,我们在对其正面(反面)进行正确匹配之后,则其反面(正面) 也就确定出来,这大大减少了数据量。但某些分类后却拼接失败的情况,使得拼接更加 的困难。 在第二个问题中,我们利用图片从上到下文字的特征增加了信息量,为了更好进行 图片匹配与拼接,对于问题三,我们再次增加图片从下到上的文字特征。在图片初次聚 类的前提下,利用从下到上的裁截距,按照与问题二类似的办法进行第二次聚类,步骤 同上,得到图片的裁截文字长度的分布直方图:

13

60 40 20

裁截文字长度

0 -20 -40 -60 -80 -100 图片
图 11 图片裁截文字长度的分布直方图

1

28 55 82 109 136 163 190 217 244 271 298 325 352 379 406

系列1

5.3.3 图片的拼接 根据前两次图片的聚类之后, 我们在对其进行分类, 将分类后的图片进行边缘匹配, 同时进行人工干预,挑选出匹配正确的片段,如下图所示:

图 12 匹配正确的片段

对每一类图片匹配成功后, 类似于问题二, 利用计算机自动拼接与人工干预相结合, 将所有各类进行整体拼接,结果如下: (复原图片见附录 12)

14

表 13 附件 5 其中一面的拼接顺序

表 14 附件 5 另一面的拼接顺序

六、模型的评价与改进

6.1 模型的优点 (1) 模型一对于解决纵切碎纸片的问题上,达到了很好的效果,对于所得的结果正确 率也是 100%的,对于解决此类问题提供了良好的思想。 (2) 模型二充分考虑了碎纸片边缘的匹配问题以及文字内部的特征信息,对于既纵切 又横切的情形,先进行了聚类将图片进行了分组,大大减少了工作量,而且增加 了准确度。 6.2 模型的缺点 (1) 对于问题一与问题二,所给的完整图片里面含有大量的的文字,所以我们可以利 用其文字特征,该结果也存在一定的偶然性。 (2) 对于问题三,对于大信息量的图片信息,只利用问题二的解决办法只能将部分的 图片进行分类,而不能单纯用计算机进行完整的拼接。
15

6.3 模型的改进方向 (1) 在问题一里面我们只考虑了边缘区域的匹配,由于结果正确所以没有继续增加条 件保证其准确率。 (2) 在设计模型二的时候,只考虑了图片从上到下的裁接距与裁截文字长度的方面, 还应该加上其在图片从下往上的数据。

七、参考文献

[1]黄添强,陈智文,苏立超等. 利用内容连续性的数字视频篡改检测[J]. 南京大学学报(自然科学 版) ,2011,47(5) :493-503. [2] 罗智中. 基于线段扫描的碎纸片边界检测算法研究 [J]. 仪器仪表学报,2011,32(2) :289-294. [3] 白宗文. 基于 HALCON 与图像拼接的文物修复系统设计与实现[J]. 电子设计工程, 2013,21 (9) : 24-26. [4] 李利军,李云伟. 基于图像灰度的拼接技术研究[J]. 计算机与数字工程,2007,35(9) :128-130. [5] 贾海燕, 朱良家, 周宗潭等. 一种碎纸自动拼接中的形状匹配方法[J]. 计算机仿真, 2006,23 (11) : 180-183.

16

八、附录

附录一: %%%%%%%%以下程序的运行,请注意文件存放的位置!! ! %%%%%%%%此程序用来解决附件 1 的图片匹配与连接 A=zeros(19,19); %共十九个纸条 for j=1:19 str='D:\附件\附件 1\'; I=imread([str,num2str(j),'.jpg']);%依次读取每一幅图像 i1=rgb2gray(I); %i1 灰度图像 i2=im2bw(i1); %i2 是二值图像 a=i2(:,72,1); %取纸片右边缘 str='D:\附件\附件 1\'; for i=1:19 I=imread([str,num2str(i),'.jpg']); %依次读取每一幅图像 i1=rgb2gray(I); %i1 灰度图像 i2=im2bw(i1); %i2 是二值图像 mi=i2(:,1,1); %取纸片左边缘 ni=a-mi; A(j,i)=sqrt(dot(ni,ni)); end end xlswrite('D:\photo1.xls',A,'A1:S19'); %将矩阵元素导入 excel 表格 %判断相邻图片并自动连接连接 a=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];%记录和纸片右相邻的纸片 for i=1:19 k=A(i,1); a(i)=1; for j=1:19 if(k>A(i,j)) k=A(i,j); a(i)=j; end end end first=1; for i=1:19 for j=1:19 if(A(i,j)==0)
17

first=j; %求出文件最左侧纸张 end end end str='D:\附件\附件 1\'; z= imread([str,num2str(first),'.jpg']); for m=1:18 m=1; str='D:\附件\附件 1\'; x = imread([str,num2str(first),'.jpg']); %记录上一张纸条 y=imread([str,num2str(a(first)),'.jpg']);%记录下一张纸条 x=z; %保存已拼接纸条 z = [x,y]; first=a(first); end imshow(z) 附录二:

图 13

附件 1 拼接图片

18

附录三: %%%%%%%%以下程序的运行,请注意文件存放的位置!! ! %%%%%%%%此程序用来解决附件 2 的图片匹配与连接 A=zeros(19,19); %共十九个纸条 for j=1:19 str='D:\附件\附件 2\'; I=imread([str,num2str(j),'.jpg']);%依次读取每一幅图像 i1=rgb2gray(I); %i1 灰度图像 i2=im2bw(i1); %i2 是二值图像 a=i2(:,72,1); %取纸片右边缘 str='D:\附件\附件 2\'; for i=1:19 I=imread([str,num2str(i),'.jpg']); %依次读取每一幅图像 i1=rgb2gray(I); %i1 灰度图像 i2=im2bw(i1); %i2 是二值图像 mi=i2(:,1,1); %取纸片左边缘 ni=a-mi; A(j,i)=sqrt(dot(ni,ni)); end end xlswrite('D:\photo2.xls',A,'A1:S19'); %将矩阵元素导入 excel 表格 %判断相邻图片并自动连接连接 a=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];%记录和纸片右相邻的纸片 for i=1:19 k=A(i,1); a(i)=1; for j=1:19 if(k>A(i,j)) k=A(i,j); a(i)=j; end end end first=1; for i=1:19 for j=1:19 if(A(i,j)==0) first=j; %求出文件最左侧纸张 end end end str='D:\附件\附件 2\'; z= imread([str,num2str(first),'.jpg']); for m=1:18 m=1; str='D:\附件\附件 2\';
19

x = imread([str,num2str(first),'.jpg']); %记录上一张纸条 y=imread([str,num2str(a(first)),'.jpg']);%记录下一张纸条 x=z; %保存已拼接纸条 z = [x,y]; first=a(first); end imshow(z) 附录四:

图 14

附件 2 拼接图片

附录五: A=zeros(209,4); for i=1:209 %for j=1:209 str='D:\附件\附件 5\a\'; I=imread([str,num2str(i),'.jpg']);%依次读取每一幅图像 i1=rgb2gray(I);%i1 灰度图像 i2=im2bw(i1);% i2 是二值图像,不需要 a=0;b=0;c=0;d=0; j=180; if any(i2(1,:)==0) while (any(i2(j,:)==0)) a=a+1; c=c+1; j=j-1;
20

end else while (all(i2(j,:)==1)) a=a-1; c=c+1; j=j-1; end end A(i,1)=a; if any(i2(j,:)==0) while (any(i2(j,:)==0)) b=b+1; d=d+1; j=j-1; end else while (all(i2(j,:)==1)) b=b-1; d=d+1; j=j-1; end end A(i,2)=b; A(i,3)=c+d; A(i,4)=i+791; end xlswrite('D:\question1.xls',A,'A210:D418'); 附录六: %%%%%%%%%%%%%注意!!运行时将附件解压至 D 盘%%%%%%%%%%%%%% ! %%%%%%%%%%%%%该程序用来对图片的二值矩阵进行分类 A=zeros(209,5); for i=1:209 str='D:\附件\附件 3\'; I=imread([str,num2str(i),'.jpg']);%依次读取每一幅图像 i1=rgb2gray(I); %i1 灰度图像 i2=im2bw(i1); % i2 是二值图像,不需要 a=0;b=0;c=0;d=0; j=1; if any(i2(1,:)==0) while (any(i2(j,:)==0)) a=a+1; c=c+1; j=j+1; end else while (all(i2(j,:)==1)) a=a-1;
21

c=c+1; j=j+1; end end A(i,1)=a; if any(i2(j,:)==0) while (any(i2(j,:)==0)) b=b+1; d=d+1; j=j+1; end else while (all(i2(j,:)==1)) b=b-1; d=d+1; j=j+1; end end A(i,2)=b; A(i,3)=c+d; A(i,5)=i; if A(i,3)<30 A(i,4)=0; elseif A(i,3)>30&&A(i,3)<=34 A(i,4)=1; elseif A(i,3)>=40&&A(i,3)<=43 A(i,4)=2; elseif A(i,3)>=44&&A(i,3)<=48 if A(i,1)>0 A(i,4)=3; else A(i,4)=4; end elseif A(i,3)>=50&&A(i,3)<=53 if A(i,1)>0 A(i,4)=5; else A(i,4)=6; end elseif A(i,3)>55&&A(i,3)<=60 if A(i,1)>0 A(i,4)=7; else A(i,4)=8; end elseif A(i,3)>61&&A(i,3)<=66 if A(i,1)>0 A(i,4)=9; else A(i,4)=10;
22

end elseif A(i,3)>67&&A(i,3)<=70 A(i,4)=11; elseif A(i,3)>76&&A(i,3)<=78 A(i,4)=12; elseif A(i,3)>80 A(i,4)=13; end end xlswrite('D:\photo3.xls',A); 附录七: %以下程序的运行,请注意文件存放的位置!! ! %此程序运行需要时间较长,请耐心等待!! ! %请使用经格式转化器转化后的 JPG 格式图片 A=zeros(209,209); a=A(:,1);%共 209 个纸条 l=A(:,1);%共 209 个纸条 for j=1:209 str='D:\附件\附件 3\'; I=imread([str,num2str(j),'.jpg']);%依次读取每一幅图像 i1=rgb2gray(I); %i1 灰度图像 i2=im2bw(i1); % i2 是二值图像,一个 180*72 的矩阵 a=i2(:,1); %取纸片左边缘 for i=1:209 I=imread([str,num2str(i),'.jpg']); %依次读取每一幅图像 i1=rgb2gray(I); %i1 灰度图像 i2=im2bw(i1); % i2 是二值图像 mi=i2(:,72); %取纸片左边缘 ni=a-mi; A(j,i)=sqrt(dot(ni,ni)); %用以判断差距 end end xlswrite('D:\photo31.xls',A); %将矩阵元素导入 excel 表格 for i=1:209 for j=1:209 if(A(i,j)==0) l(i)=l(i)+1; end end end for i=1:209 if(l(i)>=11) i end end
23

%将矩阵导入 excel 表里

附录八: %以下程序的运行,请注意文件存放的位置!! ! %请使用经格式转化器转化后的 JPG 格式图片。 %%%%%%选取以 008 作为开始第 9 组的行排序%%%%%%% A=zeros(19,19); a=[1,8,33,46,54,57,69,71,94,127,138,139,154,159,167,175,176,197,209;]%共十九个纸条 for j=1:19 str='D:\附件\附件 3\'; s=a(j) I=imread([str,num2str(a(j)),'.jpg']);%依次读取每一幅图像 i1=rgb2gray(I); %i1 灰度图像 i2=im2bw(i1); % i2 是二值图像 t=i2(:,72); %取纸片右边缘 for i=1:19 I=imread([str,num2str(a(i)),'.jpg']); %依次读取每一幅图像 i1=rgb2gray(I); %i1 灰度图像 i2=im2bw(i1); % i2 是二值图像 mi=i2(:,1); %取纸片左边缘 ni=t-mi; A(j,i)=sqrt(dot(ni,ni)); end end %%%%%%%%判断相邻图片并自动连接%%%%%%%%%% r=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];%记录和纸片右相邻的纸片 g=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];%记录和纸片右相邻的纸片 for i=1:19 k=A(i,1); r(i)=1; for j=1:19 if(k>A(i,j)&&j~=2) k=A(i,j); r(i)=a(j); g(i)=j end end end first=2; str='D:\附件\附件 3\'; z= imread([str,num2str(a(first)),'.jpg']); for m=1:18 x=z; y=imread([str,num2str(r(first)),'.jpg']);%记录下一张纸条
24

z = [x,y]; first=g(first); end imshow(z) 附件九: %请打开图片显示窗口查看拼接结果

图 15 附件三的拼接图片

附录十:

25

图 16 附件 4 的拼接图片

附录十一: %以下程序的运行,请注意文件存放的位置!! ! %请使用经格式转化器转化后的 JPG 格式图片。 A=zeros(19,19); a=[791 1121 1260 1410 1560 1510 1841 1751 1110 670 1090 191 300 1901 821 1651 210 480 1371 900 111 370 771 1790 450 261 1930 1251 230 1211 1450 800 150 600 611 1480 1530 60 1871 1540 851 431 310 390 1220 990 951 621 1381 460 1390 571 1321 1881 871 2011 1441 2001 121 1620 1701 1951 1741 2071 1570 350 1821 1991 880 1331 940 731 1760 980 401 840 891 1080 1501 1810 381 1920 661 1161 1671 21 1521 1711 420 711 1401 30 1631 2041 910 1150 1851 1801 1171 2080 590 1590 1980 1551 291 130 181 1031 651 2090 1430 580 250 140 1470 1721 320 2020 510 1911 931 201 171 1781 541 2030 221 1310 1640 1941 741 1600 360 1661 1960 1290 1580 1690 470 680 641 761 1680 1181 91 691 1890 1280 410 1831 1230 1730 41 81 861 1491 780 50 700 330 751 1271 1770 1860 11 811 280 1361 1420 2051 1060 241 1340 490 521 960 1611 1200 341 721 530 630 1301 1191 1020 161 2060 831 1460 101
26

1000 440 971 1100 1240 70 1050 1350 1140 271 501 921 1071 561 1040 1130 1971 551 ];%共十九个纸条 str='D:\附件\附件 5\'; I=imread([str,num2str(a(1,1)),'.jpg']);%依次读取每一幅图像 for j=2:19 str='C:\Users\Administrator\Desktop\附件 5\'; J=imread([str,num2str(a(1,j)),'.jpg']);%依次读取每一幅图像 I=[I,J]; end for i=2:11 str='D:\附件\附件 5\'; K=imread([str,num2str(a(i,1)),'.jpg']);%依次读取每一幅图像 for j=2:19 str='C:\Users\Administrator\Desktop\附件 5\'; J=imread([str,num2str(a(i,j)),'.jpg']);%依次读取每一幅图像 K=[K,J]; end I=[I;K]; end

1011

imshow(I) 附录十二:

%请打开图片显示窗口查看拼接结果

图 17 附件 5 的一面拼接图片 27

附录十三:

图 18 附件 5 的另一面拼接图片

28


相关文章:
2013年高教社杯全国大学生数学建模竞赛B题优秀论文
5.1.2 模型一的求解 本文选取附件 1 中碎纸片(中、英文)的数据,运用蚁群优化算法,利用 Matlab 软件编程(见附录一)求解,得到中文拼接复原图(见附录一) ,英文...
2013年全国数学建模竞赛本科组优秀论文 A题
2013全国数学建模竞赛本科组优秀论文 A题_工学_高等教育_教育专区。车道被占用...K a ? Kb 式中 a 、K a 表示波的前一种车流状态的流量和密度, b 、K...
2013全国数学建模竞赛B题优秀论文
2013全国数学建模竞赛B题优秀论文_学科竞赛_高中教育_教育专区。基于最小二乘法的碎纸片拼接复原数学模型 摘要 首先对图片进行灰度化处理,然后转化为 0-1 二值...
2013全国数模竞赛A题优秀论文
2013全国数模竞赛A题优秀论文2013 高教社杯全国大学生数学建模竞赛 编号专用页 ...%超过 28 的前一时间段的 lsum 值 b=28-c;%距离 28 的差值 x=b/((20...
2013全国数学建模竞赛A题国家一等奖论文
2013全国数学建模竞赛B题... 23页 1下载券 喜欢此文档的还喜欢 2013年数学建模A优秀论文... 40页 免费 2012年全国大学生数学建... 41页 1下载券 2013...
2013年全国大学生数学建模竞赛A题优秀论文
2013全国大学生数学建模竞赛A题优秀论文_理学_高等教育_教育专区。2013全国...> In polyfit at 81 a= 7.6389e-010 b= -1.3992e-007 c= 1.1402e...
2013年全国大学生数学建模竞赛B题全国一等奖论文
2013全国大学生数学建模竞赛B题全国一等奖论文_理学_高等教育_教育专区。2013全国大学生数学建模竞赛B题全国一等奖论文!碎纸片的拼接复原【摘要】 破碎文件的拼接...
2013全国数学建模大赛a题优秀论文
2013全国数学建模大赛a题优秀论文_数学_自然科学_专业资料。 车道被占用对城市...在图 b 中速度降低的影响 下,车流的堆积,使其在事故后密度持续增加,中途有...
2013年全国数学建模比赛优秀论文
h ?1 实际通行能力 C p / pcu ?h ?1 本题道路实际通行能力为 120 Cf ...全国数学建模比赛优秀论... 23页 4下载券 2013年数学建模B优秀论文... 32页...
数学建模2013B题优秀论文
数学建模2013B题优秀论文_理学_高等教育_教育专区。cumcm2013B题优秀论文!非常好...2009年全国大学生数学建... 38页 免费 2012年全国数学建模竞赛... 23页 1...
更多相关标签:
数学建模竞赛优秀论文 | 2016建模竞赛优秀论文 | 2014建模竞赛优秀论文 | 全国建模大赛优秀论文 | 全国数学建模优秀论文 | 全国数模竞赛优秀论文 | 全国数学建模竞赛 | 2016全国数学建模竞赛 |