VISUAL INFORMATION PROCESSING: The structure and creation of visual repr~entations

1. Introduction

Modern neurophysiology has learned much about the operation of the individual nerve cell, but un~leasantly little about the meaning of the circuits they compose in the brain. The reason for this can be attributed, at least in part, to a failure to recognize what it means to understand a complex information-processing system; for a complex system cannot be understood as a simple extrapolation from the properties of its elementary components. One does not formulate, for example, a description of thermodynamical effects using a large set of equations, one for each of the particles involved. One describes such effects at their own level, that of an enormous collection of particles, and tries to show that in principle, the microsccpic and macroscopic descriptions are consistent with one another.

The core of the problem Is that a system as complex as a nervous system or a developing embryo must be analyzed and understood at several different levels. Indeed, in a system that solves an information prdcessing problem, we may distinguish four important levels of description [~1arr & Poggio 1977, Marr 1977a].

At the lowest, there is basic component and circuit analysis -- how do transistors (or neurons), diodes (or synapses) work? The second level is the study of particular mechanisms: adders, multipliers, and memories, these being assemblies made from basic components. The third level is that of the algorithm, the scheme for a computation; and the top level contains the theorv of the computation. A theory of addition, for example, would encompass the meaning of that operation, quite independent of the representation of the numbers to be added -- say Arabic versus Roman. But it would also include the realization that the first of these representations is the more suitable of the two.An algorithm, on the other hand, is a particular method by which to add numbers. It therefore applies to a particular representation, since plainly an algorithm that adds Arabic numerals would be useless for Roman. At still a further level down, one comes upon a mechanism for addition -- say a pocket calculator -- which simply implements a particular algorithm. As a second example, tate the case of Fourier analysis. Here the computational theory of the Fourier transform -- the decomposition of an arbitrary ma thematical curve into a sum of sine waves of di ffering frequencies -- is well understood, and is expressed independently of the par ticular way in which it might be computed. One level down, there are several algorithms for computing a Fourier transform, among them the so-called Fast Fourier Transform (FFT), which comprises a sequence of mathematical ope rations, and the so-called spatial algorithm, a single, global operation that is based on the mechanisms of laser optics. All such algorithms produce the same result, so the cho ice of which one to use depends upon the pa rticular mechanisms that are available. If one has fast digital memory, adders, and mu ltipliers, one will use the FFT, and if one has a laser and photographic plates, one will use an "optical" method.

Now each of the four levels of description will have its place,in the eventual understanding of perceptual information processing, and of course there are logical and causal relations among them. But the important point is that the four levels of description are only loosely re lated. Too often in attempts to relate psychophysical problems to physiology there is confusion about the level at which a problem ar ises -- is it related, for instance, mainly to the physical mechanisms of vision (like the after - images such as the one you see after sta ring at a lightbulb) ·or mainly to the computational theory of vision (like the ambi guity of the Necker cube?). More dis turbingly, although the top level is the most neglected, it is also the most important Thi s is because the nature of the computations tha t underly perception depend more upon the computational problems that have to be solved than upon the particular hardware in which thei r solutions are implemented. To phrase the ma tter another 1-:ay, an algorithm is likely to be understood more readily by understanding the nature of the problem that it deals with than by examining the mechanism (and the hardware) by which it is embodied. There is, after all, an analog to all of this in physics, where a the rmodynamical approach represented, at least hi storically, the first stage in the study of rna tter: it succeeded in producing a theory of gross properties such as temperature.

This research was conducted at the Artificial Inte lligence Laboratory of the Massachusetts Inst i t ute of Technology. Support for the Labora tory's artificial intelligence research is prov ided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract number K0 00 14-75-C-0643, and in part by NSF grant ~1CS 77-07569.

A description in terms of mechanisms or elementary components -- in this case atoms and molecules -- appeared some decades afterwards.

Our main point, therefore, is that the topmost of our four levels, that at which the necessary structure of computation is defined, is a crucial but neglected one. Its study is separate from the study of particular algorithms, mechanisms, or hardware, and the techniques needed to pursue it are new. In the rest of this article, we summarize some examples of vision theories at the uppermost 1 eve!.

2. Conventional Approaches

