论文(修改)

承 诺 书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 辽宁工程技术大学 参赛队员 (打印并签名) ：1. 张良 2. 孙策 3. 杜旭 指导教师或指导教师组负责人 (打印并签名)： 董春胜

（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以

上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取

消评奖资格。）

日期： 2013年 9 月 15日 赛区评阅编号（由赛区组委会评阅前进行编号）：

2013高教社杯全国大学生数学建模竞赛

编 号 专 用 页

评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

基于边缘“距离和最小”的纸片拼接

【摘 要】把纸片输入matlab中将图像转化成灰度值矩阵，分别取矩阵的边缘元素所构成的边缘向量，根据边缘向量的相似程度，化为距离上的0和1，即相同记为0，不同则为1。用“距离和最小”的方法拼接出原图像。 【关键词】：mtlab 矩阵 距离和最小 灰度值

1、问题重述

1.1. 背景资料与条件

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。因此,研究碎片的自动拼接系统,既具有极大的理论意义,又具有广泛的应用背景。

二维碎片图像拼接时通过对碎片图像模型分析、变换、和特征的提取来实现对碎片的识别、相似性度量以及拼合。包括以下3个步骤: (l)碎片图像的预处理,包括碎片的数字化,平滑,轮廓提取等； (2)碎片图像的匹配,应用适当的匹配算法找出碎片间的相互匹配关系； (3)碎片图像的拼接,将相匹配的碎片拼接完整。

步骤2是算法实现的核心,直接关系到图像拼接算法的成功率和运行速度。 碎纸自动拼接技术是模式识别领域中的一个较新但很典型的应用，涉及数字图像处理，机器学习等多个学科，充分体现了当下多学科相互融合的学科特点，这也正说明了碎纸自动拼接本身具有一定的难度。

1.2. 需要解决的问题 1. 对于来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片

1

拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如需人工干预，写出干预方式及干预的时间节点。

2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如需人工干预，请写出干预方式及干预的时间节点。

3. 从现实情形出发，还有双面打印文件的碎纸片拼接复原问题需要解决。 附件5给出的是一页英文印刷文字双面打印文件的碎片数据。设计相应的碎纸片

拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。

2、模型的假设

1、纸片是规则的矩形

2、同一个附件中纸片的大小都是统一的 3、同一个附件中的语言都是统一的 4、同一个附件中的切割方式是相同的

5、所有数据均是准确的，根据像素能够近似地描绘出图形

3、模型建立与求解

一、第一问解答

以附件1所给的19张中文纵切纸片为例说明思路方法，附件2中的19张英文纸片拼接方法同理。

具体建模求解过程如下： 第一步：由matlab里的imread命令把19张中文纵切的纸片转换成198072矩阵Ai(i0,1,,18)，其中矩阵中的元素0~255是把图形灰度量化后的值，共

ai11ai12，编写程,18)中的第1列构成的向量Ai1ai11980256级灰度值【1】。

