|
三维点云学习（2）中-Kd-tree (k-dimensional tree)
kd-tree 实现
代码来自黎老师github
三维kd-tree 的图示
如下图所示，为三维kd-tree的切割图，进行三个维度的切割，kd-tree的本质就是对三个维度的数据点不断构建平衡二叉树。 
运行结果
axis 1, split value: leaf, point_indices: [24, 43, 48, 39]
axis 1, split value: leaf, point_indices: [10, 22, 37, 14]
axis 1, split value: leaf, point_indices: [17, 41, 4, 51]
axis 1, split value: leaf, point_indices: [55, 44, 27, 12]
axis 1, split value: leaf, point_indices: [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 result_set 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] |