基于条状碎纸片自动拼接 Auto Stitching of Crapped Paper Based on Strips

doi:10.12677/MOS.2013.24007

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Modeling and Simulation 建模与仿真, 2013, 2, 38-43

http://dx.doi.org/10.12677/mos.2013.24007 Published Online November 2013 (http://www.hanspub.org/journal/mos.html)

Auto Stitching of Crapped Paper Based on Strips

Dan Hang, Daqing Liao, Tingting Jiang, Ya Wang

Air Force Logistics College, Xuzhou

Email: hazel-hang@sohu.com

Received: Oct. 8th, 2013; revised: Oct. 23rd, 2013; accepted: Oct. 27th, 2013

stricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract: By using the method of similarity matching, strip scraps of paper in messy order are jointed. According to the

information on the left and the right column of each strip of paper images, we can calculate vector cosine. When vector

value is closer to 1, the matching degree of the left and right columns on other images is higher. Then according to the

maximum correlation principle, each strip of paper is spliced together, and the original text information of the image is

restored. Through the MALAB programming algorithm, the effectiveness of the algorithm is verified through prelimi-

nary examples.

Keywords: Stitching of Scrapped Paper; Correlation Analysis; Vector Angle Cosine

基于条状碎纸片自动拼接

杭丹，廖大庆，蒋婷婷，王娅

空军勤务学院，徐州

Email: hazel-hang@sohu.com

收稿日期：2013 年10 月8日；修回日期：2013 年10 月23 日；录用日期：2013 年10 月27 日

摘要：采用相似度匹配的方法，对凌乱次序的条状碎纸片进行拼接。根据每张条状碎纸图像的左、右边列处

的信息，计算它与其他条状碎纸图像的左、右边列的相关性即向量余弦值，向量值越接近 1，与其他图像左、

右列越匹配，然后根据最大相关性的原则，将各个条状碎纸拼接在一起，得到的图像就是要恢复的原始文本信

息。通过 MALAB 编程实现算法，并通过初步实例验证了算法的有效性。

关键词：碎纸片拼接；相关性；向量余弦值

1. 引言

碎纸拼接，是通过扫描和图像提取技术获取一组

碎纸片的形状、颜色等信息，然后利用计算机通过特

征匹配技术来识别相邻接的图像碎片，进而重现整个

物体的原貌。碎片拼接技术的研究很有实用价值。如，

考古研究中对破碎珍贵文物的修复，司法物证复原、

历史文献修复以及军事情报获取等领域。

碎片拼接的方法根据特征可以分为基于色彩、纹

理、材质、轮廓等图像碎片拼接；根据形状特征又可

以分为规则图像碎片和不规则图像碎片的拼接；根据

空间特征还可分为二维图像碎片拼接和三维图像碎

片拼接。

碎片拼接的主要工作流程可概括为以下三个步

骤：

1) 对图像碎片进行预处理，即对物体碎片数字

化，得到碎片的数字图像。

2) 图像碎片匹配，通过匹配算法找到相互匹配的

图像碎片。

Open Access 38

基于条状碎纸片自动拼接

3) 图像碎片的拼接合并，将相互匹配碎片拼接在

一起得到最终的复原图。

其中，最重要的就是第二步图像碎片匹配。图像

碎片匹配是图像碎片拼接的核心问题。

近些年国内很多学者对这一问题进行了大量研

究，提出了许多新的算法[1-7]，使得这一领域研究有了

长足的进步。本文采用相似度匹配的方法，对凌乱次

序的条状碎纸片进行拼接，根据每张条状碎纸图像的

左、右边列处的信息，计算它与其他条状碎纸图像的

左、右边列的相关性即向量余弦值，向量值越接近 1，

与其他图像左、右列越匹配，根据最大相关性的原则，

将各个条状碎纸拼接在一起，得到的图像就是要恢复

的原始文本信息。最后通过 MALAB 编程实现算法，

并利用附件 1，附件2提供碎片验证了算法的有效性，

实现碎片拼接为初始图像。

2. 基本假设

1) 在纸张切割处有油墨覆盖的部位没有受损断

裂，附着在纸上的油墨没有被扯开，在断裂处也没有

出现丢失油墨的情况。

2) 在图像预处理阶段对图像进行过几何畸变校

正和噪声点的抑制处理，让条状碎片不存在明显的几

何畸变以及毛刺边缘等问题，确保结果的可信度。

3. 变量说明

Bian_R——每张纸带图中右列信息

