Recognition of polyhedrons with a range finder

1. Introduction

The recognition of )-dimensional objects and the measurement of their parameters are necessary for intelligent robots that manipulate objects on the basis of visual information. The recog­ nition procedure of polyhedrons based on the line drawing of a scene has been heretofore developed~l),( 2 ), (J) However, extraction of a line drawing is difficult, and if even one edge of an object is incorrectly detected, the object may be recognized as a quite different one. ( 4 ) Besides, the constraint of the position, the arrangement and the shape of the objects are necessary for the measurement of their )-dimensional positions and sizes.

In order to measure the )-dimensional position directly, a range finder has been studied, and two typical methods have been developed up to now. One is to project a spot lifht and detect its reflecting light, 5 )and the other is baied on the stereoscopic view.( 6 ) Th~ former takes a long time to get the range of many points of objects becaus e it requires the rotation of a spot beam for the measurement of each point. The latter requires a great deal of calcu­ lation to determine the corresponding points of the two pictures.

The method presented here employs a vertical slit projector and a TV camera to pick up its reflected light. By rotating a projector from the left to the right, the distance of many points in a field of view is obtained quickly.

2. Construction of a range finder

The range finder employed in this study projects a light beam through a vertical slit in a projector at a constant distance from a TV camera as shown in Fig .1.

While the projector is rotated, pictures are sampled by a TV camera at predetermined instances and the infor­ mation related to each picture and a corresponding slit beam angle is stored. If each position of a slit in the picture is determined from a stored picture, then its )-dimensional position can be calcu­ lated by means of trigonometry. The input of picture data is controlled by a computer as shown in Fig . 2, and the video signal of each picture is converted into a digital signal by a preprocessor. ( 7 ) This preprocessor divides the frame of a camera into 256 x 256 picture elements, and 6-l x 6·l elements arf> sampler! in one scanning time.

J. Recognition of polvhedrons

The recognition procedure of polyhedrons based on a set of picture data and slit beam angles involves (1) de­ termination of slit positions, (2) compo­ sition of lines, (J) composition of planes , (4) determination of the position of planes, and (5) composition of poly­ hedrons. In (1)- (J), only picture data are used; in (4), the ]-dimensional position of the plane is obtained with slit beam angles. In (5), the objects are recognized based on the interrelation of planes. There is an alternative process of estimating the distance to the surface for each point and then analyzing the two dimensional field of distance to find surface. This method takes a. long time for calculation of the distance for evely point. The process presented here calculates only the end points of lines to determine the psoition of planes. Each procedure is described in detail in the following.

(l) Determination of slit positions

Each picture corresponding to a slit beam angle is stored in binary form where each picture element is 1 if the light intensity is above the threshold, and 0 otherwise. At first this picture is smoothed to eliminate the effect of noise caused by a vidicon camera or a preprocessor. Let the binary picture element be denoted by the matrix element C(i,j), the output of smoothing operation C'(i,j) is the majority of C(i,j), C(i, j-1) and C(i,j·l). By examining elements C'(i,j) along the jth row, from among the sequences whose clement successively takes value 1, the longest sequence is selected, and its position is established as the center of the sequence. This operation is carried out for every j, and then a slit position is denoted by the sequence of points I(j). Fig.4 illustrates the sequence of points for each slit position of a picture.

(2) Composition of lines

