JPS5830621B2 - Intersection detection method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention provides an intersection detection method that is particularly suitable for original figure information obtained by scanning a recognition target figure without applying thinning processing to the recognition target figure. The present invention relates to an intersection detection method that detects intersections (including branch points) such as intersections such as the letters "g" and "+".

Particularly when recognizing handwritten characters, the intersection of character strokes is considered to be one important indicator for recognition.

In order to extract such intersections, conventionally, as shown in FIG. 1, a so-called thinning process is performed to extract the skeleton part of the recognition target figure 1, and the thinned figure 2 is processed by, for example, 3X.
A three-mesh observation window was used to scan and extract intersections.

However, if the stroke width, that is, the character line width, of the recognition target figure (character) is thick, the thinned figure 2 obtained by the above thinning process does not necessarily represent the skeleton of the original figure faithfully. First, as shown by the dotted line 3 in FIG. 1, an undesired intersection may occur at an unexpected location.

In consideration of the above points, the present invention aims to detect intersections by using original figure information as it is without performing line thinning processing.

The intersection detection method of the present invention processes a recognition target figure in which the space between the strokes is substantially free of dust when the recognition target figure is scanned, and the recognition target figure is obtained by scanning the recognition target figure. In a pattern recognition device that performs feature extraction based on scanning information and performs recognition processing of the recognition target figure, when the recognition target figure is scanned in one direction, reflective line segments are extracted along the figure stroke facing the figure frame. It is equipped with a reflected line segment extraction unit that extracts a closed end where one end of the reflected line segment is blocked by a figure, and has a closed end extraction function that extracts a closed end where one end of the reflected line segment is blocked by a figure, and the stroke The present invention is characterized in that an intersection candidate point is set at substantially the center point of the width, and the intersection is determined from the coordinate positions of one or more set candidate points.

This will be explained below with reference to the drawings from FIG. 2 onwards.

FIGS. 2A and 2B are explanatory diagrams each illustrating a mode of intersection detection according to the present invention, and FIG. 3 is an explanatory diagram illustrating a mode of tentatively determining the coordinates of reflective line segments and intersection candidate points according to the present invention. 4 shows the configuration of one embodiment of the main part of the present invention, FIG. 5 is an explanatory diagram illustrating a mode of determining an intersection based on intersection candidate points, and FIG. 6 shows an undesired intersection candidate point. An explanatory diagram illustrating the setting state of is shown.

In FIG. 2, 1 is a figure to be recognized, 2 is a figure frame, 3 to 8 are horizontal scan reflection line segments obtained when the figure to be recognized 1 is scanned in the horizontal direction, 9 to 14 are vertical scan reflection line segments obtained when the recognition target figure 1 is scanned in the vertical direction, 3-1.4
-1.5-1゜6-1.7-1.8-1 are open ends for horizontal scanning, 9-1.10-1.111, 121゜13-1 and 14-1 are vertical, respectively. Open end when scanning direction,
3-2, 4-2, 5-2, 6-2, 7-2.

8-2 is the closed end during horizontal scanning, 9-2゜10-
2.11-2.12-2.13-2.142 are closed ends during vertical scanning, 15 to 26 are intersection candidate points, 27 and 28 are intersections, and SCN is a scanning line.

The candidate point 15 is at the closed end 3-2, the candidate point 16 is at the closed end 42, the candidate point 17 is at the closed end 9-2, the candidate point 18 is at the closed end 10-2, and the candidate point 19 is at the closed end. 72, the candidate point 20 is at the closed end 8-2, the candidate point 21 is at the closed end 5-2,
The candidate point 22 is at the closed end 62, and the candidate point 23 is at the closed end 11-
2, the candidate point 24 is found on the closed end 12-2, the candidate point 25 is found on the closed end 13-2, and the candidate point 26 is found on the graphic stroke by the closed end 14-2.

In the case of the present invention, as will be described later, (:) reflected line segments 3 to 14 along the figure stroke facing the figure frame are extracted, and (11) closed ends 3-2, 4-2 of the reflected line segments.

...14-2 is extracted, (iii) intersection candidate points 15 to 26 are set corresponding to each closed end, and (
IV) When each of the sentence difference point candidate points is a valid candidate point, intersections 27 and 28 are determined, for example, at the center of gravity of each of the candidate points.

Hereinafter, with reference to FIG. 3, extraction of reflected line segments, extraction of closed ends, and setting of intersection candidate points will be briefly explained.

In FIG. 3, 29 to 31 are counters, 3
2 represents an adder circuit.

The extraction of reflection line segments and the extraction of closed ends can be roughly considered as follows.