The problems of visual perception have attracted the curiosity of scientists for many centuries. Important early contributions were made by Newton (1704), ~o:ho I aid the founda t1 ons for modern work on color vision, and Helmholtz 0910), whose treatise on physiological optics maintains its interest even today. Early in this century, Wertheimer (1923) noticed the apparent motion not of individual dots but instead of wholes, or "fields," in images presented sequentially, as if in a movie. In much the same way do we perceive the migration across the sl::y of a flock of geese, the flock somehow constituting a single entity, and not individual birds. This observation started the Gestalt school of psychology, which was concerned with describing the qualities of wholes, including solidarity and distinctness, and trying to formulate the laws that governed their creation. The attempt failed for various reasons, and the Gestalt school dissolved into the fog of subjectivism. With the death of the school, many of its early and genuine insights were unfortunately lost to the mainstream of experimental psychology.

The next developments of importance were recent and technical. The advent of electrophysiology in the 1940's and 'SO's made single cell recording possible, and with Kuffler's (1953) study of retinal ganglion cells-- the neurons of the eye that give rise to the optic nerve -­ a new approach to the problem was born. Its most renowned practitioners are Hubel& Wiesel (1962, 1968), who since 1959 have conducted an influential series of Investigations on single cell responses at various points along the visual pathway In the cat and the monkey.

1. A random-dot stereogram (the top two images) and its decoding by Marr & Poggio's (1976) cooperative algorithm. The initial state contains all possible matches within a given disparity range, and the algorithm embodies the constraints of uniqueness and continuity to eliminate false targets. Shades of grey are used to signify matches at different disparities. The figure shows the initial state, and the states after 1,2,3,4,5,6,8 and 14 iterations . The algorithm progressively reveals a nested set of tiers. This algorithm is not the one used by the human visual system.

( · )

Students of the psychology of perception were also affected by a technological advance, the advent of the digital computer. Most notably, it allowed Bela Julesz in 19S9 to devise random-dot stereograms [see Julesz 1971], which are image pairs constructed of dot patterns that appear rand.om when viewed monocularly, but which fuse when viewed one through each eye to give a percept of shapes and surfaces with a clear three-dimensional structure. An example is shown in figure 1. Here the image for the left eye is a matrix of black and white squares generated at random by a computer program. The image for the right is made by copying the left image and then shifting a square-shaped regiou at its center slightly to the left, providing a new random pattern to fill in the gap that the shift must create. If each of the eyes sees only one matrix, as if they were both in the same physical place, the result is the sensation of a square floating in space. Plainly such percepts are caused solely by the stereo disparity between matching elements in the images presented to each eye.

More recently, considerable interest has been attracted by a rather different approach. In 1971, Shepard & Metzler made line 'drawings of simple objects that differed from one another either by a three-dimensional rotation, or by a rotation plus a reflection (see figure 2).

1. Some drawings similar to those used in Shepar & Meltzer's (1971) experiments on mental rotation. Those shown in (a) and (b) are identical and the relative angle between the two is 80 degrees. Those in (c) are not identical and no rotation will bring them into congruence.

They asked how long it took to decide whether two depicted objects differed by a rotation and a reflection, or merely a rotation. They found that the time taken depended on the 3-D angle of rota tion necessary to bring the two objects into correspondence. Indeed, it varied linearly lvith this angle. One is led thereby to the notion that a mental rotation of sorts is actua lly being performed: that a mental description of the first shape in a pair is bei ng adjusted incrementally in orientation unti l it matches the second, such adjustment requiri ng greater time when greater angles are involved.

Interesting and important though these findings are, one must sometimes be allowed the luxury of pausing to reflect upon the overall trends that they represent, in order to take stock of the kind of knowledge that is accessible t hrough these techniques. For we repeat: per haps the most striking feature of neurophysiology and psychophysics at present is tha t they describe the behavior of cells or of subjects, but do not explain it. \-.'hat are the visual areas of the cerebral cortex actually doi ng? What are the problems in doing it that need explaining, and at what level of desc ription should such explanations be sought?

3. A Computational Approach to Vision In trying to come to grips with these problems, our group at the ~1. I. T. Artificial Intelligence Laboratory has adopted a point of view that regards visual perception as a problem prima.rily in information processing. The problem commences with a large, gray-level intensity array, which suffices to approximate an image suc h as the world might cast upon the reti nas of the eyes, and it culminates in a descri ption that depends on that array, and on t he purpose that the viewer brings to it. Our particular concer n in this article will be with the derivation of a description well-suited for t he recognition of three-dimensional shapes.

