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. 匹配特征点时只需匹配每两个匹配的“图对”中的点。

创新点¶

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

结果比较¶

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