2013年高教社杯全国数学建模竞赛获奖优秀论文B题.doc

2013高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 东南大学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原模型摘要破碎文件的拼接复原一直是图像处理领域的重要内容，本题我们构建碎纸片的拼接模型并解决三种不同情形下的碎纸片的拼接复原问题，提高碎纸片的拼接效率。对于问题一，考虑到附件给我们的图像都是位图并且是纵切，我们首先将碎片图像全部转化为0到255范围的灰度矩阵并提取左右边缘向量，由此将图像的拼接问题转化为对边缘向量匹配度的研究。我们用碎片之间边缘向量的欧式距离来具体描述匹配度并以此建立了图像匹配模型。然后对附件1、2中的数据进行批量处理，得到附件1、2的复原结果(具体见正文模型部分)。对于问题二，我们首先提取碎片四周的边缘向量，然后考虑到附件3、4的碎片图像像素较小，代入图像匹配模型计算结果的精度较小。所以我们引入了行间距的概念作为图像匹配时的约束条件，以此建立了图像匹配的优化模型。同时考虑到英文字母不像中文那样是方块字，在行距匹配时会出现匹配不准的情况，所以在对英文字母进行行距匹配前，我们先对英文字母的灰度矩阵二值化，以此来提高行距匹配的准确度。我们首先利用图像匹配模型对所有的图像进行左右边缘向量的循环迭代匹配，加上一定程度的人为干预实现对所有碎片的循环迭代匹配，最后再对已得到的图像进行上下边缘向量的循环匹配，得到附件3、4的复原结果(具体见正文模型求解部分)。对于问题三，考虑到每个碎纸片都有两个面，每个面都可以进行边缘向量匹配度的计算。所以我们综合计算a和b两个面的边缘向量匹配度，对模型二中描述匹配度的欧氏距离进行了优化，建立了模型二的优化模型。利用模型二中算法求解各个碎片的欧氏距离的优化解，得到匹配度最高的图像，把它们拼接起来。最后得到附件5的复原结果(具体见正文模型部分)。关键词：图像拼接 灰度匹配 欧氏距离 循环迭代 二值化 一、 问题重述本题给了5个附件，其中附件1、2包含19条纵切的碎片，附件3、4包含1119个横纵切的碎片，附件5包含21119个双面打印的碎片。要求我们根据5个附件的内容讨论以下问题：1、对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。2、对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3、上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。【结果表达格式说明】复原图片放入附录中，表格表达格式如下：(1) 附件1、附件2的结果：将碎片序号按复原后顺序填入119的表格；(2) 附件3、附件4的结果：将碎片序号按复原后顺序填入1119的表格；(3) 附件5的结果：将碎片序号按复原后顺序填入两个1119的表格；(4) 不能确定复原位置的碎片，可不填入上述表格，单独列表。二、 问题分析2.1 问题一的分析考虑到附件给我们的图像都是位图，每个图像都有198072个像素点；我们用matlab将图像转化为198072的像素矩阵，矩阵中每个值表示图像中对应像素点的灰度值，因为我们研究的是图片的拼接，而且切从切割效果来看都是属于规则垂直切割，那么只需要研究拼接处的灰度值，所以我们将矩阵的第一列和最后一列提取出来，分别表示图像左边缘和右边缘的灰度值；这样每幅图像都产生了两个19801的向量。然后我们matlab计算每幅图之间左右向量的距离，以此来表示两幅图的匹配度，距离越小代表匹配度越大，越有可能匹配成功。然后用matlab对距离排序得到每幅图与之匹配度最大的图像并且逐次拼接。2.2 问题二的分析附件中提供了209张位图，每个图像有18072个像素点，结合模型一我们仍然可以通过计算图与图左右向量之间的距离确定两幅图的匹配度。但是考虑到附件中给我们的图像的像素较小，模型一的算法的精确度可能不够，造成匹配结果不佳错误。因此我们要对模型一进行优化，我们引入行距的概念作为图像匹配的约束条件，以此来提高模型二的精确度。另外考虑到在进行行距匹配时，由于英文字母与汉字的情形不同，我们要通过设置不同的阈值来分别考虑这两种情形。最后连接图像的过程可以参照模型一。2.3 问题三的分析 附件中提供了21119个碎纸片，每个碎纸片都可以进行边缘向量匹配度的计算。但是实际上a和b同属于一张碎纸片的正反面，所以结合模型二我们可以对同一张碎纸片计算两次匹配度，这样就能够提高匹配的精确度。不过由于图像的数量也相应增加了，计算难度也一定程度的加大，需要更多的人工干预。三、 模型假设1.假设所有附件所给的图片确实能拼接成一个完整的图；2.假设题目所给数据均真实可靠；3.假设所有碎纸片都是边缘光滑，厚度不计的。四、 符号说明H灰度矩阵h表示图像中每个像素点的灰度值L、R表示图像的左右边缘向量Q表示边缘向量矩阵D表示两边缘向量的欧氏距离P表示x个图像两两之间的匹配程度矩阵i、j、k图像序号Si表示原图中最左边的图像的总称Wi 表示原图中最右边的图像的总称五、 模型的建立与求解5.1 模型一的建立与求解5.1.1 灰度矩阵与边缘向量的建立在黑白图像中，我们用灰度表示某一点颜色的深度，范围一般从0到255，白色为255，黑色为0。所以对于一个像素为mn的图像，我们可以将它转化为一个mn的矩阵，这里我们将这个矩阵称作灰度矩阵H，每个像素点的灰度值令为hab(a=1m,b=1n,hab=0255)。那么H=h11h1nhabhm1hmn我们将矩阵H的第一列与最后一列提取出来，得到向量：L=h11hm1 R=h1nhmn 这里我们将向量L和R称作边缘向量。5.1.2 图像匹配模型的建立对于判断两个图像的匹配程度，我们可以提取两图像的边缘特征进行比较，在黑白图像中边缘特征可以量化为边缘向量。假设有x个像素为mn的图像，由matlab的imread函数我们可以求得对应的x个灰度矩阵Hi (i=1x)，其边缘向量为Li和Ri。为了方便计算，在这里我们定义这x个图像的边缘向量矩阵Q为：Q=L1R1LxRx下面我们定义矩阵Hi边缘向量和矩阵Hj边缘向量的欧式距离为：D=i=1mLi-Ri2当D的值越小，表示矩阵Hi和矩阵Hj对应的图像匹配程度越高。那么由这x个图像我们可以得到一个xx的矩阵P，矩阵P的元素表示这x个图像两两之间的匹配程度，即：P=D11D1xDijDx1Dxx其中，Dij表示Hi边缘向量和矩阵Hj边缘向量的距离。通过观察可以得到矩阵P第i行所有元素中的最小值(Dij)min，表示：图像Hi的左边缘可以与图像Hj的右边缘拼接。以此类推，可以得到所有图像的拼接顺序。5.1.3 计算两图像距离算法的图例说明如下图1所示：假设中间黑线部分把汉字“如”分成左右两部分，提取左右两边的图像边缘并放大如下图2所示， 图1 图2运用matlab中的imread函数将图2中的两边缘转化为灰度值，两组灰度值分别命名为L和R，其值如下表2：表2 像素灰度值L18300445222000000060001R180000000000022110204255000根据上表可以计算出图2 中两图像的距离为：D=（183-180）2+（0-0）2+（0-110）2+(0-0)2+(1-0)2307.85.1.4 模型一的求解(1) 中文碎纸片拼接用matlab编程得到附件1中所给的19块碎纸片的边缘向量矩阵QC(见附录)。进而得到矩阵PC，矩阵PC的具体值见下表3(具体见附录)：表3中文碎纸片的匹配矩阵H1H2H3H4H16H17H18H19H14999.15104.55381.14831.15162.65321.71978.44664.9H25379.75328.95027.65339.45244.12148.652975097.1H35115.35242.25237.44650.35140.85424.95223.74724.8H45634.35153.24787.75386.81863.55300.25498.75162.8H164687.84643.34381.54848.85024.45209.54506.73973.9H175184.24680.21399.15088.34847.94998.35404.94733.8H184751.55016.14953.54730.25500.753354885.15143H194414.54880.75092.85155.55298.1509049454566.9根据上表，我们可以得到各中文碎纸片与之匹配程度最高的碎纸片，进而我们可以得出碎片复原序号为下表2：表4 中文碎片复原序号008014012015003010002016001004005009013018011007017000006根据复原序号，我们用Matlab拼接程序拼接出复原图片见附录。(2) 英文碎纸片拼接用matlab编程得到附件2中所给的19块碎纸片的边缘向量矩阵QE(见附录)。进而得到矩阵PE，矩阵PE的具体值见下表5(具体见附录)：表5 英文碎纸片的匹配矩阵H1H2H3H4H16H17H18H19H14221.83881.83477.33748.435843678.83620.93971.7H24327.73700.23616.23649.83582.13868.93944.53934.9H34260.84241.53974.23924.73912.33686.54351.54038.2H44216.53470.72981.63266.43192.53350.93276.53321H164150.73667.83720.33914.638303789.73955.33876.7H174502.94167.33672.44105.63790.84075.21324.54036H184526.63752.33904.54062.43886.43843.64330.14048.4H1945144196.93505.43670.41349.83749.33935.93807根据上表，我们可以得到各英文碎纸片与之匹配程度最高的碎纸片，进而我们可以得出碎片复原序号为下表6：表6 英文碎片复原序号003006002017015018011000005001009013010008012014017016004根据复原序号，我们用Matlab拼接程序拼接出复原图片见附录。5.2 模型二的建立与求解考虑到问题二附件给我们的图像都是横纵切，所以我们需要提取4条边缘向量；为了简化运算，我们先提取每张图片的左右边缘向量再用Matlab编程得到所有图片中位于整张纸面首列的11张图片，然后用模型一中的方法分别从左向右计算匹配度并连接，得到11个像素为1801368的图像，再提取这11张图像的上下边缘向量进行匹配度计算并把它们连接起来得到最终结果。不过需要注意的是：在从左向右匹配时由于像素小的缘故匹配度的计算精度会比较差，所以我们需要对模型一进行优化。5.2.1 模型的优化我们注意到：当用模型一解决问题二时会发生匹配重复的情况，这主要是由于部分图像的左右边缘是空白的，与其匹配度高的图像很多但却不一定是正确的匹配。所以我们通过matlab编程计算每一个图像的每一行的像素点灰度值之和并画出行灰度值变化图来确定行与行之间的间距，并把这个指标作为图像匹配的约束条件。如下图所示为图像146和图像135行灰度值的变化图： 图3 146碎片像素变化 图4 135碎片像素变化用模型一对上述两个图计算匹配度发现匹配程度非常高，但是通过观察灰度变化图我们可以确定这两个图不可能在同一行。所以在确定一个像素阈值后我们可以通过matlab编程排除掉上述两个图匹配错误的情况。5.2.2模型二的求解流程图在对模型进行优化后，我们可以初步得到模型二求解的流程图如下图5所示：扫描第i个图像的前10列像素点是否为空白区？记录i209？i递增得到首列图像序号是是否否灰度值按行累加获取第j个首列获取第k个图像得到行间距值记录行间距行间距匹配？记录是K209?k递增否j19?j递增得到图像行分类计算上下边缘向量匹配度并连接图像是是否图55.2.3模型二的求解与结果分析(1) 中文碎纸片的拼接通过观察我们发现中文汉字在形状上属于“方块字”，因此行与行之间的间隔一般是稳定在某一范围之内的，所以可以通过行距的匹配来作为边缘向量匹配的约束条件。具体求解过程如下：Step1：利用Matlab编程确定中文碎片中属于原图最左与最右的图片(代码见附录)，命名为首图Si与尾图Wi(i=1,11)。如下表7所示为中文碎纸片的首图与尾图序号：表7Si71429384961718994125168Wi183643596074123141145176196Step2：利用Matlab编程得到Si和Wi的纵向的行间距分布并遍历其余所有图像，通过假定一个阈值可以分别得到与Si、Wi行间距分布相似的图像(代码见附录)，那么这些图像就与对应的Si和Wi处在同一行，例如：对序号为007的首图计算行间距分布，得到如下表8所示可能与之在同一行的图像序号：表80732344243455356687077849093112126127137138144149153158164166174175196208Step3：利用模型一的算法对已得到的与Si和Wi可能处在同一行的图像分别进行由左向右(Wi是由右向左)的边缘向量匹配，并将匹配度高的图像连接，得到多个像素更大的碎纸片(包含的图片序号见附录)。Step4：根据上一个步骤得到的图像序号列表，我们可以筛选出剩余的没有办法匹配成功的碎纸片序号如下表9：表98172425303546588183878895103118122130132143161167186189190193200这时，我们就需要人工干预：因为筛选出的碎纸片较多，所以我们先逐一假定这些图像为首图，再循环迭代至Step2,最终我们用Matlab编程加上一定的手动匹配将这些碎纸片分别拼接成了7个不同的碎纸片，令为Pi(i=1,2,7)。Pi所包含的图像如下式(括号内数字表示所包含的图像序号)所示：P1=(58)P2=(30)P3=(87)P4=(143,186)P5=(118,190,95)P6=(83,132,200,17)P7=(46,161,24,35,81,189,122,103,130,193,88,167,25,8)然后，我们将这7张图像依次与之前得到的含有Si和Wi的图像相比较，找到与之相匹配的图像并用Matlab编程拼接起来得到了11个像素为1801368的图像。最后再调用一次模型一的算法计算这11个图像的上下边缘匹配度，将这11个图像拼接完成后得到最终结果。如下表10为复原后的碎片序号排序：表10 中文碎片序号复原排序049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123根据复原序号，我们用Matlab拼接程序拼接出复原图片见附录。(2) 英文碎纸片的拼接通过观察，我们发现由于英文字母的高度有高有低并且相差较大，所以考虑行距的匹配情况要比中文复杂得多。我们随机选取一个碎纸片，作出它的灰度值的纵向变化曲线如下图6所示：图6根据上图我们可以发现：由于字母“d”和字母“g”的存在，空白区的灰度值不再稳定于一个特定值，而是发生了跳变，因此我们对英文字母的灰度矩阵实施二值化操作：假定一个阈值，当某一行的灰度值和小于这个阈值时，我们将这一行的灰度值令为0.以此保证空白区的灰度值稳定。不过这也导致了在用Matlab求与首图间距分布类似的其他图像时得到的结果误差很大。同时能够匹配的图像很少。所以需要的人工干预也较多。具体求解过程如下：Step1：利用Matlab编程确定英文碎片中属于原图最左与最右的图片(代码见附录)，命名为首图Sj与尾图Wj(j=1,11)。如下表11所示为英文碎纸片的首图与尾图序号：表11Sj1920708186132208159171191201Wj314482109112115127143146147178Step2：首先利用Matlab编程得到Sj和Wj的纵向的行间距分布，然后用Matlab编程遍历其余所有图像，可以分别得到与Sj、Wj行间距分布相似的图像(代码见附录)，那么这些图像就与对应的Sj和Wj处在同一行，例如：对序号为019的首图计算行间距分布，得到如下表12所示可能与之在同一行的图像序号：表12101819224244555663748283858788899397121124128134139141151152155157165171176182183194205176182183194205Step3：利用模型一的算法对已得到的与Sj和Wj可能处在同一行的图像分别进行由左向右(Wj是由右向左)的边缘向量匹配，并将匹配度高的图像连接，得到多个像素更大的碎纸片(包含的图片序号见附录)。Step4：根据上一个步骤得到的图像序号列表，我们可以筛选出剩余的没有办法匹配成功的碎纸片序号(见附录)，共有84个。这时，我们就必须要人工干预：因为筛选出的碎纸片非常多，所以我们首先要逐一假定这些图像为首图，再循环迭代至Step2,最终我们用Matlab编程加上手动拼接的方式将这些碎纸片分别拼接成了11个不同的碎纸片，令为Pj(j=1,2,11)。Pj所包含的图像如下式(括号内数字表示所包含的图像序号)所示：P1=(9)P2=(150,5,59)P3=(164,78,103,91)P4=(69,167,163,166,188)P5=(3,130,34,13,110,25)P6=(195,8,47,172,156,96,23,99,122)P7=(184,2,104,180,64,106,4,149,32,204,65)P8=(33,142,168,62,169,54,192,133,118,189,162)P9=(88,121,126,105,155,114,176,182,151,22,57) P10=(139,1,129,63,138,153,53,38,123,120，175,85,50,160,187) 然后，我们将这11张图像依此与之前得到的含有Sj和Wj的图像相比较，找到与之相匹配的图像并用Matlab编程拼接起来得到了11个像素为1801368的图像。最后再调用一次模型一的算法计算这11个图像的上下边缘匹配度，将这11个图像拼接完成后得到最终结果。如下表13为复原后的碎片序号排序：表13 英文碎片序号复原排序191075011154190184002104180064106004149032204065039067147201148170196198094113164078103091080101026100006017028146086051107029040158186098024117150005059058092030037046127019194093141088121126105155114176182151022057202071165082159139001129063138153053038123120175085050160187097203031020041108116136073036207135015076043199045173079161179143208021007049061119033142168062169054192133118189162197112070084060014068174137195008047172156096023099122090185109132181095069167163166188111144206003130034013110025027178171042066205010157074145083134055018056035016009183152044081077128200131052125140193087089048072012177124000102115根据复原序号，我们用Matlab拼接程序拼接出复原图片见附录。5.3 模型三的建立与求解考虑到附件5给我们的碎纸片都是双面的，我们可以得出这样一个初步结论：当某一碎纸片i与另一碎纸片j能够拼接，说明i的两面都能与j的两面相匹配。因此，我们可以在模型二的基础上再进行优化，即：在模型二计算欧氏距离的基础上加上另外一块纸片的匹配度计算。5.3.1模型二中欧氏距离的优化在附件5给出的数据中，给出了西文的碎图，且分为a,b两面，那么我们可以对连接方式进行以下讨论1)同向连接图7如上图7所示，当图片节点i与j的匹配连接时，要经过两次匹配，即正面匹配和反面匹配。上图情况给出的是同向连接。此时欧式距离D的优化计算式如下：D同ij=Djb-ib2+Dia-ja22)异向连接图8如上图8，当图片节点i与j的匹配连接时，要经过两次匹配，即正面匹配和反面匹配。上图情况给出的是异向连接。此时欧式距离D的优化计算式如下：D异ij=Dja-ib2+Dia-jb2易知，当欧式距离越小时，匹配程度越好，拼接结果越能接近我们的要求。故取Dij=Min(D同ij,D异ij)5.3.2 模型三的求解过程Step1 利用Matlab编程载入附件5中所有图像的灰度矩阵H；Step2 利用Matlab编程获取灰度矩阵的边缘向量L和R；Step3 逐一计算所有图像节点i与j两种连接方式(即同向连接和异向)的欧式距离D，取其据最小录入匹配矩阵；Step4 调用模型二进行求解，计算得到的结果如下表14与表15所示：表14正面碎纸片序号排序136a047b020b164a081a189a029b018a108b066b110b174a183a150b155b140b125b111a078a005b152b147b060a059b014b079b144b120a022b124a192b025a044b178b076a036b010a089b143a200a086a187a131a056a138b045b137a061a094a098b121b038b030b042a084a153b186a083b039a097b175b072a093b132a087b198a181a034b156b206a173a194a169a161b011a199a090b203a162a002b139a070a041b170a151a001a166a115a065a191b037a180b149a107b088a013b024b057b142b208b064a102a017a012b028a154a197b158b058b207b116a179a184a114b035b159b073a193a163b130b021a202b053a177a016a019a092a190a050b201b031b171a146b172b122b182a040b127b188b068a008a117a167b075a063a067b046b168b157b128b195b165a105b204a141b135a027b080a000a185b176b126a074a032b069b004b077b148a085a007a003a009a145b082a205b015a101b118a129a062b052b071a033a119b160a095b051a048b133b023a054a196a112b103b055a100a106a091b049a026a113b134b104b006b123b109b096a043b099b表15反面碎纸片序号排序078b111b125a140a155a150a183b174b110a066a108a018b029a189b081b164b020a047a136b089a010b036a076b178a044a025b192a124b022a120b144a079a014a059a060b147a152a005a186b153a084b042b030a038a121a098a094b061b137b045a138a056b131b187b086b200b143b199b011b161a169b194b173b206b156a034a181b198b087a132b093a072b175a097a039b083a088b107a149b180a037b191a065b115b166b001b151b170b041a070b139b002a162b203b090a114a184b179b116b207a058a158a197a154b028b012a017b102b064b208a142a057a024a013a146a171b031a201a050b190b092b019b016b177b053b202a021b130a163a193b073b159a035a165b195a128a157a168a046a067a063b075b167a117b008b068b188a127a040a182b122a172a003b007b085b148b077a004a069a032a074b126b176a185a000b080b027a135b141a204b105a023b133a048a051b095a160a119a033b071b052a062a129b118b101a015b205a082b145a009b099a043a096b109a123a006a104a134a113a026b049b091a106b100b055b103a112a196b054b根据上述两个表格中碎纸片的序号排列，用Matlab编程得到复原图片见附录。六、 模型评价与推广6.1 模型的评价6.1.1模型的优点(1) 模型一建立了基于灰度匹配的模型，将抽象的问题数字化，有利于理解和解决。(2) 模型二引入了二值化处理英文字母的灰度矩阵，有效地减小了计算误差。6.1.2 模型的缺点(1) 本题用到的灰度匹配模型精度较小，依赖于人工干预，适用范围太小。(2) 模型中用欧氏距离描述匹配度，导致计算复杂度加大。6.2 模型的改进第三问的模型可以用遍历英文字母的方法解决，即判断两图片相交部分是否为合法的英文字母表示形式，当然在本题中由于我们发现图片中同样的英文字母有时灰度矩阵也不同，所以本题还需要先对遍历英文字母的算法进行优化，让算法在一定范围内进行，而不是固定某一值。6.3 模型的推广本题的碎纸片复原是基于边缘内容的，如果对模型优化让其还可以基于边缘轮廓，那么本模型的适用范围将扩大很多，例如：对破损文物的拼接复原。七、 参考文献1 陈恩水，王峰，数学建模与实验M，北京：科学出版社，2008年6月：1-9。2 宋来忠，王志明，数学建模与实验,北京：科学出版社,2005：1-100。3 陈杰,MATLAB宝典，北京：电子工业出版社，2008年200-300。4 罗智中，基于文字特征的文档碎纸片半自动拼接，计算机工程与应用， 48（5）：207-210，2012。5 王正盛，Matlab与科学计算M,北京:国防工业出版社，2011年3月：1-100。 附录附件一复原图片附件二复原图片附件三复原图片附件四复原图片附件五复原图片正面反面代码modalCh.mclear all;clc;%自动生成附件1的拼接方式，将附件1改成附件2即可得到附件2的拼接方式I0=imread(D:附件1000.bmp);I1=imread(D:附件1001.bmp);I2=imread(D:附件1002.bmp);I3=imread(D:附件1003.bmp);I4=imread(D:附件1004.bmp);I5=imread(D:附件1005.bmp);I6=imread(D:附件1006.bmp);I7=imread(D:附件1007.bmp);I8=imread(D:附件1008.bmp);I9=imread(D:附件1009.bmp);I10=imread(D:附件1010.bmp);I11=imread(D:附件1011.bmp);I12=imread(D:附件1012.bmp);I13=imread(D:附件1013.bmp);I14=imread(D:附件1014.bmp);I15=imread(D:附件1015.bmp);I16=imread(D:附件1016.bmp);I17=imread(D:附件1017.bmp);I18=imread(D:附件1018.bmp);I=I0,I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I18;for i=1:19 II(:,i*2-1:i*2-1)=I(:,(i-1)*72+1:(i-1)*72+1); II(:,i*2:i*2)=I(:,i*72:i*72);endII=double(II);for l=1:19for j=1:19 sum=0;for k=1:1980 sum=sum+(II(k,(l*2)-1)-II(k,j*2)*(II(k,(l*2)-1)-II(k,j*2);end pp(l,j)=sqrt(double(sum);endendmin=1000000;start=0;for i=1:19for j=1:19if pp(i,j)min min=pp(i,j); node(i)=j;endendif min=0 start=i;end min=10000