Document image decoding using modified branch-and-bound methods

In a text-like image recognition computer-implemented method for analyzing a bitmap image into a combination of symbol templates selected from a library of templates on the basis of paths determined from traversing a decoding trellis using Markov source models and Viterbi decoding, said decoding trellis comprising a first plurality of regions likely to contain the best path for traversing the decoding trellis, and a second plurality of regions of the decoding trellis not likely to contain the best path for traversing the decoding trellis, said Viterbi decoding comprising a 2-dimensional Viterbi algorithm to compute a set of likelihood functions at each point of the image plane, wherein each point of the image plane is represented in the decoding trellis by nodes and transitions into each node and Viterbi decoding comprises computing the likelihood of the most likely path into each node at each image plane point, the improvement comprising:

• (a) using as the Markov source model a separable model, said separable model being a 2-d model that can be expressed as a top-level 1-d vertical model plus a set of horizontal models that correspond to branches of the vertical model in which for each of the horizontal models, every complete path through the horizontal model starts at a fixed horizontal position and ends at a fixed horizontal position, and the vertical displacement of every complete path in the model is a constant that is independent of the vertical starting position of the path;
• (b) without full decoding, identifying said first plurality of regions of the decoding trellis likely to contain the best path,
• (c) performing full Viterbi decoding only in the first plurality of regions determined in step (b) to determine the best path through the decoding trellis,
• (d) producing an image or text string representing an image based on the combination of symbol templates derived from the best path determined in step (c).