Direction Coding Method And Its Application To Scene Analysis

1. Introduction

Scene analysis techniques in the artificial intelligence field intrinsically have the possibility of being applied to the automation of production lines and physical distribution systems. Many studies have so far been devoted to this area, and have led to the development of prototype intelligent robot systems (1) (2) (3). In the past, we at Hitachi Central Research Laboratory have also made efforts toward developing such robot systems (4) (5) as well as toward realizing industrial eyes involving scene analysis capabilities (6) (7). A number of these have already found practical use in the automation of actual assembly and inspection processes which required unique application of visual

technology.

From this experience, we have noted that the variation of image signals from imaging devices is usually the most significant problem to be overcome whenever we attempt to put scene analysis techniques into practical use. This variation is mainly caused by subtle changes in lighting conditions as well as by the intrinsic characteristics of the imaging device itself as affected by fluctuations in power source and temperature. This variation sometimes has a highly significant influence upon the effectiveness of the scene analysis algorithms, by which objects in the image

* This work is contracted with the

Agency of Industrial Science and Technology, Ministry of international Trade and Industry, as at part of the National Research and Development Program "Pattern Information Processing System".

DIRECTION CODING METHOD AND ITS*

APPLICATION TO SCENE ANALYSIS

Haruo Yoda, Jun Motoike, Masakazu Ejiri Central Research Laboratory Hitachi Ltd. Kokubunji, Tokyo 185, Japan

are ultimately recognized.

In this paper, to begin with an image processing method that can yield stable results all of the time by minimizing the effect of image variation is proposed. Next, an attempt at object recognition by this method is described. The objects handled in this study are mainly parallelepipeds. However, unlike ordinary blocks with blank surfaces, boxes with rather complex pattern information on their surfaces were used. The method proposed here is concerned with how all geometric features, such as position and posture of the object, can be extracted by eliminating the surface information, and how this information on the objects surface can then be recognized.

This method attempted to make maximum use of macroscopic image processing, such as homogeneous processing, frequency distribution calculation, etc., as opposed to microscopic processing such as edge following. Since, it seems that macroscopic image processing is a prerequisite for high speed, stable recognition hardware to be developed in

the future.

2. Direction Coding Method

2.1 Basis of direction coding

It has been demonstrated that the image signal obtained from an imaging device is affected by a variety of factors. The form of the observable brightness signal g(x,y) is usually expressed as follows:

where the parameters a and b denote the contrast and level change respectively. In other words, even if the same scene is observed, the same image value is not expected all the time.

Another important characteristic of the image signal is that the value at each picture element in an image does not possess any specific meaning in the geometric sense. Obviously. only the relation of the image values of a picture element and its neighbors can give geometric meaning. This implies that to extract geometric features from an image it is necessary to provide a means to execute comparison with surrounding picture elements.

The two above facts are drawbacks associated with usual image processing when a brightness image itself is used as an input image. They sometimes make the image processing very complicated.

Consequently, the input brightness image is first transformed into what we call a "direction-coded image" on which almost all subsequent processing is based. In this image each picture element has a geometric meaning.

Similar to the methods that are dealt with in previous papers (8) (9), a direction-coded image is one whose value at each picture element corresponds to the tangential direction of brightness change in the original image. That is, the direction-coded image A(x,y) is obtained by performing the following transformation on the original brightness image g(x,y)

In other words, a direction-coded image is one that has ~ added to the argument of the gradient vector of g(x,y). The reason for adding ~ is simply because the direction of the border line of the brightness change gives a clearer understanding than the direction of the brightness change itself. As a result, the parameters a and b in eq. (1) are eliminated in eq.(2), thus giving a characteristic image that is not affected in principle by the contrast and black-level change of the imaging device.

In this direction-coded image, elements of A(x,y) are designated as code ¢ when 1 v 1 < 9 and where fJ is a small threshold value. That is, code ¢ represents no brightness change. This is because the noise involved in the image has a large effect on the value A(x,y). Figu+e 1 is a schematically drawn image in which the picture elements where A(x,y) # ¢ are represented by unit vectors with arrows and the picture elements where A(x,y) = ¢ by blanks.

