年全国大学生数学建模竞赛B题碎纸片的拼接复原.docx
- 文档编号:18006230
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:46
- 大小:117.47KB
年全国大学生数学建模竞赛B题碎纸片的拼接复原.docx
《年全国大学生数学建模竞赛B题碎纸片的拼接复原.docx》由会员分享,可在线阅读,更多相关《年全国大学生数学建模竞赛B题碎纸片的拼接复原.docx(46页珍藏版)》请在冰点文库上搜索。
年全国大学生数学建模竞赛B题碎纸片的拼接复原
2013高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模竞赛网站下载)。
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛章程和参赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛章程和参赛规则,以保证竞赛的公正、公平性。
如有违反竞赛章程和参赛规则的行为,我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等)。
我们参赛选择的题号是(从A/B/C/D中选择一项填写):
B
我们的参赛报名号为(如果赛区设置报名号的话):
所属学校(请填写完整的全名):
西华大学
参赛队员(打印并签名):
1.杨尚安
2.刘洋
3.叶军
指导教师或指导教师组负责人(打印并签名):
(论文纸质版与电子版中的以上信息必须一致,只是电子版中无需签名。
以上内容请仔细核对,提交后将不再允许做任何修改。
如填写错误,论文可能被取消评奖资格。
)
日期:
2013年09月15日
赛区评阅编号(由赛区组委会评阅前进行编号):
2013高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号(由赛区组委会评阅前进行编号):
赛区评阅记录(可供赛区评阅时使用):
评
阅
人
评
分
备
注
全国统一编号(由赛区组委会送交全国前编号):
全国评阅编号(由全国组委会评阅前进行编号):
碎纸片的拼接复原
摘要
本文通过分析题中相关要求及条件,建立数学模型解决了各种规则碎纸片的拼接复原问题。
针对问题一,首先将题中所给图片导入matlab软件,利用imread函数得到每张图片的文字灰度像素矩阵,再取出所有矩阵左、右列,建立像素绝对差拟配模型,得到拟配程度最高的两幅图片,进行拼接,出现不合理拼接情况则进行人工干预,最后重复上述过程,完成全部拼接并导出图像。
针对问题二,首先将全部碎片导入matlab软件,经过处理得到每张碎片中符号距离碎片上下端的像素位,再根据分类聚类思想,利用excel表格处理,将所有具有“相同”像素位的图片分为一组,得到11个分组,然后在每一个分组中建立左右连接点数目最匹配模型,再配合人工干预,将所有碎片拼接为一行图像,最后将这11行图像利用问题一中模型拼接为最终图像并打印结果。
针对问题三,首先建立一种基于K-Means局部最优性的高效聚类模型,然后根据模型利用matlab,将所给图片全部导入分类,分好类并人工调整补充后再利用matlab在每一组分类中利用问题二模型在人工干预情况下得出原始图像并打印结果。
关键词:
像素绝对差拟配模型左右连接点数目最匹配模型人工干预
一、问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。
传统上,拼接复原工作需由人工完成,准确率较高,但效率很低。
特别是当碎片数量巨大,人工拼接很难在短时间内完成任务。
随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。
请讨论以下问题:
1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预,请写出干预方式及干预的时间节点。
复原结果以图片形式及表格形式表达(见【结果表达格式说明】)。
2.对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预,请写出干预方式及干预的时间节点。
复原结果表达要求同上。
3.上述所给碎片数据均为单面打印文件,从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决。
附件5给出的是一页英文印刷文字双面打印文件的碎片数据。
请尝试设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果,结果表达要求同上。
二、模型假设
1、假设全部碎纸片边缘光滑
2、假设字符色调一致
3、假设字符间距相同,没有特殊情况
4、假设除字符外,页面没有其他地方具有任何色彩
5、假设英文字符书写标准,大小写字号均相同
三、符号说明
表示灰色像素矩阵
表示灰色像素矩阵的列数
表示灰色像素矩阵的行数
表示第几个碎片
表示某个像素点
表示某灰度像素点为黑色还是白色
表示灰色像素矩阵最右边列
表示灰色像素矩阵最左边列
表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值的和
四、模型建立与求解
4.1问题一
4.1.1问题分析
整体来看,本问题要求利用数学模型,改原有手动拼接技术为自动或半自动拼接技术,完成题中所给的相应碎纸片的拼接复原工作。
具体操作,考虑所给碎纸片内容仅有汉字或英文,而没有颜色、大小、字形之分。
因此,只能利用碎纸片中相应的文字特征进行操作,考虑碎纸片扫描进入在计算机后是以图片的形式存在,而图片又是以像素的情况组成。
所以,首先可将图片导入matlab中,以其像素为基点,得到每个图片的像素矩阵,每一像素矩阵即可表示该图片的特征。
为了利用图片像素矩阵完成图片的拼接,考虑问题一只是将原图分为了19列,每一列具有1980像素,首先可根据左端全为空白,找出原图最左一列碎片,然后利用拼接好的图片最右列像素点去匹配未拼接图片的最左列像素点,使得拼接最为吻合的即为需要拼接的图片,然后拼接,再重复上述过程,直到拼接完成。
具体操作流程如下:
图1问题一解答流程图
4.1.2数据处理
将图片导入matlab中,然后编写程序(具体代码见附录1),可得每个碎纸片灰度像素矩阵(碎片000局部像素点如下)。
图2碎片000局部灰度像素点列
4.1.3像素绝对差拟配模型建立
令碎片导入matlab编程计算所得的灰色像素矩阵为:
由于碎片像素为72*1980,因此矩阵
也是72*1980的,矩阵每一列数据即为碎片相应列像素值,其中每个像素点
表示此处为黑色或白色,用
表示某灰度像素点为黑色还是白色,即:
令
表示灰色像素矩阵最右边列,那么
令
表示灰色像素矩阵最左边列,则
令
表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值的和。
那么有
根据上述模型即可确定某一碎片灰度像素矩阵最右边列与其余未拼接碎片最左边列的绝对差值,下面讨论因差值不同而产生的匹配问题。
1、最左列的确定:
当出现某一碎片灰度像素矩阵最左列均为255时,那么说明该碎片为原始图像的最左列。
2、假设出现
情况,那么首先将
对应的碎片与该基准碎片进行拼接,若拼接不合适,这时就需要人工干预,换
对应的碎片与基准碎片进行拼接。
情况如下:
这是不确定的,而进行人工干预选择
对应的碎片后,将会出现下面情况:
这样就能正确的完成两个碎片的拼接。
3、假设出现
情况,这与上述情况相同。
因此,人工干预方式及时间选择也相同。
4.1.4像素绝对差拟配模型求解
对于附件一中碎片复原,根据上述模型,利用matlab软件,求解可得008碎片最左端矩阵列与006碎片最右端矩阵列均为:
,因此,可知008碎片为复原图最左一个碎片,006碎片为复原图最右端碎片。
其余求得所有最小的距离
的值,根据
的值,可将碎片进行复原。
复原结果如下表,复原图像见附录2。
008
014
012
015
003
010
002
016
001
004
005
009
013
018
011
007
017
000
006
表1问题一中文复原表格序列
对于附录二英文复原,与上求解过程雷同,利用matlab可得复原结果如下表,复原图像见附录3。
003
006
002
007
015
018
011
000
005
001
009
013
010
008
012
014
017
016
004
表2问题一英文复原表格序列
4.1.5问题一综合分析
综上所述,对于问题一的求解过程,未使用人工干预。
本文除使用对问题所给的碎片进行复原外,同时对具有相同属性的其他图形碎片也进行了复原,效果良好,模型稳定,可推广到所有只进行竖切的文档恢复。
4.2问题二——中文碎片复原
4.2.1问题分析
综合分析。
由于考虑问题二在问题一的基础上将碎片分的更加的细小,那么碎片的灰色像素矩阵数据在原有的基础上将会变得少很多,考虑使用问题一方法及模型,那么首先就要构造出与问题一相同的19个竖碎片,因此考虑将所有碎片分为19组,但经过试验分为19组后,由于空白出现太多,在每组中将11个碎片拼接在一起是相当困难的。
因此,转变思想,考虑将所给所有碎片分为11个组,在每个分组中将19张碎片拼接在一起,然后在将11个分组拼接在一起完成最后解答。
具体操作。
要想将11*19张图片分为11组,考虑文字具有行高的性质,分组中所拼接的19张碎片,所有文字具有的行高应该都是相同的。
根据这一思想,可将所有碎片导入matlab中,编程计算可得每张碎片符号距离碎片上下端的像素位,并将所有结果导入excel中,然后根据分类与聚类思想,利用excel表格处理,将碎片符号距离碎片上下端的像素位“相同”(不是绝对相等,允许误差前后波动两个像素)的点分为一组,对于出现空白位置误差较大的点可根据单边距离进行分类与聚类,若根据单边无法确定具体分入那组,那么就同时分入可能的分组中。
分组完成后那么每个分组中的图片定能拼接为一行图片,那么我们可建立左右连接点数目最匹配模型,结合人工干预,将每个分组中图片拼接在一起。
最后利用问题一中模型可将11个分组拼接在一起得到原图。
具体流程如下图:
图3问题二解答流程图
4.2.2数据处理
将209张碎片导入matlab中,编程得到每张碎片灰色像素矩阵,然后在利用矩阵编写程序得到每张碎片字符距离上下边界的像素位,并将其导入excel中(具体代码见附录4),下表为000至016结果:
(其余碎片结果见附录5)
碎片编号
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
上距离
0
22
37
25
12
0
0
0
0
0
0
39
25
8
93
1
6
下距离
15
0
0
0
58
0
9
15
96
0
0
0
0
0
0
3
0
表3碎片字符距离上下边界的像素位情况表
得到像素位上下边缘距离后可根据上下距离“相等”(不是绝对相等,允许误差前后波动两个像素)原则,利用excel表格处理将所给数据分为11组。
其中距上边缘距离为0,下边缘距离为21的一个分组为下表:
(其余分组见附录6)
34
42
43
47
58
77
84
94
97
183
90
136
112
127
124
121
144
149
164
表4某一属于同行碎片的分组情况表
在每一分组内,再利用matlab编程计算每张碎片左端与右端具有的可连接点数目(采用四舍五入原则)(具体代码见附录7),下表为上一分组数据的左右连接点数目:
(其他分组连接点数目见附录8)
4(34)7
3(42)6
4(43)0
6(47)3
5(58)3
4(77)2
7(84)0
0(94)4
9(97)3
1(183)9
9(90)6
3(136)3
3(112)7
5(127)6
6(124)5
3(121)3
5(144)4
7(149)9
3(164)5
表5某一同行碎片的左右连接点数目情况表
4.2.3左右连接点数目最匹配模型
本模型属于半自动模型,需人工干预,具体步骤如下:
1、选取任一分组左右连接点数目情况表,观察左右连接点数;
2、选取左端连接点数目为0的碎片作为最左端碎片,并将该图片作为基准图片;
3、观察基准图片右端连接点数目,从未拼接图片左端连接点数目中找寻与该数目最接近的碎片,人工控制,观察是否可连接。
若可连接则拼接上,并将新拼接上碎片作为基本图片,若不可连接,则重新找寻符合要求的碎片,观察是否可连接;
4、重复3步骤,直到将图片全部连接完成。
4.2.4模型求解
以上述模型为标准,考虑数据处理中那行连接过程。
首先,寻找19个点钟左端连接数为0的点,找到(94)号碎片,将其作为基准图片,观察其右边连接点数为4,从其余碎片中找寻发现(34)(43)(77)左端连接数均为4,因此,通过人工干预,观察图片字样走势发现只有(34)号碎片符合要求,再将(34)号图片作为基准图片,其右端连接点数为7,从未连接碎片中找寻发现(84)(149)号均为7,同理(84)碎片作为基准图片,以此类推即可得到该分组图片排序为:
(94)(34)(84)(183)(90)(47)(121)(42)(124)(144)(77)(112)(149)(97)(136)(164)(127)(58)(43)其具体碎片拼接图形如下:
然后根据上述模型,以相同的办法结合附录6中分组情况即可将全部11个分组中图片的连接情况找出,然后利用问题一中像素绝对差拟配模型即可拼接处原图,得到原图表格连接情况如下,具体图像见附录9。
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
001
087
018
038
148
046
161
024
035
081
189
122
103
130
193
088
167
025
008
009
105
074
071
156
083
132
200
017
080
033
202
198
015
133
170
205
085
152
165
027
060
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
000
137
053
056
093
153
070
166
032
196
089
146
102
154
114
040
151
207
155
140
185
108
117
004
101
113
194
119
123
表6汉字碎片拼接情况表
由于解决本问题使用的左右连接点数目最匹配模型,属于半自动模型。
因此,对本文的恢复进行了人工干预。
恢复此中文文档,本模型一共进行了9次人工干预。
干预方式为:
终止程序继续运行,将程序拼接过程恢复至上一步(出现碎片拼接不吻合时的前一步),然后将程序用于拼接的碎片导出,再恢复程序继续运行,找到该步拼接吻合碎片并拼接后,再将导出碎片重新导入继续运行程序。
干预时间节点:
干预时间节点即对每行碎片单独拼接时,出现碎片拼接不吻合情况时的节点。
4.3问题二——英文碎片复原
对于附录四英语碎片恢复,由于英文与汉字写法不同,英语中弧线居多,而汉字中直线居多。
因此,可以采用另一种方式对英文碎片进行拼接,依然考虑问题一中的像素绝对差拟配模型,可首先任意选择一张基础碎片,然后利用该模型进行适应性匹配,匹配过程中加以人工干预。
具体操作流程如下:
图4英文碎片复原流程图
4.3.2模型建立
1.1像素绝对值拟配模型
令碎片导入matlab编程计算所得的灰色像素矩阵为:
由于碎片像素为72*180,因此矩阵
也是72*180的,矩阵每一列数据即为碎片相应列像素值,其中每个像素点
表示此处为黑色或白色。
令
表示灰色像素矩阵最右边列,那么
令
表示灰色像素矩阵最左边列,则
令
表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值的和。
那么有
根据上述模型即可确定某一碎片灰度像素矩阵最右边列与其余未拼接碎片最左边列的绝对差值,下面讨论因差值不同而产生的匹配问题。
1、最左列的确定:
当出现某一碎片灰度像素矩阵最左列均为255时,那么说明该碎片为原始图像的最左列。
2、假设出现
情况,那么首先将
对应的碎片与该基准碎片进行拼接,若拼接不合适,这时就需要人工干预,换
对应的碎片与基准碎片进行拼接。
情况如下:
这是不确定的,而进行人工干预后将会出现下面情况:
这样就能正确的完成两个碎片的拼接。
3、假设出现
情况,这与上述情况相同。
因此,人工干预方式及时间选择也相同。
1.2人工干预
在进行像素绝对值拟配模型计算后,将会得到与基准碎片拼接度最大的几个碎片,然后利用这几个碎片可进行人工干预,具体人工干预模型如下:
1、首先将程序计算得到的拟配程度最大的碎片与基准碎片进行拼接;
2、人工判断拼接是否合理;
3、若拼接合理则进行下一次拟配模型计算,若拼接不合理则找寻第一步中与基准碎片拟配差一点的碎片进行拼接;
4、直到找到拼接成功的点才结束本次拼接,并将新拼接上的图片作为基本图片利用模型寻找拟配度最高的碎片,返回第一步。
结合上述模型1.1及1.2可计算得到问题二英文碎片复原图表格如下,具体图像见附录10
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
049
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
081
077
128
200
131
052
125
140
193
087
089
048
072
012
177
124
000
102
115
表7问题二英文碎片复原图表格表示
由于英文碎片相似程度高于中文图片。
所以每一次以基准图片找寻最佳匹配图形时很多时候出现多张图片符合匹配,因此,对此英文碎片的恢复进行了人工干预。
恢复此英文文档,本模型一共进行了39次人工干预。
干预方式为:
终止程序继续运行,将程序拼接过程恢复至上一步(出现碎片拼接不吻合时的前一步),然后将该步程序用于拼接的碎片导出,再恢复程序继续运行,直到找到与该基准碎片拼接吻合碎片并拼接完成。
干预时间节点:
当出现与基准碎片匹配不吻合时。
4.3问题三
4.3.1问题分析
考虑问题三附录中所给图片具有正反面,却不知每一个序号中a是正面还是b是正面,这也真是问题二英语复原与问题三双面复原的区别。
因此,问题二中所用的分类与聚类的方法不能完成分组。
为了完成分组,我们可考虑使用一种更加严密,严苛的分类方法,只要分类完成,那么再使用问题二连接图片的办法即可实现图片的复原。
4.3.2模型建立
许多聚类算法的基本框架是搜索与合并。
如在层次方法中需要搜索两个距离最近的类簇然后合并;而基于密度的聚类算法则不断地搜索高密子区域,然后利用连通性将其合并到当前聚类结果中。
很明显,搜索过程需要面对整个样本集合,通常会导致算法低效。
如DBSCAN需要测试每个对象是否是核心对象,并对每个核心对象搜索其直接密度可达的对象,如果没有空间索引的辅助,DBS
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国大学生 数学 建模 竞赛 纸片 拼接 复原