JPH07129772A - Method and device for recognizing start and end points of arc - Google Patents

Abstract

(57) [Abstract] [Purpose] To provide a method for detecting the start and end points of a circular arc portion from a line figure, which requires a small amount of calculation and is not easily affected by noise. [Structure] A polygonal line is approximated to a polygonal line (step 2).
3) The end points of the arc are recognized (step 25). At the connection point between the arc and the straight line, the arc end point is recognized such that the line segment resulting from the broken line approximation is longer on the straight line side and shorter on the arc side, and the angle formed by the line segment on the straight line side and the line segment on the arc side is 2 This is done by using the fact that the two conditions, that is, not a right angle, but a large amount, are satisfied.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to feature extraction for a binary image, and more particularly, to recognize a starting point and an ending point of a circular arc portion in order to extract the circular arc portion from a given line figure.
The present invention relates to a method and an apparatus for recognizing start and end points of an arc.

[0002]

2. Description of the Related Art Feature extraction is performed on a line figure input by handwriting or a line figure read by an image scanner, and the line figure is composed of what kind of figure element (straight line, line segment, arc, etc.). Is being recognized. In this case, the input line graphic is rarely composed of only one graphic element, and is often one in which line segments and arcs are connected.

Here, a conventional method for extracting the end points (start point and end point) of an arc portion from a line figure will be described with reference to FIG. Here, a line pattern 91 as shown in FIG.
Is entered.

First, if necessary, a thinning process is performed, and then, as shown in FIG. 5B, the line figure 91 is divided into relatively fine vectors for vectorization. The obtained vector sequence is represented by v (1), v (2), ..., V (n). Then, an angle a (1), a formed between adjacent vectors
(2), ..., a (n-1) is calculated. The angle a (i) is the vector v
It is the angle formed by (i) and the vector v (i + 1). Then, the rate of change g (1), g (2), ..., G (n-2) of the value of this angle is obtained. The rate of change g (i) is represented by g (i) = g (i + 1) -g (i).

Then, the vectors whose change rate is 0 are grouped. In the example shown in FIG. 5B, groups A to C
3 groups are generated. Then, a group in which the angle a (i) between adjacent vectors is approximately 0 ° is defined as a straight line group, and the other groups are defined as arc groups.
If the rate of change g (i) changes and one side of this point is a straight line group and the other side is a circular arc group, this point is recognized as the end point of the circular arc, that is, either the start point or the end point. . With the above processing, the start and end points of the arc are extracted.

[0006]

In the above-described conventional arc start / end point recognition method, since the input line figure is divided into fine vectors, a large amount of computer power and calculation time are required, and the input is performed. There is a problem in that it is easily affected by noise such as camera shake contained in a line figure and requires preprocessing.

An object of the present invention is to provide a method and apparatus for recognizing the start and end points of an arc, which has a small amount of calculation and is not easily affected by noise.

[0008]

According to the method for recognizing the start and end points of an arc of the present invention, an input step of inputting a line figure and a polygonal line approximation process for the input line figure are performed to obtain a plurality of connected line segments. In the polygonal line approximation step of dividing the line figure, and when one line segment is selected from a plurality of line segments corresponding to the line figure and the selected line segment is set as a target line segment, the following two conditions and Both of the conditions; the length of one of the two line segments adjacent to the target line segment is the length of the target line segment and the length of the other line segment of the two line segments, respectively. Is larger than a predetermined ratio and is greater than a predetermined condition; the angle formed by the one line segment and the target line segment is not two right angles but is close to two right angles, and at least one of the following two conditions:
Condition: The length of the target line segment and the length of the other line segment are substantially equal, and the condition: the angle formed by the one line segment and the target line segment is formed by the target line segment and the other line segment. For each condition, which is almost equal to the angle, check whether the condition is satisfied, and if none of the checked conditions are not satisfied,
A circular arc end point recognition step of recognizing the connection point of the one line segment and the target line segment as an end point of a circular arc portion, and the circular arc end point recognition step is sequentially applied to each line segment corresponding to the line figure.

