Data compression

Details Data compression Data compression

1993-10-27

2001-06-05

Chang, Jon (Department: 2723)

Image analysis

Image compression or coding

Lossless compression

C382S246000

Reexamination Certificate

active

06243496

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to data compression. The invention relates particularly, but not exclusively, to the field of image data compression.
2. Description of the Prior Art
It has been proposed to provide an image data processing system in which image data are decorrelated into sub-band components, quantised and then entropy encoded. The quantisation provides some degree of data compression with some loss of information content. The subsequent entropy encoding effects a further degree of data compression with no loss of information content.
One known entropy encoding technique is so called run length encoding. A typical run length encoder looks for sequences of successive zeros within a data stream and assigns a code word to substitute for each sequence of zeros within the data stream. When the data stream is subsequently read, the run-length codes can be expanded to recreate the original data stream.
A variation on this arrangement is the type of run length encoding proposed in the standard being devised by the Joint Photographic Experts Group (JPEG) and currently under review by the International Standards Organisation. The JPEG standard proposes a run-length encoding technique in which a sequence of successive zero values terminated by a non-zero value is treated as an “event” and assigned a two-word run length code. The syntax of these two-word codes is: [RUNLENGTH, SIZE], [AMPLITUDE]. The RUNLENGTH variable specifies the number of zero values preceding the non-zero value. The SIZE variable specifies the number of bits that will be required to represent the amplitude of the non-zero value that terminates the sequence of successive zero values. The AMPLITUDE variable specifies the amplitude of the non-zero value.
Once the image data has been subjected to this run length encoding, it is then subjected to Huffman encoding. Huffman encoding is a form of commaless encoding whereby events are mapped to a set of codes having the property that no valid code is a prefix of a longer code. The most common events are mapped to the shortest Huffman codes.
An alternative encoding technique for the encoding of image signals has been proposed by P. Delogne and B. Macq in an article entitled “Universal Variable Length Coding for an Integrated Approach to Image Coding”, published in Ann. Telecommun 46 7-8/1991). The authors describe a so-called “skip coding” technique for entropy encoding.
The skip coding technique will be described herein with reference to
FIG. 1
which represents a sequence of image sample code words as a two-dimensional array represented in
FIG. 1
of the accompanying drawings. In the two-dimensional array, the horizontal direction represents successive words for respective image samples, and the vertical axis represents the bits of each word from the least significant bit (LSB) position at the bottom (i.e. bit
0
) to the most significant bit position (MSB) at the top (i.e. bit
11
). In
FIG. 1
, the sample words for respective image pixels are represented as a one-dimensional stream. If, alternatively, they were represented two-dimensionally in terms of the rows and columns of a raster scanned image, the resulting array corresponding to
FIG. 1
would be three dimensional, with the rows and columns forming two dimensions and the respective bits of each code word forming the third dimension. In
FIG. 1
, the cross-hatched bit positions represent non-zero bits and the blank bit positions represent zero bits. Words
0
,
2
,
3
,
6
,
7
,
9
,
10
,
14
,
15
,
18
,
20
,
21
and
23
are assumed to represent words having only zero bits.
In accordance with the skip coding technique described in the aforementioned article, the array of sample words is then scanned as a sequence of bit runs from the most significant bit (MSB) position to the least significant bit position (LSB). However, the scanning does not access all bit positions in order. The scanning starts, for example at the top left hand position as illustrated in
FIG. 1
(i.e. the left-hand side of the MSB position—bit
11
of word
0
), and continues along the horizontal arrows A
1
.
1
, A
1
.
2
until a non-zero bit is reached in a word, or until a predetermined maximum number m of zeros have been counted. At this point either a run length code for the number of zeros terminated by a one or for the run of m zeros is encoded. If a most significant non-zero bit in a word is encountered (eg. the bit
10
of word
8
) the bits of this word are then output uncoded as represented by the vertical arrow A
2
and word
8
is eliminated from the array. After the output of a word, or if a run of m zeros has been encoded, the scan restarts at the next bit in the scanning order (e.g. in
FIG. 1
at bit
10
of word
9
) and continues along the horizontal arrows A
3
.
1
, A
3
.
2
, A
3
.
3
until a most significant non-zero bit in a further word is reached (in
FIG. 1
, bit
8
of word
19
). Note in
FIG. 1
that bit
8
of word
8
is skipped (hence the term applied to this type of coding) as by then that word has already been output and eliminated from the array. The bits of word
19
are then output uncoded as represented by the vertical arrow A
4
, the word
19
is eliminated from the array and the scanning restarts at the next bit position in the scanning order (in
FIG. 1
, bit
8
of word
20
—horizontal arrow A
5
.
1
). This process continues until the last bit in the block (bit
0
of word
23
) is reached.
The coding process proposed in this article does provide for relatively efficient coding of data samples. However, it does have a number of disadvantages. As the compression encoding employs bit-based encoding, it must operate at a faster rate than word-based encoders. Accordingly, a hardware implementation is more suited to meeting the high processing frequency requirements. However, as the coding method requires the coding process to switch repeatedly between run length encoding and the output of the bits of a word in uncoded form, this complicates the hardware implementation of the technique. Also, where data (e.g. image data) are to be stored or transmitted in a manner which provides a shuttle mode, a marker flag must be set against a word position when a most significant non-zero bit in a word is met and the remaining lower bits appended thereto in order for the skipping process to work. In the case of a digital video tape recorder, for example, where the data for recording are formatted in recording blocks, the coding will inevitably be split across those recording blocks. Then, if a recording block preceding a desired recording block is not retrieved on replay, it may be impossible to know where the marker flags have been set with the result that the replay decoder will not be able to restore the recorded data.
SUMMARY OF THE INVENTION
It is a constant aim in the field of data compression to increase the degree of compression achieved without adversely affecting the identity of the data subsequently regenerated.
Accordingly, in accordance with a first aspect of the invention, there is provided a data compression system for compressing M-bit data words where M is a plural positive integer, the data compression system comprising:
a) bit stream generating means for generating a set of bit streams in which successive bits are from a corresponding bit position of respective M-bit data words, the bit stream generating means comprises group defining means for defining a group of N data words, where N is a plural positive integer, and sequencing means for outputting the bits of the group of N data words as a set of bit streams, each bit stream relating to a respective bit position in the N data words and comprising a sequence of N data bits from that bit position of respective data words; and
b) run length encoding means connected to receive the output of the sequencing means to run length encode the set of bit streams.
The outputting of the bit streams for a group of data words in accordance with the invention, with subsequent run l

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-2481112