JPH0981687A - Stroke pattern matching device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To discriminate different line segments for which positions are largely shifted for unconnected line segments and to highly accurately match stroke patterns for which relative positional relation is not changed. SOLUTION: This stroke pattern matching device provided with a means 101 for inputting the stroke patterns as pictures and the means 102 for analyzing a structure from the stroke pattern obtained from the means 101 and detecting a feature point for realizing the matching of the stroke patterns by using features obtained from the means 102 is provided with the means 103 for describing the features of the feature point obtained in the means 102 and the features between the feature points, the means 104 for describing the features of the line segments divided by the feature point obtained in the means 102 and the features between the line segments, the means 105 for executing the matching of the stroke patterns by using the features described in the means 103, the means 106 for executing the matching of the stroke patterns by using the features described in the means 104 and the means 107 for generating a final matching result by using the output of both means 105 and means 106.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a line figure aligning apparatus for aligning line figures with each other, particularly for line figures which are time-series data of coordinates input online and line figures input as image data. The present invention relates to a line graphic matching device for matching a handwritten line graphic such as a handwritten character or a symbol in a handwritten drawing with another line graphic.

[0002]

2. Description of the Related Art Conventionally, this type of handwritten line drawing matching is used for recognizing handwritten characters. For example,
A method for line figure matching is described in "Japanese Patent Application No. 1-245507, Method for Extracting and Recognizing Line Figure, September 21, 1991" (JP-A-3-108079). This example will be described with reference to FIG. The image input from the image input unit 101 is converted into a skeleton line in the skeleton line extraction unit 201 and converted into a line figure having a width of 1 pixel. From the skeleton line, the line-graphic structure analysis unit 202 detects a branch point or an intersection point as a feature point, and the skeleton line is divided into line segments divided at the feature point. Furthermore, these line segments are described by the connection relationship between the direction and the line segments that are adjacent to each other with the feature point in between. The matching unit 203 executes matching with the model feature amount using the line segment direction and the connection relationship as the feature amount.

[0003]

In this conventional line figure matching apparatus, since only the relationship between the adjacent line segments is used as the relationship between the divided line segments, the positions of the line segments that are not connected are largely displaced. The different line segments are indistinguishable. For example, there is a problem that it cannot be distinguished from the case where the short line segment of the second stroke of "ya" is written apart from the first stroke and the line segment of the third stroke of "ka". It was

[0004]

SUMMARY OF THE INVENTION It is an object of the present invention to provide a highly accurate stroke pattern matching apparatus that executes stroke pattern matching using the relationship between line segments that are not directly connected.

For this reason, the stroke pattern matching device of the present invention is characterized in that the image input means for inputting the stroke pattern as an image and the feature point is detected by analyzing the structure from the stroke pattern obtained from the image input means. In a stroke pattern matching device that realizes stroke pattern matching using the point detection means and the characteristics obtained from the characteristic point detection means, the characteristics of the characteristic points obtained by the characteristic point detection means and the characteristics between the characteristic points Is described by the feature point description means, the line segment description means describing the feature of the line segment delimited by the feature points obtained by the feature point detection means and the feature of the line segment, and the feature point description means. Feature point matching means for performing stroke pattern matching using the feature and stroke pattern matching using the feature described by the line segment description means A line segment matching means for executing, using the output signal of said line segment matching means and the feature point matching means,
The above object is achieved by being configured with a matching control means for judging a matching result.

Further, the feature point matching means includes a relation score adding means for correcting a matching result by using a relationship between a plurality of feature points, and the line segment matching means uses a relationship between a plurality of line segments. And a line segment score adding means for correcting the matching result by using the matching result of the line segment matching means; The above-described object is also achieved by the minute matching means including the feature point score adding means for correcting the matching result using the matching result of the feature point matching means.

The matching control means corrects the score by using the magnitude relationship of the score of the matching result,
By repeatedly executing the feature point matching means and the line segment matching means to obtain a matching result,
The above objective has been achieved.

Further, there is provided image deforming means for deforming the original stroke pattern according to the matching result of the matching control means, and the image deforming means, the characteristic point detecting means, the characteristic point describing means, and the line segment. The description means, the feature point matching means, the line segment matching means, and the matching control means are repeated.
The above object is also achieved by being able to drive.

Further, in the present invention, the image input means is
By inputting a stroke pattern as online data that is a sequence of coordinate points, and including feature point detecting means for detecting a feature point by analyzing the structure from the online stroke pattern obtained from the image input means, the stroke as online data is obtained. For the pattern, the above-mentioned purpose is achieved.

[0010]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, the present invention will be described with reference to FIGS.
9 to 9 will be described. FIG. 1 is a block diagram showing an embodiment of the present invention. The first embodiment of the present invention has an image input unit 101 and a feature point extraction unit 102.
A feature point description unit 103, a line segment description unit 104, a feature point matching unit 105, a line segment matching unit 106, and a matching control unit 1
07 and an output terminal 108.

A line graphic image input from an image input unit 101 such as a scanner is subjected to preprocessing such as noise removal and binarization processing, and then obtained as a binary line graphic image. Transferred.

In this embodiment of the feature point detection unit 102, the line graphic image is thinned first. Although any thinning method may be used, a method described in, for example, "Fukinori Takahiko: Signal processing of images for FAX, OA, pp. 40-43" is known. In this case, the thinning will be described as being performed according to the rule of eight connections. The 8-connection means that adjacent pixels in the diagonal direction are also connected in addition to the pixels on the upper, lower, left and right sides. The number of connections of each pixel of the image thinned by 8 connections is examined. When the number of connected black pixels is checked, the number of black pixels of eight pixels around the pixel is checked and set as the connected number. Here, the connection number represents the number of line segments connected to the pixel. When the number of connections is 1, the pixel is set as an end point. When the number of connections is 2, the pixel is a point on the line segment and is not a feature point. When the number of connections is three or more, it means that three or more line segments intersect at that point. Points with 3 or more connections are also feature points. FIG. 6 shows an example in which the feature points of katakana “ki” are detected. Points 601, 602, 604, 605,
Points 607 and 608 are end points. Points 603 and 606
Is the intersection. At the same time, a line segment is defined by the feature points. FIG. 7 shows an example of a line segment detected from the katakana “ki”. Line segment 701, line segment 702, line segment 703, line segment 70
Four line segments 705, 706, and 707 are detected. The set of detected feature points and the set of line segments are the feature point description unit 103 and the line segment description unit 1.
04.

The feature point description unit 103 obtains the detected feature points, the respective feature amounts, and the feature amount of the relationship between the feature points. In this embodiment, the type and coordinates of the characteristic point are used as the characteristic amount of the characteristic point. Here, the type of feature point is any one of an end point, a bending point, and an intersection point in this embodiment. The number of line segments to be connected, the line segment number to be connected, the number of feature points connected with the line segment sandwiched between them, and the number of feature points that are not connected but are adjacent to each other and the distance to the feature point are used. For example,
In the case of the point 603 in FIG. 6, the feature point type is the intersection and the coordinates are (40, 30). However, the size of the image is 100 pixels horizontally and 100 pixels vertically. The number of line segments to connect is 4, and the number of line segments to connect is the line segment in FIG.
01, a line segment 702, a line segment 703, and a line segment 704. In addition, the characteristic points connected by sandwiching the line segment are points 60 in FIG.
1, point 602, point 604, and point 606. FIG.
In the example of the point 603, the points 605 and 607 are adjacent points. The distances from the point 603 to those points are 35 pixels and 45 pixels. In this embodiment, the distance between feature points is set to 50 pixels or less as the condition of proximity. In the example of the characteristic point 801 in FIG. 8, the end point 802 is also included as the near point, and the distance to that point is 5 pixels.

In the line segment description unit 104, the feature amount of the line segment itself is calculated from the input feature point list and the line segment list,
Find the relationship between line segments. The characteristics of the line segment itself are the length of the line segment, the direction of the line segment, the cumulative curvature of the line segment, and the type of line segment. In this embodiment, since the line segment is a thin line according to the 8-adjacent rule, the length of the line segment can be obtained by counting the number of black pixels in the line segment. The direction of the line segment is represented by the direction between the end points of the line segment. When the vectors between the end points of the line segment are (X1, Y1) and (X2, Y2), the direction between the end points can be calculated by the equation (1) below.

D = ArcCos ((X1 * X2 + Y1 * Y2) / (Norm (X1, Y1) * Norm (X2, Y2)) (1) Here, ArcCos (x) represents an inverse function of the Cos function. The unit is radian and Norm
(X, y) represents the norm of the vector (x, y).

Further, in this embodiment, since the line segment is thinned by the rule of 8 adjacency, the direction of each pixel in the line segment is 0 degree to the right and 0 degrees when the angle is set counterclockwise. π /
4, π / 2, 3π / 4, π, 5π / 4, 3π / 2, 7π
There are eight directions of / 4. Starting from one end of the line segment, the direction of adjacent pixels is examined. 2 adjacent for convenience
The direction between pixels is the direction of the pixel closer to the processing start feature point. Further, the difference in the direction of adjacent pixels is obtained. The direction of the pixel closer to the processing start feature point is subtracted from the direction of the pixel farther from the processing start feature point to obtain the direction change amount between pixels, that is, the curvature. However, when the value of the curvature is smaller than −π, the value obtained by adding 2π to the value is the curvature. When the curvature is larger than π, the value obtained by subtracting 2π from the value is the curvature. The curvature is the curvature of the pixel farther from the start pixel. The curvature of each pixel is obtained as described above. However, the curvature is not found at both end points of the line segment, and the curvature is set to 0. The sum of the curvatures of all the points on the obtained line segment is calculated to obtain the cumulative curvature. When the absolute value of the cumulative curvature is smaller than the curvature T, the type of this line segment is a straight line segment. If the cumulative curvature is greater than or equal to the threshold value T, it is a positive curve. In addition, when the cumulative curvature is −T or less, it is a negative curve. Further, when the line segment length is 2 or more and the start point and the end point of the line segment match, this line segment is set as a loop. If the distance between both ends is S and the length of the line segment is L, then if S / L is less than or equal to the threshold value U and the cumulative curvature is greater than or equal to the threshold value V, this line segment is It is a pseudo loop. In this embodiment, the threshold value T is π / 8, the value of the threshold value U is ⅓, and the threshold value V is π, but these values are not essential problems. Can be any value. When a pseudo loop is detected, the pseudo loop is divided into two at the center point of the line segments that form the pseudo loop, and the two points are divided into two line segments. A line segment is added and described, and the feature point description unit 103 and the line segment description unit 104 are corrected.

Then, the line segment description section 104 describes the relationship between the line segments. In this embodiment, the number of line segments sandwiched between two line segments is used as the relationship between the line segments. As a method of obtaining the number of line segments sandwiched between the present embodiment, the midpoints of two line segments are connected by a line segment, and the number of other line segments through which the line segment between the midpoints passes is obtained. First, an image area having the maximum number of pixels of the pattern is secured, and the value of each pixel is set to zero. Draw all line segments in the image. In this case, a value is substituted for each pixel of each line segment. The value in that case shall be the line segment number. In order to obtain the relationship between two line segments, a line segment is drawn from the midpoint of one line segment to the midpoint of another line segment, and the pixel value on the line segment in the image is examined. Thereby, it is checked whether or not each pixel on the line segment between the midpoints of the two line segments is on another line segment. If the line segment passes through another line segment, the line segment number is stored. After connecting the midpoints of the two line segments with a line segment, the number of the line segment that has passed is checked, and if there is no line segment that has passed, the two line segments are considered to face each other. When one type of line segment number is obtained, it is considered that one line segment exists in the two line segments, and the line segment number is stored. In this embodiment, only the case where the number of line segments existing between two line segments is 0 and 1 is stored, but it can be easily expanded even when two or more line segments exist in the line segment. FIG. 9 shows an example of the relationship between the line segments when there is no other line segment in the line segment. Arrow
It is shown by connecting related line segments. For example, line segment 9
01 and the line segment 902 are linked and stored in the line segment relationship 903.

Further, in the present embodiment, the pixel value on the line segment between the midpoints of the two line segments was examined in order to check the number of line segments existing in the two line segments. It can be obtained by drawing four line segments by the combination of the end points, checking the pixel values on the line segments, and obtaining the number of other line segments existing in the line segments. Similarly, the pixel values on the five line segments between the midpoints of the two line segments of this embodiment and between the end points of the two line segments of another embodiment are checked,
It is also possible to obtain the number of other line segments existing in the line segment.

The operation of the feature point matching unit 105 and the line segment matching unit 106 will be described with reference to FIGS. 10 to 13. It is assumed that the feature point matching unit 105 stores the feature point dictionary data of a plurality of categories in the dictionary data storage unit 1204 of FIG. The feature point dictionary data of a particular pattern in a particular category is selected, and matching with the data in the feature point description unit 103 is executed. The feature point dictionary data stored in the dictionary data storage unit 1204 is the feature point description unit 10
Similar to the feature point data generated in 3, the feature point type and coordinates for the dictionary data are used. Furthermore, it is assumed that the dictionary data storage unit 1204 of the feature point matching unit 105 also stores the weight value representing the importance of each feature point. In the feature point matching unit 105, when changing the type of the feature described in the feature point description unit 103,
Must be modified to use the same features.

Similar to the feature point matching unit 105, the line segment matching unit 106 stores the line segment dictionary data of a plurality of categories as shown in FIG.
It is assumed that the dictionary data is stored in the dictionary data storage unit 1304. The line segment dictionary data of a specific pattern in a specific category is selected to execute matching with the data in the line segment description unit 104. The line segment dictionary data stored in the dictionary data storage unit 1304 is similar to the line segment data generated by the line segment description unit 104, and the length of the line segment, the direction of the line segment, the cumulative curvature of the line segment, And the line segment type are stored. further,
It is assumed that the dictionary data storage unit 1304 also stores a weight value indicating the importance of each line segment. In the line segment matching unit 106, the line segment description unit 10
When changing the type of the feature described in 4, it is necessary to change to use the same feature.

The simple matching unit 120 in the feature point matching unit 105.
In 1, the matching score of all the feature points of the input pattern and all the feature points in the selected dictionary pattern is calculated. The characteristic point of the input pattern is Ix, and the characteristic point in the selected dictionary pattern is Djy. x is a serial number of feature points in the input pattern. Further, j represents the number of the pattern in the dictionary. Further, y is a serial number of feature points in the jth dictionary pattern. In this embodiment, the characteristic of the characteristic point is the type and coordinates of the characteristic point, and the data of the x-th characteristic point is Px, Ux, and Vx. Similarly, the data of the feature points in the dictionary pattern is Pj.
It was set to y, Ujy, and Vjy. In the feature point matching unit 105,
The matching degrees Sx, jy between all the feature points of the input pattern and all the feature points of the dictionary pattern are obtained according to the calculation of the equation (2). The obtained score is stored in the feature point score storage unit 1205 in FIG.

S (Ix, Djy) = Wpjy * Sp (Px, Pjy) + Wujy * Su (Ux, Ujy) + Wvjy * Sv (Vx, Vjy) (2) Here, Wpjy, Wujy, and Wvjy are characteristic points. Dictionary data storage unit 1 as a weight value indicating the importance of the data
It is assumed that it is stored in 204. In the present embodiment, these load values are set to a constant value of 1. However, this is not an essential problem, any value may be used, and it may be changed for each data in the dictionary pattern. In addition, Sp (Px,
Pjy), Su (Ux, Ujy), Sv (Vx, Vj
y) is a function that gives the distance between the data in the input pattern and the data in the dictionary pattern. Sp is for expressing a shift between types of feature points as a score, and stores scores in all the types and all types as a table and stores them in the dictionary data storage unit 1204. To do. In the present embodiment, Px and Pj of Sp (Px, Pjy)
The tables were set to return 100 if y were of the same type and 50 if they were of different types. This table generation method is not an essential problem of the present invention, and any table may be generated. Su (Ux, Uj
Similarly, for y), the score can be obtained from the table by the combination. In another example, Su (A
Su may be defined as BS (Ux−Ujy)) as a function of the absolute value of the difference between Ux and Ujy. In this case,
In the embodiment in which the maximum value is 100, Su = 100-10
It can be 0 * ABS (Ux-Ujy) / I, but the definition of this function may be any as long as the maximum is 100 and the minimum is 0. However, I in this embodiment represents the maximum horizontal size of the input pattern. Sv
The example of (Vx, Vjy) is realized with the same configuration as the example of Su (Ux, Ujy).

Subsequently, the relationship score adding unit 1202 in the feature point matching unit 105 corrects the score using the relationship between the feature points. In this embodiment, the feature points that are close to the connected feature points are represented in a table as shown in FIG. In FIG. 10, connected feature point pairs are represented by −1, and adjacent feature point pairs indicate the distance between the feature points. With feature point pairs,
When the element is 0, the numeral is not entered in FIG. 10, but the element is not connected and is not in proximity. When the matching process between the feature points is completed, the matching control unit 107 sends a signal to the relationship score adding unit 1202 in the feature point matching unit 105 to correct the score using the relationship between the feature points. The correction of the score shall be performed in the order of the numbers of the feature points of the dictionary pattern. This order may be arbitrary or may be carried out in parallel. J th
For the feature point Djy in the th dictionary pattern, a set of feature points to be connected is G1jy, and the number of feature points, which is the number of elements, is n1jy. Similarly, for the feature point Djy, a set of adjacent feature points is G2jy, and the number of feature points, which is the number of elements of the feature point Djy, is n2jy. The elements of these sets are obtained from the table showing the feature point relationships illustrated in FIG. Similarly, it is assumed that the relationship between the feature points of the input pattern has already been obtained and expressed as a table, and for the x-th feature point Ix in the input pattern, the set of feature points to be connected is G3x, The number of feature points connected to the feature point Ix, which is the number of elements, is n3x. Similarly, the feature point I
For x, the set of adjacent feature points is G4x, and the number of feature points, which is the number of elements, is n4.
Let x. The corrected value S '(Ix, Dj of the score at that time)
y) is calculated using the following equations (3), (4), and (5). The S (Ii, Dd) used for the correction is read from the feature point score storage unit 1205.

