Processes at Discontinuities

Introduction

Leyton [1988] developed a set of rules by which process-history can be recovered from smooth natural shapes such as outlines of tumors, clouds, or islands. In this paper, we extend this analysis to deal with shapes with first-order discontinuities such as corners, creases and cusps. A simple extension to the notation allows one extra rule to cover most of these phenomena. ( Such shapes arise also in considering processes acting on free liquid boundaries, such as drops and waves. The · present extension was motivated by an attempt to apply Leytons analysis to the description of the shapes of liquid histories [Hayes 1985]. )

The rules developed in [Leyton 1988] fall into two sets, which we will first briefly review. The first set assigns a symmetry axis to each curvature extremum of a curved shape, and interprets these symmetry axes as the directions of process activity. These rules generalise directly to the present more general case. The second set of rules assigns an intervening process-history to a pair of shapes known to be stages in the development of a single object, and we will extend this set.

The first set of rules are the Symmetry-Curvature Duality Theorem and the Interaction Principle.

* Support for M. Leyton was provided by a Presidential Young Investigators Award, #NSF IRI-8896110

Michael Leyton *

Department of Psychology Busch Campus, Rutgers University New Brunswick, New Jersey 08903

Symmetry-Curvature Duality Theorem: any section of smooth curve with one and only one curvature extremum has just one symmetry axis, which terminates at the extremum itself.

The axis is constructed by moving a circle along the outline of the shape, so that it is always tangential to the curve at two points; the axis is the trace of the midpoint of the arc between these tangent points. ( This symmetry construction is a variant of those in [Blum 1973] and [Brady 1983] )

Interaction Principle: the symmetry axes of a perceptual organisation are interpreted as the directions along which processes are most likely to act or have acted.

This interprets boundary curvature extrema as resulting from processes acting along the corresponding axes, eg a protrusion has been pushed out along its axis and an indentation has been pushed in.

To classify these extrema-based processes, Leyton [1988] considers the curvature function of the outline, ie a plot of curvature against distance travelled around the outline. ( Here we take clockwise as positive. ) There are four types of extrema, ie turning points on the curvature graph: positive maxima M+ , negative minima m-, positive minima m+, and negative maxima M- . The interaction principle suggests that these shapes are the results of process­ situations described respectively by the words protrusion, indentation, squashing and resistance (see figure 1 ).

The second set of rules in [Leyton 1988] uses descriptions of curves in the form of strings of the five symbols M+, M-, m+, m- and 0 ( indicating a point of zero curvature ). It assigns an intervening history to a pair of shapes, by which one can be transformed into the other. This consists of a process grammar which parses shape descriptions in terms of their possible process histories, and an ordering rule based on the following:

Size-is-Time Heuristic: In the absence of information to the contrary, assume size corresponds to time: ie that the larger a boundary feature, the longer it has taken to develop.

This can also be stated as "de-blurring recapitulates time", since blurring removes detail from a shape in order of size, starting with the smallest, and also incrementally moves the boundary in the direction of decreased curvature variation. This proposal is discussed in detail in [Leyton 1989]

The grammar in [Leyton 1988] has six operations, shown in figure 2, which suffice for the description of the relationship between any two smooth shapes. The operations are expressed as rewrite rules on strings of extrema symbols describing the shapes. Two are operations of process continuation, and four describe process bifurcation. They fall into three pairs of duals, where the dual of an operation corresponds to reversing the inside/ outside of a contour. All the rules can apply in reverse, since processes can recede: we will write -g to mean the reverse of g.

First-order Discontinuities

The purpose of this paper is to extend the grammar to handle processes which create first-order discontinuities in the curvature function. I Suppose for example that the protrusion process which is reshaping the curve in figure 3 is created by a sharp edge pressing against the inside of a flexible container. Initially, due to flexural rigidity in the skin, the extremum being created is smooth. Continuation, however, will produce a sharp bend in the skin ( fig. 3b ), and as the knife is pushed further outward the skin is pulled around the blade, forming a cusp ( fig. 3c ). We will call any such point of curvature-discontinuity a kink.

We observe first that the Symmetry-Curvature Duality Theorem extends naturally to curves with kinks. Both sharp bends and cusps have axes, formed by the same construction, and the theorem still holds, with the axes terminating at the discontinuity. 2

1 Continuous approaches to the formation of discontinuities have been studied by Terzopoulos et a!. [1988] and Blake and Zisserman [1987]

2ane has to slightly generalise "tangent": a tangent at a kink is any line through the kink point whose orientation is between those of the half-tangents on either side.

( The theorem extends also to include curves with straight or circular-arc segments of constant curvature, with the axis terminating at the center­ point of the segment, but we do not take advantage of this fact here. )

