碎纸片的自动拼接复原技术

摘要：破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。目前发现对碎纸片的拼接大部分由人工完成，准确率较高，但耗费大量人力财力及时间，效率很低。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。现先对仅纵切的碎纸片进行研究，开发出利用计算机，更便捷快速拼接碎纸片的方法。

本文首先对碎纸片的自动拼接复原问题建立相应的数学模型，利用图像的色彩特征建立图像灰度值矩阵，根据拼接特性找到其中可以拼接碎纸片的相关性，然后在matlab软件环境下进行编程、编译及调试，得到各碎纸片的正确拼接顺序后，对仅纵切的碎纸片进行拼接复原。

主要工作有以下几个方面：

关键词：碎纸片  拼接复原   matlab软件   灰度值

目   录

第一章  绪论

    1.1    碎纸拼接技术及项目背景·························（2）

    1.2    国内外研究现状·································（3）

    1.3    论文主要内容···································（3）

第二章  MATLAB概述

  2.1     MATLAB产生的历史背景························（4）

 2.2     MATLAB的特点································（5）

 2.3     MATLAB在图像处理中的应用····················（7）

第三章  数字图像处理

   3.1    数字图像处理技术简介···························（9）

   3.1.1  数字图像处理的特点·····························（9）

   3.1.2  数字图像处理技术的研究内容·····················（10）

   3.1.3  数字图像处理技术的应用·························（12）

   3.2    图像处理工具简介·······························（12）

   3.3    MATLAB中的图像类型及类型变换················（13）

   3.3.1  图像和图像数据·································（13）

   3.3.2  图像处理工具箱所支持的图像类型·················（13）

第四章  碎纸片拼接

   4.1    拼接思路·······································（17）

   4.2    拼接结果·······································（18）

第五章  总结与展望

5.1    全文总结·······································（20）

5.2    工作展望·······································（20）

参考文献··············································（21）

致谢···················································（21）

附录···················································（22）

第一章      绪论

1.1  碎纸拼接技术及项目背景

    为从民主德国时期安全部门的档案碎片中寻找秘密，德国政府自1991年起开始着手还原这些档案。一直到2007年，负责整理这些档案碎片的部门一直采取手工还原的方式，工作人员将碎片铺在大桌子上，通过人名和签名等痕迹将它们拼凑起来。历经17年，25名工作人员已将350袋碎片拼好，但等待它们的还有106万袋，按这个速度，他们要花几个世纪才能完成任务。德国政府决定花费835万美元，准备用计算机软件将约600万块碎纸片拼接起来[1]。同样，2011年美国国防部高级研究项目局发起“拼图挑战”，谁最先将5份切碎的文件拼凑起来将获得5万美元奖金。此举旨在希望有人能够开发计算机算法，解决文件拼接问题，方便美国军方读取战场上所获文件碎片的内容[2]。因此，开展对碎纸片的自动拼接复原技术的研究有着重要的现实意义。

    碎纸自动拼接技术是图像处理与模式识别领域中的一个较新但是很典型的应用，它是通过扫描和图像提取技术获取一组碎片的形状、颜色等信息，然后利用计算机进行相应的处理从而实现对这些碎纸片的全自动或半自动拼接还原。碎纸自动拼接的关键技术包括图像预处理和匹配。碎纸图像预处理的目的是将碎纸片表示为适合于利用计算机进行处理的形式。 图像预处理包括图像获取，背景分割，边界检测，轮廓提取和表示等。匹配技术是碎纸自动拼接中关键之中的关键，就是用储存在计算机中的模型去识别输入的未知视觉模式，并最终建立对输入的解释。

在对图像的理解中，匹配技术起着重要的作用。匹配技术可以归为两类，一类是比较具体，多对应图像底层像素或像素的集合，统称为图像匹配；另一类则比较抽象，主要与图像或目标的性质有关，统称为广义匹配。图像匹配包括模板匹配、目标匹配和动态匹配。广义匹配包括关系匹配、线图同构和特征内容匹配。特征内容包括颜色匹配、纹理匹配、形状匹配和综合特征匹配等。目前根据碎纸拼接的特点，主要用到的是颜色匹配技术，即将图形转化成像素点的灰度值并在计算机上得到相应矩阵，在忽略边缘效应的状态下对其灰度值进行匹配从而拼接。

1.2 国内外研究现状

    目前碎纸的拼接工作大部分都是靠人工的方式完成。虽然国外对这项工作进行了一些研究，但是由于碎纸的自动修复技术应用背景的特殊性，目前几乎没有公开的研究资料可以参考。类似的研究主要是集中在文物碎片的自动修复、虚拟考古、故障分析以及计算机辅助设计、医学分析等领域。

