JPH0132549B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Field of Industrial Application The present invention relates to an object detection part of a visual system used for inspection and identification of objects, and more specifically to a method for rapidly detecting object contours on binary image data. .

Configurations of Conventional Examples and Their Problems Recently, many general-purpose vision systems used for inspecting and identifying objects have been developed in the United States and Japan. In the past, there were mainly two types of methods used in these systems to inspect and identify the shape of an object. One is a method that uses statistical properties of area points on image data. For example, the identification is made based on statistical quantities such as area, major axis, minor axis, and moment of inertia. Second, a characteristic part of the object is used as a template (reference image), a correlation calculation is performed between it and the target image, and the presence or absence of an image corresponding to the reference image is determined from the correlation coefficient, and this is used for identification. It's a method.

The former method does not directly use the contour shape, so it is difficult to apply to objects with complex shapes. In addition, the latter has limited conditions such as the size and angle of the template, making it difficult to generalize.

In any case, it does not utilize contour shape data. This is because the method of detecting contour lines is usually
Executed in program mode using a computer,
If this is applied to large amounts of image data, the processing speed will be slow.

Purpose of the Invention In order to solve these problems, the present invention aims to simplify the search procedure by using a fixed contour search table, and improve the processing speed required for the search by converting this into hardware. do.

Structure of the Invention The present invention provides a contour line detection method that includes the steps of: storing an orthogonal projection binarized image of a three-dimensional object input from an image input device; storing an image obtained by filtering the image; and storing the stored image. A step of detecting the starting point of the contour to be traced by scanning the data line-by-line, and accessing the overlay memory in which the detection prohibited area is written using a fixed contour search table according to the obtained starting point. It consists of a step of tracing the contour line while
This allows high-speed contour detection.

DESCRIPTION OF THE EMBODIMENTS The general contour tracing procedure can be summarized as follows.

(1) Systematically scan the image to find points (starting and ending points) that meet the detection criteria. Once such a point is found, it becomes a reference point.

(2) Examine the neighborhood of reference points and apply appropriate tracking criteria. Use the detected point as a new reference point, and if the termination condition is not met, return to (2).

(3) Once the systematic scan is complete, the algorithm terminates.

Various tracking algorithms can be constructed by variously changing the detection criteria, tracking criteria, and termination conditions in this procedure.

The method used in the present invention is as follows.

(1) First, a search starting point is detected for a shape in which four edges are cut. This is as shown in Figure 2 a.
Scans the four edges of the image memory clockwise to detect boundary points (arrows in Figure 2 a) that change from outside the area to inside the area (〇→●).

(2) Using the starting point detected in (1) as a reference point, obtain the number of starting directions (number of detected directions) and perform contour line searching (see sections (4) to (6)).

(3) The contour lines left on the contour memory (the four edges are not cut) are scanned line by line as shown in FIG. 2b to detect the search starting point.

(4) Using the obtained starting point as a reference point, obtain the number of starting directions (number of detected directions) and start tracking.

(5) If the number of detected directions at the previous reference point is i, then i-
The area points are searched sequentially counterclockwise from direction 3 (see Figure 4).

(6) Add the next detected boundary point coordinates to the data string,
Make this the new reference point. At the same time, this point is erased from the contour line memory and written into the prohibited area memory. If this point does not match a previously detected point (a point on the prohibited area memory) or the four edges of the image, return to (5).

(7) Finish for one contour line. To find the next contour, return to (3).

(8) Termination.

(However, the contour line extracted from the input image by 4-neighborhood filter processing is written in the contour line memory.) Here, it will be shown that this method detects all contour lines.

First, when scanning in the horizontal direction, there are two types of contour shapes detected near the starting point as shown in FIG. On the other hand, there are three other types of shapes that can be obtained by scanning in the other direction, but they are representatively shown in FIG. 5 and pose no problem. Then, the number of starting directions is 7 in the case of Fig. 5 a, b
In this case, it is also set as 7.

In this case, the positional relationship with the next reference point is shown in FIG. 5a in FIG. 6 and in FIG. 7 in b. In this way, in the case of FIG. 6, if the search is started from direction 4, the next reference point can be detected. Similarly, the case shown in FIG. 7 can also be detected.

Next, consider detection on the contour line. As shown in FIG. 8, when a point is detected in the direction 6 from the previous reference point, the direction 3 from the current reference point always becomes a background point. Furthermore, there is no problem in assuming that there is no next detection point in the clockwise direction from this point. Therefore, by searching counterclockwise from direction 3, the next reference point can be detected.

Recurring from the above, it can be seen that all contour lines can be detected using this method.

As a result, the procedure for 8-neighbor search becomes simple. This is explained in FIG.

Pixel data in the eight vicinity of the reference point is set as data in directions 1 to 8 according to the number of directions. Direction 1 in Figure 9
-8 corresponds to this. The contents of the table in the figure (hereinafter referred to as the search table) are bit patterns in which 〇 indicates background points and ● indicates area points. The bottom number indicates the number of directions to the next reference point, which is obtained by looking up the table with the bit pattern for directions 1-8. For example, if the number of forward directions is 5, the direction is 2 as seen from the current reference point.
is always a background point. Next, in the order of 2≓8≓1, the direction in which the first area point is obtained is the number of directions to the next reference point.

If eight types of search tables are prepared in accordance with the number of forward directions in this manner, contour points can be detected simply by detecting pixel data of eight neighboring points and referring to the table.

In addition, an overlay memory that serves as a bit plane is prepared so as to overlap the image memory, and the end point and search prohibited area are written in this overlay memory. This is detected at the same time as the pixel data of the eight neighboring points is detected, and it is checked whether the next reference point has reached the end point or the prohibited area.

