Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2001-03-16
2004-10-05
Johns, Andrew W. (Department: 2621)
Image analysis
Image compression or coding
Lossless compression
C341S059000
Reexamination Certificate
active
06801668
ABSTRACT:
BACKGROUND OF THE PRESENT INVENTION
1. Field of the Invention
This invention relates to data compression and, in particular, compression of digital video.
2. Background of the Invention
As used herein, data compression refers to the process of representing data formatted as a sequence of symbols by fewer bits or bytes than needed by the original format. This can be achieved by using a variable length code (VLC) where frequently occurring symbols are represented by shorter code words than less frequent ones. In this way the average code word can be kept at minimum length and compression is achieved.
One way of finding an efficient VLC is to use the well-known Huffman coding algorithm, which matches code word lengths to the probability distribution of symbol occurrences. In the ideal case, the probability of a symbol should equal 2
−k
where k is the bit length of the code word. For k=1, 2, 3, . . . , this corresponds to probabilities 0.5, 0.25, 0.125, etc. The Huffman algorithm tries to match as many symbols as possible with the closest of these ideal probabilities. However, it is often the case that the original data symbols can be categorized into two different sets or types, where each type has a probability distribution of its own. By designing a separate code word table and accompanying VLC for each such symbol type, one can reduce the statistical variance. This gives a more efficient compression than using the overall distribution for all symbols disregarding their types.
Alternatively, one may use a single VLC—here referred to as a universal VLC (UVLC)—for all symbol types to be coded. Such a UVLC is typically constructed from an infinite pattern providing code words corresponding to a rather dense set of probabilities. The symbols are then coded by assigning the best code word for each symbol. If the symbols have an appropriate probability distribution, one may obtain the same performance as using a Huffman table.
When more than one VLC is used to compress data, it is of course essential that both the encoder and the decoder refer to the same VLC for each code word. This can be taken care of implicitly by following a certain standardized coding scheme. As an example, the ITU-T Recommendation H.263 for video coding uses different VLCs for different types of symbols. By correctly decoding the bitstream, the decoder is at any point aware of which type the following symbol will belong to, and hence which VLC to use.
Also for the case when a UVLC is used (instead of different VLCs) it is often possible to increase compression. This can be done by transforming symbols within types to obtain a better match to the probability distribution implied by the UVLC. One example is to merge symbols when the most probable symbol occurs too frequently. An example of this in video coding is the coding of macroblock modes where the skip mode occurs very frequently. By coding the modes of two adjacent macroblocks with one codeword, a better match to the VLC may be achieved.
However, a disadvantage of using a UVLC is the possible loss of coding efficiency as compared with using multiple VLCs. Among the features and advantages of the present invention is a way of reducing such loss of coding efficiency.
SUMMARY OF THE INVENTION
In accordance with the invention, and as illustrated in
FIG. 1
, a method of compressing data contained in variable length or universal variable length code words to be carried in a digital bitstream is provided. Starting from a first set of code words, the method includes the construction of a second set of code words consisting of code words from the first set as well as concatenations of code words from the first set. The concatenation comprises selecting a code word from the first set of code words and applying it as a prefix to itself and to all of the other words in the first set, thereby constructing the second set. Code words from said second set which has been constructed are used to carry data in compressed form in the digital bitstream.
The concatenation is preferably done by selecting a code word from the first set of code words and applying it as a prefix to itself and an optional prefix to all of the other words in said first set, resulting in said second set. This way each code word of the first set appears with and without prefix in the second set. The only exception is the code word selected as prefix, which does not appear in the second set on its own.
In another preferred embodiment, the said second set consists of 1) the selected code word concatenated with itself n times and all combinations of 2) the selected code word concatenated with itself between 0 and n−1 times followed by a concatenation with one of the other code words of said first set.
A further preferred method in accordance with the invention as described above is one in which code words of said first set comprise:
1
0x1
0x0x1
0x0x0x1, etcetera,
where x is either 0 or 1, and the prefix is chosen to be the code word 1 and in which code words of said second set comprise:
11
0x1
10x1
0x0x1
10x0x1, etcetera.
Code words from said first set may be used to carry data in the bitstream in addition to words from the second set. The decision on what code word set to use may be signaled explicitly in the bitstream or it may be decided implicitly based on previously transmitted information or lack thereof.
In accordance with the invention, the bitstream carrying compressed data may be used in video and still image compression where the previously sent information consists of quantizer and/or picture type and/or coefficient values and/or motion vector information and/or block type.
REFERENCES:
patent: 3694813 (1972-09-01), Loh et al.
patent: 4813056 (1989-03-01), Fedele
patent: 4918523 (1990-04-01), Simon et al.
patent: 5225832 (1993-07-01), Wang et al.
patent: 5298896 (1994-03-01), Lei et al.
patent: 5301032 (1994-04-01), Hong et al.
patent: 5625355 (1997-04-01), Takeno et al.
patent: 5912636 (1999-06-01), Gormish et al.
patent: 6046774 (2000-04-01), Heo et al.
patent: 6097757 (2000-08-01), Boice et al.
patent: 6483543 (2002-11-01), Zhang et al.
patent: 6647060 (2003-11-01), Ueda
patent: 0 732 854 (1996-09-01), None
patent: 0 907 288 (1999-04-01), None
European Patent Office Standard Search Report, File No. RS 106716, Oct. 29, 2001, pp. 1-2.
Hartung, F. et al., “Improving Encoding of DCT Coefficients for Low Bit-Rate Video Coding Using Multiple VLC Tables,” Proceedings 1999 International Conference on Image Processing. ICIP '99. Kobe, Japan, Oct. 24-28, 1999, International Conference on Image Processing, Los Alamitos, CA: IEEE, US, vol. 2 of 4, Oct. 24, 1999, pp. 51-55.
Bjontegaard, G. (Editor); “H.26L Test Model Long Term No. 5 (TML-5) draft 0.”; ITU Telecommunications Standardization Sector, Study Group 16, Video Coding Experts Group (Question 15); Document Q15-K-59; Filename: q15k59dl.doc; Generated: Oct. 25, 2000; Eleventh Meeting: Portland, Oregon, USA, Aug. 22-25, 2000, pp. 1-35.
Fröjdh Per
Sjöberg Rickard
Alavi Amir
Johns Andrew W.
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Method of compressing data by use of self-prefixed universal... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of compressing data by use of self-prefixed universal..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of compressing data by use of self-prefixed universal... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3280429