Method and system for automatic transcription correction

• US 5,883,986 A
• Filed: 06/02/1995
• Issued: 03/16/1999
• Est. Priority Date: 06/02/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kopec, Gary E., Chou, Philip A., Niles, Leslie T.
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Bella, Matthew C.
• Application Number:
  US08/460,454
• Time in Patent Office: 1,383 Days
• Field of Search: 382/229, 382/230, 382/231, 382/226, 382/227, 382/228, 382/310, 382/224, 382/215, 382/209, 382/309, 382/159, 382/155, 382/161, 382/203, 382/197
• US Class Current: 382/310
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context

Abstract

A method and system for automatically modifying an original transcription produced as the output of a recognition operation produces a second, modified transcription, such as, for example, automatically correcting an errorful transcription produced by an OCR operation. The invention uses information in an input text image of character images and in an original transcription associated with the input text image to modify aspects of a formal image source model that models as a grammar the spatial image structure of a set of text images. A recognition operation is then performed on the input text image using the modified formal image source model to produce a second, modified transcription. When the original transcription is errorful, the second transcription is a corrected transcription. Several aspects of the formal image source model may be modified; in particular, character templates to be used in the recognition operation are trained in the font of the glyphs occurring in the input text image. When errors in the original transcription are caused by matching glyphs against templates that are inadequately specified for the given input text image, the subsequently performed recognition operation on the text image using the trained, font-specific character templates produces a more accurate transcription.

Claims

1. A method of operating a system to correct errors in a transcription of a text image;

the system including a processor and a memory device for storing data;

the data stored in the memory device including instruction data the processor executes to operate the system;

the processor being connected to the memory device for accessing the data stored therein;

the method comprising;

operating the processor to obtain a formal two-dimensional image source model data structure, hereafter referred to as a 2D image model, modeling as a grammar a set of two-dimensional (2D) text images;

each 2D text image including a plurality of glyphs occurring therein;

each glyph being an image instance of a respective one of a plurality of characters in an input image character set;

the 2D image model including mapping data indicating a mapping between a glyph occurring in a 2D text image and a respective message string identifying a character in the input image character set;

operating the processor to obtain an image definition data structure defining a two-dimensional text image, hereafter referred to as an input 2D image of glyphs, including a plurality of glyphs occurring therein representing characters in the input image character set;

the input 2D image of glyphs having a vertical dimension size larger than a single line of glyphs;

the input 2D image of glyphs being one of the set of 2D text images modeled by the 2D image model;

operating the processor to obtain a first transcription data structure, hereafter referred to as a first transcription, associated with the input 2D image of glyphs;

the first transcription including a first ordered arrangement of transcription labels identifying characters in the input image character set represented by the glyphs occurring in the input 2D image of glyphs;

the first transcription including at least one transcription error;

operating the processor to modify the mapping data included in the 2D image model using the transcription labels in the first transcription to produce modified mapping data included in a modified 2D image model; and

operating the processor to perform a recognition operation on the input 2D image of glyphs using the modified mapping data included in the modified 2D image model;

the modified mapping data mapping a sequence of glyphs occurring in a 2D text image to a sequence of respective message strings identifying characters in the input image character set;

the sequence of message strings produced by the modified mapping data indicating a second transcription identifying the characters represented by the glyphs occurring in the input 2D image of glyphs and including a message string indicating a correction of the at least one transcription error in the first transcription;

wherein the glyphs included in the input 2D image of glyphs are perceptible as appearing in a visually consistent character image design, hereafter referred to as an input image font;

wherein the mapping data included in the 2D image model includes a first set of character templates;

wherein operating the processor to modify the mapping data included in the 2D image model includes

producing character template training data including a plurality of glyph samples and respectively paired glyph labels for each character in the input image character set;

each glyph sample being included in the input 2D image of glyphs;

each respectively paired glyph label being produced using the first transcription and indicating a respective one of the characters in the input image character set; and

producing a second set of character templates using the character template training data;

the second set of character templates indicating character images of the characters in the input image character set and being perceptible as appearing in the input image font; and

wherein performing the recognition operation on the input 2D image of glyphs using the modified 2D image model includes mapping each glyph occurring in the input 2D image of glyphs to a respective message string identifying the character in the input image character set using the second set of character templates appearing in the input image font.

