Method for aligning a text image to a transcription of the image

• US 5,689,585 A
• Filed: 04/28/1995
• Issued: 11/18/1997
• Est. Priority Date: 04/28/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chou, Philip Andrew, Bloomberg, Dan S., Niles, Leslie T., Kopec, Gary E.
• Primary Examiner(s): COUSO, YON JUNG
• Assistant Examiner(s): Kahng, Anthony H.
• Application Number:
  US08/431,004
• Time in Patent Office: 935 Days
• Field of Search: 382/229, 382/224, 364/419.13, 364/419.1
• US Class Current: 382/229
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors

Abstract

A method for establishing a relationship between a text image and a transcription associated with the text image uses conventional image processing techniques to identify one or more geometric attributes, or image parameters, of each of a sequence of regions of the text image. The transcription labels in the transcription are analyzed to determine a comparable set of parameters in transcription label sequence. A matching operation then matches the respective parameters of the two sequences to identify image regions that match with transcription regions. The result is an output data structure that minimally identifies image locations of interest to a subsequent operation that processes the text image. The output data structure may also pair each of the image locations of interest to a transcription location, in effect producing a set of labeled image locations. In one embodiment, the sequence of locations of words and their observed lengths in the text image are determined. The transcription is analyzed to identify words, and transcription word lengths are computed using an estimated image character width of glyphs in the text image. The sequence of observed image word lengths is then matched to the sequence of computed transcription word lengths using a dynamic programming algorithm that finds a best path through a two-dimensional lattice of nodes and transitions between nodes, where the transitions represent pairs of sequences of zero or more word lengths. An output data structure contains entries, each of which pairs a transcription word with a matching image word location.

Claims

1. A method of operating a machine to align image words in a text image to transcription words in a transcription associated with the text image;

the machine 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 machine;

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

the method comprising;

operating the processor to obtain an image definition data structure defining a text image including a plurality of glyphs representing characters in an image character set;

operating the processor to obtain a transcription data structure associated with the text image and including a plurality of transcription labels indicating character codes representing characters in the image character set;

operating the processor to produce an ordered image word sequence of image words occurring in the text image;

each image word being an image region in the text image including at least one glyph;

operating the processor to produce an ordered transcription word sequence of transcription words occurring in the transcription data structure;

each transcription word being a sequence of at least one transcription label indicating a character code in the image character set; and

operating the processor to perform an alignment operation to align image words in the ordered image word sequence with transcription words in the ordered transcription word sequence subject to a constraint of maintaining word order in each of the ordered transcription word sequence and the ordered image word sequence during alignment;

the alignment operation producing an image-transcription alignment data structure indicating each image word in the ordered image word sequence paired with either no (a null) transcription word or with at most one transcription word in the ordered transcription word sequence.

2. The method of operating a machine of claim 1 wherein

operating the processor to produce the ordered image word sequence of image words occurring in the text image includes determining an image word length value for each image word in the ordered image word sequence;

operating the processor to produce the ordered transcription word sequence of transcription words occurring in the transcription data structure includes producing a transcription word length value for each transcription word in the ordered transcription word sequence; and

the alignment operation aligns transcription words in the ordered transcription word sequence with image words in the ordered image word sequence by matching image word lengths to transcription word lengths.

3. The method of operating a machine of claim 2 further including operating the processor to determine an image character width value indicating an estimated character width of a glyph in the text image;

and wherein the transcription word length value produced for each transcription word in the ordered transcription word sequence is produced using the image character width value.

4. The method of operating a machine of claim 1 wherein, when the text image includes a first image word and the transcription data structure, when visually inspected and compared with the text image, does not include transcription labels visually paired with the first image word thereby indicating a missing transcription word, the alignment operation detects the missing transcription word;

the alignment operation indicating in the image-transcription alignment data structure that the first image word is paired with no (a null) transcription word.

5. The method of operating a machine of claim 1

wherein operating the processor to produce the ordered image word sequence of image words occurring in the text image includes determining an image word parameter for each image word in the ordered image word sequence;

wherein operating the processor to produce the ordered transcription word sequence of transcription words occurring in the transcription data structure includes producing a transcription word parameter for each transcription word in the ordered transcription word sequence; and

