JPS6255191B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention provides triangular, quadrilateral, pentagonal, hexagonal,
The present invention relates to a device for identifying and classifying graphic shapes such as circles, ellipses, and ellipses, and object shapes.

For example, in order to input a program into a computer, the steps are generally to create a flowchart, code it, punch it onto a card or tape, and then input it using an input device. Therefore, a lot of work is required. Therefore, if there is an input device that can recognize the flowchart, it is possible to input the program directly from the flowchart into a computer, and the labor-saving effect is enormous.

By the way, in order to recognize a flowchart, you must first understand the symbols used in the flowchart: processing (rectangle), judgment (diamond, hexagon), terminal (ellipse), connector (pentagon, circle, triangle), etc. It is important to identify and classify the

The purpose of the present invention is to enable the above-mentioned identification and classification of figure shapes to be carried out with extremely simple processing.The present invention tracks the outline of a figure while linearly approximating it, and calculates the corners of the figure from the intersection angles of two adjacent straight lines. It is characterized by having recognition logic that simultaneously detects and classifies figures into circles and angles based on extracted line segment information and extracted angle information, improving recognition accuracy, and will be described in detail below.

FIG. 1 is a block diagram of a first embodiment of the present invention, in which a reading section 1 optically reads a planar figure and provides electrical signals corresponding to the coordinates of each point on a line segment forming the figure. The output of the reading section 1 is, for example, in digital format. A contour tracking section 2 tracks contour points that are the outer shape of the graphic pattern read by the reading section 1 . Thereafter, line segment information and angle information are extracted by the line segment/angle extraction section 3, and then the circle/angle classification section 4 performs classification into circles and angles. Based on the various information thus obtained, the shape determining section 5 performs identification and classification of the read figures. Note that the contour point tracking unit 2 may use a known technique such as the 4-connection boundary line tracking algorithm [Transactions of the Institute of Electronics and Communication Engineers, Vol. 56-D, No. 11, pp. 667-668 (November 1973)]. - An example of a contour line obtained using the boundary line tracing algorithm is shown in Figure 2.

FIG. 2A shows an example of an oval outline, and FIG. 2B shows an example of a rhombus outline.

A method for extracting line segments and angles will be explained using the flowchart shown in FIG. Outline point coordinates stored in the storage device are retrieved at predetermined intervals d. For example, at the very beginning, the first point of the contour (P ₁
) and the (1+d)th point (abbreviated as P _1+d ) are extracted. A line segment having these two points as a starting point and an ending point, respectively, is defined as a provisional line segment L. If the distance D2 between the intermediate contour point, that is, the second point _P2 , and the provisional line segment _L is within the predetermined threshold Δl, the third
Distance D ₃ to the th point P ₃ ..., distance D _d to the d th point P _d , and so on, are sequentially determined whether the distance is within a predetermined threshold Δl, and if the distance exceeds Δl, If so, set that point as the end point and set the line segment with D ₁ as the starting point as the extracted line segment S _1. If all distances are within Δl, set L as the extracted line segment S ₁ . Extracted line segment S ₁
The line segment with the end point as the starting point and the end point as the point separated by d is set as the provisional line segment L, and the same operation as above is performed from the distance between the intermediate contour point and L to determine the extracted line segment S. do. Calculate the intersection angle θ ₁ between the extracted line segment S and the previously extracted extracted line segment (S ₁ in this case), and if θ ₁ is larger than the straightening judgment angle θ _s , the extracted line segment S is the extracted line segment S ₂ , and if θ ₁ is smaller than the linearization judgment angle θ ₂ , the extracted line segment S and the extracted line segment
Integrate with S ₁ . In other words, the line segment whose starting point is the starting point of S ₁ and whose ending point is the ending point of S is re-extracted.
Let it be S ₁ . In addition, if the intersection angle θ ₁ is larger than the linearization judgment angle θ _s , the intersection angle θ ₁ is also larger than the angle judgment angle θ
Check whether it is larger than _L , and if larger, add 1 to the number of detected angles.

To summarize the above, the intersection angle θ ₁ between the current extracted line segment S and the previously extracted extracted line segment S ₁ is calculated, and when θ ₁ ≦ θ _S , S ₁ and S are considered to be a straight line. Let the line segment be S ₁ .

When θ _S <θ ₁ ≦θ _L , S is set as the extracted line segment S ₂ and it is determined that S ₁ and S ₂ form an arc.

