JPH024949B2 - - Google Patents

Description

[Detailed Description of the Invention] [Field of Application of the Invention] The present invention relates to a contour processing method for rapidly performing a process of approximating a contour pixel sequence (contour point sequence) having a predetermined connection relationship on a digital image by a line segment. The present invention relates to a pixel column line segmentation device.

[Prior art]

Generally, the processing method for approximating a point sequence with a line segment is
Various methods have been reported, some of which are intended for considerably high-speed processing.

However, all of these require processing to check whether each point on the point sequence exists within the approximation error, so even if the method with the least amount of calculation is adopted, there will still be a considerable amount of line Disposal-like treatment is required.

Therefore, in visual processing where real-time processing is important, such as the visual function of robots, if it is applied directly to line segment approximation processing of hundreds or thousands of points, processing speed will be hindered, making it almost impractical. Therefore, there is a strong demand for speeding up the process.

[Purpose of the invention]

In view of the above-mentioned current situation, an object of the present invention is to provide a contour pixel string line differentiation device that can perform line segment approximation processing at high speed for contour pixel strings connected while maintaining a predetermined connection relationship in a digital image. There is a particular thing.

[Summary of the invention]

The configuration of the contour pixel column line differentiation device according to the present invention is as follows:
The desired data of the desired data is stored about the prescribed line -specific approximation data for various score patterns required to make a line approximation of the desired dialogue While sequentially searching for each contour pixel, each end point of line segmentation is determined by referring to the line segment approximation data based on the connection relationship between each pixel, and each line segment approximation of the contour pixel string is sequentially performed. The present invention comprises a search/line segmentation means for performing a search and line segmentation, and a vertex data memory that stores data on each end point of the line segmentation and outputs the data as each vertex data of line segment approximation.

The principle will be explained in more detail below.

First, dividing a pixel string into lines means dividing into lines a representative point string to replace the pixel string, using the center point of each pixel as a representative point. Here, each pixel represents, for example, one area in which the image is finely divided into square sections, and the center points thereof are arranged at equal intervals vertically and horizontally.

Among the points in such a special positional relationship,
As shown in the neighboring pixel relationship diagram for a specified pixel in Figure 1, if we consider line segment approximation of a point sequence that maintains the connection relationship of the 4 neighbors and 8 neighbors shown in a and b in the figure, the object of line segment approximation is The number of connected patterns of point sequences is a finite number if a limit is placed on the maximum length of a line segment.

Therefore, in the present invention, by efficiently storing all possible point sequence patterns in a data table in advance, in line segment approximation processing, the approximation error can be stored in the data table instead of calculating the approximation error for each point. This search process was replaced with the previous search process in order to obtain equivalent results at high speed.

This data table also stores search address (relative address) data so that the next contour pixel can be found as quickly as possible when searching for the contour of a specified area on the image. We are trying to speed it up.

Next, FIG. 2 is a format diagram of line segment approximation data according to the present invention, and is an example of a case where a contour is searched based on 4-connection.

The line segment approximation data is composed of first and second data in the format shown in FIG. 2a and b.

The first data will be explained. In the line segment approximation process, the positional relationship of the second pixel with respect to the first pixel is four patterns: top, right lateral, bottom, and left lateral, and data for these four patterns are arranged in order. The order is to search for the second pixel clockwise around the first pixel. There are two items of data for each pattern. for example,
IA1 indicates the relative address on the image of the second pixel (located directly above) with respect to the first pixel, and IP1 is the beginning of the area where data related to line segment approximation processing for the third pixel is stored. Indicates address. That is, it indicates the start address of second data to be described next.

The second data will be explained. This data is
Each contour pixel is created corresponding to the third and subsequent contour pixels in the line segmentation. For example, the case of data for the L-th contour pixel that undergoes line segmentation will be described. SA1 is the (L-1)th on the image
The relative address of the candidate pixel of the Lth contour pixel with respect to the contour pixel of the Lth contour is shown. Check the candidate pixel according to this address, and if it is not a contour pixel,
Next, conduct similar investigations in SA2, SA3, and SA4. When the pixel indicated by the address of SA3 is determined to be a contour pixel, the value of SP3 indicates line division information of the L-th contour pixel.

