JPS59792A - System and apparatus for figure recognition - Google Patents

Abstract

PURPOSE:To recognize an unknown character with high accuracy, by applying repetitively the same stop processing and propagation processing at a boundary of white figure component being identical substantially and the boundary of stroke component. CONSTITUTION:The figure on a document 41 is photoelectric-converted 42, the longitudinal and lateral spread of data is detected at a position and size extracting processing 43, and after the size is normalized 44 and the vector processing 44 is done, a stop processing 46 and a propagation processing are done. The boundary of the white figure component being identical substantially and the boundary of stroke component are independent mutually, but the content of processing is done for the same local processing principally, i.e., the stop processing 46 and the propagation processing, repetitively to change both the shapes as the figure, and the shape is made different with each other, allowing to extract the effective characteristics in applying the correlation method. The processed output is done for the foggy processing 50, similarity calculation 52 and maximum value detection 53 and the result of recognition 54 is outputted.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a method and apparatus for recognizing so-called two-dimensional patterns such as characters and figures. The present invention is based on three related prior inventions (Japanese Patent Application No. 47-50720 "Graphic Recognition Device", Japanese Patent Application No. 53-100377 "Graphic Recognition System", and Japanese Patent Application No. 1987-141836 "Pattern Recognition System") ), and contributes to improving the recognition accuracy of two-dimensional patterns.

All of the above three inventions related to the present invention have basic features such as spatial differentiation of two-dimensional figures such as characters and figures when observed as two-dimensional scalar patterns, and extraction processing of strokes and their local connection relationships. Add extraction processing to obtain two or more feature quantities at each position in a two-dimensional space, derive a two-dimensional vector pattern with these feature quantities as components, and
The unknown pattern is recognized by applying a known correlation method to the dimensional vector pattern. These inventions are more powerful as a pattern recognition method than applying the correlation method directly to two-dimensional scalar patterns obtained by observing conventional characters and figures, but they can be made even more powerful. In order to achieve this, it is necessary to effectively increase the number of vector components of the two-dimensional vector pattern 7 in terms of the types of features that can be applied.

From the above-mentioned standpoint, the present invention aims to extract features that were conventionally extracted by focusing only on the stroke components of characters and figures.
The stroke component and the next background shape surrounded by the stroke component (
By extracting mutually effective features from both of the above two-dimensional vector pattern using a generally homogeneous feature extraction process, we can extract the types of effective features, that is, the vector components of the two-dimensional vector pattern above. This makes it possible to roughly double the number of conventional methods.

In addition, a method of extracting special coating only from self-forming components without using stroke components is also known (Reference: Mori et al.
[Feature extraction using field effect method, etc.]

Journal of the Institute of Electronics and Communication Engineers, vol, 57-D, pp
, 308-315° 1974, and Oka; "On cellular automata with figures as states", Transactions of the Institute of Electronics and Communication Engineers, vol.

59-D, pp. 553-560, 1976)
. However, these methods focus only on the self-cursive form and do not substantially utilize the stroke component, and the extraction and expression of the self-form component is logical processing, and as a whole, they are not compatible with the correlation method. The content is difficult.

FIG. 1 shows an example of a two-dimensional figure consisting of a stroke component 1 and a self-stroke component 2, expressed in an expression area having a -foot spread. In addition to the stroke component 1 and the self-stroke component 2, FIG. 1 VC also displays a virtual frame 4 representing the boundary 3 between the two and the boundary of the expression area.

Of the three inventions related to the earlier applications mentioned above, the former two (Japanese Patent Application No. 47-5.0720 and Japanese Patent Application No. 53-1008)
No. 77) performs thinning processing focusing on the stroke component 1 and its boundary 8vc, finds one center line that is substantially equivalent to the two boundaries 3 in Fig. 1, and calculates each point on this center line. The presence or absence of a connection relationship between a and its adjacent points is determined by direction (4 directions to 8 directions).
direction), and the presence or absence of a connection relationship in each direction is extracted as a vector having 2 to 4 degrees of freedom in a high-order trace amount. In this case, among the connection relationships in 4 to 8 directions, components in the same direction but opposite rotations, that is, connection relationships in the upper and lower or left and right directions from the point of interest, are They are considered to be the same ingredient.

On the other hand, the 30th prior invention (Japanese Patent Application No. 141336/1983)
The boundary 3 between the stroke component 1 and the self-circulation component 2 in Fig. 1 is obtained as a two-component vector at each point by spatial differentiation, and this is further converted into an eight-component vector according to the direction of the vector. It is made into a high-grade product in trace amounts. In this case, the boundary 3ij as the first feature to be extracted can be considered to belong to both the stroke component l and the self-circulation component 2, but the macroscopic shape of the boundary 3 is different from that of the earlier invention. The curve that closely resembles the center line approximated from the stroke component 1 illustrated in the two examples is simply drawn twice, and in reality, it is extracted by focusing on the stroke component.
It has only the same meaning as the initial feature quantity. In particular, when using a known correlation method that uses the sum of the correlation values for each vector component as the correlation value between vectors, it is theoretically possible to use only the center line and only the boundary line, as shown below. It can be concluded that using the same method has almost the same effect.