In the strict sense of the independence of the direction-coded image A(x,y) from the contrast or level change in a brightness image g(x,y), the threshold value e should be a floating type allowing the value e to be controlled by a certain macroscopic value derived from the image data. In fact, in actual images in which the delicate grey level differences dominate, the subsequent processing sometimes becomes inadequate. To compensate for this situation, it is desirable to determine the threshold value e as follows:

where 0 is a small positive value and D is either a part of or the entire image area depending upon the application. Thus, e becomes a floating value which is proportional to the average contrast for the area D. Consequently, the entire g(x,y) image set is transformed into the identical image A(x,y).

2.2 Transforming into a direction-coded image

In order to transform the brightness image g(x,y) into a direction-coded image by digital computer, the following calculation is adopted for the digital image. Here, the differential values in eq. (2) are replaced by the differences using adjacent 3x3 picture elements as shown in Fig. 2(a):

In our computer simulation, a digital image of 256x256 picture elements, each of which was of 6-bit brightness (64 levels ), was used to yield a direction-coded image whose picture elements consisted of 6-bit direction values(64 directions) as shown in Fig. 2(b). In this image, the numbers 0 through 63 are assigned for the 64 directions, and the number 64 is assigned for ¢ .

If the threshold value e is too small, the direction-coded image A(x,y) is not unique as it is affected by the noise involved in the image. If 8 is too large, even the necessary information will be eliminated. Therefore, an adequate threshold value should be carefully chosen or automatically controlled by the image itself. In Fig.3 the total number of pictur~ elements whose values are not q) is plotted for an actual laboratory scene by changing the threshold value e as a parameter. A steep increase is seen in the curve where e is less than 20 . This is mainly due to the noise existing in the brightness image. From this figure, it can be said that the optimum threshold value is, in general, somewhere between 15 and 20, although it of course depends on the imaged objects and the characteristics of the imaging device used.

Special-purpose hardware for transforming a brightness image into a direction-coded image can be constructed as shown in Fig. 4. In this construction, the threshold value is determined by the image value in the previous scanning frame of the TV camera by using a modified version of eq. (3). This threshold value holds for the present frame period. Thus, the direction-coded image can be obtained in a real time mode by synchronizing it with original input brightness image from a TV camera.

3. Recognition Algorithm of a Parallelepiped

3.1 Principles of recognition

Among actual three-dimensional objects, there are quite a number of box­ like objects, since factories make extensive use of boxes in packing finished products for shipment. Therefore, from the viewpoint of the actual application of scene analysis techniques, especially to physical distribution systems, it is extremely important to refine the recognition algorithm of parallelepipeds.

For simplicity, the recognition algorithm of a box-like object viewed from the top is first described. In the direction-coded image, each picture element represents the tangential direction of brightness change. Therefore, quite a few picture elements with almost the same direction code are arranged on the linear edge line of an object, as long as a brightness difference exists on the.edge line. Figure 5(a) shows a simple example of a rectangular shape, which corresponds to the top view of a box-like object. In this case, the frequency distribution of each direction code gives four peaks for every ~ angle difference, as shown in Fig. 5(b). Therefore, when the four values at ct + ~ i (i=O,l,2,3) are added, the distribution curve gives a higher peak at d = c/.. 0 as shown in Fig. 5 (c) . This angle o4 corresponds to the principal direction of the rectangle, namely the posture of the box-like object.

Even when some other figures like triangles or circles also exist in the same image as a background, the position of the highest peak in the frequency distribution curve in Fig. 5(c) is not usually affected, as the directions of the edge lines of these figures do not possess a pitch of ~ · The situation is quite the same when there are some characters or markings on the rectangular surface. Therefore, it is possible to accurately detect the orientation of the rectangle from the peak point in the frequency distribution curve of the direction-coded image.

