数学建模拼图问题论文

1、2014年河北工业大学数学建模竞赛题目： 图片拼接问题 参赛队员信息： 姓 名所在学院班级学号参赛队员1寇如意计算机学院软件121122070参赛队员2焦孟云经管学院会计123121577参赛队员3杨航经管学院信管121121697图片拼接问题摘要 本题是图片拼接问题，主要运用MATLAB软件对碎片上下左右边界的拼接关系进行处理。首先是给出的图片为彩色图片，需要对图片进行灰度处理。其次是需要提取处理后的灰度图的像素点矩阵，方便分析碎片边界之间的衔接关系。由于问题一中给出了原始图而问题二中没有给出，所以对于问题一与问题二建立的模型是不相同的。 对于问题一，原始图片不能均等的分割出相等的16份碎片

2、，因此使得碎片的像素不同但是差别不是很大。因此为了方便以后的的相似度对比，我们可以将原始图以及碎片的大小利用imresize函数进行像素改变，将原始图片尺寸改变成，将16个碎片的大小都改变成。利用imread函数提取灰度处理后的原始图片以及附件一中碎片的像素点矩阵。将原始图的像素点矩阵平均分成16个子矩阵，将这16个子矩阵与附件一中给出的16个碎片提取的矩阵进行相似的对比，最终确定各碎片在原始图中的位置。得出复原结果。 对于问题二，没有给出原始图，因此不能用与原始图比对的方法建立模型和拼接。在这一问中首先我们通过进行像素点矩阵的提取得到。然后该问题需要进行两层筛选排序，第一层是进行行处理，得出

3、按行分类的四类碎片集合，在进行内部行排序。取出第张碎片的第一列存入矩阵中；取剩余的碎片的最后一列存入到矩阵中，计算与的相似度并从中选出最大值即为在同一层并且相邻的两张碎片，得到每层的邻接矩阵。第二层是列处理，对第选出已排好的四层的最左碎片的第一行行向量存入以及最后一行行向量存入中，分别进行相似度比较，排好上下关系。综合一二两步就可以复原图片。关键词：MATLAB软件 灰度处理 像素点矩阵 imresize函数 相似度 两层筛选排序 邻接矩阵1、问题重述破碎图像的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率虽较高，但效率很低。当

4、碎片数量巨大，人工拼接很难在短时间内完成任务，有时甚至无法完成。随着计算机技术的发展，人们试图开发破碎图像的自动拼接技术，以提高拼接复原效率。对于一张图片破碎后的各张图像的拼接，需建立图像的拼接复原模型和算法，并针对附件中的图像数据进行拼接复原。本文主要讨论：首先，对于给定原始图像的碎片，如何对附件1中整齐划割的图像进行拼接复原。复原过程不需要进行人工干预。复原结果以图片形式及表格形式表达。然后，对于未给定原始图像的碎片，如何对附件2中整齐划割的图像进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。2、问题分析破碎图像的复原，最直接而精确的办法就是人

5、工拼接，但是当碎片的数量巨大时，人工方式就显得效率低下，有时无法完成。所以，需要考虑把破碎图像的信息量化，运用计算机技术来帮助人们进行破碎图像的筛选，必要时加入适当的人工操作，用以完成破碎图像的拼接复原。问题一与问题二都是碎片复原问题，两个问题的区别就在于：问题一中有原始图，问题二中没有原始图，因此两个问题模型的建立也有一定的差异。 1、问题一题一是对于给定原始图像的碎片进行拼接复原。首先是利用MATLAB软件对给的碎片以及原始图转换成.png格式并进行灰度处理。将新处理出来的灰色图像的大小利用MATLAB中的imresize函数将原始图片尺寸改变成，将16个碎片的大小都改变成，这时新的原始图

6、片就可以均匀的分成16块大小的碎片。利用imread函数提取灰度处理后的原始图片以及附件一中碎片的像素点矩阵参考文献：1 汪晓银. 数学建模与数学实验M. 北京：科学出版社，2009.。将原始图的像素点矩阵平均分成16个子矩阵，将这16个子矩阵与附件一中给出的16个碎片提取的矩阵进行相似的对比，最终确定各碎片在原始图中的位置。拼接出最后的图像与原始图进行对比检验模型的结果。充分利用了给出的原始图，没有人工干预。 2、问题二是分析附件二所给的16片图像碎片，既有横向切割，又有纵向切割，且16片图像为规则的正方形。那么在拼接图像时需要两个方面的考虑，即横向的匹配拼接和纵向的匹配拼接。灰度处理每一张

