JPH0250278A - Closed loop graphic detecting device - Google Patents

Abstract

PURPOSE:To faithfully express a shape without distortion and to simplify device constitution by detecting a line segment to connect the starting point and ending point of a stroke component in respective scanning directions as a segment. CONSTITUTION:An original pattern is scanned in plural prescribed directions and the stroke component in each scanning direction is extracted as a sub pattern. Then, the line segment to connect the starting edge point and termination point of this sub pattern is detected as the segment. Accordingly, the segment to express the original pattern is detected by each scanning direction. Thus, the shape in the branching or crossing of the original pattern or in a joining part can be faithfully expressed without the distortion and the linearity of a linear part in the original pattern can be faithfully reflected to the segment.

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention relates to an apparatus for detecting closed-loop figures in the recognition of characters and figures, for example, characters and figures depicted in drawings such as logic circuit diagrams.

(Prior Art) In closed-loop detection processing in a conventional closed-loop figure detection device, a thinned image is created by thinning a binary image of an information medium such as a drawing so that the line width is 1. Then, a line with a line width of 1 is divided into segments I according to predetermined conditions.
For each segment, vector data consisting of information such as the position, length, angle, connectivity, etc. of the segment is extracted (conversion of the thinned image to vector data).

Then, based on the extracted vector data, the line type of the segment (for example, the line type can be a horizontal, vertical or diagonal M-line, a circle or arc, an ellipse or an elliptical arc, etc.) recognition is performed, and the segments constituting a closed loop are detected from the w4 tangent relationship between the segments (closed loop detection), and the shape of the closed loop is determined from the line types of the segments constituting the closed loop.

(Problem to be Solved by the Invention) However, in the closed-loop detection processing in the conventional device described above, some symbols used in drawings, etc., which thin the binary image for closed-loop detection, have straight parts. There are symbols that have joints with curved parts, and symbols that have branches or intersections, but these joints, branches, and intersections are easily distorted by line thinning, especially in symbols that have many joints, branches, or intersections. Since the shape of the symbol may be severely distorted, processing to correct the distortion is also required. This distortion correction process is a complicated process and requires a long processing time, so there is a problem in that the speed of the closed loop detection process cannot be increased due to the correction process. Furthermore, there is a problem in that the provision of means for performing correction processing complicates the image production structure.

In the closed-loop detection process in the conventional apparatus described above, a large amount of vector data detected for each segment is stored one-dimensionally, that is, in the order of the detected segments. When performing processing to recognize the line type of segments or to investigate the adjacent Wi relationship between segments, the information necessary for each process is searched from information such as position, length, angle, connectivity, etc. In order to do these −
Read out a large amount of dimensionally arranged vector data one by one, and recognize the line type based on the retrieved information.
I was investigating the closing clerk. Therefore, since the necessary information is retrieved by reading out a large amount of detailed data one by one, there is a problem that the amount of data to be processed increases, and therefore the processing time increases.

SUMMARY OF THE INVENTION In order to solve the above-mentioned conventional problems, it is an object of the present invention to provide a closed-loop figure detection device that can detect closed loops with simpler processing and configuration than conventional ones, and can reduce the amount of information used for closed-loop detection processing compared to conventional ones. It is in.

(Means for Solving the Problems) In order to achieve this object, the closed loop figure detection device of the present invention photoelectrically converts an information medium containing at least a closed loop figure,
A sub-pattern that creates a ring pattern of a digital signal represented by black bits and white bits by quantizing it, scans this ring pattern in a plurality of predetermined directions, and extracts stroke components in each scanning direction as a sub-pattern. an extraction means; a segment extraction means for extracting the coordinates of the starting point and ending point of the subpattern in the scanning direction when extracting the subpattern; A closed-loop segment search means for sequentially searching for segments having endpoints within a region near the endpoints of the searched segments in order to sequentially search for a starting point segment, a predetermined number of intermediate segments, and an endpoint segment constituting a closed-loop figure. It is characterized by comprising the following.

In carrying out the present invention, a subpattern is defined as a pixel group consisting of continuous figure constituent pixels in the scanning direction at the time of subpattern extraction, and the continuous length l is a predetermined length. Preferably, it is a component. In this case, the subpattern has a continuous length l! ≧Nw
(However, N is a constant and W is the line width in the ring pattern.) It is more preferable to use a stroke component constituted by a group of figure constituent pixels.

Further, in carrying out the present invention, the segment extraction means scans the subpattern in a direction forming a predetermined angle with the scanning direction during subpattern extraction, and the change point from white bit to black bit is obtained for each scanning line. Preferably, the means extracts the coordinates of the starting point and ending point of the sub-pattern based on the coordinate position and number of points of change from black bits to white bits, and the coordinate position and number of points of change from black bits to white bits.

Further, in carrying out the present invention, the segment extracting means is configured to include means for storing the coordinates of the starting point and the ending point of each segment in close relation to the origin of the coordinates, and for each scanning direction. It is preferable to do so.

Further, in carrying out the present invention, the closed loop segment search means includes a process of searching for a starting point segment, and a process of searching for an intermediate segment having one end point within a region near one end point of the found starting point segment. , searching for an end point segment that has one end point within a region near the other end point of the searched intermediate segment and has the other end point within a region near the other end point of the origin segment. is preferable.

In general, in implementing the present invention, the closed-loop segment search means includes a process of searching for a starting point segment, and a process of searching for an intermediate segment having one end point within a neighborhood area of one end point of the found starting point segment. and a process of searching for the next intermediate segment having one end point within the neighborhood 9i of the other end point of the retrieved intermediate segment a predetermined number of times; Preferably, the means performs a process of searching for an end point segment that has one end point in a neighboring region and has the other end/point in a neighboring region of the other end point of the starting point segment.

