基于Matlab GUI碎纸机破碎文档的恢复

陈斯定+++朱烨婷+++徐晶

摘 要：文章详细阐述了基于Matlab GUI对单面印刷文档经碎纸机破碎的碎片（既纵切又横切）的恢复，结合计算机对碎片的匹配搜索和人工干预，提高文档恢复的效率，达到文档的恢复。

关键词：Matlab GUI；聚类分析；人工干预

1 概述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是，当碎纸片数量巨大，人工拼接很难在短时间内完成任务[1-3]。

随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。文章基于Matlab GUI对破碎文档（既纵切又横切）的复原实现人机互动，并给出了提高文档复原效率的方法。

2 图像采样

图象采样就是按照图像空间的坐标测量该坐标测量该位置上像素的灰度值。方法如下：对连续的f（x，y）进行等间隔采样，在（x，y）平面上，将图像均分成均匀的小网格，每个小网格的位置可以用整数坐标表示，于是采样值就对应于一个M×N数字矩阵。这样就获得了数字图像中关于像素的两个属性：位置和灰度。位置由采样点的两个坐标确定，也就对应了网格行和列；而灰度表明了该像素的明暗程度。Matlab读入图象的函数为imread（filename，format）。而文章讨论的碎片图像格式为bmp的8位灰度图像，每一像素的取值范围为0～255。

3 碎片的分类

3.1 碎片特征提取

准确地确定碎片的特征对碎片的分类起着重要作用，原始的碎片图像中可利用的像素点较多，而碎片图像中能有效反应碎片的特征的像素需要恰到好处地提取。文字的笔画有粗细之分，由此，不考虑笔画的粗细，文字的轮廓更能体现碎片的特征。运用边缘检测的方法，实现对文字轮廓的确定。

（a） （b）

图1 边缘化处理前后对比图

将每行边缘轮廓像素通过累加法，得到一个180维的向量。边缘轮廓像素在180维的向量的每一分量的值呈现一定的规律，图2为图1（a）的累加向量。

3.2 K-Means聚类分析方法

K-Means聚类指基于划分的聚类分析[4]，事先需要制定将数据分为几类，给定一个有n个个体的数据集，将它划分为K个簇（k？燮n），使每个簇具有较高的相似度，而簇间的相似度较低。它需要满足以下两个条件：（1）K类中任意一类不为空集，即每一类至少有一个个体；（2）每一个体都属于且仅属于K类中的一类。

其中相似度的计算：根据一个簇中点的平均值（被看作簇的重心）来进行。K-means聚类算法的描述和处理流程如下：K-means是用于划分的K均值算法，每个簇的中点用簇中对象的均值表示，其输入为簇的数目K和包含n个对象的数据集，输出为K个簇的集合，使得平方误差准则最小。原理如下：

（1）首先为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心；（2）将样本集中的样本按照最小距离原则分配到最邻近聚类；（3）使用每个聚类中的样本均值作为新的聚类中心；（4）重复步骤（2）和（3）直到聚类中心不再变化；（5）结束，得到K个聚类。

将样本分配到距离他们最近的中心向量，并使目标函数值最小，K-means算法的目标函数通常可以表示为：

E=■■P-m■■

式中，E是数据集中所有对象的平方误差和；P是数据对象，文章表示给定对象的像素特征值；mi是Ci的均值（P和mi都是多维）；P-m■■表示P与mi之间的度量。通过求这个目标函数E的最小值来试图使生成的结果簇尽可能地紧凑和独立。

对于度量，形象地说就是我们主要考虑的样本间的差异。在数据分析和数据挖掘的过程中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。我们要比较个体x和个体y间的差异，它们都包含了n个维的特征，即x（x1，x2，…，xn），y=（y1，y2，…，yn），如下几种距离主要衡量两者的差异，其中d（x，y）越小，即样本x，y之间的距离越小，样本x，y越相似，差异度越小；反之，越大。

