如何使用KdTree进行搜索（How to use a KdTree to search）

2023-10-20 19:38
文章标签 进行 use 使用 搜索 search kdtree

本文主要是介绍如何使用KdTree进行搜索（How to use a KdTree to search），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在本教程中，我们将详细介绍如何使用KdTree来查找特定点或位置的K个最近邻居，然后我们将继续介绍如何在用户指定的半径范围内找到所有邻居（在本例中为随机） 。

#理论引入

kd树或k维树是计算机科学中用于在具有k维的空间中组织若干点的数据结构。这是一个二叉搜索树，其他约束条件是强加给它的。Kd树对于范围和最近的邻居搜索非常有用。就我们的目的而言，我们通常只会在三维空间中处理点云，所以我们所有的kd树都是三维的。kd树的每个级别都使用与相应轴垂直的超平面沿特定维度分割所有的孩子。在树的根部，所有的孩子都将根据第一维进行分割（即，如果第一维坐标小于根，它将在左子树中，并且如果它大于根，则显然将在正确的子树）。树下的每一层在下一个维度上分开，一旦所有其他维度都用尽，则返回到第一维。构建kd树的最有效的方法是使用像Quick Sort一样使用的分区方法将中间点放在根上，并将所有具有较小一维值的东西放在左边，并且放大到右边。然后，在左侧和右侧的子树上重复此过程，直到要分区的最后一棵树仅由一个元素组成。

来自Wikipedia：

一个二维kd树的例子
这是一个二维kd树的例子

这是最近邻居搜索工作的一个小时的示范。

#代码
用你最喜欢的编辑器创建一个名为kdtree_search.cpp的文件，并在里面放置以下内容：

#include <pcl/point_cloud.h>
#include <pcl/kdtree/kdtree_flann.h>#include <iostream>
#include <vector>
#include <ctime>int
main (int argc, char** argv)
{srand (time (NULL));pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);// Generate pointcloud datacloud->width = 1000;cloud->height = 1;cloud->points.resize (cloud->width * cloud->height);for (size_t i = 0; i < cloud->points.size (); ++i){cloud->points[i].x = 1024.0f * rand () / (RAND_MAX + 1.0f);cloud->points[i].y = 1024.0f * rand () / (RAND_MAX + 1.0f);cloud->points[i].z = 1024.0f * rand () / (RAND_MAX + 1.0f);}pcl::KdTreeFLANN<pcl::PointXYZ> kdtree;kdtree.setInputCloud (cloud);pcl::PointXYZ searchPoint;searchPoint.x = 1024.0f * rand () / (RAND_MAX + 1.0f);searchPoint.y = 1024.0f * rand () / (RAND_MAX + 1.0f);searchPoint.z = 1024.0f * rand () / (RAND_MAX + 1.0f);// K nearest neighbor searchint K = 10;std::vector<int> pointIdxNKNSearch(K);std::vector<float> pointNKNSquaredDistance(K);std::cout << "K nearest neighbor search at (" << searchPoint.x << " " << searchPoint.y << " " << searchPoint.z<< ") with K=" << K << std::endl;if ( kdtree.nearestKSearch (searchPoint, K, pointIdxNKNSearch, pointNKNSquaredDistance) > 0 ){for (size_t i = 0; i < pointIdxNKNSearch.size (); ++i)std::cout << "    "  <<  cloud->points[ pointIdxNKNSearch[i] ].x << " " << cloud->points[ pointIdxNKNSearch[i] ].y << " " << cloud->points[ pointIdxNKNSearch[i] ].z << " (squared distance: " << pointNKNSquaredDistance[i] << ")" << std::endl;}// Neighbors within radius searchstd::vector<int> pointIdxRadiusSearch;std::vector<float> pointRadiusSquaredDistance;float radius = 256.0f * rand () / (RAND_MAX + 1.0f);std::cout << "Neighbors within radius search at (" << searchPoint.x << " " << searchPoint.y << " " << searchPoint.z<< ") with radius=" << radius << std::endl;if ( kdtree.radiusSearch (searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance) > 0 ){for (size_t i = 0; i < pointIdxRadiusSearch.size (); ++i)std::cout << "    "  <<  cloud->points[ pointIdxRadiusSearch[i] ].x << " " << cloud->points[ pointIdxRadiusSearch[i] ].y << " " << cloud->points[ pointIdxRadiusSearch[i] ].z << " (squared distance: " << pointRadiusSquaredDistance[i] << ")" << std::endl;}return 0;
}