(Operation) According to the closed-loop figure detection device of the present invention configured as described above, a ring pattern is scanned in a plurality of predetermined directions, stroke components in each scanning direction are extracted as subpatterns, and the starting end point of this subpattern is extracted. By detecting the line segments connecting the and end points as segments, segments representing the ring pattern are detected in each scanning direction.

Since the line segment connecting the starting point and ending point of the sub-pattern is detected as a segment, the shapes of branches, intersections, and joints of the original pattern can be expressed more faithfully and without distortion than before in the segment. Furthermore, the straightness of the straight line portion of the original pattern can be more faithfully reflected in the segments than before.

Roughly speaking, according to the closed-loop figure detection device of the present invention, by sequentially searching for segments having endpoints within the vicinity of the endpoints of the searched segments, the starting point segment, intermediate segment, and end point segment constituting a closed loop are sequentially searched. To detect. The process of searching for a segment whose endpoint is within the vicinity of the endpoint of the searched segment is simple, and the process of detecting segments as described above is also simple, making the process of detecting closed-loop shapes simpler than before. can be converted into

(Example) Embodiments of the present invention will be described below with reference to the drawings.

Note that the drawings are merely shown schematically to the extent that this invention can be understood, and therefore, the arrangement positions of the components shown in the drawings, the flow of input/output signals, the shapes, dimensions, and positional relationships are merely examples shown in the drawings. It is not limited to.

FIG. 1 is a functional block diagram schematically showing the configuration of this embodiment.

As shown in the figure, the closed-loop figure detection device of this embodiment includes sub-pattern extraction means 10, segment extraction means 1
2 and closed loop segment search means 14. The sub-pattern extraction means 10 scans a ring pattern represented by a quantized photoelectric conversion signal of an information medium including at least a closed-loop figure in a plurality of predetermined directions, extracts stroke components in each scanning direction as a sub-pattern, and extracts a segment. The extraction means 12 extracts the coordinates of the starting point and ending point of the subpattern in the scanning direction at the time of subpattern extraction. The closed-loop search means 14 uses a line segment connecting the starting point and the ending point of a sub-pattern as a segment representing the sub-pattern, and sequentially searches among these segments for a starting point segment, a predetermined number of intermediate segments, and an ending point segment that constitute a closed-loop figure. Therefore, segments having endpoints within the vicinity of the endpoints of the searched segments are sequentially searched.

Roughly speaking, the closed-loop figure detection device of this embodiment includes an original pattern memory 16 for storing the original pattern, a line calculation means 18 for calculating the line width W in the ring pattern, and a sub-pattern for storing sub-patterns for each scanning direction. storage means 20;
It includes a segment storage means 22 that stores segments for each scanning direction, and a closed loop data memory 24 that stores information on segments that roughly constitute a closed loop, such as the coordinates of the start point and end point.

This embodiment will be explained in more detail below.

<Ring pattern> A photoelectric conversion unit (not shown) photoelectrically converts an optical signal from an information medium such as a logic circuit diagram into a quantized electrical signal, and converts the ring pattern or original signal represented by this quantized electrical signal into a quantized electrical signal. It is simultaneously input to the pattern memory 16 and line width calculation means 18.

In this embodiment, the ring pattern is, for example, a binary quantized electrical signal, and the character figures are expressed with black bits, and the background part of the character figure (the ground part of the information medium) is expressed with white bits. .

FIG. 2 is a diagram for explaining the original pattern. The original pattern P shown in FIG. 2 is composed of, for example, a line figure pattern P1 and a background pattern P2. In the illustrated example, for convenience of explanation, the ring pattern is a pattern consisting of a line figure pattern and a background pattern, but it may be a pattern that includes not only line figure patterns but also characters and other patterns.

Each pixel position of the original pattern is expressed in an x-y coordinate system arbitrarily set on the memory 16, and the memory 16 is
The memory 16 is a memory from which the original pattern of a pixel at a position expressed in the y coordinate system can be freely read out, and therefore the original pattern can be freely read out from the memory 16 using the x and y coordinates.

<Line Width Calculation Means> The line width calculation means 18 has a shift register configuration similar to a well-known filter circuit, and closes to the input original data so that, for example, all points in a (2×2) window become black bits. The number of points Q and the number A of all black bits in the original pattern are counted, and the line width W is calculated based on the following well-known approximation formula (1).

w= 1/ (1-(Q/A)) - (1) Sub-pattern extraction means> Figure 3 is a diagram for explaining sub-pattern extraction, and (A), (B), (C) and (D) shows a vertical sub-pattern, horizontal sub-pattern, right diagonal sub-pattern, and left diagonal sub-pattern extracted from the original pattern shown in FIG. 2, respectively.

