JPH07104954B2 - Arc extractor - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Outline] The present invention relates to a circular arc extraction device for extracting a circular arc candidate from a polygonal line generated by thinning and approximating a figure, among polygonal lines that have been subjected to thinning and polygonal line approximation. When extracting a part corresponding to a circular arc, even if it is extracted as a single circular arc, it actually contains a plurality of circular arc parts, or actually it is divided into a plurality of circular arcs and extracted regardless of the single circular arc. In order to solve the problem, the arc candidate is divided based on the temporary radius and the temporary center point of each polygonal line vector forming one circular arc candidate, and the temporary radius, the temporary center point, and the end point between the plurality of circular arc candidates are divided. By performing the process of combining the arc candidates based on the distance, the strict and effective desired arc candidates are extracted based on the original figure pattern.

[Field of Industrial Application] The present invention performs arc division processing and / or combination processing in order to generate more effective arc candidates for arc candidates extracted from polygonal lines that have been thinned / approximated. The present invention relates to a constructed arc extracting device.

[Problems to be solved by conventional technology and invention]

Generally, in the case of recognizing a figure in a figure reading device or the like, the line segment constituting the figure obtained by thinning is approximated to a broken line, and the line segment is characterized to perform the figure recognition. For that purpose, it is necessary to obtain the characteristic points for all the line segments forming the figure, and to recognize the characteristic points by comparing them with a predetermined value set in advance.

At this time, if it is known in advance whether the type of line segment that constitutes the figure is a straight line, a circular arc, or a circle, the processing speed can be reduced by reducing the number of feature points required for recognition or by limiting the recognition processing target. It becomes possible to improve.

As an arc extraction method of this kind, it is conceivable to generate polygonal line data by thinning and approximating the figure data by a known method, and extract a polygonal line string forming an arc portion from this polygonal line data as an arc candidate. However, even if a circle is extracted by this method, it may be a true circle or an ellipse. Further, there are cases where a plurality of arcs having different radii cannot be divided and are extracted as one arc. On the contrary, in some cases, a circular arc candidate, which should be one circle or circular arc, is actually divided into several circular arcs. Thus, there is a problem that undesired arc candidates are extracted unlike the original arc candidates to be extracted. Therefore, it is desired that the extracted circle / arc candidates be divided again under more severe conditions or combined under looser conditions to extract the desired arc candidates that match the original figure pattern. ing.

[Means for solving problems]

The present invention, in order to solve the above problems, an arc division processing unit 1 that divides an arc candidate into a plurality of pieces based on a temporary radius and a temporary center point of a polygonal line of an arc candidate corresponding to an arc extracted from a polygonal line, A temporary radius and a temporary center point calculated respectively for a plurality of arc candidates corresponding to the arc extracted from the polygonal line,
An arc combining processing unit 2 that connects to one arc or a circle based on the end point information is provided, and the arc candidate is divided and / or combined as necessary to extract the arc portion.

FIG. 1 shows the principle configuration of the present invention. The arc division processing unit 1 in the figure divides the arc candidate based on the temporary radius and temporary center point of the broken line of the arc candidate corresponding to the arc extracted from the broken line.

The arc joining unit 2 joins one arc or circle based on the temporary radius and temporary center point calculated for each of the plurality of arc candidates corresponding to the arc extracted from the polygonal line, and the end point information.

The arc data of the broken line string is the data of the broken line string roughly extracted as the arc candidate from the broken line approximated to the broken line.

[Action]

 Next, the operation will be described.

In FIG. 1, among the polygonal lines generated by thinning / approximating the polygonal lines, when arc data of a polygonal line string extracted as arc candidates is input to the arc division processing unit 1, the arc division processing unit 1 selects the arc candidates. The arc candidate is divided into a plurality of arc candidates on the basis of the provisional radius and the provisional center point obtained for the polygonal line vector constituting the. Further, when the arc data of the broken line string extracted as the arc candidate is input to the arc joining processing unit 2, the arc joining processing unit 2 obtains the temporary radius and the temporary center obtained for the broken line strings constituting the plurality of arc candidates. The plurality of arc candidates are combined into one arc candidate based on the points and the end points. The dividing process and the combining process can be performed independently of each other.

