JPH0136151B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a pattern matching method for determining the degree of dissimilarity between patterns in pattern recognition, particularly in recognition of two-dimensional figures such as characters.

[Background technology and its problems]

In pattern recognition of two-dimensional figures, sounds, etc.
A set of two feature vectors extracted from the pattern, A = {A ₁ , A ₂ , ..., A _I } ...(1) B = {B ₁ , B ₂ , ..., B _J } ...( 2) Evaluating the degree of similarity or dissimilarity (hereinafter referred to as dissimilarity) is the core problem.

For example, in the pattern matching method for character recognition, each point Z _i = (x _i ,
y _i ) density value set A={p(Z _i )} and the unknown input pattern density value set B={q(Z _i )} D ₁ = (A, B) = 〓 ^zi |p(Z _i )−q(Z _i )| (3) By using the following as the degree of dissimilarity, the closeness between the input character and each character concept is evaluated. In addition, the correlation value Σp
(Z _i )・q(Z _i ) may be used for the similarity, or this correlation value or the value of equation (3) may be normalized by the average concentration of A and B, but in both cases, the The basic position is the same in terms of determining quantity. Because this pattern matching method has simple logic, it has been widely used as a method for recognizing printed characters. However, since the position of the sample points is essentially fixed and superimposition is performed, the sample points are It is difficult to apply this method to objects whose positions change. For this reason, for such objects, a so-called structural analysis method is required, which associates clusters of features between the input and the mask.

In the field of speech recognition, where features are time-series, one method of structural analysis is DP (dynamic programming), which sequentially expands and contracts the sample (time axis) in a nonlinear manner to find the optimal correspondence. R.Bellman“Dynamic
Programming”, Princeton University Press,
1957) has been established as the standard matching method. In other words, when the features are arranged in series, such as in speech, Equations (1) and (2) are used to respond nonlinearly as shown in Figure 1.
The combination of sample point i of A and sample point j of B in the formula is C(k) = (i(k), j(k))...(4) The distance between the features of arbitrary sample points i and j is d(c)=d(i,j)=|A _i −B _j | ...(5), and the degree of difference between sample points A and B is are defined respectively. Equation (6) takes various combinations of correspondence between A and B, and uses the one with the smallest sum as the overall measure. w(k) is a non-negative weighting factor introduced to make the system flexible.

Here, the correspondence between A and B is allowed to be 1:2, and the distortion C
= (i, j) as a function (i, j
(i)), which is the so-called asymmetric position, and if the sampling interval of point i (line segment length in the example of a contour segment described later) is l _i , then w(k) = w( Write i) = l _i , and the problem to find D ₂ is g(i, j) = ming (i-1, j-1) + l _i・d ₁ (i, j) g (i-1, j- 2)＋l _i・d ₂ (i, j‐1, j) g (i‐2, j‐1)＋(l _i‐1 +l _i )・d ₃ (i‐1, i, j) ……( 7) Set the recurrence formula to the following constraint condition regarding j(i).
(1), (2), (3) (1) j(i) is a continuous monotonically increasing function (2) j(1)=1, j(I)J (3) j(i) This results in a DP problem in which the value of is around i, and the recursive evaluation g(i, j) at the i-th stage is obtained by calculating sequentially. The final degree of dissimilarity D ₂ is determined by D ₂ (A, B)=1/Σl ₁ g (I, J) (8). In other words, by sequentially optimizing equation (7), the desired global optimal solution of equation (6) can be quickly obtained as the degree of dissimilarity D ₂ determined by equation (8). be able to.

Note that when sampling at equal intervals (l _i = 1), the distance between features is expressed as d ₁ (i, j) = d (i, j) d ₂ (i, j-1, j) = (d (i , j-1)+d
(i, j))/2 d ₃ (i-1, i, j) = (d(i-1, j) + d
(i, j))/2 ……(9) H. Sakoe and S. Chiba “Dynamic
programming algorithm optimization for
spoken word recognition”IEEE Transactions
on Acoustics Speech and Signal Processing,
Vol.ASSP-26, NO.1, PP.43-49 (1978).

Also, in the field of character recognition, DP is easily used in online formats where the features are in chronological order.
However, in offline character recognition, there are two characteristics.
Due to the dimensional distribution, the application of DP is not easy. In the case of features of two-dimensional figures, it is important to maintain a two-dimensional relationship of proximity, but it is difficult to serialize them one-dimensionally while maintaining this relationship.

