JP4148966B2 - Pattern matching apparatus, program for realizing the same, and recording medium - Google Patents

Description

  The present invention relates to a pattern matching device that recognizes a read character image as a character, a program for realizing the same, and a recording medium.

  Conventionally, various recognition methods have been proposed for character recognition including characters including kanji, but kanji has a complicated pattern of one character and many types of characters, and even printed characters can be used in the Mincho style. There are Gothic fonts, etc., and it is very difficult to make it recognized by a machine if even handwritten characters are included. For this reason, in each device, attempts have been made to improve the identification accuracy and increase the processing speed by combining various methods such as a matching method and structural analysis.

  Conventional character image identification methods generally include a pattern matching method and a structured analysis method. A pattern matching method is often used for identifying printed characters. In the pattern matching method, a character pattern extracted from an image is matched with a standard pattern held in a dictionary to recognize a character. For this matching, a composite similarity is often used.

  In addition, since it takes a long time to calculate the composite similarity, a method is known in which simple similarity is calculated first, and composite similarity is calculated only for higher candidates having a high simple similarity value.

  FIG. 11 is a flowchart for explaining a conventional pattern matching method. First, in step S50, a character image is cut out along the circumscribed frame of characters from the input image. FIG. 12 is a diagram illustrating an example of a character image cut out. A square frame is cut out so as to circumscribe the character image “A”.

  Next, it progresses to step S51 and the characteristic of the character is extracted from the cut-out character image. A mesh feature is well known as a feature extraction method. The mesh feature is a process of dividing the cut character image into meshes, and normalizing the number of pixels in each mesh. FIG. 13 is a diagram in which the character image of FIG. 12 is divided by mesh features. In FIG. 13, a single character image is divided into 8 meshes vertically and horizontally and divided into 64 meshes. FIG. 14 shows characteristic data obtained by normalizing the number of pixels in each mesh of FIG. Image features (0 to 128) are extracted from each mesh and represented by an 8 × 8 matrix.

Next, the process proceeds to step S52, and the simple similarity between the feature data of the input character image and the feature data which is a standard pattern included in the dictionary is calculated. If the feature data of the input character image is X and the feature data of a certain category in the dictionary is Y, the simple similarity S (X, Y) is expressed by the following equation. The category corresponds to one character data. However, even the same characters with different shapes depending on the font are in different categories.

Since the denominator value becomes constant when the feature data of the input character image and the feature data of the dictionary are normalized, the denominator value can be processed only by calculating the numerator. The value of the numerator is calculated as shown in Equation 2 when an 8 × 8 mesh feature is used.

  In step S52, the above calculation is performed for all categories of the dictionary. In addition to the similarity, a city block distance, an Euclidean distance, or the like may be used as an index representing the proximity between the input character image feature data and the feature data of the dictionary.

  Next, proceeding to step S53, the top n categories (n is a natural number) are extracted from the values of simple similarity calculated for all categories. Then, the process proceeds to step S54, and the composite similarity is calculated for the n extracted categories. Next, the process proceeds to step S55, and the top m (m is a natural number) candidate characters are extracted from the calculated n composite similarities. Then, the process proceeds to step S56, and the extracted character codes of the m candidate characters are output as recognition results.

  In the pattern matching method, the simple similarity calculation process in step S52 occupies most of the entire processing amount. Thus, attempts have been made to further increase the processing speed.

  For example, in Patent Document 1, the categories of the dictionary are divided into similar category groups, and the feature data representing each group and the feature data of the input character image are matched before step S52 in FIG. It is disclosed that only the upper group performs the processing after step S52.