When θ _L <θ ₁ , S is set as the extracted line segment S ₂ and the intersection of S ₁ and S ₂ is determined to be a corner of the figure.

It turns out that.

The above operations are sequentially repeated along the contour until one complete rotation of the contour is completed.

In order to facilitate understanding, the explanation will be supplemented using the specific example shown in FIG. The black dots in the figure are contour points, and the broken lines are part of the contour line. predetermined interval d
The explanation will proceed assuming that the predetermined threshold value Δl=8 and the predetermined threshold value Δl=2. First, if the line segment with P ₁ as the starting point and P ₉ as the end point is a provisional line segment L, then the distances D ₂ to D ₈ between intermediate contour points P ₂ to _{P 8} and L are all within Δl, so L
Let be the extracted line segment S ₁ . Next, we use line segments ₉ and ₁₇ with P ₉ as the starting point and P ₁₇ as the end point as provisional line segment L, and check the distance to the intermediate contour point. Since D ₁₄ > Δl, we define provisional line segment L as a line segment. _9.14 , and the extracted line segment S becomes line _{segment 9.14 [} Figure 4 A]. So S ₁
By examining the intersection angle θ ₁ between and S, we find that the linearization judgment angle θ _S
Since it is smaller than , S is unified with S ₁ and extracted line segment S ₁ is changed to line _{segment 1.14 .} Then line segment ₁₄・
When P ₂₂ is set as the provisional line segment L, and the distances to the intermediate contour points are examined, they are all within Δl, so L is set as the extracted line segment S. Therefore, when the intersecting angle θ ₁ between S ₁ and S is examined, it is larger than the linearization determination angle θ _S , so S is registered as the extracted line segment S ₂ . In other words, the extracted line segment S ₂
= line segment ₁₄・₂₂ .

By the way, since the intersection angle θ ₁ is larger than the angle determination angle θ _L , add 1 to the number of detected angles (initially, the number of detected angles =
0, the number of detected angles = 1), and at the same time, θ ₁ is registered as the extraction angle K ₁ [Fig. 4B].

Next, line segments ₂₂ and ₃₀ are set as provisional line segments L, and when the distances to the intermediate contour points are checked, they are all within Δl, so L is set as the extracted line segment S. Then, when the intersecting angle θ ₂ between S ₂ and S is examined, it is larger than the linearization determination angle θ _s , so S is registered as the extracted portion S ₃ . That is, the extracted line segment S ₃ = line segment ₂₂ · ₃₀ . By the way, since the intersection angle θ ₂ is smaller than the angle determination angle θ _L , the number of detected angles remains unchanged, and the extraction angle K is not registered, but only the intersection angle θ ₂ is stored [FIG. 4C].

These operations are repeated one after another until one complete rotation of the contour line has been traced.

At the time when tracing one round has been completed, extracted line segment information and extracted angle information have been obtained. however,
Just by tracing one round of the tight circle, the connection relationship between the last extracted line segment S _o and the first extracted line segment S ₁ cannot be determined, so find the intersection angle θ _o between S _o and S ₁ and do the same as above. In other words, when θ _o >θ _L >θ _S , S _o is registered as a formal extraction line segment, 1 is added to the number of detected angles, and θ _o is registered as the extraction angle K _n . Further, when θ _L ≧ θ _o > θ _S , the extracted line segment S _o and the intersection angle θ _o are formally registered. Also, when θ _L > θ _S ≧θ _o , S _o
It is necessary to re-register the line segment that integrates and _S1 as the extracted line segment _S1 . In this way, the extraction of line segment information and corner information is completed.

FIG. 5 shows an example of line segment/corner extraction results for the contour example shown in FIG. 2. Note that the extraction results are obtained when the set values of each parameter are a predetermined interval d=8, a predetermined threshold value Δl=2, a linearization judgment angle θ _S =15°, and an angle judgment angle θ _L =30°.

Now, the shape of a figure is identified and classified from the line segment information and angle information obtained in this way, but just because the number of detected angles is m, it cannot be suddenly determined that it is an m-gon. This is because, as is clear from the line segment/angle extraction result example in FIG. 5A, corners are detected even in circles such as ellipses, ellipses, and circles. Of course, by setting the angle determination angle θ _L large, it is possible to prevent angles from being detected from circles, but it is not possible to set θ _L large indefinitely. This is because in a hexagon or a rhombus, the intersecting angle θ is quite small, so if θ _L is increased, there is a risk that an angle with a small intersecting angle will be mistakenly judged as an arc. In order to resolve this contradiction, it is very effective to use circle/angle classification logic in combination. i.e. equilateral triangle, square,
Parameter values such as angle detection angle θ _L are set to accurately detect angles of angles such as rectangles, rhombuses, and hexagons, and the number of detected angles is utilized to the maximum for shape identification of angles. The idea is not to place much emphasis on the number of detected angles when identifying shapes of circles.

