JPH026107B2 - - Google Patents

Description

[Detailed Description of the Invention] (1) Technical Field of the Invention The present invention relates to a closed loop representing the outer circumference of an object (referred to as an outer loop) with respect to a large number of closed loops constituting a contour figure extracted from a binarized image of a plurality of objects.
The present invention relates to a contour figure recognition method having an inner/outer identifying means for distinguishing between a closed loop (referred to as an inner loop) representing a hole in an object and determining which outer loop includes the inner loop.

(2) Conventional technology and problems FIGS. 1a and 1b are explanatory diagrams of contour figures.

When a binary image of multiple objects A, B, and C shown in figure a is expressed as a contour figure in figure b, a closed loop is traced as shown by the arrow from the x mark shown in the figure as a starting point, and loops 1 to 6 are traced. Extract. In this case, since both hole information and outer circumference information are similarly extracted as one closed loop, it is important to clarify the relationship between each closed loop.

Conventionally, there are two typical methods to solve this problem: (a) A method that returns to the binarized image and makes a decision.

(b) A method in which a closed loop is scanned horizontally in one direction from an internal point, the number of times it intersects with other closed loops is checked, and judgments are made based on that value.

There is.

FIGS. 2a to 2c are explanatory diagrams of the method (a) above.
The principle is to examine the area around the contour point in a binarized image, and since tracking is counterclockwise, if the right side is the background and the left side is the object in the direction of travel, it is determined that it is an external loop. If the relationship is the opposite, it is determined that there is an inner loop. That is, in the case of the object B with a hole shown in FIG. 1A, FIG. Figure c is an enlarged view of the internal loop section, showing the opposite relationship to figure b. However, although this method can distinguish between inside and outside, it does not know the inclusion relationship between each loop,
A further drawback is that the binarized image must be saved even after contour point extraction.

