基于聚类分析的碎纸复原算法

付苗苗，张　露，宁莹莹，黄　婵，吴梦杰

(长春师范大学数学学院，吉林长春 130032)



基于聚类分析的碎纸复原算法

付苗苗，张露，宁莹莹，黄婵，吴梦杰

(长春师范大学数学学院，吉林长春 130032)

[摘要]本文针对单面印刷文件纵向切割、单面印刷文件横纵交错切割和双面印刷文件横纵交错切割的碎纸片三个问题，运用灰度矩阵、特征匹配和蚁群算法，分别给出碎纸还原方案。

[关键词]灰度矩阵；边缘去噪；邻域平均法；图像特征匹配；蚁群算法

1问题的设立与分析

本文主要研究边缘规则的碎纸片有效快速拼接的方法。首先进行简单说明，分析讨论对象是统一的宋体四号、固定值12、首行缩进2字符的文字文件。文字文件经扫描之后调整像素为1024×1600的图片，切割成类似于碎纸机碎纸效果的小碎片。仅纵向切割碎纸片像素为128×1600，切割成8个碎纸片；横纵交错切割碎纸片像素为128×200，切割成64个碎纸片；正反面横纵交错切割成64个碎纸片，生成128张图片，碎纸片图片保存格式为*.jpg，a表示正面，b表示反面。

问题一：单面印刷文件纵向切割的碎纸片拼接。现实中的数字图像在数字化和传输过程中常常会受到设备与外界环境噪声干扰等影响，因此要先对碎纸片图片的边缘进行去噪，在这里采用邻域平均法对图像边缘进行降噪处理。构建每个碎纸图片的二值矩阵，在一定程度上降低了计算的复杂程度。然后对每个碎纸片的左右边缘相似度进行分析，通过两两比较图片左右相似程度对碎纸片进行排序与拼接，最后得以复原文件内容。

问题二：单面印刷文件横纵交错切割的碎纸片的拼接。由于这种切割方法导致碎纸文片数量相对较多，所以先判别出最左边的碎片，然后对剩下的图片进行特征值匹配(这里的特征值就是指像素点对应的值)。由于碎纸片是由文件横纵交错切割而成，不仅需要考虑碎片的左右边缘的特征，还应考虑碎片上下边缘的特征，通过比较碎纸片四周边缘的相似度，对碎纸片进行排序拼接，使得文件复原。

问题三：双面印刷文件横纵交错切割。碎纸片的数量在问题二的基础上又增加了一倍，在拼接技术上增加了难度。这里采用蚁群算法(ACA)的SIFT特征点匹配原理来解决问题。首先提取碎纸图片四周边缘的特征值，然后采用蚁群算法进行快速对比匹配排序，最后对碎纸片拼接使文件得以复原。

2模型的假设与符号说明

2.1模型的假设

假设一：原文件左右两侧均存在页边距。

假设二：不考虑扫描文件存储为图片时，光线强度对碎纸片灰度的影响。

假设三：文件中所给的碎纸片形状相同，且它们之间能够完全无缝拼接。

假设四：文件的文字高度和宽度一样，间距相同，字体大小和字体样式相同。

2.2符号的定义(表1)

表1　符号定义表

3模型的建立与求解

我们要将一个完整的文件扫描图片进行切割而成的大小相同的碎纸片，首先这些碎纸片满足了假设条件，我们将其打乱，重新编号，以达到碎纸片拼接的目的。图1、图2、图3为分解文件之后的碎纸片图像前三张。

图2　纵向切割2

图3　纵向切割3

3.1问题一：单面印刷文件纵向切割的碎纸片拼接

3.1.1步骤流程

图4　问题一步骤流程图

3.1.2图像转化为二值矩阵

二值图像(binary image)是指一副二值图像的二维矩阵仅由0、1两个值构成的。其中“0”表示黑色，“1”表示白色。每个像素点对应的颜色不是黑色就是白色，其灰度值没有中间过渡的图像。二值图像一般用来描述文字或者图形，其优点是占用空间少。 因此，针对问题一，我们先将对应的碎纸图片用MATLAB调用im2bw()函数对导入的碎纸图片求解其二值矩阵。二值矩阵部分数据如表2所示。