前东德情报机构“斯塔西”官员将大量绝密文件撕成6亿多块碎纸片后丢进16000个垃圾袋，及史学家认为恢复这些文件意义重大，但如果人工手段进行恢复，将耗费至少400年时间。在司法技术鉴定中也存在着类似的问题，大量的纸质物证复原工作目前基本上都是以手工方式完成的。一旦碎纸的数量增大到几百甚至上千块的时候，如果仍然依靠手工完成，不但耗费大量的人力、物力，而且还可能对物证造成一定的损坏。目前，在国际上，德国等发达国家对破碎文件的自动修复技术已经进行了相当长时间的研究。但是由于技术封锁的原因，我们所能够搜集到的资料非常有限。而在国内，还没有类似的研究成果问世。因此，结合碎纸自动拼接在司法技术鉴定中的应用这一背景，把计算机视觉和模式识别应用于碎片复原，开展对碎纸自动拼接技术的研究技术的研究具有重要的现实意义[3]。 本文的目标是利用计算机辅助的方法对仅纵切的碎纸片进行拼接、复原的关键技术。

碎纸自动拼接可以近似看成是一个拼图问题（jigsaw puzzle problem）。在机器人和计算机视觉领域中，很早就有学者对自动拼接问题进行了研究。H.Wolfson等人开发了一套机器人系统，能让机器人在标准的拼图游戏中找到各个对应的匹配块，并操作机器人进行自动拼图。这些技术都利用了拼图游戏中的一些特殊特征（如平滑的轮廓，显著的角点等）以及一些先验知识。

1.3 论文主要内容    

论文共分六章，第一章介绍了课题的来源、背景，研究现状和论文的组织结构。第二章介绍了matlab的相关知识。第三章研究了碎纸拼接中的关键技术之一：图像预处理。第四章结合前面的研究结果，开发出基于计算机辅助的碎纸自动拼接系统。本文的目标是利用计算机辅助的方法对仅纵切的碎纸片进行拼接、复原的关键技术。                     

第二章  MATLAB概述

     在70年代中期，Cleve Moler博士和其他同事在美国国家科学基金的资助下开发了调用EISPACK和LINPACK的FORTRAN子程序库。EISPACK是特征值求解的FOETRAN程序库，LINPACK是解线性方程的程序库。在当时，这两个程序代表矩阵运算的最高水平。

到70年代后期，身为美国New Mexico大学计算机系系主任的Cleve Moler，在给学生讲授线性代数课程时，想教学生使用EISPACK和LINPACK程序库，但他发现学生用FORTRAN编写接口程序很费时间，于是他开始自己动手，利用业余时间为学生编写EISPACK和LINPACK的接口程序。Cleve Moler给这个接口程序取名为MATLAB，改名为矩阵（matrix）和实验室(labotatory)两个英文单词的前三个字母的组合。在以后的数年里，MATLAB在多所大学里作为教学辅助软件使用，并作为面向大众的免费软件广为流传。

1983年春天，Cleve Moler到Standford大学讲学，MATLAB深深地吸引了工程师John Little。John Little敏锐的觉察到MATLAB在工程领域中的广阔前景。同年，他和Cleve Moler、Steve Bangert一起，用C语言开发了第二代专业版。这一代的MATLAB语言同时具备了数值计算和数据图示化的功能。

1984年，Cleve Moler和John Little成立了Math Works公司，正式把MATLAB推向市场，并继续进行MATLAB的研究和开发。

在当今30多个数学类科技应用软件中，就软件数学处理的原始内核而言，可分为两大类。一类是数值计算性软件，如MATLAB、Xmath、Gauss等，这类软件长于数值计算，对处理大批数据效率高；另一类是数学分析型软件，Mathmatica、Maple等，这类软件以符号计算见长，能给出解析解和任意精确解，其缺点是处理大量数据时效率较低。Math Works公司顺应多功能需求之潮流，在其卓越数值计算和图示能力基础上，又率先在专业水平上开拓了其符号计算、文字处理、可视化建模和实时控制能力，开发了适合多学科、多部门要求的新一代科技应用软件MATLAB。经过多年的国际竞争，MATLAB已经占据了数值软件市场的主导地位。

在MATLAB进入市场前，国际上的许多软件包都是直接以FORTRAN语言等编程语言开发的。这种软件的缺点是使用面窄、接口简陋、程序结构不开放以及没有标准的基库，很难适应各学科的最新发展，因而很难推广。MATLAB的出现，为各国科学家开发软件提供了新的基础。在MATLAB问世不久的80年代中期，原先控制领域里的一些软件包纷纷被淘汰或在MATLAB上重建。

时至今日，经过Math Works公司的不断完善，MATLAB已经发展成为适合多学科。多种工作平台的功能强大的大型软件。在国外，MATLAB已经经受了多年考验。在欧美等高校，MATLAB已经成为线性代数、自动控制理论、数理统计、数字信号处理、时间序列分析、动态系统仿真等高级课程的基本教学工具；成为攻读学位的大学生、硕士生、博士生必须掌握的基本技能。在设计研究单位和工业部门，MATLAB被广泛用于科学研究和解决各种具体问题。在国内，特别是工程界，MATLAB一定会盛行起来。可以说，无论你从事工程方面的哪个学科，都能在MATLAB里找到合适的功能。

MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。

 MATLAB 的应用范围非常广，包括信号和图像处理、通讯、控制系统设计、测试和测量、财务建模和分析以及计算生物学等众多应用领域。附加的工具箱（单独提供的专用 MATLAB 函数集）扩展了 MATLAB 环境，以解决这些应用领域内特定类型的问题。他具有以下诸多的优点：

   （1）友好的工作平台和编程环境 

 MATLAB由一系列工具组成。这些工具方便用户使用MATLAB的函数和文件，其中许多工具采用的是图形用户界面。包括MATLAB桌面和命令窗口、历史命令窗口、编辑器和调试器、路径搜索和用于用户浏览帮助、工作空间、文件的浏览器。随着MATLAB的商业化以及软件本身的不断升级，MATLAB的用户界面也越来越精致，更加接近Windows的标准界面，人机交互性更强，操作更简单。而且新版本的MATLAB提供了完整的联机查询、帮助系统，极大的方便了用户的使用。简单的编程环境提供了比较完备的调试系统，程序不必经过编译就可以直接运行，而且能够及时地报告出现的错误及进行出错原因分析。        

   （2）简单易用的程序语言 

 Matlab一个高级的矩阵/阵列语言，它包含控制语句、函数、数据结构、输入和输出和面向对象编程特点。用户可以在命令窗口中将输入语句与执行命令同步，也可以先编写好一个较大的复杂的应用程序（M文件）后再一起运行。新版本的MATLAB语言是基于最为流行的C＋＋语言基础上的，因此语法特征与C＋＋语言极为相似，而且更加简单，更加符合科技人员对数学表达式的书写格式。使之更利于非计算机专业的科技人员使用。而且这种语言可移植性好、可拓展性极强，这也是MATLAB能够深入到科学研究及工程计算各个领域的重要原因。

   （3）强大的科学计算机数据处理能力 

 MATLAB是一个包含大量计算算法的集合。其拥有600多个工程中要用到的数学运算函数，可以方便的实现用户所需的各种计算功能。函数中所使用的算法都是科研和工程计算中的最新研究成果，而前经过了各种优化和容错处理。在通常情况下，可以用它来代替底层编程语言，如C和C++ 。在计算要求相同的情况下，使用MATLAB的编程工作量会大大减少。MATLAB的这些函数集包括从最简单最基本的函数到诸如矩阵，特征向量、快速傅立叶变换的复杂函数。函数所能解决的问题其大致包括矩阵运算和线性方程组的求解、微分方程及偏微分方程的组的求解、符号运算、傅立叶变换和数据的统计分析、工程中的优化问题、稀疏矩阵运算、复数的各种运算、三角函数和其他初等数学运算、多维数组操作以及建模动态仿真等。 

（4）出色的图形处理功能 

 图形处理功能MATLAB自产生之日起就具有方便的数据可视化功能，以将向量和矩阵用图形表现出来，并且可以对图形进行标注和打印。高层次的作图包括二维和三维的可视化、图象处理、动画和表达式作图。可用于科学计算和工程绘图。新版本的MATLAB对整个图形处理功能作了很大的改进和完善，使它不仅在一般数据可视化软件都具有的功能（例如二维曲线和三维曲面的绘制和处理等）方面更加完善，而且对于一些其他软件所没有的功能（例如图形的光照处理、色度处理以及四维数据的表现等），MATLAB同样表现了出色的处理能力。同时对一些特殊的可视化要求，例如图形对话等，MATLAB也有相应的功能函数，保证了用户不同层次的要求。另外新版本的MATLAB还着重在图形用户界面（GUI）的制作上作了很大的改善，对这方面有特殊要求的用户也可以得到满足。 

（5）应用广泛的模块集合工具箱 

  MATLAB对许多专门的领域都开发了功能强大的模块集和工具箱。一般来说，它们都是由特定领域的专家开发的，用户可以直接使用工具箱学习、应用和评估不同的方法而不需要自己编写代码。目前，MATLAB已经把工具箱延伸到了科学研究和工程应用的诸多领域，诸如数据采集、数据库接口、概率统计、样条拟合、优化算法、偏微分方程求解、神经网络、小波分析、信号处理、图像处理、系统辨识、控制系统设计、LMI控制、鲁棒控制、模型预测、模糊逻辑、金融分析、地图工具、非线性控制设计、实时快速原型及半物理仿真、嵌入式系统开发、定点仿真、DSP与通讯、电力系统仿真等，都在工具箱（Toolbox）家族中有了自己的一席之地。 

