An ATN Model for 3-D Recognition of Solids in Single Images

1. Introduction

In this paper the use of an Augmented Transition Network ( ATN) model for image interpretation is discussed; a procedure for the 3-D recognition of randomly oriented rigid bodies with known geome­ try is described.

ATN models are mainly used in natural language un­ derstanding and speech recognition [ 1]. Here, we argue that the advantages of the Ani formal ism, namely its perspicuity and generative power, can also be brought to bear in the domain of patterns and models with more than one dimension. Syntac­ tic approaches to pattern recognition are thought of as being less aporopriate for 3-D object recognition "since it is not obvious how to incorporate in it mechanisms for relating 2-D images to 3-D objects" [ 2]. It is shown in this paper that such mechanisms can harmoniously be embedded into the ATN framework by doing the in­ verse: calculating 2-D instantiations from a 3-D model.

• The research reported in this paper has been supported by the Bundesministerium fur For­ schung und Technologie under contract No. 4135839-08IT10270. Responsibility for the content is with the authors.

The approach is based on the idea of analysis-by­ synthesis[ 3l.Knowledge of the pattern generation is stored in the model. Hypothetical model instan­ tiations are referred to as prototypes. Proto­ types are created. If the similarity between a prototype and the actual data to be analyzed ·exceeds some threshold, the prototype is con­ sidered the model instantiation for the actual pattern data. Otherwise it is layed aside and another prototype is taken into consideration. As a rule, a problem arises by the tremendous amount of orototypes to be considered. A solution is an analysis-by-synthesis search procedure as sketched in Fig. 1: Prototypes are partially built up. Partial prototype data are compared with pattern data in order to compute a similari­ ty measure to guide the selection of the partial prototype which is to be developed in the next step. The Fig. 1 feedback loop is essentially a process of hypothesis generation and verifica­ tion: based on the partial prototype selected and using the constraints imposed by the model, hypo­ theses are generated to be verified by the pattern data.

We suppose that the pattern is represented as a list of primitives (extracted in a preprocessing stage) that are associated with geometrical pro­ perties (position, orientation etc.). The ATN ap­ proach presented here is an extension of a 2-D model described earlier [ 41 dealing with corner primitives which later has been extended by straight line segment and circular arc orimiti­ ves [5]. Additionally, points can be incorpora­ ted as orimitives which can be either the central ooints 'associated with circular arcs (ellipses in 2-D) or simply corner ooints ignoring the direction of the associated edge lines.

The basic idea for the recognition of rigid bodies is as follows: when following a path through the transition network from the initial state to a goal state, any CAT-arc (see section 2.2) is associated with the placement of a nri­ mit i ve in 3-D space. Thus, the number of degrees of freedom of an object model is more and more constrained until the object is fixed in 3-D. After fixation, the rest is hypothesis verifica­ tion by checking pattern primitives at clearly defined places of the image plane.

The following example is convenient for explana­ tion. For the sake of simplicity, ambiguities are at first neol ected in the fallowing. We assume that only point primitives are used and parallel projection is provided; point occlusion is neglected. After the fixation of the first point P 1 in 3-D, the second point P 2 to be fixed must l1e on the surface of a sphere whose radius is known. Therefore the second pattern primitive point must lie within the corresponding circle in the image plane. Having chosen such a ooint, we know (neglecting ambiguity) the axis P 1 -P 2 . The object has now the freedom to rotate around P1-P2· The third point P3 (not lying on Pl-Pzl. must lie on a circle around the P 1 -P 2 axis wh1ch in projection is an ellipse. Having selected a pattern primitive point close enough to the ellipse, the object is fixed. The remainder of the path is verification.

After verification, the data are smoothed in order to get a more precise interpretation. In this respect, the method is similar to the RANSAC (random sample consensus) approach to model fit­ ting, in which estimates of the model parameters are generated using as small an initial data set as feasible; after verification, an improved fit by applying a smoothing technique is computed [6].

In the following, the main components of our system for the recognition of solids with known geometry are described: model and search.

2. Model

The model is decomposed into a purely geometrical model and a generative model. The geometrical model describes the object which is assumed to be in a randomly chosen position in 3-D space. The generative model is needed for controlling the analysis-by-synthesis procedure.

2.1 Geometrical model:

Rather than relying on a set of characteristic views, we use a single geometrical description of the object. We aim to use a description as usual in the CAD field. Thus, the teaching phase for in­ dustrial part recognition could be reduced to merely typing in the generative model with asso­ ciations to some specified geometrical model ele­ ments. As a first step, we have chosen a poly­ hedron description such that any (hidden-line)- 3-D view of the part can be calculated. Many real work pieces fall into the polyeder class or can be described sufficiently well in terms of planar or slightly bent surfaces with straight edges.

2.2 Generative model:

The generative model is represented as an Augmen­ ted Transition Network. It describes several al­ ternatives of model-to-pattern primitive asso­ ciation sequences. We use a somewhat more general representation than in our early aoproach (4]: in­ stead of describing a sequence of specified model Primitives (for example COrner!, edge3, ... ), we rather prescribe the category of primitives (for example corner, edge, ... ).

The network is augmented with a set of registers holding arbitrary information to keep track of the model-to-pattern primitive associations carried out. From these associations, informa­ tion is deduced about how the position in 3-D space is constrained and hence what constraints are imposed on the pattern primitives to be selec­ ted further. The registers contain also supple­ mentary information necessary to perform additio­ nal tests on the primitive data and to collect the information for the final image description.

The ATN consists of states, arcs, a dictionary, named registers, actions, and conditions.

Some comments on the arcs, the dictionary, and the named registers are given.

Arcs: we use the usual CAT-, JUMP-, SEEK-, and SEND-arcs (following Winograd's notation (7]). Additionally, CATegory-PHANTOM-arcs are defined as transitions by introducing a phantom pattern primitive.

Named registers: among other things they contain - po1nters to dictionary entries

• parameters

An example

The transition network model for the recognition of solids assumes oarallel projection. On its highest level the ATN has the form shown in Fig. 2. The recognition of a solid is done in three steps. In the FIX-phase (t-100-1), the object has to be fixated in 3-D space. It yields the hy­ pothes is of the solid's position and orien­ tation. In the VER-phase (MOD-2), the hypothesis established in the FIX-phase is verified. In the SMOOTH-phase (MOD-3), the data are averaged to obtain a more precise result.

CAT -arcs can be real aced by SEEK-arcs if conven­ ient. To cope with broken pattern lines, for in­ stance, an edge arc can be replaced by an edge net1~ork. For edge fragment composition the proce­ dure descrihed in [9] is appropriate and easy to incorporate into the ATN framework. Especially in the verification phase one could even think of invoking a special line finder or local feature detector. As the line is conjectured to be in a well constrained neighbourhood, line following should be possible even in highly corrupted image data.

3. Search

The search is based on the state-space search technique [10]. In the following, norles are refer­ ring to the search tree, state~rl arcs are referring to the ATN. Registers are associated with nodes.

Each node N is associ a ted with one state SN, its successor nodes N;, i=l,2, ·· nN are associated with one successor state of SN. Thus, a path from the root R to a goal node is associated with a path through the ATN.

With each node N a subspace of the sf x dimensi a­ nal position and orientation space is associa­ ted. This is imrl icitly done by a set of model-to­ pattern primitive associations [ P; ,pj] (P;: model primitive, Pj: pattern primitive) that are encountered in th~ registers when following a path from the root R of the search tree to the node N. Along this path, the position and orien­ tation space is successively reducerl.

Two basic restrictions are imposed on the [ P; ,Pjl associations:

RES1: Pi and P; are of the same category (e.g. both are i!dges)

RES2: On any path from the root to a goal node, each model primitive is encountered exact­ ly once.

Additional primitive selection restrictions will be introduced helow.

Expanding a node N:

sNCATs~

1. Select a set P of model primitives (the cate­ gory being prescribed by the arc) so that the primitive selection restrictions are not violated.
2. For each P; EP calculate the geometrical con-

straints imposed on the pattern primitives to be associated with P; (including visibili­ ty, which can always be done in the VER­ ohase l .

1. For each P· satisfying the constraints (within some.l tolerance) , a successor node with state s~ 1 and association [p. p-l i s created. If there is ambiguity about 1 't~e in­ terpretation of the position and orientation subspace reducti on introduced by the associ a­ tion, all possi hil ities are stored in an alternative register . When necessary (may be further down in the tree l, for each pass i b l e interpretation a succe ssor node is created accordingly.

S CAT- PHA~ITOMs· N N

Step 1 as above

2. For each P ·EP calculate the geometrical r ro­ perties of the phantom pattern primitive Pj·

'3. For each P;, create a successor node with state s'N and associat·ion[P;,ojl·

JUMP, SEEK, and SEND arcs produce one successor node.

Missing primitives are coped with because the FI X­ network incorporates many alternatives of fixa­ tion. For instance, in the Fig. 2 example pattern points [P 1 ,P 2 ,P 3 ] or [ P 3 ,P 5 ,P 6 ] could be chosen for fixation.

\~e use a best first strategy based on a value f which is a measure of similarity that evaluates how well the (partial) prototype fits the associa­ ted model data. Among other things,it takes into account how many phantom primitives &re associa­ ted with visible model primitives.

How to avoid doing the same thing twice?

The goal is to restrict as heavily as possible the primitive selection in order to speed-up the search.

• A l The procerlure described so far does not take into account the case that the same interpre­ tation results when using different sequences of the same [P;,P·l-associations. The approach we actually us~ i s a modification of an idea found in [ 11].

It consists of defining a unique sequence for any subset of_[P;,Pjl-associations. A~ o?vious choice is to 1mposl! a monotony restnct1on on a quality measure q(j) of the pattern primi­ tives within a category. q(j) is calculated in the preprocessing stage and can take into account, for example, the length and contrast of an edge, or the sharpness of a corner. The restriction applies within the FIX- and VER­ phase independently. (Note: the restricti?n is not applicable for all ATN structures; 1n the above example it can be used).

1. An additional source of unnecessary work stems from the fact that the same (or about

the same) position and orientation hypothesis results from different sets of [Pi ,pjl asso­ ciations. To avoid this, at the end of the FIX-phase a hold list of such hypotheses is updated. The arc is inhibited if the hypothe­ sis within some tolerance t already exists.

At this point, an obvious idea should be out1 i ned: Clustering approaches have been reported to be robust even under poor conditions (till now for 3-deqrees of freedom) [ 12] . Why not use the hold list for clustering the position-orien­ t ation hypotheses if clusters emerge? It seems promising: for undistorted data, the orocedure runs in some depth first manner; for highly ambiguous data, where many tree branchinqs are in­ troduced, more hypotheses are calculated and clusters may arise that are helpful for guidinq the search.

Note: Method B) no 1 anger ensures that the opti­ maTSolution will be found; speed-uo is qained at the expense of suboptimal ity where the error in­ duced (by method B) is held within a known hound depending on threshold t.

Addition a 1 qenera 1 speed-uo techniques are opti o­ nall y used; . their effectivity has been demonstra­ ted for one-way transition diagrams and 2-D

models [13] .

4. Discussion

!~e have shown that the ATN framework is well suited to incorporate special geometrical know1 edge as well as genera 1 semantic knowledge !or image analysis tasks. The difficulty of relat1ng 2-D images to 3-D models is avoided by doing the inverse : calculating 2-D prototypes from 3-D models. This inversion means outting the burden on search; we use a state-space search technique. Here, much speed-up is gained - without getting gross errors - by recognizing not only identical subspaces but even subspaces that contain simi­ lar prototypes. Incorporating cluster technTqli"e$ fits well into the framework and seems promising

in highly ambiguous data.

For copinq with missing pattern orimitives, phan­ tom primftives are created where possible. In­ stead of handling the pattern data directly, the procedure is actually· dealing with prototypes which comply with the a priori knowledge. (Depen­ ding on the similarity measure chosen, the proce­ dure decides upon a prototype with not too many phantom elements that should be visible). The final image interpretation is derived from the model instantiation rather than from pattern data .

Similarly, general knowledge such as 1 ine label­ ling rules can be incorporated; illegal oattern situations do not necessarily lead to a dead end because legal phantom elements can be created. yes-or-no rules will enhance the performance

Due to this error tal erance, introducing strict even when dealing with distorted pattern data.

Soecial knowledge such as problem dependent rela­ tional constraints can be introduced perspicuous­ ly in the form of ATN conditions, they may be re­ presented as a relational constraint network in­

stalled in the dictionary.

The main difference between our approach and those reported in the blocks world 1 iterature is that our approach allows coping with heavily distorted image data. This is the case with real world workpieces (see Fig. 3). Initial topology tests as described in Roberts [14] are not very useful here because they are too susceptible to data distortion. We may use objects with a less constrained geometry. Searching for consistent 1 abell inqs in 1 ine drawings usually does not pro­ vide enough information in industrial applica­ tions. Thus the results of the blocks worlds re­ search alone are not sufficient for our purposes. However, they are used to assist the recognition process, through rules incorporated into the ATN dictionary.

As a starting ooint, our ATN-based system for the

recognition of solids provides a good base of an image analysis program to be successively augmen­ ted by more genera 1 semantic knowledge and know­ ledge of the doma i n. Programs are being implemen­ ted.