Energy Measures for Boundary Extraction
Energy Measures for Boundary ExtractionThere are actually several different sets of masks. All are the same size, currently 17 x 17 pixels, which yields a good compromise between the ability to bridge small gaps and the ability to follow curved structures. This size is modifiable with a simple macro change, but seems well matched to all the other factors in the algorithm, particularly the directional resolution of the low level processing. All of the masks are used via a directional correlation of the mask with the underlying boundary hypothesis (edgel) image (the enhanced gradient magnitude in the current version). Directional information is employed by using in the correlation only points where the direction of the edgel (enhanced gradient) image agrees with the current direction of the boundary being grown. In the current version the directions must agree to within PI/8. Any tighter and we can't follow curves with the mask sizes we use.
The first set of masks are used in the computation of a seed segment - a short initial portion of a boundary that is modelled as a straight line segment. This involves both segment-body and end-stop measures. The body masks are generated (conceptually) by moving a Gaussian along a line segment and taking the maximum value generated during the sweep. In the current version, we use a Gaussian with a standard deviation of one pixel. Basically this is as narrow as we can make it without encountering digital aliasing problems as we change the orientation. The end-stop masks are a difference of Gaussians (also with 1-pixel standard deviation) separated by two standard deviations and centered at the segment endpoints. We generate seed segment templates for centered segments at 64 orientations (actually 32, since they are symmetric), and 16 lengths from about 3.5 to 13.5 pixels. The sub-pixel growth is needed to avoid a potential "miss" by the end-stop templates due to digital aliasing.
The total match value for a segment, which can be interpreted as negative energy, is given by the body match value plus 1/2 the end-stop measures if they are positive (for body and end-stop masks generated with Gaussians having the same scale). The non-linearity is needed so that a brightening of the boundary does not cause termination. This termination condition is necessarily a bit arbitrary; the values used here were designed to terminate the growth of a segment if the gradient dropped suddenly to less than 1/4 of its previous value and remained there for more than about 2 pixels. Empirical use indicates this works well, and moreover, the performance is not very sensitive to the relative weighting of the terms.
Note that the endstop measures are used even when we are seeding a longer boundary. If we leave out the end_scores, the process works marginally better on short segments becuase it doesn't get hung up on corners and start with a bad orientation estimate. But it also seeds large numbers of garbage segments off speckles in textured images, since any start is allowed to grow into a very weak seed segment, which may then propagate for a bit before a random variation kills it. The end scores kill these immediately, so we keep them.
The second set of masks are used for extending the tips of a growing boundary. These are essentially half of the segment templates - they extend out from the origin in only one direction. We need only two lengths at each of 64 orientations - equivalent to the two longest seed segments at each orientation. The shorter masks are used to establish a base value which is compared to the value from the longer masks to decide whether a tip should be extended. The presence of the end-stop values is critical here; otherwise a tip would always be grown. The energy combination is the same: the body match value added to 1/2 the end-stop value if it is positive. Again, the algorithm does not seem to be overly sensitive to the exact weighting of the two terms.
Back to
Randal Nelson's home page