S1 (Ix, Djy) = SUM (Dd is included in G1jy, MAX (S (Ii, Dd), Ii is included in G3x)) / nijy (3) where SUM (A, B ) Represents the total sum of B under the condition of satisfying A, and MAX (B, A) represents the maximum value of B under the condition of satisfying A.

S2 (Ix, Djy) = SUM (Dd is included in G2jy, MAX (S (Ii, Dd), Ii is included in G4x)) / n2jy (4) Here, SUM (A, B) ) Represents the total sum of B under the condition of satisfying A, and MAX (B, A) represents the maximum value of B under the condition of satisfying A.

S ′ (Ix, Djy) = W1 * S1 (Ix, Djy) + W2 * S2 (Ix, Djy) (5) Here, W1 and W2 represent load values at the time of addition, and In the embodiment, W1 is set to 0.3 and W2 is set to 0.2, but this is not an essential problem and any value may be used.

After obtaining and obtaining all S '(Ix, Djy) using the above equations (3), (4) and (5), further calculation according to the following equation (6) Gives the score S (I
x, Djy) is corrected.

S (Ix, Djy) = W3 * S (Ix, Djy) + S '(Ix, Djy) (6) However, although W3 is 0.5 here, any value may be used.

Next, the operation of the line segment matching section 106 will be described. The line segment matching unit 106 calculates matching scores for all line segments of the input pattern and all line segments in the selected dictionary pattern. Let Ex be the line segment of the input pattern,
The line segment in the selected dictionary pattern is set as Fjy. x
Is the serial number of the line segment in the input pattern. Also,
j represents the pattern number in the dictionary. In addition, y is the serial number of the line segment in the jth dictionary pattern.
In the present embodiment, the characteristics of the line segment are the length of the line segment, the line segment direction, the cumulative curvature of the line segment, and the line segment type,
The data Lx, Ox, Cx, Tx for the x-th line segment were used. Similarly, the data of the line segment in the dictionary pattern can be converted into Lfy, O
It was set to zy, Czy, and Tzy. The simple matching unit 1301 in the line segment matching unit 106 finds the matching Rx, jy between all the line segments of the input pattern and all the line segments of the dictionary pattern according to the calculation of Expression (7). The resulting score is stored in the line segment score storage unit 1305.

R (Ix, Djy) = WLjy * RL (Lx, Ljy) + Woj * RO (Ox, Ojy) + Wcjy * Rc (Cx, Cjy) + WTjy * RT (Tx, Tjy) (7) where WLjy, WOjy, WCjy, WTjy are
It is assumed that the weight value represents the importance of the data of the line segment and is stored in the line segment matching unit 106. In the present embodiment, these load value values are set to a constant value of 1, but this is not an essential problem and may be any value, or may be changed for each data in the dictionary pattern. RL (Lx, Lj
y), RO (Ox, Ojy), RC (Cx, Cjy),
RT (Tx, Tjy) is a function that gives the distance between the data in the input pattern and the data in the dictionary pattern. RT
Is for expressing the deviation between the types of line segments as a score, and it is assumed that scores are defined between all types and all types and stored as a table in the dictionary data storage unit 1304. . In this embodiment, RT (Tx, Tj
1 if Tx and Tjy in y) are the same type
The table was set to return 00 and 50 for different types. This table generation method is not an essential problem of the present invention, and any table may be generated.

RL (Lx, Lj of the line segment matching unit 106
Similarly, for y), RO (Ox, Ojy), and RC (Cx, Cjy), the score can be obtained from the table by combining the respective arguments. In another embodiment, RL (ABS (Lx-Ljy)) is used as Lx and L.
RL may be defined as a function of the absolute value of the j y difference.
In this case, in the embodiment in which the maximum value is 100, RL =
It can be 100-100 * ABS (Lx-Ljy) / Lx, but the definition of this function can be any as long as it has a maximum of 100 and a minimum of 0. However, in this example, when RL was smaller than 0, RL was set to 0. Similarly, as another example of RO (Ox, Ojy), RO (Ox, Ojy) = 100-2.
It can also be set to 00 * ABS (Ox-Ozy-nπ) / π. However, n is an appropriate natural number that changes Ox-Ozy-nπ from -π / 2 to π / 2. Similarly, RC
Another example of (Cx, Cjy) is RC (Cx,
Cjy) = 100-100 * ABS (ABS (Cx)-
It may also be ABS (Cjy)) / ABS (Cx).

Then, the matching control unit 107 confirms the end of the processing of the simple matching unit 1301 and transfers a signal for carrying out the matching of the relationship between the line segments to the relationship score adding unit 1302. The relation score adding unit 1302 receives the signal and calculates the matching score using the relation between the line segments. In this embodiment, in order to describe the relationship between line segments,
A table as shown in FIG. 11 was used. It is assumed that the line segment relation table of the input pattern has already been obtained by the line segment description unit 104. Further, it is assumed that the table of the relationship between the line segments of the dictionary pattern is obtained in advance and stored in the dictionary data storage unit 1304. Regarding the line segment Fjy in the j-th dictionary pattern, a set of opposing line segments, that is, a line segment in which the number of line segments existing between them is 0 is set as G5jy, and the number of elements thereof is set as n5jy. The elements of these sets are obtained from the table showing the relationship between the line segments illustrated in FIG. Similarly, it is assumed that the relationship between the line segments of the input pattern has already been obtained and expressed as a table, and the line segment E in the x-th input pattern is
For x, a set of facing line segments, that is, a line segment in which the number of line segments existing between them is 0 is defined as G6x, and the number of elements thereof is n6.
Let x. Similarly, regarding the line segment Ex, a set of line segments having the number of line segments existing between them is 1 is G7x, and the number of elements thereof is n7x. Corrected value of the score at that time R '(Ex, F
jy) is obtained using the following equations (8), (9) and (10). The R (Ei, Fd) used for the correction is read from the line segment score storage unit 1305.

R1 (Ex, Fjy) = SUM (Fd is included in G5jy, MAX (R (Ei, Fd), Ei is included in G6x)) / n5jy (8) where SUM (A, B ) Represents the total sum of B under the condition of satisfying A, and MAX (B, A) represents the maximum value of B under the condition of satisfying A.

R2 (Ex, Fjy) = SUM (Fd is included in G5jy, MAX (R (Ei, Fd), Ei is included in G7x)) / n5jy (9) where SUM (A, B ) Represents the total sum of B under the condition of satisfying A, and MAX (B, A) represents the maximum value of B under the condition of satisfying A.

R '(Ex, Fjy) = W4 * R1 (Ex, Fjy) + W5 * R2 (Ex, Fjy) (10) Here, W4 and W5 represent load values at the time of addition, and the present embodiment In the example, W4 is set to 0.5 and W5 is set to 0.3, but this is not an essential problem and any value may be used.

After obtaining and obtaining all R '(Ex, Fjy) using the above equations (8), (9) and (10),
By the calculation according to the following equation (11), the score R (Ex,
Fjy) is modified.

R (Ex, Fjy) = W6 * R (Ex, Fjy) + R '(Ex, Fjy) (11) Here, W6 is set to 0.5, but may be any value.

Corrected line segment score R (Ex, Fjy)
Is stored in the line segment score storage unit 1305. When the processing of the relation score adding unit 1302 is completed for all combinations of line segments, the matching control unit 107 sends a signal to the line segment score adding unit 1203, and the line segment score adding unit 1203.
Reads out the line segment score from the line segment score storage unit 1305 in the line segment matching unit 106, and outputs the feature point score storage unit 120.
The feature point score stored in 5 is corrected.

