基于0-1整数规划的碎纸片拼接复原算法

庄思发,付喜梅

（韶关学院数学与统计学院,广东韶关512005）

基于0-1整数规划的碎纸片拼接复原算法

庄思发,付喜梅

（韶关学院数学与统计学院,广东韶关512005）

碎纸片的拼接复原在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.研究利用计算机技术进行碎纸片的拼接与复原是一项十分重要且很有意义的工作.针对通过碎纸机切割形成的规则碎纸片的拼接复原工作提出了基于0-1整数规划的横向排序复原算法,并对既有横切又有纵切的情形提出了分类算法.实验结果表明算法准确率高,人工干预少.

0-1整数规划；碎纸片拼接；排序；分类

201 3年“高教社杯”全国大学生数学建模竞赛中,B题题目是讨论碎纸片的拼接复原问题.碎纸片的拼接复原在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统的拼接复原工作由人工完成,准确率高,但效率低.特别是当碎片数量巨大,人工拼接很难在短时间内完成任务.随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率［1］.

文字碎片拼接复原工作主要分为不规则碎片和规则碎片两类.对不规则碎片拼接还原主要采用的算法有边界检测算法、角点检测算法、遗传算法等［2］.例如,何鹏飞在文献［3］中提出了基于蚁群优化算法的全局拼接方法；文献［4］中的罗智中从文字特征的角度对碎纸片拼接复原进行了研究.他们的研究原理是基于碎纸片的边缘的形状轮廓和碎纸片边缘表现的色彩图像.而对于规则的碎片,如2013年大学生数学建模竞赛B题所讨论的使用碎纸机破碎所得的纸片,纸片均呈边缘齐整的矩形形状.其轮廓特征一致,上述的研究方法并不适用于此类问题.像此类规则碎纸片的拼接复原问题,文献［5-8］均进行了深入的研究.值得一提的是,文献［7］中段宝彬等使用近年来研究非常火热的深度卷积网络方法.上述方法在仅有纵切的情况下复原率均能达到100%复原率.但对于同时有纵切与横切的情况下,复原的准确率都不高,人工干预的次数较多.本文在2013年大学生数学建模竞赛B题的基础上对此类中文碎纸片的拼接复原工作进行研究.通过建立0-1整数规划模型给出了碎纸片横向拼接的全局优化算法,对于既有纵切又有横切的碎纸片,采用先分类再排序的办法进行复原.

1 问题分析

当碎纸片仅有纵切的情形时,每一碎纸片均为长条形.对这种碎纸片的拼接复原等价于对所有纸条进行左右排序.这个问题相当于典型的TSP（旅行商）问题,所不同的是它不需要回到起点.对于通过打印机输出的文件,其典型的特征是纸张上下左右均有一定的空白区域.纸张虽然被纵向切割成了若干条,但这一特征依然保留在了每一纸条中.依此特征,容易找出位于纸张最左侧及最右侧的两个纸条.而位于内部的其余纸条中,两纸条若是相邻的,则它们各自对应的右边缘与左边缘信息应是相似或相近的.据此原理,可以定义相应的距离以衡量纸条边缘的相似性,从最左边的碎片开始,逐一将与其相邻的碎片找出,最终将所有碎片排列正确.

定义1 给定n×1灰度向量x和y,定义x,y的余弦距离如下：

按照以上思路,首先将所有碎纸片的图片信息读入计算机,每一纸条存储为灰度矩阵数据（图片数据均来源于2013年“高教社杯”全国大学生数据建模竞赛B题）.数据矩阵中的数值为图片的灰度信息值,介于0～255之间,0代表黑色,255代表白色.因此,空白区域所有数值均为255.部分介于0与255之间的数值所占比重不大,它们实际是位于文字笔划边缘地带,仍可以看成是文字部分.

2 纵切碎纸片的横向拼接算法

假设X与Y是两纸条对应的灰度矩阵,它们若是左右相邻的,则X的最后一列数值与Y的第一列数值必定是相似的,或者说灰度值相近.仿照TSP算法的思路,以两碎片边缘的距离（定义1）来衡量两纸条边缘的相似度,再根据相似度的值可以判断两碎片是否相邻,最后给出各碎片的左右排列顺序.

2.1 启发式算法

一种易于实现且计算速度较快的排序算法是启发式算法［1］（算法1）.但该算法的缺点是所得解并非全局最优,对于仅有纵切的情形可以很好地解决,复原率可达百分百.但面对既有纵切又有横切的情形时,缺点就暴露得十分明显了,在某些碎片行中,复原率甚至低于50%.

算法1 启发式算法

假设纸张最左边及最右边的碎片对应矩阵分别为Xl与Xr,1≤l,r≤k.

输 入：X1,X2,…,Xk

初始化：令S=zeors(1,k);//0向量,存放排列好的序列；S(1)=l,S(k)=r;R=1,2,…,k;

R(l)=[];R(r)=[];//从R中删除标号l与r;t=1;

1) 令left=Xt(:,n);minDist=inf;

