Xerox Corporation

Daniel P Huttenlocher

Todd A Cass

William James Rucklidge

Peter C Wayner

Michael J Hopcroft

Ronald M Kaplan

M Margaret Withgott

Per-Kristian G Halvorsen

John Seely Brown

Dan S Bloomberg

Steven C Bagley

Eric W Jaquith

Daniel Gureasko Bobrow

Ramana B Rao

William M Newman

Martin Kay

Douglass R Cutting

Ramana R Rao

Pedro Felzenswalb

A processor is provided with a first set of digital information that includes a first structured representation of a document. From the first set of digital information, the processor produces a second set of digital information that includes a second structured representation of the document. The second structured representation is a lossless representation and includes a set of tokens and a set of positions. At least one token in the plurality of tokens has an associated semantic label which may be a character code associated with various font types in the second structured representation of the document. The semantic label may be obtained and stored in the second structured representation of the document by a computer program. The first and second representations may be resolution dependent structured representations and have, respectively, first and second characteristic resolutions. The first representation, but not the second, is provided in digital form to an untrusted recipient. A search for particular content of the second representation, including semantic labels, is requested by the recipient. A highlighted version of the first representation of the document is then provided to the recipient.

Relabelling of tokenized symbols in fontless structured document image representations

A technique that partially encrypts tokenized documents is disclosed. An electronic document image is generated from the document. A plurality of tokens are stored as a dictionary, wherein the tokens represent shapes contained in the document. A plurality of triples comprising a token identification (ID) and a corresponding position are generated from the document image, such that the token ID identifies a token from the dictionary that corresponds to a shape in the document image at the corresponding position. The token IDs are encrypted. The output representation for the secured document comprises encrypted token IDs, positions and a dictionary of tokens. Encoding techniques that reduce the size of the secured document are also disclosed. A trusted image output terminal, for use in document reconstruction, includes a single integrated circuit that performs the decrypting function and the page rendering function to significantly reduce the ability to capture the electronic document in the clear.

Methods and apparatus for partial encryption of tokenized documents

A processor measures skew of lines in an image by obtaining a first, coarse approximation to skew direction and then using the first approximation to obtain a second, fine approximation that is more precise than the first. A third, even more precise approximation can be obtained using the second approximation, and further successive approximations can be similarly obtained. In an image of text, the first approximation can be obtained by finding the direction in which characters are closest together, since intercharacter distances are typically smaller than interline distances. This direction can be determined by measuring distances from selected pixels at edges of connected components across white pixels to edges of other connected components. The measured distances in each direction can be combined to obtain a central value for the direction, such as an average. The central values form a profile indicating central value as a function of direction. The minima separated by 180&deg; within the profile indicate the direction of intercharacter spacing, which provides a first approximation of the skew direction. Alternatively, the first approximation can be obtained by finding a direction that has the largest variance in black pixels per line, because the lines in the direction of skew either have many black pixels due to characters in a line or few black pixels due to spaces between lines. The second approximation can then be obtained by determining which one of a number of directions close to the first approximation has the largest variance in black pixels per line. The range of directions used to obtain the second approximation can be based on the angle separating directions used in obtaining the first approximation.

Coarse and fine skew measurement

A method for image processing including segmenting document images into text and continuous tone regions is provided. The method uses a token shape comparison and resultant data (e.g. shape recurrence) to determine which high-contrast regions of the image correspond to text or other symbols. The identified text is then separated from the image and processing ensues.

Method and apparatus for image processing employing image segmentation using tokenization

Relabeling of tokenized symbols in fontless structured document image representations

A method for determining the boundaries of a symbol or word string within an image, including the steps of determining page orientation, isolating symbol strings from adjacent symbol strings, establishing a set of boundaries or references with respect to which measurements about, or further processing of, the symbol string may be made.

Method for determining boundaries of words in text

A method in which first and second representations of a document are provided, for example, by being made available on one or more server computers connected to a computer network, such as the Internet or a corporate intranet. The first and second representations are resolution-dependent structured representations and have, respectively, first and second characteristic resolutions, the second resolution being greater than the first. The first representation, but not the second, is provided in digital form to an untrusted recipient. For example, the first representation can be transmitted through the network from the server on which the first representation is available to a client computer connected to the network. The second representation is converted to a third representation of the document, the third representation being a representation in a human-readable, nondigital form. For example, the second representation can be transmitted through the network in a secure manner to a trusted printing facility connected to the network. The trusted facility can then produce the third representation, for example by printing a hardcopy representation of the document. Finally, the third representation, but not the second, is provided to the untrusted recipient, for example, by physically transferring the third representation to the untrusted recipient.

Using fontless structured document image representations to render

