Dynamic programming operation with skip mode for text line image decoding

• US 6,594,393 B1
• Filed: 05/12/2000
• Issued: 07/15/2003
• Est. Priority Date: 05/12/2000
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Popat, Ashok C., Bloomberg, Dan S., Minka, Thomas P.
• Primary Examiner(s): Dastouri, Mehrdad
• Application Number:
  US09/569,531
• Time in Patent Office: 1,159 Days
• Field of Search: 382/174, 382/177, 382/209, 382/217, 382/218, 382/219, 382/220, 382/229, 382/233, 382/310, 382/159, 704/242, 704/243, 704/256, 707/6
• US Class Current: 382/218
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

In a text recognition system, the computational efficiency of a text line image decoding operation is improved by utilizing the characteristic of a graph known as the cut set. The branches of the data structure that represents the image are initially labeled with estimated scores. When estimated scores are used, the decoding operation must perform iteratively on a text line before producing the best path through the data structure. After each iteration, nodes in the best path are re-scored with actual scores. The decoding operation incorporates an operating mode called skip mode. When the number of consecutive image positions for which the change value of cumulative path scores between current and prior iterations is substantially constant and exceeds a threshold, this signals the presence of a cut set, and the score change value is added to a previously computed path score until a re-scored node is encountered, thereby eliminating the expensive computation of new cumulative path scores at those image positions.

Claims

1. A method for operating a processor-controlled machine to decode a text line image;

the method comprising;

while a skip mode switch is off, for each image position in the text line image,

a first computing step of computing a maximum cumulative score indicating a measurement of a match between a sequence of character templates and an image region in the text line image from a starting location of the text line image to the image position;

a second computing step of computing a score change value between the maximum cumulative score and a prior maximum cumulative score computed at the image position; and

comparing the score change value to a prior score change value and turning the skip mode switch on when the score change value is substantially constant for at least a predetermined number of consecutive image positions in the text line image;

while the skip mode switch is on, for each image position in the text line image, a third computing step of computing the maximum cumulative score by adding the score change value to a prior maximum cumulative score computed at the image position; and

producing a transcription of the text line image using the maximum cumulative scores.

2. The method of claim 1 for operating a processor-controlled machine to decode a text line image wherein the first computing step of computing a maximum cumulative score includes using estimated matching scores to compute the maximum cumulative score;

each estimated matching score indicating an estimated measurement of a match between a character template and an image region in the text line image;

wherein the first and second computing steps, the comparing step and the third computing step are repeated in a plurality of iterations until a stopping condition is met;

each iteration producing an estimated best transcription; and

wherein the method further includes performing a re-scoring operation after each iteration;

the re-scoring operation computing an actual matching score for each image position indicating a character template included in the estimated best transcription;

the actual matching scores being available for computing maximum cumulative scores in subsequent iterations.

3. The method of claim 2 wherein the method for operating a processor-controlled machine to decode a text line image further includes the step of turning the switch mode off when the image position represents a location of a character template in an estimated best path output from a prior iteration for which an actual matching score was computed.

4. The method of claim 1 for operating a processor-controlled machine to decode a text line image wherein the at least predetermined number of consecutive image positions in the text line image is greater than a maximum set width of a character template.

5. The method of claim 1 for operating a processor-controlled machine to decode a text line image wherein

the text line image is represented as a stochastic finite state image network including a plurality of nodes and directed branches between nodes;

the stochastic finite state image network including a plurality of possible paths each indicating an ordered sequence of nodes and directed branches between nodes indicating a possible spatial arrangement of character templates in the text line image; and

producing the transcription of the text line image using the maximum cumulative scores includes producing a path of nodes and directed branches between nodes through the stochastic finite state image network using the maximum cumulative scores.

6. The method of claim 1 for operating a processor-controlled machine to decode a text line image wherein the first computing step of computing a maximum cumulative score uses a dynamic programming operation to compute the maximum cumulative score;

and wherein the third computing step of computing the maximum cumulative score by adding the score change value computes the maximum cumulative score without using the dynamic programming operation.

7. The method of claim 1 for operating a processor-controlled machine to decode a text line image wherein the text line image is represented as a graph data structure;

and wherein a total number of consecutive image positions in the text line image for which the skip mode switch is on forms a cut set in the graph data structure.

8. A method for operating a processor-controlled machine to decode a text line image;

the method comprising;

representing the text line image as a stochastic finite state image network including a plurality of nodes and directed branches between nodes;

each directed branch having associated therewith a plurality of attributes including a character template and a character label identifying a character symbol represented by the character template;

the stochastic finite state image network including a plurality of possible paths each indicating an ordered sequence of nodes and directed branches between nodes indicating a possible spatial arrangement of character templates in the text line image;

each character template indicating a character label;

a plurality of ordered character labels formed by a path indicating a transcription of the text line image;

assigning one of a plurality of estimated template-image matching scores to each directed branch in the stochastic finite state image network;

each estimated template-image matching score indicating an estimated measurement of a match between an image region of the input text line image and the character template associated with the directed branch;

performing a repeated sequence of a decoding operation followed by a re-scoring operation until a stopping condition is met;

