Data compression

Details Data compression Data compression

1997-06-12

2001-02-13

Lee, Thomas D. (Department: 2624)

Image analysis

Image compression or coding

Adaptive coding

C358S426010, C341S107000

Reexamination Certificate

active

06188795

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to compression and decompression of binary image data using arithmetic encoding. An example of the image data is a binary mask representing an object shape.
PRIOR ART DISCUSSION
The paper “Arithmetic Coding” by J. Rissanen and G. Langdon in IBM Journal of Research and Development, Vol. 23, No. 2, March 1979 describes compression by arithmetic coding using a statistical model for a data source.
As far as the inventors are aware arithmetic coding has not been applied to moving binary images, and indeed there are problems associated with its use for static binary images.
The paper “Compression of Black-White Images with Arithmetic Coding”, IEEE Transactions on Communications, Vol. 29, No. 6, pp. 858-867, June 1981 describes what is now known as context-based arithmetic encoding (CAE) for compression of binary images. The method comprises a modelling part and a coding part. The modelling part comprised two parts. The first part of the model, called the neighbourhood template, defined, for a given binary sample X, those other samples in the image which were considered to have an influence on the value of X. The word “neighbourhood” was used because it is normally a local correlation which exists in binary images. The configuration of the binary samples in this template was represented by an N bit number, where N is the number of pixels in the template. This N bit number was termed the context, denoted C. The second part was the conditional statistical model or conditional probability density function (PDF). This was a function P(X/C) defining the probability of X=0 and X=1 conditional upon C(X) i.e. the context at sample X.
The encoding of a binary image involved firstly an initialisation of the arithmetic encoder. Secondly, each sample of the image was scanned and coded in raster order. The coding of a sample X involved the computation of C(X) based on a predefined template T. The value C(X) was used to access a PDF table containing a representation of P(X/C). The value of X and P(X/C) was used to drive an arithmetic encoder. When the final sample of the image was encoded the arithmetic encoder was terminated. The result was a compressed (arithmetic) code representing the whole binary image.
The decoding of the compressed arithmetic code involved an initialisation of the arithmetic decoder. Samples were then decoded in the same order as used at the encoder. Decoding of sample X required the computation of C(X) and subsequent access to P(X/C). The arithmetic decoder used P(X/C) and the next bits in the arithmetic code to ascertain the value of X. When the last pixel was decoded, the arithmetic decoder was terminated.
Since the compression efficiency is governed by the PDF, it is very important to use one which matches well with the data. Langdon and Rissanen experimented with fixed PDFs and adaptive PDFs. The fixed PDF was generated by analysing a set of typical images (training set) and averaging the statistics over the whole set. For encoding a given image, the PDF was not allowed to change from sample to sample. The problem with this approach was that compression efficiency varied depending on how close the source image was to the average. An image which was atypical of the initial training set would not be compressed efficiently.
To overcome this problem, an adaptive PDF model was employed. The adaptive PDF model used an update algorithm to allow it to keep in touch with the varying local statistics present in many binary images. As each sample value was encoded, the PDF model was changed according to some statistical criterion. At the decoder, the sample update algorithm was used as each sample was decoded. However, this adaptive approach imposes some limitations in terms of error resilience. This is due to the fact that the update algorithm must rely on samples which have already been coded/decoded. If, due to bitstream error, a given sample is decoded incorrectly, then the update algorithm can cause the decoder to desynchronise and the error can propagate unlimited through the remainder of the image resulting in a highly distorted decoded image. Therefore, compression efficiency is achieved through PDF adaptation at the grave expense of error resilience.
OBJECTS OF THE INVENTION
One object of the invention is to provide a method for efficient arithmetic encoding of static and moving binary images.
Another object is to minimise the chances of error propagation, with little effect on compression efficiency.
SUMMARY OF INVENTION
According to the invention, there is provided a method of encoding binary image data comprising the steps of:
receiving the image data;
determining for each sample a PDF table;
computing for each sample a context number according to a template;
selecting for each sample a PDF from the PDF table according to the context number;
an arithmetic encoder encoding each sample in turn according to the PDF and the sample value,
characterised in that,
the received image data is partitioned into discrete blocks, each block comprising a plurality of samples,
the arithmetic encoder is initialised at the start of each block;
the samples of each block are encoded using a fixed template to compute the context number, and a fixed PDF table; and
the arithmetic encoder is terminated at the end of each block.
Preferably, the context number is computed by assigning estimated values to samples of the template which are in neighbouring blocks.
In one embodiment, the estimation is performed using rules which are set for each template.
Preferably, the fixed template includes samples from a previous image in an image sequence for exploiting temporal correlations.
In a further embodiment, the template samples from the previous image are determined according to motion compensation.
Preferably, motion compensation is performed by block translation and preferably the block translation includes neighbouring samples.
In one embodiment the fixed template and PDF table are chosen from a set of template/PDF table pair models, at least one model exploiting temporal correlations and at least one other model exploiting spatial correlations only.
In another embodiment, each temporal model exploits both temporal and spatial correlations.
Preferably, the temporal model includes four spatially-correlating samples and five temporally-correlating samples.
In a further embodiment, the spatially-correlating samples include the previous sample in the same row and three samples of the previous row centralised above the sample.
Preferably, the temporally-correlating samples include a sample at a position corresponding to the current sample, and the four vertically and horizontally adjoining samples.
DETAILED DESCRIPTION OF THE INVENTION


REFERENCES:
patent: 5471207 (1995-11-01), Zandi et al.
patent: 5689589 (1997-11-01), Gormish et al.
patent: 0448802 (1991-10-01), None
patent: 0813168 (1997-12-01), None
Langdon, Jr. et al, “Compression of Black-White Images with Arithmetic Coding”, Jun. 1981 (IEEE Transactions on Comm., vol. Com-29, No. 6).
Rissanen et al, “Arithmetic Coding”, Mar. 1979 (IBM J. Res. Develop. vol. 23, No. 2).
Gonzales, “DCT Coding for Motion Video Storage Using . . .”, Signal Processing, vol. 2, Aug. 1990, pp. 145-154.
Weinberger et al, “Applications of Universal Context . . .”, IEEE Transactions, vol. 5, No. 4, Apr. 1, 1996, p. 582.
Tischer et al, “Context-Based Lossless Image Compression”, Computer Journal, vol. 36, No. 1, Jan. 1993, pp. 68-77.

Affiliated with

Also associated with

Rating

Data compression does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2593833