论文总字数：24716字

摘 要

本文研究了碎纸片的半自动拼接复原技术。该技术的难点在于碎纸片的形状十分不规则，因而难以实现其局部匹配与全局搜索。为此，我们提出了一个包含四个步骤的算法框架。首先，在预处理阶段，我们数字化给定的文档碎片并提取出碎纸片的轮廓。接着，在轮廓表示阶段，我们提取出局部轮廓特征来加以表示各块碎纸片。然后，在局部匹配阶段，我们基于轮廓特征设置综合评价体系针对两两碎片之间找出匹配序列。最后，在全局搜索阶段，运用图论模型，我们将碎纸片抽象为结点，将碎纸片的匹配权值抽象为连接两个结点的边。随后，应用迭代算法，基于最大生成树算法每次选择出一条权值最大的边，融合该边所连接的两块碎纸片；由于融合碎纸片后产生了新的碎纸片和碎纸片之间的匹配，每轮迭代后还需要及时更新图论模型，直至拼接完成。这里的半自动拼接指的是，允许在系统关键参数的设置上引入适当的人工干预。

最终实验结果为，碎纸片来自同一张纸，实现其半自动拼接复原技术，测试碎纸片的数目为2,4,6片；碎纸片来自两张不同的纸，实现其半自动拼接复原技术，测试碎纸片的数目一张为2片，另一张为4片。

关键词：碎纸片拼接复原，半自动，最大生成树

A METHOD FOR SEMI-AUTOMATIC REASSEMBLY OF SHREDDED DOCUMENTS

Abstract

In this paper, we address the problem of semi-automatically assembling shredded documents. The challenge of this problem lies on the irregular shapes, which makes local matching and global matching very difficult tasks. We propose a four-step algorithmic framework. At first, we digitalize every fragments of given documents. Then we extract local outline features to represent these fragments. Afterwards, we set a proper evaluation system based on outline features to obtain the best local matching. At last, in global matching stage, we build a graph model, which regards fragments as vertices, the local matching result between two fragments as an edge linking two vertices. Moreover, applying the framework of iterative algorithm, we select an edge maximizing the weight and merge two fragments linked by this edge. Since new fragment and new local matching links related to this fragment are produced after merging vertices, we need to update graph model every iteration in time until the reassembly is over. During the whole process, proper artificial assistance is permitted when setting crucial parameters.

Our finial result shows that, we successfully reassembly documents from one paper, amount of fragments of which are 2, 4 and 6. We also successfully reassembly documents from two papers. The amount of fragments of the first paper is 2 and the second paper is 4.

KEY WORDS: document assembly, automatic, maximum spanning tree

目录

摘要 Ⅰ

ABSTRACT Ⅱ

第一章 绪论 1

1.1概述 1

1.2 研究现状 2

1.3论文组织结构 4

第二章 预处理 6

2.1 读取碎纸片 6

2.2 图像分割 6

2.2.1 边缘检测方法 6

2.2.2 门限处理方法 7

2.2.3 基于区域的分割方法 8

2.2.4 我们所采用的方式 8

2.3 获取单张碎纸片 9

2.3.1 连通分量 9

2.3.2 形态学重构技术 10

2.4.1形态学方法简介 11

2.4.2 形态学方法得到一像素宽的轮廓 11

第三章 轮廓表示 12

3.1 多边形近似 12

3.2 碎纸片特征提取 13

3.2.1 特征量的选取 14

第四章 局部匹配 16

4.1 匹配程度综合评价体系 16

4.1.2 离散评价函数 17

4.1.3 连续评价函数 17

4.2 确定匹配序列的起点和终点 17

第五章 全局搜索 19

5.1 碎纸片拼接的图论模型 19

5.2 最大生成树算法 19

5.3 基于最大生成树的迭代算法 21

5.4 最大生成树算法的变形 23

第六章 碎纸片的半自动拼接技术的实现 25

6.1系统框图 25

6.2拼接显示模块 25

6.3实验数据分析 26

6.4测试数据 26

6.5 部分测试用例的结果展示 27

第七章 总结与展望 31

7.1 本文工作总结 31

7.2 未来工作展望 31

致谢 33

参考文献（REferences） 34

第一章 绪论

1.1概述

碎纸片的拼接复原问题是军事情报获取、历史文物修复、司法物证鉴定等领域中经常要面对的问题。一个有名的例子是军事情报获取领域的“史塔西”计划。1989年11月9日柏林墙被推倒，随后，前民主德国情报机构，外号“史塔西”，开始大量销毁各式各样的档案资料。仅仅是手工撕毁的资料竟填装了整整16000个麻袋。统一后的德国政府计划尽数恢复这些被撕毁的宝贵资料，但是据估计“史塔西”计划至少要耗时400年才能够完成。截至2008年，由于每年耗资达100万欧元之巨，该计划被迫暂时停止。但是，截至2008年复原的档案中，已经包含了大量秘闻，举报，隐私和证据。另一个有名的例子是考古界的壁画修复。在世界各地，诸如希腊爱琴海、特洛伊以及古罗马等地都曾经出土了许多珍贵的壁画。这些壁画记录了当时的风土人情，除了极高的艺术价值，还是研究历史的第一手资料。但是，由于经年累月经受土层重压，壁画纷纷变形破碎，因此，这些珍贵的壁画在出土之际，常常已经成了成 百上千块碎片。为了重建这些历史珍品，目前只能依靠人力一块一块地拼接回去。

通常情况下，小规模的碎纸片复原工作都是手工拼接完成的。但是，当碎纸片的数目达到一定规模（gt;=1000）的时候，纯粹的手工拼接将会消耗大量的时间和精力；于此同时，拼接复原的结果的准确程度也会大大下降。

剩余内容已隐藏，请支付后下载全文，论文总字数：24716字