As described above, among the polygonal lines generated by thinning / approximating the polygonal lines, the stricter arc division processing and / or the arc concatenation processing are performed on the arc candidate of the polygonal line that is roughly extracted as a circular arc. It is possible to extract a desired arc candidate that matches the figure pattern.

〔Example〕

Next, the configuration and operation of one embodiment of the present invention will be described in detail with reference to FIGS.

First, the outline of the operation of the present invention will be described with reference to FIG. In the drawing or FIG. 1, the processing executed by the circular arc division processing unit 1 is shown, and the processing executed by the circular arc combination processing unit 2 is shown.

FIG. 2 shows a state in which the arc candidate is extracted. For example, as will be described later with reference to FIGS. 8 to 12, a figure is thinned and a polygonal line is approximated to generate a polygonal line, and a polygonal line array forming an arc from the generated polygonal line is extracted. is there. The extracted arc candidates are registered in the arc candidate vector table of FIG.

The figure shows a state in which the temporary radius and the temporary center point are obtained. This means that, as will be described in detail with reference to FIG. 3, the provisional radius and the provisional center point are calculated for the polygonal line sequence forming the arc candidate.

The figure shows a state in which a circle and an ellipse are divided. this is,
This means a division process, for example, dividing an ellipse into a circular portion and a straight line portion based on a temporary radius and a temporary center point obtained in the drawing for a circular arc candidate (circle or ellipse) forming a closed loop.

The figure shows a state in which an arc is divided. This means that one circular arc is divided into two circular arcs based on the temporary radius and the temporary center point of each polygonal line vector that forms the circular arc candidate obtained in the figure.

The figure shows the state in which the arc candidates divided in the figure and in the figure are registered in the arc candidate vector table.
It will be described later with reference to the drawing).

The figure shows a state in which the temporary radius, the displacement of the temporary center point, and the distance between the end points are combined. This means that they are combined into one circular arc candidate based on the temporary radii and temporary center points respectively obtained for a plurality of circular arc candidates and the difference in distance between these two end points.

The figure shows a state in which the arc candidate is registered in the arc candidate vector table.

As described above, it becomes possible to perform a dividing process and a combining process on the roughly extracted arc candidates under more strict conditions to extract a desired arc candidate that matches the original figure pattern.

The configuration and operation of this embodiment will be sequentially described in detail below.

FIG. 3 shows a flowchart for explaining the operation of the arc dividing unit 1.

FIG. 3 shows a state in which desired data is read from the arc candidate table and the arc candidate vector table of FIG. 11 in which the extracted arc candidate information is stored. At this time, when a flag is set in the loop flag column in the arc candidate table (when it is a closed loop and is a circle or an ellipse), the following process in the figure is executed as a circle candidate.
On the other hand, when the loop flag is not set (when it is a circular arc), the following processing in the figure is executed.

In the figure, it is constituted by the processing of or.

In the figure, find the center of gravity of the coordinates (X, Y) in the candidates,
A state in which this is the temporary center point is shown. This is, for example, the coordinates (X _pi ,) of each starting point P _i of the polygonal line V _i (i is extracted as an arc candidate of 0 to n) which is the arc candidate stored in the arc candidate vector table of FIG. Y _pi ) is read from the vector table of FIG. 9, and the sum total of all the read X coordinates and Y coordinates is calculated. This sum is divided by the total number n of broken lines to calculate the coordinates of the center of gravity (X _G , Y _G ) is calculated and used as the coordinates of the temporary center point AP.

In the figure, indicates a state in which the average value of the distance between the temporary center point and each point is used as the temporary radius. This is the average value AR of the distance difference between the coordinates (X _G , Y _G ) of the temporary center point AP calculated in the figure and the coordinates (X _pi , Y _pi ) of the starting point P _i of each polygonal line V _i. It means that the value is calculated by using the formula and this is used as the temporary radius AR.

