数学建模--拼图问题论文.doc

《数学建模--拼图问题论文.doc》由会员分享，可在线阅读，更多相关《数学建模--拼图问题论文.doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 相关系数百度百科 :/baike.baidu /vi

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

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

14、10111213141501-0601-0301-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

15、.5问题二模型求解1、在进展按行的分类以及行内排序时因为数据比较多具体数据见附录二，取其中的一个为例。例如：取出第一张碎片的第一列存入中，取其他几张碎片的最后一列存入中。和的相似度如下表所示：表三：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.9106

17、0.53790.77940.98530.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-

19、0302-16图片形式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

20、.2351-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.196

21、8-0.26490.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.

22、0230-0.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.0426

23、0.72240.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.8

24、7930.042201-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.4774

25、0.5591-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.3

27、5000.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.26250

28、2-110.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

29、-0.61030.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.36

30、4602-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-

31、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.11090.403202-150.23790.15200.6674-0.3244-0.36200.5632NaN-

32、0.514002-16-0.00650.2286-0.8973-0.06750.0692-0.36730.4750NaN表格的行代表每一张碎片像素点矩阵的最后一列，列代表像素点矩阵的第一列附录三：02-0502-0802-0902-1302-05-0.02090.98950.67660.476602-08-0.11740.28680.06530.396802-090.9620-0.02810.31370.045902-130.30820.01350.98260.0057表格中的行代表碎片的最后一行，列代表碎片的第一行.32、该模型在现实生活中有着很大的用途。模型不仅可以复原图片，还可以复原纸片

33、等物品，这点在可以应用到我们的生活中。例如：复原重要文件防止不必要的损失、复原古文物复原历史面貌等方面。7.2、缺乏：1、该模型实在碎片四边整齐，图片是均匀分割的。在这一点上，模型过于理想化。题目提供的附件破碎图像都是均匀的横切或纵切，较为理想化，且按从左到右，从上到下正向摆放，而实际情况中遇到的很多图像碎片是倾斜的、破碎残缺的，不规那么的。故本文建立的模型在推广应用上有一定的局限性。 2、简单的匹配算法准确度可能较低；由于时间原因，对于每个问题只应用一种简单有效的算法，处理方法单一。故可能导致图像匹配的准确程度不高，有时需参加必要的人工干预。当图像碎片数量很多时，会加重人工处理的负担。3、模

34、型应用到现实中时会受到许多外界因素的影响，例如：碎片边缘发生破损、脏污等时，就很难在进展碎片的复原。8、模型的改进与推广8.1.改进方案1优化方案算法，减少模型中的计算量。2提高计算机资源利用率，减少运行时间。3防止冗余代码，在编程过程中尽量考虑调用、循环语句。4防止模型假设的过多束缚如碎片形状规那么，提高适应性。8.2.模型推广除了复原本文所给定附件中的碎片，该模型还可适用于其他图片碎片，表格文档碎片等规那么碎片。对于现实生活中，形状不规那么的碎片，模型应作出适当的调整，充分利用碎片的几何形状，及碎片的边界特征，进展原图的拼接复原。 破碎图像的拼接复原技术还可广泛应用于卫星遥感、海底勘探、地表植被测绘、无人机监视和搜索、机器人视觉、视频监控、医学探查、电子稳像和虚拟现实等领域图像拼接复原。- word.zl-