PCL Developers blog

Siddharth Choudhary

This is my personal page

email:itzsid@gmail.com
project:Neighbor search performance benchmarking; Octree GPU implementation
mentor:Julius Kammerl (Suat Gedikli [Nico Blodow, Jochen Sprickerhof, Radu B. Rusu, Michael Dixon])

About me

I’m a student at International Institute of Information Technology, Hyderabad.

My interests include:

  • Computer Vision
  • Computer Graphics
  • High Performance Computing

Roadmap

Here is a brief outline of my GSoC project milestones:

  • Design a general framework for a search component to be integrated into PCL. It should be an interface to all currently included neighbor search routines.
  • Define methods and parameter sets for performance evaluation of neighbor search in point clouds
  • Develop and integrate methods for an automatic search method selection based on the characteristics of point clouds and amount of planned search operations
  • Developing of octree-based neighboring search in CUDA
  • Integrate CUDA-based neighbor search into the search component

Click here for a detailed roadmap

Recent status updates

Work status
Saturday, August 06, 2011
../../_images/gsoc7.png

Lately I have been working on integrating octree gpu functions with the search class. Since GPU functions can only have an advantage when we have queries in batch mode. For that a module as mentioned in my previous post is written which taken a vector of queries as an input and calls the appropriate gpu function. Right now, the calling gpu function is not working correctly which I am still working on.

Octree GPU functions
Sunday, July 24, 2011
../../_images/gsoc7.png

I started with reading octree search functions for probable porting of them onto GPU. For this I have been going through the GPU functions written by Anatoly for the last few days. Other than this I have added two functions which would act as an interface to CUDA search functions.

virtual int
radiusSearchGPU (std::vector<const PointT>& point, const double radius, std::vector<std::vector<int> >& k_indices,    std::vector<std::vector<float> >& k_distances, int max_nn = -1) const;

virtual int
nearestKSearchGPU (std::vector<const PointT>& point, int k, std::vector<std::vector<int> >& k_indices,    std::vector<std::vector<float> >& k_sqr_distances);

Keeping in mind that GPU power can only be leveraged when multiple query search is done, I have used a vector of point as an input to the function. Next I’ll try and implement some octree search functions onto GPU.

Work status
Saturday, July 16, 2011
../../_images/gsoc7.png

Last week I refined various interface functions to different search methods. deleteTree() and addPointsfromInputCloud() functions in Octree class were merged into setInputCloud(). The functions inside OrganizedDataIndex class were merged into OrganizedNeighborSearch with the function names asapproxNearestKSearch() and approxRadiusSearch(). Other than these as suggested to include a function to select the best search method on the basis of input cloud, I included a new method as,

Search<PointXYZ>* search = new AutotunedSearch<PointXYZ>(AUTO_TUNED);
search->evaluateSearchMethods(cloudIn, NEAREST_K_SEARCH|NEAREST_RADIUS_SEARCH);

It can compare different datastructure on the bais of run time for the given search method in the second argument. Next I’ll start with interfacing GPU functions in search class and put some CPU-GPU checks in auto-tuned search class.

Integration of Kdtree, Octree and OrganizedNeighborClass into search base class
Saturday, July 09, 2011
../../_images/gsoc7.png

I have done the initial integration of all search classes into one search base class. The class structure followed till now is:

class Search
class OctreePointCloud : public Search
class Kdtree : public Search
class OrganizedNeigbhorSearch: public Search
class AutotunedSearch : public Search

So, the appropriate search functions can be called as:

KdTree:

Search<PointXYZ>* kdtree = new KdTree<PointXYZ>();
kdtree->setInputCloud(cloudIn);
kdtree->nearestKSearch (test_point, no_of_neighbors, k_indices, k_distances);
kdtree->radiusSearch (test_point, radius, k_indices, k_distances);

Octree:

Search<PointXYZ>* octree = new OctreePointCloud<PointXYZ>(0.1f);
octree->setInputCloud(cloudIn);
octree->addPointsFromInputCloud ();
octree->nearestKSearch (test_point, no_of_neighbors, k_indices, k_distances);
octree->radiusSearch (test_point, radius, k_indices, k_distances);

OrganizedNeighborSearch:

