Curve Growth in Boundary Extraction

The growth process for a boundary curve starts by attempting to grow a seed segment at a high gradient point selected in the current local neighborhood. This process is directed by a seed image, a thinned version of the enhanced gradient image, which keeps track of potential starting points. Currently the image is broken into 32x32 pixel local neighborhoods, and up to 6 boundary fragments are initiated in each neighborhood. Even in highly cluttered scenes, this maximum is rarely reached. Seed segments are grown by starting with a minimally sized segment at the orientation suggested by the underlying gradient. A gradient descent process sequentially checks the match score for one-step variations, first in the orientation, and then in the length parameter. This process continues until either a local maximum in the match is reached, or the size of the seed segment reaches the maximum represented by the set of masks (about 13 pixels).

In the case that a maximum is reached, the process either returns with failure, if the segment did not exceed a user specified minimum, or generates a straight boundary representing the segment. In either case, pixels near the segment in the seed image (a thinned edgel map) are marked as unavailable so we don't try to initiate another boundary involving the same points.

In the case that the length of the seed segment maxed out, we attempt to grow the tips. This is a two-stage process. First we compute a baseline tip match score using the short tip masks at the current orientation of the tip. (When we are first starting, this is the direction of the seed segment.) We then test extensions of the tip using the longer tip masks, in the current, and neighboring directions. If any of these match values exceeds the baseline, we conclude that the tip should be extended. (See Details of energy measure) The second stage looks for the best extension. We first look for a new location for the base of the tip. This might be any of 3 pixels neighboring the current base point in the general direction of boundary propagation. From each of these, we probe out using the short tip masks, varying the direction clockwise and counterclockwise, as long as the match score keeps increasing, up to about 30 degrees until a maximum is found. The maximum over all directions and all 3 prospective base points is taken as the new base point and tip orientation.

The process terminates when either the extension test indicates that the tip can not be extended, or one of several special conditions are raised. Failure of the extension test accounts for almost all terminations in natural images, and above 95% of terminations in scenes of man-made objects. Perceptually, this generally coresponds to a highly curved corner, an occlusion, or a shadow or surface marking change. The special conditions include wrapping of a smooth, closed boundary, and gradual fading of an edge to nothing. Wrapping detection is accomplished directly using a scratch image, and occurs most frequently in images of curved manufactured objects. Slow fading to black occurs most frequently with highlights on cylindrical, semi-glossy objects. Because the process is designed to follow edges that may fade, and there is always a little bit of gradient evidence due to shading or random noise, we have to identify the situation explicitly. There is also an explicit high curvature test to look for corners of 45 degrees or more but it is hardly ever raised, as most corners cause a failure to extend exit.

After both tips have terminated, the short (6 pixel) extensions representing the tip probe are hooked to the chain of base points. A number of boundary parameters (length, curvature, center, etc.) are computed from the chain, and output along with the chain as a boundary descriptor. Image points close to the boundary (within 3 pixels) that have matching gradients are marked both in the seed image, and in the enhanced gradient image against which the tip masks are correlated. This prevents the same boundary from being extracted repeatedly.

Back to boundaries page

Back to Randal Nelson's home page