Image analysis – Pattern recognition – On-line recognition of handwritten characters
Reexamination Certificate
2000-07-27
2004-05-18
Dastouri, Mehrdad (Department: 2623)
Image analysis
Pattern recognition
On-line recognition of handwritten characters
C382S218000, C382S229000
Reexamination Certificate
active
06738515
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a pattern string matching apparatus and a pattern string matching method for use in a character recognition apparatus. The apparatus and method is designed to effect matching process for matching, for example, a first character string which has been recognized by character recognition and are to be matched, and candidates of a second character string, which is registered in a database.
Hitherto, a pattern matching process is performed, as an important process, in a character recognition apparatus in order to obtain the results of character recognition. The pattern matching process achieves matching (comparison) between candidates of a first character string which has been recognized by character recognition and are to be matched and candidates of a second character string, which is stored in a database (dictionary). Thus, the pattern matching process accomplishes the best matching between a string of characters obtained by character recognition and one of the strings of characters, registered in the database.
When the pattern string matching process is effected, various combinations of candidates of the first character string are provided according to character candidates obtained by character recognition. Further, a large number of candidates of the second character string which are matched with the first character string are provided.
As the conventional pattern string matching process, a DP matching method, a matching process by a voting method and the like are provided.
In the DP matching method, a pass searching process is effected for a plurality of character candidates constructing the first character string. However, in the DP matching method, if the candidates of recognized characters of the first character string are increased in an order of first, second, third . . . , a searching space is exponentially increased and the processing speed is extremely lowered.
Further, the matching process performed by the voting method is to vote for candidates of the second character string sequentially, by comparing each candidate of the second character string with the first character string, character by character, and then to select the candidate of the second string, which has the largest voted score. However, in this method, the character arrangement of the character string is not taken into consideration. Therefore, in a case where characters constructing the first character strings are the same but the character arrangements thereof are different, the character strings cannot be distinguished from each other. Particularly, in cultural areas using alphabetic characters, since the number of types of letters is as small as 26, the above problem becomes significant.
Therefore, it is the most important subject of the pattern string matching process how to efficiently and correctly effect the matching process for a plurality of candidates of a character string and a plurality of candidates of a character string. That is, it is required to develop a pattern string matching process for effecting the matching process at “high speed” with “the character arrangement taken into consideration”.
Further, in the pattern string matching process, noise becomes a problem. For example, suppose a case wherein cut-out of the character fails and a character different from the word is contained in the first character string in the process for recognizing the characters constructing the first character string. In this case, even if a correct character string is contained in the first character string, it becomes impossible to match them by use of the conventional method such as the DP matching method in many cases.
If the voting method is used, it is difficult to get information on a matched portion after the matching process and it is difficult to remove the noise and separately recognize the character.
Thus, the matching process which is highly “noise-resistant” and can “specify the noise position” with high precision is required.
BRIEF SUMMARY OF THE INVENTION
As described above, it is required to develop a high-speed and highly precise matching process with the character arrangement taken into consideration and an object of this invention is to provide a pattern string matching apparatus and pattern string matching method capable of effecting the high-speed and highly precise matching process with the character arrangement taken into consideration.
Further, it is required to develop a matching process which is highly noise-resistant and can specify the noise position and an object of this invention is to provide a pattern string matching apparatus and pattern string matching method capable of effecting the matching process which is highly noise-resistant and can specify the noise position.
The above object can be attained by a pattern string matching apparatus according to one aspect of this invention for effecting a matching process between first and second pattern strings each including a plurality of patterns, comprising voting means for voting according to a position of a matched pattern in the first pattern string and a position of a matched pattern in the second pattern string when the pattern of the first pattern string is matched with the pattern of the second pattern string; and determining means for determining the result of matching based on the result of voting by the voting means.
A pattern string matching method according to another aspect of this invention for effecting a matching process between first and second pattern strings each including a plurality of patterns, comprising the steps of voting according to a position of a matched pattern in the first pattern string and a position of a matched pattern in the second pattern string when each pattern of the first pattern string is matched with each pattern of the second pattern string; and determining the result of matching based on the result of voting.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.
REFERENCES:
patent: 5757959 (1998-05-01), Lopresti
patent: 5802205 (1998-09-01), Emico et al.
patent: 5832474 (1998-11-01), Lopresti et al.
patent: 6047093 (2000-04-01), Lopresti et al.
patent: 6597809 (2003-07-01), Ross et al.
Elliman, D.G. et al., “A Review of Segmentation and Contextual Analysis Techniques for Text Recognition”, Pattern Recognition, Pergamon Press Inc., Elmsford, N.Y., US, vol. 23, No. 3/4, 1990, pp. 337-346; pp. 340-341, Sec. “3.2.1 String Matching”.
Bertossi, A.A. et al., “String Matching with Weighted Errors”, Theoretical Computer Science, Amsterdam, NL, vol. 73, No. 3, Jul. 22, 1990, pp. 319-328, figure 1.
Dastouri Mehrdad
Kabushiki Kaisha Toshiba
Michael & Best & Friedrich LLP
LandOfFree
Pattern string matching apparatus and pattern string... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pattern string matching apparatus and pattern string..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern string matching apparatus and pattern string... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3267176