The circle/corner classification logic will be explained using the flowchart of FIG.

Assuming that the upper limit of the number of angles of the polygon to be recognized is n (for example, if it is sufficient to distinguish and classify from triangles to hexagons, n = 6), then when the number of detected angles is 2 or less and the number of detected angles is When is (n+1) or more, it is a circle class, but when n≧number of detected angles≧3, it may be a circle class, and there is also a possibility that it is a horn class.

Therefore, the ratio of the number of detected angles to the number of detected lines (number of detected angles/number of detected lines) is called the angle number ratio.If the number of angles is extracted accurately for angles, In the class, the number of detected angles = the number of detected lines, so the angle ratio should be 1. In the circle number, many arcs are extracted, but the number of detected angles should be 0, so the angle ratio should be 0. Become. However, if some error occurs in line segment/corner extraction, the angle ratio of angles will decrease slightly from 1, and the angle ratio of circles will increase slightly from 0. In the actual measurement example shown in FIG. 5, the angular ratio of the ellipse, which is a circle, is 3/11 = 0.27, and the angular ratio of the rhombus, which is a square, is 4/6 = 0.67.

Therefore, the circle identification threshold k ₀ is set to an appropriate value slightly larger than 0, and those whose angle ratio is less than or equal to k ₀ are identified as circles. In addition, the angle number identification threshold k ₁ is set to an appropriate value slightly smaller than 1, and those whose angle number ratio is k ₁ or more are identified as angles. In this way, most figures can be distinguished and classified into circles and angles, but with emphasis on certainty, the angle discrimination threshold k ₁ is set fairly close to 1, and the circle discrimination threshold k ₀ is set fairly close to 1. If it is set close to 0, there are some shapes where k ₁ > angular ratio > k ₀ . In that case, reliability can be increased by further utilizing the intersection angle deviation. The intersection angle deviation is the extracted intersection angle θ
It is the value obtained by subtracting the minimum value from the maximum value of ₁ ~ θ _o ,
In the case of circles, the intersection angle deviation value is small, and in the case of angles, the intersection angle deviation value is large, so that they can be distinguished and classified into angles and circles, respectively, depending on the magnitude of the appropriate threshold Δθ. The reason is that in the case of circles, all intersecting angles θ ₁ to θ _o are the linearization judgment angle θ _S and the angle judgment angle θ
It should be a value between _L and L, but since the number of detected angles is 0 at that time, it has already been classified as circular before coming to the judgment of the intersection angle deviation, and it has reached this judgment part. means that at least one detection angle was detected. That is, most intersection angles θ are θ _L ≧ θ > θ _S or happen to be θ > θ _L
This means that there is also an intersection angle θ. However, since the intersection angle θ>θ _L cannot exceed θ _L by that extreme, the intersection angle deviation = θ _nax −θ _nio
is at most a slightly larger value than θ _L −θ _S. In addition, in the case of angles, since there are no arcs, all intersecting angles θ ₁ to θ _o should be larger than the angle judgment θ _L , but in that case, the number of detected angles = the number of detected lines. Therefore, the angle ratio becomes 1, and it is already classified as angle before coming to the judgment of the intersection angle deviation.The fact that it has reached this judgment section means that the number of detected angles<the number of detected lines, that is, _θL ≧θ>θ This means that there is at least one intersection angle θ that satisfies _S. Therefore, intersection angle deviation = θ _nax −θ _nio
is at least θ _nax −θ _L. Because it is,
If a value satisfying θ _nax −θ _L >Δθ≫θ _L −θ _S is selected as the threshold value Δθ of the intersection angle deviation, it is possible to perform selective classification into circles and angles.

To give a specific example, if the angles are only from a regular triangle to a regular hexagon, the minimum value of the intersecting angle is 60° for a regular hexagon, and if θ _L = 30° and θ _S = 15°, Δθ The condition that should be satisfied is 30゜＞Δθ from the formula
≫15°, so it should be set to about 25°.