3.1 The Primal Sl!.etch. It is a commonplace that a scene and a drawing of the scene appear very s imilar, despi tc the completely different graylevel images to which they give rise. This suggests· that the artist's symbols correspond in some way to natural symbols that are computed out of the image during the normal course of its interpretation. Our theory therefore asserts that the first operation on an image · is to transform it into a primitive but rich description of the way its intensitie! change over the visual field, as opposed to a description of its particular intensity values in and of themselves. This yields a description of markedly reduced size that still captures the important aspects required for image analysis. We call it a primal sketch (Marr 1976]. Consider, for. example, an intensity array of 1,000 by 1,000, or a million points in all. Even if the possible intensity at any one point were merely black or white -- two different brightnesses -- the number of all possible arrays would still be 21.ooo,ooo. In a real image, however, there tend to be continuities of intensity -- areas where brightness varies uniformly -- and this tends to eliminate possibilities in which the black and white oscillate ~:ildly. It also tends to simplify the array. Typically, therefore, a primal sketch need not include a set of values for every point in an image. As stored in a computer, it will Instead constitute an array with numbers representing the directions, magnitudes, and spatial extents of intensity changes assigned to certain specific points in an image -- points that tend to be places of locally high or low intensity. The positions of these points, particularly their arrangement amongst their immediate neighbors -- that is to say, the local geometry of the im,1ge -- must also be made expl lei t in the primal sketch, as it would otherwise be lost. (It was Implicit, of course, in the 1, 000-by-1, 000 array, but we are no longer retaining data for each of those million places.) One way to do this is to specify "virtual lines"-- directions and distances -- between neighboring points of interest in the sketch.

The process of computing the primal sketch involves several steps. The first is the derivation of the raro primal sl!.etch (see ~larr & Hi ldreth 1979], which involves detecting and rep resenting the intensity changes in the image. First, the image Is f!l tercd through a set of medium bandpass second differential operators \72G, (where \72 is the Laplacian and G is a Gaussian distribution), and the zero­ crossi ngs in the filtered !mages are found (see figure 3). This representation of the intens ity changes Is probably complete [Marr, Foggi o & Ullman 1979].

Although In general there Is no reason why the zero-crossings found by the different channels should be related, In practise they will be. The reason is that most intensity changes in an Image arise from physical phenomena that are spaiially localized. This constraint allowed ~larr & Hildreth to formulate the spatial coincidence assumption which states: If a zero­ crossing is present in a set of independent v2G channels over a contiguous range of sizes, and it has the same position and orientation in each channel, then the set of such zero­ crossings may be taken to Indicate the presence of an Intensity change in the Image that is due to a single physical phenomenon <a change In reflectance, Illumination, depth or surface orientation).

This assumption allows one to combine the zero­ crossings from different channels into edge­ segment descriptors, bars and blobs (see figure 4b), which constitute the raw primal sketch. To obtain the full primal sketch, these primitive elements are grouped, perhaps hierarchically, into units called place-tokens, which associate properties 1 ike length, width, brightness and so forth with positions in the image !Marr 1976]. VIrtual lines may then be used to represent the local geometry of these place tokens (see figure 4c and Stevens 1978).

Recently, Marr & Ullman (1979) hav~ extended the work of Marr & Hildreth to Include the detection and use of directional selectivity. They have proposed specific roles for the X­ and Y-channels found originally by Enroth­ Cugell & Robson (1966), and in an explicit model for one class of cortical simple cell, they showed how to combine X and Y information to form a directionally selective unit.

3. 2 nodules of Earll/ Visual rroceuing. The primal sketch of an Image Is typically a large and unwieldy collection of data, even despite Its simplification relative to a gray-level array; for this Is the unavoidable consequence of the irregularity and complexity of natural Images. The next computational problem is thus Its decoding. Now the traditional approach to machine vision assumes that the essence of such a decoding is a process called segmentation, whose purpose Is to divide a primal sketch, or more generally an image, into regions that are meaningful, perhaps as physical objects. Tenenbaum & Barrow (1976), for example, applied knowledge about several different types of scene to the segmentation of images of landscapes, an office, a room, and a compressor. Freuder (1974) used a similar approach to identify a hammer in a simple scene. Upon finding a blob, his computer program would tentatively label it as the head of a hammer, and begtn 'a search for confirmation in the form of an appended shaft. If thl s approach were correct, 1 t would mean that a central problem for vision is arranging for the right piece of specialized knowledge to be made available at the appropriate time in the segmentation of an image. Freuder' s work, for example, was almost entirely devoted to the design of a system that made this possible. But despite considerable efforts over a long period, the theory and practice of segmentation remain rather primitive, and here again we believe that the main reason lies in the failure to formulate precisely the goals of this stage of the processing -- a failure, in other words, to work at the topmost level of visual theory. What, for example, is an object? Is a head an object? Is it still an object if it is attached to a body? What about a man on horseback?

