Medial Representations

Last updated on Wednesday, November 8, 1995 at 9:00 AM.

Reading

Why Medial?

To infer larger structure from a shape requieres that we be able to group together parts of the boundaries that aren't necessarily adjacent. For example, there is an immediacy to the way we see the two sides of an object. If we look at telephone poll, for example, we can make immediate judgments of how thick or thin it is. We do so by pairing up the two opposide sides and comparing them, even without having to trace completely around the object to ensure that they are indeed part of the same contour.

Once we pair sides in this fashion, it's reasonable to start talking about object middles. These middles give structure to the shape, allowing us to identify trunks, arms and branches, narrowing or widening sections, etc.

Such middle-related strctures are called medial representations.

Blum's Medial Axis

Definition

The most common form of medial representation is Blum's medial axis. (In later years, Harry Blum wrote that he prefered to call it the symmetric axis, but others continue to call it the medial axis as part of the larger class of medial representations.)

Blum's medial axis can be defined in a few different intuitive ways, all equivalent:

Grassfire Analogy.

Consider a fire started at the boundary that spreads with uniform speed and burns everything in its path. As the fire spreads into the middle, each part eventually meets other parts of the fire started at other parts of the boundary. When these two wavefronts meet, they quench each other because there is nothing left for either to burn. Since the fire spreads at uniform speed, these "quench points" must be equidistant from two different parts of the boundary. The locus of these quench points is the medial axis.

Maximal Discs.

Suppose that at each point of the boundary you placed a circle on the inside of the boundary such that it was tangent to it. If you start with a very small circle and expand it outwards, it will eventually "bump into" other parts of the boundary. When you've grown it as large as possible, you'll have a circle that has the following properties:

• It is entirely within the object, and
• It is tangent to the object at more than one point

The locus of centers of all such circles is the medial axis.

Ridges in a Distance Transform.

A distance transform assigns to each point in the image a minimal distance from some locus of points. If we build a distance transform from the boundary of the object, we end up with zero at the boundary, increasing values just inside it, yet higher values farther inside, etc. As we progress from away from a particular point on the boundary, we find increasing values in the distance map until we reach a point as which we are now closer to some other part of the boundary than the place that we left. So, the distance increases as you progress inwards until it forms a ridge, a locus of points with values higher than those just off the ridge on either side. The locus of these ridges in the distance transform is the medial axis.

There are, of course, various mathematical definitions in the literature as well. They come in different forms, but they typically correspond to one of these three intuitive definitions.

Medial Hierarchies

These branches also form a hierarchy. Each bump on an arm of the shape is a branch of a branch.

Radius Values

If we let s be arc length along any given segment of the axis, we have a one-dimensional function along the segment.

If is positive, this part of the object widens as we progress along the axis segment; if it's negative the part narrows.

The behavior of r is limited by

Types of Points

Two disjoint sets of points.

Most of the axis points fall into this category.

Three disjoint sets of points.

These are branch points.

Exactly one contiguous set of points.

These are end points.

Notice that its possible for the medial disc to touch the boundary in a set of contiguous points rather than a single one. In other words, the boundary is locally circular.

These sets of points don't really change the properties of the resulting axis--it's the number of disjoint sets of points, not the actual number of points themselves, that are important.

Sensitivity to Noise

The length of the new branch isn't necessarily reflective of the significance of the variation. It must extend all the way out to the base of the bump itself.

Building and Pruning Hierarchies

Ways to do this include

• Smoothing the boundary before computing the axis,
• Pairing the boundary points to the corresponding axis segments and pruning based on length of the boundary (Ogniewicz, 1992).

By ordering the segments according to the order in which they would be pruned, you can organize them into a top-down hierarchy.

Pruning away segments or arranging them in order of significance can (to a limited degree) let you compare similar but slightly different objects.

Other Medial Representations

• The center of the circle lies on the Blum symmetric axis.
• The midpoint of the chord between the two boundary points lies on Brady's Smooth Locus of Symmetries or SLS.
• The midpoint of the chord between the two boundary points lies on Leyton's Process-Induced Symmetric Axis of PISA.

Brady's SLS definition seems to be more intuitive than Blum's because the axis really does lie directly between the related points. It is more complex to compute, however.

Leyton's PISA definition isn't quqite as intuitive, but the resulting representation seems to describe the way you have to push in or push out the boundary to produce the shape (hence the "process-induced" in the name).

Another method, which approaches the Blum definition when taken to the continuous limit, is the Voronoi Skeleton. I'll come back to this later.

Computational Methods

1. Computational expense.
2. The discrete pixel grid.

Thinning

What is left from this thinning is a structure called a skeleton, similar in principle to the medial axis.

Distance Maps

1. Generate the distance map, and
2. Find its ridges.

Generating Distance Maps

One can compute less accurate distance maps using more efficient methods. (There are also more efficient methods for precise maps.) For these methods, we simply use a different measure of distance. Remember the city block and chessboard distances we discussed earlier? If we use a city block distance measure, we can propogate the minimum distance from the boundary by simply labeling each pixel i with

That is, we simply find the 4-connected neighbor that is closest to a neighhbor and add 1.

We can generalize this by using

and expanding the "neighborhood" of i.

If we expand to 8-connected neighbors, we could use the chessboard distance or we could more closely approximate the Euclidean distance by letting

Since we don't really care about the actual distance, just something proportional to the distance, we can approximate these distances with integers that have approximately the same ratio as . For example, values of 7 and 5 are commonly used.

We can extend this idea yet further by extending the neighborhood to pixels that are farther away. Instead of looking at a area, we could look at a one or larger. This decreases the computational advantage but also decreases the error between the distance measure and a Euclidean one.

Remember from an earlier lecture that distance measures have the following properties:

The first property ensures that our recursive distance-computing method produces a monotonically increasing result. The second property ensures that the result is lower-bounded by the Euclidean distance.

There are many other uses for distance maps in Computer Vision. We probably won't talk about others this semester, but be aware of them.

Finding Ridges

Voronoi Methods

We don't have to go to this limit, though, to get a usable skeletal structure.

Higher Dimensions

These medial manifolds have useful applications for three-dimensional vision.

Vocabulary

• Medial Axis
• Symmetric Axis
• Smooth Locus of Symmetries
• Process-Induced Symmetric Axis
• Distance Map
• Voronoi Skeleton