JPS6321949B2 - - Google Patents

Description

[Detailed Description of the Invention] (1) Technical Field of the Invention A logic circuit that mixes line figures and characters drawn along a predetermined grid axis is read by an image input device, and a grid unit is extracted from the input image data. The present invention relates to a recognition method for a single gate cell symbol that is compressed and automatically extracted as a lattice point label code indicating the graphical structure in the vicinity of a lattice point.

(2) Prior Art and Problems In the past, line figures from logic circuit drawings were input into computers by manual input using card punches or digitizers. In the case of inputting a single gate cell symbol, the operator finds the single gate cell symbol in the drawing and inputs its position and name code corresponding to that symbol using a card punch or digitizer. However, this method not only takes a lot of time, but also places a heavy burden on the operator.

In order to improve this problem, a method has been proposed in which only line shapes are automatically extracted from handwritten drawings and input into a computer.

Conventionally, as in logic circuit drawings, the term refers to logic notation symbols drawn based on predetermined lattice axes, wiring patterns between logic notation symbols drawn along the lattice axes, and symbol names. Various methods have been considered for automatically extracting the positions and shapes of logical notation symbols from drawings containing mixed characters, but logical notation symbols come in various sizes, and there is a possibility that they may be deformed by handwriting. Because of the high It has disadvantages such as becoming bulky.

In response to this, the present applicant has previously proposed several methods such as "automatic line pattern recognition method" (Japanese Patent Application Laid-Open No. 162059/1982) and "Recognition method for line figures with a circular shape" (Japanese Patent Application Laid-open No. 103074/1983). We are making proposals.

These systems optically read a drawing in which a line pattern and a group of characters drawn, for example, by hand, are present on a grid axis, and then input this input image information in units of small rectangular areas based on the grid, as shown in Figure 2. Information is compressed as a lattice point label code, and this lattice point label code is used to realize processing such as line pattern recognition. The ``line pattern automatic recognition method'' sets the information of 0 bit and 3-15 bits of the 16-bit division of the grid point label code, and the ``line pattern recognition method with a circle'' sets the information in the reverse logic. Tsuku symbol (2φ) is recognized,
Information on the presence or absence of an inverse logic symbol indicating whether or not an inverse logic symbol exists at that lattice point is set in two bits of the lattice point label code. As shown, the 12-15 bits of the grid point label code are 4
In the direction code, at the relevant grid point (a small rectangular area centered on the relevant grid point), the line is up (U), down (D),
Indicates whether you are running left (L) or right (R).
For example, if it starts from the grid point and extends to the right, R=1 and U, D, and L are 0. If it extends vertically, U and D are 1 and L and R are 0. Bits 8-11 indicate the ambiguous direction and are indicated by a "character-like" value of 1. This corresponds to a four-way code, and for example, R=1, but if it is determined from the line width etc. that this is a line element constituting a character, then F _R =1. The 7 bits are a deviation flag. This flag indicates whether a shift exists or not, and the direction of the shift is indicated by 3 to 6 bits. Specifically, if a line segment drawn along the vertical or horizontal lattice axes is not on the line correctly but is shifted above, below, to the left, or to the right, the misalignment flag is 1, indicating that it is shifted to the right. Then Z _R =1. This has the purpose of preventing double selection. In other words, the field of view is widened so that the line segment can be detected even if it shifts, so if it shifts to the right, the grid point on the right may appear to shift to the left (even to the center between the grid points). If there is a deviation), double selection will occur, but this is to prevent this. The 0 bit is an ambiguous flag, and if this bit is 1, "1" is set in bits 8-11. Specifically, this indicates that the grid point information is likely to be a character rather than a line segment.

