碎纸片的复原拼接.doc

碎纸片的拼接复原摘要本文通过matlab软件对碎片进行分析和预处理，然后用边缘像素匹配、Harris算法、NCC算法、随机抽样一致性算法建立模型，通过matlab求解，得到相应的碎片匹配编号和复原后的图像。 针对问题一：对附件1中的中文碎片，我们建立了基于边缘像素匹配的模型。首先对碎片做分析和预处理，提取碎片的边缘像素。比较左边碎片的右边缘和右边碎片的左边缘的像素相似度，分别找出000到018编号相匹配的右碎片。把对应编号制成表2，然后用imshow绘制出复合后的图像1。 对附件2中的英文碎片，我们建立了基于边缘像素匹配的半自动模型。运用中文碎片的算法求解本文题时，出现了不匹配的现象，人工干预挑出不匹配的碎片，重新运用像素相似度的次大值进行匹配，最后得到匹配编号表8和复合图像2。 针对问题二：我们建立了改进的边缘像素匹配模型。采用和附件2相似的算法，首先对附件3中的209张碎片，按照边缘像素相似度匹配，进行左右拼接，得到11张新的碎片111.jpg。然后对这11张碎片进行上下拼接。得到匹配编号表9、10和复合图像3、4。 针对问题三：我们建立了基于特征点匹配的图像拼接模型。首先用Harris角点检测算法,提取图片的特征点，然后利用NCC算法，通过用双向最大相关系数匹配的方法提取出初始特征点对,再用RANSAC剔除伪特征点对,实现特征点对的精确匹配。最后用正确的特征点匹配对实现图像的配准。最后得到匹配编号表10、11和图像5a,图像5b。关键词：图片预处理 边缘像素匹配 Harris角点检测 NCC匹配算法 RANSAC算法一、 问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、基本假设1、假设碎纸片需要人工干预时，干预时间不受人自身因素影响。2、假设碎纸片数据时由局内点组成。3、假设只有局内点才能适应该模型的数据，局外点则不能适应。4、假设除此之外的数据都属于噪点。5、给定一组（通常很小的）局内点，存在一个可以估计模型参数的过程;而该模 型能够解释或者适用于局内点。 三、 符号与名词说明：相关窗的归一化互相关系数：参考图像：待配准图像：标准差：互相关系数：相关窗内像素灰度的平均值：数据集：具有一定关系的数据点：数据子集：占有率：样本的概率4、 模型的建立与求解1、问题一 基于纸片边缘像素的匹配模型1.1附件1中文碎片拼接模型1.1.1 问题分析针对附件1我们建立了基于边缘像素匹配的模型。首先对纸片做预处理，提取纸片的边缘像素。通过人工干预确定008.bmp应为左边第一张纸片，然后设计递归算法，把第一张纸片和其他18张纸片进行两两的左右拼接，找到边缘像素相似度最高的图片，做为右边的第二张图片，把第一张图片和第二张图片融合成一张图片，和其他17张图片进行左右拼接，找到右边第三张图片，以此类推完成了19条碎片的拼接工作。拼接后的原图见附件。具体做法如下： 首先把19张中文纸片用imread导入到matlab中，提取纸片的边缘像素特征。通过人工干预确定008.bmp应为左边第一张纸片，根据起始碎片的右边缘特征，找到与之像素相似度最高的图片，依次向右拼接。在连续的向右拼接过程中，均是查找待拼接的碎片块（起始碎片为008.bmp）右边边缘1980个像素点（0-255值）和剩余碎片的左边边缘1980个像素点，找出相似度最大的碎片作为可匹配待拼接的碎片，并将成功拼接的碎片最为新的待拼接的碎片块，继续向右进行拼接工作，直到得到的待拼接的碎片块为19个，即表示完成了19张碎片的拼接。每次查找到匹配的碎片时，均使用MATLAB的矩阵合并运算，实现待拼接的碎片块和匹配的碎片的像素矩阵左右合并，再利用imshow()来完成合并的像素矩阵的图像显示。在连续向右查找匹配的过程中，合并的像素矩阵会越来越大，直到像素矩阵合并了19张碎片的1980*72个像素，最后利用imshow()实现复原后图片的绘制。其中，相似度为碎片右边边缘和碎片左边边缘像素点值（0-255）相等的个数与纵向像素点1980的比值，一次匹配时，利用附录中程序2找到最大的比值后，可得到相应的碎片编号，经过19次匹配，依次得到正确拼接的两张碎片编号，然后利用递归算法连接序列号，成功实现了19张碎片的匹配。1.1.2 算法设计步骤（1）编写读取连续19张碎片的程序（见附录程序1）。创建一个含有19个元素的结构体file，每个结构体中的元素均是一个1980*72的矩阵，利用imread读取19个碎片得到19*1980*72个像素点，并且分别存储在19个矩阵中（结构体file中）。（2）编写用来得到最大相似度对应的碎片编号的程序（见附录程序2）。利用内层for循环找到与待拼接碎片匹配的右碎片编号。再利用外层for循环找到分别与000到018编号相匹配的右碎片。得到表1。表1 正确拼接的两张碎片编号左碎片右碎片000006001004002016003010004005005009006008007017008014009013010002011007012015013018014012015003016001017000018011（3）根据递归的特点（自身调用自身的函数），编写递归程序（见附录程序3）。从附件1中找到起始的待拼接碎片（008.bmp），作为第一次调用递归的形参。根据（2）中所得的碎片编号链表（表1），依次查找008.bmp后接的碎片号作为递归函数的参数，再次调用递归，直到后接的碎片号为008.bmp，即停止递归，则可得到复原图像的碎片编号顺序。（4）编写显示拼接碎片的程序（见附录程序4）。借助递归产生的连续碎片编号，把编号匹配的图片的像素点矩阵合并成新的像素点矩阵，用imshow绘制碎片的合并图像，接着是合并后的像素点矩阵和碎片序列中对应的下一个碎片的像素点矩阵合并成另一个新的像素点矩阵，最后合并了19张碎片的像素点矩阵，用 imshow把复原的图像显示在matlab画布上。1.1.3 附件1最终匹配结果在MATLAB中调用附录中的程序，得到最终的19张碎片序号，按复原后顺序填入119的表格，见表2。以及复原后的图像，见附录中图像1。表2 附件1复原后碎片序号0080140120150030100020160010040050090130180110070170000061.2 附件2英文碎片拼接模型1.2.1问题分析在本问题中，通过人工干预选出左边起始的碎片为003，然后按照上述方法，进行边缘像素相似匹配。求解过程中发现程序5在匹配英文纸片时有缺陷。由于英文字体的特征，存在相似度值相等或次大的碎片能成功匹配的情况。又因为英文文字的局部分布密度比较小，所以利用相似度最大来进行2张碎片拼接将不完全适用于此问题，改进程序5，建立了半自动化的匹配模型。针对本问题编写程序（见附录程序6），将附件2的19张碎片导入到MATLAB工作区中，编写程序7（见附录）计算两张碎片边缘像素相似度，多次调用程序7，即可得到左边一张碎片与剩余其他18张碎片的18个相似度值，先取最大相似度值对应的碎片编号（调用程序7中运行得到的num最大值所在的位置即是编号，如第5个位置，则表示碎片编号005），人工干预判别出匹配与不匹配的相似对，对匹配不成功的碎片，重新调用程序7，进行次最大相似度匹配，最终得到碎片的匹配结果。1.2.2模型求解过程（1）利用imread()将附件2的19张碎片导入到MATLAB工作区中，见附录程序6。（2）用MATLAB调用附录中的程序7，计算待匹配碎片的右边缘与其他18个碎片的左边缘的像素相似度，找出最大相似度对应的碎片编号。多次调用程序7，方可得到与000-018碎片像素相似度最大的右边碎片编号，结果出现不匹配现象，见表3。表3 左右边碎片拼接结果左边碎片的编号程序匹配右边碎片的编号肉眼拼接验证干预时间000005匹配10s001009匹配10s002003不匹配10s003006匹配10s004003不匹配10s005001匹配10s006002匹配10s007015匹配10s008012匹配10s009013匹配10s010008匹配10s011003不匹配10s012014匹配10s013003不匹配10s014017匹配10s015018匹配10s016004匹配10s017016匹配10s018011匹配10s （3）从表3中取出4个不匹配的碎片编号，见表4。表4 4个不匹配的碎片编号002004011013 我们需要对不匹配的碎片（002，004，011，013）进行人工干预。通过人工干预得知编号为004的碎片应为最右边的碎片，即没有右边可拼接的碎片。所以将编号004的碎片作为末尾碎片，不进行再次匹配，其他则重新调用程序7（见调用程序7方法中的，），每组调用得到的18个num值（边缘像素相似度）中，不再取num最大值，而是依次取num的次大值，进而得到次大值对应的碎片编号，得到三组最终匹配成功的右边碎片编号，见表5。表5 再次匹配的结果左边碎片编号002相似度降序对应碎片编号匹配情况干预时间0.8823003已知不匹配30s0.8813007匹配30s左边碎片编号011相似度降序对应碎片编号匹配情况干预时间0.8798003已知不匹配30s0.8707000匹配30s左边碎片编号013相似度降序对应碎片编号匹配情况干预时间0.8682003已知不匹配30s0.8586010匹配30s每组次大值对应的碎片编号，全部为匹配成功，如表6所示。表6 3组匹配结果左边碎片的编号程序匹配右边碎片的编号0020070110000130101.2.3最终匹配结果根据表3至表6，整合得到000-018碎片编号的最终匹配的右边碎片编号（003为起始碎片，004为末尾碎片），见表7。表7 19张碎片右边拼接结果左边碎片的编号程序匹配右边碎片的编号000005001009002007003006004无005001006002007015008012009013010008011000012014013010014017015018016004017016018011根据表7的结果，进行碎片编号的连接，得到最终的19张碎片序号，按复原后顺序填入119的表格，如表8所示。表8 附件2复原后碎片序号003006002007015018011000005001009013010008012014017016004再利用MATLAB中imshow()（见附录绘制图像2的代码），得到复原后的图像，见附录图像2。2、问题二 改进的边缘像素匹配模型2.1问题分析首先我们利用imread读取209张中文碎片的像素点到209个180*72矩阵中，利用先纵向拼接，再横向拼接的方法实现了209张中文和英文横纵切片的复原。针对问题二的209张中文碎片，通过人工干预得到11张起始碎片编号（014、094、125、029、007、089、049、061、168、038、071），再依次取11个作为起始的碎片，取最右边的一列像素点与其余的208张碎片最左边的一列像素点进行RGB（0-255值）比较，得到相似度，取最大的相似度对应的碎片编号作为该起始碎片的右边碎片，如同问题一中附录2英文模型的求解过程，在连续得到19张可作为右边的碎片编号时，可结束该起始碎片的连续拼接，并将这19张碎片像素点合并形成新的像素点矩阵，存放在用cell定义出的file结构体（11个元素，每个元素均是19张碎片拼接而成的像素点矩阵）。类推得到11张纵向拼接而成的11张新的图片，存放在file结构体中。原理如同纵向拼接，取出file结构体中的11张图片，进行横向拼接。我们首先选出起始的图片，再根据起始图片的最下边边像素点与其他10张图片的最上边像素点的相似程度，得到最大的相似度，利用imshow来完成两张图片横向拼接，最终完成11张图片的横向拼接，即实现209张碎片的横向和纵向拼接，到达复原的目的。针对问题二的209张英文碎片，除了11张起始碎片编号的不同（191、201、086、019、159、020、208、070、132、171、081），其他拼接的过程类似，所以可按照同样的原理复原209张英文碎片。2.2求解结果运行程序后，得到匹配后图片的序列号，见表9、表10。表9附件3复原后碎片序号014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145 029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060表10 附件4复原后碎片序号191075011154190184002104180064106004149032204065039067147201148170196198094113164078103091080101026100006017028146086051107029040158186098024117150005059058092030037046127019194093141088121126105155114176182151022057202071165082159139001129063138153053038123120175085050160187097203031020041108116136073036207135015076043199045173079161179143208021007049061119033142168062169054192133118189162197112070084060014068174137195008049172156096023099122090185109132181095069167163166188111144206003130034013110025027178171042066205010157074145083134055018056035016009183152044081077128200131052125140193087089048072012177124000102115最后用imshow画出匹配后的图像，见附录中的图像3、图像4。3、问题三 基于特征点匹配的拼接模型针对问题三，我们首先用Harris角点检测算法,提取图片的特征点，然后利用相似测度NCC，通过用双向最大相关系数匹配的方法提取出初始特征点对,再用随机采样法RANSAC剔除伪特征点对,实现特征点对的精确匹配。最后用正确的特征点匹配对实现图像的配准。3.1 基于角点匹配的harris算法3.1.1检测原理 Harris 角点检测算法是一种基于信号的点特征提取算子，其原理是将所处理的图像窗口 (一般为矩形区域)向任意方向移动微小位移(x, y)，则其灰度改变量可定义为 其中，和 是一阶灰度梯度，可对图像求卷积得 为了提高抗噪能力，对图像窗口进行了高斯平滑，选用 如下的高斯窗口另外定义和矩阵： 与局部自相关函数很接近，描述了这个自相关函数在原点的形状。设 和 分别是 的 2 个特征值。和与局部自相关函数的主曲率成比例，构成一个对 的旋转不变数。此时，可以通过判断 和的值的情况来判 断平坦区、角点和边沿，有以下 3 种情况： (1)2 个曲率都很小，说明局部自相关函数很平坦； (2) 一个曲率大，另一个曲率小。说明局部自相关函数呈现山脊状，则 沿着山脊的变化很小，而垂直于山脊的变换 很大，此处为一个边沿；(3)2 个曲率都很大，说明局部自相关函数有一个尖峰， 则沿任何方向变化都很激烈，此处为一个角点。 于是，Harris 特征点可以定义为下式的局部区域最大值： 其中，表示矩阵的迹；表示矩阵的行列式 值；值 Harris推荐为 0.04。 在具体的计算中，注意下面 2 个关系： 则其角点/边缘响应函数 可定义为 3.1.2 算法步骤 从以上分析可以看出，应用 Harris 方法提取图像中角点 的过程可以分为以下几步： (1)计算图像像素点在水平和垂直方向上的梯度，以及两者的乘积，得到中 4 个元素(2) 对图像进行高斯滤波，得到新的 。 离散二维零均值高斯函数为：(3) 计算原图像上对应的每个像素点的兴趣值，即 R 值(4) 选取局部极值点。Harris 方法认为，特征点是局部范 围内的极大兴趣值对应的像素点。 (5)设定阈值，选取一定量的角点。 本问题的Harris角点检测算法用matlab软件实现，程序见附录，下图是图片000.bmp的角点检测。3.2 NCC角点匹配 经过Harris角点提取之后，获得两幅图像的角点响应值为1的像素点的具体的坐标，采用NCC算法找出特征点的对应关系。该方法选取角点为中心的7x7的窗口作为模板进行角点匹配，匹配系数达到最大值的点对即为匹配点对，匹配时要求从参考图像和待拼接图像进行双向搜索匹配，两个方向的匹配系数都达到最大时则该点对满足匹配关系。NCC算法计算过程如下： 首先，分别计算待配准图像中以每一个角点为中心的邻域与参考图像中以每一个角点为中心的相同大小邻域的互相关系数，窗口大小设置为，相当于以角点为中心从(-3，3)的搜索范围计算相关系数。 假定参考图像和待配准图像分别为和，分别提取出和个候选角点。计算待配准图像与参考图像中的每个角点邻域间的相关系数，构成大小的矩阵，采用双向搜索的方法模板相关法运行次数为。 为了降低图像亮度和对比度在匹配中的影响，采用归一化互相关系数。假定Xl(坐标为(xl，y1)、X2(坐标为(x2，y2)分别是参考图像与待配准图像中任意两个角点，则以Xl，X2为中心，窗口大小为的两图像相关窗的归一化互相关系数 定义如下： 式中的和分别分别表示图像的标准差和互相关系数，其中 上面两式中n的取值为(-3，3)，表示图像(它可以是参考图像也可以是待拼接图像)中以点(可以是待拼接图像中的角点，也可以是参考图像当中的角点)为中心的相关窗的均值，即相关窗内像素灰度的平均值： 程序见附录。3.3 RANSAC算法 计算出图像特征点问的相关性后，图像的相关点并不一定是匹配点，相关点的集合中会含有大量的不匹配的特征点。因此，还要进一步筛选出精确匹配的特征点对，本中使用RANSAC算法，提纯特征点集合。 随机抽样一致性算法是基于假设和检验的框架来实现的，从输入的数据点集中随机地选择一个最小数量的点集，并以这个最小的数据点集来估计模型的参数。然后，用所有的数据集来对模型进行检验，可以确定模型的支持度即与模型一致的数据点的数量。假设与检验的循环过程会一直进行，直到找到一个比目前最佳模型获得更好支持的模型的概率，低于预先设定的阈值，典型的设为1%5%。随机抽样一致性算法经常能够找到正确的解决方案，即使是在数据被高度污染的情况下。但是所需要的采样次数会成指数次方的增长，并且相应的计算开销会大量增加。 假定有一个数据集包含有个具有一定关系的数据点，RANSAC算法从数据集中随机采样一个大小为的数据子集，为确定模型相关计算所需要的最小数据集，它的大小是由几何模型的复杂度决定。一旦从这个最小数据集通过计算假设出一个模型，然后用数据集中的所有数据点对该模型进行检验并确定出此模型的支持度。这个过程会重复进行直到满足最终的结束评价标准。RANSAC标准的结束准则是要确保一定置信度，即至少要能选择出一个没有outliers的最小子集，所要求的采样最小数量。假定数据集中真实的inliers占有率为，则选择一个没有被污染的个inliers点样本的概率为，同样，选择k个样本，这些样本数据被污染即至少有一个outlier的概率为。因此采样的最小数量一定确保概率降到阈值以下，即： 随机抽样一致性算法过程如下：Step1：由上式，根据outliers的比例，在用户指定的置信概率下，计算出采样的数据中至少有一组全为in-liers数据所需要的采样次数。Step2：在数据集中，随机选择出个数据构成最小数据子集，并计算该子集对应的模型参考，然后用数据集中的所有数据对此模型进行检验，获得每个模型参考数的inliers数量及每个数据相对于该模型的误差。Step3：根据inliers数量和错误率来选择最优模型，获得符合该模型的inliers，并用此inliers计算出最终的模型参数。程序见附录。匹配后的碎片编号见表10、表11。表10 附件5a复原后碎片序号078b111b125a140a155a150a183b174b110a066a108a018b029a189b081b164b020a047a136b089a010b036a076b178a044a025b192a124b022a120b144a079a014a059a060b147a152a005a186b153a084b042b030a038a121a098a094b061b137b045a138a056b131b187b086b200b143b199b011b161a169b194b173b206b156a034a181b198b087a132b093a072b175a097a039b083a088b107a149b180a037b191a065b115b166b01b151b170b041a070b139b002a162b203b090a114a184b179b116b207a058a158a197a154b028b012a017b102b064b208a142a057a024a013a146a171b031a201a050a190b092b019b016b177b053b202a021b130a163a193b073b159a035a165b195a128a157a168a046a067a063b075b167a117b008b068b188a127a040a182b122a172a003b007b085b148b077a004a069a032a074b126b176a185a000b080b027a135b141a204b105a023b133a048a051b095a160b119a033b071b052a062a129b118b101a015b205a082b145a009b099a043a096b109a123a006a104a134a113a026b049b091a106b100b055b103a112a196b054b表11 附件5b复原后碎片序号020b164a081a189a029b018a108b066b110b174a183a150b155b140b125b111a078a020b164a147b060a059b014b079b144b120a022b124a192b025a044b178b076a036b010a089b147b060a086a187a131a056a138b045b137a061a094a098b121b038b030b042a084a153b186a086a187a097b175b072a093b132a087b198a181a034b156b206a173a194a169a161b011a199a097b175b162a002b139a070a041b170a151a001a166a115a065a191b037a180b149a107b088a162a002b057b142b208b064a102a017a012b028a154a197b158b058b207b116a179a184a114b057b142b073a193a163b130b021a202b053a177a016a019a092a190a050b201b031b171a146b073a193a182a040b127b188b068a008a117a167b075a063a067b046b168b157b128b195b165a182a040b141b135a027b080a000a185b176b126a074a032b069b004b077b148a085a007a003a141b135a082a205b015a101b118a129a062b052b071a033a119b160a095b051a048b133b023a082a205b112b103b055a100a106a091b049a026a113b134b104b006b123b109b096a043b099b112b103b还原后的图像见附录中的图像5a,图像5b。五、模型优缺点分析及改进方向本文所建模型的优缺点主要体现在以下几个方面：针对基于边缘像素匹配的模型：优点：模型原理简单、实用，编写程序易于实现，可以完成碎片的拼接复原。缺点：英文匹配时，比较粗糙，有一定的误差，需要人工干预。针对基于特征点匹配的图像拼接模型：优点：模型所采用harris算法、NCC算法、RANSAC算法，精度较高，匹配较准确。缺点：程序编写复杂，不易操作，容易出现错误，得不到运行结果。六、参考文献1 基于特征匹配的全自动图像拼接算法研究2 基于特征点图像拼接的配准算法研究-天津大学2008年硕士论文3 钟家强,王润生.基于边缘的图像配准改进算法J. 计算机工程与科学4 张素,王小菊.一种基于小波分解的多图像拼接技术 J.西北工业大学学报5 图像碎片复原方法的研究-华北电力大学（北京）2010年硕士论文6 MATLAB统计分析与应用附录：1. 问题一的所有附录：1.1附件1中文拼接程序：程序1（读取19张碎片）：function file=readfile()file=cell(19,1);for i=1:19 if i=10 url=strcat(00,num2str(i-1); else url=strcat(0,num2str(i-1); end url=strcat(url,.bmp); filei,1=imread(url);endend程序2（计算边缘像素相似度的程序）：function number=calu(x,y)num=zeros(1,19);for j=1:19 m(1:1980,1)=zeros(1980,1); m(1:1980,2)=zeros(1980,1); for i=1:1980 m(i,1)=x(i,72); m(i,2)=yj,1(i,1); if(m(i,2)-m(i,1)=0) num(j)=num(j)+1; end end num(j)=num(j)/1980;endmax=num(1);number=0;for n=1:19if(maxnum(n) max=num(n); number=n-1;endendend程序3(实现匹配后的碎片连接)：function linkgai(i,num) numi+1,1;if numi+1,1=8 show(numi+1,1); linkgai(numi+1,1,num);endend%function num=all()y=cell(19,1);y=readfile();num=cell(19,1);for i=1:19 x=yi,1; numi,1=calu(x,y);endend程序4（画出复原后的图片）：function show(i)global array; if i10 url=strcat(00,num2str(i); else url=strcat(0,num2str(i); end url=strcat(url,.bmp); array2,1=imread(url); imshow(array1,1 array2,1); array1,1=array1,1 array2,1;end求解附件1的总程序:function start()global array;array=cell(2,1);array1,1=imread(008.bmp);num=all()%返回000018碎片编号对应右边可拼接的碎片编号linkgai(8,num);end%function linkgai(i,num) numi+1,1%返回复原顺序的碎片编号if numi+1,1=8 show(numi+1,1); linkgai(numi+1,1,num);endend%function show(i)global array; if i10 url=strcat(00,num2str(i); else url=strcat(0,num2str(i); end url=strcat(url,.bmp); array2,1=imread(url); imshow(array1,1 array2,1); array1,1=array1,1 array2,1;end%function num=all()y=cell(19,1);y=readfile();num=cell(19,1);for i=1:19 x=yi,1; numi,1=calu(x,y);endend%function file=readfile()file=cell(19,1);for i=1:19 if i=10 url=strcat(00,num2str(i-1); else url=strcat(0,num2str(i-1); end url=strcat(url,.bmp); filei,1=imread(url);endend% function number=calu(x,y)num=zeros(1,19);for j=1:19 m(1:1980,1)=zeros(1980,1); m(1:1980,2)=zeros(1980,1); for i=1:1980 m(i,1)=x(i,72); m(i,2)=yj,1(i,1); if(m(i,2)-m(i,1)=0) num(j)=num(j)+1; end end num(j)=num(j)/1980;endmax=num(1);number=0;for n=1:19if(maxnum(n) max=num(n); number=n-1;endendend调用上述总程序的方法：先在MATLAB中设计SET PATH，将B题附件1所在路径添加到MATLAB路径中，再在COMMAND窗口中输入start()，返回的num即为000-018对应的右边可拼接的碎片编号，而返回的多个ans，即为复原顺序碎片的编号（第一个编号为人工干预的008），从而可在MATLAB画布上绘制复原图像，即实现了B题附件1的图像复原。复原后的图像1：1.2附件2英文拼接程序：程序6：说明：先在MATLAB中SET PATH将B题附件2所在路径添加到MATLAB路径中l0=imread(000.bmp);l1=imread(001.bmp);l2=imread(002.bmp);l3=imread(003.bmp);l4=imread(004.bmp);l5=imread(005.bmp);l6=imread(006.bmp);l7=imread(007.bmp);l8=imread(008.bmp);l9=imread(009.bmp);l10=imread(010.bmp);l11=imread(011.bmp);l12=imread(012.bmp);l13=imread(013.bmp);l14=imread(014.bmp);l15=imread(015.bmp);l16=imread(016.bmp);l17=imread(017.bmp);l18=imread(018.bmp);程序7：function f(x,y)m(1:1980,1)=zeros(1980,1);m(1:1980,2)=zeros(1980,1);num=0; for i=1:1980 m(i,1)=x(i,72); m(i,2)=y(i,1); if(m(i,2)-m(i,1)=0) num=num+1; end end num=num/1980end调用程序7的方法：说明：每组调用程序7得到的为某张碎片右边边缘与剩余其他碎片左边边缘像素点相似度，取得一个最大相似度（num值最大），而其对应的碎片编号即为这张左边碎片可匹配的右边碎片。左边碎片编号000的右边碎片编号为：005f(l0,l1), f(l0,l2), f(l0,l3), f(l0,l4), f(l0,l5), f(l0,l6), f(l0,l7), f(l0,l8), f(l0,l9), f(l0,l10), f(l0,l11), f(l0,l12), f(l0,l13), f(l0,l14), f(l0,l15), f(l0,l16), f(l0,l17), f(l0,l18) 左边碎片编号001的右边碎片编号为：009f(l1,l0)