JPH0312348B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Application of the Invention] The present invention relates to a line segment pattern creation method used in a component recognition device using image processing. The present invention relates to a line segment pattern creation method suitable for performing a process of approximating a sequence of points) with line segments at high speed.

[Background of the invention]

Conventionally, it has been proposed to perform component recognition by approximating a component pattern into a polygon for the purpose of high-speed and flexible image processing. At this time, all line segment patterns are stored and the sides of the polygon are extracted at high speed by comparing the contour point sequence of the part with this. Regarding this, for example, the Showa period
It was published on March 10, 1988 in the Proceedings of the National Conference of the Institute of Electrical Engineers of Japan, Volume 13, Paper No. 1340, entitled ``Part recognition technology using line segmentation pattern matching.'' Further, it is detailed in Japanese Patent Application No. 58-27519 (Japanese Unexamined Patent Publication No. 59-154578), which was previously filed by the present applicant.

However, in such conventional methods, the line segment pattern data used in line segmentation processing includes all straight line patterns within a certain length, resulting in a large memory size, which poses a problem in terms of downsizing and economical equipment. It was hot.

[Purpose of the invention]

The purpose of the present invention is to solve the above-mentioned conventional problems, compress line segment pattern data necessary for high-speed polygon approximation, and provide a line segment pattern creation method that can be executed even by a small-scale image processing device. It is about providing.

[Summary of the invention]

In the present invention, pattern data is compressed by expressing a line segment pattern as a series of advancing directions at each contour point. That is,
Since the image is a two-dimensional matrix, when all line segment patterns are created, in the case of 4-connection, each set of 4 lines (top, bottom, left and right) is rotationally symmetrical. In the case of polygonal approximation, the direction of the part does not matter; only the shape matters. Therefore, there is no need to distinguish between these four lines. Therefore, if the direction of travel is expressed as the relative direction of left turn, forward movement, and right turn when heading to the next point with respect to the direction at each contour point, the four symmetrical line segment patterns are expressed in the same series. , the data is compressed by a factor of four.

Furthermore, the line segment patterns are axially symmetrical in pairs. When viewed as a traveling direction series, the left and right sides are reversed at each corresponding point. Therefore, in the present invention, by holding only one of the two, and following the direction of travel at the first bending point, the subsequent direction of travel is reversed left and right when necessary.
The shape of one line segment pattern is expressed by one piece of data.

Further, when there are a plurality of line segment patterns, even if their shapes are different as a whole, they may be partially common. Therefore, in the present invention, the data in this common portion is shared, thereby reducing the data and reducing the required memory size.

[Embodiments of the invention]

Embodiments of the present invention will be described in detail below with reference to the drawings.

FIG. 1 is a block diagram showing an embodiment of an image processing apparatus according to the present invention.

Here, 100 is a control unit that controls the flow of required processing for each unit described below. 10
1 to 104 are related to preprocessing, and 101 is
An input control unit, 102, an image memory, 103,
The preprocessing unit 104 is an area information memory. 1
05 and 106 are related to contour extraction processing, and 1
05 is a contour extracting unit, and 106 is a contour memory. Reference numerals 107 to 109 relate to line segmentation processing, 107 is a line segmentation processing unit, 115 is a line segment pattern memory, 108 is a line segmentation information memory, 1
09 is a dictionary pattern memory. 110 and 1
11 relates to region feature extraction processing; 110;
is a region feature extraction unit, and 111 is a region feature memory. 112 to 114 are related to pattern matching processing; 112 is a common area extraction unit;
13 is a common area memory, and 114 is a recognition processing unit. It should be noted that such an image processing device is composed of hardware circuits such as a processor, a memory, and an interface circuit.

First, image data input from a television camera (not shown) is digitized by the input control unit 101 and binarized using a predetermined threshold value, and then stored in the image memory 10 as grayscale image data and binary image data.
2 is input and stored.

The image data stored in the image memory 102 is
First, the preprocessing unit 103 determines which area on the image is to be the target object area, and then the position information of the representative point of that area is stored in the area information memory 104.
is memorized.

