碎纸片的拼接复原数学建模论文.doc

碎纸片的拼接复原摘要破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作由人工完成，虽准确率高，但效率很低。特别是当碎片数量巨大，人工拼接难以完成任务。因此随着计算机信息技术的发展，开发一个碎纸片的自动拼接技术，并建立简便的拼接复原模型，提高拼接复原效率，具有重要的实现意义。文章通过对所给的附件图片数据进行分析研究，在综合考虑了碎片边缘的尖点特征、尖角特征、面积特征等几何特征下，我们将图片读入电脑，并进行二值化转换，考虑边界值的匹配，建立了图片边界匹配模型。依据模型，只要边界能匹配上就可以拼接，并依次解决了如下问题。对于问题一，由于给定图片来自同一页印刷文字文件仅纵切破碎纸片，针对附件1、附件2给出的碎片数据，建立了碎纸片拼接复原的边界匹配模型。根据模型，我们首先对附件1、附件2中的图片用matlab软件进行二值转化，得到一个储存图片的二值灰度矩阵，并利用边界相关性比较法判断矩阵中两边界变量是否能匹配得上，如果匹配得上就拼接在一起，按此算法，附件1、附件2中的碎纸片就能拼接成功，具体的算法结果见附录中的附件1、附件2。对于问题二，由于碎纸机既有纵切又有横切的情形，算法的设计上要相对复杂一些，我们在前面模型的基础上进行了修改和补充，对图片的上下左右的边界都进行了边界提取。首先，我们选将图片作二值转换，分别用矩阵进行保存，然后任迁一个，对其余的进行全程扫描，按照问题一中的边界匹配模型，逐一对其边界进行扫描匹配，其间，有些矩阵的边界数据可能一样（如空白时），我们便跳出模型，进行适当的人工干预，干预完成，再进入模型进行迭代，按此方法便可拼接成功，具体的算法结果见附录中的附件3。对于问题三，根据现实问题中的双面打印文件的碎纸片拼接复原问题，由于多了双面的问题，在算法的设计上，我们考虑了正反两的边界匹配，在原有模型的基础上，将问题一和问题二的模型相结合，建立一个新的双面碎纸片拼接模型。首先，我们随机选取一张图片，以这张图片为依据，先拼接成其所在的横条或者竖条，再以拼成的横条或者竖条像问题一中模型一样，以整条文字的信息进行拼接，直至整条文件拼接完成，然后再拓展到其它条，最后完成整个图片的拼接。在此过程中要排除边界相似度很高的情况，因此，类似于问题2模型，在模型运行过程中，我们要进行适当的人工干预，具体模型算法及结果见附件5。破碎文件的拼接复原模型是一个具有重要现实意义的问题，我们对问题进行初步的分析，并建立一个初步的模型，由于时间与知识能力方面的问题，模型还比较粗糙，适用性还不是很广，比如随意形状纸片的拼接我还没有考虑，在后面的不断学习过程中，我们可加强模型的完善与改进，使之具有更好的适用性和可移植性。关键词：matlab 自动拼接技术 模式匹配 边界提取 一、问题重述在拼接图片时，需要将所有的图片按照文字的结构以及表述的内容要流畅为依据，所以我们在寻找图片边界闭合的条件就是能拼接在一起的图片，要求其边界信息的相似度很高甚至吻合。在解决规则完整清晰的破碎文件的时候，我们主要的任务就是在成功读取图片的情况下只需要解决图片边界信息的相似度比较，然后进行匹配拼接。碎片对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。附件1、附件2为纵切碎片数据，每页纸被切为19条。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达，表格形式：将碎片序号按复原后顺序填入119的表格；对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。附件3、附件4为纵横切碎片数据，每页纸被切为1119个碎片。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达，表格形式：将碎片序号按复原后顺序填入1119的表格。可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。附件5为纵横切碎片数据，每页纸被切为1119个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有21119个文件。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，复原结果以图片形式及表格形式表达，表格形式：将碎片序号按复原后顺序填入两个1119的表格。二、问题分析这是一个对文字图片进行边缘提取和数值匹配组合的问题，匹配方案要达到以下要求：（1）当对附件1和附件2的匹配时，要求整条碎纸条的左右两边要匹配得上来；（2）当对附件3和附件4的匹配时，除了要考虑左右边界，还要考虑上下边界。要求先做出最左边碎纸片，然后像处理附件1和附件2一样，按照整条来快速往右提取剩下的图片；（3）当对附件5做匹配的时候，实现的方式就是在问题二的基础之上要求到前后两页要满足匹配的条件。三、符号说明符号符号说明，图片序数相关系数图片灰度分布函数图片边缘的梯度值梯度的方向相关系数最大值s图片边缘数值的集合ss集合中的数值目标函数值约束条件四、模型的假设 1.附件所给的碎纸来自原来完整的文件，不缺少，不增多。2.碎纸图片可以二值化，可以直接提取边界。3.每一个附件里面的碎纸图片都是大小一样的规则四边形，图片的内容清晰可见，不影响人工视觉，必要的时候可以进行人工手动。五、模型的建立与求解5.1 问题一的模型建立与求解关于问题一，对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），我们首先假设附件1和附件2中的每张碎纸片图片都是规格大小相同四边形，切口光滑平整，表面整洁。碎纸片的拼接复原就是把来自同一页的碎纸片按照一定的方法，使其拼接还原成原来的形状。我们的做法是：第一，用matlab软件中的imread函数读取附件1或附件2中的碎纸片图片文件，其中每个图片文件都是以一个1980行72列的矩阵的形式来存放图片的灰度值；第二，提取每个图片左边界和右边界的灰度值，保存在同一个矩阵里，形成一个1980行38列的矩阵；第三，从所有图片里找出左边界为空白的那张碎纸片图片，把它定义为纸张的开头；第四，由第一张碎纸片的右边界的灰度值开始，利用相关系数函数corroef分别与余下的所有碎纸片的左边界的灰度值进行运算，相关值最大的，说明两张碎纸片互相吻合，可以进行拼接，两张碎纸片拼接后融为一体，再从这张大的碎纸片的右边界的灰度值开始，分别与剩下的碎纸片的左边界的灰度值进行关联度运算，得出可以拼接的碎纸片，依此类推，最终完成所有碎纸片的拼接工作，达到还原的目的。具体流程图如图1所示，附件1的碎纸片拼接顺序如图2，附件2的碎纸片拼接顺序如图3，编程代码和复原图片见附录。开始对图片的读取提取图片的左右边界灰度值，存放在矩阵里利用相关系数corroef函数对碎纸片进行关联度运算，得出匹配顺序提取左边界灰度值为空的碎纸片作为纸张的开头检查，如个别错误，手动结束流程图 图1序号1234567复原后顺序008014012015003010002序号891011121314复原后顺序016001004005009013018序号1516171819复原后顺序011007017000006附件1拼接顺序数据表图2序号1234567复原后顺序003006002007015018011序号891011121314复原后顺序000005001009013010008序号1516171819复原后顺序012014017016004附件2拼接顺序数据表图3 5.2 问题二的模型建立与求解 问题二中对于碎纸机既纵切又横切的情形，因为此时，图片的拼接不仅仅是左右两边界，还要考虑图片的上下边界，所以，问题二是对问题一的加深和修补。对于这一问题，我们首先对图片的前期工作如读入和提取如前面模型一，接下来的匹配工作，我们首先做的就是先把图片左边空白的用边缘检测提取出来，然后就是上下匹配，完成一小片整条的拼接图，接下来就是按照问题一以整条为单位进行整条整条的边界匹配。 最初使用的配准方法是基于图像的像素灰度信息，直接利用两幅图像的灰度信息，建立两幅图像之间的相似性度量，然后采用某种搜索方法，求取使相似性度量最大变换模型。提出的基于灰度配准方法包括归一化互相关配准方法、基于傅立叶变换的相位配准方法、基于统计矩的配准方法、基于直方图的配准方法等。基于灰度的配准方法具有精度高、概念清晰等特点。开始对图片的读取边界提取左边界信息为空的图片以成功匹配得的整条边的右边界为依据匹配剩下图片的左边界信息以上下边信息为依据匹配组合成最左边整条检查，如个别错误，手动结束流程图 图4边缘检测技术是所有基于边界分割的图像分析方法的第一步，图像的边缘是图像最基本也是最重要的特征之一，图像的大部分信息都存在于图像的边缘中。目前边缘检测方法，常用的有 robert 算子、sobel 算子、prewitt 算子、gauss-laplace 算子等。在图像配准中对边缘检测算子的性能一般要求：能正确检测出有效的边缘；边缘定位精确；受噪声影响小。首先检测出图像局部特性的不连续性，再将它们连成边界，这些边界把图像分成不同的区域，检测出边缘的图像就可以进行特征提取和形状分析。我们运用梯度检测法：设是图片灰度分布函数；是图片边缘的梯度值；是梯度的方向。则有： （1） （n=1,2,.） （2）式（1）与式（2）可以得到图片在（x,y）点处的梯度大小和梯度方向。将式（1）改写为： 当时，图片为左边碎图片。边缘特征点的检测与配准，详细研究了基于边缘轮廓提取特征点和利用提取的特征点进行配准。特征点提取是基于边缘特征点图像配准方法的关键，相似性度量。相似性度量是指用哪种方法来确定待配准特征之间的相似性。它是以某种距离函数或代价函数的形式出现的。相似性度量与特征空间是紧密相连的，因为相似性度量是利用特征提取的信息，特征提取的好坏将影响相似性度量。相似性度量决定了图像配准中参与配准的因素，有利于进一步提高算法性能，常用的相似性度量有相关函数、明考夫斯基距离等。相似性度量和特征空间的选择，可以有效地降低计算量和噪声、遮挡等因素带来的影响，提高配准的精度；相关关系是一种非确定性的关系，相关系数是研究变量之间线性相关程度的量。由于研究对象的不同，相关系数有如下几种定义方式。简单相关系数：又叫相关系数或线性相关系数，一般用字母p 表示，是用来度量变量间的线性关系的量。复相关系数：又叫多重相关系数。复相关是指因变量与多个自变量之间的相关关系。例如，某种商品的季节性需求量与其价格水平、职工收入水平等现象之间呈现复相关关系。典型相关系数：是先对原来各组变量进行主成分分析，得到新的线性关系的综合指标，再通过综合指标之间的线性相关系数来研究原各组变量间相关关系。 进入下一步骤，运用相关系数算法： 得到中文第一列的排序，从上到下的图片号码是049061168038071014094125附件3 最左边拼接顺序表图5（1）029007089附件3 最左边拼接顺序表图5（2）总共十一个号码。对所有图片，运用相关系数算法，把所有图片的排列一一找出来：12345671049054065143186002057206101907806706709916231681000760630620300414038148046161161035081507115608313213201708060141280031591591991357094034084183183047121812501318210910901618490290641112012010921801000720813815815806817511089146102102154040151附件3 完整拼接顺序表图6（1）8910111213141192178118190095011022209613107906311616307230231471910501791200864189122103130193088167503320219801513317020560120731602031691340397042124144077112149097811018706610615002117390480370750550442060101004517400013705305609311207155140185108117004附件3 完整拼接顺序表图6（2） 15161718191129028091188141200617702005203631950260010870184025008009105074508515216502706060310511071151767136164127058043815718120413914591040981721710591015307016603219611101113194119123附件3 完整拼接顺序表图6（3）英文文件，采用同样的算法。由于有些图片四周边界比较特殊，有几张图片的相关系数存在的区别较小。在这里，我们需要视觉手动，把图片分别开来。最终结果在附录显示。5.3 问题三的模型建立与求解 问题三双面打印文件的碎纸片拼接复原，是前面的问题的加深。首先要把附件5里双面打印的文件碎图片读入matlab进行二值化。接着提取图片周边的图片信息，选出正面的左边为空以及后面的右边为空的图片进行上下组合，以组合成的单条为单位，再提取它的整条边的正面的左边和后面的右边的边界数字信息。正面向右后面像左进行匹配运算。做法的流程图如下图7： 开始对图片的读取图片的前后页分开存放提取左边为空的图片以及右边为空的图片作为整纸张的左开头匹配当左边为空的图片进行上下组合的最优解时同时符合背面右边为空的图片的上下组合当把整张纸的左边一列拼接得后，以此为单位和前后图片的分类基础上，前页就往右匹配时候要满足后面页往左匹配的条件，直到成功检查，如个别错误，手动结束流程图 图7问题三使用相位相关度法运算。 aco 中的人工蚂蚁代表的是一个随机构建过程，在构建过程中通过不断向部分解添加符合定义的解成分从而构建出一个完整解。因此，aco 元启发式算法可以应用到任何能够定义构建性启发式的组合优化问题。也就是说，aco 元启发式算法可以应用于任何组合优化问题中，但真正的问题在于怎样把要求解的问题描述成 aco 要求的表达方式。 考虑一个最小化问题，其中 s 是图片边缘数值的集合， 是目标函数，对于每一个数值都对应着一个目标函数值 ，是约束条件的集合。为了简化起见，这里只讨论静态组合优化问题，所以不考虑时间对目标函数和约束 的影响。问题的目标就是要找到一个全局最优可行解 ，也就是在最小化问题中具有最小成本代价的可行解。组合优化问题对应的问题描述。具有如下特征：1) 给定问题成分的有限集合，其中是图片的个数。2) 问题的状态由 上的元素组成的有限长度序列 定义。所有可能状态的集合用 来表示。3) 图片边缘数值的集合 是 的一个子集(即， )。4) 一个可行解的集合 ，有 ，这个集合是通过与问题有关的实验进行定义的，而这些实验还验证了把序列扩展成一个满足约束的完整解并非是不可能的。5) 最优解的非空集合 ，具有 和 。6) 每一个候选解 都关联着一个成本代价 。大多数情况下，对，都有 ，其中 是可行候选解的集合。 给定上述的问题描述，人工蚂蚁就可以在完全连接图 上通过随机游走来构建解，其中图上的点是 中的成分，集合完全连接 中的成分点。图 成为构建图，中的元素成为连接。最终结果见附录。六、模型的结果分析 6.1.1对于问题一模型结果的分析： 优点：实事求是，思路简单，算法已经得到正确的运行和检验。缺点：题目要求考虑的影响因素较少，但是用到的编程问题较难解决。 6.1.2对于问题二模型结果的分析：优点：对于问题的条件，在模型建立初期，因是考虑到与问题一的关系，我们的算法建立在问题二基础上进行改进，所以考虑得比较细腻，模型设想比较完整。 缺点：由于模型比较复杂，没有成功建立起来，没得计算误差，手动比较多。 6.1.3对于问题（3）模型结果的分析： 优点：对于解决双面的文字图片，我们考虑像前面的汇合，所以模型通用，约束条件增加。 缺点：模型复杂，难以建立。 七、模型的优缺点以及改进方向优点：本文使用了相关系数算法，回归算法，对简单的碎纸片完成了相应的拼接工作，并建立了相应的模型，模型具有一定的适用性。缺点：对于建立的模型比较原始，很少加入自己改进的方法。没有得到正确的检验，尚未知道模型的缺陷以及改进的方法。改进方向：这次的拼接对象是相对简单的文字图片，我们设想以后类似的拼接工作，不可能出现这么简单，对于出现更多的干扰因素。比如，图片文字信息受污染或其他原因而缺失，个别图片缺失造成数量上的不完整，或者是不规则的多边形，造成边界的多样性。这样我们可以通过建立其它的约束条件或者模型方法来解决可能出现的问题。 八、参考文献1 贾海燕,朱良家,周宗潭,胡德文. 一种碎纸自动拼接中的形状匹配方法j. 计算机仿真,2006,11:180-183.2 张欣,卜彦龙,朱良家,周宗潭. 物证复原系统中的碎纸轮廓提取技术研究j. 计算机仿真,2006,11:184-187+279.3 王正勇,何小海,吴晓红. 基于边缘特征和keren算法的图像配准j. 计算机工程与应用,2008,33:25-27.4 郝万里. 基于边缘特征的图像配准算法研究d.沈阳理工大学,2012.5 宋宝森. 全景图像拼接方法研究与实现d.哈尔滨工程大学,2012.6 邵向鑫. 数字图像拼接核心算法研究d.吉林大学,2010.7 张春玉. 平面碎片匹配复原技术研究d.西北大学,2009.8 林璐. 图像配准与拼接技术研究d.长春理工大学,2010.9 何鹏飞. 基于蚁群优化算法的碎纸拼接d.国防科学技术大学,2009.10叶耘恺. 基于边缘特征的图像配准方法研究d.重庆大学,2004.11贾海燕. 碎纸自动拼接关键技术研究d.国防科学技术大学,2005.12罗智中. 基于文字特征的文档碎纸片半自动拼接j. 计算机工程与应用,2012,05:207-210.13杨小冈,曹菲,缪栋,张云鹏. 基于相似度比较的图像灰度匹配算法研究j. 系统工程与电子技术,2005,05:918-921.14苗琦龙,栾新. 基于遗传算法和bp网络的文字识别方法j. 计算机应用,2005,s1:330-332.15王轩. 碎片拼接d.浙江大学,2011.16周石林,廖文和,尹建平. 平面碎片匹配算法的研究j. 计算机工程与应用,2009,31:151-153.附录：附录一：代码：a0=imread(000.bmp);a1=imread(001.bmp);a2=imread(002.bmp);a3=imread(003.bmp);a4=imread(004.bmp);a5=imread(005.bmp);a6=imread(006.bmp);a7=imread(007.bmp);a8=imread(008.bmp);a9=imread(009.bmp);a10=imread(010.bmp);a11=imread(011.bmp);a12=imread(012.bmp);a13=imread(013.bmp);a14=imread(014.bmp);a15=imread(015.bmp);a16=imread(016.bmp);a17=imread(017.bmp);a18=imread(018.bmp);b=zeros(1980,38);b(:,1)=a0(:,1);b(:,2)=a0(:,72);b(:,3)=a1(:,1);b(:,4)=a1(:,72); b(:,5)=a2(:,1);b(:,6)=a2(:,72);b(:,7)=a3(:,1);b(:,8)=a3(:,72);b(:,9)=a4(:,1);b(:,10)=a4(:,72);b(:,11)=a5(:,1);b(:,12)=a5(:,72);b(:,13)=a6(:,1);b(:,14)=a6(:,72);b(:,15)=a7(:,1);b(:,16)=a7(:,72);b(:,17)=a8(:,1);b(:,18)=a8(:,72);b(:,19)=a9(:,1);b(:,20)=a9(:,72);b(:,21)=a10(:,1);b(:,22)=a10(:,72);b(:,23)=a11(:,1);b(:,24)=a11(:,72);b(:,25)=a12(:,1);b(:,26)=a12(:,72);b(:,27)=a13(:,1);b(:,28)=a13(:,72);b(:,29)=a14(:,1);b(:,30)=a14(:,72);b(:,31)=a15(:,1);b(:,32)=a15(:,72);b(:,33)=a16(:,1);b(:,34)=a16(:,72);b(:,35)=a17(:,1);b(:,36)=a17(:,72);b(:,37)=a18(:,1);b(:,38)=a18(:,72);c=zeros(38,38);for i=1:2:38 for j=2:2:38 if i+1=j j=j+2; end if j=40 break end p=corrcoef(b(:,i),b(:,j); c(i,j)=p(2,1); endendtou=17;m=1;f(1,1)=(tou-1)/2;for n=1:18i,j=find(c=max(c(:,tou+1);y=(i-1)/2;f(1,m+1)=y;tou=y*2+1;m=m+1;endff1=a8 a14 a12 a15 a3 a10 a2 a16 a1 a4 a5 a9 a13 a18 a11 a7 a17 a0 a6;imshow(f1) 附件1复原顺序的表格序号1234567复原后顺序008014012015