In other words, when the value of SP3 indicates a pointer to the first data, it indicates that line segmentation is no longer possible if the Lth pixel is included.
This is a determination value for determining to perform line segmentation processing up to the (L-1)th pixel. Also, SP
If the value 3 indicates the pointer to the second data again, it means that line division is possible even if the current Lth pixel is included, and then using the data pointed to by the pointer, the (L+1)th pixel is This is the determination value for continuing the process of searching for the th contour pixel.

In this way, the second data includes four sets of search address data, line division judgment value data, and data indicating a pointer to the next processing data in four directions so that one round of the search can be performed in a clockwise direction. They are arranged as units.

The above two types of first and second data are configured as a data file so as to cover all possible patterns. In addition, 4 in each data unit
The arrangement order of the data sets in the two directions is such that the number of searches is minimized while maintaining the clockwise principle.

[Embodiments of the invention]

Embodiments of the present invention will be described below based on the drawings.

FIG. 3 is a block diagram of an embodiment of the contour pixel column line segmentation device according to the present invention, FIG. 4 is a block diagram of an embodiment of the contour pixel search section, and FIG. 5 is a block diagram of the same line segment approximation FIG. 3 is a block diagram of an embodiment of a processing section.

Here, 100 is a control unit that controls the processing flow of each unit described below, 200 is a line segment approximation data memory, 300 is an image memory, 400 is a contour pixel search unit related to the search/line differentiation means, 40 is its pixel reading circuit, 402 is its comparison circuit, 403
is the same contour pixel determination circuit, 404 is the same judgment value registration circuit, 405 is the same contour pixel recording circuit, 406
is an address generation circuit for reading the same pixel, 500
Also, a line segment approximation processing unit related to the search/line segmentation means, 5
01 is an address reading circuit for contour searching;
502 is a same address update circuit, 503 is a same line segment approximate data reading circuit, 504 is a same discrimination circuit, 505 is a same end point processing circuit, 600 is a line division information memory, and 700 is a vertex data memory. be.

First, the processing and operation of the entire apparatus will be explained based on FIG. 3.

The digital image from input IN is first stored in image memory 300.

The line segment approximation data shown in FIG. 2 described above is previously stored in the line segment approximation data memory 200.

The processing of this apparatus is started by inputting information ST indicating which region on the image is to be processed into the outline into the line segmentation information memory 600. The information ST indicating this area may indicate, for example, the address of the first pixel found when performing an area search in the raster direction from the upper left end of the image as the area representative position. This area representative point becomes the starting point of contour tracing, and also becomes the ending point after tracing around the outer periphery of the area. Furthermore, a threshold value that separates the target area from other areas is recorded as other information.

The contour pixel search unit 400 reads the value of the pixel at the region representative position from the image memory 300, determines whether the value of each pixel in the target region is on the larger or smaller side with respect to the threshold value, and displays the result as a line. It is recorded in the differentiation information memory 600.

Next, a candidate pixel for the next contour pixel is selected around the contour pixel (pixel at the representative position), and the value of the selected pixel is compared with a threshold value to determine whether the pixel is in the target area. The selection of candidates for this contour pixel is
For example, when 4-connection (4-neighborhood) is used as the connection standard, 4 pixels on the upper, lower, left, and right sides are targeted. In the case of 8-connection (8-neighborhood), the surrounding 8 pixels are targeted.

These are sequentially selected as candidates in a clockwise direction, starting from the previous contour pixel and starting from the next pixel. If the selected candidate pixel is not within the region, the next candidate is selected.

This selection process is performed by the line segment approximation processing unit 500 reading the next search address (relative address) from the line segment approximation data memory 200 and passing this to the contour pixel search unit 400.
If it is determined that the pixel is within the area, this is determined to be the next contour pixel. The address of the determined contour pixel is recorded in the line segmentation information memory 600 as the address at the time of the search. Search for the next contour pixel around this address.

In addition to recording the address of the contour pixel, information on the positional relationship (for example, top, bottom, left, right) between the previous contour pixel and the newly determined current contour pixel, that is, the connection relationship, is sent to the line segment approximation processing unit 500. passed on.

