《基于灰度像素理论的碎纸片拼接方法数学建模论文（32页）》由会员分享，可在线阅读，更多相关《基于灰度像素理论的碎纸片拼接方法数学建模论文（32页）（32页珍藏版）》请在金锄头文库上搜索。
1、1基于灰度像素理论的碎纸片拼接方法基于灰度像素理论的碎纸片拼接方法摘要摘要常规的二维碎片拼接技术一直受到科研领域重视，它在司法鉴定、文物修复、 图像处理等领域有着广泛的应用。本文研究的是二维碎片拼接技术中最典型的文 档类碎纸片拼接问题。基于文档纸片色彩明确、方向一致、无重叠等特点，利用 灰度理论对问题作出解决。通过图形扫描得到图像，然后通过二值化， Sobel 3梯度算进行预处理，并运用皮尔逊相关性度量及方差分析算法进行匹配，以实现 对纸片进行还原。本文通过 MATLAB 程序模型，以及图片像素灰度理论实现文 档碎片的重新拼接。 对于问题 1，应用图像处理技术中的灰度理论建立了灰度模型 I。在
2、对得到灰 度模型进行梯度边缘化预处理的方法进行模型改进，建立了边缘灰度模型Sobel II。然后借助于皮尔逊相关系数算法和 MATLAB 软件，对附件中所提供的碎片进 行排列拼接。 对于问题 2，采用化归思想，将二维问题渐变为一维问题。首先归纳碎片特 征运用 MATLAB 软件对碎片进行同行分类，得到 11 行 19 列的元素；采用方差 分析算法和人工干预对各行中元素进行排列，得到 11 条横切的图形；采用方差 分析算法和人工干预对其进行排列，得以还原。 本文的亮点在于对各行中元素采用方差分析算法进行左侧到右侧匹配后，同 时增加了右侧到左侧的匹配检验，大大减少了人工干预的工作。关键字：关键字：
3、 灰度理论；皮尔逊相关系数算法；梯度边缘化；方差分析算法；Sobel 人工干预2一、问题的重述一、问题的重述问题一、对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切） ， 建立碎纸片拼接复原模型和算法，并针对附件 1、附件 2 给出的中、英文各一页 文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及 干预的时间节点。复原结果以图片形式及表格形式表达。 问题二、对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算 法，并针对附件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。 如果复原过程需要人工干预，请写出干预方式及干预的时间节点。 问题三、上
4、述所给碎片数据均为单面打印文件，从现实情形出发，还可能有 双面打印文件的碎纸片拼接复原问题需要解决。附件 5 给出的是一页英文印刷文 字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并 就附件 5 的碎片数据给出拼接复原结果。二、模型的假设二、模型的假设1.所修复的文章必须是一张完整的文章，碎片一定可以拼接成功，并且文章 纸张完整； 2.碎纸片的几何尺寸完全相同，边缘清晰，且碎片中字体一致无残缺； 3.在检测是否匹配时，不存在实际中不相接的碎片但匹配度相对较高的情况。4.附件中数据真实可靠。三、符号说明三、符号说明r皮尔逊相关系数iX表示左右边代表，代表2 , 1isaXX
5、G横向边缘检测的图像YG纵向边缘检测的图像f梯度幅值X为样本平均值X为样本标准差4问题分析问题分析问题一的分析： 4.1 通过对附件 1、附件 2 进行分析，碎片在外观形状上并无差异，所以若对碎片3进行重新匹配，可以简化为对碎片边缘进行匹配。考虑先运用 MATLAB 中的函数将数据以像素灰度模型（gray-scale model）的形式进行读取。通过imread对结果和附件的观察不难发现，每片碎片列边缘像素特征较为明显，因此，可以 通过比较样本碎片左边与其他待测碎片的右边相关性(Correlation coefficient)大小， 得到最近拟合碎片，对右边也进行类似处理。这里采用皮尔逊相关系
6、数理论作为 相关性检测的基准。选取相关性度量最高值，可以得到正确的排序序列。最后运 用 MATLAB 中的函数将拼接后的图像进行输出。imshow问题二的分析： 4.2.1.与一维的区别和联系 I.区别： 1）需要匹配边数由二到四； 2）一边上可用于检测匹配程度的像素点大幅减少； 3）段落的首尾会影响检测时的判别。II.联系： 1）都可以应用灰度理论转化为数值矩阵后进行分析； 2）可以转化为一维问题，可先化成若干横条，然后 11 个横条进行匹配或先 化成若干纵条，然后 19 个纵条进行匹配。4.2.2.二维碎片的图像分析 由图 4.2.1 可以发现，行间形成的空白区域可视作一条直线，列间形成的
7、空白 区域可视作为曲折的直线。并且行间距大于列间距，因此碎片的左右两侧更不容 易在碎片中出现白边，白边属于分析匹配程度时的一种特殊情况，会提高分析难 度，应尽量避免。另外，由于碎片上下两侧的像素点少于左右两侧，故在单边进 行匹配时上下比较更容易出现错误。先成一列的难度较大，先成行较简单，并且 成行后横向像素点将增加很多，易于提高成功率，有效减少人工干预。图 4.2.14.2.3.归纳可能为一行的所有特征，进行编程监测以得到 11 行数据。采用方差分 析算法对这些数据内部的每列进行排序，得到 11 条横切的图形。然后采用方差 分析算法和人工干预对其进行排列。4问题三的分析：采用类似于问题二的方法
8、对正反面分别排序，将不完整的正反面 图进行覆盖，得到较完整图，然后进行人工干预，填入少量未识别碎片，得到拼 接结果。五、模型的建立与求解五、模型的建立与求解问题一问题一 本题考虑到文本图片有别于一般图像，具有色彩稳定，无光照因素扰乱，同 时不存在碎片旋转、变形以及遮挡的因素，所以运用基于图像灰度的图像配准方 法就能完美得解决文本图片的自动化拼接问题。 5.1.基于灰度理论求解模型对碎片进行拼接 5.2 对图像建立灰度模型 灰度（Gray scale）数字图像是每个像素只有一个采样颜色的图像。这类图像 通常显示为从最暗黑色到最亮的白色的灰度，尽管理论上这个采样可以任何颜色 的不同深浅，甚至可以是
9、不同亮度上的不同颜色。灰度图像与黑白图像不同，在 计算机图像领域中黑白图像只有黑白两种颜色，灰度图像在黑色与白色之间还有 许多级的颜色深度。但是，在数字图像领域之外， “黑白图像”也表示“灰度图像”， 例如灰度的照片通常叫做“黑白照片”。在一些关于数字图像的文章中单色图像等 同于灰度图像，在另外一些文章中又等同于黑白图像。 其实际颜色越接近白色，灰度值越接近 255；越接近黑色，灰度值越接近 0。对附件 1 中 19 图片进行编号，分别为基于灰度理论得到附。),.,(scba件 1 中 19 张碎片的 0-255 像素灰度图矩阵。 运用算子提取各碎片样本的左列与右列边缘数列，标记为Sobel矩
10、阵。),.,(,21scbaXXX为算子的表示：Sobel)2()2()2()2(7419633197 zzzzzzGzzzzzzGYxsX 梯度幅值：YXGGf用卷积模板来实现：51.2 相关性度量 选取碎片左右列后，需要对碎片进行重新排序，此处，进行各碎片边缘相关 性度量。采用皮尔逊相关系数对相关性进行分析。 两个变量之间的皮尔逊相关系数定义为两个变量之间的协方差r和标准差的商：),cov(YXYXYXXYXYXYYXEYX )(),cov(,以上方程定义了总体相关系数, 一般表示成希腊字母。基于样本对协方(rho)l差和标准差进行估计，可以得到样本相关系数, 一般表示成：ijr 2211
11、2211)()()( )( nkjkjnkikijkjnkikiij xxxxxxxx r一种等价表达式的是表示成标准分的均值。基于的样本点，样本皮尔),(iiYX逊系数是：)( )(111YiniXiYYXX nr 其中 为标准分 XiXX 简单的二维皮尔逊相关系数是两项间的差是每个变量值差的平方和再平方根， 目的是计算其间的整体距离即不相似性，其中为样本量，分别为两个变量的观n6测值和均值。描述的是两个变量间线性相关强弱的程度。的取值在-1 与+1rr之间，若表明两个变量是正相关，即一个变量的值越大，另一个变量的值，0r也会越大；若表明两个变量是负相关，即一个变量的值越大另一个变量的，0r
12、值反而会越小。的绝对值越大表明相关性越强。ijr对每一组数据进行相关系数比较可以清楚的得出最有拟合组。例如：通过 MATLAB 可视化显示与拟合度最高的是即图片与2a1o00相邻。14图 5.1.17由上图可见，相关系数越大，说明指标性质越接近。由于碎片均是正向放置，所以令分别于进行相关性度量分析，对做同样处1a222,.,scb111,.,scb理，即可得到新序列。附件一结果 08141215031002160104050913181107170006根据序列排序讲碎片进行重新匹配。考虑到自动化批量处理，下面，通过程 序来实现。 程序流程图如下：iCi,j输出图形YES交换两相 比矩阵NOi
13、=i+1j=i+1NO开始图 5.1.2 程序流程图注释：Ci，j 代表第 i 个向量与第 j 个向量的相似度的值。 运用 MATLAB 软件实现程序。 重新匹配后的的图片见附录。8图片贴合度满意，基本达到要求。再对附件 2 中碎片运用此算法进行重新排 序并进行拼接。 重新匹配后的的图片见附录。 由此可见，本算法具有一定的可行性，符合题设要求。 程序见附录。 拼接结果：附件一结果附件一结果 08141215031002160104050913181107170006附件二结果附件二结果 03060207151811000501091310081214171604问题二问题二本题是在问题一的基础
14、上的延伸及复杂化，对一中的纵切结果加以横切。同 样，应用灰度理论模型，对各个方块碎片进行重新匹配。 1.碎片灰度化处理，提取边缘数列一、得到特定行1.流程图读读取取附附件件3中中的的 数数据据将将信信息息存存储储 在在一一个个空空间间信信息息二二值值化化筛筛选选出出 同同一一行行的的碎碎片片找找到到首首尾尾两两行行对对个个别别碎碎片片进进行行 人人工工干干预预逐逐行行排排列列拼拼接接输输出出拼拼好好的的 图图片片2.说明此时，每一行内的各列尚为乱序，运行该程序后通过查找可知这些picmatrix行内部的碎片序号。如下表所示。93.程序见附录二、行内排序1.流程图2.说明此时，每一行内各列得到排
15、序，但由于白边和逗号出现，使得单向检测存在很大 偏差。故当出现以上两种情况时，记录出现情况的位置，再倒序检测匹配到那个 位置，情况会得到好转。 3.人工干预得到各行内正确的列序 1）部分不需要更改，如第四行 图看着上图，进行人工干预。记下应如何修改，再找到变量后进行调序，存储即可。4.方差匹配 方差分析（ANOVA）即 F 检验,是通过分析研究中不同来源的变异对总变异的贡 献大小，从而确定可控因素对研究结果影响力的大小。总变量(TSS)：ijtotalijYY2)(为组别为观测值个数(j=1,2,3,.,J)， iij).,3 , 2 , 1(YIji，为第 i 组第 j 个观测值， 为所有观
16、测值的平均数。ij).,3 , 2 , 1(YJj，0732455356687093126137138153158166174175196208 118232630415062768687100120142147168179191195 2112228495457659195118129141143178186188190192 312143139517382107115128134135159160169176199203 44089101102108113114117119123140146151154155185194207 51029374448555964759298104111171172180201206 619203652616367697278799699116131162163177 892425353846748188103105