In this way, the present invention uses an overlay memory in which a search table and termination conditions are written, and a contour memory in which contours extracted by 4-neighborhood filter processing are written, to eliminate contours that were conventionally controlled by program control. The feature is that point tracking can be realized using hardware using random logic, and high-speed processing is also realized.

FIG. 1 is a diagram showing an outline of an apparatus for implementing the present invention. In the figure, 101 is an image input section. The orthogonal projection binarized image of the three-dimensional object input from the image input unit 101 is stored in the image storage unit 102. Reference numeral 102 is composed of an image memory, an overlay memory superimposed thereon, a four-neighborhood filter circuit, a binarization circuit, and a contour line memory.
108 is a search starting point detection unit. Detection of search starting points on the four edges as shown in Figure 2a, and detection of search starting points on parts other than the edges as shown in Figure 2b
7 and using the image storage unit 102. Based on this data, the control section 107 sends the starting point and starting direction number of the contour line to the address calculating section 105 and the contour point searching section 104, respectively, and ends the tracking based on the terminal point information from the DMA section 103. After the process is completed, control is transferred to the search start point detection unit 108 for detecting another contour line.

The DMA unit 103 accesses eight neighboring points around the reference point or starting point from the image storage unit 102. At the same time, regarding the reference point coordinates, the data on the contour memory is erased and the data is written in the overlay memory. Furthermore, the accessed data is processed by the contour point search unit 1.
04, and temporarily stores this overlay data. The number of directions to the next reference point detected by the contour search unit 104 is compared with the stored data to detect end information. In the case of the terminal, slave end information is sent to the control section.

The contour point search unit 104 reads the number of directions to the next reference point (contour point) from the search table based on the 8 neighboring point data obtained from the DMA unit and the previously stored number of forward directions.
The search table is composed of ROM, and the input data is 3 bits of forward direction number and 8 bits of 8 neighboring point data, a total of 11 bits is given as an address, which allows the next direction number to be determined.
A total of 4 bits are read out: 3 bits and 1 bit of error information.
The error information is written so that when all eight neighboring points are "1" or all "0" and direction i-3 is "1", "1" is output. The read direction number is sent to the address calculation unit 105, and the error information is sent to the control unit 10.
Sent to 7.

The address calculation unit 105 increases or decreases the address in the X and Y directions according to the number of directions obtained by the contour point search unit 104, and calculates the next reference point address. The obtained next reference point address is sent to the DMA unit 10.
3, and is also sent to and stored in the contour data storage unit 106 along with the number of detected directions.

FIG. 10 is a diagram showing a specific example of the DMA unit, contour point search unit, and address calculation unit. First, the starting point address is set by the control unit as buffer [2] 10.
07, the starting direction number is sent to buffer [1] 1004. Memory according to buffer address
Access circuit 1001 accesses 8-neighborhood data and sends it to lookup table 1003 and comparison circuit 1002. At the same time, the data on the contour memory 303 is erased according to the buffer address, and the overlay
Write data to memory 305. The overlay data sent to the comparison circuit is temporarily stored. The next direction number is obtained from the search table, and this is sent to buffer [1], calculation table 1005, and contour data storage section. According to the direction number of Batsuhua [1],
Compare the corresponding bits of the previously stored comparison circuit to obtain termination information. The increase/decrease value in the X and Y directions for each direction is written in the calculation table, and this is sent to the calculation circuit to calculate the next reference point address. The calculation results are sent to the contour data storage section and buffer [2].

Further, the above method can also be implemented by an apparatus configured with an image memory 1102, a CPU 1103, and a temporary storage 1104 as shown in FIG. In this case, the CPU operation order is 12th.
It will be as shown in the figure.

Effects of the Invention As described above, the present invention uses an overlay memory in which a search table and terminal conditions are written, and a contour memory in which contours extracted by 4-neighborhood filter processing are written, which is not conventionally performed under program control. This is a method that enables contour point tracking, which has been previously known, to be realized using hardware using random logic, and also achieves high-speed processing.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an overview of an apparatus for carrying out the present invention, FIGS. 2 a and b are diagrams showing a method for detecting a search starting point, and FIG. 3 shows a specific embodiment of an image storage unit. Figure 4 is a diagram explaining the number of directions and search order, Figure 5 is a diagram showing the outline shape near the detected starting point, and Figure 6 is a diagram showing the positional relationship between the starting point and its adjacent points in an open figure. Figure 7 is a diagram showing the positional relationship between the starting point and its adjacent points in a closed figure, Figure 8 is a diagram generally showing the positional relationship with adjacent points on the contour line, and Figure 9 is a diagram showing the forward direction number. FIG. 10 is a block diagram showing a specific embodiment of the DMA unit, contour point search unit, and address calculation unit. FIGS. 11 and 12 are diagrams showing other embodiments of the present invention. It is a figure for explaining an example. 101... Image input section, 102... Image storage section, 103... DMA section, 104... Contour search section, 105... Address calculation section, 106... Contour data storage section, 107... Control section.

Claims (1)

[Claims] 1. A step of storing an orthogonal projection binarized image of a three-dimensional object inputted from an image input device, a step of storing an image obtained by processing the image through a filter, and a step of tracing the stored image data by scanning the stored image data line-sequentially. a step of detecting the starting point of the contour line;
A contour line detection method comprising the steps of tracing the contour line using a fixed contour search table according to the obtained starting point and accessing an overlay memory in which a detection prohibited area is written.