Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1998-12-18
2001-09-11
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S232000
Reexamination Certificate
active
06289131
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a method for compressing image data such as data of a natural image and, more particularly, to a method for encoding image data such as a static image or a dynamic image by using a wavelet transform.
2. Description of the Related Art
Conventionally, a discrete cosine transform (DCT) is popular for compressing natural image data such as static image data or dynamic image data. However, when encoding image data by using the DCT, a problem arises in achieving a high compression ratio since there is an inherent deterioration in subjective image quality caused by generation of a block distortion or a mosquito noise. In order to eliminate such a problem, various image encoding methods using a wavelet transform have been studied.
A brief description will now be given of the wavelet transform. A sub-band division shown in
FIG. 1
can be performed on an analyzing side of a filter bank shown in FIG.
2
. On the analyzing side of the filter bank, image data is filtered by a low-pass filter H
0
and a 2:1 sub-sampling (↓2) is performed in a horizontal direction. The processed image data is filtered by a high-pass filter H
1
in a horizontal direction and a 2:1 sub-sampling (↓2) is performed in a vertical direction. An image is restored by processing the obtained frequency-band signals on a synthesizing side of the filter bank. On the synthesizing side of the filter bank, a 2:1 up-sampling (↑2) and filtering by a low-pass filter F
0
or a high-pass filter F
1
are performed on each of the frequency band signals in a vertical direction, and a 2:1 up-sampling (↑2) and filtering is performed by the low-pass filter F
0
or the high-pass filter F
1
in a horizontal direction. An encoding method in which a signal is divided into frequency bands is generally referred to as a sub-band encoding. The encoding using a wavelet transform is regarded as a sub-band encoding as described below.
In the wavelet transform, a multilayer band division is performed by repeating the above-mentioned sub-band division on a low-band signal (a signal LL shown in FIG.
1
). Such a band division is referred to as an octave division. If a division is performed for three layers, ten sub-bands are obtained as shown in FIG.
3
. In
FIG. 3
, reference numerals
8
to
10
indicate sub-bands in the lowest layer,
5
to
7
indicate sub-bands in the middle layer, and
1
to
4
indicate sub-bands in the highest layer.
The frequency-band signals obtained by the above-mentioned division include signals (wavelet coefficients) LL, LH, HL and HH as shown in
FIG. 1
or FIG.
3
. In
FIG. 3
, the signal LL
1
is a signal on a low-band side in both the horizontal and vertical directions. The signal LL
1
is obtained by filtering image data by a two-dimensional low-pass filter (LPF). Hereinafter, the signal LL may be referred to as a “low-band component.” The signals HL
3
,
6
and
9
are obtained by filtering by a high-pass filter (HPF) in the horizontal direction and filtering by a low-pass filter in the vertical direction. An edge component in the vertical direction appears in the signal HL. Hereinafter, this edge component may be referred to as a “vertical component.” The signals LH
2
,
5
and
8
are obtained by filtering by a low-pass filter in the horizontal direction and filtering by a high-pass filter in the vertical direction. An edge component in the horizontal direction appears in the signals LH
2
,
5
and
8
. Hereinafter, this edge component may be referred to as a “horizontal component.” The signals HH
4
,
7
and
10
are obtained by filtering by a high-pass filter in both the horizontal direction and the vertical direction. An edge component in a diagonal direction appears in the signals HH
4
,
7
and
10
. Hereinafter, this edge component may be referred to as a “diagonal component”.
It should be noted that in the wavelet transform, the above-mentioned filters are designed so as to satisfy a condition for completely restoring a signal, that is, to satisfy an orthogonal condition and a normal condition. Additionally, when a filter having a number of taps longer than the dividing number 2 in each band division is used, a block distortion may be prevented since overlapping of basic waveforms occurs. Further, as only the low band is repeatedly subjected to the band division, a shorter basic waveform is used as the frequency increases. Thus, it can be expected that a mosquito noise caused by a quantization distortion of a high-frequency component does not spread spatially.
A description will now be given of a conventional method for encoding wavelet coefficients. First, each wavelet coefficient is quantized into a scalar quantity. The quantization process uses a linear quantization for each band. Herein, an adaptive quantization in which the quantization process is switched for each band is not considered. The coefficients are encoded subsequent to the quantization. As for the method for encoding, there is a method suggested in “9.6-kb/s Picture Coding Using Wavelet Transform”, a thesis of the 1993 Institute of Electronics, Information and Communication Engineers (IEICE) Spring Conference, D-262, 7-23. With respect to the quantized coefficients, one coefficient is taken from one of the bands LL, LH, HL and HH in the highest layer (in a case of three-times division). Four coefficients (2×2) are taken from each of the bands LH, HL and HH in the middle layer. Sixteen coefficients (4×4) are taken from each of the bands LH, HL and HH in the lowest layer. These coefficients are arranged in the same positional relationship so as to form an 8×8 block shown in FIG.
4
. The sixty-four coefficients in the 8×8 block are scanned in an order shown in
FIG. 5
so as to obtain a one-dimensional string of coefficients. Then, the coefficients are subjected to a two-dimensional Huffman encoding with [run length of zero run, significant coefficient]. However, only the DC component (LL coefficient of the highest layer) is subjected to a DPCM. As is apparent from
FIG. 5
, the scanning is performed from the highest layer toward the lowest layer. In the same layer, the canning is performed in the order of the vertical component (HL), the horizontal component (LH) and the diagonal component (HH). Additionally, the vertical components are scanned in the vertical direction, the horizontal components are scanned in the horizontal direction and the diagonal components are zigzag scanned.
Additionally, “Wavelet Transform Coding for Picture (2) “Scanning Method suitable for Wavelet Basis—”, a thesis of the 1993 Institute of Electronics, Information and Communication Engineer (IEICE) Spring Conference, D-
336, 7-46,
discloses another conventional method. In this method, 8×8 coefficients in a block are formed in a quad-tree structure by forming a single node by three coefficients (LH, HL, HH) located in the same spatial position in each layer, and scanning for a sub-tree is stopped at EOS (end of sub-tree) code. The node in the quad tree is scanned by a depth-first method, and is encoded as a one-dimensional string of the EOS or coefficients.
The conventional method described with reference to
FIG. 5
is well adapted to the method in which the DCT coefficients in a 8×8 pixel block are zigzag scanned to form a one-dimensional coefficient string and the coefficient string is encoded by the two-dimensional Huffman encoding with [run length of zero run, significant coefficient]. However, this method is not always suitable for a characteristic of the wavelet transform coefficient. In a case in which the DCT coefficients are zigzag scanned, coefficients corresponding to frequency components in the same area (8×8) are scanned in a direction from a lower frequency to a higher frequency. Accordingly, energy is concentrated into a low-frequency component, and a large significant coefficient appears in the low-frequency component. On the other hand, a frequency of appea
Couso Jose L.
Dang Duy M.
Dickstein , Shapiro, Morin & Oshinsky, LLP
Ricoh & Company, Ltd.
LandOfFree
Method for encoding wavelet coefficients 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 for encoding wavelet coefficients, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for encoding wavelet coefficients will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2527109