点云数据主要是表征目标表面的海量点集合,并不具备传统实体网格数据的集合拓扑信息。因此,如何建立离散点间的拓扑关系,实现基于邻域关系的快速查找也是点云数据处理中比较核心的问题。对于一维数据来说,典型的树形存储结构如Binary Search Tree(BST),特点在于:对于树中的每个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值,即中序遍历是有序的。这种结构在执行搜索操作时效率较高,在平均情况下,如果树保持相对平衡,BST 的时间复杂度为 O(log n)。
对于高维数据,同样可以采用这种自顶向下逐级划分数据的空间索引结构,如三维数据中比较常见的KD-Tree和Octree。本节主要是学习理解KD-Tree/Octree的构建以及近邻搜索原理,仅作为学习记录!
k-d tree,也称 k 维树,是对数据点在 k 维空间(如二维-xy,三维-xyz,K维-xyz…k)中划分的一种数据结构,主要应用于多维空间数据的搜索(如最近邻搜索、范围搜索)。k-d tree 的每一级在指定维度上(如 x 轴)分开了所有的子节点,在该维度上,小于根节点的部分划分为左子树,大于根节点的部分划分到右子树,所以本质上也是一种带有约束条件的二分查找树。
基本思想:采用分而治之的思想,根据数据特征选择一个合适的维度作为切分维度,并根据该维度的中位数作为切分值,进而根据切分维度和切分值,将数据点分割成两个子集,左子集包含小于等于切分值的数据点,右子集包含大于切分值的数据点,直到所有数据都切分完成。
经典的构造KD-Tree的方式如下:
这部分依然以三维数据作为输入进行代码练习。切分点使用当前维度上数据的均值来代替中值,切分超平面采用xyz轴轮转的形式。主要流程如下:
#pragma once
#include <memory>
#include <vector>
#include <Eigen/Dense>
#include <Eigen/Core>
// 定义KD-Tree的基础节点
typedef struct KDTreeNode{
int axis; // 切分轴
double key; // 切分点
bool is_leaf; // 是否为叶子节点
std::vector<int> value_indices; // 当前节点内存放的数据索引
std::shared_ptr<KDTreeNode> left; // 左节点
std::shared_ptr<KDTreeNode> right; // 右节点
KDTreeNode(): axis(-1), key(0), is_leaf(false) {
}
KDTreeNode(int axis_): axis(axis_), key(0), is_leaf(false) {
}
} KDTreeNode;
// 定义KD-Tree
// 属性:根节点、点云数据
// 方法:点云数据初始化、构建KD-Tree(对外接口)、递归构建KD-Tree(对内接口)、获取根节点
// 辅助方法:获取数据当前节点的切分信息(key,value_indices,左子树索引、右子树索引),获取切分轴
class KDTree{
public:
void set_data(const Eigen::MatrixXd& input_data); // 输入数据
bool create_kd_tree(int leaf_size); // 构建KD-Tree(外部接口)
std::shared_ptr<KDTreeNode> get_root(); // 获取KD-Tree的根节点(外部接口)
private:
// 递归构建KD-Tree
// 输入:需要构建的节点、原始数据、待构建的点索引、切分轴、叶子节点最少点数
bool create_kd_tree_recursive(std::shared_ptr<KDTreeNode>& root,
const Eigen::MatrixXd& values,
std::vector<int>& value_indives,
int axis,
int leaf_size);
// 获取构建当前节点需要的分割数据
// 输入:原始数据、待构建的点索引、切分轴
// 输出:切分值、切分值对应的索引、切分后的左节点索引、切分后的右节点索引
bool get_median_key_and_left_right_value_indices_maxmin(
const Eigen::MatrixXd& values,
const std::vector<int> value_indives,
int axis,
double& median_key,
std::vector<int>& median_value_indices,
std::vector<int>& left_value_indices,
std::vector<int>& right_value_indices);
int get_next_axis(int axis, int dim);
private:
Eigen::MatirxXd _data;
std::shared_ptr<KDTreeNode> _root;
};
#include "KD_Tree.h"
void KDTree::set_data(const Eigen::MatrixXd& input_data){
_data = input_data;
}
std::shared_ptr<KDTreeNode> KDTree::get_root(){
return _root;
}
bool KDTree::create_kd_tree(int leaf_size){
// 构建数据的索引列表
std::vector<int> value_indices;
for(size_t i = 0; i < _data.cols(); ++i){
value_indices.emplace_back(i);
}
return create_kd_tree_recursive(_root, _data, value_indices, 0, leaf_size);
}
bool KDTree::create_kd_tree_recursive(std::shared_ptr<KDTreeNode>& root,
const Eigen::MatrixXd& values,
std::vector<int> value_indives,
int axis,
int leaf_size){
// 判断当前节点是否为空
if(root == nullptr){
root.reset(new KDTreeNode(axis));
}
// 判断是否需要切分
if(value_indives.size() > leaf_size){
double median_key;
std::vector<int> median_value_indices, left_value_indices, right_values_indices;
get_median_key_and_left_right_value_indices_maxmin(values, value_indives, axis,
median_key, median_value_indices, left_value_indices, right_values_indices);
// 构建当前节点
root->is_leaf = false;
root->key = median_key;
root->value_indices = median_value_indices;
// 构建左右子树
int next_axis = get_next_axis(axis, values.rows());
create_kd_tree_recursive(root->left, values, left_value_indices, next_axis, leaf_size);
create_kd_tree_recursive(root->right, values, right_value_indices, next_axis, leaf_size);
}else{
root->is_leaf = true;
root->value_indices = value_indives;
}
return true;
}
bool KDTree::get_median_key_and_left_right_value_indices_maxmin(
const Eigen::MatrixXd& values,
const std::vector<int> value_indives,
int axis,
double& median_key,
std::vector<int>& median_value_indices,
std::vector<int>& left_value_indices,
std::vector<int>& right_value_indices){
// 获取均值
Eigen::VectorXd tmp_values(value_indives.size());
for(int i = 0; i < value_indives.size(); ++i){
tmp_values(i) = values(axis, value_indives[i]);
}
double max = tmp_values.maxCoeff();
double min = tmp_values.minCoeff();
if(max > min){
median_key = min + (max - min) / 2;
// 遍历所有点划分索引区分
for(int i = 0; i < value_indives.size(); ++i){
if(tmp_values(i) == median_key){
median_value_indices.emplace_back(value_indives[i]);
}else if(tmp_values(i) < median_key){
left_value_indices.emplace_back(value_indives[i]);
}else{
right_value_indices.emplace_back(value_indives[i]);
}
}
}else{
median_key = min;
int median_idx = floor(value_indives.size() / 2);
median_value_indices = std::vector<int>(
value_indices.begin() + median_idx, value_indices.begin() + median_idx + 1);
left_value_indices = std::vector<int>(
value_indices.begin(), value_indices.begin() + median_idx);
right_value_indices = std::vector<int>(
value_indices.begin() + median_idx + 1, value_indices.end());
}
return true;
}
int KDTree::get_next_axis(int axis, int dim){
if(axis >= dim -1){
return 0;
}else{
return axis + 1;
}
}
#inlcude "KD_Tree.h"
int main(){
Eigen::MatrixXd data(3, 4);
data << 1, 2, 3, 4,
1, 2, 1, 2,
0, 1, 2, 3;
KDTree kd_tree;
kd_tree.input(data);
kd_tree.create_kd_tree(1);
return 0;
}
八叉树结构是 Hunter 博士于 1978 年首次提出的一种数据模型,通过循环递归的划分方法对大小为2n x 2n x 2n 的三维空间的几何对象进行划分,从而构成一个具有根节点的方向图。如下图所示:
基本思想:基于设定的最短分割长度或最少数据约束,以数据的最大尺寸构建根节点,递归地将数据切分到八个子立方体中,直到所有数据都切分完成。
Octree的构建原理及一般步骤如下:
这部分依然以三维数据作为输入进行代码练习。Octree构建的主要流程如下:
#pragma once
#include <memory>
#include <vector>
#include <Eigen/Dense>
#include <Eigen/Core>
// 定义Octree的基础节点
typedef struct Octant{
Eigen::Vector3d center;
double extent;
std::vector<u_int> value_indices;
bool is_leaf;
std::shared_ptr<Octant> children[8];
Octant(){
}
Octant(const Eigen::Vector3d& center_, double extent_, const std::vector<u_int> value_indices_, bool is_leaf_)
: center(center_), extent(extent_), value_indices(value_indices_), is_leaf(is_leaf_){
}
}Octant;
// 定义KD-Tree
// 属性:根节点、点云数据、叶子节点最少点数、叶子节点最短分割长度
// 方法:点云数据初始化、构建Octree(对外接口)、递归构建Octree(对内接口)
class Octree{
public:
void set_data(const Eigen::MatrixXd& input_data);
bool build(int leaf_size, double min_length);
std::shared_ptr<Octant> get_root();
private:
// 递归构建子节点
// 输入:需要构建的节点、点云数据、待分配的数据索引、立方体中心,立方体扩展长度
build build_octree_recursive(std::shared_ptr<Octant>& root,
const Eigen::MatirxXd& values,
const std::vector<u_int>& value_indices,
const Eigen::Vector3d& center,
double extent);
private:
Eigen::MatrixXd _data;
std::shared_ptr<Octant> _root;
// 子节点细分终止条件
int _leaf_size;
double _min_extent;
};
#include "Octree.h"
#include <map>
void Octree::set_data(const Eigen::MatrixXd& input_data){
_data = input_data;
}
std::shared_ptr<Octant> Octree::get_root(){
return _root;
}
bool Octree::build(int leaf_size, double min_length){
_leaf_size = leaf_size;
_min_extent = min_length / 2;
// 计算立方体中心点
Eigen::Vector3d max_value = _data.rowwise().maxCoeff();
Eigen::Vector3d min_value = _data.rowwise().minCoeff();
Eigen::Vector3d center = min_value + (max_value - min_value) / 2;
double extent = (max_value - min_value).maxCoeff() / 2;
// 获取需要细分的数据索引
std::vector<u_int> value_indices;
for(size_t i = 0; i < _data.cols(); ++i){
value_indices.emplace_back(i);
}
// 递归构建Octree
return build_octree_recursive(_root, _data, value_indices, center, extent);
}
build Octree::build_octree_recursive(std::shared_ptr<Octant>& root,
const Eigen::MatirxXd& values,
const std::vector<u_int>& value_indices,
const Eigen::Vector3d& center,
double extent){
// 判断索引列表是否为空
if(value_indices.size() == 0){
return false;
}
// 判断当前节点是否为空
if(root == nullptr){
root.reset(center, extent, value_indices, false);
}
// 判断是否需要细分
if(value_indices.size() < _leaf_size || extent < _min_extent){
root->is_leaf = true;
}else{
// 计算每个点所属子节点
std::map<u_char, std::vector<u_int>> children_value_indices;
for(size_t i = 0; i < value_indices.size(); ++i){
u_char morton_mode = 0;
const Eigen::Vector3d& value_tmp = values.col(value_indices[i]);
if(value_tmp(0) > center(0)) morton_mode |= 1;
if(value_tmp(1) > center(1)) morton_mode |= 2;
if(value_tmp(2) > center(2)) morton_mode |= 4;
children_value_indices[morton].emplace_back(value_indices[i]);
}
// 递归构建子节点
double factor[2] = {
-0.5, 0.5};
for(int i = 0; i < 8; ++i){
Eigen::Vector3d child_center;
child_center(0) = center[0] + factor[int((i & 1) > 0)] * extent;
child_center(1) = center[1] + factor[int((i & 2) > 0)] * extent;
child_center(2) = center[2] + factor[int((i & 4) > 0)] * extnet;
double child_extent = 0.5 * extent;
build_octree_recursive(root->children[i], values,
children_value_indices[i], child_center, child_extent);
}
return true;
}
#include "Octree.h"
int main(){
Eigen::MatrixXd data(3, 4);
data << -1, 1, -1, 1,
-1, -1, 1, 1,
0, 0, 0, 0;
Octree oct;
oct.set_data(data);
oct.build(1, 1);
return 0;
}
文章浏览阅读3.8k次,点赞9次,收藏28次。直接上一个工作中碰到的问题,另外一个系统开启多线程调用我这边的接口,然后我这边会开启多线程批量查询第三方接口并且返回给调用方。使用的是两三年前别人遗留下来的方法,放到线上后发现确实是可以正常取到结果,但是一旦调用,CPU占用就直接100%(部署环境是win server服务器)。因此查看了下相关的老代码并使用JProfiler查看发现是在某个while循环的时候有问题。具体项目代码就不贴了,类似于下面这段代码。while(flag) {//your code;}这里的flag._main函数使用while(1)循环cpu占用99
文章浏览阅读347次。idea shift f6 快捷键无效_idea shift +f6快捷键不生效
文章浏览阅读135次。Ecmacript 中没有DOM 和 BOM核心模块Node为JavaScript提供了很多服务器级别,这些API绝大多数都被包装到了一个具名和核心模块中了,例如文件操作的 fs 核心模块 ,http服务构建的http 模块 path 路径操作模块 os 操作系统信息模块// 用来获取机器信息的var os = require('os')// 用来操作路径的var path = require('path')// 获取当前机器的 CPU 信息console.log(os.cpus._node模块中有很多核心模块,以下不属于核心模块,使用时需下载的是
文章浏览阅读10w+次,点赞435次,收藏3.4k次。SPSS 22 下载安装过程7.6 方差分析与回归分析的SPSS实现7.6.1 SPSS软件概述1 SPSS版本与安装2 SPSS界面3 SPSS特点4 SPSS数据7.6.2 SPSS与方差分析1 单因素方差分析2 双因素方差分析7.6.3 SPSS与回归分析SPSS回归分析过程牙膏价格问题的回归分析_化工数学模型数据回归软件
文章浏览阅读7.5k次。如何利用hutool工具包实现邮件发送功能呢?1、首先引入hutool依赖<dependency> <groupId>cn.hutool</groupId> <artifactId>hutool-all</artifactId> <version>5.7.19</version></dependency>2、编写邮件发送工具类package com.pc.c..._hutool发送邮件
文章浏览阅读867次,点赞2次,收藏2次。docker安装elasticsearch,elasticsearch-head,kibana,ik分词器安装方式基本有两种,一种是pull的方式,一种是Dockerfile的方式,由于pull的方式pull下来后还需配置许多东西且不便于复用,个人比较喜欢使用Dockerfile的方式所有docker支持的镜像基本都在https://hub.docker.com/docker的官网上能找到合..._docker安装kibana连接elasticsearch并且elasticsearch有密码
文章浏览阅读1.3w次,点赞57次,收藏92次。整理 | 郑丽媛出品 | CSDN(ID:CSDNnews)近年来,随着机器学习的兴起,有一门编程语言逐渐变得火热——Python。得益于其针对机器学习提供了大量开源框架和第三方模块,内置..._beeware
文章浏览阅读7.9k次。//// ViewController.swift// Day_10_Timer//// Created by dongqiangfei on 2018/10/15.// Copyright 2018年 飞飞. All rights reserved.//import UIKitclass ViewController: UIViewController { ..._swift timer 暂停
文章浏览阅读986次,点赞2次,收藏2次。1.硬性等待让当前线程暂停执行,应用场景:代码执行速度太快了,但是UI元素没有立马加载出来,造成两者不同步,这时候就可以让代码等待一下,再去执行找元素的动作线程休眠,强制等待 Thread.sleep(long mills)package com.example.demo;import org.junit.jupiter.api.Test;import org.openqa.selenium.By;import org.openqa.selenium.firefox.Firefox.._元素三大等待
文章浏览阅读3k次,点赞4次,收藏14次。Java软件工程师职位分析_java岗位分析
文章浏览阅读2k次。Java:Unreachable code的解决方法_java unreachable code
文章浏览阅读1w次。1、html中设置标签data-*的值 标题 11111 222222、点击获取当前标签的data-url的值$('dd').on('click', function() { var urlVal = $(this).data('ur_如何根据data-*属性获取对应的标签对象