Next, the contour extraction unit 105 determines a search start point based on the position information of the representative point, sequentially searches for contour pixels in the specified area on the image, and stores the center coordinate value in the contour memory 106, for example. Make me remember.

Based on the center coordinate value, the line segmentation processing unit 107
traces the point sequence representing the center of the contour pixel point by point, approximates the line segment by comparing it with the line segment pattern data preset in the line segment pattern memory 115, and finds the end points of the line segment, that is, The coordinates of each vertex obtained by polygonally approximating the area are sequentially stored in the line segmentation information memory 108. The line division information is transferred to the dictionary pattern memory 109 when registering the dictionary pattern.

Further, the region feature extraction unit 110 obtains the features of the specified region (for example, area, center of gravity, principal axis of inertia, maximum length, perimeter, etc.) from the contents of the line segmentation information memory 108 and stores them in the region feature memory 111. When registering a dictionary pattern, its characteristic information is stored in the dictionary pattern memory 109.

Furthermore, the common area extracting unit 112 extracts the currently input pattern (stored in the line segmentation information memory 108) and the dictionary pattern (stored in the dictionary pattern memory 109) so that the characteristics of both so that they match (for example, so that the center of gravity coordinates match (for example, so that the center of gravity coordinates match, or the directions of the principal axes of inertia match, etc.)
After coordinate transformation on the input pattern side, the common area (product figure) of both patterns is similarly determined as a vertex sequence and recorded in the common area memory 113.

Finally, the recognition processing unit 114 calculates the area of the common area (product figure), calculates the ratio of this to the area of the dictionary pattern or the input pattern, and if the value exceeds a predetermined value, both patterns are It is determined that there is a match and the recognition result is output. if,
If the two patterns do not match and there are a plurality of dictionary patterns, or if there are second and third dictionary patterns, the matching process is repeated in the same way. Note that the recognition processing unit 114 also outputs position and orientation information of the input pattern based on the relative positions of both matching patterns before conversion.

In the above series of image processing, a method for creating a line segment pattern used in the line segment pattern memory 115 and processing using the same, which are essential parts of the present invention, will be described next.

The polygonal approximation performed by the line segmentation processing unit 107 is a process in which the outline of the target image area is traced, and when a series of continuous outline points can be regarded as a straight line, both end points thereof are set as the vertices of the polygon.

As shown in Figure 2, there are two ways to think about contour lines: (A) and (B) where the center of the contour pixel is the contour line, and the other way is where the boundary line between area pixels and background pixels is the contour line.
There are two ways (C) and (D), and in addition, for the adjacency state of continuous contour points, only the vertical and horizontal adjacency is considered.
(B), (D), and 8-connection (A) that also takes into account diagonal adjacency,
There are two ways (C). Therefore, for contour tracing, (A)
There are a total of four methods: ~(D). However, among these, the boundary 8 connection (C) is meaningless because it does not uniquely correspond to the pixel value.

In each case, the direction of tracking is a, a',
There are possibilities as shown in b and d. From now on, boundary 4
The case of tracing contour lines using connection (D) will be explained.

An example of a contour point sequence is shown in FIG. Each contour point has a unique direction of travel, as shown by the arrow in the figure.
The shape of the contour line is represented by the columns in the traveling direction. If a restriction is placed on the length, the sequence of points that are considered to be line segments under certain conditions becomes a finite number of sequences in the advancing direction. The condition for considering a line segment is, for example, that a maximum permissible distance from the center line is determined, and a line segment is a point sequence in which all points satisfy this value.
Since the number and length of line segment patterns are finite, all line segment patterns can be created artificially.

FIG. 4 shows an example of a representation format of a line segment pattern and polygon approximation using the same.

The line segment pattern is 3xn as shown in Figure 4a.
This is stored in the memory 115 as pattern data. The second subscript value of the array corresponds to n points on the line segment pattern represented by a sequence of points, and the first subscript value corresponds to three directions of travel at each point, namely, left turn, straight ahead, and right turn. The contents of the array element are the number, ie, the pointer, of the next point when the direction of movement is determined at a certain point. For example, when the direction of travel is determined to be a right turn at the starting point "0", the number of the next point when traveling in that direction is indicated as "187". However, since there is a restriction that the point sequence can be regarded as a straight line, all three traveling directions are not always allowed at each point. An end mark END is written in the element corresponding to the prohibited direction, and when this is detected while tracing the contour line, the detected point is regarded as the end point of the line segment, and this is registered as the vertex of the polygon. do. In Fig. 4b, tracing starts from the starting point "0" of the line segment pattern at the starting point S of the line segment, and the end mark END is reached at point E.
Detect and set this point “333” as the vertex of the polygon,
Return the line segment pattern pointer to the starting point "0" and start tracing a new line segment. In the figure, the number of each point is the point number of the line segment pattern.

Next, the procedure of polygon approximation using this line segment pattern will be explained using FIG. 5 and taking FIG. 4 as an example. In polygonal approximation, contour points are traced one by one, and at the same time, a line segment pattern is traced by selecting a pointer according to the direction of movement at each point. First, set the tracking starting point, for example, point S in Figure 4b, to the first point of the polygon.
It is registered as a vertex and initialized by setting the line segment pattern pointer to "0" (step 501). From then on,
Repeat steps 501 to 507. First, determine the traveling direction at the tracking starting point S (step
502). Here, we will explain the third method of determining the direction of travel.
This will be explained using figures. In FIG. 3, it is assumed that pixel A is included in the component area. First, it is checked whether pixel B is included in the component area, and if it is not included, the traveling direction is set to be a right turn. Next, it is checked whether pixel B is included in the component area, and if it is not included, the moving direction is set to move forward, and if it is included, the moving direction is set to turn left. There are various methods for determining whether a pixel is included in a component area. For example, in the case of a binary image, determination can be made based on whether the value read from the contour memory 106 is "1" or "0".

Next, referring to the slot pointed by the line segment pattern pointer, the next pointer is selected according to the direction of travel (step 503). For example, in the case of Figure 4,
Referring to the area of pointer "0", in this case, since the direction of travel is a right turn as shown in Figure 4b,
Select the next pointer “187”. If the next pointer is the end mark END (step 504), the contour point at that point is newly registered in the line division information memory 108 as the vertex of the polygon, and the pointer is returned to "0" (step 505). .

Next, proceed to the next contour point according to the direction of travel (step 506), check the end condition, for example, whether or not the contour has been completed once and returned to the tracing start point S (step 507), and check the end condition. Steps 502 to 507 are repeated until the condition is satisfied.

For example, when tracing the contour line in Figure 4b according to the line segment pattern data in Figure 4a, start from pointer "0" and move to the next pointer "187" according to the direction of travel (right turn). move on. After that, move on to the next contour tracking, determine the direction of travel (straight ahead),
Select pointer “315”. Thereafter, tracking is performed in the same way, and when a pointer indicating the end mark END is detected, the pointer "333" at that time is registered as the vertex. Then, the coordinate position at this time is calculated based on the coordinate of the starting point and stored in the memory 108.

However, as shown in Figure 4a, out of a pair of axially symmetric line segment patterns, there is only one whose first turning point is a right turn (or left turn). is maintained, and after the first break point appears on the contour point sequence, when that break point is a left turn (right turn), the left and right of the line segment pattern is reversed and used.

Since the line segment pattern shown in FIG. 4a is constant data, it can be created offline and later loaded with the program. Therefore, there is no need to perform high-speed processing during creation.
In addition, since the contents of line segment patterns are not related to the processing procedure of polygon approximation, operations such as adjusting the roughness of polygon approximation can be programmed by replacing line segment patterns created using various straight line criteria. This can be easily done without changing the hardware or hardware.

Next, a procedure for creating a line segment pattern as shown in FIG. 4a will be explained. The line segment pattern is represented by a 3Xn array. The second subscript corresponds to each point on the line segment pattern, and the first subscript corresponds to the direction of movement at each point. The content is a pointer or end mark END that indicates the next point when the direction of travel is determined at each point. Therefore, a line segment pattern is a set of slots in which the permissible traveling directions at each point are written on the condition that the line is a straight line.

To create a line segment pattern, new points are added at each point on the line segment pattern according to the three directions of movement, and it is determined whether the added point sequence is a straight line. If it is not a straight line, create an end mark, if it is a straight line, create a new slot corresponding to the new point added, write that number as a pointer,
Repeat the same process for the new point. Continue the above steps until the line segment length reaches the allowable value. For this basic procedure, a method known as the vertical method in the state/space search method can be used.
(For details on this method, see, for example, April 15, 1970)
It is described on pages 53-56 of ``Artificial Intelligence'' published by Nihon Coronasha. ) The above is the basic idea of creating line segment patterns. The flow of processing will be explained step by step using FIG. 6 below.

