OpenCV:在 FLANN 模块中，KDTree 构造函数创建了 4 棵相同大小的树。为什么？

Question

在 FLANN 模块中，KDTree 构造函数采用配置参数来创建树。我看到默认值为 4。有人可以建议为什么 4 或为什么最近邻居搜索需要多棵树吗？

/**
 * KDTree constructor
 *
 * Params:
 *          inputData = dataset with the input features
 *          params = parameters passed to the kdtree algorithm
 */
KDTreeIndex(const Matrix<ElementType>& inputData, const IndexParams& params = KDTreeIndexParams(),
            Distance d = Distance() ) :
    dataset_(inputData), index_params_(params), distance_(d)
{
    size_ = dataset_.rows;
    veclen_ = dataset_.cols;

    trees_ = get_param(index_params_,"trees",4);   <<<<------------------ default 4
    tree_roots_ = new NodePtr[trees_];

    // Create a permutable array of indices to the input vectors.
    vind_.resize(size_);
    for (size_t i = 0; i < size_; ++i) {

Answer 1

我猜树木直到最后才被搜索；它们的构造方式也略有不同。所以当 4 棵树被部分搜索时，它们的组合性能比单棵树部分搜索要好得多。同时，它们比完全搜索的单个树更快(并且可能更有效地存储内存)。至少这是我对这个问题的直觉。

FLANN - 代表 的快速库近似值 最近的邻居。近似这个词在这里可能是一个关键。例如，在树构造的某个时刻，必须找到一组点的中位数(以在大致相等的两半上有效地分割空间)。这需要 n*log(n) 操作，但中值可以从较小的样本中近似得出，例如 n=min(100, n/100) - 我正在编造这个例子。这将导致大约 x600 的构建速度加快，而搜索速度稍慢一些。此外，我们可能会查看有限的集合，而不是探索所有维度以获得更大的方差来选择拆分。这就解释了为什么树会有所不同。

这里的另一方面，在高维空间中，对最近邻的逼近变得更加重要，因为与穷举搜索相比，标准 kd-tree 失去了效率。一种近似方法是仅检查有限数量的叶子以满足搜索精度。通常在所有树上都维护一个优先级队列，以通过增加距离来排序搜索。总之，使用近似和多棵树可以大大提高速度和内存效率，而精度损失很小。