Before explaining this problem specifically, we will explain the definition of the feature vectors, words, and notations used in the DP matching of two-dimensional figures according to the present invention. First, black dots on the boundary of a black and white binary figure are called contour points, and a closed loop of continuous contour points is called a contour. Next, as shown in Fig. 2a, when the contour is approximated by a straight line in the direction of turning the white point to the left, the line element is the contour line part or simply a line segment (indicated by arrows and symbols 1 to 12). The first (on the side without the arrow mark) and last (on the side with the mark) outline points of each line segment are called the starting point and the ending point. Note that the end point of one line segment and the start point of the next line segment are the same point. Next, the first and last line segments for the contour of one circumference are called the starting line and the ending line. The starting point of the starting line and the ending point of the ending line match.

When the contour is approximated by line segments in this way, every line segment i has a line segment i' whose end point is the start point of i, but this i' is called the line segment immediately before i, and i'=P(i ) ...(10)

Furthermore, as shown in the feature vector definition diagram ^of line _{segment i} ⁱⁿ FIG _.
The lengths l _i are listed, and each is defined as follows.

Finally, a set Q(i) of line segments that can "precede" a certain line segment i is defined as follows.

Q(i)={i′|Satisfies condition 1, condition 2, and condition 3} ……(12) Condition (1): |Z ^b _i −Z ^o _i ′|≦δ (for example, 3) Condition (2 ): |Z ^b _i −Z ^o _i ′|≦β (for example, 32) or |a _i ~a _i ′|>π/2 or (Z ^b _i −Z ^o _i ′)・(Z ^o _i −Z ^b _i ′)≧0 Condition (3): |Z ^b _i −Z ^o _i ′ | | Z ^b _i −Z ^o _p (1′) | and |Z ^b _i −Z ^o _i ′ | | Z ^b _i − Z ^o _i ″｜, i′=P(i″
) In other words, conditions (1) and (2) mean a line segment whose end point is inside the diagonal line in Figure 3, or a line segment whose end point is inside a circle with radius β and whose angular difference is π/2 or more. . However, the definition of absolute value for vectors (11)
From the formula, it is actually not a circle but a rhombus (a square rotated 45 degrees). Condition (3) is the same as conditions (1) and (2) above.
This means that among the line segments, only those whose distance from i before and after is minimal are left.

This set is for allowing line segment i to connect and correspond to the end point of line segment i', and plays an important role in the pattern matching method of the present invention.

Under the above definition, mask side feature A = {A _i }
Let us consider the correspondence of the input side feature B={B _j } by DP. First, a sequence is given to the mask side feature {A _i }. For this purpose, the order of the contour line segments described above is used as is.

Next, although the input side is also organized in a series in terms of the order of tracking, this series cannot be used as is to correlate with the mask side. That is the second
As shown in FIG. b, when a break occurs in the line, the series of contours changes (indicated by line segments 1 to 14).
This phenomenon is especially true for handwritten kanji, which have many “strokes”.
In the case of characters consisting of , this tends to occur between the start or end point of a certain stroke and another line. For example, in the case of the handwritten kanji ``田'', the standard number of blank spaces separated by lines (the number of loops) is considered to be 4, but the number of blank spaces separated by lines (the number of loops) is considered to be 4. According to an analysis of the handwriting education kanji database ETL8, it has been reported that the number of loops is approximately evenly distributed from 0 to 4.

This indicates that the assumption of correspondence between serialized feature vectors does not hold in evaluating the degree of dissimilarity of two-dimensional figures that are complex and highly deformed, such as handwritten kanji.

[Purpose of the invention]

This invention was made to solve the above problem, and provides a pattern matching method that can quickly calculate the similarity between unsequential feature vector sets using the DP method. It is something.

[Summary of the invention]

In order to achieve the above object, this invention has the following objectives:
This is a pattern matching method that has functions (1), (2), and (3).

(1) By using straight line approximation (contour segment) of the boundary between white and black on both the input side and the mask side, information distortion is reduced compared to thinned figures, and corresponding candidate points are reduced compared to the original figure. decrease. The accuracy of the evaluation function is improved by using the directionality of the contour line segment for distance evaluation.

(2) The mask-side features are serialized (using the ordering of the contour as is), whereas the input-side features are basically treated as having no ordering, which makes it easier to cut lines. At the same time, by defining a set of line segments that can precede each contour line segment on the input side, we take advantage of the high-speed processing of DP and prevent unnatural correspondence.

