碎纸片的拼接复原数学模型.docx

碎纸片的拼接复原数学模型.docx

《碎纸片的拼接复原数学模型.docx》由会员分享，可在线阅读，更多相关《碎纸片的拼接复原数学模型.docx（39页珍藏版）》请在冰点文库上搜索。

碎纸片的拼接复原数学模型

碎纸片的拼接复原

摘要

本文通过对碎纸片拼接技术的研究，建立0-1优化配对等系列模型，使用Matlab等软件进行模拟拼接，最终得到碎纸片的复原结果。

针对问题一，将所有碎片二值化，然后利用Matlab找出最左边的碎片，再建立0-1优化配对模型

从剩余图片中找到与最左边匹配的图片，并将该图片作为起始图片，再到剩余图片中找寻与它相匹配的图片，以此类推，最终得到图片的序列。

由于将原图像二值化处理之后，数据会产生较小偏差对结果可

能有一定影响，所以我们利用欧几里得距离模型

对问题一

重新计算，最终两者的结果一样。

所以两种模型均可以复原原图。

对于问题二，利用在问题一中已建立好的欧几里得距离模型，在图片的横纵二个维度范围内，可以实现情况为纵向切到文字的段与段之间的拼接以及行拼接，之后对于剩下的6张上下边缘为白边的碎片进行拼接，由于一张完整的图像的行间距基本相等，所以对于剩余六张碎片，我们在Matlab中构建了关于行间距的二值匹配度评价模型，通过对行间距的水平量化和拟合，得出行间距的最佳值，实现了对段落拼接的模拟，最终还原出原始图像。

对于问题三，在问题二的基础之上，加大了数据的检索量及增加了匹配条件的维度。

因此，我们对原有模型进行适当地推广，由左右二维改为从上下左右四个维度向中间匹配，以此减少数据搜寻量，同时增加了匹配精确度。

通过这种由四周向中心配对的分类压缩检索数据库的方法提出了0-1优化配对的推广模型应用于此问，精准地复原了原图像。

关键词：

碎片拼接、图像数字化、优化配对、二值化

1问题重述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。

特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。

随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。

请讨论以下问题：

1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果以图片形式及表格形式表达。

2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果表达要求同上。

3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。

附件5给出的是一页英文印刷文字双面打印文件的碎片数据。

请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。

2问题分析

本题要求将凌乱的矩形碎纸片拼接复原，问题的关键在于找到相邻碎纸片间的衔接特征。

拼接复原的要求是碎纸片在图形上能够无缝结合，且在内容上能够连续贯通。

由题意可知提供的这些碎纸片的形状都是矩形，且相互全等，它们以任意的顺序拼接都可以整合出完整的纸张，因此不能按碎片的形状将其复原，于是只有在纸张内容上下功夫。

由凡是切割到文字的两张碎纸片在碎片边缘内容上具有连续性，还原到图片像素上也应具有一致性。

问题

（1），考虑到仅是纵向切割为19段，数量较少，将图像二值化，分析每一对像素点二值相同情况占总体的百分比，可以给待评价的两碎片一个定量的匹配度评价，文中用相似度来反映。

通过相似度大小的比较便可以选定与原图匹配度最高的碎片，将其与原图组合后重复上述算法便可以复原初始图像。

考虑到如果数据量过大时，二值化过程会比较粗糙，因此我们对模型进行了优化，提出了另一种新模型，欧式距离模型。

通过对两侧同位置灰度值相差程度的定量比较，也可以确定出与待求碎片最为匹配的碎片。

运用两种模型，均成功复原出了原始图像。

问题

（2），碎片由仅纵切变为既纵切又横切，处理的维度上由一维增加到二维，采用问题

（1）中的欧式距离模型实现了对11行每行19张碎片的拼接，紧接着也可以将横切到有文字的纵列复原，剩下6段组合过的横向碎片，他们的上下边缘均是全白的，现在采用行间距判定的方法拼接这6段。

问题（3），在问题