（6）实用的程序接口和发布平台 

 新版本的MATLAB可以利用MATLAB编译器和C/C++数学库和图形库，将自己的MATLAB程序自动转换为独立于MATLAB运行的C和C++代码。允许用户编写可以和MATLAB进行交互的C或C++语言程序。另外，MATLAB网页服务程序还容许在Web应用中使用自己的MATLAB数学和图形程序。MATLAB的一个重要特色就是具有一套程序扩展系统和一组称之为工具箱的特殊应用子程序。工具箱是MATLAB函数的子程序库，每一个工具箱都是为某一类学科专业和应用而定制的，主要包括信号处理、控制系统、神经网络、模糊逻辑、小波分析和系统仿真等方面的应用。 

（7）应用软件开发（包括用户界面） 

    在开发环境中，使用户更方便地控制多个文件和图形窗口；在编程方面支持了函数嵌套，有条件中断等；在图形化方面，有了更强大的图形标注和处理功能，包括对性对起连接注释等；在输入输出方面，可以直接向Excel和HDF5进行连接。

 本次设计中使用的是MATLAB7.0，属于最新的版本之一，功能强大，有利于对实验进行简易操作，更能提高设计实验的准确性。

2.3 MATLAB在图像处理中的应用

 图像处理工具包是由一系列支持图像处理操作的函数组成的。所支持的图像处理操作有：图像的几何操作、领域和区域操作、图像变换、图像恢复与增强、线性滤波和滤波器设计、变换（DCT变换等）、图像分析和统计、二值图像操作等。下面就MATLAB在图像处理中各方面的应用分别介绍。

     以上所提到的MATLAB在图像中的应用都是由相应的MATLAB函数来实现的，使用时，只需按照函数的调用语法正确输入参数即可。具体的用法可参考MATLAB丰富的帮助文档。图像边缘对图像识别和计算机分析十分有用，在MATLAB中，函数edge()用于灰度图像边缘的提取，它支持六种不同的边缘提取方法，即Sobel方法、Prewitt方法、Robert方法，Laplacian3Gaussian方法、过零点方法和Canny方法。                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      

第三章    数字图像处理

一幅数字图像可以用一个矩阵来表示，对数字图像进行处理，实质上就是对特定的图像矩阵进行变换的过程，因此图形变换是数字图像处理技术的基础。 

3.1 数字图像处理技术简介

图像处理技术基本可以分成两大类：模拟图像处理(Analog Image Processing)和数字图像处理(Digital Image Processing)，数字图像处理是指将图像信号转换成数字信号并利用计算机进行处理的过程。数字图像处理技术主要包括如下内容：几何处理(Geometrical Processing)、算术处理(Arithmetic processing)、图像增强(ImageEnhancement)、图像复原(Image Restoration)、图像重建(Image Reconstruction)、图像编码(Image Encoding)、图像识别(Image Recognition)、图像理解(Imageunderstanding)。数字图像处理技术的发展涉及信息科学、计算机科学、数学、物理学以及生物学等学科，因此数理及相关的边缘学科对图像处理科学的发展有越来越大的影响。近年来，数字图像处理技术日趋成熟，它广泛应用于空间探测、遥感、生物医学、人工智能以及工业检测等许多领域，并促使这些学科产生了新的发展。

3.1.1 数字图像处理技术的特点

1. 数字图像处理技术的优点

(1)再现性好

数字图像处理与模拟图像处理的根本不同在于，它不会因图像的存储、传输或复制等一系列变换操作而导致图像质量的退化。只要图像在数字化时准确地表现了原稿，则数字图像处理过程始终能保持图像的真实再现。

(2)处理精度高

按目前的技术，几乎可将一幅模拟图像数字化为任意大小的二维数组，这主要取决于图像数字化设备的能力。现代扫描仪可以把每个像素的灰度等级量化为16位甚至更高，这意味着图像的数字化精度可以满足任一应用需求。从原理上讲不论图像的精度有多高，处理总是能实现的，只要在处理时改变程序中的数组参数就可以了。

(3)适用面宽

图像可以来自多种信息源。从图像反映的客观实体尺度看，可以小到电子显微镜图像，大到航空照片、遥感图像甚至天文望远镜图像。这些来自不同信息源的图像只要被变换为数字编码形式后，均是用二维数组表示的灰度图像组合而成，因而均可用计算机来处理。

(4)灵活性高

由于图像的光学处理从原理上讲只能进行线性运算，极大地限制了光学图像处理能实现的目标，而数字图像处理不仅能完成线性运算，且能实现非线性处理，即凡是可以用数学公式或逻辑关系来表达的一切运算均可用数字图像处理实现。

(5)信息压缩的潜力大

数字图像中各个像素是不独立的，其相关性大。在图像画面上，经常有很多像素有相同或接近的灰度。就电视画面而言，同一行中相邻两个像素或相邻两行间的像素，其相关系数可达0.9以上，而相邻两帧之间的相关性比帧内相关性一般说还要大些。因此，图像处理中信息压缩的潜力很大。

3.1.2 数字图像处理技术的研究内容

  1．几何处理

几何处理主要包括坐标变换，图像的放大、缩小、旋转、移动，多个图像配准，全景畸变校正，扭曲校正，周长、面积、体积计算等。

