Many empirical studies, including our work on boundary contours, have confirmed the intuition that natural images are scale-invariant. It is our belief that scale-invariance will become more and more important as we move to tackle vision problems in more realistic settings, where we cannot assume the knowledge of object/scene scales.

How can we cope with scale-invariance in natural images? One possible approach, being top-down and brute-force, is to explicitly search over all possible scales. This becomes expensive if one has to cover a large range of scale and a large number of object categories.

An alternative approach, as we choose here, is to develop a scale-invariant representation from bottom-up, and build on this representation later stages of visual processing.

Suppose that we are given a boundary contour, some parts of which are straight and some of which are curved. How can we represent this contour? A common way is to parametrize it by arclength, i.e. to sample it uniformly. Such a representation is rather inefficient: we would like to put enough sample points at fine-scale details, but only a few would suffice for straight lines.

Attneave had his theory that information along contours is mostly concentrated at high-curvature locations. How about we break up a contour at high-curvature locations, as done in our test of Markov assumption? Such a decomposition has the desired property that straight line segments remain undivided, and fine-scale details are sufficiently sampled.

Of course, curvature is not a scale-independent measure. We can easily fix this problem by using a scale-invariant measure, i.e. angle, as the criterion of decomposition. The result is a piecewise linear approximation of the input contour.

The piecewise linear representation above is yet incomplete, as there may exist low-contrast contours, or gaps, that are not detected by the local edge operator. We use the constrained Delaunay triangulation algorithm to complete the piecewise linear approximations. The constrained Delaunay triangulation (CDT) is a variant of of the standard Delaunay Triangulation in which a set of user-specified edges (in our case, the edges in the piecewise linear approximation) must lie in the triangulation.

(a)	(b)

Figure 2: an example of the CDT graph. We use the Pb (Probability of Boundary) edge detector as the input. G-edges (gradient edges detected by Pb) are in black and C-edges (completed by CDT) in green. Note how the CDT manages to complete gaps on the front legs of the elephant (red highlight on the inset at right). These gaps are commonly formed when an object contour passes in front of a background whose appearance (brightness/texture) is similar to that of the object.

The CDT graph can be viewed as a boundary-based, scale-invariant superpixel map. Before using it, we need to ask two questions:

1. As a discrete image representation, how much structure is lost when we move from the image to the CDT graph?
2. How good is the CDT graph at completing gradient-less gaps?

The CDT graph is a generic image representation that can be applied to many vision problems. It has all the nice properties of the superpixels. In addition, it is scale-invariant and can be computed very efficiently.

It is a nice representation to model and exploit mid-level visual cues, such as curvilinear continuity, region grouping, or figure/ground organization. We have developed probabilistic models of mid-level vision using conditional random fields on top of the CDT graphs. We can easily incorporate high-level object knowledge into these models.

The CDT graph, being small and scale-invariant, has also enabled us to efficiently find human body parts using parallelism in a scale-independent way.