Marr 11978) argued that the early stages of visual information processing ought instead to squeeze the last possible ounce of information from an image before taking recourse to the descending influence of "high-level" knowledge about objects in the world. Let us turn, then, to a brief examination of the physics of the situation. As we noted earlier, the visual process begins with arrays of intensities projected upon the retinas of the eyes. The principal factors that determine these intensities are (1) the illumlnant, (2) the surface reflectance properties of the objects viewed, (3) the shapes of the visible surfaces of these objects, and (4) the vantage point of the viewer. Thus if the analysis of the input Intensity arrays is to operate autonomously, at least in its early stages, it can only be expected to extract information about these four factors. In short, earl-y visual processing must be limited to the recovery of localized physical properties of the visible surfaces of a viewed object -- particularly local surface dispositions (orientation and depth) and surface material properties (color, texture, shininess, and so on). More abstract matters such as a description of overall three­ dimensional shape must come after this more basi c analysis is complete.

An example of early processing is stereopsis. Imagi ne that images of a scene are available from two nearby points at the same horizontal leve l -- - the analog of the images that play upon the retinas of your left and right eyes. The images are somewhat different, of course, in consequence of the slight difference in vantage. Imagine further that a particular locat ion on a surface in the scene is chosen from one image; that the corresponding loca tion is identified in the other image; and that the relative positions of the two versions of t hat location are measured. This information will suffice for the calculation of depth-­ the di s tance of that location from the viewer . Koti ce that methods based on gray-level corre lation between the pair of images fail to be suitable because a me~e grey-level measurement does not reliably define a point on a phy sical surface. To put the matter plainly, nume rous points in a surface might fortuitously be t he same shade of gray, and differences in the vantage points of the observer's eyes could change the shade as well. The matching must ev idently be based instead on objective mark ings that lie upon the surface, and so one has t o use changes in reflectance. One way of do ing t his is to obtain a primitive description of t he intensity changes that exist in each image <such as a primal sketch), and then to match t hese descriptions. After all, the line segment s, edge scp,ments, blobs, and edge termina tion points included in such a desc ri ption correspond quite closely to bounda r i es and reflectance changes on physical sur fac es. The stereo problem -- the determination of depth given a stereo pair 6f Images -- may thus be reduted to that of miltch ing two primitive descriptions, one from each eye; and to help in this task there are physical constraints that translate into two rules for how the left and right descriptions are combined:

Uniqueness . Each i tcm from each image may be assigned at most one disparity value -- that is to say, a unique position relative to its counte rpart in the stereo pair. This condition rests on the premise that the items to be matched have a physical existence, and can be in on ly one place at a time.

Continuity. Disparity varies smoothly almost eve ry\\·here. This condition is a consequence of the cohes i veness of matter, and it states tha t on ly a relatively small fraction of the area of an image is composed of discontinuities in dept h.

In the case of random-dot stereograms, the computati onal problem is rather well-defin~d, essent ial l y because of Julesz's demonstra t 1on that random-dot stereograms, containing no monocular information, still yield stereopsis. In 1976, Marr & Poggio developed a method for computing local disparities in a pair of random-dot stereograms by an iterative, parallel procedure known technically as a cooperative algorithm (see figure 1, and Marr, Poggio & Palm 1977). This sort of algorithm ha s the property that it can be defined completely in terms of simple local interactions because at each of its Iterations, each point is affected only by a calculation performed on its immediate neighborhood. Yet all points are so affected during each successive iteration, so the transformations take on a complex global nature. Subsequent comparison of the algorithm's performance with psychophysical data showed that It did not hold up "'ell as a model for human stereopsis. To be sure, it performed better than people do on the s tandard stereograms like that shown In figure 1; but it did not explain people's ability to see stereograms in which one of the two images is defocused slightly or enlarged slightly relative to the other. These observations led Marr & Poggio (1979) to devise anot~er algorithm, this one based on the human use of spatial-frequency-tuned channels and vergence eye movements. This algorithm is consistent wi th all of the currently known psychophysical cia ta.

