PCL KD树的使用

目录

一、概述

1.1原理

1.1.1 数据拆分过程

1.1.2 树的构建示例

1.2实现步骤

1.3应用场景

二、代码实现

2.1关键函数

2.1.1KD树构建与查询:

2.1.2 k近邻搜索

 2.1.3半径搜索

2.2完整代码

三、实现效果

3.1处理后点云

3.2数据显示


PCL点云算法汇总及实战案例汇总的目录地址链接:

PCL点云算法与项目实战案例汇总(长期更新)


一、概述

        KD树(K-D Tree)是一种用于组织k维空间中的点的数据结构,常用于高效的最近邻搜索、范围查询等操作。KD树通过递归地将空间划分成k维的超矩形,使得在高维空间中的搜索变得更加高效。本文将详细介绍KD树的构建原理及其在PCL中的应用。

1.1原理

        KD树的全称是k维树(k-Dimensional Tree),它是一种二叉树,用于对k维空间中的点进行组织,以便于快速地进行点的查询操作(如最近邻搜索)。KD树的基本思想是通过递归地将数据空间划分为两个部分,从而形成一棵二叉树。每个节点代表一个k维超矩形,划分过程直到节点包含的数据点数目低于某个阈值或不能再划分为止。

1.1.1 数据拆分过程

1.选择维度:
    - 在构建KD树时,选择一个维度来划分数据空间。通常,使用循环选择的方法,即在每一层递归中,依次选择数据的不同维度。例如,在三维空间(k=3)中,第一层选择x维度,第二层选择y维度,第三层选择z维度,第四层再回到x维度,以此类推。
2.选择分割点:
    - 在选定的维度上,通过找到数据在该维度上的中位数,将数据空间划分为两个部分。中位数的选择保证了数据点被尽量均匀地分割开。
3.递归构建:
    - 将数据空间划分后,左子树包含小于或等于中位数的数据点,右子树包含大于中位数的数据点。递归地对每个子空间构建KD树,直到满足终止条件(如节点数据点数目小于某个阈值)。

1.1.2 树的构建示例

假设我们有一组二维点 (x, y),要将其构建为一棵KD树:

  • 第一层(根节点):选择x维度进行划分,找到x维度的中位数,作为根节点的分割点。左子树包含所有x值小于或等于中位数的点,右子树包含所有x值大于中位数的点。
  • 第二层:对左子树和右子树,选择y维度进行划分,找到y维度的中位数,分别作为左右子树的分割点。继续递归划分。
  • 第三层:再回到x维度进行划分,依次类推,直到不能再划分为止。

1.2实现步骤

        KD树的搜索过程通常是以递归的方式进行的,主要分为最近邻搜索和范围搜索两种常见的操作。
1.最近邻搜索:
    - 从根节点开始,沿树向下递归搜索,比较查询点与节点的分割点,决定搜索左子树还是右子树。
    - 在找到一个叶节点后,记录下该叶节点的点,并计算它与查询点的距离。
    - 回溯检查其他可能包含更近点的子树。
2.范围搜索:
    - 同样从根节点开始,根据分割维度的值,判断是否需要搜索左右子树。
    - 判断当前节点的分割点是否在查询范围内,如果是,则将其纳入结果集。
    - 继续递归地检查子树,直到所有符合条件的节点都被搜索到。
通过这种分割和搜索方法,KD树能够有效地减少高维空间中的搜索范围,从而加快查询速度。

1.3应用场景

KD树广泛应用于以下场景:

  1. 最近邻搜索:用于查找点云中距离某点最近的邻居点,常用于点云配准。
  2. k近邻搜索:用于查找点云中某点的k个最近邻点,适用于点云平滑、特征计算等。
  3. 范围搜索:用于查找在一定范围内的所有邻居点,适用于聚类、边界检测等。

二、代码实现

2.1关键函数

2.1.1KD树构建与查询:

  • pcl::KdTreeFLANN:用于创建KD树对象,支持最近邻、k近邻、范围搜索。
  • setInputCloud:将点云数据输入到KD树中进行构建。
  • nearestKSearch:执行k近邻搜索,找到指定点的k个最近邻点。
  • radiusSearch:执行范围搜索,找到指定点在给定半径内的所有邻居点。

2.1.2 k近邻搜索

int pcl::KdTreeFLANN< PointT, Dist >::nearestKSearch  ( const PointT &  point,  
  unsigned int  k,  
  Indices &  k_indices,  
  std::vector< float > &  k_sqr_distances  
 )  const 

 2.1.3半径搜索

