J0228答卷.docx
《J0228答卷.docx》由会员分享，可在线阅读，更多相关《J0228答卷.docx（55页珍藏版）》请在冰点文库上搜索。
J0228答卷
基于图像边缘特征匹配的碎片拼接模型
摘要
司法物证复原、历史文献修复以及军事情报获取等领域广泛存在着破碎文件的拼接问题。
本文以三种形式的破碎文件为例，基于图像边缘特征匹配建立了碎片的拼接复原模型。
针对问题一仅纵切的规则碎片，首先提取图片的灰度矩阵，再采用Sobel算子检测得到图片的边缘特征矩阵，以边缘距离为目标函数建立碎片拼接的规划模型。
结果表明无需手动干预，可快速得到复原图见附图1、2。
对于问题二既横切又纵切的情况，可采集的边缘特征较少，匹配难度变大。
同时，由于中英文边缘差异较大，对其分别建立模型。
对于中文碎片，首先根据页边距特征拼接左边界碎片，然后根据文字行间距将碎纸片按行分为一类。
利用第一问的规划模型，将碎纸片按行拼接，从而建立基于行分类拼接的规划模型。
结果显示需要对9行复原图进行人工干预，成功匹配率为79.29%，复原图见附图3。
对于英文碎片，首先采用双三次插值法提高碎片图像像素点，采用改进的边缘距离为目标函数，拼接左边界碎片。
在此基础上，全局搜索其余碎片，建立基于单边或两边匹配的列拼接规划模型。
结果表明需要对23个碎片进行对干预，成功匹配率为89.05%，复原图见附图4。
问题三中考虑到双面文件提供信息更多，匹配过程中限制条件加强，采用匹配成功率更高的双三次插值法的拼接模型。
以双面边缘距离为目标函数，建立双面文件拼接的规划模型。
结果显示有21处需要人工干预，成功匹配率为89.99%，求解得出复原效果图见附图5。
本文的研究将对碎纸机文件的拼接复原工作提供一定借鉴。
关键词：
碎片拼接模型，图像匹配，Sobel算子，双三次插值
一．问题重述
司法物证复原、历史文献修复以及军事情报获取等领域广泛存在着破碎文件的拼接问题。
传统上，许多拼接复原工作需由人工完成，准确率较高，但效率很低。
特别是当碎片数量巨大的时候，如果依然依靠手工完成，不但耗费大量的人力物力，而且还可能对物件造成一定的损坏。
近年来，随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术代替手工操作，以提高拼接复原效率。
请根据题目背景解决以下问题：
1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法。
并根据建立的模型与算法，针对附件1、2给出的中、英文各一页文件的碎片数据进行拼接复原操作。
如果在复原过程中需要人工干预操作，请写出人工干预方式及干预的时间节点。
最终的复原结果以图片形式及表格形式来表达。
2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、4给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预操作，请写出干预方式及干预的时间节点。
3.上述两题所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。
附件5给出的是一页英文印刷文字双面打印文件的碎片数据。
请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
二．模型假设
1.假设题目所给的碎纸片完整边缘无磨损。
2.假设碎纸片的大小完全相同。
3.假设无完全空白纸片。
4.假设原文的文字都是正的，即不存在倒置的碎片。
5.假设像素灰度值的读取误差在合理可接受范围内。
三．符号说明
表1符号含义说明
符号
含义
Xm
第
个碎片的灰度矩阵
G
灰度梯度
Ym
第
个碎片的边缘矩阵
dmn
第
个碎片至第
个碎片的边缘距离
pi
第i行直接拼接结果成功匹配率
四．问题分析
问题一：
该问题是规则形状破碎文件的拼接复原问题。
由于形状轮廓完全相同，只能利用图像的边缘特征匹配技术对碎片进行拼接复原。
首先读出每张碎片的灰度矩阵，采用Sobel算子检测得到该碎片的边缘特征矩阵。
对特定的某一碎片，以边缘距离为目标函数建立图片匹配的规划模型，得到边缘特征最匹配的碎片，即为可拼接碎片。
同理，搜索每张碎片得到与其最匹配的碎片，进行拼接即可复原整个文件。
问题二：
对于既纵切又有横切的块型碎片，由于图像可提取的像素点较少，直接提取边缘特征进行相似度匹配的方法会产生很多误判，导致拼接结果准确率较低，需要改进匹配模型。
对于中文碎片，首先根据页边距留白的特征提取并拼接左边界碎纸片。
然后以此为基准，根据文字行间距具有相同的位置坐标，将每行碎纸片分为一类。
利用第一问的拼接算法，将每一行的碎纸片拼接起来，从而建立基于行分类的拼接模型。
对于英文碎片，由于英文之间的相似度更高，仅利用碎片单边匹配的行分类模型会出现更多误判情况。
因此我们首先利用双三次插值法增加图片像素点，拼接左边界碎片。
在此基础上，全局搜索其余碎片，建立基于单边或两边匹配的列拼接模型。
问题三：
由于每张碎纸片提供了双面信息，匹配过程中的限制条件加强，问题二中的距离函数在此处并不适用，因此重新定义碎纸片之间的距离函数。
采用第二问的模型，问题三的求解并非很复杂。
五．模型的建立与求解
5.1基于Sobel算子的碎片拼接复原模型
5.1.1图像灰度变换
用MatLab的imread函数[1]读取19块碎片图片，采用uint8的数据类型存储，得到每块碎片的灰度矩阵
。
5.1.2Sobel算子提取图片的边缘矩阵
在拼接碎片的过程中，如果每次直接将边缘灰度值之差最小的2块碎片拼接在一起，由于图片未经过处理，而且由于每块碎片的像素点个数为1980×72，每次拼接需要比较1980对像素点的灰度值之差，误差较大。
如果采用边缘检测算子，首先通过平滑来滤除碎片中的噪声，再提取出每块碎片中文字的边缘点，此时，碎片左右边缘中的文字边缘点值为1，其他点值为0，进行灰度值之差的比较时精度更高。
Sobel算子[2]认为邻域的像素对当前像素产生的影响不是等价的，所以距离不同的像素具有不同的权值，对算子结果产生的影响也不同。
一般来说，距离越大，产生的影响越小。
由于碎片拼接过程中，不同碎片边缘点之间的关系对拼接结果影响较大，而碎片内部点并不对结果产生直接影响。
因此，选取Sobel算子对碎片边缘图像进行处理。
ØSobel卷积
根据Sobel算子定义可以利用两个方向模板与图像进行邻域卷积来完成的算子的边缘检测。
检验水平边缘方向的模板为
，检验垂直边缘方向的模板
。
以灰度变换得到的灰度矩阵X代表原始图像，
及
分别代表横向及纵向的亮度差分近似值。
具体计算如下：
其中
表示图像
点的灰度值。
Ø边缘点的判断
图像每一个像素的横向及纵向亮度差分近似值通过（3）式结合，来计算该点灰度梯度的大小：
为了提高效率，我们使用不开平方的近似值：
若梯度
大于某一阈值，则认为该点
为边缘点。
在本题的求解过程中，阈值为Matlab软件自适应调整。
并且该点梯度方向为：
Ø提取边缘矩阵
设随机变量
其中
，
，
。
根据Sobel算法提取出碎片的边缘点，可以生成第
个碎片的边缘矩阵
。
5.1.3碎片拼接复原的规划模型的建立
对于特定的第m个碎片，定义其与剩余碎片的边缘距离
目标函数为寻找一块与特定碎片相似度最高的碎片，即寻找与特定碎片边缘距离最小的碎片，故目标函数为：
其中a，b均为定值，a=72，b=1。
（1）对第
个碎片的灰度矩阵的元素
，有
（2）根据实际意义，边缘距离须为非负值，约束为
根据上述分析，破碎文件复原总模型为
根据上述模型与算法，使用Matlab软件进行求解，拼接后的各碎片从左到右排列的结果见表2：
表2.1中文碎片复原结果表
8
14
12
15
3
10
2
16
1
4
5
9
13
18
11
7
17
0
6
表2.2英文碎片复原结果表
3
6
2
7
15
18
11
0
5
1
9
13
10
8
12
14
17
16
4
5.1.4问题一模型结果分析
通过复原图（见附图1、2）可知，基于Sobel算子的破碎文件拼接模型得到的结果完全正确，中、英文碎片的拼接成功率均为100%，且不需要进行人工干预，满足题目要求。
从算法角度来看，Sobel算法实现简单，算法时间复杂度为T（n3），用时少，加之本题数据量较小，程序运行所需时间大约为1秒。
5.2问题二中文文件拼接模型的建立与求解
5.2.1基于行分类的中文文件拼接模型的建立
仿照问题一的图像灰度变换，用MatLab的imread函数读取这209块碎片图片，采用uint8类型存储，得到每块碎片的灰度矩阵
。
由于该问的碎片较小，像素点个数仅为180×72，若进行边缘检测会使像素点更少，匹配的效果更差。
因此对于该问不再进行Sobel算子检测边缘，直接用灰度矩阵进行距离求解，找出距离最小的进行拼接。
在问题二中，破碎文件既有纵切，又有横切，且破碎图片小，若直接对全局搜索进行拼接匹配，会造成很多程序误判，得到错误结果。
为使结果更加准确，第二问的求解分步进行。
1.找出最左侧作为基准参照列
对一般的文档而言，页面的两侧会留有一定的页边距，根据这一显著特征，对209块碎片进行搜索。
得到最左列的19块碎片。
仿照第一问的左右匹配拼接，将搜索出的19块进行上下排列，复原出最左列。
将排好的最左列自上而下记为A1，A2，…，A11。
2.根据行间距以行为单位分类
以排好的最左列碎片为参照，根据页面每行的行距相同这一特征从剩余的190个碎片中选出属于每一行的碎片。
记集合
，
表示第
行的行分类集合。
3.对行的分类进行重新筛选匹配
由于像素点少，对于行分类时会出现错判情况，此时对于多于19块碎片的行筛选出最匹配的前19个碎片。
对这19个碎片采用第一问的行拼接法，匹配出正确结果；对于少于19块碎片的行，将其与之前筛选剩下的碎片混合，继续利用第一问的算法匹配。
若有必要，辅以人工干预。
直到每行完全复原。
将每行的数据以左端为基准进行整合，即可得到完整的破碎文件复原图。
其中a，b均为定值，a=72，b=1。
类似第一问，目标函数依然为寻找一块与特定碎片相似度最高的碎片，即寻找与特定碎片边距离最小的碎片，故目标函数为：
（1）对第
个碎片的灰度矩阵的元素
，有
（2）根据实际意义，距离须为非负值，约束为
根据上述分析，中文文件复原总模型为
中文文件拼接模型的过程示意图见图1。
图1中文文件拼接模型过程示意图
5.2.2基于行分类的中文文件拼接模型的算法求解
Ø左侧基准的找取
a）找出灰度矩阵前4列均为255的碎片，这些碎片就为原文档的左端。
一共11块。
b）采用类似问题一的拼接算法，对找出的11块碎片的上下端进行匹配拼接，对有问题的排列手动修改。
复原出最左列，以其为基准。
c）将排好的最左列自上而下记为A1，A2，…，A11。
Ø以行为单位分类
a）根据每块碎片对应的灰度矩阵，找出灰度值全为255的行，该行即为文档的行间，记下灰度矩阵的行下标。
b）对每块碎片记录的行下标信息进行比对，全部相同的默认为属于同一行。
记集合
，
表示第
行的行分类集合。
Ø对每行碎片进行拼接
a）若Ai元素个数为19，对于i行采用基于距离的行拼接算法进行拼接。
b）若Ai元素个数大于19，先筛选出匹配度最高的前19个碎片，对这19个碎片进行匹配拼接。
c）若Ai元素个数小于19，将Step2中筛选剩余的元素加入Ai，继续筛选出匹配度最高的前19个碎片。
对这19个碎片进行匹配拼接。
d）若有必要，对程序直接拼接结果辅以人工干预。
直到每行完全复原。
对上述模型与算法步骤进行求解，需要人工干预的节点步骤如下：
得到直接拼接结果后，对中文文档每行的人工干预措施为：
第1行：
将65插入54后。
第2行：
将162插入99后，63插入79后。
第3行：
将23插入41后，50插入191后，120插入86前，1插入87前。
第4行：
将46插入148后，88插入193后，105插入9后。
第5行：
将199插入82后。
第7行：
将84插入34后，121插入84后，58插入43前。
第9行：
将0插入174后，93插入153前，196插入32后。
第10行：
将83插入156后。
第11行：
将117插入108后，4插入117后，123插入119后。
施加人工干预后中文文件复原结果表3：
表3中文文件拼接结果表
11×（1~10）
49
54
65
143
186
2
57
192
178
118
61
19
78
67
69
99
162
96
131
79
168
100
76
62
142
30
41
23
147
191
38
148
46
161
24
35
81
189
122
103
14
128
3
159
82
199
135
12
73
160
94
34
84
183
90
47
121
42
124
144
125
13
182
109
197
16
184
110
187
66
29
64
111
201
5
92
180
48
37
75
7
208
138
158
126
68
175
45
174
0
71
156
83
132
200
17
80
33
202
198
89
146
102
154
114
40
151
207
155
140
11×（11~19）（续上表）
190
95
11
22
129
28
91
188
141
63
116
163
72
6
177
20
52
36
50
179
120
86
195
26
1
87
18
130
193
88
167
25
8
9
105
74
203
169
134
39
31
51
107
115
176
77
112
149
97
136
164
127
58
43
106
150
21
173
157
181
204
139
145
55
44
206
10
104
98
172
171
59
137
53
56
93
153
70
166
32
196
15
133
170
205
85
152
165
27
60
185
108
117
4
101
113
194
119
123
5.2.3问题二模型结果分析
定义第i行的直接拼接结果匹配成功率pi：
m为相对于正确的匹配序列，直接拼接结果的序列中正确相邻次序的个数。
若拼接完全正确，则m=18。
各行的直接拼接结果匹配成功率见表4：
表4中文文档各行直接拼接结果匹配成功率
行号
1
2
3
4
5
6
7
8
9
10
11
pi/%
88.89
72.22
55.56
72.22
83.33
100
66.67
100
77.78
88.89
66.67
图2中文文档各行直接拼接结果匹配成功率比较图
由表格可以得出，虽然不同行匹配成功率差别较大，但该种模型的平均匹配成功率为79.29%，因此只需要适当的人工干预便能完成文件拼接。
5.3基于双三次插值的英文文件拼接模型的建立与求解
5.3.1双三次插值法图像预处理
双三次插值算法[3]利用待采样点周围16个点的灰度值作三次插值，不仅考虑到4个直接相邻点的灰度影响，而且考虑到各邻点间灰度值变化率的影响。
三次运算可以得到更接近高分辨率图像的放大效果。
对于英文文件像素点非常少的情况，采用双三次插值法进行增加像素点，可以大大提高程序判断的灵敏度。
本题采用的双三次插值法基函数如下：
设
表示原图像
处像素点的灰度值。
对于一个目的像素
，其坐标通过反向变换得到的在原图中的浮点坐标为（i+u,j+v），其中i、j均为非负整数，u、v为[0,1）区间的浮点数。
根据双三次插值公式进行变换：
其中
均为矩阵，形式如下：
通过采用典型的双三次插值法对各碎纸片进行预处理，提高了图像中像素点的数目，由原来的180×72增加到了360×144，增加了边缘信息量，使后期拼接匹配过程的效果更好。
当然，还可以通过其它方式提高图像中像素点的数目，比如最近邻插值，双线性插值等。
考虑本题的需求，采用matlab自带的双三次插值法不仅速度快，精度也相对较高，英文文件拼接模型的过程示意图见图3。
图3英文文件拼接模型过程示意图
5.3.2问题二英文文件拼接模型的建立与求解
1.找出最左侧作为基准参照列
类似于中文文件，该问也根据页边距这一显著特征，对209块碎片进行搜索，由于英文页边距较大，寻找条件变为灰度矩阵前8列为255的碎片。
得到最左列的19块碎片后，将搜索出的19块进行上下排列，复原出最左列。
2.按列匹配拼接
最左端确定后，由于英文的像素点少，按列拼接除了第一行以外，其余行的每块碎片都有两个边做匹配条件，匹配成功的可能性会增大。
3.半自动干预过程
定义第m行第n列的新加碎片Q与已有碎片的距离
其中
表示第m行第n列的碎片灰度矩阵的第i行第j列的灰度值。
根据新定义的碎片距离，进行干预：
Step1：
遍历还未选入大图中的碎片，求得需填入碎片与相邻已填入碎片的距离
，选取距离的最小值，记为min；
Step2：
判短min是否大于10，如果小于10，直接将碎片拼入大图中；
Step3：
如果min大于10，程序进入断点，人工查图比较此时最小距离对应的碎片与已有碎片的拼接情况。
如果拼接结果通过人工判断符合要求，则程序继续。
如果不符合要求，查找min的次优解，重复执行此步，直到碎片符合人工判断要求；
Step4：
将以上符合要求的结果写入结果矩阵中，更新大图的信息。
重复执行Step1，直到所有的碎片都拼入图片中。
具体流程图见图2：
图4算法流程图
在前面的模型中，灰度值类型为uint8类型，但本模型定义的距离为平方，仍采用uint8类型可能会溢出，因而选用im2double函数将uint8类型的灰度值转化为double类型。
与问题一模型类似，目标函数依然为寻找最小距离的碎片，即
根据上述分析，中文文件复原总模型为
根据上述模型与算法步骤，通过Matlab软件进行求解，在以下位置进行程序上的人工干预，各位置对应替换碎片编号如表5：
表5人工干预的位置及对应的碎片
（5,2）
（8,2）
（8,3）
（9,4）
（4,5）
（1,6）
（5,6）
（5,11）
（8,6）
（8,8）
（11,8）
（4,9）
（9,11）
139
84
60
69
88
184
138
120
174
195
140
155
206
（1,12）
（1,13）
（5,13）
（1,14）
（5,14）
（4,15）
（11,16）
（7,18）
（8,18）
（8,19）
（1,14）
（5,14）
（4,15）
4
149
85
32
50
57
124
197
185
109
32
50
57
施加人工干预后，英文文件复原结果见表6：
表6英文文件复原结果表
11×（1~10）
191
75
11
154
190
184
2
104
180
64
201
148
170
196
198
94
113
164
78
103
86
51
107
29
40
158
186
98
24
117
19
194
93
141
88
121
126
105
155
114
159
139
1
129
63
138
153
53
38
123
20
41
108
116
136
73
36
207
135
15
208
21
7
49
61
119
33
142
168
62
70
84
60
14
68
174
137
195
8
47
132
181
95
69
167
163
166
188
111
144
171
42
66
205
10
157
74
145
83
134
81
77
128
200
131
52
125
140
193
87
11×（11~19）（续上表）
106
4
149
32
204
65
39
67
147
91
80
101
26
100
6
17
28
146
150
5
59
58
92
30
37
46
127
176
182
151
22
57
202
71
165
82
120
175
85
50
160
187
97
203
31
76
43
199
45
173
79
161
179
143
169
54
192
133
118
189
162
197
112
172
156
96
23
99
122
109
185
109
206
3
130
34
13
110
25
27
178
55
18
56
35
16
9
183
152
44
89
48
72
12
177
124
0
102
115
5.3.3问题二模型结果分析
对比中、英文文档的两种模型求解结果，采用双三次插值前后的匹配成功概率比较结果如表7。
表7图像处理前后比较表
是否使用双三次插值
是
否
正确匹配的概率
89.9475%
79.2936%
由表7可以看出，使用双三次插值的匹配成功概率有很大程度的提高。
因此，第三问模型仍采用基于双三次插值的英文文档拼接模型。
5.4问题三双面英文文件拼接模型
5.4.1双面英文文件拼接模型的建立与求解
仿照问题二英文文件的拼接方法，先对碎片做双三次插值处理，增加像素点。
根据页边距找出最左侧作为基准参照列，但由于正反面的碎片混合在一起，会找出22个左端碎片。
由上沿有页边距空白的特征，可得到两个左上角碎片，任意取其中一个作为正面的左上角，然后匹配拼接属于该面的左基准参照列，接着继续按列匹配。
由于碎片具有正反面，因而重新定义第m行第n列的新加碎片Q与已有碎片的距离
其中
为标记
升级会员 