
=========================================================================
      README for PD Release of MAT-1.0.x Skeletonization Software
=========================================================================

This distribution contains the public domain release of my
skeletonization software. You are welcome to redistribute this
software and to use it for any purpose, subject to the conditions
under LEGAL ISSUES, below.

For installation instructions, see file INSTALL.

For usage instructions, see the manual pages (ctran.1, voro.1, prune.1,
loadskset.1, skeleton.1, contours.1).

This software is STILL UNDERGOING REVISION. Updated versions may be obtained
by WWW http://hrl.harvard.edu/people/postdocs/rlo.html or by FTP 
from arcadia.harvard.edu.

This software is the work of Robert L. Ogniewicz and (some of the AVS
modules) of Markus Naef. Its implementation and testing 
has been carried out at the Communication Technology Laboratory, 
Swiss Federal Institute of Technology ETH, Zurich, Switzerland, and the
Division of Applied Sciences, Harvard University, Cambridge, USA.

This software uses other packages: XLOADIMAGE, the TIFF library
libtiff.a, the JPEG library libjpeg.a, and GraphicsGems. See also LEGAL
ISSUES.

Please send comments and suggestions to rlo@hrl.harvard.edu.

WHAT'S HERE
===========

This software package contains programs which compute robust Euclidean
skeletons from 2-D binary images (or, optionally, from user-defined contour
data). This goal is achieved by a small set of routines which perform
the following subtasks:

- extraction of a boundary representation (polygonal chain) from a binary
  image -> program "ctran". Several image formats are supported, 
  including GIF, TIFF, Sun Rasterfile, and JPEG.

- generation of the Voronoi diagram of the vertices of the polygonal
  chain (thus approximating the continuous medial axis) -> program "voro".

- extraction of a stable subset of the Voronoi diagram (the Voronoi
  skeleton). Different pruning techniques have been implemented. The
  simplest methods exploit saliency measures applied to each component
  of the Voronoi diagram and apply a simple threshold operation to
  extract the skeleton. More sophisticated techniques establish a
  hierarchic organization of skeleton branches (Skeleton Pyramid).
  Also a novel method of automatic skeletonization is provided. This
  technique permits to extract a `first order' or `main' medial axis
  which captures the most significant components of a shape. Skeleton
  branches associated with detail features are grouped at lower levels
  of the hierarchy. This latest method (based on the so-called
  Skeleton-Space) does not require any human supervision -> program "prune".

- compilation of the extracted skeleton data into a symbolic data
  structure which can be edited and modified with any standard
  editor (Skeleton-Set). Parser routines including a sample program
  are provided for reading back skeleton data from file 
  into machine memory -> program "loadskset".

- simple visualization routines for the display of boundary, Voronoi
  tessellation, and skeleton data -> program "shosk".
  Optionally, data can be converted into a Postscript file readable by 
  'idraw', the InterViews drawing editor.

- (Limited) support for AVS and KHOROS.

REPORTING BUGS
==============

If you find any bugs in this software, please report them to
rlo@hrl.harvard.edu.  Since this software is not supported on
a regular basis, I make no guarantees about how long it will
take to fix the bug, or if it will be fixed at all. Bug fixes
will be cheerfully accepted at any time.  
Please include as much detailed information as possible, 
including:

  1) the data file that caused the bug (if possible)
  2) the OS version and machine type you ran the program on
  3) the compiler used to compile the program

WHERE TO FIND MORE INFORMATION: LITERATURE RELATED
TO THE TECHNIQUES EMPLOYED IN THIS SOFTWARE
==================================================

Ogniewicz, R.L., "Skeleton-space: 
A multiscale shape description combining region and boundary information", 
in Proc. Conf. on Computer Vision and
Pattern Recognition, Seattle, WA, pp. 746-751, June 1994.

Ogniewicz, R.L. and Kuebler, O., "Hierarchic
Voronoi Skeletons", Pattern Recognition, vol. 28, no. 3, 
pp. 343-359, 1995.

Ogniewicz, R.L. and Kuebler, O. (1995),
Voronoi tessellation of points with integer coordinates:
Time-efficient implementation and online edge-list generation,
Pattern Recognition (in press).

Ogniewicz, R.L. and Ilg, M., 
"Voronoi skeletons: Theory and applications", in
Proc. Conf. on Computer Vision and Pattern Recognition, Champaign,
Illinois, pp. 63-69, June 1992.

Ogniewicz, R.L. (1993),
Discrete Voronoi Skeletons, Konstanz, Germany: Hartung-Gorre Verlag.

ACKNOWLEDGEMENTS
================

Several other people have contributed to the development
of this software. The authors are grateful to

Prof. Olaf Kuebler, Communication Technology Lab, Swiss
Federal Institute of Technology, Zurich, Switzerland.

Prof. Alan Yuille, Division of Applied Sciences, Harvard
University, Cambridge MA, USA.

Dr. Markus Ilg, Switzerland

LEGAL ISSUES
============

The authors make NO WARRANTY or representation, either express or implied,
with respect to this software, its quality, accuracy, merchantability, or
fitness for a particular purpose.  This software is provided "AS IS", and you,
its user, assume the entire risk as to its quality and accuracy.

This software is copyright (C) 1993, 1994, 1995 Robert L. Ogniewicz

The parts which have been written by Robert L. Ogniewicz and Markus
Naef are copyright under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version. All other parts are
subject to the specific individual copyright notices by their
authors.
  
You should have received a copy of the GNU General Public License
along with this program (see file COPYING); if not, write to the 
Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

The image loading subroutines are based in part on the work of
the Independent JPEG Group. The libjpeg.a library is copyright 
(C) 1991, 1992, Thomas G. Lane. See the corresponding README
file in subdirectory `jpeg'.

The libtiff.a library is copyright (c) 1990, 1991, 1992 Sam Leffler,
and copyright (c) 1991, 1992 Silicon Graphics, Inc.

The Graphics Interchange Format(c) is the Copyright property of
CompuServe Incorporated.  GIF(sm) is a Service Mark property of
CompuServe Incorporated.



