Document image decoding using modified branch-and-bound methods

• US 5,526,444 A
• Filed: 05/07/1993
• Issued: 06/11/1996
• Est. Priority Date: 12/10/1991
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chou, Philip A., Kopec, Gary E., Kam, Anthony C.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): ANDERSON, DAVID
• Application Number:
  US08/060,196
• Time in Patent Office: 1,131 Days
• Field of Search: 382/3, 382/13, 382/14, 382/15, 382/39, 382/56, 382/40, 382/232, 382/233, 382/228, 382/243, 382/229, 382/209, 381/41, 381/42, 381/43
• US Class Current: 382/233
• CPC Class Codes: G06F 18/00 Pattern recognition
• 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: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/148 Segmentation of character regions
• CPC Class Codes: G06V 30/19187 Graphical models, e.g. Bayesian networks or Markov models
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

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.

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).

2. The method of claim 1, wherein the Markov source model is first subjected to a transforming process to determine whether it could be converted into separable form, and if it can be converted into separable form the separable form of the source model is used.

3. The method of claim 1, in which the at least one complete path is found using a Viterbi algorithm.

4. The method of claim 1, in which at least one complete path is found using an iterated complete path algorithm comprising the steps of:

i) computing at least one score for a transition of the decoding trellis of the vertical model that corresponds to a horizontal model,

ii) finding a best path through the decoding trellis of the vertical model of the separable model using at least one computed score computed in step i,

iii) modifying at least one computed score computed in step i for a transition of the decoding trellis of the vertical model that corresponds to a horizontal model using the best path through the decoding trellis of the vertical model of the separable model,

iv) repeating step ii using the modified score and step iii until a stopping criterion is met.

5. The method of claim 4 in which, in step iii, modifying at least one score of a transition of the decoding trellis of the vertical model that corresponds to a horizontal model includes finding a best path through a decoding trellis for the horizontal model.

6. The method of claim 4 in which modifying at least one score of step iii involves using a Viterbi algorithm.

7. The method of claim 4 in which at least one score computed in step i is computed using a weighted sum of the counts of black pixels in at least one row of the image.

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.

9. The method of claim 8 in which the Markov source is first subjected to a transforming process to convert it into a separable form.