JP6320089B2 - Recognition device, recognition method and program - Google Patents

Description

  Embodiments described herein relate generally to a recognition apparatus, a recognition method, and a program.

  As a method for performing knowledge processing in character recognition, a method is known in which a character string to be recognized is modeled and stored in a knowledge dictionary, and a character string matching the model is used as a result of the knowledge dictionary. For example, a system is known that includes a word dictionary unit that registers words to be collated and a word collation unit that has a finite automaton that accepts words registered in the word dictionary unit, and outputs the words received by the finite automaton as a result of knowledge processing. (For example, refer to Patent Document 1). In addition, a technique for performing knowledge processing by collating a place name notation described in a context-free grammar with a character recognition candidate is known (see, for example, Patent Document 2).

JP-A-11-143893 Japanese Patent No. 4006176

  However, the conventional technology that models the character string to be recognized and limits the result of knowledge processing to the character string that matches the model efficiently eliminates character strings that are not possible as a result of knowledge processing and unnatural character strings. It was difficult to do. For example, a character string having five or more vowel characters in English is unnatural as a word, but it has been difficult to efficiently eliminate such character strings with conventional techniques.

  The problem to be solved by the present invention is to efficiently eliminate character strings that are not used and character strings that are prohibited from being used, and recognize character strings with high accuracy.

  The recognition apparatus according to the embodiment recognizes each of the character candidates from a candidate detection unit that detects a character candidate that is a set of pixels estimated to include a character from the input image, and recognizes each of the character candidates. A recognition unit that generates at least one recognition candidate, and each of the at least one recognition candidate is compared with a knowledge dictionary that models a character string to be recognized, and is estimated to be included in the input image. A collation unit that generates a collation result obtained by collating the character string with the knowledge dictionary, and deleting a collation result obtained by collating the character string including the prohibited character string with the knowledge dictionary from the collation result. A prohibition processing unit is provided.