（2）的基础上新增加了反面这一因素，在图片一面的遍历过程中，新增的庞大数据量及判定条件加入到原本多重的循环里，使得循环太过庞杂，以致于一个细微的变化量经过循环放大之后，都将造成最后结果相差甚远。

因此第三问解决的关键在于简化数据库及其检索条件的优化。

基于此，我们提出了两种基于普通模型的推广，通过对细胞方框的找寻和配对规则的研究，大大简化了数据库，对成功进行最佳匹配段的检索提供了便利。

3模型假设

（1）假设题目所给的数据真实可靠；

（2）假设该模型中碎片表面光滑平整且表面厚度为0；

（3）假设录入文字平整，无皱褶；

（4）假设同一附件中的所有碎片都为全等的矩形；

（5）假设碎片图像由同款拍照设备在相同的条件下拍摄得到；

（6）假设拍摄照片平稳，光线均匀；

（7）假设每张碎纸片都是等距离纵切或者横切得来的。

4定义与符号说明

符号表示

符号说明

图片对应的二值矩阵第

行最右端数字；

两张图片的边缘相似度；

两张图片边缘黑色一致的像素点个数；

灰度阈值；

图像中像素点的灰度值；

两张图片边缘白色一致的像素点个数；

两张图片边缘黑色像素点个数的最大值；

一张图片纵向像素点总数；

两点间的欧式距离；

第

行所有列之和；

第

行第

列的元素；

第

列第

行的元素与第

列第

行元素的差方和；

5模型建立与求解

5.1问题一的建模与求解

模型一（0-1优化配对模型）的准备

1.图像碎片数字化

问题一给出的是来自同一页印刷文字文件的碎纸机破碎纸片，若根据汉字检索对文字拼凑进行碎纸片的整理，一方面在最后的判定条件环节难以实现，另一方面，汉字或字母中，往往会有不同的元素出现相同部分的情况（例如偏旁部首），这也会给最后的结论带来偏差。

由电脑屏幕成像的基本原理，我们若把影像放大数倍，会发现这些连续色调其实是由许多色彩相近的小方点所组成，这些小方点就是构成影像的最小单位“像素”，各像素的灰度值也是用离散值即整数值来表示的。

抓住图像显示的本质，也即是电脑屏幕上各个像素点的表达，利用MATLAB软件可以导出图片的像素矩阵。

这种方法可以有效地排除不同元素相同部分的影响，因此下面重点对附件一的处理作详细说明。

把19张图纸碎片分别导入到MATLAB中，得到每张图片的1980×72个像素点的灰度值。

将每一个灰度值作为单个元素，相当于构建出了19个1980×72阶矩阵。

2.边界提取

提取以上求得的19个1980×72阶矩阵每组第一列和最后一列的二值序列，借助EXCEL表格进行分类汇总，构建所有的图像碎片左边界和右边界的纵向二值序列矩阵。

3.图像二值化

图像按显示效果一般可分为灰度图像、二值图像、彩色图像等。

将256个亮度等级的灰度图像通过适当的阈值选取而获得仍然可以反映图像整体和局部特征的二值化图像。

由于图像的平滑渐变性，图片中由一种颜色变化到另外一种颜色中间会有一段过渡颜色，其灰度值也呈逐渐变化。

灰度图像对应一个数据矩阵（二维数组），矩阵中的元素值表示图像对应像素在该位置上的灰度值，常用0表示黑色，255表示白色，用0~255之间的数表示灰度值。

二值图像是只有两个灰度级的图像，即黑（0）与白（255），本文在二值图像中用1代表黑色，0代表白色。

图像二值化可根据公式

（1）来进行：

（1）

其中，

是图像中像素点的灰度值，

为灰度阈值。

根据此算法可得图像二值化，即把图像中像素点灰度值大于

的用0（白色）代替，小于等于

的用1（黑色）代替，原来的灰度图像就变成了非黑即白的二值图像。

文中第一题中为了方便说明，暂且令

，即是将由白色到黑色的过渡段全作为黑色处理。