The line segment approximation processing unit 500 performs a process of approximating a series of points of contour pixels sent one after another with a line segment, and outputting each end point of the approximated line segment as a series of vertices.

This process determines the mutual positional relationship between the second, third, ... contour pixel rows following the contour pixel determined as the starting point of one line segmentation, for example, the second pixel is the starting point pixel. The third pixel on the right is expressed as above the second pixel, and this information is sequentially compared with the line segment approximation data.

As mentioned above, the line segment approximation data is, for example,
When the pixel string (dot string) from the first pixel to the Nth pixel can be approximated by a line segment, the (N+1)th pixel is to the right of or above the Nth pixel. , the pixel row from the 1st pixel to the (N+1)th pixel can be approximated by the same line segment again, but if it is located to the left or below, the pixel row from the 1st pixel to the (N+1)th pixel can be approximated by the same line segment. The line segment approximation data memory 200 contains information that the information is not possible for all possible pixel column patterns (N is less than or equal to the maximum value M).
This is data that is stored (memorized) in advance.

When one piece of contour pixel information is input from the contour pixel search unit 400, the line segment approximation processing unit 500 determines the next pixel according to the pixel number of that pixel and the pattern of the pixel strings input so far. In this case, it is determined which data in the line segment approximation data memory 200 should be looked at based on the result of the previous pixel processing.

For example, when the Nth contour pixel is found and its information is input, the line segment approximation processing unit 500 processes the line segment that has already been obtained and stored when processing the (N-1)th pixel. The approximate data search address is read from the line segment information memory 600, and data on the line segment approximate data memory 200 is read based on the address.

This data indicates whether the pixel string including the Nth contour pixel can be approximated by a line segment, and
If it can be approximated by a line segment, then the search address of the (N+1)th contour pixel and the start address of the area where data related to line segmentation are stored are shown.

If approximation with a line segment is impossible if up to the Nth contour pixel is included, the pixel row up to the (N-1)th pixel is approximated with a line segment. That is, the address of the (N-1)th pixel is recorded in the vertex data memory 700 as the end point (apex) coordinates of the line segment. Next, the (N-1)th pixel is again determined as the starting point (first pixel) of the next line segment approximation, and the next inputted contour pixel is set as the last inputted Nth pixel as the second pixel. The search address regarding (the third pixel) and the start address of the area where the line segmentation data are stored are recorded in the line segmentation information memory 600.

If line segmentation is possible even if the Nth contour pixel is included, the search address for the next input pixel and the start address of the area where line segmentation data is stored are recorded in the line segmentation information memory 600.

Subsequently, the search address of the next contour pixel is read from the line segment approximation data memory 200, is passed to the contour pixel search section 400, and enters a standby state. After confirming that the line segment approximation processing unit 500 has finished processing and entered the standby state, the contour pixel search unit 400
starts the process of searching for the next contour pixel.

As described above, while searching the outline pixels of the specified area on the pixel one by one, the line segmentation data table is searched at the same time, and line segmentation apex data is output. At the end of the process, it is confirmed that the two continuously searched contour pixels (the S-th contour pixel and the (S+1)-th contour pixel) match the contour search process start pixel and the second contour pixel. This is performed after confirmation in the pixel search unit 400.

Next, the operations and processing of the contour pixel search section 400 and the line segment approximation processing section 500 will be explained in more detail.

The contour pixel search unit 400 will be explained based on FIG.

The address generation circuit 406 for pixel readout reads the address 418 of the previous contour pixel, adds the search address (relative address) 416 sent from the line segment approximation processing unit 500 to this, and generates the pixel readout address 419. Output.

The pixel reading circuit 40 inputs this, reads the corresponding pixel value 411 from the image memory 300, and outputs it to the next comparison circuit 402.

The comparison circuit 402 compares the pixel value 411 and the threshold value 412.
and outputs binarized data 420.
The contour pixel determination circuit 403 uses this binary data 4
20 and the area determination value 413, and outputs a contour pixel determination flag 417 to the line segment approximation processing unit 500, and also outputs an address registration instruction flag 414 if it is determined to be a contour pixel. In response to this flag instruction, the contour pixel recording circuit 405 rewrites the address 419 to the contour pixel address 415 and records it in the line segmentation information memory 600.

