图像匹配问题的模型研究.docx

2013年国防科学技术大学数学建模竞赛培训论文 1A：图像匹配问题 队员1：白谨宁，九院10级， 9-4-3 队员2：李明洋，九院10级， 9-4-3 队员3：时云龙，九院10级， 9-4-3 2013年5月10日 目录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc355827464 摘要 PAGEREF _Toc355827464 \h 3 HYPERLINK \l _Toc355827465 一、问题重述与分析 PAGEREF _Toc355827465 \h 4 HYPERLINK \l _Toc355827466 二、问题假设 PAGEREF _Toc355827466 \h 4 HYPERLINK \l _Toc355827467 三、符号说明 PAGEREF _Toc355827467 \h 5 HYPERLINK \l _Toc355827468 四、模型建立与求解 PAGEREF _Toc355827468 \h 5 HYPERLINK \l _Toc355827469 4.1模型的建立 PAGEREF _Toc355827469 \h 5 HYPERLINK \l _Toc355827470 4.2模型的求解 PAGEREF _Toc355827470 \h 6 HYPERLINK \l _Toc355827471 五、模型的进一步讨论 PAGEREF _Toc355827471 \h 11 HYPERLINK \l _Toc355827472 六、模型优缺点 PAGEREF _Toc355827472 \h 12 HYPERLINK \l _Toc355827473 七、附录 PAGEREF _Toc355827473 \h 12  图像匹配问题的模型研究 摘要 这是一个匹配问题的建模研究。关于匹配问题，有很多经典的算法如模板匹配法。但模板匹配法仅能处理平移的问题，这一问题中既有平移又有旋转，因此我们考虑先找出几个匹配的特殊点，以此为突破口再寻找所有点的匹配关系。 特殊点的寻找我们考虑了寻找全等三角形的方法。通过在两个点集中寻找全等三角形，确定三角形顶点的对应关系，这样就有了三个能够正确对应的点，也就找到了突破口。 对于其他所有的点，有两种方法来确定对应关系。一种是根据全等三角形坐标的对应关系，将点集一进行坐标变换，旋转和平移到点集二，再将两个点集中的点进行比对。这种方法理论上没有问题，实际操作时会产生有较大的误差。于是我们引入了另一种方法，在处理其它点时不用坐标旋转和平移，而只计算距离。用任一点与三角形三个顶点的相对位置关系来确定对应关系。这样避免了求解过程产生的误差。从计算结果来看，这一方法也得到了比较好的效果。 关键词：匹配，全等三角形，坐标变换，相对位置  一、问题重述与分析 比较不同时间采集同一景物的两幅图像，或者同一时间由不同传感器采集的两幅图像，在众多领域，如：在检测变化方面（森林学、医学、国防）、注册与验证（卫星图像、地图、指纹）以及立体成像方面都有重要应用。其一般方法是在两幅图像中采用一定的方法抽取特征点，对特征点进行匹配。 现设第一个点集有m个点，第二个点集有n个点，第二个点集是第一个点集经过某个平移和旋转得到，但由于噪声的作用，点的相对位置有微小的变化，而且第一个点集中可能有部分点（称为缺少点）在第二个点集中找不到对应点，第二个点集中可能随机出现一些新的点（称为伪点），通常m和n的大小范围为从30到400之间。试就只有平移和既有平移又有旋转两种情形，设计模型与算法，解决以下三个问题： (ⅰ) 找到第一个点集中所有的在第二个点集中没有匹配的点； (ⅱ) 找到第二个点集中所有的在第一个点集中没有匹配的点； (ⅲ) 对有匹配的点，找出正确的对应关系。 本题要求对给出的两个点集进行匹配，并找出第二个点集中的缺少点和伪点。在点集的坐标已知的情况下，如果能首先确定两个点集中几个特殊点的对应关系，那么其他的点就都可以根据它与这几个特殊点的位置关系来找到对应的点。因此，问题就可以分为两步来解决：第一步，确定几个特殊的点的对应关系；第二步，根据与这些特殊点的位置关系寻找其他点的对应点。而特殊点的个数至少要有三个才能以此确定其它点的位置，因此我们考虑寻找两个点集中的全等三角形，以此来确定特殊点。 在确定其它点的对应关系时，可以考虑两种方法。一种是进行坐标的旋转和平移变换，另一种是计算其它点与三角形的相对位置。而考虑到由于噪声的存在，坐标的旋转会产生较大的误差，因此用计算相对位置的方法求解对应关系。 二、问题假设 假设一：两幅图像之间只存在平移和旋转的变换，而不存在拉伸和压缩变换； 假设二：噪声只对极少部分点产生较大的影响； 假设