A particular problem when recognizing a single gate cell symbol based on the grid point label code determined in this way is ambiguity evaluation and handling. Hitherto, the present applicant has proposed a "graphic pattern extraction processing method" (Japanese Patent Application Laid-Open No. 117080/1983). This method uses the "four-way code" in the grid point label code obtained as described above to calculate the similarity with dictionary patterns prepared in advance for symbols to be recognized and classified. It recognizes and classifies objects that exceed a certain threshold as symbols. The dictionary pattern specifies "0000 ” to “1111” are prepared, and as an evaluation of ambiguity, the “should be” is given a weight of “1” and the “should not be” is given a weight of “1”.
is expressed as a weight of "-1", and "a state that is different from the desired state but is acceptable" is expressed as a weight of "0".
Then, in calculating the similarity, this dictionary pattern is compared with the "four-way code" of the grid point label code, and the weights of the matches are aggregated and calculated as the similarity. Symbols are allowed and recognized and classified as symbols. However, even in this case, there is a trade-off between absorbing handwritten distortions and ambiguities and capturing subtle differences between symbols, and the techniques described above cannot be used for classifying single gate cell symbols. However, in the end, it has not reached the point where it can recognize individual symbols.

Next, the above-mentioned "figure pattern extraction processing method"
(Japanese Unexamined Patent Publication No. 58-117080), a symbol classification table is created using techniques such as "pattern matching method" (Japanese Unexamined Patent Publication No. 58-161088). The basic idea of these technologies is the same: create and prepare as many symbol classification dictionaries as the number of symbols to be classified according to the single gate cell symbol to be classified, and use the lattice extracted from the input drawing to A single gate cell symbol is classified by calculating the similarity between the four-way code of the point label code and the contents described in the dictionary pattern for symbol classification, and a symbol classification table is created.

The similarity calculation starts from the grid point in the upper left corner (address is (1, 1)), and first starts from the grid point position (1, 1) in the upper left corner to the dictionary described in the dictionary pattern for symbol classification. The degree of similarity between the grid point label code and the four-way code within the range of the corresponding symbol size is calculated. If this degree of similarity is high, i in the symbol classification table shown in FIG.
1, 1 is stored in the j column, and the symbol number of the classification group corresponding to the dictionary is stored in the NO column. If the degree of similarity is low, a degree of similarity calculation is performed with the next dictionary (dictionary pattern for another classification group). That is, matching (similarity calculation) with all symbol classification dictionary patterns is performed until a pattern with a high degree of similarity appears for one grid point. When the similarity calculation for the grid point address (1, 1) is completed, the next grid point address (2,
Moving on to step 1), a similarity calculation is performed, and if there is a symbol with a high degree of similarity, the address and classification group number of the symbol are similarly stored in the symbol classification table. In this way, similarity calculations are performed on all grid points to create a symbol classification table.

(3) Purpose of the Invention The purpose of the present invention is to provide a single gate cell symbol that can be recognized with high precision in a simple procedure based on the information of the lattice point label code that indicates the graphic structure in the vicinity of the lattice points in lattice units from input image data. The objective is to provide a recognition method for

(4) Structure of the invention In order to achieve the above object, in the present invention,
A logic circuit drawing in which line figures and characters drawn along predetermined grid axes are mixed is read by an image input device, and from the input image data, the graphic structure in the vicinity of the grid points in grid units, that is, each grid In this method, a four-way code indicating the direction of a line segment at a point and a lattice point label code expressing the presence/absence information of an inverse logic symbol are obtained, and a single gate cell symbol is recognized based on this lattice point label code. A dictionary pattern for symbol classification that groups similar symbols among power single gate cell symbols and stores a dictionary pattern for symbol classification that describes the shape, etc. within a small rectangular area that constitutes the symbol for each classification group. storage means;
symbol classification extraction for classifying and extracting single gate cell symbols into classification groups by matching the symbol classification dictionary pattern stored in the symbol classification dictionary pattern storage means with the four-way code of the lattice point label code; means, a symbol candidate table storage means for storing a symbol candidate table that describes the correspondence between a classification group of single gate cell symbols and each single gate cell symbol belonging to the group, and each single gate to be recognized. A symbol dictionary storage means stores a symbol dictionary that describes the shape of the terminal position of a cell symbol and information on the presence or absence of an inverse logic symbol, and symbol candidates are extracted from information on the classification groups of symbols classified and extracted by the symbol classification extraction means. The symbol recognition dictionary of the single gate cell symbol belonging to the classification group is retrieved by referring to the symbol candidate table stored in the table storage means, and the four-way code of the lattice point label code and the presence/absence information of the inverse logic symbol are extracted. , and means for recognizing a single gate cell symbol by performing matching with the symbol recognition dictionary.