The distance R _i between each point and the tentative center point is R _i = {(X _pi -X _G ) ² + (Y _pi -Y _G ) ² } ^1/2 ... (1) The tentative radius AR is In the figure, indicates the state in which the difference between the temporary radius AR and the distance R _{i of} each point is calculated and used to determine the circle and the arc based on this difference. For example, when there are j or more points where the difference between them is k or more, it is determined that the circle candidate is not a circle, and this arc candidate is targeted for division. If both do not meet the above conditions, they remain as circle candidates. Specifically, if it is an ellipse as shown in FIG. 4 (a), at a point near the Y-axis, the distance R _i between each point P _i and the temporary center point AP and the temporary radius AR are Difference becomes larger in the-direction (smaller than the average value), while the difference between the two becomes larger in the + direction at points near the X axis, where k = 10 and j = 5 are set, and the condition is When the number of applicable points becomes 5 or more, it is necessary to perform division processing for this arc candidate, and in this case, the following arc division processing in the figure is executed. If the circle is as shown in FIG. 4B, the temporary radius AR, each point P _i and the temporary center point
Since there is no difference in the difference with the distance R _{i from the} AP, it is not necessary to perform the division processing as a circle as it is.

The figure shows a state in which the temporary radius AR and the temporary center point AP are extracted as the radius and center point of the arc candidate.

The drawing shows a state in which the radius and center point extracted in the drawing are registered in the arc candidate table in FIG. 11, and the polygonal lines V _i constituting the extracted arc candidate are registered in the arc candidate vector table.

The figure shows a state in which the temporary radius and the temporary center point of the circular arc candidate are obtained and the circular arc is divided at the points where the temporary radii differ greatly. This is to perform division processing for the case of open loop (case of arc candidate). This will be described below. First,
The temporary radius R _i of the polygonal line V _i forming the arc candidate is defined as shown in FIG. 5 (a), and is calculated using the following formula.

R _i = L / θ ₁ (3) Here, L represents the length of the polygonal line V _i as shown in FIG. 5 (a), and θ ₁ is the extension of this polygonal line V _i (polygonal vector). Lines and,
It represents the angle between adjacent polygonal lines V _{i + 1} connected to it. AP _i represents a provisional center point. This temporary radius R _i is calculated for all broken lines V _i . Second, the tangent line V _i calculated in the first
The temporary radii R _i of
When the difference has a value equal to or larger than p, the arc is divided between the polygonal line V _i and the polygonal line V _{i + 1} . For example, as shown in FIG. 5B, there are a broken line V ₁ and a broken line V ₂ as part of the broken lines forming the arc candidate, and p = 15 is set. At this time, if the difference in length between the temporary radius R ₂ of the temporary radius R ₁ and line V ₂ fold lines V ₁ is different than 15, two between the fold lines V ₁ and fold line V ₂ of the circular arc candidate A division point is set as an arc candidate, the arc candidate is divided at this division point, and division processing is executed in the figure.

In the figure, the intersection of the perpendicular bisector of the line segment connecting the start point and the end point of the arc candidate and the perpendicular bisector of each polygonal line vector is obtained, and the optimum value is obtained from this intersection. A state in which this is the center point is shown. This means that the center point of the broken line V _i group which is a new arc candidate divided in the figure is obtained.

In the figure, shows the state of obtaining the radius from each point and the center point. This is based on the center point found in the figure and each polygonal line V _i
It means that the respective distance differences from the start point are calculated, and this average value is calculated as the radius, for example. Then, in the figure, the polygonal line V _i that belongs to the newly generated arc candidate after being divided in the figure, and the data such as the coordinates and radius of the center point calculated in the figure are shown in FIG. A candidate table and an arc candidate vector table are created and registered in each.

By the above procedure, the arc candidate forming a circle or arc is divided into a plurality of arc candidates.

Next, the combining process will be described with reference to FIG.

In FIG. 6, the figure shows a state in which only the arc candidate registered in the arc candidate table is targeted. This means that only the arc candidates registered in the arc candidate table and arc candidate vector table in FIG. 11 are searched and the following combining process is executed.

