International Business Machines Corporation

Other

William B Pennebaker

Joan LaVerne Mitchell

Keith S Pennington

Cesar Augusto Gonzales

Karen L Anderson

Michael Philip Goldowsky

Gerald Goertzel

Jorma J Rissanen

Dimitris Anastassiou

Ephraim Feig

Frederick Cole Mintzer

Glen G Langdon, Jr

Han C Wang

Frederick Hochberg

Alfred J Landon

Jan P Hoekstra

A system and method involving a statistical conditioning technique that improves the coding efficiency in compression systems which have unstable statistical properties by conditioning the probability estimate for a given model context on prior decisions for that context thus enlarging the conditioning decision set. Instead of extending the model context by increasing the range of prior decisions in the pixel neighborhood, each model context is expanded into a set of two contexts which are the actual coding contexts. For a given probability estimation model context, the selection of a coding context index is done on the basis of the previous coding decision (1 or 0) for that model context. Thus, if a model context is assigned an index A, the coding context would be assigned an index 2*A +D(A)', where D(A)' is the previous (immediately preceding) binary decision for model context A; the decision of which coding context to use turns on whether the model context was used most recently for coding a 1 or a 0. More generally, each model context index A is expanded into a set of 2**N coding context indices, where N is the number of previous decisions for model context index A used in the conditioning of, for example, an arithmetic coding decision. The addressing of the context expansion can be done in any way which expands the total number of contexts by a factor of 2**N. The index for a case where the expansion is by one decision bit may be 2*A+D(A)', whereas in the case where the expansion is by two decision bits the index may be 4*A+2*D(A)'+D(A)'.

Stabilization of probability estimates by conditioning on prior

A technique for use in, illustratively, a transform coder for imparting robustness against burst (or similar) errors to data patterns, such as illustratively two-dimensional image data, that exhibit local redundancy. Robustness is provided, in the case of images, by passing localized (blocked) image data, i.e. either pixel values or transformed, illustratively discrete cosine transform (DCT), image coefficient values therefor, through a global block transform, such as a global block Hadamard transform, prior to compression coding in order to produce 'holographic-like' compressed data for subsequent transmission and/or storage. Specifically, globally transforming an image in this fashion effectively spreads (diffuses) the image data in each block of pixels in that image or in the transform coefficients therefor in a regularly ordered pre-defined global manner throughout the entire image to create what is, in effect, intentionally 'smeared' image data. By subjecting the 'smeared' image data upon de-compression to an inverse global block transformation, such as an inverse global block Hadamard transformation, then, even if a portion of the 'smeared' data for an image is obliterated during transmission or playback, the entire image can still be advantageously reconstituted, though at a somewhat degraded quality, from the remaining 'smeared' data.

Technique for use in a transform coder for imparting robustness to

A system and method for masking adaptive quantization during compressed image data transmission by defining a scaling factor for the quantization tables of the multiple image components, wherein the scaling factor signals changes in quantization for successive blocks of the image data. The scaling factor is transmitted as a further component together with the image components to thereby signal adaptive quantization of the image data.

Adaptive quantization within the JPEG sequential mode

An apparatus for charging droplets of a volatile liquid and for directing the charged droplets against an oppositely-charged member. The apparatus comprises a source of a mist of uniform fine droplets of a volatile liquid and a droplet-charging zone associated with said source for applying a charge to the droplets in the mist. The droplet-charging zone comprises a source of ionized air ions for imparting the charge and a predetermined velocity to the droplets. A discharge conduit is provided having a discharge nozzle for directing the charged droplets against the surface of a member for attraction and deposit onto areas thereof charged to an opposite polarity. Preferably, the droplet-charging zone is associated with an air ionization zone comprising a source of air, a means for ionizing the air, and a means for directing the ionized air at a predetermined velocity into the droplet-charging zone to apply the charge to the droplets. Also, preferably the droplet-charging zone comprises oppositely-charged electrodes providing an alternating current therebetween for vibrating the air ions into contact with the droplets to assist the imparting of the charge of the air ions to the droplets.

Apparatus for formation and electrostatic deposition of charged droplets