Regarding the feature point Djy in the jth dictionary pattern stored in the dictionary data storage unit 1204, a set of feature points to be connected is G1jy, which is the number of elements.
The number of feature points connected to the feature point Djy is n1jy.
The elements of these sets are obtained from the table showing the feature point relationships illustrated in FIG. Further, the line segment connected to the feature point Djy is obtained from the line segment list connected to the feature point in the table shown in the embodiment of FIG. 10 and is set to F (Djy, Dd). However,
Dd is an element of G1jy, and F (Djy, Dd)
Represents the number of a line segment whose endpoints are Djy and Dd. Similarly, it is assumed that the relationship between the feature points of the input pattern has already been obtained and expressed as a table, and for the feature point Ix in the x-th input pattern, a set of feature points to be connected is G3x, The number of feature points connected to the feature point Ix, which is the number of elements, is n3x. At that time, the feature point Ix
The line segment connected to is obtained from the line segment list connected to the feature points in the table shown in the embodiment of FIG. 10 and is designated as E (Ix, Ii). However, Ii is an element of G3x, and E (Ix,
Ii) represents the number of a line segment whose endpoints are Ix and Ii.

Correction of the score S (Ix, Djy) in the feature point score storage unit 1205 in the line segment score addition unit 1203 is executed by calculation according to the following formulas (12) and (13).

S4 (Ix, Djy) = SUM (Dd is included in G1jy, MAX (R (E (Ix, Ii), F (Djy, Dd)), Ii is included in G3x)) / nijy (12 ) Where SUM (A, B) represents the total sum of B under the condition of satisfying A, and MAX (B, A) represents the maximum value of B under the condition of satisfying A. And S (Ix, Djy) = W7 * S (Ix, Djy) + W8 * S4 (Ix, Djy) (13) Here, W7 and W8 are 0.5 respectively,
Any value will do.

The line segment score addition unit 1203 stores all (Ix, Djy) stored in the feature point score storage unit 1205.
After performing the correction processing of the value based on the above equation (13), the matching control unit 107 sets the line segment matching unit 1
A signal is sent to the feature point score addition unit 1303 in 06 to execute the correction processing of the line segment score.

For the line segment Fjy in the jth dictionary pattern stored in the line segment score storage unit 1305, the characteristic point numbers of the end points of the line segment are G1jy and G2jy.
The elements of these sets are obtained by obtaining the end point numbers of the line segment from the table shown in FIG. Similarly, it is assumed that the relationship between the line segments of the input pattern has already been obtained and expressed as a table, and for the line segment Ex in the x-th input pattern, the feature point numbers of the end points of the line segment are set. I1x and I2
Let x. At that time, the correction of the score R (Ex, Fjy) stored in the line segment score storage unit 1305 is performed by the following equation (1)
4), the calculation is performed according to the equation (15).

R4 (Ex, Fjy) = (S (I1x, D1jy) + S (I2x, D2jy)) / 2 (14) R5 (Ex, Fjy) = (S (I1x, D2jy) + S (I2x, D1jy)) / 2 (15) R6 (Ex, Fjy) = MAX2 (R4 (Ex, Fjy), R5 (Ex, Fjy)) (16) where MAX2 (A, B) is one of A and B. The larger value shall be represented.

R (Ex, Fjy) = W9 * R (Ex, Fjy) + W10 * R6 (Ex, Fj y) (17) Here, W9 and W10 are 0.5 respectively, but what value But it's okay.

After the above processing is completed for all combinations of Ex and Fjy stored in the line segment score storage unit 1305 and the obtained scores are stored in the line segment score storage unit 1305, the matching control unit 107 , Feature point score storage unit 1
The feature point score S (Ix, Djy) is read from 205.

First, the maximum value in S (Ix, Djy) is obtained. Using Ix and Djy at that time, S (Ix,
Replace the value of Dd) with 0. Here, Dd indicates a feature point number of a dictionary pattern other than Djy. In addition, S (Ii,
Replace the value of Djy) with 0. Here, Ii indicates the feature point numbers of all input patterns other than Ix. After this correction, the maximum value in S (Ix, Djy) is calculated and S (I
x, Dd) and S (Ii, Djy) are modified. This process is repeatedly executed a small number of times out of the number of feature points of the input pattern and the number of feature points of the dictionary pattern, and S
Correct (Ix, Djy). After the completion of this correction process, the sum of the element values included in S (Ix, Djy) is obtained and is set to S.

Subsequently, the matching control unit 107 determines the line segment score R
(Ex, Fjy) is read from the line segment score storage unit 1305 in the line segment matching unit 106. First, the matching control unit 107
Calculates the maximum value of R (Ex, Fjy). E at that time
The value of R (Ex, Fd) is replaced with 0 using x and Fjy. Here, Fd indicates a line segment number of a dictionary pattern other than Fjy. Further, the value of R (Ei, Fjy) is replaced with 0. Here, Ei indicates the line segment numbers of all input patterns other than Ex. After this correction, the maximum value among R (Ex, Fjy) is calculated, and R (Ex, Fd) and R (Ei, F
jy) correction. This process is repeatedly executed a small number of times of the number of line segments of the input pattern and the number of line segments of the dictionary pattern to correct R (Ex, Fjy). After the completion of this correction process, the total sum of the element values included in R (Ex, Fjy) is calculated and set as R. Finally, the matching control unit 107 calculates and obtains S + R to obtain the matching score between the input pattern and the j-th dictionary data. The matching control unit 107 executes matching of all the dictionary data with the input pattern, and outputs the category name of the dictionary data having the maximum score from the terminal 108. In the present embodiment, the final matching result is obtained by using both the values of S and R, but the category name of the dictionary data giving the maximum value may be output from the terminal 108 by using only S. Also, using only R,
The terminal name is the dictionary data category name that gives the maximum value.
You may output from 8.

Next, another embodiment of the present invention will be described with reference to FIGS. 1, 14, and 15.

The line graphic image input from the image input unit 101 such as a scanner is obtained as a binary line graphic image after preprocessing such as noise removal and binarization processing, and is sent to the feature point detection unit 102. Transferred.

The feature point detection unit 102 detects the feature points of the line figure. The detailed description thereof is the same as the description of the first embodiment, and will be omitted.

The set of feature points and the set of line segments detected by the feature point detection unit 102 are the feature point description unit 103 and the line segment description unit 1.
04. The feature point description unit 103 obtains the detected feature points, the respective feature amounts, and the feature amount of the relationship between the feature points. In the line segment description unit 104, the feature amount of the line segment itself is calculated from the input feature point list and the line segment list,
Find the relationship between line segments. The detailed description of the feature point description unit 103 and the line segment description unit 104 is also the same as the description of the first embodiment of the first invention, and therefore will be omitted here.

Next, the feature point matching unit 105 and the line segment matching unit 1
06 and the embodiment of the matching control unit 107 will be described with reference to FIGS.
5 is performed. It is assumed that the feature point matching unit 105 stores the feature point dictionary data of a plurality of categories in the dictionary data storage unit 1204 of FIG. The feature point dictionary data of a particular pattern in a particular category is selected, and matching with the data in the feature point description unit 103 is executed. The feature point dictionary data stored in the dictionary data storage unit 1204 is the same as the feature point data generated by the feature point description unit 103, and is the feature point type and coordinates for the dictionary data. Furthermore, it is assumed that the dictionary data storage unit 1204 of the feature point matching unit 105 also stores the weight value representing the importance of each feature point. In the feature point matching unit 105, when changing the type of feature described in the feature point description unit 103, it is necessary to change so that the same feature is used.

Similar to the feature point matching unit 105, the line segment matching unit 106 stores the line segment dictionary data of a plurality of categories as shown in FIG.
It is assumed that the dictionary data is stored in the dictionary data storage unit 1304. The line segment dictionary data of a specific pattern in a specific category is selected to execute matching with the data in the line segment description unit 104. The line segment dictionary data stored in the dictionary data storage unit 1304 is similar to the line segment data generated by the line segment description unit 104, and the length of the line segment, the direction of the line segment, the cumulative curvature of the line segment, And the line segment type are stored. further,
It is assumed that the dictionary data storage unit 1304 also stores a weight value indicating the importance of each line segment. In the line segment matching unit 106, the line segment description unit 10
When the type of the feature described in 4 is changed, it is necessary to change the dictionary data so that the same feature is used.

Simple matching section 120 in feature point matching section 105
In 1, the matching score of all the feature points of the input pattern and all the feature points in the selected dictionary pattern is calculated. The detailed description is the same as that of the simple matching unit 1201 in FIG. 12, and thus will be omitted here. The generated matching score is stored in the feature point score storage unit 1205.
After obtaining the matching score for all combinations of feature points, the matching control unit 108 outputs the signal to the relation score adding unit 12
02 to activate. The relationship score adding unit 1202 in the feature point matching unit 105 corrects the feature point score using the relationship between the feature points. The embodiment is the same as that of the relationship score adding unit 1202 of FIG. 12, and thus will be omitted here.