模型一的建立

图像的0-1优化配对模型是基于像素灰度的统计匹配之上提出的。

为了反映两张碎片的匹配程度，我们引入了相似度的概念。

即两张图片相邻的两边对应一致的像素点个数占总像素点个数的百分比。

为参加匹配的两条边中黑色与黑色匹配成功的个数，

为参加匹配的两条边中白色与白色匹配成功的个数，

为一边的像素点总数，相似度

表示为：

（2）

由于图片边缘绝大多数均为白色，在统计黑白配对时，白色的部分会对结果造成影响，造成结果差距不明显。

因此在重新确定相似度的时候，我们对原有的相似度算法进行了改进，

为所比较的两条边界中黑色像素点个数的最大值

（3）

得到改进后的相似度模型：

（4）

模型一的求解

借助MATLAB完成以下循环过程：

由统计的数据特点可确定出原图片的左起第一张图像碎片，以它右侧灰度值转换的二值矩阵为基准，遍历剩下的每张图的左侧矩阵，分析筛选出相似度最大的列即确定为与之配对的图像碎片。

然后将其与先前的部分进行拼接，用筛选出来的碎片的右侧矩阵替换先前的标准矩阵，重复上述过程。

最后将拼接完成的图片在MATLAB中输出。

表1确定最后匹配顺序的各类参数统计值

图片编号

统计参数

008&014

014&012

012&015

015&003

003&010

163

141

111

392

252

206

206

197

453

453

79.13%

68.45%

56.35%

86.53%

55.63%

表1（续）确定最后匹配顺序的各类参数统计值

010&002

002&016

016&001

001&004

004&005

005&009

009&013

278

300

382

288

168

263

276

303

323

429

429

330

322

324

91.75%

92.88%

89.04%

67.13%

50.91%

81.68%

85.19%

表1（续）确定最后匹配顺序的各类参数统计值

013&018

018&011

011&007

007&017

017&000

000&006

220

223

203

255

293

313

324

265

241

349

349

385

67.90%

84.15%

84.23%

73.07%

83.95%

81.30%

最后求解出的拼接顺序为：

附件一的拼接顺序：

008---014---012---015---003---010---002---016---001---004---005---009---013---018---011---007---017---000---006

附件二的拼接顺序：

004---007---003---008---016---019---012---001---006---002---010---014---011---009---013---015---018---017---005

模型二（欧几里得模型）的建立

针对于提取出的两个待评价的边界矩阵可以构建出两个纵向的1980阶向量，向量中的每一个元素即是边界的灰度值（0~255）。

分别比较两侧对应位置灰度值可以分析出图像的相近程度。

将19张图像边界灰度值按照左边和右边两大类进行分类整合，构造出两个1980×19阶的矩阵：

（5）

同样利用碎片最左端的灰度值变化规律，可以很方便地确定出原图片最左端的起始碎片，取出其右侧的列向量记为

，任取剩下的左侧列向量记为

，从而得出两张图片边缘黑色像素点个数的最大值

。

（6）

其中，

表示

和

之间欧几里得距离，反映了两个向量间的匹配相似程度，

越小，代表两个向量差距越小，还原为灰度值后即反映了两张图片接合得最为密切。

利用MATLAB对所求得的每一个

值进行分析比较，找到最小的

值对应的图片编码即为原碎片的最佳连接选择。

再仿照模型一中后续的拼接流程，在MATLAB中实现对碎片的正确拼接。

模型二的求解

在左端数据库中遍历寻得全为0的列向量，显然是左边界的条件，设计程序找到此列向量后自动返回对应的碎片编码，再提取其右端列向量作为标准再去左边数据库中寻找最符合的列向量完成拼凑过程。

利用

表示第

列第

行的元素与第

列第

行元素的差方和，则

可以表示为：

（7）

把每一个求得的

值横向拼凑起来，便可得到一个1980×1阶的行向量。

通过对1980列的纵向遍历，可以筛选出最小值

（8）

