0%

PCL 点云索引方法K维树(KD-tree)和八叉树(octree)介绍

通过雷达、激光扫描、立体摄像机等三维测量设备获取的点云数据,具有数据量大、分布不均匀等特点。作为三维领域中一个重要的数据来源,点云数据主要是表征目标表面的海量点集合,并不具备传统网格数据的集合拓扑信息。所以点云数据处理中最为核心的问题就是建立离散点间的拓扑关系,实现基于邻域关系的快速查找。
建立空间索引在点云数据处理中已被广泛应用,常见空间索引一般是自顶向下逐级划分空间的各种空间索引结构,比较有代表性的包括 BSP树、 KD树、 KDB树、 R树、 R+树、 CELL树、四叉树和八叉树等索引结构,而在这些结构中KD树和八叉树在3D点云数据组织中应用较为广泛,PCL对上述两者进行了实现。

1.K维树(KD-tree)

1.1 KD-tree 概念简介

KD-tree 又称 K 维树是计算机科学中使用的一种数据结构,用来组织表示 K 维空间中点集合。它是一种带有其他约束条件的二分查找树。KD-tree对于区间和近邻搜索十分有用。我们为了达到目的,通常只在三个维度中进行处理,因此所有的 KD-tree 都将是三维 KD-tree。 如下图所示(动图,慢慢看), KD-tree 的每一级在指定维度上分开所有的子节点。在树的根部所有子节点是以第一个指定的维度上被分开(即如果第一维坐标小于根节点的点它将被分在左边的子树中,如果大于根节点的点它将分在右边的子树中)。

KDTree-animation.gif

树的每一级都在下一个维度上分开,所有其他的维度用完之后就回到第一个维度,建立 KD-tree 最高效的方法是像快速分类一样使用分割法,把指定维度的值放在根上,在该维度上包含较小数值的在左子树,较大的在右子树。然后分别在左边和右边的子树上重复这个过程,直到用户准备分类的最后一个树仅仅由一个元素组成。

Screenshot from 2018-03-30 11:51:38.png

1.2 PCL中KD-tree使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#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 data
cloud->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 search

int 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 search

std::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;
}

代码解读

  • 设置kdtree搜索对象和输入数据,然后使用随机坐标搜索方式
    1
    2
    3
    4
    5
    6
    7
    8
    9
    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 近邻,两个向量中一个存储搜索到查询点近邻的索引,另一个存储对应近邻的距离平方
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     // K nearest neighbor search

    int 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;

1.3 KD-tree 算法伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function kdtree (list of points pointList, int depth)
{
// Select axis based on depth so that axis cycles through all valid values
var int axis := depth mod k;

// Sort point list and choose median as pivot element
select median by axis from pointList;

// Create node and construct subtree
node.location := median;
node.leftChild := kdtree(points in pointList before median, depth+1);
node.rightChild := kdtree(points in pointList after median, depth+1);
return node;
}

2. 八叉树(octree)

2.1 octree 概念简介

八叉树结构是由 Hunter 博士于1978年首次提出的一种数据模型。八叉树结构通过对三维空间的几何实体进行体元剖分,每个体元具有相同的时间和空间复杂度,通过循环递归的划分方法对大小为( 2 n x 2 n x 2 n ) 的三维空间的几何对象进行剖分,从而构成一个具有根节点的方向图。在八叉树结构中如果被划分的体元具有相同的属性,则该体元构成一个叶节点;否则继续对该体元剖分成8个子立方体,依次递剖分,对于( 2 n x 2 n x 2 n ) 大小的空间对象,最多剖分 n 次,如下图所示。

Octree2.png

2.2 PCL中octree 在压缩点云数据方面应用

点云由海量的数据集组成,这些数据通过距离、颜色、法线等附加信息来描述空间三维点。此外,点云能以非常高的速率被创建出来,因此需要占用相当大的存储资源,一旦点云需要存储或者通过速率受限制的通信信道进行传输,提供针对这种数据的压缩方法就变得十分有用。PCL库提供了点云压缩功能,它允许编码压缩所有类型的点云,包括无序点云,它具有无参考点和变化的点尺寸、分辨率、分布密度和点顺序等结构特征。而且,底层的 octree 数据结构允许从几个输入源高效地合并点云数据。
下面解释单个点云和点云数据流是如何高效压缩的,在给出的例子中用PCL点云压缩技术来压缩用 OpenNIGrabber 抓取到的点云。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <pcl/point_cloud.h>
#include <pcl/point_types.h>
#include <pcl/io/openni_grabber.h>
#include <pcl/visualization/cloud_viewer.h>