2. The method of claim 1 of operating a system to correct errors in a transcription wherein the 2D image model includes spatial positioning data modeling spatial positioning of the plurality of glyphs occurring in a representative one of the set of 2D text images modeled by the 2D image model;

and

wherein operating the processor to produce the character template training data includes

operating the processor to determine a 2D image position indicating an image location of each glyph sample occurring in the input 2D image of glyphs using the spatial positioning data included in the 2D image model; and

operating the processor to produce the respectively paired glyph label for each glyph sample using the mapping data included in the 2D image model and using the first transcription;

the transcription labels included in the first transcription providing the message strings mapped to respective ones of the glyph samples.

3. The method of claim 1 of operating a system to correct errors in a transcription

wherein the 2D image model is represented as a stochastic finite state network data structure indicating a regular grammar, hereafter referred to as a 2D image network;

the 2D image network modeling the set of 2D text images as a series of nodes and transitions between pairs of the nodes;

the 2D image network representing the mapping data as at least one sequence of transitions from a first node to a final node, called a path, through the 2D image network;

each transition included in the at least one path indicating path data items associated therewith and accessible by the processor;

the path data items including an image displacement and a message string;

wherein the transcription data structure associated with the input 2D image of glyphs is represented as a finite state network data structure, hereafter referred to as a transcription network, modeling the transcription as a series of transcription nodes and a sequence of transitions between pairs of the transcription nodes;

each transition having a transcription label associated therewith;

a sequence of transitions, called a transcription path, through the transcription network indicating the ordered arrangement of the transcription labels in the transcription; and

wherein operating the processor to produce the character template training data further includes

merging the series of nodes of the 2D image network with the series of transcription nodes of the transcription network to produce a transcription-image network representing the modified mapping data as at least one complete transcription-image path through the transcription-image network;

the transcription labels in the transcription network providing the message strings associated with transitions in the transcription-image network;

performing a decoding operation on the input 2D image of glyphs using the transcription-image network to produce the at least one complete transcription-image path;

a transition included in the at least one complete transcription-image path indicating the path data items and mapping a 2D image position of a respective one of the glyphs occurring in the input 2D image of glyphs, computed using the image displacement, to a respective one of the transcription labels indicating a character in the input image character set;

the transcription label providing the respectively paired glyph label included in the character template training data; and

obtaining, from transitions included in the at least one complete transcription-image path, the 2D image position in the input 2D image of glyphs indicating an image location of a glyph sample in the input 2D image of glyphs and the glyph label paired therewith.

4. The method of claim 1 of operating a system to correct errors in a transcription wherein each glyph sample of the character template training data is represented as a 2D image pixel position included in a sample image region in the input 2D image of glyphs;

each sample image region including a plurality of image pixel positions in the input 2D image of glyphs, hereafter referred to as sample pixel positions, each indicating a sample pixel value; and

wherein producing the second set of character templates using the character template training data includes

operating the processor to produce, for each respective character template in the second set of character templates, a template image region including a plurality of template pixel positions for storing the respective character template; and

operating the processor to produce the set of character templates using the template image regions and the sample image regions;

producing the set of character templates including

(a) producing an image definition data structure for defining and storing an ideal image;

the ideal image being represented as a function of the second set of character templates being trained, and being a reconstruction of the input 2D image of glyphs formed by positioning respective ones of the character templates in the second set of character templates in an image plane at ideal image pixel positions indicating 2D image pixel positions of glyph samples occurring in the input 2D image of glyphs;

each respective one of the character templates positioned in the ideal image being identified by the glyph label paired with the 2D image pixel position;

(b) computing pixel scores for template pixel positions in template image regions using the sample pixel values of selected ones of the sample pixel positions in selected ones of the sample image regions included in the input 2D image of glyphs; and

(c) sequentially assigning a pixel value to selected template pixel positions in selected template image regions;

the selected template pixel positions being selected on the basis of the pixel scores optimizing the function representing the ideal image such that, when all template pixel positions have been assigned pixel values, the pixel value assigned to each selected template pixel position optimizes a matching score measuring a match between the input 2D image of glyphs and the ideal image.

5. The method of claim 1 of operating a system to correct errors in a transcription wherein each sample image region of the character template training data includes a 2D image pixel position indicating an input 2D image location of a glyph and is identified as a training data sample for the character template indicated by the respectively paired glyph label;