In the known correlation method, the correlation value of two two-dimensional vector patterns fl+j+l and g(i+j+k)- is ""+g
Orthopedic leg like Ogi. However, 1 and j are parameters representing the position, and % is a parameter representing a vector component.

In equation (1), the value of 'Sf+IE is expressed by two-dimensional vector patterns f(i, j, k) and g('r
It remains unchanged even if tk) is simultaneously translated by (λ, μk) with respect to the coordinate (11j). That is, xg(i
+λ, j0μ, k) ・・・・・・・・・・・・
(2) Using the property of equation (2) that the correlation value has, suppose that the direction of the vector representing the boundary 3 in Fig. 1 is set inward of the stroke component, and the thickness of the stroke component is By translating the vector found at boundary 3 by half of the distance, the vector representing boundary 3 in Fig. 1 is
Move to the center of stroke component 1, and if the thickness of the stroke component is constant, the vector representing the boundary 3 between stroke component 1 and self-forming component 2, which originally existed on both sides of the stroke component, is stroke component 1. When moving from both sides to the center and excluding a few special parts such as the bending part of stroke component 1, the result is a perfect match. Moreover, even if the vector is moved in this way, the correlation value remains unchanged as shown in equation (2). It is concluded that there is no significant difference.

FIGS. 2 and 3 are processing flowcharts of a known pattern recognition method that utilizes the correlation of two-dimensional vector patterns whose vector components are the direction and orientation of stroke components.

The difference between the processing flowchart in Figure 2 and the processing flowchart in Figure 3 is that each of the two-dimensional patterns on the two-dimensional pattern is processed as a high-order trace amount from the two-dimensional scalar pattern (two-dimensional scalar function) obtained by observing the two-dimensional figure. Although not essential, the method of determining a vector quantity having two or more components determined by a point is slightly different in terms of execution.

In other words, in the processing flowchart of FIG. 2, from a figure corresponding to the center line of a stroke component derived from each component of the vector by line figure processing, a point of interest on the center line is determined,
Similarly, the direction of connection with adjacent points on the center line (a direction that abstracts away the direction. In principle, there is no problem no matter how many types of directions are added, but in practice, two directions that intersect perpendicularly or intersect at a 45 degree angle) 4-way rotation is suitable)2
or extracting a four-component vector1, in this case,
If the direction of the vector is set as the tangential direction of the stroke component, it is easy to intuitively think about I/C. However, the vector direction mentioned here is used to distinguish other components of the same vector from each other. Therefore, for example, it can be added to the tangential direction! It is clear that even if the normal direction orthogonal to ll is set as the direction of the vector, the substantial processing contents and effects are the same.

On the other hand, in the processing flowchart shown in FIG. The spatial differentiation illustrated in the invention (Japanese Patent Application No. 54-141336) is used, and instead of the line drawing processing 13 and connection direction extraction processing 14 in Fig. 2, the normal direction by spatial differentiation is used in Fig. 3. A direction element extraction process 33 corresponding to the extraction process is performed. In this case, it is intuitive to distinguish the vector components, that is, the types of higher-order features, in the normal direction of the boundary 3 of the stroke component 1.
In the case of the prior application example mentioned above, the direction and rotation @ 45 degrees each
Eight components with different values are used. However, as already mentioned, the vector representing the boundary 3 between the stroke component l and the drawing formation component 2 points towards the inside of the stroke component l,
By moving each component of the vector by a predetermined amount, the vector becomes substantially equivalent to the center line of stroke component 1, the direction is abstracted, and only that direction has meaning. Therefore, in this case as well, the number of substantially effective types of high-order feature amounts or the number of vector components is four.

FIG. 4 shows an embodiment of the figure recognition method according to the present invention using a processing flowchart.
The main difference from the known processing method shown in the figure is that a stop process 46 and a propagation process 47, which are surrounded by a dashed line 48, are newly added.