Bian_L——每张纸带图中右列信息

m——碎片个数

i——第i个碎片；j——除 i之外所有碎片

B——结构元素

4. 模型的建立和求解

4.1. 图像拼接算法

图像拼接的质量，主要依赖图像的配准程度，因

此图像的配准是拼接算法的核心和关键。根据图像匹

配方法的不同仁阔，一般可以将图像拼接算法分为以

下两个类型：

1) 基于区域相关的拼接算法

这是最为传统和最普遍的算法。基于区域的配准

方法是从待拼接图像的灰度值出发，对待配准图像中

一块区域与参考图像中的相同尺寸的区域使用最小

二乘法或者其它数学方法计算其灰度值的差异，对此

差异比较后来判断待拼接图像重叠区域的相似程度，

由此得到待拼接图像重叠区域的范围和位置，从而实

现图像拼接。也可以通过 FFT 变换将图像由时域变换

到频域，然后再进行配准。对位移量比较大的图像，

可以先校正图像的旋转，然后建立两幅图像之间的映

射关系。当以两块区域像素点灰度值的差别作为判别

标准时，最简单的一种方法是直接把各点灰度的差值

累计起来。这种办法效果不是很好，常常由于亮度、

对比度的变化及其它原因导致拼接失败。另一种方法

是计算两块区域的对应像素点灰度值的相关系数，相

关系数越大，则两块图像的匹配程度越高。该方法的

拼接效果要好一些，成功率有所提高。

2) 基于特征相关的拼接算法

基于特征的配准方法不是直接利用图像的像素

值，而是通过像素导出图像的特征，然后以图像特征

为标准，对图像重叠部分的对应特征区域进行搜索匹

配，该类拼接算法有比较高的健壮性和鲁棒性。基于

特征的配准方法有两个过程：特征抽取和特征配准。

首先从两幅图像中提取灰度变化明显的点、线、区域

等特征形成特征集冈。然后在两幅图像对应的特征集

中利用特征匹配算法尽可能地将存在对应关系的特

征对选择出来。一系列的图像分割技术都被用到特征

的抽取和边界检测上。如 canny 算子、拉普拉斯高斯

算子、区域生长。抽取出来的空间特征有闭合的边界、

开边界、交叉线以及其他特征。特征匹配的算法有：

交叉相关、距离变换、动态编程、结构匹配、链码相

关等算法。

4.2. 算法

本文采用相似度匹配的方法，考虑碎片的边缘匹

配情况，根据每张条状碎纸图像的左、右边列处的信

息，计算它与其他条状碎纸图像的左、右边列的相关

性，根据最大相关性的原则，将各个条状碎纸拼接在

一起，得到的图像就是要恢复的原始文本信息。对于

碎纸片左右的相关性，我们用向量余弦值衡量向量值

越接近 1，与其他图像左、右列越匹配。

4.2.1. 向量余弦值

多维空间中有方向的线段。如果两个向量的方向

Open Access 39

基于条状碎纸片自动拼接

Open Access

3. 提取图像左边缘数据。一致，即夹角接近零，那么这两个向量就相近。而要

确定两个向量方向是否一致，这就要用到余弦定理计

算向量的夹角了。

4. 提取图像右边缘数据。

5. 计算不同图像左右边相似度向量余弦值。

6. 计算余弦值接近 1的程度。

余弦定理对我们每个人都不陌生，它描述了三角

形中任何一个夹角和三个边的关系，换句话说，给定

三角形的三条边，我们可以用余弦定理求出三角形各

个角的角度。假定三角形的三条边为 a，b和c，对应

的三个角为 A，B和C，那么角 A的余弦

7. 找相邻图像边最相似。

8. 对图片进行排序。

9. 拼接图像、匹配碎片。

4.3. 碎片复原实例(MATLAB 编程实现)

222

cos 2

bca

Abc





 算法流程图(图3)[8]：

为了初步验证算法的有效性，下面给出两个实

例：

如果我们将三角形的两边b和c看成是两个向

量，那么上述公式等价于例1：附件 1给出的碎片有 18 个，如：(仅列举

几个个碎片，具体见附件 1)。(图4)

cos bc

Abc





通过 MATLAB程序复原碎片得到的18个条形碎

片的排列顺序(MATLAB 编程实现)：表 1。

其中分母表示两个向量 b和c的长度，分子表示两个

向量的内积。下图5即为附件1原文件的复原图图1这是一份

中文文件。

