无缝钢管 直缝焊管 镀锌钢管 螺旋钢管 方矩管 镀锌方矩管 带钢 冷轧带钢 镀锌带圆管 镀锌带方矩管 不锈钢管 镀锌带钢 角钢 钢塑管 RSS
您当前的位置:首页 > 技术知识 > 技术知识库

碎纸片的拼接复原

时间:2020-06-28 10:46:14  来源:  作者:
 碎纸片的拼接复原,对重要文件的拼接复原,传统上都由人工完成,拼接准确率虽然高但是效率很低。本文旨在建立模型,利用计算机编程加少量的人工干预实现碎纸片的拼接复原。

针对问题1,由于对任意一个字符来讲,笔画是连续的,所以对于一般情况,即使文字被切开,两边的像素还是有联系的,是呈现离散性渐变的。针对此特征,建立了文字连续性模型来求解该问题。而又因为被切开的两边碎片边缘灰度是具有高相关性的,所以,又建立了向量相关模型来求解进行图片拼接。用两种模型分别求解,都得到了对附件一和附件二的正确拼接结果。

针对问题2,可以采用第一问的模型,先进行全局搜索,找出每个碎片最相似的右侧邻近碎片,拼接出每一行的图片,再利用向量相关性进行横向拼接,得到拼接结果。但是,由于纸片同时被横向与纵向切割,碎片小,数量多,碎片之间的信息量不够,容易造成误判。所以建立向量投影分类模型,首先将可能处于同一行的碎片用模糊C均值(FCM)聚类方法分到同一类。对于汉字或英文的缺行碎片(碎片中只有一行或者两行字),利用掩码补充模型将投影中缺失的行用掩码补齐,然后再放入分类。分类完成后,将每一类中的碎片进行横向排序拼接。每一类横向拼接完成后,从而拼接成完整图片。对于不能正确拼接的部分,采取了多种人工干预的策略,最终得到正确的拼接结果。

针对问题3,由于附件中的碎片分为正反两面,所以可以建立组合匹配模型将碎片首先将正反面碎片的灰度矩阵上下拼接,每张碎片的拼接方案有两种(灰度矩阵a放在左右镜像处理后的b上或灰度矩阵b放在左右镜像处理后的a上)。拼接过后,边缘灰度向量信息会增加为原来的两倍,这时利用问题二中的全局搜索模型用向量相关性的方法进行匹配拼接。拼接出所有行后,将每一行的下半部分矩阵切割放在上半部分的右边,又可增加横向拼接时的边缘信息,然后各行再次利用向量相关性的方法进行横向拼接,最终得到结果图,但是仍然存在较多的碎片不能正确匹配,需要人工干预。

由于碎片在切割时的随机性,使得机器自动拼接存在一定的难度,因此,采取恰当的人工干预的措施,是保证正确拼接的必要手段。

关键词:文字连续性  匹配  FCM聚类方法 掩码补充模型  向量投影分类模型

一.问题背景及重述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上,拼接复原工作需由人工完成,准确率较高,但效率很低。特别是当碎片数量巨大,人工拼接很难在短时间内完成任务。但如果借助计算机技术,开发出碎纸片的自动拼接技术,提高拼接复原效率将会大大提高。

问题1:给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原模型和算法,并且拼接复原附件1和附件2给出的中、英文各一页文件的碎片数据。

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

问题3:从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出了一页英文印刷文字双面打印文件的碎片数据。设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果。

二.模型假设

1、不计碎纸片边缘的磨损,没有边缘像素损耗;

2、假设纸张垂直放入碎纸机即每张小碎纸片都是规则矩形;

3、图片中的文字像素没有任何断点;

4、图像上没有任何噪声或污点造成像素干扰。

三.变量说明

 

四.模型准备与问题分析

针对题目中附件所给的图片信息,我们学习准备了图像的处理方法[1]、模式匹配方法[2]和图像拼接方法[3,4]。将图片批处理成范围值0-255之间的灰度矩阵(纯黑为0,纯白为255,数字越大,颜色越亮)。