FIGS. 3a and 3b are explanatory diagrams of the method (b) above.
The principle is to scan in one horizontal direction (left side in the figure) from the internal point P of the closed loop to be identified, check the number of intersections with other closed loops, and if it is an odd number (~), then the external loop (closed loop 2 in (see internal point P ₂ of closed loop 3 in FIG. 3a), and if there is an even number (~), it is determined that it is an internal loop (see internal point P ₃ of closed loop 3 in FIG. 3a). However, with this method, it is difficult to reliably set the internal point P of each closed loop, and the third
As shown in FIG. b, depending on the set position of P, other closed loop edges and vertices may exist on the scanning line, and this has the disadvantage that it cannot be determined based on the number of intersections.

(3) Purpose of the Invention The purpose of the present invention is to provide a contour figure recognition method capable of distinguishing whether a plurality of closed loops extracted from a binarized image of a plurality of objects are external loops or inner loops, and determining their inclusion relationship. It is.

(4) Structure of the Invention In order to achieve the above object, the contour figure recognition method of the present invention represents the outer periphery of an object with respect to a plurality of closed loops that constitute contour figures extracted from binary images of a plurality of objects. Closed loop (referred to as outer loop)
and a closed loop (referred to as an inner loop) representing a hole in an object, and determines which outer loop the inner loop is included in. While tracing the closed loop from the binarized image in a predetermined rotational direction, assigning to each contour point a connection flag indicating the adjacency relationship with the preceding and succeeding contour points, and a loop number flag indicating the order in which the closed loop was traced, Scans in the horizontal direction from any starting point of the closed loop to be identified, compares the forward connected flag and backward connected flag of the contour point of the closed loop that first intersects, and identifies the inside and outside of the closed loop based on the size relationship. This is a characteristic feature.

(5) Embodiments of the Invention Although the creation of the contour figure shown in FIG. 1 b from the binarized image shown in FIG. It determines the relationship between inner and outer loops. In other words, each closed loop in Figure b starts scanning horizontally from the upper left corner of the screen and tracks counterclockwise from the first point encountered as the starting point s, and is distinguished by a loop number indicating the order in which the starting point was detected. ing. The closed loop with loop number i will be referred to as closed loop i. Then, this number is used as a loop number flag and contour points forming each closed loop are assigned.

Furthermore, a concatenation flag is used as another flag. FIG. 4 shows eight types of adjacency relationships for a certain contour point and the values of connection flags set at each position. The connection flag is divided into two parts: the forward connection flag and the backward connection flag.
Both values are assigned to each contour point.

FIGS. 5a and 5b specifically show the method of assigning two connection flags. As shown in figure a, while tracing the closed loop counterclockwise, the contour points are
The position of the contour point P _i-1 immediately preceding the contour point Pi is assigned as a backward connection flag, and the position of the contour point P _i+1 immediately preceding the contour point Pi is assigned as the forward connection flag. In FIG. 4b, the connection flags shown in FIG. 4 are given as rear and front connection flags, respectively, according to the arrows entering and exiting each contour point from P _i-1 to _{P i+2} .

FIGS. 6a to 6e are diagrams explaining the principle of internal and external identification using the loop number flag and connection flag.

First, attention is paid to the contour point of the closed loop j that first intersects by scanning horizontally to the left from the starting point s of a general closed loop i to be identified. Then, the values of the forward connection flag and the backward connection flag of the contour point of interest are compared, and if the former value is large, it is determined that closed loop i is an inner loop included in closed loop j, and in the opposite case, it is determined that they are independent. to decide.

In Figure 6a, there are three loops l, m, and n, loop n is included in loop m, and loop l
is independent of loop m.

When closed loop m and closed loop l exist independently, the two connection flags of the contour point Pj of the closed loop l scanned from the starting point s of the closed loop m and crossed are the same as the adjacency relationship of the contour point Pj shown in the figure b. Due to the two connection flags aj and bj and the loop number flag l shown in FIG. In addition, if closed loop n is included in closed loop m, the two connection flags of the contour point Pi obtained in the same way are the adjacency relationship of the contour point Pi shown in c of the same figure, and the two connection flags of the contour point Pi shown in d of the same figure. Due to ai, bi, and loop number flag m, the forward concatenation flag bi>
It is related to the backward link flag ai. Therefore,
By scanning horizontally to the left from the starting point of a certain closed loop and making judgments based on the above principle on all intersecting contour points, it becomes possible to identify the inside and outside of the closed loop in the entire contour figure.

If the same closed loop intersects more than once, only the first intersection is inspected and the other points are ignored. Furthermore, if a closed loop including the closed loop is detected during scanning, it is immediately determined to be an internal loop, and scanning is terminated. Then, by performing similar identification processing on all closed loops present on the screen, it becomes possible to clarify the positional relationship of the completely closed loops.

FIGS. 7a to 7f specifically show all possible connections of intersecting contour points when closed loop i is included in closed loop j. That is, the possible forward connection flags for each backward connection flag at the intersection contour point are shown by broken lines. It is clear that this result can be obtained from FIGS. 4 and 6e.

FIG. 8 shows an example of processing using the figure recognition method of the present invention.

In the figure, closed loops 11 and 12 are identified as external loops because they do not intersect with other closed loops even if they are scanned horizontally to the left from their starting points S ₁ and S ₂ . When the closed loop 13 scans from the starting point _S3 , the intersection _P1 can be detected, and when its connection flag is checked, the forward connection flag > the backward connection flag, so it is included in the closed loop 11 whose contour point element is the intersection _P1 . The inner loop is identified as an inner loop. To identify the inside and outside of the closed loop 14, first, scanning is performed from the starting point _S4 to detect the intersection _P2 . Next, when the connection flag of _P2 is checked, it is found that it is independent of the closed loop 14, so scanning is continued further. next intersection
Since P ₃ is a contour point that constitutes the closed loop 13 that has already been examined, it is excluded from the points to be determined, and the scanning is further advanced to detect the intersection P ₄ . And the intersection
When checking the concatenation flag of P ₄ , the forward concatenation flag >
Since it is the backward concatenation flag, at this point,
It is identified as an inner loop included in the closed loop 11. Next, the closed loop 15 scans from the starting point S ₅ and detects the intersection P ₅ , and when a discrimination judgment is made, the closed loop 1
2, and even if the scanning is continued thereafter, it will not intersect with another closed loop, so it is identified as an external loop. Finally, the closed loop 16 is identified as an inner loop included in the closed loop 15 as a result of the identification judgment for the intersection point _P6 .

FIG. 9 is an explanatory diagram of the configuration of an embodiment of the present invention.
In the figure, 21 is an image memory in which information on a binarized image is stored, and 22 is a closed-loop contour point extraction section. This closed-loop contour point extracting unit 22 traces the contour line counterclockwise with respect to the binarized image in the image memory 21, and at the same time assigns two connection flags and a loop number flag to each contour point. Stored in table 23. A closed loop start point extraction section 24, an intersection extraction section 25, and an intersection connection flag and loop number flag extraction section 26 which exchange data with this closed loop contour point table 23 are provided. A closed loop start point extraction section 24 extracts the start point of the closed loop to be identified, and an intersection point extraction section 25 performs scanning horizontally to the left to extract points of intersection with other closed loops.

Next, the intersection connection flag and loop number flag extraction unit 26 extracts the connection flag and loop number of the extracted intersection, and the internal/external determination unit 27 compares the forward connection flag and the backward connection flag, and The internal and external identification judgments are made according to the principles shown in Figures a to e. The intersection extraction unit 25 for a certain closed loop;
Intersection connection flag and loop number flag extraction unit 2
6. Repeat the process in the internal/external judgment unit 27 until the judgment of the inner loop is made or until the scanning progresses to the left end of the screen and the judgment of the outer loop is made.1
Finish the internal/external identification for the two closed loops. Then, the closed loop start point extraction unit 24 moves on to identifying the next closed loop, and performs similar identification processing in order from the closed loop with the smallest loop number to clarify the positional relationships of all the closed loops on the screen.

(6) Effects of the Invention As explained above, according to the present invention, internal and external identification of multiple closed loops extracted from binarized images of multiple objects is performed using a connection flag and a loop number flag. It is possible to distinguish between closed loops and determine their inclusion relationships. This makes it possible to easily and without exception clarify the positional relationships of all closed loops on the screen, regardless of the shape of the figure or the positional relationships of multiple objects.

[Brief explanation of drawings]

1a, b to 3 a, b are explanatory diagrams of the conventional example, FIGS. 4 to 7 a to f are explanatory diagrams of the principle of the present invention, and FIG. 8 is an explanatory diagram of a processing example according to the present invention. , No. 9
The figure is a configuration explanatory diagram of an embodiment of the present invention, and in the figure,
1, 2, 5, 11, 12, 15 are external loops,
3, 4, 6, 13, 14, 16 are inner loops, 2
1 is an image memory, 22 is a closed loop contour point extraction unit,
Reference numeral 23 indicates a closed loop contour point table, 24 indicates a closed loop start point extraction section, 25 indicates an intersection extraction section, 26 indicates an intersection connection flag and loop number flag extraction section, and 27 indicates an internal/external determination section.

Claims (1)

[Claims] 1. Among a plurality of closed loops constituting a contour figure extracted from a binarized image of a plurality of objects, a closed loop representing the outer circumference of the object (referred to as an external loop) and a closed loop representing a hole in the object ( In the figure recognition device, the figure recognition device has an inner/outer identifying means for distinguishing between the inner loop and the outer loop and determining which outer loop the inner loop is included in. While tracking in the rotational direction, a connection flag indicating the adjacency relationship between the contour points before and after the contour point and a loop number flag indicating the order in which the closed loop is tracked is assigned to each contour point, and the process starts from any starting point of the closed loop to be identified. A contour figure recognition method that scans in the horizontal direction, compares the forward connection flag and the backward connection flag of the contour point of the closed loop that first intersects, and identifies the inside and outside of the closed loop based on the magnitude relationship.