JPS5840782B2 - Graphic processing method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention utilizes a graphic processing method, particularly graphic processing, to convert an input graphic that has undergone preprocessing into a multivalued grayscale image through appropriate operations such as thinning, thickening, and labeling. The present invention relates to a graphic processing method that performs identification by applying an image processing method to a graphic that has been converted into a multivalued image.

The term "graphics" to be subjected to graphical processing herein refers to line figures that have a structure in a broad sense, and refers to a group of line figures that have several or many categories to be identified.

In the following, the conventional technology will be explained specifically by limiting the target to characters and graphics.

An excellent explanation of the current state of OCR technology can be found in, for example, Shunji Mori: ``Research on Character Recognition Technology,'' Large Project Pattern Information Processing System Lecture Proceedings, July 7th and 8th, 1977, pp. 7-32.

As stated there, "superposition" is the basic principle of character recognition technology, and one method is template matching, which is top-down and suitable for printed character recognition.
It is broadly divided into structural analysis methods that are ottom-up and suitable for handwritten character recognition.

There are prospects for practical use of OCR for printed characters and some handwritten characters (alphanumeric characters and kana) (for example, see the collection of papers listed above).

Currently, the biggest challenge is handwritten kanji OCR.

In addition to a variety of handwritten deformations, handwritten kanji have a complex graphical structure and a large number of categories.

When relying on the structural analysis method to identify such complex handwritten line figures 1. The contour analysis method is a serial process and is fatal to line breakage and contact, while the background analysis method can capture the global characteristics of the contour. , so to speak, is too rough, so the conventional mainstream position has been to adopt the line analysis method.

In the line analysis method, the input character figure is first binarized and thinned to eliminate the influence of the line width of the input character figure (for example, Mincho font), and then features are extracted from the obtained heart line figure.

