JPH0366703B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (1) Description of the field to which the invention pertains The present invention relates to an online handwritten character recognition system in which character recognition ability does not deteriorate even due to incorrect stroke order or number of incorrect strokes.

(2) Description of conventional technology In the conventional online handwritten character recognition method, unlike the case of CR, the input pattern to be recognized is The method used was to perform recognition by matching only this pattern with a standard pattern with the same number of strokes. In this case, there was a restriction that the number of strokes had to be written down correctly. However, the more complex the shape, such as a kanji with a large number of strokes, the more likely it is that the number of strokes is incorrect, and the constraint of maintaining the correct number of strokes was a heavy burden on scribes.

One way to solve this problem is to register all the various ways of writing characters with different numbers of strokes as standard patterns for characters that are likely to have incorrect stroke counts. However, it is practically impossible to list all the different ways of writing each character with different numbers of strokes, and even if only some of them were registered as standard patterns, the number of standard patterns would be enormous. However, the amount of calculation required for recognition increases rapidly, and if the number of incorrect strokes is not registered, it will always be recognized incorrectly.

Another solution is to register standard patterns with the correct number of strokes in various stroke orders, and assuming that the input pattern is written with the wrong number of strokes, convert both the input pattern and the standard pattern into single strokes for recognition. However, the single stroke pattern was sensitive to handwritten deformation and could easily cause misrecognition, and it had the disadvantage that it could not handle unregistered stroke orders at all.

Another solution is to register only the correct stroke order and number of strokes in the standard pattern, and even if the input pattern is written in the wrong stroke order and number of strokes, the pattern with the smaller number of strokes from the standard pattern can be registered. The idea was to match all the strokes of the other pattern to the strokes of the other pattern, and combine the unresponsive strokes of the pattern with the larger number of strokes with the previous corresponding strokes in the stroke order, and perform recognition after matching the number of strokes. 57-46080), but due to the unique handwriting deformation that occurs when writing with an incorrect number of strokes, if the stroke correspondence in the previous stage is incorrect, the combination of strokes that follow the stroke order in the latter stage will also be incorrect, resulting in erroneous recognition. Ta.

(3) Purpose of the invention The present invention solves the above-mentioned conventional problems, and
By simply registering only the correct stroke order and number of strokes as standard patterns, writing in the wrong stroke order and number of strokes is allowed, and in particular, handwriting deformation caused by writing with the wrong number of strokes can be dealt with without degrading character recognition ability. The purpose is to provide an online handwritten character recognition method.

(4) Description of structure and operation of the invention The details of the present invention will be explained below with reference to Examples.

FIG. 1 is a functional block diagram of a device used in one embodiment of the present invention, in which 1 is a character information input device;
2 is a preprocessing device, 3 is a stroke feature point extraction device, 4 is a standard pattern storage device, 5 is an inter-stroke distance calculation device, 6 is a stroke correspondence device,
7 is a selective stroke combination device, 8 is an inter-pattern distance calculation device, 9 is a minimum distance value detection device,
The operation of each device will be specifically explained below.

The character information input device 1 is composed of an existing tablet, inputs the X and Y coordinates of the handwriting of each stroke of the input pattern at fixed time intervals, and sends the string of strokes to the preprocessing device 2.

The preprocessing device 2 performs noise removal, smoothing, normalization of position and size, etc. on the pen point sequence sent from the character information input device 1 based on known techniques, and processes the resulting pen point sequence into strokes. Feature point extraction device 3
Send to.

The stroke feature point extraction device 3 is a preprocessing device 2.
For each stroke's line of pen points sent from Extract a sequence of feature points representative of .

The input pattern is written as S〓, and S〓 consists of N strokes S ₁ , ..., S _i ..., S _N , and the feature points of each stroke are expressed by connecting the X and Y coordinates as _{S i =} ( , y _1i ,
..., x _oi , y _oi ). Here, n is the number of feature points included in S _i , and i represents the stroke order with 1≦i≦N, which may be different from the correct stroke order. The stroke feature point sequence extracted from the input pattern S is sent to the inter-stroke distance calculation device 5 and the selective stroke combination device 7.

