EVG-THIN v1.1: A Thinning Approximation to the Extended Voronoi Graph

Copyright (C) 2006 - Patrick Beeson  ([email protected])
This program is released under the GNU General Public License (GPL).
See COPYING for details.

----------------------------------

This program 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, 1984, "A Fast Parallel Algorithm for Thinning Digital
Patterns." Communications of the ACM, vol. 27, no. 3, pp. 236-239.

Extended Voronoi Graph:
Beeson, Jong, and Kuipers, 2005, "Towards autonomous topological place
detection using the Extended Voronoi Graph." IEEE International
Conference on Robotics and Automation (ICRA-05).

----------------------------------

See CHANGELOG for revision notes.

Installation
------------
  $ make


Running
-------
  $ ./test -image-file FILENAME1 <options>

FILENAME1 must be a .ppm, .pgm, or .pnm file.

options: 

-output-file FILENAME2 : By default the output file name is the input
	     filename with '_skeleton.ppm' appended to the end.

-min-unknown N : The minimum greyscale value (1-254) of unknown cells.
	     Occupied cells are 0-(N-1).

-max-unknown M : The maximum greyscale value (1-254) of unknown
	     cells. Free cells are (M+1)-255.     

-pruning [0|1] : Turns pruning on or off.  Pruning removes ALL
	 "branches" of the skeleton EXCEPT those that meet one of
	 these conditions: 1) The branch touches the edge of the grid,
	 2) the branch touches unknown cells.  By default, pruning is
	 on.

-min-distance R : Bleeds obstacles by R cells before calculating
	      skeleton.  This removes branches that come too close to
	      obstacles.

-max-distance S : If the skeleton gets more the S cells from the
	      nearest occupied cells, it switches to following the
	      occupied cells S away.
	      
-robot_loc X Y : This location is used to select which skeleton is
	   valid, given complex images with multiple, disjoint
	   skeletons.  By default, the "robot" is located at the
	   center of the image.

-robot-close [0|1] : The robot location (see above) is used to choose
	     which skeleton is valid (if multiple exist).  This is
	     done by Euclidean distance between the robot's location
	     at the skeletal points.  This option turn off that
	     checking except for points where the robot's distance is
	     within the distance of the skeletal point to its closest
	     obstacle.  By default, this is turned on.


Examples
--------

 $ ./test -image-file test1.pgm

 output : test1_skeleton.ppm 
 
 Basically, the Voronoi graph of the local occupancy grid of a robot.


 $ ./test -image-file test2.pgm -output-file test2_outA.ppm
 
 output: test2_outA.ppm 
 
 Notice that because the skeleton does not touch the edges (or
 unknown, grey cells), pruning removes the skeleton.


 $ ./ test -image-file test2.pgm -output-file test2_outB.ppm -pruning 0

 output: test2_outB.ppm 
 
 Because we turned off pruning, the skeleton now appears in the output image.


 $ ./ test -image-file test2.pgm -output-file test2_outC.ppm
 -pruning 0 -max_distance 10 -robot-close 0

 output: test2_outC.ppm 

 Here, we set a maximum distance the skeleton can be from occupied
 cells.  Because the robot's location is by default at the center of
 the image, we turn off 'robot-close' because the robot is not with 10
 cells of any point on the skeleton.  

 Try turning 'robot-close' on (default) and the skeleton disappears in
 the output image. 

 Even with -robot-close turned on, we can get the output to include
 the skeleton by using the 'robot-loc' option.