Search<PointXYZ>* organized_index = new OrganizedNeighborSearch<PointXYZ>();
organized_index->setPrecision(1);  // 1 for using OrganizedNeighborSearch functions and 0 for using OrganizedDataIndex functions
organized_index->setInputCloud(cloudIn);
organized_index->nearestKSearch (test_point, no_of_neighbors, k_indices, k_distances);
organized_index->radiusSearch (test_point, radius, k_indices, k_distances);

Auto-Tuned Search: For now AutotunedSearch takes the appropriate datastructure as a parameter to initiate the search function.

Search<PointXYZ>* auto_search = new AutotunedSearch<PointXYZ>(KDTREE_FLANN); // or OCTREE, ORGANIZED_INDEX
auto_search->setInputCloud(cloudIn);
auto_search->nearestKSearch (test_point, no_of_neighbors, k_indices, k_distances);
auto_search->radiusSearch (test_point, radius, k_indices, k_distances);

The above set of functions are implemented and pushed into trunk. Right now, I am working on AutotunedSearch class to make it more user friendly.

Benchmarking OrganizedNeighborClass and OrganizedDataIndex using office dataset
Sunday, July 03, 2011
../../_images/gsoc7.png

I tried benchmarking the search functions in OrganizedNeighborClass and OrganizedDataIndex classes using the office dataset which Julius gave. The dataset is available at: http://svn.pointclouds.org/data/office/ .

Following are the time benchmark tests done on radiusSearch functions for OrganizedNeighborSearch and OrganizedDataIndex. The number of nearest neighbors for both classes is the same for most of the experiments. However the indices of nearest neighbors vary for both the classes. In some cases the number of nearest neigbhors is also different for both the classes but they are nearby which suggests that OrganizedDataIndex might be an approximate version of OrganizedNeighborSearch. The search point is decided at random ensuring that the search point is not NaN. The time calculated for each search radius is average of 100 iterations.

Data: office1.pcd

Search Point: -1.16809, 0.0467238, 4.906

Search Radius Organized Neighbor Search Organized Data Index Number of Nearest Neighbors
0 0.0511418 1.3416e-06 1
0.1 0.00958581 3.3005e-05 1172
0.2 0.0102894 0.000175295 3917
0.3 0.0118625 0.000422468 7432
0.4 0.0148702 0.000436519 9336
0.5 0.0157803 0.000821651 11850
0.6 0.0166538 0.00117252 14238
0.7 0.0177392 0.00146132 16663
0.8 0.0187914 0.0017615 21237
0.9 0.0198163 0.0020671 25461

Data: office2.pcd

Search Point: -0.723531, 0.218086, 1.347

Search Radius Organized Neighbor Search Organized Data Index Number of Nearest Neighbors
0.000 0.09484 0.00000 1
0.100 0.01409 0.00022 1743
0.200 0.01513 0.00045 3739
0.300 0.01823 0.00091 14067
0.400 0.02444 0.00195 25933
0.500 0.02855 0.00289 44137
0.600 0.03438 0.00409 63127
0.700 0.04080 0.00531 74889
0.800 0.05044 0.00649 92927
0.900 0.05616 0.00811 111587

Data: office3.pcd

Search Point: 0.0144343, -0.43784, 1.263

Search Radius Organized Neighbor Search Organized Data Index Number of Nearest Neighbors
0.000 0.07388 0.00000 1
0.100 0.01170 0.00012 4538
0.200 0.01426 0.00061 13565
0.300 0.01612 0.00110 24162
0.400 0.01890 0.00196 36527
0.500 0.02515 0.00354 53609
0.600 0.03459 0.00555 73626
0.700 0.05051 0.00613 92836
0.800 0.06044 0.00957 152082
0.900 0.06897 0.01178 199561

Data: office4.pcd

Search Point: -0.447771, 0.0920419, 1.306

Search Radius Organized Neighbor Search Organized Data Index Number of Nearest Neighbors
0.000 0.04692 0.00000 1
0.100 0.00948 0.00009 3093
0.200 0.00970 0.00038 12636
0.300 0.01246 0.00083 28916
0.400 0.01408 0.00162 48606
0.500 0.01939 0.00282 75014
0.600 0.02332 0.00395 102830
0.700 0.03006 0.00550 131138
0.800 0.03190 0.00629 154212
0.900 0.03357 0.00718 168709

For now, I have integrated OrganizedDataIndex into OrganizedNeighborSearch with a setMethod() function and pushed the same into trunk. I have started with the integration of Octree function into search base class.