图像匹配问题的模型研究

《图像匹配问题的模型研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2013年国防科学技术大学数学建模竞赛培训论文1A：图像匹配问题队员1：白谨宁，九院10级，9-4-3队员2：李明洋，九院10级，9-4-3队员3：时云龙，九院10级，9-4-32013年5月10日目录摘要3一、问题重述与分析4二、问题假设4三、符号说明5四、模型建立与求解54.1模型的建立54.2模型的求解6五、模型的进一步讨论11六、模型优缺点12七、附录12图像匹配问题的模型研究摘要这是一个匹配问题的建模研究。关于匹配问题，有很多经典的算法如模板匹配法。但模板匹配法仅能处理平移的问题，这一问题中既有平移又有旋转，因此我们考虑先找出几个匹配的特殊点，以此为突

2、破口再寻找所有点的匹配关系。特殊点的寻找我们考虑了寻找全等三角形的方法。通过在两个点集中寻找全等三角形，确定三角形顶点的对应关系，这样就有了三个能够正确对应的点，也就找到了突破口。对于其他所有的点，有两种方法来确定对应关系。一种是根据全等三角形坐标的对应关系，将点集一进行坐标变换，旋转和平移到点集二，再将两个点集中的点进行比对。这种方法理论上没有问题，实际操作时会产生有较大的误差。于是我们引入了另一种方法，在处理其它点时不用坐标旋转和平移，而只计算距离。用任一点与三角形三个顶点的相对位置关系来确定对应关系。这样避免了求解过程产生的误差。从计算结果来看，这一方法也

3、得到了比较好的效果。关键词：匹配，全等三角形，坐标变换，相对位置一、问题重述与分析比较不同时间采集同一景物的两幅图像，或者同一时间由不同传感器采集的两幅图像，在众多领域，如：在检测变化方面（森林学、医学、国防）、注册与验证（卫星图像、地图、指纹）以及立体成像方面都有重要应用。其一般方法是在两幅图像中采用一定的方法抽取特征点，对特征点进行匹配。现设第一个点集有m个点，第二个点集有n个点，第二个点集是第一个点集经过某个平移和旋转得到，但由于噪声的作用，点的相对位置有微小的变化，而且第一个点集中可能有部分点（称为缺少点）在第二个点集中找不到对应点，第二个点集中可能随机

4、出现一些新的点（称为伪点），通常m和n的大小范围为从30到400之间。试就只有平移和既有平移又有旋转两种情形，设计模型与算法，解决以下三个问题：(ⅰ)找到第一个点集中所有的在第二个点集中没有匹配的点；(ⅱ)找到第二个点集中所有的在第一个点集中没有匹配的点；(ⅲ)对有匹配的点，找出正确的对应关系。本题要求对给出的两个点集进行匹配，并找出第二个点集中的缺少点和伪点。在点集的坐标已知的情况下，如果能首先确定两个点集中几个特殊点的对应关系，那么其他的点就都可以根据它与这几个特殊点的位置关系来找到对应的点。因此，问题就可以分为两步来解决：第一步，确定几个特殊的点的对应关系

5、；第二步，根据与这些特殊点的位置关系寻找其他点的对应点。而特殊点的个数至少要有三个才能以此确定其它点的位置，因此我们考虑寻找两个点集中的全等三角形，以此来确定特殊点。在确定其它点的对应关系时，可以考虑两种方法。一种是进行坐标的旋转和平移变换，另一种是计算其它点与三角形的相对位置。而考虑到由于噪声的存在，坐标的旋转会产生较大的误差，因此用计算相对位置的方法求解对应关系。二、问题假设假设一：两幅图像之间只存在平移和旋转的变换，而不存在拉伸和压缩变换；假设二：噪声只对极少部分点产生较大的影响；假设三：缺少点和伪点不是普遍现象。三、符号说明S1：第一个点集；S2：第二个

6、点集；A、B、C：第一个点集中三角形的三个顶点；X、Y、Z：第二个点集中三角形的三个顶点；l1、l2、l3：第一个点集中三角形的三边长；s1、s2、s3：第二个点集中三角形的三边长；ε：误差范围，对应两条边允许的差值百分比；λ：阈值，匹配过程中允许距离的差值；η：能正确对应的点的比例的下限，低于这一比例则认为对应关系不正确；D1、D2、D3：点集S1中任一点与三角形ABC三个顶点之间的距离；d1、d2、d3：点集S2中任一点与三角形XYZ三个顶点之间的距离。四、模型建立与求解4.1模型的建立对应关系的确立确立坐标的对应关系首先要找到两个点集中相对应的点构成的全等

7、三角形。在第一个点集S1中任取三个点A(a1,a2)、B(b1,b2)、C(c1,c2)构成三条边互不相等的三角形（若有相等的边则重新取点），三边长分别是l1、l2、l3；在第二个点集S2中遍历所有的点，得到三点X(x1,x2)、Y(y1,y2)、Z(z1,z2)构成三角形，边长为s1、s2、s3，将这两个三角形进行比较。给定一个误差范围百分比ε，如果对应边的差值都在这个范围内，就认为两个三角形全等。寻找全等三角形的C++代码见附录代码一。但是考虑到噪声的存在，按照上述方法找到的满足要求的全等三角形有可能不是事实上的对应的三角形。对于这一问题，我们可以先假定他们

8、就是事实上对应的三角形，