The standard pattern storage device 4 stores stroke feature points extracted at equal intervals on each stroke using the above-mentioned increment distance value △ from each average pattern written in the correct stroke order and number of strokes for all character categories to be matched. The stroke feature point sequence having the correct stroke order and number of strokes is sent to the inter-stroke distance calculation device 5 and the selective stroke combination device 7 as a standard pattern.

The inter-stroke distance calculation device 5 calculates all stroke pairs between the feature point sequence of the input pattern S sent out from the stroke feature point extraction device 3 and the feature point sequence of the standard pattern sent out from the standard pattern storage device 4. Calculate the distance between strokes.

The standard pattern is written as R〓, where R〓 is M strokes.
It consists of R ₁ , ..., R _j , ... R _M , and the j-th stroke R _j connects the X and Y coordinates of the feature points to R _j = (x _1j ,
y _1j , ..., x _nj , y _nj ). Here, m is the number of feature points included in R _j , and j is 1≦j
≦M represents the correct stroke order. i-th stroke S _i (x _1i , y _1i , ..., x _oi , y _oi ) (1≦i
≦N) and the j-th stroke R _j of the standard pattern R〓
The inter-stroke distance d _ij based on the smaller number of feature points of (x _1j , y _1j , ..., x _nj , y _nj ) is, for example, using the squared distance. If m≧n, d _ij = α _ij・min 0≦R≦m−n _N 〓 ⁱ⁼¹ {(x _k+p,i −x _kj ) ² +(y _k+p,i −y _kj ) ² }(1) . Here, α _ij is a factor for evaluating the difference in the number of feature points, and for example, α _ij =m/n is used.
The formula for calculating d _ij when m<n is m and n in the above formula (1).
and x and x', respectively. Note that in equation (1), it is also possible to use the square distance of the starting point or ending point without performing the min operation. By equation (1), d _ij for all stroke pairs
is calculated, and a total of M·N inter-stroke distance values are sent to the stroke matching device 6.

The stroke matching device 6 uses the M/N inter-stroke distance values sent from the inter-stroke distance calculation device 5 to match the same number of strokes from the opponent pattern for all strokes of the pattern with the smaller number of strokes. Select the strokes and associate them with each other. Specifically, depending on the magnitude of the number of strokes M and N, when M≧N, the corresponding stroke of the i-th stroke S _i of the input pattern is taken as the j _-th stroke of the standard pattern, and _M 〓 ^j=1 d _iji . minimum and
Determine N stroke pairs that satisfy the condition that j ₁ , j ₂ , ..., j _N have no overlap, and when M<N, the corresponding stroke of the j-th stroke R _j of the standard pattern is used as the i-th stroke of the input pattern. As _j stroke, _N 〓 ⁱ⁼¹ d _ijj
Determine M stroke pairs with the minimum value and no overlap in i ₁ , i ₂ , . . . , i _M . The stroke correspondence determination results are sent to the selective stroke combination device 7.

FIG. 2 shows an example of the stroke correspondence between an input pattern "character" written in five strokes with the number of incorrect strokes and the order of incorrect strokes, and a "character" in a standard pattern correctly written in six strokes. Circles indicate correspondence. The fifth stroke _R5 of the standard pattern is not supported. In the figure, black circles on the stroke represent the positions of feature points.

The selective stroke combination device 7 temporarily stores the stroke feature points of the input pattern sent from the stroke feature point extraction device 3 and the stroke feature points of the standard pattern sent from the standard pattern storage device 4, and Based on the stroke correspondence results sent from the above, the remaining uncorresponding strokes in a pattern with a large number of strokes are combined with one of the two corresponding strokes of the pattern that precede and follow each other in the stroke order, in the other pattern. This device calculates the inter-stroke distance between the corresponding strokes by combining the start point and end point based on the feature point sequence, and selects and executes the combination that reduces the distance.

Hereinafter, the specific operation of the selective stroke coupling device 7 will be explained in detail separately for the cases of M≧N and M<N.

If M≧N, the stroke matching device 6 has determined N stroke pairs between the standard pattern and the input pattern. Those N strokes in the standard pattern are Rp ₁ , Rp ₂ , ..., Rp _k , ...,
It is written as Rp _N , and the subscripts are added in ascending order of stroke order using the following formula.