After the processing of the relation score adding unit 1202 is completed, the matching control unit 108 activates the simple matching unit 1301 in the line segment matching unit 106. Similar to the feature point matching unit 105, the line segment matching unit 106 is assumed to store the line segment dictionary data of a plurality of categories in the dictionary data storage unit 1304 of FIG. The line segment dictionary data of a specific pattern in a specific category is selected to execute matching with the data in the line segment description unit 104. The description of the embodiment of the simple matching unit 1301 is the same as that of the embodiment of FIG. After obtaining matching scores for all combinations of line segments and storing them in the line segment score storage unit 1305, the matching control unit 108 outputs signals to the relationship score addition unit 1
It transmits to 302 and starts. The relationship score adding unit 1302 in the line segment matching unit 106 corrects the line segment score using the relationship between the line segments. The embodiment is the same as that of the relation score adding unit 1302 in FIG. 13, and therefore will be omitted here. The corrected line segment score is stored in the line segment score storage unit 1305.

When the processing of the relation score adding unit 1302 is completed for all combinations of line segments, the matching control unit 107 sends a signal to the line segment score adding unit 1203, and the line segment score adding unit 1203 The line segment score is read from the line segment score storage unit 1305 in the matching unit 106, and the feature point score stored in the feature point score storage unit 1205 is corrected. Since this embodiment is the same as the embodiment of the line segment score adding unit 1203 in FIG. 12, description thereof will be omitted. The line segment score addition unit 1203 performs the score correction processing on all the feature point combinations stored in the feature point score storage unit 1205, and then the matching control unit 107
A signal is sent to the feature point score addition unit 1303 in the line segment matching unit 106 to perform the line segment score correction processing. Since the embodiment of the feature point score adder 1303 is the same as the embodiment of the feature point score adder 1303 of FIG. 13,
Here, the description is omitted.

When the processing of the feature point score adding unit 1303 is completed, the matching control unit 107 causes the score changing unit 1406.
To send a signal to start. The score changing unit 1406 uses the feature point score storage unit 1205 to extract the feature point score S (Ix,
Dji) is read sequentially.

When S (Ix, Djy) is targeted, S
The value comparison with (Ix, Dd) is performed according to equation (18). Here, Dd indicates a feature point number of a dictionary pattern other than Djy. The value of S (Ii, Djy) is compared with the expression (1
Follow 9). Here, Ii indicates the feature point numbers of all input patterns other than Ix.

S (Ix, Djy) -S (Ix, Dd)> K, (18) Dd is a feature point number of all dictionary patterns other than Djy S (Ix, Djy) -S (Ii, Djy)> K (19) Ii is a feature point number of all input patterns other than Ix Here, in the present embodiment, the value of K is set to 20, but this value may be any value. The above equation (18) and equation (1
If S (Ix, Djy) that satisfies 9), then S (I
Correct the value by adding K'to (x, Djy). In the present embodiment, the value of K'is set to 20, but this value may be any value. Further, in this embodiment, the corrected S (Ix, Dj
When y) exceeds 100, the value of S (Ix, Djy) is set to 100. Next, S (Ix, Dd) and S (I
i, Djy) correction. In the present embodiment, K ″ is subtracted from the value of S (Ix, Dd) for correction.
K ″ is subtracted from the value of (Ii, Djy). In the present embodiment, the value of K ″ is set to 30, but this value may be any value. In this embodiment, the corrected S (Ix, D
When the value of d) or S (Ii, Djy) is smaller than 0, the value is set to 0. This process is repeatedly executed for all S (Ix, Djy) that satisfy equations (18) and (19). After the processing of the score changing unit 1406 is completed, the matching control unit 107 outputs the signal to the score changing unit 1406.
Send to 506 and start.

The score changing unit 1506 sequentially reads the line segment scores R (Ex, Fjy) from the line segment score storage unit 1305. R (Ex, Fd) and R (Ei, Fjy) R (E
When x, Fjy) is a target, the value is compared with R (Ex, Fd) according to equation (20). Where Fd is F
It refers to the line segment number of a dictionary pattern other than jy. R (Ei,
Fji) is compared with the value according to equation (21). Here, Ei indicates the line segment numbers of all input patterns other than Ex.

R (Ex, Fjy) -R (Ex, Fd)> K, (20) Fd is the line segment number of all dictionary patterns other than Fjy R (Ex, Fjy) -R (Ei, Fjy)> K (21) Ei is the line segment number of all input patterns other than Ex Here, in the present embodiment, the value of K is set to 20, but this value may be any value. The above equation (20) and equation (2
In the case of R (Ex, Fjy) satisfying 1), R (E
x, Fjy) is added to K'to correct the value. In the present embodiment, the value of K'is set to 20, but this value may be any value. In the present embodiment, the corrected R (Ex, Fj
When y) exceeds 100, the value of R (Ex, Fjy) is set to 100. Next, R (Ex, Fd) and R (E
i, Fjy) correction. In the present embodiment, K ″ is subtracted from the value of R (Ex, Fd) for correction.
K ″ is subtracted from the value of (Ei, Fjy). In the present embodiment, the value of K ″ is 30, but this value may be any value. Further, in this embodiment, the corrected R (Ex, F
When the value of d) or R (Ei, Fjy) is smaller than 0, the value is set to 0. This process is repeatedly executed for all R (Ex, Fjy) satisfying the expressions (20) and (21).

After the processing of the score changing unit 1506 is finished, the matching control unit 107 operates the relation score adding unit 1202 in the feature point matching unit 105 and the relation score adding unit 1302 in the line segment matching unit 106. The matching control unit 107
Then, the line segment score addition unit 12 in the feature point matching unit 105.
03 and the feature point score adding unit 130 in the line segment matching unit 106.
Activate 3. Further, the matching control unit 107 includes the score changing unit 1406 and the line segment matching unit 10 in the feature point matching unit 105.
The score changing unit 1506 in 6 is operated. This series of operations is repeated a fixed number of times. In the present embodiment, the number of repetitions is three, but any number may be used. Even when the number of repetitions is less than 3, when it is detected that the feature points of the input pattern and the feature points of the dictionary pattern have a one-to-one correspondence, or the line segment of the input pattern and the line segment of the dictionary pattern If is detected to have a one-to-one correspondence,
The repetition is interrupted and the final score calculation process is executed.

The matching control unit 107 reads the feature point score S (Ix, Djy) from the feature point score storage unit 1205. First, the maximum value in S (Ix, Djy) is obtained. Using Ix and Djy at that time, S (Ix, Dd)
Replace the value of with 0. Here, Dd indicates a feature point number of a dictionary pattern other than Djy. In addition, S (Ii, Dj
Replace the value in y) with 0. Here, Ii indicates the feature point numbers of all input patterns other than Ix. After this correction, the maximum value in S (Ix, Djy) is calculated, and S (Ix, Djy)
Modify Dd) and S (Ii, Djy). This processing is repeatedly executed a small number of times of the number of characteristic points of the input pattern and the number of characteristic points of the dictionary pattern, and S (I
x, Djy) is corrected. After the completion of this correction process, the sum of the element values included in S (Ix, Djy) is obtained and is set to S.

Then, the matching control unit 107 determines the line segment score R
(Ex, Fjy) is read from the line segment score storage unit 1305 in the line segment matching unit 106. First, the matching control unit 107
Calculates the maximum value of R (Ex, Fjy). E at that time
The value of R (Ex, Fd) is replaced with 0 using x and Fjy. Here, Fd indicates a line segment number of a dictionary pattern other than Fjy. Further, the value of R (Ei, Fjy) is replaced with 0. Here, Ei indicates the line segment numbers of all input patterns other than Ex. After this correction, the maximum value among R (Ex, Fjy) is calculated, and R (Ex, Fd) and R (Ei, F
jy) correction. This process is repeatedly executed a small number of times of the number of line segments of the input pattern and the number of line segments of the dictionary pattern to correct R (Ex, Fjy). After the completion of this correction process, the total sum of the element values included in R (Ex, Fjy) is calculated and set as R. Finally, the matching control unit 107 calculates and obtains S + R to obtain the matching score between the input pattern and the j-th dictionary data. The matching control unit 107 executes matching of all the dictionary data with the input pattern, and outputs the category name of the dictionary data having the maximum score from the terminal 108. In the present embodiment, the final matching result is obtained by using both the values of S and R, but the category name of the dictionary data giving the maximum value may be output from the terminal 108 by using only S. Also, using only R,
The terminal name is the dictionary data category name that gives the maximum value.
You may output from 8.