A second example of early visual processing concerns the derivation of structure from motion. It has long been known that as an object moves relative to the viewer, \he way its appearance changes provides information that we can use to determine its shape (Wallach & o' Connell 1953). The motion analog of a random-dot stereogram is illustrated in figure 5, and as expected, humans can easily perceive shape from a succession of frames, each of which on its own is merely a set of random­ dots. In various papers and a forthcoming book on the subject, Ullman (1979a & b) decomposed the problem into two parts: matching the elements that occur in consecutive images; and deriving shape information from measurements of their changes in position. Ullman then showed that these problems can be solved mathematically. His basic idea is that in general, nothing can be inferred about 'the shape of an object given only a set of sequential views of it; for some extra assumptions have to be made. Accordingly, he formulntes an assumption of rigidity, which states that if a set of moving points has a unique interpretation as a rigid body in motion, that interpretation is correct. (The assumption is based on a theorem which he proves, stating that three distinct views of four noncoplanar points on a rigid body are sufficient to determine uniquely their three­ dimensional arrangement in space.) From this he derives a method for computing structure from motion. The method gives results that are quantitatively superior to the ability of humans to determine shape from motion, and which fail in qualitatively similar circumstances. Ullman has also devised a set of simple algorithms by which the method may be implemented.

3. 3 The 2.}-Dimensional Sk.etch. Both of the

techniques of image analysis discussed in the preceding paragraphs provide information about the relative distances to various places in an image. In the case of stereopsis, it is the matching of points in a stereo pair that leads to such info rmation. In the case of structure from motion, it is the matching of points in successive images. ~lore generally, however, we ~now that vision provides several sources of information about shapes in the visual world. the most direct, perhaps, are the aforementioned stereo and motion, but texture gradients in a single image are nearly as effective. Furthermore, the theatrical techniques of facial make-up reveal the ~ ensiti vity of perceived shapes to S'hading (see i orn 1975), and color sometimes suggests the anner in which a surface reflects light. It often happens that some parts of a scene are onP.n to inspection bv some of these techniques,

111d other parts to inspection by others. Yet different as the techniques are, they all have tWO important characteristics in common: they rely on information from the image rather than a priori knowledge about the shapes of the v1ewed objects; and the information they specify concerns the depth or surface orientation at arbitrary points in an image, r~ther than the depth or orientation associated Wlth particular objects (see Table 1);

Table 1

The form in which various early visual processes de­ liver information about the changes in a scene.

r = depth

ljr = small, local changes in depth

~r = large changes in depth

~ ~ local surface orientation

In order to make the most efficient use of di fferent and often complementary channels of in formation deriving from stereopsis, from moti on, from contours, from texture, from co lor, from shading, they need to be combined in some way. The computational question that now arises is thus how best to do this, and t~e natural ans~er is to seek some representation of the visual scene that makes explicit just the information these processes can deliver. \ve seek, in other words, a r~pre scntation of surfaces in an image that makes explicit their shapes and orientations, m~c h as the Arabic representation of a number makes explicit its composition by powers of t~n. It might be contrasted with the rtpresentation of a surface as a mathematical expression, in which the orientation is only implicit, and not at all apparent. We call such a representation the 2~-dimensional sketch <Marr & Nishihara 1978; Marr 1978), and in the particular candidate for it shown in figure 6, surface orientation is represented by covering an image with needles. The length of each needle defines the dip of the surface at that point; so that zero length corresponds to a surface that is perpendicular to the vector from the viewer to the point, and increasing lengths denote surfaces that tilt increasingly away from the viewer. The orientation of each needle defines the local ~irection of dip.

Our argument is that the 2!-D sketch is useful 2 because it makes explicit information about the image in a form that is closely matched to what I mage analysis can deliver. To put it another way, we can formulate the goals of this stage of visual processing as being primarily the construction of this representation, discovering, for example, what are the surface orientations in a scene, which of the contours in the primal sketch correspond to surface discontinuities and should therefore be represented in the 2!-D sketch, and which 2 contours are missing in the primal sketch and need to be inserted Into the 2~-D sketch In order to bring It Into a state that is consistent with the nature of three-dimensional space. This formulation avoids the difficulties associated with the terms "region" and "object" -- the difficulties inherent in the i m,,ge segmentation approach; for the gray level intensity array, the primal sketch, the variou ~. modules of early visual processing, and finally the 2~-dlmensional sketch itself deal only with discovering the properties of surfaces In an image. One Is pleased about that, for we know of ourselves as perceivers that surface orientation can be associated with unfami 1 iar shapes, so its representation probably precedes the decomposition of the scene into objects. One fs thus free to ask precise questions about the computational structure of the 2~-D sketch and of processes to create and maintain it. We are currently much occupied with these matters.

