Method and system for character recognition

• US 8,064,700 B2
• Filed: 03/10/2010
• Issued: 11/22/2011
• Est. Priority Date: 02/15/2004
• Status: Active Grant

• Current Assignee: Kyocera Corporation
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kushler, Clifford A., Stafford-Fraser, James Q., King, Martin T., Grover, Dale L.
• Primary Examiner(s): Seth; Manav
• Application Number:
  US12/721,456
• Publication Number:
  US 20110044547A1
• Time in Patent Office: 622 Days
• Field of Search: 382/135, 382137-140, 382181-231, 382/321, 715/200, 715230-233, 715/273, 715/275, 345634-636, 345468-471
• US Class Current: 382/181
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/332 Query formulation
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/433 using audio data
• CPC Class Codes: G06F 16/434 using image data, e.g. images, photos, pictures taken by a user
• CPC Class Codes: G06F 16/435 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 16/9554 by using bar codes
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 40/117 Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/134 Hyperlinking
• CPC Class Codes: G06F 40/14 Tree-structured documents parsing G06F40/205; validation G06F40/226
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes
• CPC Class Codes: G06F 40/174 Form filling; Merging
• CPC Class Codes: G06K 17/0016 : Selecting or retrieving of images by means of their associated code-marks, e.g. coded microfilm or microfiche microfilm reading G03B21/11; computers therefor G06F16/00; teaching devices G09B5/02; accessing record carriers G11B27/002; static digital stores using optical elements G11C13/04; intermediate storage of facsimile picture signals H04N1/21
• CPC Class Codes: G06Q 10/00 : Administration; Management
• CPC Class Codes: G06Q 10/10 : Office automation; Time management
• CPC Class Codes: G06Q 20/102 : Bill distribution or payments
• CPC Class Codes: G06Q 20/12 : specially adapted for electronic shopping systems
• CPC Class Codes: G06Q 20/4012 : Verifying personal identification numbers [PIN]
• CPC Class Codes: G06Q 30/00 : Commerce
• CPC Class Codes: G06Q 30/02 : Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0207 : Discounts or incentives, e.g. coupons or rebates
• CPC Class Codes: G06Q 30/0241 : Advertisements
• CPC Class Codes: G06Q 30/0283 : Price estimation or determination
• CPC Class Codes: G06Q 30/04 : Billing or invoicing
• CPC Class Codes: G06Q 30/06 : Buying, selling or leasing transactions
• CPC Class Codes: G06Q 30/0601 : Electronic shopping [e-shopping]
• CPC Class Codes: G06Q 30/0603 : Catalogue ordering
• CPC Class Codes: G06Q 30/0623 : Item investigation
• CPC Class Codes: G06Q 30/0641 : Shopping interfaces
• CPC Class Codes: G06Q 30/0643 : Graphical representation of items or shoppers
• CPC Class Codes: G06Q 40/04 : Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: G06V 30/10 : Character recognition
• CPC Class Codes: G06V 30/142 : using hand-held instruments; Constructional details of the instruments
• CPC Class Codes: G06V 30/1444 : Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields
• CPC Class Codes: G06V 30/1448 : based on markings or identifiers characterising the document or the area
• CPC Class Codes: G06V 30/248 : involving plural approaches, e.g. verification by template match; Resolving confusion among similar patterns, e.g. "O" versus "Q" G06V30/242 takes precedence
• CPC Class Codes: G06V 30/262 : using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: G06V 30/40 : Document-oriented image-based pattern recognition
• CPC Class Codes: G07F 17/40 : for devices for accepting orders, advertisements, or the like
• CPC Class Codes: G07G 1/00 : Cash registers alarm indicators G07G3/00
• CPC Class Codes: H04N 1/00204 : with a digital computer or a digital computer system, e.g. an internet server programmed control between transmitter and receiver or between image input and image output device H04N1/32561
• CPC Class Codes: H04N 1/00244 : with a server, e.g. an internet server fax-servers or the like for store and forward H04N1/324
• CPC Class Codes: H04N 1/00326 : with a data reading, recognizing or recording apparatus, e.g. with a bar-code apparatus arrangements for the associated working of recording or reproducing apparatus with related apparatus G11B31/00
• CPC Class Codes: H04N 1/0036 : Alphanumeric symbols
• CPC Class Codes: H04N 1/00363 : Bar codes or the like
• CPC Class Codes: H04N 1/00374 : on the same page as at least a part of the image
• CPC Class Codes: H04N 1/00381 : Input by recognition or interpretation of visible user gestures manual input means, e.g. digitisers, writing tablets H04N1/00392; gesture input to computers G06F3/017; recognition algorithms G06V40/20
• CPC Class Codes: H04N 1/107 : with manual scanning
• CPC Class Codes: H04N 1/2166 : for mass storage, e.g. in document filing systems information retrieval G06F16/00
• CPC Class Codes: H04N 1/2187 : with image input from a plurality of different locations or from a non-central location, e.g. from one or more users
• CPC Class Codes: H04N 1/32128 : attached to the image data, e.g. file header, transmitted message header, information on the same page or in the same computer file as the image for information embedded in the image H04N1/32144
• CPC Class Codes: H04N 1/34 : for coin-freed systems ; Pay systems
• CPC Class Codes: H04N 2201/0081 : Image reader H04N2201/0091 - H04N2201/0094 take precedence
• CPC Class Codes: H04N 2201/3215 : of a time or duration
• CPC Class Codes: H04N 2201/3249 : data relating to a linked page or object, e.g. hyperlink
• CPC Class Codes: H04N 2201/3253 : Position information, e.g. geographical position at time of capture, GPS data
• CPC Class Codes: H04N 2201/3263 : of a graphical motif or symbol, e.g. Christmas symbol, logo H04N2201/3211 takes precedence
• CPC Class Codes: H04N 2201/3266 : of text or character information, e.g. text accompanying an image H04N2201/3226 takes precedence
• CPC Class Codes: H04N 2201/3277 : The additional information being stored in the same storage device as the image data
• CPC Class Codes: H04N 2201/3278 : Transmission
• CPC Class Codes: Y02A 90/10 : Information and communication technologies [ICT] supporting adaptation to climate change, e.g. for weather forecasting or climate simulation
• CPC Class Codes: Y10S 707/99931 : Database or file accessing
• CPC Class Codes: Y10S 707/99934 : Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 : Pattern matching access
• CPC Class Codes: Y10S 707/99943 : Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 : Object-oriented database structure processing

