2014全国大学生数学建模大赛.doc

碎纸片的拼接复原摘要本文讨论了三种情况下的碎纸片复原问题。通过聚类分析、灰度匹配、人工干预的方法，借助MATLAB软件，建立三个数学模型，分别给出了三个问题的解决方案。针对问题一的情形，我们建立了边缘识别模型。首先，将图像像素映射成灰度矩阵，然后利用灰度矩阵边缘特征的相关匹配原理，用MATLAB软件提取每个矩阵的左右边缘信息，并对二值化的图像进行相似匹配。最后，利用迭代数列函数找出所求碎片的排列顺序，对附件1及附件2给出的碎片各拼接成一张完整图片。针对问题二的情形，建立了基于文字特征的模式识别模型。通过研究碎纸片内文字行特征，提出了基于碎片文字行特征的碎片拼接算法。如果碎片内的文字行在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行或表格，因而可以很容易地从形状相似的多碎片中挑选出相邻碎片。其方案是先运用MATLAB软件对209个碎片进行聚类分析，共分成11类，然后利用问题一的方法对每一类的碎片进行拼接，最后对附件3及附件4给出的碎片各拼接成一张完整图片。针对问题三的情形，建立基于文字特征的双模式匹配模型。首先基于问题二，根据碎纸片内英文文字的行特征，进行两次边缘识别检索，分别检索出a面和b面，然后通过人工干预进行匹配，最终得出正反面碎纸片的排列顺序。为了检验所建立的模型对碎片拼接复原的效果，对模型进行了灵活性检验和误差分析，做出了优缺点评价以及可行性建议。关键词： 碎纸片拼接 模式识别 边缘匹配 聚类分析 一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。【数据文件说明】(1) 每一附件为同一页纸的碎片数据。(2) 附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。(3) 附件3、附件4为纵横切碎片数据，每页纸被切为1119个碎片。(4) 附件5为纵横切碎片数据，每页纸被切为1119个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有21119个文件，例如，第一个碎片的两面分别对应文件000a、000b。【结果表达格式说明】(5) 复原图片放入附录中，表格表达格式如下：(6) 附件1、附件2的结果：将碎片序号按复原后顺序填入119的表格；(7) 附件3、附件4的结果：将碎片序号按复原后顺序填入1119的表格；(8) 附件5的结果：将碎片序号按复原后顺序填入两个1119的表格；(9) 不能确定复原位置的碎片，可不填入上述表格，单独列表。二、模型假设与符号说明2.1模型假设结合本题实际，为了保证模型求解的准确性和合理性，我们排除了未知因素的干扰，提出了以下三点假设：1碎纸机破碎纸片时对印刷文字无磨损；2假设纸张为完整的一张纸，且页边距部位零3人工干预不对所建立的模型或函数造成误差，也不会对碎纸片数据造成影响；4印刷文字规格均相同，不存在文件中出现不同种类文字的现象；2.2符合说明A 一维数组B一维数组BJ数组B中的第J个元素Ii第i块碎纸片的灰度矩阵Ii第i块碎纸片灰度矩阵的首末两列Ii对Ii二值化处理后的矩阵LIiLIi最首列RIiRIi的末列Si K值三、问题分析与模型建立3.1 针对问题一建模3.1.1问题一分析当碎片数量巨大，人工拼接很难在短时间内完成任务，我们考虑利用计算机实现碎纸片的自动拼接或识别，将碎纸片数字化。通过MATLAB软件编程 1可以很好地实现这样的转化。利用MATLAB将图像转换成灰度矩阵，再对灰度矩阵进行二值化的数据处理，这就是实现碎纸片利用计算机处理而得到拼接复原的基本思想，之后根据具体问题做出相应处理。3.1.2建立模型I第一步：将附件一中的图片利用MATLAB进行图像想数字的转化，将图片批量导入之后再分析附件一中的图片特点。问题一图片为纵切，因此我们只须对列进行研究；第二步：根据常识，每页纸都有页边距，因此，切开后只有两块碎纸片有页边距，也即这两块碎纸片具有这样的特征：其中必有一块左侧边缘有空白，其中一块右侧边缘有空白，空白转换成灰度矩阵即为255，由此可编程寻找首末两块碎纸片；第三步：如果一张纸被撕成两片，那么中间相邻部分的对应位置是极为相似的，由此，两相邻边缘作差取绝对值求和肯定最小。依据这个原理的在MATLAB中编程实现计算机自动识别与某一块相匹配的块。3.2针对问题二建模3.2.1问题二分析问题二旨在将经过横纵切方式切割后得到的碎纸片拼接复原，首先，我们获取碎片文字所在行的几何特征信息，比如文字行的行高、文字行的间距等信息，拼接碎片时如利用这些信息进行拼接，其拼接效率无疑比单纯利用边界几何特征方法要好些。由于文字文档的文字行方向和表格线方向平行且单一，如果碎片内的文字行或表格在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行或表格，凭此特征可以很容易地从形状相似的多碎片中挑选出相邻碎片。因文字行或表格线的高度特征、间距特征的识别比字迹断线识别和文字图像的理解实现起来要容易得多，利用碎片内文字行特征或表格特征拼接形状相似的碎纸片理论上是可行的。同一行的字体处于同一高度，如下图所示： 另一方面由于可能出现两行或者多行行列高度相同的图像，计算机数字分析图像能力的缺陷，让计算机对碎片进行完全意义上的自动化拼接也几乎不太可能，为保证拼接的准确性，需要在拼接过程中加入人工干扰过程。一般而言拼接碎片时先利用计算机搜索与目标碎片匹配的未拼接碎片，并根据匹配程度显示待选碎片，操作员再根据人脑进一步分析结果舍弃或拼接待选碎片，这种半自动拼接2。这种方法综合利用了计算机高速计算能力以及人的文字图像识别和理解能力，拼接效率比纯人工高，拼接准确性也好于纯计算机拼接法。本文将详细研究这种基于文字特征、表格特征的碎片半自动拼接方法。3.2.2建立模型II为了研究横纵切碎纸片问题，本文建立模型II：基于文字特征的模式识别模型，所采用的主要方法是聚类分析 3，步骤如下：第一步：利用模型一求出最左侧的一列碎片 Ci；第二步：利用模型二求解左侧碎片Ci所在行的图片第三步： 把每一行的图片看成一类，再次利用模型一排除第i行的顺序第四步： 矩阵逆置第五步： 未实现连接的行，用人工方式连接起来。3.3针对问题三建模3.3.1问题三分析 问题三是在问题一与问题二的基础上复杂化，问题三所处理的对象为双面打印横纵切结合英文碎纸片，我们通过寻找问题三与问题一、问题二的相似关系，可以在模型I和模型II的基础上对模型进行进一步优化，结合一定的人工干预，最终可以确定灰度矩阵的最终匹配行与列，确定碎纸片的排列顺序。3.3.2建立模型III第一步：利用模型一求出最上侧的一列碎片 Ci；会出现38个碎纸片，然后基于模型一进行两次边缘匹配，得到两行碎纸片，分别为a,b面；第二步：接下来重复执行上述执行Ci+1；第三步：根据这次得到的a,b面与Ci次得到的a,b面人工干预确定怎么连接；第四步：未实现连接的行，用人工方式连接起来。四、模型求解4.1模型I求解将图片导入MATLAB 中的到总灰度矩阵Gray1和每块矩阵Ii(i=119)Gray1=I1,I2,I3,I19其中，I1=A11,1A11,72A11980,1A11980,72I2=A21,1A21,72A21980,1A21980,72I3=A31,1A31,72A31980,1A31980,72I17=A171,1A171,72A171980,1A171980,72I18=A181,1A181,72A181980,1A181980,72I19=A191,1A191,72A191980,1A191980,72分别表示块000到块019的相对应的灰度矩阵。之后我们将Ii(i=119)中首末两列取出来分别为Ii(i=119)，并将新矩阵Ii(i=119)中不等于零的元素全部置1，等于零的元素不做处理，这样又得到一个新矩阵Ii(i=119)，规定Ii(i=119)左侧一列为LIi(i=119),右侧一列为RIi(i=119)这样再做如下处理： Si=i=119LIi-RIj 其中j=119 ;再取这19个中最小的Si的下标存放在数组B中,J=119 B=B1,B2,B18,B19 BJ=MinS1,S2,S19这里的BJ表示第J-1块碎纸片后面所跟的块IBJ设之前找到的首列为Ii（此时确定值），假设Ii后面跟的是BJ（此时为确定值），定义BBJ为取数组B中第BJ个数据。利用迭代法依次在进行拼接方程如下：A=Ii,IBJ A=A,IBBJ设有N块碎纸片公式（5）为给A赋初值将公式（6）循环进行N-1次即可实现全自动拼接，拼接后所得图片编号见附件1顺序和附件2顺序。4.2模型II求解将图片导入MATLAB 中的到总灰度矩阵Gray1和每块矩阵Ii(i=119)Gray1=I1,I2,I3,I19其中，I1=A11,1A11,72a11980,1a11980,72I2=A21,1A21,72A21980,1A21980,72 I3=A31,1A31,72A31980,1A31980,72I19=A191,1A191,72A191980,1A191980,72分别表示由块000到块019的相对应的灰度矩阵。将Ii(i=119)中首末两列取出来分别为Ii(i=119)，然后将新矩阵Ii(i=119)中不等于零的元素全部置1，等于零的元素不做处理，这样又得到一个新矩阵Ii(i=119)，规定Ii(i=119)左侧一列为LIi(i=119),右侧一列为RIi(i=119)这样再做如下处理：Si=i=119|LIi-RIj|其中j=119 ;再取这19个中最小的Si的下标BJ=MinS1,S2,S19，所得拼接后的图像可见附件3顺序和附件4顺序。4,3模型III求解将图片导入MATLAB 中的到总灰度矩阵Gray1和每块矩阵Ii(i=1207)其中，I1=A11,1A11,72a11980,1a11980,72I2=A21,1A21,72A21980,1A21980,72 I3=A31,1A31,72A31980,1A31980,72I19=A191,1A191,72A191980,1A191980,72分别表示由块000到块019的相对应的灰度矩阵。将Ii(i=119)中首末两列取出来分别为Ii(i=119)，然后将新矩阵Ii(i=119)中不等于零的元素全部置1，等于零的元素不做处理，这样又得到一个新矩阵Ii(i=119)，规定Ii(i=119)左侧一列为LIi(i=119),右侧一列为RIi(i=119)这样再做如下处理：Si=i=119|LIi-RIj|其中j=119 ;再取这19个中最小的Si的下标Gray1=I1,I2,I3,I19其中，I1=A11,1A11,72A11980,1A11980,72I2=A21,1A21,72A21980,1A21980,72I3=A31,1A31,72A31980,1A31980,72I17=A171,1A171,72A171980,1A171980,72I18=A181,1A181,72A181980,1A181980,72I19=A191,1A191,72A191980,1A191980,72分别表示块000到块019的相对应的灰度矩阵。之后我们将Ii(i=119)中首末两列取出来分别为Ii(i=119)，并将新矩阵Ii(i=119)中不等于零的元素全部置1，等于零的元素不做处理，这样又得到一个新矩阵Ii(i=119)，规定Ii(i=119)左侧一列为LIi(i=119),右侧一列为RIi(i=119)这样再做如下处理： Si=i=119LIi-RIj 其中j=119 ;再取这19个中最小的Si的下标存放在数组B中,J=119 B=B1,B2,B18,B19 BJ=MinS1,S2,S19这里的BJ表示第J-1个碎纸片后面所跟的块IBJ假设之前找到的首列为Ii（此时确定值），假设Ii后面跟的是BJ（此时为确定值），定义BBJ为取数组B中第BJ个数据。利用迭代法依次在进行拼接方程如下：A=Ii,IBJ A=A,IBBJ设有N个碎纸片，公式（5）为给A赋初值将公式（6）循环进行N-1次即可实现全自动拼接，拼接后所得图片编号见附录附件5a顺序和附件5b顺序。五、模型的检验与模型的评价5.1模型的检验5.1.1检验分析 模型有一个更客观、更科学的评价，需要分别对原问题所建立的三个模型进行不同角度的检验。模型I和模型II建立之初的目的是拼接复原出仅纵切和横纵切文字印刷碎纸片，模型III的适用对象是将双面英文打印碎纸片拼接复原，因此可以就每种模型的特点分别采用其适用的对象进行检验，即若我们检验模型I，则选取单面打印纸经纵切后所得碎纸片作为检验对象，同理具有附件3、附件4和附件5特点的碎纸片可以作为模型II和模型III的检验对象。对模型的检验可以采用多种方法和多种指标，全面的检验策略将对模型的改进起到积极的作用。5.1.2检验方法（1）准确性检验 对模型的准确性检验，是最为重要的检测方法，如果所建立的模型经过准确性检测，不能达到令人满意的效果，则该模型不具有或者具有很弱的可行性。对于模型I， 我们通过程序在MATLAB中所得的图像结果与完全人工拼接验证后所得到的结果完全相同，这就证明了模型I的准确性。而对于模型II和模型III的准确性检验，由于附件3、附件4和附件5碎片数据的巨大工作量，采用原拼图检验是不可取的，因此我们可以自制碎纸片进行准确性检验。（2）实用性检验实用性检验主要考虑所建立的模型在处理同类对象时的效果，这一点我们可以相对图像拼接技术在社会生活中的应用。在建立三个模型的时候，都给出了利用计算机MATLAB程序，因此可以利用这些程序，检验其在司法物证复原、历史文献修复以及军事情报获取等领域的有效性。（3）创造性检验在我们建立模型时，收集了一些碎纸片拼接复原技术方面的资料，通过与那些方法作对比，发现仅仅就模型I来看，就会在更短的时间内将碎纸片拼接复原，这些碎纸片并没有非常显著的规律，对于问题二和问题三中我们所建立的模型来看，由于加进了少量的人工干预，使得与其他方法在作对比时较为困难，因此，有必要更为系统地对所建立的这三个模型进行进一步地创造性探究。5.1.3评价结果（1）优点本文所用数学模型综合利用了计算机高速计算能力以及人的文字图像识别和理解能力，拼接效率比纯人工高，拼接准确性也好于纯计算机拼接法，这是我们在模型检验中得到的结论，速度快也正是解决了我们建立碎纸片拼接复原的最终问题，达到了我们想要的最终目的。在准确性方面，通过程序的调试，将问题一到问题三中所要求的三张图片完整地拼接复原，所得到的图像可见附录中的附表5.在实用性方面，我们剪切了一系列的完整相片，对同一张相片通过三种切割方式（即纵切、横切纵切结合以及将相片折叠为两层后再进行横切纵切结合）切割，然后照样将零散的相片碎纸片进行扫描，利用我们针对原来三个问题所分别建立的三个模型，最终未出乎意料地将完整地相片信息一一展现在Matlab程序拼接复原后的荧屏前，证实了模型的实用性。最后，我们通过收集相关资料，对现存的各种图片拼接技术方法进行了对比，我们的模型可以应对不同的情况，解决了很多技术所存在的弊端问题，这证实了模型的创造性。尤其是模型III，不仅可以快速地拼接出双面打印英文碎纸片的排列顺序，还可以通过拼接出a面然后利用b面进行检验，这样能够大大提高拼接碎纸片的准确率，降低偶然情况发生的概率。（2）缺点在对模型及对应的程序做了各项检验后，在避免了许多拼接复原技术弊端的前提下，也发现了模型I、II、III所存在的缺点。至于模型I，它的缺陷是适用范围相对较小，从题目的程序中我们就可以知道，模型I只是适用于纵切图片之间的拼接，当然这是由我们最初的目的所决定的。至于模型II和模型III，我们发现它们的特点是都需要在程序的自动化中加以适当的人工干预作为辅助。5.2模型的误差分析与排除5.2.1模型误差分析数学模型一般是在忽略了很多实际因素的情况下建立，就是所谓的理想化模型，误差分析主要抓住，当我们在建立模型时，忽略了那些因素，要对考虑该因素若加入到模型中，会产生怎样的变化。数学模型是对现实世界的理想化，不可能是真实世界的再现。任何数学模型在建立和使用的过程中，不可避免的产生模型误差。在碎纸片的拼接复原中会附加进数据测量误差，舍入误差和截断误差等。有必要对所建立的三个问题的模型进行分析，并给出估计。5.2.2误差排除方法设计一般来说，在进行误差排除的时候，首先要做的应该是在建立模型之前尽量控制实验数据的质量，使之测量准确可靠，当碎纸片数据带有无法消除的测量误差时，应该分析它会对三个模型所造成的影响，并对模型误差进行估计。在碎纸片拼接时要注意灰度矩阵的函数近似截断误差排除，我们利用的模糊数学分析方法，在处理一些函数问题时是一定存在数值误差的，因此可以采用泰勒近似式等的误差控制函数，并通过对碎纸片的整体边缘像素数据进行分析，以判断我们的假设是否合理。六、模型的改进和推广6.1模型的改进 本文建立的三个图形拼接模型，在改变横切或者纵切碎纸片像素相关性、灰度分布特性的同时，很难