If polyhedrons are placed in the background that consists of planes, a projected slit image is generally composed of lines as shown in Fig.5. In the image, a discontinuous terminal point of a line corresponds to a discontinuous boundary point of a plane and an intersection of two lines corresponds to a boundary point of two adjacent planes. In the first step for composition of lines from the sequence of slit points I(j), discon­ tinuous points are found and each set of I(j) whose elements are regarded as continuous is listed. A set of slit points {I(j), j=js-jej constitutes a line or several adjacent lines. The next step is, therefore, to find the number of lines included in a set of slit points, and the terminal points and the equation of each line. At first a sequence of I(j) which constitutes a line segment is found. This sequence {I(ji), ji=j_ 3 ,j_ 2 ,j_ 1 ,j 0 , j 1 ,j 2 ,j 3 } must satisfy the following two equations:

where~.=l(j.)-I(j ), fl. =constant and 1 1 o Os 6.t=constant. Eq.(l) and Eq.(2) provide the measures of symmetry and linearity of a line segment, respectively.

Starting from this line segment, {I(j), J=j -j } is tracked upward and s p downward until the terminal point of a line is found. This algorithm is, as shown in Fig.6, to track the slit point, sequentially correcting the equation of a line. Fig.7 shows the result of the tracking and Fig.8 shows the lines thus obtained.

(1) Composition of planes

This operation groups lines obtained in (2) into classes whose element consti­ tutes a plane. If slit images a re sampl ed at constant time intervals, then the images of the slits proj ected on the same plane form nearly parall e l lines at constant intervals. Adjacent lines which correspond to slit beam anglesC{i' C\i +l' are grouped into the same class, and then the lines in a class are again di­ vided into different classes based on their intervals. After this operation, each class of lines constitutes a plane. The principle of the above two classifi­ cation algorithms is about the same as that of tracking i n (2); i. e ., at first find the segment of a plane and then examine the next line if it belongs to the plane until the bound a ry line of the plane is found.

(4) Determinati on of the positions of planes

A class of lines obtained in (3) does not precisely compose a plane becaus e of errors in various phases of the procedure. In this stage, the )-dimensional position of each plane is calculated from the class of lines and their correspondi~g slit beam angles. Let a plane consist of n lines and the equation of the plane be denoted t by bx + c = 0. Let L(xi' b, c) denote the Euclidian distance between the plane and a point xi on the ith line, then L(x . , b, c) can be easily calculated. 1 2 Let the integral of L (x ., b, c) be 1 defined as

The coefficients of the equation of the plane, b ancl c, are determine<! by the l eas t squares method so that the follow­ ing value J is minimized.

(5) Composition of polyhedrons

In this process, the objects are recogniz ed and their parameters are measured from the shape and the position of the planes. Although this algorithm depends on the purpose of the particular recognition, an example of finding the shape, size and position of polyhedrons is described her e. First, the background planes are eliminated from the list of the obtained planes. The vertical planes are picked up from the rest of the planes and the ir ge ometrical relation is examined. Kext, the horizontal planes on the vertical ones are found. If a hori zontal plane is found, the shape of the poly­ hedron is recognized according to the shape of the horizontal plane and the adjacent vertical planes. If it is not found, the shape of the polyhedron is estimated from the vertical planes on ly. Once the shape of the polyhedron is determined, its size and position is obtained easily because the shape and position of all the surface planes of the polyhedron are known. The result of the recognition is illustrated in Fig.9.

This recognition procedure has low sensitivity to noise because it utilizes )-dimensional information. The slit image, for example, may be broadened according to the direction of planes. In this case, the center points of the slit image may not make straight lines as shown in Fig.lO. However, based on the 3dimensional position of the planes, the polyhedron is correctly recognized. The result of this procedure for Fig.lO is illustrated in Fig.ll.

4. Conclusions

A range finder is used to project a light beam through a vertical slit on the polyhedrons. Based on the 3-dimensional position of the slit image, the objects are recognized and their parameters are obtained. This method determines not only the boundary of the polyhedrons but also the 3-dimensional position of their surface planes. Thus, recognition is reliable compared with one based on the line drawing of the objects. In addition, this range finder may be used to measure the 3-dimensional position of any point for input to the usual recognition methods The defect of this device is in the mechanical rotation of the slit projector, but the mechanical part may be reduced by using a mirror.

Acknowledgements

The authors would like to express appreciation to Dr. S. Tsuji for kind guidance, encouragement and advice.

Rf'ferences

1. J. McCarthy et al. "A computer with eyes and ~ars", AFIPS Conf. Proc. 33 Part I (1968).
2. C.R. Brice ('t al. "Scene Analysis Using Regions", S.R.I. Artificial Intelligence Group T('chnical Kote 17 (1970).
3. Y. Shirai "Extraction of the Line Drawing of 3-Dimensional Objects by Sequential Lightening from Multidirections", Material No.IT-32, Inst. of Electronics and Comm. Eng. of Japan (1970).
4. M. Minsky et al. "Artificial Intelligence and Intelligent Automata", Progres Rep., Dep. of Electrical Eng. M.I.T. (1970).
5. G.E. Forsen "Processing Visual Data with an Automaton Eye", Pictorial Pattern Recognition, Thompson Book Co., Washington D.C. (1968).
6. L.L. Sutro et al. "Assembly of Computers to Command and Control a Robot", Rep. R-582, Instrumentation Lab. M.I.T. (1968).
7. Y. Suzuki et al. "Industrial Eye 1", Joint Conf. of four Electrical Institutes (1968). ·

t :starting point

Fig.7. The result of tracking