JPH048832B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a circular shape extraction processing method for drawings such as logical circuit diagrams in which geometric shapes and characters exist.

Logic circuit diagrams consist of symbols such as and, nand, or, noah, flip-flop, lines connecting them, explanatory characters or short sentences, etc., and are drawn along predetermined grid axes (grid Such logic circuit diagrams (handwritten on paper) can be read by an automatic reading device such as a facsimile, and the output video signal is analyzed and input to a processing device such as a figure recognition and character recognition computer for automatic circuit design. It is considered. The present invention attempts to recognize some circular figures, that is, to extract circular figures such as those shown in FIG.

The circular shapes in the logic circuit diagram include those that mean reversal as shown in FIG. In the case of FIG. 1a, if the circle figure M does not exist, it is an AND gate, and if it does, it is a NAND gate, so it is important that the figure M is a circle and what kind of surrounding figures it is connected to.
In the present invention, the surrounding figure N of the circular figure M, or the AND symbol in FIG. The objective is to recognize the meaning of the circular shape and to understand the meaning of the circular shape.

To extract circular shapes, an n x n bit (usually 3 x 3 bit) window, which is used in general character and figure recognition, is used (for example, as a known example,
(Described in Publication No. 117527). Figure 2a shows the window W.
shows. During figure recognition, a photoelectric conversion device such as a facsimile machine reads a drawing, stores it in a memory, cuts out a figure to be recognized from the memory, and performs recognition. It shows the address area of a portion, and by moving this window horizontally and vertically (changing the physical address of the window in that way), the entire area of the graphic memory is scanned. Assuming that the figure memory stores a circular figure (shown as an annular body, which also indicates the width of the outline of the circle) as shown in Figure 3a, the memory can be horizontally ,
During vertical scanning, if the window W is not on a graphic, all stored data in W is 0 (0 is a non-graphic part, in this example, it is a white background). When the window W is at the position shown in b, the data stored in the window W becomes as shown in FIG. 3b. Here, 1 indicates a graphic part, in this example a black part. Similarly, if the window W is at positions c, d, and e in FIG. 3a, the data stored in W will be as shown in c, d, and e in the same figure.

Due to the distribution of the white and black binary data within the window W,
You can know the direction of the figure outline. For example, the third
In the case of the binary data distribution in figure b or e, the direction of the outline of the window-opposing part of the figure is the vertical direction, and in the case of c and d, it is in the diagonal direction, more specifically, C is in the 45° direction with respect to the positive X axis of the XY coordinate axes, d is the same 135° direction. In this way, eight directions, ie, up and down V, left and right H, and diagonal D, can be determined using the window W as shown in FIG. 2b.
Once the orientation of each part of a figure contour is known, this provides useful information for figure recognition.

For example, a circular figure has equal vertical, horizontal, and diagonal directions, whereas a rectangle (including squares) as shown in Figure 1g has only vertical and horizontal directions (because it is written on graph paper, ). Therefore, a circle and a rectangle can be distinguished depending on whether or not there is a diagonal component.

However, in logic circuit diagrams, triangles like cd in Figure 1 often appear. This triangle has a diagonal orientation, so a handwritten triangle may be mistaken for a circle. The causes of the misidentification are thought to be as follows.
That is, the triangle in Figure 1c has a vertical direction and a hypotenuse of 30° to the horizontal direction, and the triangle in Figure 1d has a horizontal direction and a hypotenuse of 30° to the vertical direction. . In other words, the hypotenuse is a 30° component. The logic circuit diagram also has symbols such as e and f in Figure 1,
In this case, similar triangles appear in each section as surrounded by dotted lines. By the way, in the direction judgment using the window W, as mentioned above, there are eight kinds of directions: horizontal, vertical, and diagonal directions of 45 degrees, and these do not include the 30 degree diagonal component. Therefore, in 8-direction judgment, the 30° component is quantized into either the 45° component or the horizontal or vertical components, and a quantization error occurs at this time. A circle is also recognized as having horizontal, vertical, and 45° diagonal components equally, so if the 30° diagonal in the triangle above becomes 45° diagonal and vertical due to handwriting Alternatively, if distributed horizontally, the triangle will have components in any direction and will be indistinguishable from a circle.

The present invention aims to improve this point,
It is possible to perform circular recognition by reliably separating symbols with a circular shape that exist in a handwritten logic circuit diagram from other symbols such as triangles, and furthermore, it is possible to determine the meaning of the circular symbol from the positional relationship with the contours of neighboring symbols. This is what I am trying to do.

The present invention automatically reads a drawing in which geometric figures and characters drawn along a lattice axis are present using a conversion device, stores it in a memory, extracts a line figure having a circular shape from the read output, In a circular shape extraction processing method that recognizes the characteristics of a circular shape from the relationship with line shapes in the vicinity of the shape, the central bit is given a weight of 0, and the remaining 8 bits around it are given different weights (≠0). ), and the weighted addition result obtained based on the data pattern appearing in the window is horizontal,
16 types of directions F ₁ including vertical, 30° and 45° diagonal directions,
Prepare windows with different eigenvalues for each of F ₂ ,...F ₁₆ , scan the memory using the 3 x 3 bit window, and calculate horizontal, vertical, 30° and 16 including 45° diagonal direction
The direction of the contour of the figure is determined for each direction of the species, the circle figure is extracted from the distribution state in the direction, and the relationship between the circle figure and the grid points and its information is determined to recognize the character of the circle figure. This is a characteristic feature.
This will be explained below with reference to Examples.

FIG. 4 shows a procedure for identifying 16 directions according to the present invention.
The binary data distribution within the window W is shown in Figure 4 as 1, 2,...1
6, the shape contours are F ₁ , F ₂ ,...
Suppose it has a direction of F ₁₆ . Although these 16 directions divide 360° into 16 parts, they are not evenly divided, but are unevenly divided, with a 30° component and a 45° component, as shown in Figure 5. Even in the case of the 8-way method,
There are various cases in which the binary data bits appearing in the window W are distributed as shown in Fig. 4 1 to 16, but in the 8-way method, by giving ambiguity, some bits are specifically ignored ( (Don't Care), it is summarized in one of eight directions.
In the present invention, these are arranged in 16 directions more faithfully to the original figure contour.

The window W scans the area while shifting one dot at a time, and it is checked at each scanning position which of the 16 directions shown in FIG. 4 the distribution of data bits within the window matches, and a matching pattern is detected. If it does not match with either direction, it is ignored, the window W is shifted to the next scanning position, and the same process is performed.

Each bit of the 3 x 3 bit window W is shown in Fig. 417.
As shown in the figure, different weights 1, 2, 4,
Add 8, 16, 32, 64, 128. The center bit has a weight of 0. Also in Figure 4 1-16 ×
The marked bits or cells are don't care. When weighted like this and multiplied by the data 1 and 0 of each bit to calculate the total sum, the total sums are 214, 146 (150), respectively, as shown in Figure 4, 1, 2, 3, etc.
147 (151), ... are obtained (the numbers in parentheses are when the parts marked with an x are also calculated), and when such a sum is obtained, the direction of the figure outline is F ₁ , F ₂ , F ₃ , ... It is determined that each direction.

If the figure contour is in a direction other than the directions F ₁ -F ₁₆ , the data pattern appearing within the window W will be other than those shown in FIGS. Furthermore, when a circular figure is drawn by hand, it is not a perfect circle, and therefore does not have equal dimensions in all directions. Therefore, a margin is provided for the frequency of appearance of the directions F ₁ , F _{2 ,} . Expressed mathematically, the frequency of appearance of directions F ₁ , F ₂ , ... is expressed as HIST
F ₁ , F ₂ , ..., and the upper and lower limits of each frequency are H ₁
~H ₁₆ , L ₁ ~L ₁₆ (These upper and lower limits are determined based on the size of the figure and the resolution of the device that converts the figure into a binary signal. In other words, the image scanner, facsimile, etc. that reads the drawing If the resolution of the photoelectric conversion device is sufficient to detect line segments,
The appearance frequency of the 16 species will be high, and conversely, if the resolution is poor, the appearance frequency will be low, so change the upper and lower limits set for the appearance frequency according to the resolution) L ₁ HIST F ₁ H ₁ L ₂ HIST F ₂ H ₂ 〓 L ₁₆ HIST F ₁₆ H ₁₆ , then the figure is a circle. Of course, anything that does not satisfy this condition is not a circle. In the case of a triangle, if it is the triangle in Figure 1 c, the direction F ₁ ,
F ₄ , F ₆ , F ₉ , F ₁₂ , F ₁₄ appear more frequently,
There is a high possibility that the upper limit of the above conditions will be exceeded. Also,
The frequency of appearance in other directions is low, and there is a high possibility that the lower limit of the above conditions will not be reached. in general,
In logic circuit diagrams, circular symbols mainly have meaning attached to other symbols. That is, for example, FIG.
The circular symbol M is attached to the AND gate N to form a symbol called NAND gate. In this case, the circular symbol M means the inversion of the signal. Therefore, to understand the meaning of a circle, it is essential to check nearby symbols. In the present invention, the logic circuit diagram is drawn on the grid axis, and there are restrictions on the position of the circular figure. That is, in the case of a NAND gate, the lattice points + are located on the left and right sides of the circular figure _M1 as shown in FIG. _{6 M1} , or the lattice points + are located above and below the circular figure _M1 as shown in M2. For each grid point, a memory area (32-bit memory area in this example) for storing data such as connection information with the upper, lower, left, and right grid points is secured, and in the example shown in Fig. 6, a semicircular 10 analysis (this is done by projecting vertically and horizontally as shown by the dotted line)
Since we know that grid point 12 has arms above and below (a line segment extending upward and a line segment extending downward), we write Write “1” (present). This "column for circular existence possibility" means "column for presence/absence of reverse logic symbols." If this exists, the probability that the figure is a NAND gate increases, and if there is information such as a line segment to the left of the lattice points 14 and 16, it is determined that the figure is a NAND gate. If the NAND gate is oriented vertically, a shape _M2 is detected, and the shape M2 has arms on the left and right (a line segment extending to the left and a line segment extending to the right) at its upper grid point 17 or lower grid point 18. If so, "1" (presence) is written in the circular existence possibility column (inverse logic symbol presence/absence column) in the information storage memory area of that lattice point in the same manner as above. In the case of a page connector, a circle is drawn to surround the grid points, and there are no grid points on the circumference. In this case, information indicating the existence of a circular figure is added to the information column of the grid point at the center of the circle.

FIG. 7 is a flowchart showing the outline of the above-mentioned circular figure extraction and recognition process. The image input device in this figure is, for example, a facsimile, and if the object to be recognized is a circular figure, the square area is a scanning area that includes the circular figure. The directional table is a list of how the 16 directions F ₁ to _{F 16} appear for circles, triangles, squares, etc. The 4-way code table is a list of the connection statuses of each grid point in four directions, vertically, horizontally, and horizontally. The overall processing procedure is as described above.

According to the present invention, it is possible to correctly recognize a circular figure in a logic circuit diagram without confusing it with a triangle, etc., and it is possible to reliably distinguish between an AND gate and a NAND gate.

In addition, in the present invention, each value HIST of the histogram
Because shapes are extracted using F ₁ , F ₂ , ... independently, shapes can be extracted with simpler processing compared to methods that use the relative distribution state of the histogram (such as peaks and valleys, or the difference between them). Extraction can be achieved.

[Brief explanation of drawings]

Figure 1 is an explanatory diagram showing examples of geometric figures, Figure 2 is an explanatory diagram showing examples of geometric figures.
The figure is an explanatory diagram of the direction recognized as the scanning window, Fig. 3 is an explanatory diagram of the scanning situation, Fig. 4 is an explanatory diagram of the 16-direction indexing procedure, Fig. 5 is an explanatory diagram of the 16-direction, and Fig. 6 is an explanatory diagram of the direction recognized as the scanning window. is an explanatory diagram of the relationship between figures and grid points, and FIG. 7 is a flowchart of circle figure extraction and recognition processing. In the drawing, M is a circular shape, W is a window, F ₁ to _{F 16} are 16 directions,
+ marks indicate grid points.

Claims (1)

[Claims] 1. A drawing in which geometric figures and characters drawn along the lattice axis are automatically read by a converter and stored in a memory, and a line figure having a circular shape is obtained from the readout output. In the circular extraction processing method that extracts The weighted addition results obtained based on the data patterns appearing in the window are made to have different eigenvalues for each of the 16 directions F ₁ , F ₂ , ...F ₁₆ including horizontal, vertical, 30° and 45° diagonal directions. A window of 3×3 bits is used to scan the memory, and 16 directions F ₁ , F including horizontal, vertical, 30° and 45° diagonal directions are determined from the data pattern appearing in the window. ₂ ,... F ₁₆ The direction of the figure outline is determined separately, and the direction F ₁ , F ₂ ,...
...A circular shape extraction processing method characterized by extracting circular shapes under the condition that each frequency of appearance of _F16 is within a predetermined range.