JPH0746363B2 - Drawing reader - Google Patents

Description

Description: TECHNICAL FIELD OF THE INVENTION The present invention relates to a drawing reading apparatus for recognizing symbols in drawings.

[Technical background of the invention and its problems] In conventional symbol recognition, first, one or more symbols are cut out by utilizing local characteristics of an input image, position information of lines and figures, and sent to a recognition unit. The procedure was to identify the shape. This method does not cause any problems in rough drawings, that is, in drawings in which the distance between symbols is sufficiently large, but if the symbols are close to each other, symbol detection cannot be performed accurately, resulting in recognition. There is a situation where you cannot do it.

[Object of the Invention] It is an object of the present invention to provide a drawing reading device capable of accurately recognizing a symbol even in a densely drawn drawing or a figure of an arbitrary size.

[Summary of the Invention] Among geometrically classified subfigures such as loops and fills detected from input image data, those which can be combined in terms of distance are first selected, and then these are selected. The symbol symbols in the dictionary are predicted from the partial figure, and symbol candidates are obtained. In the collation with the dictionary, it is verified whether or not the feature description on the predicted model matches the feature of the symbol candidate. If collation is not possible, a symbol candidate with another combination is tried. By repeating such trials, the process of combining partial graphics and the process of recognizing symbols are gradually advanced to complete the process for all symbols. That is, as shown in FIG. 6, the content of the collation result is fed back to the symbol detection for use.

[Advantages of the Invention] According to the present invention, it is possible to perform a dense drawing process in which symbol detection cannot be performed only by the local feature of input image data or the positional information of a figure.

[Embodiment of the Invention] FIG. 1 is a hardware configuration diagram for realizing one embodiment of the present invention. The apparatus includes an input unit 11 such as a facsimile and a drum scanner, a frame memory 12 for storing an input image, an address controller 13 for managing a two-dimensional address of the frame memory, and a line drawing processor 1 for processing an image on the frame memory.
4. A table processing processor 15 for recognizing symbols based on the processing result of the line figure processor, and a storage unit 16 for storing a dictionary and various tables. FIG. 2 shows the entire procedure of the symbol recognition processing in the drawing reading using this apparatus.

(B) "Creation of segment table" For the binary image on the frame memory 12 input from the input unit 11, the line graphic processor 14 creates a segment table which is subjected to graphic processing described below. This segment table is created from the following four steps.

Step1: Detect the connected figure in the input image (thin line image).

Step2: Make a thin line for each connected figure.

Step3: According to the size of the circumscribed rectangle of each connected figure, it is classified into characters and figure areas.

Step4: For each figure area, line segments are traced on the thinned image to create a segment table.

Here, the segment refers to a digital line segment between feature points (branch points, end points) in the thinned image. Also, above St
ep4 is specifically described. Connection information between segments represented by effective graph representation (parent link & child link information) based on the tracking direction of the thinned image, end point coordinates of the segment, number of branches at the end point, segment Information about the shape of the segment such as the length is obtained, and the information is stored in the segment table area of the storage unit 16 via the table processing processor 15.

When the above processing is completed, the table processor 15 detects the sub-symbol which is a constituent element of the symbol from the figure described in the segment.

(B) “Creating a sub-symbol table” In general, symbols in drawings have loops,
It is a necessary condition to include at least one of a branch point, an end point, a fill, and a refraction point. Then, the table processor 15 finds a figure including these five partial features from the segment table and creates a sub-symbol table.

The sub-symbols are, for example, five types of loop sub-symbol 41, short segment (collection of) sub-symbol 42 independent segment sub-symbol 43 (not shown), filled sub-symbol 44 and refraction sub-symbol 45.

FIG. 4 shows an example of three symbols composed of a combination of the above sub-symbols.

(C) "Detection of Symbol Candidates" After creating the sub-symbol table, the table processor 15 detects a sub-symbol that can be combined in terms of distance and executes a symbol recognition processing algorithm. The symbol recognition processing algorithm uses a dictionary for symbols to combine sub-symbols and perform symbol recognition as symbol candidates. If unrecognizable, try a symbol candidate with another combination. While repeating such trials, the symbol recognition process is gradually advanced to complete the process for all symbols.

FIG. 3 is a functional diagram for explaining the function of the symbol recognition algorithm described above. This configuration is a dictionary 31 that describes symbols (in the storage unit 16). A sub-symbol integration function that obtains symbol candidates using a dictionary 32 Work memory that describes the characteristics of detected symbol candidates
33 Matching function of symbol candidate and dictionary 34 It is composed of five functions of a feature extraction routine group 35 for obtaining features necessary for dictionary matching.

