碎纸片复原

关于碎纸片的自动拼接复原的数学模型问题

摘要

本文根据碎纸片内的文字特征、图片像素特征特点提出了基于文字特征的文档碎纸片自动拼接复原模型。根据碎纸拼接模型提出了基于MATLAB[1]语言为核心的自动拼接算法，并用该算法的程序对碎纸机碎纸的实际例子进行了拼接实验。对这类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配。然而由于理论和技术的限制，让计算机具备类似人类那种识别碎片边缘的字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。但是利用现有的计算机技术，完全可以获取碎片文字所在行的几何特征信息，比如文字行的行高、文字行的间距等信息。拼接碎片时如利用这些信息进行拼接，其拼接效率无疑比单纯手工拼接要高。

针对问题一，由于碎纸片数量比较少且只有纵向切割，采用比较简单的二值模型进行碎纸配对。由于图像都具有三颜色RGB，扫描之后的碎纸片需要对其进行灰度处理得到一张灰度值图像，若定义原点之后，每一个像素点都具有X、Y坐标值，碎纸片的灰度值可构成一个二维矩阵。二维矩阵的每一个元素都代表着碎纸片的特征值，根据图片每一个灰度值的大小即可判断出碎纸图片边界特性。对于一个选定的纸片，将每一个待拼接碎纸片的二维矩阵的最左一列与其二维矩阵的最右一列进行差值比较，再求把所有的差值求和，生成一个相应的矩阵。将该矩阵的最小值来作为相似度矩阵的判断条件，以此便可求出该图片是否能够成功拼接。最后利用加权平均的融合方法进行图像无缝平滑，得到无缝拼接[2]图像。

针对问题二：根据附件3和附件4给出的碎片资料可以看出，碎片除了有纵向切割之外还有横向切割，这给单一的拼接算法带来了一定的困难。本文根据图片的质量与清晰度可以将问题简化，将附录所给出的碎纸片用简单的算法进行分组归类，使得拼接问题变得单一化，先使用第一问的模型进行纵向拼接成11行之后，再以第一问的模型进行横向拼接。只需要对问题一所提出的算法模型稍作优化处理，即可解决问题二。

针对问题三：问题三的模型是在前两个模型为基础的一个推广模型，该模型实现了现实问题的求解，比模型1、2应用范围更广阔。模型3主要应用模型2进行求解，加上人工干预，手动将一些匹配错误的数据调整好，是一种基于半自动的拼接碎纸复原方法。该方法也提高了碎纸拼接的效率，缩短了人工拼接的时

间，也是一种值得推广的模型。

关键字：碎纸复原；自动拼接；MATLAB；数学模型；灰度值

一、问题重述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接工作量巨大，很难在短时间内完成任务。随着计算机技术的发展，拼接工作的巨大工作量可以通过计算机完成，人们开始试图开发碎纸片的自动拼接技术，以提高拼接复原效率。

碎纸拼接的前提是计算机能够识别图片间的差异性与相关性。但计算机不能通过直接观察的方式获取图片的相关信息，需要通过软件编程来实现对图片信息的读取、分析及处理。利用MATLAB程序对图片数据进行读入，从读取的数据中，可以获得的信息是图片的明暗程度。但是，仅仅是数据明暗信息的读入后，计算机软件并不具备如人脑般的自主将信息分析处理的能力。因此，还需用软件编程的方式使计算机具有这方面的“智能”。通过软件控制的方式，使各个图片之间进行拼接对比，找出最合适的拼接结果，就是拼接复原后的图片。

问题一：对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法。并对于附件1、附件2中的中、英文各一页碎纸机纵切碎纸片进行拼接复原。

问题二：对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。

问题三：附件5给出的是一页英文印刷文字双面打印文件的碎片数据。尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。

二、基本假设与符号说明

2.1基本假设

1．图片质量有一定的保证，能够在肉眼观察下分辨；

2．破碎图片完整，没有缺少，丢失的现象；

3．图片在拼接的过程中噪声对拼接结果影响很小。

2.2 符号说明

符号

X(ejw)

F(u,v) 符号的含义 离散傅里叶变化值 离散余弦变化值

碎片灰度值