In Patent Document 2, the feature data of the input character image is divided into lines, the maximum value of each line is marked, and the feature data of the dictionary may have a maximum value for each line in advance. It is disclosed that all locations are marked, collated whether the marked locations match, and the processing after step S52 in FIG. 11 is performed only when they match.
JP-A 63-263590 Japanese Patent No. 2938276

  However, Patent Document 1 has a problem that it is difficult to perform ideal division when dividing into similar category groups. In addition, since the feature data of the input character image is matched with the representative vector of the group, the dictionary data frequently comes close to another group instead of a group including a category having inherently similar feature data. For this reason, a plurality of groups are left as candidates, and the candidates may not be narrowed down.

  Further, in Patent Document 2, the location of the maximum value is obtained for each row of the feature data. However, since the location of the maximum value is very easy to shake, it is difficult to create dictionary data prepared in advance. There is a high possibility of leakage. If a mark that can take the maximum value in a wide range is provided in order to prevent leakage, it matches with the majority, and the speed cannot be increased very much.

  Further, in Patent Documents 1 and 2, there is a problem that data used for speeding up must be prepared in advance in addition to dictionary feature data, leading to an increase in data capacity.

  It is an object of the present invention to provide a pattern matching apparatus that accurately recognizes characters while reducing the amount of calculation for matching for character recognition to increase the speed. Another object of the present invention is to provide a program for realizing the pattern matching device and a recording medium on which the program is recorded.

  In order to achieve the above object, the present invention provides a pattern matching apparatus that recognizes characters by comparing feature data of an input character image with feature data of a plurality of categories included in the dictionary, the plurality of categories included in the dictionary. Means for obtaining dictionary collation data which is a binary value indicating whether or not each element of each category is equal to or less than a first threshold value from the feature data of the category, and from the feature data of the input character image , A means for obtaining input collation data that is a binary value indicating whether or not each element is equal to or greater than a second threshold, and collating the dictionary collation data with the input collation data, and matching elements Means for performing matching calculation with a dictionary only for a category whose number is equal to or less than a predetermined value.