The arc start / end point recognition device of the present invention divides the line figure into a plurality of connected line segments by applying input means for inputting the line figure and a polygonal line approximation process to the input line figure. A polygonal line approximation unit, a storage unit that stores the plurality of line segments, and a line segment that is read from the storage unit one by one to be a target line segment, and the following two conditions and both of the following conditions; The length of one of the two line segments is larger than the length of the target line segment and the length of the other line segment of the two line segments by a predetermined ratio or more, The angle formed by the one line segment and the target line segment is not two right angles, but is close to two right angles, and at least one of the following two conditions and conditions; the length of the target line segment and the other line segment Conditions of approximately equal length;
The angle formed by the one line segment and the target line segment is substantially equal to the angle formed by the target line segment and the other line segment, and it is checked whether or not the condition is satisfied for each condition, and If there is nothing that does not hold, an arc end point recognition unit that recognizes the connection point of the one line segment and the target line segment as the end point of the arc portion.

[0010]

[Operation] When a polygonal line approximation process is applied to a line figure,
This line figure is approximated by a polygonal line consisting of several vertices and a line segment connecting these vertices. In this case, the distance between the vertices is long in the original line figure where the curvature is small, and is short where the curvature is large. In a general line figure, a straight line (line segment) is often connected before and after the arc portion.

Therefore, focusing on the connection point between the straight line portion and the circular arc portion, the condition; the line segment by the polygonal line approximation is longer on the straight line side and shorter on the arc side, and the condition is: the line segment on the straight line side and the line segment on the arc side. The angle between and is not 2
2 conditions are satisfied. Therefore, the point where these two conditions are satisfied is a candidate for the connection point of the straight line portion and the circular arc portion.
The condition is also a condition for preventing detection of a point that is bent in a V shape. In reality, these conditions may be satisfied even when a curve other than a circular arc is connected to a straight line. Therefore, it is necessary to confirm the establishment of at least one of the following two conditions: the condition; the lengths of the line segments on the arc side are almost equal; and the condition: the angles formed by two adjacent line segments in three consecutive line segments are almost equal. ,conditions,
If either of the above is denied, it is necessary to consider that it is not the end point of the arc part.

Therefore, both of the conditions
For at least one of the above conditions, it is possible to conclude that these conditions are the connection points between the straight line and the circular arc, that is, the end points (start point or end point) of the circular arc, if there are no unsatisfied results. it can.

[0013] Since the divisional division into a plurality of line segments by the polygonal line approximation processing is considerably coarser than the divisional division into fine vectors in the conventional method, the amount of calculation can be reduced accordingly, and the time required for the calculation can be reduced. It gets shorter. Further, the rougher the step, the less likely it is to be affected by noise, and the influence of erroneous recognition due to noise does not reach the subsequent stage.

In actual calculation, it may be easier to handle the data as a vector rather than a line segment. In such a case, in the polygonal line approximation step, instead of a plurality of line segments, It is only necessary to obtain a plurality of vectors respectively from the one end point side of the line figure toward the other end point side, and the condition determination may be performed on this vector in the arc end point recognition step. In this case, as can be easily understood by those skilled in the art, since the definition of the angle between the line segments (the direction of which is not defined) and the definition of the angle between the vectors (having the direction) are different, the arc end point recognition step Alternatively, it is necessary to consider that the definition of the corner is different in the condition judgment by the arc end point recognition means.

Here, regarding the outline of the polygonal line approximation processing,
A brief description will be given with reference to FIG.

In the polygonal line approximation processing, a line figure represented by a point sequence is targeted, and it is assumed that only the thinned end points and passing points are present in the input point sequence. One end point of the input point sequence is the start point, and the other end point is the end point. Two positive constants errmax and conemax are defined as input parameters.

The operation of searching for the next point is an operation of scanning the input point sequence from the starting point and searching for a point errmax away. However, once scanned, the point is not scanned,
That is, it does not go back. The starting point is the point at which the operation for finding the next point is performed, and the point obtained by the operation for finding the next point is the point of interest (in the polygonal line approximation process), and the point between the starting point and the point of interest ( The point found in the past by the operation of searching for a point) is the past point. Further, when defining a line segment connecting the starting point and the target point as a vertical bisector, and defining an isosceles triangle whose base length is twice conemax (the vertex of this triangle is the starting point), The area inside the equilateral triangle is the cone area. Common area of multiple cone areas
Set as ne area.

With the above definition,
The vertices (by polygonal line approximation) are points output as a result of polygonal line approximation, and the temporary vertices are points temporarily stored as vertices. The start and end points are vertices.

First, the starting point is used as the starting point (step 4
1) The starting point is set as the point of interest (step 42). Then, the point next to the point of interest is searched, and that point is set as the point of interest. The point of interest is set as a temporary vertex (step 43). Further, a point next to the point of interest is searched for, and that point is set as the point of interest (step 44).