(3) By evaluating not only the distance between contour lines but also the way in which the front and rear contour lines are connected, not only the amount of overlap but also the amount of distortion when space is distorted nonlinearly is included in the evaluation.

[Principle of the invention]

Next, the principle of the pattern matching method of the present invention will be explained.

First, the notation for the mask side feature is as shown in Equation (11), and for the input side feature, the following symbols are used: start point coordinate ω ^b _j , end point coordinate ω ^e _j , direction α _j , and length λ _j . In the above description, a set of line segments that can precede the mask side is defined, but in actual matching, this set Q is defined only on the input side.

Based on the above preparation, the recurrence formula corresponding to the above equation (7) can be written as g(i, j)=min{h ₁ (i, j), h ₂ (i, j),
h ₃ (i, j)} ...(13) Expressed as. h ₁ , h ₂ , and h ₃ in equation (13) are the correspondence evaluation quantities of a, b, and c shown in the correspondence diagram between mask line segment i and input line segment j in FIG. 4, and a is 1 vs.1(i
= i' vs. j = j'), b is 1 vs. 2 (i = i' vs. j' = j-1
，
j), c is 2 to 1 (i'=i-1, i to j'=j),
Further, M indicates a mask, and N indicates an input.

Now, if we compare the first term in min in Equation (7) and the equation for calculating h ₁ in Equation (14), the first difference is that in Equation (14), When finding h ₁ , j″∈
Min (minimization) processing is being performed on Q(j'). On the other hand, in equation (7), there is only one calculation term for j″=j−1.
In the case of dimensional series, it is guaranteed that i will occur after i-1 and j will occur after j-1, so when j corresponds to i, it will correspond to i-1. This is because it is only necessary to limit the opponent to j-1.

On the other hand, if it is not serialized, when j corresponds to i, all the partners corresponding to i-1
Since j″ must be taken into consideration, the condition j″∈Q(j′) is required. Here, Q(j') is the aforementioned set of line segments that can precede. Using such a subset rather than the set of all line segments as Q(j') speeds up the computation and eliminates unnatural correspondences.

The second difference is that there is a term γ,
In Equation (7), the distance between the correlated features is evaluated, but the distortion of C=(i, j) is not evaluated. As a result of distorting C=(i,j),
It is natural to think that even if there is a perfect match, the evaluation will be lower if there is a large amount of distortion. Therefore, in the evaluation at each time point, we define a function γ of the difference between the transition from j″ to j′ on the input side, which corresponds to the transition from i′−1 to i′ on the mask side, and define this amount of distortion as a characteristic. The sum added to the distance between the two is the comprehensive evaluation value.

Next, the distance between the above features (outline portions) is defined as follows.

In the above equation (15), the symbol ~ in d ₁ is the calculation of the angular difference, the result is between -π and π, and the coefficient 2/π is the unit when the angular difference becomes π/2. This is a coefficient to make the evaluation amount the same as the difference in length. Also,
For length, a difference of up to 2 times is allowed with an evaluation of 0. _d2 ,
In the case of d ₃ , the above distance is distributed proportionally by length.

Also, regarding the term γ, the corresponding line segment (A
The amount of distortion is evaluated from the positional relationship between the starting point of side i' and j' for side B and the end point of the previous line segment (i'-1 for side A and j'' for side B). and γ(i′−1, i′; j″, j′)=｜ω ^b _j ′−ω ^e _j ″
｜−｜Z ^b _i ′
−Z ^e _i ′ _-1 ｜｜……(16) is defined as follows.

Normally, the line segments on the mask side are continuous, so |Z ^b _i ′−Z ^e _i ′ ₋₁ |=0, but it is not 0 when moving from one contour to the next.

The initial conditions are h ₃ (i, j) = ∞ g (i'-1, j'') = 0 γ (i'-1, i', j'', j') = 0 i = 1 i' = 1 Let i'=1...(17).

The degree of difference based on the overall optimal correspondence between the mask side A and the input side B, which corresponds to the above equation (8), is D ₃ (A, B)=1/Σl _i min j{g(I, j)}... ...(18) is obtained.

In this way, the degree of dissimilarity expressed by equation (18)
When calculating _D3 , it is possible to correspond to the mask side even for the input side where the order of the series has changed, and the evaluation amount that takes into account the amount of line breaks can be calculated using the DP method. can be obtained quickly using

[Embodiments of the invention]

FIG. 5 is a block diagram for explaining the matching procedure according to an embodiment of the present invention.

In the same figure, h ₁ , h ₂ , and h ₃ are respectively (14th)
This is the calculation block for Eq. The data input to the calculation block _h1 are the characteristics a _i , l _i , | of the mask storage unit A.
Z ^b _i −Z ^e _i-1 |, characteristics α _j , λ _j , | of input buffer section B
ω ^b _j −ω ^e _j ″|, and the recursive evaluation g of the i-1st stage
(i-1, j″), j″∈Q(j). g(i-1,
j″) is stored in temporary memory block g _-1 .
Also, the data input to calculation block _h2 is
a _i , l _i , |Z ^b _i −Z ^e _i-1 |, α _p(j) , λ _p(j) , α _j , λ _j ,
｜ω ^b _p(j) −
ω ^e _j ″|, j″∈Q(P(j)) and g(i−1, j″) from block g _−1.Then , the data input to calculation block _h3 is Characteristics of A
a _i-1 , l _i-1 , a _i , l _i , |Z ^b _i-1 −Z ^e _i-2 | and the characteristics of input side B α _j , λ _j , |ω ^b _j −ω ^e _j ″ | and i-2-stage recursive evaluation g(i-2, j″), j″∈Q(j), and g(i
-2, j'') is stored in temporary memory block g _-2 .

The (14th) calculated block h ₁ , h ₂ , h ₃
The value of the formula is the minimum value calculation block of formula (13).
min ₁ , the recursive evaluation amount with each j in the i-th stage is calculated, and is sent to the temporary storage block g ₀ , completing the calculation of the i-th stage.

Next, in preparation for the calculation of the i+1th stage, first,
Send all the contents of g _-1 to g _-2 , then send all the contents of g ₀ to g _-1 . At this stage, memory block g _-1 has g
The value of (i,j) is stored in memory block g _-2 as g(i-
1, j) is entered, completing the preparation for the calculation of the i+1th stage.

The above is the operation related to the iterative calculation part by DP which forms the main part of this invention, but in order to explain the entire process, it is necessary to explain the initial value setting of equation (17) and the degree of difference in equation (18). It is necessary to supplement.
Therefore, the explanation will be given in order starting from the first stage. In addition,~
indicates each process. And ~ is a repetition.

First, before processing, the initial value setting block is
INIT sets all values of g _-1 to zero. This corresponds to the second equation of equation (17). In the calculation for the first mask line segment i=1, zero is supplied as the value of γ to blocks h ₁ and h ₂ , and ∞ is output from h ₃ . That is, block h ₁ outputs h ₁ (i, j) = l ₁ · d ₁ (1, j), and block h ₂ outputs h ₂ (i, j) = l ₁ · d ₂ (1, P (j), j) are output and their minimum value is calculated in block min ₁ . Note that during processing, ∞ is output from block _h3 in order to prevent the value of _h3 from being selected as the min ₁ output. Next, the recursive evaluation amount g in the first stage for each j calculated in the process
All (1, j) are sent to block g ₀ and stored,
The first stage calculation is completed, g _-1 is sent to g _-2 , and g ₀
is sent to g _-1 .

In the second stage calculation for the second mask line segment i=2, the values obtained during the above-mentioned normal iterative calculation are calculated in blocks _h1 and _h2 . On the other hand, in block _h3 , the values set in block g _-1 prior to the first stage have been transferred to block g _{-2, so all values in block g -2 are} zero ( (middle equation of equation (17)). Also No. (17)
From the third equation, the values of γ are also calculated assuming that they are all zero. Then, the results of h ₁ , h ₂ , and h ₃ are sent to block min ₁ , and the second stage recursive evaluation amount g (2, j) for each j is calculated and stored in block g ₀ . The second stage processing is completed, and the preparation for the third stage is completed after the data is moved from g _-1 to g _-2 and from g ₀ to g _-1 .

The iterative processing from the third stage onwards is as described above.
Finally, g(I, j)j=1~J in stage I is
, is calculated by iterating over j, and the block
min ₂ to find the minimum value for j in equation (18), which is divided by Σl _i to find the overall degree of dissimilarity D ₃ (A, B) based on the optimal correspondence.

It should be noted that the above is one embodiment of the present invention, and changes such as those described in (1) to (5) below and combination thereof are easily possible.

(1) In equation (14), the range of min is set to j″∈Q(j′) assuming that all line segments can be disconnected from the previous line, but at points where there is no possibility of disconnection,
Calculating with j″=P(j′) eliminates the need to minimize Equation (14) and speeds up the calculation.Specifically, when Figure 2 a is considered as a mask, For i′=2, 4, and 9, where there is a possibility of disconnection,
j″∈Q(j′) is used, but for other line segments j″=
This means using P(j').

(2) In equations (14) and (15), the length l _i of each line segment is made variable, so the weight of l _i is used in the calculation formula, but should it be fixed length? , or by using each contour point as is without performing line segment approximation, there is no need to consider the length.

That is, d ₁ , d ₂ , d ₃ in equation (15) can be rewritten as equation (9), and d can be written as d (i, j) = 2/π | α _j ~ a _i | can be simplified.

(3) Transforming equations (13) and (14), g(i, j) = ming′(i, j)+l _i d ₁ (i, j) g′(i, P(j) )+l _i d ₂ (i, j′, j) g′ (j‐1, j)+(l _i ′+l _i )d ₃ (i′, i, j) g′(i′, j′)= min j″∈Q(j′) {g(i′−1, j″)+γ(i′−
1, i′; j″j′)}.In other words, between the i-th stage and the i-1th stage,
By calculating g'(i', j') as an intermediate result, the calculation of γ and the calculation of d can be separated.

(4) Use, for example, a center line instead of an outline as a feature. Also, the evaluation d between the features in equation (15)
This is performed by adding higher-order features other than the angular difference, such as position information and line-to-line relationships.

(5) The DP processing described in the above embodiment is used only for associating line segments, and discrimination between patterns is performed using another evaluation function. In addition, DP processing is applied not to the entire contour but to each part of the contour.

〔Effect of the invention〕

As explained in detail above, according to the present invention, between feature vectors that are not serialized,
Dissimilarity, which allows topological deformations such as line breaks and performs global optimal evaluation, can be quickly determined using the DP method. Furthermore, by adding not only the distance between features but also spatial distortion to the evaluation quantity and defining a set of line segments that can be "preceded," we aim to speed up processing while eliminating unnatural correspondences. be able to. Further, the present invention is not only used as a degree of dissimilarity between contour feature vectors for character recognition, but is also excellent and can be widely applied to pattern recognition.

[Brief explanation of drawings]

Figure 1 is a diagram explaining the principle of DP matching between feature vectors that are sequenced like speech, Figure 2 a,
b is a diagram for explaining the outline line segment features used in this invention and how the series of line segments changes due to line breaks, and Figure 3 is a diagram showing the outline segment features and the "possible precedence" of the outline segment. An explanatory diagram of the contour line segment, Fig. 4a,
b and c are diagrams for explaining the operation at each stage of the DP matching of the present invention, and FIG. 5 is a block diagram for explaining the matching procedure of one embodiment of the present invention. In the figure, M is a mask, N is an input, h ₁ , h ₂ , h ₃ are calculation blocks, g ₀ , g _-1 , g _-2 are temporary storage blocks for recursive evaluation quantities, and INIT is an initial value setting block. ,
min ₁ and min ₂ are minimum value calculation blocks.

Claims (1)

[Claims] 1 Set of standard pattern features A = {A ₁ , A ₂ ,...
...A _i , ..., A _I };
Set of features of unknown input pattern B = {B ₁ , B ₂ ,...
...B _j , ..., B _J }, and one point of i'=i on the A side, or i'=
Two points i-1 and i and 1 of j'=j on the B side
a point, or a point j' before j, and means for calculating an evaluation quantity d of the distance between two features of j;
means for previously defining a part of the B for each j' as j'' that corresponds to the i'-1 when j'corresponds; and a transition from the i'-1 to i'; and,
Similarly, the evaluation amount r regarding the difference between the transition from j″ to j′
i-th (i=1, 2,...
..., during the calculation of the recursive evaluation quantity by dynamic programming in stage I); the above d, the above i' and j' in the calculation of this d, and the above j' are predetermined by the means defined above. In the calculation of d and r, (i'-
i, j″);
and the minimum value of the added values within the range of the means and definitions of i', j', j'' is set as the recursive evaluation g(i, j) of the optimal correspondence for i. A pattern matching method.