Assist channel coding using a rewrite model

• US 7,110,621 B1
• Filed: 05/19/2000
• Issued: 09/19/2006
• Est. Priority Date: 05/19/2000
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Popat, Ashok C.., Greene, Daniel H.
• Primary Examiner(s): Bali, Vikkram
• Assistant Examiner(s): LAROSE, COLIN M
• Application Number:
  US09/574,406
• Time in Patent Office: 2,314 Days
• Field of Search: 382/310, 382/209, 382/215, 382/217, 382/218, 382/309
• US Class Current: 382/310
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/12 Detection or correction of errors, e.g. by rescanning the pattern
• CPC Class Codes: G06V 30/19173 Classification techniques
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context

Abstract

A system encodes a separate assist channel that carries only a small amount of additional information in a hardcopy document to compensate for failure of an OCR system to accurately reconstruct a scanned electronic version of the hardcopy document. After the OCR system produces an interpretation of the scanned electronic version of the hardcopy document, a rewrite system that is guided by the assist channel operates independent from the OCR system to correct decoding errors produced by the OCR system.

Claims

1. A method for decoding image data for a hardcopy document, comprising:

recording a scanned representation of the hardcopy document that includes a primary set of symbol data and a secondary set of encoding data;

the primary set of symbol data providing a first channel of human readable information rendered on the hardcopy document;

the secondary set of encoding data providing a second channel of machine readable information rendered on the hardcopy document;

receiving a decoded form of the scanned representation of the hardcopy document from a decoding module to define a candidate set of symbol data; and

rewriting, independent of the decoding module, the candidate set of symbol data using an event library and the secondary set of encoding data; and

computing a shortest path of a product graph of the candidate set of symbol data and the secondary set of encoding data;

the event library identifying likely failures encountered when the scanned representation of the hardcopy document is decoded;

the event library comprising a rule that represents a transformation.

2. The method according to claim 1, wherein said computing is performed using a shortest path computation.

3. The method according to claim 2, wherein the shortest path computation comprises a two-pass dynamic programming computation.

4. The method according to claim 1, wherein the product graph is defined by:

defining nodes that correspond to both position in the candidate set of symbol data and the secondary set of encoding data; and

defining arcs that satisfy the candidate set of symbol data and the secondary set of encoding data.

5. The method according to claim 4, wherein the product graph is further defined by matching symbols in the candidate set of symbol data with events from the event library.

6. The method according to claim 1, wherein the decoding module performs dynamic programming to decode the scanned representation of the hardcopy document.

7. The method according to claim 1, wherein the secondary set of encoding data is encoded using one of separation coding, block coding, and convolution coding.

8. The method according to claim 1, wherein the decoded form of the scanned representation includes certainty estimates of the candidate set of symbol data.

9. An apparatus for decoding image data for a hardcopy document, comprising:

means for recording a scanned representation of the hardcopy document that includes a primary set of symbol data and a secondary set of encoding data;

the primary set of symbol data providing a first channel of human readable information rendered on the hardcopy document;

the secondary set of encoding data providing a second channel of machine readable information rendered on the hardcopy document;

means for receiving a decoded form of the scanned representation of the hardcopy document from a decoding module to define a candidate set of symbol data; and

means for rewriting, independent of the decoding module, the candidate set of symbol data using an event library and the secondary set of encoding data; and

computing a shortest path of a product graph of the candidate set of symbol data and the secondary set of encoding data;

the event library identifying likely failures encountered when the scanned representation of the hardcopy document is decoded;

the event library comprising a rule that represents a transformation.

10. An apparatus for decoding image data for a hardcopy document, comprising:

a scanner for recording a scanned representation of the hardcopy document that includes a primary set of symbol data and a secondary set of encoding data;

the primary set of symbol data providing a first channel of human readable information rendered on the hardcopy document;

the secondary set of encoding data providing a second channel of machine readable information rendered on the hardcopy document;

a decoding module coupled to the scanner for providing a decoded form of the scanned representation of the hardcopy document to define a candidate set of symbol data; and

a rewrite module for rewriting, independent of the decoding module, the candidate set of symbol data using an event library and the secondary set of encoding data; and

computing a shortest path of a product graph of the candidate set of symbol data and the secondary set of encoding data;

the event library identifying likely failures encountered when the scanned representation of the hardcopy document is decoded;

the event library comprising a rule that represents a transformation.

11. The apparatus according to claim 10, further comprising a module for decoding the secondary set of encoding data for use by the rewrite module.

12. The apparatus according to claim 10, further comprising a module for decoding and decompressing the secondary set of encoding data for use by the rewrite module.

13. The apparatus according to claim 10, wherein said computing means performs a shortest path computation that includes a two-pass dynamic programming computation.

14. The apparatus according to claim 10, wherein the product graph is defined by:

nodes that correspond to both position in the candidate set of symbol data and the secondary set of encoding data; and

arcs that satisfy the candidate set of symbol data and the secondary set of encoding data.

15. The apparatus according to claim 14, wherein the product graph is further defined by symbols in the candidate set of symbol data that are matched with events from the event library.

16. The apparatus according to claim 10, wherein the rewrite module performs dynamic programming to decode the scanned representation of the hardcopy document.

17. The apparatus according to claim 10, wherein the secondary set of encoding data is encoded using one of separation coding, block coding, and convolution coding.

18. The apparatus according to claim 10, wherein the decoded form of the scanned representation includes certainty estimates of the candidate set of symbol data.