each sample image region including a plurality of image pixel positions in the input 2D image of glyphs, hereafter referred to as sample pixel positions, each indicating a sample pixel value; and

wherein producing the second set of character templates using the character template training data includes

operating the processor to produce, for each respective character template in the second set of character templates, a template image region including a plurality of template pixel positions for storing the respective character template; and

operating the processor to produce the set of character templates using the template image regions and the sample image regions;

producing the set of character templates including

(a) computing template pixel scores for respective ones of the template pixel positions in the template image regions using the sample pixel values indicated by the sample pixel positions included in the sample image regions;

(b) assigning a foreground pixel value to a template pixel position, referred to as an assigned template pixel position, in one of the template image regions;

the assigned template pixel position being selected on the basis of the template pixel scores;

(c) modifying the sample pixel values of the sample pixel positions used in computing the template pixel score for the assigned template pixel position to indicate modified sample pixel values that, when used in computing a subsequent template pixel score for an unassigned template pixel position, reduce the chance that a foreground pixel value will be assigned to the unassigned template pixel position on the basis of the subsequent template pixel score; and

(d) repeating substeps (a), (b) and (c) until a stopping condition indicates that the second set of character templates is complete.

6. The method of claim 1 of operating a system to correct errors in a transcription wherein each character template included in the second set of character templates is based on a character template model defining character image positioning of first and second adjacent character images in an image, referred to as a sidebearing model of character image positioning, wherein a template image origin position of the second character image is displaced in the image by a character set width from a template image origin position of the first character image adjacent to and preceding the second character image;

the sidebearing model of character image positioning requiring that, when a first rectangular bounding box drawn to contain the first character image overlaps with a second rectangular bounding box drawn to contain the second character image, the first and second character images have substantially nonoverlapping foreground pixels; and

wherein operating the processor to produce the second set of character templates further includes determining, for each character template, a character set width thereof using the character template training data.

7. A method of operating a system to correct errors in a transcription of a text image;

the system including a processor and a memory device for storing data;

the data stored in the memory device including instruction data the processor executes to operate the system;

the processor being connected to the memory device for accessing the data stored therein;

the method comprising;

operating the processor to obtain a formal two-dimensional image source model data structure, hereafter referred to as a 2D image model, modeling as a grammar a set of two-dimensional (2D) text images;

each 2D text image including a plurality of glyphs occurring therein;

each glyph being an image instance of a respective one of a plurality of characters in an input image character set;

the 2D image model including mapping data indicating a mapping between a glyph occurring in a 2D text image and a respective message string identifying a character in the input image character set;

operating the processor to obtain an image definition data structure defining a two-dimensional text image, hereafter referred to as an input 2D image of glyphs, including a plurality of glyphs occurring therein representing characters in the input image character set;

the input 2D image of glyphs having a vertical dimension size larger than a single line of glyphs;

the input 2D image of glyphs being one of the set of 2D text images modeled by the 2D image model;

operating the processor to obtain a first transcription data structure, hereafter referred to as a first transcription, associated with the input 2D image of glyphs;

the first transcription including a first ordered arrangement of transcription labels identifying characters in the input image character set represented by the glyphs occurring in the input 2D image of glyphs;

the first transcription including at least one transcription error;

operating the processor to modify the mapping data included in the 2D image model using the transcription labels in the first transcription to produce modified mapping data included in a modified 2D image model; and

operating the processor to perform a recognition operation on the input 2D image of glyphs using the modified mapping data included in the modified 2D image model;

the modified mapping data mapping a sequence of glyphs occurring in a 2D text image to a sequence of respective message strings identifying characters in the input image character set;

the sequence of message strings produced by the modified mapping data indicating a second transcription identifying the characters represented by the glyphs occurring in the input 2D image of glyphs and including a message string indicating a correction of the at least one transcription error in the first transcription;

wherein operating the processor to modify the mapping data included in the 2D image model includes

constructing a language model using the transcription labels included in the first transcription;

the language model modeling as a grammar the ordered arrangement of the transcription labels indicated by the first transcription as at least two sequences of transcription labels;

one of the sequences of transcription labels indicating the ordered arrangement of the transcription labels indicated by the first transcription; and

