JPH0447867B2 - - Google Patents

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention uses a binary image that constitutes the outline of an object in order to grasp the shape of the object captured by a television camera in, for example, a visual recognition system. The present invention relates to a contour line extraction device that extracts contour line data along the contour of an object from a group of contour point data obtained in the order of screen scanning.

[Conventional technology]

Generally, in visual recognition systems, etc., calculations are required to extract the shape of an object from a binary image that makes up the object's outline, or to determine various parameters such as the position of the center of gravity of the object or the circumference of the object's outline. From the viewpoint of ease of use, it is necessary to extract contour data arranged along the contour of the object. That is, it is necessary to generate contour point data from the boundaries of shading in a gradation image obtained from a television camera, for example, and to extract contour line data forming a closed loop based on the contour point data.

FIGS. 5 and 6 are diagrams for explaining contour line extraction by the conventional method.

As a conventional contour line extraction method of this type, for example, as shown in FIG.
- By setting the y coordinate system in advance and scanning 2 the screen 1, the outline point data group (x ₁ , y ₁ ) (x ₂ , y ₂ )...(x _o , y _o ) in the screen scanning order, store these in the contour point data memory 3, and then perform contour line extraction processing on the contour point data group, and extract the contour point data group from the contour of the object, for example in a counterclockwise direction. Contour data (x _A1 , y _A1 ) (x _A2 , y _A2 ) along (indicated by m in the figure)... (x _Ao ,
_yAo ) and stored in the contour data memory 4. In this method, as shown in FIG. ₆ , for example, as shown in FIG _.
and eight surrounding positions A that can be connected to this starting point.
After searching the contour point data memory 3 for G to G and extracting the next contour point connected after the starting point P, the next contour point connected next to the extracted contour point is determined as described above. By similarly extracting and repeating this procedure thereafter, the extracted contour points are sequentially stored in the contour data memory 4 as contour data.

[Problem that the invention seeks to solve]

However, in such a conventional contour line extraction method, in order to extract the next contour point connected to a certain contour point, the contour is calculated for all eight data values surrounding one contour point. Since point data memory 3 must be searched,
There is a problem in that the number of times the contour point data memory 3 is searched is required to obtain the final contour data, and the processing time for contour extraction increases accordingly.

In order to solve this problem, the inventor of the present application previously proposed a contour extraction device as shown in Japanese Patent Application No. 58-225622. According to this proposed invention, a memory storing a group of contour point data is scanned once, an intermediate data point sequence is stored in a point sequence buffer, and each data point sequence is combined. I am trying to extract line data. Since contour point data can be sequentially processed in just one scan, contour data can be extracted at extremely high speed.

In the above-mentioned proposed invention, it is more desirable if the point sequence buffer is not required because the memory area can be saved.

The present invention aims to solve the above problems, makes it possible to speed up the processing time, and further improves and develops the above proposed invention. It is an object of the present invention to provide a contour line extraction device that enables extraction of contour line data.

[Means for solving problems]

Therefore, in the previously proposed invention, the present invention uses the first read contour point data as the starting point of both of a pair of data point sequences, does not temporarily store the data point sequence in the point sequence buffer, and instead Information on the connection relationship between contour points is stored in the connection information memory, and intermediate data point sequences are managed by the connection information memory. That is, the contour line extraction device of the present invention is a contour line extraction device that extracts a group of contour point data obtained in screen scanning order from a closed-loop binary image forming the contour of an object as contour line data along the contour of the object. a contour point data memory for storing the contour point data group; a point sequence end point storage means for storing each point sequence end point data corresponding to the end point of each data point sequence to be processed; a connected information memory that stores pointer information pointing to the connected contour point data, and whether the contour point data read from the contour point data memory is adjacent to the point sequence end point data stored in the point sequence end point storage means. data extraction processing means having means for determining whether or not the contour point data is connected to the end point data of the point sequence when the data extraction processing means determines that the contour point data is not connected to the point sequence end point data; starting point detecting means for detecting and storing this in the point sequence end point storage means;
When the data extraction processing means determines that the contour point data is connected to the previously detected point sequence end point data, the contour point data is detected as an extension point and stored in the point sequence end point storage means. extension point detection means for storing pointer information pointing to the connected contour point data in the connection information memory; and connection of each end point by comparing the end points of each point sequence data based on the information stored in the connection information memory. A closed-loop forming means for extracting closed-loop contour data by determining a relationship and combining point sequences that can be connected, and a contour data memory in which contour data from the closed-loop forming means is stored. It is characterized by Hereinafter, embodiments will be described with reference to the drawings.

〔Example〕