2．算数处理

算数图像处理主要对图像施以加、减、乘、除等运算。

3. 图像变换

由于图像阵列很大，直接在空间域中进行处理，涉及计算量很大。因此，往往采用各种图像变换的方法，将空间域的处理转换为变换域处理，不仅可减少计算量，而且可获得更有效的处理。

4. 图像增强

图像增强处理主要是突出图像中感兴趣的信息，而减弱或去除不需要的信息，从而使有用的信息得到加强，便于区分或解释。主要方法有直方图增强、伪彩色增强法、灰度窗口等技术。

5. 图像复原

图像复原的主要目的是去除干扰、模糊和图像畸变，恢复图像的本来面目。典型的去噪操作就属于复原处理。图像噪声包括随机噪声和相干噪声，随机噪声干扰表现为麻点干扰，相干噪声表现为网文干扰。去模糊也是复原处理的任务。这些模糊来自透镜散焦，相对运动，大气湍流，以及云层遮挡等。这些干扰可用维纳滤波、逆滤波波等方法加以去除。去除图像畸变则需要借助图像的空间变换操作。

6. 图像分割

图像分割是将图像中有意义的特征部分提取出来，这是进一步进行图像识别、分析和理解的基础。目前已研究出不少边缘提取、区域分割的方法，但还没有一种普遍适用于各种图像的有效方法。因此，对图像分割的研究还在不断深入之中，是目前图像处理中研究的热点之一。

7. 图像重建

几何处理、图像增强、图像复原都是从图像到图像的处理，即输入的原始数据是图像，处理后输出的也是图像，而重建处理则是从数据到图像的处理，也就是说输入的是某种数据，而处理结果得到的是图像。该处理的典型应用就是 CT 技术，早期为 X射线 CT，后来发展的有 ECT、超声 CT、核磁共振(NMR)等。图像重建的主要算法有代数法、迭代法、傅立叶反投影法、卷积反投影法等，其中以卷积反投影法运用最为广泛，因为它的运算量小、速度快。值得注意的是三维重建算法发展得很快，而且由于与计算机图形学相结合，把多个二维图像合成三维图像，并加以光照模型和各种渲染技术，能生成各种具有强烈真实感及纯净的高质量图像。三维重建技术也是当今颇为热门的虚拟现实和科学可视化技术的基础。

8. 图像编码

图像编码研究属于信息论中信源编码范畴，其主要宗旨是利用图像信号的统计特性及人类视觉的生理学及心理学特性对图像信号进行高效编码，即研究数据压缩技术，以解决数据量大的矛盾。一般来说，图像编码的目的有 3 个：(1)减少数据存储量；(2)减低数据率以减少传输带宽；(3)压缩信息量，便于特征提取，为识别做准备。

9. 模式识别

模式识别是数字图像处理的又一研究领域。当今，模式识别方法大致 3 种，即统计识别法、句法结构模式识别法和模糊识别法。统计识别法侧重于特征，句法结构识别侧重于结构和基元，而模糊识别法是把模糊数学的一些概念和理论用于识别处理。

10. 图像理解

图像理解是由模式识别发展起来的方法。该处理输入的是图像，输出的是一种描述。这种描述并不仅是单纯的用符号做出详细的描绘，而且要利用客观世界的知识使计算机进行联想、思考及推论，从而理解图像所表现的内容。

3.1.3数字图像处理技术的应用

在社会生产和科研活动中，人们要频繁的接触到图像，例如照片、图画、书报、医学 X 光片和卫星遥感图像等。图像是人们认识客观世界的重要知识来源。随着计算机的高速化和大容量化，图像信息的处理已成为可能。另外，由于摄像设备的小型化和高精度化，图像的画质有了显著改善。随着这些技术的进步，图像处理在工作站及个人计算机的小型机上已可以实现。

数字图像处理主要采用计算机来实现，随着计算机软硬件技术的突飞猛进，以及图像处理的长足发展，使得数字图像处理技术无论在科学研究、工业生产、军事国防以及现代管理决策部门等各行各业都得到越来越多的应用，其应用场合广阔、内容众多、形式新颖、门类齐全，可以说是方兴未艾，正向着实时化、大型化、小型化、远程化等多方面迅猛发展。

3.2图像处理工具箱简介

Matlab是一种基于向量（数组）而不是标量的高级程序语言，因而matlab从本质上就提供了对图像的支持。数字图像实际上是一组有序离散的数据，使用Matlab可以对这些离散数据形成的矩阵进行一次性的处理。Matlab对图像的处理功能主要集中在它的图像处理工具箱（Image Processing Toolbox）中。图像处理工具箱是由一系列支持图像处理操作的函数组成，可以进行诸如几何操作、线性滤波和滤波器设计、图像变换、图像分析与图像增强、数学形态学处理等图像处理操作。

 图像处理工具箱主要有：