(5) Embodiments of the Invention Figures 1a-c and 2 show a single gate cell symbol and a grid point label code, respectively, applicable to the present invention.

Figures 1a-c show two examples each of single gate cell symbols in logic circuit diagrams. The figure a shows a gate with 3 inputs and 2 outputs, the figure b shows a gate with 3 inputs and 1 output, and the figure c shows a gate with 1 input and 1 output. In each of the two examples, one phase of the input or output is inverted. .

These single gate cell symbols are based on the above-mentioned proposed example ``line pattern automatic recognition method'' (Japanese Patent Application Laid-Open No.
162059) and "Method for Recognizing Line Figures Having Circular Shapes" (Japanese Unexamined Patent Publication No. 103074/1983), graphic information in the vicinity of lattice points is compressed and expressed in small rectangular area units based on the lattice. FIG. 2 shows the lattice point label code of the present invention, in which the types and positions of the ambiguous flag, deviation direction, deviation flag, ambiguous direction, and 4-way code are as proposed above, and the inverse logic symbol ( A bit is added to indicate the presence or absence of 2φ).

FIGS. 3, 4a to 4d, and 5a to 5g are diagrams for explaining the outline and principle of the present invention.

The present invention provides a second image data extracted from input image data.
Applies to the grid point label code in the figure. First, for example, by using the method of "Graphic Pattern Extraction Processing Method" (Japanese Patent Application Laid-open No. 117080/1982), the four-way code of the obtained lattice point label code and the single gate cell symbol to be classified in advance are matched. The symbol classification table shown in FIG. 3 is created by calculating the degree of similarity with the symbol classification dictionary pattern prepared by the above method.

Figure 3a shows the contents of this single gate cell symbol classification table, where (i, j) is, for example,
These are the lattice point coordinates of representative points in the case of NAND circuits set in each direction as shown in Figure 4 a to d, and NO indicates the classification number of the classification group of a single gate cell symbol. For example, Figure 1 a, b , c are classified according to the number of inputs and outputs, as shown in the two examples. Also,
SDRCT indicates the direction of a single gate cell symbol, for example, as shown in Figure 4 a to d.
= 0 to 3. As described later, when recognition is completed by the processing of the present invention, the recognition number of a single gate cell symbol (a number that corresponds one-to-one with each single gate cell symbol) is , and FLAG is set when it is determined that it is not a single gate cell symbol. Furthermore, TOTAL indicates the number of classification groups of single gate cell symbols that have been classified and extracted.

5a to 5g show the processing procedure and dictionary structure for recognizing individual single gate cell symbols from the single gate cell symbols classified and extracted as classification number NO in the symbol classification table of FIG. 3.

Each processing procedure is shown below.

(1) Search symbol classification table.

Grid point coordinates (i, j) and classification numbers stored in the symbol classification table in Figure 3
NO, take out the direction SDRCT one by one. Here, (i _s , j _s ) as grid point coordinates is a classification group containing a single gate cell symbol shown in FIG. 5a as a classification number, that is, NO=13
However, it is assumed that 0 is extracted as SDRCT.

(2) Search candidate symbol table.

As shown in Figure 5b, for each classification number of a classification group of single gate cell symbols, the number of the single gate cell symbol belonging to that group (candidate symbol number), and the single gate cell symbol belonging to that classification group. A candidate symbol table describing the number of symbols (number of candidate symbols) is prepared in advance. For example, for a classification group (classification number 13) that includes a single gate cell symbol with 3 inputs and 2 outputs as shown in FIG. The candidate symbol table for is shown.

(3) Symbol recognition dictionary and conversion.

As a symbol recognition dictionary, Figure 5 c, d, e
A symbol recognition dictionary corresponding to a single gate cell symbol (candidate symbol number) to be finally recognized is prepared as shown in FIG. Figure 5c,
d and e are candidate symbol number 13 of classification number 13,
14 and 15 symbol recognition dictionaries are shown. Each corresponds to each grid point address (expressed as a relative address from the representative point of the grid point coordinates shown in FIG. 4) of the single gate cell symbol shown on the left side of the symbol recognition dictionary (i, j). and the shape of the four-way code of the lattice point label code that will be extracted at that position and the bit information ST indicating the presence or absence of the inverse logic symbol. Furthermore, the * mark on the outside of the margin is information indicating that the state ST should not apply to that grid point address. The left side of the lower end shows the size of the dictionary, and the right end shows the inverse logic symbol (2φ), that is, the number of inverted phases.