表2二值矩阵表

3.1.3图像边缘去噪——邻域平均法

现实中的数字图像在数字化和传输过程中常受到成像设备与外部环境噪声干扰等影响，称为含噪图像或噪声图像。所以，我们采用邻域平均法对图像进行边缘去噪，在像素点的某一邻域内取像素的均值来代替该点的像素。将已经进行二值化的碎纸片图片左右边缘进行去噪处理，消弱噪声点起到平滑作用，减小相似度误差，增大匹配准确度。设f(i,j)为给定的含有噪声的图像上像素点对应的值，经过邻域平均处理后的图像上像素点对应的值为g(x,y)，则邻域平均法也可以用数学公式表达(S=[1024*1600])：

3.1.4边缘相似度

边缘相似度是比较待测图像边缘上各个点与对应的标准图像边缘上各个点之间的位置差距，用来判断对应的各个点的相似程度。将含噪图像通过噪声抑制算法处理后的待测边缘图像设为BY，对于BY上的一个边缘点x(i,j)，其边缘相似度可以定义为：

根据公式，可总结出每个点的相似程度。通过计算待测图像边缘点与对应的标准图像边缘点之间的位置差距来比较。如果两个点完全重合，则对应的两个点相似程度最大，计算公式的值为1；如果相差k个像素点，根据计算公式对应的两个点的相似程度则降低e-k；如果出现的不是待测图像边缘上的点，却检测成了边缘点，或者是待测图像边缘上的点，却没检测出来，根据计算公式显示default。每个碎纸片图像边缘相似度可以定义为图像边缘上所有点的边缘相似度的平均值。

其中，M为待测边缘图像中边缘上的点的总个数。

3.1.5基于MATLAB比较边缘相似程度进行排序

通过比较每个碎纸片图像的左右边缘相似程度，得出排列顺序，如表3所示。

表3　问题一的碎纸拼接顺序表

采用MATLAB拼接技术，调用imread()函数进行拼接。

3.2问题二：单面印刷文件横纵交错切割的碎纸片的拼接

3.2.1步骤过程

图5　问题二步骤流程图

3.2.2图像特征匹配

简而言之，特征匹配就是根据图像的特征进行匹配拼接，如果说我们进行的是不规则图形的拼接，就可以根据图形的边缘形状来进行筛选，而这里我们用规则的碎纸片转化成图像进行拼接，同样也是需要提取和分析图像的特征，例如图6和图7所示的两个碎纸片。

图6横纵交错切割1

图7　横纵交错切割2

图8　对应图4特征分析

图9　对应图5特征分析

图8中p3板块有文字；图9中q1、q3板块有文字，q2板块有部分文字，这分别就是图8和图9的图像特征，而且显然图像特征不匹配。

下面用程序来判断碎纸片图像边缘是否有匹配，建立如下模型：

该模型表示第一张图片最后一列的第i个特征值与其它张图第一列的第i个特征值比较，并且还对后一张碎纸片图像的第一列的第i+1，i-1个特征点进行比较。

3.2.3基于MATLAB比较边缘特征点匹配程度进行排序和拼接

通过比较每个碎纸片的左右上下边缘的特征点的匹配程度，对碎纸片排序如表4所示。

表4　问题二的碎纸拼接顺序表

(横向续表)

(横向续表)

(横向续表)

调用MATLAB拼接函数进行拼接，恢复原文件。

3.3问题三：双面印刷文件横纵交错切割

3.3.1步骤过程

图10　问题三步骤流程图

3.3.2基于ACA搜索的碎纸片图像SIFT特征点匹配

蚁群算法(ACA)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法，其灵感来源于蚂蚁。蚂蚁群体在寻找食物过程中，当一只蚂蚁找到食物后会释放信息素，周围的蚂蚁就会知道这个地方有食物，从四面八方不同的路径找到食物，最短路径上慢慢会聚集很多的蚂蚁。自然界中蚂蚁搜索食物的过程是一个不断聚类过程，食物就是聚类中心，用数学语言来表述就是：Xi是一只蚂蚁，蚂蚁分别聚集到j个聚类中心Cj(j=1,2,…,k)Xi到Cj的距离为dij，采用如下欧式距离计算。