The line segment pattern is represented by an array T. C is the counter that shows how far the line segment pattern is used.
shall be. Also, for compression of axisymmetric patterns,
By setting an on/off flag to indicate whether the point sequence has already bent to the right or left, or whether it continues to move only straight, and by restricting the initial bending direction to one direction, an axisymmetric pattern is created only in one direction, and the data is Compress in half.

First, as shown in FIG. 6a, the point sequence and counter are initialized. In the point sequence, the first two points are fixed to, for example, (0,0) and (1,0). This results in
The line segment pattern is one of the four rotationally symmetric patterns.
data is compressed. Leave the flag turned off. Also, clear the counter to 0.

Next, for the point (1,0) and the 0th slot of the line segment pattern, there are three directions of travel (left turn, straight ahead, right turn).
Point sequence extension processing (step 602) is performed to extend the point sequence and perform straight line determination. The point sequence extension process further includes the next point sequence extension process, and the extension is repeated one after another until the permissible length is reached. Details of the point sequence extension process will be explained with reference to FIG. 6b. Incidentally, FIG. 6b is a diagram showing the subroutine of step 602 in FIG. 6a.

First, as shown in Figure 6b, the point to be processed is set to P
Specify with. This pointer P is a local variable within the point sequence extension process, and is fixed to the value of C at the beginning of the point sequence extension process (step 611). The value of C itself changes during processing. Next, the counter and point sequence length are incremented (steps 612 and 613), and a new point is added assuming that the direction of travel is a left turn. That is, pointer entry processing (step 614) is performed.
This pointer entry process is as shown in Figure 6c.
Pointer entry processing is performed only if the flag is on (steps 621 to 625), and if it is off, an end mark END is entered (step 627). This results in
The first bending point direction is limited to the right. Next, the direction of travel is set to be straight ahead, and pointer entry processing is performed this time, regardless of the flag (step 615). Next, the direction of travel is set to right, a new point is added, the flag is turned on, and pointer entry processing is performed (step 616).
That is, after turning right even once, the flag is turned on.

