Xerox Corporation

Gary E Kopec

Philip Andrew Chou

Leslie T Niles

Dan S Bloomberg

Steven C Bagley

Anthony C Kam

Dennis S Arnon

Jesse Hull

A two-dimensional (2D) image model models the layout structure of a class of document images as an image grammar and includes production rules having explicit layout parameters as data items that indicate information about the spatial relationships among image constituents occurring in images included in the class. The parameters are explicitly represented in the grammar rules in a manner that permits them to be automatically trained by a training operation that makes use of sample document images from the class of modeled documents. After each sample image is aligned with the 2D grammar, document-specific measurements about the spatial relationships between image constituents are taken from the image. Optimal values for the layout parameters are then computed from the measurement data collected from all samples. An illustrated implementation of the 2D image model takes the form of a stochastic context-free attribute grammar in which synthesized and inherited attributes and synthesis and inheritance functions are associated with each production rule in the grammar. The attributes indicate physical spatial locations of image constituents in the image, and a set of parameterized functions, in which the coefficients are the layout parameters, compute the attributes as a function of a characteristic of an image constituent of the production rule. The measurement data is taken from an annotated parse tree produced for each training image by the grammar. A trained grammar can then be used, for example, for document recognition and layout analysis operations on any document in the class of documents modeled by the grammar.

Automatic training of layout parameters in a 2D image model

A method for operating a machine to perform unsupervised training of a set of character templates uses as the source of training samples an image source of character images, called glyphs, that need not be manually or automatically segmented or isolated prior to training. A recognition operation performed on the image source of character images produces a labeled glyph position data structure that includes, for each glyph in the image source, a glyph image position in the image source associating an estimated image location of the glyph in the image source with a character label paired with the glyph image position that indicates the character in the character set being trained. The labeled glyph position data and the image source are then used to determine sample image regions in the image source; each sample image region is large enough to contain at least a single glyph but need not be restricted in size to only contain a single glyph. The template construction process using unsegmented samples is mathematically modeled as an optimization problem that optimizes a function that represents the set of character templates being trained as an ideal image to be reconstructed to match the input image. The method produces all of the character templates substantially contemporaneously by using a novel pixel scoring technique that implements an approximation of a maximum likelihood criterion subject to a constraint on the templates produced which holds that foreground pixels in adjacently positioned character images have substantially nonoverlapping foreground pixels. The character templates produced may be binary templates or arrays of probability values.

Unsupervised training of character templates using unsegmented samples

A method and system for automatically modifying an original transcription produced as the output of a recognition operation produces a second, modified transcription, such as, for example, automatically correcting an errorful transcription produced by an OCR operation. The invention uses information in an input text image of character images and in an original transcription associated with the input text image to modify aspects of a formal image source model that models as a grammar the spatial image structure of a set of text images. A recognition operation is then performed on the input text image using the modified formal image source model to produce a second, modified transcription. When the original transcription is errorful, the second transcription is a corrected transcription. Several aspects of the formal image source model may be modified; in particular, character templates to be used in the recognition operation are trained in the font of the glyphs occurring in the input text image. When errors in the original transcription are caused by matching glyphs against templates that are inadequately specified for the given input text image, the subsequently performed recognition operation on the text image using the trained, font-specific character templates produces a more accurate transcription.

Method and system for automatic transcription correction

A method for producing, or training, a set of character templates uses as the source of training samples an image source of character images, called glyphs, that are not previously segmented or isolated for training. Also used is a labeled glyph position data structure that includes, for each glyph in the image source, a glyph image position in the image source associating an image location of the glyph with a character label paired with the glyph image position that indicates the character in the character set being trained. The labeled glyph position data is used to identify a collection of glyph sample image regions in the image source for each character in the character set; each glyph sample image region is large enough to contain a glyph and typically contains adjacent glyphs for other characters. The invention mathematically characterizes the template construction problem using unsegmented samples as an optimization problem that optimizes a function that represents the set of character templates being trained as an ideal image to be reconstructed to match the input image. The method produces all of the character templates contemporaneously by using a novel pixel scoring technique that implements an approximation of a maximum likelihood criterion subject to a constraint on the templates produced which holds that foreground pixels in adjacently positioned character images have substantially nonoverlapping foreground pixels. The character templates produced may be binary templates or arrays of pixel color probability values, and may also have substantially disjoint supports, such that adjacently imaged templates have substantially no overlapping foreground pixels.

Method of producing character templates using unsegmented samples

