Process Recovery

ABSTRACT

In many disciplines, the scientist uses the shape of an entity to infer processes that have acted upon the entity. We develop inference rules by which the curvature extrema of a shape can be used to infer the precise trajectories of processes that have created the shape. A formal grammar is also ela­ borated by which, given two views of the same entity at two developmental stages, the scientist can infer the processes that acted in between the two stages.

I. INTRODUCTION.

In many disciplines, such as astrophysics, developmental biology, medicine, geography, meteorology, etc., the shape of some entity, such as an embryo, tumor, or cloud, is used by the scientist to infer processes that have acted upon the entity. In this paper, we present a set of inference rules by which the cur­ vature extrema of a shape can be used to infer the significant processes that have determined the shape. We also develop a for­ mal grammar by which a scientist, who has two views of an entity at two developmental stages, can infer the processes that produced the second stage from the first.

D. TWO BASIC RULES

We begin by presenting two simple rules by which the curvature extrema of an individual shape can be used to infer significant processes that have acted upon that shape. Throughout the paper, we will assume that the input to the rules are shapes represented in the form of smooth planar out­ lines. However, an equivalent anaJysis applies to three­ dimensional input, as shown in Leyton (1987c).

The inference, from curvature extrema to processes, will be seen as requiring two stages:

curvature extrema .. symmetry axes .. proceues

Section D.l deals with the first stage, and section D.2 deals with the second stage.

D.l. Curvature Extrema .. Symmetry Axes

As just stated, central to the development of our process inference rules will be the use of a symmetry analysis.

Observe first, however, that, given two segments of a curve, it is rarely the case that a straight axis refiects one seg­ ment on to the other. Nevertheless, it may be po!lSible to define

*Current Mailing address: Michael Leyton, Department of Psycholoay, Rutgen Univenity, Busch Campus, New Brunswick, NJ 08903. The research was. sup­ ported by NSF grant IST-8418164 to Harvard; and by NSF grant IST-8312240 and AFOSR grant F4962Q-83.C-{)13S to MIT.

PROCESS RECOVERY

Michael Leyton

SUNY Buffalo and Rutgers University*

symmetry in a differenlial sense. Consider the two bold curves c 1 and c 2, in Fig la. Although there is no mirror that reflects one curve onto the other, a mirror along line Q0 reflects the tangenl Une, at A, onto the tangenl Une, at B. It turns out that the existence of such a symmetry is equivalent to the existence of a circle that is tangential at both A and B. (The mirror Will contain the circle center 0.)