4. Later Processing Problems.

The final components of our visual processing theory concern the application of visually derived surface information for the representation of three-dimensional shapes in a way that is suitable specifically for recognition (~larr & Nishihara 1978). By this we mean the ability to recognize a shape a~ being the same as a shape seen earlier, and this in essence depends on being able to describe shape s consistently each time they are seen,

whatever the circumstances of their positions relative to the viewer. The problem with local surface representations such as the 2~-D sketch is ·that the description depends as much on the viewpoint of the observer as it does on the structure of the shape. In order to factor out a description of a shape that depends on its structure alone, the representation must be based on readily Identifiable geometric features of the overall shape, and the dispositions of these features must be specified relative to the shape in itself. In brief, the coordinate system must be "object­ centered," not "viewer-centered." One aspect of this deals with the nature of the representation scheme that is to be used, and another with how to obtain it from the 2~-D sketch. \,'e begin by discussing the first, and will then move on to the second.

4. 1 The 3-0 Model Representation. The most basic geometric properties of the volume occupied by a shape are (1) its average location (or center of mass); (2) its overall size, as exemplified, for example, by its mean diameter or volume; and (3) its principal axis of elongation or symmetry, if one exists. A description based on these qualities would certainly be inadequate for an application such as shape recognition; after all, one can tell little abo1,1t the three­ dimensional structure of a shape given only its position, size, and orientation. But if a shape itself has a natural decomposition into components that can be so described, this volumetric scheme is an effective means for describing the relative spatial arrangement of those components. The illustration of figure 7 shows a familiar version of this type of description, the stick figure (see Blum 1973) . The recognizability of the animal shapes depicted in the illustration is surprising considering the simplicity of representation used to describe them.

The reason such a description works so well lies, ~>.·e think, in (1) the volumetric (as opposed to surface-based) definition of the primitive elements -- the sticks-- used by the representation; (2) the relatively small number of elements used; and (J) the relation of elements to each other rather than to the vieNer. In short, this type of shape representation is volumetric, modular, and can be based on object-centered coordinates. The figure 8 Illustrates the scheme of representation that was developed from these ideas. Here the description of a shape is composed of a hierarchy of stick-figure specifications we call 3-D models. In the simplest, a single axis element is used to specify the location, size, and orientation of the entire shape; the human body displayed in the Illustration will serve as an instance. This element is also used to define a coordinate system that will specify the dispositions of subsidiary axes, each of these specifying in turn a coordinate system for 3-D models of "arm," "hand," and so on. This hierarchical structure makes it possible to treat any component of a shape as a shape in itself. It also provides flexibility In the detail of a description.

1. The arrangement of 3-n models into the representation of a human shape. First the overall form thevbody'~- is given an axis. This yields an object-centred coordinate system which can then be be used to specify the arrangement of the "arms~" "legs," "torso," and "head." The position of each of these is specified by an axis of its own, which in turn serves to define a coordinate system for specifying the arrangement of further Rubsidiary parts. This gives a hierarchy of 3-n models, shown here extending downwards as if they were cylindrical, but that is purely for illustrative convenience. (From Marr & Nishihara, 1978 figure 3).
2. The definition of a generalized cone. It is the surface created by moving a cross-section along a given straight axis. The cross-section may vary smoothly in size, but its shape remains constant. Several examples are shown here. In each, the cross-section is shown at several positions along the trajectory that spins out the construction.

4. 1. 1 Shape.s Admitting 3-0 l'lodel Oe.scription.s. If the scheme for a given shape is to be uniquely defined and stable over unimportant variations such as viewpoint -- lf, in a word It Is to be canonical -- its definition must take advantage of any salient geometrical characteristics that the shape inherently possesses. If a shape has natural axes, then those should be used. The coordinate system for a sausage should take advantage of Its major axis, and for a face, of its axis of symmetry.

Highly symmetrical objects, like a sphere, a square, or a circular disc, will inevitably lead to ambiguities In the choice of coordinate systems. For a shape as regular as a sphere this poses no great problem, because its description in all reasonable systems is the same. One can even allow other factors, like the direction of motion or spin, to influence the choice of coordinate frame. For other shapes, the existence of more than one possible choice probably means that one has to represent the object in several ways, but this is acceptable provided that their number is small. For example, there are four possible axes on which one might wish to base the coordinate system for representing a door, namely the midlines along its length, its width, and Its thickness, and also the axis of its hinges. (This last would be especially useful to represent how the door opens.) For a typewriter, there are two reasonable choices, an axis parallel to its width, because that is usual ly its largest dimension, and the axis about which a typewriter is roughly symmetrical.