欧几里得距离（sqEuclidean）：d（x，y）=（■（xi-yi）2）1/2

绝对值距离（cityblock）：d（x，y）=（■xi-yi

特别地当xi∈0，1yi∈0，1 此时又称汉明距离；

余弦距离（cosine）：d（x，y）=（■xi，yi）/（（■xi2）1/2（■yi2）1/2）

4 碎片匹配

根据碎片邻接原理以及图片格式的性质，我们给出了如下定理：

定理1. 假设a1和a2分别为“.bmp”图片格式两碎纸片的矩阵（如图5），s1为a1最右侧列，s2为a2的最左侧列，如果a1与a2为邻接碎纸片（a1为左边，a2为右边）的必要条件为：

如果非边缘第m个点，m∈s1为黑色（值为0），则s2中的第m-1，m，m+1个位置中必然存在不为白色的点（值255）；同理：如果此时s2处非边缘的第n个点，n∈b为黑色（值为0），则s1中的第m-1，m，m+1个位置中必然存在不为白色的点（值255）。

证明：由“.bmp“图片格式灰度（值0～255）特性即证。

图3 碎纸片匹配示意图

因为这是图像匹配[1]的必要条件，即不满足这个条件必定不能匹配，满足条件为可能匹配的碎纸片。假设满足条件中的碎纸片矩阵集合为an■，i∈N■，则如果i=1，则这一个唯一确定的匹配。如果i>1，则需要人工干预，找出匹配度最高的碎纸片。

定理2. 假设a1和a2分别为“.bmp”图片格式两碎纸片的矩阵，s1为a1最右侧列，s2为a2的最左侧列，定义绝对值差异度

d（S1，S2）=■S1i-S2i，其中S1=（S11，S12，…，S1n），S2=（S21，S22，…，S2n）

5 碎片拼接Matlab GUI软件包

运用前面三节的内容，我们设计了碎片拼接Matlab GUI软件包， 根据聚类分析K均值距离公式的不同，我们设计了如下参数设置界面：

图4 k-means参数设置界面

点击图4的确定按钮后，弹出图5行内拼接界面。

图5 行内拼接界面

完成行内拼接后，点击“下一步”，出现行间拼接界面，最后生成完整的纸张。

图6 行间拼接界面

参考文献

[1]庄俊东.基于数字图像处理的人民币碎纸片拼接方法的研究[D].上海交通大学，2010.

[2]张翠.基于点线的文档图片数字水印与碎纸片拼接[D].中国海洋大学，2011.

[3]葛巧瑞.自然场景下的文字分割及识别研究[D].西安电子科技大学，2011.

[4]吕晓玲，谢邦昌.数据挖掘方法与应用[M].北京：中国人民大学出版社，2009.endprint

摘 要：文章详细阐述了基于Matlab GUI对单面印刷文档经碎纸机破碎的碎片（既纵切又横切）的恢复，结合计算机对碎片的匹配搜索和人工干预，提高文档恢复的效率，达到文档的恢复。

关键词：Matlab GUI；聚类分析；人工干预

1 概述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是，当碎纸片数量巨大，人工拼接很难在短时间内完成任务[1-3]。

随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。文章基于Matlab GUI对破碎文档（既纵切又横切）的复原实现人机互动，并给出了提高文档复原效率的方法。

2 图像采样

图象采样就是按照图像空间的坐标测量该坐标测量该位置上像素的灰度值。方法如下：对连续的f（x，y）进行等间隔采样，在（x，y）平面上，将图像均分成均匀的小网格，每个小网格的位置可以用整数坐标表示，于是采样值就对应于一个M×N数字矩阵。这样就获得了数字图像中关于像素的两个属性：位置和灰度。位置由采样点的两个坐标确定，也就对应了网格行和列；而灰度表明了该像素的明暗程度。Matlab读入图象的函数为imread（filename，format）。而文章讨论的碎片图像格式为bmp的8位灰度图像，每一像素的取值范围为0～255。

3 碎片的分类