Next, another embodiment of the present invention will be described with reference to FIG. The embodiment of FIG. 3 is different from the embodiment of FIG. 1 only in the online input unit 301 and the feature detection unit 302, and the feature point description unit 103, the line segment description unit 104, and the feature point matching unit 10 are different.
The operations of the line matching unit 106, the line segment matching unit 106, and the matching control unit 107 are the same as those in the embodiment of FIG.

The online data input unit 301 transfers a stroke pattern sampled by an input device such as a tablet that can input a series of coordinate data designated in time series to the feature point detection unit 302. The feature point detection unit 302 may be of any type as long as it can detect feature points such as end points, intersections, and bending points from the stroke pattern. Divide each into a set of line segment data. In this embodiment, the line segment data is divided into units of 3 pixels, but this is not an essential problem and any number of pixels may be used. The points at the ends of the stroke are the endpoints and can be determined. In order to obtain the intersections, it may be determined whether or not they intersect in all combinations of line segments, but in the present embodiment, an image pattern in which all pixel values are 0 is prepared in advance. , Line segment sets are numbered from 1 in order. Line segments are drawn in the image pattern from one end point of the line segment to the other end point in order from the first line segment. The value of the passing pixel at that time is taken as the line segment number. However, when drawing the line segment, if the value of the target pixel is not already 0, it is detected that the line segment intersects with the line segment whose number is the value of the pixel. The detected point is set as an intersection, and its coordinates are stored. When a bending point is adopted as the feature point, the direction changes are sequentially accumulated from the first line segment to the last line segment of the stroke pattern delimited by the feature point, and when a certain threshold is exceeded, The stroke pattern is divided into two, and the division points are set as bending points. As a cumulative value of direction change, D = 0 is initially set. The changes in the directions of the first line segment and the second line segment are expressed by vectors (Di1, Dj1) and (Di2, D) indicating the directions of the respective line segments.
j2) is used to calculate the direction change by the calculation according to the equation (22), and the change is accumulated.

D = D + ArcCOS (Dik * Di (k + 1) + Djk * D (k + 1) 2 / Norm (Dik, Djk) / Norm (Di (k + 1), Dj (k + 1) )) (22) Here, ArcCOS gives an inverse function of the COS function, and its unit is radian. Also, Norm (x,
y) is a function that gives the norm of the vector (x, y).

The value of D is calculated by sequentially increasing k by 1 from 1 and the absolute value of D exceeds the threshold value when the final line segment in the stroke delimited by the feature points is processed. Sometimes, the stroke is selected as including the bending point. The method of selecting the bending point is to obtain a reference line connecting the start point and the end point of the stroke, and obtain the distance from the start point or the end point of the line segment included in the stroke to the reference line,
The point that gives the maximum distance is selected as the inflection point and the stroke is divided. Divide all strokes,
When the absolute value of the cumulative value of change in direction of all strokes becomes less than or equal to the threshold value, the bending point selection is ended. The feature points and the stroke pattern thus obtained are transferred to the feature point description unit 103 and the line segment description unit 104, and the subsequent processing is continued.

The feature point description section 103, the line segment description section 104,
Feature point matching unit 105, line segment matching unit 106, matching control unit 1
Since the operation of 07 is the same as that of the embodiment of FIG. 1, the description will be omitted.

Next, another embodiment of the present invention will be described with reference to FIG.

The line graphic image input from the image input unit 401 such as a scanner is subjected to preprocessing such as noise removal and binarization processing, and is obtained as a binary line graphic image. It is transferred to the output unit 102.

The characteristic point detecting section 102 detects the characteristic points of the line figure. The detailed description thereof is the same as the description of the first embodiment, and will be omitted.

The set of feature points and the set of line segments detected by the feature point detection unit 102 are the feature point description unit 103 and the line segment description unit 1.
04. The feature point description unit 103 obtains the detected feature points, the respective feature amounts, and the feature amount of the relationship between the feature points. In the line segment description unit 104, the feature amount of the line segment itself is calculated from the input feature point list and the line segment list,
Find the relationship between line segments. The detailed description of the feature point description unit 103 and the line segment description unit 104 is also the same as the description of the first embodiment of the first invention, and therefore will be omitted here.

The operations of the feature point matching unit 105, the line segment matching unit 106, and the matching control unit 407 are the same as those of the embodiments of FIGS. 12 and 13 used in the description of the first embodiment. The feature point matching unit 105 includes a simple matching unit 1201 and a relationship score adding unit 12
02, line segment score addition unit 1203, dictionary data storage unit 1
204 and a feature point score storage unit 1205.
Further, the line segment matching unit 106 includes a simple matching unit 1301, a relationship score adding unit 1302, a feature point score adding unit 1303,
Dictionary data storage unit 1304, line segment score storage unit 1305
Consists of The description of the operation of these components is the same as the description of the embodiment using FIG. 1, FIG. 12, and FIG. Feature point matching unit 105 and line segment matching unit 10
6 and the matching control unit 407 generate and store the matching score between the feature points of the input pattern and the dictionary pattern in the feature point score storage unit 1205, and the line segment score storage unit 1305 stores the input pattern and the dictionary pattern. A score of matching between the line segments is generated and stored.

When the processing of the feature point matching unit 105 and the line segment matching unit 106 is completed, the matching control unit 407 stores the feature point score S (Ix, Djy) in the feature point score storage unit 1205.
Sequentially read. The matching control unit 407 uses S (Ix, Dj
When targeting y), the value of S (Ix, Dd) is compared according to equation (18). Here, Dd indicates a feature point number of a dictionary pattern other than Djy. S (Ii, Dj
The value is compared with y) according to equation (19). here,
Ii indicates the feature point numbers of all input patterns other than Ix. Here, in the present embodiment, the value of K is set to 20, but this value may be any value. Equation (18) and Equation (1
When S (Ix, Djy) satisfying 9) is detected,
The image transforming unit 4 stores S (Ix, Djy) and (Ix, Djy).
09 to be stored. This process is performed for all (Ix,
Djy) is repeatedly executed.

The matching control unit 407 reads the feature point score S (Ix, Djy) from the feature point score storage unit 1205. First, the maximum value in S (Ix, Djy) is obtained. Using Ix and Djy at that time, S (Ix, Dd)
Replace the value of with 0. Here, Dd indicates a feature point number of a dictionary pattern other than Djy. In addition, S (Ii, Dj
Replace the value in y) with 0. Here, Ii indicates the feature point numbers of all input patterns other than Ix. After this correction, the maximum value in S (Ix, Djy) is calculated, and S (Ix, Djy)
Modify Dd) and S (Ii, Djy). This processing is repeatedly executed a small number of times of the number of characteristic points of the input pattern and the number of characteristic points of the dictionary pattern, and S (I
x, Djy) is corrected. After the completion of this correction process, the sum of the element values included in S (Ix, Djy) is obtained and is set to S.

Subsequently, the matching control unit 407 again reads the line segment score R (Ex, Fjy) from the line segment score storage unit 1305 in the line segment matching unit 106. First, the matching control unit 40
7 obtains the maximum value of R (Ex, Fjy). The value of R (Ex, Fd) is replaced with 0 using Ex and Fjy at that time. Here, Fd indicates a line segment number of a dictionary pattern other than Fjy. Further, the value of R (Ei, Fjy) is replaced with 0. Here, Ei indicates the line segment numbers of all input patterns other than Ex. After this correction, R (Ex, Fjy)
The maximum value of R (Ex, Fd) and R (Ei,
Fjy) correction. This process is repeatedly executed a small number of times of the number of line segments of the input pattern and the number of line segments of the dictionary pattern to correct R (Ex, Fjy). After the completion of this correction process, the total sum of the element values included in R (Ex, Fjy) is calculated and set as R. Finally, the matching control unit 407 calculates and obtains S + R to obtain the matching score Sj between the input pattern and the j-th dictionary data. In this embodiment, the matching result is obtained by using both the values of S and R, but only S may be used as Sj. Alternatively, only R may be used as Sj.

After the processing is completed, the matching control unit 407
Sends a signal to the image transforming unit 409 to activate.

In the image transformation section 409, the matching control section 407
The image transformation is executed based on (Ix, Djy) received from. Image transformation processing is "Beier, T and Neely, S," Featu
re Based Image Metamorphosis ", Proc. of SIGGRAPH92,
1992 ", there are many publicly known image transforming means, but in this embodiment, the image transforming means described below is used.