According to experiments, _line segments _and
Corners were extracted and 40 types of figure patterns were classified as circles/corners using the angle identification threshold k ₁ = 0.85, the circle identification threshold k ₀ = 1.15, and the intersection angle deviation threshold Δθ = 30°. , the classification accuracy rate was 100%. here 40
The breakdown of the shape patterns of the species is equilateral triangle, square,
Rectangle, rhombus (interior angles are 60° and 120°), regular hexagon,
Dimensions are varied in 5 steps for 8 types: circle, ellipse, and ellipse.

From the line segment information, corner information, and circle/corner information obtained in this way, the shape of the figure can be easily identified and classified.

Figure 7 is a flowchart for determining the shape of angles.
゜), a regular pentagon, and a regular hexagon will be explained below. When the number of detected angles is 3, 5, and 6, there is only one corresponding figure type each, so when the number of detected angles = 3, it is an equilateral triangle, and the number of detected angles =
When the number of detected angles is 5, it can be determined that it is a regular pentagon, and when the number of detected angles is 6, it can be determined that it is a regular hexagon.

When the number of detected angles is 4, there are three types of corresponding figures: square, rectangle, and rhombus, so in order to identify and classify them, first check whether each of the four detected angles K ₁ to _{K 4} is approximately a right angle. If it is almost a right angle, it is a square or rectangle, and if it is not, it is a rhombus. Note that whether or not the angle is approximately right angle may be determined by determining, for example, whether 80°<K ₁ to K ₄ <100°.

If each of the four detection angles K ₁ to _{K 4} is approximately a right angle, the lengths of the extracted line segments are set as l ₁ , l ₂ , l ₃ , l ₄ in order of length, and (l ₃ + l ₄ )/(l ₁ +l ₂ ) is larger than the side length ratio threshold H, it is determined that it is a square, and the side length ratio threshold H
It is determined that it is a rectangle in the following cases. The side length ratio threshold H corresponds to the side length ratio of the rectangle to be identified.
You can set it to a value slightly larger than that.

FIG. 8 is a flowchart for determining the shape of circles, and for convenience of explanation, an example will be described in which the types of circles are limited to circles, ellipses, and ellipses.
For circles and ellipses, all extracted line segments are circular arcs, so the lengths of the extracted line segments should be short and fairly uniform. On the other hand, since the length has two straight line segments, only two of the extracted line segments should be long, and the others should be short and fairly even. Therefore, the lengths of the extracted line segments are set as l ₁ , l ₂ ,
l ₃ , l ₄ , and when (l ₁ + l ₂ )/(l ₃ + l ₄ ) is larger than the side length ratio threshold Z, it is determined that it is an ellipse, and when it is less than the side length ratio threshold Z, it is determined that it is a circle. It is an ellipse. Side length ratio threshold Z
is preferably set near a value obtained by dividing the minimum length of the straight line portion of the ellipse to be identified by the predetermined interval d described above.

The identification classification between a circle and an ellipse is the X of the figure pattern.
If we take the projection onto the axis and the Y axis, in the case of a circle, theoretically, X _V = X _H and Y _V = Y _H , so
It should be that XHI=X _V /X _H =1, YHI=Y _V /Y _H =1. Therefore, considering the margin for some errors, the case where XHI≒1 and YHI≒1 is determined to be a circle, and the other cases are determined to be an ellipse.

Note that the intersection angle deviation, that is, the value obtained by subtracting the minimum value from the maximum value of the extracted intersection angles θ ₁ to _{θ o} , can also be used for classification between circles and ellipses. Because,
In the case of a circle, the radius of curvature is always constant over one circumference, so the intersection angles θ ₁ to θ _o are all almost equal and the intersection angle deviation approaches 0, whereas in the case of an ellipse, the radius of curvature This is because since the angle of intersection is not constant, it is possible to utilize the property that the intersection angle deviation has a value above a certain level.

Thus, equilateral triangles, squares, rectangles, rhombuses,
It is possible to reliably identify and classify regular pentagons, regular hexagons, circles, ellipses, and ellipses.

As explained above, in the first embodiment, in the method of tracking the outline of a figure while linearly approximating it, detecting the corners and arcs of the figure from the intersection angles of two adjacent straight lines, and identifying and classifying the shape of the figure, It is equipped with a circle/angle classification section that first classifies shapes into circles and angles based on extracted line segment information and extracted angle information. There is an advantage that even if a corner of a figure is incorrectly determined, an error will not occur in the result of classification and identification of the figure.