Abstract

Character recognition is described. In one embodiment, it may use matched sequences rather than character shape to determine a computer-legible result.

Claims

1. An article of manufacture comprising a non-transitory computer-readable medium with instructions encoded thereon, the instructions configured to cause one or more processors to perform a method comprising:

receiving an image of a sequence of glyphs;

for each of a subset of glyphs of the sequence;

determining whether the glyph matches a retained glyph;

assigning to the glyph a character identity associated with the retained glyph in response to determining that the glyph matches a retained glyph;

retaining the unmatched glyph, selecting a character identity for the unmatched glyph, and assigning the selected character identity to the unmatched glyph in response to determining that the glyph does not match a retained glyph;

generating a representation of the image of the sequence of glyphs with the assigned character identities; and

identifying the sequence of glyphs using the generated representation.

2. The article of manufacture of claim 1, wherein the assigned character identities relate to a spatial or ordinal position of the glyph within the sequence of glyphs.

3. The article of manufacture of claim 1, wherein identifying the sequence of glyphs using the generated representation includes identifying a single sequence of glyphs from multiple possible sequences of glyphs represented by the generated representation by comparing shape information associated with the generated representation to shape information associated with the identified multiple possible sequences of glyphs.

4. The article of manufacture of claim 1, wherein determining whether a glyph matches a retained glyph includes determining that the glyph matches a retained glyph to a certain degree of probability.