A processor is provided with a first set of digital information that includes a first, resolution-independent structured representation of a document. This first representation is one from which various image collections (e.g., sets of page images) can be obtained, each such image in each such collection having a characteristic resolution. From the first set of digital information, the processor produces a second set of digital information that includes a second, resolution-dependent structured representation of the document. The second structured representation is a lossless representation of a particular one of the image collections obtainable from the first structured representation, and it includes a set of tokens and a set of positions. The second set of digital information is produced by extracting the tokens from the first structured representation, and by determining the positions from the first structured representation. Each extracted token includes pixel data representing a subimage of the particular image collection. Each position is a position of a token subimage in the particular image collection. At least one of the token subimages contains multiple pixels and occurs at more than one position in the image collection. The second set of digital information thus produced can be made available for further use (e.g., distribution, transmission, storage, subsequent reconversion into page images). Applications of the invention include high-speed printing and Internet (World Wide Web) document display.

Fontless structured document image representations for efficient

A method and apparatus for comparing symbols extracted from binary images of text for classifying into equivalence classes. The present invention uses a Hausdorff-like method for comparing symbols for similarity. When a symbol contained in a bitmap A is compared to a symbol contained in a bitmap B, it is determined whether or not the symbol in bitmap B fits within a tolerance into a dilated representation of the symbol in bitmap A with no excessive density of errors and whether the symbol in bitmap A fits within a tolerance into a dilated representation of the symbol in bitmap B with no excessive density of errors. If both tests are passed, an error density check is performed to determine a match. The dilated representation of the bitmap accounts for various quantization errors that may occur along the boundaries of a symbol defined in the respective bitmaps. The dilation utilized preserves the topology of the symbol. The topology preserving dilation is one where symbols are 'thickened' yet the local topology (or connectedness) of the symbol is not changed. Such a dilation is performed by applying a set of local rules to 'off' pixels that are adjacent to 'on' pixels. Quantization effects are also accounted for through the use of a non-linear error allowance. The non-linear error allowance implements the idea that small symbols provide for little or no error, whereas large symbols provide for a proportionately larger amount of error.

Method and apparatus for comparing symbols extracted from binary images

A method and apparatus for applying morphological image criteria that identify image units in an undecoded document image having significant information content, and for retrieving related data that supplements the document either from elsewhere within the document or a source external to the document. The retrieved data can result from character code recognition or template matching of the identified significant image units, or the retrieved data can result directly from an analysis of the morphological image characteristics of the identified significant image units. A reading machine can allow a user to browse and select documents or segments thereof, and to obtain interactive retrieval of documents and supplemental data.

Method and apparatus for supplementing significant portions of a

A method for determining the relative equivalency or match between two or more character strings represented in an array of image data, including the steps of determining page orientation, isolating character strings from adjacent character strings, and establishing a set of boundaries or reference lines about the character strings. Subsequently, the boundaries are used to represent the character string images as word shape contours or signals which are generated from the imaginal data within the boundaries. The word shape contours are then compared using one of the described comparison methods to determine the relative equivalency or similarity of the contours.

Method for comparing word shapes

A method for reducing an image of a character or word string to one or more one dimensional signals, including the steps of determining page orientation, isolating character strings from adjacent character strings, establishing a set of references with respect to which measurements about the character string may be made, and deriving a plurality of measurements with respect to the references in terms of a single variable signal, from which information about the symbol string may be derived.

Method of deriving wordshapes for subsequent comparison

A method for reducing an image of a character or word string to one or more one dimensional signals, including the steps of determining page orientation, isolating character strings from adjacent character strings, establishing a set of references with respect to which measurements about the character string may be made, and deriving a plurality of measurements with respect to the references in terms of one dimensional signal, amenable to identification processing techniques.

Optical word recognition by examination of word shape

A method for comparing two image sections consisting of a plurality of image signals, or pixels, where each image section represents a token (e.g., character, symbol, glyph, string of components, or similar units of semantic understanding), in order to identify when similar tokens are present within the image sections. The invention further operates without the need for individually detecting and/or identifying the components making up the tokens. In one embodiment, the method relies upon the detection of connected components within words to first isolate individual word tokens and then applies a two stage process where dilated images of the tokens are compared with model representations of the tokens to determine the relative similarity therebetween.

Method for comparing image sections to determine similarity therebetween

A processor measures size or spacing of connected components for an image of text by obtaining a distribution of measurements of distances between edges of connected components. The distances are measured along lines extending in a measuring direction, such as a direction parallel or perpendicular to lines of text, which can be determined based on a measurement of skew. The distance measurements then can be used to produce a distribution of measurements as a function of distance, such as a histogram. Sufficient distances are measured that the histogram or other distribution data indicates a measure of size or spacing of connected components for the image, such as a stroke width, a maximum character width or height, or a spacing between characters, words, or lines. To measure sizes, distance can be measured across pixels within connected components. To measure spacings, distance can be measured across pixels that are not within connected components. Measurements in a direction parallel to lines of text can indicate intercharacter spacing, interword spacing, vertical stroke width, and maximum character width. Measurements in a direction perpendicular to lines of text can indicate interline spacing, horizontal stroke width, and maximum character height. A machine could store an input image in memory, obtain data indicating size or spacing of connected components, modify the stored data according to the sizes or spacings indicated, and provide an output image based on the modification. The data indicating size or spacing could be used in segmentation and character recognition.

Growing community of inventors

Ithaca, NY, United States of America

Daniel P Huttenlocher