In matching the symbol recognition dictionary and the grid point label code, which will be described next, it is necessary to convert the symbol recognition dictionary according to the direction SDRCT taken out from the symbol classification table. In other words, (i, j) and ST in the symbol recognition dictionary are represented by (0,
0), the relative grid address is shown.
When SDRCT=1 to 3, the contents of the symbol recognition dictionary must be converted in consideration of this fact. Since this transformation is a simple geometric coordinate transformation, we will omit the details and use
The case where SDRCT=0 will be explained.

(4) Matching between symbol recognition dictionary and grid point label code.

The relative grid point address (i, j) and state ST described in the symbol recognition dictionary and the grid point label code (2φ,
4-way code) (similarity calculation)
The results are stored in the recognition buffer shown in FIG. 5g.

For matching, grid point coordinates (i,
By adding j) to the relative grid address (i, j) written in the symbol recognition dictionary, the address of the grid point label code to be actually matched can be extracted. For example, as shown in FIG. The grid point label code of the grid point address (i, j) of each symbol recognition dictionary 13, 14, 15 is obtained by adding the grid point coordinates (i _s , j _s ) from which the classification group shown in a is extracted to (i, j) of each symbol recognition dictionary 13, 14, 15. 2φ, 4-way code) and the state ST described in the symbol recognition dictionary.

Column A of the recognition buffer shown in Figure 5g is 4.
The degree of coincidence of direction codes, column B is the phase (2φ)
The column C shows the degree of coincidence of the inverted phase from the state of the phase (2φ) described in the dictionary.

(5) Judgment.

(i) If A+B is a full score, that is, twice the size of A+B and the dictionary described in the symbol recognition dictionary, that candidate symbol becomes the recognition result. This corresponds to the first candidate symbol number of the recognition buffer in g of the same figure. and
Enter that symbol number 13 in SNO.

(ii) If there is no case where A+B is a full score, C is a full score, that is, the maximum score among those that match the number of phases (2φ) described in the symbol recognition dictionary and are larger than a certain threshold for A+B. The recognition result is the one with . Then enter that symbol number in SNO.

(iii) If neither (i) nor (ii) applies, a threshold is set for A+B+C, and the largest one that is greater than or equal to that value is taken as the recognition result.
Then enter that symbol number in SNO.

(iv) If there is nothing that falls under (i) to (iii), it is determined that it is not a symbol, and "1" is set in the FLAG column of the symbol classification table.

As described above, a single gate cell symbol can be recognized in a very simple form by performing the two-step process of classification and recognition based on the grid point label code extracted from the input drawing data. It is possible to achieve recognition using simple features compared to the case of applying conventional techniques, and since similarity calculation is used for matching, it is possible to sufficiently absorb deformations caused by handwriting.

FIGS. 6a and 6b are explanatory diagrams of the configuration of an embodiment of the present invention according to the above-mentioned principle.

The figure shows the main parts of the example circuits in the above-mentioned proposed examples "Line pattern automatic recognition method" (Japanese Patent Application Laid-Open No. 57-162059) and "Recognition method for line figures with circular shapes" (Japanese Patent Application Laid-Open No. 58-103074). Using Matching (similarity calculation) is performed between the lattice point label code and the dictionary memory, and the present invention is applied to the result.

In Figure a, the handwritten drawing is on the image input device 1.
The image data is read and stored in the image memory 2.

The input state of the reference point is detected from this image data by the reference point detection circuit 4, and the address of each grid point corrected based on the input distortion is held in the grid point table 5.

Next, the control unit 11 reads out the screen memory 2 in a 2×2 verification window with the size between the grid axes based on the address obtained from the grid point table 5, and uses the grid conversion circuit (horizontal) 6 and the grid conversion circuit (horizontal) The resulting data is transferred to the circuit (vertical) 8 and processed in the grid point label code generation circuit (horizontal) 7 and the grid point label code generation circuit (vertical) 9 to extract the initial grid point label code LBL. .
This is then stored in the LBL table 13.