FIG. 1 is a diagram illustrating a configuration of a recognition device 10 according to the embodiment. FIG. 2 is a flowchart showing processing of the recognition apparatus 10 according to the embodiment. FIG. 3 is a diagram illustrating an example of an input image. FIG. 4 is a diagram showing the configuration of style data. FIG. 5 is a diagram illustrating a process for generating a series of character candidates from an input image. FIG. 6 is a diagram showing the structure of fragment data. FIG. 7 is a diagram illustrating an example of a fragment number. FIG. 8 is a diagram illustrating a configuration of character candidate data. FIG. 9 is a diagram illustrating an example of character candidate numbers. FIG. 10 is a diagram illustrating an example of the start point number and end point number of a character candidate. FIG. 11 is a diagram illustrating an example of a character candidate matrix. FIG. 12 is a diagram showing the configuration of the character recognition dictionary. FIG. 13 is a diagram showing the configuration of recognition candidate sequences. FIG. 14 is a diagram illustrating a configuration of the knowledge dictionary. FIG. 15 is a diagram showing a configuration of the prohibition dictionary. FIG. 16 is a diagram illustrating an example of a first nondeterministic finite automaton. FIG. 17 is a diagram illustrating an example of a second non-deterministic finite automaton obtained by converting the first non-deterministic finite automaton. FIG. 18 is a diagram illustrating a configuration of the collation result data. FIG. 19 is a flowchart showing the matching process. FIG. 20 is a flowchart showing the knowledge dictionary search process. FIG. 21 is a diagram illustrating an example of the flow of data access in the knowledge dictionary search process. FIG. 22 is a flowchart showing the prohibition dictionary search process. FIG. 23 is a diagram illustrating an example of the flow of data access in the forbidden dictionary search process. FIG. 24 is a flowchart showing the result extraction process. FIG. 25 is a diagram illustrating an example of data referred to in the result extraction and a character code stacked on the stack. FIG. 26 is a diagram illustrating an example of characters used as recognition results in the recognition apparatus 10 according to the modification and symbols representing the types of those characters. FIG. 27 is a diagram illustrating an example of the contents of a knowledge dictionary in which a character string recognized by the recognition apparatus 10 according to the modification is represented as a symbol string representing a character type. FIG. 28 is a diagram illustrating an example of collation result data according to the modification. FIG. 29 is a diagram illustrating a hardware configuration of the recognition apparatus 10 according to the embodiment.

  FIG. 1 is a diagram illustrating a configuration of a recognition device 10 according to the embodiment. For example, the recognition device 10 recognizes a character string included in an input image read by a scanner or the like, and outputs the recognized character string.

  The recognition device 10 includes an input unit 30, an input image storage unit 32, a style data storage unit 34, a candidate detection unit 36, a candidate storage unit 38, a character recognition dictionary storage unit 40, a recognition unit 42, knowledge A dictionary storage unit 44, a collation unit 46, a collation result storage unit 48, a prohibition dictionary storage unit 50, a prohibition processing unit 52, a result extraction unit 54, and an output unit 56 are provided.

  The input unit 30 inputs an input image captured by a scanner or the like. The input unit 30 may input an input image from another computer via a network or the like. The input image storage unit 32 stores the input image input by the input unit 30.

  The form data storage unit 34 stores form data for specifying an area in which a character string in the input image is described.

  The candidate detection unit 36 detects a character candidate from the input image based on the format data stored in the format data storage unit 34. Each character candidate is a set of pixels estimated to include one character. The candidate detection unit 36 writes the detected character candidate in the candidate storage unit 38.

  The candidate storage unit 38 stores character candidates. Furthermore, the candidate memory | storage part 38 memorize | stores the recognition candidate which is a candidate character of the recognition result of the character candidate corresponding to each of a character candidate.

  The character recognition dictionary storage unit 40 stores a character recognition dictionary. The character recognition dictionary stores information for calculating the degree of similarity between the image to be recognized and each character registered in advance.

  The recognition unit 42 recognizes each of the character candidates stored in the candidate storage unit 38 based on the character recognition dictionary stored in the character recognition dictionary storage unit 40. And the recognition part 42 produces | generates the at least 1 recognition candidate which is a candidate character of a recognition result with respect to one character candidate. The recognition unit 42 writes the generated at least one recognition candidate in the candidate storage unit 38 in association with the character candidate.

  The knowledge dictionary storage unit 44 stores a knowledge dictionary obtained by modeling a character string to be recognized. In the present embodiment, the knowledge dictionary is a deterministic finite automaton that models a character string to be recognized.

  The collation unit 46 collates each knowledge candidate with at least one recognition candidate, and generates at least one collation result obtained by collating the character string estimated to be included in the input image with the knowledge dictionary. In this process, the matching unit 46 generates a matching result including a score representing the likelihood of the corresponding character string. Then, the collation unit 46 writes the generated at least one collation result in the collation result storage unit 48.

  The collation result storage unit 48 stores at least one collation result generated by the collation unit 46. The collation result storage unit 48 stores collation results at the start point, the middle stage, and the completion point in the process of collating character strings obtained by arranging recognition candidates of character candidates with the knowledge dictionary from the top. Note that the collation unit 46 may delete a collation result having a low score for the purpose of saving the storage area in the middle of the collation.

  The prohibition dictionary storage unit 50 stores a prohibition dictionary that models a prohibited character string. In the present embodiment, the prohibition dictionary is a deterministic finite automaton that models a character string to be prohibited.

  The prohibition processing unit 52 deletes the collation result obtained by collating the character string including the prohibited character string with the knowledge dictionary from at least one collation result. In the present embodiment, the forbidden processing unit 52 collates each character string specified by the collation result with the forbidden dictionary that is a deterministic finite automaton, and responds when the character string is received by the deterministic finite automaton of the forbidden dictionary. Delete verification results.

  When the collation result obtained by collating the character string including the character string to be prohibited with the knowledge dictionary is generated in the middle stage of collation by the collation section 46, the prohibition processing section 52 deletes the collation result in the middle stage. May be. Further, after all the collations by the collation unit 46 are completed, the prohibition processing unit 52 collates whether each of a plurality of collation results includes a prohibited character string, and includes a character string including the prohibited character string. You may delete the collation result obtained by collating a knowledge dictionary.

  After all the collation by the collation unit 46 and the deletion by the prohibition processing unit 52 are completed, the result extraction unit 54 obtains one or more collation results based on the score from at least one collation result stored in the collation result storage unit 48. A character string specified by the selected one or more matching results is extracted. As an example, the result extraction unit 54 extracts a character string specified by a matching result having the best score.

  The output unit 56 outputs the character string extracted by the result extraction unit 54 to the outside.

  FIG. 2 is a flowchart showing processing of the recognition apparatus 10 according to the embodiment. First, in step S1, the recognition apparatus 10 inputs an input image.

  Subsequently, in step S <b> 2, the recognition apparatus 10 detects a character candidate that is a set of pixels presumed to include one character from the input image. Subsequently, in step S3, the recognition apparatus 10 recognizes each of the character candidates based on the character recognition dictionary, and generates at least one recognition candidate that is a candidate character of the recognition result.

  Subsequently, in step S4, the recognition apparatus 10 collates each knowledge candidate with at least one recognition candidate, and at least one obtained by collating the character string estimated to be included in the input image with the knowledge dictionary. Generate verification results. At the same time, in step S4, the recognition apparatus 10 collates each character string specified by the collation result with the prohibition dictionary, and collates the character string accepted by the deterministic finite automaton of the prohibition dictionary with the knowledge dictionary. Delete the matching result.

  Subsequently, in step S5, the recognition device 10 selects one collation result based on the score from the collation result after extracting all the collation processes, extracts a character string specified by the selected collation result, and recognizes it. The result string. When the number of character candidates is 0, that is, when no character is included in the input image, a collation result to be selected is not generated in step S5. In this case, the character string of the recognition result is an empty character string. Finally, in step S6, the recognition device 10 outputs a character string as a recognition result.

  FIG. 3 is a diagram illustrating an example of an input image. In the present embodiment, as shown in FIG. 3, the input image is image data obtained by taking an order form for ordering a product with a scanner or the like. The name of the orderer is entered inside a predetermined entry frame of the input image. In the present embodiment, the recognition apparatus 10 recognizes a character string with a Japanese name entered inside a predetermined entry frame, and outputs text data representing the recognized character string.

  FIG. 4 is a diagram showing the configuration of style data. The form data storage unit 34 stores form data created in advance.

  As shown in FIG. 4, the format data includes a value indicating the number of entry frames included in the input image and an array for storing entry frame records for the number of entry frames. In this example, the index of the first entry in the array is zero. That is, the sequence is 0 origin. Other sequences used in this embodiment are also 0 origin unless otherwise specified. Each entry frame record corresponds to each entry frame included in the input image on a one-to-one basis.

  Each entry frame record includes information indicating the position of the corresponding entry frame in the input image. In this example, the information indicating the position of the entry frame is the X coordinate (horizontal coordinate) of the left and right ends and the Y coordinate (vertical coordinate) of the upper and lower ends of the corresponding entry frame.

  FIG. 5 is a diagram illustrating a process for generating a series of character candidates from an input image. The candidate detection unit 36 specifies an area of the entry frame based on the information indicated in the entry frame record (for example, an area surrounded by a dotted line in FIG. 5), and extracts a partial area image from the specified area. Subsequently, the candidate detection unit 36 binarizes the extracted partial region image to generate a binary image. Subsequently, the candidate detection unit 36 extracts black pixel connected components on the binary image and performs labeling on each connected component. Each labeled connected component is an element constituting a character and is called a fragment. Subsequently, the candidate detection unit 36 generates a character candidate by combining one or more pieces arranged in a row. A character candidate is a set of pixels presumed to represent one character.

  FIG. 6 is a diagram showing the structure of fragment data. The candidate storage unit 38 stores fragment data representing a fragment. As shown in FIG. 6, the fragment data includes a value indicating the number of fragments and an array for storing fragment records for the number of fragments. Each fragment record has a one-to-one correspondence with each fragment.

  Each fragment record includes information indicating the position of the corresponding fragment and a binary image indicating the shape of the fragment. In this example, the information indicating the position of the fragment is the X coordinate of the left and right ends of the corresponding fragment and the Y coordinate of the upper and lower ends, and indicates the circumscribed rectangle of the fragment. A binary image indicating the shape of a fragment is an image in which pixels on the connected component are black pixels and the rest are white pixels in a circumscribed rectangle of the fragment.

  The candidate detection unit 36 calculates the center X coordinate and the center Y coordinate for each fragment. The center X coordinate is an average value of the X coordinates of the left and right ends. The center Y coordinate is an average value of the Y coordinates of the upper and lower ends. Then, the candidate detection unit 36 sorts the plurality of fragment records in the array in ascending order of the center X coordinate. Thereby, the candidate detection unit 36 can align the plurality of fragment records in the array in the character entry direction in the entry frame (in this example, the direction from left to right).

  FIG. 7 is a diagram illustrating an example of a fragment number. Each fragment record is identified by an array index. The index after the fragment records are arranged in the character entry direction is called a fragment number. Therefore, each fragment is associated with a fragment number as shown in FIG.

  FIG. 8 is a diagram illustrating a configuration of character candidate data. The candidate detection unit 36 generates a character candidate by combining one or more pieces arranged in a row. In this process, the candidate detection unit 36 generates a character candidate by combining one or more fragments in all patterns in which the lateral width L of the circumscribed rectangle is equal to or less than a predetermined length (Lmax).

  The candidate storage unit 38 stores character candidate data representing character candidates. As shown in FIG. 8, the character candidate data includes a value indicating the number of generated character candidates, a character candidate matrix (described later in detail), and an array for storing character candidate records for the number of character candidates. Each character candidate record has a one-to-one correspondence with each character candidate.

  Each character candidate record includes information indicating the position of the corresponding character candidate, a start point number and an end point number (described later in detail) of the corresponding character candidate, a binary image indicating the shape of the character candidate, and a recognition candidate entry. Includes recognition candidate sequences (described in detail below). In this example, the information indicating the position of the character candidate is the X coordinate of the left and right ends and the Y coordinate of the upper and lower ends of the corresponding character candidate, and indicates the circumscribed rectangle of the character candidate on the binary image. A binary image showing the shape of a character candidate is an image in which the pixels on the character candidate are black pixels and the rest are white pixels in the circumscribed rectangle of the character candidate. A value of the recognition candidate entry is set by the recognition unit 42, and no value is set by the candidate detection unit 36.

  FIG. 9 is a diagram illustrating an example of character candidate numbers. Each character candidate record is identified by an array index. The index of the character candidate record is called a character candidate number. Therefore, a character candidate number is associated with each character candidate as shown in FIG.

  FIG. 10 is a diagram illustrating an example of the start point number and end point number of a character candidate. Character candidates are generated by combining one or more pieces arranged in series. For this reason, character candidates are uniquely identified by a set of a fragment number for the first fragment in the sequence of one or more fragments as a source and a value obtained by adding 1 to the fragment number for the last fragment. Can do.

  In this embodiment, the fragment number for the first fragment is called the start point number of the character candidate, and the value obtained by adding 1 to the fragment number for the last fragment is called the end point number of the character candidate. Accordingly, each character candidate is associated with a start point number and an end point number as shown in FIG. Note that the start point number and the end point number represent character character delimiter positions, and thus both the start point number and the end point number are collectively referred to as position numbers.

  FIG. 11 is a diagram illustrating an example of a character candidate matrix. As shown in FIG. 11, the character candidate matrix is a two-dimensional array of character candidate numbers having a start point number as a first index and an end point number as a second index. The character candidate matrix is initialized by setting all entries to -1 before starting the generation of character candidate records. Each time the candidate detection unit 36 creates a character candidate, it writes the character candidate number in the corresponding entry of the character candidate matrix.

  FIG. 12 is a diagram showing the configuration of the character recognition dictionary. The character recognition dictionary storage unit 40 stores a character recognition dictionary created in advance. As shown in FIG. 12, the character recognition dictionary includes a value indicating the number of dictionary entries and an array for storing dictionary entries.

