Inferring History from Shape by Michael Leyton, Page 2. (Return to page 1)   The Process Grammar We will now show how to infer a more detailed history of the object. The problem will be solved in the following way. Suppose, for the sake of argument, we have any two shapes from the object's history. How can we infer the intervening history between the two shapes? Our method of solving this problem will be to develop a grammar that generates the second shape from the first via a sequence of stages. Observe now that, since the later shape is assumed to emerge from the earlier shape, one will wish to explain it, as much as possible, as the outcome of what can be seen in the earlier shape. In other words, one will wish to explain the later shape, as much as possible, as the extrapolation of what can be seen in the earlier one. As a simple first cut, let us divide all extrapolations of processes into two types: (1) Continuations (2) Bifurcations (i.e. branchings). What we will do now is elaborate the only forms that these two alternatives can take. We first look at continuations and then at bifurcations.   Continuations Consider any one of the M+ extrema in the next figure. It is the tip of a protrusion, as predicted by our Semantic Interpretation Rule. What is important to observe is that, if one continued the process creating that protrusion, i.e. continued pushing out the boundary in the direction shown, the protrusion would remain a protrusion. That is, the M+ extremum would remain a M+ extremum. This means that continuation at a M+ extremum does not structurally alter the boundary. Exactly the same argument applies to any of the m- extrema in the above figure. That is, continuation of an indentation remains an indentation. That is, a m- extremum will remain m-. Now recall that there are four types of extrema, M+, m-, m+, M-. We have seen that continuations at the first two do not structurally alter the shape. However, we shall now see that continuations at the second two do cause structural alteration. Let us consider these two cases in turn.   Continuation at m+ A m+ extremum occurs at the top of the left-hand shape in the next figure. In accord with our Semantic Interpretation Rule, the process terminating at this extremum is a squashing process; i.e., it explains the flattening at the top of the shape. Now let us continue this process; i.e. continue pushing the boundary in the direction shown. At some point, an indentation will be created, as shown in the top of the right-hand shape in this figure: Observe what happens to the extrema involved. Before continuation, i.e. in the left-hand shape (above), the relevant extremum is m+ (at the top). After continuation, i.e. in the right-hand shape, this extremum has changed to m-. In fact, observe that a dot has been placed on either side of the m-, on the curve itself. These two dots are points where the curve, locally, is completely flat; i.e. where the curve has 0 curvature. Therefore the top of the right-hand shape is given by the sequence 0 m- 0. Thus the transition between the left-hand shape and the right-hand shape can be structurally specified by simply saying that the m+ extremum, at the top of the first shape, is replaced by the sequence 0 m- 0, at the top of the second shape. This transition will be labeled Cm+, meaning Continuation at m+. That is, we have:  Cm+ : m+ ® 0 m- 0 The above string of symbols says "Continuation at m+ takes the m+ and changes it into the triple 0 m- 0". Observe that, although this operation is, formally, a rewrite rule on discrete strings of extrema, the rule actually has a highly intuitive meaning. Using our Semantic Interpretation Rule, we see that it means: squashing continues till it indents.   Continuation at M-  As noted earlier, we need to consider only one other type of continuation, that at a M- extremum. In order to understand what happens here, consider the left-hand shape in the figure below. The symmetry-analysis given at the beginning of this paper describes a process-structure for the indentation that is very subtle, as shown: There is a flattening of the lowest region of the indentation due to the fact that the downward arrows, within the indentation, are countered by an upward arrow, which is within the body of the shape and terminates at the M- extremum. This latter process is an example of what our Semantic Interpretation Rule calls internal resistance. The overall shape could be that of an island where an inflow of water (into the indentation) has been resisted by a ridge of mountains (in the body of the shape). The consequence is the formation of a bay. Now, recall that our interest is to see what happens when one continues a process at a M- extremum. Thus let us continue the M- process upward, in the left-hand shape (in the above figure). At some point, the process will burst out and create the protrusion shown at the top of the right-hand shape. In terms of our island example, there might have been a volcano, in the mountains, that erupted and sent lava down into the sea. Now let us observe what happens to the extrema involved. Before continuation, i.e. in the left-hand shape, the relevant extremum is M- (in the center of the bay). After continuation, i.e. in the right-hand shape, this extremum has changed to M+ (at the top of the protrusion). In fact, observe that, once again, a dot has been placed on either side of the M+, on the curve itself. These two dots represent, as before, points where the curve is, locally, completely flat; i.e. where the curve has 0 curvature. Therefore the top of the right-hand shape is given by the sequence 0 M- 0. Therefore the transition between the left-hand shape and the right-hand shape can be structurally specified by simply saying that the M- extremum, in the left-hand shape, is replaced by the sequence 0 M- 0, at the top of the right-hand shape. This transition will be labeled CM-, meaning Continuation at M-. Thus we have: CM- : M- ® 0 M+ 0 The above string of symbols says "Continuation at M- takes the M- and changes it into the triple 0 M+ 0." Observe once again, that, although this operation is a formal rewrite rule on discrete strings of extrema, the rule actually has a highly intuitive meaning. Using our Semantic Interpretation Rule, we see that it means: internal resistance continues till it protrudes.   Bifurcation We saw above that process-continuation can take only two forms. Our purpose now is to elaborate the only forms which the bifurcation (branching) of a process can take. Note that, because there are four extrema, we have to examine bifurcation at each of these four.   Bifurcation at M+ Consider the M+ extremum at the top of the left-hand shape in the figure below, and consider the upward protruding process terminating at this extremum. We wish to examine what would result if this process bifurcated. Under bifurcation, one branch would go to the left and the other to the right. That is, the branching would create the upper lobe in the right-hand shape: Observe what happens to the extrema involved. Before splitting, one has the M+ extremum at the top of the first shape. In the situation after splitting (i.e. in the second shape), the left-hand branch terminates at a M+ extremum, and so does the right-hand branch. That is, the M+ extremum, in the first shape, has split into two copies of itself in the second shape. In fact, for mathematical reasons, a new extremum has to be introduced in between these two M+ copies. It is the m+ shown at the top of the lobe of the second shape. Therefore, in terms of extrema, the transition between the first and second shapes can be expressed thus: The M+ extremum at the top of the first shape is replaced by the sequence M+ m+ M+ along the top of the second shape. This transition will be labeled BM+, meaning Bifurcation at M+. That is, we have: BM+ : M+ ® M+ m+ M+ The above string of symbols says "Bifurcation at M+ takes the M+ and changes it into the triple M+ m+ M+." Observe that, although this transition has just been expressed as a formal re-write rule on discrete strings of extrema, the transition has, in fact, the following highly intuitive meaning: a nodule develops into a lobe.   Bifurcation at m- Consider now the m- extremum at the top of the left-hand shape in the figure below, and consider the downward indenting process terminating at this extremum. We will examine what results if this process bifurcates. Under bifurcation, one branch would go to the left and the other to the right. That is, the branching would create the bay in the right-hand shape: Observe, again, what happens to the extrema involved. Before splitting, one has the single extremum m- in the indentation of the first shape. In the situation after splitting (i.e. the second shape), the left-hand branch terminates at a m- extremum, and so does the right-hand branch. That is, the top m- in the first shape has been split into two copies of itself, in the second shape. Again, for mathematical reasons, a new extremum has to be introduced in between these two m- copies. It is the M- shown at the center of the bay in the second shape. Therefore, in terms of extrema, the transition between the first and second shapes can be expressed thus: The m- extremum in the first shape is replaced by the sequence m- M- m- in the second shape. This transition will be labeled Bm-, meaning Bifurcation at m-. That is, we have: Bm- : m- ® m- M- m- The above string of symbols says "Bifurcation at m- takes the m- and changes it into the triple m- M- m-." Observe that, although the transition has just been expressed as a formal re-write rule using discrete strings of extrema, the transition has, in fact, a highly intuitive meaning: an inlet develops into a bay.   Bifurcation at m+ and M- Bifurcations at these two extrema turn out to be very easy to understand: They are simply the introduction of a protrusion and the introduction of an indentation, respectively. It will therefore not be necessary to diagram them.   The Complete Grammar Recall that the problem we are examining is this: Given two views of an object (e.g. a tumor), at two different stages of development, how is it possible to infer the intervening shape-evolution? Observe that, since one wishes to explain the later shape as an outcome of the earlier shape, one will try to explain the later shape, as much as possible, as the extrapolation of the process-structure inferrable from the earlier shape. We have now shown that all possible process-extrapolations are generated by only six operations: two continuations and four bifurcations. Therefore, these six operations form a grammar that will generate a later shape from an earlier one via process-extrapolation. The grammar is as follows:   PROCESS GRAMMAR Cm+ : m+ ® 0 m- 0 CM- : M- ® 0 M+ 0 BM+ : M+ ® M+ m+ M+ Bm- : m- ® m- M- m- Bm+ : m+ ® m+ M+ m+ BM- : M- ® M- m- M- Recall however that, although these operations are expressed as formal re-write rules on discrete strings of extrema, they describe six intuitively compelling situations, as follows:   SEMANTIC INTERPRETATION OF THE GRAMMAR Cm+ : squashing continues till it indents. CM- : internal resistance continues till it protrudes. BM+ : a protrusion bifurcates; e.g. a nodule becomes a lobe. Bm- : an indentation bifurcates; e.g. an inlet becomes a bay. Bm+ : a protrusion is introduced. BM- : an indentation is introduced.   These situations are illustrated in the above figures. This page has shown only a few rules from Leyton's book - those inferring history from curvature extrema. However Leyton presents over 600 pages of rules for inferring history from any object. His rules have been used in over 20 scientific disciplines such as radiology, meteorlogy, computer vision, chemical engineering, forensic science, linguistics, and archaeology. Ordering Leyton's book at Amazon