3.1 碎片特征提取

准确地确定碎片的特征对碎片的分类起着重要作用，原始的碎片图像中可利用的像素点较多，而碎片图像中能有效反应碎片的特征的像素需要恰到好处地提取。文字的笔画有粗细之分，由此，不考虑笔画的粗细，文字的轮廓更能体现碎片的特征。运用边缘检测的方法，实现对文字轮廓的确定。

（a） （b）

图1 边缘化处理前后对比图

将每行边缘轮廓像素通过累加法，得到一个180维的向量。边缘轮廓像素在180维的向量的每一分量的值呈现一定的规律，图2为图1（a）的累加向量。

3.2 K-Means聚类分析方法

K-Means聚类指基于划分的聚类分析[4]，事先需要制定将数据分为几类，给定一个有n个个体的数据集，将它划分为K个簇（k？燮n），使每个簇具有较高的相似度，而簇间的相似度较低。它需要满足以下两个条件：（1）K类中任意一类不为空集，即每一类至少有一个个体；（2）每一个体都属于且仅属于K类中的一类。

其中相似度的计算：根据一个簇中点的平均值（被看作簇的重心）来进行。K-means聚类算法的描述和处理流程如下：K-means是用于划分的K均值算法，每个簇的中点用簇中对象的均值表示，其输入为簇的数目K和包含n个对象的数据集，输出为K个簇的集合，使得平方误差准则最小。原理如下：

（1）首先为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心；（2）将样本集中的样本按照最小距离原则分配到最邻近聚类；（3）使用每个聚类中的样本均值作为新的聚类中心；（4）重复步骤（2）和（3）直到聚类中心不再变化；（5）结束，得到K个聚类。

将样本分配到距离他们最近的中心向量，并使目标函数值最小，K-means算法的目标函数通常可以表示为：

E=■■P-m■■

式中，E是数据集中所有对象的平方误差和；P是数据对象，文章表示给定对象的像素特征值；mi是Ci的均值（P和mi都是多维）；P-m■■表示P与mi之间的度量。通过求这个目标函数E的最小值来试图使生成的结果簇尽可能地紧凑和独立。

对于度量，形象地说就是我们主要考虑的样本间的差异。在数据分析和数据挖掘的过程中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。我们要比较个体x和个体y间的差异，它们都包含了n个维的特征，即x（x1，x2，…，xn），y=（y1，y2，…，yn），如下几种距离主要衡量两者的差异，其中d（x，y）越小，即样本x，y之间的距离越小，样本x，y越相似，差异度越小；反之，越大。

欧几里得距离（sqEuclidean）：d（x，y）=（■（xi-yi）2）1/2

绝对值距离（cityblock）：d（x，y）=（■xi-yi

特别地当xi∈0，1yi∈0，1 此时又称汉明距离；

余弦距离（cosine）：d（x，y）=（■xi，yi）/（（■xi2）1/2（■yi2）1/2）

4 碎片匹配

根据碎片邻接原理以及图片格式的性质，我们给出了如下定理：

定理1. 假设a1和a2分别为“.bmp”图片格式两碎纸片的矩阵（如图5），s1为a1最右侧列，s2为a2的最左侧列，如果a1与a2为邻接碎纸片（a1为左边，a2为右边）的必要条件为：

如果非边缘第m个点，m∈s1为黑色（值为0），则s2中的第m-1，m，m+1个位置中必然存在不为白色的点（值255）；同理：如果此时s2处非边缘的第n个点，n∈b为黑色（值为0），则s1中的第m-1，m，m+1个位置中必然存在不为白色的点（值255）。

证明：由“.bmp“图片格式灰度（值0～255）特性即证。

图3 碎纸片匹配示意图

因为这是图像匹配[1]的必要条件，即不满足这个条件必定不能匹配，满足条件为可能匹配的碎纸片。假设满足条件中的碎纸片矩阵集合为an■，i∈N■，则如果i=1，则这一个唯一确定的匹配。如果i>1，则需要人工干预，找出匹配度最高的碎纸片。

