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:

• Geometric data - Recall that the Voronoi diagram of a point set S decomposes the plane into regions around each point such that each point within the region around is closer to than to any other site in S. Similarly, the Voronoi diagram of a set of line segments L decomposes the plane into regions around each line segment such that each point within the region around is closer to than to any other site in L.  

  Any polygon is defined by a collection of line segments such that shares a vertex with . The medial-axis transform of a polygon P is simply the portion of the line-segment Voronoi diagram that lies within P.

  Any line-segment Voronoi diagram code thus suffices to do polygon thinning. In the absence of such a code, the most readily implementable thinning algorithm starts at each vertex of the polygon and grows the skeleton inward with an edge bisecting the angle between the two neighboring edges. Eventually, these two edges meet at an internal vertex, a point equally far from three line segments. One of the three is now enclosed within a cell, while a bisector of the two surviving segments grows out from the internal vertex. This process repeats until all edges terminate in vertices.  

• Image data - Whenever attempting geometric approaches to image processing problems, we must remain aware that images are pixel-based and not continuous. All the pixels sit as lattice points on an integer grid. While we can extract a polygonal description from the boundary and feed it to the geometric algorithms above, the internal vertices of the skeleton will most likely not lie at grid points. This may well make geometric approaches inappropriate for your intended application.   

  Algorithms that explicitly manipulate pixels tend to be easy to implement, because they avoid complicated data structures. The basic pixel-based approach for constructing a skeleton directly implements the ``brush fire'' view of thinning. Imagine a brush fire along all edges of the polygon, burning inward at a constant speed. The skeleton is marked by all points where two or more fires meet.   The resulting algorithm traverses all the boundary pixels of the object, deletes all except the extremal pixels, and repeats. The algorithm terminates when all pixels are extreme, leaving an object only 1 or 2 pixels thick. When implemented properly, this takes time linear in the number of pixels in the image.

  The trouble with such pixel-based approaches is that the geometry doesn't work out exactly right. For example, the skeleton of a polygon is no longer always a tree or even necessarily connected, and the points in the skeleton will be close-to-but-not-quite equidistant to two boundary edges. The usual solution is to tweak your implementation until it gives skeletons that look decent on the data that you think is most interesting. Since you are trying to do continuous geometry in a discrete world, there is no way to solve the problem completely. You just have to live with it.

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 http://hrl.harvard.edu/people/postdocs/rlo/rlo.dir/rlo-soft.html.

Programs for constructing Voronoi diagrams are discussed in Section .

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 time for arbitrary n-gons [Lee82], although linear-time algorithms exist for convex polygons [AGSS89]. An algorithm for constructing medial-axis transforms in curved regions was given by Kirkpatrick [Kir79].

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