wherein the alignment operation uses similarity measurements between the image word parameters and the transcription word parameters to perform the alignment.

6. The method of operating a machine of claim 1 wherein

the transcription data structure includes a transcription label error causing the processor to identify a sequence of transcription labels as a transcription word, referred to as an errorful transcription word, in the ordered transcription word sequence that cannot be identically matched to an image word in the text image by visual inspection of the text image;

the errorful transcription word including at least one of a transcription label deletion, a transcription label substitution, or a transcription label insertion; and

the alignment operation, when pairing image words in the ordered image word sequence to transcription words in the ordered transcription word sequence including the errorful transcription word, determines whether the errorful transcription word can be paired with an image word in the ordered image word sequence and if so, determines with which image word to pair the errorful transcription word.

7. The method of operating a machine of claim 1 wherein

the alignment operation is implemented as a dynamic programming operation that represents the ordered transcription word sequence and the ordered image word sequence as a two-dimensional lattice data structure, hereafter referred to as a lattice, including a plurality of nodes and transitions between nodes;

a transition between two nodes representing a pair of sequences of zero or more image words in the ordered image word sequence and zero or more transcription words in the ordered transcription word sequence;

the dynamic programming operation producing a path through the nodes in the lattice from a first node to a final node using scores computed for nodes and computed for transitions between nodes in the lattice;

a score for a transition indicating a similarity measurement between the zero or more transcription words and the zero or more image words associated with the transition;

the dynamic programming operation storing node identification information for each node and transition in the path, as the path through the lattice is produced; and

the alignment operation produces the image-transcription alignment data structure indicating transcription words paired to image words by backtracing through the nodes included in the path from the final node to the first node using the node identification information.

8. The method of operating a machine of claim 7 wherein the similarity measurement indicated by the score for a transition is a function of image word lengths of the zero or more image words and of the zero or more transcription words associated with the transition.

9. The method of operating a machine of claim 1 wherein

each image word in the ordered image word sequence is represented as an image word location defined according to an image coordinate system describing the text image;

each transcription word in the ordered transcription word sequence is represented as a transcription word location in the ordered label sequence of the transcription labels included in the transcription data structure; and

transcription words aligned with image words are represented in the image-transcription alignment data structure as transcription word locations in the transcription and as image word locations in the text image, respectively.

10. A method of operating a machine to label image locations of image regions in a text image with label data available in a transcription data structure associated with the text image;

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

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

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

the method comprising;

operating the processor to store, in the memory device of the machine, an image definition data structure defining a text image including a plurality of glyphs;

operating the processor to store, in the memory device of the machine, a transcription data structure associated with the text image and including an ordered sequence of transcription labels indicating character code information about image regions occurring in the text image;

operating the processor to produce an ordered image region sequence of image regions occurring in the text image;

each image region being defined with respect to its location in the text image relative to at least one glyph occurring in the text image;

operating the processor to produce an ordered transcription region sequence of transcription regions occurring in the transcription data structure;

each transcription region being a sequence of at least one transcription label;

operating the processor to perform an alignment operation to align image regions in the ordered image region sequence with transcription regions in the ordered transcription region sequence;

the alignment operation computing similarity measurements measuring a similarity between image regions and transcription regions;

the alignment operation determining a best pairing between the image regions in the ordered image region sequence and transcription regions in the ordered transcription region sequence that optimizes the similarity measurements such that each one of the image regions in the ordered image region sequence is paired with either no (a null) transcription region or with at most one transcription region in the ordered transcription region sequence; and

operating the processor to produce an image transcription alignment data structure indicating transcription regions paired with image region locations of paired image regions.

11. The method of operating a machine of claim 10 further including

operating the processor to determine an image region parameter value for each image region;

the image region parameter value indicating a measurement of a geometric characteristic of the image region;

operating the processor to determine an image glyph parameter value indicating a measurement of a geometric characteristic of a glyph occurring in the text image; and

operating the processor to determine a transcription region parameter for each transcription region in the ordered transcription region sequence using the image glyph parameter value; and