#说明
下面的代码首先将rand()与系统时间联系起来，然后用随机数据创建并填充PointCloud。

  srand (time (NULL));pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);// Generate pointcloud datacloud->width = 1000;cloud->height = 1;cloud->points.resize (cloud->width * cloud->height);for (size_t i = 0; i < cloud->points.size (); ++i){cloud->points[i].x = 1024.0f * rand () / (RAND_MAX + 1.0f);cloud->points[i].y = 1024.0f * rand () / (RAND_MAX + 1.0f);cloud->points[i].z = 1024.0f * rand () / (RAND_MAX + 1.0f);}

下一个代码创建我们的kdtree对象，并将我们随机创建的云作为输入。然后我们创建一个分配随机坐标的“searchPoint”。

  pcl::KdTreeFLANN<pcl::PointXYZ> kdtree;kdtree.setInputCloud (cloud);pcl::PointXYZ searchPoint;searchPoint.x = 1024.0f * rand () / (RAND_MAX + 1.0f);searchPoint.y = 1024.0f * rand () / (RAND_MAX + 1.0f);searchPoint.z = 1024.0f * rand () / (RAND_MAX + 1.0f);

现在我们创建一个整数（并设置它等于10）和两个向量来存储我们搜索到的最近邻居。

  // K nearest neighbor searchint K = 10;std::vector<int> pointIdxNKNSearch(K);std::vector<float> pointNKNSquaredDistance(K);std::cout << "K nearest neighbor search at (" << searchPoint.x << " " << searchPoint.y << " " << searchPoint.z<< ") with K=" << K << std::endl;

假设我们的KdTree返回多于0个最接近的邻居，它将把所有10个最近邻居的位置打印到我们的随机“searchPoint”中，这个“searchPoint”被存储在我们以前创建的向量中。

  if ( kdtree.nearestKSearch (searchPoint, K, pointIdxNKNSearch, pointNKNSquaredDistance) > 0 ){for (size_t i = 0; i < pointIdxNKNSearch.size (); ++i)std::cout << "    "  <<  cloud->points[ pointIdxNKNSearch[i] ].x << " " << cloud->points[ pointIdxNKNSearch[i] ].y << " " << cloud->points[ pointIdxNKNSearch[i] ].z << " (squared distance: " << pointNKNSquaredDistance[i] << ")" << std::endl;}

现在我们的代码演示了在某个（随机生成的）半径内找到给定的“searchPoint”的所有邻居。它再次创建2个向量来存储关于我们的邻居的信息。

  // Neighbors within radius searchstd::vector<int> pointIdxRadiusSearch;std::vector<float> pointRadiusSquaredDistance;float radius = 256.0f * rand () / (RAND_MAX + 1.0f);

再次，像以前一样，如果我们的KdTree在指定的半径范围内返回多于0个邻居，它将打印出已存储在我们向量中的这些点的坐标。

  if ( kdtree.radiusSearch (searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance) > 0 ){for (size_t i = 0; i < pointIdxRadiusSearch.size (); ++i)std::cout << "    "  <<  cloud->points[ pointIdxRadiusSearch[i] ].x << " " << cloud->points[ pointIdxRadiusSearch[i] ].y << " " << cloud->points[ pointIdxRadiusSearch[i] ].z << " (squared distance: " << pointRadiusSquaredDistance[i] << ")" << std::endl;}

#编译和运行程序
将下面的行添加到您的CMakeLists.txt文件中：

cmake_minimum_required(VERSION 2.8 FATAL_ERROR)project(kdtree_search)find_package(PCL 1.2 REQUIRED)include_directories(${PCL_INCLUDE_DIRS})
link_directories(${PCL_LIBRARY_DIRS})
add_definitions(${PCL_DEFINITIONS})add_executable (kdtree_search kdtree_search.cpp)
target_link_libraries (kdtree_search ${PCL_LIBRARIES})

制作好可执行文件之后，就可以运行它了。简单地做：

./kdtree_search

一旦你运行它，你应该看到类似的东西：

