Project

General

Profile

A Novel Graph-based Invariant Region Descriptor for Image Matching

这篇文章主要想解决的问题是匹配中的错配,为此作者提出将一些特征点按一定准则集合为一个图(一个点集),在匹配的时候先匹配图,再匹配点。

算法描述

  1. 用SURF(SIFT也可)算法生成特征点及其描述子。
  2. 对任意两个特征点,若他们的几何距离、色彩距离(RGB的差得平方和)均小于各自对应的阈值,则这两个点属于同一图。(具体实现可能通过并查集一类的算法)
  3. 对于每个生成的图,选择其中一个点,用Dijkstra单源最短路径算法得出从该点到最远点的路径,并以此路径得到这幅图的一个生成树,记路径上的点为1,2,3,...,m。
  4. 当匹配两幅图G1、G2时,将G1分别与G2的m个子图按一定函数去匹配(子图的定义是最短路径前k个点(1≤k≤m)构成的图)。
  5. 匹配特征点时只需匹配每两个匹配的“图对”中的点。

创新点

将图论的思想引入特征点匹配,提高了匹配的准确度,给精确匹配打开了一个新方向。但算法时间复杂度高,且该方法只是一个近似,会在一定程度上漏掉一些正确匹配的点。而且该算法现阶段略显粗糙,如何更准确地定义图,如何更好地匹配图,如何降低运算量,是可以考虑去突破的。

结果比较

根据作者提供的样例图片匹配结果看,引入该算法大大降低了错配点对;但仍有少量错配点对存在。