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

.-.碎纸片的拼接复原摘要本文主要采用了模糊模型识别、灰度相关、傅里叶变换等方法对碎纸自动拼接进行了深入探讨。文中主要结合司法物证复原、历史文献修复、军事情报获取这一背景，针对横纵切碎自动拼接展开探究。提出一种基于最大梯度和灰度相关的全景图拼接法。同时采用边界提取法使图像预处理达到最好的效果，期间采用傅里叶变换对图像进行处理，最后再利用匹配准则等方法处理图像的拼接。最终应用模糊模型识别法建立模型，通过隶属函数的建立实现最终的碎纸拼接。期间有些碎纸片计算机无法识别，需要进行人工干预，从而才能得到一副完整的复原图。图像拼接的主要工作流程可以概括为以下三个步骤：（1）对图像碎片进行预处理，即对物体碎片数字化，得到碎片的数字图像。（2）图像碎片匹配，通过匹配算法找到相互匹配的图像碎片。（3）图像碎片的拼接合并，将相互匹配的图像碎片拼接在一起得到最终结果。针对问题一：将图像导入MATLAB进行相应的转化，由于数据量较大，所以对数据进行优化提取。计算提取数据的均值与方差，找出其模糊集，建立符合题意的隶属函数。由于模糊集的边界是模糊的，如果要把模糊概念转化为数学语言，需要选取不同的置信水平(01)来确定其隶属关系，从而实现纵切图像的全景拼接。（如表一、表二）针对于问题二：由于是横纵切碎纸片，所得图像较多，采用提取像素法对图片进行灰度分析，通过中介量阈值的确定来找出像素点的差别，梯度值在这一过程中也是作为衡量两张碎纸片是否匹配的标准。从而对数据进行处理，最后导入MATLAB软件实现拼接。（如表三、表四）针对问题三：它是在问题一和问题二上加深了难度，采用提取像素点，傅里叶变换，灰度相关、模糊相似优先比等方法对问题进行分析，通过（0,1）矩阵的简化运算以及傅里叶变换得到最后的结果，但对于傅里叶变换需说明一点，变换之后的图像在原点平移之前四角是低频，最亮，平移之后中间是低频最亮，也就是说幅角比较大。此过程中同时也需要人工干预，最终实现拼接。（如表五、表六）关键词：模糊模型识别灰度相关傅里叶变换梯度值自动拼接.-.一、问题重述1.1问题的背景社会的飞速发展离不开秘要文件的建立，“斯塔西”情报机构官员将大量绝密文件撕成六亿多张碎纸片丢进1600个垃圾袋中，到了当代，历史学家觉得很有恢复的必要，但如果人工拼接将是一个巨大的工程，将要耗费四百年时间。所以这将推动了计算机自动拼接技术的发展。在司法界中，物证额提取也是一项较为重要的环节，所以拼接技术得到了空前的发展。德国等发达国家对破碎文件的修复技术已经进行了相当长时间的研究，但由于技术封锁的原因我们得到的资料是有限的。在国内，碎片拼接技术还不是相当的成熟，因此，结合碎纸拼接技术的重要性这一背景，把计算机视觉和模式识别应用于碎纸复原，所以，对碎片自动拼接技术的探究是十分有必要的，发展到今天，随着拼接技术的提高，应用的领域也越来越广，同时对技术的研究也具有重要的现实意义。1.2问题的提出随着计算机的发展，数字图像处理也随之产生。碎纸拼接技术是图像处理与模式识别领域中的一个很典型的应用。在司法物证还原，历史文献修复以及军事情报获取等领域具有重大的贡献。传统上，拼接复原工作一般由人工完成，虽然具有较高的准确率，但是效率太低。特别当碎纸片数量较大时，人工拼接很难完成此任务。随着计算机技术的发展，人们试图开发碎纸自动拼接技术，高效的完成高难度任务。下面考虑三个问题：（1）对于给定的仅纵切的中英文各一页文件的碎纸片数据进行拼接复原，期间如果涉及到人工干预需写出干预的时间节点，复原结果以图片形式及表格形式表达。（2）对于给定既横切又纵切的中英文各一页文件的碎纸片数据进行拼接复原，如需进行人工干预同上。表达结果要求同上。（3）以上两问均为单面打印，但在现实生活中，大多数情况下是双面打印，此问给出的是一页英文印刷文字双面打印文件的碎纸片数据，表达结果要求同上。.-.二、模型的基本假设(1)假设给出的文件文字清晰，不存在损坏缺失；(2)假设在裁剪过程中碎纸片不存在磨损；(3)假设裁剪出的碎纸片形状、大小相同；(4)假设纸张是方形的；(5)假设横切面和纵切面与边缘分别平行；三、符号说明a：矩阵的均值；2：矩阵的方差；ix：任意碎片中提取的样本；jx：提取样本后在剩余样本抽取的碎片；(1)(,)fxy：待拼接的左图像；(1)(,)fxy:左图像的梯度图像；(2)(,)fxy:待拼接的右图像；(2)(,)fxy:右图像的梯度图像；()(,)Tfxy:拼接模板；()(,)Tfxy:模板的梯度图像；(3)(,)fxy:右图像中某一子图像；(3)(,)fxy:右图像中某一子图像的梯度图像；g(s,t):表示滤波前的图像；(,)fxy:表示滤波后的图像；xyS:表示像素(,)xy的某个领域；(,)GDTR:表示梯度图像()(,)Tfxy和(2)(,)fxy相应位置的梯度差异.-.四、问题分析这是一个利用计算机技术将碎纸片拼接的问题，一种典型的解决平面图像碎片的方法：匹配算法。它是定义一个判别式，把不符合判别式的一对对候选匹配通过多尺度方法逐步从原可能匹配的集合中删除，最后剩下的少量匹配对可能就是真正匹配的图像碎片对。对于问题一，将碎纸片导入MATLAB转化为矩阵，这时生成十九个1980×72的矩阵，由于数据繁多，运算量过大，通过计算方差对数据进行优化处理，选取具有代表性的部分进行分析处理，从而完成纵切的图片拼接。（如表一，表二）对于问题二，由于横纵切图片，所以形成的碎纸片数量较大，如果在采用问题一的做法显然是不明智的，所以，我们采用灰度相关进行匹配，具体做法是：在一幅图中选取一块子图像作为模板，根据某个相似度评价函数对第二幅图像中的像素灰度值进行比较，找出两幅图像的匹配点。同时采用傅里叶变换辅助灰度相关匹配进行拼接。如果灰度相关方法上遇到数据量处理较大的问题，采用变换多分辨率模板将灰度相关变换到不同分辨率上进行，从而精简计算过程。针对问题三，则是在问题一、问题二上增加了难度，必须满足双面拼接，所以我们在这一问运用弹性匹配，灰度相关，提取像素点，傅里叶变换等方法对图片进行拼接。具体操作流程如下图：碎纸片单面双面纵切碎片纵横切碎片纵横切碎片读取碎片转化傅里叶变换为灰度矩阵求最大梯度建立模型并求解复原图.-.最后采用模糊模型识别法建立整体模型，最终实现五张碎纸文件的成功拼接。五、模型的建立与求解5.1问题一模型的建立与求解我们认为，可以采用模糊识别模式。首先针对第一问我们采取将图片导入MATLAB软件，生成19个1980×72的矩阵，由于较大数据量所以我们提取优化的一部分数据进行分析，提取结果如下：25525525525525525525525525525525525525525525525525525525525525512012814213921425525525525525549005208255255255255255790089255255255255255255104001212552552552552552551090012225525525525525525511300122255255255255255255117001222552552552552552551210012225525525525525524312300120242232206218255000000001262550000000012625546130020383310126255255280012225525525524825522200012225525525525525516000012225525525525525599000122255255255255255290001222319518925525500001131904525225502600122107001502550960012223090222433612800122255102001281051280012225518800911831280012225525266187255251128001222552552552552552551280012225525525525525525512800122255255255255234255128001222552552552552512551280012225525525525525525512800122255255255255255.-.由上表数据分析得：221()1,2,,niiaainn，综上可以算出优化后提取的矩阵的均值和方差，代入相关数据，经计算可得：=215.8462a，2=11.2915（1）若已知n个类型在被识别的全体对象U上的隶属函数，则可按隶属原则进行归类。此处介绍的是针对正态模型模糊的情形。对于正态型模糊变量x,其隶属度为2()()xabAxe其中，a为均值，222b，2为相应方差。按泰勒级数展开，取近似值得若有n种类型m个指标的情形，则第i种类型在第j种指标上的隶属函数是(1)2(1)(1)(1)(1)(2)2(2)(2)(2)(2)0,1,1,1,0,ijijijijijijijijijijijijijijijijijxabxaabxabAaxaxaaxabbabx其中，(1)ija和(2)ija分别是第i类元素第j种指标的最小值和最大值，222ijijb，而2ij是第i类元素第j种指标的方差。21,()0,xaxabAxbxab1,(1,2,,)niiaainn.-.（1）若有n种类型12(,,,)nAAA，每类都有m个指标，且均为正态型模糊变量，相应的参数分别为(1)ija，(2)ija，ijb（i1,2，，n；j=1,2，，n）。其中，(1)minijijax，(2)maxijijax，222ijijb，而2ij是ijx的方差。待判别对象的B的m个指标分别具有参数ja，(1,2,,)jbjm，且为正态型模糊变量，则B与各个类型的贴近度为(1)2(1)(1)(1)(1)(2),2(2)(2)(2)(2)0,()11,()2()1,11,()20,()jijjijjijijjijjijjijijijjijjijijjijjijjijijjijjaabbaaabbaabbABaaaaaaaabbbbabba记,1miniijjmSAB,又有01miniijnSS，按贴近原则可认为B与0iA最贴近。将附件1和附件2的碎纸片所提取出的优化灰度矩阵，经过MATLAB软件跟模糊模型对灰度矩阵的处理，得到了附件1和附件2复原后的碎片序号顺序（表一和表二）和复原图（附录\附件1、2的复原图）。表一：附件1复原后的碎片序号顺序表二：附件2复原后的碎片序号顺序5.2问题二模型的建立与求解关于灰度相关匹配，只要模板大，则能做到图像对准精确，拼接成功率较高，但由于需要比较两幅图像的灰度值，所以存在较大的计算量，所以使用多分辨率008014012015003010002016001004005009013018011007017000006003006002007015018011000005001009013010008012014017016004.-.模板将会度相关变换到不同分辨率上进行比较，从而可以从算法上提高效率。在问题一仅纵切建立的模型下，先将问题二中纵切进行排列。排列后，进行人工干预，碎纸片的边缘特征找出首张碎纸片，剩下的碎纸片根据其贴近度进行拼接。基于最大梯度和灰度相关的算法可作如下描述：(,){(,)|(,)}xyfxymediangststS①算法使用梯度最大值来缩小后续基于灰度相关的匹配范围，梯度计算公式：2212(,)[