精华内容
下载资源
问答
  • 使用matlab对输入数据建立Kd-tree并通过Kd-tree进行k-NN查询。k-NN查询的主要算法思路来自知乎【量化课堂】kd 树算法之详细篇
  • 为了进一步提高效率,Steven Michael 开发的 kd-tree 工具http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=7030&objectType=file用于有效识别范围内的点。 对于大型数据集,此代码可以...
  • kd-Tree源码(c++)

    2019-03-01 14:00:46
    之前写的一个kd-tree,程序里用了一些qt的数据结构,基本不影响阅读。该程序仅供初学kd-tree的同学参考,
  • 文章目录KNN算法的模型提升KD-Treekd树是什么kd树的原理1.树的建立;2.最近邻域搜索(Nearest-Neighbor Lookup)3.构造方法4.案例分析4.1 树结构的建立4.2 最近领域的搜索4.2.1 查找点(2.1,3.1)4.2.2 查找点(2,4.5)5...
  • 树 CG.ZJU项目 基于“图形硬件上的实时KD-树构建”,在OpenCL上实现GPU kd-树构建(Kun Zhou等) 来源:hpRayTracing 感谢BlanGeek
  • 这是一个非常快的纯 C# kd-tree,没有依赖项。 它还附带一个示例应用程序,您可以在其中处理数字并执行一些最近邻查询。 这是Java kd-tree 的 C# 端口: : 由于 Google Code 已删除新项目的“下载”,临时用户...
  • k近邻查询算法是查询大规模空间数据的常用算法之一,使用Kd-Tree先构建大规模空间数据的索引,然后对搜索空间进行层次划分,再进行k近邻查询,能保证搜索的效率.但是,传统的Kd-Tree构建有两个缺点:使用测试数据点...
  • KD-Tree 开源实现以及 OpenCV KD-Tree 使用
  • 点云处理---kd-tree

    2021-06-01 10:25:08
    kd

    KD-tree在二叉树的基础上,实际上就是变成了多维度的分割,分割方法变为维度轮换分割:x-y-z-x-y-z…
    1.kd-tree的构建
    (1)节点定义
    每个节点按我的理解其实就是单维度上的一片空间区域,该节点储存了该节点的分割维度axis,分割轴的坐标value,该节点区域内的点的索引point_indices,以分割轴分开的左右节点也是两个区域,被当做left、right两个节点存储起来。
    在这里插入图片描述

    from result_set import KNNResultsets, RadiusNNResultSet
    import numpy as np
    import math
    import os
    import random
    
    # define the node
    
    
    class Node:
        # init function
        def __init__(self, axis, value, left, right, point_indices):
            '''
            pram:
            axis:划分的维度
            value:节点的值
            left:左节点
            right:右节点
            point_indices:点集中的序号
            '''
            self.axis = axis
            self.value = value
            self.left = left
            self.right = right
            self.point_indices = point_indices
        # check if is leaf
    
        def is_leaf(self):
        #叶子节点的时候是不再对空间进行划分的,所以value是none
            if self.value == None:
                return True
            else:
                return False
    
        # print function
        def __str__(self):
            output = ''
            output += 'axis %d, ' % self.axis
            if self.value is None:
                output += 'split value: leaf, '
            else:
                output += 'split value: %.2f, ' % self.value
            output += 'point_indices: '
            output += str(self.point_indices.tolist())
            return output
    

    (2)kd树构建
    kdtree_construction调用递归构造函数kdtree_recursive_builder构建kd-tree节点

    def kdtree_construction(data, leaf_size):
        '''
        input:
        data(numpy array)
        leaf_size(the smallest size of each node)
        '''
        N, dim = data.shape[0], data.shape[1]
    
        # build the kd-tree
        root = None
        root = kdtree_recursive_builder(
            root, data, np.arange(N), axis=0, leaf_size=leaf_size)
        return root
    

    kdtree_recursive_builder

    def kdtree_recursive_builder(root, db, point_indices, axis, leaf_size):
        """
        param:
        root
        data:NxD
        point_indeces:N
        axis:scale
        leaf_size:scale
        """
     	#如果root不存在,先建立root
        if root is None:
            root = Node(axis, None, None, None, point_indices)
    
        
        #如果当前的节点数量大于叶子节点数,才进一步的进行分割,否则就不进行进一步分割,当前节点就作为叶子结点
        #叶子结点特点就是value==None
        if len(point_indices) > leaf_size:
            # --- get the split position ---
            #对当前传入的数据节点在划分维度上进行排序,选出当前维度的中间值数据点
            #划分点的value就等于中间值数据点的均值,注意此处划分的中间平面不穿过数据点
            point_indices_sorted, _ = sort_key_by_value(
                point_indices, db[point_indices, axis])  # 点的索引按照value的大小顺序进行排序
            #求出当前维度下中间值的点的索引位置
            middle_left_idx = math.ceil(point_indices_sorted.shape[0] / 2) - 1
            #中间点在原来点集合中的索引
            middle_left_point_idx = point_indices_sorted[middle_left_idx]
            #中间点的value值
            middle_left_point_value = db[middle_left_point_idx, axis]
    		#中间点后一个点也一样
            middle_right_idx = middle_left_idx + 1
            middle_right_point_idx = point_indices_sorted[middle_right_idx]
            middle_right_point_value = db[middle_right_point_idx, axis]
    
            root.value = (middle_left_point_value + middle_right_point_value) * 0.5#取中间两个数据点value的平均值,不穿过数据点
            # === get the split position ===
            root.left = kdtree_recursive_builder(root.left,
                                                 db,
                                                 point_indices_sorted[0:middle_right_idx],
                                                 axis_round_robin(
                                                     axis, dim=db.shape[1]),
                                                 leaf_size)
            root.right = kdtree_recursive_builder(root.right,
                                                  db,
                                                  point_indices_sorted[middle_right_idx:],
                                                  axis_round_robin(
                                                      axis, dim=db.shape[1]),
                                                  leaf_size)
        return root
    
    

    sort_key_by_value排序函数:

    
    # sort_key_by_value
    def sort_key_by_value(point_indeces, value):
        # 确保输入的点的索引和点的值维度相同
        assert(point_indeces.shape == value.shape)
        assert(len(point_indeces.shape) == 1)  # 1xN
        sort_idx = np.argsort(value)  # value是一个列表,不是numpy
        point_indeces_sort = point_indeces[sort_idx]
        value_sort = value[sort_idx]
        return point_indeces_sort, value_sort
    

    axis_round_robin函数,轮换确定分割维度:0-->1,1--》2,2-->0

    
    # axis_round_robin,改变分割维度
    def axis_round_robin(axis, dim):
        if axis == dim-1:
            return 0
        else:
            return axis+1
    

    2.kd-tree的KNN查找
    和二叉树的查找很相似,不同之处在于初始时刻要判断当前节点是不是叶子节点,是的话就直接将各个节点计算和当前查询点的距离,把这些点插入到结果集合中。
    不是叶子节点的时候:也是先比较查询点和当前节点的value的大小,选择从左边找还是从右边找。
    是否查找一个节点区域的关键是:判断当前最坏距离与(查询点坐标—节点区域分割坐标之差)之间的大小关系。
    在这里插入图片描述

    def kdtree_knn_search(root: Node, data: np.ndarray, result_set: KNNResultsets, query_point: np.ndarray):
        if root == None:
            return
        # check if is a leaf
        #当当前节点是叶子节点的时候,由于不能再进一步的在当前节点空间上区分左右子空间了,
        #所以就暴力的把所有叶子节点中的节点都拿出来和查询点计算距离,把距离较近的点都插入到result
        if root.is_leaf():
           # compare the contents of a leaf
            leaf_points = data[root.point_indices, :]#root.point_indeces是一个列表,存储的是点在元数据中的索引
            #print("leaf index:", root.point_indices)
            diff = np.linalg.norm(np.expand_dims(
                query_point, 0) - leaf_points, axis=1)
            for i in range(diff.shape[0]):
                result_set.add_point(diff[i], root.point_indices[i])
            return False
    #距离小于root value,从左边开始找
        if query_point[root.axis] <= root.value:
            kdtree_knn_search(root.left, data, result_set, query_point)
            #如果左边没有找够,就继续从右边找
            if math.fabs(query_point[root.axis] - root.value) < result_set.worst_Dist():
                kdtree_knn_search(root.right, data, result_set, query_point)
        else:
        #从右边开始找
            kdtree_knn_search(root.right, data, result_set, query_point)
            if math.fabs(query_point[root.axis] - root.value) < result_set.worst_Dist():
                kdtree_knn_search(root.left, data, result_set, query_point)
    
        return False
    

    3.kd-tree的radius查找

    def kdtree_radius_search(root: Node, data: np.ndarray, result_set: RadiusNNResultSet, query_point: np.ndarray):
        if root == None:
            return
        # check if is a leaf
        if root.is_leaf():
           # compare the contents of a leaf
            leaf_points = data[root.point_indices, :]
            print("leaf index:", root.point_indices)
            diff = np.linalg.norm(np.expand_dims(
                query_point, 0) - leaf_points, axis=1)
            for i in range(diff.shape[0]):
                result_set.add_point(diff[i], root.point_indices[i])
            return False
    
        if query_point[root.axis] <= root.value:
            kdtree_radius_search(root.left, data, result_set, query_point)
            if math.fabs(query_point[root.axis] - root.value) < result_set.worst_Dist():
                kdtree_radius_search(root.right, data, result_set, query_point)
        else:
            kdtree_radius_search(root.right, data, result_set, query_point)
            if math.fabs(query_point[root.axis] - root.value) < result_set.worst_Dist():
                kdtree_radius_search(root.left, data, result_set, query_point)
    
        return False
    

    main函数调用:

    def main():
        # generate the data
        db = 64
        dim = 3
        leaf_size = 4
        k = 8
        print('runing')
        db_np = np.random.rand(db, dim)
        root = kdtree_construction(data=db_np, leaf_size=leaf_size)
        query = np.asarray([0, 0, 0])
        # result_set = KNNResultsets(capacity=k)
        # kdtree_knn_search(root, data=db_np,
        #                   result_set=result_set, query_point=query)
    
        # print(result_set)
    
        result_set = RadiusNNResultSet(radius=1)
        kdtree_radius_search(
            root, data=db_np, result_set=result_set, query_point=query)
        print(result_set)
    
    
    if __name__ == '__main__':
        main()
    

    python相关:

     diff = np.linalg.norm(np.expand_dims(
                query_point, 0) - leaf_points, axis=1)
      #计算范数:在列的方向上计算,也就是计算每个点和查询点之间的距离(空间距离)
    
    展开全文
  • UE4-Kdtree:UE4插件-源码

    2021-05-06 00:50:09
    UE4插件:kd-tree 这是一个UE4插件,可提供用于将kd-tree构建为蓝图功能库的实用程序功能。 支援环境 该插件在以下环境中经过测试。 UE4版本:4.22 ...Build Kdtree从Vector对象生成一个kd-tree(蓝图中
  • Kd-Tree算法原理

    2019-05-11 14:22:22
    Kd-Tree算法原理和开源实现代码 本文介绍一种用于高维空间中的快速最近邻和近似最近邻...Kd-Tree,即K-dimensional tree,是一种高维索引树形数据结构,常用于在大规模的高维数据空间进行最近邻查找(Nearest Nei...

    转载于: http://www.cnblogs.com/lysuns/articles/4710712.html

    Kd-Tree算法原理和开源实现代码

     

    本文介绍一种用于高维空间中的快速最近邻和近似最近邻查找技术——Kd-Tree(Kd树)。Kd-Tree,即K-dimensional tree,是一种高维索引树形数据结构,常用于在大规模的高维数据空间进行最近邻查找(Nearest Neighbor)和近似最近邻查找(Approximate Nearest Neighbor),例如图像检索和识别中的高维图像特征向量的K近邻查找与匹配。本文首先介绍Kd-Tree的基本原理,然后对基于BBF的近似查找方法进行介绍,最后给出一些参考文献和开源实现代码。

     

    一、Kd-tree

     Kd-Tree,即K-dimensional tree,是一棵二叉树,树中存储的是一些K维数据。在一个K维数据集合上构建一棵Kd-Tree代表了对该K维数据集合构成的K维空间的一个划分,即树中的每个结点就对应了一个K维的超矩形区域(Hyperrectangle)。

    在介绍Kd-tree的相关算法前,我们先回顾一下二叉查找树(Binary Search Tree)的相关概念和算法。

    二叉查找树(Binary Search Tree,BST),是具有如下性质的二叉树(来自wiki):

    1)若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值;

    2)若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值;

    3)它的左、右子树也分别为二叉排序树;

    例如,图1中是一棵二叉查找树,其满足BST的性质。

    File:Binary search tree.svg

    图1 二叉查找树(来源:Wiki)

    给定一个1维数据集合,怎样构建一棵BST树呢?根据BST的性质就可以创建,即将数据点一个一个插入到BST树中,插入后的树仍然是BST树,即根结点的左子树中所有结点的值均小于根结点的值,而根结点的右子树中所有结点的值均大于根结点的值。

     

    将一个1维数据集用一棵BST树存储后,当我们想要查询某个数据是否位于该数据集合中时,只需要将查询数据与结点值进行比较然后选择对应的子树继续往下查找即可,查找的平均时间复杂度为:O(logN),最坏的情况下是O(N)。

     

    如果我们要处理的对象集合是一个K维空间中的数据集,那么是否也可以构建一棵类似于1维空间中的二叉查找树呢?答案是肯定的,只不过推广到K维空间后,创 建二叉树和查询二叉树的算法会有一些相应的变化(后面会介绍到两者的区别),这就是下面我们要介绍的Kd-tree算法。

     

     怎样构造一棵Kd-tree?

    对于Kd-tree这样一棵二叉树,我们首先需要确定怎样划分左子树和右子树,即一个K维数据是依据什么被划分到左子树或右子树的。

    在构造1维BST树时,一个1维数据根据其与树的根结点和中间结点进行大小比较的结果来决定是划分到左子树还是右子树,同理,我们也可以按照这样的方式, 将一个K维数据与Kd-tree的根结点和中间结点进行比较,只不过不是对K维数据进行整体的比较,而是选择某一个维度Di,然后比较两个K维数在该维度 Di上的大小关系,即每次选择一个维度Di来对K维数据进行划分,相当于用一个垂直于该维度Di的超平面将K维数据空间一分为二,平面一边的所有K维数据 在Di维度上的值小于平面另一边的所有K维数据对应维度上的值。也就是说,我们每选择一个维度进行如上的划分,就会将K维数据空间划分为两个部分,如果我 们继续分别对这两个子K维空间进行如上的划分,又会得到新的子空间,对新的子空间又继续划分,重复以上过程直到每个子空间都不能再划分为止。以上就是构造 Kd-Tree的过程,上述过程中涉及到两个重要的问题:1)每次对子空间的划分时,怎样确定在哪个维度上进行划分;2)在某个维度上进行划分时,怎样确 保在这一维度上的划分得到的两个子集合的数量尽量相等,即左子树和右子树中的结点个数尽量相等。

     

    问题1: 每次对子空间的划分时,怎样确定在哪个维度上进行划分?

    最简单的方法就是轮着来,即如果这次选择了在第i维上进行数据划分,那下一次就在第j(j≠i)维上进行划分,例如:j = (i mod k) + 1。想象一下我们切豆腐时,先是竖着切一刀,切成两半后,再横着来一刀,就得到了很小的方块豆腐。

    可是“轮着来”的方法是否可以很好地解决问题呢?再次想象一下,我们现在要切的是一根木条,按照“轮着来”的方法先是竖着切一刀,木条一分为二,干净利 落,接下来就是再横着切一刀,这个时候就有点考验刀法了,如果木条的直径(横截面)较大,还可以下手,如果直径较小,就没法往下切了。因此,如果K维数据 的分布像上面的豆腐一样,“轮着来”的切分方法是可以奏效,但是如果K维度上数据的分布像木条一样,“轮着来”就不好用了。因此,还需要想想其他的切法。

    如果一个K维数据集合的分布像木条一样,那就是说明这K维数据在木条较长方向代表的维度上,这些数据的分布散得比较开,数学上来说,就是这些数据在该维度 上的方差(invariance)比较大,换句话说,正因为这些数据在该维度上分散的比较开,我们就更容易在这个维度上将它们划分开,因此,这就引出了我 们选择维度的另一种方法:最大方差法(max invarince),即每次我们选择维度进行划分时,都选择具有最大方差维度。

     

    问题2:在某个维度上进行划分时,怎样确保在这一维度上的划分得到的两个子集合的数量尽量相等,即左子树和右子树中的结点个数尽量相等?

    假设当前我们按照最大方差法选择了在维度i上进行K维数据集S的划分,此时我们需要在维度i上将K维数据集合S划分为两个子集合A和B,子集合A中的数据 在维度i上的值都小于子集合B中。首先考虑最简单的划分法,即选择第一个数作为比较对象(即划分轴,pivot),S中剩余的其他所有K维数据都跟该 pivot在维度i上进行比较,如果小于pivot则划A集合,大于则划入B集合。把A集合和B集合分别看做是左子树和右子树,那么我们在构造一个二叉树 的时候,当然是希望它是一棵尽量平衡的树,即左右子树中的结点个数相差不大。而A集合和B集合中数据的个数显然跟pivot值有关,因为它们是跟pivot比较后才被划分到相应的集合中去的。好了,现在的问题就是确定pivot了。给定一个数组,怎样才能得到两个子数组,这两个数组包含的元素 个数差不多且其中一个子数组中的元素值都小于另一个子数组呢?方法很简单,找到数组中的中值(即中位数,median),然后将数组中所有元素与中值进行 比较,就可以得到上述两个子数组。同样,在维度i上进行划分时,pivot就选择该维度i上所有数据的中值,这样得到的两个子集合数据个数就基本相同了。

     

     解决了上面两个重要的问题后,就得到了Kd-Tree的构造算法了。

    Kd-Tree的构建算法:

    (1) 在K维数据集合中选择具有最大方差的维度k,然后在该维度上选择中值m为pivot对该数据集合进行划分,得到两个子集合;同时创建一个树结点node,用于存储;

    (2)对两个子集合重复(1)步骤的过程,直至所有子集合都不能再划分为止;如果某个子集合不能再划分时,则将该子集合中的数据保存到叶子结点(leaf node)。

     

    以上就是创建Kd-Tree的算法。下面给出一个简单例子。

    给定二维数据集合:(2,3), (5,4), (9,6), (4,7), (8,1), (7,2),利用上述算法构建一棵Kd-tree。左图是Kd-tree对应二维数据集合的一个空间划分,右图是构建的一棵Kd-tree。

     

    kd-tree

    图2 构建的kd-tree

     其中圆圈代表了中间结点(k, m),而红色矩形代表了叶子结点。

     

     

    Kd-Tree与一维二叉查找树之间的区别:

    二叉查找树:数据存放在树中的每个结点(根结点、中间结点、叶子结点)中;

    Kd-Tree:数据只存放在叶子结点,而根结点和中间结点存放一些空间划分信息(例如划分维度、划分值);

     

    构建好一棵Kd-Tree后,下面给出利用Kd-Tree进行最近邻查找的算法:

    (1)将查询数据Q从根结点开始,按照Q与各个结点的比较结果向下访问Kd-Tree,直至达到叶子结点。

    其中Q与结点的比较指的是将Q对应于结点中的k维度上的值与m进行比较,若Q(k) < m,则访问左子树,否则访问右子树。达到叶子结点时,计算Q与叶子结点上保存的数据之间的距离,记录下最小距离对应的数据点,记为当前“最近邻点”Pcur和最小距离Dcur。

    (2)进行回溯(Backtracking)操作,该操作是为了找到离Q更近的“最近邻点”。即判断未被访问过的分支里是否还有离Q更近的点,它们之间的距离小于Dcur。

    如果Q与其父结点下的未被访问过的分支之间的距离小于Dcur,则认为该分支中存在离P更近的数据,进入该结点,进行(1)步骤一样的查找过程,如果找到更近的数据点,则更新为当前的“最近邻点”Pcur,并更新Dcur。

    如果Q与其父结点下的未被访问过的分支之间的距离大于Dcur,则说明该分支内不存在与Q更近的点。

    回溯的判断过程是从下往上进行的,直到回溯到根结点时已经不存在与P更近的分支为止。

     

    怎样判断未被访问过的树分支Branch里是否还有离Q更近的点? 

    从几何空间上来看,就是判断以Q为中心center和以Dcur为半径Radius的超球面(Hypersphere)与树分支Branch代表的超矩形(Hyperrectangle)之间是否相交。

    在实现中,我们可以有两种方式来求Q与树分支Branch之间的距离。第一种是在构造树的过程中,就记录下每个子树中包含的所有数据在该子树对应的维度k上的边界参数[min, max];第二种是在构造树的过程中,记录下每个子树所在的分割维度k和分割值m,(k, m),Q与子树的距离则为|Q(k) - m|。

     

    以上就是Kd-tree的构造过程和基于Kd-Tree的最近邻查找过程。

     

    下面用一个简单的例子来演示基于Kd-Tree的最近邻查找的过程。

    数据点集合:(2,3), (4,7), (5,4), (9,6), (8,1), (7,2) 。

    已建好的Kd-Tree:

    kd-tree

    图3 构建的kd-tree

     其中,左图中红色点表示数据集合中的所有点。

     

    查询点: (8, 3) (在左图中用茶色菱形点表示)

    第一次查询:

    kd-tree

    图4 第一次查询的kd-tree

    当前最近邻点: (9, 6) , 最近邻距离: sqrt(10),

    且在未被选择的树分支中存在于Q更近的点(如茶色圈圈内的两个红色点)

     

    回溯:

    kd-tree

    图5 回溯kd-tree

     

    当前最近邻点: (8, 1)和(7, 2) , 最近邻距离: sqrt(2)

     

    最后,查询点(8, 3)的近似最近邻点为(8, 1)和(7, 2) 。

     

     

    二、Kd-tree with BBF

     上一节介绍的Kd-tree在维度较小时(例如:K≤30),算法的查找效率很高,然而当Kd-tree用于对高维数据(例如:K≥100)进行索引和查找时,就面临着维数灾难(curse of dimension)问题,查找效率会随着维度的增加而迅速下降。通常,实际应用中,我们常常处理的数据都具有高维的特点,例如在图像检索和识别中,每张图像通常用一个几百维的向量来表示,每个特征点的局部特征用一个高维向量来表征(例如:128维的SIFT特征)。因此,为了能够让Kd-tree满足对高维数据的索引,Jeffrey S. Beis和David G. Lowe提出了一种改进算法——Kd-tree with BBF(Best Bin First),该算法能够实现近似K近邻的快速搜索,在保证一定查找精度的前提下使得查找速度较快。

     

    在介绍BBF算法前,我们先来看一下原始Kd-tree是为什么在低维空间中有效而到了高维空间后查找效率就会下降。在原始kd-tree的最近邻查找算法中(第一节中介绍的算法),为了能够找到查询点Q在数据集合中的最近邻点,有一个重要的操作步骤:回溯,该步骤是在未被访问过的且与Q的超球面相交的子树分支中查找可能存在的最近邻点。随着维度K的增大,与Q的超球面相交的超矩形(子树分支所在的区域)就会增加,这就意味着需要回溯判断的树分支就会更多,从而算法的查找效率便会下降很大。

    一个很自然的思路是:既然kd-tree算法在高维空间中是由于过多的回溯次数导致算法查找效率下降的话,我们就可以限制查找时进行回溯的次数上限,从而 避免查找效率下降。这样做有两个问题需要解决:1)最大回溯次数怎么确定?2)怎样保证在最大回溯次数内找到的最近邻比较接近真实最近邻,即查找准确度不 能下降太大。

    问题1):最大回溯次数怎么确定?

    最大回溯次数一般人为设定,通常根据在数据集上的实验结果进行调整。

    问题2):怎样保证在最大回溯次数内找到的最近邻比较接近真实最近邻,即查找准确度不能下降太大?

    限制回溯次数后,如果我们还是按照原来的回溯方法挨个地进行访问的话,那很显然最后的查找结果的精度就很大程度上取决于数据的分布和回溯次数了。挨个访问 的方法的问题在于认为每个待回溯的树分支中存在最近邻的概率是一样的,所以它对所有的待回溯树分支一视同仁。实际上,在这些待回溯树分支中,有些树分支存 在最近邻的可能性比其他树分支要高,因为树分支离Q点之间的距离或相交程度是不一样的,离Q更近的树分支存在Q的最近邻的可能性更高。因此,我们需要区别 对待每个待回溯的树分支,即采用某种优先级顺序来访问这些待回溯树分支,使得在有限的回溯次数中找到Q的最近邻的可能性很高。我们要介绍的BBF算法正是 基于这样的解决思路,下面我们介绍BBF查找算法。

    基于BBF的Kd-Tree近似最近邻查找算法

    已知:

    Q:查询数据;   KT:已建好的Kd-Tree;

     

    1. 查找Q的当前最近邻点P

    1)从KT的根结点开始,将Q与中间结点node(k,m)进行比较,根据比较结果选择某个树分支Branch(或称为Bin);并将未被选择的另一个树分支(Unexplored Branch)所在的树中位置和它跟Q之间的距离一起保存到一个优先级队列中Queue;

    2)按照步骤1)的过程,对树分支Branch进行如上比较和选择,直至访问到叶子结点,然后计算Q与叶子结点中保存的数据之间的距离,并记录下最小距离D以及对应的数据P。

    注:

    A、Q与中间结点node(k,m)的比较过程:如果Q(k) > m则选择右子树,否则选择左子树。

    B、优先级队列:按照距离从小到大的顺序排列。

    C、叶子结点:每个叶子结点中保存的数据的个数可能是一个或多个。

     

    2. 基于BBF的回溯

    已知:最大回溯次数BTmax

    1)如果当前回溯的次数小于BTmax,且Queue不为空,则进行如下操作:

    从Queue中取出最小距离对应的Branch,然后按照1.1步骤访问该Branch直至达到叶子结点;计算Q与叶子结点中各个数据间距离,如果有比D更小的值,则将该值赋给D,该数据则被认为是Q的当前近似最近邻点;

    2)重复1)步骤,直到回溯次数大于BTmax或Queue为空时,查找结束,此时得到的数据P和距离D就是Q的近似最近邻点和它们之间的距离。

     

    下面用一个简单的例子来演示基于Kd-Tree+BBF的近似最近邻查找的过程。

    数据点集合:(2,3), (4,7), (5,4), (9,6), (8,1), (7,2) 。

    已建好的Kd-Tree:

    kd-tree

    图6 构建的kd-tree

     

    基于BBF的查找的过程:

    查询点Q:   (5.5, 5)

    第一遍查询:

    kd-tree with bbf

    图7 第一次查询的kd-tree

     

    当前最近邻点: (9, 6) , 最近邻距离: sqrt(13.25),

    同时将未被选择的树分支的位置和与Q的距离记录到优先级队列中。

     

    BBF回溯:

    从优先级队列里选择距离Q最近的未被选择树分支进行回溯。

    kd-tree with bbf

    图8 利用BBF方法回溯kd-tree

     

    当前最近邻点: (4, 7) , 最近邻距离: sqrt(6.25)

     

    继续从优先级队列里选择距离Q最近的未被选择树分支进行回溯。

    kd-tree with bbf

    图9 利用BBF方法回溯kd-tree

     

    当前最近邻点: (5, 4) , 最近邻距离: sqrt(1.25)

     

     最后,查询点(5.5, 5)的近似最近邻点为(5, 4) 。

    展开全文
  • kd-tree基本概念 kd-tree(k-dimensional tree)是一种用于组织表示 k 维空间中点集合的数据结构。 kd-tree是扩展的二叉排序树,K为空间的维度,通过一定规律将点云数据按树状分类。假设分类节点 A 用第 i...

    kd-tree基本概念

    • kd-tree(k-dimensional tree)是一种用于组织表示 k 维空间中点集合的数据结构

    • kd-tree是扩展的二叉排序树,K为空间的维度,通过一定规律将点云数据按树状分类。假设分类节点 A 用第 i 维作划分标准,则在第 i 维的值小于 A 的归到左边,大于 A 的归到右边。

    • kd-tree建立的关键在于确定怎样划分左子树和右子树,即一个K维数据是依据什么被划分到左子树或右子树的。
      例:2-D(K=2)树的建立过程
      对于由点A(51,56)、B(31,54)、C(61,41)、D(26,81)、E(91,11)、F(86,71)组成的集合:在这里插入图片描述
      B点的 X 值(31)< A(51),归到左边;C点的 X 值(61)>A(51),归到右边。

    • 对于点云数据,树的每一级都在在一个维度上分开,所有维度用完后便回到第一个维度,直到最后一个分支上只有一个元素。

    kd-tree对点云数据的应用

    • 根据点云数据生成k-d树,建立点云的拓扑关系,实现基于邻域关系的快速查找。最近邻搜索是使用点云数据时的核心操作,可用于查找点组或特征描述符之间的对应关系或定义一个或多个点周围的局部邻域。

    pcl中的kd-tree模块

    pcl库中提供了kd-tree数据结构,基于FLANN进行快速最近邻检索。

    • 类 class pcl ::KdTree< PointT > 为kd-tree数据结构的实现。
    • 类 class pcl ::KdTreeFLANN< PointT, Dist > 具有近邻搜索实现功能。

    基本函数

    • void pcl::getApproximateIndices (const typename pcl::PointCloud< PointT >::ConstPtr &cloud_in, const typename pcl::PointCloud< PointT >::ConstPtr &cloud_ref, std::vector< int > &indices) 获取给定点云到参考点云的一组近似索引。
    展开全文
  • 三维点云学习(2)中-Kd-tree (k-dimensional tree) kd-tree 实现 代码来自黎老师github 三维kd-tree 的图示 如下图所示,为三维kd-tree的切割图,进行三个维度的切割,kd-tree的本质就是对三个维度的数据点不断...

    三维点云学习(2)中-Kd-tree (k-dimensional tree)

    kd-tree 实现

    代码来自黎老师github

    三维kd-tree 的图示

    如下图所示,为三维kd-tree的切割图,进行三个维度的切割,kd-tree的本质就是对三个维度的数据点不断构建平衡二叉树。
    在这里插入图片描述

    运行结果

    axis 1, split value: leaf, pointindices: [24, 43, 48, 39]
    axis 1, split value: leaf, pointindices: [10, 22, 37, 14]
    axis 1, split value: leaf, pointindices: [17, 41, 4, 51]
    axis 1, split value: leaf, pointindices: [55, 44, 27, 12]
    axis 1, split value: leaf, pointindices: [5, 61, 9, 47] axis 1, split value: leaf, point_indices: [42, 54, 56, 7] axis 1, split value: leaf, point_indices: [58, 26, 19, 31] axis 1, split value: leaf, point_indices: [0, 29, 25, 23] axis 1, split value: leaf, point_indices: [62, 18, 33, 49] axis 1, split value: leaf, point_indices: [63, 38, 53, 30] axis 1, split value: leaf, point_indices: [15, 32, 57, 46] axis 1, split value: leaf, point_indices: [13, 2, 20, 28] axis 1, split value: leaf, point_indices: [1, 16, 45, 6] axis 1, split value: leaf, point_indices: [34, 8, 35, 40] axis 1, split value: leaf, point_indices: [36, 50, 21, 11] axis 1, split value: leaf, point_indices: [52, 60, 59, 3] tree max depth: 5 

    搭建kd-tree的步骤

    1.根据点的个数判断是否需要进行root的构建

    根据需要,判断是否需要构建leaf,不需要构建单独的leaf,就对数据集进行分割构建kd-tree
    在这里插入图片描述

    2.分割的方法

    如下图所示为二维kd-tree的两种分割方法,图一是分割线在点上,图二是分割线不包含点
    在这里插入图片描述
    如下图所示,分别为顺序分割法和自适应分割法
    在这里插入图片描述
    二维kd-tree如下如所示
    在这里插入图片描述
    Stores points that belongs to this partition,对节点里的点在对应的维度上进行进行sort排列
    在这里插入图片描述
    寻找中点,并在中点附近进行切割
    在这里插入图片描述

    3.kd-tree 的复杂度

    在这里插入图片描述
    优化kd-tree复杂度的方法
    在这里插入图片描述

    3.kd-tree -kNN Search

    在这里插入图片描述
    是否搜索的判断
    在这里插入图片描述

    个人重要知识点补漏

    1.assert断言函数

    assert函数可以用于差错

    def sort_key_by_vale(key, value):
        assert key.shape == value.shape       #assert 断言操作,用于判断一个表达式,在表达式条件为false的时候触发异常
        assert len(key.shape) == 1            #numpy是多维数组
        sorted_idx = np.argsort(value)        #对value值进行排序
        key_sorted = key[sorted_idx]
        value_sorted = value[sorted_idx]      #进行升序排序
        return key_sorted, value_sorted
    

    2.kd-tree的核心在于分割与排序,下图红框正是精华所在,不断排序在对应轴上的点

    在这里插入图片描述

    def axis_round_robin(axis, dim):         #用于轴的轮换
        if axis == dim-1:
            return 0
        else:
            return axis + 1
    

    3.np.linalg.norm()函数用于求二范数,当org=2(默认),可以理解为求对应点的模

        if root.is_leaf():
            # compare the contents of a leaf
            leaf_points = db[root.point_indices, :]
            diff = np.linalg.norm(np.expand_dims(query, 0) - leaf_points, axis=1)             #取行的差值,暴力搜索
            for i in range(diff.shape[0]):
                result_set.add_point(diff[i], root.point_indices[i])
            return False
    

    4.axis = 0 ,axis = 1 的混淆点

    1.在二维数组里,axis=1代表纵向推移,axis=0代表横向推移

    在这里插入图片描述

    2.在numpy高维数组里,axis=1代表横向推移,axis=0代表纵向推移

    代码

    import random
    import math
    import numpy as np
    
    from lidar_KnnRnnClass_2 import KNNResultSet, RadiusNNResultSet
    
    
    class Node:
        def __init__(self, axis, value, left, right, point_indices):
            self.axis = axis
            self.value = value
            self.left = left
            self.right = right
            self.point_indices = point_indices
    
        def is_leaf(self):
            if self.value is None:
                return True
            else:
                return False
    
        def __str__(self):
            output = ''
            output += 'axis %d, ' % self.axis
            if self.value is None:
                output += 'split value: leaf, '
            else:
                output += 'split value: %.2f, ' % self.value
            output += 'point_indices: '
            output += str(self.point_indices.tolist())
            return output
    
    
    def sort_key_by_vale(key, value):
        assert key.shape == value.shape       #assert 断言操作,用于判断一个表达式,在表达式条件为false的时候触发异常
        assert len(key.shape) == 1            #numpy是多维数组
        sorted_idx = np.argsort(value)        #对value值进行排序
        key_sorted = key[sorted_idx]
        value_sorted = value[sorted_idx]      #进行升序排序
        return key_sorted, value_sorted
    
    
    def axis_round_robin(axis, dim):         #用于轴的轮换
        if axis == dim-1:
            return 0
        else:
            return axis + 1
    
    
    def kdtree_recursive_build(root, db, point_indices, axis, leaf_size):    #kd树的建立
        """
        :param root:
        :param db: NxD
        :param db_sorted_idx_inv: NxD
        :param point_idx: M
        :param axis: scalar
        :param leaf_size: scalar
        :return:
        """
        if root is None:
            root = Node(axis, None, None, None, point_indices)           #实例化Node
    
        # determine whether to split into left and right
        if len(point_indices) > leaf_size:                              #判断是否需要进行分割
            # --- get the split position ---
            point_indices_sorted, _ = sort_key_by_vale(point_indices, db[point_indices, axis])  #对点进行排列,dp存储信息
            middle_left_idx = math.ceil(point_indices_sorted.shape[0] / 2) - 1     #分一半
            middle_left_point_idx = point_indices_sorted[middle_left_idx]          #左边界点
            middle_left_point_value = db[middle_left_point_idx, axis]
    
            middle_right_idx = middle_left_idx + 1
            middle_right_point_idx = point_indices_sorted[middle_right_idx]
            middle_right_point_value = db[middle_right_point_idx, axis]           #右边界点
    
            root.value = (middle_left_point_value + middle_right_point_value) * 0.5    #取中值为节点值
            # === get the split position ===
            root.left = kdtree_recursive_build(root.left,
                                               db,
                                               point_indices_sorted[0:middle_right_idx],
                                               axis_round_robin(axis, dim=db.shape[1]),
                                               leaf_size)                                  #对对应的轴值进行排序
            root.right = kdtree_recursive_build(root.right,
                                               db,
                                               point_indices_sorted[middle_right_idx:],
                                               axis_round_robin(axis, dim=db.shape[1]),
                                               leaf_size)                                  #对对应的轴值进行排序
        return root
    
    
    def traverse_kdtree(root: Node, depth, max_depth):      #计算kdtree的深度
        depth[0] += 1
        if max_depth[0] < depth[0]:
            max_depth[0] = depth[0]
    
        if root.is_leaf():                                 #打印最后的叶子节点
            print(root)
        else:
            traverse_kdtree(root.left, depth, max_depth)    #累加计算深度
            traverse_kdtree(root.right, depth, max_depth)
    
        depth[0] -= 1
    
    
    def kdtree_construction(db_np, leaf_size):
        N, dim = db_np.shape[0], db_np.shape[1]
    
        # build kd_tree recursively
        root = None
        root = kdtree_recursive_build(root,
                                      db_np,
                                      np.arange(N),
                                      axis=0,
                                      leaf_size=leaf_size)
        return root
    
    
    def kdtree_knn_search(root: Node, db: np.ndarray, result_set: KNNResultSet, query: np.ndarray):   #KNNResultSet 继承二叉树的结果集
        if root is None:
            return False
    
        if root.is_leaf():
            # compare the contents of a leaf
            leaf_points = db[root.point_indices, :]
            diff = np.linalg.norm(np.expand_dims(query, 0) - leaf_points, axis=1)
            for i in range(diff.shape[0]):
                result_set.add_point(diff[i], root.point_indices[i])
            return False
    
        if query[root.axis] <= root.value:          #如果 q[axis] inside the partition   如果查询点在根节点的左边,一定要查找左边
            kdtree_knn_search(root.left, db, result_set, query)
            if math.fabs(query[root.axis] - root.value) < result_set.worstDist():   #如果目标点离轴虚线的距离小于worst_dist 继续搜寻节点的右边
                kdtree_knn_search(root.right, db, result_set, query)
        else:
            kdtree_knn_search(root.right, db, result_set, query)
            if math.fabs(query[root.axis] - root.value) < result_set.worstDist():
                kdtree_knn_search(root.left, db, result_set, query)
    
        return False
    
    
    def kdtree_radius_search(root: Node, db: np.ndarray, result_set: RadiusNNResultSet, query: np.ndarray):
        if root is None:
            return False
    
        if root.is_leaf():
            # compare the contents of a leaf
            leaf_points = db[root.point_indices, :]
            diff = np.linalg.norm(np.expand_dims(query, 0) - leaf_points, axis=1)
            for i in range(diff.shape[0]):
                result_set.add_point(diff[i], root.point_indices[i])
            return False
    
        if query[root.axis] <= root.value:
            kdtree_radius_search(root.left, db, result_set, query)
            if math.fabs(query[root.axis] - root.value) < result_set.worstDist():
                kdtree_radius_search(root.right, db, result_set, query)
        else:
            kdtree_radius_search(root.right, db, result_set, query)
            if math.fabs(query[root.axis] - root.value) < result_set.worstDist():
                kdtree_radius_search(root.left, db, result_set, query)
    
        return False
    
    
    
    def main():
        # configuration
        db_size = 64
        dim = 3                #三维
        leaf_size = 4
        k = 1                  #一个点
    
        db_np = np.random.rand(db_size, dim)
    
        root = kdtree_construction(db_np, leaf_size=leaf_size)
    
        depth = [0]
        max_depth = [0]
        traverse_kdtree(root, depth, max_depth)
        print("tree max depth: %d" % max_depth[0])
    
        # query = np.asarray([0, 0, 0])
        # result_set = KNNResultSet(capacity=k)
        # knn_search(root, db_np, result_set, query)
        #
        # print(result_set)
        #
        # diff = np.linalg.norm(np.expand_dims(query, 0) - db_np, axis=1)
        # nn_idx = np.argsort(diff)
        # nn_dist = diff[nn_idx]
        # print(nn_idx[0:k])
        # print(nn_dist[0:k])
        #
        #
        # print("Radius search:")
        # query = np.asarray([0, 0, 0])
        # result_set = RadiusNNResultSet(radius = 0.5)
        # radius_search(root, db_np, result_set, query)
        # print(result_set)
    
    
    if __name__ == '__main__':
        main()
    

     

    展开全文
  • KD-Tree C++程序

    2016-05-31 09:15:39
    一个清晰明了的KD-Tree程序,用来学习很不错
  • Kd-Tree算法原理和开源实现代码   本文介绍一种用于高维空间中的快速最近邻和近似最近邻查找技术——Kd-TreeKd树)。Kd-Tree,即K-dimensional tree,是一种高维索引树形数据结构,常用于在大规模的高维数据...
  • 基于Kd-tree最近邻居搜索的快速dbscan算法 调用方式: double eps = 0.02 ; // radius of searching int minPts = 1 ; // minimus points number Dbscan< Clusterable> dbscan = new Dbscan< Clusterable> (eps, ...
  • 使用kd-tree加速k-means

    2021-02-13 01:09:56
    //选取方差大的维度,会需要很长时间//改成使用选取数据范围最大的维度//这样构建kdtree的速度会变快,但是在kmean更新中心点会变慢 boolean isleaf = true;for(int i=0;i isleaf=false;break; }if(isleaf){ node....
  • 今天上点硬菜,我们来看一个机器学习领域经常用到的数据结构——KD-Tree。从线段树到KD树在讲KD树之前,我们先来了解一下线段树的概念。线段树在机器学习领域当中不太常见,作为高性能维...
  • kdtree(kd-树)的mex库,它允许最近邻域,k最近邻域,范围等查询 kd-tree的简约实现。该实现既可以通过MEX调用在MATLAB内部使用,也可以直接从C / C ++程序中作为独立工具使用。网站上的图像已使用“ fulltest.m”...
  • kd-tree的python实现

    千次阅读 2018-03-28 00:02:14
    [ kD-tree的C语言实现 ]是多年前写过的一篇kd-tree的博客。当时正在看李航老师的《统计学习方法》一书,看到kNN算法和kd-tree之间的关系,非常有兴趣进行深入了解,所以汇总了一些资料,后面由于实际工作中用不到,...
  • Kd-tree改进后的BBF算法

    2018-03-02 16:04:37
    文档内对BBF算法原理进行了详细的说明,并附带源码以及源码解释
  • kd-tree的基本教程PDF

    2010-07-12 11:47:14
    关于kd-tree的基本教程,作者是Andrew W. Moore
  • KD-Tree算法

    万次阅读 多人点赞 2018-05-06 21:49:08
    kd树(k-dimensional树的简称),是一种分割k维数据空间的数据结构,主要... 一、Kd-tree其实KDTree就是二叉查找树(Binary Search Tree,BST)的变种。二叉查找树的性质如下:1)若它的左子树不为空,则左子树上所...
  • KD-Tree

    2019-05-18 17:24:00
    http://www.cnblogs.com/lysuns/articles/4710712.html
  • kd-tree算法 matlab

    2010-04-20 14:34:20
    matlab可用的kd-tree算法,运行时请将mex下对应系统的文件加入到matlab路径中
  • 三维点云处理:8 Kd-tree: 二叉树适合简单的一维查找,涉及到二维的查找就需要用到Kd-tree。k即为k-dim,k维的意思。 KD-tree和二叉树的原理是一样的。在二维平面中对平面不断切分。...kdtree查找:
  • 点云聚类及匹配(KD-Tree & OCTree)

    千次阅读 2021-10-11 18:06:09
    int main() { int queryNum = 3;//用于设置返回邻近点的个数 vector<float> vecQuery(2);//存放查询点的容器 vector<int> vecIndex(queryNum);//存放返回的点索引 ... cv::flann::KDTre
  • Kd-Tree算法原理 最近邻查找

    千次阅读 2018-08-22 09:12:38
    本文介绍一种用于高维空间中的快速最近邻和近似最近邻...Kd-Tree,即K-dimensional tree,是一种高维索引树形数据结构,常用于在大规模的高维数据空间进行最近邻查找(Nearest Neighbor)和近似最近邻查找(Approxi...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,819
精华内容 5,927
关键字:

kd-tree