That is, for example, suppose that the illustrated end 3-2 is extracted as a candidate point for a reflected line segment in the illustrated scan 5CN1 of FIG. Assume that a point (temporarily referred to as point p) is extracted.

At this time, take the difference between the X coordinate value of the point corresponding to the end 3-2 and the X coordinate value of the above point p, and if the difference exceeds the threshold, the reflected line segment 3 is minute candidate point (edge 3-2
) and does not extend to the above point p.

At this time, since the upper part of the reflected line segment candidate point (end 3-2) is occluded by the stroke, the candidate point is regarded as a point on the reflected line segment and also as a closed end of the reflected line segment. do.

For example, while the recognition target figure 1 shown in FIG.
1/1 with half the frequency of the above clock signal relative to 1.
2 clock signal 1/2CL is supplied.

The counter 29 starts counting when the scanning point reaches the x mark position shown in FIG. 2A, and stops counting at the point where the white mesh changes to a black mesh, that is, point a shown in FIG. 2A. be done.

Therefore, when the counting is completed, the contents of the counter 29 represent the coordinate information of point a.

The counter 30 starts counting when the scanning point reaches the x mark position shown in FIG. 2A, and stops counting when the scanning point reaches the position shown in FIG. 2A.

Therefore, when the counting is completed, the contents of the counter 30 represent the coordinate information of the dot.

The counter 31 starts counting when the scanning point reaches the point a shown in FIG. 2A, and stops counting when the scanning point reaches the point a shown in FIG. 2A.

Therefore, when the counting is completed, the contents of the counter 31 have a value corresponding to the distance (ba)/2.

As a result, the adder circuit 32 outputs coordinate information given by (a+b)/2.

Reflection line segment 3 or 4 is located at point a(
or point b - hereinafter abbreviated as a (b)), and then determine point a (b) and point a on the vertically adjacent scanning line.
It is checked whether the points a and (b) are continuous in the vertical direction, and if they are continuous, it can be thought of as connecting each point a and (b) and extracting it as a line segment.

During this time, for the starting end and ending end of the reflected line segment, respectively,
It is checked whether the figure is open to a figure frame or a white mesh area, or whether it is closed by a figure frame or a black mesh area.

When the graphic black mesh area is closed, the ends are closed as described above as closed ends 3-2, 4-2, . . .
It can be considered that...

Note that the above-mentioned extraction of reflection line segments and extraction of closed ends are determined one after another while, for example, the horizontal scanning progresses one after another.

At this time, as mentioned above, the value (a+b)/2 is also obtained for each scan.

Under this condition, when the closed end of the reflection line segment, for example 32, is extracted, the point 15 indicated by the above value (a+b)/2 is
Set as an intersection candidate point.

Note that each candidate point marked with a circle is set during scanning in the horizontal direction, and each candidate point marked with an x is set during scanning in the vertical direction.

Whether or not the intersection candidate point is valid is determined based on the following concept.

That is, (a) the intersection candidate point 17 shown in FIG. 2A is set by the closed end 92.

However, the candidate point 17 is viewed from the closed end 9-2.

Since the other end of the - mark is in contact with the graphic frame 2, the candidate point 17 is not considered as a candidate point for determining the intersection 27.

In other words, since there is no other reflected line segment at the opposite end of the stroke, it is not considered as a candidate point.

(b) The same applies to the intersection candidate point 18 shown in FIG. 2A.

(C) In the recognition target figure 1 as shown in FIG.
Candidate points with an extremely large distance from the closed end A, such as candidate point A' set corresponding to the closed end A, are not considered as candidate points for determining an intersection (the above distance is a threshold α ).

(d) When the recognition target figure 1 as shown in FIG. 6 has a slight bulge in the stroke,
Blocked edges B, C, D, 'E, etc. are extracted, intersection candidate points B', C', D', E', etc. are set, and an undesired intersection F may be determined.

Therefore, when extracting closed ends B, C, D, and E, the length of the reflected line segment from which the closed end is extracted is checked, and if the line segment length is less than a predetermined value, Avoid viewing it as a closed end for setting intersection candidate points.

As a result, candidate points C', D', and E' shown in FIG. 6 are deleted, and since candidate point B' is set by only one closed end B, an intersection is determined. is ignored as a candidate point.

As explained with reference to FIGS. 2 and 3, the coordinate values a, (a+b)/2, and b are determined for each scan.
That will be understood.

FIG. 4 shows an example in which correct candidate point coordinates are set while removing incorrect candidate points as described in (a) to d) above based on the above coordinate values. It shows the configuration.

In the figure, 33 to 36 are coordinate tables, 37 and 38 are registers, 39 is a differential circuit, 40 is a comparison circuit, and 41
is a line segment length counter, and 42 to 44 are AND circuits, respectively.

