US5883823A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method of a fast inverse discrete cosine transform and video compression/decompression systems employing the same
Assignee: Oracle America Inc
•
Filing: 1997-01-15
•
Granted: 1999-03-16
•
Expires: 2017-01-15
Abstract
Abstract An array of DCT transform coefficients are converted to a two-dimensional array of spatial data in a video compression or decompression system. The array of DCT transform coefficients are divided into two groups. A regional IDCT algorithm is applied to all coefficients, both non-zero and zero, of the first group, while IDCT computation is applied to only non-zero coefficients of the second group. The results of the operations are then combined and/or mapped to form the output array of spatial data. In one specific implementation wherein an 8×8 array of DCT coefficients are to be transformed, the first region is defined by the first quadrant of coefficients in the 8×8 array. A regional IDCT algorithm is applied to both zero and non-zero coefficients in the first quadrant. The non-zero coefficients in the remaining three quadrants are calculated directly, and the results of the direct calculations are combined with the results of the regional IDCT algorithm applied to the first quadrant coefficients. The resulting values are then mapped to the output matrix.
Inventors
- 👤 Wei Ding
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 16:43
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/147; G06T; G06T9/00; G06T9/007
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
124 words
A method for performing an inverse discrete cosine transform (IDCT) upon a matrix of DCT coefficients to thereby construct a video image in a video system comprising: selecting a sub-matrix of DCT coefficients from said matrix of DCT coefficients; performing, in a regional IDCT computation unit, a regional inverse discrete cosine transform algorithm using each coefficient of said sub-matrix of DCT coefficients to derive a first region result; selecting only non-zero DCT coefficients from a remainder of said matrix of DCT coefficients; calculating, in a direct IDCT computation unit, an inverse discrete cosine transform component for each said non-zero DCT coefficient in said remainder; and adding said inverse discrete cosine transform component calculated for each said non-zero IDCT coefficient with said first region result.
Claim 2
Independent Claim
124 words
A method for performing an inverse discrete cosine transform (IDCT) upon a matrix of DCT coefficients to thereby construct a video image in a video system comprising: selecting a sub-matrix of DCT coefficients from said matrix of DCT coefficients; performing, in a regional IDCT computation unit, a regional inverse discrete cosine transform algorithm using each coefficient of said sub-matrix of DCT coefficients to derive a first region result; selecting only non-zero DCT coefficients from a remainder of said matrix of DCT coefficients; calculating, in a direct IDCT computation unit, an inverse discrete cosine transform component for each said non-zero DCT coefficient in said remainder; and adding said inverse discrete cosine transform component calculated for each said non-zero IDCT coefficient with said first region result.
Claim 3
Dependent Claim
30 words
The method for performing an inverse discrete cosine transform as recited in claim 1 further comprising retrieving each DCT coefficient of said matrix of said DCT coefficients from a memory.
Claim 4
Dependent Claim
31 words
The method for performing an inverse discrete cosine transform as recited in claim 1 wherein said remainder includes all DCT coefficients in said matrix other than DCT coefficients in said sub-matrix.
Claim 5
Dependent Claim
41 words
The method for performing an inverse discrete cosine transform as recited in claim 1 wherein said first region result includes an even-even IDCT component class, an even-odd IDCT component class, an odd-even IDCT component class, and an odd-odd IDCT component class.
Claim 6
Dependent Claim
42 words
The method for performing an inverse discrete cosine transform as recited in claim 4 wherein said even-even IDCT component class is calculated using even-row, even-column DCT coefficients within said sub-matrix, and is independent of odd-row and odd-column DCT coefficients of said sub-matrix.
Claim 7
Dependent Claim
100 words
The method for performing an inverse discrete cosine transform as recited in claim 5 wherein said even-odd IDCT component class is calculated using even-row odd-column DCT coefficients within said sub-matrix and is independent of odd-row and even-column DCT coefficients of said sub-matrix, and wherein said odd-even DCT component class is calculated using odd-row, even-column DCT coefficients within said sub-matrix and is independent of even-row and odd-column DCT coefficents of said sub-matrix, and wherein said odd-odd DCT component class is calculated using odd-row, odd-column DCT coefficients within said sub-matrix and is independent of even-row and even-column DCT coefficients of said sub-matrix.
Claim 8
Dependent Claim
27 words
The method for performing an inverse discrete cosine transform as recited in claim 6 wherein an even-operator is applied to each even-column DCT coefficient of said sub-matrix.
Claim 9
Dependent Claim
27 words
The method for performing an inverse discrete cosine transform as recited in claim 7 wherein an odd-operator is applied to each odd-column DCT coefficient of said sub-matrix.
Claim 10
Dependent Claim
42 words
The method for performing an inverse discrete cosine transform as recited in claim 8 wherein said output of said odd-operator applied to each odd-column DCT coefficient is applied to said odd-operator if said each odd-column DCT coefficient is an odd-row DCT coefficient.
Claim 11
Dependent Claim
41 words
The method for performing an inverse discrete cosine transform as recited in claim 9 wherein said output of said even-operator applied to each even-column DCT coefficient is applied to said even-operator if said even-column DCT coefficient is an even-row DCT coefficient.
Claim 12
Dependent Claim
42 words
The method for performing an inverse discrete cosine transform as recited in claim 10 wherein said output of said odd-operator applied to each odd-column DCT coefficient is applied to said even-operator if said each odd-column DCT coefficient is an even-row DCT coefficient.
Claim 13
Dependent Claim
41 words
The method for performing an inverse discrete cosine transform as recited in claim 11 wherein said output of said even-operator applied to each even-column DCT coefficient is applied to said odd-operator if said even-column DCT coefficient is an odd-row DCT coefficient.
Claim 14
Dependent Claim
27 words
The method for performing an inverse discrete cosine transform as recited in claim 6 wherein an even-operator is applied to each even-row DCT coefficient of said sub-matrix.
Claim 15
Dependent Claim
27 words
The method for performing an inverse discrete cosine transform as recited in claim 13 wherein an odd-operator is applied to each odd-row DCT coefficient of said sub-matrix.
Claim 16
Dependent Claim
75 words
The method for performing an inverse discrete cosine transform as recited in claim 5 wherein said inverse discrete cosine transform component calculated for each said non-zero DCT coefficient in said remainder is added to a corresponding one of either said even-even IDCT component class, said even-odd IDCT component class, said odd-even IDCT component class or said odd-odd IDCT component class depending on a row and column of said each non-zero DCT coefficient in said matrix.
Claim 17
Dependent Claim
46 words
The method for performing an inverse discrete cosine transform as recited in claim 15 further comprising, after adding said inverse discrete cosine transform component calculated for each non-zero DCT coefficient to said corresponding IDCT component class, mapping said IDCT component classes to an IDCT output matrix.
Claim 18
Dependent Claim
43 words
The method for performing an inverse discrete cosine transform as recited in claim 16 wherein said mapping of said IDCT component classes to said IDCT output matrix includes mapping a first-quadrant of said output matrix by adding each of said IDCT component classes.
Claim 19
Dependent Claim
101 words
The method for performing an inverse discrete cosine transform as recited in claim 17 wherein said mapping of said IDCT component classes to said full IDCT output matrix includes mapping a second, third, and fourth quadrant of said IDCT output matrix through calculation of the following equations: b(x,y+4)=s.sub.00 (x, 3-y)-s.sub.01 (x, 3-y)+s.sub.10 (x, 3-y)-s.sub.11 (x, 3-y) b(x+4,y)=s.sub.00 (3-x,y)+s.sub.01 (3-x,y)-s.sub.10 (3-x,y)-s.sub.11 (3-x,y) b(x+4, y+4)=s.sub.00 (3-x, 3-y)-s.sub.01 (3-x, 3-y)-s.sub.10 (3-x, 3-y)+s.sub.11 (3-x, 3-y) for x=0,1,2,3 and y=0,1,2,3, and where b(i, ii) represent spatial domain data of said full IDCT output matrix and s i ,ii represent IDCT data of said IDCT component classes.
Claim 20
Dependent Claim
140 words
An inverse discrete cosine transform (IDCT) computation unit for a video system comprising: a regional IDCT computation engine configured to select a sub-matrix of DCT coefficients from a matrix of DCT coefficients and to perform a regional inverse discrete cosine transform algorithm using each coefficient of said sub-matrix of DCT coefficients to derive a first region result; a direct IDCT computation engine configured to select only non-zero DCT coefficients from a remainder of said matrix of DCT coefficients and to calculate an inverse discrete cosine transform component for each said non-zero DCT coefficient in said remainder; and a combine unit coupled to said regional IDCT computation engine and to said direct IDCT computation engine, wherein said combine unit is configured to add said inverse discrete cosine transform component calculated for each said non-zero IDCT coefficient with said first region result.
Claim 21
Dependent Claim
140 words
An inverse discrete cosine transform (IDCT) computation unit for a video system comprising: a regional IDCT computation engine configured to select a sub-matrix of DCT coefficients from a matrix of DCT coefficients and to perform a regional inverse discrete cosine transform algorithm using each coefficient of said sub-matrix of DCT coefficients to derive a first region result; a direct IDCT computation engine configured to select only non-zero DCT coefficients from a remainder of said matrix of DCT coefficients and to calculate an inverse discrete cosine transform component for each said non-zero DCT coefficient in said remainder; and a combine unit coupled to said regional IDCT computation engine and to said direct IDCT computation engine, wherein said combine unit is configured to add said inverse discrete cosine transform component calculated for each said non-zero IDCT coefficient with said first region result.
Claim 22
Dependent Claim
26 words
The IDCT computation unit as recited in claim 19 wherein said remainder includes all DCT coefficients in said matrix other than DCT coefficients in said sub-matrix.
Claim 23
Dependent Claim
36 words
The IDCT computation unit as recited in claim 19 wherein said first region result includes an even-even IDCT component class, an even-odd IDCT component class, an odd-even IDCT component class, and an odd-odd IDCT component class.
Claim 24
Dependent Claim
43 words
The IDCT computation unit as recited in claim 21 wherein said even-even IDCT component class is calculated by said regional IDCT computation engine using even-row, even-column DCT coefficients within said sub-matrix, and is independent of odd-row and odd-column DCT coefficients of said sub-matrix.
Claim 25
Dependent Claim
113 words
The IDCT computation unit as recited in claim 22 wherein said even-odd IDCT component class is calculated by said regional IDCT computation engine using even-row odd-column DCT coefficients within said sub-matrix and is independent of odd-row and even-column DCT coefficients of said sub-matrix, and wherein said odd-even DCT component class is calculated by said regional IDCT computation engine using odd-row, even-column DCT coefficients within said sub-matrix and is independent of even-row and odd-column DCT coefficents of said sub-matrix, and wherein said odd-odd DCT component class is calculated by said regional IDCT computation engine using odd-row, odd-column DCT coefficients within said sub-matrix and is independent of even-row and even-column DCT coefficients of said sub-matrix.
Claim 26
Dependent Claim
29 words
The IDCT computation unit as recited in claim 23 wherein said regional IDCT computation engine is configured to apply an even-operator to each even-column DCT coefficient of said sub-matrix.
Claim 27
Dependent Claim
29 words
The IDCT computation unit as recited in claim 24 wherein said regional IDCT computation engine is configured to apply an odd-operator to each odd-column DCT coefficient of said sub-matrix.
Claim 28
Dependent Claim
37 words
The IDCT computation unit as recited in claim 25 wherein said output of said odd-operator applied to each odd-column DCT coefficient is applied to said odd-operator if said each odd-column DCT coefficient is an odd-row DCT coefficient.
Claim 29
Dependent Claim
36 words
The IDCT computation unit as recited in claim 26 wherein said output of said even-operator applied to each even-column DCT coefficient is applied to said even-operator if said even-column DCT coefficient is an even-row DCT coefficient.
Claim 30
Dependent Claim
37 words
The IDCT computation unit as recited in claim 27 wherein said output of said odd-operator applied to each odd-column DCT coefficient is applied to said even-operator if said each odd-column DCT coefficient is an even-row DCT coefficient.
Claim 31
Dependent Claim
36 words
The IDCT computation unit as recited in claim 28 wherein said output of said even-operator applied to each even-column DCT coefficient is applied to said odd-operator if said even-column DCT coefficient is an odd-row DCT coefficient.
Claim 32
Dependent Claim
29 words
The IDCT computation unit as recited in claim 23 wherein said regional IDCT computation engine is configured to apply an even-operator to each even-row DCT coefficient of said sub-matrix.
Claim 33
Dependent Claim
29 words
The IDCT computation unit as recited in claim 30 wherein said regional IDCT computation engine is configured to apply an odd-operator to each odd-row DCT coefficient of said sub-matrix.
Claim 34
Dependent Claim
75 words
The IDCT computation unit as recited in claim 22 wherein said combine unit is configured to add said inverse discrete cosine transform component calculated for each said non-zero DCT coefficient in said remainder to a corresponding one of either said even-even IDCT component class, said even-odd IDCT component class, said odd-even IDCT component class or said odd-odd IDCT component class depending on a row and column of said each non-zero DCT coefficient in said matrix.
Claim 35
Dependent Claim
40 words
The IDCT computation unit as recited in claim 32 wherein map said IDCT component classes to an IDCT output matrix after adding said inverse discrete cosine transform component calculated for each non-zero DCT coefficient to said corresponding IDCT component class.
Claim 36
Dependent Claim
32 words
The IDCT computation unit as recited in claim 33 wherein said combine unit is further configured to map a first-quadrant of said output matrix by adding each of said IDCT component classes.
Claim 37
Dependent Claim
89 words
The IDCT computation unit as recited in claim 34 wherein said combine unit is further configured to map a second, third, and fourth quadrant of said IDCT output matrix through calculation of the following equations: b(x,y+4)=s.sub.00 (x, 3-y)-s.sub.01 (x, 3-y)+s.sub.10 (x, 3-y)-s.sub.11 (x, 3-y) b(x+4,y)=s.sub.00 (3-x,y)+s.sub.01 (3-x,y)-s.sub.10 (3-x,y)-s.sub.11 (3-x,y) b(x+4, y+4)=s.sub.00 (3-x, 3-y)-s.sub.01 (3-x, 3-y)-s.sub.10 (3-x, 3-y)+s.sub.11 (3-x, 3-y) for x=0,1,2,3 and y=0,1,2,3, and where b(i, ii) represent spatial domain data of said full IDCT output matrix and s i ,ii represent IDCT data of said IDCT component classes.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-15 | 2002-09-14 | 2003-03-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-15 | 2006-09-14 | 2007-03-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-15 | 2010-09-14 | 2011-03-16 | $7700.00 | Window Closed / Lapsed |