JPS6174077A - Segment pattern preparing system - Google Patents

Abstract

PURPOSE:To compress segment pattern data which becomes necessary in a high speed polygonal approximation by expressing a segment pattern as the system of the direction of travel in respective outline points. CONSTITUTION:Four rotating symmetrical segment patterns of upward and downward and right and left are represented and expressed by one segment pattern and stored in a segment pattern memory 115. When the direction of the first crossover point of the segment pattern is limited to the right and collated with an actual point row, the later direction of travel is reversed when the first crossover point of the point row is the left. Further, by sharing the data of the part in common between different segment patterns as a whole, namely, the partial row of the direction of travel, a necessary data quantity is decreased and is stored in the segment pattern memory 115.

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, in the Proceedings of the National Conference of the Institute of Electrical Engineers of Japan, published on June 10, 1988 [13], paper number 1340, it says:
The part based on line segmentation pattern matching is explained in detail.

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. Met.

[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. Our goal is to provide the following.

[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 on the top, bottom, left and right is rotationally symmetrical.

In the case of polygonal nobby approximation, the direction of the line segment 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.

If we look at this 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 line segment patterns and reversing the subsequent direction of movement from side to side according to the direction of movement at the first bending point, the shape of the two line segment patterns is divided into one part. The data is expressed as follows.

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

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

Reference numerals 112 to 114 relate to pattern matching processing, 112 is a common area extraction unit, 115 is a common area memo IJ, and 114 is a recognition processing unit. Note that such an image processing apparatus is composed of a processor, a memory, and hard circuits such as 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, and then input to the image memory 102 as grayscale image data and binary image data. be remembered.

The image data stored in the image memory 102 is first determined by the preprocessing unit 103 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 memo January 4 Ni g self 1.・Being forced.

Next, the contour extracting unit 105 determines a search starting point based on the position information of the representative point, sequentially searches for contour pixels in the specified region on the image, and stores the central coordinate value in the contour memory 105. to be memorized.

Based on the center coordinate values, the line segmentation processing unit 107 traces the line of points representing the center of the contour pixel point by point, and compares it with the line segment pattern data preset in the line segment pattern memory 115 to form a line segment. The coordinates of 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 10 days. 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 designated 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
Store it in 1. 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 10) and the dictionary pattern (stored in the dictionary pattern memory 109) based on the characteristics of both. After converting the coordinates on the input cover turn side so that they match (for example, so that the centers of gravity match or the directions of the principal axes of inertia match), the common area (seed shape) of both patterns is converted in the same way. is obtained as a vertex sequence and recorded in the common area memory 115.

Finally, the recognition processing unit 114 calculates the area of the common area (seed 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 the two patterns do not match and there are multiple dictionary patterns, the second. The matching process with the sixth dictionary pattern is repeated in the same way. Note that the recognition processing unit 114 also outputs the position and orientation information of the input pattern based on the relative positions of both matched patterns before conversion.

In the above series of image processing, the main part of the present invention is
Next, a method of creating a line segment pattern used in the line segment pattern memory 115 and processing using the same will be described.

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 of thinking about contour lines: (A) and (B) that the center of the contour pixel is the contour line, and the other way of thinking that the boundary line between the area 1 and f-view pixels is the contour line. (0),
There are two ways (D), and in addition, for the adjacent state of continuous contour points, there is a 4-connection (B) t (
D), and 8-connection (A) that also takes into account diagonal descent,
There are two ways (CI). Therefore, for contour tracing (
There are a total of four methods: A) to (D). However, among these, the boundary 8 connection (0) is meaningless because it does not uniquely correspond to the pixel value.

In each case, the direction of tracking includes (-), (4
5G6. ), there are possibilities as shown in (i). Hereinafter, a case will be described in which a contour line is traced using boundary 4 connection (D).

An example of a contour point sequence is shown in FIG. Each contour point has its own direction of movement, as indicated by the arrow in the figure, and the shape of the contour line is represented by a column of this direction of movement. If a restriction is placed on the length, the sequence of points that can be considered as a line segment under certain conditions becomes a finite number of sequences in the direction of travel. The conditions for considering it as a line segment are, for example,
For example, a method is used in which a maximum permissible distance from the center line is determined, and a line segment is defined as a sequence of points where 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 M minute pattern is 3XrL, as shown in Figure 4 (4).
This is stored in the memory 115 as pattern data. The second subscript value of the array corresponds to rL points on the line segment pattern represented by a sequence of points, and the first subscript value corresponds to the three directions of travel at each point, that is, 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, starting point "0"
When the direction of travel is determined to be a right turn at ', 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, the detected point is regarded as the end point of the line segment.
Register this as the vertex of the polygon. In Fig. 4<h>, the starting point of the line segment pattern is ゛0 at the starting point S of the line segment.
Tracing is started from ', end mark E ND is detected at point E, this point '333'' is set as the vertex of the polygon, the pointer of the line segment pattern is returned to the starting point 10'', and tracing of a new line segment is started. 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 points (for example, the three points in the fourth figure) are registered as the first vertices of the polygon, and the line segment pattern pointer is initialized to ``0'' (step 501).

Thereafter, the processes of steps 501 to 507 are repeated.

First, the traveling direction at the tracking start point S is determined (step 502). Here, a method for determining the traveling direction will be explained using FIG. 3. In FIG. 3, it is assumed that pixel A is included in the component area.

First, check whether pixel B is included in the component area,
If not included, the direction of travel will be a right turn. Next, it is checked whether the pixel B is included in the component area (D), and if the pixel B 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 to determine whether a pixel is included in the component area. For example, if it is a binary image, outline memo 1J
It can be determined whether the value read from 106 is 1' or 0.

Next, the slot pointed to by the pointer of the line segment pattern is referred to, and the next pointer is selected according to the direction of movement. (Step 503). For example, in the case of FIG.
In this case, the traveling direction is the 4th area (,
! )) is a right turn, so the pointer of ′
Select “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 points are returned to 05 (step 505). .

Next, proceed to the next contour point according to the traveling direction (step 506), and check the end condition, for example, whether or not the contour has been circled once and returned to the tracking start point S.Step 507
), steps 502 to 507 are repeated until the termination condition is satisfied.