combining the language model with the mapping data included in the 2D image model to produce the modified mapping data included in the modified 2D image model;

the modified mapping data constraining the mapping between a glyph occurring in a 2D text image and a respective message string identifying a character in the input image character set to map a sequence of glyphs to a sequence of respective message strings indicated by the language model and identifying characters in the input image character set;

the sequence of respective message strings produced by the modified mapping data being one of the at least two sequences of transcription labels occurring in the first transcription.

8. The method of claim 7 of operating a system to correct errors in a transcription wherein the language model constructed using the transcription labels included in the first transcription is a character n-gram model indicating a plurality of sequences of n transcription labels occurring in the first transcription.

9. The method of claim 8 of operating a system to correct errors in a transcription wherein the language model is a character bigram model.

10. The method of claim 8 wherein the sequences of n transcription labels indicated by the character n-gram model include at least one sequence of transcription labels added using information about the language represented by the glyphs occurring in the input 2D text image.

11. The method of claim 7 of operating a system to correct errors in a transcription wherein the 2D image model is represented as a stochastic finite state network data structure indicating a regular grammar, hereafter referred to as a 2D image network;

the 2D image network modeling the set of 2D text images as a series of nodes and transitions between pairs of the nodes;

the 2D image network representing the mapping data as at least one sequence of transitions from a first node to a final node, called a path, through the 2D image network;

each transition included in the at least one path indicating path data items associated therewith and accessible by the processor;

the path data items including an image displacement and a message string;

wherein constructing the language model using the transcription labels included in the first transcription includes constructing a language model network represented as a finite state network data structure;

the language model network modeling the plurality of sequences of transcription labels as a series of transcription nodes and a sequence of transitions between pairs of the transcription nodes;

each transition in the language model network having a transcription label associated therewith;

a sequence of transitions, called a language model path, through the language model network indicating one of the plurality of sequences of transcription labels;

wherein operating the processor to combine the language model with the mapping data included in the 2D image model includes merging the series of nodes of the 2D image network with the series of transcription nodes of the language model network to produce a language-image network representing the modified mapping data as at least one complete language-image path through the language-image network;

the transcription labels in the language model network providing the message strings associated with transitions in the language-image network; and

wherein performing the recognition operation on the input 2D image of glyphs using the modified mapping data includes performing the recognition operation using the language-image network;

the second transcription being produced by extracting the sequence of message strings from the sequence of transitions included in the at least one complete language-image path through the language-image network.

12. A method of operating a system to correct errors in a transcription of a text image;

the system including a processor and a memory device for storing data;

the data stored in the memory device including instruction data the processor executes to operate the system;

the processor being connected to the memory device for accessing the data stored therein;

the method comprising;

operating the processor to obtain a stochastic finite state network data structure, hereafter referred to as a two-dimensional (2D) image network;

the 2D image network modeling as a grammar a set of 2D text images, each including a plurality of glyphs;

the 2D image network including a first set of character templates representing character images in an input image character set;

a representative one of the set of 2D text images being modeled as at least one path through the 2D image network;

the at least one path indicating path data items associated therewith and accessible by the processor;

the path data items indicating character templates included in the first set of character templates, image origin positions, and message strings such that the at least one path through the 2D image network maps respective ones of the plurality of glyphs included in the representative image to message strings indicating characters in the input image character set;

operating the processor to obtain an image definition data structure defining a two-dimensional text image, hereafter referred to as an input 2D image of glyphs, including a plurality of glyphs occurring therein representing characters in the input image character set;

the input 2D image of glyphs having a vertical dimension size larger than a single line of glyphs;

the input 2D image of glyphs being one of the set of 2D text images modeled by the 2D image model;

operating the processor to obtain a first transcription data structure, hereafter referred to as a first transcription, associated with the input 2D image of glyphs;

the first transcription including a first ordered arrangement of transcription labels identifying characters in the input image character set represented by the glyphs occurring in the input 2D image of glyphs;

the first transcription including at least one transcription error;

operating the processor to produce a second set of character templates using the 2D image model;

the second set of character templates being produced using character template training data produced using the first transcription and the input 2D image;

operating the processor to construct a language model network represented as a finite state network data structure using the transcription labels included in the first transcription;

the language model network modeling a plurality of sequences of transcription labels occurring in the first transcription as a series of transcription nodes and a sequence of transitions between pairs of the transcription nodes;

