基于边界像素点匹配的组内拼接方法

基于边界像素点匹配的组内拼接方法

1.碎胶片的拼接技术破碎文件的整合在司法证据恢复、历史遗迹恢复和军事信息采集等领域发挥着重要作用。由于同一文件多是用同一种语言书写的,不同的语言采用的字符特征不同,因此应针对不同语言的文件建立相应的拼接算法。英语是一种世界语言,研究用英文书写的被切割后的文件拼接是破碎文件研究的一个主要问题。传统上,拼接复原工作需由人工完成,准确率较高,但效率很低。特别是当碎片数量巨大,人工拼接很难在短时间内完成任务。随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。当前文献中讨论的多是非规则碎片的拼接问题,多从碎片边缘的曲线特点提取边缘特征,建立边缘特征点的匹配算法进行拼接。对于规则碎片的拼接研究较少。罗智中分析了基于几何特征的碎纸片自动拼接方法的缺点,研究了碎纸片内文字行特征,表格特征特点,以及碎纸片内文字行特征、表格线特征的获取方法,提出了基于碎片文字行特征或表格特征的碎片半自动拼接算法。本文以2013全国大学生数学建模B题(以下简称2013B题)附件2和附件4为例,研究一页单面英文文件被纵切,或者即被纵切又被横切产生的规则无噪声且形状为矩形碎纸片的拼接技术。2.纵切中文碎片的连接恢复算法2.1边缘像素分布在2013B题附件2中纸张被纵切为19条英文碎片,需要将这19条碎片进行排序复原。部分碎片如图1所示。观察图片可知,英文字母每一笔画可以认为是连续变化的,在切割处每一个被切开的笔画两边的像素点分布相同。假设一个形状连续变化被一切为二的物体,产生的两个截断面相同。因此要将碎片进行拼接,可根据边缘像素点分布情况进行匹配。用matlab读取每张图片,得到一个数字矩阵,矩阵中每一个元素代表图像该点的灰度值。记Ei为将附件2中的每张图片0-1化后的矩阵。即像素值大于γ的点为1,认为这一点无英文,其它像素值为0,认为这一点有英文笔画。截断处两边同为0表示前后笔画连续,同为1表示左右均为背景,称为像素的连续性。其中γ为0-1化阀值,可取γ=255。对附件2得到19个的0-1矩阵(i=1,…,19).抽取19个矩阵的最前列和最后列,建立大小均为1980×19的qian,hou矩阵,分别存储每张图片的最前列和最后列。于是,根据连续性,定义纸条之间的匹配度矩阵其中pij表示第i个纸条和第j个纸条之间的匹配度,其值为第i个纸条的最前列和第j个纸条的最后列元素相加求和后,2或0的个数占总个数的比例,2或0说明匹配成功,匹配度越大代表两张图片应该拼在一起,称此模型为“边界像素点匹配”模型。2.2计算纸条匹配度矩阵算法A:边界像素点匹配算法A1:读取附件2中每张图片并0-1化得到19个1980×72的0-1矩阵Ei(i=1,…,19)。A2:用矩阵qian和hou存储组内所有碎片的最前列和最后列。A3:计算纸条之间的匹配度矩阵A4:依据匹配度矩阵进行拼接(1)纸条左边界汉字长度全为0的即为最左边的纸条,记为第j=1条;(2)p=2,…,n对其余碎纸片利用pipeidu矩阵找到与第j-1条匹配度最大的纸条。2.32013b题为附件2的连接结果对2013B题附件2,用Matlab编程计算拼接结果。图2为复原图局部。3.纵切英文破纸连接恢复算法3.1小写字母书写2013B题附件4给出了每页纸被纵横切为11×19个,共209个碎片,部分碎片如图3。如图3,对于纵横切的英文,每个碎片需要和上、下、左、右四个碎片进行拼接。同时由于碎片较小,根据算法A进行两两之间的拼接误差会很大,错误率较高。因此,可以把在同一行的碎片聚类,行内拼接为一个长碎片后,再上下行进行拼接。容易看出碎片是随机切割的,所以文字区域在碎片的上下位置不同。但是同行碎片的文字区域上下位置吻合,并结合行特征进行聚类,将209张归于11类。观察发现英文字母大写和小写具有不同的规则,同一字号下大写字母高度相同,但是小写字母差别较大,如图4。由于实际多采用小写字母,同时大写字母只在个别情况出现,本文只分析小写字母书写的文件。小写字母书写分为上中结构(如:b、k)和中下结构(如:y、j)。为了确定英文字母所在的行高度,可以通过图片英文中部所占得位置来确定位于同一行的图片。如图3.3所示,A、B、C、D、E分别表示行中心位置,且A和C为一个碎片中首行英文的中心位置,B和D为一个碎片中第二行英文的中心位置。若A与C的位置相近,B与D的位置相近图片,则两个碎片应该位于同一组,就有可能匹配。同时,观察碎片发现每两行英文中部位置之间都相差63,行与行之间的距离为12,见图5。用matlab读取附件4中209张图片,经过程序0-1化后得到209个180×72的矩阵Qi(i=1,…,209),将每个矩阵,将0-1化后的矩阵按行求和,作出每张图片的投影波峰图,如图3.4。从投影波峰图可以看出由于英文字母的特点,一行英文投影后会产生量较大的波峰,据此寻找每张图片离碎片顶端的两个最大的波峰,根据他们的位置求平均的中心位置。实际执行时,由于每行英文字母的情况不同,造成投影波峰比较凌乱,有许多伪波峰,如图3.4中(a)和(b)中第一幅图所示。因此需将投影波峰图进行分段平滑处理,如图3.4中(a)和(b)中间图所示。即,若假设一个引文字母的笔画宽度为3,则找到投影波峰图大于2之外的最小值,记为b=5*a,令为投影波峰图阀值,其中5表示一个碎片中一行有5个字母。将投影波峰图中大于b的值置为2,小于等于2且大于0的值置为1。又由于存在段首空格和段末空行的情况,可能使得某些碎片第一行英文离顶端大于63的情况。于是,找出这个波峰图的中部位置,记为zhong_jian。令zhong_jian=zhong_jian-63做循环,直到zhong_jian小于0。求出每张图片负的zhong_jian。如果两张图片匹配,那么它们的负的zhong_jian应该比较接近,将zhong_jian相近的图片归为一组。分成若干组后利用算法A对于每一组行排序。然后将每组形成的正确的行拼接结果再利用算法A进行上下拼接。3.2人工归组的方法算法B:纵横切英文碎片拼接算法B1:用matlab读取附件4中209个图片将并0-1化,得到209个180×72的矩阵Qi(i=1,…,209)。B2:对所有的Qi,用matlab将矩阵按行求和,得投影波峰图,记为hi。B3:对i=1,…,209,寻找Qi中间位置。(1)计算hi的b,并将其平滑处理;(2)从第k=1位置开始,记hi中第一值由1变为2时,2所在的位置为zui_da,表示hi的主高峰位置;记hi中第一值由2变为1时,2所在的位置为ci_da,表示的hi次高峰位置;如果两个值只差介于20到25之间则结束,否则从k=ci_da+1开始继续寻找。(3)计算zui_da和ci_da的平均值的,记为zhong_jian,并循环减去63,直到zhong_jian小于0,得Qi中间位置。B4:根据找到的负的中间值进行人工归组后利用算法A进行组内拼接。B6:将每组形成的行拼接结果利用算法A进行上下拼接,得到结果图。3.32边缘匹配算法a和b、bmatlab编程寻找到每张图片的中间值导入excel中人工排序可得到一个分组表,见表3.1。由于英文行与行之间的空行高度只有12,因此在聚类分组时,会有很多重复,不是希望的11组。表3.1中分成6组,其中有5组包含约38个碎片,剩余一组包含19个碎片。第64和191幅图归为第一组。在每一组的碎片中,均包含两个最左边的碎片(其第一列全为0),利用边缘像素点匹配算法进行拼接,得到两行。图7为拼分组后组内拼接结果示意图。观察图7发现图中有不少出错处,但是19个碎片的拼接错误处最多不超过5个,可以在B6步之前先人工进行干预调整。最后利用算法A进行上下拼接,得到附件4的拼接复原图。matlab编程进行行排序得到行排序图,见图8。4.基于拼接算法的定位优化为了验证算法的可行性,选取700×540的模糊英文图片做模型模拟,并裁剪为10×10个,共100个大小为70×54的碎片。图9显示6张图。图10为行排序后的图。观察发现,尽管原模拟图选取的是字体更小、碎片更小的英文文件,但是利用拼接算法还是可以对图片进行很好的复原。图11为复原图局部。5.边缘像素点的匹配对