According to this configuration, the dictionary collation data and the input collation data are collated, and only when there is no coincidence or the number of coincidence is small, the speed can be increased by calculating the similarity. Obtaining whether or not each element of the feature data of the input character image is greater than or equal to the second threshold has a meaning of indicating whether or not it is a character portion when the threshold is increased to some extent. Further, obtaining whether or not each element of the feature data of a plurality of categories included in the dictionary is equal to or less than the first threshold has a meaning indicating whether or not it is a background portion when the threshold is reduced to some extent. Since the feature data of the dictionary is an average of many patterns, when the threshold value is reduced, being below that threshold means that it is absolutely the background part, and the corresponding character has been entered. In some cases, it is used that the part does not become a character part. In addition, when the feature data of the character image input so that the character part overlaps the element that originally becomes the background part, the matching with the dictionary is not performed. However, even if matching is performed in this case, the degree of similarity can be obtained by the calculation of Formula 2, so that the product of x _i corresponding to a large portion of the feature data of the input character image and the corresponding element y _i of the dictionary is small. As a result, the value of the similarity also becomes small, and even if all the matching calculations are performed, the possibility of finally becoming a candidate is low.

  Further, in the present invention, it is not necessary to store dictionary collation data in advance, and it is only necessary to obtain a value once when the apparatus is started up, so there is no need to have extra data other than dictionary feature data. .

  Since it is possible to determine whether or not to perform matching by collating input collation data obtained from input character image feature data and dictionary collation data obtained from dictionary feature data, high-speed calculation is possible. Also, the accuracy of the recognition result is increased. Furthermore, if the collation between the input collation data and the dictionary collation data is performed by a logical product of a unit, it is possible to reduce the amount of calculation required for the determination. Further, by performing the processing to be obtained from the feature data of the dictionary at the time of starting the apparatus, it is not necessary to have dictionary collation data in advance, and the data capacity can be reduced.

  FIG. 1 is a block diagram showing the main configuration of the pattern matching apparatus. The pattern matching device 10 is connected to an input device 11 and an output device 12. The input device 11 is composed of an image scanner or the like, and reads the character image and sends the read character image to the pattern matching device 10. The output device 12 is composed of a liquid crystal display device or the like and outputs characters recognized by the pattern matching device 10.

  The pattern matching apparatus 10 is cut out by a predetermined method, a control unit 13 that controls the entire apparatus, a cutout unit 14 that cuts out an image sent from the input device 11 into a character image for one character, and a predetermined method. A feature extraction unit 15 that extracts feature values of a character image and creates feature data to be described later, a large classification unit 16 that narrows down candidates for matching calculation before calculating a simple similarity, and a simple that constitutes the dictionary 21 Similarity degree dictionary feature data 17 and composite similarity dictionary feature data 18, and similarity between the input character image feature data and simple similarity dictionary feature data 17 and composite similarity dictionary feature data 18 are calculated. And a dictionary matching data creating unit 20 for creating dictionary matching data used when performing the large classification process from the dictionary feature data 17 for simple similarity.

  FIG. 2 is a flowchart for explaining the pattern matching method. First, in step S10, the cutout unit 14 receives an image input to the input device 11, and cuts out a character image along a circumscribed frame of characters in the image. An example of the clipped character image is the same as in FIG.

  Next, it progresses to step S11 and the characteristic of the character is extracted from the cut-out character image. A mesh feature can be used as the feature extraction method. The mesh feature is a process of dividing the cut character image into meshes, and normalizing the number of pixels in each mesh. An example in which the character image is divided by the mesh feature is the same as in FIG. In FIG. 13, a single character image is divided into 8 meshes vertically and horizontally and divided into 64 meshes. The characteristic data obtained by normalizing the number of pixels in each mesh by numerical values is the same as that shown in FIG. Image features are extracted from each mesh and represented by an 8 × 8 matrix.

  Next, it progresses to step S12 and performs a large classification process. This is a process for narrowing down candidates for matching calculation before calculating the simple similarity in step S13. Details of this processing will be described later.

  Next, the process proceeds to step S13, and simple similarity is calculated for the candidates narrowed down in step S12. The simple similarity is calculated from the input character image feature data and the simple similarity dictionary feature data 17. When the feature data of the input character image is X and the feature data of a certain category of the dictionary is Y, the simple similarity S (X, Y) is expressed by the following equation (1). The category corresponds to one character data. However, even the same characters with different shapes depending on the font are in different categories.

  Since the denominator value becomes constant when the feature data of the input character image and the feature data of the dictionary are normalized, the denominator value can be processed only by calculating the numerator. The value of the numerator is calculated as shown in Equation 2 when an 8 × 8 mesh feature is used. In addition to the similarity, a city block distance, an Euclidean distance, or the like may be used as an index representing the proximity between the input character image feature data and the feature data of the dictionary.

  In step S14, the top n categories (n is a natural number) are extracted from the values of simple similarity calculated for all categories. Then, the process proceeds to step S15, and the composite similarity is calculated for the n extracted categories. Next, the process proceeds to step S16, and the top m (m is a natural number) candidate characters are extracted from the calculated n composite similarities. In step S17, the extracted character codes of the m candidate characters are output as recognition results. The above is the character recognition process for one character, and is normally repeated until there is no character image to be cut out.

  FIG. 3 is a flowchart showing the operation of the dictionary collation data creation unit 20. First, in step S <b> 20, simple similarity dictionary feature data 17 is extracted from the dictionary 21.

  Next, the process proceeds to step S21, and a value i (i is a natural number) of a counter (not shown) provided in the dictionary collation data creation unit 20 is set to 1 which is an initial value. Next, the process proceeds to step S22, and it is determined whether or not the value of the i-th (counter value) element among the 64 pieces of feature data is equal to or less than a threshold value β (β is a natural number).

  In step S22, when the value of the i-th element of the feature data is equal to or less than the threshold value β, the process proceeds to step S23 and the corresponding bit is set to 1. On the other hand, if the value of the i-th element of the feature data is larger than the threshold value β in step S22, the process proceeds to step S24 and the corresponding bit is set to 0. Then, the process proceeds from step S23 or step S24 to step S25 to increment the counter value i.

  Next, the process proceeds to step S26, where it is determined whether or not the counter value i is larger than 64. In step S26, if the counter value i is larger than 64, it is determined that all the elements of the feature data have been checked, and the process proceeds to step S27. On the other hand, if the counter value i is 64 or less in step S26, the process returns to step S22.

  In step S27, it is determined whether or not processing has been completed for all categories. In step S27, if the processing has been completed for all categories, the creation of dictionary collation data is terminated. On the other hand, if the processing has not been completed for all categories, the process returns to step S20.

  For example, an example of dictionary collation data when β = 2 will be described. FIG. 4A shows characteristic data of the dictionary of the character “A”, and 64-bit dictionary collation data “1100011100000000000000011000000000000000000001000000000000000000” is created. In FIG. 4B, for easy understanding of the image, the portion that is 1 for each element is represented by black, and the portion that is 0 is represented by white.

  FIG. 5A shows the characteristic data of the dictionary of the character “I”, and 64-bit dictionary collation data “0011100100111000001110000011110000001100000011000000110000001111” is created. FIG. 5 (b) shows a portion that becomes 1 for each element in black and a portion that becomes 0 in white for easy understanding of the image.

  FIG. 6A shows the characteristic data of the dictionary of the character “kai”, and 64-bit dictionary collation data “1100011110000001000000000000000000000000000000001000000100000000” is created. FIG. 6 (b) shows a portion that becomes 1 for each element in black and a portion that becomes 0 in white for easy understanding of the image.

  In this way, 64-bit data for collation is created for all categories. Note that the dictionary collation data creation process need only be performed once when the pattern collation apparatus 10 is activated. Further, if there is a sufficient capacity of a ROM (not shown) or the like, data created in advance may be stored instead of being created at startup.

  FIG. 7 is a flowchart for explaining the large classification processing in step S12 of FIG. First, in step S30, input collation data is created from the input character image feature data using the threshold value α. Details of this processing will be described later.

  Next, the process proceeds to step S31, where the input collation data created in step S30 is collated with the dictionary collation data created in the flow of FIG. This collation may be performed by a logical product of 64-bit data. The number of bits that can be handled at a time differs depending on the capacity of the processing device. Therefore, if there is a 64-bit processing capacity, it may be processed at one time. Good. Similarly, if the processing capability is 16 bits, the processing may be divided into four.

  Next, the process proceeds to step S32, and it is determined whether or not the number of matching elements is equal to or less than p (p is a natural number) as a result of the collation in step S31. Specifically, since the collation result is a 64-bit bit string in step S31, it may be determined whether or not the number of bits that are 1 is less than or equal to p. Whether or not it is 1 may be checked for each bit. For example, it is calculated using a table that divides into 8 bits and returns a number that is 1 in 8 bits. Also good. FIG. 8 is an example of a table that returns a number that is 1 for an 8-bit value. In particular, when p = 0, it can be determined whether or not the result is 0 in the process of step S31, so that it is not necessary to count the number of coincidence, and the process can be performed at a higher speed.

  If the number of matching elements is not more than p in step S32, the process proceeds to step S33, and the category is checked as a candidate target. On the other hand, if the number of matching elements is larger than p in step S32, the process proceeds to step S34, and the category is not set as a candidate target.

  It progresses to step S35 from step S33 or step S34, and it is determined whether collation was completed with respect to all the categories. If it is determined in step S35 that all categories have been verified, the process proceeds to step S36. On the other hand, if collation has not been completed for all categories, the process returns to step S31.

  In step S36, it is determined whether or not the number of categories checked as candidate targets in step S33 is equal to or less than k (k is a natural number). This is a process of checking if there are too many candidates remaining with the set value of the threshold value α depending on the feature data of the input character image.

  In step S36, if the number of categories checked as candidate targets is k or less, the large classification process is terminated. On the other hand, if the number of categories checked as candidate targets is greater than k in step S36, the process proceeds to step S37 to change the value of the threshold α. Specifically, by reducing the value of the threshold value α, elements that are regarded as characters are increased. That is, the number of 1 bits in the 64-bit input collation data created in step S30 is increased, and the possibility that the collation result in step S31 is not less than p is increased.

  FIG. 9 is a flowchart for explaining the input collation data creation process in step S30 of FIG. First, in step S40, a value i of a counter (not shown) is set to 1 which is an initial value. Next, the process proceeds to step S41, where it is determined whether or not the value of the i-th (counter value) element among the 64 feature data of the input character image is greater than or equal to a threshold value α (α is a natural number). To do.

  If the value of the i-th element of the feature data is greater than or equal to the threshold value α in step S41, the process proceeds to step S42 and the corresponding bit is set to 1. On the other hand, if the value of the i-th element of the feature data is smaller than the threshold value α in step S41, the process proceeds to step S43 and the corresponding bit is set to 0. Then, the process proceeds from step S42 or step S43 to step S44 to increment the counter value i.

  Next, the process proceeds to step S45, where it is determined whether or not the counter value i is larger than 64. In step S45, if the counter value i is larger than 64, it is determined that all elements of the feature data of the input character image have been checked, and the creation of the input collation data is terminated. On the other hand, if the counter value i is 64 or less in step S45, the process returns to step S41.

  For example, a large classification process when α = 30 and p = 0 will be described. 64-bit input collation data, for example, “0001000001111110001000000011111001101001100110011011001100000110” is generated from the feature data of the character image input by the process of step S30 in FIG. FIG. 10 shows the portion of the input verification data in black and the portion of 0 in white for easy understanding of the input collation data image.

  In step S31 of FIG. 7, for example, the collation result with “A” in FIG. Also, the collation result with “I” in FIG. 5 is “0001000000111000001000000011110000001000000010000000000000000110”, and since the number of matches is not 0, it can be seen that the candidate is not a candidate. In addition, the collation result with “Meeting” in FIG. 6 is “0000000000000000000000000000000000000000000000001000000100000000”, and since the number of matches is not 0, it can be seen that it is not a candidate target.

  By performing large classification processing in this way and using the feature data of the dictionary well, candidates can be narrowed down and speeded up without dropping characters that may be matched.

  The numerical values used in the present embodiment are not specific values and may be set as appropriate. Further, although processing is performed when there are too many candidates in step S36 and step S37 in FIG. 7, it is also possible to increase the number of candidates by checking if there are too few candidates and increasing the value of α. . In addition to changing the threshold value α of the feature data of the input character image, it is possible to prepare a plurality of threshold values β for the feature data of the dictionary and change the data to be collated according to the conditions. is there. Further, the process of step S36 and step S37 of FIG. 7 may be omitted, and the number of remaining candidates may be changed so that it does not matter.

  The pattern matching apparatus 10 is equipped with a pattern matching program for executing the above-described operation. The pattern matching program is recorded on a recording medium such as a ROM, HDD, CD, or DVD.

