碎纸片的拼接复原论文.docx
《碎纸片的拼接复原论文.docx》由会员分享，可在线阅读，更多相关《碎纸片的拼接复原论文.docx（32页珍藏版）》请在冰点文库上搜索。
碎纸片的拼接复原论文
高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题.
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性.如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理.
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）.
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：
B
我们的参赛报名号为（即电子文件名）：
B0813
所属学校（请填写完整的全名）：
广西师范大学
参赛队员（打印并签名）：
1.
2.
3.
指导教师或指导教师组负责人（打印并签名）：
日期2013年9月16日
赛区评阅编号（由赛区组委会评阅前进行编号）：
高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
纸片的拼接复原
摘要
碎纸自动拼接复原技术现今可以归结到计算机视觉和模式识别领域内的问题，它在司法物证复原、历史文献修复等重要领域都起着重要的作用.本文主要分析了文字的拼接技术，通过研究碎纸片内的像素矩阵和文字行特征特点，提出了基于文字图形的半自动拼接算法.
对于问题1中的这种单面的仅纵向切碎的文字文件，通过Matlab程序分析附件中每个碎片的像素矩阵，确定拼接的第一个碎片（自左向右拼接），再根据两列像素矩阵的像素绝对差的和来确定相邻碎片的编号，从而得到完整的拼接方案.例如文字文件的拼接结果如下表所示：
顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
编号
0
0
8
0
1
4
0
1
2
0
1
5
0
0
3
0
1
0
0
0
2
0
1
6
0
0
1
0
0
4
0
0
5
0
0
9
0
1
3
0
1
8
0
1
6
0
0
1
0
0
4
0
0
5
0
0
9
对于问题2中既纵切又横切的碎纸片，在问题一的基础上，充分考虑横向匹配和纵向匹配的要求，运用Matlab程序筛选最左列碎片成分，经过适当的人工干预根据文字行特征将所剩碎片进行行分类，大大提高拼接效率，得到意想的效果.例如文字文件的拼接结果如下表所示：
顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
编号
0
0
3
0
0
6
0
0
2
0
0
7
0
1
5
0
1
8
0
1
1
0
0
0
0
0
5
0
0
1
0
0
9
0
1
3
0
1
0
0
0
8
0
1
2
0
1
4
0
1
7
0
1
6
0
0
4
对于问题3，在前两问的基础上，建立筛选附件5碎片图的优化模型，通过Matlab编程，使用附件给的418张碎纸片图，将最终复原图划分为11个碎片横条区域，降低了拼接复原难度以及所需时间.最终复原结果见附录.
最后，分析了所建立模型的优缺点以及推广，评价了文字碎纸片的拼接和复原实际情况.
关键词文字图形碎片半自动拼接像素灰度MATLAB程序
一问题的重述
碎纸自动拼接复原技术是计算机视觉和模式识别领域内的问题.它在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统意义上的拼接复原工作需由人工完成，准确率较高，但效率非常低，特别是当碎片数量巨大时，人工拼接很难在短时间内完成任务.随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率.
本文主要讨论：
首先，对于给定的来自同一页单面印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，同时对题目中的附件1和附件2给出的中、英文各一页文件的碎片数据进行拼接复原.
其次，对于同样是单面印刷文件既纵切又横切的情形，在第一问的基础上设计出碎纸片拼接复原模型和算法，对附件3和附件4给出的中、英文各一页文件的碎片数据进行拼接复原.
最后，联系现实中的情况，对还有可能出现双面打印文件的碎纸片进行拼接复原.在前两问的基础上，设计出相应的碎纸片拼接复原模型与算法，并附件5中双面打印文件的碎片数据给出拼接复原结果.
在上述复原过程中，由于计算机的识别可能会出现偏差，那么就需要在拼接过程中进行必要的人工干预，在适当的时候我们会用干预的方式给出复原过程.并最终以图片形式及表格形式完成给出复原结果.具体结果在附件中给出.
二问题的分析
破碎文件的复原，最直接及最精确的就是人工拼接，但是当碎片的数量巨大时，人工方式就显得效率低下，所以就考虑把破碎文件运用计算机技术来帮助人们进行破碎文件的复原，让计算机在这个过程中发挥主要作用，但是用计算机处理，又不是百分之一百完美，因此在适当的时候也需要进行人工干预.
本文运用碎纸片的自动拼接技术，对每个附件给出的碎片文字材料进行分析，尽可能减少人工干预，本文给出的图像数据均为形状、大小一样的规则长四边形，由于形状的一致性，所以在拼接时如果只考虑利用碎片的边界特征，直接拼接，显然效果不理想.
考虑到使用计算机的拼接过程应该与人工拼接过程是相类似的，即拼接时不但考虑碎片边缘是否匹配，还要判断碎片内的字迹断线和文字内容是否匹配.然而根据现在已有的技术，实现计算机智能识字是几乎不可能的.但是我们可以获取图片所提供的像素信息，将其转化为矩阵，根据图像的像素矩阵值进行碎片拼接，用计算机去运行处理数据，可以想象其拼接效率无疑比单纯利用边界特征的方法好很多.
以下是对各问题的详细分析：
针对问题1，对附件1和附件2提供的数据，每页纸被切为19条碎片，对于这种单面的仅纵向切碎的文字文件，我们仅考虑碎片左右两侧的拼接.首先，在转换中发现，像素图片矩阵的值是介于0到255之间的一个像素矩阵，随着像素矩阵值的增加，我们发现随着像素矩阵数值的增大，所代表的区域越来越浅，最后255这个数值，代表了白色区域.其次，对于问题1中的附件1和附件2图片，由于仅纵向切碎的文字文件，仅考虑碎片左右两侧的拼接.需运用Matlab程序分别对附件1和附件2中的19个碎片计算其像素矩阵，将每个附件中19条图像转换成19个
的像素矩阵，筛选出每个像素矩阵的第一列像素矩阵值，然后运用Excel软件统计各列像素值等于255的个数，可以粗略的认为所含255个数最多的列所对应的碎片则是拼接顺序中的左边第一条（如果有必要进行人工干预，但是本文第一问没有进行人工干预）.接下来从左边开始选取第二条碎片，关于第二条待匹配的碎片，用先确定的第一条像素矩阵的最后一列，对其进行数值求和，然后将剩下的18个像素矩阵中的第一列和最后一列矩阵进行分别求和.将首先确定的最左边第一条矩阵中的最后一列矩阵与求出的18个像素矩阵中的第一列矩阵分别进行做差，然后将差值取绝对值，这样就可以得出，如果差值越小，其重叠的相似度也应该相对越高.这样可筛选得出相似度较高的碎片，即与第一个碎片相匹配，该碎片位于拼接顺序的第二条，确定第二条后，再用第二条的最右边矩阵并以此类推，逐一从左到右查询碎片，直到碎纸片的复原结果.
针对问题2，在问题1的基础上，继续对所给的附件3和附件4进行分析.针对附件3和附件4的特点，附件3和附件4给出了碎片既横切又纵切的中英文图像，那么在拼接时就有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.那么我们就考虑在问题解决中可以分为两步进行，首先考虑横向拼接，一旦横向拼接完成了，纵向拼接自然相对就好解决了.根据碎片像素矩阵特征和行距特征将其分类，再结合问题1的方法将各类碎片进行匹配，即可得到11个碎片横条.接着考虑纵向拼接，使用Matlab程序对得到的新的横条碎片进行像素分析，比较像素矩阵中第一行数据中255的个数，个数最多的碎片即是原文件的第一行，依次类推，同样的方法即可知道具体的排列顺序，从而得到碎纸片复原的结果.
针对问题3，在问题1和问题2的基础上，继续对所给的附件5进行分析.实际生活中存在很多双面打印的文件，这些双面文件的碎纸片混合在了一起，当对其进行拼接复原时，首先要判断同一面的文字碎片，然后再进行拼接.附件5给出了碎片既横切又纵切的英文文字图像，那么在拼接时依旧有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.首先考虑横向拼接，转换得到180x72的像素矩阵，这些是介于0到255之间的一个像素矩阵，随着图片的增加，相应的增多转换得到的像素矩阵，在问题2的基础上继续进行检验所给的碎纸片图，运用Matlab读取了418张碎片图后，将每张碎片转换得的像素矩阵的第一列以及最后一列各自取出，通过程序进行验证，可以算出匹配度高的相邻碎片，此时进行一次人工干预，拼接出位于同一行的碎片横条；接着考虑纵向拼接，运用Matlab程序对得到的新的横条碎片进行像素分析的提取，配准各个横条的像素矩阵的第一行与最后一行的相关度，综合分析碎纸片上英文之间的行距，进而确定拼接的碎片横条位于哪一行，得到最终的复原结果.
综上所述，以上三个问题的解决流程可用下面的流程图表示：
图2问题解决流程图
三模型假设准备与符号说明
3.1模型的假设
1、假设碎纸机把一页印刷文字文件碎成形状规则，大小一样的碎片，看做形状、大小相同的长方形.
2、在碎纸过程中，只考虑文字被切开，不考虑文字笔画的丢失、碎片添加的任何痕迹等.
3、假设文档碎片的文字的方向已经确定（按照阅读标准确定，从左向左右，自上而下），不考虑碎片图像的旋转问题.
4、图片在复原的过程中，不考虑图片像素的改变，只考虑碎片相对应的固定像素值的匹配问题.
3.2模型准备
不规则几何文档碎纸片计算机拼接的方法一般利用碎片边缘的尖角特征、尖点特征、面积特征等一些几何特征，搜索与之匹配的相邻碎纸片进行拼接，这种基于边界的几何特征的拼接方法并不适用于边缘的形状相似的碎纸片.对于这类边缘相似的碎纸片的拼接问题，理想的计算机拼接的过程与人工拼接的过程类似，即拼接时不仅要考虑拼接碎纸片的边缘是否匹配，还要判断碎纸片内的文字字迹断线或文字内容是否匹配，但是由于理论和技术的限制，让计算机具备类似于人的的那种识别碎纸片边缘字迹断线、以及理解碎纸片内文字图像的含义的智能几乎是不太可能的.
但是利用现在已有的技术，完全可以获取到碎纸片文字所在行的几何特征信息，如文字行的行高及间距等信息.如果利用这些信息进行碎纸片拼接，其拼接的效率就比单纯利用边界的几何特征方法更好.
根据本文题设要求，经考虑分析，本文采取转换矩阵数组元素拼接的技术对破碎的文字文档进行拼接复原.由于计算机数字分析图像能力方面的存在一定的缺陷，让计算机对碎纸片进行完全意义上的自动化拼接页几乎是不太可能，为保证其拼接的准确性，需要在拼接的过程中加入一定的人工干扰过程.一般来说，先利用计算机搜索出于目标碎纸片相匹配的未拼接碎纸片，并根据匹配的程度按顺序到得待选的碎纸片，然后人为地进一步分析结果进行舍弃或拼接待选碎纸片[3].
一页文字文件的碎片拼接复原相当于全景图的生成技术，而相邻图像的配准及拼接是该技术的关键.图像的拼技术一般分为基于图像特征的方法和基于图像灰度的方法.特征提取的方法通常涉及大量的几何与图像形态学的计算，计算量大，没有一般的模型可遵循，但需要针对不同的应用场景来选择各自适合的特征，所提取的图像特征包括更高层的语义信息，基于特征的方法具有尺度不变性和放射不变形.然而基于图像灰度的拼接方法简单简单易行，并且其数字统计模型以及收敛速度、定位精度等均具有定量的分析和研究结果，此类方法得到了广泛的应用.
本文中的文字图像中文字区域的文字结构相对单一，并可能出现相同或相似的字符，因此文字容易出现匹配出现误差.对于文字左右拼接的情况，可以对图片中划分的每行文字进行分析处理，通过提取文字图片的边缘像素矩阵，得到文字出现在图片边缘的那一行高，进一步对一行行的文字拼接复原，这也有利于获取更精确的配准结果.
基于文字的图像灰度的方法不需要提取文字图像的相应的特征，只以两幅图像相连接部分对应的像素灰度的相似性准则来寻找图像的匹配位置.待匹配的图像，首先求出图像中最左边一列的像素矩阵值之和，和最右边一列像素矩阵之和。
然后定义其相连接的区域的相似度可由像对应的像素灰度平方差之和来衡量，其计算文字图片像素与和所搜索的文字图片像素灰度值的距离[4]：
该方法称为差和法其中
分别代表图像各个像素的灰度值，
代表各个像素的坐标.其值最小者所对应的位置为最佳的匹配位置.不过，为了减少计算的工作量和评价标准，这里我们定义对应像素的灰度的绝对值之差然后求和去代替原来的像素灰度平方差之和，其计算文字图片像素与和所搜索的文字图片像素灰度值的距离：
3.3符号说明
————相对应的像素绝对差值
——像素矩阵的像素值
————第
个碎片最后一列与第
个碎片第一列的图像矩阵值和的差的绝对值（
）
————点对的欧氏距离和
————欧式距离和代价
————误差函数
————给定的初始值
四模型的建立和求解
4.1问题1的模型与求解
对于问题1的解决，主要有以下四个步骤：
步骤1确定像素矩阵
运用Matlab程序分别对附件1和附件2中所给出的19张碎片图像进行像素矩阵计算，每个图都对应得到一个
的像素矩阵.
步骤2确定左边第一列碎片
通过Matlab程序筛选出每个像素矩阵的第一列像素值，运用Excel软件统计各列像素值等于255的个数.运算的结果如下图：
图1附件1碎片最左边像素为255的个数
其中横坐标为碎纸片的编号，纵坐标是像素为255的个数。
从上表的结果中，筛选出第一列的像素值为255的个数最多的是编号为008的图片，说明编号为008的图片是附件1中碎纸片复原的拼接顺序中位于左边的第1张图片.
同理，得到附件2中每个图片的像素矩阵的第一列的像素值为255的个数最多的是编号为003的图片，说明编号为003的图片是附件2中碎纸片复原的拼接顺序中位于左边的第1张图片.
步骤3确定碎片顺序
对于本题中出现的形状、大小一样的相邻两块碎片拼接，只需考虑两块碎片灰度的绝对差值[3].因此可运用Matlab程序建立以下模型：
对于待匹配的图像，像素矩阵像素的像素值
，
表示行数，
为列数，其连接区域的相似度可由相对应的像素灰度绝对差值来衡量，即计算第1张图片的图像矩阵的最后一列的像素值与待匹配图片的图像矩阵的第一列的像素值的绝对差值的总和，计算公式如下：
下面先对附件1进行讨论，可通过Matlab程序进行计算得到它们相对应的像素差的绝对值，如下表的结果：
表1附件1碎片008与其他碎片的相素差的绝对值表
碎片编号
000
001
002
003
004
005
97181
110965
116889
124112
107114
78601
碎片编号
006
007
009
010
011
012
111883
98983
111394
101593
92901
98493
碎片编号
013
014
015
016
017
018
119446
27544
84125
112468
11626
86740
根据表1中的数据进行比较，可筛选出与碎片008相对应的像素绝对差值最小的碎片014，即编号为014的碎片能与编号为008的碎片相互匹配重叠，作为拼接顺序的第2张图片.
依次类推，按照相同的方法，在Matlab程序依次筛选出位于拼接顺序的第3张图片，第4张图片，……，第19张图片，从而得到附件1的拼接复原文件（见本文附件一），拼接顺序如下表所示：
表2附件1文件的拼接顺序
顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
编号
0
0
8
0
1
4
0
1
2
0
1
5
0
0
3
0
1
0
0
0
2
0
1
6
0
0
1
0
0
4
0
0
5
0
0
9
0
1
3
0
1
8
0
1
6
0
0
1
0
0
4
0
0
5
0
0
9
同理，计算附件2的第1张图片的图像矩阵的最后一列的像素值与待匹配图片的图像矩阵的第一列的像素值的绝对差值的总和，结果如下表：
表3附件2碎片003与其他碎片的相位差绝对值表
碎片编号
000
001
002
004
005
006
66977
63869
70269
78117
92269
25277
碎片编号
007
008
009
010
011
012
76883
82185
72522
78422
65808
77712
碎片编号
013
014
015
016
017
018
77658
88992
71768
76748
74628
63442
从表3的结果可以看出，附件2中得到与碎片003的像素绝对差值最小的碎片编号为006，即编号为006的碎片能与编号为003的碎片相互匹配重叠，作为拼接顺序的第2张图片.
以此类推，在Matlab程序依次筛选出位于拼接顺序的第3张图片，第4张图片，……，第19张图片，从而得到附件2的拼接复原文件（见本文附件二），拼接顺序如下表所示：
表4附件2文件的复原拼接结果
顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
编号
0
0
3
0
0
6
0
0
2
0
0
7
0
1
5
0
1
8
0
1
1
0
0
0
0
0
5
0
0
1
0
0
9
0
1
3
0
1
0
0
0
8
0
1
2
0
1
4
0
1
7
0
1
6
0
0
4
4.2问题2模型与求解
运用Matlab程序对附件3给出的209个碎片图像进行像素矩阵计算，其中每个图像得到一个
的矩阵，刷选出209个碎片图像中每个像素矩阵的第一列像素矩阵和最后一列像素矩阵，即2个
的像素矩阵.然后对得到209个第一列像素矩阵和最后一列像素矩阵进行列求和.把上述的求和结果转换成一个
的矩阵：
其中第
个碎片最后一列图像矩阵值和与第
个碎片第一列的图像矩阵值和的差的绝对值为矩阵中的元素
（
），比较筛选出矩阵中的第
行所有元素的最小的一个
，则说明第
个碎片的左边与第
个碎片的右边相匹配，这样就完成了附件3的横向拼接顺序，得到11个新的横条碎片.
接着进行纵向拼接，使用Matlab程序分别对得到的所有新的横条碎片进行像素矩阵计算，筛选出11个碎片图像中每个像素矩阵的第一的像素矩阵.用Excel软件统计各个新横条的像素矩阵中第一行数据中255的个数，得到个数最对的碎片是按如下表的顺寻拼接的横条，即该序列的横条位于纵向拼接顺序的第一个.
部分行拼接结果如图2、图3所示：
图2附件3横向拼接复原图
（1）
图3附件3横向拼接复原图
（2）
最后，在对所得新的11个横条处理的问题上，主要有像素矩阵分析法或者直接采用人工干预.由于只有11个横条，并且根据汉字的笔画特征，本文采取用人工干预的方式，对11个横条进行干预，逐一确定，最终得到到附件3的拼接复原结果（见本文附件三、附件四）：
表5附件3部分拼接复原结果
顺序
1
2
3
4
5
6
…
13
14
15
16
17
18
19
编号
0
4
9
0
5
4
0
6
5
1
4
3
1
8
6
0
0
2
…
0
1
1
0
2
2
1
2
9
0
2
8
0
9
1
1
8
8
1
4
1
顺序
20
21
22
23
24
25
…
32
33
34
35
36
37
38
编号
0
6
1
0
1
9
0
7
8
0
6
7
0
6
9
0
9
9
…
1
6
3
0
7
2
0
0
6
1
7
7
0
2
0
0
5
2
0
3
6
顺序
…
…
…
…
…
…
…
…
…
…
…
…
…
…
编号
…
…
…
…
…
…
…
…
…
…
…
…
…
…
顺序
172
173
174
175
176
177
…
184
185
186
187
188
189
190
编号
0
7
1
1
5
6
0
8
3
1
3
2
2
0
0
0
1
7
…
1
7
0
2
0
5
0
8
5
1
5
2
1
6
5
0
2
7
0
6
0
顺序
191
192
193
194
195
196
…
203
204
205
206
207
208
209
编号
0
8
9
1
4
6
1
0
2
1
5
4
1
1
4
0
4
0
…
1
1
7
0
0
4
1
0
1
1
1
3
1
9
4
1
1
9
1
2
3
同理，运用Matlab程序对附件4中给出的209个横纵交切的英文碎片进行像素矩阵计算.参照附件3同样的思路，首先得到横向拼接顺序的11个新的横条碎片，然后再通过纵向拼接顺序干预逐一得到附件4的复原图，附件4的拼接复原结果
升级会员 