规则碎片拼接算法

李 猛，刘家保

(1.合肥市统计局，合肥230071;2.安徽新华学院 公共课教学部，合肥230088)

如今世界上纸质碎片的拼接技术分人工和计算机自动拼接两种。由人工完成的拼接复原的正确率高，但效率非常低，当碎片数量多时，人工拼接难以在短时间里完成。随着计算机技术的发展，现代碎片拼接研究方向主要集中在计算机自动拼接［1－6］，但在处理碎片拼接时，当今主流是采用形状匹配、边缘比较、数据库匹配等技术，对硬件运算能力和储存能力都有着极高的要求。而很多情况下，并不需要处理太过复杂的碎片，如一般办公室通常采用的是碎纸机碎纸，所得的碎片形状比较规则，拼接不需要考虑形状匹配等因素，因此使用主流的对高硬件运行速度和存储空间消耗的算法就比较浪费。因此，以文件碎片边缘的黑白色匹配程度为依据，结合动态规划［8］理论，以普通家用电脑为硬件基础，提出了一种简洁有效的规则碎片自动拼接算法。

1 相关设定与定义

1.1 设 定

(1)无切割误差。碎纸机在切割文件时没有误差，切出来的碎片中文字方向平行于上下边缘，同一文件碎片大小完全一致;

(2)无打印误差。纸质文件按同一标准打印出来，行号、字号、行间矩完全一致，中文字体完全一致，英文字体完全一致;

(3)无物理误差。碎片图片无污迹，无毛边等干扰情况;

(4)论文中使用的误差为根据拼接实验中碎片的数据选定，可根据实际碎片数据进行更改。

1.2 定 义

(1)两文件碎片之间的匹配率［5］。读取每一个碎纸片图片文件为数据矩阵，选取适当阀值，将其用二值法化为0－1矩阵。任取碎纸片i和碎纸片j进行比较，记:

(2)已分组文件之间的行匹配率。在以将碎片文件分组排序的基础上，任取第i组和第j组进行比较，记

(3)碎片文字行高估计值。碎片所在行的每行文字所占碎片文件象素行数的最大值与最小值的估计值，简称为文字行高估计值。根据一碎片包含文字行数，每一碎片的行高估计值约有4～6个。如图1中碎片000.bmp 的行高估计值可记为 0，26，56，96，124，165。

图1 待拼接碎片000.bmp

2 碎片的按行分组

此时，仍可以碎片之间的匹配率为标准，利用贪心法［8］逐行拼接后再按行匹配率进行排序。但通过对中国2013年数学建模竞赛B题附件3提供碎片实际拼接结果发现，直接拼接误差非常大，正确率仅为30.81%。因此，在此采用先按行分组，再进行拼接的方法来降低误差。

在假定中，碎片文件的四边平行于原纸张相应边缘，且其中文字是按同一标准逐行打印而成的。所以从理论上，同行碎片文件的同行文字的行高与行间距都应该是对应相等的(图2)。

从图2中可以看出000.bmp，007.bmp，045.bmp行间矩基本相同，因此可以归成一类。且因为笔划、字形、灰度等情况可能会产生部分误差，通过图形对比，可把误差额度设置为(－5，5)。

分组算法:

第1步，按每一文件第一行象素全为255，和有多行不为255分类，为避免特殊情况产生误差，仅有前面连续2行以内不全为255的情况单独归为一类。

第2步，将按顺序选择一个未分组文件单独分为一组，提取每一行汉字所占象素行数的最小值和最大值，可得到3对数据。

第3步，以上述3对数据为基础，设为上述碎片文件的初始文字行高估计值，以同一类中其它文件的相应数据进行比较，选取方差小于阀值k的文件，将其加入001文件所在组，并将碎片文字行高估计值改为已加入该组的所有碎片文件相应数据的平均值。k的值根据实际需要选定，如根据允许误差范围(－5，5)，则可取阀值k=6×25=150。

第4步，以新得到的估计值为标准，重复步骤3，筛选出所有符合条件的文件，归为一组。

第5步，重复步骤2、3、4，直至完成全部分组。

第6步，根据整张纸片切割的行数m和列数n，对以上各组数据进行现次处理，按每组包含文件个数从大到小排列，以前11为基础。包含文件个数超过列数n的，以所在组每一碎片文件相应数据与碎片文字行高估计值比较，选出与标准差最小的n个文件，其余文件从组中移出。小于列数n的，以该组的碎片文字行高估计值为基础，将未分组文件和包含文件个数不超过3个的组包含文件依次比较，选出方差最小的若干个文件加入组中，补足n个。

图2 待拼接碎片示例图

以图2 中000.bmp，001.bmp，007.bmp，045.bmp 4个文件为例。

(1)000.bmp、007.bmp、045.bmp 同属于多行不全为255 的一类。

(2)按编号顺序从000.bmp开始分组处理，此时分组数为0，所以001不属于任何一组，将其单独分为1组{000.bmp}。提取碎片文件000.bmp每一行汉字所占象素行数的最小值和最大值，得到一组数据1、26、57、96、125、165，将其设为组{000.bmp}对应碎片所在行的相应数据的初始估计值。经检测，001.bmp属于第一行象素值全为255这一类别，此时，没有与其同一组的碎片文件，因此001.bmp单独分为一组{001.bmp}。

(3)经检测007.bmp每一行汉字所占象素行数的最小值和最大值为1、26、59、96、125、165，与初始估计值相比较，方差为4小于阀值k，所以将007.bmp并入组{000.bmp}，取新的碎片文字行高估计值为00.bmp和001.bmp 相应数据的平均值，1、26、58、96、125、165。

