林 川，张学新

(1.武汉大学 经济与管理学院，湖北 武汉 430072；2.湖北工程学院 数学与统计学院，湖北 孝感 432000)

破损文档图像的拼接与恢复是摄影测量、计算机视觉、计算机图形学以及档案研究和调查科学领域中一个非常活跃的研究课题。例如，在大型图片的扫描和跨多页内容的打印过程中，常常会出现失真，不可能理想地完全重构原来的图片；由于材料老化，人为或遭遇机器切碎，文件可能被撕掉等等。针对这些场合场合，设计原始文档的自动或半自动重建算法能显著减轻复杂、费时的人工操作。

图像拼接是指从一组单独的或重叠的子图像重建或拼接成一个单一的、连续的图像的技术。通常两个片段之间的匹配仅出现在其相应的轮廓线上一小部分区域，所以图像拼接过程中必须进行部分曲线的匹配。根据碎片曲线的抽样是否均匀，匹配方法大体分为两类。一类是基于字符串匹配的方法，其中的碎片曲线通过均匀抽样的点表示，另类是基于特征匹配的方法，其中的碎片曲线通常由临界点或多边形近似表示。Peter & Adelson[1]使用多分辨率样条技术把多个图像拼接成一个较大的全景图。针对图像存在大量旋转拍摄、缩放和透视失真问题，Yasushi Kanazawaa & Kenichi Kanatani[2]提出了分层匹配方法，该方法首先提取特征点，然后通过随机投票和变量模板匹配方式逐步估计两张图像间的匹配关系。Ramesh Babu & Ravishankar[3]提出基于四叉树技术的全自动无缝图像拼接方法，但在实际应用中，难以用一个给定的成像源在一次拍摄中捕捉一个很大的图像。Durga Patidar & Akshay Jain[4]使用一种互相关的重叠去除算法确定和选择在新图像与先前合成图像间最相关性的点。为了快速计算相关性，他们组合快速傅立叶变换和基于梯度的图像融合算法，消除图像连接处的尖锐图像强度变化，逐步将一个个图像混合到相邻的复合图。Sevcenco等[5]假定图像的重叠区域中的光度不一致，提出基于Haar小波2D集成技术的无缝拼接图像方法。Rajesh Kumar等[6]采用无特色配准和最小混合方法，该方法适应于拼接一个在每两个连续图像间具有一定程度重叠的静止图像序列。在基于边缘点、角点、拐点等特征，基于碎片文字行特征、表格线特征的确定与匹配方面及小波域方法的研究方面，国内也有一些成果[7-10]，它们主要针对彩色图像及有明显特征的碎片文档。目前，很多图像拼接方法需要图像间有精确重叠和相同的场景以获得无缝的拼接结果。当需要拼接的图像无明显特征时，例如，当两个图像之间的关系完全未知时，匹配算法很难奏效。当前，研究无特征的图像拼接问题仍是一个挑战性的课题。

对那些重叠区域较大，平移和旋转量较小的图像拼接问题，基于字符串匹配的方法是有效的。基于特征的匹配方法通常在处理小的重叠区域时，一般比基于字符串匹配的方法更准确，但计算密集。鉴于此，本文提出了一种面向同一页印刷文字文件的纵切碎纸片的无特征图像拼接算法，该方法基于图像灰度，在矩阵行和相关度最大准则下，先选取每个碎片右列的灰度点集，然后分析每点编码空间邻居的碎片结构(即左列)，通过与其他碎片的局部特征进行相关度匹配，将破碎纸片成功复原。

1 基本原理

在扫描图像或打印文档时，相邻图像或文档之间存在部分重叠，因此，在进行相似性匹配后，可以确定出相邻碎片间的重叠位置，根据相对位置建立相邻图像或文档对，实现两个及多个图像的拼接。理论上，由于存在成对相关的补偿数据，任何相邻图像对可以完美地被拼接在一起。由于失真的出现，使得并非所有成对的相对位置可以同时实现拼接，需要根据某种相似度准则建立优化模型。

图像拼接的基本原则是整体对齐、局部调整、自动选择、图像融合、手动曝光补偿。通常，图像拼接与破损文档的恢复遵循如图1所示的步骤。

图1 图像拼接流程

其中，图像配准和图像合并是图像拼接中两个主要组成部分。图像配准的目的是找到需要拼接的图像之间的几何关系，而图像合并是生成一个完整的组合图像。

2 纵切碎纸片拼接算法

2.1 问题描述

将文档扫描图像沿纵向切分为19条碎片，得到来自同一页纸的纵切碎片数据集。部分中、英文碎片图像样例见图2。纵切碎纸片拼接的主要任务是试对给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切)，建立碎纸片拼接复原模型和算法。

图2 部分纵切碎片图像

2.2 模型假设

本文设计的算法基于如下三个方面的假设：

(1)每个碎纸片上字的大小、粗细相同；

(2)每个碎纸片上每一行的行间距相同；

(3)每个碎纸片内容没有缺损。

2.3 拼接模型

