Extraction of the Line Drawings of 3-Dimensional Objects by Sequential Illumination From Several Directions
Proceedings of the Second International Joint Conference on Artificial Intelligence. Pages 71-78.
© 1971 International Joint Conferences on Artificial Intelligence
Abstract
The extraction of the line drawing of }-dimensional objects presented here is developed for the eye of the intelligent robot studied in the Electrotechnical Laboratory. This procedure consists mainly of two processes. First, four line drawings of the same objects illuminated from four different directions are sequentially obtained. Second, by applying 2-dimensional logical operations to these line drawings, a complete one is extracted. This method is applicable to more then two polyhedrons in a scene which is difficult by usual methods heretofore presented because of too small difference of light intensities between · two different planes or the effects of shadows.
- J. McCarthy et al. "A computer with hands eyes and ears", AFIPS Conf. Proc., Vol.33 (1968).
- N.J. Nilsson "A Mobile Automaton", International Joint Conf. on Artificial Intelligence (1969).
- S. Tsuji et al. "Industrial Eye" Conf. of Inst. of Electric Eng. (1970).
- Y. Suzuki et al. "Industrial Eye Joint Conf. of four Electrical Institutes (1968). 1" '
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. Introduction
The recognition of }-dimensional objects is necessary for intelligent robots that manipulate objects in re lation to visual information. Cp to now the r~cognition of a simple polyhedron based on its line drawing has been studiM by lighting it so that the effect of shadow is eliminated.(l),( 2 )The ex traction of a complete line drawing is, however, very difficult because of too small differences of light intensities between .two different planes or the effects of shadows. The improved method presented here for extracting the line drawing consists of two steps. First, by lighting the objects from several di rections sequentially, the line drawing for each illumination is extracted. Next, only useful information is ex tracted from the obtained line drawings. This method has been developed for the eye of the intelligent robot studied in the Electrotechnical Laboratory. (J)
The outline of the whole procedure is shown in Fig.l. Each block in Fig.l is described in the following sections.
2. Data input
A vidicon TV camera is used as the visual input device. A preprocessor( 4 ) (Fig.2) is employed to transfer the video signal to a computer. This preprocessor divides a picture frame into 256 x 256 picture elements and digitizes the video signal of 64 x 64 elements to 6 bits (64 levels of light intensity) in one scanning period. The region of a picture frame to be sampled is controlled by a computer.
3. Extraction of a line drawing illuminated from one direction
The procedure to obtain a line drawing, which is represented by a set of equations of lines, consists of (1) smoothing, (2) spatial differentiation, (3) filtering 1, (4) thinning, (5) filtering 2, (6) tracking and (7) line fitting. Each stage is described below.
( 1) Smoothing
This stage is to eliminate the noise of the vidicon camera and the prepro cessor, by applying a 3 x 3 nonlinear filter to the picture elements. Let the element of the J x 3 matrix be denoted as in Fig.J and the value of the picture element corresponning to the matrix element i be nenoten by C(i). Th e filter is to compare C(O) with the other picturp elements C(i), i=l, ... ,8 , and if neces sary correct C(O}. The criterion of the correction is based on the fact that the object is a polyhedron. Therefore , the fine structure of brightness as shown in Fig.4 may not exist. If the condition shown in Fig.4 holds, C(O) is correcten as follows.
The filter is applied to every picture element repeatedly until the correction is no longe r required. This smoothing operation eliminates the chan,c of brightne ss caused by nois e , but preserves the resoluti on of the picture which is lost by the usual smoothing metho rh.
(2) Spatial Differentiation
The 2-dimensional nifference of light intensity at each picture element D and the direction of the gradient K are calculated by the 3 x 3 array as follows.
The direction of the gradient is digitized as
Thus the value of D is large at the picture element corresponding to the edge of the object, and the nirection of the edge is nearly perpendicular to the di rection of the gradient. The result of spatial differentiation is illustrated in Fig.S.
(3) Filtering 1
If a picture includes an edge, the picture elements with large D constitute a line whose width is larger than 2 elements. Based on this fact, the noise is eliminated by the 3 x 3 filter. Let D(i) denote the value D of the C(i), filter 1 corrects D(O) to 0 if among its anjacent D(i)(i=l, ... ,8), mor e than five D(i) take value 0.
(4) Thinning
The edges of the objects are detect ed by filtering 1 such that the D of each element distributes like a ridge whose center corresponds to an edge. The thinning is to detect ihe peak of the D and correct the other D to 0. The algorithm is to detect the segment of the line formed by the picture elements and to examine sequentially the adjacent element toward its perpendicular direction to determine whether or not the D of the element is to be corrected. For a detailed description, the definitions are given in the following:
- The direction perpendicular to K is dentoed by L.
- Two elements which are adjacent to an element in the direction L are denoted by .(_and {' respectively, and those which are adjacent in the direction K are denoted by k and k'.
- Let K(i) denote the value K of the element i; the element 0 is the line segment with error d if and only if the following two conditions are satisfied.
- I K(f}-K(O)I S d, 2. IK((' )-K(O~~d. The correction of D(k) and D(k') is based on the 3 x 3 arrays of elements where k and k' are defined in (b). The cor rection algorithm of D(k) is as follows.
- )} If the element is the line segment with error 3, then L2); otherwise no correction.
- l2) If I K(k)-K(O)I~J, then (J); otherwise no correction.
- J If D(k)!Da(Da is constant), then (4); otherwise no correction.
- 4 If D(k)<Da, then (5); otherwise l6).
- 5 If IK(k)-K(OM~2, then D(k)=O; otherwise (6).
- 6 If the element k is the line segment with error J, then D(k)=O; otherwise no correction.
The correction of D(k') is just the same except k is replaced by k' in the above algorithm. This rather complicated algorithm is required in order to preserve the true line segments near the crossing point of more than two lines.
(5) Filtering 2
For the elimination of the noise from the obtained set of D and K, the J x 3 filter is applied to the each element. The operation of the filter is to correct the D of the element to 0, (1)· if more than 7 adjacent elements' Dare 0, or (2) if both D(e) and D(i') are 0. In case (1) , the isolated points are eliminated, while in case (2), those points which do not constitute a line are eliminated. This obtained result is illustrated in Fig. 6.
(6) Tracking
A set of elements which constitutes a line is picked up by tracking the element sequentially based on the D and K of the element. The starting point of the tracking must be on the line. Scanning each element by the 3 x 3 array, the starting point is decided as the center element of such an array to satisfy the following two conditions.
- I KU)-K(O)I~l or IK((.')-K(O)IS 1
- l K( i )-K(O)I~ 1 for i such that iE{{,~-l,f ... l} nnd iEtt',f-1,.('+1} From the starting point the element is
tracked toward the direction L(O), and then toward the opposite direction until the terminal point is found. The tracking algorithm is shown in Fig.7, where initial value o< 0 =L and n 0 =constant.
(7) Line Fitting
From the sets of elements each of which constitutes a line, the equation of the line is obtained by ihe least squares method. In order to simplify the calculation without a great deal of error, the equation is represented as y=ax+b or X=ay+b such that a~l. The obtained line drawing is illustrated in Fig . 8 .
4. Synthesis of the Desired Line Drawing
The desired line drawing is defined such that it includes all the edges of the polyhedron and no others. In order to get the desired line drawing , the autho~proposes the following 2-di mentional operations. They are the logical OR( T) and logical AND(·) of two line drawings . Let A and B denote the two line drawings; the function of each operation is as follows.
- OR: This operation synthesizes the line drawing that includes all the edges included in both A and B. Although the lines in A and B which correspond to the same edge do not necessarily occupy the same place in the drawing, they must be regarded as the same edge. For example, the result of OR operation of the line drawings A (Fig.8) and B shown in Fig.9 (this is denoted by A+B) is shown in Fig.lO.
- AND: This operation synthesizes the line drawing that includes only those edges that are included in both A and B. The result of the operations of A and B · (denoted by A.B) is illustrated in Fig.ll.
The philosophy of synthesis of the desired line drawing is to extract the useful information from 4 line drawings which are obtained by lighting the objects from different directions. Let A, B and C denote the line drawings obtained by lighting from different directions , if the position of the shadow in A is different from that in B, the result of A·B includes no lines caused by the effect of the shadow . Although each A, B or C alone may not include edges whose adjacent planes have the same light intensities, every edge is included in either A, B or C. Therefore, the result of (A+B+C) includ e s every edge. On the other hand, if the objects are lighted from the frontal direction, the obtained line drawing D is fre e from the effect of the shadow. Thus, the operation sequence to synthesize the desired line drawing E from D and the othe r 3 line drawings ob tained by lighting from diff e rent di rection A, B and C consists of th e next 6 steps.
| 1 F=A·B, | 2 E=F+D, |
| 3 F=A·C, | 4 E=F+E, |
| 5 F=B·C, | 6 E=F+E |
The result of this sequence using A(Fig.8) , B(Fig.9), C(Fig.l2) and D(Fig.l3) is illustrated in Fig.l4.
The block "Set the lighting" in Fig.l is, therefore, to get the line drawings A, B, C and D, and the block "Indicate the logical operation" is to perform the above described sequence.
5. The procedure of the 2-dimensional logical operations
There are mainly two methods for the previously defined logical operations such as the one at the line drawing level and at the intensity array level. For simplicity of the procedure, the latter method is adopted heri!.
The procedure of the logi~al 6per ations previously defined .is as tollows. First, the line drawing is mapped .to the array of the differentiation. The element of the array .that corresponds .to a line segment of the line drawing is given value D1 and the direction of the lirie L, and the ·adjacent element . is given D2 (Dz<Dl) and L. The result .of this operation is just the same as oqtained in spatial differentiation described in 3 - (2), except that it includes no noise. The operation OR of A and B utilizes the two arrays thus ·mapped from A and B, respectively, to make a new array by adding the two arrays. · Then, by applying the previously described thinning, tracking and line. fitting to the new array, the result of OR is obtained. The operation AND ,i ,s just the same as OR except that the new array is made such that if D=O at one of the corresponding elements of two arrays, then the value of the corresponding new element is 0. Thus these operations regard the two lines, in A and B, as the same ed~e even if their positions are slightly different from each other. .,This method is very simple because only new algorithm to be de veloped is to map the line drawings to the array of differentiation. The other algorithm such as thinning, tracking and line fitting are just the sam~ as described in s .ectio.n 3.
6. Conclusions
The extraction of the .line drawing by sequential lighting from s .everal directions is proved to be applicable to a scene where . objects are placed behind other objects. The desired line drawing of a few types of prisms and pyramids are obtained by lighting from the left, right, up and front sequentially. The calculation time is about 10 times as long as that of obtaining a line drawing illuminated from one direction. Though it takes at present about 2 minutes. by NEAC-3100 (cycle time is 2/-{ sec, 32K core memory), a large part of the calculation can be processed by special purpose hardware. Application to more compli cated objects may be possible if the present resolution of a picture (64 x 64) is improved.
Acknowledgements
The authors would like to express appreciation to Mr. M. Suwa and Y. Suzuki who provided them with an excellent hardware system.
@inproceedings{ijcai1971p8,
title = {Extraction of the Line Drawings of 3-Dimensional Objects by Sequential Illumination From Several Directions},
author = {Shirai, Yoshiaki and Tsuji, Saburo},
booktitle = {Proceedings of the Second International Joint Conference on
Artificial Intelligence, {IJCAI-71}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {D.C. Cooper},
pages = {71--78},
year = {1971},
url = {https://ijcai.org/proceedings/1971/8},
}
TY - CPAPER TI - Extraction of the Line Drawings of 3-Dimensional Objects by Sequential Illumination From Several Directions AU - Shirai, Yoshiaki AU - Tsuji, Saburo T2 - Proceedings of the Second International Joint Conference on Artificial Intelligence, IJCAI-71 PB - International Joint Conferences on Artificial Intelligence PY - 1971 SP - 71 EP - 78 UR - https://ijcai.org/proceedings/1971/8 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: