94
Fig. 1: Search paths. Fig.2: Edge candidates. Fig.3: Contour lines.
mean of all individual measurements that contributed to the entire edge. Thus, the edge list of this type contains
more information than a mere gradient image for subsequent region determination. All edges are simultaneously
connected with each other in an ordered sequence with respect to their properties length, angle and horizontal
midpoint position. This enables efficient local search procedures for gdge grouping.
The process of contour following requires about 70 ms CPU-time ~ on the average for an image of a complexity
shown in fig. 1—3. Of course, the actual time requirement is dependent on the number of image structures being
in accordance with the straight line supposition and therefore varies slightly from image to image.
22 Region segregation
Having formed an edge list, a connection of proper edges to regions supplies orientation, position, length, width,
and variances of presumed object parts as well as a new level of meaning. Unlike in other applications (e.g. [Dolan
& Riseman 92]), regions cannot be properly separated by a closed boundary because in joint areas an intensity gra-
dient between subparts is mostly missing (see fig. 4). Hence, segmentation is pursued in terms of assigning appro-
priate border lines to each other. Provided an appropriate distance function, the resulting score values could be
entered into a triangular part of a N by N assignment matrix from which the correct pairings have to be determined
by optimization. Several problems do occur here:
l. The number of pairings to be considered is of the order ouv? ) (with N the number of edges). An exhaustive
enumeration of each feature pairing is computationally inefficient.
2. À sound merit function for optimization is difficult to find. For example, it is not always the case that a contour
line has only one partner. When legs are closed a centre line between them belongs to either left and right leg.
3. Often two lines of different lengths have to be combined. If the
longer one is split, additional regions can be segmented (compare
fig. 5a and 5b). But this can be achieved by additional list manipu-
lations only and is not covered by assessments given by an assign-
ment matrix. E
Thus, a globally optimal assignment is approximated by making locally
optimal decisions. This procedure runs considerably fast (around 10 ms
for a typical configuration of 30 edges); only in rare cases a region pres-
ent will be missed. The algorithm follows a prune-and-search scheme
[Edelsbrunner 87], see fig. 6 as an illustration.
1. One list element is chosen to be active (called pivot element here).
For this a suitable second edge shall be searched for. Beginning
with the longest edge of the list, the procedure terminates when the
shortest edge has been processed as pivot element.
2. For each pivot element a limited number of appropriate test ele- Fig.4: Perpendicular to the main
ments as potential partners are sequentially determined in its vi- limb axes no edges can be deter-
cinity (local search). This neighbourhood is expressed in terms of mined.
1 Performance for a SGI 210VGX with one CPU exhibiting 20 MIPS and 3.3 MFLOPS.
IAPRS, Vol. 30, Part 5W1, ISPRS Intercommission Workshop "From Pixels to Sequences’, Zurich, March 22-24 1995
Fi
le
th
wh
CO:
na
to
ua
lat