其中，Xi表示蚂蚁，Cj表示聚类中心，m表示维数，P表示加权因子。假设算法中蚂蚁对自己所走过的有记忆，则可根据2张待拼接碎纸片图像上互信息浓度选择转移方向，从而引导蚂蚁根据互信息浓度测度最大值的方向移动。信息素计算公式：

其中，计算公式中α为信息素的相对重要程度，β为启发式因子的相对重要程度，ρ为信息素蒸发系数，1-ρ为信息素的持久性系数，τ为窗口信息素含量，η为启发函数，N为循环遍历次数。

图像特征匹配是将从两个或多个图像中提取出来的图像特征或者说特点用参量描述出来，并通过参量的相关算法来进行图片匹配的一种方法。所以要先对带匹配的两张碎纸片图像进行处理，然后提取满足特定要求的特征集或特征区，然后将其进行对应匹配，生成一组新的对应特征对集，最后利用这组特征对之间的对应关系计算出全局变换参数。基于图像特征的匹配方法可以克服利用图像灰度信息进行匹配的缺点，由于图像的特征点比较像素要少很多，大大减少了匹配过程中的计算量；特征点的匹配度量值对位置的变化比较敏感，可以大大提高匹配的精确程度；特征点的提取过程可以减少噪声的影响，对灰度变化和图像变形等都有较好的适应能力。

3.3.3基于MATLAB结合算法对碎纸片进行排序拼接

经过计算得到如下拼接顺序与效果：a面，即正面拼接顺序如表4所示；b面，即反面拼接顺序如表5所示。

表5　问题三的碎纸片拼接顺序表

(横向续表)

(横向续表)

(横向续表)

4总结

4.1碎纸复原的优点

首先，本文解决问题的方法简单清晰，并且可以通过Matlab软件快速求解，有较强的理论性和实用性，通过实际的操作，验证了其可靠性。其次，全文贯彻边缘去噪，在相对精确的数据基础上比较碎纸片图像边缘的相似度，是保证图像拼接成功的基础。最后，碎纸片拼接复原的模型是基于文字信息构建的，先对碎纸片图像进行二值化，使研究数据简单化，再对图像二值矩阵的边缘相似度进行分析，查找排列顺序，自动拼接，相比较全人工拼接还是快一些的。

4.2改进

邻域平均处理可实现去噪的效果，模版尺寸越大，减少噪声的效果越好。但却牺牲了图像的清晰度，因此可以换取另外一种较好的边缘去噪的方法或者使用更好的扫描设备。由于采用了建立图像二值矩阵的方法，还原效果不够精确，不如直接使用灰度值进行边缘比较。

[参考文献]

[1]姜启源.数学模型[M].北京:高等教育出版社,2007.

[2]韩中庚.数学建模方法及其应用[M].北京:高等教育出版社,2009.

[3]陈杰.MATLAB宝典[M].北京:电子工业出版社,2013.

[4]贾海燕.一种碎纸自动拼接中的形状匹配方法[J].计算机仿真,2006,23(11):180-183.

[5]罗智中.基于文字特征的文档碎纸片半自动拼接[J].计算工程与应用,2012,48(5):207-210.

Shredding Restored Algorithm Based on Clustering Analysis

FU Miao-miao, ZHANG Lu, NING Ying-ying, HUANG Chan, WU Meng-jie

(School of Mathematics,Changchun Normal University, Changchun Jilin 130032,China)

Abstract:This paper studied the effective and fast splicing method of regular boundary on the scraped paper.On according to the actual example :the printing files of single-sided with longitudinal cutting and transverse and longitudinal staggered cutting ,even the printing files of double side with staggered vertical and horizontal cutting, we give the shredding restored algorithm, respectively.

Key words:gray matrix; edge-noise-removing; neighborhood average method; image feature matching; ant colony algorithm

[收稿日期]2016-04-07

[基金项目]国家级大学生创新创业训练计划项目“碎纸复原技术”(102052015003)。

[作者简介]付苗苗(1971- )，女，教授，博士，从事应用数学研究。

[中图分类号]TP391

[文献标识码]A

[文章编号]2095-7602(2016)06-0029-07