灰度值矩阵边缘列的差值

边缘列的差值和

碎片相似度矩阵评价值

碎纸片坐标

每一碎片的像素坐标

两幅待拼接的图像

待拼接碎片的灰度平均值

空白区域的像素值

分组配对相关度值

问题的决策变量

碎纸边界差异度

分别为碎片左端和右端的边缘列

在未说明之处均为自然数 Im Di Mi MIN (x,y) (u,v) fi，fj h1，h2 Iij n[i] Cxy Spq p，q i，j，x，y

三、问题分析

3.1问题重要性分析

在文物修复、司法物证鉴定等领域普遍存在着碎片拼接问题, 但目前碎片拼接工作几乎都是以手工方式完成的。当碎片的数量增大到一定程度时，如果仍然

依靠手工完成，不但耗费大量的人力、物力，而且还可能对物件造成一定的损坏。很多碎片拼接问题都可以归结为或近似为二维碎片的拼接问题，碎纸拼接是其中的典型问题。对二维碎片自动拼接问题的研究，不仅具有广阔的应用前景，而且具有很强的理论意义。

3.2 问题的思路分析

二维碎片自动拼接问题主要有两种解决方案：基于轮廓的拼接和基于文字特征及内容的拼接[3]。基于轮廓的拼接主要应用于手撕碎的纸片，有比较明显的边角轮廓，相对来说此类碎纸拼接相对比较容易。从理论上来说，前者类似的模型研究已经比较成熟了，而对于碎纸机粉碎的文档基本轮廓都是单向排列的直边，很难用轮廓类似法来拼接。因此本文是基于碎片文字内容的自动拼接技术模型研究。基于内容的二维碎片自动拼接问题, 可以由以下分析得出：

将图片的像素信息提取出来，其实就是将图片转化为一个关于纵向坐标与横向坐标变化而引起灰度变化的二元函数。因此，我们可以建立数学模型：

Hf(x,y) （1）

其中，H表示灰度值函数，x表示横向坐标，y表示纵向坐标。

问题一：对于附件1、附件2中的纵切碎纸片进行拼接复原，只需判别每列纸片的数据差异，即每片纵切碎片的边缘相似度差异。此问题中的碎纸片数量比较少，且粉碎程度低，只有纵向粉碎。对于两两碎片之间的相似度算法相对来说比较简单。因此，可以将经过碎纸机切割后的整张纸作为1行19列的数组，对两张碎纸片的灰度值矩阵的边缘部分进行相似度配对，就很容易得出相邻碎纸的拼接。在程序中进行拼接对比，得出拼接复原的图片，这样将在很大程度上减小计算机运算的复杂程度。

问题二：对于附件3，附件4里面碎纸片数量多，且横向，纵向都被切割，拼接难度就比较大了。从碎片的图片可以看出中文文档里面有很多碎片横向切割时正好边缘部分是空白没有文字的，若完全采用问题一的算法则无法实现附件3，附件4的碎纸拼接。因此需要寻找更优的算法或者采用半自动（即人工干预）的办法来达到碎纸片的拼接。就不仅要考虑到待拼接两片碎纸片fi和fj 灰度值矩阵的列与列间的数据差异，还需考虑到fi和fj灰度值矩阵的行与行之间的数据差异。因此，需要建立二维的数据组，即11行19列的数据组，在程序中进行拼接对比，得出拼接复原的图片。

问题三：附件5给出的是一页英文印刷文字双面打印文件的碎片数据。在对问题三建立模型的时候，将双面打印的英文文档转化成了两页不同的碎片进行各

自的拼接。其主体模型与上述问题的模型思想一样，优化的程序要求得到两幅不同的图像。从附录5可以看出，碎纸片的结合了问题一，问题二的难点，并且是双面文档，使得拼接难度更大，因此要在问题二算法的基础上，优化程序得到问题三的算法。

四、模型的建立与求解

4.1问题一的模型构建

4.1.1 前期模型理论分析

