Image analysis – Pattern recognition – Classification
Reexamination Certificate
2000-05-12
2004-01-13
Chang, Jon (Department: 2623)
Image analysis
Pattern recognition
Classification
C382S228000, C382S229000
Reexamination Certificate
active
06678415
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to image decoding and image recognition techniques, and in particular to such techniques using stochastic finite state networks such as Markov sources. In particular, the present invention provides a technique for efficiently integrating a language model into a stochastic finite state network representation of a text line image, for use in text line image decoding.
Stochastic grammars have been applied to document image recognition problems and to text recognition in particular. See, for example, the work of Bose and Kuo, identified in reference [1] which uses hidden Markov models (HMMs) for word or text line recognition. Bracketed numerals identify referenced publications listed in the Appendix of Referenced Documents. See also U.S. Pat. No. 5,020,112, issued to P. A. Chou and entitled “Image Recognition Using Two-Dimensional Stochastic Grammars.”
U.S. Pat. No. 5,321,773 (hereafter the '773 DID patent), issued to Kopec and Chou, discloses a document recognition technique known as Document Image Decoding (hereafter, DID) that is based on classical communication theory. This work is further discussed in references [2], [3] and [3]. The DID model
800
, illustrated in
FIG. 14
, includes a stochastic message source
810
, an imager
811
, a channel
812
and a decoder
813
. The stochastic message source
810
selects a finite string M from a set of candidate strings according to a prior probability distribution. The imager
811
converts the message into an ideal binary image Q. The channel
812
maps the ideal image into an observed image Z by introducing distortions due to printing and scanning, such as skew, blur and additive noise. Finally, the decoder
813
receives observed image Z and produces an estimate {circumflex over (M)} of the original message according to a maximum a posteriori (MAP) decision criterion. Note that in the context of DID, the estimate {circumflex over (M)} of the original message is often referred to as the transcription of observed image Z.
The structure of the message source and imager is captured formally by combining their functions into a single composite image source
815
, as shown by the dotted lines in FIG.
14
. Image source
815
models image generation using a Markov source. A Markov source is a stochastic finite-state automaton that describes the spatial layout and image components that occur in a particular class of document images as a regular grammar, representing these spatial layout and image components as a finite state network. A general Markov source model
820
is depicted in FIG.
15
and comprises a finite state network made up of a set of nodes and a set of directed transitions into each node. There are two distinguished nodes
822
and
824
that indicate initial and final states, respectively. A directed transition t between any two predecessor (L
t
) and successor (R
t
) states in the network of
FIG. 15
has associated with it a 4-tuple of attributes
826
comprising a character template, Q, a label or message string, m, a transitional probability, &agr;, and a two-dimensional integer vector displacement, &Dgr;. The displacement indicates a horizontal distance that is the set width of the template. The set width of a template specifies the horizontal (x-direction) distance on the text line that the template associated with this transition occupies in the image.
Decoding a document image using the DID system involves the search for the path through the finite state network representing the observed image document that is the most likely path that would have produced the observed image. The '773 DID patent discloses that decoding involves finding the best (MAP) path through a three-dimensional (3D) decoding trellis data structure indexed by the nodes of the model and the coordinates of the image plane, starting with the initial state and proceeding to the final state. Decoding is accomplished by a dynamic programming operation, typically implemented as a Viterbi algorithm. The dynamic programming operation involves computing the probability that the template of a transition corresponds to a region of the image to be decoded in the vicinity of the image point. This template-image probability is represented by a template-image matching score that indicates a measurement of the match between a particular template and the image region at the image point. Branches in the decoding trellis are labeled with the matching scores. A general description of the implementation of the Viterbi algorithm in the context of Document Image Decoding is omitted here and is provided in the discussion of an implementation of the present invention in the Detailed Description below.
U.S. Pat. No. 5,526,444 (hereafter, the '444 ICP patent) issued to Kopec, Kam and Chou and entitled “Document Image Decoding Using Modified Branch-And-Bound Methods,” discloses several techniques for improving the computational efficiency of decoding using the DID system. The '444 ICP patent disclosed the use of a class of Markov source models called separable Markov models. When a 2D page layout is defined as a separable Markov source model, it may be factored into a product of 1 D models that represent horizontal and vertical structure, respectively. The '444 ICP patent further discloses that decoding with a separable model involves finding the best path through the 2D decoding trellis defined by the nodes of the top-level model, some of which are position-constrained, and the vertical dimension of the image. The computational effect of a position constraint is to restrict the decoding lattice for a node to a subset of the image plane, providing significant computational savings when used with standard Viterbi decoding.
The '444 ICP patent further discloses the use of a recursive Markov source. A recursive source is a collection of named sub-sources each of which is similar to a constrained Markov source except that it may include an additional type of transition. A recursive transition is labeled with a transition probability and the name of one of the Markov sub-sources. The interpretation of a recursive transition is that it represents a copy of the named sub-source. Thus, some of the transitions of the top-level vertical model are labeled with horizontal models. One aspect of each of the horizontal models is that every complete path through the model starts at a fixed horizontal position and ends at a fixed horizontal position, effectively reducing decoding to a one-dimensional search for the best path. A second aspect is that the vertical displacement of every complete path in the model is a constant that is independent of the vertical starting position of the path. Thus, the horizontal models describe areas of the image plane that are text lines, and the top-level vertical model with its nodes that are constrained by position defines which rows of pixels in the 2D image are to be considered as potential text lines. The match score for each branch is computed by running the horizontal model (i.e., performing the Viterbi procedure) along the appropriate row of the image. The overall decoding time for a separable model is dominated by the time required to run the horizontal models, that is, to decode individual text lines.
In conjunction with the use of separable models, the '444 ICP patent also discloses a heuristic algorithm called the Iterated Complete Path (hereafter, ICP) algorithm that fits into the framework of the Viterbi decoding procedure utilized by DID but improves on that procedure by focusing on a way to reduce the time required to decode each of the horizontal models, or lines of text. The ICP algorithm disclosed in the '444 ICP patent is an informed best-first search algorithm that is similar to heuristic search and optimization techniques such as branch-and-bound and A* algorithms. During decoding, ICP causes the running of a horizontal model (i.e., computes the actual template-image matching scores) f
Bloomberg Dan S.
Greene Daniel H.
Popat Ashok C.
Chang Jon
Le Brian
McBain Nola M.
Xerox Corporation
LandOfFree
Document image decoding using an integrated stochastic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Document image decoding using an integrated stochastic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Document image decoding using an integrated stochastic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3214719