JPH0464114B2 - - Google Patents

Description

[Detailed Description of the Invention] [Summary] In the field of image processing, especially figure recognition processing, in order to quickly obtain closed-loop information about figures, which is considered to be the most important, images are subjected to thinning and broken lines using known techniques. By doing so, graphic information is converted into a table, and loop detection is realized by searching the table.

[Industrial application field]

The present invention relates to a closed figure identification device that extracts a figure having a closed loop from figure data. Here, the closed figure (figure with a closed loop) refers to the question box in the flowchart shown in Figure 3a, the logic gate symbol in Figure 3b, and the like.

[Conventional technology]

Automatic input of design drawings, maps, etc. requires recognition of shapes. It is important for shapes to have closed loops, such as boxes in flowcharts, gate symbols in circuit diagrams, alphanumeric characters, etc., and this can provide useful information for separating shapes from other shapes and determining the type of shape. many. Therefore, if information indicating whether a figure has a closed loop or not, and if so, what kind of closed loop it has, can be quickly obtained, the figure cutout process and identification process can be performed efficiently.

Conventional closed-loop information extraction techniques can be roughly divided into the following two methods depending on the target data.

A method for directly extracting closed-loop information from a binary image (a) A method for extracting from raster data; as shown in Figure 4a, a binary image is raster scanned, and the obtained raster data, that is, changes from white pixels to black pixels. The outside and inside of _the figure are distinguished by using the converted data of P ₁ and point P ₂ that change from black pixel to white _pixel . _P1 ,
P ₂ , P ₁ , P ₂ , and finally P ₁ and P ₂ , but the part from P ₂ in the middle to P ₁ ) is a closed loop.

(b) Method of extraction by contour tracking processing; 4th
As shown in Figure b, this method calculates all the contours of a binary image and uses the internal contours as a closed loop.

Method for extracting closed-loop information from broken line data The binary image is thinned using line thinning technology, as shown in Figure 4c.
As shown in the figure, the closed loop is obtained by converting the data into broken line data and storing it in memory, and sequentially searching the broken line data. Most searches rely on the coordinates of polygonal lines.

[Problem that the invention seeks to solve]

However, (1) with the above method, it is not possible to clearly associate the extracted closed-loop information (sequence of contour points) with the figure to be cut out. That is, when a figure has a line width, the contour points and the center line of the figure do not match, so a figure with a closed loop cannot be accurately separated from other figures. In Figure 5a, closed-loop information is extracted from the original image of a thick line figure. Although the inner closed loop of the original image can be clearly extracted, it is not clear how much of the upper and lower line parts should be included in the outer closed loop. Instead, it ends at an appropriate point, so ambiguity remains.

In addition, (2) in the above method, the line data is arranged one-dimensionally in the main memory of the computer, and as shown in Figure 5b, for example, it starts from a line, progresses, and then branches. Or go to, the polygon line is followed using the coordinate value as a key, and if it can complete one cycle, it is considered a closed loop, so there is a part where it goes back and forth, and the order stored in the polygon table does not match the search order. So it takes time to explore.

In addition, in both the methods (3) and (3) above, determining the inside and outside of a figure is complicated. For example, in a case where there is a closed figure within another closed figure, as shown in FIG.

Furthermore, in the method (4) above, it is also necessary to search for parts of the figure that are unrelated to the closed loop. For example, as shown in FIG. 5d, if the closed loop is local and most of the remaining branches are open branches, all of these open branches are also searched, which is wasteful.

[Means for solving problems]

In the present invention, in order to solve the above-mentioned problem (1), line data is processed, and in order to solve the above-mentioned problem (2), a branch point table and an arc table suitable for search are used. In order to solve problem (3), the sum of the angle differences between the broken lines is calculated, and in order to solve problem (4), preprocessing is performed to delete unnecessary parts in advance.

That is, the present invention provides a closed figure identification device that extracts closed loop information from the data of a figure that has been thinned and broken lines.
, a branch table M3 indicating a group of line segments connected to a branch point of the figure, and an arc table storing the start and end line segments of the line segment group connecting an open end point or branch point of a line segment to the next open end point or branch point. M2 and
Open arc deletion mechanism P that accesses the broken line data memory and deletes arcs with open end points
1, mechanisms P2 and P3 that sequentially select each line segment of a non-open arc clockwise or counterclockwise and calculate the sum of the angular differences of adjacent line segments; The present invention is characterized by comprising a loop data creation mechanism P4 that stores each group of line segments as a closed loop in a loop data memory together with a flag indicating the direction followed.

[Operation] According to this method, since the polygonal line data is processed, closed loop information can also be expressed as a set of polygonal line data, and there is no mismatch between the figure and the loop information.

In addition, by using a preliminary table suitable for searching and deleting unnecessary parts in preprocessing, high-speed processing is possible.Furthermore, when searching the polygonal line data, the degree difference between each polygonal line is calculated, so by the sum of the differences, Outer loops and inner loops can be identified without unnecessary calculations.