The stop process 46 and the propagation process 47 are carried out using the previously exemplified well-known method of extracting features by focusing only on the components that form the figure (Reference Futsumori, et al., "Feature extraction using the field effect method", Electronic Communication Academic journal, vol, 57-D, pp, 3
0B-31. By repeatedly applying local processing (that is, stop processing 46 and propagation processing 47), which are mutually independent but whose processing content is basically the same, to the boundary 3 of stroke component 2 and the boundary 3 of stroke component 1. , the shapes of both figures are changed so that when the correlation method is applied to the mutually different shapes, effective features can be extracted for each.

What should be noted here is that, as shown in equation (2) above, in the propagation process, the vector component (feature) f(1°j, k) extracted in the vectorization process 45 in Figure 4 is This is merely a translation of (1,,+) by (to λ, μk), and does not mean that the boundary 3 of the stroke component 1 and the boundary 3 of the drawing formation component 2 have been effectively separated/extracted. . That is, as shown in the present invention, the propagation process 47
The amount of movement of the vector component by the individual processed butter/
A process determined by the local shape of a two-dimensional figure and the mutual relationship of higher-order features (vector components) at multiple parts within an individual two-dimensional figure (in the present invention, such processing is The process is called a stop process 46) By controlling the stroke component 1 and the boundary 3 of the drawing formation component 2 to be different by VC, it becomes possible to effectively separate and extract the boundary 3 of the stroke component 1 and the boundary 3 of the drawing formation component 2 as independent features.

In the embodiment of FIG. 4, the form 41. Photoelectric conversion processing 4
2 and the position/size extraction process 43 are forms and techniques known in the field of optical character recognition devices (QC!R) and the like. In principle, the size normalization process 44 is performed on the form 41.
The vertical and horizontal expansion of the data representing the two-dimensional figure obtained by observing and measuring the above figure is detected by the position/size extraction process 43, and a rectangular area having a width of one foot added in advance is obtained. And its vertical and horizontal expansion! A known method (Japanese Patent Application No. 53-100377,
(mentioned above) is used.

It should be noted that it is better to carry out the size normalization process 44 as late as possible in the processing flowchart of FIG. 4, such as after the vectorization process 45 or before the blurring process 50, in order to preserve the characteristics of the original figure. It can be extracted without distortion. However, in general, the data t before the normalization process 44 is
Since the normalization process 44 is much larger than that after 44, the more the normalization process 44 is delayed, the more the overall amount of data to be processed will increase significantly.

In consideration of this point, the normalization process 44 in the example shown in FIG.
is performed before the vectorization process 45, but in reality, it is only necessary to decide at what stage it is appropriate to perform the normalization process 44, taking into consideration the overall purpose and cost.

The vectorization process 45 in FIG.
No. 86, supra), and various other methods are publicly known, and in principle, they can be used to measure the local variation of a two-dimensional scalar pattern obtained by observation, or alternatively, from a global perspective. Any quantity can be used as long as it is a quantity that can be obtained (as found using the line drawing process described above) or a quantity that can be uniquely associated with these, but here we will use a type of spatial differentiation. A possible method will be explained using acid as an example.

In the vectorization process 45, the two-dimensional scalar pattern subjected to the size normalization process 44 is converted into f('+j)+the vector representing the boundary 3 of the stroke component 1 by U.
k(i + j) T Similarly, boundary 8 of self-forming component 2
Assuming that the first component of the vector representing is Vk (1, j),
Uk(i,j) and VkD+j) by the following equation (3)
seek.

The above equation (3) is expressed as f(i, j) −f(1+λ,
When j tenμk)≧0, the value is expressed as “k(' r j
) and f(i,j)-f(t+λ,j
This means that 5tykDpj)=0 when 1μk)<0. Note that if s fCl, j) - f (i + λ, j + μk) > 0, '@ is negative, so f (1 + λ, j + μk) - fD + j) is negative, so Vk (1, j) −
In the opposite case, (10λ, j0μk)−f(1,j) is selected as the value of 7k(′+j).

By using equation (3), the vector components detected by distinguishing the difference in the direction of change can be
This prevents them from canceling out and disappearing in the blurring process 50, which will be described later.

However, the values in Table 1 are used for the above λ and μkVC. Further, O≦f(i+,+)≦M (positive finite value) is temporarily added.

Table 1: From equation (3) above, Uk(i * j ) (!:
vk(' e j ) u are both non-negative, and the following (4
) has the property of establishing the relationship of the equation.

Uk (1, j) +Vk (i r j) = 1f (1,
j) - f (i + λ, j + μk) l ・・・・・・・
...(4) Sara's Uk (' + j ) and V
k (1, j) is fk (i, j) = f (i, j) - f (1 + λ, j + μk) ......
...(6), it can also be expressed as follows.

・・・・・・・・・・・・(Forcing here to facilitate intuitive understanding of subsequent processing.)
Therefore, the vector orientations and propagation directions of uk(1,j) and Vk(1,j) are determined as shown in Table 2.

Table 2 Note that in Table 1, the subscripts are indicated as vector component numbers. Furthermore, as a specific method for the vectorization process 45, when considering the diagonal direction (when the component number is an even number) as illustrated in Tables 1 and 2, Japanese Patent Application No. 54-141336 ( It is more effective to use a known spatial differentiation method as exemplified in σ above, and such a method may be used, but in that case, the spatial frequency components of the two-dimensional pattern Since the attenuation of high frequency components is more significant than in the method exemplified in the present invention, the number of division points of the parameters (i, j) at the position of the two-dimensional pattern fD, , +) after the size normalization process 44 is increased. It is necessary to take such considerations into account.