问题一中的附件图片,碎片数据较少,每一张碎片都比较大,那么相应的灰度矩阵中包含的信息就比较多,处理起来相对容易。而且仔细观察,分别只有一张图片的最左端和最右端边缘是没有文字的。由于完整纸片切开后,边缘处仍然是有联系的。所以可以提取图像边缘的灰度信息,首先找出第一张图片,然后利用图片的边缘信息找出下一张图片与之拼接。

问题二中,给出的图片碎片比较小,只有180*72像素,图像信息以及边缘信息都比较少。而且,由于既横切又纵切,图片的顺序被打乱,无法直接拼接。因此,首先得将这些碎片分类,将同一行的图片归在同一类中,然后将归类后的图片进行横向排序,拼接出这一行的图片碎片,因为有些碎片包含的边缘信息过少,可能无法分类或者成功排序,这时进行人工干预。每一行图片按排序拼接后,即可将问题转化为第一问的问题进行纵向拼接,最终得到结果。

问题三中附件五的碎片与问题二中附件四的类似,都是英文小碎片,但是正反面被打乱。虽然正反面一开始无法识别,但是某一张图的正面与另一张正面横向投影对齐,反面的横向投影也就会对齐。所以我们可以利用a面和b面的矩阵上下组合,变成一个大的单面图片,一方面增加了拼接的信息量,同时又将问题转化为第二问中类似的问题,利用第二问的模型即可找出双面碎片的拼接结果。

五.模型建立与求解

5.1   问题一的求解

5.1.1 基于文字连续性模型的碎片拼接

首先,对问题1的分析可知,该问题为一个图像处理问题。根据字的特征,我们知道笔画是连续的,图片放大之后我们也能看到有字的部分图像偏暗,由字中间向边缘,慢慢变亮直至超过字范围而变成白色。我们利用这一点,建立文字连续性模型来处理拼接问题。

      

(a)                                                                  (b)       

图1:点阵字体的锯齿现象

由字体放大图1(a)可以看出笔画周边的锯齿,每一个锯齿方块就是一个像素,范围大小在255以下。切割后的图像,这些锯齿也会分开。但是,虽然像素分开了,由于汉字字体或者英文字体大部分是连体的,所以这些碎片的图像灰度信息会有一定的相关性或者说是连续性。

如图1(b),假如图片像素按照红线所示切开分为a,b两块。可以看到红线左右两边的像素块大都是相连的,最理想的情况就是如同像素块2,3或者4,5在同一位置直接对应,这种情况就可以认为这两个像素块匹配,匹配数num加1。但是,也有可能出现像素块1这样的情况,与之对应的位置没有像素块,但是下方或者上方有像素块,由于这些像素的连续性,所以也认为像素1得到匹配,num=num+1。

读取所有图片,由于纸张有页边距,若某一张碎片为完整纸片上的最左一张,则其图像左侧必定全为白色,即灰度值的前几列为255,通过这种方法,能很快找到第一张碎片,将其放入集合中,记为。

找到第一张碎片后,用第一张碎片的右边缘去和中所有碎片的左边缘进行匹配。由于白色点太多,匹配成功数会很大,影响结果。所以,我们只选取非白色点进行匹配,匹配过程中,非白色点的总数记为sumofb,每选取边缘非白色点匹配一次,sumofb=sumofb+1。

匹配率[3]的计算方法为:

                         (1)

求得第一张碎片的右边缘和集合中每张碎片左边缘的匹配率后,将所得的匹配率对比,选取匹配率最高的那张碎片,将其放入集合中,记为(i为碎片的排列顺序),将右边缘像素去和中剩余碎片的左边缘像素进行匹配,重复此类操作,直到中没有碎片,最终得到排序结果即为碎片的拼接方案。计算所得集合中与的最大匹配率如表1所示。

表1:附件一中中文字符碎片拼接顺序及匹配情况:

当前碎片编号

8

14

12

15

13

10

2

16

1

最佳匹配碎片编号

14

12

15

13

10

2

16

1

4

最大匹配率

0.83

0.96

0.82

