Huffman encoder, Huffman encoding method and recording...

Details Huffman encoder, Huffman encoding method and recording... Huffman encoder, Huffman encoding method and recording...

2001-01-31

2003-08-12

Jeanglaude, Jean Bruner (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from number of pulses

C341S063000, C341S060000, C341S050000, C382S232000, C358S438000

Reexamination Certificate

active

06606039

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a Huffman encoder, a method for Huffman encoding and a recording medium having a program for a Huffman encoding process recorded thereon for encoding data which has been subjected to discrete cosine transformation into Huffman codes.
2. Description of the Prior Art
Image data includes a huge amount of information. It is therefore impractical to process image data as it is from the viewpoint of the memory capacity required therefor and communication speed. Techniques for compressing image data are therefore important.
One of international standards for image data compression is the JPEG (Joint Photographic Expert Group) standard. JPEG adopts the DCT (discrete cosine transformation) method which involves irreversible encoding and the reversible encoding method which involves DPCM (differential PCM) in a two-dimensional space. The compression of image data according to the DCT method will now be described.
FIG. 7
is a block diagram of a Huffman encoder which performs compression of image data according to the DCT method.
A DCT device
100
performs discrete cosine transformation (hereinafter referred to as “DCT”) on original image data input thereto and outputs DCT coefficients. During such DCT, as shown in
FIG. 8
, image data is divided into a plurality of pixel blocks each having 8×8 pixels. As shown in
FIG. 9
, one 8×8 pixel block includes 64 items of pixel data P
XY
(X, Y=0, . . . , 7). Two-dimensional DCT on an 8×8 pixel block thus divided will provide 64 DCT coefficients S
UV
(U, V=0, . . . , 7).
The DCT coefficient S
00
, is referred to as “DC coefficient”, and the remaining 63 DCT coefficients are referred to as “AC coefficients”. As shown in
FIG. 9
, the number of horizontal frequency components at high frequencies of a block which has been subjected to DCT is smallest at the left end of the block and is greatest at the right end, and the number of vertical frequency components at high frequencies is smallest at the top of the block and is greatest at the bottom.
A quantizer
110
shown in
FIG. 7
quantizes DCT coefficients output by the DCT device
100
as expressed by the following equation using a quantization table consisting of 8×8 quantization coefficients Q
UV
(U, V=0, . . . , 7) to output quantized DCT coefficients &ggr;
UV
(U, V=0, . . . , 7).
 &ggr;
UV=round (
S
UV
/Q
UV
)  (1)
where “round” represents a process of rounding a number to the nearest integral number. Image quality and the amount of encoded information are controlled by such quantization.
FIG. 10
shows examples of the DCT coefficients output by the quantizer
110
. In
FIG. 10
, “A”, “B”, “C”, “D”, “E” and “F” represent values other than “0”.
A Huffman encoding portion
120
in
FIG. 7
encodes the DCT coefficients &ggr;
UV
output by the quantizer
110
into Huffman codes to output encoded data. Referring to encoding of a DC coefficient, the difference between the DC coefficient of the current block and the DC coefficient of the preceding block is obtained, and the difference is encoded. In this case, differences between DC coefficients are grouped; and a group number SSSS is assigned to each difference; and a Huffman code is assigned to each group number SSSS.
Referring to encoding of AC coefficients, as shown in
FIG. 11
, the AC coefficients are first arranged on a one-dimensional basis as a result of a zigzag scan. The one-dimensionally arranged AC coefficients are encoded using run lengths NNNN representing the number of consecutive coefficients “0” (invalid coefficients) and the values of coefficients (valid coefficients) other than “0”. In this case, the valid coefficients are grouped, and a group number SSSS is assigned to each of the valid coefficients. When an AC coefficient is encoded, a Huffman code is assigned to a combination of the run length NNNN and the group number SSSS.
FIG. 12
shows an example of a table of Huffman codes for DC coefficients. For example, a Huffman code “00” having a code length of 2 is assigned to a DC coefficient difference whose group number SSSS is “0”; a Huffman code “010” having a code length of 3 is assigned to a DC coefficient difference whose group number SSSS is “1”; and a Huffman code “011” having a code length of 3 is assigned to a DC coefficient difference whose group number SSSS is “2”.
In the Huffman code table of
FIG. 12
, a group number SSSS only identifies the group to which a DC coefficient difference belongs. An additional bit is used to identify one of DC coefficients belonging to one group.
FIG. 13
shows an example of a table of Huffman codes for AC coefficients. For example, a Huffman code “1010” having a code length of 4 is assigned to an AC coefficient whose run length/group number combination NNNN/SSSS is “0/0”; a Huffman code “00” having a code length of 2 is assigned to an AC coefficient whose NNNN/SSSS is “0/1”; and a Huffman code “01” having a code length of 2 is assigned to an AC coefficient whose NNNN/SSSS is “0/2”.
In the Huffman code table of
FIG. 13
, a group number SSSS only identifies the group to which a valid coefficient belongs. An additional bit is used to identify one of valid coefficients belonging to one group.
FIG. 14
is a schematic view of an example of a Huffman encoding process in the Huffman encoder according to the related art shown in FIG.
7
.
As shown in
FIG. 14
, DCT coefficients are quantized as expressed by Equation 1 to obtain quantized DCT coefficients &ggr;
UV
. In the example shown in
FIG. 14
, a quantized DCT coefficient &ggr;
00
of “16” is obtained from a DCT coefficient S
00
of “260” and a quantization coefficient Q
00
of “16”. Similarly, quantized DCT coefficients &ggr;
01
=4, &ggr;
02
=−2, &ggr;
10
−7, &ggr;
11
=3, &ggr;
21
=−1 and &ggr;
30
=−1 are obtained, and other quantized DCT coefficients &ggr;
UV
are 0.
The quantized DCT coefficients &ggr;
UV
are one-dimensionally arranged as a result of a zigzag scan to obtain run lengths representing the number of the coefficients “0” and valid coefficients. The first valid coefficient (DC coefficient) is “16” which is followed by run length/valid coefficient combinations of “0/4”, “0/−7”, “1/3”, “0/−2”, “2/−1” and “0/−1”, and the last run length is “54”.
In order to change the data compression rate of the above-described Huffman encoder according to the related art, the 8×8 quantization coefficients Q
UV
included in the quantization table must be changed. This makes a process for controlling the data compression rate complicated.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a Huffman encoder, a method for Huffman encoding process, a program for a Huffman encoding process in which a data compression rate can be easily changed and a recording medium having the program for a Huffman encoding process recorded thereon.
A Huffman encoder for encoding a series of data into Huffman codes, according to an aspect of the invention comprises determination means for determining whether each item of a series of data is within a predetermined range and encoding means for performing encoding using combinations of the number of consecutive invalid coefficients and valid coefficients, the invalid coefficients being data among the series of data which are within the predetermined range, the valid coefficients being data out of the predetermined range.
In the Huffman encoder according to the invention, the determination means determines whether each item of a series of data is within a predetermined range. The encoding means treats data among the series of data which are within the predetermined range as invalid coefficients, treats data out of the predetermined range as valid coefficients and performs encoding using combinations of the number of consecutive invalid coefficients and valid coefficients.
In this case, the number of invalid coefficients can be arbitrarily adjusted by

Affiliated with

Also associated with

Rating

Huffman encoder, Huffman encoding method and recording... does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3094407