Image recognition method using finite state networks

• US 5,321,773 A
• Filed: 12/10/1991
• Issued: 06/14/1994
• 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.
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/805,700
• Time in Patent Office: 917 Days
• Field of Search: 382/30, 382/34, 382/56, 382/37, 382/36, 382/39, 382/14, 382/15, 395/10, 395/50, 395/63
• US Class Current: 382/209
• 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 recognition system, in particular for document image recognition, using an imaging model employing a 2-dimensional finite state automaton corresponding to a regular string grammar. This approach is not only less computationally intensive than previous grammar-based approaches to document image recognition, but also can handle a wider variety of image types. Features of the imaging model include a sidebearing model of glyph positioning, an image decoder based on linear scheduling theory for regular interative algorithms, the combining of overlapping image sub-regions, and a least-squares estimation procedure for measuring character parameters from character samples in the image.

Claims

1. For use in an image recognition system of noisy 2-d images, an imager based on an imaging model using stochastic finite state networks, said imager comprising:

means for inputting an object to be imaged;

means for constructing a bitmap image of the object by combining symbol templates selected from a library of templates on the basis of paths determined by a stochastic finite state network.

2. The imager of claim 1, wherein the finite state network comprises branches having a set of attributes including a label and a multidimensional displacement on the bitmap.

3. The imager of claim 2, wherein the symbol templates use a sidebearing model of symbol shape description and positioning.

4. In an image synthesis method, comprising the steps:

inputting an object to be imaged to an imager, inputting a stochastic finite state network for the class of objects to be imaged, providing a library of symbol templates, causing said imager to construct a bitmap image of the object by combining symbol templates selected from the library on the basis of paths determined by the stochastic finite state network.

5. The method of claim 4, wherein the symbol templates are derived from a sidebearing model of symbol description and positioning.

6. The method of claim 5, wherein the sidebearing model allows overlapping bounding boxes but not overlapping symbols.

7. The method of claim 4, wherein the symbol templates are derived from images containing samples of the symbols by estimating the font metrics using an estimation procedure.

8. The method of claim 7, wherein the estimation procedure is a least-squares procedure.

9. For use in an image recognition system, a decoder for reconstructing an object used to make a noisy 2-d bitmap image, said decoder including a library of symbol templates substantially corresponding to the symbols present in the object and a stochastic finite state network for parsing the bitmap image to reconstruct the object by combining symbol templates selected from the library of templates on the basis of paths determined by the stochastic finite state network.

10. The decoder of claim 9, wherein the finite state network comprises branches having a set of attributes including a label, an image displacement, and a node transition probability.

11. The decoder of claim 9, wherein the decoder further comprises computation means for doing computations and a scheduler for ordering the computations for determining the most likely path through the network.

12. The decoder of claim 11, wherein the computations include maintaining a score of matches of an image symbol to the templates in the library.

13. The decoder of claim 11, wherein the scheduler is a row-major linear scheduler.

14. The decoder of claim 9, wherein the network comprises a Markov source which each transition is labelled with a symbol template and a displacement and the symbol templates are based on a sidebearing model of the symbol.

15. In an image recognition method, comprising the steps:

inputting to a decoder a noisy 2-d bitmap image to be reconstructed, inputting a stochastic finite state network for the class of objects represented by the image, providing a library of symbol templates substantially corresponding to object symbols of the image, causing said decoder to reconstruct the object by combining symbol templates selected from the library on the basis of paths determined by the stochastic finite state network.

16. The method of claim 15, wherein the symbol templates are derived from a sidebearing model of symbol description and positioning.

17. The method of claim 16, wherein the sidebearing model allows overlapping bounding boxes but not overlapping symbols.

18. The method of claim 15, wherein the symbol templates are derived from images containing samples of the symbols by estimating the font metrics using an estimation procedure.

19. The method of claim 18, wherein the estimation procedure is a least squares procedure.

20. In a noisy 2-d image recognition method comprising a stochastic finite state model of image generation for generating from a document comprising a plurality of characters a binary image from which the document can be intelligently reconstructed, the steps of:

(a) determining glyph positioning in the bitmap by determining the sidebearing attributes of the glyph,

(b) producing character templates representing each glyph positioned as determined in step (a),

(c) parsing the binary image using a selection of the templates produced by step (b) following the paths of a stochastic finite state network to reconstruct the document.

21. In an image recognition method comprising a finite state model of image generation for generating from a document comprising a plurality of characters a binary image from which the document can be intelligently reconstructed, the steps of:

(a) establishing character models from character samples used in the document by estimating the font metrics of each character using a least-squares procedure,

(b) producing a template of each document character and using same and a Markov source to construct the image.

22. The method of claim 21, further comprising reconstructing the document from the image using a stochastic finite state automaton in which finite states of the model are based on the probability that the document character resembles one of the character models established in step (a).

23. An image recognition system comprising:

an imager based on an imaging model comprising finite state networks and means for inputting an object to be imaged, said imager comprising means for constructing a bitmap image of the object by combining symbol templates selected from a library of templates on the basis of paths determined by a finite state network; and

a decoder for reconstructing the object used to make a bitmap image, said decoder including a library of symbol templates substantially corresponding to the symbols present in the object and a finite state network for parsing the bitmap image to reconstruct the object by combining symbol templates selected from the library of templates on the basis of paths determined by the finite state network.

24. A text-like image recognition method for analyzing a bitmap image, comprising:

(a) forming a decoding trellis comprising a stochastic finite state network based on Markov source models and Viterbi decoding, said source models having transitions and nodes and associated with each transition are a template, a transition probability, a message, and a 2-dimensional displacement,

(b) providing a library of symbol templates each representing a possible symbol at points of the image plane, each point of the image plane being represented in the decoding trellis by nodes and transitions into each node,

(c) finding the most likely path through said decoding trellis by said Viterbi decoding comprising executing a 2-dimensional Viterbi algorithm in which the likelihood of an individual transition of a path comprises the transition probability of the transition and the likelihood that the symbol template from the library associated with the transition corresponds to the region of the image in the vicinity of said image point,

(d) combining the symbol templates and messages associated with the transitions of the said most likely path.

25. An image recognition process for reconstructing from a bitmap image a text-like document, comprising:

(a) forming an image network based on a hidden markov source imaging model using stochastic finite state networks, said image network having a set of nodes interconnected by directed transitions and with a start state and a final state and with each transition associated with attributes comprising a character label, an image template including a 2-dimensional displacement and a transition probability,

(b) synthesizing an output image representing the bitmap image by traversing a path through the image network and at each transition copying into the output the template attribute associated with that transition where the transitions of the path are selected on the basis of a maximum score computed by iterating over the transitions into each node, the maximum score indicating the most likely path into the node.

26. The method of claim 25, wherein the source imaging model is a sidebearing model of character shape description and spacing.