Next, each pointer entry process shown in FIG. 6b will be explained in detail with reference to FIG. 6c. This figure 6c
6 is a diagram showing the subroutines of steps 614, 615, and 616 in FIG. 6b. First, a point sequence is extended (step 622), and it is determined whether the length of the point sequence exceeds an allowable value (step 623). As a result, if the line is exceeded, an end mark is written (step 627), and if it is not exceeded, it is determined whether the point sequence to which the new point has been added is a straight line (step 623), and if it is not a line, an end mark is written. Write (step
627). Any judgment criteria may be used as necessary. For example, a method is used in which a center line of a series of points is drawn using the least squares method and a maximum allowable value is set for the distance from this to each point. If it is a straight line, increment counter C and create a new slot.
This counter value is entered as a pointer (step 625), and the point sequence extension process shown in FIG. 6b is performed on this new point to increment the length of the point sequence (step 626). In this way,
A line segment pattern as shown in FIG. 4a is created. That is, the counter is incremented from pointer "0" and pointer entry processing is performed,
If the first turning point is on the left, an end mark is written, and the pointer writing process for straight travel is continued until the allowable value. Thereafter, pointer entry processing for turning right and then turning left is performed within the allowable value.

The line segment pattern created in this way includes all point sequences that are considered to be straight lines under certain standards, and does not include double point sequences of the same shape.
When viewed partially, there are portions C and D of the same shape as shown in FIGS. 7a and 7b. When this same-shaped part includes the end point of the line segment, the point sequence data corresponding to that part will have double equivalent data,
Data can be compressed by using one as a representative and erasing the others.

