Source: Minsky, M., & Papert, S. (1969). 1968–1969 Progress Report (MIT Artificial Intelligence Laboratory Artificial Intelligence Memo, Issue.
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
ARTIFICIAL INTELLIGENCE MEMO NO. 200
1968–1969 Progress Report
Marvin Minsky and Seymour Papert
545 Technology Square, Cambridge, Massachusetts 02139
| This report mainly summarizes the Project MAC A. I. Group work between July 1968 and June 1969 but covers some work up to February 1970. The work on computer vision is described in detail. This summary should be read in conjunction with last year’s A. I. Group Report which is included at the end of this Memo. |
ARTIFICIAL INTELLIGENCE GROUP PERSONNEL
Prof. M. L. Minsky, Prof. S. A. Papert, G. K. Adler, M. D. Beeler, W. T. Beyer, T. O. Binford, Prof. M. Blum, H. E. Brammer, T. F. Callahan, E. Charniak, P. E. deCoriolis, W. Diffie, D. E. Eastlake, H. Fell, J. S. Freiberg, S. L. Geffner, J. P. Golden, R. W. Gosper, R. D. Greenblatt, J.-Y. Gresser, A. K. Griffith, Prof. A. Guzman, W. H. Henneman, A. Herskovits, C. E. Hewitt, J. T. Holloway, P. Holloway, B. K. P. Horn, K. M. Jacobs, J. L. Jaroslav, T. L. Jones, E. I. Kampits, T. F. Knight, L. J. Krakauer, Prof. W. A. Martin, G. H. H. Mitchell, Prof. J. Moses, R. Noftsker, R. Orban, D. N. Perkins, Jr., J. S. Roe, P. R. Samson, R. C. Schroeppel, J. M. Shah, S. W. Smoliar, M. Speciner, W. A. Spies, N. F. Stone, G. J. Sussman, C. T. Waldrop, D. L. Waltz, J. C. Wentzell, J. L. White, P. H. Winston, T. A. Winograd.
Guests: Prof. C. K. Chow, T. G. Evans, Prof. E. Fredkin, Prof. H. N. Mahabala, Prof. M. S. Paterson, G. Voyat.
1968–1969 PROGRESS REPORT
This report should be read in conjunction with last year’s.* This is particularly important to obtain a rounded view of our work on vision. In fact, much of what we say this year is logically prior to much that we said last year. Thus last year we discussed the abstract and theoretical problems related to the interpretation of pictures presented in a clean form (as line drawings or as subsets of an abstract retina) while this year we say more about how to obtain such pictures from the real world. The reason of course lies in the fact that the “higher level” work did not depend as heavily on prior solutions of hardware and systems problems.
We have not reported new work that lies directly in the line of development of ideas discussed last year. In particular, we have deepened and generalized some of the theorems on computational geometry. But the new state of knowledge is indistinguishable from the old on the level of discussion of this kind of report. Similarly we have not reported very new work which is still at a too primitive level of development to be presented intelligibly. This includes work on natural language processing, concept information, teaching and a number of mathematical topics. The time constant for a project of this sort is longer than a year. These matters will be dealt with in a further report due in the Fall of 1970.
Analysis of Visual Scenes: The Concept of Vertical Problem-Solving
One can use vision in many ways to find out about objects in space. Let us begin with some of the simplest ideas, and then move on to the deeper problems. If the camera can move, one could use stereoscopic correlations of two pictures. Or one might use local operations to measure motion parallax. These do not solve all problems. Stereoscopy does not work well on featureless surfaces or curved boundaries; motion effects are misleading on plain or shiny objects. Nevertheless, both methods can help find the three-dimensional locations of parts of visual objects.
Focusing provides a third method of location. Its distinctive feature is that it needs only a single eye in a fixed location, provided that the eye has a wide enough optic aperture. For then the idea of measuring distance by stereoscopic parallax merges with that of measuring distance by finding the best focus setting. Berthold K. P. Horn has developed a program that can find the lens setting for best focus at each point in the visual field. The procedure, applied to a series of points along a horizontal scan through the middle of a cube, yields a profile. Horn’s program uses local Fourier transforms and compares the relative energy in the high and low spatial frequencies. It servo-controls the lens to maximize the highs, and it focuses at least as well as one can do manually.
Horn will discuss the focusing procedure in detail in his thesis “Shape from Shading: A Method for Finding the Shape of a Smooth, Opaque Object from One View”. Two techniques are available: one uses a fast circular scan to obtain a periodic function characteristic of a large neighborhood; the other makes a faster scan of a smaller square. An operation manual (Horn, “Focusing”, A.I. Memo 160) gives instructions for using the system with the PDP-6 computer and its optical-mechanical accessories, as well as some of the theory of the focusing procedure.
Now we have described three methods for optical range-finding. There are many other ways to attack just this one aspect of visual technology such as flying-spot scanning from a site off-center from the camera, holographic methods, and even optical radar. We must not, however, allow the myriad of technological possibilities to divert us from the deeper and incompletely understood problem of developing a visual system flexible enough to deal with real-world problems. The goal we have set ourselves is to find how to make a system that can approach the versatility of human vision.
One outstanding feature of that system is its “passiveness”—the great extent to which it can see without much special preparation or interaction with the objects in the scene. The secret lies in the intelligent viewer’s ability to combine what he sees with what he knows about his world.
To pursue this, we have concentrated on the problem of reconstructing a three-dimensional structure using only a single monocular picture. People are quite good at understanding what is shown in a photograph; we should like to know how to make a machine do this.
Now, with a very few exceptions, the many past attempts at computer analysis of scenes have been rather fruitless, and we should try to understand what went wrong. Almost all of those past attempts followed the same general plan: the picture is subjected to a sequence of transformations; each transformation is intended, in turn, to produce a successively more abstract representation until, finally, one obtains the desired description of the scene. Typically, such a sequence might be:
1. Remove noise (by clipping, smoothing, etc.);
2. Enhance features (by boosting gradients, etc.);
3. Extract features (finding edges, vertices, etc.);
4. Group features into objects (by regions, parallelisms, etc.);
5. Identify objects (by partial matches, etc.).
Although there is a great deal of plausibility to this idea of progressing relentlessly from local to global, the concept of serial stages of pre-processing does not actually work well in practice. It is simply not suited to the real problem. Errors and assumptions made at each level are passed on to the next, and even if each is quite clever at how it handles its data, the accumulation of mistakes over many stages leads to chaotic over-all results. The basic grammar of the problem is too context-dependent. The appearance of an object’s features (and even their occurrence or non-occurrence) usually depends on global aspects of the arrangement and illumination of the scene. One must cope, for example, with:
• Direct line-of-sight occlusion of parts of objects,
• Shadow occlusions that depend on the directions of lighting,
• Highlights,
• Reflections,
• Textures,
• Decorations,
• Many other interactions between visual features and spatial forms.
Accordingly, the inevitable ambiguity problems met at each level—”Is this an edge or not?” or “Are these two features part of the same object?”—are often not solvable at that level. One can select a plausible interpretation only by using a wider variety of knowledge about the real world—knowledge that ranges from principles of optics and geometry to knowledge about the particular environment and the objects likely to be in it.
In the traditional processing sequence outlined above—we shall call it the horizontal vision system—different kinds of knowledge are implicit at each level. The principles of optics are involved because each visual point represents a distribution function of space points in a way that depends on focus, scattering, reflection and noise. In the extraction of features, the processor must know whether the objects are likely to have straight edges, or texture boundaries, or polished surfaces. In analyzing a room, to give an extreme but real example, imagine the resulting chaos if the system did not know the significance of a picture frame!
At the level of grouping features and identifying spatial bodies, we have already seen how problems of projections and occlusion of three-dimensional objects lead us away from the simple template-matching schemes that work fairly well for two-dimensional problems. We found, however, that many of these difficulties could be handled by symbolic-description systems, and we shall assume that the reader is familiar with Prof. Adolfo Guzman’s work. We now conclude that the lower-level aspects of vision, too, are best treated as problems in artificial intelligence to be handled by a mixture of general methods and special knowledge. Because the different kinds of knowledge interact at different levels, we must provide channels for such interactions so that hypotheses about high-level things like objects—perhaps proposed by heuristics that use local evidence—can be confirmed, rejected or revised by returning to other levels for other kinds of evidence. We use the term vertical system for this type of organization.
We have not yet enough experience with verticality to discuss it abstractly. But we now know a substantial amount about its application to visual problems; the body of this section reports what we have found so far.
Optical Anatomy of a Simple Scene
The data and methods used here are from work by Arnold K. Griffith. Typical features of light intensity profiles across visual scenes include:
a: an outer edge. Against the dark background, it is a simple, sudden change in intensity, giving a typical “bipolar” pulse in the smoothed second derivative.
b: a more symmetrical feature; it is due to the “highlight” reflection on the front edge of a cube.
b’: a superposition of the effects of a b and a small a.
c: the reflection of the bright surface of an upper cube in the top of a lower right cube. Although the paint there is dull, this surface is seen at a low angle, and this enhances reflections.
d: the crack between lower cubes. The brightness measurements are logarithmic and truncated so that plots won’t overlap.
e: the spot of dirt on an upper front corner of a cube. The edges and corners of objects often have highlights and often are dirty.
f: a shadow boundary visible on the dark background.
f’: another shadow boundary, somewhat less sharp because of penumbra and depth of focus.
The internal edges often give small signals. Their width is an illusion due to the smoothing operation; on sharp corners, the highlight line is very narrow and easily missed by a coarse scan.
Annette Herskovits (AI Memo 183) and Griffith made separate studies of the edges of geometrical objects; both concluded that the most common phenomena were superpositions of three effects: (1) a simple step, (2) a slope change, and (3) a highlight or a crack. They both investigated various detection filter methods for these. Griffith’s thesis will include a theory of optical detection of edges under various assumptions about their intrinsic character and about the kinds of noise one might expect in a vision system.
Another kind of process works in a complementary manner; it labels points whose neighborhoods are relatively homogeneous. Then the system finds the boundaries of the connected regions of such points. Thomas O. Binford (AI Memo 182) describes experiments on such a system. There are many problems in deciding how to reduce the region boundaries to useful line-descriptions.
Still another approach to line-finding uses a two-dimensional local-gradient detector, followed by a scheme for assigning the locally maximal features to edges, as in the early work of L. G. Roberts. Richard D. Greenblatt is developing a system of this sort.
Problems exist at every stage of such processes. At each level, the selection of relevant features requires some a priori knowledge about the local world. Our verticality thesis holds that one cannot expect any one decision policy to work over a very wide range of situations, but that even a little feedback in this selection will help considerably. For example, each of the systems mentioned above will miss some edges of some objects, because of the problems of resolution, illumination, focus, contrast, texture or noise. If the system misses an interior edge, the SEE program may have to propose one object in place of two, or two objects in place of one.
Assuming we are in a world of geometrical bodies, there is a variety of ways in which to use knowledge of the fact to propose corrections. Missed edges, for example, are often related to concavity, and, in a rather Bayesian way, this suggests a search for missed lines radiating from the concave vertices into the figure’s interior: proposed lines of several kinds include v (directly to other vertices), E (interior extensions of the vertex’s edges), and L (an absolute vertical edge, very common in real interior scenes). One might further propose parallels and lines that make confocal triplets.
In the case of structures made entirely of rectangular solids, Prof. Manuel Blum showed that a remarkable number of interior edges can be reconstructed just from the outer profile of the scene.
The number of lines proposed by such a scheme can be held to the order of tens, rather than of thousands. And the cost of verifying the existence of an edge with a specified location is enormously smaller than that of finding all such features independently. The use of proposer-verifier system can thus reduce the total picture-processing effort by relaxing the tolerances on the early, brute-force, feature-finding stages. In his forthcoming thesis, Griffith will give details of a complete system, already working, that does this.
By using a priori information, one can often get much more out of a picture than might seem to be in it. Assuming (correctly) that a sphere is uniformly colored and that the light comes from a compact source, one of Horn’s programs is able to reconstruct the surface by solving the appropriate differential equations. The method is quite complementary to stereoscopy since it relies on uniformity of surface, whereas stereoscopy and focusing need inhomogeneous surface detail or discontinuities.
Lawrence J. Krakauer is developing a system that analyzes scenes such as a bowl of fruit. The process begins by locating and analyzing illumination maxima; it appears that, from their intensity-shape behavior one can, in many cases, distinguish dull from shiny surfaces. Local maxima connected by an illuminated band are likely to be on the same object. Krakauer’s goal is to discover visual characteristics of surface properties, and to establish heuristics for grouping “non-geometric” features into natural objects.
The Vision System
Guzman’s SEE program assumes a scene description in terms of edges, vertices and regions, and produces a proposed assignment of these features to a set of three-dimensional bodies. Guzman’s thesis describes in detail a more advanced version of that project. It includes additional heuristics for linking parts of objects, analysis of the system’s behavior, discussion of and heuristics for correction of mistakes because of pre-processor errors, and some analysis of the system errors due to inherent ambiguities in ordinary scenes.
Guzman’s thesis also includes some observations about the problem of matching features between stereo pairs. In any stereo pair, one can dissect the two pictures into sets of matching line-pairs, defined by the planes through the two eye-points. Any physical object visible to both eyes will be sandwiched between the same highest and lowest such lines. For two different objects, it is unlikely this will be true by coincidence, especially if the objects have more than one visible face! Thus, once enough point features are identified in the monocular pictures, one will have little difficulty in matching them between the pictures, and expensive cross-correlations should be unnecessary.
In another attack on stereoscopic vision, David N. Perkins, Jr. is developing a system that compares two views and produces depth information. His matching procedure is complicated by the requirement that it be tolerant of the many kinds of errors that pre-processors are likely to make. It proceeds by matching vertices and arcs topologically, with some geometric constraints, and with a back-up and search procedure for finding maximal matches of substructures when there are possible local ambiguities. Given the best topological match, the program proceeds to analyze the arcs that are thus proposed for matching to obtain space curves.
We now have a complete horizontal system of programs connecting Binford’s topological pre-processor with Guzman’s SEE program and on through to Patrick Winston’s new system that recognizes some particular types of objects—e.g., wedges, pyramids, and rectangular blocks—and learns to identify some multi-object structure such as rows, towers and bridges.
Professor Hosakere N. V. Mahabala developed the TOPOLOGIST-to-SEE interface. This program, SETUP (“Pre-processor for Programs Which Recognize Scenes”, A.I. Memo 177), gobbles a list of line segments and produces a complete topological description of the graph formed by the lines. SETUP contains heuristics for plausible guesses about line locations and connections. All lines are treated as enclosed within strips of a certain width, and all problems about closure, intersection, containment, colinearity, etc., are resolved by procedures that are based on a single predicate about the orientation of a point with respect to one of these half-line strips.
Richard Orban has developed a new program, ERASER, which detects and removes shadow boundaries from geometrical scenes. ERASER resembles SEE in that it uses the same classification of vertex features, but it also uses information about the relative brightness of regions. Its heuristics are based largely on the abundance of L, T and X types of vertices on the boundaries of shadow regions. ERASER is designed to criticize the output of SETUP, to remove shadow boundaries, and then to re-submit the result to SETUP before passing the problem on to SEE.
Mechanical Structure Analysis of Visual Scenes
Blum and Griffith have written a program that can analyze the stability of the three-dimensional structure of rectangular blocks. The program uses this analysis in a planning scheme to propose the order in which the structure is to be built.
Winston is completing a program that learns to recognize types of structures from sequences of examples. We consider it to be a major advance in the areas generally known as concept-formation, or machine-learning. Given a scene, Winston’s program attempts to describe the scene in terms of elementary objects and already-known sub-structures and relations. For example, when shown an arch and a non-arch (where blocks touch), it discovers the MUST-NOT-ABUT relation and modifies its description of ARCH accordingly.
Having an explicit description (rather than just a test) for a concept seems absolutely crucial. The advantages include:
1) The possibility of making deductions about the concept, including its consistency with a proposed detection scheme;
2) Combining several descriptions in non-trivial ways;
3) Comparing and contrasting descriptions, as in Evans’s program;
4) Using the description to generate, rather than merely to select, what next to do in a search program.
Theorem-Proving
Gerald J. Sussman has implemented a theorem-proving program that uses the Resolution principle with an assortment of retrieval methods and other heuristics to make deductions in predicate calculus. Although there has been a number of interesting results, we nevertheless believe that the use of this technique, as an approach to artificial intelligence, is receiving much undue attention today, and we do not plan to give it a large place in our future activity unless some new and impressive demonstration of its power comes to light.
An example that puts one of the problems into a nutshell: suppose one is given A ⇒ B and C ⇒ D, and (A ⇒ B) & (C ⇒ D) ⇒ E, and one wants to deduce the simple conclusion E. The Resolution program manages eventually to obtain E, but only after many steps of converting the given statements into expanded “normal” forms that are in themselves rather meaningless. Sussman modified the representation so that the symbols were not recognized by the prover as meaning implies, and added a separate set of axioms for using a more natural deduction method. Now the Resolution system produced a better proof in less time, even though it had to work indirectly through the new axioms!
Carl E. Hewitt is developing a language for constructing deductive systems with the utmost heuristic flexibility. His language, PLANNER, is designed to allow use of knowledge and types of representations of great variability. In PLANNER, a statement like “A implies B” can be interpreted as an imperative: “set up a procedure that will see if A is ever asserted, and if this happens assert B also” or “set up a procedure that will see if B is ever desired as a goal, and if so assert A as a new sub-goal to be deduced.” All statements are expressed in a pattern-matching language, MATCHLESS.
Natural Language Systems
Terry A. Winograd is completing a system for handling problems of computer understanding of natural language. The system is designed to accept information in normal English sentences, to answer questions, and to execute commands, using semantic information context to understand pronoun references and to disambiguate grammatically complicated texts. Winograd’s system is based on a heuristic grammar (PROGRAMMAR, A.I. Memo 181) that uses contextual information in analyzing the sentence, carrying out the semantic analysis concurrently.
Loosely Stated Mathematical Problems
Eugene Charniak has completed a program, CARPS (CAlculus Rate Problem Solver), that can solve word problems stated in imprecise English, such as:
| A train, starting at 11:00 a.m., travels east at 45 miles per hour while another, starting at noon from the same point, travels south at 60 miles per hour. How fast are they separating at 3:00 p.m.? |
CARPS translates this problem into an internal representation indicating objects, velocities, starting times, and conditions. It formulates the algebraic expression and calculates derivatives using MATHLAB components to output the final result (e.g., 72.246 MILES/HOUR).
MATHLAB
MATHLAB is an interactive computer-program system developed to facilitate creative work that involves extensive manipulation of symbolic algebraic expressions. In the MATHLAB project, serious attention has been paid to human engineering and to efficiency and speed of operation as well as to basic mathematical problems.
This last year, progress was made on faster parsing algorithms, polynomial representations, and a decision procedure implemented by Joel Moses (due to Risch) for symbolic integration of expressions involving rational functions, logarithms, and exponentials. In 1958, W. D. Maurer compiled a table of 150 integrals involving the error function erf(x). Moses’s program was able to verify and correct errors in these published tables.
Chess
MacHack-VI, a chess program developed by Richard D. Greenblatt for the PDP-6 computer, was begun in November 1966. Since then, it has participated in five official U.S. Chess Federation tournaments and achieved an official rating of 1528. In its last tournament, it achieved a performance rating of 1720. It wins about 86 per cent of its games against tournament players and represents a programming effort of about six man-months.
Eye-Tracking
This year we achieved an old goal of enabling the machine to look at a person—specifically, looking at a man’s eyes to determine his point of fixation in real time. Incorporating an eye-tracking device developed by J. Merchant of Honeywell, Samuel L. Geffner created programs that display text for a subject to read and take real-time action (such as pronouncing the fixated word or displaying its translation).
The A.I. Time-Sharing System
Our system is based on time-sharing a two-processor machine (PDP-6 and PDP-10) with a core memory of 2¹⁸ words of 36 bits (Incompatible Timesharing System – ITS, described in A.I. Memo 161a by Donald E. Eastlake III). The real-time processor handles sensors, mechanical arms (AMF Versatran, MA-2, MA-3), and optical dissectors.
LISP (MACLISP)
MACLISP, described by Jon L. White (A.I. Memo 190), features array space garbage collection, improved LAP machine-language interface, dynamic compiler tables (Whitfield Duffie), and optimized fast arithmetic capabilities.
Mechanical Hands and Arms
David L. Waltz studied human hand motions for tool handling. Jean-Yves Gresser analyzed arm kinematics for 10-degree-of-freedom tentacle-like hydraulic manipulators. Force sensing was developed using Time-Domain Reflectometry (TDR) coaxial cable surfaces and six-axis strain-gauge wrist telemeters (Callahan, Shah, Minsky).
Computer Eyes
Berthold K. P. Horn (A.I. Memo 178) detailed our image dissector camera system. Operating under direct program control over a 4096:1 dynamic range with 1 part in 64 brightness discrimination sensitivity, it provides high-precision visual inputs.
References
1. Lawrence G. Roberts, Machine Perception of Three-Dimensional Solids, Department of Electrical Engineering, M.I.T., Ph.D. Thesis, May 1963.
2. Thomas G. Evans, “A Program for the Solution of Geometric-Analogy Intelligence Test Questions”, Semantic Information Processing, M.I.T. Press (Cambridge) 1968, pp. 271-353.
3. A. Newell, “Learning, Generality and Problem Solving”, Information Processing 1962, IFIP Congress 1962, North Holland Publishing Co. (Amsterdam) 1963, pp. 407-412.
4. Edward A. Feigenbaum, “The Simulation of Verbal Learning Behavior”, Computers and Thought, McGraw-Hill Book Co. (New York), 1963, pp. 297-309.
5. M. A. K. Halliday, “Some Notes on ‘Deep’ Grammar”, J. Linguistics, 3, 1967.
6. Terry A. Winograd, “Linguistics and the Computer Analysis of Tonal Harmony”, J. Music Theory, 12, 1968.
7. R. Anderson, “Syntax-Directed Recognition of Hand-Printed Two-Dimensional Mathematics”, Ph.D. Thesis, Division of Engineering and Applied Physics, Applied Math, Harvard University, Cambridge, Mass., Jan. 1968.
8. H. A. Ernst, MH-1, A Computer-Operated Mechanical Hand, Department of Electrical Engineering, M.I.T., Ph.D. Thesis, December 1961.