Curvature is Sq/Ss, where q is the rotation angle and s is distance along the curve. However, at a kink, the tangent rotates through a finite amount in zero distance, so the curvature can be regarded as infinite3. The curvature graph has a single point at infinity, which we will indicate by a spike. Thus, kink-formation on the shape contour corresponds to spike-formation on the graph of the curvature function. Curvature graphs with spikes are a useful heuristic tool to help visualise the properties of curves with kinks.

A curvature graph with a spike is the limiting case of one with a narrow peak, in which the peak is made narrower while the area beneath it remains constant, so its height goes to infinity. This corresponds to a part of the boundary containing a curvature extremum having a certain amount of rotation squeezed into a smaller part of the curve, with a kink as the limit of this process. If one slightly blurs a kinked curve, the kink will appear to be merely a tight smooth bend, and the spike on the curvature graph will be replaced by a peak. Notice that this means that kink formation accords with the size-is-time heuristic, since the sequence from smooth extremum to kink is both the temporal order and the de-blurring order.

A kink, like a smooth extremum, has a parity: its spike may be upwards or downwards in the curvature graph ( ie its curvature may be positively or negatively infinite ). This distinction encodes a salient perceptual aspect of the curve, the direction of the kink's bend.

Describing kinks

Rather than introduce new symbols for kinks, we will indicate the direction of a kink by attaching a subscript to one of the four symbols being used for smooth extrema. The suffix is either + or - , depending on the direction of the spike-point of the curvature graph: it is the parity of the spike. The parity of the spike need not match that of the superscript, and this flexibility is crucial to the expressiveness of the notation, as we will see.

The change from a smooth protrusion to a kink, as in our earlier example, is described simply by the attachment of a subscript to the extremum symbol denoting the smooth bulge initially produced by the knife. This transforms the string ... M+ ... into the string ... M,: ... We can characterise this change as the introduction into the curvature function of a spike which sends the extremum point to infinity in the direction of the extremum, so that the same suffix is attached to the symbol.

3 we follow in the distinguished footsteps of Paul Dirac.

Similar versions can be given of the other three types of process. The dual, a sharp indentation, transforms m-into m:. Notice that the other two smooth extrema m· and M- are produced by processes ( respectively, squashing and internal resistance ) acting in the opposite direction to the convexity of the curve at that point, so that the result of "sharpening" the process is a kink whose curvature graph has a spike of opposite parity from its neighborhood. Thus, the kinks formed here are cusps. These are also a dual pair, consisting of the transformations m+ -> m~ and M- -> M;.

We will summarise these four transformations as the rule K of kink-introduction. Kink-introduction corresponds intuitively to the application of a sharp distorting process. In terms of the curvature function, it can be simply described as the addition of a positive spike to a maximum or a negative spike to a minimum

Cusp-Formation

Now let us consider the transformation from a sharp bend to a cusp ( figure 3 ). Here, the boundary curvature on either side of the corner-point changes parity. The change in the curvature function can be described as "pulling" the function down until it goes below the x-axis. While cusps can be formed in several ways, the common feature is that the x-axis of the curvature graph is made to separate a smooth neighborhood of the point from the point itself. 4 Thus, cusp-formation in the shape contour corresponds to zero separation in the curvature function.

Cusp-formation at l'vr and m·

The kink rule K introduces a zero separation immediately at "blunt" extrema. Consider, for example, a kink created at M- . Zero separation in this case means that the spike neighborhood is negative, but the spike is positive. The shape contour is therefore locally concave, but has a convex kink, ie a cusp, like the profile of a lower leg distorted by a broken shin bone . Notice that the process creating such a kink is along the axis of the curvature minimum, in the same direction as the internal resistance process hypothesised by the interaction principle ( see figure 1 ).

4 Some skew comers, such as the end of a cats claw, have a curvature graph in which the spikepoint separates regions on opposite sides of the x-axis. The notation developed in this paper cannot easily handle such asymmetric phenomena, or cases where the curve is kinked elsewhere than at extrema of curvature. Work on these will be reported in later papers.

Cusp-formation at M*" and m-

The other two cases do not form cusps so directly, but our main result is that the the rules of the original grammar suffice to describe all the remaining transformations.

The central complexity in describing cusp formation is that the spike-neighborhood is only part of the entire curvature graph and therefore pulling it through the x-axis has consequences in the rest of the graph, and we want the grammatical rules to accurately reflect the corresponding changes in contour shape. We illustrate this by considering an example ( figure 3 ) involving the introduction of concavities on either side of the kink as it changes from a simple bend to a cusp under the inexorable progression of the sharp protruding process.

Looking at this change more closely, we can see that the kink is a place of maximum curvature, a peak in the curvature function ( figure 3b).

As the kink becomes sharper, the curvature immediately to the sides of the kink-point decreases. At some stage, it will be less than the curvature of the m+ extrema at the sides of the shape. But these were the old minima of curvature, so that the curvature adjacent to the kink is now the minimum ( figure 3c ). One can think of the process as the two m+ points of minimum curvature sliding along the contour towards the kink and eventually being absorbed by it.