0.92

0.97

0.92

0.97

0.94

0.83

当前碎片编号

4

5

9

13

18

11

7

17

0

最佳匹配碎片编号

5

9

13

18

11

7

17

0

6

最大匹配率

0.85

0.87

0.97

0.92

0.74

0.89

0.98

0.91

0.99

表2:附件一中英文字符碎片拼接顺序及匹配情况:

当前碎片编号

3

6

2

7

15

18

11

0

5

最佳匹配碎片编号

6

2

7

15

18

11

0

5

1

最大匹配率

0.93

0.91

0.95

0.92

0.89

0.90

0.76

0.96

0.88

当前碎片编号

1

9

13

10

8

12

14

13

16

最佳匹配碎片编号

9

13

10

8

12

14

13

16

4

最大匹配率

0.99

0.87

0.87

0.94

093

0.92

0.96

0.84

0.82

5.1.2  基于向量相关性的碎片拼接

提取碎片边缘向量,选出第一张图片后,计算右边缘向量与集合中的每一张碎片左边缘向量的相关系数[5]:

                                       (2)

将所得的对比,选出相关系数最最大的,放入集合中。再用选出的碎片右边缘向量与中剩余碎片匹配,重复此操作,直到中没有碎片,最终得到排序结果即为碎片的拼接方案。计算求得集合中与的相关系数为:

表3:附件二中中文字符碎片拼接顺序及匹配情况:

当前碎片编号

8

14

12

15

13

10

2

16

1

最相关碎片编号

14

12

15

13

10

2

16

1

4

最大相关系数

0.80

0.85

0.88

0.91

0.84

0.89

0.94

0.88

0.86

当前碎片编号

4

5

9

13

18

11

7

17

0

最相关碎片编号

5

9

13

18

11

7

17

0

6

最大相关系数

0.88

0.88

0.88

0.87

0.86

0.86

0.84

0.88

0.90

5.2  问题二的求解

问题二中所给附件三、四都是小碎片,宽度为72像素,与第一问中的一致,但是高度只有180像素,为第一问碎片的1/11,所以左右边缘的灰度信息较少,容易造成误判。

5.2.1 模型1 建立全局搜索的碎片拼接模型

由问题一的求解可以看出,利用向量相关模型或者文字连续性模型可以不必区分碎片的文字语言。所以对于问题二,可以建立全局搜索模型,同时利用第一问中的向量相关分析来进行碎片拼接。全局搜索模型算法如下:

Step 1:根据页边距找出11张处于纸片第一列的碎纸片,记为集合。取其中一张记为,放入;

Step 2:我们从存放于U的所有纸片中任取一张碎纸片与进行向量匹配,记录下匹配的相关系数,取相关系数最大的那张图片作为的下一张纸片,记为,以此法依次匹配得到后面的18张图片(最后一张同样存在页边距);对于得到的这样一条横串,我们记为

Step 3:从上面的集合中再任取一张图片记为,重复step2;

Step 4:当,我们根据问题1中的方法对进行拼接,即可得到整张纸片原图。

5.2.2模型2 基于向量投影分类的碎片拼接模型

但是由于附件三和四中都给出了209张碎片,如果进行全局搜索的话,时间复杂度,计算量十分庞大。所以为了减少计算时间,我们首先根据碎片中行距的位置对碎片进行预分类,将同一行的碎片分在一类,再对同一类中的碎片利用第一文的方法进行排序。

由于中英文文字在像素图片中的显示形式不一样,所以我们通过这两种文字显示的不同特征来用两种投影方式来进行分类排序。
来顶一下
返回首页
返回首页
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
推荐资讯
201不锈钢卷带_佛山市源远华钢业有限公司
201不锈钢卷带_佛山市
304不锈钢板_无锡金大友发金属制品有限公司
304不锈钢板_无锡金大
不锈钢板_无锡泰邦特钢有限公司
不锈钢板_无锡泰邦特
聊城亮洁不锈钢复合管厂
聊城亮洁不锈钢复合管
相关文章
    无相关信息
栏目更新
栏目热门