数学建模b题一等奖优秀论文.docx

该【数学建模b题一等奖优秀论文 】是由【立华】上传分享，文档一共【22】页，该文档可以免费在线阅读，需要了解更多关于【数学建模b题一等奖优秀论文 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Documentnumber:WTWYT-WYWY-BTGTT-YTTYU-2018GT
数学建模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、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
(2)对于碎纸机既纵切又横切的情形,设计碎纸片拼接复原模型和算法,并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
(3)对于双面打印文档,研究如何进行碎纸片的拼接复原问题。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求尝试设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果。
二、模型的基本假设
待拼接的碎纸片来自同一页印刷文字文件。
待拼接复原的碎纸片是规整的矩形。
模型中的碎纸片长度、宽度和面积都相等。
附件中照片都是同标准拍摄。
三、符号说明
表1符号说明
符号
符号说明
灰度值
红色
绿色
蓝色
矩阵
裁截距
裁截文字长度
行间距
裁截空白距离
字体高度
四、问题分析
将不规则的文档碎纸片进行拼接,一般是利用碎纸片的边缘曲线,尖点、尖角、面积等几何特征,搜索与之匹配的相邻碎纸片。但对于边缘形状相似的碎纸片,这种基于边界几何特征的拼接方法失效,拼接时不但要考虑待拼接碎纸片边缘是否匹配,还要判断碎片内的字迹断线或碎片内的文字内容是否匹配。
本问题给定的碎纸片有以下几个特点:
1、每一张碎纸片都是规整的矩形;
2、所有的碎纸片的长度、宽度都相等,形状是完全一样的;
3、每一张碎纸片里都包含着文字(汉字、英文),不存在空白的碎纸片;
4、不同的碎纸片之间没有重叠部分。
由于碎纸片的形状相同,因而不能针对碎纸片的几何特征建立数学模型;碎纸片间无重叠,也不能利用图像融合技术进行图像配准。
根据上述分析,我们考虑将图片进行数字化处理,根据每张碎纸片上的边缘文字特征进行匹配,也就是利用图片边缘文字的像素进行最优化匹配。
五、模型的建立与求解
问题一的建模与算法
由于碎纸片本身不具有体现其拼接特性的数字特征,我们需要将其数字化、矩阵化,将问题转化为矩阵之间的相关性。

利用软件,将附件中所给的BMP格式的图片转化成JPG格式,去除图片的多彩性。为了对碎纸片进行数字化,我们将图像进行灰度处理,取出图像中每一个像素点的灰度值,灰度值的大小与像素点颜色的红绿蓝成分有关。
根据文献[1],每个像素点的,即
,
其中,的取值范围是。
问题一将同一页印刷文字文件纵切为19张图片(见图1),根据实际情况,我们将每张图片设置为格式,于是,每张图片对应一个的灰度矩阵。
图1附件1未进行拼接的19张碎纸片

将图片进行灰度处理以后,每个像素的灰度值介于之间。灰度值不能直接用于文字图片的拼接,还须进行二值化处理。
将图片放入直角坐标系,规定:若点的像素灰度值大于或等于,该点用数值表示,并将其设定为白色;若点的像素灰度值小于,该点用数值表示,并将其设定为黑色。由此得到像素点的二值化函数:
其中,为预先设定的全局灰度阈值。于是,每张图片的灰度矩阵转化为下列的数字矩阵:
,
其中

1、图片左右拼接的数学模型
设分别表示左右放置的两张图片对应的数字矩阵,定义前一个矩阵的最后一列与后一个矩阵的第一列之间的偏差函数为:
其中,分别表示矩阵第列和第列的元素。
对于给定的矩阵,若存在矩阵,使得与之间的偏差函数达到最小,则称与可以匹配,此时与对应的图片可以左右拼接。
2、图片上下拼接的数学模型
类似地,设分别表示上下放置的两张图片对应的数字矩阵,定义上面矩阵的最后一行与下面矩阵的第一行之间的偏差函数为:
其中,分别表示矩阵第行和第行的元素。
对于给定的矩阵,若存在矩阵,使得与之间的偏差函数达到最小,则称与可以匹配,此时与对应的图片可以上下拼接。
我们称上述基于数字矩阵之间列(或行)距离的图片拼接模型为最小二乘法拼接复原模型。

