JPH09237339A - Circle/circular arc recognizing method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To reduce an arithmetic quantity at the time of recognizing a circle/ circular arc. SOLUTION: A draft line 21 in the shape of a circular arc is previously drawn in a displayed picture so as to specify a center 22 based on the draft line 21 (S1). After specifying the center 22, a detecting area is limited from the center 22 (S2). Next, pixels within the detecting area and a distance between centers to prepare a histogram (S3). A threshold value straight line 23 is provided for the prepared histogram (S4) to judge whether the histogram exceeds this threshold value straight line 23 (S5). As the result of judging, the place of a radius exceeding the threshold value straight line 23 is judged to include a circle or a circular arc. Next with respect to the place judged to include the circle or the circular arc, pixels are referred to again to determine the starting/finishing angles of the circular arc (S7). After determining, a gap of a small angle generated at the circular arc is buried or a circular arc of a small angle is erased (S8). After then, formed circle/circular arc are detected.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a drawing input device for optically reading and recognizing a drawing including characters and figures and a method for recognizing a circle / arc by a recognition device using an image.

[0002]

2. Description of the Related Art In image processing, it is widely used in various fields to extract a circle or an arc based on image data input from a camera or an image scanner.

Generally, when a drawing or a document is automatically input to a computer, a figure is represented by broken line approximation. However, in the polygonal line approximation as it is, even a portion that can be regarded as a curve is expressed as a set of straight lines (for example, a set of line segment vectors as shown by the start / end coordinate series). Therefore, when the above portion is enlarged, a natural curve becomes a rectangular angular figure. Therefore, it is necessary to recognize a portion that can be regarded as a curved portion from the polygonal line approximation data and more accurately represent the curved portion of the original figure. Conventionally, there are the following means for determining that the polygonal line approximation data series is on a circular arc.

[0004] Figure 13 a means of using a midline intersection, this means adjacent vectors V _i, V _{i + 1} through the midpoint of the vector V _i, V _{i + 1} to the two perpendicular linear q _i , Q _{i + 1} intersection Δ
1 is the center of the arc. In addition, in FIG. 13, Δ2
Is two straight lines q _{i + 1} and q _{i + 2} perpendicular to the vectors V _i and V _{i + 1.}
, And Δ3 is also the intersection of the straight lines q _{i + 2} and q _{i + 3} .

As described above, with the means using the midline intersection shown in FIG. 13, the center of the arc can be obtained by two vectors, but there is a problem that the variations in the vectors cannot be absorbed, and two or more vectors are the same. Intersection points Δ1, Δ2, Δ3 ...
When it is expanded to ..., there is a problem that the arc center candidate point becomes unstable.

Further, as shown in FIG. 14, in the means using the normal intersections, the angle formed by the vectors V _i and V _{i + 1} passes through the coordinate point sandwiched between the adjacent vectors V _i and V _{i + 1} , and the like. A dividing straight line (normal line) q _i is obtained, and an intersection point Δ1 of two continuous normal lines q _i and q _i-1 is set as an arc center. In the means for using the normal line intersection shown in FIG. 14, although the arc center candidate points are somewhat stable as compared with the midline intersection shown in FIG. 13, three vectors are required and the adjoining vector lengths are equal to each other. At the time of balance, there is a problem that the normal intersection becomes unstable like Δ2 and Δ3. Each of the above two means has a problem that the arc center becomes unstable and the arc portion cannot be accurately recognized from the polygonal line approximation data.

Therefore, in recent years, a means has been conceived in which the center of a circular arc is accurately estimated and the error is minimized to find the center of a circle or circular arc by using the least squares method. This means is performed as follows. Here, the equation (x−a) ² + of the center of the circle (a, b) and the circle of radius r
From (y−b) ² = r ² , x ² + y ² + Ax + By + C = 0
Get. Next, the above-mentioned a, b, and r are obtained by using the least squares method with respect to a certain vector coordinate group. The following equation is a vector coordinate group.

[0008]

[Equation 1]

Then, the above equation becomes the following equation.

[0010]

