Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-10
2002-07-16
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06421695
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the implementation of an inverse discrete cosine transform (IDCT) in digital image processing systems, and more particularly, to an improved implementation of two-dimensional IDCT without zero-stuffing to accelerate the processing time of inverse discrete cosine transform.
2. Description of the Background Art
FIG. 1
is a flow chart showing a typical digital image decoding process in a digital image processing system. As shown in
FIG. 1
, the prior stages of IDCT are inverse quantization and inverse zigzag scanning and, in most implementations, the inverse zigzag scanning is carried out as an output stage of the inverse quantization. The present invention is theoretically based on the non-zero input characteristic of inverse discrete cosine transform. The non-zero input characteristic represents the fact that the IDCT input has many zero-valued data. This is because the discrete cosine transform (DCT) and the quantization operation in the digital image encoding system convert many non-zero data into zero data to reduce the data size of the encoded bit-stream. The compressed bit-stream is an input to a decoding system. A VLD (Variable Length Decoder) and an inverse quantizer with inverse zigzag scanning deal with the encoded bit-stream and it is the input of the IDCT where zero data is reconstructed. There are many zero elements in the N×N IDCT input block. These zero-valued data are created by zero stuffing operation using the position information, which is obtained by inverse zigzag scanning.
It is known that there are two different methods (A) and (B) for implementing IDCT.
(A) The first IDCT method allows a simple and regular structure for implementing 2-dimensional (2-D) IDCT by decomposing it into two one-dimensional IDCTs. A matrix form for implementing N×N 2-D IDCT will be written as following equation (1):
Z
j
k
=
2
N
∑
u
=
0
N
-
1
∑
v
=
0
N
-
1
C
u
C
v
X
u
v
cos
[
(
2
j
+
1
)
u
π
2
N
]
[
(
2
k
+
1
)
v
π
2
N
]
(
1
)
Here, u, v, j and k equal 0, 1, . . . , (N−1), and Z
jk
denotes the j-th row, k-th column element in an output matrix of the 2-D IDCT, X
uv
represents u-th row, v-th column element in an input matrix X of the 2-D IDCT, and Cu and Cv represent elements in a cosine kernel matrix C of the IDCT.
The 2-D IDCT can be separated into two 1-D IDCTs, which is shown in a matrix form as following equation (2):
Z=CXC
T
=YC
T
=(
CY
T
)
T
(2)
Here, “Z” represents an output matrix of the 2-D IDCT. The notation “CX” is a matrix multiplication, where “C” represents a cosine kernel matrix of the IDCT, and “X” represents an input matrix of the first 1-D IDCT, and “Y” matrix represents an input matrix of the second 1-D IDCT. The matrix Y is obtained as a result of the first matrix multiplication CX and is transposed in order to make the same matrix multiplication form as the matrix multiplication CX. Then, the transposed matrix Y becomes the input matrix of the second 1-D IDCT.
FIG. 2
shows a matrix multiplication form CX=Y in 1-D IDCT operation according to the conventional art, wherein the notation “C” represents a cosine kernel matrix, “X” represents input data matrix, and “Y” represents an output data matrix where each element is obtained by the inner product of the corresponding column and row in matrixes C and X. The matrix multiplication CX of the 1-D IDCT focuses on how to generate an output element Y
jk
and requires N input elements and N cosine coefficients simultaneously. The N input elements and the N cosine coefficients are multiplied respectively and N multiplication outputs are obtained. These N multiplication outputs are added to generate an output element Y
jk
. All N input elements are required to make the output element Y
jk
.
(B) Second IDCT method considers the non-zero input characteristic in the IDCT input domain. It is apparent that there are many zero elements in the IDCT input domain since IDCT input is a compressed DCT coefficient.
According to the widely accepted standards, such as MPEG, it is known that there are many zero elements in the IDCT input. These zero elements are added into the IDCT input after performing inverse zigzag scanning, however if zero data are present in the IDCT input data, it is difficult to skip the zero data in reading only non-zero data from an IDCT input memory. The inverse zigzag scanning operation is to find a relative position of the inverse quantized data. These inverse quantized data are placed in the IDCT input memory using the position information and the rest of the input memory where non-zero data are not occupied are filled with zeros, which we dubbed this operation zero-stuffing.
In one type of technique, the non-zero processing is applied to two-dimensional IDCT directly. This kind of 2-D direct implementation also aims at fast IDCT computation, however, the 2-D direct implementation requires complex interconnection between multipliers and an accumulator array and large hardware cost such as N×N accumulator array.
In another technique, a zero input detector is used to inactivate the controllable multiply-addition operation when the input data value is detected as a zero. In other words, this IDCT technique reads all input elements one by one and the zero input detector determines whether each input element is zero or not and generates a control signal to a controllable multiply-addition unit. The multiply-addition unit is performed only when the control signal tells that the input data value is a non-zero. If there are M non-zero input elements in the N×N input data block, this technique consumes N
2
cycles to read N
2
input elements. Among N
2
cycles, the IDCT operation including multiply operation and addition operation will be activated for M cycles when non-zero elements are processed. This technique has an ability to selectively processing only non-zero inputs. However, it needs a plenty of time for reading all IDCT input elements to determine whether they are zero or not, whereas the IDCT input characteristic refers to the fact that the value zeros are widely distributed in the input data of the IDCT.
SUMMARY OF THE INVENTION
Therefore, it is an object of the present invention to carry out a 1-D IDCT using non-zero input data being applied without a zero stuffing.
It is another object of the present invention to selectively process non-zero input data so as to perform 1-D IDCT during cycles corresponding to the number of non-zero elements among the input data.
To achieve the above-described objects, there is provided an apparatus for implementing inverse discrete cosine transform in a digital image processing system according to the present invention which includes a first non-zero feeding unit for storing therein a first position information of an inverse zigzag scanned non-zero input data, a second non-zero feeding unit for receiving the first position information and storing therein a second position information, a 1-D IDCT core for receiving the inverse zigzag scanned non-zero input data and performing the 1-D IDCT operation in accordance with the first or second position information, and a memory unit for storing therein the 1-D IDCTed data value.
The features and advantages of the present invention will become more readily apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific example, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.
REFERENCES:
patent: 5301136 (1994-04-01), Mcmillan, Jr. et al.
patent: 5345408 (1994-09-01), Hoogenboom
patent: 5471412 (1995-11-01), S
Bae Seong Ok
Min Seung Jai
Birch & Stewart Kolasch & Birch, LLP
LG Electronics Inc.
Mai Tan V.
LandOfFree
Apparatus for implementing inverse discrete cosine transform... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for implementing inverse discrete cosine transform..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for implementing inverse discrete cosine transform... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2864498