IEEE Trans Pattern Anal Mach Intell. 2014 Nov;36(11):2227-40. doi: 10.1109/TPAMI.2014.2321376.
For many computer vision and machine learning problems, large training sets are key for good performance. However, the most computationally expensive part of many computer vision and machine learning algorithms consists of finding nearest neighbor matches to high dimensional vectors that represent the training data. We propose new algorithms for approximate nearest neighbor matching and evaluate and compare them with previous algorithms. For matching high dimensional features, we find two algorithms to be the most efficient: the randomized k-d forest and a new algorithm proposed in this paper, the priority search k-means tree. We also propose a new algorithm for matching binary features by searching multiple hierarchical clustering trees and show it outperforms methods typically used in the literature. We show that the optimal nearest neighbor algorithm and its parameters depend on the data set characteristics and describe an automated configuration procedure for finding the best algorithm to search a particular data set. In order to scale to very large data sets that would otherwise not fit in the memory of a single machine, we propose a distributed nearest neighbor matching framework that can be used with any of the algorithms described in the paper. All this research has been released as an open source library called fast library for approximate nearest neighbors (FLANN), which has been incorporated into OpenCV and is now one of the most popular libraries for nearest neighbor matching.
对于许多计算机视觉和机器学习问题来说，大的训练集是取得良好性能的关键。然而，许多计算机视觉和机器学习算法中最耗费计算资源的部分包括查找与表示训练数据的高维向量的最近邻匹配。我们提出了用于近似最近邻匹配的新算法，并对其进行了评估和与以前的算法进行了比较。对于匹配高维特征，我们发现两种算法最为有效：随机 k-d 森林和本文提出的一种新算法，优先级搜索 k-均值树。我们还提出了一种用于匹配二进制特征的新算法，通过搜索多个层次聚类树，并展示了它优于文献中常用的方法。我们表明，最优的最近邻算法及其参数取决于数据集的特征，并描述了一种自动配置过程，用于查找搜索特定数据集的最佳算法。为了扩展到非常大的数据集，否则它们将无法在单个机器的内存中容纳，我们提出了一个分布式最近邻匹配框架，可以与本文中描述的任何算法一起使用。所有这些研究都已作为一个名为快速近似最近邻库（FLANN）的开源库发布，该库已被集成到 OpenCV 中，现在是最流行的最近邻匹配库之一。