[Equation 2]

Here, A, B and C are obtained, and a =-(1 /
2) A, b =-(1/2) B, r = √ (│a ² + b ² -C
|), The center (a, b) of the circle and the radius r are obtained.

Next, a method of recognizing a circle or an arc by applying the above least squares method to a drawing input device will be described.
In the drawing input device, the least squares method is performed using the contour vector and the core line vector of the figure, and after the center / radius is obtained, if these vector coordinate sequences are circles or arcs, the start angle and end angle Discriminate and calculate how many times At this time, as shown in FIG. 15, when the start point and the end point of the vector coordinate sequence match in the ST portion shown in the figure, it is easy to recognize as a circle, but as shown in FIG. 16 and FIG. If the positional relationship between the start point and the end point of the coordinate sequence is deviated (circled in the figure) or part of the end point is returned, it is difficult to recognize it as a circle only with the vector coordinate sequence. This can be applied to the case of the circular arc in FIG. 18, and even if the center and the starting point and the ending point of the coordinate sequence are known, if the end of the circular arc slightly returns (the part circled in the figure), the vector coordinates Since the starting point and the ending point of the column have a tendency to be unstable, the starting point and the ending point of the coordinates are not sufficient for discriminating a circle and calculating the starting and ending angles of a circular arc.
As a result, the recognition rate of circles and arcs decreases.

For a circle having an intersection as shown in FIG. 19, first, four 90 ° arcs are detected, and then those arcs are
The means of synthesizing and recognizing it as one circle is taken. In the case of FIG. 20, three 90 ° arcs are combined and recognized as a 270 ° arc. However, when the arc is first detected, if the start angle and the end angle of the 90 ° arc are not calculated correctly, it becomes difficult to combine them, and the recognition rate of the circle and the arc decreases.

In the equation for finding the center and radius by the least squares method, Σx _i , Σy _i , Σx _i ² , Σy _i ² , Σx _i ² y _i ,
If Σx _i y _i ² , Σx _i ³ , Σy _i ³ , and Σx _i y _i are executed by using a computer, there is a possibility that the calculation may overflow. For example, (x _i , y _i ) = (0,0), (0,10),
In the case of (10,10), (10,0), Σx _i = 20, Σy _i = 20, Σ
x _i ² = 200, Σy _i ² = 200, Σx _i ² y _i = 1000, Σx _i y _i ²
= 1000, Σx _i ³ = 2000, Σy _i ³ = 2000, Σx _i y _i = 100
Becomes

On the other hand, samples (x _i , y _i ) = (100,100), (100,110), (110,
110), (110,100), Σx _i = 420, Σy _i = 42
0, Σx _i ² = 44200, Σy _i ² = 44200, Σx _i ² y _i = 464100
0, Σx _i y _i ² = 4641000, Σx _i ³ = 4662000, Σy _i ³ = 46
62000, Σx _i y _i = 44100, and the integrated result becomes a large value. If the maximum value that can be expressed in the computer is 4000000, normal operation results will not be obtained in the later example.

In order to prevent such a calculation error, normally, the coordinates of the points are not used as they are, and the center of gravity of the point sequence or the smallest quadrangle (circumscribing quadrangle) that completely encloses the point sequence is used. After conversion to coordinates with the center or the like as the origin, calculation for obtaining the above parameters is performed.

Looking at (5,5) as the origin in the previous example and (105,105) in the latter example, both are (x _i , y _i ) = (-5, -5),
(-5,5), (5,5), (5, -5), and Σx _i = 0, Σy _i =
0, Σx _i ² = 100, Σy _i ² = 100, Σx _i ² y _i = 0, Σx _i y
The parameters _i ² = 0, Σx _i ³ = 0, Σy _i ³ = 0, Σx _i y _i = 0 are calculated. These values are smaller than those of the above two examples and do not exceed the maximum value of 4,000,000. When A, B, and C are obtained using this parameter, A = 0, B = 0, C = −50, and a = 0, b = 0, r = 5√2. Since the coordinates are converted, in the previous example, a = 5 + 0 =
5, b = 5 + 0 = 5, r = 5√2, a = 105 + 0 = 105 in the later example,
b = 105 + 0 = 105 and r = 5√2.