In general, if an axis can be distinguished in a shape, it can be used as the basis for a local coordinate system. One approach to the ~roblem of defining object-centered coordinates 1s therefore to examine the class of shapes having an axis as an integral part of their structure. Consider, accordingly, the class of so-called generalized cone.s, each of these being the surface swept out by moving a cross-section of constant shape but smoothly varying size along an axis, as shown in figure 9. Binford (197 1) has drawn attention to this class of constructions, suggesting that It might provide a convenient way of describing three­ dimensional surfaces for the purposes of computer vision (see also Agin 1972, Nevatia 1974). ll'e regard it as an important class not because the shapes themselves are easily de sc r i babl e, but because the presence of an axis allows one to define a canonical local coordinate system. Fortunately, many objects, especi ally those whose shape was achieved by growt h, are described quite naturally in terms of one or more generalized cones. The animal

~hapes of figure 7 provide some examples; the lndividual sticks are simply the axes of generalized cones that approximate the shapes of parts of these creatures. Many artifacts can also be described in this way-- say a car <a.small box sitting atop a longer one) or a bu1ldlng (a box with a vertical axis).

It Is important to remember, however, that there exist surfaces that cannoc conveniently be approximated by generalized cones, for example a cake that has been transected at some arbitrary plane, or the surface formed by a crumpled newspaper. Cases 11 ke the cake could be dealt with by introducing a suitable surface primitive for describing the plane of the cut, In much the same way as an axis in the 3-D model representation is a primitive that describes a volumetric element. But the crumpled news~aper poses apparently Intractable problems.

4. 2 finding the Natural Coordinate Sv.stem. Even If a shape possesses a canonical coordinate frame, one still Is faced with the problem of finding it from an image. Our own Interest in this problem grew from the question of how to interpret the outline.s of objects as seen In a two-dimensional Image (Marr 1977b), and our start ing point was the observation that when one looks at the silhouettes In Picasso's "Rites of Spring" <reproduced here in figure 10), one perceives them in terms of very parti cular three-dimensional shapes, some familiar, some less so. This is quite remarkable, because the silhouettes could in theory have been generated by an infinite variety of three-dimensional shapes which, from other viewpoints, would have no discernible similarities to the shapes we perceive. One can perhaps attribute part of the phenomenon to a familiarity with the depleted shapes, but not all of It, because one can use the medium of a silhouette to convey a new shape, and because even with considerable effort it is difficult to imagine the more bizarre three-dimensional surfaces that could have given rise to the same si 1 houettes. The paradox, then, Is that the bounding contours In Picasso's "Rites" apparently tell us more than they should about the shape of the figures. For example, neighboring points on such a contour could in genera l arise from widely separated points on the original surface, but our perceptual Inte rpretation usually Ignores this posslbili ty.

The first observation to be made is that the contours that bound these silhouettes are contours of surface discontinuity, which are preci sely the contours wl th which the 2 '-D sketch is concerned. Secondly, because~we can interpret the silhouettes as three-dimensional shapes, then imp! lei t in the way we interpret them must lie some a priori assumptions that allow us to infer a shape from an outline. If a surface violates these assumptions, our analysis will be wrong, In the sense that the shape we assign to the contours will differ from the shape that actually caused them. An everyday example is the shadowgraph, where the appropriate arrangement of one's hands can, to the su rprise and delight of a child, produce the shadow of a cluck or a rabbit.

\\hat assumptions is it reasonable to :;uppose that we make? In order to explain them, we need to define the four constructions that appear in figur e 11. The se are (1) a three-dimensional surface ,;; (2) its image or silhouette sv as seen from a viewpoint V; (3) the bounding conto~r cv of s~ and 14) the set of points on the sur face r that project onto the contour Cv. h'e shall call this last the contour generator of cv, and we shall denote it by rv.

Observe that the contour Cv, 1 ike the contours in the work of Picasso, imparts very little information about the three-dimensional surface that caused it. Indeed, the only obvious feature available in the contour is the distinction between convex and concave places -- that is to say, the presence of inflection points. In order that these inflections be "reliable," one needs to make some assumptions about the way the contour was generated, and we choose the following restrictions [Marr 1977):