2) 对R中每一标号s,令right=Xs(:,1);并计算:dist=dcos(left,right);//left与right之间的距离

3) 若dist<=minDist,则令minDist=dist;target=s;否则返回2);

4) 若R中标号均已遍历,则令S(t+1)=target;R(R=target)=[];t=t+1,若t=k–1,则跳到5),否则返回1);

输出已排序标号：S.

2.2 全局优化算法

为使算法有较强的适用性，本文引入0-1整数规划，提出一种全局优化算法（算法2）.为了得到全局最优解,先计算出任意两张碎片之间的左右邻接距离（定义2）,再将问题转化成0-1整数规划问题进行求解.0-1整数规划的求解,实际上是在所有可能的排列顺序中寻找碎片邻接总距离最小的排列,显然,算法时间复杂度为O(n!),其中n为待排序的碎片总数.问题中待排序的碎片总量不大时，该算法依然能够顺利并高效的得出最优解.

定义2 假设X1,X2,…,Xk为k个待排序的m×n灰度矩阵,记Xi(:,t)为Xi的第t列数据,t=1,2,…,n,i=1,2,…,k.则Xi与Xj之间的距离aij定义为：

并规定碎片自身距离为无穷,即aii=∞,i=1,2,…,k.

如此,可得到一个非对称距离矩阵A=(aij),因对任意一个非最右侧碎片Xi来说,位于其右侧的碎片

是唯一的,故可设如下决策变量：

以总距离最小为目标,可得如下0-1整数规划：

该0-1整数规划容易使用Lingo或MATLAB软件求得最优结果,而后需要从最优解中回溯碎片排列顺序.方法是,先从待排序的碎片中确定首末两张碎片标号,然后从首碎片开始,依次从最优解中确定其相邻碎片标号,详见算法2.

算法2 全局优化算法

假设纸张最左边及最右边的碎片对应矩阵分别为Xl与Xr,1≤l,r≤k.

输 入：Xl,X2,…,Xk

初始化：Y=zeros(1,k);

1) 确定序列中最左边碎片Xl与最右边碎片Xr,置Y(1)=l,Y(k)=r;

2) 求解整数规划(1),得最优解矩阵X=(Xij);

3) for i=2:k–1//回溯碎片标号排列顺序

l=Y(i–1);

for j=1:k

若xlj=1,则Y(i)=j;

end

end

输出Y

因每一碎片包含的文字信息较多,碎片的边缘信息量大,故只有纵切的情形下算法效率与准确率都比较高,且不需要人工干预.

算法在实际运行过程中,某些碎片边缘会因相似度过大导致在回溯碎片标号时产生“子圈”,尤其是当碎片既有纵切又有横切时.当算法第三步的回溯过程到达某一碎片时,下一标号又指向了起点碎片,即最左边碎片.这将导致输出结果Y产生重复标号序列而得不到正确的结果.例如,某行排序结果中碎片标号出现了如下的循环:50,55,66,50,55,66,50,55,66,50,55,66,50,55,66,50,55,66,142.

为解决此问题,可考虑在循环中增加一个判断条件：若某一碎片标号的下一标号指向了起点标号,则将该碎片标号视为新的起点碎片,继续回溯后序碎片标号.也可考虑将回溯过程进行反向操作,即从最右端碎片标号开始往前回溯它的前一碎片标号.

3 纵横切碎纸片的拼接复原算法

当碎纸片经既有纵切又有横切而得到时,此时碎片尺寸较小,包含的信息量也少.此时直接使用算法1或算法2都无法进行处理,比较好的处理办法是先将问题中的209张碎片进行分类,属于同一横切行的碎片为一类.由于中文字符的特点,若碎片是位于相同的横切行,则它们的字符高度是可以对齐的,也即是说这些碎片的黑白相间的间隔是可以对齐的.据此,可以定义适当的距离再通过聚类分析,将碎片进行行聚类.为能够得到碎片黑白间隔信息,给出如下定义：

定义3给定m×n灰度矩阵X,称m×1向量θ=θ(X)为X的示性向量,其各分量θi(1≤ i≤ m)按如下方式取值：若X的第i行数据全为255（共n个）,则θi=0,否则θi=1.

聚类时,可用上述定义的余弦距离作为聚类准则.如问题所述,纸张被切成了11行19列的碎片,因此聚类分析类别数应定为11.MATLAB的聚类工具箱提供了丰富的聚类函数,如cluster,pdist,linkage等,可直接使用.但在实际计算时笔者发现聚类的效果并不理想,某些类中只有1到2个碎片被划入,而某些类中却被划入了多达38个碎片.这将导致过多的人工干预.

造成这个结果的原因是对于文章段落的末尾碎片部分,原本是在同行的碎片,却因位于行末的碎片下半部分几乎全是空白,与位于行首的碎片相差过大而被误分至其它类中.如图1中给的例子,两个碎片本是在纸张中同一行位置所切出的,但在聚类时会被分至不同类别.