1≦p ₁ ＜p ₂ ＜...＜p _K ＜...＜p _N ≦M (2) Also, Rp _k (1≦k≦N) corresponds to Sq _k (1≦k≦N) in the input pattern, respectively. It is assumed that the This device supports M-
The N uncorresponding strokes are sequentially selectively combined with the corresponding strokes. Now, the uncorresponding stroke of interest in the standard pattern is denoted as Rt. i<
Assuming that the connection partner has already been determined for the uncorresponding stroke R _i that satisfies t, the connection partner of Rt is determined as follows.

() When t<p ₁ According to equation (2), in this case, there is no corresponding stroke that precedes Rt in stroke order. Therefore, Rp ₁ is unconditionally selected as the binding partner.

() In the case of p _k < t < p _k+1 (1≦ _k ≦N− ₁ ), Ru It is written as In general, u≦p _k .
Here, the following two types of combined strokes are generated. However, ~ represents an operation of combining strokes in the order of occurrence.

Rt′=Ru〜…〜Rp _k〜 …〜Rt−1〜Rt Rt″=Rt〜Rt+1〜…〜Rp _k+1 Figure 3 shows the correspondence between Rp _k and Sq _k , and
A conceptual diagram of the generation of Rt′ and Rt″ is shown.

As shown in FIG. 3, Rt' is the stroke that should correspond to Sq _k in the input pattern. On the other hand, Rt″ is the stroke that should correspond to Sq _k+1 . Therefore, calculate the distance between strokes between Rt′ and Sq _k , and between Rt″ and Sq _k+1 , and select the smaller value. Select the connection method. That is, the binding partner of Rt is determined by the following equation.

a′・d ^* q _k , t′≦a″・d ^* q _k+1 , t″ → Combine Rt to Rp _k a′・d ^* q _k , t′＞a″・d ^* q _k+1 , t″ → Rt is combined with Rp _k+1 . However, a′, a″ are factors (≧1) that evaluate the difference in the number of feature points. Also, the distance between strokes
As d ^* , a square distance based on DP matching, which is a known technique in which the starting point and the ending point are associated with each other, may be used. In that case, Si=
(x _1i , y _1i , ..., x _oi , y _oi ) and Rj = (x′ _1j , y′ _1j ,
..., x _nj , y′ _nj ) distance d ^* _ij is calculated by the following formula.

d ^* _ij = min τ _o 〓 ^k=1 {(x _ki −x′〓 _(k)j ) ² + (y _ki −y′〓 _(k)j ) ² }(3) However, τ is τ(1 )=1, τ(n)=m is a monotonically non-decreasing matching function.

Here, the reason for using DP matching in which the start and end points are combined is based on the requirement that the strokes generated by the combination should completely overlap with a corresponding stroke in the input pattern.

() When p _N <t According to equation (2), in this case, there is no corresponding stroke that follows Rt in stroke order. Therefore, Rp _N is unconditionally used as the binding partner.

By the above steps divided into (), (), and (),
All uncorresponding strokes of the standard pattern are determined to have a joining partner, and the joining is performed to convert them into a pattern of N strokes.

On the other hand, if M<N, the stroke matching device 6 has determined M stroke pairs between the standard pattern and the input pattern. Let these M strokes in the input pattern be Sq ₁ ,..., Sq _k ,
..., Sq _M , and the subscripts are added in ascending order of stroke order using the following formula.

1≦q ₁ <q ₂ <...<q _k <...<q _M ≦N (2)' Also, Sq _k (1≦k≦M) is the same as Rp _k (1≦k≦M) in the standard pattern, respectively. It is assumed that there is a correspondence. This device detects N− in the input pattern.
The M uncorresponding strokes are sequentially selectively combined with the corresponding strokes. The specific procedure is the same as in the case of M≧N, and the uncorresponding stroke of interest is
When written as St, ()t<q ₁ , ()q _k <t<q _k+1 ,
The binding partner is determined separately in the case of ( )q _M <t.

Through the above process, the selective stroke coupling device 7
aligns the number of strokes of the input pattern and the standard pattern to K=(min(M,N)), and generates K stroke pairs with the same stroke order and number of strokes. These stroke pairs can be rewritten as S _k , R _k (1≦k
≦K).

This result is sent to the inter-pattern distance calculation device 8.