首先读出图2中19张碎纸片图像的像素获得19个矩阵。然后把各个矩阵的第一列依次读出，形成First矩阵；把各个矩阵的最后一列依次读出，形成Last矩阵。最后把像素小于128的替换为0(表示黑字)，将像素大于128的替换为1(表示空白)，将First矩阵、Last矩阵转变为二进制的矩阵BF=(bfij)19×180，BL=(blij)19×180。

建立模型。将BF矩阵的每一列与BL矩阵的每一列进行匹配，如果两个矩阵相同行的像素同时为1，则该行匹配，以行匹配成功总数最大为目标函数建立优化模型。即

maxz=∑xijt，i=1，2，…，19，j=1，2，…，19，t=1，2，…，1 980

约束条件为：

1)比较BF的第i列与BL的第j列的相同的第t行像素值是否同时为1， 即

yit+zjt≥2×xijt，i=1，2，…，19，j=1，2，…，19，t=1，2，…，1 980

(1)

2)BL的每一列与BF的固定列的每一行配对成功的次数如果小于1 980，则该张对应的碎纸片为最左边的，即

(2)

3)BF的每一列与BL的固定列的每一行配对成功的次数如果小于1 980，则该张对应的碎纸片为最右边的，即

(3)

综上，最佳的配对模型为：

maxz=∑xijt，

(4)

模型物理含义。如果把矩阵BF与矩阵BL的每一列视为19维空间上的一个点，则maxz=∑xijt本质上是最小化欧式空间上的两点间距离，等同于最大化两向量的夹角的余弦值。

2.4 算法实现

算法1是本文提出方法的总结。

算法1:纵切碎纸片拼接算法输入:碎纸片数据像素矩阵。第1步 :边界检测与裁剪图像。读取碎纸片数据像素矩阵,进行边界检测,裁剪各像素矩阵的第一列和最后一列,将剪裁出的所有第一列依次拼接到First矩阵中,剪裁出的所有最后一列依次拼接到Last矩阵中并分别保存;第2步 :图像二值化。把像素小于128的替换为0,表示黑字;将像素大于128的替换为1,表示空白,将所求的矩阵转变为二进制的矩阵,求得 矩阵和 矩阵分别保存。第3步 :碎纸片配对。比较 矩阵的每一列与 矩阵的每一列,如果相同行的像素同时为1,则该认为行匹配成功。以行匹配成功总数为目标函数,极大化之。输出:碎片序号的复原顺序号。

3 实验结果与分析

对模型(4)使用Matlab编写拼接程序，排列最佳方案的矩阵并将碎纸片复原，纸片顺序复原结果见表1和表2。中文文档图像碎片拼接结果见图3，英文文档图像碎片拼接结果见图4。从图3和图4的拼接结果可以看出，本文算法能有效实现纵切文档图像的无缝拼接，拼接后的图像内容完整，无明显的拼接痕迹。

表1 中文文档图像碎片序号复原顺序

表2 英文文档图像碎片序号复原顺序

图3中文文档图像碎片拼接结果

图4英文文档图像碎片拼接结果

4 结论

本文提出了一种基于灰度相关匹配的纵切碎纸片拼接方法，该方法以相邻匹配的相容性作为相似性度量，以行匹配成功总数最大作为全局优化的准则函数，进行优化求解。在拼接过程中，首先两两配对，并将所有匹配的列序号排序，然后进行人工干预，求得最佳方案，最后通过消除匹配的模糊性以恢复原始文档。本文算法的优点在于不需复杂的图像预处理过程，适合于图像畸变小、切割规则的碎片拼接。

[参 考 文 献]

[1] Burt P J，Adelson E H.A multiresolution spline with application to image mosaics [J].ACM Transactions on Graphics，1983，2(4): 217-236.

[2] Kanazawa Y.Kanatani K.Image mosaicing by stratified matching[J].Image and Vision Computing，2004，22(2): 93-03.

[3] Ramesh B D R，Ravishankar M.Automatic seamless image mosaicing: an approach based on quad-tree technique//Proceedings of the World Congress on Engineering，2010: 687-691.

[4] Patidar M D，Jain M A .Automatic Image Mosaicing: An approach based on FFT[J].International Journal of Scientific Engineering and Technology，2011，1(1): 1-4.

[5] Ioana S S，Peter J H，Pan Agathoklis.Seamless stitching of images based on a Haar wavelet 2D integration method//Proceedings of the 17th International Conference on Digital Signal Processing，2011:1-6.

[6] Kumar C R，Nikhita N，Roy S，Murthy V V S.An image stitching system using featureless registration and minimal blending[J].International Journal of Engineering Research and Applications，2012，2(2): 1215-1222.

[7] 刘金根,吴志鹏,刘上乾，等.一种基于特征区域分割的图像拼接算法[J].西安电子科技大学学报：自然科学版，2002，29(6): 768-772.

[8] 张欣,卜彦龙,朱良家，等.物证复原系统中的碎纸轮廓提取技术研究[J].计算机仿真，2006，23(11): 184-187.

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

[10] 李波.一种基于小波和区域的图像拼接方法[J].电子科技，2005(4): 49-52.