For example, when tracing the contour line of FIG. 4()υ according to the line segment pattern data of FIG. 4(cL), pointer 10'
It starts from , and advances to the next pointer 187' according to the direction of travel (right turn). Thereafter, the process moves to the next contour tracing, determines the traveling direction (straight ahead), and selects the pointer 315'. After that, tracking is performed in the same way, and the end mark Ei
When a pointer indicating ND is detected, the pointer 353 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 4 (-), the first bending point of a pair of axially symmetric line segments is a right turn (or left turn).
Since there is only one side of the line segment pattern, the flag is held in this loop, 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 sides of the line segment pattern are Use it in reverse.

Since the line segment pattern shown in FIG. 4 (-) 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 the line segment pattern are not related to the processing procedure of polygon approximation, by replacing line segment patterns created using various straight line criteria, operations such as adjusting the roughness of polygon approximation can be easily performed using the program. This can be easily done without changing the hardware or hardware.

Next, a procedure for creating a line segment pattern as shown in FIG. 4(a) 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 allowed traveling directions at each point are written on the condition that the line is a straight line.

To create a line pattern, at each point on the line pattern, add new points according to the three directions of progression,
It is determined whether the point sequence obtained by adding this 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 added new point, write that number as a point, and 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. (This method is described, for example, on pages 53 to 56 of "Artificial Intelligence" published by Corona Publishing on April 15, 1970.) The above is the basic idea of creating a line segment pattern.

The flow of processing will be explained step by step using FIG. 6 below.

The line segment pattern is represented by an array T. Let C be a counter that indicates how far a line segment pattern is used. Also,
In order to compress axially symmetrical patterns, a flag is set to indicate whether the point sequence has already bent to the right or left, or whether it continues to move straight ahead, and this flag is set to indicate whether the point sequence has already bent to the right or left, or whether it continues to move straight. Create only one pattern and compress the data in half.

First, as shown in FIG. 6 (α), the point sequence and counter are initialized. For example, the first two points of the point sequence are (010)
and fixed at (1,0). As a result, the line segment pattern is limited to one of the four rotationally symmetric patterns, and the data is compressed. Leave the flag turned off. Also, clear the counter to 0.

Next, for the point (11O) and the 0th slot of the line segment pattern, a point string extension process (step 602) is performed to extend the point string in three directions of travel (left turn, straight turn, right turn) to determine a straight line. . 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. Note that this figure 6) is a diagram showing the subroutine of step 602 in FIG. 6(eL).

First, as shown in Figure 6 (8), the point to be processed is specified by P. This pointer P is a local variable within the point sequence extension process, and is fixed to the value of O at the beginning of the point sequence extension process ( Step 611).The value of 0 itself changes during processing.

Next, the counter and point sequence length are incremented in 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 6
14). This pointer entry process is shown in Figure 6 (G).
As shown in FIG. 3, pointer entry processing is performed only when the flag is on (steps 621 to 625), and when it is off, an end mark END is written (step 627). This limits the direction of the first bending point to the right. Next, the traveling direction is set to go straight, 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 77-g is turned on.