7、碎片并进行像素点矩阵的提取得到。该问题需要进行两层筛选排序，第一层是筛选出在同一行的碎片并进行行内部的排序。任意选取一张碎片，取出第张碎片的第一列存入矩阵中；取剩余的碎片的最后一列存入到矩阵中，计算与的相似度并从中选出最大值即为在同一曾并且相邻的两张碎片。循环上述过程，找出在同一层的四张图片并且左右相接关系拍好。在进行第二层的排序，选出已排好的四层的最左碎片的第一行行向量存入以及最后一行行向量存入中，分别进行相似度比较，排好上下关系。综合第一层和第二层的排序就可以得到最终的复原图形。在这一问中，需要人工干预选出一张碎片让其他碎片进行比对排序。3、问题假设1、 假设图片的碎片四边都是直线，无折损

8、和缺口；相邻的两个碎片可以完全重合。2、 假设图片的方向已经确定，按照阅读习惯，从左向右，自上而下，不考虑碎片图像的旋转问题。3、 假设图片是由原图4*4切割的；即同一行的碎片等宽，同一列的碎片等长。3、假设附件一中的16块碎片大小相近，改变图片尺寸不会影响最终结果。4、假设附件二中的16块碎片的大小完全一样。5、假设原始图的像素改变一个较小的值不会影响最终的复原图。4、符号含义 ： 从第张图片中提取出来的像素点矩阵（为原始图）； ： 从处理完的原始图分割的16张图中提取出来的像素点矩阵； ： 相似度系数，两个等维矩阵的相似程度；5、模型的建立5.1模型建立的准备1、将附件一和附件二中给出的给

9、图片有.bmp格式转换成.png格式。对新转换成的图片进行灰度处理即，将给出的彩色图片转换成灰度图。灰度图像在黑色与白色之间还有许多级的颜色深度，这些颜色深度在矩阵中体现在矩阵的元素值在0-255之间。2、对于问题一将第一步中已经转化成灰度图的图片或碎片进行大小的改变。由于附件一给出的碎片的像素各不相同，原始图不是均匀的分成等大的16份，而且改变的像素相对于整体像素而言很小。所以在不影响最终结果的前提下我们可以简单的改变一下灰度处理以后的原始图以及碎片图片的大小。使原始图改变为像素的灰度图像，使16张不等大的碎片都变成像素的碎片。3、利用MATLAB中的imread函数算法，从处理完的灰度图片

10、中提取像素点矩阵存入到中。并且将问题一中的原始图的像素点矩阵平均分成16份。5.2 问题一模型的建立1、首先需要对给出的图片进行灰度处理，将给出的彩色图片转换成灰度图。在MATLAB中灰度处理的函数为： 2、灰度处理后的图片需要改变大小方便进行相似度的对比。原始图片不能均等的分割出相等的16份碎片，因此使得碎片的像素不同但是差别不是很大。因此为了方便以后的的相似度对比，我们可以将原始图以及碎片的大小利用函数进行改变，使得原始图可以均等的分成16份，而碎片的像素也变成相同的以便以后的对比处理。 在MATLAB中改变图片的大小的函数： numrows和numcols分别指定目标图像的高度和宽度。

11、显而易见， 由于这种格式允许图像缩放后长宽比例和源图像长宽比例不相同，因此所产生的图像有可能发生畸变。但是由于减少的像素值相对于总的像素值而言比较小，所以这种改变不会对最终的结果产生影响。3、处理好的碎片中提取出的像素点矩阵与由平均分成的16份两两进行相似度的计算。用MATLAB中的相似度求取的函数： ：相似度系数。其中的与矩阵行数与列数都是相同的。求出的相似度系数大小可以衡量与矩阵的相似程度，从而知道碎片与从原始图中切割出的图片的相似程度，确定出碎片在原始图中的位置。代表完全不相关，代表完全相关。的值越小代表两矩阵之间的相似程度越差，反之则越好2 相关系数百度百科 2014年8月20日2。5

12、.3 问题一模型求解 应用MATLAB软件，先用rbg2gry()函数将彩图处理成灰度图像，再用imresize（）函数改变原始图以及碎片的大小。最后用imread（）读取修改大小后的图片的像素点矩阵=。对原始图读取的矩阵进行均匀分割成16个子矩阵（等大的碎片）即：=其中、。从附件一中给出的碎片中读出的矩阵与进行相似度计算。例如：附件一中01-01读出的矩阵与切割出的16个子矩阵进行比较（运行程序见附件一），得出的结果如下表一：12345678 -0.0056-0.4115-0.4490-0.26320.6820-0.37020.1484-0.04929101112131415160.8668

13、-0.4008-0.04260.72240.48810.37480.9789-0.0872中是分割原始图得到的分别与的相似度系数从表中我们可以看出附件一给出的碎片01-01与切割原始图得到的碎片中的第十五块的相似度最大，也就是说碎片01-01在原始图的第十五块所在的位置。用同样的方法可以算出每一个碎片在原始图中的位置（程序见附见二）。通过对比得到附件一中的碎片与原始图的切割碎片的对应关系（运算结果见附录一），得到如下结果：表二：1234501-1501-0901-1201-0401-0567891001-1101-0701-0801-0201-10111213141501-0601-0301-