K nearest neighbor search at (455.807 417.256 406.502) with K=10494.728 371.875 351.687 (squared distance: 6578.99)506.066 420.079 478.278 (squared distance: 7685.67)368.546 427.623 416.388 (squared distance: 7819.75)474.832 383.041 323.293 (squared distance: 8456.34)470.992 334.084 468.459 (squared distance: 10986.9)560.884 417.637 364.518 (squared distance: 12803.8)466.703 475.716 306.269 (squared distance: 13582.9)456.907 336.035 304.529 (squared distance: 16996.7)452.288 387.943 279.481 (squared distance: 17005.9)476.642 410.422 268.057 (squared distance: 19647.9)
Neighbors within radius search at (455.807 417.256 406.502) with radius=225.932494.728 371.875 351.687 (squared distance: 6578.99)506.066 420.079 478.278 (squared distance: 7685.67)368.546 427.623 416.388 (squared distance: 7819.75)474.832 383.041 323.293 (squared distance: 8456.34)470.992 334.084 468.459 (squared distance: 10986.9)560.884 417.637 364.518 (squared distance: 12803.8)466.703 475.716 306.269 (squared distance: 13582.9)456.907 336.035 304.529 (squared distance: 16996.7)452.288 387.943 279.481 (squared distance: 17005.9)476.642 410.422 268.057 (squared distance: 19647.9)499.429 541.532 351.35 (squared distance: 20389)574.418 452.961 334.7 (squared distance: 20498.9)336.785 391.057 488.71 (squared distance: 21611)319.765 406.187 350.955 (squared distance: 21715.6)528.89 289.583 378.979 (squared distance: 22399.1)504.509 459.609 541.732 (squared distance: 22452.8)539.854 349.333 300.395 (squared distance: 22936.3)548.51 458.035 292.812 (squared distance: 23182.1)546.284 426.67 535.989 (squared distance: 25041.6)577.058 390.276 508.597 (squared distance: 25853.1)543.16 458.727 276.859 (squared distance: 26157.5)613.997 387.397 443.207 (squared distance: 27262.7)608.235 467.363 327.264 (squared distance: 32023.6)506.842 591.736 391.923 (squared distance: 33260.3)529.842 475.715 241.532 (squared distance: 36113.7)485.822 322.623 244.347 (squared distance: 36150.5)362.036 318.014 269.201 (squared distance: 37493.6)493.806 600.083 462.742 (squared distance: 38032.3)392.315 368.085 585.37 (squared distance: 38442.9)303.826 428.659 533.642 (squared distance: 39392.8)616.492 424.551 289.524 (squared distance: 39556.8)320.563 333.216 278.242 (squared distance: 41804.5)646.599 502.256 424.46 (squared distance: 43948.8)556.202 325.013 568.252 (squared distance: 44751)291.27 497.352 515.938 (squared distance: 45463.9)286.483 322.401 495.377 (squared distance: 45567.2)367.288 550.421 550.551 (squared distance: 46318.6)595.122 582.77 394.894 (squared distance: 46938.1)256.784 499.401 379.931 (squared distance: 47064.1)430.782 230.854 293.829 (squared distance: 48067.2)261.051 486.593 329.854 (squared distance: 48612.7)602.061 327.892 545.269 (squared distance: 48632.4)347.074 610.994 395.622 (squared distance: 49475.6)482.876 284.894 583.888 (squared distance: 49718.6)356.962 247.285 514.959 (squared distance: 50423.7)282.065 509.488 516.216 (squared distance: 50730.4)

How to use a KdTree to search

这篇关于如何使用KdTree进行搜索（How to use a KdTree to search）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/249290。

相关文章

中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
使用SecondaryNameNode恢复NameNode的数据

使用SecondaryNameNode恢复NameNode的数据

1）需求： NameNode进程挂了并且存储的数据也丢失了，如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2）故障模拟 （1）kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 （2）删除NameNode存储的数据（/opt/module/hadoop-3.1.4/data/tmp/dfs/na
阅读更多...
Hadoop数据压缩使用介绍

Hadoop数据压缩使用介绍

一、压缩原则 （1）运算密集型的Job，少用压缩 （2）IO密集型的Job，多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1）为了支持多种压缩/解压缩算法，Hadoop引入了编码/解码器 2）要在Hadoop中启用压缩，可以配置如下参数
阅读更多...
Makefile简明使用教程

Makefile简明使用教程

文章目录 规则makefile文件的基本语法：加在命令前的特殊符号：.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具，常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
pdfmake生成pdf的使用

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据，将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2