The image transforming unit 409 selects the maximum value from the plurality of scores S (Ix, Djy) received from the matching control unit 106 and sets it as M. In addition, S (Ix, Djy) are arranged in descending order. S (Ix, Djy) in order from the maximum value
The image transformation is performed using (Ix, Djy).
Since the image deformation processing using each (Ix, Djy) is the same, the case where the deformation processing is executed for one set (Ix, Djy) will be described. S (Ix, Djy)
The same process is repeated by changing the value of (Ix, Djy) in descending order of.

In this embodiment, the size of the image along with the input pattern and the dictionary pattern is J pixels in the vertical direction and I pixels in the horizontal direction, and both J and I are set to 100, but any value may be used. The upper left coordinate of the image is (0, 0), and the lower right coordinate is (I,
J).

The image transformation section 409 reads the coordinates (X11, Y11) of the feature point Ix in the input pattern from the feature point description section 103 for (Ix, Djy). In addition, the feature point matching unit 105 outputs the feature point Djy in the dictionary pattern.
Read out the coordinates (X21, Y21).

The coordinates (X11, Y11) of the input pattern are moved toward (X21, Y21), and the points of the other coordinates of the input pattern are moved accordingly. The pixel value of the coordinate (X ', Y') of the moving destination is obtained from the pixel value of the coordinate (X, Y) of the moving source. Pixel values at all the destination points are calculated and obtained according to the following equations (23), (24), and (25).

U = (X21−X11) * Z * S (Ix, Djy) / M V = (Y21−Y11) * Z * S (Ix, Djy) / M (23) However, in this embodiment, Z is Although it is set to 0.3, any value may be used.