When recognizing a circle or an arc drawn in the drawing,
Usually, one circle or arc is rarely divided into other lines and has a series of coordinate sequences. As shown in FIG. 21, two straight lines X,
Considering a circle divided into four arcs A, B, C, and D by Y as an example, it is easy to think of a vertex (indicated by a small circle in the figure) included in A as a series of coordinate strings ( It is a sequence of vertices that connects branches and end points), but A, B, C,
To recognize that D is a circle,
Check whether each of A, B, C and D is valid as an arc, and if each is valid as an arc, A, B,
It is necessary to check whether the combination of C and D is valid as a circle.

In order to check the validity of the circle and the arc, the error between the circle and the arc and the coordinate sequence obtained by the above means is checked to determine the validity. However, the parameter obtained in the portion A is the parameter obtained with (x _A , y _A ) as the origin, and the parameter obtained in the portion B is the parameter obtained with (x _B , y _B ) as the origin. _A ≠ x _B and y _A ≠ y _B.
Therefore, if the parameters obtained by combining A and B are used as the origin (x _AB , y _AB ),
Since it is necessary to perform the integration calculation again for all the parameters, there is a problem that the calculation time becomes enormous when the parameters are obtained for various combinations.

[0020]

In addition to the above problem, in the method of using the contour of an image as a method for detecting a circle / arc in a drawing, the contour needs to be correctly generated, but the blurring of the image may occur. If so, the contour may not be accurately generated. Further, in the method of using the Hough transform from an image, it is less affected by the blur of the image, but if the center and the radius are both obtained from the image data, the amount of calculation becomes enormous and the calculation time is also affected. become. Furthermore, in the above circle / arc detection method, for contour data,
Using the least squares method, the error calculated there is compared with a certain threshold, and if the error is smaller, it is determined to be a circle or an arc. If the error is larger, a set of line segments (polyline or polygon ) Is determined.
However, with this determination method, although it may appear to the human eye as a set of line segments, it may be recognized as a circle or an arc.

For example, when there are two contours shown in FIGS. 22 (a) and 22 (b), if the least squares method is applied to them,
In the case of FIG. 22A, a circle passing through three points can be drawn, and the error becomes “0”. Further, in the case of FIG. 22B, a circle passing through five points cannot be drawn and an error occurs. It is also a problem that different results occur for the polygonal lines having the same shape shown in FIGS. 22 (a) and 22 (b).

In addition to the above, when a circle / arc is extracted from the drawing data of only line segments, the center coordinates of the circle / arc after extraction by the least squares method from the coordinate sequence in which the start point / end point of the line segment group is taken. When calculating the radius with (the least square method always gives one answer for any data), it is necessary to judge whether the calculated circle is valid or not.

In this case, as shown in FIG. 23, the average or maximum value of the distances between the start point / end point or middle point of the original line segment data LD and the circle CY calculated by the least square method (FIG. 23 (c )
The arrow part in) is taken, and if it is smaller than the set threshold value, it is a circle.

In the case of the above method, since there is no index in the method of determining the threshold value for determining that it is a circle, it is difficult for a person who uses the circle / arc extraction process to determine the threshold value. There is a problem that a straight line slightly bent as shown in FIG. 24 (a) also becomes an arc as shown in FIG. 24 (b). In particular, in FIG. 24B, since the polygonal line is calculated as a circle having a large radius, the distance to the circle at each point becomes small.

The present invention has been made in view of the above circumstances, and aims to reduce the calculation amount at the time of circle / arc recognition, and
An object of the present invention is to provide a method for recognizing a circle / arc that improves the determination of circle / arc recognition.

[0026]

