Document image decoding using modified branch-and-bound methods
First Claim
1. 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).
5 Assignments
0 Petitions
Accused Products
Abstract
An image decoding and recognition system and method comprising a fast heuristic algorithm using hidden Markov models (HMM). The new search algorithm, called an "iterative complete path" (ICP) algorithm, patterned after well-known branch-and-bound (B&B) methods, significantly reduces the complexity and improves the speed of HMM image decoding without sacrificing the optimality of the straightforward procedure. An advantageous form of the heuristic functions which is useful in applying the ICP algorithm to text-like images is described. The ICP algorithm is directly applicable to the separable type of finite-state source models. Also disclosed is a technique for transforming more general source models into such a separable form.
-
Citations
9 Claims
-
1. 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). - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. 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 at least one complete path computed through a decoding trellis of a Markov source, 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) producing an image or text string representing an image based on the combination of symbol templates. - View Dependent Claims (9)
-
Specification