Here, it is checked whether the point of interest is farther from the starting point than the point of the past (step 45). If the point of interest is not far, the process proceeds to step 49. If it is far, the point of interest is the common co
It is checked whether it exists in the ne area (step 46).
If it is not in the common cone area, the process proceeds to step 48 and the common
If it is in the cone area, the target point is set as a temporary vertex (step 47), and the process proceeds to step 48.

In step 48, it is checked if the common cone area is no longer present. If the common cone area exists, the process proceeds to step 44 to search for the next target point, and if the common cone area does not exist at all, the routine proceeds to step 49.

In step 49, the temporary vertex is set as a vertex,
The vertex is set as a new starting point, and the process returns to step 42.

By repeating the above operation from the start point to the end point, the polygonal line approximation of the line figure is performed.

[0024]

Embodiments of the present invention will now be described with reference to the drawings. FIG. 1 is a block diagram showing the configuration of an arc start / end point recognition apparatus according to an embodiment of the present invention.

This arc start / end point recognition device includes an input unit 1 such as a tablet or an image scanner for inputting a line figure,
It is obtained as a result of the line thinning unit 2 that performs the thinning process on the input line figure, the polygonal line approximation processing unit 3 that performs the polygonal line approximation process on the line figure that has been subjected to the line thinning process, and the polygonal line approximation process. A storage unit 4 for storing a plurality of vectors, a vector is taken out from the storage unit 4, and it is checked whether or not all of the above four conditions (1) to (4) are satisfied. It is composed of and.

Next, the operation of this embodiment will be described with reference to FIG.

First, a line image is input by the input unit 1 (step 21), and the line thinning unit 2 performs a thinning process on the line image (step 22). Here, it is assumed that the line figure after the thinning process is represented in FIG.

Next, a polygonal line approximation process is performed on the line figure 11 after the thinning process (step 23). Here, as shown in FIG. 3B, it is assumed that the input line graphic 11 is divided into a plurality of vectors extending from one end side to the other end side of the line graphic 11. The vector thus generated is stored in the storage unit 4. Then, the vertex approximate to the polygonal line (the connection point of the vector) closest to one end of the line figure is set as the target point (step 24).

Next, the arc end point recognition unit 5 refers to the storage unit 4 to confirm whether or not the above-mentioned four conditions (1) to (4) are satisfied, and discriminates whether or not the set target point is the arc end point ( Step 25). Then, it is determined whether or not step 25 has been performed for all the vertices of the polygonal line approximation (step 26), and if there is a vertex that has not been set as the attention point, that vertex is set as a new attention point (step 27), the process proceeds to step 25, and if step 25 has been executed for all the vertices, the process ends.

Here, the operation of the arc end point recognizing section 4 will be described with reference to FIG.

Three consecutive vectors on the line figure are defined as vectors a to c, and the end point of the vector a (that is, the vector b).
Make sure that the starting point) is the point of interest. First, it is checked whether the condition "vector a is considerably longer than vector b and vector c" is satisfied (step 3).
1) If it is satisfied, the process proceeds to step 32, and if it is not satisfied, the process proceeds to step 36, and it is assumed that the target point is not the end point of the arc. In particular,

[0032]

[Equation 1] Check the establishment of. Here, r is a constant of 0 <r <1, but is set to 0.5, for example.

In step 32, it is checked whether or not the condition that "the lengths of the vector b and the vector c are almost the same" is satisfied. If not established, the process proceeds to step 36 in the same manner as described above, and the point of interest is not the end point, and if established, the process proceeds to step 33. Specifically, s is a constant,

[0034]

[Equation 2] Check the establishment of. s is set to about 2, for example.

In step 33, it is confirmed whether or not the condition "the angle formed by the vectors a and b is not 0 ° but close to 0 °" is satisfied. This condition is equivalent to the condition that the angle formed by the line segments is not 2 right angles but is close to 2 right angles. If the condition is not satisfied, the process proceeds to step 36 in the same manner as described above, and the target point is not the end point. If the condition is satisfied, the process proceeds to step 34. Specifically, the vectors a and b
Let θ be the angle formed by and t be a constant,

[0036]

## EQU3 ## The establishment of θ <t is checked. For example, t is set to about 60 °.

In step 34, it is checked whether or not the condition "the angle formed by the vector a and the vector b is almost the same as the angle formed by the vector b and the vector c" is satisfied. If the condition is not satisfied, the procedure proceeds to step 36 in the same manner as described above, and the target point is not the end point. If the condition is satisfied, the procedure proceeds to step 35, and finally the target point is the end point of the arc. Make a conclusion. Specifically, the angle between the vectors a and b is θ, the angle between the vectors b and c is φ, and u is a constant.