Depending on this initial grid point label code LBL,
A first verification window of a predetermined size is set by the verification window setting circuit 12, and using this, the verification circuit 3 performs the first verification process. The first verification deviation information SX1, SY1 obtained as a result is stored in the SX1/SY1 table 16.

First verification deviation information obtained in this way
After the lattice point address of the lattice point table 5 is shifted and normalized by the address conversion circuit 18 based on SX1 and SY1, the lattice conversion circuit (horizontal) 6 and the lattice conversion circuit (vertical) 8 and the lattice point label are The first verification label code is generated by the code generation circuit (horizontal) 7 and the grid point label code generation circuit (vertical) 9.
Find LB1 and enter it in the LB1 table 14. Based on this LB1, a second verification window of a predetermined size is set by the verification window setting circuit 12,
Using this, the verification circuit 3 performs a second verification process. The second verification deviation information SX2 obtained as a result,
Store SY2 in the SX2/SY2 table 17.

Second verification deviation information obtained in this way
After the lattice point address obtained from the lattice point table 5 is shifted and normalized by the address conversion circuit 18 using SX2 and SY2, the second verification label code LB2 is obtained in the same manner as described above, and this is converted into the LB2 table 1.
Store in 5.

Next, in order to investigate the detailed figure state in the vicinity of the grid points, a third verification window is set in the verification window setting circuit 12, and processing is performed by the verification circuit 3 in the same manner as in the case of the first and second verification windows described above. . The data obtained as a result is sent to the LB3 generation circuit 19 to obtain a third verification label code LB3, which is stored in the LB3 table 20.

Then, the third verification label code LB3 from the LB3 table 20, the initial grid point label code LBL from the LBL table 13, the first verification label code LB1 from the LB1 table 14, and the LB2 table 15.
Second verification label code LB2 from SX1/SY1 First verification deviation information SX1, SY1 from table 16
The grid point label code determining circuit 21 repairs and corrects the second verification deviation information SX2, SY2, etc. from the SX2/SY2 table 17. The resulting grid point label code LABEL is stored in the label table 22.

For the lattice point label codes from the label code table 22, a pair processing circuit 23 performs processing to remove those in which the relationship between lattice points is not a pair, and a line pattern breakage correction circuit 24 corrects line pattern breaks. and character removal circuit ()25
The relation between the grid points that indicates character characteristics is removed by the following method, and the next deviation correction circuit ( ) 26 corrects the deviation direction even if the deviation flag of the grid point label code at that grid point is "1". Both the grid point deviation flag and ambiguity flag are “0”
If so, the initial grid point shift flag is set to "0". Furthermore, even if the ambiguity flag of the lattice point label code at that lattice point is “1” in the ambiguity correction circuit ( ) 27, at least two of the four directions are “1” indicating an ambiguous direction, and the ambiguous direction If both the deviation flag and ambiguity flag of the grid point facing the grid point are "0", the ambiguity flag of the original grid point is dropped to "0".

In the proposed example below, procedures such as character removal, misalignment correction, ambiguity correction, etc. are further repeated, but these are omitted in the present invention. Then, it is corrected by the above-mentioned correction circuits 23-27 in the label table 22 and sent to the similarity calculation circuit 29, while the dictionary pattern for symbol classification from the dictionary memory 28 is inputted for each classification group of single gate cell symbols. A symbol classification table 30 is created by performing matching (similarity calculation). In this way, in the symbol classification table 30, for each classification group of each symbol, its position (i _s , j _s ), classification number NO, and direction are stored, for example, based on the characteristics of 3 inputs and 2 outputs.
SDRCT is stored.

Next, the grid point coordinates (i _s , j _s ), classification number NO, and direction stored in the symbol classification table 30 are determined by the processing described in FIGS.
The SDRCT is read out, the symbol candidate table 31 is searched based on the classification number NO, and the candidate symbol number is extracted. Next, the symbol recognition dictionary 32 corresponding to the retrieved candidate symbol number is read out, the symbol dictionary conversion circuit 33 converts the symbol dictionary according to the direction SDRCT, and then the symbol dictionary is inputted to the matching circuit 34 and converted into a label table. Matching is performed with the lattice point label code from No. 22, and the degree of matching shown in FIG. 5g is evaluated. This is repeated as many times as there are classification groups of single gate cell symbols stored in the symbol classification table 30, and the recognized symbols are sequentially stored in the symbol recognition table 35.