＊ Image Acquisition Toolbox＊ Image Processing Toolbox＊ Signal Processing Toolbox＊ Wavelet Toolbox＊ Statistics Toolbox＊ Bioinformatics Toolbox＊ Matlab Compiler＊ Matlab COM builder

3.3  Matlab中的图像类型及类型转换     

3.3.1 图像和图像数据

    Matlab中的数字图像是由一个或多个矩阵表示的，Matlab强大的矩阵运算功能完全可以应用于图像，那些适用于矩阵运算的语法对Matlab中的数字图像同样适用。

缺省：double (64位浮点数)    uint8（无符号8位整型）

3.3.2  图像处理工具箱所支持的图像类型

图像处理工具箱支持4种图像类

型，它们是：

真彩色图像（RGB images）

索引色图像（index images）

灰度图像（intensity images）

二值图像（binary images）

此外，Matlab还支持由多帧图像组成的图像序列。

1.真彩色图像

真彩色图像用 R、G、B 3个分

量表示1个像素的颜色，所以对1个

尺寸为m×n的真彩色图像来说，其          

数据结构就是一个m×n×3的多维数组。如果要读取图像中(100，50)处的像素值，可以查看三元组(100,50,1∶3)。

真彩色图像可用双精度存储，此时亮度值的范围是［0,1］。常用的存储方法是用无符号整型存储，亮度值的范围为［0,255］。

真彩色图像数据格式：

双精度类: Double

(每个像素占8个字节)

整数类：Uint8

(每个像素占1个字节)

数组大小：m×n×3

(:,:,1)－红色分量

(:,:,2)－绿色分量

(:,:,3)－蓝色分量

像素取值：[0,1]

数组大小：m×n×3

(:,:,1)－红色分量

(:,:,2)－绿色分量

(:,:,3)－蓝色分量

像素取值：[0,255]

    2.索引色图像

索引图像是把像素值直接作为RGB调色板下标的图像。             

  Matlab中的索引色图像包含2个结构，一个是调色板map；另外一个是图像数据矩阵X。调色板是一个有3列和若干行的色彩映像矩阵，矩阵的每行都代表一种色彩，通过3个分别代表红、绿、蓝颜色强度的双精度数，形成一种特定的颜色。图像数据可以是uint8或是双精度的。需要注意的是Matlab中的调色板的色彩强度是［0,1］中的浮点数，0代表最暗，1代表最亮。

索引图像的数据格式：

双精度类:Double

(每个元素占8个字节)

整数类：Uint8

(每个元素占1个字节) 

图像数组大小：m×n

图像元素取值:[1,p]

调色板矩阵：p×3

图像数组大小：m×n

图像元素值:[0,p-1]

调色板矩阵：p×3

    3.灰度图像

    存储灰度图像只需要一个数据矩阵，数据类型可以是double也可以是uint8。存储时会使用一个默认的调色板来显示图像。

    灰度使用黑色调表示物体。每个灰度对象都具有从0%（白色）到100%（黑色）的亮度值。使用黑白或灰度值扫描仪生成的图像通常以灰度显示。使用灰度还可将彩色图稿转换为高质量黑白图稿。

灰度级变换（点运算）的定义

换T将产生一个输出图像g(x，y),           

且g(x，y)的每一个像素值都是由

f(x,y)的对应输入像素点的值决定

的，g(x，y)=T(f(x,y)).

4.二值图像

与灰度图像相同，二值图像只需一个数据矩阵，每个像素只有2个灰度值。可以采用uint8或double类型存储，工具箱中以二值图像作为返回结果的函数都使用uint8类型[9]。    

第四章 碎纸片拼接

4、1  拼接思路

根据以上科学知识的研究，首先对碎纸片拼接技术建立数学建模。

由于所给碎纸片为黑字白底，仅黑白两种颜色，可以将其断定为灰度图像，从而无需将其转换为灰度图像。如果所给图像为彩色图像，则需要用rgb2gray()函数将彩色图像转换为灰度图像后再进行研究计算。

首先将灰度图像使用imread（）函数转换为灰度值矩阵，由于图片为1980*72的尺寸，故得到的灰度值矩阵为1980行72列。

经分析可知，两张碎纸片若能无缝拼接，则这两张碎纸片之间的关系为，左边碎纸片对应的灰度值矩阵的最后一列与右边碎纸片对应的灰度值矩阵的第一列相似度最大，在忽略边缘效应的情况下可以认为这两列的值是完全相等的。故设计一段程序使之按照这种规律循环。由此可以判定出我们所需要的只是每个灰度值矩阵中的第一列和最后一列的数值，通过判断彼此之间的相似度关系可以得出碎纸片拼接顺序。同时，我们可以通过灰度值矩阵的第一列数值判断出第一张待接碎纸片。经过观察，我们发现第008张图片的第一列灰度值均为255，即全白，对于一张完整的印有字体的完整的纸而言，唯有其灰度值矩阵中的第一列和最后一列存在全白，由此可以断定该008图片为第一张待拼接图片。

