THE EXTENDED EUCLIDEAN DISTANCE TRANSFORM
Mark Wright
June 1995
Shape representation has always played a central role in computer vision. Skeletal shape descriptors which make symmetry explicit are an important class of shape representations. The goal of this thesis is to study the problems encountered using skeletal shape descriptors. The thesis unites three main themes of work: A filter based approach to skeletonisation, skeletonisation using parallel wave propagation and skeletonisation using an extended Euclidean distance transform.
The distance transform approach to skeletonisation computes a skeleton by identifying the so called local maxima of the distance transform. A new method has been proposed to detect these features using a filter-base approach inspired by models of processes in the human visual system. Further improvements were made by using a filter designed to detect a specific geometric feature on the distance transform which corresponded to the skeletal points. This improved the quality of skeletons obtained but could only compute restricted skeletal descriptions.
The wave propagation algorithm of Brady and Scott has been studied; they originally implemented this on a simulator of the Connection Machine. The issues of mapping the algorithm onto an array of transputers have been investigated. An efficient implementation was realised by reducing synchronisation and data transfer overheads. It was found that the algorithm could compute more general shape descriptions than the distance transform approach but the quality of skeletons produced was not as good.
Using standard techniques from singularity theory, an analysis of distance functions from object boundaries has been undertaken. This resulted in the formal definition of a new extended Euclidean distance transform. An algorithm has been devised to perform skeletonisation using the extended distance transform. This combined the advantages of the filter and wave based techniques in that it produced skeletons of a high quality which made more symmetries explicit than the standard distance transform approach. In addition, the extended distance transform provides an elegant unifying framework for work on skeletal shape descriptions.
If you have difficulty viewing files that end '.gz',
which are gzip compressed, then you may be able to find
tools to uncompress them at the gzip
web site.
If you have difficulty viewing files that are in PostScript, (ending
'.ps' or '.ps.gz'), then you may be able to
find tools to view them at
the gsview
web site.
We have attempted to provide automatically generated PDF copies of documents for which only PostScript versions have previously been available. These are clearly marked in the database - due to the nature of the automatic conversion process, they are likely to be badly aliased when viewed at default resolution on screen by acroread.