EVG-Thin: A Thinning Approximation to the Extended Voronoi Graph
Copyright (C) 2006 - Patrick Beeson (pbeeson at cs.utexas.edu)This program is released under the GNU General Public License (GPL).
This code implements an extension of the pixel-based "thinning" algorithm that finds skeletons of bitmaps. The classic thinning algorithm is a fast approximation of the Voronoi diagram; however, this software also approximates the Extended Voronoi graph. This code was written to be applied in real-time to occupancy grids (from the mobile robotics literature) where cells are either occupied, free, or unknown, but it should work on bitmap images for other domains.
Relevant Citations
- Classic Thinning Algorithm:
Zhang and Suen. "A Fast Parallel Algorithm for Thinning Digital Patterns." Communications of the ACM, vol. 27, no. 3, pp. 236-239, 1984. - Extended Voronoi Graph:
Beeson, Jong, and Kuipers. "Towards autonomous topological place detection using the Extended Voronoi Graph." IEEE International Conference on Robotics and Automation (ICRA), 2005.
Language
C++ (tested with g++-4.0 under Linux 2.6)
Changelog
Download
- Compressed Tarball [.tgz] (25kB)
KLD-Sampling: Adequately Sampling from an Unknown Distribution
Copyright (C) 2006 - Patrick Beeson (pbeeson at cs.utexas.edu)This program is released under the GNU General Public License (GPL).
This code implements Dieter Fox's KLD-sampling algorithm (KLD stands for Kullback-Leibler distance). When using particle filters to approximate an unknown distribution, too few particles may not adequately sample the underlying distribution, while too many samples can increase the run time of time sensitive programs (e.g. particle filter localization for a mobile robot). Running the included test program demonstrates how different KLD-sampling parameters affect both the number of samples and the estimated mean and variance of the underlying distribution. The test program assumes a 1D underlying distribution, but the provided KLD-sampling module works on multivariate distributions.
Relevant Citations
- Fox. "Adapting the sample size in particle filters through KLD-sampling." International Journal of Robotics Research (IJRR), 2003.
Language
C++ (tested with g++-4.0 under Linux 2.6)
Download
- Compressed Tarball [.tgz] (13kB)