接下来可以将008图的灰度值矩阵的最后一列作为原始的参考数列，设计算法将该列与其他灰度值矩阵的第一列进行循环比较判断，若判断出某一列的第一列与之相等，则以该列所在矩阵的最后一列作为参考数列，进行接下来的与其他数列的比较，如此循环往复的比较。判断出碎纸片的正确顺序后，用imshow函数对已经排好序的碎纸片进行输出。

应用此程序建立的模型，人工干预次数为1，机器运算次数为17，认为准确率为 16/17，较为成功。 根据上述模型，得到了复原拼接结果，经观察文件汉字笔画，拼接完整，文章文理通顺，条理清楚，碎片边缘间契合完好，且与实际手动拼接所得结果相同。即认为上述模型基本符合条件，在不考虑其他因素影响下，能完成碎纸片的自动拼接，应用于实际生活中。 此模型程序简单，准确率高，只需要在程序执行之前进行一次人工干预，不需要对待拼接图形的全部内容进行详细的分析，可以节省大量的时间和人力，在信息高速发展的今天，有着重要的现实意义。但此模型适用于在文字字数不多，文字文章连贯的，仅进行单方向切割的，简单碎纸片的拼接。

4、2  拼接结果

通过对程序的编写，得到各碎纸片的排列顺序，结果如下：

y =  

Columns 1 through 15

9    15    13    16     4    11     3    17     2     5     6    10    

14    19    12

Columns 16 through 19

 8    18     1     7

完整的程序代码见附录。

对排列好的碎纸片进行输出，得到完整的拼接图像如下：

第五章   总结与展望

5、1 全文总结

碎纸自动拼接复原是计算机视觉和模式识别的一个基本问题，图像预处理和碎片匹配是其中得关键技术。本文主要研究了碎纸自动拼接中得图像灰度值处理和匹配技术，并且应用于基于计算机辅助的碎纸自动拼接复原系统当中。

本文在查找了大量相关资料的基础上，围绕碎纸自动拼接这个主题重点研究了图像预处理技术，并将该技术应用到了碎纸拼接中，提出了基于碎纸拼接的一种方法。

（1）本文首先对matlab软件的概述及基本使用注意事项进行总结，防止在使用用matlab软件过程中出现不必要的问题。

（2）经过这段时间的研究，作者对图像的分类进行了不同程度的了解，由于不同图像分析方法不同，使得在建模过程中使用方法不同。

（3）本文在完成项目中对matlab软件的图像预处理技术进行了研究，了解到如何将不同类型的图像转换成灰度图像，从而进行进一步研究。

通过本次的毕设结果可知，程序简单易懂、错误率较低，保证了拼接的正确性，节省了大量人力物力及时间，并且可以将其推广到现实生活中去，比如破碎人民币的回复、历史文物的复原、司法文件的拼接等，另外还可以应用到拼图游戏的开发中。但是在准确性较高的同时，也存在着不足：本次设计所给的图片中含有大量的文字，所以我们利用它的文字特征也存在着一定的偶然性；在拼接过程中，我们也只考虑了边缘上的拼接，并没有继续增加条件以保证结果的准确性。

5、2 工作展望

本文通过对纵切的碎纸片复原进行了研究，在现实生活中，碎纸片的样式千奇百怪，例如对纵切加横切的碎纸片进行拼接，对双面且存在中英文打印的碎纸片进行拼接，对手撕不规则碎纸片进行拼接复原等等一系列的碎纸片的拼接技术的研究。并且当碎纸片的数量较大时，又该如何进行拼接等，这将会是一个比较大的研究课题。

参考文献

[1]林彬 .一起来拼图 打败碎纸机[N].钱江晚报 ，2011-12-02

[2]袁思陶 .德国计划将600万块档案碎片拼接还原[N].新华网，2007-05-11

[3]曹海燕.碎纸自动拼接关键技术研究[D].国防科学技术大学研究生院

[4]马辉.matlab在简单数学建模中的应用.

[5]蔡旭辉、刘卫国、蔡立燕.MATLAB基础与应用.北京：人民邮电出版社，2009

[6]王正林、刘明.精通MATLAB7.北京：电子工业出版社，2006

[7]Mathworks. MATLAB Programming Version 7.

[8]http://www.mathworks.cn/access/helpdesk/help/helpdesk.html

[9]王慧琴.数字图像处理 .北京：北京邮电大学出版社，2006

[10]卓金武等.MATLAB在数学建模中的应用.北京：北京航空航天大学出版社  2011

附   录

碎纸拼接完整程序代码如下：

[I1 map]=imread('d:\matlab\000.bmp');II1=im2double(I1);

[I2 map]=imread('d:\matlab\001.bmp');II2=im2double(I2);

[I3 map]=imread('d:\matlab\002.bmp');II3=im2double(I3);

[I4 map]=imread('d:\matlab\003.bmp');II4=im2double(I4);

[I5 map]=imread('d:\matlab\004.bmp');II5=im2double(I5);

