基于文字特征的文档碎纸片拼接软件设计
2014-11-06沈钊弘陈振邦
沈钊弘++陈振邦
摘 要：将图片进行灰度处理，再转化为0—1二值矩阵，利用矩阵行（列）偏差函数，建立基于最小二乘法的拼接模型。针对双向切割碎片全局搜索的局限性，利用文字的行高和行间距的特征，建立相似度函数，并人工拼接出边缘列，再多行并行拼接，然后逐次调整，最后复原；针对双向切割的双面打印碎片，先在碎纸中找出26个字母及各种标点符号的完整字符，制作出模板，再利用该模板进行匹配判定，借助人工拼接边缘列，逐次手动调整，实现复原。
关键词：二值法 最小二乘法 灰度 完整字符
中图分类号：TP301 文献标识码：A 文章编号：1674-098X（2014）04（a）-0195-01
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。
将不规则的文档碎片进行拼接，一般是利用碎纸片的边缘曲线，尖点、尖角、面积等几何特征，通过神经网络算法、蚁群算法等搜索与之匹配的相邻碎纸片[2]。但对于边缘形状相似的碎纸片，这种基于边界几何特征的拼接方法就失效了，拼接时不但要考虑边缘是否匹配，还要判断碎片内的文字内容是否匹配。
用碎纸机粉碎的纯文本文档具有以下特点：
（1）所有碎纸片都是规则的矩形，且形状完全相同；
（2）几乎每张碎纸片都包含有文字；
（3）不同碎纸片之间没有重叠部分；
针对以上特征，该文从文字特征入手，将碎纸片上的边缘文字特征进行匹配，即利用边缘文字的像素进行最优化匹配。
1 模型的假设
（1）待拼接的碎纸片来自同一页印刷文字文件。
（2）待拼接复原的碎纸片是规整的矩形。
（3）模型中的碎纸片长度、宽度和面积都相等。
（4）碎纸片的照片是同标准拍摄的。
2 软件设计原理
先用对图像进行灰度值[1]转换，得到每张碎片图像的数值矩阵（数值在0～255），再通过二值法得到灰度阈值，将所有矩阵转换成0-1矩阵。
2.1 单向切割碎片拼接模型的设计
2.1.1 纵向切割碎片拼接
设A、B分别为左右放置的两张图片对应的数字矩阵，定义前一个矩阵与后一个矩阵的第一列之间的偏差函数为：
其中A（i，72），B（i，1）分别表示矩阵第72列和第1列的元素。
对于给定的矩阵A，若存在矩阵B，使得A与B之间的偏差函数达到最小，则A与B匹配，此时A与B对应的图片可以左右拼接。
2.1.2 横向切割碎片拼接
类似地，设C、D分别为左右放置的两张图片对应的数字矩阵，定义前一个矩阵与后一个矩阵的第一列之间的偏差函数为：
其中C（1980，j），D（1，j）分别表示矩阵C、D第1980行和第1行的元素。
对于给定的矩阵A，若存在矩阵B，使得A与B之间的偏差函数达到最小，则C与D匹配，此时C与D对应的图片可以左右拼接。
2.2 双向切割碎片拼接模型的设计
由于双向切割处理量较大，2.1的拼接方法复原率较低，因此，再考虑文本的打印特征，即行高和行间距。
首先对每张图的文字像素进行数据处理，逐行搜索（记第j行的白点数），当白点数出现突变时，说明搜索到文字图像的分界线，记录下该行及相应点数，作为行高特征数据，即
取每张图的文字特征数集
具体实现原理如下图所示，将像素值积分后得到绿色多峰曲线，再进行平滑处理（如蓝色曲线所示），从而得到行高值。
利用以上得到的数据，设两图片的边界向量分别为m、n，则代入相关系数[3]求法可得到相关度函数L，即
以此作为判断依据，从人工拼接得到的边界列开始搜索，实现拼接。
2.3 双向切割的双面打印碎片拼接模型的设计
本功能只适用于英文文本。
首先制作26个字母及标点符号的完整字符模板，通过联通区域法，对存在完整字符的图片驻点扫描，同为白色区域且位置相邻的点构成一个区域，搜索得到完整字符的数据矩阵。
再根据不同字体的需要，设置相似度阈值（即碎片与模板的相似程度阈值），拼接过程同2.2。
3 结语
从仿真实验的结果可以看出，单向切割碎片的拼接功能能实现100%复原，双向切割碎片的拼接能实现86%复原，双向切割双面打印碎片的拼接能实现96%的复原，因此该软件能大幅度地提高拼接效率，为情报人员及相关工作人员节省时间和精力。但是，由于软件的数学模型是通过一定的简化所建立的，因此软件的功能也具有一定的局限性，必须符合所有碎片只来自同一张纸的情况，工作人才可以使用此软件。另外，软件的后两个功能人不能实现全自动，这也是该软件需要改进的地方。
参考文献
[1] 李利军，李云伟.基于图像灰度的拼接技术研究[J].计算机与数学工程，2007， 35（9）：128-130.
[2] 贾海燕，朱良家，周宗潭，等.一种碎纸自动拼接中的形状匹配方法[J].计算机仿真，2006，23（11）：180-183.
[3] 盛骤，谢式千.概率论与数理统计[M].4版.北京：高等教育出版社，2012.endprint
摘 要：将图片进行灰度处理，再转化为0—1二值矩阵，利用矩阵行（列）偏差函数，建立基于最小二乘法的拼接模型。针对双向切割碎片全局搜索的局限性，利用文字的行高和行间距的特征，建立相似度函数，并人工拼接出边缘列，再多行并行拼接，然后逐次调整，最后复原；针对双向切割的双面打印碎片，先在碎纸中找出26个字母及各种标点符号的完整字符，制作出模板，再利用该模板进行匹配判定，借助人工拼接边缘列，逐次手动调整，实现复原。
关键词：二值法 最小二乘法 灰度 完整字符
中图分类号：TP301 文献标识码：A 文章编号：1674-098X（2014）04（a）-0195-01
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。
将不规则的文档碎片进行拼接，一般是利用碎纸片的边缘曲线，尖点、尖角、面积等几何特征，通过神经网络算法、蚁群算法等搜索与之匹配的相邻碎纸片[2]。但对于边缘形状相似的碎纸片，这种基于边界几何特征的拼接方法就失效了，拼接时不但要考虑边缘是否匹配，还要判断碎片内的文字内容是否匹配。
用碎纸机粉碎的纯文本文档具有以下特点：
（1）所有碎纸片都是规则的矩形，且形状完全相同；
（2）几乎每张碎纸片都包含有文字；
（3）不同碎纸片之间没有重叠部分；
针对以上特征，该文从文字特征入手，将碎纸片上的边缘文字特征进行匹配，即利用边缘文字的像素进行最优化匹配。
1 模型的假设
（1）待拼接的碎纸片来自同一页印刷文字文件。
（2）待拼接复原的碎纸片是规整的矩形。
（3）模型中的碎纸片长度、宽度和面积都相等。
（4）碎纸片的照片是同标准拍摄的。
2 软件设计原理
先用对图像进行灰度值[1]转换，得到每张碎片图像的数值矩阵（数值在0～255），再通过二值法得到灰度阈值，将所有矩阵转换成0-1矩阵。
2.1 单向切割碎片拼接模型的设计
2.1.1 纵向切割碎片拼接
设A、B分别为左右放置的两张图片对应的数字矩阵，定义前一个矩阵与后一个矩阵的第一列之间的偏差函数为：
其中A（i，72），B（i，1）分别表示矩阵第72列和第1列的元素。
对于给定的矩阵A，若存在矩阵B，使得A与B之间的偏差函数达到最小，则A与B匹配，此时A与B对应的图片可以左右拼接。
2.1.2 横向切割碎片拼接
类似地，设C、D分别为左右放置的两张图片对应的数字矩阵，定义前一个矩阵与后一个矩阵的第一列之间的偏差函数为：
其中C（1980，j），D（1，j）分别表示矩阵C、D第1980行和第1行的元素。
对于给定的矩阵A，若存在矩阵B，使得A与B之间的偏差函数达到最小，则C与D匹配，此时C与D对应的图片可以左右拼接。
2.2 双向切割碎片拼接模型的设计
由于双向切割处理量较大，2.1的拼接方法复原率较低，因此，再考虑文本的打印特征，即行高和行间距。
首先对每张图的文字像素进行数据处理，逐行搜索（记第j行的白点数），当白点数出现突变时，说明搜索到文字图像的分界线，记录下该行及相应点数，作为行高特征数据，即
取每张图的文字特征数集
具体实现原理如下图所示，将像素值积分后得到绿色多峰曲线，再进行平滑处理（如蓝色曲线所示），从而得到行高值。
利用以上得到的数据，设两图片的边界向量分别为m、n，则代入相关系数[3]求法可得到相关度函数L，即
以此作为判断依据，从人工拼接得到的边界列开始搜索，实现拼接。
2.3 双向切割的双面打印碎片拼接模型的设计
本功能只适用于英文文本。
首先制作26个字母及标点符号的完整字符模板，通过联通区域法，对存在完整字符的图片驻点扫描，同为白色区域且位置相邻的点构成一个区域，搜索得到完整字符的数据矩阵。
再根据不同字体的需要，设置相似度阈值（即碎片与模板的相似程度阈值），拼接过程同2.2。
3 结语
从仿真实验的结果可以看出，单向切割碎片的拼接功能能实现100%复原，双向切割碎片的拼接能实现86%复原，双向切割双面打印碎片的拼接能实现96%的复原，因此该软件能大幅度地提高拼接效率，为情报人员及相关工作人员节省时间和精力。但是，由于软件的数学模型是通过一定的简化所建立的，因此软件的功能也具有一定的局限性，必须符合所有碎片只来自同一张纸的情况，工作人才可以使用此软件。另外，软件的后两个功能人不能实现全自动，这也是该软件需要改进的地方。
参考文献
[1] 李利军，李云伟.基于图像灰度的拼接技术研究[J].计算机与数学工程，2007， 35（9）：128-130.
[2] 贾海燕，朱良家，周宗潭，等.一种碎纸自动拼接中的形状匹配方法[J].计算机仿真，2006，23（11）：180-183.
[3] 盛骤，谢式千.概率论与数理统计[M].4版.北京：高等教育出版社，2012.endprint
摘 要：将图片进行灰度处理，再转化为0—1二值矩阵，利用矩阵行（列）偏差函数，建立基于最小二乘法的拼接模型。针对双向切割碎片全局搜索的局限性，利用文字的行高和行间距的特征，建立相似度函数，并人工拼接出边缘列，再多行并行拼接，然后逐次调整，最后复原；针对双向切割的双面打印碎片，先在碎纸中找出26个字母及各种标点符号的完整字符，制作出模板，再利用该模板进行匹配判定，借助人工拼接边缘列，逐次手动调整，实现复原。
关键词：二值法 最小二乘法 灰度 完整字符
中图分类号：TP301 文献标识码：A 文章编号：1674-098X（2014）04（a）-0195-01
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。
将不规则的文档碎片进行拼接，一般是利用碎纸片的边缘曲线，尖点、尖角、面积等几何特征，通过神经网络算法、蚁群算法等搜索与之匹配的相邻碎纸片[2]。但对于边缘形状相似的碎纸片，这种基于边界几何特征的拼接方法就失效了，拼接时不但要考虑边缘是否匹配，还要判断碎片内的文字内容是否匹配。
用碎纸机粉碎的纯文本文档具有以下特点：
（1）所有碎纸片都是规则的矩形，且形状完全相同；
（2）几乎每张碎纸片都包含有文字；
（3）不同碎纸片之间没有重叠部分；
针对以上特征，该文从文字特征入手，将碎纸片上的边缘文字特征进行匹配，即利用边缘文字的像素进行最优化匹配。
1 模型的假设
（1）待拼接的碎纸片来自同一页印刷文字文件。
（2）待拼接复原的碎纸片是规整的矩形。
（3）模型中的碎纸片长度、宽度和面积都相等。
（4）碎纸片的照片是同标准拍摄的。
2 软件设计原理
先用对图像进行灰度值[1]转换，得到每张碎片图像的数值矩阵（数值在0～255），再通过二值法得到灰度阈值，将所有矩阵转换成0-1矩阵。
2.1 单向切割碎片拼接模型的设计
2.1.1 纵向切割碎片拼接
设A、B分别为左右放置的两张图片对应的数字矩阵，定义前一个矩阵与后一个矩阵的第一列之间的偏差函数为：
其中A（i，72），B（i，1）分别表示矩阵第72列和第1列的元素。
对于给定的矩阵A，若存在矩阵B，使得A与B之间的偏差函数达到最小，则A与B匹配，此时A与B对应的图片可以左右拼接。
2.1.2 横向切割碎片拼接
类似地，设C、D分别为左右放置的两张图片对应的数字矩阵，定义前一个矩阵与后一个矩阵的第一列之间的偏差函数为：
其中C（1980，j），D（1，j）分别表示矩阵C、D第1980行和第1行的元素。
对于给定的矩阵A，若存在矩阵B，使得A与B之间的偏差函数达到最小，则C与D匹配，此时C与D对应的图片可以左右拼接。
2.2 双向切割碎片拼接模型的设计
由于双向切割处理量较大，2.1的拼接方法复原率较低，因此，再考虑文本的打印特征，即行高和行间距。
首先对每张图的文字像素进行数据处理，逐行搜索（记第j行的白点数），当白点数出现突变时，说明搜索到文字图像的分界线，记录下该行及相应点数，作为行高特征数据，即
取每张图的文字特征数集
具体实现原理如下图所示，将像素值积分后得到绿色多峰曲线，再进行平滑处理（如蓝色曲线所示），从而得到行高值。
利用以上得到的数据，设两图片的边界向量分别为m、n，则代入相关系数[3]求法可得到相关度函数L，即
以此作为判断依据，从人工拼接得到的边界列开始搜索，实现拼接。
2.3 双向切割的双面打印碎片拼接模型的设计
本功能只适用于英文文本。
首先制作26个字母及标点符号的完整字符模板，通过联通区域法，对存在完整字符的图片驻点扫描，同为白色区域且位置相邻的点构成一个区域，搜索得到完整字符的数据矩阵。
再根据不同字体的需要，设置相似度阈值（即碎片与模板的相似程度阈值），拼接过程同2.2。
3 结语
从仿真实验的结果可以看出，单向切割碎片的拼接功能能实现100%复原，双向切割碎片的拼接能实现86%复原，双向切割双面打印碎片的拼接能实现96%的复原，因此该软件能大幅度地提高拼接效率，为情报人员及相关工作人员节省时间和精力。但是，由于软件的数学模型是通过一定的简化所建立的，因此软件的功能也具有一定的局限性，必须符合所有碎片只来自同一张纸的情况，工作人才可以使用此软件。另外，软件的后两个功能人不能实现全自动，这也是该软件需要改进的地方。
参考文献
[1] 李利军，李云伟.基于图像灰度的拼接技术研究[J].计算机与数学工程，2007， 35（9）：128-130.
[2] 贾海燕，朱良家，周宗潭，等.一种碎纸自动拼接中的形状匹配方法[J].计算机仿真，2006，23（11）：180-183.
[3] 盛骤，谢式千.概率论与数理统计[M].4版.北京：高等教育出版社，2012.endprint
