We describe the analysis of visual scenes consisting of black on white drawings formed with curved lines, depicting familiar objects and forms: houses, trees, persons, and so on; for instance, drawings found in coloring books. The goal of such analysis is to recognize (by computer) such forms and shapes when present in the input scene; that is, to name (correctly) as many parts of the scene as possible: finger, hand, girl, dance, and so on. Complications occur because each input scene contains several such objects, partially occluding each other and in varying degrees of orientation, size, and so on. The analysis of these line drawings is an instance of'the context problem', which can be stated as'given that a set (a scene) is formed by components that locally (by their shape) are ambiguous, because each shape allows a component to have one of several possible values (a circle can be sun, ball, eye, hole) or meanings, can we make use of context information stated in the form of models, in order to single out for each component a value in such manner that the whole set (scene) is consistent or makes global sense?' Thus, shape drastically limits the values that a component could have, and further disambiguation is possible only by using global information (derived from several components and their interrelations or interconnections) under the assumption that the scene as a whole is meaningful. This paper proposes a way to solve'the context problem' in the paradigm of coloring book drawings. We have not implemented this approach; indeed, a purpose of this paper is to collect criticisms and suggestions.

One example of this will suffice.

Given P {P1,.. P„} as input, set j 0, 00 8 (the identity substitution),

We have attempted to discover formal rules for transcribing into musical notation the fugue subjects of the Well-Tempered Clavier, as this might be done by an amanuensis listening to a'deadpan' performance on the keyboard. In this endeavour two kinds of problem arise: what are the harmonic relations between the notes, and what are the metrical units into which they are grouped? The harmonic problem is that the number of keyboard semitones between two notes does not define-- their harmonic relation, and we further develop an earlier theory of such relations, arriving at an algorithm which assigns every fugue to the right key and correctly notates every accidental in its subject.

A general game-playing program must know the rules of the particular playing game. These rules are:(1) an algorithm indicating the winning state;(2) an algorithm enumerating legal moves. A move gives a set of changes from the present situation.There are two means of giving these rules:(1) We can write a subroutine which recognizes if we have won and another which enumerates legal moves. Such a subroutine is a black box giving to the calling program the answer: 'you win' or 'you do not win', or the list of legal moves. But it cannot know what is in that subroutine.(2) We can also define a language in which we describe the rules of a game. The program investigates the rules written with this language and finds some indications to improve its play. Artificial Intelligence and Heuristic Programming Edinburgh University Press

The importance of effective task representations in the design of programs intended to exhibit sophisticated behaviour manifests itself in the area of Picture Interpretation as the so-called ‘Linguistic Approach’. A brief survey of Pattern Description Languages leads up to an analysis of a simple letter recognition task from which it is argued that at least two types of description of the pattern must be utilised if any significant pattern generalisation is to be achieved, and in general that all picture interpretation tasks involve descriptions in two domains. Further support for this viewpoint is provided by a characterization of the problem of interpreting line diagrams as pictures of three dimensional sceness, in which the form of these decriptions and of their interrelation by an algorithm is described in detail. The paper concludes by relating these ideas to the distinction between syntax and semantics, and the concept of denotation.

To every 3-dimensional scene there correspond as many 2-dimensional pictures as there are possible vantage points for the camera. It is, however, possible to construct pictures for which there is no corresponding scene containing physically -realizable objects. Pictures of such'impossible objects' can be useful in giving insight into the constraints or grammatical rules associated with the'language' of pictures, just as nonsense sentences can be useful in illustrating the rules of other languages. Impossible objects have been used by psychologists (Penrose and Penrose 1958) to create visual illusions which successfully challenge the ability of our perceptual systems to synthesize a 3-dimensional world from 2-dimensional information. The incompatibilities among the various portions of pictures of these objects are a novel way of testing our picture analysis procedures. The purpose of this paper is to demonstrate some possible decision procedures and to test them on pictures of both possible and impossible objects.

In this paper, we develop the algorithm, given in Plotkin (1970), for findingthe least generalization of two clauses, into a theory of inductive generalization.The types of hypothesis which can be formed are very simple. They allhave the form: (x)Px --> Qx.We have been guided by ideas from the philosophy of science, followingBuchanan (1966). There is no search for infallible methods of generatingtrue hypotheses. Instead we define (in terms of first-order predicate calculus)the notions of data and evidence for the data. Next, some formal criteria areset up for a sentence to be a descriptive hypothesis which is a good explanationof the data, given the evidence. We can then look for the best such hypothesis.Machine Intelligence 6

One of the central principles upon which intelligent devices seem to operate is that of maintaining internal models of their external environments. How difficult this is, depends upon both the complexity of the model and its method of representation. In particular, it is usually easy when the problem is posed in the classical heuristic search paradigm, and the data structures used to represent static configurations of the puzzle are relatively unproblematic (arrays, lists, and so on). The lack of side-effects reflects the simplicity of the physics which such models embody. This limitation to elementary forms of interaction is not, of course, intrinsic to the heuristic search method; but when more complex models are constructed it becomes less trivial to pursue the consequences of performing an action. This approach is more general than the heuristic search method (but the latter -- when it has sufficient expressive power -- wins at present by its computational advantage). Assertions mentioning several different situations can then be used to describe dynamical laws which move us from one situation to another. But in some ways the resulting sharp separations between states of affairs are an embarrassment. For if we distinguish two situations s1 and s2, then from the fact, if such it be, that a predicate p is true of Si, nothing whatever follows concerning s2. And this is true even when s2 is directly associated with sl. Say s2 results from s1 by the performance of some action: s2 do (a, si) then no matter how remote -- speaking intuitively -- the connection between the property p and the action a, it still does not follow that p is true of s2. If we want it to so follow we must state this explicitly. Now, unfortunately, there are innumerable facts which might remain unchanged when actions are performed. So instead of writing a law of motion' in the form A(s) B(do(a, s)) where A and B are fairly short expressions, we are apparently obliged to list systematically all conceivable facts which are not changed. So that the law looks more like (Ci(s)& Ci(do(a, s))& & C„(do(a, s))&B(do(a, s)) for some very large n. This works for small problems (such as the familiar hungry anthropoid), but these are usually better formalized in the heuristic search paradigm anyway.

Amsterdam: North-Holland.