The following will explain the case of setting the candidate points 15 shown in FIG. 2A as an example.

While horizontal scanning is performed, the coordinate values a, (a
+b)/2 and b are respectively determined and the coordinate table 33,
34, 35.

It is set to 36.

At this time, each time the coordinate value a corresponding to the reflected line segment 3 is set, the line segment length counter 41 is incremented by 1, and it may be considered that the line length of the reflected line segment 30 is maintained.

Now, the point with coordinate value a5 obtained during #5 scanning is reflected line segment 3
Assume that it is found that the closed end 3-2 is the closed end 3-2.

Note that whether or not it is a closed end is determined at least during #7 scanning.

When the closed end 3-2 is determined, the coordinate value a5 of the closed end 32 is set in the register 38, while the table 35
From there, the coordinate value (a 5 + b 5 )/2 is set in the register 37 via the AND circuit 42.

At this time, if either the coordinate value a5 or b5 matches that of the graphic frame 2, the AND circuit 42 is turned off and is not set in the register 37.

The AND circuit 42 performs the above-mentioned invalidity judgments (a) and (b).
Judgments are being made accordingly.

When the value (a 5 + b 5 )/2 is set in the register 37, the difference circuit 39 calculates the coordinate value (a5
Extract the distance between +b 5 )/2 and a5.

The distance is then compared with a threshold value α by the comparison circuit 40, and if the distance is smaller than the threshold value α, the comparison circuit 40 outputs a logic “1”.

The comparison process performs a determination corresponding to the above-mentioned invalidity determination (e).

In this state, when the length of the 30 reflected line segments exceeds a predetermined value, the line segment length counter 41 outputs logic "1", AND circuits 44 and 43 are both turned on, and the register 37
The content (a5+b5)/2 is a valid intersection candidate point 15 (
The coordinates are taken in as the coordinates shown in FIG. 2A).

In determining an intersection from the valid intersection candidate points captured as described above, FIGS. 5A and 5B are used.

As shown in Figure C, the center of gravity of each candidate point is determined from the coordinate values, and the coordinates of the intersection are finally determined.

As described above, according to the present invention, it is possible to directly detect intersections based on original figure information without performing so-called thinning processing.

Note that the reflection line segment extraction and closed end extraction according to the present invention are also widely used for other feature extraction.

Therefore, the necessity of extracting reflected line segments is not disadvantageous to the present invention.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram illustrating problems in line thinning processing, FIGS. 2A and B are explanatory diagrams illustrating aspects of intersection detection according to the present invention, and FIG. 3 is an explanatory diagram illustrating the aspects of intersection detection according to the present invention. An explanatory diagram illustrating a manner in which intersection candidate points are tentatively determined, FIG. 4 shows an embodiment of the main part of the present invention, and FIG. 5 shows a manner in which intersections are determined based on intersection candidate points. FIG. 6 is an explanatory diagram illustrating the setting state of undesired intersection candidate points. In the figure, 1 is a figure to be recognized, 2 is a figure frame, 3 to 8 are horizontal scanning reflection line segments, and 9 to 14 are vertical scanning reflection line segments, 3-2, 4-2. 5-2. ...14-2 are respectively closed ends, 15 to 26 are intersection candidate points, 27 and 28 are intersections, 29
31 to 31 are counters, 32 is an adder circuit, 33 to 36 are coordinate tables, 37 and 38 are registers, 39 is a difference circuit, 40 is a comparison circuit, and 41 is a line segment length counter.

Claims (1)

[Scope of Claims] 1. A recognition target figure whose processing target is a recognition target figure in which the space between strokes is substantially free of dust when the recognition target figure is scanned, and a scan obtained by scanning the recognition target figure. In a pattern recognition device that extracts features based on information and performs recognition processing of the figure to be recognized, when the figure to be recognized is scanned in one direction, reflective line segments are extracted along the figure strokes facing the figure frame. It is equipped with a reflected line segment extraction unit and a closed end extraction function that extracts a closed end where one end of the reflected line segment is blocked by a figure, and the stroke width is calculated on the figure stroke that is in contact with the extracted closed end. An intersection detection method characterized in that an intersection candidate point is set at substantially the center of the intersection, and the intersection is determined from the coordinate positions of one or more of the set candidate points. 2. The closed end used to set the intersection candidate point is determined based on the reflected line segment whose line segment length is equal to or greater than a predetermined value. The intersection detection method described in Section 1. 3. The intersection candidate points used to determine the intersection are limited to intersection candidate points whose distance from the closed end is within a predetermined value, or The intersection detection method described in Section 2. 4. The intersection candidate point used to determine the intersection excludes the intersection candidate point set at the center point between the closed end and the graphic frame. The intersection detection method according to any one of ranges 1 to 3.