US5426673A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Discrete cosine transform-based image coding and decoding method
Assignee: University of California, San Diego
•
Filing: 1994-02-09
•
Granted: 1995-06-20
•
Expires: 2014-02-09
Abstract
Abstract A fast discrete cosine transform (DCT) based method of encoding and decoding signals is disclosed. A signal of finite length is decomposed into subsignals of shorter length and an approximate DCT (A-DCT) is computed by keeping only selected subsignals. Computation time decreases relative to the number of subsignals being used to compute the A-DCT, fewer subsignals resulting in a faster computation. For signal compression applications, the computed A-DCT coefficients are quantized and coded. For signal recovery, the encoded A-DCT coefficients are processed through a decoder and the decoded signal is recovered using a direct inverse DCT (I-DCT). In some applications, an approximate inverse DCT (AI-DCT) based on similar decomposition can be used to recover the signal from the encoded data. In image coding applications, the image recovered from the decoded signal exhibits negligible block artifacts compared to conventional JPEG, particularly for low bit rate compression.
Inventors
- 👤 Sanjit K. Mitra
- 👤 Sung-Hwan Jung
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 17:14
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/85; H04N19/86; H04N19/10; H04N19/102; H04N19/124; H04N19/126; H04N19/60; H04N19/63
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
106 words
A method for processing digital signals, comprising the steps of: (a) providing a digital signal; (b) decomposing said digital signal into a plurality of subbands, said subbands including one or more dominant frequency subbands; (c) discarding subbands other than said dominant frequency subbands and performing a discrete cosine transform on said dominant frequency subbands; (d) weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital signal to produce an approximate discrete cosine transform of said digital signal; and encoding said digital signal using coefficients from said approximate discrete cosine transform.
Claim 2
Independent Claim
106 words
A method for processing digital signals, comprising the steps of: (a) providing a digital signal; (b) decomposing said digital signal into a plurality of subbands, said subbands including one or more dominant frequency subbands; (c) discarding subbands other than said dominant frequency subbands and performing a discrete cosine transform on said dominant frequency subbands; (d) weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital signal to produce an approximate discrete cosine transform of said digital signal; and encoding said digital signal using coefficients from said approximate discrete cosine transform.
Claim 3
Dependent Claim
41 words
A method as recited in claim 1, wherein said digital signal has a size of N data points and said digital signal is decomposed into M subbands, where N is an integer, M is an integer, M=2 L and L=an integer.
Claim 4
Dependent Claim
32 words
A method as recited in claim 1, further comprising the steps of performing an inverse discrete cosine transform on said encoded digital signal using said coefficients and decoding said encoded digital signal.
Claim 5
Dependent Claim
112 words
A method as recited in claim 1, wherein said step of discarding subbands other than said dominant subbands and performing a discrete cosine transform on said dominant frequency subbands comprises the step of performing an approximate discrete cosine transform of said digital signal according to ##EQU12## where said digital signal has a size of N data points, N is an integer, C is the approximate discrete cosine transform of said digital signal, C g is the (N/2)-point discrete cosine transform of subsequence g(n), g(n)=1/2␣x(2n)+x(2n+1} for n=0, 1, . . . (N/2)-1, x(n) is the N-point data sequence of said digital input signal, and said dominant frequency subband is a low frequency subband.
Claim 6
Dependent Claim
112 words
A method as recited in claim 1, wherein said step of discarding subbands other than said dominant frequency subbands and performing a discrete cosine transform on said dominant frequency subbands comprises the step of performing an approximate discrete cosine transform of said digital signal according to ##EQU13## where said digital signal has a size of N data points, N is an integer, C is the approximate discrete cosine transform of said digital signal, S h is the (N/2)-point discrete cosine transform of subsequence h(n), h(n)=1/2{x(2n)-x(2n+1)} for n=0, 1, . . . (N/2)-1, x(n) is the N-point data sequence of the digital signal, and said dominant frequency subband is a high frequency subband.
Claim 7
Dependent Claim
60 words
A method as recited in claim 3, wherein said inverse discrete cosine transform is performed on said encoded signal according to: ##EQU14## where said digital signal has a size of N data points, N is an integer, x(n) is the N-point data sequence of said digital signal, C(k) is the discrete cosine transform of x(n), ζ(0)=1/2 and ζ(k)=1 for 1<k<N-1.
Claim 8
Dependent Claim
72 words
A method as recited in claim 3, wherein said inverse discrete cosine transform is performed on said encoded signal according to: ##EQU15## where said digital signal has a size of N data points, N is an integer, x(n) is the approximate N-point data sequence of said digital signal, C (k) is the approximate discrete cosine transform of the N-point data sequence x(n) of said digital input signal, ζ(0)=1/2 and ζ(k)=1 for 1<k<N-1.
Claim 9
Independent Claim
174 words
A method for processing a digital image signal, comprising the steps of: (a) extracting a plurality of subband blocks from said digital image signal, said subband blocks including a low-low frequency subband block; (b) discarding subband blocks other than said low-low frequency subband block, performing a discrete cosine transform on said low-low frequency subband block, and weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital signal to produce an approximate discrete cosine transform of said digital signal according to ##EQU16## where said digital image signal has a size of N data points, N is an integer, C is the approximate discrete cosine transform of said digital image signal, C g is the (N/2)-point discrete cosine transform of subsequence g(n), g(n)=1/2{x(2n)+x(2n+1)} for n=0, 1, . . . (N/2)-1, x(n) is the N-point data sequence of the digital image signal; and (c) encoding said digital image signal using discrete cosine transform coefficients corresponding to said low-low frequency subband block.
Claim 10
Independent Claim
174 words
A method for processing a digital image signal, comprising the steps of: (a) extracting a plurality of subband blocks from said digital image signal, said subband blocks including a low-low frequency subband block; (b) discarding subband blocks other than said low-low frequency subband block, performing a discrete cosine transform on said low-low frequency subband block, and weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital signal to produce an approximate discrete cosine transform of said digital signal according to ##EQU16## where said digital image signal has a size of N data points, N is an integer, C is the approximate discrete cosine transform of said digital image signal, C g is the (N/2)-point discrete cosine transform of subsequence g(n), g(n)=1/2{x(2n)+x(2n+1)} for n=0, 1, . . . (N/2)-1, x(n) is the N-point data sequence of the digital image signal; and (c) encoding said digital image signal using discrete cosine transform coefficients corresponding to said low-low frequency subband block.
Claim 11
Dependent Claim
35 words
A method as recited in claim 8, wherein said digital image signal has a size of N×N data points where N is an integer and said digital image signal is decomposed into four subband blocks.
Claim 12
Dependent Claim
80 words
A method as recited in claim 9, wherein said step of performing an approximate discrete cosine transform on said digital image signal includes the step of performing an N/2×N/2-point discrete cosine transform on said N/2×N/2 low-low frequency subband block and weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital image signal to produce an approximate discrete cosine transform of said digital image signal.
Claim 13
Dependent Claim
76 words
A method as recited in claim 10, further comprising the steps of: (a) decoding said encoded digital image signal; and (b) performing an inverse discrete cosine transform on said decoded digital image signal according to ##EQU17## where said digital image signal has a size of N data points, N is an integer, x(n) is the N-point data sequence of said digital image signal, C(k) is the discrete cosine transform of x(n), ζ(0)=1/2 and ζ(k)=1 for 1≦k≦N-1.
Claim 14
Dependent Claim
85 words
A method as recited in claim 10, further comprising the steps of: (a) decoding said encoded digital image signal; and (b) performing an inverse discrete cosine transform on said decoded signal according to ##EQU18## where said digital image signal has a size of N data points, N is an integer, x(n) is the approximate N-point data sequence of said digital image signal, C(k) is the approximate discrete cosine transform of the N-point data sequence x(n) of said digital image signal, ζ(0)=1/2 and ζ(k)=1 for 1≦k≦N-1.
Claim 15
Independent Claim
252 words
A method for encoding and decoding low bit rate image signals, comprising the steps of: (a) providing a digital image signal; (b) extracting a plurality of subband blocks from said digital image signal, said subband blocks including a low-low frequency subband block; (c) discarding subband blocks other than said low-low frequency subband block, performing a discrete cosine transform on said low-low frequency subband block, and weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital image signal to produce an approximate discrete cosine transform of said digital image signal according to ##EQU19## where said digital image signal has a size of N data points, N is an integer, C is the approximate discrete cosine transform of said digital image signal, C g is the (N/2)-point discrete cosine transform of subsequence g(n), g(n)=1/2{x(2n)+x(2n+1)} for n=0, 1, . . . (N/2)-1, x(n) is the n-point data sequence of the digital image signal; (d) encoding said digital image signal using discrete cosine transform coefficients corresponding to said low-low frequency subband block; and (e) decoding said encoded digital image signal; and (f) performing an inverse discrete cosine transform on said decoded digital image signal using said coefficients according to ##EQU20## where said digital image signal has a size of N data points, N is an integer, x(n) is the N-point data sequence of said digital image signal, C(k) is the discrete cosine transform of x(n), ζ(0)=1/2 and ζ(k)=1 for 1≦k≦N-1.
Claim 16
Independent Claim
252 words
A method for encoding and decoding low bit rate image signals, comprising the steps of: (a) providing a digital image signal; (b) extracting a plurality of subband blocks from said digital image signal, said subband blocks including a low-low frequency subband block; (c) discarding subband blocks other than said low-low frequency subband block, performing a discrete cosine transform on said low-low frequency subband block, and weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital image signal to produce an approximate discrete cosine transform of said digital image signal according to ##EQU19## where said digital image signal has a size of N data points, N is an integer, C is the approximate discrete cosine transform of said digital image signal, C g is the (N/2)-point discrete cosine transform of subsequence g(n), g(n)=1/2{x(2n)+x(2n+1)} for n=0, 1, . . . (N/2)-1, x(n) is the n-point data sequence of the digital image signal; (d) encoding said digital image signal using discrete cosine transform coefficients corresponding to said low-low frequency subband block; and (e) decoding said encoded digital image signal; and (f) performing an inverse discrete cosine transform on said decoded digital image signal using said coefficients according to ##EQU20## where said digital image signal has a size of N data points, N is an integer, x(n) is the N-point data sequence of said digital image signal, C(k) is the discrete cosine transform of x(n), ζ(0)=1/2 and ζ(k)=1 for 1≦k≦N-1.
Claim 17
Dependent Claim
27 words
A method as recited in claim 13, wherein said digital image signal has a size N×N and said digital image signal is decomposed into four subband blocks.
Claim 18
Dependent Claim
79 words
A method as recited in claim 14, wherein said step of performing a discrete cosine transform on said digital image signal includes the step of performing an N/2×N/2-point discrete cosine transform on said N/2×N/2 low-low frequency subband block and weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital image signal to produce an approximate discrete cosine transform of said digital image signal.
Claim 19
Independent Claim
114 words
An apparatus for processing digital signals, comprising: (a) means for providing a digital signal; (b) means for decomposing said digital signal into a plurality of subbands, said subbands including one or more dominant frequency subbands; (c) means for discarding subbands other than said dominant frequency subbands and performing a discrete cosine transform on said dominant frequency subbands; (d) means for weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital signal to produce an approximate discrete cosine transform of said digital signal; and (e) means for encoding said digital signal using coefficients from said approximate discrete cosine transform.
Claim 20
Independent Claim
114 words
An apparatus for processing digital signals, comprising: (a) means for providing a digital signal; (b) means for decomposing said digital signal into a plurality of subbands, said subbands including one or more dominant frequency subbands; (c) means for discarding subbands other than said dominant frequency subbands and performing a discrete cosine transform on said dominant frequency subbands; (d) means for weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital signal to produce an approximate discrete cosine transform of said digital signal; and (e) means for encoding said digital signal using coefficients from said approximate discrete cosine transform.
Claim 21
Dependent Claim
29 words
An apparatus as recited in claim 16, further comprising means for performing an inverse discrete cosine transform on said encoded signal using said coefficients and decoding said encoded signal.
Claim 22
Independent Claim
177 words
An apparatus for processing a digital image signal, comprising: (a) means for extracting a plurality of subband blocks from said digital image signal, said subband blocks including a low-low frequency subband block; (b) means for discarding subband blocks other than said low-low frequency subband block, performing a discrete cosine transform on said low-low frequency subband block, and weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital signal to produce an approximate discrete cosine transform of said digital signal according to ##EQU21## where said digital image signal has a size of N data points, N is an integer, C is the approximate discrete cosine transform of said digital image signal, C g is the (N/2)-point discrete cosine transform of subsequence g(n), g(n)=1/2{x(2n)+x(2n+1)} for n=0, 1, . . . (N/2)-1, x(n) is the N-point data sequence of the digital image signal; and (c) means for encoding said digital image signal using discrete cosine transform coefficients corresponding to said low-low frequency subband block.
Claim 23
Independent Claim
177 words
An apparatus for processing a digital image signal, comprising: (a) means for extracting a plurality of subband blocks from said digital image signal, said subband blocks including a low-low frequency subband block; (b) means for discarding subband blocks other than said low-low frequency subband block, performing a discrete cosine transform on said low-low frequency subband block, and weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital signal to produce an approximate discrete cosine transform of said digital signal according to ##EQU21## where said digital image signal has a size of N data points, N is an integer, C is the approximate discrete cosine transform of said digital image signal, C g is the (N/2)-point discrete cosine transform of subsequence g(n), g(n)=1/2{x(2n)+x(2n+1)} for n=0, 1, . . . (N/2)-1, x(n) is the N-point data sequence of the digital image signal; and (c) means for encoding said digital image signal using discrete cosine transform coefficients corresponding to said low-low frequency subband block.
Claim 24
Dependent Claim
73 words
An apparatus as recited in claim 18, further comprising means for decoding said encoded digital image signal and performing an inverse discrete cosine transform on said decoded digital image signal according to ##EQU22## where said digital image signal has a size of N data points, N is an integer, x(n) is the N-point data sequence of said digital image signal, C(k) is the discrete cosine transform of x(n), ζ(0)=1/2 and ζ(k)=1 for 1≦k≦N-1.
Claim 25
Independent Claim
260 words
An apparatus for encoding and decoding low bit rate image signals, comprising: (a) means for providing a digital image signal; (b) means for extracting a plurality of subband blocks from said digital image signal, said subband blocks including a low-low frequency subband block; (c) means for discarding subband blocks other than said low-low frequency subband block, performing a discrete cosine transform on said low-low frequency subband block, and weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital image signal to produce an approximate discrete cosine transform of said digital image signal according to ##EQU23## where said digital image signal has a size of N data points, N is an integer, C is the approximate discrete cosine transform of said digital image signal, C g is the (N/2)-point discrete cosine transform of subsequence g(n), g(n)=1/2{x(2n)+x(2n+1)} for n=0, 1, . . . (N/2)-1, x(n) is the N-point data sequence of the digital image signal; (d) means for encoding said digital image signal using discrete cosine transform coefficients corresponding to said low-low frequency subband block; (e) means for decoding said encoded digital image signal; and (f) means for performing an inverse discrete cosine transform on said decoded digital image signal using said coefficients according to ##EQU24## where said digital image signal has a size of N data points, N is an integer, x(n) is the N-point data sequence of said digital image signal, C(k) is the discrete cosine transform of x(n), ζ(0)=1/2 and ζ(k)=1 for 1≦k≦N-1.
Claim 26
Independent Claim
260 words
An apparatus for encoding and decoding low bit rate image signals, comprising: (a) means for providing a digital image signal; (b) means for extracting a plurality of subband blocks from said digital image signal, said subband blocks including a low-low frequency subband block; (c) means for discarding subband blocks other than said low-low frequency subband block, performing a discrete cosine transform on said low-low frequency subband block, and weighting the coefficients from said discrete cosine transform to make them as close as possible to coefficients for an exact discrete cosine transform of said digital image signal to produce an approximate discrete cosine transform of said digital image signal according to ##EQU23## where said digital image signal has a size of N data points, N is an integer, C is the approximate discrete cosine transform of said digital image signal, C g is the (N/2)-point discrete cosine transform of subsequence g(n), g(n)=1/2{x(2n)+x(2n+1)} for n=0, 1, . . . (N/2)-1, x(n) is the N-point data sequence of the digital image signal; (d) means for encoding said digital image signal using discrete cosine transform coefficients corresponding to said low-low frequency subband block; (e) means for decoding said encoded digital image signal; and (f) means for performing an inverse discrete cosine transform on said decoded digital image signal using said coefficients according to ##EQU24## where said digital image signal has a size of N data points, N is an integer, x(n) is the N-point data sequence of said digital image signal, C(k) is the discrete cosine transform of x(n), ζ(0)=1/2 and ζ(k)=1 for 1≦k≦N-1.
References Cited (Backward Citations)
US4943855A
Cited
US5068744A
Cited
US5297236A
Cited
US5247357A
Cited
US5305115A
Cited
US5006929A
Cited
US4974078A
Cited
US5107348A
Cited
US5216518A
Cited
US5235434A
Cited
US5168375A
Cited
US5231485A
Cited
US5309232A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-06-19 | 1998-12-19 | 1999-06-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-06-19 | 2002-12-19 | 2003-06-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-06-19 | 2006-12-19 | 2007-06-20 | $7700.00 | Window Closed / Lapsed |