Object Recognition Using Three-Dimensional Information

ABSTRACT

This rarer describes an arproach to the recognition of stacked objects with planar and curved surfaces. The range data of a scene are obtained by a range finder. The system works in two phases. In a learning phase, a scene containing a single object is described in terms of properties of regions and relations between them. This description is stored as an object model. In a recognition phase, an unknown scene is described in the same way as in the learning phase. And then the description is matched to the object models so that stacked objects are recognized one by one. Efficient matching is acHieved by a combination of data-driven and model-driven search process. ExperiMental results for blocks and machine parts

are shown.

I INTRODUCTION

This paper describes a method recognition using three-diftenaional scene. Our aim is to deal with scenes the following features: for data which object of a have

1. Objects are placed in any 3-D position with any orientation.
2. Objects may be ·atacked in a scene.
3. Objects have planar and/or smoothly curved surfaces.

Recognition of real objects has been studied aiaing at realization of automatic inspection, asseably and so on. For this purpose, the recognitim. 111ethod should be flexible and efficient enough to analyze scenes with stacked objects and recognize them. It is well known that even recognition of a a~ple object is not easy if the object is allowed to rotate in 3-D apace. The shape identification methods using a monocular gray picture [1, 2] assuaed uny constraints on input scenes. Recognition of scenes with stacked objects was studied for simple scenes [3).

If range data is available, more flexible recognition can be achieved because 3-D shapes of objects are directly obtained. In order to analyze a scene with multiple objects occluding one another, it is often necessary to make a scene description which includes useful inforution for

Masaki Oshima and Yoshiaki Shirai

Electrotechnical Laboratory 1-1-4, Umezono, Sakura-mura, Niihari-gun Ibaraki, 305 Japan

recognition. There have been several studies on scene description using range data [4-12]. Some methods assumed planarity on objects [ 4, 10, 12 ] . Sugihara (9] rroposed a way for trihedral objects. Agin [S], and Nevatia and Binford [6] described a scene including curved objects with generalized cylinders. Although the method is advantageous in describing body which possesses considerable elongation, there may arise some difficulties for other kind of objects. We have developed a ~ethod which describes a scene with planar and smoothly curved surfaces [8]. The method is applicable to general scenes with real objects. Recognition of objects usually requires pattern matching process: matchin& a part of a scene description to a part of an object model. The control strategy for matchins is important in processing a complex scene. The blind search is inefficient under circumstances where objects are stacked and the position and orientation of them are not known a priori. Our system, at first, tries to set reliable and useful features of a scene and to match them to ~dela so that the result may suide the further processing. Thus the system realizes flexible and efficient recosnition.

II OUTLINE

The system works in two phases: learning and recognition as shown in Fig. 1. In learning phase, known objects are shown to the system one by one. The system makes a description of a scene in terma of properties of regions( surfaces) and their relations. The description is stored as a model of an object. If one view is not enough to build a model of an object, several typical views are shown. In recognition phase, the system makes a description of unknown scenes in the same way as in learning phase.

The systea selects ~ng unknown regions those which seea to be most reliable and useful for recognition. A part of a scene consisting of these regions is called a kernel( see Fig. 2). Then a model is selected which includes regions corresponding to the kernel. Once a candidate model is chosen, regions neighboring the kernel are searched for by a model-driven matching process. When this process terminates, the system decides if the candidate model is really found or not. This process is repeated until all regions in a scene are processed. Further details of description and matching are described in the following sections.

III DESCRIPTION .Q!. .!£!!!!!

Our range finder employs a vertical slit projector and a TV ea.era to pick up the reflected light. By rotating a projector from the left to the right, many points in a field of view are obtained.

Three-diaensional eo-ordinates of are calculated by triangulation ( Fig. processing (8] proceeds as follows: the points 3(a)). The

1. Group the points into small surface elements and assuming each element to be a plane. get the equations of the surface elements( Fig. 3(b)).
2. Merge the surface elements together into regions( elementary regions, Fig. 3(C)).
3. Classify the elementary regions into planar and curved ones( Fig. 3(d)).
4. Try to extend the curved regions by merging adjacent curved regions to produce larger regions( global regions) and fit the quadratic surfaces to them( Fig. 3(e)).
5. Describe the scene in te~s of properties of regions and relations between regions( Fig. 3(f)).

Fig. 4. Slit image of a scene.

Figure 4 shows an example of a alit image of a scene to be processed, which includes a dodecahedron, an icosahedron, and a cylinder. In Fig. 5 elementary re~ions of the scene are shown.

The properties of a region consist of: (a) type of a surface fitted to the region( planar or curved, and type of quadratic curve for curved region)

