Method and apparatus for converting bitmap image documents to editable coded data using a standard notation to record document recognition ambiguities

• US 5,359,673 A
• Filed: 12/27/1991
• Issued: 10/25/1994
• Est. Priority Date: 12/27/1991
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: de La Beaujardiere, Jean-Marie R.
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/814,347
• Time in Patent Office: 1,033 Days
• Field of Search: 382/40, 382/57, 382/36, 382/39, 382/61, 364/419, 364/419.08, 364/419.14, 395/145-147
• US Class Current: 382/229
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition

Abstract

Documents represented as bitmap images are transformed into coded textual data and coded graphics data by graphics and textual recognizers, which use a standard notation for recording the results of the document recognition processes, including any ambiguities, in a document description language. Recognized portions of the document, represented as editable coded data, such as for example ASCII, are placed in elements, defined in the document description language, with all contents of an element sharing some common characteristic. Elements can include, for example: character-string-elements, questionable-character-elements, questionable-word-elements, verified-word-elements, alternate-word-elements, segment-elements, and arc-elements.

Claims

1. A method of transforming a document represented as a bitmap image into an editable coded data stream defined using a machine readable document description language that records coded information resulting from the document transformation process and information regarding uncertainties in the document transformation process, comprising:

performing a first transformation operation on at least a text portion of said bitmap image using a character recognition apparatus, to transform at least said text portion of said bitmap image into coded information recognized with a level of confidence;

outputting and recording said coded information into one or more elements that are defined using said document description language, each element having a machine readable element type identifier that indicates the type of said coded information regarding the recognized bitmap image recorded in said element so that the type of coded information contained in each element can be known without examining the coded information contained in each element, the element type identifier for each element having been defined based on the type of coded information recorded in the element and the level of confidence with which said bitmap image represented by said coded information was recognized so that each of said elements is selectively identified, each element having coded information of a single type recorded therein; and

when said character recognition apparatus determines that the recognized bitmap image contained in an element has not been recognized with at least a predetermined level of confidence, recording in said element uncertainty information determined by said first recognition apparatus regarding said recognized bitmap image contained in said element;

wherein said element type identifier is a character-string-element or a questionable-character-element, each character-string-element containing a string of consecutive characters recognized by said character recognition apparatus with at least said predetermined level of confidence, each questionable-character-element containing said uncertainty information determined by said character recognition apparatus for a character which was not recognized with at least said predetermined level of confidence by said character recognition apparatus.

2. The method of claim 1, wherein said uncertainty information includes a degree of uncertainty with which said character recognition apparatus transformed said bitmap image.

3. The method of claim 1, further comprising:

for each questionable-character-element, using a word recognizer to transform said questionable-character-element and adjacent confidently recognized characters in a same word as said questionable-character-element into one or more elements having an element type identifier defined as a verified-word-element, by substituting alternate characters for said questionable-character-element when one or more words created by said substituting are recognized by said word recognition apparatus;

when more than one verified-word-element is transformed for each questionable-character-element, said more than one verified-word-elements being placed in an element having an element type identifier defined as an alternate-word-element;

said question-able-character-element remaining when no verified words are recognized by said word recognition apparatus.

4. The method of claim 3, further comprising:

for each alternate-word-element, using a semantics analyzer to transform verified words of the verified-word-elements contained in each alternate word element into an element identified as a character-string-element corresponding to one of the verified words contained in said alternate-word-element when said semantics analyzer determines that said one of said verified words is a correct word, said alternate-word-element remaining when none of said verified words is determined to be a correct word by said semantics analyzer.

5. The method of claim 4 wherein for each verified-word-element contained in each alternate word element, said semantics analyzer determines and identifies a confidence level of each verified word contained in each verified-word-element, and indicates the confidence level of each verified-word-element when none of the verified words in an alternate-word-element are determined to be a correct word by said semantics analyzer.

6. The method of claim 1, wherein for each questionable-character-element, said uncertainty information pertaining to a character not recognized with at least said predetermined level of confidence includes a most likely uncertain character identified by said character recognition apparatus.

7. The method of claim 6, wherein for each questionable-character-element, said uncertainty information pertaining to a character not recognized with at least said predetermined level of confidence also includes a degree of confidence determined by said character recognition apparatus for said most likely uncertain character.

8. The method of claim 1, wherein for each questionable-character-element, said uncertainty information pertaining to a character not recognized with at least said predetermined level of confidence includes alternate possible uncertain characters identified by said character recognition apparatus.

9. The method of claim 8, wherein for each questionable-character-element, said uncertainty information pertaining to a character not recognized with at least said predetermined level of confidence also includes a degree of confidence determined by said character recognition apparatus for each said alternate possible uncertain character.

10. A method of transforming a document represented as a bitmap image into an editable coded data stream defined using a machine readable document description language that records coded information resulting from the document transformation process and information regarding uncertainties in the document transformation process, comprising the steps of:

a) analyzing text portions of said bitmap image using a character recognizer to transform said text portions of said bitmap image into said coded information recognized with a level of confidence;

b) outputting and recording said coded information into a series of elements that are defined using said document description language, each element having a machine readable element type identifier that indicates the type of said coded information regarding the recognized bitmap image recorded in said element so that the type of coded information contained in each element can be known without examining the coded information contained in each element;