In order to achieve the above-mentioned object, the present invention provides a method for recognizing a circle / arc by a drawing input device capable of editing, shaping, etc. of a figure, and After drawing an arc-shaped construction line on the and specifying the center of the circle / arc based on the construction line, limit the detection area from that center, calculate the pixel and center point distance in the area, and then create a histogram. If a threshold value is set in the histogram and it is determined whether there is a histogram that exceeds the threshold value, and if there is a circle / arc, if there are two or more arcs, both arcs are smaller. When there is an angular gap, the gap is filled, and when there is an arc with a small angle in both arcs, the arc is erased to obtain a shaped circle / arc. is there.

The second invention is a method for recognizing a circle / arc by a drawing input device capable of editing, shaping, etc. of a figure,
After obtaining the distance between the vertices of the contour data of the figure, it is determined whether the distance between the vertices is larger or smaller than the preset maximum distance X, and when it is larger, new vertices are added at equal intervals, The method is characterized in that the least squares method is applied to the data newly added with the vertices to determine the circle / arc.

A third aspect of the present invention is a method for recognizing a circle / arc by a drawing input device capable of editing, shaping, etc. in a figure. After calculating a circle from the line segment data of the contour data of the figure by the method of least squares, When the maximum distance between a point on a line segment and a circle is [(1/2) x line width] or less, create a rectangle with a line width whose thickness is specified at the end of the line segment data, and If all the points of the data do not fall within the rectangle, it is extracted as a circle / arc.

According to a fourth aspect of the present invention, the circle calculating process determines whether or not the radius is small after obtaining the radius in this calculating process. When the radius is small, a designated threshold for circle determination is set and the threshold is set. The method is characterized in that the wire diameter is changed to the reference radius before the operation.

[0030]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a flow chart showing a first embodiment of the present invention. In FIG. 1, an arbitrary circle / arc is not detected from the entire drawing, but first, a circular arc is displayed on a display image shown in FIG. 2 by a mouse or a keyboard. By writing the draft line 21 in advance, the center 22 is designated in step S1 based on the draft line 21. Center 2
If 2 is specified, the detection area from the center 22 is limited in step S2. Here, limiting the detection area is
This is to prevent the possibility of enormous amount of calculation by being able to detect any circle.

Next, the distance between the pixel in the detection area and the center point is calculated, and a histogram as shown in FIG. 3 is created in step S3. A threshold straight line 23 as shown in FIG. 4 is provided in the created histogram in step S4, and it is determined in step S5 whether or not the threshold straight line 23 is exceeded. As a result of the determination, it is determined that there is a circle or a circular arc at a location having a radius exceeding the threshold straight line 23.

Next, with respect to the portion determined to have a circle or an arc in step S6, the pixel is referred to again, and the start angle / end angle of the arc is determined in step S7. Figure 5 after decision
When an arc as shown in FIG. 6A is formed, the gap with a small angle Δθ ₁ is filled in to form the arc as shown in FIG.
When it becomes an arc as shown in FIG. 6A, the arc having a small angle Δθ ₂ is erased to form an arc as shown in FIG. 6B in step S8. By forming an arc as in step S8, the shaped circle / arc is formed in step S8.
It becomes possible to detect it at 9.

FIG. 7 is a flow chart showing a second embodiment of the present invention. This second embodiment is an improvement of the method of applying the circle / arc least squares method to contour data. In FIG. 7, first, the distance between the first vertices of the contour data is checked in step S11 to find the distance between the vertices of the contour data. When obtaining the distance, the maximum distance X between the vertices is set in advance. The smaller this distance is, the more accurate the determination becomes, but the processing takes longer. In step S12, it is determined whether the distance between the vertices of the contour data obtained in step S11 is larger than the maximum distance X that is set. If the determination result is larger than the maximum distance X, new vertices are added at equal intervals by the number obtained by subtracting "1" from (distance between vertices) / (maximum distance X) [rounding up the remainder] in step S13. To do.

FIG. 8 shows the case of step S13.
This will be described with reference to (a) and (b). FIG. 8A shows the original data. When the maximum distance X between the vertices is “1” as described above, the vertices are added at equal intervals as shown in FIG. 8B. In FIG. 8B, double circles are added vertices.

