- Tools -

EVG-Thin: A Thinning Approximation to the Extended Voronoi Graph

This code implements an extension of the pixel-based "thinning" algorithm that finds skeletons of bitmaps.
Further information

Patrick Beeson;

Get the Source Code via SVN
svn co https://svn.openslam.org/data/svn/evg-thin

Long Description
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.

Hardware/Software Requirements
Linux/Unix, G++ 3.3/4.0.x

Papers Describing the Approach
T. Y. Zhang and C. Y. Suen: A Fast Parallel Algorithm for Thinning Digital Patterns, Communications of the ACM, vol. 27, no. 3, pp. 236-239, 1984 (link)

Patrick Beeson, Nicholas K. Jong, and Benjamin Kuipers: Towards autonomous topological place detection using the Extended Voronoi Graph, IEEE International Conference on Robotics and Automaton (ICRA), 2005 (link)

License Information
This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
The authors allow the users of OpenSLAM.org to use and modify the source code for their own research. Any commercial application, redistribution, etc has to be arranged between users and authors individually and is not covered by OpenSLAM.org.

This program is released under the GNU General Public License (GPL). Copyright (C) 2006 - Patrick Beeson

*** OpenSLAM.org is not responsible for the content of this webpage ***
*** Copyright and V.i.S.d.P.: Patrick Beeson; ***