c) the element type identifier for each element having been defined using said document description language based on the type of coded information recorded in the elements by defining the type identifier of each of said elements as character-string-elements or questionable-character-elements, each element defined as a character-string-element containing a string of consecutive characters recognized by said character recognizer with at least a predetermined level of confidence, each element defined as a questionable-character-element containing information pertaining to a character not recognized with at least said predetermined level of confidence, said character-string-elements and said questionable-character-elements being arranged as a continuous stream of elements based on an order of the characters in said bitmap image, each element having coded information of a single type recorded therein;

d) for each element defined as a questionable-character-element, analyzing the coded information pertaining to the character contained therein and adjacent confidently recognized characters contained in a same word as said questionable-character-element using a word recognizer, to transform and record said coded information and adjacent confidently recognized characters into one or more elements having type identifiers defined as verified-word-elements by substituting alternate characters for said questionable-character-element and determining whether one or more verified words created by said substituting are recognized by said word recognizer; and

e) when more than one verified-word-elements are transformed for each questionable-character-element, placing said more than one elements defined as verified-word-elements in an element having an element type identifier defined as an alternate-word-element, said questionable-character-element remaining when no verified words are recognized by said word recognizer.

11. The method of claim 10, further comprising:

f) for each alternate-word-element, analyzing the verified words of the verified-word-elements contained therein and surrounding words using a semantics analyzer, to transform said alternate-word-element into an element identified as a character-string-element corresponding to one of verified words contained in said alternate-word-element when said semantics analyzer determines that one of said verified words is a correct word, said alternate-word-element remaining when none of said verified words is determined to be a correct word by said semantics analyzer.

12. The method of claim 11, wherein for each verified-word-element contained in each alternate-word-element, said semantics analyzer determines and identifies a confidence level of each verified word contained in each verified-word-element, and indicates the confidence level for each verified-word-element when none of the verified words in an alternate-word-element are determined to be a correct word by said semantics analyzer.

13. The method of claim 10, wherein for each questionable character element, said information pertaining to a character not recognized with at least said predetermined level of confidence includes a most likely uncertain character identified by said character recognizer.

14. The method of claim 13, wherein for each questionable-character-element, said information pertaining to a character not recognized with at least said predetermined level of confidence also includes a degree of confidence determined by said character recognizer for said most likely uncertain character.

15. The method of claim 10, wherein for each questionable-character-element, said information pertaining to a character not recognized with at least said predetermined level of confidence includes alternate possible uncertain characters identified by said character recognizer.

16. The method of claim 15, wherein for each questionable-character-element, said information pertaining to a character not recognized with at least said predetermined level of confidence also includes a degree of confidence determined by said character recognizer for each said alternate possible uncertain character.

17. An automatic document recognition apparatus for transforming text documents represented as bitmap image data into an editable coded data stream defined using a machine readable document description language that records coded data resulting from the document transformation process and information regarding uncertainties in the document transformation process, said apparatus comprising:

a character recognizer having;

a) first transformation means for performing a character recognition operation on said bitmap image representation of said document to transform said document into coded character data recognized with a level of confidence; and

b) first identification means for outputting and recording said coded character data into one or more elements that are defined using said document description language, said first identification means further defining a machine readable element type identifier for each element, said element type identifier indicating the type of said coded character data regarding the recognized bitmap image recorded in said element so that the type of coded character data contained in each element can be known without examining the coded character data contained in each element, said identification means selectively identifying said one or more elements by defining the element type identifier for each element based on the type of coded data recorded in the element and the level of confidence with which said bitmap image was recognized, each element having coded character data of a single type recorded therein, and, when said first transformation means determines that the coded character data contained in the element has not been transformed with a predetermined level of confidence, said identification means also recording in said element uncertainty information determined by said first transformation means regarding said coded character data contained in said element;

wherein said element type identifier is a character-string-element or a questionable-character-element, each character-string-element containing a string of consecutive characters recognized by said character recognition apparatus with at least said predetermined level of confidence, each questionable-character-element containing said uncertainty information determined by said character recognition apparatus for a character which was not recognized with at least said predetermined level of confidence by..said character recognition apparatus.

18. The apparatus of claim 17, wherein said uncertainty information includes a confidence level with which said first transformation means determined said coded data.

19. The apparatus of claim 17, further comprising:

a word recognizer having;

i) second transformation means for transforming each questionable-character-element and adjacent confidently recognized characters in a same word as the question-able-character-element into one or more verified words by substituting alternate characters for the questionable-character-element and verifying that a word resulting from said substituting exists in a lexicon; and

ii) second identification means using said document description language for placing each verified word in an element having an element type identifier defined as a verified-word-element, and when more than one verified-word-elements are created for a questionable-character-element, placing said more than one verified-word-elements in an element having an element type identifier defined as an alternate-word-element, said questionable-character-element remaining when no verified words are determined to exist.

20. The apparatus of claim 19, further comprising:

a semantics analyzer including;

1) means for determining which verified word within an alternate-word-element is a correct verified word based on words surrounding the alternate-word-element; and

2) third identification means for identifying said correct verified word and for replacing said alternate-word-element with an element identified as a character-string-element containing said correct verified word.