On Seeing Things, Again

ABSTRACT

Computational vision has developed as a dis­ tinct scientific field in the last decade with a shared paradigm, a research strategy and a collec­ tion of results within a common theory. That development has focussed on an analysis of the visual task itself; the task requires the unpacking of a collection of confounding processes. Explicit intermediate representations of the confounded domains must be constructed, with certain characteristics. Constraint-based representations and processes provide a common methodology at all levels of the visual system. Adequacy criteria may be applied to the various representations of visual knowledge, both implicit and explicit, that have been proposed. Finally, nine broad areas of research progress are summarized. The agenda for the next decade must include understanding meta-knowledge computation such as the representation and use of the hierar­ chies of default assumptions that our microtheorie~ require.

THE .TASK

The v1s1on problem is characterized by information loss in the image formation process . The intensity values in an image are the result of the interaction of many factors, including the intensity, colour, location and nature of the light sources, the position, reflectance, trans­ parency and opaqueness of the objects in the scene, the transmission, refractance, absorption and scattering properties of the light transmission media, the optical properties of the imaging device, th~ response characteristics of the sensor

and so forth.

The difficulty of computational v1s1on arises not because we do not understand or cannot model these processes and their interactions; we do and we can . The difficulty lies in representing the uncertainty caused by the many-to-one confounding process itself and in resolving that uncertainty through the acquisition of more imagery or the addition of other constraints on the elements of the confounded domains .

ON SEEING THINGS, AGAIN

Alan Mackworth Laboratory for Computational Vision Department of Computer Science University of British Columbia

Vancouver, B.C. , Canada V6T 1 W5

II THE EMERGENCE OF A SCIENCE

The emergence of the science of computational vision over the last decade has been characterized by this focus on the nature of the visual task itself. Any vision system must make explicit descriptions of the sets of elements of the implicit, confounded domains that could have produced the image under certain specific~ priori assumptions (Mackworth, 1983a).

Marr (1982) insisted on three levels of analysis: a computational theory of the task that specifies the purposes of the system, the domains involved and the input/output predicates for processes operating on those domains, an algorith­ mic level giving detailed descriptions of those processes and a mechanism level that describes the implementation of those algorithms on the real hardware available (or on virtual hardware, since this analysis may be recursive) . The research conducted in the style of this dictum has had several effects. First, we see that there can be a genuine science of vision with a common body of theory at the computational level. 1his science can be applied either to biological systems or to man-made artefacts. Second, an obsession with particular algorithms or mechanisms without justification or analysis at the computational task level is sterile. Some historically early work concentrated on performance and one-off demonstrations, even going so far as to make a virtue of necessity, claiming "The program is the theory". The days of the theory-shy vision­ hacker are over. Equally, of course, we must avoid Charybdis : theory that exists for its own sake, masquerading as pure science, with all its seductive allure. Highly mathematical micro­ theories embodying artificial assumptions, not embedded in a realistic system design, may not be very useful .

Since the computational level of analysis is, in large measure, dictated by the task and the mechanism level dictated, in some sense, by the hardware, the widest choice with the weakest evaluation measures occurs at the algorithmic level (Poggio, 1983).

III INTERMEDIATE REPRESENTATIONS

must have explicit representations of the inter­ mediate stages. Such intermediate representations mus t have certain characteristics. They mu st be capable of finitely representing ~and ~the (usually) infinite number of configurations in the intermediate domains that could have produced the image . They are best thought of as intensional descriptions of equivalence classes in some con­ figuration space for the intermediate domain . They must be capable of being refined as additional information is available in the form of additional imagery of the assumed common underlying scene whether that information comes from stereo, colour, structured light, a rangefinder, motion or some other source. They must be efficiently computable from the information available in the image and the other intermediate representations. They must be capable of representing the tradeoffs between intermediate domains such as the shape/perspective tradeoff or the reflectance map/shape tradeoff (Woodham, 1983) that allow one factor to be varied while simultaneously varying the other to maintain a constant image. Finally, they must be capable of representing and enabling access to model constraints (and their logical consequences) such as "this surface is convex", "all surfaces are 'smooth' or ruled", "all surfaces have Lambertian reflectance maps", "all objects in this domain are opaque polyhedra", "this object is a banana" and the like.

Intermediate representations such as the primal sketch (Marr, 1982), intrinsic images (Barrow and Tenenbaum, 1978), the gradient space (Huffman, 1971 ; Mackworth, 1973), the 2~0 sketch (Marr, 1982), the reflectance map (Horn, 1977) and generalized cylinders (Binford, 1971) have been developed with some of these criteria in mind if not explicitly stated, although none of them properly satisfy all those crit~ria.

Intermediate representations are arranged on a spectrum based on the degree of egocentricity of .their coordinate frames . The ones noted are so ordered. Representations can be categorized as retina-centred, viewer-centred, object-centred and world-centred .

IV CONSTRAINTS

This characterization of the v1s1on task is based on the fact that a single image undercon­ strains the scene; it asks how to represent the equivalence class of possible scenes . . It then asks what additional constraints are necessary to specify the scene uniquely. The additional constraints may arise from ~ priori general knowledge of the scene domain, the imaging process, lighting and the like or from contingent know­ ledge of context or from general or specific object models or from additional images together with assumptions about how they interrelate in the scene domain.

The constraint-based view has proven useful at the computational, algorithmic and mechanism levels of analysis (Marr, 1982 ; Hackworth, 1973,

1977a; Zucker, 1981). The intermediate repre­ sentations can al so be judged on their ability to support this view of the process by allowing representation of such constraints at all levels of the visual system.

V VISUAL KNOWLEDGE REPRESENTATIONS