Each dictionary entry includes a character code and predetermined D _sub basis vectors. A base vector is a feature vector of a subspace representing a character corresponding to a character code. As an example, the feature vector is obtained by dividing a binary image of a corresponding character by a predetermined number in the vertical direction and the horizontal direction, obtaining a ratio of the number of black pixels in each divided area, It is calculated by using the ratio as an element of the feature vector.

FIG. 13 is a diagram showing the configuration of recognition candidate sequences. The recognition candidate array stored in the character candidate record includes predetermined N _cand recognition candidate entries as shown in FIG. Each recognition candidate entry includes a character code and a similarity.

The recognition unit 42 performs character recognition for each of the character candidates, and generates at least one recognition candidate that is a candidate character of the recognition result. In the present embodiment, the recognition unit 42 generates N _cand recognition candidate entries determined in advance for each character candidate record, and writes them in the recognition candidate array.

More specifically, the recognition unit 42 extracts a feature vector from a binary image included in the corresponding character candidate record, and collates it with a base vector stored in each dictionary entry of the character recognition dictionary by a subspace method. To calculate the similarity. The recognizing unit 42 extracts the character code stored in the dictionary entry for each of the top N _cand dictionary entries having the similarity, and generates a recognition candidate entry including the extracted character code and the calculated similarity. Then, the recognition unit 42 _writes the generated N _cand recognition candidate entries in the recognition candidate array of the corresponding character candidate record. Furthermore, the recognition unit 42 arranges the recognition candidate entries included in the recognition candidate arrays of the respective character candidate records in descending order of similarity.

  FIG. 14 is a diagram illustrating a configuration of the knowledge dictionary. The knowledge dictionary storage unit 44 stores a knowledge dictionary created in advance by a designer or the like.

  In the present embodiment, the knowledge dictionary is a deterministic finite automaton that models a character string to be recognized. In the present embodiment, a knowledge dictionary that is a deterministic finite automaton is also referred to as DFAα. For example, DFAα is generated by a designer describing a character string to be recognized in a regular expression and converting the regular expression into a deterministic finite automaton.

  As shown in FIG. 14, DFAα includes a value indicating the number of states, a state array for storing state records for the number of states, and an edge array for storing edge records for the number of edges.

  Each state record has a one-to-one correspondence with each state included in DFAα, and the state is uniquely identified by the number of the state record, that is, the state number. It should be noted that the state array is 0 origin, and therefore the state with the state number 0 is the start state. Each status record includes an acceptance status flag, a pointer to the edge record in the edge array, and the number of elements in the edge record.

  The acceptance state flag indicates whether or not the state is an acceptance state. As an example, the acceptance status flag indicates that it is in an acceptance state when it is 1, and indicates that it is not in an acceptance state when it is 0.

  The pointer to the edge record indicates the storage position of the set of edges that exit from the state in the edge array. The number of elements in the edge record represents the number of edges that exit from the state. The edge record corresponding to all the edges going out from the state can be specified by the pointer to the edge record and the number of elements.

  Each edge record has a one-to-one correspondence with each edge included in DFAα. Each edge record includes a transition destination state number and a code.

  The state number of the transition destination represents a state number that specifies the state of the transition destination by the edge.

  The code represents the input symbol that causes the transition represented by the edge. In the present embodiment, a character code representing a character is stored in the code. Therefore, in DFAα, a transition from one state to another state occurs due to a character code representing a recognition candidate character.

  FIG. 15 is a diagram showing a configuration of the prohibition dictionary. The prohibition dictionary storage unit 50 stores a prohibition dictionary created in advance by a designer or the like.

  In the present embodiment, the prohibition dictionary is a deterministic finite automaton that models a prohibited character string. The prohibited character strings are character strings that are prohibited from being input, character strings that cannot be input, unnatural character strings, and the like, and are defined by, for example, a designer. In this embodiment, the prohibition dictionary that is a deterministic finite automaton is also called DFAβ.

  As shown in FIG. 15, DFAβ includes a value indicating the number of states, a state array for storing state records for the number of states, and an edge array for storing edge records for the number of edges. Since each element constituting the forbidden dictionary is the same as the knowledge dictionary (DFAα) shown in FIG. 14, detailed description thereof will be omitted.

  In DFAβ, a designer describes a prohibited character string in a regular expression (modeled), converts the regular expression into a first nondeterministic finite automaton, and converts the first nondeterministic finite automaton into a second nondeterministic It is obtained by converting to a finite automaton and converting the second non-deterministic finite automaton to a deterministic automaton.

  FIG. 16 is a diagram illustrating an example of a first nondeterministic finite automaton. FIG. 17 is a diagram illustrating an example of a second non-deterministic finite automaton obtained by converting the first non-deterministic finite automaton. In the automaton shown in FIG. 16, the input symbol string on the path from the start state to the acceptance state represents a character string to be prohibited.

  The second non-deterministic finite automaton is obtained by converting the first non-deterministic finite automaton as shown in FIG. 16 by the following procedure. First, the first nondeterministic finite automaton is returned from the start state to the start state, and an edge of a self-loop in which all characters (codes) are assigned as input symbols is added. Subsequently, the automaton with the added self-loop returns to the start state from each of the states other than the start state, and adds an empty edge (ε transition) to which the empty symbol ε is assigned as an input symbol. A second non-deterministic finite automaton as shown in 17 is obtained.

  That is, in the second nondeterministic finite automaton, as shown in FIG. 17, the input symbol string on the path from the start state to the accepting state represents a prohibited character string. In addition, the second nondeterministic finite automaton returns from the start state to the start state and returns to the start state from each of the states other than the start state and the edge of the self-loop where all characters are assigned as input symbols. An empty symbol contains an empty edge assigned as an input symbol.

  DFAβ obtained by converting the second non-deterministic finite automaton configured as described above into a deterministic finite automaton is a model of a prohibited character string, and includes a character string including the prohibited character string. It is configured so that a transition to the accepting state is surely made when the is input.

  Note that a method for generating a nondeterministic finite automaton or a deterministic finite automaton from a regular expression, and a method for generating a deterministic finite automaton from a nondeterministic finite automaton are described in, for example, A. V. Aiho, R.A. Cessie, J.H. D. Written by Ullman, translated by Kenichi Harada, Compiler I, first edition 1986, pp. 134-172 and the like.

  FIG. 18 is a diagram illustrating a configuration of the collation result data. The collation unit 46 collates each of the recognition candidates included in the character candidates with the knowledge dictionary sequentially from the top, and collates the character string estimated to be described in the entry frame of the input image with the knowledge dictionary. The verification result obtained is obtained. Then, the matching unit 46 writes the generated matching result in the matching result storage unit 48. At the same time, the forbidden processing unit 52 collates the character string specified by the collation result with the forbidden dictionary, and deletes the collation result representing the character string accepted by the deterministic finite automaton of the forbidden dictionary from the collation result storage unit 48. To do.

  The verification result storage unit 48 stores verification result data. The collation result data includes the number of collation results and an array of collation results for each position number.

  The number of matching results represents the number of matching results associated with the position number. The collation result array stores the collation result associated with the position number. Each collation result includes a pair of a state number α, a state number β, a score, a code, a position number, and a collation result number. Each collation result is uniquely identified by a pair of a position number associated with the storage destination array and a number as an array element in the storage destination array. From now on, the position number associated with the collation result storage array is referred to as "position number associated with the collation result", and the number as the array element in the collation result storage array is referred to as "collation result number". It is called.

  The state number α represents the state of the knowledge dictionary (DFAα). That is, the state number α indicates a state reached when DFAα is sequentially shifted from the start state in accordance with each character from the first recognition candidate to the recognition candidate at the position.

  The state number β represents the state of the forbidden dictionary (DFAβ). That is, the state number β indicates a state reached when DFA β is sequentially shifted from the start state in accordance with each character included in the character string specified by the collation result.

  The score represents a value obtained by accumulating the degrees of similarity associated with the recognition candidates at the head to the recognition candidates at the position. That is, the score represents the likelihood of the character string from the first recognition candidate to the recognition candidate at the position. The code is a character code representing a recognition candidate character at the position.

  The pair of the position number and the number of the matching result is obtained immediately after the character candidate is traced one by one from the head to the corresponding position while the matching result is generated while the DFAα is transitioned using the character candidate recognition candidate as the input symbol. It represents the position number associated with the collation result and the number of the previous collation result. The pair of the position number and the collation result number is referred to when the result extraction unit 54 extracts the character string of the recognition result.

  FIG. 19 is a flowchart showing the matching process. Details of the collation process shown in step S4 of FIG. 2 will be described with reference to FIG.

  First, in step S11, the collation unit 46 initializes collation result data. Specifically, the collation unit 46 sets the number of collation results to 0 for all the position numbers of the collation result data and empties the collation result array.

  Subsequently, in step S12, the collation unit 46 generates a new collation result in association with the position number 0. In the new collation result, the state number α and the state number β are set to 0, the score is set to 0, the position number and the collation result number are set to −1, and the code is set to −1. Subsequently, in step S13, the matching unit 46 sets the number of matching results associated with the position number 0 to 1. Subsequently, in step S14, the collation unit 46 substitutes 0 for a variable Pst representing the position number.

  Subsequently, in step S15, the collation unit 46 determines whether or not Pst is equal to or less than Pstmax. Pstmax is a value obtained by subtracting 1 from the last position number Ped. When Pst is equal to or less than Pstmax (true in step S15), the collation unit 46 advances the process to step S16.

  In step S <b> 16, the collation unit 46 calls the prohibition processing unit 52. In step S <b> 16, the prohibition processing unit 52 executes a prohibition dictionary search process using the prohibition dictionary for each matching result associated with the position number Pst. Thereby, the prohibition processing unit 52 can delete the collation result obtained by collating the character string including the character string to be prohibited with the knowledge dictionary. Details of the prohibition dictionary search process will be described later with reference to FIGS.

  Subsequently, in step S <b> 17, the matching unit 46 narrows down the matching results associated with Pst from the highest score to the Npr-th score. That is, the matching unit 46 deletes the matching result whose score is lower than the Nprth.

  Subsequently, in step S18, the collation unit 46 executes a knowledge dictionary search process using the knowledge dictionary for each collation result associated with Pst. Thereby, the collation part 46 can produce | generate the new collation result linked | related with the position number after Pst. The knowledge dictionary search process will be described later with reference to FIGS. 20 and 21.

  Subsequently, in step S19, the collation unit 46 adds 1 to Pst. The collation part 46 will return a process to step S15, after complete | finishing step S19. And the collation part 46 repeats the process of step S16 to step S19 until Pst exceeds Pstmax.

  When Pst is no longer equal to or less than Pstmax (No in step S15), the collation unit 46 advances the process to step S20. In step S <b> 20, the collation unit 46 calls the prohibition processing unit 52. In step S20, the prohibition processing unit 52 performs a prohibition dictionary search process using the prohibition dictionary for each matching result associated with the last position number Ped. Thereby, the prohibition processing unit 52 can delete the collation result obtained as a result of collating the character string to be prohibited with the knowledge dictionary. And the collation part 46 complete | finishes this flow, after finishing the process of step S20.

  FIG. 20 is a flowchart showing the knowledge dictionary search process. FIG. 21 shows an example of the flow of data access in the knowledge dictionary search process.

  The knowledge dictionary search process in step S18 of FIG. 19 will be described with reference to FIGS. First, in step S31, the collation unit 46 refers to the collation result data and lists all the collation results associated with Pst.

  Subsequently, in step S32, the collation unit 46 refers to the character candidate records in the character candidate data array, and lists all the character candidates having Pst as the starting point position. The collating unit 46 scans all entries whose starting point numbers match Pst in the character candidate matrix and collects all character candidates having Pst as the starting point position by collecting the numbers of character candidates other than -1. be able to.

  Subsequently, the collation unit 46 performs the processing of step S34 to step S48 for each of all the character candidate records listed in step S32 (loop processing between step S33 and step S49). Hereinafter, the character candidate corresponding to the character candidate record to be processed in this loop processing is referred to as “character candidate Cc”.

  In step S34, the collation unit 46 refers to the recognition candidate array of the character candidate record corresponding to the character candidate Cc, and lists all recognition candidate entries of the character candidate.

  Subsequently, the collation unit 46 performs the processing of Step S36 to Step S47 for each of all the recognition candidate entries listed in Step S34 (loop processing between Step S35 and Step S48). Hereinafter, the recognition candidate corresponding to the recognition candidate entry to be processed in this loop processing is referred to as “recognition candidate Cr”.

  Subsequently, the collation unit 46 performs the processing of step S37 to step S46 on each of all the collation results associated with Pst listed in step S31 (loop between step S36 and step S47). processing). Hereinafter, the verification result to be processed in this loop process is referred to as “matching result Mp”.

  In step S37, the collation unit 46 refers to the knowledge dictionary (DFAα) and enumerates state records corresponding to the state number α included in the collation result Mp.

  Subsequently, in step S38, the collation unit 46 creates an edge record representing an edge that exits from the state of the state number α based on the pointer to the edge record included in the state record enumerated in step S37 and the number of elements of the edge record. By specifying the stored range, all edge records representing the edges going out from the state of the state number α are listed.

  Subsequently, the collation unit 46 performs the processing of Step S40 to Step S45 for each of all the edge records listed in Step S38 (loop processing between Step S39 and Step S46). Hereinafter, the edge record to be processed in this loop processing is referred to as “edge record Er”.

  In step S40, the collation unit 46 determines whether or not the character code set in the recognition candidate entry of the recognition candidate Cr matches the character code set in the edge record Er. If they do not match (No in step S40), the collation unit 46 moves the process to the next edge record and repeats the process from step S40. If they match (Yes in step S40), the collation unit 46 advances the process to step S41.

  In step S41, the collation unit 46 generates a new collation result Mn in association with the end point position of the character candidate record of the character candidate Cc, and writes it in the collation result data.

  Subsequently, in step S42, the collation unit 46 sets the state number (transition destination state number) set in the edge record Er as the state number α in the new collation result Mn. The collation unit 46 sets −1 as the state number β in the new collation result Mn.

  Subsequently, in step S43, the collation unit 46 sets the character code set in the recognition candidate entry of the recognition candidate Cr as a code for the new collation result Mn.

  Subsequently, in step S44, the collation unit 46 sets the position number Pst associated with the collation result Mp as the position number for the new collation result Mn. The collation unit 46 stores the number of the collation result Mp as the collation result number in the new collation result Mn.

  Subsequently, in step S45, the matching unit 46 sets a value obtained by adding the score stored in the matching result Mp and the similarity stored in the recognition candidate entry of the recognition candidate Cr as a score to the new matching result Mn. .

  In step S46, the collation unit 46 exits from the loop and proceeds to step S47 after completing the process of steps S40 to S45 for all edge records.

  In step S47, the collation unit 46 exits from the loop and proceeds to step S48 after completing the processes of step S37 to step S46 for all the collation results associated with Pst.

  In step S48, the collation unit 46 exits from the loop and proceeds to step S49 after completing the process of steps S36 to S47 for all the recognition candidate entries corresponding to the character candidate Cc.

  In step S49, the collation unit 46 exits from the loop and ends the present flow after completing the processes in steps S34 to S48 for all the character candidate records.

  As described above, the collation unit 46 writes the number (state number α) indicating the state of the knowledge dictionary (DFAα) reached by collation in the collation result of the first character candidate. Then, when the collation unit 46 collates the second character candidate following the first character candidate with the knowledge dictionary (DFAα), the collation unit 46 indicates the number (state number α) written in the collation result of the first character candidate. The second character candidate is collated by following the edge corresponding to the state transition by the recognition candidate of the second character candidate.

  FIG. 22 is a flowchart showing the prohibition dictionary search process. FIG. 23 shows a data flow in the forbidden dictionary search process.

  The forbidden dictionary search process will be described with reference to FIGS. First, in step S51, the prohibition processing unit 52 refers to the collation result data and lists all the collation results associated with Pst.

  Subsequently, the prohibition processing unit 52 executes the processing of step S53 to step S62 for each of all the matching results listed in step S51 (loop processing between step S52 and step S63). Hereinafter, the verification result to be processed in this loop process is referred to as “matching result Mt”.

  In step S53, the prohibition processing unit 52 acquires the matching result M immediately before specified by the position number and the matching result number stored in the matching result Mt.

  Subsequently, in step S54, the prohibition processing unit 52 refers to the prohibition dictionary (DFAβ), and acquires a state record corresponding to the state number β stored in the previous matching result M.

  Subsequently, in step S55, the prohibition processing unit 52 determines an edge that exits from the state of the state number β based on the pointer to the edge record stored in the state record acquired in step S54 and the number of elements of the edge record. By specifying the range in which the edge records to be represented are stored, all edge records representing the edges going out from the state of the state number β are listed.

  Subsequently, in the loop process between step S56 and step S58, the prohibition processing unit 52 executes the determination process of step S57 for each of all the edge records listed in step S55. Hereinafter, the edge record to be processed in this loop processing is referred to as “edge record Et”.

  In step S57, the prohibition processing unit 52 determines whether or not the character code stored in the verification result Mt to be processed matches the character code stored in the edge record Et. If they do not match (No in step S57), the prohibition processing unit 52 proceeds to the next edge record process and repeats the process in step S57. If they match (Yes in step S57), the forbidden processing unit 52 exits the loop process between step S56 and step S58, and advances the process to step S59.

  In step S59, the prohibition processing unit 52 confirms the acceptance state flag of the state record St specified by the state number of the transition destination of the edge record Et, and whether or not the state of DFAβ corresponding to the state record St is an acceptance state. Determine whether.

  When it is in the accepting state (Yes in step S59), in step S61, the prohibition processing unit 52 deletes the matching result Mt. When it is not in the accepting state (No in step S59), in step S60, the prohibition processing unit 52 sets the state number of the transition destination of the edge record Et as the state number β in the matching result Mt.

  In the loop processing between step S56 and step S58, the prohibition processing unit 52 advances the processing to step S62 when the character codes do not match for all edge records. In step S62, the prohibition processing unit 52 sets 0 representing the initial state as the state number β in the matching result Mt.

  When the process of step S60, step S61, or step S62 is completed, the prohibition processing unit 52 repeats the process from step S52 for the next matching result.

  In step S63, the forbidden processing unit 52 exits the loop after completing the processing of step S53 to step S62 for all the matching results, and ends this flow.

  As described above, the prohibition processing unit 52 writes the number (state number β) indicating the state of the prohibition dictionary (DFAβ) reached by collating the character string specified by the first collation result into the first collation result. . Then, when the prohibition processing unit 52 collates the character string specified by the second collation result obtained by collating the second character candidate following the first collation result with the knowledge dictionary (DFAα), The character string specified by the second collation result is collated by following the edge corresponding to the state transition by the recognition candidate of the second character candidate from the state of DFAβ indicated by the number written in the collation result of 1. .

  FIG. 24 is a diagram illustrating a flow of result extraction processing performed by the result extraction unit. FIG. 25 is a diagram illustrating data referred to in the result extraction and a state of character codes stacked on the stack.

  The result extraction shown in step S5 of FIG. Hereinafter, details of the result extraction will be described with reference to FIGS. 24 and 25. First, in step S70, the result extraction unit 54 checks whether or not the number of character candidates is 0. If the number of character candidates is 0, the flow ends with the recognition result character string as an empty character string in step S84. To do. If the number of character candidates is not 0, in step S71, the result extraction unit 54 enumerates all the collation results associated with the last position number Ped, and then executes the processing after step S72.

  Subsequently, in step S72, the result extraction unit 54 acquires a state record corresponding to the state number α from the knowledge dictionary (DFAα) for each of the matching results listed in step S71, and confirms the acceptance state flag.

  Subsequently, in step S73, the result extraction unit 54 determines whether there is a collation result in which the state corresponding to the state number α is an accepted state. Hereinafter, the collation result in which the state corresponding to the state number α is the accepting state is referred to as “the collation result of the accepting state with DFAα”. When there is a matching result in the accepted state in DFAα (Yes in step S73), in step S74, the result extracting unit 54 sets the matching result having the maximum score among the matching results in the accepted state in DFAα as the matching result Mx. select. When there is no collation result in the accepted state in DFAα (No in step S73), in step S75, the result extraction unit 54 selects the collation result having the maximum score as the collation result Mx among all the collation results listed. To do.

  Subsequent to step S74 or step S75, in step S76, the result extraction unit 54 substitutes the position number px associated with the selected matching result Mx for the variable p representing the position number. Further, the result extraction unit 54 substitutes the number mx of the selected matching result Mx into the variable m representing the number of the matching result.

  Subsequently, in step S77, the result extraction unit 54 empties the stack which is a FILO (First In Last Out) memory.

  Subsequently, in step S78, it is determined whether the collation result code indicated by p and m is -1. When the code of the collation result indicated by p and m is not −1 (false in step S78), the result extraction unit 54 advances the process to step S79.

  In step S79, the result extraction unit 54 loads the code stored in the matching result indicated by p and m on the stack. Subsequently, in step S80, the result extraction unit 54 sets the position number stored in the matching result indicated by p and m to p, and the number of the matching result stored in the matching result indicated by p and m in p. substitute.

  And the result extraction part 54 complete | finishes the process of step S80, returns a process to step S78, and until the code stored in the collation result which p and m point to becomes -1, the process of step S79 and step S80 is carried out. Repeat the process. Thereby, as shown in FIG. 25, the result extraction unit 54 can select character codes in order from the end of the character string and accumulate them in the stack.

  When the code of the matching result pointed to by p and m is −1 (true in step S78), that is, when the position number indicates the matching result associated with 0, the result extraction unit 54 performs the process. Proceed to S81. In step S81, the result extraction unit 54 initializes the character string of the recognition result stored in the memory to an empty character string.

  Subsequently, in step S82, it is determined whether the stack is empty. If the stack is not empty (false in step S82), the result extraction unit 54 extracts one code from the top of the stack and adds it to the end of the character string of the recognition result stored in the memory in step S83.

  When the process of step S83 is completed, the result extraction unit 54 returns the process to step S82 and repeats the process of step S83 until the stack becomes empty. As a result, the result extraction unit 54 can generate the character string from the beginning to the end.

  Then, when the stack becomes empty (true in step S82), the result extraction unit 54 ends the process of this flow.

  As described above, the recognition apparatus 10 according to the present embodiment uses the prohibition dictionary that models the prohibited character string, and collates the character string including the prohibited character string with the knowledge dictionary. Delete the result. Thereby, the recognition apparatus 10 according to the present embodiment can efficiently eliminate character strings that are not used and character strings that are prohibited from being used, and recognize character strings with high accuracy.

