Uncertainty Reduction Paradigm Using Structural Knowledge in Line-Drawing Understanding

1. Image constituent level

The drawing image is segmented into image constituents on the basis of the segmentation algorithm (Kaneko and Wakana 1982). The algorithm scans the image both in horizontal and vertical direction and gives each black pixel the number of succeedingly connected black pixels in respective direction as the value 1JI. According to the value 1JI, the drawing image is segmented into three types.

1. type 1 : 1 :iii 1J1 :iii 50 in vertical, 21 :iii 1JI :iii 50 in horizontal.
2. type 2 : 1:il1J1:il 50 in horizontal, 21:ii1pS50 in vertical.
3. type 3 : 1 :iii 1JI :iii 30 in both direction.

2. Geometrical element level

Segmented image constituents type 1, 2 are interpreted as linear element and type 3 as massive element. Certainty factor is computed for linear element using the common-sense knowledge such that "the line width is uniformly thinw and for massive element "the size is small or it does not contact to a linear element. w (Representation of the knowledge is shown in APPENDIX A. and B.) If the certainty factor is not high, the constituent is re-interpreted as both linear and massive element.

3. Drawing-primitive level

The linear and the massive elements are respectively classifi~d and interpreted as drawing primitives by the heuristic knowledge about their shape and relation.

Interpretation of massive elements

A massive element is interpreted as solid-line element, broken-line element, arrow, character and noise on the basis of the common-sense knowledge shown in APPENDIX C. The certainty factor of four drawing primitives without noise is computed as an example in APPENDIX D.

Interpretation of linear elements

A linear element is interpreted as solid-line element, short line, line in characters and noise. The certainty factor is computed for solid line and line in characters. The short line is merged and noise is removed at the next structural element level.

Modification of the certainty factor

The certainty factor is modified using knowledge about the relationship between drawing-primitives as shown in APPENDIX E.

4. Structural element level

Drawing-primitives are gathered and integrated into structural elements like line, connecting point and character string.

Lines which compose symbols are interpreted as symbol lines, and the remaining lines are interpreted as connecting lines. As task dependent knowledge for symbol is not available at present, symbol recognition is not carried out. At this level, symbol extraction is only done using the following semi-task dependent knowledge: (1) A symbol is almost closed by lines. (2) Lines with arrow do not compose symbols. (3) A symbol includes characters in itself.

B. Interpretation Process

The hierarchical interpretation proceeds from the image constituent level to the symbol level in bottom-up manner, using heuristic knowledge about shape of and relation between the constituents.

Multiple-interpretation is done at three places in Figure 1. 1) The image constituents are interpreted both as linear elements and massive elements. 2) The massive elements are interpreted as solid-line elements, broken-line elements, arrows and characters. 3) The linear elements are interpreted as solid-line elements and characters.

The multiple-interpretation is converged by the hierarchical and context-sensitive interpretation as shown in Figure 2. In this figure, the hyphen in "P-2" is interpreted as solid-line element, broken-line element and character. Character "2", however, has a high certainty factor as character so that the certainty factor of"-" is increased as character. This hierarchical and context-sensitive interpretation has two effects;

1. The certainty factor of constituents with distinct features is increased rapidly. This means that the interpretation of distinct constituent converges faster at a low level.
2. Inversely, the interpretation of ambiguous constituent is postponed until the processing proceeds to a higher level. It is, however, accelerated by the already converged interpretation of distinct constituents.

IV EXPERIMENTS

A. Application of Structure Analysis

An application system has been developed to investigate the validity of structure analysis described in section III. The system can transform the input drawing image into an output drawing image with beautiful sense according to the user specification such as language translation from Japanese to English, or a figure size change leaving the character size unchanged (Ariki and Sakai 1985).

Transformation results are shown in Figure 3 and Figure 4. Figure 3(a) is an input image with low quality due to gaps in solid lines, contact of a character with a line, false appearance of Jines and white noise. The structure analysis described in section III succeeded and the transformed image of Figure 3(b) was generated. Symbol lines and connecting lines are shown by solid Jines and broken lines respectively. In Figure 4, handwritten drawings with a broken line are digitized at low resolution. Structure analysis separated the characters touching Jines and recognized the broken line. In Figure 3 and Figure 4, automatic character recognition and language translation are not implemented at present. They are left to user specification.

B. Evaluation of Knowledge Quality

We briefly investigated the rate of correct interpretation at the drawing-primitive level for 32 line-drawing images with the quality of Figure 3. They are summarized as follows:

1. The rate of correct character interpretation is 98.5%. This is because the common-sense knowledge such that "if characters exist around itself, it may be character." has a high validity for interpretation.
2. Broken-line element is correctly interpreted at rate of 100%. It is concluded that the common-sense knowledge such that "if broken-line element exists around itself, it may be broken-line element." has a strong validity.

1. Arrow is interpreted correctly at rate of 56%. The knowledge about the shape of an arrow does not seem to have strong validity.
2. Solid-line element is interpreted correctly in most cases, but sometimes it is confused with an arrow.

V. CONCLUSION

In this paper, we proposed an uncertainty reduction paradigm based on context-sensitive and hierarchical interpretation for homograph, multiple-interpretation for heuristic knowledge, and finally certainty factor for data ambiguity.

In the paradigm, the interpretation proceeds from the image constituent level to the symbol level in bottom-up manner using common-sense knowledge given as the heuristic description. The common-sense knowledge is used to compute or modify the certainty factor of multiple-interpretation in context-sensitive manner. The hierarchy of constituents and also the hierarchy of knowledge effectively serve to reduce the uncertainty of interpretation at lower level. Remaining problems are summarized as follows:

1. Integration of top-down approach to this paradigm by using task dependent knowledge at the symbol level.
2. Detail evaluation of knowledge quality and automatic int;rease of knowledge quality by inductive reasoning.