next up previous contents index CD CD Algorithms
Next: Polygon Partitioning Up: Computational Geometry Previous: Bin Packing

Medial-Axis Transformation



Input description: A polygon or polyhedron P.

Problem description: What is the set of points within P that have more than one closest point on the boundary of P?

Discussion: The medial-axis transformation is useful in thinning a polygon, or, as is sometimes said, finding its skeleton. The goal is to extract a simple, robust representation of the shape of the polygon. As can be seen from the figures above, the thinned versions of the letters capture the essence of the shape of an `A' and a `B', and would be relatively unaffected by changing the thickness of strokes or by adding font-dependent flourishes such as serifs.      

The medial-axis transformation of a polygon is always a tree, making it fairly easy to use dynamic programming to measure the ``edit distance'' between the skeleton of a known model and the skeleton of an unknown object. Whenever the two skeletons are close enough, we can classify the unknown object as an instance of our model. This technique has proven useful in computer vision and in optical character recognition. The skeleton of a polygon with holes (like the `A' and `B') is not a tree, but an embedded planar graph, but it remains easy to work with.   

There are two distinct approaches to computing medial-axis transforms, depending upon whether your inputs are arbitrary geometric points or pixel images:

Implementations: MAT [Ogn93] is a medial-axis transform code designed for 2D skeletonization of binary images, written by Robert Ogniewicz. MAT accepts a variety of different input formats, including polygonal representations. This seems to be a solidly built program, and it should be your first stop on seeking a routine for thinning.   It available from

Programs for constructing Voronoi diagrams are discussed in Section gif.

Notes: For a comprehensive surveys of thinning approaches in image processing, see [LLS92, Ogn93]. The medial axis transformation was introduced for shape similarity studies in biology [Blu67]. Applications of the medial-axis transformation in pattern recognition are discussed in [DH73]. Good expositions on the medial-axis transform include [O'R94, Pav82].  

The medial-axis of a polygon can be computed in tex2html_wrap_inline30301 time for arbitrary n-gons [Lee82], although linear-time algorithms exist for convex polygons [AGSS89]. An tex2html_wrap_inline30303 algorithm for constructing medial-axis transforms in curved regions was given by Kirkpatrick [Kir79].

Related Problems: Voronoi diagrams (see page gif), Minkowski sum (see page gif).    

next up previous contents index CD CD Algorithms
Next: Polygon Partitioning Up: Computational Geometry Previous: Bin Packing

Mon Jun 2 23:33:50 EDT 1997