碎纸片拼接复原实质上就是图像的相似拼接。在图像拼接之前必然要对图像做预处理，使得处理过的图像之间具有相似的特征性，然后寻找一个相似评价标准来衡量两个图片是否能够配对以及拼接之后的效果如何。对于图像处理实际上有很多种方法，比如对图像做灰度处理、进行二值处理、进行变换域处理等等。下面对于碎片特征值的求解就基于变换域的方法与提取图像灰度值的方法进行比较。

对碎片特征值的求解提出的基于变换域[3]的方法，利用傅立叶变换的性质得到图像的变换参数。图像经过离散傅里叶变化与离散余弦变化均可得到碎片的特征点，通过对特征点相似度矩阵的比较也可得到碎纸图片的拼接。

离散傅里叶变换DFT公式

X(e)X(z)|zejj

nx(n)ejn4... n(1,2,3,N ,

（2）

离散余弦变换DCT公式

1(2i1)u(2j1)vF(u,v)C(u)C(v)[f(i,j)coscos] 41616i0j0

（3）

由离散傅里叶变换与离散余弦变换对图像进行特征值提取得到的结果见附录表格1所示（仅提取了8行7列进行比较），

表1 特征值提取数据表

由表1可知对于简单的图片拼接采用图片的灰度值更简单，更能看出碎纸片的特征性。而其他两种方法多用在图像融合与复杂图像拼接上面，又由于离散傅立叶变换的特点，它具有只能检测两幅具有大小的图像局限性，对于任意尺寸的图像会导致拼接失败，而离散余弦变化太过复杂，因此我们直接采用碎纸图片灰度值作为图片拼接的基础。

4.1.2 模型1的建立

简单地利用MATLAB软件提取每一个碎片的灰度值，构成一组矩阵。根据边缘灰度值特点，先利用算法找出碎片中起始位置的的一个碎纸片fi，作为拼接的起点。接着再利用fi的灰度值矩阵的最右一列与其余待拼接纸片fj的灰度值矩阵最左一列求差，得到每一对对应像素点的差，将得到的该列矩阵的元素所有差累加求和得到一个差值和Di。取所有待拼接纸片中Di的最小值，此片碎纸片即为与

fi 碎片相匹配的碎片fj。第二步，以已经拼接好的图片的最右边纸片为基础，用上面步骤选择与之最匹配纸片。依次类推，便可得到所有碎片的相邻碎片，再利用函数将矩阵拼接得到完整的拼接图。

将上述阐述的理论问题进行模型分析，可以将碎纸拼接问题转化为婚配问题

[4]。我们可以以碎纸片之间的灰度值的差异性为权建立一幅权有向完全图，由碎纸片的边缘特征可直接得出边界的灰度值均为255，边界差异度为Spq=0，并且规定Cpq1。根据图矩阵模型，我们用二值规划来建立所给的问题模型。引入变量二值变量Cxy，若碎片fi的右边界与碎片fj的左边界匹配，记Cxy1，否则记Cxy0，即：

1,碎片fi的右边界与碎片fj的左边界匹配Cxy，

0,碎片fi的右边界与碎片fj的左边界不匹配

（4）

其中，Cxy为问题的决策变量。

目标函数：

要求对附件的N张碎纸片进行配对拼接，转化为碎纸片灰度值矩阵边缘列的差值和的最小值。则目标函数为：

MINCxySxy

x0y0NN

约束条件： （5）

根据问题的要求提出以下约束条件：

（1） 规定Cpq=1；

（2） 对于一份完整的文档来说，左端的碎片左边界和右端碎片的右边界不可能

与其

它碎片之间进行配对拼接，也就是说对于左端碎片的左边界

Cxqyq0 (xp,x1,2,3, ..

（6）

对于右端碎片的右边界

Cpyxp0 (yq,y1,2,3, ..

（7）

除了左右两端边界之外的碎纸片必有碎纸片与之进行左右配对拼接，（3）对于剩余的碎纸片x，有：

（8） Cy1nxy1

对于其余的碎纸片y，有：

C

x1nxy1

（9）

（3） 碎纸片本身与本身不能进行配对拼接，即对于pq,应有Cpq0； （4） 已经配对好的碎纸片，不能够在进行配对拼接。

综上所述：该问题的优化模型为：

MINCxySxy

x0y0NN

Cpq1

Cxyyq0,xp

Cxyxp0,yq

n （10）约束条件：Cxy1,yq y1

n

Cxy1,xpx1

C0,pqpq

Cxy0,1

（11）

对与上述构建的模型，需要结合具体的算法才能是模型得到应用。本文提出

一种基于MATLAB程序[5]的碎片拼接算法。根据模型1的约束条件得出算法的整体流程图如下图1所示：

图1 模型1的方框流程图

第一步：首先对碎纸图片求取灰度值

imgray(255imread(file))

（12）

说明：gray在MATLAB里面是一个灰度值函数，imread是图片读取函数 由公式（12）得到一个ij大小的矩阵如下所示：

000000...000000000256...00000025600...00[1**********]...00255000000...00im|ij 000...0025002560

[**************]...00.........00...............

0000000...00000000...000

（13）

其中，0代表该碎纸图片区域为白色，没有字；其他值代表该区域有灰度值，即有字迹的出现。在im矩阵中，最后一列或几列都为0时表示着该边缘有可能是最边缘的碎片，没有其他的碎片与之相接。

fi 矩阵的最右一列与 fj 矩阵的最左一列的差值

(i,k)-(B)i, 14. .. i(1,2,3,N MiA

（14）

DMi

i0n

（15） 以该差值为标准，即相似度矩阵来判断fj，fj是否具有相似边缘，依次来判断fj，fj是否为相邻碎纸片，最后能够排序出完全匹配的碎片顺序。

4.1.3 模型求解

通过MATLAB比较碎纸片的的灰度值信息，确定最左边的破碎图片（可利用一边灰度值全为0来判断）。当最左边的碎纸片确定后，将此碎纸片的灰度值矩阵的右边界与剩余碎纸片的灰度值矩阵的左边界进行配对。利用公式（14），（15），我们先将选定破碎图片的右边界与其余各个破碎图片的左边界进行像素作差并取绝对值，最后对其进行求和运算。将求得的值进行比较，得到最小值，则其对应的破碎图片为选定图片的拼接图片。将其作为新的选定图片，重复上述步骤，

直到完成全部拼接为止。

以此循环得到一个以D值为元素的矩阵，求最小值来寻相似边缘的碎片。

MINmin(D1,D2,D3,...Dn)

（16）

根据上述算法用MATLAB程序求得的结果如下表所示：

表2 附件一配对拼接结果表

说明：该表中9代表附录一中编号为009的碎纸片，该顺序为依次相邻的两

片碎纸的顺序，最后拼接复原图结果见附录中图4所示。

表3 附件二配对拼接结果表

说明：该表中4代表附录一中编号为004的碎纸片，该顺序为依次相邻的两

片碎纸的顺序，最后拼接复原图结果见附录中图5所示。

4.2 问题二模型的构建

4.2.1 模型2的建立

根据附件3和附件4的碎片可以知道，碎片在纵向切割的基础上加上了横向

切割。该问题的模型则可以根据模型1的基础上进行优化，得到模型2的建立。模型2的主体思想是先将碎纸图片看成一个二维的函数

,y) fF(x

（17）

x，y表示碎片在横向和纵向上的坐标，因此将209张碎片分成了一个1119

的矩阵形式。

对于每一个碎纸片而言可以根据问题一的思想，将每一个碎片提取出图片的

灰度值，得到一个二维的矩阵，因此也可将每一个像素点看成一个二维的函数

GA(u,v)

（18）

u，v表示碎纸片像素的灰度值。

模型的主要思路：由于最左边没有文字，则它的灰度值为0，首先根据图像

边缘效应的特征值可确定每一行的第一张图片，然后再使用模型1的思想求取fi的最右一列的灰度值与fj的最左一列作差，每行元素做差之后再求各差值的总和。由最小函数得到一个相似度最好的碎纸片，即有可能是当前碎纸片的相邻纸片。以此循环得到每一行的拼接结果。在此基础上将每一行看做一个碎纸片，重复模型1的算法，得到一张完整的拼接图片。方框流程图如下图4所示：

图2 模型2的方框流程图

4.2.2 改进模型的建立

总体来说，第二问模型与第一问模型相似，但是问题二模型需考虑到破碎纸

片纵向坐标与横向坐标，相较于第一问，模型更加复杂一些。改进模型的建立是以模型2为基础的，实质上是对模型2的优化算法。因此，改进模型的基础理论部分与模型2相同。同样将209个碎纸片看成一个1119的阵列，将每一个图片的像素点看成是一个二维的矩阵。

fxyf(xi,yi)

i1j11911

（19）

其中f(xi,yj)为破碎纸片的关于像素分布的二元函数，fxy为拼接完成后的

总像素分布函数。上述公式表示，对各破碎纸片进行数据分析，先进行纵向的拼接，然后进行横向拼接，最终得到拼接复原图。

关于纵向拼接的算法原理，主要采用分组分类的原则。根据图片的边缘理论，

一个文档的边缘都是空白的，由此根据边缘的像素点的值，利用MATLAB程序简单的将左右两边缘的碎纸片找出。对于每一行的分组主要根据第一个碎片和最后一张碎片的空白行所在位置，以此为标准，寻找其它碎纸片的空白的位置与标准碎片进行比对，相似度最高的19张碎片作为一行。

以整个图片的左边一列为标准碎片，假设某行空白的像素值为0。

Ii10 i0,1,2,3... 1

IijI1i0 （20） 若 j0,1,2,... ,

（21）

] 1则 n[i]n[i

（22）

在所有的碎片都查找过之后，排序找出最大的19个数据，然后进行分组处

理。

改进模型的基本思想：改进模型与模型2不同之处在于，改进模型先将相似

性209张碎纸片进行分组处理，采用模型2的部分算法，将整张图片的最左列求取出来，再根据每张图片的进行分组，对每一个分好组的图片做一个评分标记，表示该张图片在分组过程中是否正确。待每一张图片分好组之后，将每组的图片完全隔离开来，直接两次调用问题一的模型则可得到完整的图片拼接。算法流程框图如下图5所示：

图3 改进模型的方框流程图

4.2.4 模型求解

对于碎纸机既纵切又横切的情形，就需要对其中某一破碎纸片与其他破碎纸

片的横向坐标与纵向坐标都进行探讨与分析。为了选定一片合适的纸片作为拼接的起始点，首先需要对所有破碎纸片进行数据分析，选择原纸片的某一顶角作为拼接的起始点。首先进行纵向的拼接，即将破碎纸片拼接成纵向的长条状；然后，对其进行横向的拼接，即将第一步所得的长条状纸片再次进行拼接，最后便可得到拼接复原图形。

对于上述模型2与改进模型的比较，模型2的拼接结果有一定的误差，且拼

接速度相对较慢，算法复杂。以下是模型2的拼接结果：

表4 附件三碎纸拼接配对表

说明：该表为一个1119的阵列表，071代表编号为071的碎纸片，该

表格顺序与正常图片顺序以致，最后拼接复原图结果见附录中图6所示。

表5 附件四碎纸拼接配对表

说明：该表为一个1119的阵列表，071代表编号为071的碎纸片，该

表格顺序与正常图片顺序一致，最后拼接复原图结果见附录中图7所示。

4.3 问题三的模型建立

4.3.1模型3的建立

由附件五可以看出，碎纸片除了横切和纵切之外，还分了a,b两页。附件三

的材料才是符合实际情况的，文档打印一般都是双面打印。因此问题三的模型实际上就是模型2的推广应用。在问题三中双面拼接，这是我们要考虑的问题，实际情况下扫描成图片的碎纸是分不清正反面的。因此核心问题就是，找出a,b两面的碎纸片对应拼接，但是不能让a,b两面的纸片混拼。

模型主要思想：首先，利用模型2的算法将附录三的所有碎片分好组，再调

用模型1的算法将所有碎片纵向拼接起来，得到一系列横向切割的碎纸片。将这

些碎纸片采用模型2的算法横向拼接，拼接之后发现a页的末尾一列与b页开始一列合在了一起，因此就需要人工干预将合在一起的a,b两页手工分开。

4.3.2 模型3求解

根据上述模型思想，利用MATLAB算法得到的拼接配对结果如下所示：

表6 附件五a页碎纸拼接配对表

说明：由于很多重配对的碎纸片和混拼的结果，所以省略了碎纸片的标号a

与b，直接用数据表示结果。

表7 附件五b页碎纸拼接配对表

说明：由于很多重配对的碎纸片和混拼的结果，所以省略了碎纸片的标号a

与b，直接用数据表示结果。

该模型的建立与求解的结果与预期值不一样，说明该算法程序对附件五的碎

片拼接不适用。由于双面碎纸片要比单面的复杂多，使得a，b两面的碎纸面混在了一起，在拼接过程中出现了错误的配对。

由于时间有限，对于模型3的求解算法只能优化到这个程度，若需要将a，

b两页图片完美的配对成功，还需要寻找另一个相似度判断准则，使得程序能够同时以两个准则判断fj，fj两个碎纸片是否能够配对，且同时将a，b两面的组图分开，以致于配对的时候不会将a，b两面的碎片混拼。

五、无缝平滑拼接

对配对好的碎片还要将其拼接起来才能供给人们读取，图像拼接要达到无缝

平滑拼接效果才能达到人们的视觉效果。为了拼接后的图像具有视觉一致性而且没有明显的接缝，采用加权平均的融合方法进行图像无缝平滑拼接。假设f1，f2是两幅待拼接的图像，首先计算f1和f2灰度平均值h1和h2，求得比值d，对f2

进行修正，使得f2的亮度与f1统一，即

f1(x,y)h1(x,y)h1 f(x,y)df（x,y）=f(x,y)222h2

（23）

将图像h1和h2在空间叠加，则图像无缝平滑后的图像像素f可表示为

(x,y)f1f1(x,y)d1f1(x,y)d2f(x,y) (x,y)(f1f2) f(x,y)(x,y)f22

（24）

式子中：d1，d2表示权重值，一般与重叠区域的宽度有关，且

d1+d2=1,0

实现了在重叠区域中由f1到f2的平滑过渡。

六、模型优化与评价

本文从多方面考虑，对所给问题建立了多个模型。从问题一的解答到问题三的解答，就是从初步模型到最终模型的优化。本文建立的数学模型有很多优越之处，但还是有需要改进的地方。

6.1 本文模型特点

本文模型相对而言较为通俗易懂，但同时又贴近题意。模型都从较为有特征的碎纸图片入手，如边界上的碎纸图片。从中找到特殊点，从而推广至其他碎纸图片。通过对碎纸图片边界的比较，将相关度最大的图片视为一组并进行图片的拼接。最终，得到准确的拼接复原图片。在回答问题一和问题二时，不仅给出了拼接后的图片，还给出了碎纸图片的正确排列序号，使结果更加显而易见。

在对于问题二，问题三模型建立的求解中，本文采用先分组后拼接的方法。这对附录3、附录4、附录5中大量碎纸图片来说减少了很多工作量，使得模型的算法优化的很多，且可以直接调用模型一的算法程序。使得在模型求解过程中更快速，算法程序更简洁。

在模型的整个求解过程中，除了需要对碎纸图片按一定的规则命名之外，其他都是通过调用MATLAB的M.file文件，实现所有碎纸片的自动拼接效果。这是本模型的一个最大优点之处，拼接过程当中无人工干预增加了拼接的效率，且通过在本附录中给出的拼接结果数据可知，利用本文前两个模型的拼接结果几乎没有误差，达到或接近100%的拼接率。

6.2 本文模型不足

1) 对于问题二，数据量较大，因此导致所编程序运行时间较长，不能

在短时间内取得拼接复原图像。如果对程序作出优化，运行时间应当会有一定的缩短，但在此次时间有限，留在赛后可自行研究是否有更好的算法或者优化本算法程序。

2) 本文没有详细考虑到多组边缘像素的相关度比较，虽然在本题中边

缘像素的相关度较大，我组的方法可以满足要求并得到良好的拼接效果，但对于其他情况可能导致拼接结果出现一些误差。

3) 由于附录所给的碎纸图片噪声小，图片质量高。使得拼接过程中外

界因素影响小，这对本次建模过程中减少了很大的负担。但是实际情况当中并不是这样，对扫描上来的碎纸图片，有很差的边缘效应并且图片质量不高，简单的算法对碎纸拼接可能效果不是很好，因此算法有待进一步优化提高。

参考文献

[1] 薛定宇，陈阳泉，高等应用数学问题的MATLAB求解(第2版)[M]，北

京：清华大学出版社，2008。

[2] 王娇颖，陈卫东，一种基于特征不变描述的图像无缝拼接算法，应用光

学，第32卷第1期：59~64页，2011年1月。

[3] 陈古春，苏波，基于图片DCT域共生矩阵的图像拼接盲检测，上海交通

大学学报，第45卷第10期：1547~1551页，2011年10月。

[4] 姜启源，谢金星，叶俊，数学模型(第3版)[M]，北京： 高等教育出版

社，2003。

[5] 刘同娟，郭键，刘军.MATLAB建模、仿真及应用，北京，中国电力出

版社。

附录：

1． 附件一求解结果

表9 附件一碎片拼接配对表

图4 附件一碎片拼接复原结果图

2. 附件二求解结果

表10 附件二碎片拼接配对表

图5 附件二碎片拼接复原结果图

3．附件三求解结果

表11 附件三碎纸拼接配对表

图6 附件三拼接复原结果图

4．附件四求解结果

表12 附件四碎纸拼接配对表

图7 附件4拼接结果图

5．模型1相关代码：

说明：该代码在windows操作系统MATLAB7.1的语言环境下编写运行

for i=1

for j=1:19

file = ['data\pic_',int2str(i),'_',int2str(j),'.bmp'];

im{i,j} = double(255-imread(file));

end

end

x=size(im{1,j},1);

y=size(im{1,j},2);

for i=1:19

Z=im{1,i}

for j=1:(x-1)

if Z(j,1)~=Z(j+1,1)

break;

end

if j==x-1

xu(1)=i;

end

end

end

for n=1:18

for j=1:19

MIN(j)=0;

end

min=1000000000;

C=0;

A=im{1,xu(n)};

for j=1:19

if j~=xu(1)

B=im{1,j};

M=abs(A(:,y)-B(:,1));

for p=1:x

MIN(j)=M(p)+MIN(j);

end

if min>MIN(j)

min=MIN(j);

end

end

end

for j=1:19

if j~=xu(1)

if MIN(j)==min

h=n+1;

xu(h)=j

end

end

end

end

D=[im{1,xu(1)},im{1,xu(2)},im{1,xu(3)},im{1,xu(4)},im{1,xu(5)},im{1,xu(6)},im{1,xu(7)},im{1,xu(8)},im{1,xu(9)},im{1,xu(10)},im{1,xu(11)},

im{1,xu(12)},im{1,xu(13)},im{1,xu(14)},im{1,xu(15)},im{1,xu(16)},im{1,xu(17)},im{1,xu(18)},im{1,xu(19)}];

imshow(D)

7.模型2相关代码：

for i=1:11

for j=1:19

file = ['f4\pic_',int2str(i),'_',' (',int2str(j),')','.bmp'];

im{i,j} = double(255-imread(file));

end

end

x=size(im{i,j},1);

y=size(im{i,j},2);

q=1;

for i=1:11

for j=1:19

Z=im{i,j};

for p=1:(x-1)

if

(Z(p,7)~=Z(p+1,7))||(Z(p,6)~=Z(p+1,6))||(Z(p,5)~=Z(p+1,5))||(Z(p,4)~=Z(p+1,4))||(Z(p,3)~=Z(p+1,3))||(Z(p,2)~=Z(p+1,2))||(Z(p,1)~=Z(p+1,1))

break;

end

if p==x-1

xy{q,1}=[i,j];

if(q

q=q+1;

end

end

end

end

end

q=1;

for i=1:11

for j=1:19

Z=im{i,j};

for p=1:(x-1)

if

(Z(p,y)~=Z(p+1,y))||(Z(p,y-1)~=Z(p+1,y-1))||(Z(p,y-2)~=Z(p+1,y-2))||(Z(p,y-3)~=Z(p+1,y-3))||(Z(p,y-4)~=Z(p+1,y-4))

break;

end

if p==x-1

xy{q,19}=[i,j];

%if(q

q=q+1;

%end

end

end

end

end

k(:,:,:)=0;

for q=1:11

C=xy{q,1};

i=C(1);

j=C(2);

A=im{i,j};

for ii=1:x

for jj=1:y

if(A(ii,jj)~=0) break; end

if(jj==y) k(q,1,ii)=1;

end

end

end

end

kk(:,:,:)=0;

for i=1:11

for j=1:19

B=im{i,j};

for ii=1:x

for jj=1:y

if(B(ii,jj)~=0) break; end

if(jj==y) kk(i,j,ii)=1;

end

end

end

end

end

k1(:,1:19,:)=0;

for q=1:11

C=xy{q,19};

i=C(1);

j=C(2);

A=im{i,j};

for ii=1:x

for jj=y:-1:1

if(A(ii,jj)~=0) break; end

if(jj==1) k1(q,19,ii)=1;

end

end

end

end

for q=1:11

for qq=1:11

for i=1:11

for j=1:19

m=0;

for ii=1:x

if(k(q,1,ii)==kk(i,j,ii))

if(k1(q,19,ii)==kk(i,j,ii))

m=m+1;

t(i,j)=m;

end

end

end

end

end

end

for tt=1:19

max=0;

for i=1:11

for j=1:19

if(max

max=t(i,j);

s=[i j];

end

end

end

G1(q,tt)=s(1,1)

G2(q,tt)=s(1,2)

t(G1(q,tt),G2(q,tt))=0;

end

end

for q=1:11

C=xy{q,1};

i=C(1);

j=C(2);

AA=im{i,j};

F1(q,1)=i;

F2(q,1)=j;

for n=1:18

for tt=1:19

MIN(q,tt)=0;

end

min=10000000;

for tt=1:19

if ([G1(q,tt) G2(q,tt)]~=xy{1,1})%&([G1(q,tt) G2(q,tt)]~=xy{2,1})&([G1(q,tt)

G2(q,tt)]~=xy{3,1})&([G1(q,tt) G2(q,tt)]~=xy{4,1})%&([G1(q,tt) G2(q,tt)]~=xy{5,1})&([G1(q,tt) G2(q,tt)]~=xy{6,1})&([G1(q,tt) G2(q,tt)]~=xy{7,1})&([G1(q,tt) G2(q,tt)]~=xy{8,1})&([G1(q,tt) G2(q,tt)]~=xy{9,1})&([G1(q,tt) G2(q,tt)]~=xy{10,1})&([G1(q,tt) G2(q,tt)]~=xy{11,1}) BB=im{G1(q,tt),G2(q,tt)};

MM=abs(AA(:,y-1)-BB(:,1));

for pp=1:x

MIN(q,tt)=MIN(q,tt)+MM(pp);

end

if min>MIN(q,tt)

min=MIN(q,tt);

end

end

end

for tt=1:19

if MIN(q,tt)==min

h=n+1;

F1(q,h)=G1(q,tt);

F2(q,h)=G2(q,tt);

end

end

AA=im{F1(q,h),F2(q,h)};

F1=textread('.txt');F2=textread('.txt');

end

set (gca,'position',[0,0,1.1,1.1] );

DD{q}=[im{F1(q,1),F2(q,1)},im{F1(q,2),F2(q,2)},im{F1(q,3),F2(q,3)},im{F1(q,4),F2(q,4)},im{F1(q,5),F2(q,5)},im{F1(q,6),F2(q,6)},im{F1(q,7),F2(q,7)},im{F1(q,8),F2(q,8)},im{F1(q,9),F2(q,

9)},im{F1(q,10),F2(q,10)},im{F1(q,11),F2(q,11)},im{F1(q,12),F2(q,12)},im{F1(q,13),F2(q,13)},im{F1(q,14),F2(q,14)},im{F1(q,15),F2(q,15)},im{F1(q,16),F2(q,16)},im{F1(q,17),F2(q,17)},im{F1(q,18),F2(q,18)},im{F1(q,19),F2(q,19)}];

DDD=[DD{1};DD{2};DD{3};DD{4};DD{5};DD{6};DD{7};DD{8};DD{9};DD{10};DD{11}]; imshow(DDD)

end