the decoding operation computing maximum cumulative path scores at image positions in the text line image using the plurality of estimated matching scores;

the decoding operation producing a best path of directed branches and nodes through the stochastic finite state image network using the maximum cumulative path scores; and

producing the transcription of the input text line image using the character labels associated with the directed branches of the best path;

the re-scoring operation computing, after every repetition of the decoding operation, actual template-image matching scores between character templates and image regions identified by nodes included in the best path and re-labeling directed branches of the stochastic finite state image network incoming to nodes included in the best path with the actual matching scores;

the decoding operation computing the maximum cumulative path scores at selected image positions in the text line image by adding a score change value to a prior maximum cumulative path score when the score change value between maximum cumulative path scores computed during production of a prior best path and maximum cumulative path scores computed during production of a current best path using the actual matching scores produced by the re-scoring operation is substantially constant for at least a predetermined number of consecutive image positions in the text line image.

9. The method of claim 8 for operating a processor-controlled machine to decode a text line image wherein the re-scoring operation further includes, for each node included in the best path, computing a plurality of actual template-image matching scores between character templates and image regions for a plurality of image positions surrounding the node;

and

wherein re-labeling the directed branch incoming to the node with the actual matching score includes re-labeling the directed branch incoming to the node with a largest actual matching score selected from the plurality of actual template-image matching scores.

10. The method of claim 8 for operating a processor-controlled machine to decode a text line image wherein the stochastic finite state image network representing the text line image is implemented as a decoding trellis data structure.

11. The method of claim 8 for operating a processor-controlled machine to decode a text line image wherein the decoding operation uses a dynamic programming operation for computing the maximum cumulative path scores at all image positions except for the selected image positions in the text line image when the decoding operation computes the maximum cumulative path scores without using the dynamic programming operation by adding the score change value to the prior maximum cumulative path score.

12. The method of claim 8 for operating a processor-controlled machine to decode a text line image wherein each of the plurality of estimated template-image matching scores is an upper bound measurement of a match between an image region of the text line image and the character template associated with the directed branch.

13. The method of claim 8 for operating a processor-controlled machine to decode a text line image wherein the at least predetermined number of consecutive image positions in the text line image is greater than a maximum set width of a character template.

14. In an image recognition computer-implemented method for analyzing a bitmap text line image into a combination of character symbol templates selected from a library of templates on the basis of at least one complete path computed through a decoding trellis of a Markov source, the improvement comprising:

assigning an estimated match score to each transition in the decoding trellis according to a character template associated with the transition;

the estimated match score for a character template being a substitute for an actual match score;

the actual match score indicating a measurement of a match between an image region of the text line image and the character template associated with the transition;

performing a repeated sequence of a decoding operation followed by a re-scoring operation until a stopping condition is met;

the decoding operation producing a complete path of nodes and transitions through the decoding trellis using the estimated match scores assigned to the transitions;

the re-scoring operation assigning an actual match score to each transition in the complete path having an estimated match score;

the actual match scores being available in the decoding trellis to subsequent iterations of the decoding operation;

the decoding operation producing the complete path by computing maximum cumulative path scores at every image position in the text line image;

when a score change value between maximum cumulative path scores computed during production of a prior best path and maximum cumulative path scores computed during production of a current best path using the actual matching scores available in the decoding trellis is substantially constant for at least a predetermined number of consecutive image positions in the text line image, the decoding operation computing a maximum cumulative path score for an image position in the text line image by adding the score change value to a prior maximum cumulative path score while the score change value remains substantially constant.

15. An article of manufacture for use in a machine that includes a memory device for storing data;

a storage medium access device for accessing a medium that stores data; and

a processor connected for accessing the data stored in the memory device and for receiving data from the storage medium access device;

the article comprising;

a data storage medium that can be accessed by the storage medium access device when the article is used in the machine; and

data stored in the data storage medium so that the storage medium access device can provide the stored data to the processor when the article is used in the machine;

the stored data comprising instruction data indicating instructions the processor can execute;

the processor, in executing the instructions, while a skip mode switch is off, for each image position in the text line image,

performing a first computing step of computing a maximum cumulative score indicating a measurement of a match between a sequence of character templates and an image region in the text line image from a starting location of the text line image to the image position;

performing a second computing step of computing a score change value between the maximum cumulative score and a prior maximum cumulative score computed at the image position; and

comparing the score change value to a prior score change value and turning the skip mode switch on when the score change value is substantially constant for at least a predetermined number of consecutive image positions in the text line image;

the processor, further in executing the instructions, while the skip mode switch is on, for each image position in the text line image, performing a third computing step computing the maximum cumulative score by adding the score change value to a prior maximum cumulative score computed at the image position; and

the processor, still further in executing the instructions, producing a transcription of the text line image using the maximum cumulative scores.

16. The article of manufacture of claim 15 wherein the processor, in executing the instructions, uses a dynamic programming operation to compute the maximum cumulative score when performing the first computing step of computing a maximum cumulative score;

and wherein the processor, in executing the instructions, computes the maximum cumulative score by adding the score change value to the prior maximum cumulative score without using the dynamic programming operation when performing the third computing step of computing the maximum cumulative score.