wherein the alignment operation is implemented as a dynamic programing operation that aligns image regions in the ordered image region sequence to transcription regions in the ordered transcription region sequence using similarity measurements between image region parameters and transcription region parameters, subject to a constraint of maintaining region order in each of the ordered transcription region sequence and the ordered image region sequence during the dynamic programming operation.

12. The method of operating a machine of claim 10 wherein, when the ordered transcription region sequence includes fewer transcription regions than image regions included in the ordered image region sequence, the transcription data structure indicates a missing transcription region;

and wherein the alignment operation uses the similarity measurements to detect the missing transcription region so that the best pairing between the image regions in the ordered image region sequence and transcription regions in the ordered transcription region sequence indicates the missing transcription region.

13. A method of operating a machine to pair image words in a two-dimensional (2D) text image with transcription words in a transcription associated with the text image;

the machine 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 machine;

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

the method comprising;

operating the processor to receive and store, in the memory device of the machine, an image definition data structure defining a two-dimensional (2D) text image of pixels and including a plurality of glyphs;

the 2D text image having a vertical dimension size larger than a single line;

the plurality of glyphs representing characters in an image character set;

operating the processor to receive and store, in the memory device of the machine, a transcription data structure associated with the 2D text image and including a plurality of transcription labels indicating character codes representing characters in the image character set;

operating the processor to determine an image word location in the 2D text image for each of a plurality of image words occurring therein;

each image word being an image region including at least one glyph positioned with respect to an image baseline;

the plurality of image word locations identifying an ordered image word sequence of the image words occurring in the 2D text image;

operating the processor to determine an image word length value for each image word in the 2D text image indicating a length of the image word;

operating the processor to determine an image character width value indicating an estimated character width of a glyph in the 2D text image;

operating the processor to determine a transcription word location for each of a plurality of transcription words occurring in the transcription data structure;

each transcription word being a sequence of at least one transcription label indicating a character code in the image character set and separated from other transcription labels indicating character codes in the image character set by a transcription word boundary character code;

the plurality of transcription word locations identifying an ordered transcription word sequence of the transcription words occurring in the transcription data structure;

operating the processor to determine a transcription word length value for each transcription word using the image character width value and a count of the transcription labels included in the transcription word;

operating the processor to perform an alignment operation to align transcription word lengths in the ordered transcription word sequence with image word lengths in the ordered image word sequence;

the alignment operation maintaining the ordered image word sequence and the ordered transcription word sequence when aligning the image word lengths and the transcription word lengths;

the alignment operation producing a list of word pairs indicating transcription words in the ordered transcription word sequence paired to matching image words in the ordered image word sequence; and

operating the processor to produce an image-transcription alignment data structure using the list of word pairs, the image word locations and the transcription word locations;

the image-transcription alignment data structure indicating, for each word pair, the transcription word location of a transcription word and the image word location of a paired image word.

14. The method of operating a machine of claim 13 wherein, when the 2D text image includes a first image word and the transcription dam structure, when visually inspected and compared with the 2D text image, does not include transcription labels visually paired with the first image word thereby indicating a missing transcription word, the alignment operation detects the missing transcription word;

the alignment operation further producing missing word data indicating that the first image word is not paired with a transcription word;

the image-transcription alignment data structure using the missing word data to indicate that an image word location of the first image word is paired with no transcription word location of a transcription word.

15. The method of operating a machine of claim 13 wherein

the alignment operation is implemented as a dynamic programming operation that represents the ordered transcription word sequence and the ordered image word sequence as a two-dimensional lattice data structure, hereafter referred to as a lattice, including a plurality of nodes and transitions between nodes;

a transition between two nodes representing a pair of sequences of zero or more image words in the ordered image word sequence and zero or more transcription words in the ordered transcription word sequence;

the dynamic programming operation producing a path through the nodes in the lattice from a first node to a final node using scores computed for nodes and computed for transitions between nodes in the lattice;

a score for a transition indicating a similarity measurement between the zero or more transcription words and the zero or more image words associated with the transition;

the dynamic programming operation storing node identification information for each node and transition in the path, as the path through the lattice is produced; and

the alignment operation produces the image-transcription alignment data structure indicating the list of word pairs by backtracing through the nodes included in the path from the final node to the first node using the node identification information.