The present invention relates to computer apparatus and methodology for adapting the value of a probability of the occurrence of a first of two binary symbols which includes (a) maintaining a count of the number k of occurrences of the first symbol; (b) maintaining a total count of the number n of occurrences of all symbols; (c) selecting confidence limits for the probability; and (d) when the probability is outside the confidence limits, effectuating a revision in the value of the probability directed toward restoring confidence in the probability value. The number of allowed probabilities is, optionally, less than the total number of possible probabilities given the probability precision. Moreover, an approximation is employed which limits the number of probabilities to which a current probability can be changed, thereby enabling the probability adaptation to be implemented as a deterministic finite state machine.

Probability adaptation for arithmetic coders

Methods for the coating of different closely-spaced areas of an electrode member to produce a color filter matrix thereon. A thin translucent layer of electroconductive composition, such as indium tin oxide (ITO), is applied to isolated areas of the electrode substrate, and selected ones of said areas are charged to one polarity while the other closely-spaced areas are charged to an opposite polarity. Color material is introduced as fine droplets in a volatile vehicle, charged to said opposite polarity, for selective attraction to said selected areas and repulsion from all other areas. The procedure is repeated with different color material droplets for deposition on others of said closely-spaced areas to produce a multi-colored matrix filter, such as on the lower pel electrode or on the upper pixel common electrode of a LCD device. Preferably the ITO layer is coated with a thin polymer layer and the color material is a diffusible dye which is heat-diffused thereinto.

Electrostatic deposition of LCD color filters

A system and method for maximizing data compression by optimizing model selection during coding of an input stream of data symbols, wherein at least two models are run and compared, and the model with the best coding performance for a given-size segment or block of compressed data is selected such that only its block is used in an output data stream. The best performance is determined by 1) respectively producing comparable-size blocks of compressed data from the input stream with the use of the two, or more, models and 2) selecting the model which compresses the most input data. In the preferred embodiment, respective strings of data are produced with each model from the symbol data and are coded with an adaptive arithmetic coder into the compressed data. Each block of compressed data is started by coding the decision to use the model currently being run and all models start with the arithmetic coder parameters established at the end of the preceding block. Only the compressed code stream of the best model is used in the output and that code stream has in it the overhead for selection of that model. Since the decision as to which model to run is made in the compressed data domain, i.e., the best model is chosen on the basis of which model coded the most input symbols for a given-size compressed block, rather than after coding a given number of input symbols, the model selection decision overhead scales with the compressed data. Successively selected compressed blocks are combined as an output code stream to produce an optimum output of compressed data, from input symbols, for storage or transmission.

Dynamic model selection during data compression

A system is described for reformatting halftone data for compression, wherein an original bilevel image is reformatted to produce another bilevel image that allows vertical correlations to be recognized by the compression technique, thus improving compressibility dramatically, with particular suitability for facsimile transmissions. In reformatting it is assumed that a selected halftone frequency H will satisfactorily describe an entire document, and each of successive sets of H consecutive lines are concatenated to form respective single lines. The thus reformatted lines have a clearer halftone periodicity offering greater correlation and permit more efficient coding by well-known standard bilevel compression algorithms (e.g., CCITT G3 (MR) or GF4 (MMR)). For an image with unknown pattern frequency, a technique for readily estimating the frequency for use in reformating the image is described.

Compression of binary halftones

Apparatus and method for adapting the estimated probability of either the less likely or more likely outcome (event) of a binary decision in a sequence of binary decisions involves the up-dating of the estimated probability in response to the renormalization of an augend A. The augend A changes value with each binary decision, the size of the change depending on which of the binary events has occurred as input. Re-normalization of A occurs when the A value becomes less than a prescribed minimum value AMIN. According to the invention, there may be differing contexts in which binary decisions may occur, each context having a corresponding estimated probability value which is up-dated with binary decisions in the respective context. Also according to the invention, there may be one or more possible next values for an estimated probability in response to a given binary decision event. The selection of one of multiple possible next values in response to a given binary decision event is preferably determined based on a renormalization correlation count.

