Method of indexing words in handwritten document images using image hash tables

• US 5,953,451 A
• Filed: 06/19/1997
• Issued: 09/14/1999
• Est. Priority Date: 06/19/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Syeda-Mahmood, Tanveer F.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Miller, Martin E.
• Application Number:
  US08/878,512
• Time in Patent Office: 817 Days
• Field of Search: 382/186, 382/187, 382/292, 382/228, 382/203, 382/305, 707/3-6
• US Class Current: 382/187
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06V 30/2264 using word shape

Abstract

A method of locating handwritten words in handwritten text images under a variety of transformations including changes in document orientation, skew, noise, and changes in handwriting style of a single author which avoids a detailed search of the image for locating every word by pre-computing relevant information in a hash table and indexing the table for word localization. Both the hash table construction and indexing can be done as fast operations taking time quadratic in the number of basis points. Generally, the method involves four stages: (1) Pre-processing where features for word localization are extracted; (2) Image hash table construction; (3) Indexing where query word features are used to look up hash table for candidate locations; and (4) Verification, where the query word is projected and registered with the underlying word at the candidate locations. The method has applications in digital libraries, handwriting tokenization, document management and OCR systems.

Claims

1. A method of localizing handwritten words in an image of a document, comprising:

a) pre-processing a document containing handwriting where curves with features for word localization are extracted from handwritten words contained in the document, wherein each curve includes selected features with the selected features being less than all of the features for the curve;

b) grouping the curves to form curve groups;

c) computing basis triples from the selected features of the curves of the curve groups;

d) computing affine coordinates for the features of the curves in each curve group with respect to corresponding basis triples computed with said (c);

e) using the affine coordinates and basis triples to create an image hash table with entries for indexing the handwritten words of the document, wherein the image hash table includes a list of the basis triples;

f) indexing the handwritten words with the image hash table, wherein query word features are used to look up the handwritten words in the image hash table for candidate locations; and

g) verifying registration of underlying words within the image hash table by projecting a query word onto one of the underlying words at the candidate locations to find a match.

2. The method of of claim 1, in which basis points are taken from a single curve, wherein said (d) includes computing affine coordinates for all features on all curves in a curve group.

3. The method of claim 2, further comprising accommodating for changes in appearance of handwritten words in terms of orientation, skew and intra-word separation.

4. The method of claim 1, wherein the localizing is performed on a document obtained from either an image reading or electronic source.

5. The method of claim 1, wherein said (g) includes recovering pose parameters by solving a set of linear equations to verify that a word corresponds with a candidate location.

6. The method of claim 1, wherein said (g) includes:

generating a verification score from curves; and

determining whether the verification score exceeds a selected threshold.

7. The method of claim 1, further comprising providing the curves with corners, wherein the selected features comprise the corners.

8. The method of claim 1, further comprising using consecutive triples of features for basis points.

9. The method of claim 1, in which consecutive triples are used for basis points, wherein said (c) includes computing a linear number of basis points.