定理2. 假设a1和a2分别为“.bmp”图片格式两碎纸片的矩阵，s1为a1最右侧列，s2为a2的最左侧列，定义绝对值差异度

d（S1，S2）=■S1i-S2i，其中S1=（S11，S12，…，S1n），S2=（S21，S22，…，S2n）

5 碎片拼接Matlab GUI软件包

运用前面三节的内容，我们设计了碎片拼接Matlab GUI软件包， 根据聚类分析K均值距离公式的不同，我们设计了如下参数设置界面：

图4 k-means参数设置界面

点击图4的确定按钮后，弹出图5行内拼接界面。

图5 行内拼接界面

完成行内拼接后，点击“下一步”，出现行间拼接界面，最后生成完整的纸张。

图6 行间拼接界面

参考文献

[1]庄俊东.基于数字图像处理的人民币碎纸片拼接方法的研究[D].上海交通大学，2010.

[2]张翠.基于点线的文档图片数字水印与碎纸片拼接[D].中国海洋大学，2011.

[3]葛巧瑞.自然场景下的文字分割及识别研究[D].西安电子科技大学，2011.

[4]吕晓玲，谢邦昌.数据挖掘方法与应用[M].北京：中国人民大学出版社，2009.endprint

摘 要：文章详细阐述了基于Matlab GUI对单面印刷文档经碎纸机破碎的碎片（既纵切又横切）的恢复，结合计算机对碎片的匹配搜索和人工干预，提高文档恢复的效率，达到文档的恢复。

关键词：Matlab GUI；聚类分析；人工干预

1 概述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是，当碎纸片数量巨大，人工拼接很难在短时间内完成任务[1-3]。

随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。文章基于Matlab GUI对破碎文档（既纵切又横切）的复原实现人机互动，并给出了提高文档复原效率的方法。

2 图像采样

图象采样就是按照图像空间的坐标测量该坐标测量该位置上像素的灰度值。方法如下：对连续的f（x，y）进行等间隔采样，在（x，y）平面上，将图像均分成均匀的小网格，每个小网格的位置可以用整数坐标表示，于是采样值就对应于一个M×N数字矩阵。这样就获得了数字图像中关于像素的两个属性：位置和灰度。位置由采样点的两个坐标确定，也就对应了网格行和列；而灰度表明了该像素的明暗程度。Matlab读入图象的函数为imread（filename，format）。而文章讨论的碎片图像格式为bmp的8位灰度图像，每一像素的取值范围为0～255。

3 碎片的分类

3.1 碎片特征提取

准确地确定碎片的特征对碎片的分类起着重要作用，原始的碎片图像中可利用的像素点较多，而碎片图像中能有效反应碎片的特征的像素需要恰到好处地提取。文字的笔画有粗细之分，由此，不考虑笔画的粗细，文字的轮廓更能体现碎片的特征。运用边缘检测的方法，实现对文字轮廓的确定。

（a） （b）

图1 边缘化处理前后对比图

将每行边缘轮廓像素通过累加法，得到一个180维的向量。边缘轮廓像素在180维的向量的每一分量的值呈现一定的规律，图2为图1（a）的累加向量。

3.2 K-Means聚类分析方法

K-Means聚类指基于划分的聚类分析[4]，事先需要制定将数据分为几类，给定一个有n个个体的数据集，将它划分为K个簇（k？燮n），使每个簇具有较高的相似度，而簇间的相似度较低。它需要满足以下两个条件：（1）K类中任意一类不为空集，即每一类至少有一个个体；（2）每一个体都属于且仅属于K类中的一类。

其中相似度的计算：根据一个簇中点的平均值（被看作簇的重心）来进行。K-means聚类算法的描述和处理流程如下：K-means是用于划分的K均值算法，每个簇的中点用簇中对象的均值表示，其输入为簇的数目K和包含n个对象的数据集，输出为K个簇的集合，使得平方误差准则最小。原理如下：