Figure 1 shows the configuration of one embodiment of the present invention, and Figure 2 shows the configuration of the first embodiment.
Figure 3 is a flowchart for explaining the outline of the processing according to the illustrated embodiment in Figure 1. Figure 4 shows the relationship between the starting point and the connecting point. A diagram for explanation is shown.

In FIG. 1, a contour point data memory 3 is a memory that stores a group of contour point data obtained in the screen scanning order for a closed-loop contour binary image forming the contour of an object as shown in FIG. 2a, for example. be.
In the case of a binary image as shown in FIG. 2a, information as shown in FIG. 2b is set in the contour point data memory 3. The contour line data memory 4 is a memory in which the contour extraction results are stored, and in the case of a binary image as shown in FIG. 2a, a group of contour point data is stored as shown in FIG. This is ultimately stored and retained as contour line data that follows the contour.

The data extraction processing section 10 processes the contour point data sequentially read out from the contour point data memory 3, and includes a compression circuit 11, a processing determination circuit 12, and a connection point determination circuit 13. Compression circuit 11
Although not essential in the present invention, in order to reduce the number of contour point data to be subjected to intermediate processing, further speeding up the processing and saving memory, contour point data is transferred from the contour point data memory 3. When reading out,
For example, a process is performed in which consecutive points in the horizontal direction are newly grouped into one piece of contour point data. That is, the compression circuit 11 compiles data whose y-coordinates are equal and whose x-coordinates are increased by 1, as shown in FIG. 2c. With respect to the contents of the contour point data memory 3 shown in FIG. 2b, the output of the compression circuit 11 is as follows.
The result will be as shown in FIG. 2d. The results are written to the contour point data memory 3 or the connection information memory 15 as required.

Until the scanning of the contour point data memory 3 is completed, the processing determination circuit 12 determines whether the y-coordinate value of the contour point data has changed compared to that of the previously read contour point data, that is, raster scanning. It is determined whether or not the raster scan is lowered by one level. If the raster scan is lowered by one level, the y-coordinate value in the point sequence register 14, which will be described later, is updated. Furthermore, when the raster scan is completed, a raster scan end signal S is output.

The connected point determination circuit 13 refers to the x-coordinate value stored in the point sequence register 14 and determines whether the contour point data read from the contour point data memory 3 corresponds to any point sequence in the previously processed data. This is a circuit that determines whether to connect or not to connect.

The point sequence register 14 is a register that stores point sequence end point data, and stores the x coordinate value [x _T1 , x _T2 ] and y coordinate value of a pair of end points of a data point sequence that has already been detected. be. In this embodiment, in order to simplify the explanation, a case will be explained in which one set of point sequence end point data is handled, but in reality, coordinate information is stored for each point sequence according to the number of point sequence end point data. There is. The connection information memory 15 is a workpiece that holds forward pointer and backward pointer information between adjacent contour points, as shown in FIG. 2e, for example, for the contour point data shown in FIG. 2d. It's memory. These pointer information are held corresponding to each contour point data, and therefore,
Since this is not related to the number of generated point sequences, the connected information memory 15 may have a relatively small memory capacity.

The starting point detection circuit 16 detects when the connection point determination circuit 13 determines that the contour point data to be processed is not connected to the data point sequence stored in the point sequence register 14 and the connection information memory 15. The circuit is activated, and at this time, the set of the left end x coordinate and right end x coordinate (these x coordinates may take the same value) of the contour point data is set as the end point of a pair of point sequences, Point sequence register 14
, and set it as new point sequence end point data.

On the other hand, the point sequence extension circuit 17 is connected to the connection point determination circuit 1.
3, the contour point data to be processed is transferred to the point sequence register 14 and the connection information memory 15.
This circuit operates when it is determined that the data point sequence is connected to the data point sequence stored in the point sequence register 14.
Pointer information for mutually associating the end points of the data point sequence to be connected with the contour point data is set in the connection information memory 15. Then, since the contour point data currently being processed becomes a new endpoint, the contents of the point sequence register 14 for the original endpoint are updated with its x-coordinate value. This results in an extended data point sequence.

The closed loop forming circuit 18 is a circuit that operates in response to the raster scanning end signal S from the processing determination circuit 12, and it operates based on the pointer information regarding the data point sequence set in the connection information memory 15. The endpoints are compared to determine the connection relationship between the endpoints, and each point sequence that can be connected is combined to read contour point data in a closed loop. Contour point data extracted counterclockwise according to the forward pointer or backward pointer, for example, is treated as contour data forming a closed loop.
The contour data are sequentially stored in the contour data memory 4.

Next, the operation of the contour line extraction device according to this embodiment will be explained with reference to FIGS. 1 to 4.