Then, in step S14, it is determined whether or not all the vertices are checked, and if checked, the process proceeds to step S15, and the least squares method is applied to the data in which the vertices are added, and the circle / circle is applied. After making the determination, the processing is terminated. If it is determined in step S14 that the space between the vertices has not been checked, the process of step S16 (moving between the next vertices) is performed and the process returns to step S12.

The circle / arc determination method according to the second embodiment described above can be applied not only to processing of contour data but also to circle / arc recognition of graphic data already recognized as a line segment.

FIG. 9 is a flow chart showing a third embodiment of the present invention. In the third embodiment, the circle / arc recognition processing is performed by using the line width. In FIG. 9, the line width is input to the circle calculation process by the least squares method in step S21. After the circle calculation processing is performed in step S21, it is determined in step S22 whether the maximum distance between the circle on the line segment and the circle is equal to or less than [threshold value = (1/2) × line width]. If it is, it is determined to be a circle, and if it is above, it is determined to be a line segment. If it is determined to be a line segment, the line segment is set to "NO" and the line segment is left as it is.

Step S23 is a process for judging whether the condition of FIG. 10 shown below is satisfied. In FIG. 10, at the end of the line segment data, a rectangle having a line width with a designated thickness (the broken line shown in FIG. 10) is used. (Rectangle formed in step 1) is created, and all points d1 to
If d4 falls within it, they are determined to be straight lines and remain line segments. On the other hand, if it is determined in step S23 that the line segment data does not fit within the line width rectangle, it is recognized as a circle / arc.

FIG. 11 is a flow chart showing a fourth embodiment of the present invention. This fourth embodiment is an improvement of the third embodiment, and the same parts as those of the third embodiment are designated by the same reference numerals. It was In FIG. 11, the line width is input to the circle calculation process by the least square method in step S21, and then the circle calculation process is performed to obtain the radius of the circle. In step S21a, it is determined whether the calculated radius is small.
As shown in FIG. 2, the designated threshold for circle determination is set to step S21b.
Set with. As shown in FIG. 12, this designated threshold is linearized in step S21c until it reaches a reference radius (until the radius reaches a certain size). As a result, even a small radius can be calculated as a circle. In this way, after the circle calculation processing is performed, it is determined in step S22 whether the maximum distance between the circle on the line segment and the circle is equal to or less than [threshold = (1/2) × line width]. If it is "YES" below, it is determined to be a circle, and if it is "NO" above, it is determined to be a line segment. If it is determined to be a line segment, the line segment remains as it is, and if it is determined to be a circle, step S
The process of 23 is performed to determine a circle / arc. By performing such processing, a circle / arc having a small radius can be accurately extracted. When the radius of the circle / arc is smaller, the level of the designated threshold may be set to be lowered.

[0040]

As described above, according to the first aspect of the present invention, the circle / arc can be recognized directly from the image, and the center can be designated when recognizing the circle / arc. The amount of calculation can be reduced, and unexpected and unnecessary appearance of unnecessary circles / arcs can be prevented. According to the second invention, it is possible to improve the determination of the recognition of the circle / arc. According to the third aspect of the present invention, it is possible to obtain a judgment threshold value necessary for the circle / arc recognition processing using the least squares method with a relatively easy value, and use the threshold value for straight line judgment to detect a slightly broken line. It is possible to prevent accidentally making an arc. 4th
According to the invention, even a small circle / arc can be accurately extracted.

[Brief description of drawings]

FIG. 1 is a flowchart showing a first embodiment of the present invention.

FIG. 2 is an explanatory diagram of a display image.

FIG. 3 is an explanatory diagram of a histogram.

FIG. 4 is an explanatory diagram in which a threshold line is drawn on a histogram.

FIG. 5A is an explanatory view of an arc having a small angle gap;
(B) Explanatory drawing of the circular arc which filled the gap.

6A is an explanatory diagram of a small-angle circular arc, and FIG. 6B is an explanatory diagram in which the small-angle circular arc is deleted.

FIG. 7 is a flowchart showing a second embodiment of the present invention.

FIG. 8A and FIG. 8B are explanatory views of the operation of the second embodiment.