Now drag the circle along the two curves, while always maintaining the double-touching property. As in Leyton (1987b), one can define a differenlial symmetry axis to be the trajectory of some mid-potnl associated with the circle. For example, the Symmetric Axis Transform (SAT) of Blum (1973) defines the symmetry axis to be the locus of circle-centers 0 . This will give some curved axis running between the two curves c 1 and c2· Again, the Smooth Local Symmetry (SLS) of Brady (1983) defines the symmetry axis to be the locus of chord midpoints P. (In the present case, this will produce a slightly different axis from the SAT.) Alternatively, we shall propose here a new symmetry analysis in which the symmetry axis is the trajectory of the midpoint Q of the arc AB, as the circle moves. As shown in Leyton ( 1987c), this analysis has remark­ ably different properties from the other two analyses and these properties make the analysis particularly appropriate for the inference of processes. Because of its appropriateness to process­ inference, the new analysis will be called Process-Inferring Symmetry Analysts (PISA~ We shall see several examples of applying PISA, later.

It is now po!lSible to state a result that is crucial to the entire paper. It is a theorem that was proposed and proved in Leyton (1987b), and it relates the curvature extrema of a smooth planar curve to the curve's symmetry structure:

SYMMEI'RY-cDRVATURE DUALITY TIIEOREM (Ley­ ton, 1987b): Any segmenJ of a smcoth plarwr curve, bounded by two consecutive curvature extrelTUl of the sai'IU type (either both TTUlXilTUl or both minilTUl) has a unique differential symi'IUtry axis (under SAT, SLS, or PISA) and this axis terminates at the curvature extremum of the opposite type (minimum or TTUlX­ imum, respectively).

Fig 1b illustrates the theorem. The two points labeled m­ are two consecutive extrema of the same type (i.e. they bend in the same direction relative to the curve). The theorem states that, under any of the alternative differential symmetry ana­ lyses, there is one and only one sy=etry axis. Furthermore, this axis terminates at the extremum M +, of the opposite type (this extremum bends in the opposite direction).

The theorem will be our first inference rule: It assigns, to each extremum, a unique sy=etry axis that terminates at that extremum.

n.2. Symmetry Axes ... Processes

The value, to our argument, of identifying symmetry axes, is given by the following crucial principle which was proposed and extensively corroborated in Leyton (1984, 1985, 1986a, 1986b, 1986c, 1987a)

INTERACI10N PRINCIPLE (Leyton, 1984): The symi'IUtry axes of a perceptual organization are inJerpreted as the prind· pal directions along which processes are most likely to act or have acted.

The basis for this proposal is as follows: It was argued in Leyton (1986b) that if a transformation, acting on an organization is one in which symmetry axes become invariant lines (eigen­ spaces) under the transformation, then the transformation will tend to preserve the symmetries; i.e. be structure·preserving on the organization. Two further stages of argument are then needed to obtain the above principle: (1) invariant lines are interpreted as principal directions of action, and (2) transforma­ tions that are most structure-preserving tend to be understood as most likely. The above principle has been psychologically vali­ dated on simple and complex shape, as well as motion perception (Leyton, 1985, 1986b, 1986c, 1987a).

The Interaction Principle can be regarded as an inference rule. It claims that a symmetry axis is interpreted as the princi­ pal direction of a hypothesized process. In fact, since· we are con­ cerned, in the present paper, with the inference of processes that have already taken place, the principle implies that a symmetry axis is interpreted as a record of a process.

ll.3. Curvature Extrema ... Processes

Putting together the two inference rules given thus far, we obtain this conclusion:

Each curvature extremum implies a process whose trace is the unique symmetry axis associated with, and terminating at, that extremum

To see that our two inference rules yield highly appropri­ ate process-analyses, let us consider all possible shapes that have eight extrema or less. Drawings of all such shapes have been provided by Richards, Koenderink & Hoffman (1985). In Fig 2, we have taken all these drawings and applied our two inference rules. The lines with arrows represent the process-records inferred by our rules. That is, the lines are the directions of growth, indentation, squashing, etc, along which the deforma­ tions are supposed to have happened. As can readily be seen, these process-records correspond strongly with one's intuition as to how the shapes were formed.

Three co=ents are in order:

(1) The letters on each shape denote the curvature extrema. as follows: Let M and m denote a local maximum and local minimum respectively, and + and - denote positive and negative curvature repectively. Thus there are four types of extrema: M +, m -. m ·, and M - . ·

(2) The symmetry analysis, used in Fig 2, was PISA, the new analysis introduced in section 11.1. This is because, as shown in Leyton (1987c), the SAT and SLS cannot correctly infer squashing and indentation, whereas PISA can.

(3) Fig 2 is stratified into levels according to number of extrema. The only three levels that can exist, with up to eight extrema, are: Level I, shapes with 4 extrema; Level U, shapes with 6 extrema; Level 01, shapes with 8 extrema.

m. THE PROCESS GRAMMAR

The above analysis presented inference rules by which a single shape can be given a process-description. However, in many observational situations, the scientist has two views of an object at two developmental stages. The scientist attempts to infer the processes that produced the second stage from the first. It is this problem that we now attempt to formalize and solve. We shall develop a process-gram11Ulr such that, given two shapes. one shape is expressed as the extrapolation of processes inferred in the other by the above inference rules.

The operations of the grammar are specified purely in terms of modifications at extrema, but such that these modifications correspond to process-extrapolations. Physically natural extrapolations have two forms, conlinuations and bifur· cations, which we now consider in turn.

Continuations.

The continuation of a process at a M · or m- extremum does not change the extremum type, as can be seen by looking at any of the M · and m- extrema in Fig 2. However, continuation at a m + or M - does change the type, as we shall now see:

(1) Continuation at m· (labeled Cm·) yields m- , as is illustrated by continuing the upward m · process at the bottom of shape P1 (Fig 2) and thus obtaining shape P2. This form of extrapolation is fully specified by the following re-write rule expressed purely in terms of the curvature extrema along the bottoms of the respective shapes:

(where each 0 represents a curvature zero, indicated by a dot on the curve in P2).

(2) Continuation at M - (labeled CM-) yields M +, as is illustrated by continuing the upward M - process in shape T3 (Fig 2) and thus obtaining the top protruding M · process in T4. The rule is specified as:

Bifurcations:

A bifurcation has the effect of taking an extremum (max­ imum or minimum) and pulling it apart into two copies of itself. Between the copies, an extremum of the opposite type (minimum or maximum, respectively) is unavoidably intro­ duced. In the smallest such non-trivial change, the introduced extremum has the same sign as the splitting extremum. Logi­ cally, there are four such primitive bifurcations, as follows. All other bifurcations are derivable from these together with the above two continuation operations.

(3) Bifurcation at M· (labeled BM·) must be given by the re-write rule

An illustration is the following. Consider the protruding pro­ cess at the top of T4 (in Fig 2). If the process bifurcates, one branch goes to the left and the other to the right. The resulting shape has been drawn on its side as Q6 in Fig 2.

Fig 2. The inference rules applied to the shapes of Richards, Koenderink and Hoffman, 1985.

(4) Bifurcation at m· (labeled Bm·) must be given by the re-write rule

An illustration is the following. Consider the indenting process at the top of T2 (in Fig 2). If the process bifurcates, one branch goes to the left and the other to the right. The resulting shape is Q2 (in Fig 2).

(5) Bifurcation at m· (labeled Bm·) must be given by the re-write rule

and is simply the introduction of a protrusion. An illustration is the transition from Pl to Tl (in Fig 2); i.e. a protrusion has been introduced at the top of Tl.

1. Bifurcation at M- (labeled BM-) must be given by the re-write rule

and is simply the introduction of an indentation. An illustration is the transition from T3 to Q3 (in Fig 2); i.e. an extra indentation has been introduced in the bottom of the lagoon in Q3.

IV. THE POWER OF THE GRAMMAR

The first remarkable thing to emerge from the above analysis is that a grammar of only six operations generates all process extrapolations; and, furthermore, that the grammar suc­ cessfully encodes extrapolations purely in terms of re-write rules on extrema.

Let us illustrate also the intuitive power of the grammar to yield process-explanations. Let us choose two arbitrary shapes, for example, the pair shown in Fig 3. The assumption is that the two shapes are two stages in the development of the same object; e.g. a tumor, cloud, island, embryo, etc. We now show that the process-grammar gives a compelling account of the intervening development.

Using a blurring heuristic, described in Leyton ( 1987c), one can identify the intervening succession of shape-outlines. Let us suppose that the succession is T6 ... T5 ... Q7 ... Q5, as shown in Fig 4. However, a succession of outlines is not a process­ explanation. One requires the grami'TUlr to provide the interven­ ing process-history. The grammar does this by the successive transformation of process-diagrams. In particular, for Fig 4, the grammar generates the successive process-structures by the sequence of operations, CM - · BM · · Cm ·. The operation­ sequence is the process-explanation for the intervening develop­ ment. The explanation can be expressed as follows:

T6

T5

1. One particular process turns out to be crucial to the entire development. It is the internal process represented by the bold upward arrow in the first shape of Fig 4 (the arrow terminating at M -).
2. This continues upward and creates the protrusion in the second shape of Fig 4.
3. This same process then bifurcates, creating the lobe in the third shape of Fig 4, where a downward squashing process has also been introduced from above.
4. The new squashing process continues, creating the top indentation shown in the fourth shape of Fig 4. ·

As the reader can see, the grammar, although derived formally, provides an intuitively powerful process explanation.