The area pixel judgment value registration circuit 404 registers the first pixel of the area.
The binarized data 420 of the th contour pixel is input, and the area determination value 421 is stored in the line segmentation information memory 6.
Store to 00.

The line segment approximation processing section 500 will be explained based on FIG.

The address reading circuit 501 for contour search reads the data search address 5 from the line segmentation information memory 600.
11 is input, the search address (relative address) 512 for searching the next contour pixel is read from the line segment approximation data memory 200 in accordance with this, and this address information 516 ( In FIG. 4, it is sent as 416) and an address update flag 513 is output.

The address update circuit 502 receives this flag and outputs an update address 514 that updates the previously received data search address 511 to the next data search address to the line segmentation information memory 600.

Determination flag 5 indicating that a new contour pixel has been found
17 (417 in FIG. 4) is the contour pixel search unit 40
0, the line segment approximation data reading circuit 503 reads line segment approximation data 518 from the line segment approximation data memory 200 in accordance with the data search address 515.

The discrimination circuit 504 discriminates this data, and when the line division end point is confirmed, it sends out the end point processing instruction flag 519, and the end point processing circuit 505 reads the end point address 520 from the line division information memory 600, It is converted into differentiation apex data 52 and recorded in the apex data memory 700. Further, the next line segmentation data search address 522 is recorded in the line segmentation information memory 600. If the line division end point is not reached, the determination circuit 504 determines the address 523 of the area where the next contour pixel search address data is stored.
Output.

As described above, when approximating the outline of a specified area on an image with line segments and outputting polygonal representation data, instead of performing area tracking processing and line segment approximation calculation each time, By storing patterned line segment approximation data, line segmentation processing can be performed at high speed through efficient data search processing.

〔Effect of the invention〕

As described above in detail, according to the present invention, it is possible to realize a contour pixel line line differentiation device that performs line separation processing at high speed for continuous contour pixel strings while maintaining a predetermined connection relationship. By adding visual functions to robots, robots, etc., significant effects can be obtained in improving the functionality, efficiency, and reliability of automated work processes.

[Brief explanation of drawings]

FIG. 1 is a diagram showing the relationship between neighboring pixels for a designated pixel;
FIG. 2 is a format diagram of line segment approximation data according to the present invention, FIG. 3 is a block diagram of an embodiment of the contour pixel string line differentiation device, and FIG. 4 is an implementation of the contour pixel search section. Example Block Diagram FIG. 5 is a block diagram of one embodiment of the same line segment approximation processing section. 100... Control unit, 200... Line segment approximation data memory, 300... Image memory, 400... Contour pixel search unit, 500... Line segment approximation processing unit, 600... Line segmentation information memory, 600... Vertex data memory.

Claims (1)

[Claims] 1. In a device that performs line segment approximation for a contour pixel sequence of a digital image, for each type of point sequence pattern recognized as an approximate line segment, the following conditions are determined as part of each point sequence pattern. A line segment approximation data memory in which a pattern of satisfied pixels is stored in advance, and contour pixels connected to the pixel for each pixel at the end point of a certain approximation line segment on a certain contour outer periphery of a digital image are sequentially calculated by referring to the data memory. and a data memory for storing end points of each of the plurality of approximate line segments obtained by the means as apex data of each approximate line segment. Pixel column line differentiation device. 2. The means for obtaining the series of approximate line segments refers to the data memory to determine candidate pixels that should become contour pixels connected to the end point pixel, and selects the continuous contour pixels from the candidate pixels according to a predetermined threshold value. 2. The contour pixel column line segmentation device according to claim 1, wherein the device is a means for segmenting contour pixel columns and lines. 3. The means for obtaining the series of approximate line segments is such that when there are no contour pixels that are connected to the pixels at the end point and should become part of the approximate line segment, the approximate line segment is considered to be complete and the end point is determined. 2. The contour pixel column line segmentation device according to claim 1, characterized in that the device registers the vertex data in the vertex data memory and searches for another approximate line segment.