Nevatia - 6 
set, say a pair of features, to which we add more features that are consistent with the given 
constraints. Thus, it may be possible to limit the complexity to be only linearly dependent on 
number of features, m, (i.e. 0(m)), in the image. 
Use of constraints from geometry is a key component in this approach to reducing 
complexity. The stronger the relations between desired features, the fewer candidates we will 
generate. Knowledge of viewing geometry, such as that of vanishing points (or the direction of 
verticals for parallel projection) can be very important. In our implementation for building 
detection, we can not, in general, estimate the orientation of the sides of the building a priori ; 
however, given one side, the viewing geometry allows us to constraint the direction of the other 
side (assuming a flat roof). Fig. 6 shows the hypotheses generated from the image of Fig. 1(a) by 
the USC building finder described in [6]. The number of hypothesized parallelograms is 2339, 
while the number of segments in Fig. 1(b) is 9344. Even though 2339 may appear to be a large 
number, note that it is not anywhere as large as 9344 4 . 
Figure 6. Roof hypotheses from Figure 2(b) 
b) Validity : A perceptual grouping system must make many subtle distinctions at every stage of 
processing. Observed features in an image are fragmented due to characteristics of the images and 
of the feature detectors. Their may be unmodelled distortions and noise present. Thus, each stage 
of grouping must allow for some “tolerances” from expected properties. Also, we are likely to 
generate many alternative hypotheses for explaining the observed evidence and must select 
among them. This process can be difficult and the right set of rules and parameters is often chosen 
by a trial and error process. Our approach has been to not discard too many hypotheses at an early 
stage but rather to make the distinctions between likely hypotheses only when sufficient data is 
available to make a reliable distinction.