FIG. 9 is a flowchart showing a third embodiment of the present invention.

FIG. 10 is an operation explanatory view of the third mode.

FIG. 11 is a flowchart showing a fourth embodiment of the present invention.

FIG. 12 is a characteristic diagram for describing the operation of the fourth mode.

FIG. 13 is an explanatory diagram of a conventional example.

FIG. 14 is an explanatory view of a conventional example.

FIG. 15 is an explanatory diagram when the start point and the end point match.

FIG. 16 is an explanatory diagram when the start point and the end point do not match.

FIG. 17 is an explanatory diagram when the start point and the end point do not match.

FIG. 18 is an explanatory diagram when a part of an arc is returned.

FIG. 19 is an explanatory diagram when a circle is composed of four 90 ° arcs.

FIG. 20 is an explanatory view when a 90 ° arc and three arcs are combined to form a 270 ° arc.

FIG. 21 is an explanatory diagram of a circle divided into four arcs.

22 (a) and 22 (b) are explanatory views in which different results are produced depending on the contours.

23A is an explanatory diagram of line segment data, FIG. 23B is an explanatory diagram of a circle obtained by the line segment data by the least square method, and FIG.

24A is an explanatory diagram of line segment data, and FIG. 24B is an explanatory diagram of a circle obtained by the line segment data by the least square method.

[Explanation of symbols]

S1 ... Circle / arc center specification step S2 ... Detection area setting step from center S3 ... Histogram creation step S4 ... Histogram threshold setting step S5 ... Judgment step S6 ... Circle / arc step S7 ... A step of determining the start angle and end angle of the arc S8 ... A step of filling a small angle gap or erasing the small angle arc S9 ... A circle / arc detection step

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Daisaku Fukumoto 2-17-17 Osaki, Shinagawa-ku, Tokyo Stock Company Shameidensha (72) Masamichi Hirabayashi 2-1-117 Osaki, Shinagawa-ku, Tokyo Shares Inside the company Meidensha (72) Inventor Minoru Kobayashi 2-11-17 Osaki, Shinagawa-ku, Tokyo Stock company Inside the company Meidensha (72) Kenji Sasaki 2-11-17 Osaki, Shinagawa-ku, Tokyo Inside the company Meidensha

Claims (4)

[Claims] 1. A method of recognizing a circle / arc by a drawing input device capable of editing, shaping, etc. a figure, and draws an arc-shaped draft line on an image and designates the center of the circle / arc based on the draft line. After that, limit the detection area from the center, create a histogram after calculating the pixel and center point distance in the area, set a threshold on the histogram to determine whether there is a histogram that exceeds the threshold, In some cases, when it is determined that there is a circle / arc, if there are two or more arcs and there is a small angle gap between both arcs, the gap is filled and the arc with the smaller angle of both arcs is filled. If there is, a circle / arc recognition method is characterized in that the arc is erased to obtain a shaped circle / arc. 2. In a method of recognizing a circle / arc by a drawing input device capable of editing and shaping a figure, the distance between the vertices of contour data of the figure is obtained, and then the distance between the vertices is preset. After determining whether it is larger or smaller than the maximum distance X, if it is larger, add new vertices at equal intervals,
A circle / arc recognition method, characterized in that a least squares method is applied to data with newly added vertices to determine a circle / arc. 3. A method for recognizing a circle / arc by a drawing input device capable of editing, shaping, etc. a figure, after calculating a circle from the line segment data of the contour data of the figure by the least squares method, and then calculating the line segment. The maximum distance between the upper point and the circle is [(1 /
2) × line width] or less, create a rectangle with a line width whose thickness is specified at the end of the line segment data, and if all the points of the line segment data do not fall within the rectangle, use a circle / arc. A circle / arc recognition method characterized by extraction. 4. The circle calculating process, after obtaining the radius in this calculating process, judges whether the radius is small, and when it is small, sets a specified threshold for circle determination and sets the threshold as a reference radius. 4. The method for recognizing a circle / arc according to claim 3, wherein the diameter is changed until the wire diameter is reached.