第二步：提取Ai(i0,1,序令第i个矩阵1m元素ai1m255(m1,2,若,1980)的作为整张纸的排头页；

2

Ai(i0,1,,18)中的第72列构成的向量Ai72ai721ai722中的72m元素ai721980ai72m255(m1,2,,1980)则表示此页是排尾页，找出排尾页为006图片。

第三步：由第二步得到的006纸片对应的矩阵A6的第1列构成的向量

a611aA61612，其中的元素0a61m255(m1,2,a611980,1980)，同其他17页纸片构

成的矩阵的第72列组成的向量Aj72aj721aj722（其中j6）中的元素aj7219800aj72m255(m1,2,,1980)，进行距离比较。

其中设计距离算法如下：

Step1：相应位置两元素间的距离b6lm1980m10(a61maj72m0)； 其它1Step2：求距离和B6ljb6lm，表示006纸片和Aj对应的纸片总的距离； Step3：取距离和最小的B6lj所对应的纸片j同006的左边相连；

Step4：以此方法，由排尾页006从右往左推到排头，期间结合第二步得出

的排头页008按照以上思路从右往左推到排尾页，提高准确率，最后就拼出了完整页。

最后把附件1、附件2拼接出的表格分别如下表1、表2：

表1

复0员0后8 序号 014 012 015 003 010 002 016 001 004 005 009 013 018 0 1 1 007 017 000 006 表2

3

复员后序号 0 0 3 0 0 6 0 0 2 0 0 7 0 1 5 0 1 8 0 1 1 0 0 0 0 0 5 0 0 1 0 0 9 0 1 3 0 1 0 0 0 8 0 1 2 0 1 4 0 1 7 0 1 6 0 0 4

二、第二问求解

基于第一问左右比较的模型加以改进，设计出比较上下左右四个方向的模型来推导其中一幅图该和那几张图如何拼接。

4、模型评价

近几十年图像复原一直是重要的研究课题，查找大量资料发现图像拼接领域很多都是分为：输入图像和参考图像、预处理、图像配准、融合，最后得出目标图像或全景图【2】。很多都是根据图像有重叠部分进行模板匹配等方法进行的研究，而本题文字间没有重叠，若生搬硬套这些方法是行不通的。所以，本文大胆提出把图像化成矩阵，再提取矩阵有用信息按照所设计出的“距离和最小”模型进行拼接，实验证明想法可行。

5、模型改进

对于这种“距离和最小”拼接碎纸片的方法，基于简单的规则图片有着很

好的效果，但对于较复杂和不规则的图片，其边缘向量的距离和较难定义和计算，此时应通过SIFT特征算法提取特征矩阵。尺度不变特征变换 （ScaleInvariant Feature

Transform，SIFT）算法【3】是 1999 年 Lowe提出的一种稳健的算法，由于它引入尺度，使

4

得图像在有较大缩放的情况下，仍能稳定取特征点；由于它在特征描述符计算时考虑了特征点梯度主方向， 因此特征描述符具有较强的旋转不变性， 这为后续正确匹配提供了良好的条件。在匹配点中寻找包围面积最大的 4 对匹配点对，由这四对点计算变换矩阵最终得到拼接图像。

6、参考文献

[1]何东健. 数字图像处理（第二版）. 西安电子科技大学出版社, 2009.

[2]杨占龙. 基于特征点的图像配准与拼接技术研究[博士论文]. 西安电子科技大学, 2008, 3-4.

3LOWE D G． Object recognition from local scale-invariant features

[J]． International Conference on Computer Vision. 1999-9：1150-1157.

7、附录

1.以006图片为例，找它的左边相连的图片程序。（其它图片处理方法照此例一个个算）

clc

A6=imread('006.bmp')； %读入006图片 A0=imread('000.bmp'); %读入000图片 a6=size(A6); %求矩阵大小 m=a6(1); %取矩阵行数 A61=A6(:,1) %取A6第1列 A072=A0(:,72) %取A0第72列 bm=zeros(m,1); for i=1:m

if A61(i)==0&&A072(i)==0 bm(i)=0; else bm(i)=1; end end

s=sum(bm) %求距离和

程序运行结果显示：s =

1799

再同其它16个比较就会发现006与000纸片距离最小，所以000在006的右边，依此可以找到整张纸正确的顺序，期间不许人工干预，就是重复的工作。附件2中的英文纸片也是按此方法实现的。

5

2.附件1拼接成完整图片程序。（其它图片处理好后按此方法拼接成完整的）

clc

I1=imread('008.bmp'); I2=imread('014.bmp'); I3=imread('012.bmp'); I4=imread('015.bmp'); I5=imread('003.bmp'); I6=imread('010.bmp'); I7=imread('002.bmp'); I8=imread('016.bmp'); I9=imread('001.bmp'); I10=imread('004.bmp'); I11=imread('005.bmp'); I12=imread('009.bmp'); I13=imread('013.bmp'); I14=imread('018.bmp'); I15=imread('011.bmp'); I16=imread('007.bmp'); I17=imread('017.bmp'); I18=imread('000.bmp'); I19=imread('006.bmp');

I=[I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I19]; imshow(I)

3.附件1拼接成功图样。

6

4.附件2复原图片。

7

5.

8