The next step is to eliminate all direct\on.cod~s except the neighbors of ~o + lr ~ (~=0,1,2,3). Thus, the edge lines of the rectangle are enhanced because all other background noise and figures are considerably reduced. This processing may be called "direction code filtering". Further processing is done as shown in Fig. 5(d). That is, the picture elements with direction codes of ()( 0 and c/.. 0 + 1t are pr'?,.i ected on the line L whose angle is ()( 0 + -lt , and are counted to yield a frequency curve q. Then, the peaks in the frequency distribution are detected, and the stripe regions are generated so that each region contains an edge line. The regions for the remaining two ed~e lines whose direction codes are do + 2 and c/. 0 + -f-1t are also detected in the same manner. These regions are then used to filter out all other picture elements, thus enabling the edge lines to become more pronounced. After this filtering operation, the determination of the edge lines becomes much easier, and the ordinary method of line determination can be easily applied. Examples of these processes are shown in Fig. 6.

3.2 paral elepipeds

When a parallelepiped placed on a table is viewed from above at an oblique angle, the periodicity of th·e -f angle differences among the edge lines ih the image disappears. However, by extending the above-mentioned algorithm under the following three premises, the recognition of a parallelepiped becomes possible:

1. The imaging device is placed far from the object compared to the size of the object so that the distortion of the image caused by projection becomes negligible.
2. The object is placed on a horizontal plane.
3. The angle 1 ·between the vertical line and the optical axis of the imaging device must be known.

Under these circumstances, edge lines with angles of 0. + -f i (i=O,l,2,3) in the image at r 0 are transformed to edge lines with angles of Pi ( i=O, 1, 2, 3) when viewed obliquely at l' = J , as shown in Fig. 7(a) and 7(b). The relationships between 0( and (3i are as follows:

tan (3i = tan ( d. + f i) cos r (5) where i = 0, 1, 2 and 3.

Therefore, by calculating ~i from eq. (5) with C( as a parameter, the nwnber of picture elements N ( l3i ) at angle /3i are counted from the direction-coded oblique image. Then, the frequency distribution curve N ( {3 0 ) +N ( {3 1 ) +N ( {3 1 ) +N( {3l) is obtained as shown in Fig.7{c) .

The angle c( = d..o at which the frequency distribution curve gives a maximum peak corresponds to the orientation of the object when viewed vertically from the top ( l = 0). Therefore, by using this angle 0( 0 , (3;. is computed from eq. (5) for 0( 0 + f i · Next , the filtering operation on the direction­ coded image extracts only the picture

element\whose directions coincide with (.3i , T and 4-1t . This enhances true edge lines of the obliquely imaged parallelepiped considerably. Examples of these processes as well as subsequent edge detection and determination processes are shown in Fig. 8. By this method, it becomes possible to accurately detect edge lines without the confusion normally introduced by a noisy background or complex pattern information on the object surfaces.

4. Recognition Algorithm of Surface Information

4.1 Spatial transformation

To read and recognize surface information on an obliquely imaged parallelepiped, the image should first be converted to the normalized image having no relation to the position and orientation of the object. This can be effected by adequate expansion, contraction, shift and rotation.

As shown in Fig. 9 , the lozenge­ shaped image portion corresponding to the upper surface of the object is transformed into a square image so that the edge points A, B, c and D correspond to the edge points A', B', C' and D' respectively. This is done by linear coordinate transformation by neglecting the projection distortion of the imaging system. That is, there exists the following relationship between the pre-transformed coordinates (x,y) and the . post-transformed coordinates (X,Y) :

where Ax , Ay , ··· , Dx , Dy denote the x and y coordinates of the edge points A, B, C, and D in the oblique image, and w corresponds to the length of the edge line of the square in the transformed image. From this equation, a picture point (X,Y) in the new image is obtained from the original image by averaging the picture element data at (x,y) or its vicinity, or by other interpolating methods. Figure 10 shows an example of this spatial transformation, in which the image is transformed as if it were viewed from the top of the object. In this normalized square image, the number of picture elements is standardized at 64x64. As this image is normalized according to its position and the size of its surface, a pattern matching method with standard patterns is applicable. This will be further covered in the next section.

In the above example, a method of transforming an original brightness image into a normalizP.d brightness image of the surface is described. However, it is also easy to convert directly from the direction-coded oblique image into the direction-coded normalized square image of the surface. That is, the direction code at (X,Y) is computed as follows: First, the coordinate (x,y) is computed from eq. (6) , and the direction code f3 at (x,y) is determined from the direction-coded original image by a suitable avera~ing ~r interpolating method. Then, the d1rect1on code (3 is .converted into 0( using eq. (5) Finally, the principal direction c:Xo ( see Fig. 5(a) ) is subtracted.

4.2 Information compression and recognition

The two-dimensional normalized image of the surface discussed in the above section is still too redundant to directly perform pattern matching with standard patterns. Also, in this case, the large volume of image data would necessitate an enormous memory capacity for standard patterns. Therefore, the following data compression is performed:

1. From the direction-coded, normalized square image of the surface, picture elements with a certain direction code are extracted and projected on the line L perpendicular to the direction code to yield the frequency distribution curve q as shown in Fig. 11 (a) .
2. This frequency distribution curve is transformed into the Fourier series and the magnitudes of the lower four harmonics (from 1st through 4th) are computed.
3. The above two processes are performed for all of the direction codes, thus giving a data table with 64 directions times 4 harmonics as shown in Fig. ll(b) ·
4. The data table thus obtained shows how the four magnitudes of the lower harmonics change with the direction change. Therefore, by regarding the four rows of the table as four waveforms, these can be transformed into the Fourier series.
5. The lower eight harmonics (from 1st through 8th) are chosen to compute each magnitude, thus giving a final table with 8x4 magnitude data as shown in Fig. ll(c) ·

By the above data compression, a normalized image is expressed as information with 8x4(=32) words. In other words, an image of the surface corresponds to a point in a 32-dimensional space. Therefore, the distances in the 32dimensional space between the unknown image pattern and the pre-determined standard patterns are computed. The pattern with the minimum distance is determined as the best match.

The algorithm mentioned above has the followinq features; it is (1) invariant to- the pattern rotation, and (2) invariant to the pattern shift. These features arise from the following facts:

1. The frequency distribution of each direction code is transformed into the Fourier series.
2. The magnitude change of each harmonic in relation to the direction change is transformed into the Fourier series.
3. Only the magnitude data are used, and the phase data as well as d.c. component are neglected.

Therefore, even when the spatial transformation in Fig. 10 gives an upsid~­ down image, the subsequent matching process gives the correct answer. For example, the symbols A , ) , \;;/ and <( as well as A with any arbitrary angle will lead to the same result A . This characteristic is extremely useful when the posture of a pattern can not be specified beforehand. Table 1 shows an example of some experimental data which represent the relative distances in 32dimensional space between some simple example patterns. It can be seen from the table that the same patterns give smaller distances regardless of the pattern inclinations.

5. Conclusion

The algorithm discussed in this paper is summarized as follows. First, the edge lines of a parallelepiped are extracted based on the direction-coded image. Next, the position of the object is determined irrespective of the existence of a noisy background or the existence of surface information of considerable complexity. Then, by using the edge point data of the detected object, the surface image is projected as a normalized square image as if it were being viewed from a direction perpendicular to the surface. Finally, the double Fourier transformation is performed on the direction-coded image of the normalized square image. One of the Fourier transformations is in ~onjunction with the axial direction in order to find the distribution of the direction code, and the other is with radial direction to determine magnitude variation. As a result, an image is largely reduced as to its quantity of information and is transformed into position-invariant and rotation-invariant data for easier pattern matching.

The main characteristics of this method arise from the fact that the direction-coded image is preferentially used. It is possible to regard this direction-coded image as the image in which the microscopic features in the original brightness image are distributed. For these microscopic features of the original image, macroscopic treatment such as frequency distribution calculation and Fourier transformation is performed.

Therefore, this method is hardly effected by background noise or local noise which sometimes exists in the image. Such macroscopic processing of microscopic features is one of the most effective methods of actually applying image processing to industrial use. · Furthermore, this method seems to hold promise of effective application in more complicated scene analysis and pattern recognition problems.