• (b) equation of the surface in a 3-n space.
• (c) 2-D properties of the region( area, perimeter, compactness (4~rea/perimeter'), mean radius, standard deviation of radii, minimum radius, and maximum radius, etc.)
• (d) three-dimensional centroid of the region
• (e) number of adjacent regions.

The relations between regions consist of:

• (a) adjacency
• (b) type of intersection( convex or concave)
• (c) angle between regions( For non-planar regions, planes are fitted to them.)
• (d) relative positions of the centroids.

The matching section. properties and relations process described in are the used in following

III HATCHING

A. Selecting .!. ~ .!!!!!_ assuming the ~ probable .!!!2.!!.!!

The system firstly selects the most promising region. The criterion is based on the type of the region, the area of the region, and the number of adjacent regions in the following manner. We consider that planar regions are more reliable and useful than curved ones because the relative directions of planar surfaces of an object are consistent under rotation of partial occlusion. Regions with larger area are also better because properties of larger regions are leas sensitive to noise. Regions with many neighbors are also more useful because many relations can be used in matching. For each region s,, the following function is calculated. The region s, which aaximizea the function is selected as a part of the kernel:

A(Si) and N_(s~) are the area of a region s, and the number of adjacent regions respectively. Ao ·A· and /.1 are weights.

The model to be selected must have a region that corresponds to s,. Suppose the region St has no neighboring regions. Then the kernel contains only one region. Let M~ denote i-th region of j-th aodel. The dissimilarity between Si and M~ is evaluated by the differences of their properties defined in section 3. Let ~ denot~ l-th property of a region and n denote an operator to evaluate the difference between property values. The system calculates the following function:

The system selects a model if the value is small enough. small, the assumption fails. which minimizes fa If the value is not

If the region SA has neighboring regions, the evaluation function should contain the relations between regions. Among neighboring regions a region s( is picked out which maxi~izes Eq.(l); Now the kernel consists of SA and SA· Let H~ denote a neighbor of "·J , and q.,. denote 111- h relation between regions. (the relations are defined in section 3.) The system calculates the following function:

where 2)~ denotes a weight,

i f.' The system selects a model which ~inim zes if the value is small enough.

B. Verification ~ assumption

The system verifies an assumed model by matching the regions around the kernel to those of the model. Since some regions of the ~del may not be seen in the scene, regions in the scene are picked up one by one, and are matched to those of ·the model object.

Starting from a kernel, the system tries to establish a correspondence between scene regions and model regions and to find all the regions of the object in the scene. At each step, the system selects a new region S~ among those which are adjacent to known regions (that is, the regions which have been selected and matched in the earlier steps). Again,Eq.(l) is used for the selection of a new region.

Whenever s~ is selected from the scene, the corresponding region is searched for in the model. The search is based on the dissi~ilarity function which evaluates dissimilarity of properties and that of relations between s~ and supposed model region Mu.; ( see Fig. 6).

The function compares properties of the region p (S~) with that of the region in the model p~(M~). The function also compares relations q (~,s,) between s~ and the known regions S· of the same object with those q.,.(M"'i ,M (i) of the corresponding regions Mw; and M~ in the model. Suppose the number of already known regions is K. The dissimilarity of region s~ and M~- is defined as follows:

where ~ and T.,.. denote weights. Note areas are used as weights so that more regions contribute more to f 3 · that the reliable

The region with ~inimum f 3 is chosen. If the value is small enough, the match is considered to be acceptable. Generally if a surface of an object is not fully eeen, the region may not pass the teat and it may r~in unknown. However, if a plane is partially occluded by other surfaces, the type and the direction of the region are not affected by the occlusion. Such a planar region, therefore, is determined to ~atch a model region . if the dissimilarity of corresponding relative direction is sufficiently small, 3-D position correspondence is good enough, and the area of the region is less than that of the model.

When a matching process for a model te~inates, the system checks if the assumption is acceptable or not. If enough portion of the model is found, the syste~ concludes that it has found an object that is identical to the assumed model. The position and orientation of the object are calculated from the correspondence of the regions.

V EXPERIMENTAL RESULTS

Experiments are made to recognize two kinds of scenes: one with blocks and one with machine parts. In the first experiment, ten kinds of objects with planar and/or quadratic curved surfaces( shown in Fig. 7) are used for object models.

Figure 8 illustrates an example of a description of a model. The result of recognition( which corresponds to Fig. 4) ia shown in Fig. 9. The first two letters in a region indicate the model object and the letter in the parentheses indicates the corresponding region in the model.

In the second experiment. machine parts( pulley. liner. piston. and conrod of a car) are used for object models. Figure 10 shows an example of an input image. Figure 11 shows elementary region' In Fig. 12, the result of recognition is several similar scenes were The processing time for shown in Fig. 10 is about and 1 min. for matching. shown. Experiments for so far satisfactory. a typical scene such as 3 min. for description

..

Fig. 11. Elementary regions.

VI CONCWSION

We have proposed a system to recognize stacked objects using range data. The system describes a scene in te~ of planes and anoothly curved surfaces. Models of objects are built in the system by shoving the. one by one. Objects are recognized by aatching the description of an input scene to those of models. The matching program picks up regions Which are .oat reliable and useful for recognition, and aatches thea to those of a aodel object. Once a candidate model is chosen, then by a guidance of the nodel, the rest of the scene regions are searched for. Thus the system has realized flexible and efficient recognition. The result of experiments shows that this scheme is prottiaing.

ACKNOWLF.DGEMENTS.

We would like to thank the members of the computer vision section at the Electrotechnical Laboratory for their helpful discussions.