〔Example〕

FIG. 2 shows the data structure that is the basis of the present invention. As a result of thinning and breaking lines for the figure, the second
Suppose that line segments 1, 2, . . . 9 in figure a are obtained. Data of these line segments 1, 2,...
are sequentially stored in the memory M1 as shown in FIG. This storage order is not necessarily the order of broken lines in the loop. The format of the line segment data is as shown in Figure 1e, where the starting and ending coordinates of the line segment are X1, Y1, X2,
It consists of Y2 and end point connection information N1, N2. N is 0 when the end point is open, 1 when it is a bend (there is one next line segment), and 2 when it is a branch. This thinned or broken line figure has open endpoints (endpoints with no line segment beyond this) a and b, and branching points, but the line segment or line that connects one endpoint or branching point to the next endpoint or branching point A subgroup is called an arc, and its starting and ending arcs are stored in the arc table M3 in FIG. 2c. Further, for branch points, a branch table M2 shown in FIG. 2d is provided. This shows a line segment that starts and ends at a branch point, and although the order does not matter, here it is assumed to be counterclockwise. Therefore, for a branch point, it is --(--, etc.), and for a branch point, it is --(--, etc.).

Since line segments with open end points do not constitute a loop, such line segments are excluded from processing targets (deletion of unnecessary portions) in the present invention. If this line segment removal is performed, the next line segment may have an open end point, but in this case, this line segment is also removed from the processing target. When open line segments are removed one after another in this way, if there is a loop, the branch point is reached and the removal of open line segments stops. Removal of this open line segment therefore results in the removal of open arcs.

Branch points also exist between open arcs, but since open arcs are removed, what remains in the end is only a closed figure, or only a plurality of closed figures and line segments connecting them. The latter is shown in Figure 1f.

FIG. 1 shows the configuration of an apparatus for identifying closed figures. M1 is a line data memory, M2 is a branch table, M3 is an arc table, and M4 is a loop data memory. P1 to P5 are processing units, and P1 performs the above-mentioned open arc deletion. This open arc deletion mechanism P1 reads end point information N1 or N2 of the line segments at both ends of each arc in the arc table M3 from the memory M1, checks it, and
If so, an unused flag is set for each line segment of the arc in the line segment data memory M1 as an open arc. In the case of Figure 2 a,
Arcs 1 and 3 are open arcs because one end point a and b of line segments 1 and 6 are open and N1 or N2 is 0. Therefore, line segments 1 and 6 in memory M1 are open arcs.
The unused data is flagged as unused. Arcs 2 and 4 are N1 of line segments 2 and 5, 7 and 9 at both ends,
Since neither N2 is 0, it is a non-open arc. An unused flag is also set in the arc table M3 for open arcs.

If the open arc is removed, it will look like Figure 2 f.
It will be a figure without whiskers, but if we consider the loop that goes around each area, we can go around the area with the left hand (touching the outline of the area with our left hand) and go around the inside as shown in the figure. It rotates to the right (clockwise), and when it rotates around the outside, it rotates to the left.
Treating each line segment as a vector, and finding the sum of the angular differences between adjacent vectors, we get 2π for clockwise rotation.
When the rotation is counterclockwise, it becomes -2π, so from this we can determine whether the rotation is counterclockwise or clockwise, and therefore whether it is an inner loop or an outer loop. The vector search mechanism P2 and the angle difference calculation mechanism P3 perform this process.

That is, the vector search mechanism P2 uses the arc table M
3 non-open arc is selected and the line segment number (vector number) is stored in register R1. Then, the angular difference calculating mechanism P3 calculates the angular difference between the vector of the number set last time and the vector of the number set this time in the register R1, and stores the sum of the previous angular difference. Assuming that the vector search mechanism P2 sequentially sets the number of the line segment within the arc from the line segment at the end of a certain non-open arc to the register R1 while referring to the arc table M3 and the broken line data memory M1, the angle difference calculation mechanism P3 The bending angle of the arc (the sum of the degree differences of each line segment) is calculated and stored. A branch point is reached at the end of the arc, but which line segment to select next can be determined from the branch table M2.

For example, if we select arc 2, set it in register R1 with the numbers of line segments 2, 3, ... 5, and find the sum of these angle differences, arc 2 ends at line segment 5, but at this time branch table M2 , and know that line segment 5 belongs to branch point B, and that line segments 6 and 7 follow it. If the above-mentioned unused flag is also attached to the branch table, it can be determined that the next processing target is line segment 7, and by referring to arc table M3, it can be determined that this belongs to arc 4. Therefore, arc 4 should be the next target to be processed.