[0038]

[Equation 4] Check the establishment of. For example, u is set to about 2.
As described above, whether or not the target point is the end point of the arc is identified for each target point. The parameters r, s, t, u used here can be appropriately set according to the quality and type of the input line figure.

In the example of the vector shown here, since the operation in the forward direction and the backward direction with respect to the target point is not symmetrical, the vector a
Is a vector −b ′, a vector b is a vector −a ′, and a vector on the starting point side of the vector a is a vector d, the vector d is a vector −c ′.
It is necessary to perform similar processing (reverse processing) on these vectors a ', b', c '. Without reverse processing,
A detection failure occurs at the end points of the arc. When the line segment is considered, the direction is not taken into consideration, so that it is not necessary to perform the reverse processing.

[0040]

As described above, according to the present invention, the polygonal line approximation processing is performed on the input line figure, and the line segment by the polygonal line approximation is long on the straight line side and short on the arc side at the connection point of the arc portion and the straight line portion. Therefore, the angle formed by the line segment on the straight line side and the line segment on the arc side is not 2 right angles, but quite large.
By paying attention to the fact that the condition is satisfied, there is an effect that it is not necessary to generate a fine vector, the calculation amount and the calculation time are reduced, and the influence of noise is reduced.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of an arc start / end point recognition device according to an embodiment of the present invention.

2A is a flowchart showing an operation of the apparatus of FIG. 1, and FIG. 2B is a flowchart showing an operation of an arc end point recognition unit.

3A and 3B are diagrams illustrating a method of recognizing the start and end points of an arc in the apparatus of FIG.

FIG. 4 is a flowchart illustrating a polygonal line approximation process.

5A and 5B are diagrams illustrating a conventional method for recognizing the start and end points of a circular arc.

[Explanation of symbols]

 1 Input part 2 Thinning part 3 Polygonal line approximation part 4 Storage part 5 Arc end point recognition part 21-27, 31-36 steps

Claims (3)

[Claims] 1. A start / end point recognition method for searching a start point and an end point of an arc portion from a given line figure, comprising an input step of inputting a line figure and a polygonal line approximation process for the input line figure. A polygonal line approximation step of dividing the line figure into a plurality of connected line segments, selecting one line segment from the plurality of line segments corresponding to the line figure, and selecting the selected line segment as a target line segment. The following two conditions and both of the following conditions: the length of one of the two line segments adjacent to the target line segment is the length of the target line segment and the other of the two line segments Is greater than each of the lengths of the line segments by a predetermined ratio or more, and the condition; the angle formed by the one line segment and the line segment of interest is not two right angles but close to two right angles, and the following two conditions and At least one of the conditions: the length of the line segment of interest and the length of the other line segment Are substantially equal to each other, and the condition; the angle formed by the one line segment and the target line segment is substantially equal to the angle formed by the target line segment and the other line segment. And, if none of the examined conditions are not satisfied, an arc end point recognition step of recognizing the connection point of the one line segment and the target line segment as an end point of an arc portion, the line figure The method for recognizing the start and end points of an arc, wherein the arc end point recognition step is sequentially applied to each line segment corresponding to. 2. A plurality of line segments obtained in the polygonal line approximation step are respectively expressed as a vector from one end side of the line figure to the other end side thereof, and the arc end point recognition step sets a condition for the vector. Claim 1 in which a determination is made
The method for recognizing the start and end points of an arc described in. 3. A start / end point recognizing device for searching for a start point and an end point of an arc portion from a given line figure, wherein input means for inputting the line figure and polygonal line approximation processing for the input line figure. , A polygonal line approximation unit that divides the line figure into a plurality of connected line segments, a storage unit that stores the plurality of line segments, and a line segment that is read from the storage unit one by one as a target line segment. 2 conditions and both, condition; the length of one of the two line segments adjacent to the target line segment is the length of the target line segment and the length of the other line segment of the two line segments The angle between the one line segment and the target line segment is not two right angles but is close to two right angles, and at least one of the following two conditions and the conditions: The length of the target line segment and the length of the other line segment It is checked whether or not the condition is satisfied for each of the conditions that the angle formed by the one line segment and the line segment of interest is substantially equal to the angle formed by the line segment of interest and the other line segment. A circular arc end point recognizing means for recognizing a connection point of the one line segment and the target line segment as an end point of the circular arc portion when none of the examined conditions is satisfied. Start / end point recognition device.