Consider now what has happened to the corresponding curvature functions. In the transition from b to c, the first maximum has moved downwards, allowing the two minima to unite. If we ignore the spike, this is exactly the reversed operation -Bm+ of the original grammar: m+ ~ m+ -> m+. If we had a smooth contour, this merging of minima would have resulted in a simple minimum (as -Bm+ describes) since the axes of the minima would then also have merged. Notice that here, however, the minima have partially opposed axes, which means that the processes which are associated with them have components directed towards each another, and the rule instead transforms M: into m:. We will call this a pinching.

Finally, as the distortion continues, the curvature at either side of the kink continues to fall until it becomes zero, at which point further distortion produces a cusp (figure 2d). The corresponding event in the curvature function is the lowering of the minimum through the x-axis. But this in turn is simply an example of the operation Cm+ of the original grammar: m+ -> 0 m- 0. In the case of a smooth contour, this shape change is caused by a squashing process directed perpendicularly inwards along the symmetry axis of the local extremum. Here, the oppositely-directed components of the processes which are associated with the minima of the pinching serve exactly this role ( figure 4 ).

The contour on each side of the kink behaves locally just as a smooth contour acting under the influence of local processes would act according to the original process rules. We see then that in this case, the formation of a cusp can be described by the use of rules from the original grammar in contexts which preserve their underlying process-oriented intuitions.

The difference between a sharp bend and a cusp is encoded by the difference between the curvature and spike parities of a doubly labelled symbol:

The use of the rule Cm+ has introduced such a parity difference into the string, from which the creation of a cusp can be inferred. Thus cusp-formation at either maxima or minima of curvature requires no new operation besides kink-formation K .

Other kinks

The four other combinatorial possibilities of adding a kink subscript to a symbol denoting a curvature extremum can be derived from K together with the bifurcation rules of the original grammar. For example, the rule K will not directly produce the kink m; from the convex minimum m+. The squashing process hypothesised by the interaction principle is acting inwards in this case, but a sharp outward protrusion is necessary to produce the positive kink. This can be derived however by first introducing a process in the required outward direction:

and then proceeding as in our earlier example, by applying K to the new protrusion

and then reversing the bifurcation:

Notice that the reverse-bifurcation which is applicable is exactly the one needed to undo the effects of our first rule application and restore the overall shape of the contour. In this case, therefore, the whole sequence has a natural interpretation as a squashing being pushed back by a sharp protrusion process, forming a kink in the contour which remains in place even when the protrusion process yields back to the restored force of the squashing ( figure 5).

Similar uses of appropriate bifurcations will produce M!.", m:;. and M: . An example of the dual formation of M: from M- would be a sharp concave crease caused by the impact of a small hard object on a concave section of smooth metal bodywork which rebounds from the impact, restoring its overall shape. Here the rule K introduces plastic deformation to the rules of the original grammar.

Curvature Components

In a string of symbols representing a curve, the superscripts and subscripts both encode perceptually significant aspects of the shape, but do so essentially independently. Consider for example the kink­ formation stage in our example. Since the relevant extremum of the initial smooth curve is M+ , the kink-formation rule must convert it toM;. Now, although theM and the upper+ in this symbol are each a memory of the initial smooth extremum, they nevertheless have perceptual significance in the second shape. They represent the fact that the curvature is still a local positive maximum in approaching the discontinuity along the contour. We will call the upper + in the symbol M; , and similarly for the other kinky symbols, the curvature parity.

the second string can be regarded as the same sequence as the first, with a suffix added at the appropriate point to indicate the position of the kink. In fact, the second string encodes the same curvature content as the first, since curvature is defined only at smooth points. Thus we can think of the second string as having two independent components: the sequence M+m+ M+, which encodes the the smooth curvature content, and the lower subscript + which encodes the spike. The first component is the curvature component of the string.

The key point is that successive shape transitions, as in the cusp formation, can be regarded purely as manipulations of the curvature component, using the operations of the original grammar, in which the continued presence of the subscript keeps track of the presence and position of the spike. Thus, all the rules of the original grammar can be applied freely to the curvature components of strings with subscripts, and correspond naturally to symmetrical curvature transformations on the smooth portions of angular curves.

As a more complex example, consider the bay in the top left shape of figure 6. We wish to consider cusp­ formation at the left indentation m- in the bay. Reading along the contour from left to right, the shape of the bay is described by

with the curvature function shown. Applying K to the first m- gives

as shown. Applying the rule CM- to the middle extremum, we obtain

Now the suffixed m.: is flanked by 0, and so the reversed rule -Cm- can be applied, giving

and the parity difference shows that a cusp has been formed.