A direction flag is attached to the line segment to be processed. If the line segment selection direction is from the starting point (From) to the ending point (To) of the line segment (vector), the positive direction is +, and if it is the opposite, it is the negative direction -. An example of this is shown in Figure 2g. The search direction is inward (clockwise)
There is an outer rotation (counterclockwise rotation), but this example is an inner rotation, and in this case, at the branch point, choose the one closest to the right in the direction of travel. This means that the line segments are arranged counterclockwise in the branch table, so simply select the next line segment.

If two loops share a part and are adjacent to each other, the search direction will be reversed even though the shared part has the same inner circumference, and the direction flag will be marked + and -. Also, the search direction is reversed in the outer (counterclockwise) portion of the non-shared portion. Therefore, one line segment is attached with positive and negative direction flags, and the line segment with these flags has been searched. The vector search mechanism checks the direction flag of the line segment, and if the positive and negative direction flags are attached, the vector number is no longer set in register R1. When all line segments in the polyline data memory M1 are marked with forward and reverse direction flags, the loop search ends.

When an arc is selected and there are no more line segments to be processed in that search direction, or when the sum of the angular differences becomes 2π (or -2π), or when returning to the beginning (from the first arc) The loop is closed when the starting point of the starting line segment and the ending point of the last line segment of the subsequent arc have the same coordinate values.
At this time, the loop data creation mechanism P4 assigns an ID to the loop, and registers the group of line segments of the loop in the loop table M4 together with flags indicating inner and outer loops. An overview of these processes in the order of processing is as follows.

Step 1: Arcs included in open arcs in the line data are excluded from processing. Repeat this until all open arcs are removed, then proceed to step 2.

Step 2: Select one arbitrary vector. If both the forward and reverse direction flags are attached to the vector, it is rejected and another vector is selected.Step 3: A search is performed in the direction where the vector is not flagged. In other words, in the case of the positive direction, the To side end point,
In the case of the opposite direction, search for a vector connected to the From side end point. Gives a direction flag to the vector. If the end point is a branch point, choose the one closest to the right from among multiple branch vectors (for clockwise rotation). If the corresponding vector is not found, it is determined that the loop is closed, it is registered in the loop table, and the process returns to step 2. Otherwise, repeat step 3.

Control mechanism P5 monitors and adjusts the movement of the entire mechanism. In a line figure like a checkerboard, there are loops that go around one eye, loops that go around two eyes, etc.
Although a large number of loops are possible, the present invention deals with only a small (inner) loop in which only one eye revolves, and a loop in which the entire eye revolves outward. Therefore, if a forward or reverse direction flag is attached to a line segment, the search for that line segment ends.

When turning clockwise, the sum of the angular differences of each line segment is 2π, which means that each vector V ₁ ,
The sum Σθi of the angular differences θ ₁ , θ ₂ , ... of V ₂ , ... is equal to the sum Σαi of the angles α ₁ , α ₂ , ... for each vector with respect to the point P in the loop, and after one round, Σαi = 2π By being. If it is counterclockwise, it is in the opposite direction, so Σαi = −2π
It is.

〔Effect of the invention〕

As explained above, according to the present invention, since the polygonal line data is processed, closed loop information can also be expressed as a set of polygonal line data, and there is no mismatch between the figure and the loop information. There is no need to associate images with loop contours. Also, since a spare table suitable for searching is used, high-speed processing is possible. Further, when searching for broken line data, the angle difference between broken lines can be found, and advantages such as being able to easily distinguish between outer loops and inner loops can be obtained.

[Brief explanation of the drawing]

Figure 1 is a block diagram showing the configuration of the present invention, Figure 2 is a block diagram showing the configuration of the present invention.
3 is an explanatory diagram of each part of the present invention, FIG. 3 is an explanatory diagram of a closed figure, FIG. 4 is an explanatory diagram of a conventional system, and FIG. 5 is an explanatory diagram of problems of the conventional system. In the drawing, M1 is a broken line data memory, M2 is an arc table, M3 is a branch table, P1 is an open arc deletion mechanism, P2 is a vector search mechanism, and P
3, P4 is a mechanism for calculating the sum of angular differences.

Claims (1)

[Scope of Claims] 1. A closed figure identification device that extracts closed loop information from the data of figures that have been thinned and broken lines, comprising: a broken line data memory M1 that stores the coordinates of both ends of each line segment of the figure, and end point connection information; , a branching table M3 indicating a group of line segments connected to a branching point of the figure, and an arc table M2 storing the start and end line segments of the line segment group connecting an open endpoint or branching point of a line segment to the next open endpoint or branching point. , an open arc deletion mechanism P1 that accesses the broken line data memory and deletes arcs with open end points, and selects each line segment of non-open arcs clockwise or counterclockwise one after another and calculates the sum of the angular differences between adjacent line segments. and a loop data creation mechanism P4 that stores each line segment group in a loop data memory as a closed loop when each line segment of a non-open arc is traced and a flag indicating the direction of the line segment is traced. Features a closed figure identification device.