int pcl::KdTreeFLANN< PointT, Dist >::radiusSearch  ( const PointT &  point,  
  double  radius,  
  Indices &  k_indices,  
  std::vector< float > &  k_sqr_distances,  
  unsigned int  max_nn = 0  
 )  const 

2.2完整代码

#include <pcl/io/pcd_io.h>  // 用于加载PCD文件
#include <pcl/point_types.h>  // PCL点类型定义
#include <pcl/kdtree/kdtree_flann.h>  // PCL中的KD树实现
#include <pcl/visualization/pcl_visualizer.h>  // 用于可视化点云
#include <vector>
#include <iostream>

// 将搜索到的结果渲染为红色,并在可视化窗口中显示
void visualizeResult(pcl::PointCloud<pcl::PointXYZ>::Ptr cloud, const std::vector<int>& indices)
{
    // 创建一个带颜色信息的点云对象,用于存储带有颜色信息的点云
    pcl::PointCloud<pcl::PointXYZRGB>::Ptr coloredCloud(new pcl::PointCloud<pcl::PointXYZRGB>);

    // 遍历原始点云中的每个点
    for (size_t i = 0; i < cloud->points.size(); ++i)
    {
        // 创建一个带有RGB颜色信息的点对象
        pcl::PointXYZRGB point;
        point.x = cloud->points[i].x;  // 复制点的X坐标
        point.y = cloud->points[i].y;  // 复制点的Y坐标
        point.z = cloud->points[i].z;  // 复制点的Z坐标

        // 判断当前点是否在搜索到的索引列表中
        if (std::find(indices.begin(), indices.end(), i) != indices.end())
        {
            // 如果是搜索到的点,将颜色设置为红色
            point.r = 255;
            point.g = 0;
            point.b = 0;
        }
        else
        {
            // 如果不是搜索到的点,将颜色设置为白色
            point.r = 255;
            point.g = 255;
            point.b = 255;
        }

        // 将带颜色的点添加到新的点云对象中
        coloredCloud->points.push_back(point);
    }

    // 设置点云的基本属性
    coloredCloud->width = coloredCloud->points.size();  // 设置点云宽度为点的数量
    coloredCloud->height = 1;  // 设置点云高度为1(无序点云)
    coloredCloud->is_dense = true;  // 设置点云为稠密点云

    // 创建一个PCLVisualizer对象,用于显示带颜色的点云
    pcl::visualization::PCLVisualizer::Ptr viewer(new pcl::visualization::PCLVisualizer("3D Viewer"));
    viewer->setBackgroundColor(0, 0, 0);  // 设置背景颜色为黑色
    viewer->addPointCloud<pcl::PointXYZRGB>(coloredCloud, "result");  // 将带颜色的点云添加到可视化窗口
    viewer->setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 3, "result");  // 设置点的大小

    // 启动可视化主循环,保持窗口打开直到用户关闭
    while (!viewer->wasStopped())
    {
        viewer->spinOnce(100);  // 刷新窗口,间隔100ms
    }
}

int main(int argc, char** argv)
{
    // 1. 创建PointCloud对象,用于存储点云数据
    pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);

    // 2. 读取点云数据,加载PCD文件
    if (pcl::io::loadPCDFile("bunny.pcd", *cloud) == -1)
    {
        PCL_ERROR("Couldn't read file input.pcd \n");  // 如果文件加载失败,输出错误信息
        return -1;  // 返回错误代码并退出程序
    }

    // 3. 创建KD树对象,并将点云数据输入到KD树中进行构建
    pcl::KdTreeFLANN<pcl::PointXYZ> kdtree;  // 创建KD树对象
    kdtree.setInputCloud(cloud);  // 将点云数据设置为KD树的输入

    // 4. 定义一个查询点,用于进行搜索
    pcl::PointXYZ searchPoint(-0.0208042, 0.125974, 0.0209606);  // 查询点的坐标

    // 5. k近邻搜索(K Nearest Neighbor Search)
    int k = 1000;  // 设置k值,表示要查找的最近邻点的数量
    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;

    // 使用KD树进行k近邻搜索,找到距离查询点最近的k个点
    if (kdtree.nearestKSearch(searchPoint, k, pointIdxNKNSearch, pointNKNSquaredDistance) > 0)
    {
        // 如果搜索成功,将搜索结果进行可视化
        visualizeResult(cloud, pointIdxNKNSearch);
    }

    // 6. 半径搜索(Radius Search)
    float radius = 0.03;  // 设置搜索半径
    std::vector<int> pointIdxRadiusSearch;  // 用于存储在指定半径范围内的点的索引
    std::vector<float> pointRadiusSquaredDistance;  // 用于存储在指定半径范围内的点的距离平方值

    std::cout << "Neighbors within radius " << radius << " around point ("
        << searchPoint.x << " " << searchPoint.y << " " << searchPoint.z << ")" << std::endl;

    // 使用KD树进行半径搜索,找到查询点在给定半径范围内的所有点
    if (kdtree.radiusSearch(searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance) > 0)
    {
        // 如果搜索成功,将搜索结果进行可视化
        visualizeResult(cloud, pointIdxRadiusSearch);
    }

    // 7. 混合搜索(k近邻搜索 + 半径搜索)
    std::vector<int> hybridSearchIndices;  // 存储混合搜索结果的索引
    for (size_t i = 0; i < pointIdxNKNSearch.size(); ++i)
    {
        // 判断k近邻搜索的点是否也在指定半径范围内
        if (pointNKNSquaredDistance[i] <= radius * radius)
        {
            hybridSearchIndices.push_back(pointIdxNKNSearch[i]);  // 如果满足条件,将索引添加到结果中
        }
    }

    std::cout << "Hybrid search results within K=" << k << " and radius " << radius << std::endl;

    // 如果混合搜索结果不为空,将结果进行可视化
    if (!hybridSearchIndices.empty())
    {
        visualizeResult(cloud, hybridSearchIndices);
    }

    return 0;
}