14、1301-1401-011601-16根据表二可以得到图片的复原结果：表格形式：01-1501-0901-1201-0401-0501-1101-0701-0801-0201-1001-0601-0301-1301-1401-0101-16图片形式：5.4问题二模型的建立 将转化好格式的碎片进行灰度处理并提取其像素点矩阵存入中，从提取出来的每一个矩阵的第一列以及最后一列存入到和中。利用（3）式分别进行两两相似度对比，按行进行分类和行内部的排序。排好的碎片取出第一行行向量存入以及最后一行行向量存入中，分别进行相似度比较，排好上下关系。具体流程图如下：5.5问题二模型求解 1、在进行按行的分类以及

15、行内排序时因为数据比较多（具体数据见附录二），取其中的一个为例。例如：取出第一张碎片的第一列存入中，取其他几张碎片的最后一列存入中。和的相似度如下表所示：表三：02-0202-0302-0402-0502-06-0.75870.7613-0.71160.5089-0.359002-0702-0802-0902-1002-110.9851-0.19290.030702223-0.799902-1202-1302-1402-1502-160.27620.3144-0.53230.42000.5249从表格中筛选出相似度最大，由表格三可以看出第一张碎片像素点矩阵的第一列与第七张碎片像素点矩阵的最后一

16、列相似度最大。所以02-01与02-07在同一层且07在01的左侧。用同样的方法处理十六张碎片就可以的出如下的对应关系：（其中表格中第一行和第三行表示每张碎片的第一列；第二行与第三行表示没张碎片的最后一列）表四：02-0102-0202-0302-0402-0502-0602-0702-08最大相似度0.98510.89650.93450.97690.55560.96740.95630.8933对应碎片7814102412402-0902-1002-1102-1202-1302-1402-1502-16最大相似度0.83320.70260.97380.91060.53790.77940.985

17、30.9787对应碎片4915591323表中数据出现重复的情况，此时进行人工干预。根据表格中最大相似度可以看出：02-05、02-08、02-09、02-13的最大相似度比较小，因此这四张碎片位于原图的第一列。行内根据上述表格中的对应关系可以构成邻接矩阵：表五：02-0502-1202-0702-0102-0802-0202-1502-1102-0902-1002-0402-0602-1302-1402-0302-162、进行列排序时： 将02-05、02-08、02-09、02-13四张碎片的第一行和最后一行向量分别存入和中，对和进行相似度计算得出四张碎片上下邻接关系（相似度计算结果见附录

18、）。取与的相似度计算结果表格为例：表六：02-0802-0902-130.98950.67660.4766 从表中可以看出02-05这张碎片的上边与02-08的下边的相似度很高，所以第五张与第八张为上下邻接关系。根据其他的上下边的相似度得出四张图片的上下邻接关系（运算结果见附录三）通过四张碎片两两比较就可以得到四张碎片的上下邻接关系为：02-0802-0502-0902-13 对比上述两步的结果就可以得出图片的复原结果：表格形式02-0802-0202-1502-1102-0502-1202-0702-0102-0902-1002-0402-0602-1302-1402-0302-16图片形式

19、6、模型结果检验 本题建立的模型成功的将问题一与问题二的碎片拼接复原。我们将这一模型应用到其他的碎片拼接上，同样的到了最终的复原图。因此本题建立的模型是正确的。7、模型的优点与不足7.1、优点：（1）、充分的运用了计算机技术，大大节约了用人工拼接的时间和资源。用MATLAB软件碎片进行拼接复原不仅可以节约人力物力，而且使运算变得简便、快捷。3 姜启源. 数学模型（第四版）M. 北京：高等教育出版社，2010 年. 附录一：1234567801-01 -0.0056-0.4115-0.4490-0.26320.6820-0.37020.1484-0.049201-020.0287-0.2351-

20、0.4058-0.41170.6845-0.13280.2297-0.231301-03-0.20340.89930.2333-0.09650.68140.4441-0.05150.008901-040.0728-0.1884-0.3906-0.5037-0.4074-0.31610.2746-0.121801-050.0287-0.2351-0.4058-0.41170.9814-0.13280.2297-0.231301-060.0285-0.5170-0.4245-0.20380.0388-0.47060.1194-0.076901-07-0.01650.0421-0.1968-0.26

21、490.2571-0.02400.4013-0.068901-08-0.1759 0.32990.27420.0509-0.23600.5743-0.1240-0.096701-090.0399-0.3469-0.2281-0.2178-0.2470-0.17500.2170-0.110301-10 0.0539-0.4243 -0.3742-0.1410-0.2645-0.33270.0976-0.097901-11-0.0154-0.0515-0.2344-0.3079-0.1339-0.09370.9438-0.064601-12 -0.11210.42840.2016-0.0230-0

