如何使用KdTree进行搜索(How to use a KdTree to search)

2023-10-20 19:38

本文主要是介绍如何使用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

相关文章

Java Lambda表达式的使用详解

《JavaLambda表达式的使用详解》:本文主要介绍JavaLambda表达式的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、前言二、Lambda表达式概述1. 什么是Lambda表达式?三、Lambda表达式的语法规则1. 无参数的Lambda表

Spring组件实例化扩展点之InstantiationAwareBeanPostProcessor使用场景解析

《Spring组件实例化扩展点之InstantiationAwareBeanPostProcessor使用场景解析》InstantiationAwareBeanPostProcessor是Spring... 目录一、什么是InstantiationAwareBeanPostProcessor?二、核心方法解

详解如何使用Python构建从数据到文档的自动化工作流

《详解如何使用Python构建从数据到文档的自动化工作流》这篇文章将通过真实工作场景拆解,为大家展示如何用Python构建自动化工作流,让工具代替人力完成这些数字苦力活,感兴趣的小伙伴可以跟随小编一起... 目录一、Excel处理:从数据搬运工到智能分析师二、PDF处理:文档工厂的智能生产线三、邮件自动化:

Spring @RequestMapping 注解及使用技巧详解

《Spring@RequestMapping注解及使用技巧详解》@RequestMapping是SpringMVC中定义请求映射规则的核心注解,用于将HTTP请求映射到Controller处理方法... 目录一、核心作用二、关键参数说明三、快捷组合注解四、动态路径参数(@PathVariable)五、匹配请

Java 枚举的基本使用方法及实际使用场景

《Java枚举的基本使用方法及实际使用场景》枚举是Java中一种特殊的类,用于定义一组固定的常量,枚举类型提供了更好的类型安全性和可读性,适用于需要定义一组有限且固定的值的场景,本文给大家介绍Jav... 目录一、什么是枚举?二、枚举的基本使用方法定义枚举三、实际使用场景代替常量状态机四、更多用法1.实现接

springboot项目中使用JOSN解析库的方法

《springboot项目中使用JOSN解析库的方法》JSON,全程是JavaScriptObjectNotation,是一种轻量级的数据交换格式,本文给大家介绍springboot项目中使用JOSN... 目录一、jsON解析简介二、Spring Boot项目中使用JSON解析1、pom.XML文件引入依

Java中的record使用详解

《Java中的record使用详解》record是Java14引入的一种新语法(在Java16中成为正式功能),用于定义不可变的数据类,这篇文章给大家介绍Java中的record相关知识,感兴趣的朋友... 目录1. 什么是 record?2. 基本语法3. record 的核心特性4. 使用场景5. 自定

Python使用Tkinter打造一个完整的桌面应用

《Python使用Tkinter打造一个完整的桌面应用》在Python生态中,Tkinter就像一把瑞士军刀,它没有花哨的特效,却能快速搭建出实用的图形界面,作为Python自带的标准库,无需安装即可... 目录一、界面搭建:像搭积木一样组合控件二、菜单系统:给应用装上“控制中枢”三、事件驱动:让界面“活”

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

Python验证码识别方式(使用pytesseract库)

《Python验证码识别方式(使用pytesseract库)》:本文主要介绍Python验证码识别方式(使用pytesseract库),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全... 目录1、安装Tesseract-OCR2、在python中使用3、本地图片识别4、结合playwrigh