Next, regarding each pointer entry process in Fig. 6 (4),
This will be explained in detail according to figure (G). FIG. 6(0) is a diagram showing the subroutines of steps 614, 615, and 616 in FIG. First, a point sequence is extended (step 622), and it is determined whether the length of the point sequence exceeds an allowable value (step 625). As a result, if it exceeds the limit, an end mark is entered (step 627).
, if not, it is determined whether the point sequence to which the analyzed point is added is a straight line (step 625). 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 the counter Q and create a new slot,
Enter this counter value as a pointer.Step 62
5) For this new point, perform the point sequence extension process shown in Figure 6) to increment the length of the point sequence (step 626). In this way, Figure 4 (4
) is created. That is, pointer entry processing is performed by incrementing a counter from pointer O, and if the first turning point is on the left, an end mark is written, and pointer entry processing for straight travel is continued 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 is considered to be a straight line based on a certain standard, and includes all of the O point series, and does not include dot series of the same shape twice, but when viewed partially, it is shown in Figure 7. (α), (As shown in the figure, there are parts O and D of the same shape. When this part of the same shape includes the end point of the line segment, the point sequence data attached to that part has double equivalent data. The data can be compressed by representing one of them 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, unnecessary portions are erased going backwards from this point.

First, as shown in FIG. 8(cL), the line segment pattern array is scanned to find the end point, and erasure marks are written in all but the first 1A1 (step 801).

Next, the line segment pattern array is scanned and a point sequence integration process is performed to erase all but one point that includes a structure (
Step 802).

The point sequence integration process will be explained in detail using FIG. 8(k). First, pointer J to be sampled is designated. Then, the next workpiece to be sampled is cleared (step aii). Next, the line segment pattern is scanned, points including J are searched for, and a point sequence erasing process is performed in which erasing marks are written on all points except the first A1 (step 812). Next, if A1 exists (step 813), similar point sequence integration processing is performed for A1 (step 814).

Finally, erase all slots marked with erasure marks, pack the data, and exit (step 803).
.

By performing the above processing, in the case of 4-connection, it is possible to replace the expression format of the line segment pattern from the series of feeding directions at each of the four points (up, down, left, and right) to the series of relative traveling directions. Therefore, four rotationally symmetrical line segment patterns in the vertical and horizontal directions 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, by sharing the data of the common part between different line segment patterns as a whole, that is, the partial sequence in the advancing direction, the amount of data required is reduced, and the line segment pattern memory 1
15 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 drawings]

FIG. 1 is a block diagram showing an embodiment of an image processing device used in the present invention, FIG. 2 is a diagram for explaining a contour tracing method in polygon approximation processing, and FIG. FIG. 4 is a diagram showing an example of line segment pattern expression format and polygon approximation. FIG. 5 is a flowchart showing the procedure of polygon approximation. FIG.
7 is a diagram showing an example of line segment patterns having common parts, and FIG. 8 is a 70-chart of data compression processing for removing common parts of line segment patterns. 101... Input control section, 102... Image memory, 103... Preprocessing section, 104... Area information memory, 105... Contour extraction section, 106... Contour memory, 107... Line segmentation processing unit, 108... Line segmentation information memory, 109... Dictionary pattern memory, 110... Area feature extraction unit, 111... Area feature memory, 112... Common area extraction unit, 113. ... common area memory, 114 ... recognition processing section, 100 ... control section, 115 ... line segment pattern memory. Representative patent attorney Akira Takahashi Taiyo 1 Figure 2 (A) (β) (: (1') (
8) (α) (J) (L:l)
Figure 3 Figure 5 Figure 6 Figure 6 (α) Figure 6 (C) Figure 7 Figure 8 (α) (6) Go to Step δ03

Claims (1)

[Scope of Claims] 1. Polygons of the part image are generated by comparing the contour point sequence of the part image with data stored in a line segment pattern memory that stores various line segment patterns required for line segment approximation. In an image processing device that performs approximation and performs recognition processing based on a polygon's vertex coordinate string, by replacing the expression format of line segment patterns from a series of absolute traveling directions to a series of relative traveling directions. A line segment pattern creation method characterized in that a rotationally symmetrical line segment pattern represented by an absolute direction of travel is represented by one line segment pattern represented by a relative direction, and stored in a line segment pattern memory. method. 2. The line segment pattern is expressed in a series of three relative traveling directions: forward, right turn, and left turn, and is stored in a line segment pattern memory. Line segment pattern creation method described in section. 3. Among the line segment patterns, the axis-symmetric line segment pattern is
If the direction of the first bending point is limited to one of the two and stored in the line segment pattern memory, and when comparing it with the contour point sequence, if the direction of the first bending point of the point sequence is opposite, Claim 1, characterized in that the traveling direction of the line segment pattern memory is reversed and compared with the data stored in the line segment pattern memory.
3. The line segment pattern creation method according to any one of Items 1 and 2. 4. The line segment pattern according to any one of claims 1 to 3, characterized in that a partial sequence in a common traveling direction of the line segment pattern is shared and stored in the line segment pattern memory. Line pattern creation method.