The symbols used in the drawings are characterized by including therein one or more of loops, branch points, end points, filled areas, and inflection points. The symbol dictionary 31 describes this partial figure as a book constituent element by the characteristics of the sub-symbols constituting each symbol and the relationship between the sub-symbols.

Specifically, the dictionary 31 is expressed by the following three layers of frames.

F1: Kind (and number) of sub-graphics that make up a symbol ... Describe the kind (and number) of sub-symbols such as loops, endpoints, etc. that make up a symbol in each slot.

F2: Features of sub-symbols ... In a frame that describes the features of sub-symbols that form a symbol, each slot is described in the form of a constraint condition for a variable, such as a loop length of 10 to 50.

F3: Characteristics between sub-symbols (relationship frame) ... In a frame in which a geometrical relationship between sub-symbols forming a symbol is described, each slot has “the relationship between sub-symbol A and sub-symbol B is ~” It is described in the form.

FIG. 5 shows a representation example of symbols in this dictionary. Here, the description contents of the F1 frame are as follows.

Symbol code (symbol name): Assigns variables to each AHS constituent sub-symbol, and assigns the type of the attached sub-symbol (loop, short segment, independent segment, fill, refraction) as the attribute of those variables. Further, in order to express the shape of the sub-symbol, a pointer to the F2 frame is assigned to each variable X1, X2, X3. That is, each slot is represented by three sets of (variable name, subsymbol, type, pointer to F2 frame).

A pointer to the F3 frame that expresses the relationship between each variable (sub-symbol).

In the F2 frame, one type of subsymbol feature and a pointer to the F1 frame are described for each frame, and each feature is represented by four groups (feature name, minimum value, maximum value, penalty). The features used to describe this subsymbol are:
It depends on the type of sub-symbol.

For example, the features used to describe the loop sub-symbols corresponding to the variables X1 and X2 can be the loop length, the number of end points, and the number of constituent segments.

The description content of the F3 frame is a slot describing the feature between the sub-symbol and the pointer P1 to the F1 frame P1 to the pointer P2 to the F2 frame. For example, (TOUCH (X1, X2) NOT): Loops X1 and X2 are separated. (POSITION (X1, X2, X3) KO): The positional relationship between loops X1 and X2 and short segment X3 is expressed as KO (variable).

In FIG. 3, the integration function 32 (1) focuses on one of the (unprocessed) sub-symbols of the sub-symbol table 36 and predicts a symbol having this as a constituent element. Check for integration with the (unprocessed) subsymbols of. FIG. 6 shows an example of a flow chart of the processing.

First, the sub-symbol table 36 is searched, and one of the unprocessed sub-symbols is set as the focused sub-symbol SI, and its data is written in the work memory 33.

Next, the integration function 32 searches the sub-symbol table 36 again, and uses the position information of each sub-symbol Si to obtain the distance di between the target sub-symbol SI and each sub-symbol Si. Where di = max (XIl-Xih, 0) + max (Xil-XIh, 0) + max (YIl-Yih, 0) + max (Yil-YIh, 0) where Xil: minimum X of the circumscribed rectangle of subsymbol Si Coordinates Xih: Maximum X coordinate of circumscribed rectangle of sub symbol Si Yil: Minimum Y coordinate of circumscribed rectangle of sub symbol Si Yih: Defined as maximum Y coordinate of circumscribed rectangle of sub symbol Si. The data of the symbol Si is written in the work memory 33. The Euclidean distance was not adopted in obtaining di here because the accuracy of the distance is not required so much and the multiplication and the square root calculation are avoided in order to reduce the processing amount required for the distance calculation. Further, the threshold value th is empirically determined so that the sub-symbols in one symbol are always integrated.

Hereinafter, a procedure for integrating sub-symbols and detecting symbol candidates will be described.

The integrated function 32 predicts a symbol composed of a sub-symbol group in the work memory 33. That is, the sub-symbol of interest
Dictionary 31 that has the same type of subsymbol characteristics as SI
Search from F2 frame. Then, the corresponding F1 frame is searched from the pointer described in the F2 frame. The figure of this F1 frame is called a prediction symbol.

For example, if the sub-symbol SI of interest is a loop, F1
When the frame is searched, the symbol AHS shown in FIG. 5 is detected as one of the prediction symbols. (Here, the detected predictive symbols are all F1 frames including the target sub-symbol S1.) Next, the integrated function 32 stores the sub-symbol group described in the predictive symbols in the work memory 33. It is determined whether or not the sub-symbol is detected in advance. If all of the prediction symbols correspond to this sub-symbol, a combination of this sub-symbol is created as a symbol candidate. Here, two loops and one short segment are stored in the work memory 33, and all of these sub-symbols are present in the prediction symbol AHS, so a combination of two loops and one short segment is used. Create as a symbol candidate.

