A Theory of the Origami World

1. INTRODUCTION

This paper presents a brief summary of a theory of the Origami world[4], a model for understanding line drawings in terms of plane surfaces and for finding their qualitative 3-D shapes by assigning the labels (+, -, 1 or I) to each line. The labels signify the physical meaning of the lines (Huffman [2)): the label+ stands for a convex edge, -for a concave edge, and tor ' for an occluding edge.

The theory is an extension of the work of Huffman [2) and Mackworth[6], but the feature is that it is surface oriented, that the precompiled knowl­ edge is all contained in the augmented junction dictionary, and that the labeling is all symbol­ ically performed using the filtering procedure not only for a consistency check of junction labels as in Waltz[7) but also in the consistency check of surface orientations in the gradient space.

2. SUMMARY OF THE THEORY OF THE ORIGAMI WORLD

2.1 Surface-oriented Assumption

An important feature of the Origami world is that it is surface oriented. This idea can be best illustrated by Fig. 1. Though it appears perfect, the Huffman-Clowes-Waltz labeling scheme for the trihedral world cannot handle it. The reason for this failure is that the trihedral world essentially assumes solid objects, and thus the picture of a box would need to be "super" perfect, as in Fig. 2, in order for it to be handled.

The assumption concerning the geometrical configu­ rations around a vertex in the Origami world is as follows. The planar surfaces meet edge to edge, no more than three surfaces of different orienta­ tions meet at a vertex, and the combination of the three orientations is general in the sense that they span the three-dimensiona 1 space. Let us call such vertices up-to-3-surface vertices .

Figure 2. A ''super-perfect'' line drawina of the "box" scene for the trihedral world.

2.2 Legal Junction Labels for Up-to-3-Surface Vertices

Once we recognize the basic assumptions of the Origami world, we can generate the junction dictionary, as in the Huffman-Clowes-Waltz theory, which contains legal junction labels (i.e., possible line-label combinations) for each junction type. Table 1 gives an idea of the degree of constraints imposed by the up-to-3 surface vertices compared with the trihedral vertices.

2.3 Augmented Junction Dictionary

Necessity : A legal junction label represents a possible configuration of surfaces at a vertex. Consistently laheling a line drawing, so that all the junctions are given legal junction labels, is nothing but checking the consistency of surface interconnections hy passing information by means of line labels from one junction to another. The Waltz filtering[?) on junction labels is known to be a good method for doing this. !~wever, the labeling in the Origami world cannot simply rely on the filtering on junction labels. Because of the weaker restriction at the vertices than the trihedral world, a lot of anomalous interpreta­ tions exist in which the labeling is consistent, but the whole configuration is not possihle[6].

Links: The junction dictionary for the Origami world is augmented for more thorough and. global consistency check concerning surface orientations. The surface orientations are conveniently represent­ ed by means of the gradient space[2) [6). To each legal junction label is attached the information as to what constraints in the gradient space should be satisfied by the surfaces incident at the junction. Fig. 3 shows two examples. As shown in Fig. 3(a), the constraints are represented by the links which connect a pair of related regions and which include information about the constraint~ on their gradients. The properties of dual lines of the gradient space are used here.

In such a junction label as shown in Fig. 3(b), which is legal in the Origami world, we have an occluded intersection. It is typicallt a result of folding a planar surface along BC, thus Rl occludes a part of R2. A little more generally, we can include such cases that the interse~tion line of Rl and R2 lies within the angle ABC. Therefore, the associated link represents that the gradient G2 of R2 should be inside of the fan-snaped area

----------------------------------- * This research was done while the author was visiting Department of Computer Science, Carnegie-Mellon University, Pittsburg, Pa.

whose or1g1n is at Gl, and is bounded by the lines which are perpendicular to AB and BC.

2.4 Labeling Procedure

The labeling procedure of the Origami world uses the augmented junction dictionary. First, the Waltz filtering on junction labels is performed. Then, the procedure begins to assign a junction label, which has been filtered and left, to each junction one by one. When a junction label is assigned to a junction, the constraints represented by the associated links are instantiated by the directions of lines of that particular junction.

Consistency of surface orientations is tested by using these instantiated constraints. The test can be performed by an iterative "filtering" operation defined on a labeled graph called a Surface Connection Graph (SCG), in which a node represents a surface, and an arc represents the instantiated constraint between the surfaces. The feature of this labeling procedure of the Origami world is that all the constraints are maintained symbolically in the SCG during the computation.

2.5 The Results of Labeling

As a result of the labeling procedure, not only a labled line drawing but also a SCG, which is a summarized description of straints on the gradients of the involved we obtain filtered the con­ surfaces.

Let us see a few examples of labeling. Usually we obain multiple labelings. The "cube" scene has three labelings (Fig. 4). The "box" line drawing of Fig. 1 has eight labelings, two of which are shown in Fig. 5. The labeling in Fig. S(a) corresponds to an "ordinary box"; the two front faces form a convex intersection, and partially occlude the rear two faces which form a concave intersection. Fig. 4(b) corresponds to a "squashed box"; the front two faces, as we 11 as the rear two, form a concave intersection.

3. DISCUSSIONS AND COMMENTS

3.1 Origami World and Various Worlds

Assume we have a set of line drawings. We can consider a set of all the combinations in assignments of line labels for those line drawings. A subset exists comprising those interpretations which can be realized by plane surfaces. Let us denote this subset as the Plane Surface World, Spsw. We can also think of a subset, the Consistent Gradient World Scgw, consisting of interpretations in which all the constraints on the graidents of surfaces are completely satisfied. Obviously Scgw :> Spsw.

We can view a labeling procedure as a method con­ sisting of a generator and a tester: given a line drawing, a generator generates interpretations in a certain manner, each of which a tester accepts or rejects based on a certain criterion. Table 2 summarizes various labeling methods (1](2](3](6] [7) according to this taxonomy. Various suhsets can be defined which are generated by generators or determined as legal by testers. Fig. 6 shows the set inclusion relationships among those sub­ sets. The locations of several example interpre­ tations indicated in it can serve to understand the relationships. (See (4) for details).

3.2 Qualitative Shape Recovery

Note that we have only qualitatively recovered the 3-D shapes by labeling drawings. For example, the labeling of Fig. 4(a) represents a convex corner, but it can be either a cube or a skewed rohmboid. In fact, a "cube" scene ( ~), a "trapezoid-block" scene ( c$) and a "house" scene ( (9) all have the equivalent labelings, In order to recover the shape quantitatively we need to introduce more assumptions together with tools for exploiting them.

3.3 "Natural" and "Unnatural" Interpretations

One of the common impressions we tend to have about those multiple interpretations is that most of them are "unnatural", and therefore it is a disadvantage of the theory to allow them. It is true that we do not usually think of such peculiar shapes as Fig. 4(c) and S(b) in interpreting these line drawings. It should be very difficult even to imagine those shapes as possible interpretations. However, any labeling is geometrically no more "natural" or "unnatural" than others, unless we use more assumptions.

The above two points (3.2 and 3.3) are actually closely related problems, for whose solution we need to identify more assumptions concerning image formation process and objects in concern. The recent paper (5] by the author presents a theory and a technique which can recover "natural" quantitative 3-D shapes of an object from a single picture, so that we can generate images of the same object as we would see it from other directions.

ACKNOWLEDGEMENT

I thank John Kender, Allen Newell, Raj Reddy, and Steven Shafer for having very stimulating discussions with me.