22、.41490.9358-0.0857-0.169301-130.7326-0.2026-0.05510.15270.6057-0.14510.0074-0.016701-14 0.1610-0.0989 0.18880.74210.4302-0.0136-0.26840.105601-15-0.01280.01090.10350.10720.0414-0.1550-0.06260.498501-16-0.06070.2204 0.64590.1914-0.21920.2558-0.21590.0673 91011121314151601-010.8668-0.4008-0.04260.7224

23、0.48810.37480.9789-0.087201-020.6797-0.25460.03110.67810.58860.42590.6860-0.243001-03-0.53500.35570.0478-0.4376-0.1734-0.3407-0.4292-0.162201-040.4941-0.34310.28960.41160.94490.40250.52440.024601-050.6797-0.25460.03110.67810.58860.42590.6860-0.243001-060.9872-0.4816-0.12110.77840.46810.48330.87930.0

24、42201-07-0.10830.00240.9451-0.18050.29880.0478-0.03540.123601-08-0.49210.82710.0023-0.4162-0.3331-0.2299-0.4176-0.192601-090.4970-0.24350.02820.46030.38080.82690.3907-0.023801-100.7788-0.3993-0.18290.97220.39200.45590.73290.151001-110.1337-0.13110.43350.10620.30300.22330.17190.074501-12-0.47740.5591

25、-0.0153-0.3337-0.2956-0.1724-0.3833-0.281001-130.0416-0.1808-0.01510.07170.08240.05390.00760.151001-14-0.20400.0364-0.2659-0.1263-0.5123-0.1994-0.26800.136701-15-0.0871-0.0768-0.0617-0.0948-0.1339-0.1024-0.05780.100301-16-0.44910.3043-0.1585-0.3907-0.4130-0.2704-0.46940.1059（表格的行代表由原始图切割形成的矩阵，列代表碎片提

26、取出来的像素点矩阵）附录二：02-0102-0202-0302-0402-0502-0602-0702-0802-01NaN-0.75870.7613-0.71160.5089-0.35900.9851-0.192902-020.8965-0.6701NaN-0.42070.50790.0861-0.2748-0.244902-030.0101-0.35030.5184NaN0.2950-0.26640.4979-0.498702-04-0.20940.03980.13090.1808NaN0.04100.6925-0.158002-05-0.1349-0.23610.5556-0.35000

27、.1454NaN0.3426-0.378102-060.3182-0.57200.6258-0.86170.9674-0.7272NaN-0.792602-070.17490.0614-0.3716-0.05520.2862-0.1376-0.2302NaN02-08NaN0.5973-0.48940.6930-0.89330.46130.00710.571702-09-0.44600.7133-0.71580.7429-0.83320.3815-0.22180.807102-100.1235-0.0736-0.00590.0833-0.15740.3784-0.20210.262502-11

28、0.10780.0271-0.42670.4775-0.49380.2746-0.35620.409102-120.08680.1056-0.26220.5845-0.66580.9106-0.02960.411602-13-0.04590.2091-0.34380.2204-0.0767-0.1236-0.10260.359302-140.5441-0.1579-0.37750.08230.02750.2309-0.19390.319802-150.1614-0.50010.9853-0.66590.6060-0.38360.3539-0.761302-16-0.37320.5388-0.6

29、1030.9787-0.84130.6432-0.06960.756902-0102-0202-0302-0402-0502-0602-0702-0802-010.030702223-0.79990.27620.3144-0.53230.42000.524902-020.0657-0.15840.30900.27140.50400.0838-0.17110.087202-03-0.04390.40920.2246-0.3264-0.27660.9345-0.22520.001502-040.00280.9769-0.1628-0.3149-0.10610.4191-0.03410.364602

30、-050.07160.12040.3000-0.5464-0.39110.4837-0.0650-0.294102-06-0.1392-0.05510.88480.2214-0.08550.3547-0.5632-0.545202-07-0.2255-0.32370.03010.95630.5111-0.3179-0.35340.012902-080.08770.0896-0.6807-0.4964-0.1427-0.26970.62140.313302-09NaN-0.1797-0.7172-0.05490.1582-0.53610.54400.304102-100.7026NaN-0.1355-0.0037-0.0981-0.07870.00930.053502-11-0.1426-0.0400NaN-0.3116-0.0216-0.24920.97380.553002-120.33030.1930-0.6006NaN0.0677-0.16380.25640.483102-13-0.5379-0.2318-0.14780.4703NaN-0.25780.08090.145602-14-0.1044-0.0704-0.14630.50360.7794NaN0.