Image recognition method using finite state networks

Claim 2

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.

Claim 3

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.

Claim 4

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

Claim 5

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.

Claim 6

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.

Claim 7

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

Claim 8

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

Claim 9

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.

Claim 10

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

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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

Claim 16

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

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

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

Claim 21

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

Claim 22

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.

Claim 23

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

Claim 24

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.

Claim 25

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.

Claim 26

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.

Claim 27

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.

Claim 28

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

Claim 29

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.

Claim 30

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.

Claim 31

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.

Claim 32

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.

Claim 33

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.

Claim 34

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.

Claim 35

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