(6) Effects of the Invention As explained above, according to the present invention, the grid point label code is first extracted based on the grid point label code indicating the graphical structure in the vicinity of the grid point extracted from the input image data in grid units. The four-way code and the four-way code to be extracted within each small rectangular area (rectangular area based on the grid point used for extracting the grid point label code) constituting the symbol to be classified are described above. A single gate cell symbol is classified by matching with the dictionary pattern for symbol classification, and then the four-way code of the grid point label code and information on the presence or absence of an inverse logic symbol (2φ) are used.
A two-step processing procedure is used to recognize each single gate cell symbol by matching the shape of the terminal part of the single gate cell symbol in four directions with a symbol recognition dictionary that describes the presence or absence of an inverse logic symbol. Furthermore, since the matching uses similarity calculation to absorb handwritten deformations, highly accurate single gate cell symbol recognition can be achieved with a simple procedure using only simple features.

[Brief explanation of drawings]

1a-c and 2 are a single gate cell symbol and a grid point label code applied to the present invention, respectively, and FIGS. 3, 4 a-d, and 5 a-g are schematic diagrams of the present invention. 6A and 6B are explanatory diagrams of the configuration of an embodiment of the present invention, in which 1 is an image input device, 2 is an image memory, 3 is a verification circuit, 4 is a reference point detection circuit, and 5 is a diagram explaining the principle. is a lattice point table, 6 is a lattice conversion circuit (horizontal), 7 is a lattice point label code generation circuit (horizontal), 8 is a lattice conversion circuit (vertical), 9 is a lattice point label code generation circuit (vertical), 10 is an address Control unit, 11 is a control unit, 12 is a verification window setting circuit, 13 is an LBL table, 14 is an LB1 table, 15 is an LB2 table, 16 is a SX1, SY1 table, 17 is a SX2, SY2 table, 18 is an address conversion circuit, 19 is LB3 generation circuit, 20 is LB3
Table 21 is a grid point label code determination circuit;
22 is a label table, 23 is a pair processing circuit, 24
25 is a line pattern breakage correction circuit, 25 is a character removal circuit (), 26 is a deviation correction circuit (), 27 is an ambiguity correction circuit (), 28 is a dictionary memory, 29 is a similarity calculation circuit, 30 is a symbol classification table, 3
1 is a symbol candidate table, 32 is a symbol recognition dictionary, 33 is a symbol recognition dictionary conversion circuit, 34 is a matching circuit, and 35 is a symbol recognition table.

Claims (1)

[Claims] 1. A logic circuit drawing in which line figures and characters are mixed drawn along predetermined grid axes is read by an image input device, and from the input image data, information in the vicinity of the grid points is determined in grid units from the input image data. The graphic structure, that is, the four-way code indicating the direction of the line segment at each grid point, and the grid point label code that expresses the presence/absence information of the inverse logic symbol are obtained, and a single gate cell symbol is created based on this grid point label code. In the recognition method, among the single gate cell symbols to be recognized, similar symbols are grouped, and a dictionary pattern for symbol classification is created that describes the shape, etc. within the small rectangular area that constitutes the symbol for each classification group. A symbol classification dictionary pattern storage means to be stored; and a symbol classification dictionary pattern stored in the symbol classification dictionary pattern storage means is matched with the four-way code of the lattice point label code to form a single gate cell symbol. Symbol classification extraction means for classifying and extracting into classification groups, and symbol candidate table storage for storing a symbol candidate table that describes the correspondence between classification groups of single gate cell symbols and individual single gate cell symbols belonging to that group. symbol dictionary storage means for storing a symbol dictionary that describes the shape of the terminal position of each single gate cell symbol to be recognized and information on the presence or absence of an inverse logic symbol; The symbol recognition dictionary of the single gate cell symbol belonging to the classification group is retrieved from the information on the classification group of the symbol by referring to the symbol candidate table stored in the symbol candidate table storage means. 1. A method for recognizing a single gate cell symbol, comprising means for matching a direction code and information on the presence or absence of an inverse logic symbol with the symbol recognition dictionary to recognize a single gate cell symbol.