5. The article of manufacture of claim 1, wherein retaining the glyph includes adding an image of the glyph to a template of glyph images.

6. A method comprising:

storing an image of a text sequence in a non-transitory computer-readable medium associated with a computing system, the text sequence including multiple glyphs unknown to the computing system;

using one or more processors associated with the computing system to associate an identity to a subset of the multiple glyphs based on (1) similarities in shape between the glyphs within the image of the text sequence, and (2) relative locations of the glyphs within the image of the text sequence; and

using the one or more processors to generate a text representation by replacing the glyphs with the associated identities.

7. The method of claim 6, further comprising:

using the one or more processors to compare the generated text representation with a database of text representations to recognize the text sequence represented by the generated text representation.

8. The method of claim 6, further comprising:

using the one or more processors to compare the generated text representation with a database of text representations to identify two or more candidate text representations that match the generated text representation; and

using the one or more processors to query a dictionary to assign probabilities to the candidate text representations, where the assigned probabilities are based on a relative linguistic likelihood of the candidate text representation.

9. The method of claim 6, further comprising:

using the one or more processors to compare the generated text representation with a database of text representations to identify two or more candidate text representations that match the generated text representation; and

using the one or more processors to compare shape information associated with the generated text representation to shape information associated with the candidate text representations.

10. An article of manufacture comprising a non-transitory computer-readable medium with instructions encoded thereon, the instructions configured to cause one or more processors associated with a computing system to perform a method comprising:

receiving an image of a text sequence, the text sequence including multiple glyphs unknown to the computing system;

associating an identity to a subset of the multiple glyphs based on (1) similarities in shape between the glyphs within the image of the text sequence, and (2) relative locations of the glyphs within the image of the text sequence; and

generating a text representation by replacing the glyphs with the associated identities.

11. A method comprising:

storing an image of a sequence of glyphs in a non-transitory computer-readable medium associated with one or more processors;

for each of at least a subset of the glyphs, in the order of the sequence;

determining whether an identifier has been attributed to the glyph;

in response to determining that no identifier has been attributed to the glyph;

selecting an unassigned identifier;

assigning the selected identifier to the glyph;

attributing the selected identifier to the glyph; and

attributing the selected identifier to any glyphs that follow the glyph in the sequence and match the glyph; and

generating an encoding of the image that is based on the identifiers attributed to the glyphs of the sequence.

12. The method of claim 11, wherein the generating includes concatenating the identifiers attributed to the glyphs in the order of the sequence.

13. The method of claim 11, wherein the generating includes generating an encoding that contains, for glyphs to which the same identifier was attributed, the same value.

14. The method of claim 11, wherein the generating includes generating an encoding that contains, for each of at least a subset of the glyphs, an offset in the sequence to a glyph to which the same identifier was attributed.

15. An article of manufacture comprising a non-transitory computer-readable medium with instructions encoded thereon, the instructions configured to cause one or more processors to perform a method comprising:

receiving an image of a sequence of glyphs;

initializing an encoding of the image;

for each of at least a subset of the glyphs, in the order of the sequence;

determining an offset to a glyph earlier in the sequence that matches the glyph; and

storing a value in the encoding that indicates the determined offset.

16. The article of manufacture of claim 15 wherein the determining includes determining an offset to the earliest glyph in the sequence that matches the glyph.

17. The article of manufacture of claim 15 wherein the determining includes determining an offset to the most recent glyph in the sequence that matches the glyph.

18. A method comprising:

storing an image of a sequence of glyphs in a non-transitory computer-readable medium associated with one or more processors;

using the one or more processors to initialize an encoding of the image; and

for each of at least a subset of the glyphs, in the order of the sequence, using the one or more processors to determine an offset to a glyph earlier in the sequence that matches the glyph and store an indication of the determined offset in the encoding.