Other

Xerox Corporation

Thomas P Minka

Dan S Bloomberg

Ashok Chhabedia Popat

In a text recognition system that uses a stochastic finite state network to model a document image layout, the computational efficiency of text line decoding is improved. In a typical implementation, the dynamic programming operation that accomplishes decoding uses actual scores computed between two-dimensional (2D) bitmapped character template images and the (2D) bitmapped observed image. Scoring measures the degree of a match between a character template and the observed image. Computation of these actual scores is replaced with the simpler computation of column-based (i.e., one-dimensional) heuristic scores. Because the column-based heuristic scores can be shown to be a true upper bound on actual template-image scores, the heuristic scores are accurate enough to use in place of actual scoring during text line decoding. The heuristic scores essentially reduce the expensive two-dimensional computation of the actual template-image scores required by prior decoding methods to a simpler but accurate one-dimensional computation.

Document image decoding using text line column-based heuristic scoring

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.

Growing community of inventors

Cambridge, MA, United States of America

Thomas P Minka