算法思想
第一步,对附件中的19幅图片分别进行灰度处理,然后取灰度阈值,进行二值化,得到19个数字矩阵,即图片的数字化。
第二步,对上述19个数字矩阵进行检测,若存在一个矩阵的最左侧一列元素全是1,根据破碎图片的特点,则该图片即为从左边起第一张碎纸片,记为。
第三步,计算与其余18张图片对应矩阵的列偏差值。
若存在,使得达到最小,则即位第二张图片。
重复上述的步骤,依次得到所有碎纸片的排列,即可拼接成完整图片。
附件1、2的拼接复原结果
附件1和附件2的拼接顺序如下表:(附件1的算法程序见附录一,复原图片见附录二;附件2的算法程序见附录三,复原图片见附录四)
表2附件1拼接顺序
8
14
12
15
3
10
2
16
1
4
5
9
13
18
11
7
17
0
6
表3附件2拼接顺序
3
6
2
7
15
18
11
0
5
1
9
13
10
8
12
14
17
16
4
问题二的模型建立与算法

步骤一:将附件所给的BMP格式图片转换成JPG格式的图片;
步骤二:对图片进行灰度处理;
步骤三:然后进行二值化处理;
最后,得到209张图片的数字化矩阵。

对于碎纸机既纵切又横切的情形,与问题一仅纵切相比,图片变小,因而每张图片包含的信息量明显变小,如果仅利用最小二乘法,碎片之间的匹配不唯一。为了解决这个问题,我们利用聚类分析法,对碎片先进行分类。
经观察测试,原始文档碎片具有下列特点:
(1)字体大小:字体的最大高度和最大宽度一致。
(2)切割的均匀性:同方向的切割线平行,图片大小均相等,沿纵横方向按直线切割。
(3)文字的行距:文字的行间距等同,段落间距为定值。
为了对209幅图片进行聚类分析,如图2所示,我们定义聚类指标如下:
表示图片上端裁接处的字体长度,我们称之为裁截文字长度;为行间距;表示图片上端文字与切割线之间的空白距离,我们称之为裁截空白距离;为字体高度,其中,。
图2图片聚类指标示意图
令或,称为第张图片的裁截距,由图2,如,则。一般地,图片从上往下看,不同的裁截线形成的裁截文字长度不同,文字间的行间距相同,所以,如果裁接处的文字长度不相等,那么文字与空白间距之和就不相等。根据的不同取值,下面对图片进行分类。
根据二值化矩阵的特点以及文字的特征,只要存在文字,则矩阵的某一行元素一定存在0元素,且在文字之间的元素为1。如下图所示:
图3文字特征图
利用软件进行编程,将每个图片的裁截文字长度、行间距、裁截空白距离、字体高度以及裁截距的结果以的形式输出到表格之中。(程序见附录五)
按裁接距进行聚类分析,使用软件分析处理后,得到聚类中心分布图如下所示:
表4聚类中心
聚类中心
聚类
1
2
3
4
5
6
7
8
9
10
11
V1
7
52
32
120
44
58
133
64
109
69
78
根据表4所示的聚类中心,对表格中裁截距进行初步分类。得到聚类结果如下表所示:
表5每个聚类中的案例数
每个聚类中的案例数
聚类
1
2
3
4
5
6
7
8
9
10
每个聚类中的案例数
聚类
1
2
3
4
5
6
7
8
9
10
11
有效
11
有效
缺失
.000
根据聚类结果发现,并不能将图片平均分成11个组。这时需要增加信息量来更好地进行分类,进一步观察图2,我们可以发现:图片的上端裁截处可能是文字,也可能为空白。但是裁截距可能相等,此时通过图片上端裁截处是空白还是文字加以人工分类。
用将数据导出到中并进行分析,结果如下:
-100
-50
0
50
0
50
100
150
200
250
高度
图片数量
图4分析结果
由图4可以看出:图片大体分为11个组别,为了得到更精确地聚类结果,通过软件,我们再次确立聚类中心如下图所示:
表6第二次聚类中心
最终聚类中心
聚类
1
2
3
4
5
6
7
8
9
10
11
V1
25
2
40
-38
-93
-69
-84
15
34
-23
-10
通过上面两次聚类,确立了两个不同聚类中心。利用第一次确立的裁接距的聚类中心对图片进行初步分类,然后利用裁截文字或者裁接空白再次进行判别,最终将图片分成了11组。如下表所示:(以上的算法都是在软件下操作,程序见附件六)
表7各组图片数量
组别
0
1
2
3
4
5
6
7
8
9
10
11
12
13
图片数量
3
18
8
19
19
18
18
19
18
18
18
10
19
3
由上表可以看出大部分图片已经分出组别,其中有4个组达到了19张图片,有6个组有18张图片,仅缺少一张图片。此时我们进行人工干预,根据每组图片总数目应为19,且每类都应存在可作为文件左右边缘的碎纸片,我们对少量图片进行归类可得到如下分组结果。如下表:
表8聚类后的结果
组别
1
2
3
4
5
6
7
8
9
10
11
图
片
编
号
2
6
1
8
3
34
13
5
0
15
4
11
19
18
9
12
42
16
10
7
17
40
22
20
23
24
14
43
21
29
32
27
89
28
36
26
25
31
47
66
37
45
33
101
49
52
30
35
39
58
106
44
53
60
102
54
61
41
38
51
77
109
48
56
71
108
57
63
50
46
73
84
110
55
68
80
113
65
67
62
74
82
90
125
59
70
83
114
91
69
76
81
107
94
139
64
93
85
117
95
72
86
88
115
97
145
75
126
132
119
118
78
87
103
128
112
150
92
137
133
123
129
79
100
105
134
121
157
98
138
152
140
141
96
120
122
135
124
173
104
153
156
146
143
99
142
130
159
127
181
111
158
165
151
178
116
147
148
160
136
182
171
166
170
154
186
131
168
161
169
144
184
172
174
198
155
188
162
179
167
176
149
187
180
175
200
185
190
163
191
189
199
164
197
201
196
202
194
192
177
195
193
203
183
204
206
208
205
207
、算法与求解
算法思想
下面我们分两步来做,第一步,对每组碎纸片进行拼接;第二步,将各组进行拼接。最终完成文件复原。
在已知文件切为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组的拼接结果,这里我们不在一一赘述,发现每组的拼接均无误,这说明我们的分类达到了预期的效果。
图片的整体拼接
上一步骤中我们得到了11×19的碎纸片拼接而成的11个等大小的纸片,那么接
下来,根据行偏差函数,判断11个纸片的上下拼接顺序,可以得到以下编号的图片可以上下拼接:
完成以上组合的拼接后,进行人工干预,完成图片的整体拼接,结果如下(复原图片详见附录九):
表9附件3拼接顺序
049
054
065
143
186
002
057
192
178
118
190
095
011
022
129
028
091
188
141
061
019
078
067
069
099
162
096
131
079
063
116
163
072
006
177
020
052
036
168
100
076
062
142
030
041
023
147
191
050
179
120
086
195
026
000
087
018
038
148
046
161
024
035
081
189
122
103
130
193
088
167
025
008
009
105
074
014
128
003
159
082
199
135
012
073
160
203
169
134
039
031
051
107
115
176
094
034
084
183
090
047
121
042
124
144
077
112
149
097
136
164
127
058
043
125
013
182
109
197
016
184
110
187
066
106
150
021
173
157
181
204
139
145
029
064
111
201
005
092
180
048
037
075
055
044
206
010
104
098
172
171
059
007
208
138
158
126
068
175
045
174
001
137
053
056
093
153
070
166
032
196
071
156
083
132
200
017
080
033
202
198
015
133
170
205
085
152
165
027
060
089
146
102
154
114
040
151
207
155
140
185
108
117
004
101
113
194
119
123
对于附件4,我们按照与处理附件3相同的模型和算法进行处理,得到拼接结果表格如下,(复原图片详见附录十):
表10附件4拼接顺序
191
075
011
154
190
184
002
104
180
064
106
004
149
032
204
065
039
067
147
201
148
170
196
198
094
113
164
078
103
091
080
101
026
100
006
017
028
146
086
051
107
029
040
158
186
098
024
117
150
005
059
058
092
030
037
046
127
019
194
093
141
088
121
126
105
155
114
176
182
151
022
057
202
071
165
082
159
139
001
129
063
138
153
053
038
123
120
175
085
050
160
187
097
203
031
020
041
108
116
136
073
036
207
135
015
076
043
199
045
173
079
161
179
143
208
021
007
049
061
119
033
142
168
062
169
054
192
133
118
189
162
197
112
070
084
060
014
068
174
137
195
008
047
172
156
096
023
099
122
090
185
109
132
181
095
069
167
163
166
188
111
144
206
003
130
034
013
110
025
027
178
171
042
066
205
010
157
074
145
083
134
055
018
056
035
016
009
183
152
044