each transition in the language model network having a transcription label associated therewith;

a sequence of transitions, called a language model path, through the language model network indicating one of the plurality of sequences of transcription labels;

operating the processor to merge the series of nodes of the 2D image network with the series of transcription nodes of the language model network to produce a language-image network;

the transcription labels in the language model network providing the message strings associated with transitions in the language-image network; and

operating the processor to perform a decoding operation on the input 2D image of glyphs using the language-image network including the second set of character templates to produce at least one complete language-image path through the language-image network;

the language-image network mapping a plurality of glyphs included in the input 2D image of glyphs to a sequence of message strings indicating characters in the input image character set such that the sequence of message strings indicates one of the plurality of sequences of transcription labels indicated by a language model path through the language model network and the sequence of message strings includes a message string that indicates a correction for the at least one transcription error;

the sequence of message strings indicating a second, corrected transcription.

13. The method of claim 12 wherein the decoding operation performed on the input 2D image of glyphs using the language-image network is a dynamic programming based decoding operation.

14. The method of claim 12 of operating a system to correct errors in a transcription wherein each character template included in the second set of character templates is based on a character template model defining character image positioning of first and second adjacent character images in an image, referred to as a sidebearing model of character image positioning, wherein a template image origin position of the second character image is displaced in the image by a character set width from a template image origin position of the first character image adjacent to and preceding the second character image;

the sidebearing model of character image positioning requiring that, when a first rectangular bounding box drawn to contain the first character image overlaps with a second rectangular bounding box drawn to contain the second character image, the first and second character images have substantially nonoverlapping foreground pixels; and

wherein operating the processor to produce the second set of character templates further includes determining, for each character template, a character set width thereof using the character template training data.

15. A method of operating a system to correct errors in a transcription of a text image;

the system including a processor and a memory device for storing data;

the data stored in the memory device including instruction data the processor executes to operate the system;

the processor being connected to the memory device for accessing the data stored therein;

the method comprising;

operating the processor to obtain a formal two-dimensional image source model data structure, hereafter referred to as a 2D image model, modeling as a grammar a set of two-dimensional (2D) text images;

each 2D text image including a plurality of glyphs occurring therein;

each glyph being an image instance of a respective one of a plurality of characters in an input image character set;

the 2D image model including mapping data indicating a mapping between a glyph occurring in a 2D text image and a respective message string identifying a character in the input image character set;

operating the processor to obtain an image definition data structure defining a two-dimensional text image, hereafter referred to as an input 2D image of glyphs, including a plurality of glyphs occurring therein representing characters in the input image character set;

the input 2D image of glyphs having a vertical dimension size larger than a single line of glyphs;

the input 2D image of glyphs being one of the set of 2D text images modeled by the 2D image model;

operating the processor to obtain a first transcription data structure, hereafter referred to as a first transcription, associated with the input 2D image of glyphs;

the first transcription including a first ordered arrangement of transcription labels identifying characters in the input image character set represented by the glyphs occurring in the input 2D image of glyphs;

the first transcription including at least one transcription error;

operating the processor to modify the mapping data included in the 2D image model using the transcription labels in the first transcription to produce modified mapping data included in a modified 2D image model; and

operating the processor to perform a recognition operation on the input 2D image of glyphs using the modified mapping data included in the modified 2D image model;

the modified mapping data mapping a sequence of glyphs occurring in a 2D text image to a sequence of respective message strings identifying characters in the input image character set;

the sequence of message strings produced by the modified mapping data indicating a second transcription identifying the characters represented by the glyphs occurring in the input 2D image of glyphs and including a message string indicating a correction of the at least one transcription error in the first transcription;

wherein the step of operating the processor to modify the mapping data included in the 2D image model includes operating the processor to perform a constraining operation on the 2D image model using the first transcription to produce the modified mapping data;

the modified mapping data included in the 2D image model being capable of producing a representative transcription of a 2D text image that indicates the first ordered arrangement of transcription labels included in the first transcription;

the constraining operation and the modified mapping data together preventing the recognition operation from producing all possible message strings capable of being produced by the mapping data of the 2D image model in an unmodified form and limiting the recognition operation to producing a second transcription identifying only the characters represented by the glyphs occurring in the input 2D image of glyphs.