In early two dimensional scene understanding work, Shirai [148] and Waltz [162] achieved a rough separation of objects from the background by assuming external boundaries of regions were the separator. Heuristics for adding isolated background regions, based on TEE matching, were suggested. These techniques required that the background be shadow free, and that the objects did not contact the image boundary.
Both of these approaches concentrated on finding relevant objects by eliminating the irrelevant (i.e. the background). This was later seen to be unprofitable because relevance is usually determined at a higher level. The methods were also incapable of decomposing the object grouping into smaller object groups.
Guzman [81] started a sequence of work on surface segmentation using image topology. Starting from line drawings of scenes, he used heuristics based on boundary configurations at junctions to link together image regions to form complete bodies. Huffman [95] and Clowes [48] put Guzman's heuristics into a more scientific form by isolating distinct bodies at connected concave and obscuring boundaries in two dimensional images.
Sugihara [155] proposed two heuristics for separating objects in an edge labeled three dimensional light-stripe based range data image. The first separated objects where two obscuring and two obscured segments meet, depending on a depth gap being detectable from either illumination or viewer effects. The second heuristic separated bodies along concave boundaries terminating at special types of junctions (mainly involving two obscuring junctions). Other complexities arose because of the disparate illumination and sensor positions.
Kak et al. [99] described segmentation from a labeled edge diagram that connects "cut"-type vertices with obscuring and concave edges, producing a segmentation similar to the primitive surface clusters.
The work described here extends the previous work for application to objects with curved surfaces, some laminar surface groupings and hierarchical object structure. In particular, obscuring boundaries can become connecting (in certain circumstances) which allows the two laminar surfaces in the folded leaf problem to become joined into a single surface cluster (Figure 5.3). Further, concave boundaries defining ambiguous depth relationships can be exploited to limit combinatorial explosion in the creation of larger surface clusters, which is necessary to provide the image context for structured object recognition.
Given the current input data, it is possible to directly infer from surface depth and orientation the type of surface discontinuity boundaries (i.e. obscuring, convex, concave). If the orientation data were missing, then topological analysis like that from the two dimensional blocks world analysis (e.g. [95,48,162,110,161,100,162]) can sometimes uniquely deduce the three dimensional boundary type. Labeling rules could also correct some data errors (e.g. [60]).
These projects also introduced the boundary labels of types obscuring (front surface, back surface) and shape discontinuity (convex, concave) that are used for the reasoning described here. Also useful is the understanding of how boundary junctions relate to observer position and vertex structures (e.g. Thorpe and Shafer [160]).