Location>code7788 >text

KD-Tree Study Notes

Popularity:643 ℃/2024-07-23 16:34:03

Learning Materials:

1.B Station - A Cat Named Little Flower
2.Language Sparrow - Double Fool:kdtree
3.B station video: learning kdtree prior knowledge: KNN algorithm

KD Tree Introduction and Background

  The k-d tree, a data structure that partitions a k-dimensional data space. It is mainly applied to the search of key data in multi-dimensional space. About the background of kd-tree, it is mainly an algorithm to solve the feature point matching problem, kd-tree is an algorithm for indexing structure and approximate query in high dimensional space.
  With respect to feature matching operators, they can be divided into two categories, the first of which is thelinear scanning methodHowever, this method compares the distance between the points in the data set and the query point one by one, that is, exhaustive, the disadvantage is obvious, the search efficiency is low. Next.Creating data indexes, and kdtree is just such a method, whose basic idea is to divide the search space hierarchically, dividing the space without overlapping.

Structure of the KD tree

The following passage is taken fromLanguage Sparrow - Double Fool:kdtree
image
Seems more complex, in fact, not complicated at all, binary sorting tree to learn it, in fact, kdtree some places and binary sorting tree is a bit similar, that is, thethe left is small and the right is large (idiom); the left is small and the right is large, but not strictly similar, look at the following diagram: kdtree construction process:
image
There is such a number of point sets, draw these points in the coordinate system, first we divide according to perpendicular to the x-axis, as shown in Figure (1), to find the horizontal coordinates of each point, 2, 3, 4, 7, 8, 9, to take the median of (4 + 7) / 2 = 5.5, then since the distance from the 4 and 7 are 1.5, so we can take the 7 as a criterion for the division of the left and right blocks, then the points (7 2) added to the tree, then we divide according to the y-axis, take the left and right blocks were divided, and the above logic is the same, the division is completed and then add the point to the tree, pay attention to the left small right big, and so on can be divided successfully.Note: When a subtree node of a kdtree has only one child, there is no such thing as a left or right child.

KD Tree Algorithm for Finding Nearest Neighbors

As pictured (from the b-site video above):imageimage

Here we want to find the neighborhood of (3, 4.5) in the following steps:

  1. Looking first at the root of the tree, here noted as level 1, the root is x(1)(Here we see x(1) as the x-axis and x(2) as the y-axis)Since we are looking for the point with a horizontal axis of 3, we look for the one smaller than 7, which arrives at (5,4).
  2. (5,4) is in the row for y, so at this point we look at 4, and since 4.5>4, this goes to (4, 7).
  3. Reaching the leaf node (4, 7), at which point we take it as the current closest point, the distance to (3, 4.5) is calculated to be 2.69.
  4. Start backtracking to (5, 4) at a distance of 2.06 to update the nearest neighbor point. At this point we find that the line between (3, 4.5) and (5, 4) makes a circle with radius and intersects the y=4 hyperplane, so at this point we need to go into another subspace to find it, that is, we have to backtrack to (2, 3) here, and after calculating it, the distance is 1.8.
  5. Make the circle again, this circle does not intersect with x=7, so you do not have to go into the right subtree of the root node to find it. End.

KNN algorithm on KD trees

image

KD Tree Related Functions

PCL mediumpcl::KdTree<PointT>It is an implementation of kd-tree data structure. And provides some subclasses and wrapper classes for fast searching based on FLANN. You can refer to the corresponding API, the following is the specific use of the two classes.

  1. pcl::search::KdTree < PointT >
    pcl::search::KdTree<PointT>bepcl::search::Search< PointT >is a subclass ofpcl::KdTree<PointT>The wrapper class of the Contains (1) k-nearest neighbor search and (2) neighborhood radius search.
    Sample code:
#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
#include <pcl/search/> // embodykdtreeheader file
typedef pcl::PointXYZ PointT;
int main()
{
	pcl::PointCloud<PointT>::Ptr cloud(new pcl::PointCloud<PointT>);
	pcl::io::loadPCDFile("", *cloud);
	// defineKDTreeboyfriend
	pcl::search::KdTree<PointT>::Ptr kdtree(new pcl::search::KdTree<PointT>);
	kdtree->setInputCloud(cloud); // Set the point cloud to be searched,build upKDTree
	std::vector<int> indices; // Stored Query Nearest Neighbor Index
	std::vector<float> distances; // Store the square of the corresponding distance of the nearest neighbor points
	PointT point = cloud->points[0]; // Initialize a query point
	
	// inquiry distancepointnearestkcheckpoint
	int k = 10;
	int size = kdtree->nearestKSearch(point, k, indices, distances);
	std::cout << "search point : " << size << std::endl;
	// consult (a document etc)pointhave a radius ofradiusPoints in the neighborhood sphere
	double radius = 2.0;
	size = kdtree->radiusSearch(point, radius, indices, distances);
	std::cout << "search point : " << size << std::endl;
	system("pause");
	return 0;
}
  1. pcl::KdTreeFLANN < PointT >
    pcl::KdTreeFLANN<PointT>bepcl::KdTree<PointT>subclasses that accomplish the same thing.
#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
// Includes related header files
#include <pcl/kdtree/kdtree_flann.h>
typedef pcl::PointXYZ PointT;
int main()
{
	pcl::PointCloud<PointT>::Ptr cloud(new pcl::PointCloud<PointT>);
	pcl::io::loadPCDFile("", *cloud);
	pcl::KdTreeFLANN<pcl::PointXYZ> kdtree; //establishKDtree
	(cloud); // Set the point cloud to be searched,build upKDTree
	std::vector<int> indices; // Stored Query Nearest Neighbor Index
	std::vector<float> distances; // Store the square of the corresponding distance of the nearest neighbor points
	PointT point = cloud->points[0]; // Initialize a query point
	
	// inquiry distancepointnearestkcheckpoint
	int k = 10;
	int size = (point, k, indices, distances);
	std::cout << "search point : " << size << std::endl;
	// consult (a document etc)pointhave a radius ofradiusPoints in the neighborhood sphere
	double radius = 2.0;
	size = (point, radius, indices, distances);
	std::cout << "search point : " << size << std::endl;
	system("pause");
	return 0;
}