Next, the stop processing 46 and the propagation processing 47 will be explained, or for convenience of explanation, the propagation processing 47 will be explained first.

Since the propagation process 47 is repeated multiple times, the result of the nth propagation process 47 is expressed as Uk("l (i t j )
Write l vk(n)(i, j), and the first
The method is to perform a foot prosthesis using the formula (8).

However, Uklo) (1, j) = Uk(i, j)
, yk(o)(1, j)=Vk(' r j ), and the values in Table 1 are used for (λ, μk).

The first method of this propagation process 47 corresponds to moving each vector component by a unit amount in the direction of the direction of the vector component in Table 2.

The second method of propagation processing 47 is the same as the first method for orthogonal components (components with odd component numbers in Table 2) among each vector component, but for oblique components (components with odd component numbers in Table 2). As for the even-numbered components), as shown in the propagation directions shown in the lower part of Table 2, the method is to propagate the same amount in two directions, one or two times.

However, in this case, the first propagation process 47 and after the second propagation process 47,
@ Propagate as is in the directions moved in the first propagation process 47. (Since the first propagation process 47 propagates the same amount in two orthogonal directions, even if the propagation in the subsequent propagation processes 47 is limited to one direction, the overall quantity will be doubled. The stop processing 46 will be explained next. Similar to the propagation process 47, the stop process 46 can be implemented in a variety of ways within the scope of the claims of the present invention, and three of these methods will be specifically described.

The first method of the stop processing 46 is when a pair of vector components having the same direction but opposite directions (for example, a pair of vector components with component numbers 1 and 5 in Table 2) exist on the same coordinate point. , or the directions in which the above pair of vector components are shown in the propagation directions in Table 2 (in this case, the directions are also taken into account)
If each of them exists on a pair of adjacent coordinate points in ′@ (that is, when the next propagation is performed, they pass each other and cannot exist on the same coordinate point), then Stop further propagation.

The first method of this stopping process 46 can be intuitively considered to be stopping due to a collision of mutually opposite vector components. In addition, the amount of the vector component to be stopped in the interweaving with is equal to the quantitatively smaller one of the colliding vector components, and the vector is calculated by subtracting the amount of the smaller vector component from the quantitatively larger vector component. Ingredients are stopped processing 4
If step 6 is not performed and the propagation process 47 is continued thereafter, the process can be performed even if the original figure or the figure subjected to the size normalization process 44 has not been binarized. Table 3 shows the combinations of vector components that are stopped due to collision in the first method of the stopping process 46.

Table 3 The system is stopped only at the collision of the combination of vector components marked with symbol (A) in Table 3. The meaning of symbol (A) is the fifth
As shown in the figure, this means a case where horizontal freezing or vertically opposing vector components collide. In addition, in this first method of stopping processing, if we take into account the oblique component (the even-numbered component in Table 2) as a vector component, collisions occur, for example, when the original figure is a right-angled isosceles triangle. Since there may be an inconvenient situation where the opposite component no longer exists, we use horizontal and vertical components (odd-numbered components in Table 2) as vector components.
It can only be applied when considering only Therefore, the collision of the oblique component indicated by the symbol (Bl) in FIG. 5 is not considered.

Table 4 shows the stopping conditions for the second method of the stopping process 46.

Table 4 In Table 4, the symbol (AJ + (B) or (C
) means that the stop processing 46 is performed only between vector components that are filled in. The three types of symbols in Table 4 (
A).

(B) and (0) mean that, as shown in FIG. ), if the directions of the incident vector component 62 and the opposing vector component differ by 180 degrees, and the same @ is in an oblique direction, use the symbol (B), and if the direction of the incident vector component 61 or 62 and the direction vector component is 135 degrees If different, use the symbol (
C1 is used for differentiation. The reason why the stop conditions for the stop process 46 are differentiated in this way is that, although not essential, there are some differences in specific methods.

In the actual stop processing 46, if a pair of vector components satisfying the conditions in Table 4 exist on the same coordinate point or on adjacent coordinate points in the same direction of mutual propagation, An amount corresponding to the smaller one is stopped at the corresponding coordinate point for both related vector components.

Furthermore, in the second stopping processing method, even if the diagonal component of the pair of vectors passes each other between adjacent coordinate points, it may be stopped at the adjacent coordinate points.

In this case, the vector components to be stopped according to the stopping conditions in Table 4 include those that have been stopped by the stopping process 46 before 7t.

The stopping conditions for the third method of stopping process 46 are shown in Table 5.
The symbols used in the table are as in the case of the second method above.
This has the meaning shown in Figure 7.

The specific stopping process is also similar to the second method, except that it also includes stopping between mutually orthogonal vector components. This stop between orthogonal vector components is indicated by symbol (E) in Table 5.

By the stop processing 46 described above, the stroke component U
The relationship of parallel movement that holds between k (1, j) and the output component Vk (1, j), and the above-mentioned (2).
As the identity of the correlation value shown in the equation is disturbed, the effectiveness as a feature for recognition is ensured, and the types of effective features as a whole are increased.

Note that the above-mentioned vectorization process 45. Stop processing 46
, and the number of components (types of features) of the two-dimensional vector pattern derived by the propagation process 47 may vary depending on the contents of the vectorization process 45 and the stop process 46 performed first, or if the vectorization process 45 is horizontally or In the case where the first method is used as the stop processing 46 and is carried out only in the vertical direction, there are fewer cases, resulting in a total of 4 pieces, 2 pieces for the stroke component and 2 pieces for the 1 white spot forming part.
In this case, the formal VC can obtain twice the number of vector components, but if the first method of the stop processing 46 is used, vector components that are oriented 180 degrees from each other are generally on the same coordinate point. Therefore, since the same amount of vector components are stopped, the same difference ρ cannot be used as an effective feature in the correlation method, and in the end, the number of effective vector components that can be used is four.

On the other hand, the number of practical Nagisa University vector components obtained by applying the present invention is 16. This involves performing vectorization processing 45 eight times in horizontal, vertical, and diagonal directions, and stopping processing 46.
In this case, VL has eight vector components each for the stroke component and the drawing component. However, the thickness of the stroke part is 2, like characters written in black on a white background.
When targeting a figure whose shape or meaning as a dimensional pattern is not important, the direction of the vector is abstracted from the stroke component, and the directions are mutually VC.
By adding vector components with different iso degrees as a two-dimensional pattern and creating a new vector component, the number of stroke components can be reduced to four without any practical problems.

Therefore, the practical number of vector components in this case is 4 for the stroke part and 8 for the outgoing figure part.
There will be 12 pieces in total.

Next, in the embodiment shown in FIG. 4, the judgment 49 as to whether or not to complete the stop processing 46 and the propagation process 47 is made by setting the number of repetitions of these processes in advance, or by using the stop processing 4
6, by detecting whether or not there are any more vector components that need to be propagated by 47tj by using an appropriate means, and if there are no more vector components that need to be propagated by 47tj, then the next propagation process 47 is performed. III Processing 5
What is necessary is to shift it to 0.

Next, the blurring process 50 in the embodiment of FIG. Each component of the two-dimensional vector function derived by the stop process 46 and the propagation process 47 is expressed as "j two-dimensional function fk(' +
j ), (where k is a parameter representing the first component, 1 is a parameter of the jFi coordinate). Specifically, the following equation (9) is calculated.

Note that the blurring process 50 is a two-dimensional function fk(i + j)
This is done to attenuate the high frequency components when viewed in the spatial frequency domain, so if a similar effect can be obtained, other filter functions other than the Gaussian type, such as a rectangular filter that is simple to calculate, may be used. It is also possible to use a filter function of the shape (a function that is non-negative and 1 and 9 only when r and 8 are within a finite rectangular region containing the origin 'f, and 0 in other cases).

Next, in the embodiment of FIG. 4, the similarity calculation 52 is performed using i! ii! This is a process to find the degree of similarity between the data obtained by performing the blurring process in step 50 on the unknown figure to be corrected and the standard butter/ which has roughly the same expression format.
, k) (hereinafter, as long as necessary F(/l=(F, ('
), F2 (′)r..., Fk(t), ・Fk(z
The data G(1,j+k)=Gk(1,j+k)=Gk(1,
;l) to G"" (G1 + 01 +...+ Gk
+ .

However, (F(z), G) = Σ(Fk(t), Gk)(
Fk(t), Gk); ΣΣF(71(1,j,
xa(i,j,k)j II F(') 11 = (FC'), F(tl
) Total 1IG11 = (G, G) ÷ In addition, the above (F('), G) is an appropriate number of pairs w
It may also be obtained from the following equation (19) using =1, 2, . . . , K for k:.

(F” + G) = X Wkx (Fk” +
Gk) --(11) In the above equations (101 and 01), the parameter represents the first component of a two-dimensional vector function, and the parameter and j represent two-dimensional coordinates. Also, step 52 mentioned here
The method of calculating the similarity between two-dimensional vector functions is based on the aforementioned prior invention (Japanese Patent Application No.
00377), and is a known method.

Next, in the embodiment shown in FIG. 4, the maximum value detection 63 basically detects each of the L standard patterns F(t); n-1, 2, . . . and the unknown figure G 5k4z) ; I
.

-1, 2,..., L, the maximum similarity sG(M
1 may be determined, and the category represented by the corresponding standard pattern (FCM) may be recognized as the category of the unknown figure G.

In the embodiment shown in FIG. 4, the final recognition result output 54 is determined in step 53 depending on the purpose of use of the system, and outputs the sudden recognition result in the form of a code or video on a storage medium such as a floppy disk. This is a process of outputting to another information processing system or output device, and is a well-known technology.

FIG. 8 shows the main process of processing an actual two-dimensional figure according to the embodiment shown in FIG. 4, which has been described above.

In FIG. 8, a scalar figure 71 shows the shape of the handwritten numeral "'0" which has been subjected to the size normalization process 44. The next stroke component 72 and self-circulation component 73 are derived by performing vectorization processing 45, and here the types of directions are only horizontal and vertical directions, and diagonal directions are not determined. Therefore, the number of vector components is four for both the stroke component 72 and the self-stroke component 73. In addition, U1 to U shown in the figure?
Symbols such as l and V, ~v7, etc. are expressed in formula (3) and the second
Match it with that in the table.

In the figures in the third row from the top in FIG. 8, the leftmost group 74 is the stop component of the stroke component obtained by the stop process 46 and the propagation process 47, and the second group 75 from the left is the self-generated part. It is a stopping component. Furthermore, 3 from the left
The second group 76 is a portion of the self-rotating components 73 that was generated from the temporary frame 4 in FIG. Although a slight improvement in recognition performance can be expected, this part can be ignored in practice. The bottom figure in Figure 8 is
From the left, a stop component 74 of the stroke component subjected to the blurring process 50, a stop component 75 of the self-generated component subjected to the blurring process 50, and a stop component 7B of the virtual frame component.
i/i: Brush treated.

FIG. 9 shows a block diagram of a character recognition device as an embodiment of the graphic recognition device according to the present invention which executes the above-described graphic recognition method.

In this embodiment, the main control section 80 performs overall control, and consists of a lamp main control unit (MPU) 81, a main storage device 82, and an input/output control section 83, and an internal bus 84.
are interconnected by. The input/output control unit 83 is provided with processing circuits 100 to 700 that execute each processing step of the processing flowchart in FIG. Multiple units are connected. The main storage device 82 stores a control program for the entire character recognition device, a control program for opening processing, and various data used for editing recognition results as needed.

In the embodiment of FIG. 9, the form 41 is the same as the form 41 in the processing flowchart of FIG. The photoelectric conversion unit 110 scans the form 41 and converts its local optical reflectance % or absorption rate into a binary or multivalued sequential digital electrical signal, and the position/size detection circuit 100
send to The position/size detection circuit 100 performs position/size detection processing using the detector element! ! The position and size of the smallest rectangular area surrounding the entire two-dimensional figure (in this case, a character) are detected and sent to the size normalization processing circuit 200 via the external bus 85.

The size normalization processing circuit 200 takes all of the position and size data detected by the position/size detection circuit 100, and calculates the size of the corresponding two-dimensional figure by adding it in advance. Reduce the size of the work area in the shape of a triangle. At this time, it is assumed that the digital electrical signal representing the two-dimensional figure on the form 41 outputted from the photoelectric converter $110 has been written in the main storage device 84 once.

The vectorization processing circuit 300 is the large @ awn normalization processing circuit 2
00 processed two-dimensional figure data of scalar expression,
A process equivalent to spatial differentiation is performed to convert the data into data representing two sets of two-dimensional vector patterns, a stroke component and a white figure component. This vectorization processing circuit 300 has at least two registers that temporarily store all data, and a function that calculates the difference between the numerical values stored in these registers, including the positive and negative signs. The stop processing circuit 400 performs the stop processing 46 on each of the data representing the two sets of two-dimensional vector patterns generated by the vectorization processing circuit 800 together with JAY, and determines whether there is any remaining data to be subjected to the propagation processing 47. If detected, the VC is sent to the propagation processing circuit 450 if it remains. The propagation processing circuit 460 generates a pair of coordinate axis directions [1
It has the ability to move data one by one. As already mentioned, this propagation process 47 only applies the vector component of the special leg (vector component in the diagonal direction) in the first time.
It also has a function of storing 470 times of propagation processing so that it can be moved by the same amount in the two coordinate axis directions. When one propagation process 47 is completed for each set of two-dimensional vector patterns, the corresponding data is sent back to the all-stop processing circuit 400, and the stop process 46 and the propagation process 47 are repeated. The completion of the stop process 46 and the propagation process 47 is achieved by a function of detecting whether or not there remains data to be subjected to the propagation process 47 provided in the stop process circuit 400 for each set of two-dimensional vector patterns. Judge by.

The blur processing circuit 500 receives the data for which the stop/propagation process 48 has been completed, and executes the filling process 50 shown in equation (9) for each vector component of the two sets of two-dimensional vector patterns.

The similarity calculation circuit 600 generates two sets of two-dimensional vector patterns subjected to the blurring process 50 and at least one pattern per category that is stored in advance in the similarity calculation circuit 600 or the main storage 84 in the same data format. The similarity 5G (A+) is obtained by dividing each set of standard pattern data j151 using the formula 00).The function of the similarity calculation circuit 6000 is mainly a multiplier that calculates the sum of products of two sets of data strings. and the function of the storage device that supplies the standard pattern data 51 to this multiplier, so it is necessary to speed up these multipliers and storage devices by parallelizing them as necessary. There is.

Furthermore, in order to recognize the input figure, it is necessary to find the maximum similarity SG(M) from among the plurality of similarities SG('')2l=1,2...,L. Maximum value detection 53) in FIG. 4 may be performed by software on the main processing unit 81, or if necessary, a maximum value detection circuit may be provided in the similarity calculation circuit 600 to speed up the processing. You can do it like this.

The output circuit 700 is an interface circuit for transmitting all recognition results to a host system, an external storage device, or an image output device in the form of a preset code or image, depending on the usage mode of this embodiment. As described above, the individual functional processing circuits constituting this embodiment can be easily designed and manufactured using known techniques. Therefore, as already mentioned, the present invention can improve the types of effective features that can be extracted using the conventional method (already published, Japanese Patent Application No. 1973: (-100377)) by simply adding the stop processing circuit 4 (river and propagation processing circuit 450). (The number of vector components of a two-dimensional vector pattern) can be roughly doubled.
When the present invention is applied to a handwritten character recognition device, there is an effect that unknown characters can be recognized with high accuracy.

[Brief explanation of drawings]

W, Figure 1 is an explanatory diagram of the graphic concept used in the explanation of the present invention, Figure 2 is a processing flowchart of the pattern recognition method of the earlier application related to the present invention, and Figure 3 is a diagram of another pattern recognition method of the earlier application. Processing flowchart, FIG. 4 is a processing flowchart showing an embodiment of the figure recognition method according to the present invention, and FIG.
The figure is a conceptual explanatory diagram showing the entire first method of the stop processing 46.
The figure is a conceptual explanatory diagram showing the second method of the stop processing 46.
The figures also illustrate the third method of the stop processing 46. Figs. 1 and 8 illustrate the embodiment of the present invention shown in Fig. 4. FIG. 9 is a block diagram of a character recognition device showing an embodiment of the figure recognition device according to the present invention. Fig. 1 Fig. 2 Fig. 3 Fig. 21 Fig. 5 Fig. 6 (+) (2) Fig. 7 (1), (2) No. 1: Figure 3 Sub-1 Figure Procedure Amendment (Voluntary) August 2, 1981 Kazuo Wakasugi, Commissioner of the Japan Patent Office1, Indication of the case, Patent Application No. 99748 of 19832, Name of the invention, figure recognition system and device 3, Person making the amendment Relationship with the case Patent applicant Address 1-5-11 Honmachi, Koganei City, Tokyo Name
An 1) Michio 4, Agent 101 Address 4th floor, New Sun Building, 2-8-6 Kajicho, Chiyoda-ku, Tokyo Tel: 03 (256) 2625 (1) Detailed explanation of the invention in the specification column 6, Amendment Contents (1) From line 8 to line 13 on page 34 of the specification [This is the bottom row of FIG. 8]. "In the figure at the bottom of FIG. 8, the first group 77 from the left is the stop component 7 of the stroke component.
4 with blur processing 50, second group 78
Similarly, the third group 79 is the one in which the blurring process 50 is applied to the stopped component 75 of the self-generated component, and the third group 79 is the one in which the blurring process is applied to the stopped component 76 of the virtual frame component. ” he corrected. (2) Insert the following sentence between page 34, line 13 and line 14 of the specification. ``In other words, in Figure 8, vectorization is performed only in the horizontal and vertical directions without considering the diagonal direction, propagation processing is applied to this, and the first stop processing method using the stop conditions shown in Table 3 is applied. The process of the case and the results up to the blurring process are shown in Figure 1.Next, Figure 1O shows how to vectorize the handwritten digit ``0'' in the horizontal and vertical directions, considering the diagonal direction as shown in Table 2. In addition, vector components in diagonal directions are obtained, propagation processing is also performed in diagonal directions as shown in Table 2, and the vector components are obtained by a computer simulator by applying the third stop processing method based on the stop conditions shown in Table 5. The results are shown below. In other words, in Figure 10, 70
indicates the original handwritten digit "0" that was the object of observation, and the figures f1 to f+6 in the second row are vectors obtained by spatially differentiating the stroke components of the group 72 on the left.
In addition, group 73 on the right shows the white figure components subjected to spatial differentiation and made into a solid 1-hell. The third row from the top of FIG. 10 shows the results of performing the propagation process and the stop process 46 under the conditions shown in Table 5, respectively. The fourth row shows the group 74 on the left side of the third row organized and summarized, since it is practically meaningless to consider the difference in direction of stroke components. Figure 11 shows the fourth stage of Figure 10 obtained by applying the propagation process considering the diagonal direction as shown in Table 2 and the stopping conditions shown in Table 5 for the handwritten digits "0" to "9". This shows the results up to the blurring process corresponding to the eyes. However, the first column on the far left shows handwritten digits, the third column shows the processing results Fl-F4 virtually added to the stroke components, and the fourth column shows the white figure formation components. A virtual addition of processing results F5 to F12, and a second
The column is the virtual addition of the third and fourth columns, that is, F
1 to F12 are all added. Looking at this second column, it is clear at a glance how good the information extraction state is when the present invention is applied. 10 and 11 above show the results of directly processing raw data without performing the size normalization process 44. In FIG. On the other hand, FIG. 12 shows the result corresponding to the fourth row of FIG. shows. Furthermore, Fig. 13 shows the results corresponding to the first to fourth columns of Fig. 11 when the present invention is applied to handwritten kanji. , the fourth column shows the total sum of processing results for the white figure forming component, and the second column shows the sum of the results in the third and fourth columns. (3) On page 40, line 13 of the specification, insert the following sentence after "...". "Also, FIG. 10 is an explanatory diagram showing the state of data generated and converted when handwritten numeral "0" is processed by applying the embodiment using the third stop processing method in consideration of the diagonal direction, Figure 11 is an explanatory diagram showing data obtained as a result of processing the same handwritten digits "0" to "9", Figure 12 is an explanatory diagram showing an example of data used in the standard pattern, and Figure 3. FIG. 2 is an explanatory diagram showing an example of the result of processing handwritten Chinese characters by applying the present invention. 1...stroke component, 2...white figure component, 3...-boundary, 4...virtual frame. (4) Add the drawings in Figures 10 to 13 attached to this amendment. Figure 1 3

Claims (4)

[Claims] (1) The original two-dimensional figure expressed on a two-dimensional plane is observed as a two-dimensional scalar function, and each point on the coordinate plane that expresses the observed two-dimensional scalar function, or the coordinate plane that is enlarged or reduced. Then, the change in the two-dimensional scalar function value in at least two or more directions is detected as a higher-order state quantity corresponding to each direction by distinguishing the direction of the change, and detected at each point on the coordinate plane. The plurality of higher-order state quantities obtained are divided into two sets in relation to the direction of change of the above-mentioned function value, and a unique unit quantity is minutely moved for each higher-order state quantity for each set. When the relative relationship between two or more predetermined higher-order state quantities on each point on the coordinate plane and adjacent points before and after the minute movement satisfies certain conditions, it is guided according to certain rules corresponding to that relative relationship. A new higher-order state quantity is detected in relation to the above coordinate plane, and a two-dimensional vector pattern having the detected Niijima-order state quantity as a vector component, and a plurality of pre-prepared standards in the same expression format as this are prepared. A figure recognition method characterized by determining the category of an original two-dimensional figure by comparing it with a pattern. (2) In the above figure recognition process, the process of binarizing or quantizing the observed function value of the two-dimensional scalar function or two-dimensional vector function, and the process of binarizing or quantizing the function value of the observed two-dimensional scalar function or two-dimensional vector function A size normalization process that makes the expansion on the coordinate plane approximately constant,
2. The figure recognition method according to claim 1, further comprising a step of convolving the two-dimensional scalar function or the two-dimensional vector function with a filter function. (3) observation means for observing an original two-dimensional figure expressed on a two-dimensional plane as a two-dimensional scalar function; and a coordinate plane for expressing the two-dimensional scalar function observed by the observation means;
Or, at each point on the coordinate plane that is enlarged or reduced, the change in the above two-dimensional scalar function value in at least two or more directions is distinguished, and the height corresponding to each direction and direction is calculated. A means for detecting next-order state quantities and a plurality of higher-order state quantities detected at each point on the coordinate plane are divided into two sets in relation to the direction of change of the above-mentioned function value, and each set of each set is A means for performing minute movement of a specific unit quantity for each higher-order state quantity, and a means for performing a minute movement of a specific unit quantity for each higher-order state quantity, and a relative relationship between predetermined two or more higher-order state quantities at each point on the coordinate plane and adjacent points before and after the minute movement. means for detecting a new higher-order state quantity derived according to a certain rule corresponding to the relative relationship when the condition of one foot is satisfied, and a means for detecting a new higher-order state quantity in relation to the coordinate plane; A figure recognition device comprising: a two-dimensional vector pattern; and means for determining a category of an original two-dimensional figure by comparing it with a plurality of standard patterns prepared in advance and having the same expression format. . (4) means for binarizing or converting the function value of the two-dimensional scalar function or two-dimensional vector function observed by the observation means; and Large enough to keep the spread on the coordinate plane roughly constant! ! a normalization means;
3. The figure recognition device according to item 3 of the scope of Patent R Seishui, characterized in that it includes a blurring processing means for convolving the two-dimensional scalar function or the two-dimensional vector function with a filter function.