JPH0312347B2 - - 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) 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]

The line segment patterns are arranged in sets of two and are axially symmetrical. When viewed as a traveling direction series, the left and right sides are reversed at each corresponding point.
Therefore, in the present invention, the shapes of the two line segment patterns are made into one by holding only one of them and reversing the subsequent direction of movement from side to side according to the direction of movement at the first bending point when necessary. It is designed to be expressed using two pieces of data.

[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.
101 to 104 are related to preprocessing, and 101
is an input control unit; 102 is an image memory; 103
is a preprocessing unit, and 104 is an area information memory. 105 and 106 are related to contour extraction processing; 105 is a contour extraction unit; and 106 is a contour memory. 107 to 109 are related 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,
109 is a dictionary pattern memory. 110 and 111 are related to region feature extraction processing;
0 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.

First, the input image data is input to the input control unit 1.
After being digitized with 01 and binarized with a predetermined threshold, the data is input and stored in the image memory 102 as grayscale image data and binary image data.

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, for example, the center coordinate value in the contour memory 106. let

Based on the center coordinate values, the line segmentation processing unit 107 approximates the line segment by tracing the point sequence representing the center of the contour pixel one by one and comparing it with the line segment pattern data preset in the line segment pattern memory 115. Then, the end points of the line segment, that is, the coordinates of each vertex obtained by approximating the area to a polygon, 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 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 After performing coordinate transformation on the input pattern side so that they match (for example, so that the center of gravity coordinates match, or the principal axis of inertia directions match, etc.),
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, the matching process with the second and third dictionary patterns is repeated in the same way. Note that the recognition processing unit 114 also outputs position and orientation information of the input pattern from 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 (C), where the boundary line between area pixels and background pixels is the contour line.
There are two ways (D), and in addition, there are 4 connections (B) and (D) that consider only vertical and horizontal adjacency for the adjacency state of continuous contour points.
and 2 of 8 connections (A) and (C), which also take diagonal adjacency into account.
There is a street. Therefore, there are a total of four methods (A) to (D) for contour tracing. However, of these, 8 boundaries are connected
(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 3× as shown in Figure 4a.
It is represented by a two-dimensional array of n, and this is stored in the memory 115 as pattern data. second of array
The subscript value is n on the line segment pattern represented by a series of points.
points, and the first index value corresponds to the three directions of travel at each point, namely, turn left, go straight, and turn right. 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, the tracing start point, for example, point S in FIG. 4b, is registered as the first vertex of the polygon, and the line segment pattern pointer is initialized by setting it 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 be a left turn. 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 Figure 4a is constant data, it must be created offline.
It can be loaded later 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.
It is described on pages 53-56 of ``Artificial Intelligence'' published by Corona Publishing on May 15th. ) The above is the basic idea of creating line segment patterns. The flow of processing will be explained below with reference to FIG.

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 straight, and by restricting the direction of the initial bend to one direction, an axially symmetrical pattern is created only in one direction, and the data 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, a point sequence extension process (step 602) is performed for the point (1, 0) and the 0th throttle of the line segment pattern to extend the point sequence in three directions of travel (left turn, straight ahead, right turn) to determine a straight line. Let's do it. 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. Note that this Fig. 6b is a step of Fig. 6a.
602 is a diagram showing a subroutine.

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. FIG. 6c 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 end mark is exceeded, an end mark is entered (step
627), if not, 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 straight line, an end mark is written (step 627).
Any judgment criteria may be used as necessary. For example, a method is used in which the 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 to create a new slot, write this counter value as a pointer, and press (step
625) For this new point, perform the point sequence extension process shown in FIG. 6b, and increment the length of the point sequence (step 626). In this way, the fourth
A line segment pattern as shown in Figure a is created. That is, the counter is incremented from pointer "0" to perform pointer entry processing, and if the first break point is on the left, an end mark is entered,
Continue the pointer entry process for straight-ahead travel up to the allowable value.

Thereafter, pointer entry processing for a right turn and then a left turn 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, the direction of the first breaking point of the line segment pattern is limited to the right, and when comparing with the actual point sequence, if the first breaking point of the point sequence is on the left,
By reversing the subsequent direction of movement, the line segment pattern memory 115 can be compressed in half.

〔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 line segment patterns with common parts, and Figure 8 is a line segment diagram. 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)

[Claims] 1. In 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 that have been created in advance, For axially symmetrical line segment patterns, the line segment pattern is stored only in one of the line segment patterns, and when matching the contour point sequence of the image with the line segment pattern, the first point sequence of the A line segmentation pattern dictionary characterized in that when the direction of a bending point is reversed, the subsequent direction of movement can be reversed and compared with the stored line segment pattern.