(Modification)
The recognition apparatus 10 according to the modified example refers to FIG. 1 to FIG. 25 except that the knowledge dictionary and the format of the verification result data are different from the functions of the verification unit 46, the prohibition processing unit 52, and the result extraction unit 54. The configuration is the same as described above. Hereinafter, the recognition apparatus 10 according to the modification will be described with respect to differences from the configuration described with reference to FIGS.

  FIG. 26 is a diagram illustrating an example of characters used as recognition results in the recognition apparatus 10 according to the modification and symbols representing the types of those characters. FIG. 27 is a diagram illustrating an example of the contents of a knowledge dictionary in which a character string recognized by the recognition apparatus 10 according to the modification is represented as a symbol string representing a character type.

  The recognition apparatus 10 according to the modification uses a knowledge dictionary that models a character string in which symbols representing character types are arranged. For example, the symbols indicating the type of character include a symbol “N” indicating a number from 1 to 9, a symbol “n” indicating a number from 0 to 9, a symbol “−” indicating a hyphen, an apartment name, and an apartment name. The symbol “M” representing the letter used for the building name is used. The knowledge dictionary includes a wild card character string in which these symbols are arranged as shown in FIG.

  FIG. 28 is a diagram illustrating an example of collation result data according to the modification. In this modification, each of the matching results included in the matching result data includes a set of a score s, the number of replaced characters c, and a character string w in which a wild card character string is partially replaced with a recognition result.

  The collation result data includes an array in which the collation result is stored and the number of elements of the array corresponding to each position number. Note that in FIG. 28, the character that indicates the underline of the character string w of the collation result indicates a portion in which the wild card is replaced with the recognition result.

  In this modification, the collation unit 46 first copies each character string included in the knowledge dictionary and sets it as an element of the collation result array of position number 0, thereby initializing the collation result array of position number 0. Turn into. In each collation result, 0 is set as the score, 0 is the number of replaced characters, and a character string copied from the knowledge dictionary is set as the character string w. Subsequently, the collation unit 46 generates a collation result after the position number Pst + 1 while sequentially increasing the position number Pst by 1 from 1 to Pstmax.

  In this modification, the collation unit 46 acquires the number c of replaced characters of the collation result in the knowledge dictionary search process, and the c-th character of the character string w of the collation result is the character code of the recognition candidate Cr of the character candidate Cc. Is matched with the position number equal to the end point number of the character candidate Cc, a new matching result Mn is generated. In the new collation result Mn, the score obtained by adding the similarity of the recognition candidate Cr to the score of the previous collation result, the number of replaced characters c + 1, and the c-th character in the character string w of the collation result are replaced with the recognition candidate Cr. Set to a character string.

  In this modification, the prohibition processing unit 52 acquires the number c of replaced characters in the matching result in the prohibition dictionary search process, and stores the partial character string up to the c-1th character in the matching result character string in the prohibition dictionary. It is confirmed whether or not it is accepted by the registered DFAβ. Then, the prohibition processing unit 52 deletes the matching result when it is accepted, and leaves the matching result when it is not accepted.

  As described above, the recognition apparatus 10 may collate character strings by any method as long as it obtains a collation result by collating a knowledge dictionary that models a character string to be recognized with character candidates. . The recognition device 10 may detect the prohibited character string by any method as long as it is a method for detecting the prohibited character string from the collation result.

  FIG. 29 is a diagram illustrating a hardware configuration of the recognition apparatus 10 according to the embodiment.

  The recognition apparatus 10 can be realized by a general computer system that can execute a program. As an example, the recognition device 10 includes a display 110, a keyboard 112, a scanner 114, an external storage device 116, a communication device 118, and a computer 120.

  The display 110 is a display device and displays a recognized character string or the like. The keyboard 112 is an input device, and receives information from a user and inputs information. The scanner 114 obtains an input image or the like by reading information written on a sheet or the like. The external storage device 116 is a hard disk drive or an optical disk drive, and stores various types of information. The communication device 118 inputs and outputs information with an external computer or the like via the Internet or the like, and acquires, for example, an input image from the outside or outputs a character string to the outside.

  As an example, the computer 120 includes a CPU 122, an input / output control unit 124, and a storage device 126. The CPU 122, the input / output control unit 124, and the storage device 126 are connected by a bus 128.

  The CPU 122 executes a program to control the entire recognition apparatus 10. The input / output control unit 124 is an interface with the display 110, the keyboard 112, the scanner 114, the external storage device 116, the communication device 118, and the like. The input / output control unit 124 also controls data transfer via the bus 128.

  The storage device 126 includes a ROM, a RAM, a hard disk drive, or the like. In the storage device 126, any device such as a ROM, a RAM, or a hard disk drive can be accessed by the same address space. The storage device 126 stores programs, input images, style data, dictionary data (character recognition dictionary, knowledge dictionary and prohibition dictionary), work data (character candidates and collation results), and the like. These data may be stored in any device (ROM, RAM, and hard disk drive) constituting the storage device. In addition, part or all of these data may be stored in a server or the like accessed via the external storage device 116 or the communication device 118.

  The program executed by the recognition apparatus 10 of the present embodiment is an installable or executable file, and is a computer-readable recording medium such as a CD-ROM, a flexible disk (FD), a CD-R, or a DVD. Recorded and provided. The program executed by the recognition apparatus 10 of the present embodiment may be configured to be stored by being stored on a computer connected to a network such as the Internet and downloaded via the network. Further, the program executed by the recognition apparatus 10 of the present embodiment may be configured to be provided or distributed via a network such as the Internet.

  The program executed by the recognition apparatus 10 of this embodiment includes the above-described units (the input unit 30, the candidate detection unit 36, the recognition unit 42, the collation unit 46, the prohibition processing unit 52, the result extraction unit 54, and the output unit 56). As the actual hardware, the CPU 122 (processor) reads the program from the storage medium and executes it to load the respective units onto the main storage device, and the input unit 30 and the candidate detection unit 36. The recognition unit 42, the collation unit 46, the prohibition processing unit 52, the result extraction unit 54, and the output unit 56 are generated on the storage device 126. The input unit 30, the candidate detection unit 36, the recognition unit 42, the collation unit 46, the prohibition processing unit 52, the result extraction unit 54, and the output unit 56 may be partially or entirely configured by hardware.

  Although several embodiments of the present invention have been described, these embodiments are presented by way of example and are not intended to limit the scope of the invention. These novel embodiments can be implemented in various other forms, and various omissions, replacements, and changes can be made without departing from the scope of the invention. These embodiments and modifications thereof are included in the scope and gist of the invention, and are included in the invention described in the claims and the equivalents thereof.

