《2013全国数学建模竞赛__碎纸片拼接复原》由会员分享，可在线阅读，更多相关《2013全国数学建模竞赛__碎纸片拼接复原（55页珍藏版）》请在金锄头文库上搜索。
1、.word格式.2013高教社杯全国大学生数学建模竞赛重庆工商大学 姜木北小组作品编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）.专业.专注.碎纸片的拼接复原摘 要目前，“碎片拼接复原”技术在司法物证复原、历史文物修复及社会生活各项领域扮演着重要角色，对于碎片数量特别巨大而人工又难以在短时间内完成碎片拼接时，要找到一种高效快捷的自动拼接方法已变得尤为重要。本文针对只有中英文的碎片拼接问题，综合分析了从单一的纵切到纵横切以及纵横切双面碎片这三个不
2、同的情况，提出了碎片拼接复原的解决方案.在问题一中，对于仅有“纵切”且数量相对较少的碎纸片，我们基于边缘去噪和采用构建碎纸图片的左右边缘二值矩阵提取相似度分析的方法，再通过两张图片左右相似度匹配排序，得到附件1和附件2中的碎纸排序（见表2和表3），并运用Matlab的图像处理工具箱，按排列顺序导入碎纸片得到相应拼接结果（见附录附件一）.在问题二中，由于碎纸片数量相对较多，同时存在横切和纵切的情况，在问题一的基础上增加了碎纸片的上下边缘相似度匹配。在进行人工干预，找到第一张起始碎纸片作为匹配起点后，我们基于索贝尔算子的原理，对碎纸片灰度值进行边缘相似度的旋转检测和比较匹配，最后进行二叉树搜索排序
3、（见表4和表5）。对附件3和4的碎纸图片拼接出的结果详见附录中的附件二.在问题三中，由于碎纸片是两面的并且碎纸片数量更多，若采用第二问的求解方案则加大了求解难度同时也存在较大误差。因此，我们基于蚁群算法（ACA）的SIFT特征点匹配原理来求解。先提取碎纸图片特征点，然后基于蚁群算法的最优化快速比对匹配，最后基于ACA的搜索排序对碎纸片拼接。Matlab编程所求得的排序结果详见表6和表7，附件5中的碎纸片拼接复原结果见附录中的附件三.在问题的解决中，我们得出结论:碎纸图片导入量越小，图片匹配出的效果越佳，在相似度的匹配上，出现的误差减小,最后拼出的图像效果好，人工干预量也相对小。本建模考虑到了图
4、片噪声对图片拼接时的影响，选择了去噪效果较好的邻域平均法对图片进行处理。但是，为了解题方便，我们忽略了碎纸机切纸时碎纸片可能产生的边界遗失破损。在这里我们的改进是，对于边界遗失图像碎片的修复，根据复原后的整体形状，可以根据线连续性来拟合此类线段,从而得到较为完整的图像.关键词：碎纸拼接、腐蚀算法、蚁群算法、图像特征匹配、邻域平均法一、问题的重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提
5、高拼接复原效率。现解决如下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达.2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上.3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题
6、需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上.二、问题的分析本题是一个关于碎纸片拼接复原的问题，针对题目的要求，我们对于“碎纸片拼接复原”等一系列问题的处理特点和处理方案，就每个问题做除了以下的具体分析： 21针对问题1的分析结合给出的碎纸机碎片情况，分别是一页中文和英文文件的碎片数据，也就是说，在每张碎片中都会出现相当多的完整或不完整的汉字（英文）或者结构，要解决把纵切的碎纸片拼接复原的问题：首先，利用MATLAB编程建立图片的二值矩阵。鉴于纸片的大小相同，并且只有黑白两色，通
7、过观察附件一的碎片，每张碎片最左端或者最右端不是全空，这些碎片就可以全部转化为二值图，0代表白色，1代表黑色。其次，采用邻域平均法对图像进行边缘去噪，进一步利用分割最佳阈值的迭带算法来达到消除或减少噪声影响的效果。最后，比较图像左右边缘的相似情况,从而得出两个边缘图像的相似度,以此来度量两个图像能否匹配。复原过程中需要人工干预，将依顺序显示的未拼接碎片，采用半自动拼接，即人工选择碎片并拼接到计算机屏幕上。将序号排列好后；再通过基于MATLAB编程将19张图片分别排好序通过调用imshow()函数合成图片，这样就能得到最终求解结果.22针对问题2的分析求解要求中我们可以知道该问题在第一问的基础上
8、增加了“横切”碎片，出现的纸张既有横切又有纵切。解决方案与第一问有所不同；增加了“横切”过后，在第一问的左右相似度比较之上增加了上下边缘的相似度比较和匹配。但考虑到求解精度我们采用灰度值（0255）求解的图片处理方法；同样基于MATLAB编程对附件3和附件4中的碎片分别进行灰度处理得到图片矩阵的灰度值；并采用基于Sobel 的算法对个碎片进行四个边的边缘化处理，提取边缘特征，并对其进行边缘相似度的计算。同时对边缘化处理后的灰度值进行聚类分析确定一个阀值，也就是确定一个误差值。只考虑切缝处并对其相似度一致的缝合。又由于该问中需要拼接的图片数量众多，我们采用基于二叉树的搜索排序算法对相似度矩阵排序
9、并得到该相似度矩阵所对应的图片序列号数组，该排列的序列号数组即为碎片的组合方式；最后采用MATLAB循环调用序列号数组对应的碎片名拼接出所求结果达到解决该问题的目的.2.3针对问题3的分析对于问题3其实是在问题二的基础上在增加了正反面的拼接。另外通过分析题目中告诉了的类容可以发现附件中同一个序号表示是一张碎纸图片，a和b表示同一张碎片的了两面，但并不确定a和b的正反。这样同第二问中的解决思路相似，但由于问题三中对应的附件5的碎图片数据量过大如若采用第二问的求解方式也并不理想所以我们采用基于蚁群算法（ACA）的SIFT特征点图像碎片拼接方法。针对附件五中的图片基于MATLAB采用所设计的算法提取
10、其特征点并建立特征点匹配矩阵。再利用这些特征点匹配矩阵根据理论建模设计基于MATLAB的算法求解出顺序排列的部分序列号和误差节点。将其中求得的序列号对应的碎纸图片导入MATLAB中求解出拼接图像，最后通过人工干预的方式补全各个残缺节点的碎片得到完整的纸片图像已达到拼接出碎纸片的正反两面的目的.三、模型假设1、 假设未碎纸张的文字行方向沿水平方向，字与字之间有间隔且字宽度与高度比值1/3；2、 假设碎片模型为理想模型，碎片表面光滑平整无磨损且厚度为零；3、 假设在切割过程中除边界外，其他切割线都切割文字；4、 假设每张碎纸片的大小一致；5、 假设碎纸机切的纸片无损坏；6、 假设碎图片中的文字符字
11、体格式相同，英文字符字体格式相同. 四、符号的定义图像平面上的一系列平均噪声点，第个二值矩阵图像的分割阀值，即灰度值阀值，灰度均值，待测边缘图像边缘点经横（纵向）边缘检测的图像梯度方向第i像素和它的K连通像素边缘相似度不同中心像素点的协议变量，为启发式因子的相对重要程度为信息素的相对重要程度为信息素蒸发系数表示信息素的持久性系数为窗口信息素含量五、模型的建立及求解5.1 问题一模型的建立及求解算法的流程图：载入图像建立图片的二值矩阵采用邻域平均法进行边缘去噪比较图像左右边缘的相似情况运用腐蚀算廓提取方法来消除图像的左右边界的作用图15.1.1、把图像转化为二值矩阵二值图像是指每个像素不是黑就是
12、白，其灰度值没有中间过渡的图像。二值图像一般用来描述文字或者图形，其优点是占用空间少，人们经常用黑白、B&W、单色图像表示二值图像，但是也可以用来表示每个像素只有一个采样值的任何图像，例如灰度图像等.因此针对问题一，我们先将对应的碎纸图片用Matlab调用im2bw函数对导入的碎纸图片求解其二值矩阵.5.1.2、图像边缘去噪邻域平均法邻域平均法是一种利用Box模板对图像进行模板操作（卷积操作）的图像平滑方法最简单的平滑滤波是将原图中一个像素的灰度值和它周围邻近像素的灰度值相加，然后将求得的平均值作为新图中该像素的灰度值。它采用模板计算的思想，模板操作实现了一种邻域运算，即某个像素点的结果不仅与
13、本像素灰度有关，而且与其邻域点的像素值有关.将附件1或2中已经进行二值化的碎纸片矩阵惊醒边缘去噪处理，消弱噪声点起到平滑作用，减小相似度误差，增大匹配准确度.设为给定的含有噪声的图像，经过邻域平均处理后的图像为，则邻域平均法也可以用数学公式表达： (1)式中：，；是以为中心的邻域的集合，M是S内的点数.邻域平均法的思想是通过一点和邻域内的像素点求平均来去除突变的像素点，从而滤掉一定的噪声，其主要在实际应用中，也可以根据不同的需要选择使用不同的模板尺寸，如33、55、77、99等。邻域平均处理方法是以图像模糊为代价来减小噪声的，且模板尺寸越大，噪声减小的效果越显著。如果是噪声点，其邻近像素灰度与
14、之相差很大，采用邻域平均法就是用邻近像素的平均值来代替它，这样能明显消弱噪声点，使邻域中灰度接近均匀，起到平滑灰度的作用.从理论上看: a、要改变均值滤波的滤波能力，就要改变模板的大小，模板越大去噪能力越强，反之越弱； b、由于是在整幅图上以取局部灰度平均的方法来淡化噪声，所以不可避免的会使原有图像的清晰度、对比度下降，会损失原有图像的细节，模板越大损失的越多； c、对整幅图像用同一个模板，不能适应局部具体情况，会出现有滤波不均匀的情况.5.1.3、分割阀值的迭代分析法 阀值分割方法是把图像的灰度分成不同的等级，然后用设置灰度门限的方法确定欲分割物体的边界。当用阀值来分割口标与背景时，如果某一
15、灰度值g是某图像的分割阀值，即小于g的灰度点将构成口标(不妨如此假设)，而大于g的灰度点就构成背景一般而言，如果灰度值g可以作为图像的一个阀值，那么它应该使按这个阀值划分口标和背景的错误分割的图像像素点数为最小.如果前景物体的内部具有均匀一致的灰度值，并分布在另一个灰度值的均匀背景上，那么图像的灰度直方图应具有明显的双峰。可是在许多情况下，噪声的干扰使峰谷的位置难以判定或者结果不稳定本文采用迭代算法，有效地消除或减少噪声对灰度门限值g的影响.设有一幅混入噪声的图像g (x),力是由原始图像f (x,y)和e(x,y)叠加而成的。即: （2）这里假设各点的噪声是互不相关的，且具有零均值，标准差为。通过阀值分割将图像分割为两部分，由于噪声是随机作用于图像的像素点上，则可以认为在分割出口标和背景图像上噪声干扰仍为，即:
