JP4594765B2 - Character recognition apparatus, character recognition method, and character recognition program recording medium - Google Patents

Description

  The present invention relates to an image identification technique for capturing a character string as an image and identifying the character string. As a specific industrial application system, for example, a Japanese translation system for a signboard can be cited.

  Character string identification existing in the landscape generally goes through four steps: character string position specification, character region specification, binarization, and character identification. However, such a technique has a problem in that character string position specification, character region specification, and binarization are not successful due to the influence of illumination fluctuations, complicated background, and the like, and character string identification accuracy is low.

In order to solve such a problem, as a character string identification technique existing in a landscape, there is a method of passing through three steps of full-screen search, character candidate narrowing down, and character string estimation by a language model (for example, Non-Patent Document 1) reference.).
Yoshinori Kusachi, Naomi Ito, Akira Suzuki, Kenichi Arakawa, “Recognition of Characters in Scenery Not Required for Text Areas for Image Indexing”, IEICE Technical Report PRMU 2004-89, (2004-10), p.37 -42

  However, in the above method, there is a limit to the feature definition and identification algorithm, the distinction between the background and the character cannot be made completely, and many character candidates exist in the background portion, and the character string estimation by the language model is successful. There was a problem of not working.

  This invention is made | formed in view of this situation, The objective is to provide the character recognition technique which solved the said subject.

Accordingly, in order to solve the above-described problem, the invention according to claim 1 is a character recognition device that recognizes characters in an image, and extracts features by cutting out a local image while scanning the input image. A first-stage character recognition unit that determines a character candidate based on the similarity between the feature and the character feature registered in the dictionary, and a feature that is different from the feature already used for feature extraction for the determined character candidate One or more different feature character recognition means for narrowing down the character candidates from the similarity between the feature and the character feature registered in the dictionary, and the first-stage character recognition means and the One of the one or more different feature character recognition means includes a line width detection means for detecting a line width of a line in a plurality of directions, and a line width of the line in each direction. Output feature vectors as feature values Means for generating a plurality of filters according to the direction in which the line width is detected and the line width of the lines, and the degree of coincidence between the image and the plurality of filters. A degree of coincidence calculating means for calculating a line width of a line obtained by multiplying the degree of coincidence by the line width value of the filter line showing the maximum degree of coincidence in the calculated degree of coincidence And calculating means .

The invention according to claim 2 is a character recognition method in a character recognition device for recognizing characters in an image, wherein the first stage character recognition means cuts out the local image while scanning the input image. And a first-stage character recognition step for determining a character candidate based on the similarity between the feature and the character feature registered in the dictionary, and one or more different-character character recognition means include the determined character candidate A different feature character recognition step of extracting a feature different from the feature already used for feature extraction and narrowing down the character candidates based on the similarity between the feature and the feature of the character registered in the dictionary. and, in any step of the different characteristic character recognition step and the first stage character recognition step, a line width detection means, the input image, the line width detection step of detecting a width of a line in a plurality of directions The output means outputs a feature vector having the line width of the line in each direction as a feature value, and in the line width detection step, the filter generation means detects the line width and A filter generation step for generating a plurality of filters according to the line width of the line, a coincidence degree calculating means for calculating a coincidence degree between the image and the plurality of filters, and a line width calculating means, A line width calculation step of setting a line width of a line obtained by multiplying the line width value of the filter showing the maximum degree of coincidence in the calculated degree of coincidence by the coincidence degree. And

According to a third aspect of the present invention, there is recorded a program in which the character recognition device or the character recognition method according to the first or second aspect is executable by a computer.

According to the first to third aspects of the present invention, the different character recognition means further narrows down the character candidates determined by the first-stage character recognition means, so that the number of character candidates in the background portion can be reduced.

Moreover, character candidates can be further reduced by combining and narrowing different features between the first-stage character recognition means and the different-character recognition means.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

(String translation system)
First, an example in which the character recognition device is applied to a character string translation system will be described with reference to FIG. The character string translation system includes a mobile terminal 11 such as a PDA with a camera, a character recognition device 12, a character string estimation device 13, and a translation device 14.

  In this character string translation system, the user takes an image with the portable terminal 11 and sends it to the character recognition device 12. The character recognition device 12 extracts character candidates from the image and sends them to the character string estimation device 13. The character string estimation device 13 estimates a character string from the character candidates and sends it to the translation device 14. The translation device 14 translates the character string and sends the translation result to the portable terminal 11 so that the user can view the translation result. As described above, the character string translation system allows the user to see the translation result of the character string based on the captured character string image.

(Character recognition device)
Here, the configuration of the character recognition device 12 will be described with reference to FIG. As shown in FIG. 2, the character recognition device 12 includes a first-stage character recognition unit 21 and N different characteristic character recognition units 22-1 to 22-N.

(First stage character recognition means)
The first-stage character recognition means 21 is a means for extracting character candidates from an image. For example, “character recognition in a landscape that does not require a text area for the purpose of image indexing”, IEICE Technical Report PRMU 2004-89. (2004-10), p. 37-42.

  Here, the first stage character recognition means 21 will be described with an example. The first-stage character recognition means 21 generates a multi-resolution image in order to correspond to characters of different sizes, cuts out an image of a predetermined size while shifting the position, and performs a coarse / fine search. This result is used as an index. In the image search, when a keyword is input, only the corresponding character is extracted from the index to determine regularity, and an image determined to be regular is output as a result.

  Here, the coarse / fine search includes pattern learning and pattern identification. Hereinafter, pattern learning and pattern identification will be described.

  [Pattern Learning] Pattern learning is composed of four stages: feature extraction, creation of a category hierarchy, pattern generation by geometric deformation, and dictionary generation.

In the feature extraction, an original pattern (w × w) obtained by photographing a character from the front is prepared, and the feature is extracted. The feature utilizes a weighted direction index histogram feature (WDCH). WDCH is used for OCR and targeted for binary images, but can be easily extended to gray images. The outline of the algorithm is shown below. However, M and N are positive constants.
1: A differential value and direction are obtained from the original pattern using a Sobel operator.
2: The direction of differentiation is quantized in the M direction.
3: The original pattern is divided into N × N grids.
4: The magnitude of the differential value is added in each M direction of each grid.
5: Consider a feature vector of N × N × M, and normalize the norm.

  Since WDCH is based on differential values, it is not easily affected by brightness fluctuations. Further, by using the sum of the differential values in the grid, it is possible to absorb minute variations in shape such as deformation due to fonts.

  In creating a category hierarchical structure, each category is clustered based on the similarity of feature vectors to create a hierarchical structure. Each node includes a plurality of categories. In the lowest layer node, only a single category is included.

  In the pattern generation by geometric deformation, a character deformation pattern accompanying a change in viewpoint is generated for each category. The original pattern is geometrically deformed by five-parameter affine transformation of rotation, vertical skew, horizontal skew, aspect ratio, and enlargement / reduction. Although the size of the generated pattern may be larger than the original pattern, features are extracted using only partial patterns within the window size of the current pattern, and this feature vector is used for dictionary generation.

  In dictionary generation, a dictionary for each node is created in the following procedure.

  As a first stage, feature compression is performed. First, the features are compressed in each layer. All feature vectors including the geometric deformation pattern are subjected to principal component analysis and compressed using eigenvectors having higher eigenvalues. This compressed feature vector is represented as f (c, r, p). However, c is a category, r is a compression rate, and p is a deformation parameter.

  As a second stage, dictionary generation at each node is performed. If the category set of each node is C, the principal component analysis is performed on the vector of f (C, r, p), and the subspace Ed (C, r) is obtained. Here, d is the number of dimensions of the subspace, and is an integer determined by the system, which is determined by the contribution rate.

  The compression rate of each layer is set to be lower toward the lower layer, thereby realizing the coarse / fine search. In the upper layer, although the accuracy is low, identification is performed at high speed, and in the lower layer, identification is performed at low speed but with high accuracy.

[Pattern Identification] A small area of size W × W is cut out while moving the position over the entire surface of the multi-resolution image, and pattern identification is performed. In pattern identification, a coarse / fine search is performed while following a plurality of routes in a hierarchical structure. The outline of the algorithm is shown below.
1. Feature extraction: Extracting features by cutting out regions while changing the position of each resolution image. Features of all cutout areas are calculated in advance.
2. Initialization: Start from the root node of the tree structure.
3. Candidate node setting: Nodes in the first layer are set as candidate nodes in all cutout areas. Repeat 4-6 for each cutout area.
4). Compression: compresses the features of the clip region using the compression ratio of the lower layer. This is represented as I ′ (r).
5). Projection distance calculation: The projection distance L (C) is obtained using the partial space of the candidate node C according to the following equation.

Where D is the subspace dimension.
6). Screening: The rank of each candidate node is calculated from the above distance values. The candidate nodes are updated from the distance and rank thresholds.
7). Peak detection: Three-dimensional (vertical, horizontal, resolution) spatial connectivity is calculated for each candidate node in all cutout regions, and a segment is obtained. Only the candidate nodes with the smallest peak of distance value within each segment are left. Other candidate nodes are deleted.
8). Screening in the local region: The following processing is performed for each set of peaks having the same resolution. First, the space is divided into blocks, and the peaks included in each block are sorted according to distance values, and only a certain number from the top is adopted. Thereafter, the same processing is performed by shifting the block division position by a half block horizontally / vertically.
9. Peak integration of the same candidate characters: If two peaks having the same candidate character are taken out and integrated with a smaller distance value if the center coordinate and the resolution are close to each other, the processing is repeated until there is no pair of peaks to be integrated.
10. Candidate node update: A node connected to a layer below the candidate node is registered as a new candidate node.
11. End determination: If the candidate node has reached the lowest layer, the remaining candidate node is output as an index and the process ends. Otherwise, the process returns to 4 above. The format of the index is (category name, position, size, similarity).

  The spatial connectivity of 7 is not limited to three dimensions, but two dimensions (vertical and horizontal) can be considered. In addition, the above 7 to 9 are processes for reducing the processing amount, which is a tradeoff between accuracy and processing amount. It is not necessary to carry out at all levels, and it is sufficient to carry out only at a predetermined level.

[Image search] In image search, when a keyword is input as a character string, the index obtained by pattern identification is searched for a place where the pattern is spatially arranged regularly, and the index where such a place exists is searched. Is output as a search result. As a rule of spatial arrangement of patterns, here
(1) The pattern size is almost the same
(2) The pitch is almost constant
(3) The pitch size is within a certain range relative to the size of each individual pattern.
(4) The pattern arrangement order matches the input character string order, and the difference in angle between the pattern arrangement direction and the horizontal or vertical direction is within a certain range.

  In this case, the search algorithm searches for all the locations in the index where any combination of two characters in the forward direction that make up the input character string exists, and at these points the start position of the virtual input character string is determined. A two-dimensional coordinate and a value of a two-dimensional vector representing character advance are calculated, and voting is performed in a voting space constituted by these parameters. However, at the time of voting, it is checked whether or not the combination does not violate the rules (1), (3), and (4) above. Finally, the voting space is searched for the presence or absence of a part whose score is equal to or greater than a threshold value.

  In this algorithm, the candidate characters to be processed at the time of voting are limited to only two categories, so it is possible to perform high-speed processing even for indexes that contain many false candidate characters, and partial due to the characteristics of voting processing. It is robust against lack of correct answers.

  In this way, the first stage character recognition means 21 determines character candidates (candidate category, position, size, similarity) from the image.

(Different character recognition means)
The different feature character recognition means 22-1 to 22-N are means for recognizing characters from character candidates (candidate category, position, size, similarity), and after extracting features from an image, a subspace method or the like is used. Character recognition is performed. The subspace method is described in detail in the following documents. “E. Oja. Subspace Methods of Pattern Recognitions. Research Studies Press, 1983.”.

  For example, the first stage character recognition means 21 extracts a feature from the photographed image, and outputs a character candidate as shown in FIG. 3 based on the similarity between this feature and the character feature registered in the dictionary. And On the other hand, the different-character recognition unit 22-A uses the feature used by the first-stage character recognition unit 21 for the image corresponding to the position and size of the character candidate information output from the first-stage character recognition unit 21. Features that are different from the above are extracted, and character categories are identified. Then, character candidate data as shown in FIG. 4 is output as intermediate data. Further different character recognition means 22-B, which is different from the character candidate data, extracts features different from the different character recognition means 22-A and narrows down the character candidates. Finally, an output as shown in FIG. 5 is obtained based on the distance threshold (for example, within 1000) or the rank threshold (for example, within 5) of each character candidate. That is, character candidates can be reduced by performing processing using the different character recognition means 22 that narrows down character candidates by focusing on a plurality of different features.

(First stage character recognition means and different feature character recognition means share feature extraction means)
Here, the case where the first stage character recognition means 21 and the different feature character recognition means 22 share the feature extraction means 61 will be described with reference to FIG. As shown in FIG. 6, it is assumed that the first-stage character recognition unit 21 and the different-character recognition unit 22 share the feature extraction unit 61, and only the parameters thereof are different.

  For example, a case where the feature extraction unit 61 uses an extended weighted direction index histogram in which the number of blocks can be input as a parameter will be described with reference to FIGS.

FIG. 7 is a diagram showing a flow of processing of the extended weighted direction index histogram. As shown in FIG.
The direction / size of the edge is obtained (S71).

  The direction of the edge is quantized (S72).

  Block division is performed (S73).

  The sum of edge sizes in each block / quantization direction is calculated (S74).

  Smoothing is performed (S75).

  Each value is regarded as an element of one feature vector, and the norm size is normalized (S76).

  The extended weighted direction index histogram is processed through the above processing.

  In addition, about said S72, S74, and S75, details are described in the following literature which described the detail of the weight direction index histogram. “T. Wakabayashi, S. Tsuruka, F. Kimura, Y. Miyake,“ Accuracy Improved Through Through Incremented Feature Size in Jl. Ip. 1994 (in Japan) ".

  In S71, as shown in FIG. 8, the size and direction of the edge are obtained. As a specific example, it can be calculated using vertical and horizontal Sobel operators.

  In S73, as shown in FIG. 9, when the number of blocks is 8, the image is divided into 8 × 8 blocks. When the number of blocks is 4, the image is divided into 4 × 4 blocks.

  In S76, using a general technique, the magnitude of the norm can be normalized by regarding each value as an element of one feature vector.

  In this way, character candidates can be reduced without lowering the identification rate by using the features used in the first stage character recognizing means 21 and the features used in the different characteristic character recognizing means 22 that are different only in parameters. It becomes possible.

(First stage character recognition means and different feature character recognition means use different features)
Here, the case where the first stage character recognition means 21 has the weighted direction index histogram feature extraction means 101 and the different feature character recognition means 22 has the line width feature extraction means 102 will be described with reference to FIG. The first stage character recognition unit 21 may include the line width feature extraction unit 102, and the different feature character recognition unit 22 may include the weighted direction index histogram feature extraction unit 101.

(Line width feature extraction means)
The line width feature extraction unit 102 will be described with reference to FIG. FIG. 11 is a configuration diagram of the line width feature extraction unit 102. As shown in FIG. 11, the line width feature extraction unit 102 includes an image input unit 111 that inputs a character pattern group or an image (referred to as an image pattern), and a line width detection unit that detects line widths in a plurality of directions at an arbitrary pixel. 112 and output means 113 for outputting as a feature vector having a line width in each direction of each pixel as a feature value.

  FIG. 12 is a calculation example of line width detection, and calculates line widths in directions of 0 degrees, 45 degrees, 90 degrees, and 135 degrees with respect to the image “A”. For example, binarization is performed locally and the length of connection in each direction is measured. As shown in FIG. 12, a line width value in four directions is obtained for each pixel, and this is regarded as a feature vector (however, the line width value of a pixel having no numerical value is 0). The dimension of the feature vector is the number of directions × the number of pixels.

  Here, the line width feature extraction unit 102 having the line width histogram calculation unit 133 will be described with reference to FIG. As shown in FIG. 13, a line width feature extraction unit 102 having a line width histogram calculation unit 133 includes an image input unit 131 that inputs a character pattern group or an image (referred to as an image pattern), and lines in a plurality of directions at an arbitrary pixel. The line width detecting means 132 for detecting the width, the line width histogram calculating means 133 for calculating the line width histogram for each direction in the determined local area, and the line width histogram in each direction of each local area as the feature values. It is comprised from the output means 134 which outputs as a feature vector.

  FIG. 14 is a calculation example of a line width histogram. As shown in FIG. 14, a local region is set for the image with respect to the line width calculated by the line width detecting unit 132 in FIG. 13, and the size of the line width is added for each angle direction within the local region. To do. Here, in the local region near the center of 0 degree, the line width of each pixel is 1, 1, 0.5, and these are added to 2.5. As shown in FIG. 14, line width histograms in four directions are obtained in each region, and these are regarded as feature vectors. The dimension of the feature vector is the number of directions × the number of local regions. Note that the local region is obtained by, for example, simply dividing an image into a lattice shape.

(Line width detection means)
Here, the line width detecting means 112 and 132 will be described with reference to FIG. As shown in FIG. 15, the line width detection means 112, 132 is a filter generation means 151 that calculates a plurality of filters according to an arbitrary direction and line width, and an area centered on the pixel of interest matches a plurality of filters A degree-of-match calculation means 152 for calculating a degree and a line width calculation means 153 that multiplies the degree of coincidence by the line width of the filter indicating the maximum degree of coincidence to obtain the line width.

  FIG. 16 is an example of a filter generated by the filter generation unit 151. As shown in FIG. 16, this is an example of a filter that detects four directions and three types of line widths. The line width in this case is 2, 3, and 4.

(Measuring method)
The degree of coincidence calculation means 152 calculates the degree of coincidence between each generated filter and the area centered on the target pixel. Here, the configuration of the degree-of-match calculation means 152 will be described with reference to FIG. As shown in FIG. 17, the coincidence degree calculation unit 152 includes a normalized correlation unit 171. The normalized correlation unit 171 receives the filter and the character pattern group or image generated by the filter generation unit 151, calculates a normalized correlation value between the filter and the character pattern group or image, and calculates the normalized correlation value. Output as degree of match. In the calculation of the normalized correlation value, for example, an inner product value or a distance can be used.

  Thus, the first stage character recognition means 21 has the weighted direction index histogram feature extraction means 101, and the different feature character recognition means 22 has the line width feature extraction means 102, that is, the first stage character recognition means 21 and By combining features having completely different principles with the different feature character recognition means 22, it is possible to dramatically reduce the number of character candidates with a slight decrease in the recognition rate.

(Program etc.)
In the above-described embodiment, the character recognition device is realized by, for example, a CPU included in a computer device that constitutes the character recognition device, and required first-stage character recognition processing, different character recognition processing, feature extraction processing, and extension. Weighted direction index histogram feature extraction processing, line width feature extraction processing, normalized correlation calculation processing, and the like can be installed as application programs.

  In addition, processing results and calculation results such as first-stage character recognition processing, different feature character recognition processing, feature extraction processing, extended weighted direction index histogram feature extraction processing, line width feature extraction processing, normalized correlation calculation processing, etc. Data may be written to and read from an internal memory or an external storage device.

  In addition, a recording medium recording software program codes for realizing the functions of the present embodiment is supplied to a system or apparatus, and a CPU (MPU) of the system or apparatus reads and executes the program code stored in the storage medium. It is also possible. In this case, the program code itself read from the storage medium realizes the functions of the above-described embodiment, and examples of the storage medium storing the program code include CD-ROM, DVD-ROM, and CD-R. , CD-RW, MO, HDD and the like.

The block diagram of a character string translation system. The block diagram of a character recognition apparatus. An output example of the first stage character recognition means. The example of an output of a different characteristic character recognition means. The example of an output of a different characteristic character recognition means. An example of sharing feature extraction means between first stage character recognition means and different feature character recognition means. The processing flow figure of an extended weight direction index histogram. The figure which shows the example which calculates | requires the magnitude | size and direction of an edge. The figure which shows the example which divides | segments an image into a block. The block diagram of a 1st step character recognition means and a different characteristic character recognition means. The lineblock diagram of a line width feature extraction means. The figure which shows the example of calculation of line | wire width detection. The lineblock diagram of a line width feature extraction means. The figure which shows the example of calculation of a line width histogram. The lineblock diagram of a line | wire width detection means. The figure which shows the example of the filter produced | generated by the filter production | generation means. The block diagram of a coincidence degree calculation means.

Explanation of symbols

DESCRIPTION OF SYMBOLS 11 ... Portable terminal 12 ... Character recognition apparatus 13 ... Character string estimation apparatus 14 ... Translation apparatus 21 ... First stage character recognition means 22 ... Different character recognition means 61 ... Feature extraction means 101 ... Extended weight direction index histogram feature extraction means 102 ... line width feature extraction means 111 ... image input means 112 ... line width detection means 113 ... output means 131 ... image input means 132 ... line width detection means 133 ... line width histogram calculation means 134 ... output means 151 ... filter generation means 152 ... Matching degree calculating means 153... Line width calculating means 171... Normalized correlation means

Claims (3)

A character recognition device for recognizing characters in an image,
First stage character recognition means for extracting a feature by cutting out a local image while scanning an input image, and determining a character candidate based on the similarity between the feature and the feature of a character registered in the dictionary;
For the determined character candidate, a feature different from the feature already used for feature extraction is extracted, and the character candidate is narrowed down based on the similarity between the feature and the feature of the character registered in the dictionary. Characteristic character recognition means,
Any one of the first stage character recognition means and the one or more different characteristic character recognition means includes:
Line width detecting means for detecting line widths of the input image in a plurality of directions;
Output means for outputting a feature vector having a line width of the line in each direction as a feature value;
The line width detecting means is
Filter generation means for generating a plurality of filters according to the direction of detecting the line width and the line width of the line;
A degree of coincidence calculating means for calculating a degree of coincidence between the image and the plurality of filters ;
A line width calculation means for setting a value obtained by multiplying the degree of coincidence by the value of the line width of the filter line indicating the maximum degree of coincidence in the calculated degree of coincidence;
A character recognition device comprising: A character recognition method in a character recognition device for recognizing characters in an image,
First stage character recognition means extracts a feature by cutting out a local image while scanning the input image, and determines a character candidate based on the similarity between the feature and the feature of the character registered in the dictionary A step recognition step;
One or more different feature character recognition means extracts, for the determined character candidate, a feature different from the feature already used for feature extraction, and based on the similarity between the feature and the feature of the character registered in the dictionary A different feature character recognition step for narrowing down character candidates,
In any of the first stage character recognition step and the different character recognition step,
A line width detecting unit that detects line widths in a plurality of directions with respect to the input image;
An output unit that outputs a feature vector having a line width of the line in each direction as a feature value;
In the line width detection step,
A filter generating step for generating a plurality of filters according to a direction in which the line width is detected and a line width of the line;
A degree of coincidence calculating means for calculating a degree of coincidence between the image and the plurality of filters;
A line width calculation step in which the line width calculation means sets the value obtained by multiplying the coincidence by the value of the line width of the filter line indicating the maximum coincidence in the calculated coincidence; ,
A character recognition method characterized by comprising: A recording medium having recorded thereon a computer program capable of executing the character recognition device or character recognition method according to claim 1 or 2 .