In the figure, the arbitrary arc candidates retrieved from the table shown in FIG. 11 in the figure and the respective values of the center point coordinates (X, Y) and the radius R are the predetermined minimum values (X _MIN , Y _MIN , R _MIN ) and smaller than a predetermined maximum (X _MAX , Y _MAX , R _MAX ) are found.

The figure shows a state in which the distance between the end points of these two arbitrary arc candidates is checked. This is to read the coordinates of the end points of the two arc candidates from the FIG. 9 vector table by reading out the start point coordinates and the tail coordinates corresponding to the leading and trailing polygonal lines V _i registered in the FIG. 11 arc candidate vector table. This means finding the shortest distance between the end points of. When the distance between the two end points is smaller than the predetermined value L, the combining process is executed in the figure. When the distance between the two end points is larger than the predetermined value L, the two arc candidates are not connected in the figure, and the following steps in the figure are repeated to search for the next candidate.

In the figure, the state of being combined into one arc is shown. this is,
Since all the conditions are satisfied for the two arc candidates in and in the figure, it means to recalculate the center point, the radius, and the end point for all the broken lines V _i included in these two arc candidates. is doing. For example, in the process of considering two arc candidates shown by using P and Q as shown in FIG. 7 and extracting the arc candidates roughly using only the interior angle θ ₁ of the polygonal line V _i , the arc P and the arc at the point A are processed. It is divided into Q and. At this time, the distance between the center point PP of the circular arc P and the center point QQ of the circular arc Q is less than or equal to a predetermined value s, and the radius PR of the circular arc P and the radius of the circular arc Q.
If the difference in length of QR is equal to or smaller than the predetermined value t, the end points of the arc P and the arc Q are in contact with each other at the point A, so it is determined that they may be combined as one arc.

FIG. 11 shows a state in which various pieces of information in which two arcs are combined into one arc are registered in the arc candidate table and arc candidate vector table in FIG.

The figure shows a state in which it is determined whether or not there are arcs to be combined, including newly extracted arc candidates.
If YES, repeat the following in the figure. If NO, end.

As described above, in the case where a more strict condition is applied to any two arc candidates and the condition is satisfied, the two arc candidates are combined into one arc candidate and the coordinates of the center point are newly added. By calculating the radius, etc. and registering it in the table in FIG. 11, it becomes possible to extract valid arc candidates.

Next, with reference to FIGS. 8 to 12, a procedure for extracting arc candidates by applying a rough condition to a broken line string obtained by thinning / approximation of a graphic pattern will be described.

FIG. 8 is a conceptual explanatory diagram for extracting arc candidates. In the figure, the thinning / polygonal line approximation processing unit 3 thins the input figure pattern, and further polylineizes the thinned line figure to generate polygonal line data.

The classification processing unit 4 classifies the broken line into a straight line candidate broken line, a circular arc candidate broken line, and a distortion candidate broken line based on the length of the broken line.

The arc extraction processing unit 5 extracts arc candidate broken lines forming an arc from the arc candidate broken lines classified by the classification processing unit 4.

The circular arc calculation processing unit 6 calculates the radius and center point coordinates of the circular arc connecting the circular arc candidate polygonal lines forming the circular arc extracted by the circular arc extraction processing unit 5.

As described above, the circular arc division processing unit 1 divides one circular arc candidate into a plurality of circular arc candidates.

As described above, the arc combining processing unit 2 combines a plurality of arc candidates into one arc candidate.

In FIG. 8, when the graphic pattern is input to the thinning / polygonal line approximation processing unit 3, the graphic pattern is thinned based on a known technique, and, for example, a bending point appears in the thinned line graphic. The polygonal line approximation processing such as connecting the point sequences in the line figure with line segments is performed, and the polygonal line data is output. The classification processing unit 4 to which this polygonal line data is input determines the polygonal line as a straight line candidate polygonal line according to the length of the input polygonal line.
It classifies into arc candidate polygonal lines and distortion candidate polygonal lines, and outputs the classified data. The circular arc extraction processing unit 5 traces the circular arc candidate polygonal lines in this classification data, and sequentially extracts other adjacent circular arc candidate polygonal lines that are connected within a predetermined angle range with respect to a certain circular arc candidate polygonal line, and 1 Put together. The circular arc calculation processing unit 6 that has received the notification of the circular arc candidate polygonal lines grouped into one calculates the radius and center point coordinates of the circular arcs for these circular arc candidate polygonal lines as circular arc data and registers it in the table in FIG. .

By following the above, we trace the arc candidate polygonal line of the polygonal line that is a thin line of the figure pattern and approximate the polygonal line, and a series of one in which the other arc candidate polygonal lines adjacent to one arc candidate polygonal line are connected within the predetermined angle range. It is possible to combine them into one, obtain the radius and center point coordinates of the arc for the group of arc candidate polygonal lines, roughly extract the arc portion from the polygonal line, and register it in the table in FIG. The operation of roughly extracting the arc portion will be described below.

FIG. 9 shows a vector table. This stores the polygonal line data generated by the thinning / polygonal line approximation processing unit 1 in FIG. In the X-coordinate, Y-coordinate, and end point information on the start point side shown by using (a) in the figure, the start point side coordinates of the corresponding broken line V _i and end point information such as branching are stored. X coordinate, Y coordinate on the end point side shown using (b) in the figure,
In the end point information and the end point information, the end point information such as the coordinates and the branch of the corresponding broken line V _{i on} the end point side are stored. Information corresponding to the straight line candidate polygonal line, the circular arc candidate polygonal line, and the distortion candidate polygonal line is stored in the attribute indicated by (c) in the figure.

The operation of FIG. 8 will be described with reference to the flowchart of FIG.

In FIG. 10, the process shows a state in which all broken line data is generated. This means that the thinning / polygonal line approximation processing unit 3 generates polygonal line data for all polygonal lines V _i (i = 1 to n) and stores them in the vector table of FIG.

The process indicates a state in which classification is performed according to length. this is,
The classification processing unit 4 compares the lengths L of all the polygonal line data read from the vector table in FIG. 9 with predetermined values L _MAX and L _MIN, and if the length L is longer than L _MAX , the polygonal line V _i is straightened. It is classified as a candidate polygonal line, "1" is stored in the attribute column in the vector table in Fig. 9, and when it is shorter than L _MIN , the polygonal line V _i
Is classified as a distortion candidate polygonal line and “3” is stored in the attribute column, and if neither is found, it means that the polygonal line V _i is classified as a circular arc candidate polygonal line and “2” is stored in the attribute column. . The length L of the broken line data may be calculated based on the starting point side coordinates and the ending point side coordinates of the vector table of FIG.

The process indicates a state of extracting arc candidates. This is executed by the following processing.

The process shows a state in which two arc candidate vectors that do not sandwich the branch point are extracted as arc candidates. This means that the attribute in the vector table in Fig. 9 means a circular arc candidate polygonal line "2".
Means that two adjacent broken lines V _i in which is stored are searched and the coordinates and the like are read.

The process shows a state in which the arc candidate vector is traced using the internal angle θ of the vector of the two broken lines V _i . At this time, if it is in contact with the distortion candidate vector, the tracking ends there. This is because, as shown in FIG. 12 (a), the inside angle θ of the vector of _two adjacent broken lines V _i, for example, broken lines V ₁ and V ₂ read in the figure is larger than a predetermined range, for example, 90 ° or more. And 18
It is determined whether or not it exists in a range smaller than 0 °, and if it exists, it means extraction as an arc candidate (this is registered in the arc candidate vector table in FIG. 11 in the process). For example, register as V ₁ , V ₂ ...).
Similarly, the next arc candidate vector is sequentially extracted. Also, if you hit a branch point during tracking,
As shown in FIG. 12 (b), the interior angle θ is checked for all the polygonal lines V _i , the optimal polygonal line V _i is selected, and tracking is continued. Furthermore, when a distortion candidate vector appears during the tracking of the arc candidate vector, the distortion candidate polygonal line is skipped and the above process is continued. In this case, two branch points sandwiching the distortion candidate polygonal line are collectively considered as one branch point, and processed in the same manner as the ordinary branch point. For example, Figure 12 (C)
As shown, if the tracking from fold line V ₁ was carried out, line
Regarding V ₂ , polygonal line V ₃ and polygonal line V ₄ , looking at the internal angle θ with polygonal line V ₁ ,
Make sure to proceed in the direction of polygonal line V ₂ that meets the conditions. When a series of tracking is completed in this direction, then tracking is similarly performed in the opposite direction.