DESCRIPTION OF SYMBOLS 10 Recognition apparatus 30 Input part 32 Input image memory | storage part 34 Style data memory | storage part 36 Candidate detection part 38 Candidate memory | storage part 40 Character recognition dictionary memory | storage part 42 Recognition part 44 Knowledge dictionary memory | storage part 46 Collation part 48 Collation result memory | storage part 50 Forbidden dictionary memory | storage Unit 52 prohibition processing unit 54 result extraction unit 56 output unit 110 display 112 keyboard 114 scanner 116 external storage device 118 communication device 120 computer 122 CPU
124 I / O controller 126 Storage device 128 Bus

Claims (10)

A candidate detection unit that detects a character candidate that is a set of pixels estimated to include a character from the input image;
A recognition unit that recognizes each of the character candidates and generates at least one recognition candidate that is a candidate character of a recognition result;
Each of the at least one recognition candidate is collated with a knowledge dictionary obtained by modeling a character string to be recognized, and a collation result obtained by collating a character string estimated to be included in the input image with a knowledge dictionary is obtained. A verification unit to be generated;
Among the matching results, a prohibition processing unit for deleting a matching result obtained by matching a character string including a prohibited character string and a knowledge dictionary;
A recognition device comprising: The matching unit generates a matching result including a score representing the likelihood of the corresponding character string,
The recognition apparatus according to claim 1, further comprising: a result extraction unit that selects one matching result based on the score from the matching result and extracts a character string specified by the selected matching result. The recognition apparatus according to claim 1, wherein the knowledge dictionary is a finite automaton that models a character string to be recognized. The knowledge dictionary is a first deterministic finite automaton;
The collation unit
Write a number indicating the state of the first deterministic finite automaton reached by collation to the collation result of the first character candidate,
When collating the second character candidate following the first character candidate with the first deterministic finite automaton, the second character candidate from the state indicated by the number written in the collation result of the first character candidate The recognition apparatus according to claim 3, wherein the second character candidate is collated by following an edge corresponding to the state transition by the recognition candidate. The forbidden processing unit is obtained by collating the character string specified by the collation result with a forbidden dictionary that models the forbidden character string and collating a character string including the forbidden character string with a knowledge dictionary. The recognition apparatus according to claim 1, wherein the verification result is deleted. The recognition apparatus according to claim 5, wherein the prohibition dictionary is a finite automaton that models a character string to be prohibited. The forbidden dictionary is a second deterministic finite automaton;
The prohibition processing unit is
A number indicating the state of the second deterministic finite automaton reached by collating the character string specified by the first collation result is written to the first collation result;
When collating a character string specified by a second collation result obtained by collating the second character candidate following the first collation result with the second deterministic finite automaton, the first collation result The character string specified by the second collation result is collated by following the edge corresponding to the state transition by the recognition candidate of the second character candidate from the state indicated by the number written in The recognition device described. The second deterministic finite automaton is
The recognition apparatus according to claim 7, wherein when a character string including a prohibited character string is input, the recognition apparatus is configured to transition to an acceptance state. A candidate detection step of detecting a character candidate that is a set of pixels presumed to include a character from the input image;
A recognition step of recognizing each of the character candidates and generating at least one recognition candidate that is a candidate character of a recognition result;
Each of the at least one recognition candidate is collated with a knowledge dictionary obtained by modeling a character string to be recognized, and a collation result obtained by collating a character string estimated to be included in the input image with a knowledge dictionary is obtained. A matching step to generate,
Among the matching results, a prohibition processing step of deleting a matching result obtained by matching a character string including a prohibited character string and a knowledge dictionary;
A recognition method including: A program for causing a computer to function as a recognition device,
In the computer,
A candidate detection step of detecting a character candidate that is a set of pixels presumed to include a character from the input image;
A recognition step of recognizing each of the character candidates and generating at least one recognition candidate that is a candidate character of a recognition result;
Each of the at least one recognition candidate is collated with a knowledge dictionary obtained by modeling a character string to be recognized, and a collation result obtained by collating a character string estimated to be included in the input image with a knowledge dictionary is obtained. A matching step to generate,
Among the matching results, a prohibition processing step of deleting a matching result obtained by matching a character string including a prohibited character string and a knowledge dictionary;
A program that executes

Images