X = X'X11 / (X11 + U) When X '<X11 X = (X' (I-X11) -UI) / (I-X11-U) Other than above (24) If I-X11- When U is smaller than 0, the value of Z is temporarily corrected and I-X11-U is set to be larger than 0.

Y = Y'Y11 / (Y11 + V) When Y '<Y11 Y = (Y' (I-Y11) -VI) / (I-Y11-V) Other than above (25) If I-Y11- When V is smaller than 0, the value of Z is temporarily corrected and I-Y11-V is set to be larger than 0.

X and Y obtained by the calculation according to the equations (24) and (25) are decimal numbers, which are rounded to integers to obtain coordinates, and the pixel value of the coordinates is taken out.
Pixel values at the coordinates of X'and Y '. X'is changed from 0 to I and Y'is changed from 0 to J to obtain all pixel values to obtain a deformed image.

Based on this deformed image, the following S (Ix, Dj
y) is taken out and the image transformation process is performed according to the above equations (23), (24) and (25).

All S stored in the image transformation unit 409
After performing the image transformation process on (Ix, Djy), the obtained transformed image is transferred to the image input unit 501,
The feature point detection unit 202, the feature point description unit 103, the line segment description unit 104, the feature point matching unit 105, and the line segment matching unit 106 are driven. Based on the generated score, formula (18), formula (1
Detecting feature points with sufficiently large scores according to 9),
The image is transferred to the image transforming unit 409, and the image transforming process is executed again. This series of operations is repeated a fixed number of times. In the present embodiment, the number of repetitions is three, but any number may be used. Further, even if the number of times of repetition is less than 3, if it is detected that the final matching score Sj obtained by the matching control unit 407 becomes larger than a certain threshold value, the repeating is interrupted, and at that time, The matching score Sj obtained at the end of is the matching score with the j-th dictionary data.

The matching control unit 407 executes matching of all the dictionary data with the input pattern according to the above-described matching embodiment, and outputs the category name of the dictionary data having the maximum score from the terminal 108.

The image input unit 101 and the feature point detection unit 102 of the above embodiment are changed to the online data input unit 501 and the feature point detection unit 301 as in the embodiment of FIG. FIG. 5 shows an embodiment for realizing the matching of the pattern input in the online data format, which is the same operation as the above. In this embodiment, the online data input unit 50 is used.
1, feature point detection unit 302, feature point description unit 103, line segment description unit 104, feature point matching unit 105, line segment matching unit 106,
The image transformation unit 509 and the matching control unit 407 are included.

The online data input unit 501 transfers a stroke pattern sampled by an input device such as a tablet which can input a series of coordinate data designated in time series to the feature point detection unit 302. The embodiment of the feature point detection unit 302 is the feature point detection unit 3 of the embodiment of FIG.
Since the operation is the same as that of No. 02, description thereof will be omitted here.

The characteristic point description section 103, the line segment description section 104,
The operation of the feature point matching unit 105 and the line segment matching unit 106 is as shown in FIG.
The description is omitted because it is the same as the embodiment described above.

When the processing of the feature point matching unit 105 and the line segment matching unit 106 is completed, the matching control unit 407 stores the feature point score S (Ix, Djy) in the feature point score storage unit 1205.
Sequentially read. The matching control unit 407 uses S (Ix, Dj
When targeting y), the value of S (Ix, Dd) is compared according to equation (18). Here, Dd indicates a feature point number of a dictionary pattern other than Djy. S (Ii, Dj
The value is compared with y) according to equation (19). here,
Ii indicates the feature point numbers of all input patterns other than Ix. Here, in the present embodiment, the value of K is set to 20, but this value may be any value. Equation (18) and Equation (1
When S (Ix, Djy) satisfying 9) is detected,
The image transformation unit 5 sets S (Ix, Djy) and (Ix, Djy).
09 to be stored. This process is performed for all (Ix,
Djy) is repeatedly executed.

Subsequently, the matching control unit 407 again retrieves the feature point score S (Ix, Dj from the feature point score storage unit 1205.
y) is read out. First, the maximum value in S (Ix, Djy) is obtained. Using Ix and Djy at that time, S (I
Replace the value of x, Dd) with 0. Where Dd is Djy
A feature point number of a dictionary pattern other than. In addition, S (I
Replace the value of i, Djy) with 0. Where Ii is Ix
Other than the above, it indicates the feature point numbers of all input patterns. After this correction, the maximum value in S (Ix, Djy) is calculated, and S
Modify (Ix, Dd) and S (Ii, Djy). This processing is repeatedly executed a small number of times of the number of characteristic points of the input pattern and the number of characteristic points of the dictionary pattern, and S (Ix, Djy) is corrected. After the completion of this correction process, the sum of the element values included in S (Ix, Djy) is obtained and is set to S.

Subsequently, the matching control unit 407 again reads the line segment score R (Ex, Fjy) from the line segment score storage unit 1305 in the line segment matching unit 106. First, the matching control unit 40
7 obtains the maximum value of R (Ex, Fjy). The value of R (Ex, Fd) is replaced with 0 using Ex and Fjy at that time. Here, Fd indicates a line segment number of a dictionary pattern other than Fjy. Further, the value of R (Ei, Fjy) is replaced with 0. Here, Ei indicates the line segment numbers of all input patterns other than Ex. After this correction, R (Ex, Fjy)
The maximum value of R (Ex, Fd) and R (Ei,
Fjy) correction. This process is repeatedly executed a small number of times of the number of line segments of the input pattern and the number of line segments of the dictionary pattern to correct R (Ex, Fjy). After the completion of this correction process, the total sum of the element values included in R (Ex, Fjy) is calculated and set as R. Finally, the matching control unit 407 calculates and obtains S + R to obtain the matching score Sj between the input pattern and the j-th dictionary data. In this embodiment, the matching result is obtained by using both the values of S and R, but only S may be used as Sj. Alternatively, only R may be used as Sj.

After the end of the processing, the matching control unit 407
Sends a signal to the image transformation unit 509 and activates it.

The image transformation unit 509 is the image transformation unit 4 of FIG.
Although the same operation as that of 09 can be used as an example,
Here, another embodiment will be described. Image transformation unit 5
09 selects the maximum value from the plurality of scores S (Ix, Djy) received from the matching control unit 106 and sets it as M.
In addition, S (Ix, Djy) are arranged in descending order. The image transformation is performed using (Ix, Djy) of S (Ix, Djy) in order from the maximum value. First, each (Ix, Djy)
Is associated with a point on the corresponding input pattern. Since the image deformation processing using each (Ix, Djy) is the same, the case where the deformation processing is executed for one set (Ix, Djy) will be described. The same processing is repeatedly executed in the descending order of S (Ix, Djy) by changing the value of (Ix, Djy).

In the present embodiment, the size of the image along with the input pattern and the dictionary pattern is J pixels in the vertical direction and I pixels in the horizontal direction, and both J and I are set to 100, but any value may be used. The upper left coordinate of the image is (0, 0), and the lower right coordinate is (I,
J).

The image transforming unit 509 uses the coordinates (X1) of the feature point Ix in the input pattern corresponding to (Ix, Djy).
1, Y11) is read from the online data input unit 501. Further, the coordinates (X21, Y21) of the feature point Djy in the dictionary pattern are read from the feature point matching unit 105.

The coordinates (X11, Y11) of the input pattern are moved toward (X21, Y21), and the point on the line segment connected to the feature point of the input pattern is moved accordingly. The coordinates (X ', Y') of the destination are calculated from the coordinates (X, Y) of the source. The point to move is the feature point (X1
1, Y11) and the points on the stroke which are connected to each other are sequentially read from the online data input unit 501 and the movement processing is performed. Along the stroke, feature points (X11, Y1
The coordinate of the movement destination is calculated and calculated according to the equations (23) and (26), where Q is the distance from 1) to the point to be moved. However, only the point where the distance Q is equal to or less than the threshold value H from (X11, Y11) is set as the movement target. In this embodiment, H is set to 40 pixels, but this value may be any value.

X ′ = X + U * Q / H Y ′ = Y + V * Q / H (23) The generated pattern is again used by the online data input unit 5
Stored in 01.

Based on this deformed image, the next S (Ix, Dj
y) is taken out, and the image transformation process is performed according to the above equations (23) and (26).

All S stored in the image transformation unit 509
After performing the image transformation process on (Ix, Djy), the obtained transformed image is input to the online data input unit 50.
1, and the feature point detection unit 302 and the feature point description unit 10
3, the line segment description unit 104, the feature point matching unit 105, and the line segment matching unit 106 are driven. Based on the generated score, the formula (1
8), a feature point having a sufficiently large score is detected according to equation (19), transferred to the image transformation unit 509, and the image transformation process is executed again. This series of operations is repeated a fixed number of times. In the present embodiment, the number of repetitions is three, but any number may be used. Further, even if the number of times of repetition is less than 3, if it is detected that the final matching score Sj obtained by the matching control unit 407 becomes larger than a certain threshold value, the repeating is interrupted, and at that time, The matching score Sj obtained at the end of is the matching score with the j-th dictionary data.

The matching control unit 407 executes matching of all the dictionary data with the input pattern according to the above-described matching embodiment, and outputs the category name of the dictionary data having the maximum score from the terminal 108.

[0107]

As described above, the stroke pattern matching device of the present invention is characterized by a feature point description means for describing the features of the feature points obtained by the feature point detection means and the features between the feature points, and the feature point detection. A line segment describing means for describing the feature of a line segment delimited by the feature points obtained by the means and the feature of the line segment, and a feature point for performing stroke pattern matching using the feature described by the feature point describing means Matching means, line segment matching means for performing stroke pattern matching using the features described by the line segment describing means, and feature point matching means and output signals of the line segment matching means are used to determine the matching result. And the matching control means for adjusting the stroke pattern, the relationship between the line segments that are not connected can be added to the matching.

Further, the feature point matching means is provided with a relation score adding means for correcting the matching result by using the relation of a plurality of feature points, and the line segment matching means is matched by using the relation of a plurality of line segments. The relationship score adding means for correcting the result; the feature point matching means, the line segment score adding means for correcting the matching result using the matching result of the line segment matching means; and the line segment matching means, By providing the feature point score adding means that corrects the matching result using the matching result of the feature point matching means, it is possible to realize the matching of the stroke patterns including the line segments that are not connected with high accuracy.

Further, the matching control means uses the magnitude relation of the score of the matching result to correct the score and the feature point matching means and the line segment matching means repeatedly to obtain the matching result. By providing the stroke pattern, it is possible to more accurately match the stroke pattern even with a deformed stroke pattern.

Further, according to the matching result of the matching control means,
An image transforming unit that transforms the original stroke pattern is provided, and the image transforming unit, the feature point detecting unit, the feature point describing unit, the line segment describing unit, the feature point matching unit, the line segment matching unit, and the matching control unit are repeatedly driven. As a result, the stroke patterns can be more accurately aligned with each other even for the more deformed stroke patterns.

Further, according to the present invention, the image input means inputs the stroke pattern as online data which is a sequence of coordinate points, and the structure is analyzed from the online stroke pattern obtained from the image input means. By including the feature point detecting means for detecting, it is possible to realize the matching of stroke patterns including line segments that are not accurately connected, even for stroke patterns as online data.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of an embodiment of a stroke pattern matching device of the present invention.

FIG. 2 is a block diagram showing a configuration of a conventional stroke pattern matching device.

FIG. 3 is a block diagram showing a configuration of an embodiment of a stroke pattern matching device of the present invention.

FIG. 4 is a block diagram showing a configuration of an embodiment of a stroke pattern matching device of the present invention.

FIG. 5 is a block diagram showing a configuration of an embodiment of a stroke pattern matching device of the present invention.

FIG. 6 is a diagram showing an example of feature points of a stroke pattern.

FIG. 7 is a diagram showing an example of a line segment of a stroke pattern.

FIG. 8 is a diagram showing an example of proximity feature points of a stroke pattern.

FIG. 9 is a diagram showing an example of a relationship between stroke segments of a stroke pattern.

FIG. 10 is a diagram showing an example of a table including characteristics of a relationship between characteristic points of a stroke pattern.

FIG. 11 is a diagram showing an example of a table including characteristics of relationships between stroke patterns of line segments.

FIG. 12 is a block diagram showing a configuration example of a feature point matching unit.

FIG. 13 is a block diagram showing a configuration example of a line segment matching unit.

FIG. 14 is a block diagram showing another configuration example of a feature point matching unit.

FIG. 15 is a block diagram showing another configuration example of the line segment matching unit.

[Explanation of symbols]

101, 401 Image input unit 102, 302 Feature point detection unit 103 Feature point description unit 104 Line segment description unit 105 Feature point matching unit 106 Line segment matching unit 107, 407, 507 Matching control unit 108 Output terminal 201 Skeleton line extracting unit 202 Line figure structure analysis unit 203 Matching unit 301, 501 Online data input unit 409, 509 Image transformation unit 601, 602, 603, 604, 605, 606, 6
07, 608 Feature points 701, 702, 703, 704, 705, 706, 7
07 Line segment 801, 802 Feature point 803 Relationship between feature points 901, 902 Line segment 903 Line segment relationship 1201, 1301 Simple matching section 1202, 1302 Relation score adding section 1203 Line segment score adding section 1204, 1304 Dictionary data storage section 1205 Feature Point score storage unit 1303 Characteristic point score addition unit 1305 Line segment score storage unit 1406, 1506 Score change unit

Claims (8)

[Claims] 1. An image inputting means for inputting a stroke pattern as an image, a characteristic point detecting means for detecting a characteristic point by analyzing a structure from the stroke pattern obtained from the image inputting means, and the characteristic point detecting means. In a stroke pattern matching device that realizes stroke pattern matching using the obtained features, a feature point description unit that describes the features of the feature points obtained by the feature point detection unit and the features between the feature points, and the feature Stroke pattern matching is performed using the line segment description means for describing the features of the line segment delimited by the feature points obtained by the point detection means and the feature of the line segment, and the feature described by the feature point description means. Feature point matching means, line segment matching means for performing stroke pattern matching using the features described by the line segment describing means, the feature point matching means, and the line A stroke pattern matching device comprising: a matching control means for judging a matching result by using an output signal of the minute matching means. 2. The stroke pattern matching device according to claim 1, wherein the feature point matching means comprises a relationship score adding means for correcting the matching result by using the relationship between a plurality of feature points. 3. The stroke pattern matching device according to claim 1, wherein said line segment matching means comprises a relationship score adding means for correcting the matching result by using the relationship between a plurality of line segments. 4. The stroke pattern matching device according to claim 1, wherein said feature point matching means comprises line segment score adding means for correcting the matching result by using the matching result of said line segment matching means. . 5. The stroke pattern matching device according to claim 1, wherein said line segment matching means comprises feature point score adding means for correcting the matching result by using the matching result of said feature point matching means. . 6. The matching control means repeatedly executes the means for correcting the score, the feature point matching means and the line segment matching means by using the magnitude relation of the score of the matching result,
The stroke pattern matching device according to claim 1, further comprising means for obtaining a matching result. 7. An image transforming unit for transforming an original stroke pattern according to a matching result of the matching control unit,
The image transformation means, the feature point detection means, the feature point description means, the line segment description means, the feature point matching means, the line segment matching means, and the matching control means can be repeatedly driven. Item 1. The stroke pattern matching device according to item 1. 8. The feature point detection, wherein the image input means inputs a stroke pattern as online data which is a sequence of coordinate points and analyzes the structure from the online stroke pattern obtained from the image input means to detect a feature point. The stroke pattern matching device according to claim 1, further comprising means.