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

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图像匹配问题的模型研究摘要这是一个匹配问题的建模研究。关于匹配问题，有很多经典的算法如模板匹配法。但模板匹配法仅能处理平移的问题，这一问题中既有平移又有旋转，因此我们考虑先找出几个匹配的特殊点，以此为突破口再寻找所有点的匹配关系。特殊点的寻找我们考虑了寻找全等三角形的方法。通过在两个点集中寻找全等三角形，确定三角形顶点的对应关系，这样就有了三个能够正确对应的点，也就找到了突破口。对于其他所有的点，有两种方法来确定对应关系。一种是根据全等三角形坐标的对应关系，将点集一进行坐标变换，旋转和平移到点集二，再将两个点集中的点进行比对。这种方法理论上没有问题，实际操作时会产生有较大的误差。于是我们引入了另一种方法，在处理其它点时不用坐标旋转和平移，而只计算距离。用任一点与三角形三个顶点的相对位置关系来确定对应关系。这样避免了求解过程产生的误差。从计算结果来看，这一方法也得到了比较好的效果。关键词：匹配，全等三角形，坐标变换，相对位置一、问题重述与分析比较不同时间采集同一景物的两幅图像，或者同一时间由不同传感器采集的两幅图像，在众多领域，如：在检测变化方面（森林学、医学、国防）、注册与验证（卫星图像、地图、指纹）以及立体成像方面都有重要应用。其一般方法是在两幅图像中采用一定的方法抽取特征点，对特征点进行匹配。现设第一个点集有m个点，第二个点集有n个点，第二个点集是第一个点集经过某个平移和旋转得到，但由于噪声的作用，点的相对位置有微小的变化，而且第一个点集中可能有部分点（称为缺少点）在第二个点集中找不到对应点，第二个点集中可能随机出现一些新的点（称为伪点），通常m和n的大小范围为从30到400之间。试就只有平移和既有平移又有旋转两种情形，设计模型与算法，解决以下三个问题：() 找到第一个点集中所有的在第二个点集中没有匹配的点；() 找到第二个点集中所有的在第一个点集中没有匹配的点；() 对有匹配的点，找出正确的对应关系。本题要求对给出的两个点集进行匹配，并找出第二个点集中的缺少点和伪点。在点集的坐标已知的情况下，如果能首先确定两个点集中几个特殊点的对应关系，那么其他的点就都可以根据它与这几个特殊点的位置关系来找到对应的点。因此，问题就可以分为两步来解决：第一步，确定几个特殊的点的对应关系；第二步，根据与这些特殊点的位置关系寻找其他点的对应点。而特殊点的个数至少要有三个才能以此确定其它点的位置，因此我们考虑寻找两个点集中的全等三角形，以此来确定特殊点。在确定其它点的对应关系时，可以考虑两种方法。一种是进行坐标的旋转和平移变换，另一种是计算其它点与三角形的相对位置。而考虑到由于噪声的存在，坐标的旋转会产生较大的误差，因此用计算相对位置的方法求解对应关系。二、问题假设假设一：两幅图像之间只存在平移和旋转的变换，而不存在拉伸和压缩变换；假设二：噪声只对极少部分点产生较大的影响；假设三：缺少点和伪点不是普遍现象。三、符号说明S1：第一个点集；S2：第二个点集；A、B、C：第一个点集中三角形的三个顶点；X、Y、Z：第二个点集中三角形的三个顶点；l1、l2、l3：第一个点集中三角形的三边长；s1、s2、s3：第二个点集中三角形的三边长；：误差范围，对应两条边允许的差值百分比；：阈值，匹配过程中允许距离的差值；：能正确对应的点的比例的下限，低于这一比例则认为对应关系不正确；D1、D2、D3：点集S1中任一点与三角形ABC三个顶点之间的距离；d1、d2、d3：点集S2中任一点与三角形XYZ三个顶点之间的距离。四、模型建立与求解4.1模型的建立对应关系的确立确立坐标的对应关系首先要找到两个点集中相对应的点构成的全等三角形。在第一个点集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+代码见附录代码一。但是考虑到噪声的存在，按照上述方法找到的满足要求的全等三角形有可能不是事实上的对应的三角形。对于这一问题，我们可以先假定他们就是事实上对应的三角形，按下文建立的模型方法求出对应关系，确定点的对应关系，这时如果能够对应的点很少，就可以确定全等三角形不是真正对应的；如果最终对应的点的数量超过某一个比例，就可以认为最初全等三角形的对应关系是正确的，最终所有点的对应关系也是正确的。对应点的匹配在确定了全等三角形的基础上，计算S1中任一点与这三个点A、B、C之间的距离D1、D2、D3，在S2中计算所有点到全等三角形三个顶点X、Y、Z之间的距离d1、d2、d3,如果在误差范围内满足|D1-d1|, |D2-d2|, |D3-d3|,那么认为这两个点是匹配的。遍历S1中所有的点即可找出S1中点在S2中的匹配关系。确定点的匹配关系的C+代码见附录代码二。得出所有点的对应关系后，检验其中能正确匹配的点的个数，计算其比例，若大于，则认为这一对应关系正确；否则认为对应关系有误，此时回到最初的步骤，重新在S1中选择三角形寻找S2中全等的三角形，重新得出对应关系进行计算，直到正确为止。4.2模型的求解对数据集一的求解取S1中三点A（146，50）、B（165，55）、C（178，46），误差范围=3，求出S2中对应的全等三角形的三个顶点 X（108，69）、Y（128，78）、Z（140，67）。进一步解出所有点的对应关系。其中能正确匹配的点如下表所示：点集一点集二点集一点集二横坐标X纵坐标Y横坐标X纵坐标Y横坐标X纵坐标Y横坐标X纵坐标Y531052314210611176139626222771101446316381324646114817399865447701231207613986545342140109961298826477014214697168882653421421461051678892441081465010869889262129150146105167952959451655512878106111621291784614067我们看到，由于其中某些点本身相距很近，在我们允许的误差范围内出现了一对多的情况（上表中用红色突出显示的数据）。将这些多余的匹配关系删去，得到最终能正确匹配的点的匹配关系如下表：点集一点集二点集一点集二横坐标X纵坐标Y横坐标X纵坐标Y横坐标X纵坐标Y横坐标X纵坐标Y531052314211481739962622277123120761398132464614010996129865447701421469716888265342146501086988924410815014610516795295945165551287810611162129178461406711014463163其中能正确对应的点的个数为17，占总数的65.38%。初看这一比例比较小，要怀疑是否是正确的匹配。但通过画出散点图标出匹配的点就发现点集二是点集一通过平移得到的，点集一中有一部分点整体丢失而在点集二中出现了整片的新的点。据此通过比对原点集，可以找出其中的缺少点（第一个点集中在第二个点集没有匹配的点）和伪点（第二个点集中在第一个点集没有匹配的点）如下表：缺少点伪点110824201911734126202012229231111582828201611633918162374114017153701251711189217017541181102对数据集二的求解取S1中三点A（50，833）、B（762，879）、C（887，329），误差范围=3%，设定匹配比例下限=85%，求出S2中对应的全等三角形的三个顶点 X（2125，51109）、Y（1488，50791）、Z（1159，51248）。进一步解出所有点的对应关系。其中能正确匹配的点如下表所示：点集一点集二点集一点集二横坐标X纵坐标Y横坐标X纵坐标Y横坐标X纵坐标Y横坐标X纵坐标Y97233110805121349842415505131788315410945140949941815505131786615811115141249842415535131281340111451542499418155351312844154113051425391189155951571911371115351200579670157451053887329115951248679984160450725886366117451214377318162351455858336118851252400371162351399936540119651034427483164151285861375120151215471660167051105990683120250881491752168751012885482122051107531855169050902856471124351129510805169250957733215125651412444656169351119772344127051279214146170651677747307128051323277306171151505702222128751417184118172351715630611291515944608651760509207974821301511424348241768509686872391309514084458591771509326621921313514602935011772513208837581329508543556571775511537704971332511382413891776514437595321356511103366481789511686813541358513057983180651788727470136151180772281864516556412821367513873118051874510338327521374508792536851880511678718541378507702837621883510845401011390515926123188951779541197142651503258748190051107702615143651057247752191251107706612143651057159583192751297702615144051056783961929515007066121440510561365861950513136855781442510972318751975510005212031447515051126001977513007698041452508561226311988512678419821455506641407912026511134771551469515671478772053510317789061484507591559722082509407628791488507915182021195112149337715395135750833212551109423216154151531959552131509794232161541515414494021725101342820315415154123998221450968将多于的匹配关系删去，得到最终能正确匹配的点的匹配关系如下表：点集一点集二点集一点集二横坐标X纵坐标Y横坐标X纵坐标Y横坐标X纵坐标Y横坐标X纵坐标Y97233110805121349941815535131288315410945140939118915595157186615811115141257967015745105381340111451542679984160450725844154113051425377318162351455911371115351200400371162351399887329115951248427483164151285886366117451214471660167051105858336118851252491752168751012936540119651034531855169050902861375120151215510805169250957990683120250881444656169351119885482122051107214146170651677856471124351129277306171151505733215125651412184118172351715772344127051279460865176050920747307128051323434824176850968702222128751417445859177150932630611291515942935011772513207974821301511423556571775511536872391309514082413891776514436621921313514603366481789511688837581329508547983180651788770497133251138772281864516557595321356511103118051874510336813541358513052536851880511677274701361511802837621883510846412821367513876123188951779832752137450879258748190051107871854137850770247752191251107540101139051592159583192751297541197142651503783961929515007026151436510571365861950513137066121440510562318751975510006855781442510971126001977513005212031447515051226311988512677698041452508561407912026511138419821455506641478772053510314771551469515671559722082509407789061484507595182021195112176287914885079150833212551109493377153951357959552131509794232161541515314494021725101342820315415154123998221450968498424155051317这样共有89个点能正确匹配，占第一个点集的89，这一比例大于设定的比例下限85%，因此我们认为这一匹配关系是正确的。至此，我们已经求出了能正确匹配的点的匹配关系。将这些有匹配的点与原来的点集比较，就得到了其中的缺少点和伪点，如下表：缺少点伪点2062412565236410865613545112716532613595120027926140051762297598148951737337597162251531389529210351246508282629490752260793608五、模型的进一步讨论1.对于在寻找全等三角形阶段，若是编译后得到两组甚至多组结果，说明点集二存在不止一个三角形与点集一中输入的三角形全等。由于事实上两组点集只存在一种对应关系，这时只需要我们分别进行验证求解，得到匹配点较多、效果较好的就是所求解。2.在上述模型中，求匹配点对比两组三角形三条边是我们阈值的设定是直接取一个固定数字（点集一中阈值为5；点集二中阈值为10），但实际上我们经常说的误差是个相对概念。即边长值为1000时，阈值取50有可能都是合适的，而边长10时，阈值取1应该更合适。所以在问题求解中，我们取单一数值作为三条边对比的阈值是不合适的。进一步改进的话，阈值应该设定为边长*系数，系数取1%、5%等更合适。3.我们注意到：在找匹配点代码中阈值大可以得到更多潜在匹配的点但同时重复匹配的概率也变大；阈值小可能会丢失一定的匹配的点但同时匹配重复的概率变小精度更高（即使按照讨论二中阈值的设定方法也存在这个问题）。所以，这里就存在一个如何取值的问题。在实际模型过程中，我们是通过多次取值，分析结果，取结果最好时的阈值作为最终值。4.由于点受噪声的干扰，部分点的相对位置发生了改变，所以出现了有些点处于可匹配又不可匹配的边缘。因此在模型求解的结果分析中，不同的阈值得到不同的结果。那么如何判断结果的好坏？是得到匹配点数越多越好？但事实上匹配点数越多说明匹配的效果越差。所以如何衡量匹配结果的好坏，需要进一步考虑。六、模型优缺点模型优点：1、用多次运算取最优解的方法，得到的结果比较可靠。2、对特殊点进行了分析，得到了尽可能多的匹配点。3、考虑到了点的漂移，允许对微小漂移的点进行匹配。模型缺点：1、阈值的取法还不够科学，不够系统。2、全等三角形的找法不够系统。七、附录代码一：寻找两个点集中的全等三角形。 int main()int x100,y100;/两个数组，分别保存第二个点集96个数据的横坐标和纵坐标ifstream fin;fin.open(D:data2.txt);if(!fin)cout文件未打开endl;return 0;for(int c=0;cxcyc;fin.close();/从文件中读入第二个点集的数据 int a1,a2,b1,b2,c1,c2;/定义a1,a2,b1,b2,c1,c2六个变量分别存储第一个点集的三个点的横纵坐标由用户输入couta1a2;cout第一个点的坐标为： a1,a2 endl; coutb1b2;cout第二个点的坐标为： b1,b2 endl; coutc1c2;cout第三个点的坐标为： c1,c2 l2l1，方便后面全等三角形的确定。*/double temp;if(l1l2) 代码二：确定点的匹配关系。 int main()int a1,a2,b1,b2,c1,c2,x1,x2,y1,y2,z1,z2,a100,b100,x100,y100,i,j;/a1,a2,b1,b2,c1,c2分别存放第一个点集中被筛选出来的三个点的横纵坐标；x1,x2,y1,y2,z1,z2分别存放第二个点集中被筛选出来的三个点的横纵坐标；/a100,b100分别存放第一个点集中所有点的横纵坐标；x100,y100分别存放第二个点集中所有点的横纵坐标；double L1,L2,L3,S1,S2,S3;/L1,L2,L3分别存放第一个点集中待测点与第一个点集中筛选出来的三个点的距离；S1,S2,S3分别存放第一个点集中待测点与第二个点集中筛选出来的三个点的距离；/cina1a2b1b2c1c2x1x2y1y2z1z2;couta1a2;cout第一个点的坐标为： a1,a2 endl; coutb1b2;cout第二个点的坐标为： b1,b2 endl; coutc1c2;cout第三个点的坐标为： c1,c2 endl;coutx1x2;cout第一个点的坐标为： x1,x2 endl; couty1y2;cout第二个点的坐标为： y1,y2 endl; coutz1z2;cout第三个点的坐标为： z1,z2 endl;/a1=50;a2=833;b1=762;b2=879;c1=887;c2=329;x1=2125;x2=51109;y1=1488;y2=50791;z1=1159;z2=51248;ifstream fin1;fi