#include <pcl/compression/octree_pointcloud_compression.h>

#include <stdio.h>
#include <sstream>
#include <stdlib.h>

#ifdef WIN32
# define sleep(x) Sleep((x)*1000)
#endif

class SimpleOpenNIViewer
{
public:
SimpleOpenNIViewer () :
viewer (" Point Cloud Compression Example")
{
}

void
cloud_cb_ (const pcl::PointCloud<pcl::PointXYZRGBA>::ConstPtr &cloud)
{
if (!viewer.wasStopped ())
{
// stringstream to store compressed point cloud
std::stringstream compressedData;
// output pointcloud
pcl::PointCloud<pcl::PointXYZRGBA>::Ptr cloudOut (new pcl::PointCloud<pcl::PointXYZRGBA> ());

// compress point cloud
PointCloudEncoder->encodePointCloud (cloud, compressedData);

// decompress point cloud
PointCloudDecoder->decodePointCloud (compressedData, cloudOut);


// show decompressed point cloud
viewer.showCloud (cloudOut);
}
}

void
run ()
{

bool showStatistics = true;

// for a full list of profiles see: /io/include/pcl/compression/compression_profiles.h
pcl::io::compression_Profiles_e compressionProfile = pcl::io::MED_RES_ONLINE_COMPRESSION_WITH_COLOR;

// instantiate point cloud compression for encoding and decoding
PointCloudEncoder = new pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA> (compressionProfile, showStatistics);
PointCloudDecoder = new pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA> ();

// create a new grabber for OpenNI devices
pcl::Grabber* interface = new pcl::OpenNIGrabber ();

// make callback function from member function
boost::function<void
(const pcl::PointCloud<pcl::PointXYZRGBA>::ConstPtr&)> f = boost::bind (&SimpleOpenNIViewer::cloud_cb_, this, _1);

// connect callback function for desired signal. In this case its a point cloud with color values
boost::signals2::connection c = interface->registerCallback (f);

// start receiving point clouds
interface->start ();

while (!viewer.wasStopped ())
{
sleep (1);
}

interface->stop ();

// delete point cloud compression instances
delete (PointCloudEncoder);
delete (PointCloudDecoder);

}

pcl::visualization::CloudViewer viewer;

pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA>* PointCloudEncoder;
pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA>* PointCloudDecoder;

};

int
main (int argc, char **argv)
{
SimpleOpenNIViewer v;
v.run ();

return (0);
}

2.3 octree算法 Matlab 伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function [binDepths,binParents,binCorners,pointBins] = OcTree(points)

binDepths = [0] % Initialize an array of bin depths with this single base-level bin
binParents = [0] % This base level bin is not a child of other bins
binCorners = [min(points) max(points)] % It surrounds all points in XYZ space
pointBins(:) = 1 % Initially, all points are assigned to this first bin
divide(1) % Begin dividing this first bin

function divide(binNo)

% If this bin meets any exit conditions, do not divide it any further.
binPointCount = nnz(pointBins==binNo)
binEdgeLengths = binCorners(binNo,1:3) - binCorners(binNo,4:6)
binDepth = binDepths(binNo)
exitConditionsMet = binPointCount<value || min(binEdgeLengths)<value || binDepth>value
if exitConditionsMet
return; % Exit recursive function
end

% Otherwise, split this bin into 8 new sub-bins with a new division point
newDiv = (binCorners(binNo,1:3) + binCorners(binNo,4:6)) / 2
for i = 1:8
newBinNo = length(binDepths) + 1
binDepths(newBinNo) = binDepths(binNo) + 1
binParents(newBinNo) = binNo
binCorners(newBinNo) = [one of the 8 pairs of the newDiv with minCorner or maxCorner]
oldBinMask = pointBins==binNo
% Calculate which points in pointBins==binNo now belong in newBinNo
pointBins(newBinMask) = newBinNo
% Recursively divide this newly created bin
divide(newBinNo)
end

以上。


参考文献:

  1. 点云库PCL学习教程
  2. k-d tree wiki
  3. PCL官方KD-tree使用教程