2013年数学建模(B题)碎纸片的拼接复原模型
- 格式：doc
- 大小：3.10 MB
- 文档页数：20
下载文档原格式
合集下载
2013全国数学建模竞赛B题优秀论文
基于最小二乘法的碎纸片拼接复原数学模型摘要首先对图片进行灰度化处理,然后转化为0-1二值矩阵，利用矩阵行（列）偏差函数，建立了基于最小二乘法的碎纸片拼接数学模型，并利用模型对图片进行拼接复原。
针对问题一，当两个数字矩阵列向量的偏差函数最小时，对应两张图片可以左右拼接。
经计算，得到附件1的拼接结果为：08,14,12,15,03,10,02,16,01,04,05,09,13,18,11,07,17,00,06。
附件2的拼接结果为:03,06,02,07,15,18,11,00,05,01 ,09,13, 10,08,12,14,17,16,04。
针对问题二，首先根据每张纸片内容的不同特性，对图片进行聚类分析，将209张图片分为11类；对于每一类图片，按照问题一的模型与算法，即列偏差函数最小则进行左右拼接,对于没有拼接到组合里的碎纸片进行人工干预，我们得到了11组碎纸片拼接而成的图片；对于拼接好的11张图片，按照问题一的模型与算法，即行偏差函数最小则进行上下拼接,对于没有拼接到组合里的碎纸片进行人工干预。
我们最终经计算，附件3的拼接结果见表9，附件4的拼接结果见表10。
针对问题三，由于图片区分正反两面，在问题二的基础上，增加图片从下到上的裁截距信息，然后进行两次聚类，从而将所有图片进行分类，利用计算机自动拼接与人工干预相结合，对所有图片进行拼接复原。
经计算，附件5的拼接结果见表14和表15该模型的优点是将图片分为具体的几类，大大的减少了工作量，缺点是针对英文文章的误差比较大。
关键字：灰度处理，图像二值化，最小二乘法，聚类分析，碎纸片拼接一、问题重述碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情报获取以及故障分析等领域都有着广泛的应用。
近年来，随着德国“斯塔西”文件的恢复工程的公布，碎纸文件复原技术的研究引起了人们的广泛关注。
传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。
特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。
碎纸片的拼接复原2013全国数学建模竞赛——碎纸片拼接复原
碎纸片的拼接复原 2013全国数学建模竞赛——碎纸片拼接复原导读：就爱阅读网友为您分享以下“2013全国数学建模竞赛——碎纸片拼接复原”的资讯，希望对您有所帮助，感谢您对的支持!2013高教社杯全国大学生数学建模竞赛重庆工商大学姜木北小组作品编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）碎纸片的拼接复原摘要目前，“碎片拼接复原”技术在司法物证复原、历史文物修复及社会生活各项领域扮演着重要角色，对于碎片数量特别巨大而人工又难以在短时间内完成碎片拼接时，要找到一种高效快捷的自动拼接方法已变得尤为重要。
本文针对只有中英文的碎片拼接问题，综合分析了从单一的纵切到纵横切以及纵横切双面碎片这三个不同的情况，提出了碎片拼接复原的解决方案.在问题一中，对于仅有“纵切”且数量相对较少的碎纸片，我们基于边缘去噪和采用构建碎纸图片的左右边缘二值矩阵提取相似度分析的方法，再通过两张图片左右相似度匹配排序，得到附件1和附件2中的碎纸排序（见表2和表3），并运用Matlab的图像处理工具箱，按排列顺序导入碎纸片得到相应拼接结果（见附录附件一）.在问题二中，由于碎纸片数量相对较多，同时存在横切和纵切的情况，在问题一的基础上增加了碎纸片的上下边缘相似度匹配。
在进行人工干预，找到第一张起始碎纸片作为匹配起点后，我们基于索贝尔算子的原理，对碎纸片灰度值进行边缘相似度的旋转检测和比较匹配，最后进行二叉树搜索排序（见表4和表5）。
对附件3和4的碎纸图片拼接出的结果详见附录中的附件二.在问题三中，由于碎纸片是两面的并且碎纸片数量更多，若采用第二问的求解方案则加大了求解难度同时也存在较大误差。
因此，我们基于蚁群算法（ACA）的SIFT特征点匹配原理来求解。
先提取碎纸图片特征点，然后基于蚁群算法的最优化快速比对匹配，最后基于ACA的搜索排序对碎纸片拼接。
2013年数学建模
碎纸片的拼接复原
摘要
碎纸片的拼接复原主要采集碎纸片边缘信息的挖掘，利用碎纸片边缘构造特征因子，利用特征因子来描述碎片边缘的行列特征，然后根据碎纸片边缘提供的信息进行调整，并对贪心算法进行改进，找到有效克服局部最优解的拼接算法。
问题1：首先，纸片采取的是纵向切割，利用matlab软件对纸片左右边缘提取1980×2个像素点，直接利用边缘像素点的差异性来定义匹配度。
然后用改进贪心算法寻找最短路径，最后碎片复原时进行部分人工干预，成功复原附件1和附件2的碎纸片。
问题2：对附件3，4中的张碎片边缘提取180×72个像素点，对此，为了提高碎纸片的匹配精度，本文引入评估函数区别对待黑白区内的不同匹配，借助评估函数重新定义匹配度，使得较少的边缘信息将碎片分为19类，同时采用问题1与改进的贪心算法寻找捷径，将这一类的碎片复原，其他18类同理。
最后整理剩下的19类的碎片，采取好19类上下边缘的灰度矩阵和行距特征，利用以上的特征，引用人机交互拼接方法，成功复原附件3，附件4的碎纸片。
问题3：
关键词：特征因子，灰度矩阵，贪心算法，拼接，人工干预
问题的重述与分析。
2013年数学建模B题碎纸片的拼接复原
年
9 月 15 日
赛区评阅编号（由赛区组委会评阅前进行编号） ：
1
2013 高教社杯全国大学生数学建模竞赛
编 号 专 用 页
赛区评阅编号（由赛区组委会评阅前进行编号） ：
赛区评阅记录（可供赛区评阅时使用） ： 评 阅 人 评 分 备 注
全国统一编号（由赛区组委会送交全国前编号） ：
全国评阅编号（由全国组委会评阅前进行编号） ：
2
三.模型假设
1. 所有碎纸片的拼接都可以忽略边缘效应，即可无缝地融合在一起； 2. 对于仅纵切的两块待拼接的碎纸片，可用像素点灰度值矩阵的相似度大于 0.6 作为 判别标准； 3. 对既纵切又横切的碎纸片，拼接后原图形四周的像素点是 255； 4. 人工干预可以准确的选择出不确定的待拼接图形； 5. 对于既纵切又横切的两块待拼接的碎片，先进行行拼接，再进行列拼接； 6. 假设给定待拼接碎纸片边缘平滑。
二.问题分析
第一问中， 对于中、 英文的纵切单面文件， 可以选择矩阵相关性匹配算法， 在 MATLAB 中导入图形后，将图形中的变量转换为矩阵的形式，采用矩阵相似度比较法，提取待拼 接图形中第一列和最后一列像素点灰度值， 用 corr2 函数进行相似度比较， 然后根据相 关系数的大小来判断待拼接图形文字区域的相似程度，相关系数（0 表示毫不相关，-1 和 1 表示完全相关，靠近-1 或 1 表示相似程度较大） 。 由此得到待拼接图形的相应位置，从而实现文字的拼接。 第二问中，中、英文的纵横切单面文件拼接复原的处理问题，在上一问的基础上将 问题简化为 19 次行方向的碎片拼接，对一拼接的行再进行列方向上的拼接。依然使用 矩阵相关性算法，在 MATLAB 中导入图形后，将各个图形的变量转换为的相应的矩阵形 式，矩阵相似度比较，提取待拼接图形四周边缘像素点灰度值，用 corr2 函数进行相似 度比较， 然后根据相关系数的大小来判断带拼接图形文字区域的相似程度。 由于图形数 量多， 相关系数不能唯一确定一张拼接图形， 此时要进行人工干预， 筛选出合适的图形， 再对剩余的待拼接图进行矩阵相似度比较，得到行方向的图形。最后根据 MATLAB 软件 编写的程序和人工干预拼接处整张图形。 第三问中，对于中、英文的纵横切双面文件的拼接复原，在第二问的基础上需要比 较正反两面， 在比较的过程中其中一张有可能出现正反两面与另一张图像在算法中计算 出来的相关系数几乎差不多，此时可能要进行人工干预，选出那张是正面还是反面。
2013 数模国赛 B题 碎纸片的拼接复原
2013高教社杯全国大学生数学建模竞赛B题碎纸片的拼接复原首先分析问题：对于第一问分析如下对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
求matlab图像拼接程序clear;I=imread('xingshi32.bmp');if(isgray(I)==0)disp('请输入灰度图像,本程序用来处理128 *128的灰度图像!');elseif (size(I)~=[128,128])disp('图像的大小不合程序要求!');elseH.color=[1 1 1]; %设置白的画布figure(H);imshow(I);title('原图像');zeroImage=repmat(uint8(0),[128 128]);figure(H); %为分裂合并后显示的图设置画布meansImageHandle=imshow(zeroImage);title('块均值图像');%%%%%设置分裂后图像的大小由于本图采用了128像素的图blockSize=[128 64 32 16 8 4 2];%%设置一个S稀疏矩阵用于四叉树分解后存诸数据S=uint8(128);S(128,128)=0;threshold=input('请输入分裂的阈值(0--1):');%阈值threshold=round(255*threshold);M=128;dim=128;%%%%%%%%%%%%%%%%% 分裂主程序%%%%%%%%%%%while (dim>1)[M,N] = size(I);Sind = find(S == dim);numBlocks = length(Sind);if (numBlocks == 0)%已完成break;endrows = (0:dim-1)';cols = 0:M:(dim-1)*M;rows = rows(:,ones(1,dim));cols = cols(ones(dim,1),:);ind = rows + cols;ind = ind(:);tmp = repmat(Sind', length(ind), 1);ind = ind(:, ones(1,numBlocks));ind = ind + tmp;blockValues= I(ind);blockValues = reshape(blockValues, [dim dim numBlocks]);if(isempty(Sind))%已完成break;end[i,j]=find(S);set(meansImageHandle,'CData',ComputeMeans(I,S));maxValues=max(max(blockValues,[],1),[],2);minValues=min(min(blockValues,[],1),[],2);doSplit=(double(maxValues)-double(minValues))>threshold;dim=dim/2;Sind=Sind(doSplit);Sind=[Sind;Sind+dim;(Sind+M*dim);(Sind+(M+1)*dim)];S(Sind)=dim;end对于第二问于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
碎纸片的拼接复原问题.概要
2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原问题摘要破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。
本文针对已给图像先进行了图片灰度二值化处理得到碎纸片的像素矩阵，提取碎纸片的边缘像素矩阵，对边缘矩阵进行相似度分析，相似度的度量采用向量距离平方和最小化，在相似度度量中设置阈值、对相近相似度的候选纸片进行人工干预、对数据量较大的附件，采用文本特征，如页边距、行距进行筛选，降低计算量，提高计算精度。
使用Matlab软件编程实现了上述算法，在对附件的拼接中通过少量的人工干预，可实现纸片的完整拼接，效果较好。
关键词：相似度；文字特征；碎纸片拼接；Matlab；1 问题重述1.1 问题的描述设计一个碎纸片的自动拼接模型，以提高碎纸片的拼接复原效率。
1.2 问题的要求（1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
复原结果以图片形式及表格形式表达。
（2）对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
复原结果表达要求同上。
（3）从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。
附件5给出的是一页英文印刷文字双面打印文件的碎片数据。
请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
1.3 问题的分析对破碎文件这类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎纸片内的字迹断线或碎片内的文字内容是否匹配，然而由于理论和技术的限制，让计算机具备类似人那种识别破碎边缘地字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。
2013国赛 碎纸片的拼接复原数学建模B解题思路分析
2， 图片为文字，所以可以确认文字的形状，但大多为残字，故 可以补全剩余部分。 #根据残字，进行文字预算，找到字体可能是的字，补全字体，找图 片能补全的部分。 3， 图片文字都为从左到右书写，有固定的行。 #文字又从左到右书写，故可以对字的上下画线，从而将文字的拼接， 改为图形线性的匹配。 4，图片可能正反双面，也就是说可以双向确定但是，由于不知道什 么是正面，什么是反面，所以无法确定，故可以将其当做一副。 #广范围查询。 ￥还可以计算他的下一个或上一个字的位置。
பைடு நூலகம்
故可以对字的上下画线从而将文字的拼接4图片可能正反双面也就是说可以双向确定但是由于不知道什么是正面什么是反面所以无法确定故可以将其当做一副
残纸碎片平拼接
图片信息：
1， 图片边缘完整，语言不是普通话，故无法用语法辨别。 2， 图片为文字，所以可以确认文字的形状，但大多为残 字，故可以补全剩余部分。 3， 图片文字都为从左到右书写，有固定的行。 4，图片可能正反双面，也就是说可以双向确定但是，由 于不知道什么是正面，什么是反面，所以无法确定，故可 以将其当做一副。
(完整word版)2013年数学建模b题
精心整理碎纸片的拼接复原【摘要】：碎纸片拼接技术是数字图像处理领域的一个重要研究方向，把计算机视觉和程序识别应用于碎纸片的复原，在考古、司法、古生物学等方面具有广泛的应用，具有重要的现实意义。
本文主要结合各种实际应用背景，针对碎纸机绞碎的碎纸片，基于计算机辅助对碎纸片进行自动拼接复原研究。
针对问题1，依据图像预处理理论，通过matlab程序处理图像，将图像转化成适合于计算机处理的数字图像，进行灰度分析，提取灰度矩阵。
对于仅纵切的碎纸片，根据矩阵的行提取理论，将。
建中的任一列与矩阵值，序列号。
将程序进行循环操作，得到最终的碎片自动拼接结果。
、；分别作为新生成的矩阵、。
，将矩阵中的任一列分别与矩阵中每一列代入模型，所得p值对应的值即为横排序；将矩阵中的任一行分别于矩阵中的任一行代入模型，所得q值对应的值即为列排序。
循环进行此程序，得计算机的最终运行结果。
所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。
针对问题3，基于碎纸片的文字行列特征，采用遗传算法，将所有的可能性拼接进行比较，进行择优性选择。
反面的排序结果用于对正面排序的检验，发现结果有误差，此时，进行人工干预，调换碎纸片的排序。
【关键词】:灰度矩阵欧式距离图像匹配自动拼接人工干预一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。
传统上，大量的纸质物证复原工作都是以人工的方式完成的，准确率较高，但效率很低。
特别是当碎片数量巨大，人工拼接不但耗费大量的人力、物力，而且还可能对物证造成一定的损坏。
随着计算机技术的发展，人们试图把计算机视觉和模式识别应用于碎纸片复原，开展对碎纸片自动拼接技术的研究，以提高拼接复原效率。
试讨论一下问题，并根据题目要求建立相应的模型和算法：、附件4(1)(2)(3)(4)纸片的自动拼接。
问题1：根据图像预处理理论，通过程序语言将图像导入matlab程序，对图像进行预处理，将碎纸片转换成适合于计算机处理的数字图像形式，并对数字图像进行灰度分析，提取灰度矩阵。
数学建模b题碎纸片的拼接复原
碎纸片的拼接复原【摘要】：碎纸片拼接技术是数字图像处理领域的一个重要研究方向，把计算机视觉和程序识别应用于碎纸片的复原，在考古、司法、古生物学等方面具有广泛的应用，具有重要的现实意义。
本文主要结合各种实际应用背景，针对碎纸机绞碎的碎纸片，基于计算机辅助对碎纸片进行自动拼接复原研究。
针对问题1，依据图像预处理理论，通过matlab程序处理图像，将图像转化成适合于计算机处理的数字图像，进行灰度分析，提取灰度矩阵。
对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵A1，提取每个灰度矩阵的最后一列，生成新矩阵B1。
建立碎纸片匹配模型: dai,bj=t=0m-1bti-atj2 ，其中i，j=0,⋯n-1。
p=0≤i≤n-10≤j≤m-1mind(ai,bj)将矩阵A1中的任一列与矩阵B1中的每一列带入模型，所得p值对应的i ,j 值，即为所拼接的碎片序列号。
将程序进行循环操作，得到最终的碎片自动拼接结果。
针对问题2，首先将图像信息进行灰度分析，提取灰度矩阵。
基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列和最后一列，分别生成新矩阵A2、B2；提取所有灰度矩阵的第一行和最后一行，分别作为新生成的矩阵C2、D2。
由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。
在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型：dai,bj=t=0m-1btj-ati2 ，其中i，j=0,⋯n-1。
dci,dj=s=0n-1dsj-asi2 ，其中i，j=0,⋯m-1。
p=0≤i≤n-10≤j≤m-1mind(ai,bj)，q=0≤i≤n-10≤j≤m-1mind(ci,dj)将矩阵A2中的任一列分别与矩阵B2中每一列代入模型，所得p值对应的i ,j 值即为横排序；将矩阵C2中的任一行分别于矩阵D2中的任一行代入模型，所得q值对应的i ,j值即为列排序。
2013全国大学生数学建模竞赛B题
将008代表的矩阵C8的第二列元素与其它矩 阵的第一列元素进行两两匹配。记录元素相 同的个数，个数除以1980为C8矩阵第二列对 其它矩阵第一列的边缘匹配度，记为：
比较这18个数据，最大的即为与008匹配的 碎纸片。然后以所找到的碎纸片的第二列开 始，求出它与其它矩阵第一列的边缘匹配度， 找出最大的，以此类推把19张碎纸片拼接完 成。
三.问题2的分析
英文碎纸片的分析 通过观察可以发现英文字母的主要的 部分拥有同一上界和同一下界，例如：
将图片中每一行中黑色像素数少于13的及 字母的次要部分转变为二值化矩阵中的0， 将每一行中黑色像素大于等于13的及字母 的主要部分转化为二值化矩阵中的1，这样 得到的新的二值化矩阵 。例如图像转变为 如下图的方式：
二.问题1的分析
步骤一：使用matlab中的imread函数 可以做出图片的灰度矩阵 ，读取每 张图片文件的数据，其目的是将附件 中给的 bmp 格式的碎纸片图以灰度 值矩阵的形式存储。再将灰度值矩阵 转化为 0-1 矩阵，来得到模型的数 据基础；
由于该像素图片转换后为
的矩阵，ቤተ መጻሕፍቲ ባይዱ
论文中无法放置，所以仅简单举例说明:
以纸片000与001为例，匹配方式可能为：
将①②的边缘匹配度相加得到边缘匹配度 之和，将③④的边缘匹配度相加得边缘匹 配度之和，两者的和做出比较。若仅有一 个大于等于1.9，则计算机输出该匹配度， 人工判断是否碎纸片是否匹配；若两者均 大于等于1.9，计算机把两个匹配度之和输 出，人工选择判断碎纸片应是否匹配与如 何匹配；若两者均小于1.9，则计算输出最 大者，人工判断碎纸片是否匹配。这样可 以得到一些在同一横行的碎纸片的拼接。
总体思路
三步走：分行，行内排序，行间排序
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。
如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员 (打印并签名) ：1.2.3.指导教师或指导教师组负责人 (打印并签名)：（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。
以上内容请仔细核对，提交后将不再允许做任何修改。
如填写错误，论文可能被取消评奖资格。
）日期： 2013 年 9 月 10 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原模型摘 要： 本文针对碎纸片的拼接复原问题，提出了互相关匹配模型。
首先对附件图片数值化处理并建立矩阵；然后根据图像页边距特点定位最左边和最右边的碎片；按照每张碎片中的文字部分所在位置，提取同一行碎片，利用互相关函数11()()()()11)T T jk jk jkjk ft f t ft f t ρρ--==-≤≤∑∑横向拼合。
在第一问中，附件一、二仅作横向相关性比较即可；在第二、三问中，需要提取同一行碎片横向拼接，并将横向拼合完整的碎片进行竖向拼合，经过人工干预得到结果。
最终结果见附录。
关键词：拼接复原；互相关；矩阵；数值化；人工干预一、问题重述在司法物证复原、历史文献修复以及军事情报获取等领域的破碎文件的拼接上，传统的拼接复原工作需由人工完成，准确率较高，但效率很低。
尤其是当碎片数量巨大时，人工拼接很难在短时间内完成任务。
随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。
我们需要用算法分别设计出附件1至附件5的拼接方法及拼接结果。
二、模型假设1. 忽略实际拼接中边缘的整齐性；2. 不需要考虑实际拼接中破碎文件大小是否一致；3. 忽略碎片边缘的损耗，认为拼接后是完整的图片；4. 在模型的建立过程中重视算法与建模思想，淡化程序的编写；5. 文字的行间距一定。
三、符号说明jk ρ 互相关系数（11jk ρ-≤≤）()j f t 相关像素数组1()k f t 相关像素数组2 i P 图像像素值矩阵 i Q 处理后图像像素值矩阵 ,mn mn a b 矩阵元素四、问题的分析1. 已知条件的分析第一，对碎片尺寸和数量的分析。
附件1和附件2的图片尺寸均为721980⨯，碎片数量均为19；附件3、附件4和附件5的图片尺寸均为72180⨯，碎片数量均为1119⨯。
由于纵列有11个，像素值180，总值111801980⨯=，因此，所有拼接后的图像尺寸一致，均为1368⨯1980。
第二，对碎片边界的分析。
对于附件1、2，所有碎片上行和下行像素值为白。
其中，一张碎片位于最左端，最左列像素值均为白；一张碎片位于最右端，最右列像素值均为白。
对于附件3、4、5，拼接后图像四边像素值为白，碎片也存在边像素值全为白的情况，因此需要分类讨论。
切割线为长度完全相等的直线，因此切割线两边应有很大的相似度，灰度值相似。
第三，对碎片正反性的分析。
附件5存在正反面情况，同一块用a 、b ，但根据题意分析，我们无法确定碎片的正反，即a 可能是正面，也可能是反面。
因此拼合时，应当注意统一序号在同一平面出现的单一性，例如，000a 在设定正面出现以后，000b 一定在反面。
第四，对碎片像素白色行的分析 对于中文，同一行的所有碎片文字是横向对齐的，因此白色开始的位置是一样的。
因此可以提取出同一行的碎片。
2. 拼接方法的分析由于碎片是长方形，有四条边，因此边的拼接有优先顺序。
由于长边特征较为明显，采样点多，因此优先横向拼接，然后纵向拼接。
当电脑拼接无法完成时，采取人工干预。
五、模型的分析与求解1. 方法的确立根据对问题的分析，我们得知此问题需要计算离散序列之间的相关性，因此我们需要使用互相关系数计算和矩阵的计算。
2. 模型的建立 1. 1图像数字化由于电脑中图像的大小是由像素数量表示，而每个像素点均由一个数值表示，因此利用matlab 读取灰度图像的像素值，第n 副图用矩阵表示为：在第一问中，n=72，m=1980；在第二问、第三问中，n=72，m=180。
1. 2数据预处理由于互相关函数需要比较正负范围相等的数组，因此我们将n P 的每个数值减去max 2a ，使mn a 在 [-max 2a ，max 2a]范围内，即 127.5127.5127.5127.5127.5127.5127.5127.5127.5m n A ⨯---⎛⎫⎪--- ⎪=⎪⎪---⎝⎭ (111212122212)a (0255)n n i m m mn a a a a a P a a a a ⎛⎫⎪⎪=≤≤ ⎪ ⎪⎭⎝…………………111212122212127.5127.5127.5127.5127.5127.5127.5127.5127.5n n i i m m mn a a a a a a Q P A a a a ---⎛⎫⎪--- ⎪=-= ⎪⎪---⎭⎝…………………111212122212(127.5127.5)n n m m mn b b b b b b b b b b ⎛⎫ ⎪ ⎪=-≤≤ ⎪⎪⎭⎝…………………1. 3相关性的计算由于碎片大小完全一致，切割线完全竖直且交界处长度完全相等，并且切割线无损，图像可以完全拼接，因此相邻两个图形交接处相似。
由于图像已经数字化处理，因此可以由边界相应像素数值的相关性来确定两张图是否相邻。
对于相关性的计算，我们使用互相关函数。
互相关函数公式为：11()()()()11)T T jk jk jk jk ft f t ft f t ρρ--==-≤≤∑∑公式中，分子表示的是两组离散数值的相似程度，分母则起到归一化作用，相邻两边的数组分别为序列)()(t f t f k j 、。
当1jk ρ→时，两组数相似程度最大，即两张图片最有可能相邻； 当1jk ρ→-时，两组数相似程度最小，即两张图片不相邻。
根据这个公式，即可算出两个图边缘的相关度。
1. 4图像的拼接 1. 4. 1 第一问附件一：首先，根据图像页边距白边特点定位最左边为白色的碎片，i P 的第一列列向量为11211255255(0255)255m a a a a -⎛⎫ ⎪- ⎪≤≤ ⎪ ⎪-⎝⎭…，将i=1,2，……19分别带入计算，仅当i=15时，112112552550255m a a a -⎛⎫⎪- ⎪= ⎪ ⎪-⎝⎭…，因此，最左边碎片为014。
然后，令72()j j f t b =1()k j f t b =，将014矩阵数据带入()j f t 中分别计算jk i ρ，当取得取max ρ时，i-1即为相邻碎片。
同理，即可拼接整幅图。
结果见附录。
198011019801198012210198012019801198012220019801019801198012200()(),1()()()(),2()()()(),19()()j k j k j k jkj k j k j kt t t t it t i t i t t f t f t i f t f t f t f t i f t f t f t f t i f t f t ρ-=--==-=--==-=--==⎧⎪⎪=⎪⨯⎪⎪⎪⎪⎪=⎪=⎨⨯⎪⎪⎪⎪=⨯⎩∑∑∑∑∑∑∑∑∑…⎪⎪⎪⎪⎪ 同理可得附件二结果。
Matlab 附件一 拼接图1. 4. 2 第二问首先，确定最左边碎片。
因为碎片存在非左边仍有白边的情况，例如附件4的图002.bmp ，如下图所示。
（由于底色是白色与文档背景相同，进行了对比度降低处理。
）附件4-002.bmp因此，需要提取多组行向量，根据是否均为0确定最左碎片，同理可确定最右碎片。
左碎片满足条件如下：111212122212255255255255255255=025*******r r m m mr a a a a a a a a a ---⎛⎫⎛⎫⎛⎫ ⎪ ⎪ ⎪--- ⎪ ⎪ ⎪=== ⎪ ⎪ ⎪ ⎪ ⎪ ⎪---⎝⎭⎝⎭⎝⎭………… 式中，r 的大小由实际图像左边缘白边像素数量决定。
在附件3中，r 取15时，满足条件的碎片数量为11。
利用同一行碎片文字垂直位置相同的特点，根据最左边碎片的文字的垂直位置特点，确定图像所在行。
同第二问，分别计算同一行序列的互相关系数，取最大值拼合。
然而，这样只能拼接出11个横行碎片，用互相关函数拼接部分碎片后，最后用人工干预完成白边部分的拼合。
结果如附件所示。
1. 4. 3 第三问由于是两面混合，首先忽视两面性，认为所有碎片是在同一平面上，进行整体拼接，则图像应该为2219⨯个碎片，在进行最左边和最右边计算时会出现22个碎片。
然后根据第二问方法，进行横向碎片的拼接，纵向碎片的拼接。
最后进行人工干预。
由于图像是由两面组成的，因此两张图片的对称点（第n 列和第20-n 列对称）数字相同字母不同，例如199b 在一个面的第4行、第19列，那么199a 就在另一面的第4行、第1列。
因此正反两面的对应行所在位置一致，可以人工将图拼合完整。
效果如如下，结果见附件。
Matlab 附件五拼接图六、模型评价模型优点：1、模型具有坚实可靠的数学基础，经过实践数据分析证明，互相关函数在本题中应用的可行性，简化了对模型问题的分析；2、模型能较好的优化人工干预次数。
模型缺点：1、附件3、4、5在拼接时没有完全脱离人工干预；2、在实际推算中，模型会产生较大的运算量；3、模型在现实生活中的应用有待优化，因为现实中很少有完全规则的文字碎片。
参考文献：[1]屈婉玲等编,离散数学,北京：高等教育出版社 ,2008[2]同济大学数学系编，工程数学——线性代数同济第五版,北京：高等教育出版社，2007[3](美)奥本海姆等著刘树棠译,信号与系统（第二版）,北京：电子工业出版社 2013[4]张志涌等编著,精通MATLAB R2011a,北京：北京航空航天大学出版社 ,2011[5](美)穆尔著，高会生，刘童娜，李聪聪译,MATLAB实用教程（第二版）,北京：电子工业出版社 ,2010[6](美)莫勒（Moler,C.B）著喻文健译,MATLAB数值计算,北京：机械工业出版社, 2006[7](美)冈萨雷斯（Gonzalez.R.C.）等著阮秋琦等译,数字图像处理（MATLAB版）,北京：电子工业出版社 ,2005[8](美)冈萨雷斯等著阮秋琦译,数字图像处理的MATLAB实现（第2版）,北京：清华大学出版社 ,2013[9](美)罗森著袁崇义等译,离散数学及其应用,北京：机械工业出版社 ,2011附录附录一模型结果附件1结果：列数1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19序号0080140120150030100201600100400500901301801100701700006 附件一效果图附件二效果图列数1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19序号0030060020070150180110000500100901301008012014017016004行列1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 191 049054065143186002057192178118190950110221290280911881412 061019078067069099162096131079063116163072006177020520363 168100760621420304102314719105179120861950260010870184 03814804616102403508118912210313193088167025008009105074附件4结果：1314附录三效果图附录四效果图附录五效果图1 附录五效果图2附录二部分源程序（由于源程序篇幅过长，打印不便，因此只附上部分程序）使用软件:MatlabI000=imread('000.bmp')I001=imread('001.bmp')I002=imread('002.bmp')I003=imread('003.bmp')I004=imread('004.bmp')I005=imread('005.bmp')I006=imread('006.bmp')I007=imread('007.bmp')I008=imread('008.bmp')I009=imread('009.bmp')I010=imread('010.bmp')I011=imread('011.bmp')I012=imread('012.bmp')I013=imread('013.bmp')I014=imread('014.bmp')I015=imread('015.bmp')I016=imread('016.bmp')I017=imread('017.bmp')I018=imread('018.bmp')P=[I000,I001,I002,I003,I004,I005,I006,I007,I008,I009,I010,I011 ,I012,I013,I014,I015,I016,I017,I018]% 最左计算函数function F=borderright(x)for j=1:1:19y(j)=0for i=1:1:1980if(x(i,72*(j-1)+1)==255)y(j)=y(j)+0elsey(j)=y(j)+1endendif(y(j)==0)F=jendendendfunction d=split(x,y,m)maxx=[0,0]for j=1:1:19z(j)=0if((j~=(m(1)+1))&&(j~=(m(2)+1))&&(j~=(m(3)+1))&&(j~=(m(4)+1))& &(j~=(m(5)+1))&&(j~=(m(6)+1))&&(j~=(m(7)+1))&&(j~=(m(8)+1))&&( j~=(m(9)+1))&&(j~=(m(10)+1))&&(j~=(m(11)+1))&&(j~=(m(12)+1))&& (j~=(m(13)+1))&&(j~=(m(14)+1))&&(j~=(m(15)+1))&&(j~=(m(16)+1)) &&(j~=(m(17)+1))&&(j~=(m(18)+1))&&(j~=(m(19)+1)))for i=1:1:1980if((x(i,72*y)<255)&&(x(i,72*(j-1)+1))<255)z(j)=z(j)+1elsez(j)=z(j)+0endendelsez(j)=0endif(z(j)>maxx(1))maxx=[z(j),j]endendd=maxx(2)endfunction two(x,a,b)for i=1:1:afor j=1:1:bif(x(i,j)<255)x(i,j)=0endendendf3=0f4=0f5=0f3=double(f3)f4=double(f4)f5=double(f5)p=0bai=0HENG=[19,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 ;20,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 70,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 81,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 86,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 132,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 145,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 159,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 171,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 191,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1;201,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1;]for k=1:1:11a=HENG(k,1)for i=2:1:19for b=1:1:208f3=0f4=0f5=0for c=1:1:180f1=Q(c+a*180,72)f2=Q(c+b*180,1)f3=f3+Q(c+a*180,72)*Q(c+b*180,1)f4=f4+f1*f1f5=f5+f2*f2endr(b)=f3/sqrt(f4*f5)if r(b)>pp=r(b)h=bendr(b)=0endp=0HENG(k,i)=ha=hfor c=1:1:180bai=bai+Q(c+a*180,72)endif ((bai==22950)&&(i==19))msgbox('àÞÀ²')endif ((bai==22950)&&(i<19))msgbox('¹þ¹þ£¬È˹¤¸ÉÔ¤°É')breakendbai=0endendf3=0f4=0f5=0f3=double(f3)f4=double(f4)f5=double(f5)p=0bai=0% 初始化数组%HENG=[49,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,14 1;% 61,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,36; %168,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,18;% 38,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,74; % 71,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,60; %14,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,176;% 94,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,43; %125,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,145;% 29,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,59; % 7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,196; %89,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,123;]for k=1:1:11a=HENG(k,19)for i=18:-1:1for b=1:1:208f3=0f4=0f5=0r(b)=0if b~=105for c=1:1:180f1=Q(c+a*180,1)f2=Q(c+b*180,72)f3=f3+Q(c+a*180,1)*Q(c+b*180,72) f4=f4+f1*f1f5=f5+f2*f2endr(b)=f3/sqrt(f4*f5)if r(b)>pp=r(b)h=bendendendp=0HENG(k,i)=ha=hfor c=1:1:180bai=bai+Q(c+a*180,1)endif (bai>22000)&&(i>1)msgbox('¹þ¹þ£¬È˹¤¸ÉÔ¤°É')breakendbai=0endend。