In this embodiment, the scanning directions of the ring pattern are, for example, four directions: vertical (parallel to the y-axis), horizontal (parallel to the The sub-pattern extraction means 10 scans the ring pattern in the vertical direction to extract a vertical sub-pattern VSP (
Figure 3 (A) 9) v! VSP extraction means 10a for extracting oil
By scanning the ring pattern in the horizontal direction (direction parallel to the X-axis), the horizontal sub-pattern H3P (Fig. 3 (8)
? H5P extraction means 10b extracts the ring pattern R3P (refer to FIG. 3(C)); R3P extraction means 10c extracts the right diagonal sub-pattern R3P (see FIG. 3(C)) by scanning the original pattern diagonally to the right in 456 directions; By scanning in 456 directions, the left diagonal sub-pattern LSP (Fig. 3(D)
9).

Moreover, the sub-pattern extracting means 10 of this embodiment is a pixel group consisting of continuous figure constituent pixels in the scanning direction at the time of sub-pattern extraction, and the continuous length β is a pixel group of a predetermined length (for example, !≧Nw( (N is a constant) A stroke component consisting of a figure-constituting pixel group with a length l) is extracted as a sub-pattern in the scanning direction.

More specifically, the vSP extraction means 10a scans the entire original pattern in the memory 16 in the vertical direction, and detects black bits that are continuously detected on the scanning line in the vertical direction. Among the black bit groups consisting of consecutive black bits on the scanning line, the length l is a predetermined length, for example, β≧N
The black bit group corresponding to w is extracted and stored in the vSP memory 20a. As a result, only vertical sub-patterns, which are stroke components in the vertical scanning direction, can be extracted from the original pattern, as shown in FIG. 3(8).

Similarly to the VSP extraction means 10a, the H3P extraction means 1
0b extracts the horizontal sub-pattern and stores it in the H8P memory 20b, the R3P extraction means 10c extracts the right diagonal sub-pattern and stores it in the R3P memory 20c, and roughly the LSP extraction means 10d extracts the left diagonal sub-pattern and stores it in the LSP memory. Save to 20d.

When the angle between the line segment consisting of the connected black bit groups and the main scanning direction, for example, the horizontal direction, is e, the length l of the black bit group is β''=nw (however, n=1/ Si
nθ). Thus, for example, in the horizontal and vertical directions! ≧N, W (however, N, = 1/Sinθ1), a black bit group of length p, and β≧ in the right diagonal and left diagonal directions.
Try to extract a black bit group of length β such that N2w (N2=1/Sinθ2), however, θ1+θ2≦45°
), el and θ2 to arbitrary suitable values (for example, 131=02
=, 22.5'), all line segments can be classified and extracted into one of the sub-patterns.

sub-pattern storage means> In this embodiment, vertical, horizontal, right diagonal 45 degrees, and left diagonal 4
In order to store subpatterns extracted for each of the four scanning directions in the 5° direction for each scanning direction, the subpattern storage means 2 is used.
0wo, VSP memory 20a, H3P memory 20b 1st S
It consists of a P memory 20c and an LSP memory 20d.

An x-y coordinate system is arbitrarily set on each memory 20a to 20d, and the pixel position of each sub-pattern is expressed in the x-y coordinate system, and the storage and reading of each sub-pattern is performed using x and y coordinates. I use it so that I can do it freely.

The extracted sub-patterns are stored in memories 20a, 20b, 20c.
When m is stored in 20d, the subpattern is stored at a pixel position corresponding to the pixel position on the original memory 1.6 of the extracted subpattern.

<Segment extraction means> Segment extraction means (2) of this embodiment is the
Segments of sub-patterns are extracted by applying the method disclosed in Japanese Patent No. 55868. In other words, the segment extraction means 12 scans the subpattern in a direction forming a predetermined angle (for example, perpendicular to the scanning direction at the time of subpattern extraction), and obtains the coordinate position of the point of change from white bit to black bit for each scanning line. The coordinates of the starting point and ending point (hereinafter simply referred to as the starting point and ending point) of the sub-pattern are extracted based on the coordinate position and the number of points of change from black bits to white bits.

Furthermore, in this embodiment, in order to extract the coordinates of the starting point and ending point of the sub-pattern in each of the four scanning directions of vertical, horizontal, 45° diagonal right and 45° left diagonal, the segment extracting means 12 is used to extract the coordinates of the starting point and ending point of the vertical sub-pattern. VSEG extracting means 12a for extracting the coordinates of the end point, H3EG extracting means +2b for extracting the coordinates of the start point and end point of the horizontal sub-pattern, and R3E extracting the coordinates of the start point and end point of the right diagonal sub-pattern.
It consists of a G extraction means 12c and an LSEG extraction means +2d for extracting the coordinates of the starting point and end point of the left diagonal sub-pattern.

The VSEG extraction means 12a scans the vertical sub-pattern in a direction that makes an angle of, for example, 90 degrees with the scanning direction when extracting the vertical sub-pattern, that is, in the horizontal direction, and extracts the black bit ( The coordinates of the black bit (hereinafter referred to as the black change point) and the coordinates of the white bit (hereinafter referred to as the white change point) when the black bit changes to the white bit are detected for each scanning line, and the The starting point and the starting point of the vertical sub-pattern are determined based on the coordinates of the detected black change point and white change point and the coordinates of the black change point and white change point detected in the scanning line one line before the scanning line that has finished the scanning. Extract the coordinates of the end point.

Similarly to the VSEG extracting means 12a, the H8EG extracting means +2b scans a vertical sub-pattern in the vertical direction, and the R5EG extracting means 12c scans a right diagonal sub-pattern, for example, in a 45° left diagonal direction, roughly extracting LSEG. The means +2d extracts the coordinates of the starting point and ending point of each sub-pattern by scanning the left diagonal sub-pattern in a right diagonal direction of 45°, for example.

Assuming that a scanning line or one stroke is crossed, on the scanning line, a black bit is detected successively after a white bit, a white bit is detected after a continuous black bit, and so on.
Therefore, after the black bit is detected consecutively after the black change point, the white change point is detected. Therefore, the detection of a change point can be regarded as the detection of a stroke, roughly speaking, the black-white change point is when a black bit is detected consecutively after a black change point, and then a white change point is detected. It can be seen that if the black-and-white change point is detected for a particular stroke, the black-and-white change point can be detected for each stroke even when a scanning line crosses a plurality of strokes.

Also, if the line that has just been scanned is called the scanning line, and the line one line before the scanning line is called the previous line, then the strokes that were not detected in the previous line but are the same as the strokes detected in the scanning line. , the change point in the scan line is the change point of the starting point of a newly appearing stroke in the scan line. Further, the change point in the previous line of the stroke detected in the previous line but not detected in the scanning line becomes the change point of the end point of the stroke that disappeared in the scanning line.

The continuity of the stroke is expressed by the following relational expressions (2a) and (2b)
Judgment can be made based on. A black-and-white change point that satisfies relational expressions (2a) and (2b) is a change point of the same stroke, and if not, a change point of a different stroke.

XaYm≦X mV (lll+ + + ”-・
(2a) Xwvm≦X BY(111+11 − (
2b) However, the X of the black change point detected in the Ym row
The coordinates and the X coordinate of the white change point are ×8□ and XWVm,
In addition, the X coordinate of the black change point and the X coordinate of the white change point detected in the line YCm+1), which is the next line after the Ym line, are
(□1. and XI'/Tm.1.

Hereinafter, extraction of the start point and end point of a vertical sub-pattern will be explained using extraction of the start point and end point as an example.

FIGS. 4(A) to 4(8) are diagrams for explaining extraction of the starting point and ending point of a sub-pattern.

A vertical pattern as shown in Fig. 4 (A) is detected, and this pattern is scanned in the main direction from the origin O in the direction where the shall be scanned.

As the pattern shown in FIG. 4(A) is scanned, no black-white change point is detected from the scanning start line to the line one line before the 71st line, and the black-white change point (2
change points) are detected.

Since no change point has been detected in the lines up to one line before the 71st line, the stroke change point detected in the 71st line becomes the change point of the stroke starting point.

Assuming that the stroke that appeared in line 71 is stroke 1, the coordinates of the starting point of this stroke are shown in the VSEG table 22a.
Saved in

If the start point of a stroke is expressed, for example, by the coordinates of the midpoint of the black and white change point at the start point, the coordinates of the black change point detected on the 71st scanning line are (Xsv+, Yy+) and the coordinates of the white change point are (Xwv+ % Yv+ ) (however, Y□ is 7
The X coordinate of the starting point of the stroke is (XaVI +xwy+)/2, and the Y coordinate is YVI.

Roughly speaking, the VSEG extracting means 12a scans 71 lines or less, but at this time, the VSEG extracting means 12a uses the relational expression (2a
) and (2b) to determine the continuity of the stroke. The VSEG extracting means 12a stores the coordinates of the change points of the scanning line and the previous line for each stroke based on the determination of the continuity of the strokes.

If we roughly scan the vertical sub-patterns, we will see 7 from line 71.
Only the change point of stroke 1 is detected up to the line one line before the second line.

In scanning 72 lines, the number of change points is 4, indicating that a new stroke has appeared. At this time, the change point detected in the previous line (the line one line before line 72) and the scanning line (72
It is possible to detect a set of changing points that satisfy the relational equations (2a) and (2b) and a set of changing points that do not satisfy the relational equations (2a) and (2b), and therefore, the relational equations (2a) and (2b) A new stroke detected in the scanning row that was not detected in the previous row based on the stroke, that is, stroke 2
can be detected. The coordinates of the starting point of this new stroke 2 are determined from the coordinates of the black-white transition point of the starting point and are stored in the VSEG table 22a.

Roughly scanning the vertical subpatterns, we get from line 72 to line 73.
Stroke up to the line one line before the line] and 2 change points are detected.

In scanning 73 lines, there are two change points for stroke 2. At this time, the change point that satisfies relational expressions (2a) and (2b) between the change point detected in the previous row (the line one line before the 73rd row) and the change point detected in the scanning row (73rd row) The set and the set of unsatisfied change points can be detected, and therefore the relational expression (
Based on 2a) and (2b), it is possible to detect the stroke detected in the previous line but not detected (disappeared) in the scanning line, that is, stroke 1. The coordinates of the end point of this disappeared stroke 1 are determined and V
It is saved in the SEG table 22a. The coordinates of the end point are expressed, for example, by the coordinates of the midpoint of the black-white transition point at the end point.

Further scanning of the vertical sub-pattern causes Y4 to start from line 73.
Only the changing point of stroke 2 is detected up to the previous line, and no changing point is detected when scanning the Y4 line. A change point is detected in the previous row (one line before the Y4 row), but no change point is detected in the scan row (Y4 row), so
The end point of the stroke detected in the previous row, that is, the end point of stroke 2, is determined from the change point of the previous row in the VSEG table 22.
Save to a.

Further, as shown in FIG. 4(B), strokes 3 and 4 that overlap in a certain scanning range but overlap in a certain scanning range are detected as a vertical pattern.The strokes 3 and 4 in the illustrated example are from line 71 to line 73. The lines up to the line one line before the line do not overlap, but the lines up to the line one line before the Y3 line and Y4 line overlap.

When the pattern shown in FIG. 4(B) is scanned, the number of change points becomes two in 73 lines. Examining the change points that satisfy the relationship equations (2a) and (2b) between the change point in the scanning row (line 73) and the change point in the previous row (the line one line before row 73),
It can be seen that the change points of different strokes in the previous line satisfy the relational expressions (2a) and (2b) between the change points of the scanning line, and therefore it can be seen that they are continuous.

That is, it can be seen that the strokes detected separately in the previous row overlap in the scanning row. In this case, the earlier detected stroke, stroke 3, has not yet disappeared in the scanning line, and the remaining stroke 4
is assumed to have disappeared in the scanning line, and the coordinates of the end point of stroke 4 are determined from the change point of stroke 4 in the previous line and stored in the VSEG table 22a. As a result, Y3
The change point detected by scanning the rows and below is detected as the change point of stroke 3.

The starting points and end points of the horizontal sub-pattern, right diagonal sub-pattern, and left diagonal sub-pattern are also extracted in the same manner as in the case of the vertical sub-pattern described above.

A line segment connecting the start point and end point of a subpattern is a segment of that subpattern.

Figure 5 shows a segmented ring pattern and Figure 6 shows a segmented ring pattern.
Figures (A) to (D) are explanatory diagrams of detected segments.

As described above, by each extraction means 12a to +2d,
For example, from the ring pattern shown in Fig. 2, a vertical segment (VSEG) v+~V? , horizontal segment (H8EG) h, ~hlo, right diagonal segment (RS
E G ) r + ~ r2 and left diagonal segment (L
SEG) β1-β2 are detected.

In FIG. 6, the directions indicated by solid line and broken line arrows respectively schematically indicate the main scanning direction and sub-scanning direction of the sub-pattern in scanning for extracting segments. As can be seen from these figures, when scanning sequentially in the sub-scanning direction, the end point detected first among the end points of the sub-pattern (
The coordinates of the starting point S of the segment are detected from the changing point of the starting point (starting end point), and the coordinates of the end point E of the segment are detected from the changing point of the endpoint (v! endpoint) detected later among the endpoints of the sub-pattern. In the process of closed-loop segment detection described later,
The coordinates of the starting point and ending point of each of these segments are used as segment information.

Conventional thinning processing does not include branching, intersections,
When extracting a segment with a ring pattern in which straight lines and curved lines join, the shapes of the branches, intersections, and joints are often not faithfully represented in the segment, but are distorted. Ta. However, as is clear from the above explanation, in this embodiment, a sub-pattern is formed by a group of black bits that are continuously detected on a scanning line, and a line segment connecting the starting point and ending point of this sub-pattern is Let be a segment. Therefore, the shapes of branches, intersections, and joints of the original pattern can be expressed in segments more faithfully and without distortion than before.

In addition, in the conventional drawing process that handles figure data that has been made into thin lines and broken lines, the broken lines are cut at branch points, etc., and NWA
There may be cases where a component is divided into multiple segments. As a result, the process of detecting a closed-loop figure having a target shape has become complicated. On the other hand, in this embodiment, a sub-pattern is formed by a group of black bits that are consecutively detected on a scanning line, and a line segment connecting the starting point and ending point of this sub-pattern is defined as a segment. Therefore, the straightness of the straight line portion of the ring pattern can be more faithfully reflected in the segments than before.

Segment Storage Means> FIGS. 7(A) to (D) are diagrams showing an example of a segment table stored in the segment storage means.

The coordinates of the start point and end point of each segment are determined by each extraction means 12.
a to +2d are stored in the tables 22a to 22b, respectively, and are therefore stored for each scanning direction. Along with this, the coordinates of the starting point and ending point of each segment are determined by each extraction means 1.
By 2a~+2d, the place with the origin of the coordinates! In relation to the relationship, for example, as shown in FIG. 7, the starting points are arranged and saved in the order of detection of the starting points, that is, in the order of the starting points closest to the origin.

How far are the coordinates of the start and end points of the segment from the coordinate origin 0? It is better to arrange and save the coordinates of the start point and end point in the order of the start point closest to the origin ○, as well as save the coordinates of the start point and end point in the order of the end point closer to the origin 0. You can also do as follows.
The coordinates of the segments may be arranged in the order of starting points that are farther or closer to the origin 0, or alternatively, the coordinates of the starting and ending points may be saved in order of starting points that are farther or closer to the origin ○.

In this way, by storing the origin in relation to the MK relation and storing each segment by scanning direction, it is possible to limit the segment search range in the closed-loop segment search process described later, thereby reducing the number of segments to be searched. Therefore, it is possible to speed up the search process for closed loop segments.

<Closed Loop Segment Search Means> The closed loop segment search means 14 of this embodiment searches for segments constituting a triangular closed loop in the closed loop segment search process. A process of searching for an intermediate segment that has one endpoint within a neighborhood area of one endpoint, and a neighborhood area that has one endpoint within a neighborhood area of the other endpoint of the searched intermediate segment and the other endpoint of the origin segment. In addition, the closed loop segment search means 14 of this embodiment searches for an end point segment having the other end point within the closed loop segment.
(Natural number 4) For example, in order to search for segments that constitute a rectangular closed loop, there is a process of searching for a starting point segment, and a middle gate segment having one end point within the vicinity of one end point of the searched starting point segment. The search process and the process of searching for the next intermediate segment that has one end point within the vicinity of the other end point of the searched intermediate segment are repeated a predetermined number of times (n-3 times, for example, when n=4, One end point is within the vicinity of the other end point of the intermediate segment searched for a predetermined number of times (n-2), and the process is performed only once) In addition, in the search for segments that constitute this n-gon-shaped closed loop, there is one starting segment, one ending segment, and a total of n- intermediate segments. Two are detected.

As shown in FIG. 1, the closed loop segment retrieval means 14 of this embodiment mainly includes a CPU 14a which controls the above-described closed loop segment retrieval processing, and a search dictionary 14b which stores retrieval information for closed loop retrieval.

The search dictionary 14b stores predetermined search information related to the shape of the closed loop figure to be searched.

FIG. 8 is a diagram showing an example of the description of search information, and is a diagram showing search information of a frame-shaped loop, a trapezoidal loop, and a triangular loop as an example. Further, FIG. 9 is a diagram showing an example of the shape of a closed loop detected using search information.

Figure 9 (A
) is detected using the trapezoidal loop search information, a closed loop with the shape shown in FIG. 9(C) is detected using the trapezoidal loop search information, and a closed loop with the shape shown in FIG. 9(C) is detected using the triangular loop search information. be done. In FIG. 9, a rectangular area indicated by a dotted line indicates an area near the end point of the segment.

The search information is expressed using the following formulas (3) to (5). However, the search information and the method of describing the search information are not limited to those described below.

! L (ρ1, ρ2)=(SEI)Nl −・・
(3) (β 3 , β 4)”Cl-02
[ΔX1Δx2. Δyt, Δy2 ]
" = (SF3)"N2"N3 - (4
) L (β5, β6)'' C3-04[Δx3゜Δx
4. Δya, Δy4] :05-ca
[Δx5゜Δx6. Δy5. Δy6]”
= (SE3)"N4.N5"N6 - (5) Here, β1 to β6 are numerical values to specify the length of the segment, and SEI to SE3 are symbols to specify the type of segment (when specifying a vertical segment is the symbol V, symbol H is used to designate a horizontal segment, symbol R is used to designate a right diagonal segment, and symbol ji is used to designate a left diagonal segment), N1 to N6 are the names given to the segments, 01 to C6 are symbols specifying the start point S or end point E of the segment, and ΔX1 to Δx6 and Δy1
~Δy6 represents a numerical value for specifying a search area (nearby area of an end point of a segment).

Equation (3) represents the process of searching for a segment whose length ρ satisfies 121≦β≦β2 from among the segments specified by the symbol SEI, and giving the name N1 to the searched segment (search process of the origin segment, Figure 10 (A) described below
reference).

Equation (4) calculates the neighborhood area [Δxi, Δx2. End point C within Δy+, Δy2]
1 and the length l is β3≦β≦β4
Search for the segment specified by the symbol SE2, and assign the name N to the searched segment.
2 (intermediate segment search process, see Figures 10 (B) and (C) below), the end point C2 (7)
If the coordinates are XC2 and y coordinate 'FrVc2, the end point C
The area near 2 has an X coordinate of XC2-ΔX1 or more XC2+Δ
X2 or less and y coordinate is VC2-△y1 or more VC
This is a region within a range of 2+Δy2 or less.

Roughly, equation (5) is the end point C of the segment given the name N4.
Neighboring area of 4 [Δx3. Δx4. △y3. [Δx5. Δx6. ΔV5. △y
6] (a segment having the other end point C5 and whose length l satisfies β5≦β≦16 is denoted by the symbol S
Represents the process of searching among the segments specified by E3 and giving the name N6 to the searched segment (v!
In the point segment search process, the area near the end point 04 (XC4, Vca") is X
This is a region where the coordinates are from Xc'a-ΔX3 to Xc4+ to X4 or less, and the y coordinate is from Vca-Δy3 to Vca+Δy4. Similarly, end point C5 (Xcs, Y
The area near es) has an X coordinate of ×(5−ΔX5 or more
5+ΔX6 or less and the y coordinate is '/cfi-Δy
The range is 5 or more yc and +Δy6 or less.

The closed loop segment search means 14 performs the above-mentioned (3) to (5).
) When a starting point segment, intermediate segment, and ending point segment that meet the processing conditions expressed by the expression ) is stored in the closed-loop data memory 24.

FIGS. 10(A) to 10(D) are diagrams showing the flow of closed loop segment search processing. Hereinafter, the flow of the closed-loop search process will be schematically explained using, as an example, a frame-shaped loop search performed using the frame-shaped loop search information shown in FIG. 8. In the following explanation, please refer to the search information shown in FIG. 8 as appropriate.

First, as shown in FIG. 10(A), a segment having a length ρ of 56≦β≦720 is searched among the vertical segments using the search information of the starting point segment, and a name is given to one searched vertical segment. Give W. This name W
, is hereinafter referred to as the starting point segment W.

Next, as shown in FIG. 10(B), using the search information of the intermediate segment, a segment having a starting point S within the vicinity area [8, 8, 8, 8] of the starting point S of the starting point segment W, A segment with length l of 56≦β≦720,
A search is made among the horizontal segments, and a name W2 is given to the searched horizontal segment. The segment given this name W2 will be referred to as an intermediate segment W hereinafter.

Similarly, as shown in FIG. 10(C), the end point S of the intermediate segment W2 is searched using the search information of the next intermediate segment.
A segment having a starting point S within the neighborhood area [8, 8, 8, 8] and having a length l of 56≦β≦720 is searched among the vertical segments, and Give the name W3. This name w3
The segment that has been given is hereinafter referred to as intermediate segment w3.

As shown in the next M2C diagram (D) 1, using the search information of the end point segment, the start point S is within the vicinity area [8, 8, 8, 8] of the end point E of the start point segment w1, and the intermediate segment w3 A segment having an end point E within the neighborhood region [8, 8, 8, 8] of the end point E, and 56≦! ≦720
A segment having a length l is searched among the horizontal segments, and a name w4 is given to the searched horizontal segment.

Then, the searched start point and end point coordinates of W1 to W4 are stored in the closed loop data memory 24.

Note that in the above example, the numerical value specifying the length of the segment and the numerical value specifying the neighboring area are the same for each segment, but they can be set to different values for each segment.

11(A) to (8) are diagrams showing an example of the flow of operation of the closed loop segment search means, and FIG. (B) shows the flow of operations focusing on n-gon closed loop search processing when n≧4.

When the segment extracting means 12 finishes extracting segments for each direction, the closed loop segment retrieval means 14 reads the retrieval information stored in the retrieval dictionary +4b and performs retrieval processing. The search means 14 is one f! When the search process is completed for the same closed-loop search information, the next different closed-loop search information is read and the search process is performed, so the dictionary +4
All f! stored in b! Search processing is sequentially performed for closed-loop search information of the same type or for search information arbitrarily and suitably selected from the closed-loop search information stored in the dictionary 14b.

Hereinafter, in order to deepen the understanding of the present invention, the flow of operations will be explained separately for the case of a closed-loop search process of a diagonal shape and the case of a closed-loop search process of an n-gon shape (n=4).

(Triangular closed loop search process) As shown in FIG. 11(A), when the closed loop segment search means 14 starts the triangular closed loop search process (S100), it searches for search information for closed loop segment search, such as Read the search information for the triangular loop shown in Figure 8 (S102), and roughly search the segment information (start point and end point coordinates of the segment) for the start point segment search.
For example, read from the VSEG table 22a (S+0
4) Determine whether or not the segment information read based on the search information regarding the origin segment satisfies the conditions of the origin segment (S+06). If the conditions are satisfied, the origin segment is detected, and if the conditions are not satisfied, the origin segment is detected. The origin segment will not be detected.

1: When a starting segment is detected Next to 5106, segment information for intermediate segment search is read from the LSEG table 22d (S+0
8) Determine whether the read segment information satisfies the intermediate segment condition based on the search information regarding the intermediate segment (SIIO). If the condition is satisfied, the intermediate segment is detected, and if the condition is not satisfied, the intermediate segment is detected. No intermediate segments will be detected.

1-1: When an intermediate segment is detected Next to 3110, segment information for searching for an end point segment is read from, for example, the R3EG table 22c (SiI2),
It is determined whether the read segment information satisfies the conditions of the end point segment based on the search information regarding the end point segment (SiI2). If the condition is satisfied, the end point segment is detected, and if the condition is not satisfied, the end point segment is detected. It will not be detected.

If an end point segment is detected, the detected start point, intermediate and end point segments are considered to constitute a closed loop, so next to 8114, the start point and end point coordinates of these segments are stored in the closed loop data memory 24.
), In the next iteration, for example, it is determined whether or not the search for the starting segment has been completed based on whether or not all of the segment information of the VSEGy-pull 22a has been read (SI+8), If not all has been read, the search for the starting segment is completed. Since there is no one, the process returns to step 8104. If all have been read, the search for the starting point segment has been completed, and the triangular closed loop search process ends (S+18).

Further, if the end point segment is not detected in 5114, next to 5114, it is determined whether or not the intermediate segment search 1Fr has been completed, for example, based on whether all the segment information in the LS and EG child tables 2a has been read (S+2
0). If the entire segment has not been read, the search for intermediate segments has not been completed, and the process returns to step 8108. If all of the segments have been read, the search for intermediate segments has been completed, so the process of 3118 is performed.

1-2: 5110 when no intermediate segment is detected
If no intermediate segment is detected in step 5110, then in step 8120 it is determined whether the search for the intermediate segment has ended or not, and processing is performed in accordance with the determination result.

2: 3106 when starting segment 1fr is not detected
If the starting point segment is not detected at 5106, then at 8118, it is determined whether the search for the starting point segment has ended or not, and processing is performed according to the result of the determination.

(N-gonal closed loop search process) As shown in FIG. 11(B), when the closed loop segment search means 14 starts the search process for a closed loop with an n-gon shape, for example, n=4 (3200), the closed loop segment search unit 14 starts the closed loop segment search process (3200). For example, the search information for the trapezoidal loop shown in FIG. It is determined whether a starting point segment has been detected based on whether the read segment information satisfies the conditions for a starting point segment (5206).

3: When a starting point segment is detected Next to 5206, initialize i (initial value = 1) (S20
7), reads segment information for intermediate segment N+ search from, for example, the LSEG table 22d (S20
8) If the segment information read based on the search information between the intermediate segment N□ satisfies the intermediate segment condition, it is determined whether the intermediate segment is detected (3210).

3-1: When an intermediate segment is detected Next to 5210, all the predetermined intermediate segments are searched depending on whether all the search information for the n-gonal intermediate segment has been read (whether or not i=n-2). It is determined whether or not (S212
).

If all intermediate segments have not been retrieved, itl is incremented (5214), the segment information of the next intermediate segment is read from, for example, the VSEG table 22a (S2Q8), and the process of 5210 is performed.

If all intermediate segments have been searched, next to 5212, segment information for searching for an end point segment is read from the R5EG table 22c, for example (S21δ), and the segment information read based on the search information between the end point segments is the end point. Whether the segment condition is satisfied or not is determined by 1 to determine whether the end point segment has been detected (52+8).

If an end point segment is detected, the detected start, intermediate, and end point segments are considered to constitute a closed loop, so next to step 8218, ``Save the start point and end point coordinates of these segments in the closed loop data memory 24 522.
0) Then, for example, it is determined whether the search for the starting segment has been completed based on whether all the segment information in the VSEG table 22a has been read (S222).
If the search for the starting segment has not been completed, the process returns to step 5204 to read the remaining segment information. If the search for the starting point segment has been completed, the n-gon closed loop search process is completed (S224).

If the end point segment is not detected at 3218, the search dictionary +4b is reversely traced and the intermediate segment detection loop (5226, 5228, 5230, 5208,
5210, 5212, 5214) 52 to do 8
26(7) Processing is performed.

In step 5226, it is determined whether the search for the intermediate segment Nl has ended (S226). For example, if i=2, V
It is determined whether or not the search for the second intermediate segment N2 has been completed, depending on whether or not all the segment information in the SEG table 22a has been read.

If the search for the intermediate segment N is not completed, the process returns to step 3208 to search for the remaining segment information for the intermediate segment N+.

If the search for the intermediate segment NI has been completed, the intermediate segment N immediately before the intermediate segment Nl (for example, the intermediate segment where i=m), (for example, the intermediate segment where i=m) is searched.
In order to search for the intermediate segment (m-1), i is subtracted by 1 (5228), and then it is determined whether or not i=o (3230).

If i=0, it means that a closed loop figure including the starting point segment related to the search was not detected, so the process of 5222 is performed to search for the next starting point segment and detect the closed loop figure including the next starting point segment. Return to

If i = 0, it is determined whether the search for the previous intermediate segment N (for example, the intermediate segment where i = m-1) has been completed (5226), and processing is performed according to the determination result of 5226. .

3-2: 8210 when intermediate segment is not detected
If no intermediate segment is detected, it is determined whether the search for the intermediate segment is finished based on whether all segment information between the intermediate segment being searched has been read (S226).

After completing the search for the intermediate segment, search dictionary +4
Steps 5228 and 5230 are performed to search for the previous intermediate segment by tracing b backwards.

If the search has not been completed, the process returns to step 3208 to read the remaining segment information in order to search for the intermediate segment.

2: If the starting point segment is not detected If the starting point segment is not detected in 5206, then 8
At step 222, it is determined whether the search for the starting point segment has ended or not, and processing is performed in accordance with the determination result.

This invention is not limited to the embodiments described above; therefore, the configuration, operation, flow of operation, operating conditions, and numerical conditions of each component are merely examples, and therefore, the invention is limited to the embodiments described above. The present invention is not limited to this, and the configuration, operation, flow of operation, operating conditions, and numerical conditions of each component can be changed as desired.

(Effects of the Invention) As is clear from the above description, according to the closed-loop figure detection processing of the present invention, stroke components in each scanning direction are treated as sub-patterns, and line segments connecting the start and end points of these sub-patterns are treated as segments. Since the detection is performed, the shapes of branches, intersections, and joints of the original pattern can be represented in segments more faithfully and without distortion than before. Therefore, since processing for distortion correction is not required and closed loop detection processing can be simplified, the device configuration can be made simpler than before.

Furthermore, since the line segment connecting the start point and end point of the sub-pattern is detected as a segment, the straightness of the M line portion of the original pattern can be more faithfully reflected in the segment than before.

Since the straightness of the follower pattern is better preserved than before, the shape description of loop figures can be more easily performed than before. Furthermore, since straightness is preserved better than before, the search conditions for the closed-loop shape to be detected can be simplified, and the closed-loop figure detection process can therefore be simpler than before.

Roughly speaking, according to the closed-loop figure detection processing of the present invention, by sequentially searching for segments that have endpoints within the vicinity of the endpoints of the searched segments, the starting point segment, intermediate segment, and end point segment constituting a closed loop are sequentially detected. To detect. The process of searching for a segment whose endpoint is within the vicinity of the endpoint of the searched segment is simple, and the process of detecting segments as described above is also simple, making the process of detecting closed-loop shapes simpler than before. speed of detection processing.

[Brief explanation of the drawing]

FIG. 1 is a functional block diagram for explaining the invention in detail; FIG. 2 is a diagram for explaining ring patterns; FIGS. 3(A) to (D) are diagrams for explaining sub-pattern extraction; FIG. (A) to (B) are diagrams for explaining the principle of extraction of the start and end points of subpatterns. Figure 5 is a diagram showing a segmented ring pattern. Figure 6 (A) to (D) is an explanation of segments. Figures 7 (A) to (D) are diagrams used to explain the segment table. Figure 8 is a diagram showing an example of description of search information. Figures 9 (A) to (C) are diagrams used to describe the segment table. 10(A) to 10(D) are diagrams showing an example of the flow of the closed loop segment search process, and FIGS. 11(A) to 11(B) are diagrams showing the operation of the closed loop segment search means. It is a figure showing an example. 0...Sub pattern extraction means Oa・-v sp extraction means Ob・-HS P extraction means Oc...R8P extraction means Od...LSP extraction means 2...Segment extraction means 2a-VSEG extraction means 2b. ...H3EG extraction means 2cmR8EG extraction means 2d-LSEG extraction means 4...Closed segment search means 4a...CPU, +4b-...Search dictionary.

Claims (7)

[Claims] (1) Create an original pattern of a digital signal represented by black bits and white bits by photoelectrically converting and quantizing an information medium containing at least a closed-loop figure, and scan the original pattern in a plurality of predetermined directions. subpattern extracting means for extracting stroke components in each scanning direction as a subpattern; segment extraction means for extracting coordinates of a starting point and a terminal point of the subpattern in the scanning direction at the time of extracting the subpattern; and a starting point of the subpattern. The line segment connecting the sub-pattern and the terminal point is taken as the segment representing the sub-pattern, and in order to sequentially search for the starting point segment, a predetermined number of intermediate segments, and the ending point segment that constitute the closed loop figure from among the segments, the end point of the searched segment is 1. A closed-loop figure detection device comprising: closed-loop segment search means for sequentially searching for segments having endpoints within a neighboring region. (2) The sub-pattern is a stroke component consisting of a pixel group consisting of continuous figure constituent pixels in the scanning direction at the time of sub-pattern extraction, the continuous length l of which is a predetermined length. The closed-loop figure detection device according to claim 1. (3) The sub-pattern has the continuous length l≧Nw
(However, N is a constant and w is the line width in the original pattern)
3. The closed-loop figure detection device according to claim 2, wherein the stroke component is constituted by a group of figure constituent pixels. (4) The segment extraction means scans the subpattern in a direction forming a predetermined angle with the scanning direction during subpattern extraction, and the coordinate position and number of points of change from white bits to black bits obtained for each scanning line; and means for extracting the coordinates of the starting point and the ending point of the sub-pattern based on the coordinate position and the number of points of change from black bits to white bits. Closed-loop figure detection device as described in . (5) The segment extraction means is characterized in that the coordinates of the starting point and ending point of each segment are stored in relation to the positional relationship with the origin of the coordinates and for each scanning direction. 5. The closed-loop figure detection device according to any one of 4 to 5. (6) The closed-loop segment search means includes a process of searching for a starting point segment, a process of searching for an intermediate segment having one end point within a region near one end point of the searched starting point segment, and a process of searching for the found intermediate segment. A method of searching for an end point segment having one end point within a region near the other end point of the starting point segment and having the other end point within a region near the other end point of the starting point segment. The closed-loop figure detection device according to any one of Items 1 to 5. (7) The closed-loop segment search means includes a process of searching for a starting point segment, a process of searching for an intermediate segment having one end point within a region near one end point of the searched starting point segment, and a process of searching for the found intermediate segment. The process of searching for the next intermediate segment that has one end point within the vicinity area of the other end point of is performed a predetermined number of times, and 7. The means for searching for an end point segment having the other end point in a vicinity area of the other end point of the starting point segment. Closed loop figure detection device.