举个具体的例子，假如提取碎纸片左边 Bian_L

和右边 Bian_R 对应向量分别是 x1，x2，…，x64000

和y1，y2，…，y64000，那么它们夹角的余弦等于，

例2：附件2给出的碎片有 18 个，如图 6：(仅列

举几个碎片，具体见附件 2)

1 1226400064000

222 222

1 2640001264000

cos xy xyxy

xxx yyy







 





通过 MATLAB程序复原碎片得到的 18 个条形碎

片的排列顺序(MATLAB 编程实现)：见表 2。

当两条边向量夹角的余弦等于一时，这两条边文

字情况信息完全重复；当夹角的余弦接近于一时，两

条边文字信息相似，从而可以归成一类；夹角的余弦

越小，两条边文字信息越不相关，如图 1和2。

Figure 1. Vector similarity

图1. 两向量相似

4.2.2. 算法

下面给出本文算法的步骤：

1. 首先通过MATLAB 软件确定图像位置，再调

用MATLAB 软件里的 imread 函数读取图像数据(即颜

色值)。

2. 用MATLAB 软件里的 im2double 函数把图像

的数据类型转换成双精度浮点类型。 Figure 2. Vector independent

图2. 两向量无关

Table 1. Fragment sequence of recovery

表1. 复原碎片排列顺序

008 014 012 015 003010 002 016001004005009013018011 007 017 000006

Table 2. Fragment sequence of recovery

表2. 复原碎片排列顺序

003 006 002 007 015018 011 000005001009013010008012 014 017 016004

基于条状碎纸片自动拼接

转换双精度

类型（取边缘

带存入数组）

其余碎片

程序筛选出

的初始碎条

计算余弦值

左边缘转换双

精度类型

左边缘转换双

精度类型

拼接后的不

完整文档

左边缘转换双精

度类型

循环

碎条

完整图

调入

Figure 3. Flow chart

图3. 流程图

Figure 4. Fragment legend

图4. 碎片图示

图7即为附件 2原文件的复原图图 2这是一份英

文文件。

5. 模型评价

传统上，拼接复原工作需由人工完成，准确率较

高，但效率很低。特别是当碎片数量巨大，人工拼接

很难在短时间内完成任务。由于碎纸片的拼接复原技

术的重要性，目前世界上对它已经有了研究，能够查

阅到的文档碎片拼接技术主要使用曲线的特征来进

行碎片拼接，计算量非常巨大。

本文首先介绍了一些关于碎纸拼接的方法，然后

在详细研究了 MATLAB 软件的应用的基础上，设计

了碎纸片自动拼接复原的算法，最后通过题目中的实

例对本文提出的算法和方法进行验证，通过拼接出来

的图像可以证明本文的算法和方法是切实可行的。但

是可以看到，文章主要解决的是对规则长条形状的碎

纸片能够进行很好的拼接，而对于非规则的碎片、形

状差异大的碎片等等情况，还不能够进行顺利的拼

Open Access 41

基于条状碎纸片自动拼接

Figure 5. Restored view

图5. 复原图

Figure 6. Fragment legend

图6. 碎片图示

Open Access

基于条状碎纸片自动拼接

Figure 7. Restored view

图7. 复原图

接，因此有待深入研究。

参考文献 (References)

[1] 陶波, 于志伟, 郑筱祥 (1997) 图样的自动拼接.

中国生物医

学工程学报

, 4, 29-35.

[2] 韩煜 (2008) 基于颜色和纹理特征的计算机自动拼图研究.

硕士论文, 首都师范大学, 北京.

[3] 钟家强, 王润生 (2001) 基于边缘的图像配准改进算法.

计

算机工程与学科

, 6, 25-29.

[4] 罗智中 (2011) 基于线段扫描的碎纸片边界检测算法研究.

仪器仪表学报

, 24, 7-9.

[5] 刘金根, 吴志鹏 (2002) 一种基于特征区域分割的图像拼接

算法.

西安电子科技大学学报

, 6, 768-771.

[6] 贾海燕, 朱良家, 周宗潭, 胡德文 (2006) 一种碎纸自动拼接

中的形状匹配方法.

计算机仿真

, 23, 180-183．

[7] 吕科 (2003) 空间物体碎片的自动复原算法研究.

计算机应

用

, 4, 29-33.

[8] 苏金明, 张莲花, 刘波 (2005) MATLAB 高级编程. 电子工业

出版社, 北京.

Open Access 43