The procedure will be explained using FIG. Since the portion to be erased always includes the end point of the line segment, that is, the slot containing the end mark in all three directions, the unnecessary portions are erased going backwards from this point.

First, as shown in Figure 8a, scan the line segment pattern array to find the end point, and select the first point I
, and write erasure marks on all others (step 801). Next, the line segment pattern array is scanned and a point sequence integration process is performed in which all but one point containing I is deleted (step 802).

The point sequence integration process will be explained in detail using FIG. 8b. First, pointer J to be explored is specified. Then, the next exploration target I is cleared (step 811). Next, the line segment pattern is scanned, a point including J is searched for, and an erase mark is written on all points except the first point I (step
812). Next, if point I exists (step 813), a similar point sequence integration process is performed for point I (step 814).

Finally, all slots marked with erasure marks are erased, the data is packed, and the process ends (step 803).

By performing the above processing, in the case of 4-connection, the expression format of the line segment pattern can replace the series of absolute traveling directions at each of the four points (up, down, left, and right) with a series of relative traveling directions. Therefore, four rotationally symmetrical line segment patterns (up, down, left and right) can be representatively represented by one line segment pattern, and the size of the line segment pattern memory 115 can be compressed to one-fourth.

Also, when limiting the direction of the first breaking point of the line segment pattern to the right and comparing it with the actual point sequence, if the first breaking point of the point sequence is on the left, the subsequent direction of movement must be reversed. Accordingly, the line segment pattern memory 115 can be compressed in half.

Furthermore, the amount of data required is reduced by sharing the data of the common part between different line segment patterns as a whole, that is, the partial sequence in the traveling direction.
Line segment pattern memory 115 can be compressed.

〔Effect of the invention〕

As described above, according to the present invention, while taking advantage of polygon approximation processing in an image processing device, the required memory size can be significantly reduced, and the image processing device can be made smaller and more economical.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing one embodiment of an image processing device used in the present invention, and FIG. 2 is a diagram for explaining a contour tracing method in polygon approximation processing.
FIG. 3 is a diagram showing an example of a region outline, FIG. 4 is a diagram showing an example of the representation format of a line segment pattern and polygon approximation,
Figure 5 is a flowchart showing the procedure of polygon approximation, Figure 6 is a flowchart of line segment pattern creation processing, Figure 7 is a diagram showing an example of a line segment pattern having a common part, and Figure 8 is a line segment It is a flowchart of data compression processing for removing common parts of patterns. 101...Input control unit, 102...Image memory, 103...Preprocessing unit, 104...Region information memory, 105...Contour extraction unit, 106...Contour memory, 107...Line differentiation processing unit, 108... ...Line differentiation information memory, 109...Dictionary pattern memory,
110...Region feature extraction unit, 111...Region feature memory, 112...Common area extraction unit, 113...
Common area memory, 114... Recognition processing unit, 100
...Control unit, 115...Line segment pattern memory.

Claims (1)

[Scope of Claims] 1. A line segmentation pattern dictionary that stores various line segment patterns used in line segmentation processing that performs polygonal approximation of an input image using line segment patterns created in advance, A line segmentation pattern dictionary characterized in that a plurality of line segment patterns that are rotationally symmetrical to each other among the line segment patterns to be stored are represented and stored as one line segment pattern based on relative direction expression. 2. The line segment pattern dictionary according to claim 1, wherein the expression format of the line segment pattern is expressed and stored as a series of three relative traveling directions: forward, right turn, and left turn. . 3 Among the line segment patterns, the axis-symmetric line segment pattern is stored with the direction of the first bending point limited to one of the directions, and when comparing it with the contour point sequence of the image, the first bending point of the point sequence is When the direction of the bending point is reversed, the line according to claim 1 or 2, wherein the subsequent direction of movement can be reversed and compared with the stored line segment pattern. Differentiation pattern dictionary. 4. The line segmentation pattern dictionary according to any one of claims 1 to 3, wherein a partial sequence in a common direction of movement among the line segment patterns is shared and stored.