Now, suppose that the closed-loop binary image that constitutes the outline of the object is as shown in Figure 2a,
As shown in FIG. 2b, the contour point data memory 3 stores contour point data (x ₂ ,
y ₃ )...(x ₂ , y ₁ ) is stored.

When the contour point data (x ₂ , y ₃ ) . Equally, data whose x coordinate increases by 1 are grouped together. As a result, when the reading is completed, the contour point data memory 3
The contents are as shown in FIG. 2d. That is, each piece of data has an x-coordinate of its left end, and an x-coordinate and a y-coordinate of its right end.

This compressed initial contour point data (x ₂ , x ₃ ,
When y ₃ ) is supplied to the processing determination circuit 12 , y ₃ is set in the y coordinate register of the point sequence register 14 in the processing determination circuit 12 . Next, this contour point data (x ₂ , x ₃ , y ₃ ) is sent to the connection point determination circuit 1.
3, since the x coordinate value of the point sequence register 14 is empty data, it is determined that there is no data point sequence to which the contour point data (x ₂ , x ₃ , y ₃ ) is connected, and this The data is sent to the starting point detection circuit 16. The starting point detection circuit 16 stores the contour point data (x ₂ , x ₃ , y ₃ ) as the starting points of a pair of point sequences T1 and T2 as shown in FIG. Then, as shown as (i) in FIG. 2F, a pair of X ₂ and X ₃ is set as point sequence end point data in a pair of storage sections (x _T1 , x _T2 ) of the point sequence register 14.

When the next contour point data (x ₁ , x ₁ , y ₂ ) is sent to the processing judgment circuit 12, the processing judgment circuit 12 first detects that the y-coordinate value has changed, and stores it in the point sequence register 14. The y coordinate register in is updated to y ₂ . Then, the data is sent to the connection point determination circuit 13, and in the connection point determination circuit 13,
The point sequence register 14 is referred to and it is determined whether this contour point data (x ₁ , x ₁ , y ₂ ) is adjacent to any of the end point data of the previously set storage section (x _T1 , x _T2 ). It is determined whether And x ₁ is the contents of x _T1 part
Since it is adjacent to _x2 , the point sequence extension circuit 17 is activated.

The point sequence extension circuit 17 receives contour point data (x ₁ , x ₁ ,
y ₂ ), as shown in FIG. 2e, the contour point data _{( x 1} , x _{1 ,} y ₂ ), and the contour point data (x ₂ , x ₃ , y ₃ ) is set at the address corresponding to the contour point data (x ₁ , x ₁ , y ₂ ) in the connection information memory 15. Set a backward pointer to . Also, the x _T1 portion of the point sequence register 14 is updated to x ₁ .

Similarly, when the next contour point data (x ₃ , x ₃ , y ₂ ) is sent to the processing judgment circuit 12, the processing judgment circuit 12
The y-coordinate value is checked, but since the y-coordinate value in the point sequence register 14 does not change, the data is passed to the connection point determination circuit 13 as is. In the connection point determination circuit 13, contour point data (x ₃ , x ₃ ,
y ₂ ) is recognized as being connected to the other point sequence T2 stored in the point sequence register 14, and the point sequence extension circuit 17 is activated.

The point sequence extension circuit 17 receives contour point data (x ₃ , x ₃ ,
y ₂ ), as shown in FIG. 2e, the contour point data ( _{x 3 ,} x _{3 ,} y ₂ ), and the contour point data (x ₂ , x 3 , y ₃ ) is set at the address corresponding to the contour point data (x ₃ , x ₃ , y ₂ ) in _the connection information memory 15. Set a backward pointer to . Also, the _xT2 portion of the point sequence register 14 is updated to _x3 .

Furthermore, when the next contour point data (x ₁ , x ₂ , y ₂ ) is sent to the processing judgment circuit 12, the processing judgment circuit 12
The y-coordinate value is checked in point sequence register 1.
Since the y coordinate value in 4 has changed, y ₁ is set in the point sequence register 14. Then, the data is delivered to the connection point determination circuit 13, and the connection point determination circuit 1
3, the contour point data (x ₁ , x ₂ , y ₂ ) is stored in the point sequence T1 or point sequence T2 stored in the point sequence register 14.
It is determined whether or not to connect to any of the following. In this case, first, it is recognized that it is connected to the point sequence T1,
The point sequence extension circuit 17 is activated.