In addition, if it is not equipped with a circle/angle classification section,
In order to avoid misjudging the intersection angle between two circular arcs as an angle of a figure, the angle judgment angle θ _L must be made large, and as a result, there is a possibility that a real angle may be missed. There are cases where there is little margin for the setting value of _L. However, by providing a circle/angle classification section,
Since the angle determination angle θ _L can be set with the primary consideration being to detect all the corners of the figure, there is also the advantage that the margin for the set value of θ _L is larger than in the former case.

In the first embodiment, a method was explained in which the slope of the extracted line segment is not used in the shape determination section, but since the starting point coordinates and end point coordinates of each line segment are known, slope information of each line segment can also be obtained. By using gradient information, it is easy to detect parallel relationships between line segments.
More accurate identification and classification becomes possible. It is also possible to increase the types of figures to be identified.

Furthermore, in the first embodiment, only the method of identifying and classifying the shapes of figures was explained, but it goes without saying that by using the gradient of extracted line segments, etc., it is also possible to determine the inclination angle of figures. stomach.

Furthermore, in the first embodiment, only the method of identifying and classifying the shape of the figure was explained, but it is also possible to obtain the figure dimensions from the length information of the extracted line segment, the coordinate information of the corner detection point, etc. Needless to say.

Since the present invention can accurately identify and classify basic graphic shapes, it can of course be used for flowchart recognition and input equipment, and can also be used for object identification and classification such as parts. can do. It can also be used to identify and classify outer frames in recognition and verification of seal impressions.

[Brief explanation of the drawing]

Fig. 1 is a block diagram of the first embodiment of the present invention, Fig. 2 A and B are examples of contour lines, Fig. 3 is the flow of the line segment/corner extraction section of the embodiment of the present invention, Fig. 4 A, B
and C are explanatory diagrams of the line segment/corner extraction method, Figure 5A
and B are examples of line segment/corner extraction results according to the embodiment of the present invention, FIG. 6 is the flow of the circle/angle classification section according to the embodiment of the present invention, and FIG. 7 is the shape determination section for angle figures according to the embodiment of the present invention. FIG. 8 is a flowchart of the circular figure shape determination section according to the embodiment of the present invention. 1...Reading section, 2...Contour tracking section, 3...Line segment/corner extraction section, 4...Circle/corner classification section, 5...Shape determination section, θ _S
... Straight line judgment angle, θ _L ... Angle judgment angle, S ₁ - S _o ... Extraction line segment, θ ₁ - _{θ o} ... Intersection angle, K ₁ - K _n ... Extraction angle, k ₀
... Circle identification threshold, k ₁ ... Horn identification threshold, Δθ... Threshold for intersection angle deviation, H... Side length ratio threshold.

Claims (1)

[Scope of Claims] 1. A reading unit that optically reads line segments that make up a figure drawn on a sheet of paper and provides electrical signals corresponding to the coordinates of each point that makes up the line segment; A contour tracking section that tracks the contour points of the figure pattern read by the contour tracking section, a provisional line segment connecting two contour points, and a contour point sandwiched between the two contour points, and a distance between the two contour points are always less than or equal to a predetermined threshold. , and means for sequentially linearly approximating the contour line by a group of continuous provisional line segments such that the interval between the two contour points is maintained at an initial setting value as long as the condition is met; Based on the magnitude relationship between the intersection angle between two adjacent straight lines and the two types of large and small thresholds, if the intersection angle is less than the small threshold, the two straight lines are integrated into one straight line, and the intersection angle is set to the small threshold. If the line segment is larger, the two straight lines are registered as an extracted line segment without unifying them, and if the intersection angle is larger than the larger threshold, the line segment is created by repeating the operation of registering the intersection angle and the detected angle. A line segment/corner extraction unit configured with a means for extracting information and corner information, and a shape determination unit that identifies and classifies figures from the extracted line segment information and corner information, and calculates the number of detected corners. The figure pattern is divided into circles and angles by the value obtained by dividing the value by the number of extracted line segments, the magnitude relationship between the two threshold values, and the magnitude relationship between the value obtained by subtracting the minimum value from the maximum value of the extracted intersection angles and the threshold value. An apparatus for identifying and classifying graphic shapes, characterized by comprising a circle/corner classification section for classifying shapes.