数学建模B题论文.docx
- 文档编号:11506262
- 上传时间:2023-06-01
- 格式:DOCX
- 页数:22
- 大小:139.23KB
数学建模B题论文.docx
《数学建模B题论文.docx》由会员分享,可在线阅读,更多相关《数学建模B题论文.docx(22页珍藏版)》请在冰点文库上搜索。
数学建模B题论文
2013高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模竞赛网站下载)。
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛章程和参赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛章程和参赛规则,以保证竞赛的公正、公平性。
如有违反竞赛章程和参赛规则的行为,我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等)。
我们参赛选择的题号是(从A/B/C/D中选择一项填写):
B
我们的参赛报名号为(如果赛区设置报名号的话):
所属学校(请填写完整的全名):
兰州交通大学
参赛队员(打印并签名):
1.杨润华
2.于守阳
指导教师或指导教师组负责人(打印并签名):
1.雷斌
2.王履程
(论文纸质版与电子版中的以上信息必须一致,只是电子版中无需签名。
以上内容请仔细核对,提交后将不再允许做任何修改。
如填写错误,论文可能被取消评奖资格。
)
日期:
年月日
赛区评阅编号(由赛区组委会评阅前进行编号):
2013高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号(由赛区组委会评阅前进行编号):
赛区评阅记录(可供赛区评阅时使用):
评
阅
人
评
分
备
注
全国统一编号(由赛区组委会送交全国前编号):
全国评阅编号(由全国组委会评阅前进行编号):
碎纸片的拼接复原方案
摘要:
1.问题的提出
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。
传统上,拼接复原工作需由人工完成,准确率较高,但效率很低。
特别是当碎片数量巨大,人工拼接很难在短时间内完成任务。
随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。
1.1碎纸机破碎纸片的方式
据题可知对于给定的来自同一页印刷文字文件,碎纸机破碎纸片的方式分为仅纵切、即纵切又横切两种碎纸方式。
1.2碎纸片的分类
给定的碎纸片有:
(1)单面打印纸仅纵切汉字碎片;
(2)单面打印纸仅纵切英文碎片;(3)单面打印纸即纵切又横切汉字碎片;(4)单面打印纸即纵切又横切英文碎片;(5)双面打印纸即纵切又横切英文碎片。
1.3需要解决的问题
(1)对给定的来自同一页单面打印纸仅纵切汉字碎片,设计碎纸片拼接复原模型和算法,并针对附件1给出的一页中文文件的碎片数据进行拼接复原。
(2)对给定的来自同一页单面打印纸仅纵切英文碎片,设计碎纸片拼接复原模型和算法,并针对附件2给出的一页中文文件的碎片数据进行拼接复原。
(3)对给定的来自同一页单面打印纸即纵切又横切汉字碎片,设计碎纸片拼接复原模型和算法,并针对附件3给出的一页中文文件的碎片数据进行拼接复原。
(4)对给定的来自纸仅纵切英文碎片,设计碎纸片拼接复原模型和算法,并针对附件4给出的一页中文文件的碎片数据进行拼接复原。
(5)对给定的来自同一页双面打印纸仅纵切英文碎片,设计碎纸片拼接复原模型和算法,并针对附件5给出的一页中文文件的碎片数据进行拼接复原。
2.问题的分析
常规文档碎纸片计算机拼接方法一般利用碎片边缘的尖点特征、尖角特征、面积特征等几何特征,搜索与之匹配的相邻碎纸片并进行拼接,但这种基于边界几何特征的拼接方法并不适用于边缘形状及大小相同的碎纸片。
对这类边缘相似的碎纸片的拼接,理想的计算机拼接过程应与人工拼接过程类似,即拼接时不但要考虑待拼接碎纸片边缘是否匹配,还要判断碎片内的字迹断线或碎片内的文字内容是否匹配,然而由于理论和技术的限制,让计算机具备似人那种识别碎片边缘的字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。
但是利用现有的技术,完全可以获取碎片文字所在行的几何特征信息,比如文字行的行高、文字行的间距等信息,拼接碎片时如利用这些信息进行拼接,其拼接效率无疑比单纯利用边界几何特征方法要好些。
由于大多数文字文档的文字行方向和表格线方向平行且单一,如果碎片内的文字行或表格在碎片边缘断裂,那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行或表格,凭此特征可以很容易地从形状相似的多碎片中挑选出相邻碎片。
因文字行或表格线的高度特征、间距特征的识别比字迹断线识别和文字图像的理解实现起来要容易得多,利用碎片内文字行特征或表格特征拼接形状相似的碎纸片理论上是可行的。
另外由于计算机数字分析图像能力的缺陷,让计算机对碎片进行完全意义上的自动化拼接也几乎不太可能,为保证拼接的准确性,需要在拼接过程中加入人工干扰过程,考查问题的题设与要求,我们必须首先观察、分析并提取附件中的碎片的字符特征,建立基于字符特征的碎片半自动拼接复原模型与算法。
3.模型的假设
假设一:
中文文件在碎切前的文字间距、行间距、汉字高度以及汉字宽度为一定值。
假设二:
英文文件在碎切前的行间距、字符高度以及字符宽度为一定值。
假设三:
碎切后的各图片中文字方向一致。
假设四:
碎切后的所有图片能够拼接成一个完成的页,没有多余碎片,也不缺少碎片。
4.定义与符号说明
各符号及其含义见表1:
表1符号含义说明
符号
含义
m,n
碎片图像的尺寸,m是图像的高度,n是图像的宽度
ms,ns
碎片子图像的尺寸,ms是子图像的高度,ns是子图像的宽度
pv
图像垂直投影
ph
图像水平投影
cent
聚类中心
r
5.模型的建立与求解
5.1问题一
5.1.1模型建立
基于假设一,计算两个拼接图像每行字符的垂直投影,判断字符垂直投影宽度是否满足一定的条件,来判别拼接是否成功;所有行都判断完后,计算拼接成功的概率,运用贝叶斯判别模型,确定拼接是否成功。
建立的模型如下:
模型一:
成功概率=(拼接成功行数/判断行数)
每行拼接成功是否成功的条件:
(1)字符垂直投影宽度小于先验值40;
(2)字符垂直投影宽度大于先验值36;
(3)每行应当有完整的两个汉字;
汉字高度36~39
行间距28~30
汉字宽度 38 字符间距6
模型二:
按照K-Means聚类算法,对各图片的文字行数进行聚类
5.1.2模型求解
第一步:
求文字行数
对附件1中19幅碎片图进行水平投影,依据假设一,得到各幅图的文字行数。
碎片图000的水平投影图如图1所示。
图1碎片图001的水平投影图
附件1各图中文字行数如表2所示。
表2附件1各图中文字行数
编号
000
001
002
003
004
005
006
007
008
009
行数
25
27
28
28
27
27
25
26
25
27
编号
010
011
012
013
014
015
016
017
018
行数
28
26
28
26
28
28
27
26
26
第二步:
聚类分析
按照碎片图中文字行数进行聚类分析,得到如表3所示聚类结果。
行数
25
26
27
28
编号
000006008
007011013017018
001004005009016
002003010012014015
第三步:
分组拼接判别
按照模型一,编写matlab程序,进行图片拼接,通过进行大量实验,得到拼接成功的概率大于80%,即为拼接成功。
在判别前,对部分特殊情况进行了处理,比如“非”等。
附件1中各分组的拼接结果如表4所示。
表
组号
1
2
3
行数
26
27
28
拼接次序
013-018-011-007-017
016-001-004-005-009
014-012-015-003-010-002
第四步:
组间拼接判别
按照第四步的拼接结果,计算出组间拼接分组,按照模型一,继续进行判别,得到最终的拼接顺序,如表6所示。
8
14
12
15
3
10
2
16
1
4
5
9
13
18
11
7
17
0
6
第五步:
生成拼接图
按照第四步得到的拼接顺序,运用matlab,生成附件1的拼接图如图2所示。
第六步:
拼接结果验证
人工对拼接好的图片进行验证,发现拼接后的文件语法通顺,拼接吻合度达到100%,说明拼接结果良好。
5.2问题二
5.2.1模型建立
基于假设二,计算两个拼接图像每行字符的垂直投影,判断字符垂直投影宽度是否满足一定的条件,来判别拼接是否成功;所有行都判断完后,计算拼接成功的概率,运用贝叶斯判别模型,确定拼接是否成功。
建立的模型如下:
模型三:
成功概率=(拼接成功行数/判断行数)
每行拼接成功是否成功的条件:
(1)字符垂直投影宽度大于先验值6,并小于33或者大于40,小于45;
(2)字符间距为2~4;
(3)每行应当有完整的两个汉字;
汉字高度36~39
行间距28~30
汉字宽度 38 字符间距6
模型四:
按照K-Means聚类算法,对各图片的文字行数进行聚类
5.2.2模型求解
第一步:
求文字行数
对附件2中19幅碎片图进行水平投影,依据假设一,得到各幅图的文字行数。
附件2各图中文字行数如表2所示。
表附件2各图中文字行数
编号
000
001
002
003
004
005
006
007
008
009
行数
29
28
30
25
25
29
30
30
28
28
编号
010
011
012
013
014
015
016
017
018
行数
28
29
28
28
28
29
26
27
29
第二步:
聚类分析
按照碎片图中文字行数进行聚类分析,得到如表3所示聚类结果。
表附件2按文字行数聚类结果
行数
25
26
27
28
29
30
编号
003004
016
017
001008009010012013014
000005011015018
002006007
第三步:
求解字母的垂直投影的特征数据
因英文字母的垂直投影宽度值变化幅度比较大,并且字母数量少,因此,从附件2中提出所有小写字母和大写字母,以及标点符号的水平投影宽度、均值和方差,如表所示。
字母
宽度
均值
方差
字母
宽度
均值
方差
9
4.8889
2.4721
m
42
9.3333
8.257
.
6
4.3333
1.0328
M
45
11.8667
10.8389
a
22
9.5
6.7312
n
28
9.4286
9.1426
A
37
7.7297
4.3947
N
39
10.5879
9.7676
b
26
11.3077
11.1347
o
24
5.7921
5.7921
c
19
8.0526
4.1962
P
27
10.8519
10.5819
d
27
11.6296
11.1395
p
27
11.6296
11.1671
e
21
9.1429
4.5748
q
26
11.6538
11.1317
E
27
11.8148
11.2698
r
18
8.4444
7.9574
f
15
12.4
11.9092
R
32
11.625
10.5303
F
26
10.8846
11.7655
s
18
9.7778
3.6389
g
25
13.6
5.909
t
15
10.8
11.8876
h
28
10.1786
12.2052
T
29
8.6552
11.9082
H
39
10.8205
12.9673
u
28
8.3929
8.7532
i
13
10.2308
12.0565
v
26
6.0385
3.7998
k
27
10.4815
11.0048
w
40
7.175
4.1131
l
12
14
16.085
y
27
7.7778
5.2208
L
28
8.4286
12.2215
Y
33
9.2424
5.6736
统计英文字母的垂直投影宽度的分布情况,大多数集中在26-28之间,具体如图所示。
英文字母垂直投影宽度分布图
第四步:
分组拼接判别
按照模型一,编写matlab程序,进行图片拼接,通过进行大量实验,得到拼接成功的概率大于85%,即为拼接成功。
然而,因英文字母的垂直宽度差别较大,并且跨度比较大,因此,在拼接判别中,出现了实际拼接不上,但通过计算,拼接成功概率很高。
对于这种特殊情况,需要人工干预。
附件2中各分组的拼接结果如表4所示。
组号
1
2
3
行数
28
29
30
拼接次序
001-009-013-010-008-012-014
015-018-011-000-005
006-002-007
第五步:
组间拼接判别
按照第四步的拼接结果,计算出组间拼接分组,按照模型一,继续进行判别,得到最终的拼接顺序,如表6所示。
3
6
2
7
15
18
11
0
5
1
9
13
10
8
12
14
17
16
4
第五步:
生成拼接图
按照第四步得到的拼接顺序,运用matlab,生成附件2的拼接图如图2所示。
第六步:
拼接结果验证
人工对拼接好的图片进行验证,发现拼接后的文件语法通顺,拼接吻合度达到100%,说明拼接结果良好。
5.3问题三
5.3.1模型建立
对于纵横都切割的情况,首先确定各碎片图中第一行文字的底部位置、文字的行数,按照第一行文字底部的位置和文字行数聚类,优先以按照第一行文字底部的位置聚类。
聚类后,按照问题一中的方法,首先拼接出行。
然后按照假设文字高度确定的条件,再逐行进行拼接。
参考问题一的建立的模型,进行求解。
5.3.2模型求解
第一步:
确定碎片图中文字的行数和第一行文字的底部位置
对附件3中,各碎片图进行水平投影,得到碎片图中文字的行数和第一行文字的底部位置。
第二步:
聚类分析
按照第一行文字的底部位置和文字行数进行聚类,优先以第一行文字的底部位置进行聚类,得到如表所示。
序号
行号
位置
序号
行号
位置
序号
行号
位置
序号
行号
位置
5
4
2
7
3
27
125
2
45
39
3
64
75
4
2
45
3
27
182
3
46
3
3
65
10
4
3
175
3
27
16
2
46
31
3
65
37
4
3
53
3
28
21
2
46
51
3
65
48
4
3
56
3
28
109
2
46
73
3
65
55
4
3
68
3
28
110
2
46
107
3
65
59
4
3
126
3
28
145
2
46
115
3
65
64
4
3
137
3
28
157
2
46
128
3
65
92
4
3
138
3
28
181
2
46
134
3
65
98
4
3
158
3
28
187
2
46
159
3
65
104
4
3
174
3
28
13
3
47
160
3
65
111
4
3
208
3
28
106
2
47
169
3
65
171
4
3
32
2
28
139
2
47
176
3
65
172
4
3
70
2
28
150
2
47
12
3
66
180
4
3
93
2
28
173
2
47
82
3
66
206
4
3
153
2
28
184
2
47
199
3
66
44
4
4
166
2
28
197
2
47
203
3
66
201
4
4
196
2
28
204
2
47
29
3
71
46
3
15
6
3
34
102
2
52
28
3
77
81
3
15
19
3
34
117
2
52
91
3
77
103
3
15
20
3
34
119
2
52
95
3
77
122
3
15
36
3
34
146
2
52
118
3
77
130
3
15
52
3
34
155
2
52
129
3
77
148
3
15
61
3
34
207
2
52
141
3
77
161
3
15
63
3
34
4
2
53
143
3
77
167
3
15
69
3
34
40
2
53
186
3
77
8
2
15
72
3
34
101
2
53
188
3
77
25
2
15
79
3
34
108
2
53
2
3
78
74
2
15
96
3
34
113
2
53
11
3
78
105
2
15
99
3
34
114
2
53
22
3
78
24
3
16
116
3
34
123
2
53
49
3
78
35
3
16
131
3
34
140
2
53
54
3
78
38
3
16
162
3
34
151
2
53
57
3
78
88
3
16
163
3
34
154
2
53
65
3
78
189
3
16
67
3
35
185
2
53
178
3
78
193
3
16
78
3
35
194
2
53
190
3
78
9
2
16
177
3
35
1
3
56
192
3
78
47
3
21
170
3
39
120
3
58
71
2
109
58
3
21
202
3
39
18
3
59
89
1
120
121
3
21
15
3
40
23
3
59
14
2
133
124
3
21
33
3
40
30
3
59
183
3
21
80
3
40
41
3
59
34
3
22
83
3
40
50
3
59
42
3
22
132
3
40
62
3
59
43
3
22
133
3
40
76
3
59
77
3
22
156
3
40
86
3
59
84
3
22
198
3
40
87
3
59
90
3
22
60
2
40
142
3
59
94
3
22
85
2
40
168
3
59
97
3
22
152
2
40
179
3
59
112
3
22
205
2
40
191
3
59
127
3
22
17
3
41
195
3
59
136
3
22
200
3
41
26
3
60
144
3
22
27
2
41
100
3
60
149
3
22
165
2
41
147
3
60
164
3
22
66
2
45
135
3
63
第三步:
拼接碎片图的各行
按照问题一中的方法,拼接碎片图中的各行。
第四步:
拼接出整个文件
将拼接好的碎片图中的各行,两两拼接,通过水平投影,判断是否拼接成功。
拼接出的顺序如表所示。
第五步:
拼接结果验证
人工对拼接好的图片进行验证,发现拼接后的文件语法通顺,拼接吻合度达到100%,说明拼接结果良好。
5.4问题四
5.4.1模型建立
结合问题二和问题三建立的模型,对问题4进行求解。
5.4.2模型求解
按照问题三模型求解的过程,进行求解。
因英文字母的垂直投影宽度在拼接判别中的局限性,可采用英文字母的垂直投影的波形,与待判别区域的垂直投影进行比较,提高判别的准确行。
各英文字母的垂直投影波形图如图所示。
a
A
b
B
c
d
e
E
f
g
h
H
i
I
J
k
l
m
M
n
N
o
p
P
r
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 论文