Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
2000-04-25
2003-12-02
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image compression or coding
Transform coding
C382S251000, C382S239000, C382S236000, C348S407100, C348S103000, C348S097000
Reexamination Certificate
active
06658161
ABSTRACT:
BACKGROUND OF THE INVENTION
This application incorporates by reference Taiwanese application Ser. No. 88115162, filed Sep. 3, 1999.
1. Field of the Invention
The invention relates in general to a signal-processing method and a device therefor which combine a coordinate transformation with quantization and more particularly to a signal-processing method and a device therefore for achieving adaptive calculation quantity, image quality and bit rate.
2. Description of the Related Art
In digital signal compression, in order to reduce redundant data in coding, the coordinate transformation is usually applied for compressing image data or video data. That is because these data have good energy compact effect after the coordinate transformation. A good energy compact effect represents that, most energy is compacted at lower frequency bands, and little energy exists at higher frequency bands. After quantization, only data at lower frequency bands have codes. Therefore, the data are compressed.
Discrete Cosine Transform (DCT) is a coordinate transformation from the time domain to the frequency domain. There are four basic types of DCT, which are DCT-I, DCT-II, DCT-III and DCT-IV. What follows is the expression of the four types.
DCT-I:
y
(
k
)
=
(
2
N
)
1
/
2
e
(
k
)
∑
n
=
0
N
e
(
n
)
x
(
n
)
·
cos
(
nk
π
N
)
where n, k=0,1, . . . , N.
DCT-II:
y
(
k
)
=
(
2
N
)
1
/
2
e
(
k
)
∑
n
=
0
N
-
1
x
(
n
)
·
cos
(
(
2
n
+
1
)
k
π
2
N
)
where n, k=0,1, . . . , N−1.
DCT-III:
y
(
k
)
=
(
2
N
)
1
/
2
∑
n
=
0
N
-
1
e
(
n
)
x
(
n
)
·
cos
(
(
2
k
+
1
)
n
π
2
N
)
where n, k=0,1, . . . , N−1.
DCT-IV:
y
(
k
)
=
(
2
N
)
1
/
2
∑
n
=
0
N
-
1
x
(
n
)
·
cos
(
(
2
k
+
1
)
(
2
n
+
1
)
π
4
N
)
wheren n, k=0,1, . . . , N−1.
In the above expressions, when n=0,
e
(
n
)
=
1
2
,
else e(n)=1, and y(k) is an output from DCT and x(n) is an input to DCT. In practice, DCT-II is the most popular.
In the following statements, one-dimensional (1-D) DCT is first introduced for explaining two-dimensional (2-D) DCT.
Since the energy compact effect of DCT resembles to that of the Karhunen-Loe've transform, there are many researches about how to reduce computational complexity for 1-D DCT, for example, Lee's DCT algorithm. The Lee's DCT algorithm only needs 12 multiplication operations and 29 addition operations for 8-point 1-D DCT. In convention, the low-bound computational complexity of multiplication for N-point 1-D DCT is expressed as: &mgr;(DCT
N
)=2
n+1
−n−2; wherein N=2
n
and &mgr; represents low-bound multiplication operations.
Therefore, the computational complexity for 8-point 1-D DCT of Lee's algorithm meets the requirement of the low-bound calculation quantity.
It is assumed that Y(k) is the result of x(n)'s DCT transformation, wherein k & n=0, 1, 2, . . . N−1. The Forward DCT (FDCT) of x(n) can therefore be expressed as:
Y
(
k
)
=
2
N
e
(
k
)
∑
n
=
0
N
-
1
x
(
n
)
cos
[
(
2
n
+
1
)
k
π
2
N
]
(
1
)
,wherein when k=0,
e
(
k
)
=
1
2
,
else e(k)=1.
This type of DCT is the so-called DCT-II type. The Inverse DCT (IDCT) of the DCT-II type is expressed as:
x
(
n
)
=
∑
k
=
0
N
-
1
e
(
k
)
Y
(
k
)
cos
[
(
2
n
+
1
)
k
π
2
N
]
(
2
)
wherein when k=0,
e
(
k
)
=
1
2
,
else e(k)=1.
Eq. (2) is also expressed as:
x
(
n
)
=
∑
k
=
0
N
-
1
Y
^
(
k
)
cos
[
(
2
n
+
1
)
k
π
2
N
]
(
3
)
wherein Ŷ=e(k)Y(k)
Based on odd k and even k, the following expression is obtained:
g
(
n
)
=
∑
k
=
0
N
/
2
-
1
G
(
k
)
cos
[
(
2
n
+
1
)
k
π
N
]
h
(
n
)
=
∑
k
=
0
N
/
2
-
1
H
(
k
)
cos
[
(
2
n
+
1
)
k
π
N
]
(
4
)
wherein
G
(
k
)=
Ŷ
(2
k
),
H
(
k
)=Ŷ(2
k
+1)+Ŷ(2
k
−1),
k
=0
, . . . , N
/2−1
, Ŷ(−
1)=0
From the above description, x(n) can be expressed as:
x
(
n
)
=
g
(
n
)
+
(
1
/
2
cos
[
(
2
n
+
1
)
π
N
]
)
·
h
(
n
)
x
(
N
-
n
-
1
)
=
g
(
n
)
-
(
1
/
2
cos
[
(
2
n
+
1
)
π
N
]
)
·
h
(
n
)
n
=
0
,
…
,
n
/
2
-
1
(
5
)
It should be noticed that equations (2)~(5) come from IDCT. Because DCT is an orthogonal transform, the structure of FDCT is inversed from that of IDCT. The structure for 8-point 1-D DCT is shown in FIG.
1
. In
FIG. 1
, X(0)~X(7) represent the input data, and y(0)~y(7) represent the output data. Herein, y(0)~y(7) are also called 1-D DCT outputs.
In image compression, it is usually to perform DCT on an image block with 8*8 pixels, and this kind of DCT transformation is usually a 2-D DCT transformation.
Here, another conventional 4*4 recursive 2-D DCT structure is taken as an example. Because this structure is a recursive one, its application can be extended to N*N 2-D DCT (N=2
n
). 8*8 2-D DCT structure can also be deduced, which is as shown in FIG.
2
. In
FIG. 2
, x
00
, x
01
, . . . represent the input data, and y(m, n) (m, n=0~7) represent the 2-D DCT outputs. To realize this 2-D DCT structure, eight 1-D DCT structures are required. These 1-D DCT structures are the Lee's 1-D DCT structure. The outputs from 1-D DCT are represented by a
i
(i=0~63). For simplicity, only some of the a
i
values are shown in FIG.
2
. However, the non-shown a, values can be easily deduced from the figure. The scanning orders (or zig-zag order) represent the frequency-scanning orders of 2-D DCT outputs of the image block with 8*8 pixels. The output at a lower frequency band has also a lower scanning order. The 2-D DCT operation of an image block with 8*8 pixels totally includes 96 multiplication operations, 466 addition operations and 49 shift operations.
Generally speaking, when an image block with 8*8 pixels is performed by a 2-D DCT and quantization operation, the high frequency coefficients are often 0. In coding, these coefficients having a value of 0 are not taken into calculation.
In real practice, in order to obtain desirable quality of the reconstructed image, more calculations are required. However, more calculations cause the reduction of throughput rate or the increase of hardware cost. Therefore, it is important to trade off the computational complexity against the reconstructed image quality.
In image data compression, coordinate transformation and quantization operations are usually combined.
FIG. 3
a
is a block diagram of a conventional method for coordinate transformation and quantization. Herein, the coordinate transformation usually directs to DCT, which is a coordinate transformation from time domain (time coordinate) to frequency domain (frequency coordinate). In this conventional method, all 2-D DCT coefficients of the image block are calculated and then quantized for obtaining quantized outputs. The 2-D DCT unit
310
calculates all 2-D DCT coefficients, whose structure is shown as FIG.
2
. The quantization unit
320
quantizes these 2-D DCT coefficients. The method to perform quantization is well known; so the detail is not described here.
The above-mentioned conventional method can have the optimized quality of the reconstructed image. However, the conv
Chen Oscal Tzyh-Chiang
Hsieh Hsun-Chang
Industrial Technology Research Institute
Kassa Yosef
Mehta Bhavesh M.
LandOfFree
Signal-processing method and device therefore does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Signal-processing method and device therefore, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Signal-processing method and device therefore will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3095293