（1）首先为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心；（2）将样本集中的样本按照最小距离原则分配到最邻近聚类；（3）使用每个聚类中的样本均值作为新的聚类中心；（4）重复步骤（2）和（3）直到聚类中心不再变化；（5）结束，得到K个聚类。

将样本分配到距离他们最近的中心向量，并使目标函数值最小，K-means算法的目标函数通常可以表示为：

E=■■P-m■■

式中，E是数据集中所有对象的平方误差和；P是数据对象，文章表示给定对象的像素特征值；mi是Ci的均值（P和mi都是多维）；P-m■■表示P与mi之间的度量。通过求这个目标函数E的最小值来试图使生成的结果簇尽可能地紧凑和独立。

对于度量，形象地说就是我们主要考虑的样本间的差异。在数据分析和数据挖掘的过程中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。我们要比较个体x和个体y间的差异，它们都包含了n个维的特征，即x（x1，x2，…，xn），y=（y1，y2，…，yn），如下几种距离主要衡量两者的差异，其中d（x，y）越小，即样本x，y之间的距离越小，样本x，y越相似，差异度越小；反之，越大。

欧几里得距离（sqEuclidean）：d（x，y）=（■（xi-yi）2）1/2

绝对值距离（cityblock）：d（x，y）=（■xi-yi

特别地当xi∈0，1yi∈0，1 此时又称汉明距离；

余弦距离（cosine）：d（x，y）=（■xi，yi）/（（■xi2）1/2（■yi2）1/2）

4 碎片匹配

根据碎片邻接原理以及图片格式的性质，我们给出了如下定理：

定理1. 假设a1和a2分别为“.bmp”图片格式两碎纸片的矩阵（如图5），s1为a1最右侧列，s2为a2的最左侧列，如果a1与a2为邻接碎纸片（a1为左边，a2为右边）的必要条件为：

如果非边缘第m个点，m∈s1为黑色（值为0），则s2中的第m-1，m，m+1个位置中必然存在不为白色的点（值255）；同理：如果此时s2处非边缘的第n个点，n∈b为黑色（值为0），则s1中的第m-1，m，m+1个位置中必然存在不为白色的点（值255）。

证明：由“.bmp“图片格式灰度（值0～255）特性即证。

图3 碎纸片匹配示意图

因为这是图像匹配[1]的必要条件，即不满足这个条件必定不能匹配，满足条件为可能匹配的碎纸片。假设满足条件中的碎纸片矩阵集合为an■，i∈N■，则如果i=1，则这一个唯一确定的匹配。如果i>1，则需要人工干预，找出匹配度最高的碎纸片。

定理2. 假设a1和a2分别为“.bmp”图片格式两碎纸片的矩阵，s1为a1最右侧列，s2为a2的最左侧列，定义绝对值差异度

d（S1，S2）=■S1i-S2i，其中S1=（S11，S12，…，S1n），S2=（S21，S22，…，S2n）

5 碎片拼接Matlab GUI软件包

运用前面三节的内容，我们设计了碎片拼接Matlab GUI软件包， 根据聚类分析K均值距离公式的不同，我们设计了如下参数设置界面：

图4 k-means参数设置界面

点击图4的确定按钮后，弹出图5行内拼接界面。

图5 行内拼接界面

完成行内拼接后，点击“下一步”，出现行间拼接界面，最后生成完整的纸张。

图6 行间拼接界面

参考文献

[1]庄俊东.基于数字图像处理的人民币碎纸片拼接方法的研究[D].上海交通大学，2010.

[2]张翠.基于点线的文档图片数字水印与碎纸片拼接[D].中国海洋大学，2011.

[3]葛巧瑞.自然场景下的文字分割及识别研究[D].西安电子科技大学，2011.

[4]吕晓玲，谢邦昌.数据挖掘方法与应用[M].北京：中国人民大学出版社，2009.endprint