(4)依次将045.bmp 相应数据与之比较，最终将文件分为两组{000.bmp，001.bmp，045.bmp}和{001.bmp}。

每组内碎纸片的排序为:以分组数据为基础，对每一组文件，以同组文件之间的匹配率为标准，应用贪心法，将同组碎片文件排序。对已排序数据，以不同组文件之间的组匹配率为基础，应用贪心法，将各组进行排序。

3 人工较正和计算机辅助人工较正

在碎片过多的情况下，计算机拼接可能会由于打印、笔划、字型的不同等原因产生一定的误差，此时就需要通过手工对已处理结果进行较正。但受视力、思考速度等身体条件影响，在需要较正碎片量较大的情况下，人工较正可能会产生速度较慢、有一定误差等问题。

对此，在人工较正过程中，仍可以使用计算机进行辅助，用以加快较正速度，减少较正工作量。在处理过程中，可以采用遍历法，仍以碎片之间的匹配律为基础，让计算机按顺序推荐出与错拼的文件最匹配的5个(根据需要可自由选择数目)文件，便于快速较正误差。

4 拼接实验

试验以中国2013年数学建模竞赛B题提供文件为实验对象，使用MATLAB程序作为编程工具［7］。

4.1 仅纵向切割的碎片拼接

此时所有碎片均为一行，跳过行分组阶段，直接应用贪心法进行排序，即可直接得到正确顺序。此种情况下因计算匹配率时相应象素点数量较大，因而所得匹配率数据值可信度高，拼接结果错误率极小，一般不需要人工较正。

4.2 纵横切碎片拼接的问题

第1步，把所有碎片按前面的分组算法分组。以附件3为例，得表1:

表1 分组后得到的碎片组合

此处根据实际情况可适当调整阀值、误差区域。

第2步，对每一组分别排序，得表2:

表2 每一分组内部的碎片排序结果

第3步，人工较正。纵横切割的碎片在计算匹配率时进行比较的象素点较少，因此出错的可能性相对仅纵切的情况较高，偶尔需要进行人工较正。

通过上述结果，观察可得，上述结果中094号碎片与201号碎片不在正确的位置上，因为只有两个错误碎片，将094和201交换所在组重新排序即可。

若错误碎片也可采用计算机辅助，利用程序依次将094以外的其它碎片遍历一遍，得到与094匹配率最高的5个文件034、058、090、149、164，人工对比发现034号碎片与094号拼接最符合要求。同理可找到与201最适碎片005。

第4步，行间排序。利用两行之间的行匹配率，应用贪心法进行排序，得到表3正确顺序。

表3 附件3碎片附原顺序

5 倾斜切割的理论算法

从理论上来说，碎纸机切割纵横切割相结合，但实际上由于纸张变形、文件放置、机器精度等问题，很难做到标准的垂直和平行切割，在实际情况中难免会出现一些误差。这时仍可根据碎片文件之间的匹配率进行拼接，但如前所述，直接拼接误差太大所有仍然要先考虑分组。以下仅针对文件产生一定倾斜角的情况从理论上提出分组，其余情况可依此拓展。针对以下3个碎片文件(图3):

图3 倾斜切割所得到的文件碎片

现采用两种思路进行行分组:

(1)对碎片一分析，得到图片倾斜角大小，由此判断出与文字方向平行的空白行位置与相应行数。文字倾斜时因其上下两行文字高度始终改变，纵横切割拼接方法中按一行文字高度分组的方法就不适用了。这里采用相连接的两碎片左右文字的衔接度来分组。由于文字倾斜时一行文字所占最大值与最小值始终改变，因此采用按列抽样的方法。如对上面第一个碎片，抽取最左侧n列，取一行文字所占象素位置，逐列取其最大值和最小值(为避免误差，对一行文字最高处明显与前后不符的列舍去)，分别取其平均值，设为碎片文件左侧行高参数的估计值。同理，可得到碎片文件右侧参数的估计值。在允许一定的误差情况下，根据前一文件最右侧参数的估计值和最右侧参数估计值的比较进行行分组即可。

(2)在扫描碎片文件时通过手动，将碎片中文字方向恢复为水平，如上面碎片文件可扫描为图4:

图4 将文字方向调为水平后得到的文件碎片

此时可将文件按斜行分组，且每两个碎片要以如下两个标准进行拼接:两个碎片文件之间的匹配律;前一碎片文件最右侧文字行高与后一文件最左侧文字行高相匹配。

［1］罗智中.基于线段扫描的碎纸片边界检测算法研究［J］.仪器仪表学报，2011，32(2):289-294

［2］王欣洁.基于灰度矩阵的中文碎纸片的拼接复原算法［J］.智能计算机与应用，2013，3(6):95-97

［3］徐雅平，王运生.碎纸片的拼接复原［J］.上海商学院学报，2013，4(5):79-84

［4］李晓霞，高志鹏，张蕊倚，等.关于中英文的碎纸片拼接复原问题研究［J］.运城学报2013，31(5):12-15

［5］杨雯雯，陶佳琪，郑路通，等.单页单面汉字纵横切碎片拼接复原算法［J］.运城学报2013，31(5):16-20

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

［7］王沫然.MATLAB6.0与科学计算［M］.北京:电子工业出版社，2011

［8］THOMASH C，CHARLESE L，RONALD L R.Introduction to Algorithms算法导论［M］.北京:机械工业出版社，2010