Steps Towards the Representation of Complex Three-Dimensional Objects

STEPS TOWARDS THE REPRESENTATION OF COMPLEX THREE-DIMENSIONAL OBJECTS

Ruzena K. Bajcsy and Barry I. Soroka Dept of Computer & Information Science

Moore School of Electrical Engineering

University of Pennsylvania I D2 Philadelphia PA 19174

INTRODUCTION

We are investigating the description of complex three-dimensional objects ln terms of three-dimensional primitives and composition relations between them. Our input is a description of an arbitrary three-space in the form of gray-levels assigned to the points of a cubic lattice. Sequential tomograms are one source of input data, as are serial light and 'electron micrographs.

Our approach is motivated by the observation that a primitive can give rise to only a small number of region types on a plane which cuts it. By inverting the process we can reason from a region found on a slice back to the primitives from which it might have been cut. When the sliced object is composed from several prLmitives, the regions cut by planes will reflect the joints and containment relations between the primitives involved.

AN EXAMPLE

Let us briefly consider right circular cylinders, which are sliced into circles, ellipses (possibly truncated), and rectangles. An ellipse suggests two possible cylinders. The next step in completing the description of space will be to determine which of the suggested cylinders is present (both may be!) and the length of the cylinder axis. This would involve looking at another slice some moderate distance away from the current one.

DESIGN CONSIDERATIONS

• We fORTRAN) features: are constructlng (in LISP and a processor with three useful
• Primitives can be added or changed by altering the function which maps regions into possible primitives. Thus, to add "blocks" to the system, we would add the rules which tell us, for instance, that a triangular region is cut from a corner of a block.
• The strategy for obtaining a complete description of space may be systematically varied. What should the processor do when it discovers two disjoint regions on a single slice? Should it pursue the hypothesised primitives sequentially or in parallel? Furthermore, we would like to incorporate a mechanism which would mimic human abilities to perceive a Gestalt.
• The system should be interruptible so that at any moment we may stop the processor and ask questions like:

What do you know at this point? you going to do next? What will you? What are it tell

Our interest in cognitive iss'ues like (2) and (3) has led us to reject holistic approaches (such as the symmetric axis transform) in favor of a more heuristic approach.

INFORMATION FLOW

• If the--sY"stein ___ '"hypot.hesises the existence of a cylinder, then it may request a slice somewhere out along the axis in order to binary-search for the length of the axis. This request may be performed immediately or it may be enqueued with other requests, depending on th~ search strategy selected. In either case, the outcome of the request must be returned to the . requesting hypothesis for evaluation. We store a deductive pattern (if-then-else) on the property-list of the requestor so that the deduction may be performed as soon as the requested information becomes available.

Some slices are a priaPi more informative than others. The most reasonable initial slice to examine is one through the center of space. Similarly, examining one sllce devalues the slices immediately adjacent to it.

• A region may affect dormant hypotheses (those waiting for unanswered requests). Thus, regions must be able to index into the set of current hypotheses and activate those potentially affected. A hypothesis may be both dormant and active!

CRITERIA FOR EVALUATING PERFORMANCE

We have been unable to find evidence of experiments into human competence and performance on the task our system will handle. Our system should be able to mlmlc human behavior in interpreting slices of three-space. Further, our model of hypothesis formation should account for interpolation given two slices, moderately separated, what is happening in the space between them?

.CQNCLUSION

We have raised here some questions appropriate to the task of developing descriptions of three-spaces from .slices. We have set forth design considerations for a processor currently under development. Further answers and details will be presented at the Conference.