从K近邻算法、距离度量谈到KD树、SIFT+BBF算法（二）

之前blog内曾经介绍过SIFT特征匹配算法，特征点匹配和数据库查、图像检索本质上是同一个问题，都可以归结为一个通过距离函数在高维矢量之间进行相似性检索的问题，如何快速而准确地找到查询点的近邻，不少人提出了很多高维空间索引结构和近似查询的算法。一般说来，索引结构中相似性查询有两种基本的方式：一种是范围查询，范围查询时给定查询点和查询距离阈值，从数据集中查找所有与查询点距离小于阈值的数据另一种是K近邻查询，就是给定查询点及正整数K，从数据集中找到距离查询点最近的K个数据，当K=1时，它就是最近邻查询。同样，针对特征点匹配也有两种方法：最容易的办法就是线性扫描，也就是我们常说的穷举搜索，依次计算样