+\
碎纸片的拼接复原
【摘要】：碎纸片拼接技术是数字图像处理领域的一个重要研究方向，把计算机视觉和程序识别应用于碎纸片的复原，在考古、司法、古生物学等方面具有广泛的应用，具有重要的现实意义。本文主要结合各种实际应用背景，针对碎纸机绞碎的碎纸片，基于计算机辅助对碎纸片进行自动拼接复原研究。
针对问题1，依据图像预处理理论，通过matlab程序处理图像，将图像转化成适合于计算机处理的数字图像，进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵A1，提取每个灰度矩阵的最后一列，生成新矩阵B1。建立碎纸片匹配模型:
dai,bj=t=0m-1bti-atj2 ，其中i，j=0,⋯n-1。
p=0≤i≤n-10≤j≤m-1mind(ai,bj)
将矩阵A1中的任一列与矩阵B1中的每一列带入模型，所得p值对应的i ,j值，即为所拼接的碎片序列号。将程序进行循环操作，得到最终的碎片自动拼接结果。
针对问题2，首先将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列和最后一列，分别生成新矩阵A2、B2；提取所有灰度矩阵的第一行和最后一行，分别作为新生成的矩阵C2、D2。由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型：
dai,bj=t=0m-1btj-ati2 ，其中i，j=0,⋯n-1。
dci,dj=s=0n-1dsj-asi2 ，其中i，j=0,⋯m-1。
p=0≤i≤n-10≤j≤m-1mind(ai,bj)，q=0≤i≤n-10≤j≤m-1mind(ci,dj)
将矩阵A2中的任一列分别与矩阵B2中每一列代入模型，所得p值对应的i ,j值即为横排序；将矩阵C2中的任一行分别于矩阵D2中的任一行代入模型，所得q值对应的i ,j值即为列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。
针对问题3，基于碎纸片的文字行列特征，采用遗传算法，将所有的可能性拼接进行比较，进行择优性选择。反面的排序结果用于对正面排序的检验，发现结果有误差，此时，进行人工干预，调换碎纸片的排序。
【关键词】: 灰度矩阵 欧式距离 图像匹配 自动拼接 人工干预
一、 问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，大量的纸质物证复原工作都是以人工的方式完成的，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接不但耗费大量的人力、物力，而且还可能对物证造成一定的损坏。随着计算机技术的发展，人们试图把计算机视觉和模式识别应用于碎纸片复原，开展对碎纸片自动拼接技术的研究，以提高拼接复原效率。试讨论一下问题，并根据题目要求建立相应的模型和算法：
1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。
2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。
3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
结果表达格式说明：
复原图片放入附录中，表格表达格式如下：
(1) 附件1、附件2的结果：将碎片序号按复原后顺序填入119的表格；
(2) 附件3、附件4的结果：将碎片序号按复原后顺序填入1119的表格；
(3) 附件5的结果：将碎片序号按复原后顺序填入两个1119的表格；
(4) 不能确定复原位置的碎片，可不填入上述表格，单独列表。
二、问题分析
碎纸片自动拼接技术是图像处理与识别领域中的一个较新但很典型的应用，是通过扫描和图像提取技术获取一组碎纸片的信息，然后利用计算机进行相应的处理，从而实现对这些碎纸片的全自动或半自动的拼接复原。碎纸片的自动拼接可以近似地看作是一个拼图问题。在机器人和计算机视觉领域中，很早就有学者对自动拼图进行了研究[1，2]。但是这些技术都利用了拼图游戏中的一些特殊特征及一些先验知识，而在许多实际应用中都不能满足这些条件。
根据待拼接图像（输入）与拼接图像（输出）的不同类型[3]，可以将图像拼接分为四类：基于静态图像的静态图像拼接、基于静态图像的动态图像拼接、基于视频的序列的静态图像拼接和基于视频序列的动态图像拼接。本文主要致力于静态图像的静态图像拼接，即碎纸机绞碎的规则的碎纸片的自动拼接。
问题1：
根据图像预处理理论，通过程序语言将图像导入matlab程序，对图像进行预处理，将碎纸片转换成适合于计算机处理的数字图像形式，并对数字图像进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵A，提取每个灰度矩阵的最后一列，作为新矩阵B。建立碎纸片匹配模型。根据遗传算法的思想，将矩阵A中的任一行与矩阵B中的每一行带入模型，由最大相似性原理得s值对应的i ,j值，即为所拼接的碎片序列号。将程序进行循环操作，并最终建立对输入的解释。
问题2：
首先对碎纸片图像进行预处理，通过matlab程序将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列，生成新矩阵A2，提取最后一列，结合生成新矩阵B2；提取所有灰度矩阵的第一行，作为新生成的矩阵C2，提取最后一行，作为新矩阵D2。由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型。将矩阵A2中的任一列分别与矩阵B2中每一列代入模型，所得p值对应的i ,j值即为横排序；将矩阵C2中的任一行分别于矩阵D2中的任一行代入模型，所得q值对应的i ,j值即为列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。
问题3：
针对双面打印文件的碎纸片拼接处理，首先要对碎纸片两面的图像信息都进行图像预处理，运用matlab程序提取图像的灰度矩阵。基于碎纸机绞碎的碎纸片，每个碎纸片的大小是一样的,采用差距度量法。取矩阵中特征值从第一行中开始到限制条件取i行，限制条件是当取到i行时满足每行都是特征值的矩阵还有2m个矩阵，则这2m个矩阵为同一行碎片所产生的矩阵。包括正反面碎纸片。然后取其中矩阵左边列向量满足，此行矩阵所剩两个矩阵，此过程虽然误差较小，针对其他问题可能要产生误差，需要人工干预，剔除多余矩阵。然后取出两个中的一个矩阵，与产生的这一行矩阵进行匹配，获取一行排序较优的碎片链接。运用嵌套循环实现每行的排序连接。
三、符号说明
m
提取灰度矩阵行（列）生成的新矩阵的行数
n
提取灰度矩阵行（列）生成的新矩阵的列数
A
提取灰度矩阵第一列生成的新矩阵
B
提取灰度矩阵最后一列生成的新矩阵
C
提取灰度矩阵第一行生成的新矩阵
D
提取灰度矩阵最后一行生成的新矩阵
d(ai,bj)
矩阵A中第i列与矩阵B中第j列的欧氏距离
d(ci,dj)
矩阵C中第i行与矩阵D中第j行的欧氏距离
四、模型假设
1） 同一切线处的两条边界灰度值的差别在误差范围之内。
2） 所有的待拼接的碎纸片都是规则的。
3） 假设不存在文件缺失、人为因素等意外因素。
4） 假设所有的数字图像文件都是已整理好的，不需要再进行旋转、剪裁等操作。
五、模型建立与问题解决
首先，对碎纸片图像进行预处理。由于基于文字的数字图像中文字和背景的灰度值存在明显差异，运用程序把已整理好的数字图像依次导入matlab软件，根据图像显示技术，提取其灰度矩阵，改变数字图像的视觉效果，将数字图像转化成一种更适合于计算机进行分析处理的数据形式。再者，本文涉及的是无重叠的规则碎纸片拼接，因此只需处理每一张碎纸片的边缘交界处的数据，应用matlab程序对灰度矩阵进行边界数据的提取，减少了数据的处理量，为碎纸片的自动拼接节省了时间。然后，对所提取的每组数据进行相似性度量，采用二维欧式距离，即：
dai,bj=t=0m-1bti-atj2 ，其中i，j=0,⋯n-1。
根据遗传算法，将提取的所有待拼接碎纸片的边界数据进行分别左右、上下交叉的两两匹配，根据最大相似性原则，建立匹配准则：
p=0≤i≤n-10≤j≤m-1mind(ai,bj)
所得p值对应的i ,j值即为拼接序列。
5.1 问题一
我们依据图像预处理理论，通过matlab程序处理图像，将图像转化成适合于计算机处理的数字图像，并对数字图像进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵A1，提取每个灰度矩阵的最后一列，生成新矩阵B1。建立碎纸片匹配模型:
dai,bj=t=0m-1bti-atj2 ，其中i，j=0,⋯n-1。
p=0≤i≤n-10≤j≤m-1mind(ai,bj)
将矩阵A1中的任一列与矩阵B1中的每一列带入模型，所得p值对应的i ,j值，即为所拼接的碎片序列号。将程序进行循环操作，得到最终的碎片自动拼接结果。
附件1的碎纸片复原结果为：
表-1
008
014
012
015
003
010
002
016
001
004
005
009
013
018
011
007
017
000
006
附件2的碎纸片复原结果为：
表-2
003
006
002
007
015
018
011
000
005
001
009
013
010
008
012
014
017
016
004
5.2 问题二
根据图像预处理理论，首先将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列，生成新矩阵A2，提取最后一列，结合生成新矩阵B2；提取所有灰度矩阵的第一行，作为新生成的矩阵C2，提取最后一行，作为新矩阵D2。由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型：
dai,bj=t=0m-1btj-ati2 ，其中i，j=0,⋯n-1。
dci,dj=s=0n-1dsj-asi2 ，其中i，j=0,⋯m-1。
p=0≤i≤n-10≤j≤m-1mind(ai,bj)，q=0≤i≤n-10≤j≤m-1mind(ci,dj)
将矩阵A2中的任一列分别与矩阵B2中每一列代入模型，所得p值对应的i ,j值即为横排序；将矩阵C2中的任一行分别于矩阵D2中的任一行代入模型，所得q值对应的i ,j值即为列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。
附件3的碎纸片复原结果为：
表-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
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
附件4的碎纸片复原结果为：
表-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
081
077
128
200
131
052
125
140
193
087
089
048
072
012
177
124
000
102
115
5.3问题三
针对双面打印文件的碎纸片拼接处理，首先要对碎纸片两面的图像信息都进行图像预处理，运用matlab程序提取图像的灰度矩阵。基于碎纸机绞碎的碎纸片，每个碎纸片的大小是一样的,采用差距度量法。取矩阵中特征值从第一行中开始到限制条件取i行，限制条件是当取到i行时满足每行都是特征值的矩阵还有2m个矩阵，则这2m个矩阵为同一行碎片所产生的矩阵。包括正反面碎纸片。然后取其中矩阵左边列向量满足，此行矩阵所剩两个矩阵，此过程虽然误差较小，针对其他问题可能要产生误差，需要人工干预，剔除多余矩阵。然后取出两个中的一个矩阵，与产生的这一行矩阵进行匹配，获取一行排序较优的碎片链接。运用嵌套循环实现每行的排序连接。
附件5的碎纸片复原结果为：
正面结果：
表-5
136a
047b
020b
164a
081a
189a
029b
018a
108b
066b
110b
174a
183a
150b
155b
140b
125b
111a
078a
005b
152b
147b
060a
059b
014b
079b
144b
120a
022b
124a
192b
025a
044b
178b
076a
036b
010a
089b
143a
200a
086a
187a
131a
056a
138b
045b
137a
061a
094a
098b
121b
038b
030b
042a
084a
153b
186a
083b
039a
097b
175b
072a
093b
132a
087b
198a
181a
034b
156b
206a
173a
194a
169a
161b
011a
199a
090b
203a
162a
002b
139a
070a
041b
170a
151a
001a
166a
115a
065a
191b
037a
180b
149a
107b
088a
013b
024b
057b
142b
208b
064a
102a
017a
012b
028a
154a
197b
158b
058b
207b
116a
179a
184a
114b
035b
159b
073a
193a
163b
130b
021a
202b
053a
177a
016a
019a
092a
190a
050b
201b
031b
171a
146b
172b
122b
182a
040b
127b
188b
068a
008a
117a
167b
075a
063a
067b
046b
168b
157b
128b
195b
165a
105b
204a
141b
135a
027b
080a
000a
185b
176b
126a
074a
032b
069b
004b
077b
148a
085a
007a
003a
009a
145b
082a
205b
015a
101b
118a
129a
062b
052b
071a
033a
119b
160a
095b
051a
048b
133b
023a
054a
196a
112b
103b
055a
100a
106a
091b
049a
026a
113b
134b
104b
066b
123b
109b
096a
043b
099b
反面结果：
表-6
078b
111b
125a
140a
155a
150a
183b
174b
110a
066a
108a
018b
029a
189b
081b
164b
020a
047a
136b
089a
010b
036a
076b
178a
044a
025b
192a
124b
022a
120b
144a
079a
014a
059a
060b
147a
152a
005a
186b
153a
084b
042b
030a
038a
121a
098a
094b
061b
137b
045a
138a
056b
131b
187b
086b
200b
143b
199b
011b
161a
169b
194b
173b
206b
156a
034a
181b
198b
087a
132b
093a
072b
175a
097a
039b
083a
088b
107a
149b
180a
037b
191a
065b
115b
166b
001b
151b
170b
041a
070b
139b
002a
162b
203b
090a
114a
184b
179b
116b
207a
058a
158a
197a
154b
028b
012a
017b
102b
064b
208a
142a
057a
024a
013a
146a
171b
031a
201a
050a
190b
092b
019b
016b
177b
053b
202a
021b
130a
163a
193b
073b
159a
035a
165b
195a
128a
157a
168a
046a
067a
063b
075b
167a
117b
008b
068b
188a
127a
040a
182b
122a
172a
003b
007b
085b
148b
077a
004a
069a
032a
074b
126b
076a
185a
0006
080b
027a
135b
141a
204b
105a
023b
133a
048a
051b
095a
160b
119a
033b
071b
052a
062a
129b
118b
101a
015b
205a
082b
145a
009b
099a
043a
096b
109a
123a
006a
104a
134a
113a
026b
049b
091a
106b
100b
055b
103a
112a
196b
054b
六、模型检验与推广
碎纸片自动拼接是计算机视觉和模式识别的一个基本问题，图形预处理和碎片匹配是其中的关键技术。虽然我们本次实验的仿真所涉及的碎纸片的数量及种类不多，但是它充分表明了所进行的碎纸片自动拼接复原技术研究的可行性。目前，系统还在进一步完善阶段，主要有一下几个问题：
1）边缘灰度值的精确提取
从实验分析可看出，边缘灰度值的精度对减少匹配的计算量和提高匹配的准确性都非常重要。它在很大程度上决定了纸片匹配的排序问题，有时甚至会导致某些匹配的失败。
2）数据库的开发管理
在实际应用中，由于设备等条件的限制，一次的处理往往不能解决全部的拼接问题。因此，必须开发合理的数据库，以充分利用每一次的拼接结果。
3）程序优化
虽然在进行简单的拼接复原工作时，该系统可以满足要求。但是在实际的应用中，通常会涉及对大量不规则纸片或彩色碎片数据进行管理和处理工作。因此，必须继续优化程序结构，提高程序的交互能力，真正实现快速有效的计算机辅助碎纸片自动拼接复原。
本文基于计算机辅助对碎纸机绞碎的碎纸片实现自动快速拼接，从图形显示技术中提取图形的灰度信息，并提出欧氏距离的配准方法，对图像中的误匹配点产生极大的抑制，求解的变换矩阵精度得到提高，大大缩短了匹配时间，在现实应用中具有重要意义，类似的研究可广泛应用到文物碎片的自动修复、司法物证修复、计算机辅助设计等领域。
七、参考文献
[1] Wolfson H，Kalvin A，Schonberg E，Lambdan Y，Solving jigsaw puzzles by computer，Annales of Operation Research，1988，12:51-64
[2] Freeman H，Garder L，Apictorial jigsaw puzzles:the computer solution of a problem in pattern recognition ，IEEE Trans.Elec.Comp，1964,13:118-127
[3] 余宏生，金伟其，散字图像拼接方法研究进展口[J]，红外技术，2009,31（6）：348-353
[4] 杨帆，数字图像处理与分析（第2版），北京：北京航空航天大学出版社，2010.8:205-208
[5] 何晓群，应用多元统计分析，北京：中国统计出版社，2010.6:179-182
[6] 张文修，梁怡，遗传算法的数学基础，西安：西安交通大学出版社，2000.5:13-33
[7] 方贤勇，图像拼接技术研究[D]，杭州：浙江大学计算机学院，2005
[8] 杨翠，图像融合与配准方法研究[D]，西安：西安电子科技大学，2008
[9] 叶耘恺，基于边缘特征的图像配准方法研究[D]，重庆：重庆大学，2009
[10] 苏彦华，数字图像识别技术典型案例，人民邮电出版社，2004
[11] Fischler M, Bolles R, Random sample consensus : A paradigm for model fitting with application to image analysis and automated cartography [J], Communications of the ACM, 1981,24(6):381-395
附录：
附件1的复原图片：
附件2的复原图片：
附件3的复原图片：
附件4的复原图片：
附件5的复原图片：
正面：
反面：
源程序如下：
cd (C:\Users\127\Desktop\附件1);
files=dir(*.bmp);
for i=1:19
s(:,:,i)=imread(files(i).name);
end;%将所有碎片导入一个三维数组
for j=1:19
n=0;
for i=1:1980
if s(i,1,j)==255
n=n+1;
end;
end;
if n==1980
disp(j);%找出最左边的碎片
break;
end;
end;
Figure 1
clear all
clc
cell{1}=imread(000.bmp);
cell{2}=imread(001.bmp);
cell{3}=imread(002.bmp);
cell{4}=imread(003.bmp);
cell{5}=imread(004.bmp);
cell{6}=imread(005.bmp);
cell{7}=imread(006.bmp);
cell{8}=imread(007.bmp);
cell{9}=imread(008.bmp);
cell{10}=imread(009.bmp);
cell{11}=imread(010.bmp);
cell{12}=imread(011.bmp);
cell{13}=imread(012.bmp);
cell{14}=imread(013.bmp);
cell{15}=imread(014.bmp);
cell{16}=imread(015.bmp);
cell{17}=imread(016.bmp);
cell{18}=imread(017.bmp);
cell{19}=imread(018.bmp);
for i=1:19
cell2{i}=im2bw(cell{i},0.5);
end
t=8
for x=1:18
x=sum(sqrt((cell2{t}(:,72)-cell2{i}(:,1)).*(cell2{t}(:,72)-cell2{i}(:,1))));
j=1;
for i=1:19
if i==t
continue;
end
x1=sum(sqrt((cell2{t}(:,72)-cell2{i}(:,1)).*(cell2{t}(:,72)-cell2{i}(:,1))));
if x1
展开阅读全文
相关搜索