论文部分内容阅读
摘 要：在对于碎纸机仅纵切的情形，运用Matlab对灰度图形成的灰度值矩阵进行二值化处理，提取每个子块的左右边界轮廓特征串形成成对比较矩阵，通过编程得到子块的匹配顺序，并对灰度值矩阵进行灰度图还原。
关键词：碎片拼接复原；边缘匹配；灰度；特征向量；动态定位
一、问题分析
1、碎纸机仅纵切
碎纸片拼接复原技术的关键技术包括图像预处理和匹配，印刷文字文件均为灰度图，且图像像素为72€？980，因此，对于图像的预处理过程，每个像素点处可用灰度值对其进行量化处理，形成72€？980型灰度值矩阵，其中灰度级为256级，并且存在不可避免的噪声干扰，256级灰度矩阵和小级数灰度矩阵产生相似的匹配度，但小级数灰度矩阵显著提高程序的运行速度，所以，需要指定某个灰阶为阈值，对灰度图像进行二值化处理，碎片子块在匹配过程中，对于碎纸机仅纵切情形，提取子块灰度矩阵中的轮廓特征串，所有子块左右轮廓线处的特征串分别两两形成成对比较矩阵，对每个子块之间的匹配度进行定义，利用Matlab和C++编程进行子块拼接的排序，并对图片复原。
2、碎纸机既纵切又横切
对于碎纸机既纵切又横切的情形，碎片子块匹配过程中增加了上下轮廓处的匹配问题，选择利用上下左右轮廓处的特征向量进行匹配，一个是在前述基础上进行子块的动态定位，另一个是加入图像特征的分析过程，运用模型对碎片进行筛选，通过特征向量之间的联系进行距离分析，在分析过程中不免存在匹配误差，此时，需要进行对误差分析，利用Lingo进行优化。在匹配难区分是进行必要的人工干扰。
本文基于2013年全国大学生数学建模竞赛B题进行部分问题解答分析。
二、模型的建立及求解
1、碎纸机仅纵切碎纸片拼接复原模型
当碎纸机仅纵切碎纸片时，左右轮廓边缘匹配是问题的突破点，而碎纸片拼接复原技术的关键技术包括图像预处理和匹配。附件1中所给的印刷文字文件均为灰度图，图像像素为72€？980，因此，对于图像的预处理，每个像素点处用灰度值进行量化处理，这样，形成72€？980型灰度值矩阵，其中灰度级数为256级，并且存在不可避免的噪声干扰，256级灰度矩阵和小级数灰度矩阵产生相似的匹配度，但是小级数灰度矩阵显著提高程序运行速度，所以，指定灰阶为128为灰度阈值，对碎片子块的灰度矩阵进行二值化处理：
其中， gikt表示第i个子块灰度值矩阵中，第k行第t列经二值化后的灰度值， 表示第i个子块灰度值矩阵中，第k行第t列经二值化前的灰度值。
通过以上步骤形成二值化后的灰度矩阵，提取每个子块的轮廓特征串，第i个子块右侧的特征串为ui，左侧的特征串为li，将第i个子块右侧特征串中的点依次与其他18个子块的左侧特征串进行对比，定义匹配度Sij为：
其中Sijk表示第i个子块与第j个子块进行对比时，aik是否等于bjk的一个开关变量，匹配度越高表示两个子块契合度越高。
第i个子块右侧特征串中的点依次与其他18个子块的左侧特征串进行对比之后，会产生18个匹配度，排序为1子块的左侧特征串应该全为0，因此，利用C++编程对匹配过程进行循环，因为在碎纸机纵切的情形下特征串对比之后匹配度差别比较大，故可直接取最大匹配度为契合的拼图。
根据碎片子块的排序可以将其灰度值矩阵进行排序，此时，运用Matlab的画图功能，利用量化灰度图的逆过程，即可把复原图片显示出来。
2、碎纸机既纵切又横切
碎纸机既纵切又横切的时候，在碎纸机仅纵切的情形上增加了横切的情形，也就是碎片子块匹配过程中增加了上下轮廓处的匹配问题，基于第一问的思路，并不对灰度值矩阵进行二值化处理，对碎片子块进行动态匹配。
附件3和附件4碎片子块的位置可以表示为矩阵，其中pmn为子块位于第m行第n列，其中m=1，2，…，11，n=1，2，…，19，由分析可知，位于左侧矩形框内的子块最左侧特征向量全为0，因此，首先对附件3进行子块的第一轮筛选。经过筛选后的子块利用每个子块上下轮廓特征向量之间距离的比较确定两子块的契合度，并进行排序，具体做法沿用模型一的思路。
通过C++编程对最右侧和最左侧进行第一轮筛选，筛选过后发现，位置矩阵第一列元素，p11，p21，…，pm1，所对应的11个位置有16个匹配子块，因为计算机拼接过程中，只根据条件约束进行筛选，不考虑文字内容是否匹配，因此，在第一轮筛选结束后对子块进行人工干扰识别排序。
第一轮定位排序是根据C++和Matlab编程筛选和上下向量距离比较匹配度产生，此时子块之间匹配起来容易，匹配度也梯度变化大，好识别，但是附件三中的碎片相对于附件一和附件二的碎片来说要更小更碎，在进行第二列位置定位的时候匹配度差异不明显，此时进行第二轮筛选。
第二轮筛选定位出p12处的子块，p12处子块的边界条件为左向量与p11处子块的右向量距离最短，上向量中元素全为0，对于第二轮筛选出的子块再次进行人工干扰选择，定位出此处子块为第156张碎片图片。
这时p13，p14，…，p1n处的子块利用边界条件的约束和向量之间的距离建立优化目标函数，利用Lingo编程优化，依次选择定位。
第二行定位完成后，利用第一行和左侧定位后的子块的右侧特征向量同样利用Lingo进行优化，此时需要对误差相差不大的碎片子块进行人工干预。
四、模型的推广
对这类边缘相似的碎片拼接，理想的计算机拼接过程应与人工拼接技术相似，拼接过程中不但要考虑边缘是否重合，还要对文字内容是否匹配进行鉴别。
对于碎纸机仅纵切的情形，碎片匹配简单可以直接进行特征向量的比较；对于碎纸机既纵切又横切的情形，运算量加大，提取边缘向量仍然可以对碎片子块进行定位匹配，考虑到每个字块具有其一定的图像特征，比如行间距，字间距等，利用这个特征可以对碎片进行筛选并定位复原。
图像特征提取分组匹配模型是在图像特征提取的基础上进行匹配，充分利用了打印文件的特征，通过计算机对条件的筛选匹配，辅以人工干扰，提高了正确率和效率，因此，对于边界形状不明显的碎片可利用此方法进行拼接复原。
参考文献：
[1]罗智中.基于文字特征的文档碎纸片半自动拼接[].计算机工程与应用，2012，（5）.
[2]周志刚，桑农，万立，陈铁灵.利用灰色理论构造统计量进行图像边缘检测[].系统工程与电子技术，2013，（5）.
作者简介：王秀丽（1993-），女，山东聊城人，长安大学建筑工程学院本科生。
关键词：碎片拼接复原；边缘匹配；灰度；特征向量；动态定位
一、问题分析
1、碎纸机仅纵切
碎纸片拼接复原技术的关键技术包括图像预处理和匹配，印刷文字文件均为灰度图，且图像像素为72€？980，因此，对于图像的预处理过程，每个像素点处可用灰度值对其进行量化处理，形成72€？980型灰度值矩阵，其中灰度级为256级，并且存在不可避免的噪声干扰，256级灰度矩阵和小级数灰度矩阵产生相似的匹配度，但小级数灰度矩阵显著提高程序的运行速度，所以，需要指定某个灰阶为阈值，对灰度图像进行二值化处理，碎片子块在匹配过程中，对于碎纸机仅纵切情形，提取子块灰度矩阵中的轮廓特征串，所有子块左右轮廓线处的特征串分别两两形成成对比较矩阵，对每个子块之间的匹配度进行定义，利用Matlab和C++编程进行子块拼接的排序，并对图片复原。
2、碎纸机既纵切又横切
对于碎纸机既纵切又横切的情形，碎片子块匹配过程中增加了上下轮廓处的匹配问题，选择利用上下左右轮廓处的特征向量进行匹配，一个是在前述基础上进行子块的动态定位，另一个是加入图像特征的分析过程，运用模型对碎片进行筛选，通过特征向量之间的联系进行距离分析，在分析过程中不免存在匹配误差，此时，需要进行对误差分析，利用Lingo进行优化。在匹配难区分是进行必要的人工干扰。
本文基于2013年全国大学生数学建模竞赛B题进行部分问题解答分析。
二、模型的建立及求解
1、碎纸机仅纵切碎纸片拼接复原模型
当碎纸机仅纵切碎纸片时，左右轮廓边缘匹配是问题的突破点，而碎纸片拼接复原技术的关键技术包括图像预处理和匹配。附件1中所给的印刷文字文件均为灰度图，图像像素为72€？980，因此，对于图像的预处理，每个像素点处用灰度值进行量化处理，这样，形成72€？980型灰度值矩阵，其中灰度级数为256级，并且存在不可避免的噪声干扰，256级灰度矩阵和小级数灰度矩阵产生相似的匹配度，但是小级数灰度矩阵显著提高程序运行速度，所以，指定灰阶为128为灰度阈值，对碎片子块的灰度矩阵进行二值化处理：
其中， gikt表示第i个子块灰度值矩阵中，第k行第t列经二值化后的灰度值， 表示第i个子块灰度值矩阵中，第k行第t列经二值化前的灰度值。
通过以上步骤形成二值化后的灰度矩阵，提取每个子块的轮廓特征串，第i个子块右侧的特征串为ui，左侧的特征串为li，将第i个子块右侧特征串中的点依次与其他18个子块的左侧特征串进行对比，定义匹配度Sij为：
其中Sijk表示第i个子块与第j个子块进行对比时，aik是否等于bjk的一个开关变量，匹配度越高表示两个子块契合度越高。
第i个子块右侧特征串中的点依次与其他18个子块的左侧特征串进行对比之后，会产生18个匹配度，排序为1子块的左侧特征串应该全为0，因此，利用C++编程对匹配过程进行循环，因为在碎纸机纵切的情形下特征串对比之后匹配度差别比较大，故可直接取最大匹配度为契合的拼图。
根据碎片子块的排序可以将其灰度值矩阵进行排序，此时，运用Matlab的画图功能，利用量化灰度图的逆过程，即可把复原图片显示出来。
2、碎纸机既纵切又横切
碎纸机既纵切又横切的时候，在碎纸机仅纵切的情形上增加了横切的情形，也就是碎片子块匹配过程中增加了上下轮廓处的匹配问题，基于第一问的思路，并不对灰度值矩阵进行二值化处理，对碎片子块进行动态匹配。
附件3和附件4碎片子块的位置可以表示为矩阵，其中pmn为子块位于第m行第n列，其中m=1，2，…，11，n=1，2，…，19，由分析可知，位于左侧矩形框内的子块最左侧特征向量全为0，因此，首先对附件3进行子块的第一轮筛选。经过筛选后的子块利用每个子块上下轮廓特征向量之间距离的比较确定两子块的契合度，并进行排序，具体做法沿用模型一的思路。
通过C++编程对最右侧和最左侧进行第一轮筛选，筛选过后发现，位置矩阵第一列元素，p11，p21，…，pm1，所对应的11个位置有16个匹配子块，因为计算机拼接过程中，只根据条件约束进行筛选，不考虑文字内容是否匹配，因此，在第一轮筛选结束后对子块进行人工干扰识别排序。
第一轮定位排序是根据C++和Matlab编程筛选和上下向量距离比较匹配度产生，此时子块之间匹配起来容易，匹配度也梯度变化大，好识别，但是附件三中的碎片相对于附件一和附件二的碎片来说要更小更碎，在进行第二列位置定位的时候匹配度差异不明显，此时进行第二轮筛选。
第二轮筛选定位出p12处的子块，p12处子块的边界条件为左向量与p11处子块的右向量距离最短，上向量中元素全为0，对于第二轮筛选出的子块再次进行人工干扰选择，定位出此处子块为第156张碎片图片。
这时p13，p14，…，p1n处的子块利用边界条件的约束和向量之间的距离建立优化目标函数，利用Lingo编程优化，依次选择定位。
第二行定位完成后，利用第一行和左侧定位后的子块的右侧特征向量同样利用Lingo进行优化，此时需要对误差相差不大的碎片子块进行人工干预。
四、模型的推广
对这类边缘相似的碎片拼接，理想的计算机拼接过程应与人工拼接技术相似，拼接过程中不但要考虑边缘是否重合，还要对文字内容是否匹配进行鉴别。
对于碎纸机仅纵切的情形，碎片匹配简单可以直接进行特征向量的比较；对于碎纸机既纵切又横切的情形，运算量加大，提取边缘向量仍然可以对碎片子块进行定位匹配，考虑到每个字块具有其一定的图像特征，比如行间距，字间距等，利用这个特征可以对碎片进行筛选并定位复原。
图像特征提取分组匹配模型是在图像特征提取的基础上进行匹配，充分利用了打印文件的特征，通过计算机对条件的筛选匹配，辅以人工干扰，提高了正确率和效率，因此，对于边界形状不明显的碎片可利用此方法进行拼接复原。
参考文献：
[1]罗智中.基于文字特征的文档碎纸片半自动拼接[].计算机工程与应用，2012，（5）.
[2]周志刚，桑农，万立，陈铁灵.利用灰色理论构造统计量进行图像边缘检测[].系统工程与电子技术，2013，（5）.
作者简介：王秀丽（1993-），女，山东聊城人，长安大学建筑工程学院本科生。