There are two methods: one that sequentially extracts single character lines, and another that focuses on the end points and branching points of single character lines (for the former, see Iwata: ``Automatic recognition of handwritten kanji'', 51st Radio Research Institute Proceedings of the presentation, 1976, pp. 62-71, for the latter, Hiratsuka Ogawa: “Handwritten kanji reading system with a correct reading rate of over 95%” Nikkei Electronics, 197
August 12, 4th issue.

(pp. 82-119).

However, it has the following drawbacks, and the solution is still unclear.

That is, (2) the "whiskers" and "v-+Y" phenomena in the thinning process cannot be dealt with by local processing.

■It is difficult to judge the inclination and linearity of the core wire.

■There is no effective general classification method because lines are traced microscopically and features are extracted from the bottom up.

■Vulnerable to wire breakage and contact. The above-mentioned drawbacks ■～■ arise when attempting to recognize the recognition target by applying the line analysis method from the standpoint of structural analysis when the recognition target is not only characters and figures such as handwritten kanji, but generally a group of line figures that have a structure. This is an essential difficulty.

In order to solve these drawbacks, the present invention converts a binarized input figure into a multivalued gray image that reflects its geometric and topological characteristics, and then performs identification using an image processing method. This is an attempt to change the way of thinking, and in order to ignore the influence of the line width of the input character shape, it performs core line (thinning) and then thickens it, which may cause the influence of whiskers etc. in some cases. It is an object of the present invention to provide a figure processing method that is stable even against handwritten deformation of input figures by creating a multivalued grayscale image in a form that can suppress the image processing, and is characterized in that large classification can be easily incorporated into the processing method. It is said that

In the case of the present invention, a figure processing method A is used that preprocesses an input figure and converts it into a multivalued image that reflects its structure, and figure identification is performed on the input figure converted into an image based on an image processing method. It has a two-stage structure with graphic processing method B up to the point where it is executed.

As mentioned above, the objects of the present invention are general collections of line figures that have a structure and are composed of various categories.

Here, we specifically consider handwritten characters, especially handwritten kanji, but it goes without saying that it can be widely applied as described above.

Explain in the following order (A) and (B). I will clarify.

Processing (A) When the input figure is subjected to preprocessing such as noise division, normalization of size and position, and binarization, a binary figure as shown in FIG. 1 is obtained.

Next, this binary figure is subjected to line thinning processing, the line width is normalized to "l", and a label 0 is attached to the center line portion, resulting in a figure as shown in FIG.

The obtained core wire (area labeled 0) is used as a core and thickened.

Each time the thickening process is executed for 1 5 steps (thickening the line width by rlJ), the resulting area is expanded by 1°2.3. . . . and sequentially label them.

The situation is shown in Figure 3.

The thickening process and labeling work are completed when labels have been applied to all the white parts that are the figure backgrounds (see FIG. 4).

Label 0,1゜2.3. In a screen filled with ..., a function f(k) for the label value (f is a monotonically non-decreasing function, for example, f(k) = k.

By assigning r(k)=k, f(k)=exl to that point (pixel) as a gradation level, the original input figure is converted into a multivalued gradation image.

Note that selecting a function form other than f(b)- corresponds to appropriate weighting.

First, it will be explained that the multivalued gray image obtained by the procedure described above faithfully reflects the structure of the input figure.

Eleventh, the core line portion (area labeled 0) obtained through the thinning process is the geometric feature of the input figure itself.

The line thinning process here is just a means to standardize the line width to "l" and quantify the number of lines included in the input figure and the complexity of the figure as a whole. It should be noted that since this is not a preprocessing for extracting a structure, there is no need to be concerned about the "V→Y" phenomenon.

Second, labeling of the graphic background using thickening processing is a means for expressing the topological features of the input graphic.

This is because the label value given to each point on the white background is
This is because the distance is from the core portion closest to the white point, and reflects the positional relationship with respect to the core wire portion, that is, the topological characteristics.

Third, by finally converting the label value function f into a multi-valued grayscale image, the geometric and topological features of the original input figure are simultaneously absorbed into the image representation. be done.

For example, this image representation corresponds to a three-dimensional representation of the input figure on a platform that looks at a mountain range with the central line as a ridge.

As is clear from the above, there is an epoch-making change in the idea of the present invention in that the structure of the input figure is reduced to shading levels.

Furthermore, an important feature of this image representation is that it is extremely stable against handwritten deformation.

This is because, if we pay attention to the pixels that consist of pixels, in the case of binary representation, handwritten deformation (the level changes from 0 to 1 or from 1 to 0, with or without F), but in the case of multivalued representation, This is because, even if handwritten deformation occurs, the level value changes only between the light and shade levels close to one line portion.

Processing B: First, the multivalued grayscale image obtained by applying the transformation shown in the above graphic processing method A to the input graphic is roughly classified.

Here, there are two feature quantities used for major classification.

Both use the shapes at the time labeling is completed.

One is to define the number of pixels belonging to the region in the label as Pk,
This is a change pattern depending on the absolute number of Pk and k.

The other one is further labeled 0, 1, 2 . ...The total number of pixels belonging to the k area is defined as Ak (:ΣPi), and the quantity Pk2/Ak is used to evaluate the complexity of the input figure.
(k=0.1.2,...) (This amount is (perimeter) 2
/(area)).

Subsequently, the process moves to identification processing after major classification, that is, identification processing 1 as described later.

First, let's start with the first and second multivalued image representations (NXN pixels).
．． ..., the gray level values of each pixel are read in the order of N rows and read as N two-dimensional vectors.

Each figure obtains an N2-dimensional vector representation whose components are gray levels in image representation.

From a sample set of various N2-dimensional vectors belonging to one figure category consisting of .

The essential point is that various deformations within the same category, especially handwritten deformations, are regarded as a kind of noise.

The eigenvalues and eigenvectors of all figure categories to be recognized are calculated in advance, and when an input N2-dimensional vector of unknown category is given, which eigenvectors are included as principal components is evaluated, and the eigenvectors that contain the most The identification is completed by identifying the figure category represented by the eigenvector.

As is clear from the above, in order to essentially reduce the method to template matching, we focus on the fact that various transformations within the same category exhibit unique behavior for each category. The method is to extract features in the form of eigenvectors using KL transformation.

FIG. 5 shows the configuration of an embodiment of the graphic processing method of the present invention.

Reference numeral 10 in the figure is a line figure input unit, which performs figure scanning using, for example, a flying spot scanner;
11 is a preprocessing unit that performs noise removal, normalization, and binarization, 12 is a thinning processing unit that thins the line width Ill as shown in FIG. 2, and 13 is a thicker line. A processing and labeling processing unit that performs thick processing and labeling as shown in Figs. 3 and 4; 14 is a large classification processing unit; 15 is a dictionary memory for large classification features; 16 is a multi-value processing 1T represents an identification processing section, and 18 represents a dictionary pattern memory.

After passing through the processing section 1011, a binary figure as shown in FIG. 1 is obtained which has undergone preprocessing as is well known.

The two figures are converted by the thinning processing unit 12 into a figure with a line width of "l" as shown in FIG.

The thickening processing and labeling processing unit 13 sequentially performs thickening processing on the figure shown in FIG. 2 by a width corresponding to the line width "l",
Labels are sequentially applied as shown in FIGS. 3 and 4.

As shown in "Processing B" above, the major classification processing unit 14 determines the size of the input figure based on the characteristic quantity, that is, (i) the change pattern depending on the absolute number of Psc and k, or (il) the evaluation quantity Pk2/Ak. Perform classification.

That is, the information (i) or (11) above corresponding to each figure to be recognized is stored in the memory 5.

Then, extract the feature quantity of the input figure to be recognized (f) or (11), compare the feature quantity with the feature quantity sequentially read from the memory 5, and extract the candidate figure to which the input figure belongs. do.

In other words, it is roughly classified. The multivalue processing unit 16 performs the above-mentioned "processing B"
The process of obtaining the N2-dimensional vector shown in is performed.

Then, the identification processing section 17 compares the output from the multi-value processing section 16 with the dictionary pattern read out from the memory 18 corresponding to the figures that have been roughly classified and extracted as candidates.

Note that technical aspects regarding the components 13, 14, and 15 in FIG. 5 will be supplemented below.

■ Regarding the thick processing and labeling processing section 13f.

For distance transformations, 1 e.g. A, Rosenfeld
.

A, C, Kak: Digital Picture Pr
ocessing”, l)p, 352-357゜Aca
There is an explanation in demic Press, 1976.

Here, two pixels (i, D.

As the distance between (k, A), d((it J) (k t l)) = rnax(
It k'l.

An example will be shown regarding distance conversion (thick labeling processing) when using 1j-l+).

first. The binary original pattern (size NXN mesh) is converted into the following h(i, j).

0: Character center line part" (°・j) (i) Mask scanning (hereinafter referred to as \scanning) that scans in the right direction from the upper left corner to the lower right corner,
(ii) Mask scanning that scans from the lower right corner to the upper left corner to the left (hereinafter referred to as \scan); (iii) Mask scanning that scans from the lower left corner to the upper right corner in the right direction (hereinafter referred to as /scan) Then, mask scans (hereinafter referred to as l-scans) that scan leftward from the upper right corner of the GVI toward the lower left corner are sequentially performed to complete the distance conversion.

The patterns obtained by each one scan, \scan, /scan, and Z scan are sequentially g1t g2. Let ga, g<.

g+(itj) is the distance transformation field finally obtained.

The conversion contents for each scanning direction are shown below.

(1)\scan ■ Concerning part 15 of the dictionary memory for major classification features.

For each category θ that is a figure to be recognized.

From the figure obtained by thickening and labeling the average pattern of that category, each label kf roughness, number of pixels Pk (θ) and Ak (θ) = Σ pH (0)
Calculate 1=0, generate two feature vectors (with M dimensions), and store them in memory.

■ Regarding the major classification processing section 14.

For each label k from the input line figure that has been made thicker and has been subjected to labeling processing.

Calculate.

dimension) Two feature vectors (both M generate.

Category θ is sequentially selected from part 15 of the special amount memory for dogs.
Call the coma-related feature 'fiP(4, L(θ))1, for example, using the similarity between two vectors a and b.

ψ2 However, ψ1 and ψ2 are equal to the threshold A category θ that satisfies the following is selected as a candidate figure.

That is, major classification processing is performed. As explained above, 1. When a line figure group having a complex structure and including various categories is to be recognized, the bottom-up character and thinning that are inevitable with the conventional line analysis method from the viewpoint of structural analysis are realized. This method solves the difficulties of processing and the instability with respect to deformation, especially handwritten deformation, at once.Firstly, it seeks a multivalued image representation that reflects the geometric and topological features of the binary input figure. By treating the images as 21 images, major classification and identification are realized in a consistent flow of image processing.

The great advantage of the present invention is that it is versatile as a graphic processing method, and the structure of the input graphic is naturally reflected in the multivalued image representation, and the information regarding the structure in one image representation is processed by KL transformation. The flow of extraction and use for identification does not depend on the recognition target.

Specific applications include recognition of handwritten characters and handwritten kanji.

In that case, various handwritten deformations are effectively absorbed as noise in the image representation by the KL transformation.

[Brief explanation of drawings]

Figure 1 shows the results of preprocessing of noise removal, size normalization, and binarization on the input figure (the handwritten kanji ``tai'' is used as the input figure). Figure 2 shows the binary figure being thinned by 1 and the resulting core line is given a molecular label of 0, and Figure 3 is the result of thickening processing using this core line as a starting point. , one 5t
1, 2, 3, etc. in the area obtained for each ep. . . . Figure 4 is a diagram showing how the frame is completely filled with labels and the thickening process and labeling work have been completed. Figure 5 is a diagram showing the configuration of an embodiment of the present invention. shows. In the figure, 10 is a line figure input section, and 11 is a preprocessing section. 12 is a thinning processing section, 13 is a thickening processing and labeling processing section, 14 is a large classification processing section, 15 is a dictionary memory for large classification feature values, 16 is a multivalue processing section, 1T is an identification processing section, 18
represents a dictionary pattern memory.

Claims (1)

[Scope of Claims] 1 In figure processing 1, an input figure subjected to preprocessing is converted into a core line with a line width of "1", and a center line part is extracted from which the influence of the line width of the input figure itself is eliminated. and a thinning processing unit that attaches a label O to the core wire portion. Using the label Q area obtained in the thinning processing section as a starting point, the width is
A thick processing/label processing section is installed which performs thickening processing in increments of 1" and labels the areas obtained for each thickening process sequentially as 1, 2, 3, etc., and receives an input figure. After filling a certain frame consisting of labels with labels, convert the original input figure into a multi-valued gray image by using a monotonically non-decreasing function f(k) for the label value as the gray level at each point, and perform the conversion. A graphic processing method characterized in that a recognition process is performed on a multivalued grayscale image based on the multivalued grayscale image. 2 The above recognition process uses the figures to which the above labels have been given to determine the number of pixels Pk belonging to each label area and Ak=-Σ
Using Pi, the change in Pk due to kf is roughly classified into two quantities: i=0 and/or (Pk)2/Ak, and then the Karhun method is applied to the multivalued image representation.
2. The graphic processing method according to claim 1, wherein eigenvectors belonging to large eigenvalues are obtained by en-Loive transformation, and the eigenvalues and eigenvectors for each graphic category are used to identify the figure.