On the other hand, if the combination of sub-symbols described in the F1 frame does not exist in the work memory 33, or if the processing of the collating function 34 described later fails, the remaining F1 frames are searched again. If the collation function 34 does not succeed even after all the F1 frames are searched, the remaining F2 frames are searched and the same processing is repeated.

Now, the matching function 34 performs a matching process between the symbol candidate and the predicted symbol (that is, the dictionary), and StepA: each sub-symbol constituting the symbol candidate is a constraint condition described in the F2 frame corresponding to the predicted symbol. Step B: Verify that each sub-symbol satisfies the conditions for the mutual relationship described in the F3 frame of the prediction symbol.

In the verification in step A, it is preferable to evaluate the badness of matching, for example, in the form of adding a penalty, rather than the perfect matching, and tolerate a difference to some extent.

By using the feature extraction function 35 for the verification in step B, the storage capacity of the intermediate storage data such as the segment table 36 and the sub-symbol table 37 can be reduced and the speed of the entire system can be increased. That is, in consideration of the fact that it is enormous in terms of time and storage capacity to obtain information about the conditions in the relational frame in advance for all the segments or sub-symbols, these tables are compared in this embodiment. Only the information that is frequently referred to in the physical relationship frame is stored, and the information that is relatively infrequent is measured again only when the need for collation occurs in Step B. For this reason Step
Corresponding to the condition to be collated in B, for example, the data necessary for the judgment in the sub-symbol table 36 or the segment table 37 refers to these,
For example, find the direction between two points.

 2 Find the position of P3 from P1 and P2.

At two points P1 and P2 for a certain direction ▲ ▼
Seek the direction of.

 Find the number of inflection points in the specified segment.

 Check the connectivity of subsymbols sI and si.

It is determined whether or not the point P is inside a rectangular area.

A feature extraction routine is provided for each
If necessary, the line figure processor 14 is activated to measure directly from the image in the frame memory 12.

(D) “Output of symbol code” If the collation succeeds as described above, the code of the predicted symbol is output to the symbol table 38 as the symbol recognition result.
Then, for the sub-symbols forming the symbol candidate, after setting a flag indicating that they have been deleted or processed from the sub-symbol table 36, a target sub-symbol is newly selected from the unprocessed sub-symbols. The process shown in is repeated.

The present invention has been described by taking the symbol recognition in the drawing reading as an example, but it goes without saying that the symbol is not limited to the symbol but can be applied to the recognition of general figures and characters or various images.

Note that the integration function of the above-described embodiment predicts symbols after integrating the sub-symbol groups. However, the sub-symbols of interest are first predicted, and the sub-symbols that can be set and integrated are obtained. You may

Further, in the above embodiment, the symbol recognition processing is performed after the creation of the sub-symbol table is completed. However, the symbol recognition processing described above may be alternately performed every time the sub-symbol is detected using the segment table. You can also

[Brief description of drawings]

FIG. 1 is a hardware configuration diagram of an embodiment of the present invention, and FIG.
FIG. 4 is a flow chart of an embodiment of the present invention, FIG. 3 is a functional diagram of a table processor, FIG. 4 is a diagram showing an example of partial graphics constituting a symbol, and FIG. 5 is a dictionary of this embodiment. FIG. 6 is a diagram showing an example in which the symbol is expressed, and FIG. 6 is a flowchart for explaining the processing of the integrated function. 11 …… Input section 12 …… Frame memory 13 …… Address controller 14 …… Line drawing processor 15 …… Table processing processor 16 …… Storage section

Claims (1)

[Claims] 1. A storage means for storing a graphic to be read, a partial graphic which is a minimum unit constituting the graphic and is classified according to geometrical features, and a positional relationship of the partial graphic in association with each other. A dividing means for performing line segment tracing of a figure to be read and dividing the figure into partial figures; and a figure having the first partial figure which is one of the partial figures divided by the dividing means as a constituent element A candidate detecting means for detecting as a candidate of a figure to be read from the means, and a figure in which another partial figure which is a constituent element of the candidate of the figure detected by the candidate detecting means exists near the first partial figure is extracted. And a figure whose position of the figure to be read coincides with the figure to be read based on the positional relationship between the figure extracted by the extracting means and the figure stored in the storage means. A drawing reading device comprising a recognition means for outputting the output.