A technique for automatically training a set of character templates using unsegmented training samples uses as input a two-dimensional (2D) image of characters, called glyphs, as the source of training samples, a transcription associated with the 2D image as a source of labels for the glyph samples, and an explicit, formal 2D image source model that models as a grammar the structural and functional features of a set of 2D images that may be used as the source of training data. The input transcription may be a literal transcription associated with the 2D input image, or it may be nonliteral, for example containing logical structure tags for document formatting, such as found in markup languages. The technique uses spatial positioning information about the 2D image modeled by the 2D image source model and uses labels in the transcription to determine labeled glyph positions in the 2D image that identify locations of glyph samples. The character templates are produced using the input 2D image and the labeled glyph positions without assigning pixels to glyph samples prior to training. In one implementation, the 2D image source model is a regular grammar having the form of a finite state transition network, and the transcription is also represented as a finite state network. The two networks are merged to produce a transcription-image network, which is used to decode the input 2D image to produce labeled glyph positions that identify training data samples in the 2D image. In one implementation of the template construction process, a pixel scoring technique is used to produce character templates contemporaneously from blocks of training data samples aligned at glyph positions.

Automatic training of character templates using a transcription and a

A method for establishing a relationship between a text image and a transcription associated with the text image uses conventional image processing techniques to identify one or more geometric attributes, or image parameters, of each of a sequence of regions of the text image. The transcription labels in the transcription are analyzed to determine a comparable set of parameters in transcription label sequence. A matching operation then matches the respective parameters of the two sequences to identify image regions that match with transcription regions. The result is an output data structure that minimally identifies image locations of interest to a subsequent operation that processes the text image. The output data structure may also pair each of the image locations of interest to a transcription location, in effect producing a set of labeled image locations. In one embodiment, the sequence of locations of words and their observed lengths in the text image are determined. The transcription is analyzed to identify words, and transcription word lengths are computed using an estimated image character width of glyphs in the text image. The sequence of observed image word lengths is then matched to the sequence of computed transcription word lengths using a dynamic programming algorithm that finds a best path through a two-dimensional lattice of nodes and transitions between nodes, where the transitions represent pairs of sequences of zero or more word lengths. An output data structure contains entries, each of which pairs a transcription word with a matching image word location.

Method for aligning a text image to a transcription of the image

A technique for automatically producing, or training, a set of bitmapped character templates defined according to the sidebearing model of character image positioning uses as input a text line image of unsegmented characters, called glyphs, as the source of training samples. The training process also uses a transcription associated with the text line image, and an explicit, grammar-based text line image source model that describes the structural and functional features of a set of possible text line images that may be used as the source of training samples. The transcription may be a literal transcription of the line image, or it may be nonliteral, for example containing logical structure tags for document formatting and layout, such as found in markup languages. Spatial positioning information modeled by the text line image source model and the labels in the transcription are used to determine labeled image positions identifying the location of glyph samples occurring in the input line image, and the character templates are produced using the labeled image positions. In another aspect of the technique, a set of character templates defined by any character template model, such as a segmentation-based model, is produced using the grammar-based text line image source model and specifically using a tag transcription containing logical structure tags for document formatting and layout. Both aspects of the training technique may represent the text line image source model and the transcription as finite state networks.

Automatic training of character templates using a text line image, a

Character level text editing is performed on an image without recognizing characters, by operating on a character-size array obtained from a two-dimensional array defining an image region. A processor, in response to a request for a text editing operation, accesses an edit data structure that includes the image region array and performs the operation. The character-size array is obtained by dividing the image region array when necessary. An image region array that includes more than one line is divided along interline spaces. An image region array that includes one line is divided along intercharacter spaces. Character-size arrays are divided out of larger arrays by finding connected component bounding boxes, and then determining from the bounding boxes whether the connected components are likely to form a character. If so, the connected components are used to obtain the character-size array and spatial data about position, size, and shape of the character. Smaller arrays and spatial data can replace a larger array in the edit data structure. Smaller arrays are obtained only as necessary to perform a requested text editing operation, and if the edit data structure is not otherwise modified, obtaining a smaller array does not necessitate redrawing of the display. In addition to character level editing, a text editing operation can be performed on a sequence of arrays, such as a word, line, or a sequence that begins on one line and ends on another. The spatial data can be used to position arrays after insertion or deletion, to advance a cursor through the text, and to justify a line of arrays. A character-size array can be assigned to a keyboard key, and the key may then be used to insert that array into the text or to request a search for other arrays matching that array.

Editing text in an image

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.

Document image decoding using modified branch-and-bound methods

A method and apparatus for identifying and correcting for document skew. Lines of a bitmap are scanned and a variance in the number of ON pixels as a function of skew angle is calculated. Skew of the original document occurs when the variance is a maximum.

Method and apparatus for identification of document skew

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.

Image recognition method using finite state networks

A method and apparatus for identifying and correcting for document skew. Lines of a bitmap are scanned and a variance in the number of ON pixels as a function of skew angle is calculated. Skew of the original document occurs when the variance is a maximum. Once the skew has been identified, the document is deskewed accordingly.

Growing community of inventors

Belmont, CA, United States of America

Gary E Kopec