便可以完成一次匹配，再利用匹配到的列的左侧列向量返回对应的编码值，导出其右侧列向量，继续作为标准匹配下去，最后遍历所有得到结果为：

附件一的拼接顺序：

008---014---012---015---003---010---002---016---001---004---005---009---013---018---011---007---017---000---006

附件二的拼接顺序：

004---007---003---008---016---019---012---001---006---002---010---014---011---009---013---015---018---017---005

模型一与模型二的比较与分析

问题一所采取的两种模型均可以得出最后正确的拼接结果，但对比它们的具体实现过程，可以发现这两种模型各自具有的优缺点。

第一种0-1优化配对模型在处理过程中为了说明方便，将图像进行了二值化处理，并将白色与黑色中间灰色的过渡部分近似处理为黑色，由此一来，处理得到的误差就相对增大了，但考虑到第一题本身的特点，在数据量较小的情况下是可以采用此种做法，可有效简化数据的统计及计算过程。

第二种基于欧几里得距离的灰度匹配模型充分考虑到了图像灰度值的变化过程对整体结果的影响，综合进了每一列灰度值的差，对整个边界的相似程度会有一个更加客观的评价，但在数据处理上较0-1优化配对模型更为复杂，并且欧几里得模型在处理边界为白边的情形时存在缺陷。

5.2问题二的建模与求解

模型一（欧几里得二维匹配模型）的建立

由于问题

（2）是对问题

（1）的扩充，相当于评价匹配度时在问题一的基础之上增加了纵向维度的因素，所以本问中的基本思想仍然可沿用问题

（1）中基于欧式距离的评价模型。

所不同的是现在碎纸机既纵切又横切，出现碎片的情形较问题

（1）中也出现更多，因此前期对本问中的大量碎片进行合理的分类是关键。

将19张碎片批量导入MATLAB（图片批量导入程序代码见附件），可得到对应的19个72×180阶矩阵，以列为单位分别对19个矩阵依次进行校核，由最左端灰度值的变化情况可以确定出每张图片左边距的对比情况，从而筛选出可以作为左边界的16个碎片。

但其中包含有文章中间刚好没切到文字的部分，我们称作“假边界”。

通过设定预值对左边距进行再次筛选，可以从16个碎片中确定出真实的11个边界碎片，见下表。

表2筛选出的原图左边界碎片编码

原图左边界碎片编码

049

061

168

038

071

014

094

125

029

007

089

取以上的每一个左边界碎片进行分析，以其右边界矩阵为标准，遍历剩下所有碎片的左边界矩阵，借助欧式距离模型便可确定出匹配度最高的碎片

.

（9）

在MATLAB环境下进行编程，实现对数据的自动循环遍历，找到其中最小的

值后自动返回对应的碎片编号，并自动将找到的碎片与前面的进行拼接，用新对象的最右端列矩阵作为新标准重复上述循环过程。

由于第一次按左边界条件筛选出来的有16张碎片满足条件，虽然已经设计方法实现了对“假边界”的剔除，但在每一条进行拼接的时候，剩下的5张碎片会对配对过程产生影响。

因此我们在左边界配对的时候，把16张碎片都作同等处理，按照已建立的模型进行匹配拼接，直到右边界的列矩阵元素全是255，反映到图片上是原文中间段右端没有切到文字或者本身就是原文的右边界两种情况。

如此我们可以确定出16段横向碎片，再利用程序实现对不完整条形段的两两拼接，由此确定出完整的11行横向碎片。

以上解决了在横纵切的情况下的一维横向拼接，接下来讨论将横向条形碎片纵向拼接成为最后的整体。

类似于碎片横向处理时的思想，先将现有的11张碎片大致分类。

依照上下边缘特点，可归纳为两类，即是上下边缘包含有黑色部分和上下边缘为全白。

其中包含有黑色部分的上下边缘可直接运用欧式模型匹配到最合适的，最后整理得到6段横向碎片，他们的上下边缘均为白色。

下面给出了这6段经过拼接后整行的示意图：

（仅给出了第一列碎片的编号）

