Representation and control in program that understands line sketches of houses

In this thesis, a program, HOUSE, is described that can interpret line sketches of houses and other polyhedral objects. The program is part of the SEE project, a sketch understanding project at the University of British Columbia. In this respect HOUSE is a generalization of MAPSEE, a program that can interpret line sketches of geographic maps. The most important goal of HOUSE is to test the adequacy and efficiency of the program's control structure which is based on a helical metaphor for the perceptual process. Such a helical metaphor is based on a stratified interpretation process with a bottom-up, pass-oriented control structure. HOUSE takes (like MAPSEE) as input a plot program by means of which the sketch can be displayed on a graphical display device. The program subsequently describes the sketch at different levels of representation. These levels can be categorized in two domains: a picture domain consisting of two-dimensional representations of the sketch and a scene domain consisting of three-dimensional representations. Processing in the picture domain is dominated by a segmentation process that results in three different types of representations. In contrast with MAPSEE, HOUSE also maintains different levels of representation in the scene domain. Each of these levels represents the sketch at a different degree of abstraction. The cycle of perception with its four stages serves as a metaphor for describing the interpretation process at each of these levels. Cues are first formed by the segmentation process (cue discovery); these cues (the vertices) suggest possible interpretations for the primitives (the edges) at the lowest level in the interpretation domain (model invocation); these interpretations are taken by a network consistency algorithm that tests the global consistency among these interpretations (model testing and elaboration). Interpretations that are part of a globally consistent description of the sketch then serve as cues for the next higher level where the cycle is repeated. This process continues until the sketch is described at the highest possible level of abstraction. Several examples were run with the program. Apart from a number of desirable features, these tests showed two important weaknesses of the helical metaphor: its inability to account for incomplete line sketches, and its inability to impose top-down constraints. These weaknesses led to the formulation of a more powerful metaphor: the multi-helix. Among other things, this multi-helix allows multiple access to the different levels of representation in both a bottom-up and top-down direction. A comparison of the multi-helix metaphor with several other perceptual processing metaphors argues for the former's superior ability to account for certain characteristics of the perceptual process. Consequently, the multi-helix can be seen as another step towards a theory of machine perception.Science, Faculty ofComputer Science, Department ofGraduat