Image recognition through localized interpretation

Details Image recognition through localized interpretation Image recognition through localized interpretation

1997-10-17

2001-07-10

Au, Amelia (Department: 2723)

Image analysis

Pattern recognition

Feature extraction

C382S209000

Reexamination Certificate

active

06259814

ABSTRACT:

TECHNICAL FIELD
The present invention relates generally to image processing, and specifically to image recognition by partitioning a matrix representing a character or other image into a plurality of sub-matrices and performing localized interpretation of said sub-matrices by means of lookup tables.
BACKGROUND ART
The field of optical character recognition (OCR) has long been applied to the problem of recognizing machine-printed characters from a page of text. However, special problems exist when attempting to recognize handwritten characters, even in the case of constrained, hand-printed formats used by pen-based or “palm top” computers. The difficulty lies in the extreme variability of such images. Historically, no single OCR algorithm has proven adequate to recognize handwritten characters with the desired level of accuracy.
One method of reducing variability has been to map a character image onto a grid of boxes, producing a standardized matrix that can be compared against a set of referents. U.S. Pat. No. 5,539,840 to Krtolica et al. discloses such an approach in which a character image is mapped onto a 16×16 matrix. Despite improvements brought about by this technique, there remains a substantial amount of image variability. Thus, there remains a need for an algorithm providing even greater accuracy.
Theoretically, it should be possible for a machine to recognize a character image as well as a human provided that the recognition system is trained with all possible images and sufficient memory is provided to record the learned patterns. This “brute force” method would be nearly error free, except for the effects of noise and the process of quantizing the images to fit the standard matrix. However, such a method is highly impractical. For a 16×16 bi-level character image, there are exactly 2
256
(nearly 10
80
) unique patterns. Aside from the technical difficulty in storing this many patterns, the time required to recognize the image as well as train the system with all possible referent characters would be excessive.
Thus, there remains a need for a highly accurate recognition system that is not overly sensitive to the effects of character image variability. Moreover, there remains a need for a recognition system that is efficient both in terms of recognition time and storage requirements.
DISCLOSURE OF INVENTION
The present invention addresses the image variability problem while reducing the need for system resources. Although the following discussion centers on the problem of character recognition, one skilled in the art will understand that the same principles apply to recognizing other types of images. A document often includes elements other than text, such as diagrams or photographs. Thus, the scope of the present invention should not be limited to recognizing only printed or handwritten characters.
In accordance with the present invention, a character image is recognized by training (
301
) a lookup table with a set of known referent characters; obtaining (
302
) a bitmap of a character image to be recognized; mapping (
303
) the bitmap onto a standardized character matrix; partitioning (
304
) the matrix into a plurality of sub-matrices; determining (
305
) a set of candidates for each sub-matrix; and selecting (
306
) a preferred candidate from among the set of candidates responsive to at least one pre-defined selection criterion.
In another aspect of the invention, the lookup table is trained by obtaining (
601
) a bitmap of a referent character; mapping (
602
) the bitmap onto a standardized character matrix; partitioning (
603
) the matrix into a plurality of sub-matrices; addressing (
604
), for each sub-matrix, a lookup table using a binary representation of the sub-matrix as an index into said table; and storing (
605
), in each addressed table entry, a representation of the referent character.
In yet another aspect of the invention, a candidate set is determined by initializing (
701
) a candidate set; addressing (
702
), for each sub-matrix, a lookup table using a binary representation of the sub-matrix as an index into said table; adding (
703
) to a candidate set, characters corresponding to addressed entries of said table; and recording (
704
) the number of occurrences of each candidate.
In accordance with the invention, apparatus (
100
) for pattern recognition includes a scanner (
102
), a character mapper (
104
), a matrix partitioner (
106
), a candidate set builder (
108
), and a character selector (
110
).


REFERENCES:
patent: 4379283 (1983-04-01), Ito et al.
patent: 4437122 (1984-03-01), Walsh et al.
patent: 4521909 (1985-06-01), Wang
patent: 4648119 (1987-03-01), Wingfield et al.
patent: 4799270 (1989-01-01), Kim et al.
patent: 4979221 (1990-12-01), Perryman et al.
patent: 5125048 (1992-06-01), Virtue et al.
patent: 5337370 (1994-08-01), Gilles et al.
patent: 5386483 (1995-01-01), Shibazaki
patent: 5539840 (1996-07-01), Krtolica et al.
patent: 5555317 (1996-09-01), Anderson
patent: 5559530 (1996-09-01), Yamashita et al.
patent: 5680476 (1997-10-01), Schmidt et al.
patent: 5689343 (1997-11-01), Loce et al.
patent: 5875264 (1999-02-01), Carlstrom

Affiliated with

Also associated with

Rating

Image recognition through localized interpretation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Image recognition through localized interpretation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image recognition through localized interpretation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2514419