为避免这样的现象,采用分类而非聚类的方法.即先从所有碎片中找出位于最左侧或最右侧的11张碎片作为已知类别的样本,再将所有剩余样本归于所属类别中,最后利用算法2对相应类别的碎片进行行排序.实际计算过程中,为进一步消除空白行的影响,每一灰度矩阵的示性向量,只取其上半部分,而忽略其下半部分,而且使用最右侧碎片作为已知类别.如果某一个碎片的示性向量与某已知类别的距离小于给定的阈值?时,则认为其属于该类别.

对于该209个碎片数据,经过多次的运算与比较,发现当取阈值τ=0.12时分类的结果最好,准确率最高,达到97%.此时209张碎片中仅有6张碎片没有被归类.其它阈值会导致某些类别被归入过多碎片,而某些类别则又出现过少碎片.例如,当τ=0.15时,分类结果中第1类归入了27张碎片,而第10类仅有9张碎片,准确率仅92%.分类算法见算法3,表1给出了当τ=0.12时的分类结果.

图1 两个同行被错分异类的碎片

最优结果（见表1）中仍有6张碎片没有被归类,此时通过人工干预的办法容易将它们归入相应的类别中,剩余的6张碎片分别是：14、15、72、90、126及183.经人工干预后,其中14、126及183号碎片归入第9类,15号碎片归入第10类,72号碎片归入第5类,90号碎片归入第7类.

上述分类方法简单易操作,正确率高,人工干预少.表2列出了同类文献不同方法碎纸片拼接复原的准确率，本文的算法3准确率高达97%，明显优于其他算法.当209张碎片被正确归入类别后,再使用算法2对属于同行的碎片进行行排序.因算法2是全局优化算法,故对所有11类的碎片进行行排序的结果能保证百分百的正确率,因此也不需要人工干预.经行排序后可得到经过横向切割的11条纸条排列序号.再按正确序列输出图像,可得到相应的复原效果图.图2给出了其中第10类的复原效果图.最后将11条碎纸条复原效果图经过简单的人工排序后可还原成完整的纸张结果,完整结果图略.

表1 τ=0.12时纵横切碎纸片分类结果

4 结语

研究利用计算机技术进行碎纸片的拼接与复原是一项十分重要且很有意义的工作.本文针对通过碎纸机切割而成的中文碎片提出了分类与排序算法,排序算法准确率高达100%,而分类算法的准确率高达97%,较k-均值聚类法高出近25个百分点.但也有如下两方面的缺点：一是算法依赖于中文字符排列比较齐整的特点,对于字符高度不一的英文碎片不适应；二是算法对不同类型的纸张复原效果不一.若被切割的纸张是全文字类型的,则效果较为理想.但若文件中出现插图、表格等类型时,因含有较多空白碎片,导致算法同样需要较多的人工干预.这些缺点有待日后进一步深入研究.

表2 各种方法的碎纸片拼接复原准确率

图2 第10类碎片经算法2的复原效果

［1］薛毅.碎纸片拼接复原的数学方法[J].数学建模及其应用,2013,2（5）:9-13.

［2］陈玉成,田娇.一种等大小矩形碎纸片拼接还原方法[J].厦门理工学院学报,2014,22（3）:103-108.

［3］何鹏飞.基于蚁群优化算法的碎纸拼接［D］.长沙：国防科学技术大学,2009.

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

［5］鲁嘉琪.基于文字信息的碎纸片拼接复原算法[J].现代电子技术,2014（4）:28-31.

［6］李明珺,徐晖,江彩云,等.基于Matlab研究碎纸片的拼接复原[J].赣南师范学院学报,2014,35（6）:19-22.

［7］段宝彬,韩立新.改进的深度卷积网络及在碎纸片拼接中的应用[J].计算机工程与应用,2014（9）:176-181.

［8］李蕾,麻思达,潘博渊.基于TSP规划模型的碎纸片拼接复原问题研究[J].数学建模及其应用,2014,3（2）:12-17.

Algorithm for Reconstruction of Shredded Paper Based on 0-1 Integer Programming

ZHANG Si-fa，FU Xi-mei
（School of Mathematics and Statistics,Shaoguan University,Shaoguan 512005,Guangdong,China）

The recovery of shredded paper has important application in judicial evidence recovery,historical document restoration and military intelligence acquisition.It is a very important and meaningful task to use computer technology for splicing and recovering of shredded paper.A sorting algorithm based on 0-1 integer programming is proposed for the splicing recovery of regular shredding pieces formed by shredder cutting,the classifying algorithm for the case of existing crosscutting and slitting is presented either.The experimental results show that the algorithm has high accuracy and less human intervention.

0-1 integer programming；reconstruction of shredded paper；sorting；classify

O221.4；TP391.41

A

1007-5348（2017）09-0009-06

2017-04-14

韶关学院科研项目（SY2016KJ16;S201501019）.

庄思发（1979-），男，广东揭西人，韶关学院数学与统计学院讲师，硕士；研究方向：模式识别、图像处理等.

（责任编辑：邵晓军）