表3处理过后得到的新碎片表

新拼接出的碎片

碎片1

碎片2

碎片3

碎片4

碎片5

碎片6

049

…

061

…

168

…

038

…

071

…

089

…

125

…

029

…

007

…

014

…

094

…

模型一的求解

模型关键就在于如何将这些局部拼接成横向碎片的小整体拼接成完整的纸张。

任取一横向碎片对其进行分析，利用MATLAB软件对拼接成局部整体的碎片再进行数字化处理，得到其灰度矩阵。

以该矩阵的第1行向量与下一碎片图像矩阵的第180行向量进行匹配。

根据问题一中建立的最短欧几里得模型，

以

取得最大值作为匹配条件，就可以将上诉得到的横向碎片拼接复原。

最后所得碎片拼接的结果为：

表4附件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

142

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中的英文碎片，重复上述操作，便可拼接复原出完整的纸张。

模型二（行间距的二值匹配模型）的建立与求解

基于欧式模型的匹配度评价方法在第二题中只能实现到每一行的拼接以及切割线切割到文字的纵向两行的拼接，但切割线切割到行间的纵向两行的拼凑用这种方法显然无法实现，因此需要采用新的方法加以实现。

图1段落的模拟图（横坐标表示纸片整体的行数，纵坐标表示每行字符包含的像素个数）

在第一问的0-1优化配对模型中，我们对图像进行了二值化处理，运用同样的方法，将现已拼接出的六张整行图片可以用6个不同阶数的0，1二值矩阵表示。

再以一个像素点为单位，对图片的每行进行求和，绘出和值曲线，找出曲线上两个突变值对应横坐标之差即为行间距。

用

表示第

行第

列，用

记录第

行所有列的求和

（10）

借助MATLAB对每一行求得的

值用曲线描述出来，便可以模拟出行间距的平均水平，可以确定出行间距的平均值。

图2行间距变化曲线图

为了排除个别段落偶然误差的影响，统计出6张图片中完好的20组行间距，并利用最小二乘法拟合出一个更为准确的行间距值。

以行间距为判定条件可以将6组图片纵向匹配还原为原图。

表5第一行还原统计表

049

054

065

143

186

002

057

192

178

118

190

095

011

022

129

028

091

188

141

5.3问题三的建模与求解

0-1优化配对推广模型的建立与求解

对第一、二、三问题作进一步分析，我们发现三个问题的本质就是要解决两张图片间相互配对的过程，其关键便是要选取一定的判定指标来评判两张图片间的匹配水平。

由于附件五中的碎片两面都印刷有文字，碎片的正反面是不知道的，且碎片的数量有418张。

如果还是沿用问题一和二中得到的模型进行求解，在碎片的匹配过程中势必会出现一配多的情况。

这就会使碎片无法顺利拼接复原。

为了放大碎片图像的差异及提高匹配的精度，我们使用归一化灰度组合法（NIC）来分析求解第三问。

归一化灰度组合法（NIC）的基本思想是基于基准图和实时图灰度的相关性，和传统的灰度相关法不同的是，NIC是通过灰度组合矩阵来计算灰度的相关性。

NIC和灰度相关法的关系可以从下面的推导看出，常用的均方差灰度相关算法的公式如下：

（11）

式中

和

表示实时图和基准图，

和

表示匹配模板大小，

表示当前匹配像素，公式（11）可以用灰度组合矩阵表示为

（12）

式中，

表示在当前匹配像素

处的灰度组合矩阵，

表示最大灰度级数

表示。

级数

所代表的灰度值，为了方便表示，灰度组合矩阵用

表示两幅图像中共有多少对像素，它们的灰度组合是

。

约定在

矩阵中行代表实时图的灰度，二列代表基准图的灰度。

它性质如下

（13）

根据上诉的方法，考虑到由于每张图片的摆放方法是唯一确定的，因此我们对每一张图片进行编号，统一定义上边界为

，下边界为

，左边界为

，右边界为

，

表示第

张

图片。