三、实现效果

3.1处理后点云

3.2数据显示

K nearest neighbor search at (-0.0208042 0.125974 0.0209606) with K=1000
Neighbors within radius 0.03 around point (-0.0208042 0.125974 0.0209606)
Hybrid search results within K=1000 and radius 0.03

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/881017.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

linux系统维护:给linux的根目录分配更多的额外的磁盘空间,实现系统磁盘容量的平滑升级

目录 一、背景说明 二、概念介绍 1、物理卷&#xff08;Physical Volume, PV&#xff09; 2、卷组&#xff08;Volume Group, VG&#xff09; 3、逻辑卷&#xff08;Logical Volume, LV&#xff09;&#xff1a; 三、操作过程 1、vmware中新增磁盘 2、查看磁盘信息 3、格式化…

安卓13长按电源按键直接关机 andriod13不显示关机对话框直接关机

总纲 android13 rom 开发总纲说明 文章目录 1.前言2.问题分析3.代码分析4.代码修改5.编译6.彩蛋1.前言 有些设备需要在长按电源键的时候,直接关机。不需要弹出对话框进行询问。 2.问题分析 过滤电源按键,需要在系统里面处理的话,那么我们需要熟悉android的事件分发,然后再…

stm32f411ceu6芯片学习

首先找到对应芯片的数据手册&#xff0c;硬件电路设计参考的是Electrical characteristics这一节&#xff0c;芯片的每一个引脚都会有推荐的电路接线。 基本每个芯片&#xff0c;都可以在数据手册中找到厂家提供的参考电路图&#xff0c;这就是绘制芯片的原理图最基本的依据。 …

力扣题解2390

大家好&#xff0c;欢迎来到无限大的频道。 今日继续给大家带来力扣题解。 题目描述​&#xff08;中等&#xff09;&#xff1a; 从字符串中移除星号 给你一个包含若干星号 * 的字符串 s 。 在一步操作中&#xff0c;你可以&#xff1a; 选中 s 中的一个星号。 移除星号…

清理C盘缓存,删除电脑缓存指令是什么

在处理计算机系统的C盘缓存清理任务时&#xff0c;需要谨慎操作以确保系统的稳定性和数据的安全性。通常&#xff0c;Windows操作系统中并没有直接的“一键清理C盘缓存”的单一命令&#xff0c;因为缓存文件分散存储于多个位置&#xff0c;并且有些缓存对于系统性能至关重要&am…

HarmonyOS元服务与卡片

元服务与卡片 文章目录 一、元服务1.介绍2.常见元服务项目步骤 二、卡片1.介绍2.卡片的创建3.卡片的数据的变更4.卡片的进程间通讯4.1使用工具包4.2使用步骤 5.卡片路由postCardAction&#xff1a;快速拉起后台5.1格式5.2快速拉起指定页面--router5.3调用后台功能--call5.3卡片…

基于Java的房地产在线营销管理系统研究与实现

目录 前言 功能设计 系统实现 获取源码 博主主页&#xff1a;百成Java 往期系列&#xff1a;Spring Boot、SSM、JavaWeb、python、小程序 前言 随着信息技术的迅猛发展&#xff0c;互联网已经渗透到我们生活的方方面面&#xff0c;为各行各业带来了前所未有的变革。房地产…