4 and 2, the fifth stroke _R5 of the uncorresponding standard pattern is combined with _R4 by selective stroke combination. In the figure, black circles on the stroke represent the positions of feature points.

The inter-pattern distance calculation device 8 calculates the inter-stroke distance for each corresponding stroke using the input pattern with the same number of strokes and stroke order sent from the selective stroke combination device 7 and the feature point sequence of the standard pattern. The device calculates the summation result as the inter-pattern distance.The stroke-to-stroke distance is determined by matching the starting point and ending point, which is a known technique, and applying the DP matching method based on the smaller number of feature points, for example, by formula (3). ), calculate the inter-stroke distance d ^* _kk for each of the K stroke pairs S _k and R _k (1≦k≦K), and calculate the inter-pattern distance as _K 〓 ^k=1 d ^* _kk Calculate as. The calculated inter-pattern distance is sent to the minimum distance value detection device 9.

The operations of devices 5 to 8 described above are performed for all standard patterns stored in the standard pattern storage device 4. When this operation is completed, the minimum distance value detection device 9 detects the minimum distance among all the accumulated inter-pattern distances, and sends the character category of the standard pattern corresponding to this as an identification result from the device. Output.

(5) Description of effects As explained in detail above, according to the present invention,
It is possible to significantly improve the online handwritten character recognition function by allowing writing in the wrong order of strokes and with the wrong number of strokes, which has been considered impossible until now. In particular, it is only necessary to register only the correct stroke order and number of strokes as a standard pattern, and between the input pattern of incorrect stroke order and number of strokes and the standard pattern, first select the strokes that match the stroke order for the smaller number of strokes. The unique handwriting that occurs when a pair is determined, and then the uncorresponding strokes in the pattern with the larger number of strokes are selectively combined with the corresponding strokes to improve the overlap between the patterns, and the strokes are written with an incorrect number of strokes. High recognition accuracy can be achieved as a result of absorbing deformation and aligning strokes in the same stroke order and number of strokes.This makes it possible to realize online handwritten character recognition for an unspecified number of scribes who frequently write with various stroke orders and numbers of strokes. It has great advantages when applied in the field.

[Brief explanation of drawings]

FIG. 1 is a functional block diagram of a device used in one embodiment of the present invention, FIG. 2 is a conceptual diagram of a specific example for explaining the operation of the device 6 in FIG. 1, and FIGS. 3 and 4 are 2A and 2B are a conceptual diagram and a concrete example diagram for explaining the operation of the device 7 shown in FIG. 1, respectively. In the figure, 1 is a character information input device, 2 is a preprocessing device, 3 is a stroke feature point extraction device, 4 is a standard pattern storage device, 5 is a distance between strokes calculation device, 6 is a stroke matching device, and 7 is a selective 8 is an inter-pattern distance calculation device;
9 indicates a minimum distance value detection device.

Claims (1)

[Claims] 1. It should be recognized that this is a stage in which feature point sequences are extracted and stored at equal intervals with a predetermined increment distance value for all strokes of an average pattern written with the correct number of strokes and stroke order for each character category as a standard pattern. a step of extracting and temporarily storing a sequence of feature points at equal intervals for all strokes of the input pattern using the step distance value; After calculating the inter-stroke distance based on the smaller number of feature points between the input pattern and the standard pattern, calculate the inter-stroke distance from the other pattern for all strokes of the pattern with the smaller number of strokes between the input pattern and the standard pattern. Selecting the same number of strokes with the minimum sum and no overlap and associating them with each other, and selecting two strokes of the pattern that are arranged one after the other in the stroke order for the strokes that remain uncorresponded in the above-mentioned correspondence in the pattern with the larger number of strokes. Assuming a connection with one of the existing strokes of the book, calculate the inter-stroke distance between the corresponding stroke in the pattern with the smaller number of strokes and the starting point and end point based on the feature point sequence. The step of selecting and executing the combination that reduces a step of calculating distances and accumulating their addition results; a step of repeatedly performing all the above steps for all of the standard patterns to be matched and accumulating the addition results sequentially; and after completing the step, performing the addition. An online handwritten character recognition method comprising the step of detecting a minimum value among the results and outputting a character category of a standard pattern corresponding to the minimum addition result as a recognition result.