储成伟1
1 武汉学院信息工程学院
摘要：对重要文件的拼接复原，传统上都由人工完成，拼接准确率虽然高但是效率很低。本文旨在建立模型，利用计算机编程加少量的人工干预实现碎纸片的拼接复原。全等矩形破碎文字图片的拼接还原技术是一种特殊的图片拼接复原技术，它处理的图片具有明显几何规律而不能采用边沿几何形状识别拼接还原。对于规律性较强的图片，先通过数据挖据，得到图片中所有文字占据连续像素行的平均行数，图片中两行文字间的间距（行距）占据的连续像素行的平均行数，以及每张图片所包含的文字和行距之间的交替规律即行信息向量，并对图片边沿进行二值化处理。
关键词：破碎图片；贪心算法；数据挖掘；模式识别
依托武汉学院大学生创新训练项目，指导老师李丽容，湖北省教育科学规划课题-重点课题：2019GA066
1 引言
破碎文件的拼接还原在复原司法物证、修复历史文献以及获取军事情报等领域都有着重要的应用。一般地，由人工完成拼接复原，虽然准确率很高，但效率却低。尤其是当有数量巨大的碎片时，采用人工拼接复原几乎不可能在短时间内完成。随着计算机技术的发展，人们可以利用计算机实现破碎文件的自动拼接还原，以提高拼接复原效率，这样就可以把人从繁重的工作中解放出来，不再需要人工从大量碎纸堆中一块一块的比对寻找匹配的碎片，减轻了人的工作量和劳动强度，还能够让需求者在极短的时间内得到想要的结果，迅速准确的得到复原结果。
还原技术采用贪心算法，对图片进行拼接还原。先从图片的行信息向量中筛选出所有可能成为第一行的图片，对这些图片的行信息向量进行聚类分析，得到第一行的所有图片的序号。用同样的方法得到最左侧所有图片的序号，对这两个集合取交集，就得出了位于第一行第一列（左上角）的图片。根据左上角的图片，和最左侧所有图片的集合以及先前得到的文字和行距的信息，依次拟合出左侧图片的排列顺序。根据已排好序的左侧图片的行信息向量对剩下的图片进行分类，得到每张图片所在的行，再通过具有二值特征的Tanimoto测度，得出每行图片的排列顺序。最终得出所有图片的排列顺序，将所有图片按照该顺序拼接，即可实现图片的拼接还原。利用计算机完成破碎文件的拼接复原，不论是在复原司法物证方面，还是在修复历史文献方面，以及在获取军事情报等方面，相对于人工拼接都有着强大的时间优势，特别是军事情报和司法物证等具有即时性的文件，越是有时间上的优势，越能够提升价值。
2 背景
碎纸自动拼接技术是图像处理与模式识别领域中的一个较新且很典型的应用，它是通过扫描和图像提取技术得到一组碎纸片的颜色、形状等信息，然后利用计算机进行相关的处理从而实现对这些碎纸片的半自动或全自动拼接还原。
全等矩形破碎文字图片的拼接还原，主要是修复那些经特殊文件粉碎工具处理后而形成全等矩形的破碎文件，比较典型的就是还原经碎纸机处理后的文件。
此技术主要是针对在碎纸机的作用下，目标文件已经全被切割成全等的矩形小碎片。在进行拼接前人工将所有的小碎片放正（即上下不颠倒）扫描录入，并对每一个录入的图片进行编号，让每个碎片对应一个唯一的编号。然后将得到的所有碎片的图像的信息导入计算机，让计算机对其进行拼接还原得出目标图片（即原始资料的图片）及所有编号的排列顺序（位置）。
3数字图像概述
数字图像就是能够在计算机上显示和处理的图像，可以分为位图和矢量图两大类。位图一般用数字阵列来表示，通常有BMP、JPG、GIF等格式，矢量图由矢量数据库表示。本论文处理对象为位图，范例为BMP格式的图形。
一副数字图像可以视为一个二维函数f(x,y)，x和y为坐标，在平面中的任意一对坐标(x,y)上的幅值f称为该点图像的灰度、亮度、或强度。
一个大小为的数字图像是由行列的有限元素组成的，每个元素都有特定的位置和幅值，代表了其所在行列位置上的图像物理信息，如灰度彩色等。这些元素称为图像元素或像素。根据每个像素所代表信息的不同，可将图像分为二值图像、灰度图像、RGB图像及索引图像等。每个像素只有黑白两种颜色的图像称为二值图像。在二值图像中，像素只有0和1两种取值，用0表示黑，用1表示白。在二值图像中进一步加入许多介于黑色与白色之间的颜色深度，就构成了灰度图像。这类图像通常显示为从最暗黑色到最亮白色的灰度，每种灰度称为一个灰度级，通常用表示。在灰度图像中像素的取值范围为且为整数。根据类型的不同，可能有256种取值或者种取值，当时即为二值图像。
为了表述像素之间的绝对位置，本文所使用的坐标约定图1_1所示
图1_1 像素之间的绝对位置的坐标约定
.png)
其中，行列（M行N列）必须为正整数，在矩阵中，采用先行下标，后列下标的表示方法，因此是先纵坐标（对应行），然后才是横坐标（对应列）。
通过软件完成对图像的处理实质上就是通过计算机修改图像的像素矩阵。Matlab通过调用imread函数获取图像底层数据即像素矩阵。通过imwrite函数将底层数据写入对应格式的图片中。用计算机实现破碎图片的拼接还原，就是通过对底层数据进行数据挖掘，通过一系列算法进行处理，最终确定每张图片的对应位置，最后定义一个更大的像素矩阵，将所有图片的底层数据写入到矩阵的对应位置从而完成图片的拼接复原。
3.1获取图像的行信息向量和列信息向量
编号结束后，通过计算机图像处理软件获取每张图片的像素矩阵（表示编号为的图片，表示数字图像是由行列的有限元素组成）。如图3_2展示了待处理小图片‘001’号（即图3_1所示图片）的部分像素矩阵(“上”字的局部)。
.png)
图3_2 小图片000号的像素矩阵部分截图
得到所有图片像素矩阵后，由于每张图片都是全等的矩形图片，所以每张图片的像素矩阵的行数和列数都相等，每张图片的边沿线和其他图片的边沿线都完全匹配，直接用边沿线匹配还原出目标图案显然是行不通的。示例中的每张图片的像素矩阵都是一个的矩阵。若想将所有的小图片还原成一副完整的文字图片，需要对每张图片进行处理，挖掘出更多有用的信息。
首先可以根据每张图片的像素矩阵得到每张图片像素矩阵中哪些行和哪些列是全白的，哪些行和列表示有字迹的存在。根据这些信息可以直接筛选出那些可能为最顶端位置的图片和最左边、最底端，及最右边的图片。
.png)
于是可以得到每张图片的行信息向量和（表示编号为的图片）。例如‘001’号图片的行信息向量的分段
为了降低信息熵，让图片的边沿容易识别，对每张图片进行图片左侧边沿处理和右侧边沿处理。其算法分别如下：
3.2贪心算法
一般来说贪心算法不一定能够求得一个特定问题的最优解，但是贪心选择和最优子结构是两个关键的特点。如果问题具有这两个性质，就可以设计出它的一个贪心算法，并求出其中一个最优解。
贪心选择是指：一个全局最优解可以通过局部最优（贪心）选择来达到，换言之，当考虑做选择时，只要考虑对当前问题的最佳选择，而不考虑子问题的结果。
最优子结构是指：对一个问题来说，如果它的一个最优解包含了其子问题的最优解，则称该问题具有最优子结构。
通过前面的步骤对每张图片的处理后，就可以进入图片的拼接还原了，为了让这些边角全等的矩形小图片最终拼接成一张完整的文字图片。可以采用贪心算法来完成。
如果所有小图片拼成一张完整的图后，假设虚拟环境下将这张图卷起来，使最左端和最右端相接则满足了所有小图片都有后继这一条件。这样求所有图片拼接成一张完整图片就可转化成一个最优化问题，即求使得所有（；i=1，…，n；k=1，…，n）之和并且使得这个和式最大时的一个最优解。即：
目标函数：
.png)