The process shows a state in which the tracking ends when the straight line candidate vector is touched. This is the 9th time during the processing in the figure.
When "1", which means a straight line candidate broken line, is read from the attribute column of the diagram vector table, it means that the tracking ends here.

The process indicates the state of setting a flag when extracted as a closed loop. This means that a flag is set in the loop flag column in the arc candidate table of FIG.

The process indicates a state in which the arc candidate vector sequence is stored in a table and the distortion candidate vector information and interior angle information are also saved. This means registering the results traced by the processing or the table in FIG. Fig. 11 In the arc candidate table, the number of vectors that satisfy the condition tracked by processing or the broken line that satisfies the condition
Pointers for each vector pointing to the arc candidate vector table for registering V _i , coordinates (X, Y) of the start and end points of a series of arc candidate polygonal lines that satisfy the conditions, a loop flag indicating a closed loop, and a series obtained by tracking The radius of the arc calculated for the polygonal line and the coordinates (X, Y) of the center point of the arc are stored.

As described above, the polygonal line data is stored in the vector table of FIG. 9, the arc candidate polygonal line, the distortion candidate polygonal line, and the straight line candidate polygonal line are classified based on the polygonal line data, and the adjacent arc candidate polygonal lines are classified. Based on the internal angle θ, an arc candidate is extracted, and the extracted arc candidate is registered in the table in FIG.

〔The invention's effect〕

As described above, according to the present invention, the arc candidate is divided based on the temporary radius and the temporary center point of each polygonal line vector that constitutes one circular arc candidate, and the temporary radius for each of the plurality of circular arc candidates is calculated. Since it adopts a configuration that joins arc candidates based on the distance between the tentative center point and end points, it applies more rigorous conditions to the arc candidates of the polygonal lines that are roughly extracted and is more faithful to the original pattern. It is possible to extract a circular arc part. Further, since the arc dividing process and the arc combining process are handled separately and independently, it is possible to extract the optimum arc portion adapted to the type of original figure and the use of figure processing.

[Brief description of drawings]

FIG. 1 is a block diagram showing the principle of the present invention, FIG. 2 is a flowchart for explaining the operation of the present invention, FIG. 3 is a flowchart for explaining the operation of a circular arc division processing unit, and FIGS. 4 and 5 are operational explanatory diagrams for the circular arc division processing. , FIG. 6 is a flowchart for explaining the operation of the arc combining processing unit, FIG. 7 is an operation explanatory view of the arc combining processing, FIG. 8 is a principle configuration diagram of the arc extracting processing, FIG. 9 is a vector table, and FIG. 10 is an arc. Operation explanation flowchart of extraction processing,
FIG. 11 shows an example of a table, and FIG. 12 shows an operation explanatory diagram of arc extraction processing. In the figure, 1 indicates an arc division processing unit, and 2 indicates an arc combination processing unit.

Claims (1)

[Claims] 1. A table in which a polygonal line string extracted based on a predetermined condition from a plurality of polygonal lines generated by thinning and approximating a figure is registered as an arc candidate, and an arc candidate polygonal line registered in the table. The temporary radius Ri of the
A circular arc division processing unit (1) for dividing the circular arc candidate, and a difference in temporary radius and a temporary center point calculated respectively for any two circular arc candidates registered in the above table from a predetermined value Is small and the distance between the end points of both is less than or equal to a predetermined value, an arc combining processing unit (2) that connects to one arc or circle is provided, and the above-mentioned division or combination is performed on the arc candidate to form an arc portion. A circular arc extraction device characterized by extracting the arc.