The point sequence extension circuit 17 receives contour point data (x ₁ , x ₂ ,
y ₂ ), the contour point data (x ₁ , x ₂ , y ₂ ) is stored in the address corresponding to the contour point data (x _{1 , 2} ), and at the same time, set the contour point data (x ₁ , x ₁ , y ₂ ) at the address corresponding to the contour point data (x ₁ , x ₁ , y ₂ ) in the connected information memory 15. Set a backward pointer to . Also, the x _T1 portion of the point sequence register 14 is updated to x ₂ . By this,
The point sequence register 14 is as shown in parentheses (f) in FIG. Further, the connection information memory 15 has information as shown in FIG. 2e.

At the next stage, the processing determination circuit 12 detects the end of the data, and the processing determination circuit 12 outputs a raster scan end signal S, which is applied to the closed loop forming circuit 18. The closed loop forming circuit 18 is
Follow the forward pointer or backward pointer in the connection information memory 15 and find the end points (x ₃ , x ₃ , y ₂ ) and (x ₁ , x ₂ , y ₁ ).
It is detected that there is a connection relationship between the two. Then, referring to the compressed contour point data string shown in FIG. While restoring the data point sequence T1, the data point sequence T2 is restored in the forward direction while restoring the data point sequence T1.
The portion corresponding to is traced in the opposite direction, and the result is written into the contour data memory 4 as contour data. As shown in FIG. 2g, the contour data memory 4 stores contour data obtained by extracting the contour of an object along the counterclockwise direction.

FIG. 3 shows an overview of the above processing in the form of a flowchart, and the processing ends by forming a closed loop. For example, microprogramming or other means can be adopted as individual embodiments of each of the above circuits or processing units, and from the above explanation, it is clear that those skilled in the art can implement it, and design changes regarding the specific configuration can be implemented. is possible as appropriate.

Note that in the above embodiment, the outline of the object is 1
In other words, the case where there is one closed loop has been described, but if the present invention is applied also when the outline of the object is complex or when there are multiple objects, the starting point detection circuit 16
, the number of data point sequences increases accordingly, and by appropriately combining each data point sequence, contour line data can be similarly extracted.

〔Effect of the invention〕

As explained above, according to the present invention, it is possible to extract contour line data by scanning the memory storing a group of contour point data substantially once, and the processing necessary for extracting contour line data is The time can be significantly reduced. Furthermore, since information regarding intermediate data point sequences in the middle is managed by pointer information, processing becomes easier and the amount of memory required may be reduced. Note that horizontally continuous contour point data can be compressed all at once, and if this compression is adopted, the amount of memory can be further reduced.

[Brief explanation of the drawing]

Figure 1 shows the configuration of one embodiment of the present invention, and Figure 2 shows the configuration of the first embodiment.
FIG. 3 is a flowchart for explaining the outline of the processing according to the illustrated embodiment in FIG. 1, and FIG. 4 shows the relationship between the starting point and the connection point. FIGS. 5 and 6 are diagrams for explaining contour line extraction by the conventional method. In the figure, 3 is a contour point data memory, 4 is a contour line data memory, 10 is a data extraction processing section, 11 is a compression circuit, 12 is a processing judgment circuit, 13 is a connection point judgment circuit, 14 is a point sequence register, and 15 is a connection information memory, 16 a starting point detection circuit, 17 a point sequence extension circuit,
18 represents a closed loop forming circuit, and T1 and T2 represent data point sequences.

Claims (1)

[Scope of Claims] 1. A contour extraction device that extracts a group of contour point data obtained in screen scanning order from a closed-loop binary image constituting the contour of an object as contour data along the contour of the object, comprising: a contour point data memory for storing a group of contour point data; a point sequence end point storage means for storing each point sequence end point data corresponding to the end point of each data point sequence to be processed; A connection information memory that stores pointer information pointing to contour point data, and determining whether the contour point data read from the contour point data memory is adjacent to the point sequence end point data stored in the point sequence end point storage means. and a data extraction processing means having means for detecting the contour point data as a starting point of a new data point sequence when the data extraction processing means determines that the contour point data is not connected to the point sequence end point data. starting point detection means for storing the contour point data in the point sequence end point storage means, and when it is determined by the data extraction processing means that the contour point data is connected to the previously detected point sequence end point data, the contour point data is set as an extension point. an extension point detection means for detecting and storing this in the point sequence end point storage means and storing pointer information pointing to the connected contour point data in the connection information memory; and based on the information stored in the connection information memory. a closed loop forming means that compares the end points of each point sequence data to determine the connection relationship between each end point, and extracts closed loop contour data by combining each point sequence that can be connected; 1. A contour extraction device comprising: a contour data memory in which contour data is stored. 2. The data extraction processing means includes data compression means for collectively outputting continuous contour point data in the scanning direction in the contour point data memory as one contour point data. The contour line extraction device described in Section 1.