[I6 map]=imread('d:\matlab\005.bmp');II6=im2double(I6);

[I7 map]=imread('d:\matlab\006.bmp');II7=im2double(I7);

[I8 map]=imread('d:\matlab\007.bmp');II8=im2double(I8);

[I9 map]=imread('d:\matlab\008.bmp');II9=im2double(I9);

[I10 map]=imread('d:\matlab\009.bmp');II10=im2double(I10);

[I11 map]=imread('d:\matlab\010.bmp');II11=im2double(I11);

[I12 map]=imread('d:\matlab\011.bmp');II12=im2double(I12);

[I13 map]=imread('d:\matlab\012.bmp');II13=im2double(I13);

[I14 map]=imread('d:\matlab\013.bmp');II14=im2double(I14);

[I15 map]=imread('d:\matlab\014.bmp');II15=im2double(I15);

[I16 map]=imread('d:\matlab\015.bmp');II16=im2double(I16);

[I17 map]=imread('d:\matlab\016.bmp');II17=im2double(I17);

[I18 map]=imread('d:\matlab\017.bmp');II18=im2double(I18);

[I19 map]=imread('d:\matlab\018.bmp');II19=im2double(I19);

%将图片转换为灰度矩阵

A=zeros(1980,19);    

A(:,1)=II1(:,1);A(:,2)=II2(:,1);A(:,3)=II3(:,1);A(:,4)=II4(:,1);

A(:,5)=II5(:,1);A(:,6)=II6(:,1);A(:,7)=II7(:,1);A(:,8)=II8(:,1);

A(:,9)=II9(:,1);A(:,10)=II10(:,1);A(:,11)=II11(:,1);A(:,12)=II12(:,1);

A(:,13)=II13(:,1);A(:,14)=II14(:,1);A(:,15)=II15(:,1);A(:,16)=II16(:,1);

A(:,17)=II17(:,1);A(:,18)=II18(:,1);A(:,19)=II19(:,1);

%A是每张碎纸片灰度值矩阵的第一列所组成的新矩阵，作为比较数列，

B(:,1)=II1(:,72);B(:,2)=II2(:,72);B(:,3)=II3(:,72);B(:,4)=II4(:,72);

B(:,5)=II5(:,72);B(:,6)=II6(:,72);B(:,7)=II7(:,72);B(:,8)=II8(:,72);

B(:,9)=II9(:,72);B(:,10)=II10(:,72);B(:,11)=II11(:,72);B(:,12)=II12(:,72);

B(:,13)=II13(:,72);B(:,14)=II14(:,72);B(:,15)=II15(:,72);B(:,16)=II16(:,72);

B(:,17)=II17(:,72);B(:,18)=II18(:,72);B(:,19)=II19(:,72);

%B是每张碎纸片灰度值矩阵的最后一列组成的新矩阵，是参考数列

b=II9(:,72);   

 %经判断008图为第一张待接碎纸片，故将其作为参考数列

[m,n]=size(A);%m为评价的指标数，n为评价对

r=1;

x=zeros(1,n-1);

for k=1:(n-1)

    D=A; %A为原始数据

     for i=1:n

         D(:,i)=abs(D(:,i)-b);

     end

     for i=1:m

         mmm(i)=max(D(i,:));

         nnn(i)=min(D(i,:));

    end

    mm=max(mmm);

    nn=min(nnn);

     for i=1:m

        for j=1:n

           D(i,j)=(nn+0.5*mm)/(D(i,j)+0.5*mm);

       end

   end

    for i=1:n

        r(i)=sum(D(:,i));

 end

       C(k,:)=r;

       x(k)=find(C(k,:)==max(C(k,:)));

       b=B(:,x(k));

   %寻求关联度最大的数，找匹配度

   end

   for i=1:n-1

       y(i+1)=x(i);

   end

   y(1)=9;

   y     %图像的位置

%将已排好序的碎纸片进行输出

> I0=imread('d:\matlab\008.bmp');

I1=imread('d:\matlab\014.bmp');

I2=imread('d:\matlab\012.bmp');

I3=imread('d:\matlab\015.bmp');

I4=imread('d:\matlab\003.bmp');

I5=imread('d:\matlab\010.bmp');

I6=imread('d:\matlab\002.bmp');

I7=imread('d:\matlab\016.bmp');

I8=imread('d:\matlab\001.bmp');

I9=imread('d:\matlab\004.bmp');

I10=imread('d:\matlab\005.bmp');

I11=imread('d:\matlab\009.bmp');

I12=imread('d:\matlab\013.bmp');

I13=imread('d:\matlab\018.bmp');

I14=imread('d:\matlab\011.bmp');

I15=imread('d:\matlab\007.bmp');

I16=imread('d:\matlab\017.bmp');

I17=imread('d:\matlab\000.bmp');

I18=imread('d:\matlab\006.bmp');

>> I=[I0,I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I18];

>> imshow(I)