Apparatus and method for compressing and de-compressing binary decision data by arithmetic coding and decoding wherein the estimated probability Qe of the less probable of the two decision events, or outcomes, adapts as decisions are successively encoded. To facilitate coding computations, an augend value A for the current number line interval is held to approximate one by renormalizing A whenever it becomes less than a prescribed minimum AMIN. When A is renormalized, the value of Qe is up-dated. The renormalization of A and up-dating of Qe are preferably based on a single-bit test. Also, each Qe value is preferably specified as a 12-bit value having the least significant bit set to 1 and having no more than four other bits set to 1. The number of Qe values in the 1/4 to 1/2 probability range is enhanced to improve coding efficiency. A decision coding parameter of preferably six bits indicates the sense of the more probable symbol (MPS) in one bit and identifies a corresponding Qe value with the remaining five bits. In addition to probability adaptation, the present invention discloses an allocation of bits in a code stream register in which preferably two spacer bits are inserted between a next byte portion (which contains a byte of data en route to a buffer) and a fractional portion which may be involved in further computation. With the two spacer bits, any code greater than or equal to Hex `CO` which follows a Hex `FF` byte is illegal for data and therefore provides for an escape from the code stream. The two spacer bits also reduce the number of stuff bits inserted to account for carry or borrow propagation. Encoding and decoding can be performed interchangeably by hardware or software which feature differing coding conventions.

Arithmetic coding encoder and decoder system

A data compression/de-compression system includes a first arithmetic coding encoder, characterized by a first set of encoding conventions, which encoder generates a code stream that points to an interval along a number line in response to decision event inputs. The code stream can be adjusted to point to the same interval as code streams generated by one or more other arithmetic coding encoders characterized by encoding conventions differing in some way from those in the first set. In a binary context, optimal hardware encoders increment or decrement the value of the code stream in response to each occurrence of a more probable decision event while optimal software so changes the code stream value for each occurrence of a less likely event. According to the invention, the code streams for optimal hardware encoders and optimal software encoders are made either identical or compatible to enable similar decoding for each. Identical or compatible code streams are obtained from encoders having different event sequence or symbol ordering along intervals on the number line. Moreover, various hardware and software decoders--with respective symbol ordering and other conventions--can be used in conjunction with encoders having respective conventions, wherein each decoder retrieves the same sequence of decisions for a code stream pointing to a given interval. In both encoding and decoding, the present invention overcomes finite precision problems of carry propagation and borrow propagation by handling data in bytes and bit stuffing at byte boundaries and by pre-borrowing as required.

Arithmetic coding data compression/de-compression by selectively

The method according to the present invention enlarges a binary digital image by a method comprising the steps of: storing the rows of the image as a plurality of run end representations, in which a row is represented as a sequence of values giving the white and black run ends; enlarging each row of the image along the horizontal axis by altering the value of each run end representation to achieve enlargement on the horizontal axis by a factor F1; enlarging the image along the vertical axis by interpolating rows between the lines of the partially enlarged image so as to produce enlargement along the vertical axis by a factor F2; storing the enlarged size image generated by the above steps in run end form. An image enlarged by the method of the present invention may be reduced by the simple technique of dividing the image into blocks of pixels and assigning one pixel in a reduced image for each block of pixels in the larger image. Each pixel in the reduced image may by set equal to a center pixel in each block.

Method for enlarging an image stored in run representation form

Digital data defining images are stored in a multiplane buffer. The buffer may store plural images by restricting data corresponding to an image or image portion to storage in less than half the bit planes of the buffer. An image is displayed by reading data from the buffer and selectively passing only a portion of the data read to a display. The data defining the images may be converted from facsimile (single bit per pixel) to gray scale format (multiple bits per pel) before being written to the buffer. The conversion relies on a table storing data definitive of the effect, on the image, of a facsimile transition (1/0 ot 0/1) as a function of the location of the transition. Conversion from facsimile to gray scale is effected by examining the facsimile data for data transmission and summing the effect of each of the transitions to convert a segment of facsimile data to gray scale data. A system is also disclosed for rapidly converting an image in run-end form to a reduced-resolution gray-tone image.

Soft copy display of facsimile images

In an image in which some pixels in some rows of an image have values associated therewith, apparatus and method of processing, for subsequent entropy coding or decoding, graylevel data for the remaining pixels in the image.

Growing community of inventors

Carmel, NY, United States of America

William B Pennebaker