Linux学习笔记8 理解Ubuntu网络管理,做自己网络的主人

本文讲解了Ubuntu下网络由什么管理&#xff0c;介绍了临时ip和路由的设置方法&#xff0c;介绍了静态持久化网络配置的方法以及各网络管理软件之间的关系。 来看看Ubuntu网络管理。 序言 原本学习ubuntu网络管理就是为了检查nginx安装过程中使用wget获取压缩包为什么解析不出…

Python编码系列—Python适配器模式:无缝集成的桥梁

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…

Jenkins怎么设置每日自动执行构建任务?

在 Jenkins 中设置每日自动执行构建任务可以按照以下步骤进行&#xff1a; 一、安装必要插件 确保安装了 “Timestamper” 插件&#xff0c;这个插件可以为构建添加时间戳&#xff0c;方便查看构建的执行时间。 二、配置任务 打开需要设置每日自动执行的 Jenkins 任务。在 …

105.游戏安全项目-基址的技术原理-分析技巧

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a;易道云信息技术研究院 本人写的内容纯属胡编乱造&#xff0c;全都是合成造假&#xff0c;仅仅只是为了娱乐&#xff0c;请不要盲目相信…

品牌力是什么?如何评估企业品牌影响力?

品牌影响力&#xff0c;其实就是指品牌在消费者心智中所占据的位置&#xff0c;以及它对消费者购买决策和行为的影响力。如果一个企业的品牌影响力越强&#xff0c;它在消费者心中的印象就越深刻&#xff0c;能够更有效地驱动消费者的购买行为&#xff0c;形成品牌忠诚度&#…

【C++ 学习】多态的基础和原理(10)

目录 前言1. 概念2. 多态的定义及实现2.1 多态的构成条件2.2 虚函数2.3 虚函数重写2.4 虚函数重写的例外2.4.1 协变2.4.1 析构函数的重写 2.5 多态调用和普通调用2.6 函数重写/函数隐藏/函数重载 的对比2.6.1 函数重写2.6.2 函数隐藏2.6.3 函数重载 2.7 C11 final 和override 3…

爬虫--翻页tips

免责声明&#xff1a;本文仅做分享&#xff01; 伪线程 from DrissionPage import ChromiumPage import timepage ChromiumPage() page.get("https://you.ctrip.com/sight/taian746.html") # 初始化 第0页 index_page 0# 翻页点击函数 sleep def page_turn():page…

计算机毕业设计 美妆神域网站的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…

IP 协议分析《实验报告》

目录 一、 实验目的 二、实验设备和环境 三、实验记录 1、实验环境搭建 2、IP 协议分析 1.设置抓包接口 2.IP 报文分析 3.报文长度计算 4.生存时间 TTL 5.分析总结 3、IP分片 1.IP 分片简介 2.捕获分组 3.结果分析 一、 实验目的 1、掌握 IP 协议数据报格式&…

硬件工程师笔试面试——保险丝

目录 10、保险丝 10.1 基础 保险丝原理图 保险丝实物图 10.1.1 概念 10.1.2 保险丝的工作原理 10.1.3 保险丝的主要类型 10.1.4 保险丝的选择和使用注意事项 10.2 相关问题 10.2.1 保险丝的额定电流和额定电压是如何确定的? 10.2.2 保险丝的熔断速度对电路保护有何…

2024年PMP报考需要什么条件?怎么报名?

PMP证书报名的门槛并不高&#xff0c;在项目管理领域里也很热门&#xff0c;很多公司要求项目组成员去考PMP证书的&#xff0c;很多招聘JD也要求持PMP证书优先&#xff0c;如果你是在项目相关管理岗位工作&#xff0c;不妨一起考一个。 一、PMP报考条件 PMP 报考条件是需要35个…

AI是否会带来一场认知革命?Reid Hoffman 的独特见解

随着人工智能&#xff08;AI&#xff09;技术的迅猛发展&#xff0c;关于AI对人类社会及认知的影响&#xff0c;已经成为了学术界和业界热议的话题。硅谷著名投资人、LinkedIn联合创始人Reid Hoffman&#xff0c;在斯坦福大学的演讲中分享了他对AI的深刻看法。他认为&#xff0…

Windows版本下Redis安装与使用---详解

目录 1、下载Redis压缩包 2、解压到文件夹 3、启动Redis服务 4、打开Redis客户端进行连接 5、使用一些基础操作来测试 6、Redis常用的服务指令 7、C#项目使用redis 8、C#中使用StackExchange.Redis库操作Redis 9、执行 Redis 命令 10、常见报错和相关指令 1、下载Redi…