The vision task requires knowledge-based processing thus placing it firmly in the artifi­ cial intelligence paradigm. A set of criteria for descriptive adequacy and procedural adequacy must be used to evaluate proposed visual knowledge representations (Clowes, 1971; Havens and Mackworth, 1983). Parenthetically, this does not prejudge the goal-driven/data-driven distinction which is simply one of the procedural adequacy issues for the particular task and level of the vision system involved.

The constraint-based approach is not commit­ ted to a thoroughgoing proceduralization of the knowledge necessary for interpretation. As a consequence it enables the design of image-based systems where there may be no rigid distinction between input and output (Barrow and Tenenbaum, 1978). Information and constraints are simply propagated from whichever source is able to supply them. In overdetermined visual tasks such as industrial inspection or remote sensing, where part geometry, digital terrain, reflectance and lighting models are available, this may be most fruitful approach (Woodham, 1983). It also suggests a rapprochement of the long-divorced vision and graphics communities. Other knowledge representations including logic (Kowalski, 1979), grammars (Browse, 1982) and schema systems (Havens and Mackworth, 1983) share thi~ procedural adequacy advantage (Mackworth, 1983b) .

VI THE ACHIEVEMENTS

In summary, there are nine main areas of achievement of the past decade of computational vision. First, there has been a convergence on a paradigm for a science of computational vision (Brady, 1981). Second, there has been an emphasis on understanding, modelling and exploiting the physics of image formation - its geometry and radiometry (Horn, 1977). Third, the constraint­ based nature of vision has b~come clear . Fourth, the importance of various intermediate represen­ tations and criteria for judging them have emerged. Fifth, there has been a flurry of microtheories, results and algorithms for shape recovery from various information sources including shading (Ikeuchi and Horn, 1981), texture (Witkin, lg81), motion (Ullman, 1979; Longuet-Higgins and Prazdny, 1981), stereo ( Grimson, 1981 ; Baker and Binford, 1981), contour (Clowes, 1971; Huffman, 1971; Mackworth, 1973; Barrow and Tenenbaum, 1981 ; Kana de, 1981) and photometric stereo (Woodham, 1981). Sixth, some of the new insights have been applied to understanding the neuro­ physiology and psychophysics of mammalian vision systems (Poggio, 1983; Ullman and Hildreth, 1983; Zucker, 1983). Seventh, new non-von Neumann models of computation of the cooperative (Marr, 1982), connectionist (Hinton, 1981; Ballard, 1981), relaxation (Zucker, 1981), and consistency (Mackworth, 1977b) style are emerging and suggesting new architectures. Eighth, criteria of descriptive and procedural adequacy have guided the development of schema-based knowledge repre­ sentations for high level vision (Hanson and Riseman, 1978; Brady and Wielinga, 1978; Browse, 1982; Havens, 1983; Havens and Mack­ worth, 1983). Engineering applications of the new science in industrial inspection, robotics and remote sensing are flourishing at CMU, SRI, Machine Intelligence, Fairchild, Hitachi, GM, Stanford, MIT, McGill, UBC and many other labs around the world .

VII THE AGENDA

The agenda for the next decade has the same item at the top of the list as the agenda of the last decade, "How is vision possible?" The answers to that question will continue to flow from pushing hard at the boundaries of all the nine areas outlined above.

One additional research topic must be added to that agenda . The current standard theory has within it a large collection of microtheories concerned, for example, with shape recovery . Each of these microtheories has its own set of assump­ tions and restrictions, domain of applicability, requisite inputs and attached methods, many of which are implicit both in the theories and the programs that implement them. We must now learn how to represent these knowledge "bundles" explicitly in our programs and have well-struc­ tured ways of indexing, invoking, using and coordinating them.

As an example of this, our cooperative inter­ pretation paradigm suggests that two (or more) knowledge sources can work synergistically to interpret an image when either alone would do poorly (Mackworth, 1978). Glicksman's (1983) Missee system uses the qualitative spatial scene knowledge provided by the Mapsee2 interpretation of a sketchmap to augment the spectral and spatial constraints crudely extracted from an aerial image of the same scene, integrating information from both sources into a single schema-based represen­ tation.

More generally, meta-knowledge computation must be part of the vision system. One approach to this is to apply default logic theory (Reiter, 1980). Many logical implications flow from the scene domain to the image domain but can only be reversed under various contingent "general view­ point", "general 1 ight source" or "smooth surface" assumptions analogous to the "closed world" or "circumscription" (McCarthy, 1980) assumptions. As a trivial example, a straight edge in a 3D scene is depicted as a straight line in the image. The abductive inference step required to reverse that logical impliciation does not follow without explicitly invoking the default "general view­ point" assumption. Current vision systems (Lowe and Binford, 1981; Binford, 1981) abound with examples of this style of reasoning . We must develop a logic of depiction.

The importance of hierarchical descriptions both in the image domain and in the scene domain is well understood . Spatial frequency channels, for example, simply encode a hierarchy of image detail useful for edge detection (Marr and Hildreth, 1980) and stereo matching (Grimson, 1981). Within a particular scene domain, specia­ lization and composition hierarchies serve both descriptive and procedural adequacy (Mackworth and Havens, 1981). Hierarchical descriptions will also prove to be useful for organizing collections of default and domain assumptions of widely varying power and generality.

ACKNOWLEDGEMENTS

The suggestions and support of all my colleagues, especially Bave Brent, Roger Browse, Rachel Gelbart, Jay Glicksman, Bill Havens, Jan Mulder, Ray Reiter and Bob Woodham, are gratefully acknowledged. Max Clowes was a mentor and a friend.