1. Each point on the contour generator rv projects to a different point on the contour cv.
2. 2 . Nea rby points on the contour cv arise from nearby points on the contour generator rv. 3. The contour generator rv lies wholly in a single plane.

The first and second restrictions say that each point on the contour of the image comes from one point on the surface (which is an

assumption that facilitates the analysis but is not of fundame~tal importance), and that where the surface looks continuous in the image, it really is continuous in three dimensions. The third restriction is simply the demand th·t the cllffcrcnce between convex and concave contour segments reflects properties of the surface, rather than of the imaging process.

It turns out to be a theorem that if the surface 1 s smooth (for our purposes, 1 f it 1 s twice differentiable with continuous second deri vati vel and if restrictions 1 through 3 hold for all distant viewing positions in any one plane (as illustrated in figure 11), then the viewed surface is a generalized cone. (The converse is also true: if the surface is a generalized cone, then conditions 1 through 3 will he found to be true).

This means that if the convexities and concavities of a bounding contour in an image are actual properties of a surface, then that surface is a generalited cone or is composed of several such cones. In brief, the theorem says that a natural link exists between generalized cones and the imaging process itself. The combination of these two must mean, we think, that generalized cones will play an intimate role in the development of vision theory. ·

10. "Rites of Spring" by Pablo Picasso. We immediately interpret such silhouettes in terms of particular three-dimensional surfaces -- this despite the paucity of information in the image itself. In order to do this, we plainly must invoke certain a priori assumptions and constrainsts about the-;;ture of shapes.

S. Discussion.

~e have tried in this survey of visual information processing to make two principal points. The first is methodol og leal: nnel y that it 1s important to be very clear about the nature of the understanding we seek. The results we try to achieve should be precise ones, at the level of what we call a computational theory. The critical act in formulating computational theories turns out to be the discovery of valid constraints on the way the world is structured -- constraints that provide sufficient information to· allow the processing to succeed. Consider stereopsis, which presupposes continuity and uniqueness in the world, or structure from visual motion, which presupposes rigidity, or shape froa contour, which presupposes the three restrictions just discussed, or even edge detection, which presupposes the assumption of spatial coincidence. The discovery of constraints that are valid and universal leads to results about vision that have the same quality of permanence as results in other branches of science.

The second point is that the·critical issues for vision seem to us to revolve around the nature of the representations and the nature

of the processes that create, maintain, and eventually interpret them. We have suggested an overall framework for visual information processing (summarized in table 2), that includes three categories of representation upon which the processing is to operate. The first ~ncompasses representations of intensity variations and their local geometry in the input to the visual system. One among these, the primal sketch, is expressly intended to be an efficient description of these variations which captures just that information required by the image analysis to follow. The second· category encompasses the representations of visible surfaces -- the descriptions, in other words, of the physical properties of the surfaces that caused the images in the first place. The nature of these representations -­ the 2{-dimensional sketch in particular --

is determined primarily by what information can be extracted by modules of image analysis such as stereopsis and structure from motion. Like the primal sketch of the previous category, the 2-i-dimensional sketch is intended to be a

final or output representation: this is where the separate contributions from the various image-analysis modules can be combined into a unified description. The third category encompasses all representations which are subsequently constructed from information contained in the 2-i-D sketch. The designs of these tertiary representations are determined largely by the use to which they are to be put, as was tne case for the 3-D model representation, to be used for shape recognition. If one had wanted instead, for example, to reprcseht a shape simply for later reproduction, say by the milling of a block of metal, then the 2-i-D sketch would itself have been sufficient,as the milling process depends explicitly on information about local depth and orientation, such as that sketch can provide.

Finally, a remark of a rather different nature. As we have seen, some aspects of human earl y visual processing, like stereopsis, have apparently been understood well enough to implement them in mac.hines !Marr & Poggio 1979, Marr & Grimson 1979]. The computational power required by these early proceses is prohibitive, and until recently the prospects for real-time implementation of human-like early vision were remote. It now appears, however, that the emerging VLSI and CCO technologies will be able to supply the necessary processing power. This could make the next two decades very interesting.

Table 2

A frarrework for the derivation of shape infonnation fran images.

ACKWOW~ED�EHENTS: I than~ Keith Nishihara and ~ichac l Fciertag for help in assembling this surrf')". I thank the Royal Society for permi ss ion to reproduce figures 3, 4, 6, 7, and 8, ilncl the ~1. I. T. press for figure 5.