It is a block diagram which shows the main structures of the pattern collation apparatus of this invention. It is a flowchart explaining a pattern matching method. It is a flowchart which shows operation | movement of the dictionary collation data preparation part of this invention. (A) shows the characteristic data of the dictionary of the character “A”, and (b) shows an image of FIG. 4 (a). (A) shows the characteristic data of the dictionary of the character “I”, and (b) shows the image of FIG. 5 (a). (A) shows the characteristic data of the dictionary of the character “kai”, and (b) shows the image of FIG. 6 (a). It is a flowchart explaining the large classification process of step S12 of FIG. It is an example of the table which returns the number which is 1 with respect to the value of 8 bits. It is a flowchart explaining the creation process of the input collation data of step S30 of FIG. An example of the input collation data of the present invention is represented by an image. It is a flowchart explaining the conventional pattern matching method. It is a figure which shows an example of the conventional character image cut out. It is the figure which divided | segmented the character image of FIG. 12 by the mesh characteristic. 14 is characteristic data obtained by normalizing the number of pixels in each mesh in FIG.

Explanation of symbols

10 Pattern matching device 21 Dictionary

Claims (6)

A pattern matching device that recognizes characters by comparing feature data of an input character image and feature data of a plurality of categories of a dictionary,
Means for obtaining dictionary collation data which is a binary value indicating whether or not the value is equal to or less than a first threshold value for each element of each category from the feature data of a plurality of categories included in the dictionary; Means for obtaining input collation data, which is a binary value indicating whether or not each element is greater than or equal to a second threshold value from the feature data of the character image; and the dictionary collation data and the input collation data. A pattern matching apparatus comprising: means for matching and performing a matching calculation with a dictionary only for a category in which the number of matching elements is equal to or less than a predetermined value.   2. The pattern matching apparatus according to claim 1, wherein the dictionary matching data creation process is performed only once when the apparatus is activated. 3. The pattern matching apparatus according to claim 1, wherein the dictionary matching data is matched with the input matching data, and matching calculation with the dictionary is performed only for a category having zero matching elements. The pattern matching apparatus according to claim 1, wherein when the dictionary matching data and the input matching data are matched, a logical product operation is performed collectively in a certain unit. In a pattern matching program that recognizes characters by comparing feature data of an input character image with feature data of a plurality of categories that the dictionary has by controlling the computer,
  From the feature data of a plurality of categories possessed by the dictionary, dictionary collation data which is a binary value indicating whether or not each element of each category is equal to or less than a first threshold is obtained, and the input character image The input collation data which is a binary value indicating whether or not each element is equal to or greater than the second threshold is obtained from the feature data, and the dictionary collation data and the input collation data are collated and matched. A pattern matching program that performs matching calculation with a dictionary only for a category in which the number of elements to be performed is a predetermined value or less. A recording medium on which the pattern matching program according to claim 5 is recorded.

Images