US5523847A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Digital image processor for color image compression
Assignee: International Business Machines Corp
•
Filing: 1992-10-09
•
Granted: 1996-06-04
•
Expires: 2012-10-09
Abstract
Abstract The objects of this invention are accomplished by rearranging the DCT process such that non-trivial multiplications are combined in a single process step. In particular, the DCT equations for the application of the two-dimensional DCT process on k×k points are factored into 1) a permutation matrix, 2) a diagonal matrix, and 3) a matrix whose product with an arbitrary vector having k 2 points requires considerably fewer non-trivial multiplications. Furthermore, in some cases none of these non-trivial multiplications are nested; that is, no output of a non-trivial multiplication is ever involved in another multiplication operation. The diagonal matrix is not unique for any set of data. Once the diagonal matrix elements are chosen the remaining factors are developed. When the factorization is complete, the diagonal matrix is absorbed into the quantization step which follows the DCT process. The quantization step is the multiplication of a diagonal matrix by the DCT output data. The quantization diagonal matrix is combined with the diagonal matrix of the DCT to form one multiplication process by which non-trivial elements multiply data. This combination of multiplication steps reduces the number of non-trivial multiplications in the DCT process. In addition, the non-trivial multiplications are approximated by multiplications by rational numbers, whose computation is achieved with additions, subtractions and shift operations (multiplications by powers of 2). This approximation procedure offers greater numerical accuracy than a procedure based upon approximating the multiplication factors of a standard DCT process with rational factors because the number of non-trivial multiplications have been minimized and none are nested. Furthermore, if the quantization constants are chosen so that they are all either powers of 2 or sums and differences of powers of 2, then the quantization process itself can be achieved with either shifts only or with shifts and additions and subtractions only. Finally, the same reduction in non-trivial multiplications is provided for the inverse DCT and dequantization process.
Inventors
- 👤 Ephraim Feig
- 👤 Elliot N. Linzer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 06:22
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/147; G06T; G06T9/00; G06T9/008
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
131 words
A method for transmitting an image over a data channel, comprising: converting signals representing an image into RGB form data; transforming said RGB form data into YUV data; converting said YUV data into DCT data by multiplying a factored transform matrix F k to a plurality of subsets of said YUV data having k points wherein: A.sub.k =D.sub.k F.sub.k ; A k is a transform matrix converting subsets of YUV data into DCT data; and D k is a k×k diagonal matrix; absorbing D k into a matrix having elements η ij to form a quantization matrix having elements η ij ; quantizing said DCT data with said quantization matrix; converting said quantized DCT data into signals for transmission over said data channel; and applying said signals to said data channel.
Claim 2
Independent Claim
131 words
A method for transmitting an image over a data channel, comprising: converting signals representing an image into RGB form data; transforming said RGB form data into YUV data; converting said YUV data into DCT data by multiplying a factored transform matrix F k to a plurality of subsets of said YUV data having k points wherein: A.sub.k =D.sub.k F.sub.k ; A k is a transform matrix converting subsets of YUV data into DCT data; and D k is a k×k diagonal matrix; absorbing D k into a matrix having elements η ij to form a quantization matrix having elements η ij ; quantizing said DCT data with said quantization matrix; converting said quantized DCT data into signals for transmission over said data channel; and applying said signals to said data channel.
Claim 3
Dependent Claim
39 words
A method for transmitting an image over a data channel, as in claim 1, wherein: D k is the k×k diagonal matrix in which the jj-th element is the first entry in the j-th row of A k .
Claim 4
Dependent Claim
38 words
A method for transmitting an image over a data channel, as in claim 1, wherein: a (jk+i)-th element of D k ○ × D k is absorbed to form said quantization matrix, wherein ○ × is tensor multiplication.
Claim 5
Dependent Claim
26 words
A method for transmitting an image over a data channel, as in claim 3, wherein: non rational elements of F k are approximated by rational elements.
Claim 6
Dependent Claim
30 words
A method for transmitting an image over a data channel, as in claim 4, wherein: a function of multiplying by a rational number is implemented by shift and add operations.
Claim 7
Independent Claim
159 words
A method for transmitting an image over a data channel, comprising: converting signals representing an image into RGB form data; transforming said RGB form data into YUV data; converting said YUV data into DCT data by multiplying a factored transform matrix F k ○ × F k by a plurality of subsets of said YUV data having k 2 points wherein: A.sub.k ○ × A.sub.k =(D.sub.k ○ × D.sub.k)(F.sub.k ○ × F.sub.k); A k ○ × A k is a transform matrix for converting subsets of YUV data into DCT data; and D k ○ × D k is a k 2 ×k 2 diagonal matrix; absorbing D k ○ × D k into a matrix having elements η ij to form a quantization matrix having elements η ij ; quantizing said DCT data with said quantization matrix; converting said quantized DCT data into signals for transmission over said data channel; and applying said signals to said data channel.
Claim 8
Independent Claim
159 words
A method for transmitting an image over a data channel, comprising: converting signals representing an image into RGB form data; transforming said RGB form data into YUV data; converting said YUV data into DCT data by multiplying a factored transform matrix F k ○ × F k by a plurality of subsets of said YUV data having k 2 points wherein: A.sub.k ○ × A.sub.k =(D.sub.k ○ × D.sub.k)(F.sub.k ○ × F.sub.k); A k ○ × A k is a transform matrix for converting subsets of YUV data into DCT data; and D k ○ × D k is a k 2 ×k 2 diagonal matrix; absorbing D k ○ × D k into a matrix having elements η ij to form a quantization matrix having elements η ij ; quantizing said DCT data with said quantization matrix; converting said quantized DCT data into signals for transmission over said data channel; and applying said signals to said data channel.
Claim 9
Dependent Claim
50 words
A method for transmitting an image over a data channel, as in claim 6, wherein: D k ○ × D k is the k 2 ×k 2 diagonal matrix in which the jj-th element is the first entry in the j-th row of A k ○ × A k .
Claim 10
Dependent Claim
32 words
A method for transmitting an image over a data channel, as in claim 6, wherein: a (jk+i)-th element of D k ○ × D k is absorbed to form said quantization matrix.
Claim 11
Dependent Claim
29 words
A method for transmitting an image over a data channel, as in claim 8, wherein: non-rational elements of F k ○ × F k are approximated by rational elements.
Claim 12
Dependent Claim
30 words
A method for transmitting an image over a data channel, as in claim 9, wherein: a function of multiplying by a rational number is implemented by shift and add operations.
Claim 13
Independent Claim
135 words
A method for generating an image, comprising: sensing signals representing said image from a data channel; decoding said sensed signals into DCT form data; absorbing a diagonal matrix D k into a matrix having elements η ij to form a dequantization matrix having elements η ij ; dequantizing said DCT form data with said dequantization matrix; converting said DCT data into YUV data by multiplying a plurality of subsets of said DCT data having k points by a factored transform matrix F k t , wherein: A.sub.k.sup.-1 =F.sub.k.sup.t D.sub.k ; A k -1 is a transform matrix for converting subsets of DCT data into YUV data; and D k is a k×k diagonal matrix; converting said YUV data into RGB form data; and applying said RGB form data to a display to generate said image.
Claim 14
Independent Claim
135 words
A method for generating an image, comprising: sensing signals representing said image from a data channel; decoding said sensed signals into DCT form data; absorbing a diagonal matrix D k into a matrix having elements η ij to form a dequantization matrix having elements η ij ; dequantizing said DCT form data with said dequantization matrix; converting said DCT data into YUV data by multiplying a plurality of subsets of said DCT data having k points by a factored transform matrix F k t , wherein: A.sub.k.sup.-1 =F.sub.k.sup.t D.sub.k ; A k -1 is a transform matrix for converting subsets of DCT data into YUV data; and D k is a k×k diagonal matrix; converting said YUV data into RGB form data; and applying said RGB form data to a display to generate said image.
Claim 15
Dependent Claim
39 words
A method for generating an image, as in claim 11, wherein: D k is the k×k diagonal matrix in which the jj-th element is an inverse of a first entry in a j-th row of A k -1 .
Claim 16
Dependent Claim
34 words
A method for generating an image, as in claim 11, wherein: a (jk+i)-th element of D k ○ × D k is absorbed to form said dequantization matrix, wherein ○ × is tensor multiplication.
Claim 17
Dependent Claim
22 words
A method for generating an image, as in claim 13, wherein: non-rational elements of F k t are approximated by rational elements.
Claim 18
Dependent Claim
26 words
A method for generating an image, as in claim 14, wherein: a function of multiplying by a rational number is implemented by shift and add operations.
Claim 19
Independent Claim
135 words
A method for generating an image, comprising: sensing signals representing said image from a data channel; decoding said sensed signals into DCT form data; absorbing a diagonal matrix D k -1 into a matrix having elements η ij to form a dequantization matrix having elements η ij ; dequantizing said DCT form data with said dequantization matrix; converting said DCT data into YUV data by multiplying a plurality of subsets of said DCT data having k points by a factored transform matrix F k t wherein: A.sub.k.sup.-1 =F.sub.k.sup.-1 D.sub.k.sup.-1 ; A k -1 is a transform matrix for converting subsets of DCT data into YUV data; and D k -1 is a k×k diagonal matrix; converting said YUV data into RGB form data; and applying said RGB data to a display to generate said image.
Claim 20
Independent Claim
135 words
A method for generating an image, comprising: sensing signals representing said image from a data channel; decoding said sensed signals into DCT form data; absorbing a diagonal matrix D k -1 into a matrix having elements η ij to form a dequantization matrix having elements η ij ; dequantizing said DCT form data with said dequantization matrix; converting said DCT data into YUV data by multiplying a plurality of subsets of said DCT data having k points by a factored transform matrix F k t wherein: A.sub.k.sup.-1 =F.sub.k.sup.-1 D.sub.k.sup.-1 ; A k -1 is a transform matrix for converting subsets of DCT data into YUV data; and D k -1 is a k×k diagonal matrix; converting said YUV data into RGB form data; and applying said RGB data to a display to generate said image.
Claim 21
Dependent Claim
40 words
A method for generating an image, as in claim 16, wherein: D k -1 is the k×k diagonal matrix in which the jj-th element is an inverse of a first entry in a j-th row of A k -1 .
Claim 22
Dependent Claim
36 words
A method for generating an image, as in claim 16, wherein: a (jk+i)-th element of D k -1 ○ × D k -1 is absorbed to form said dequantization matrix, wherein ○ × is tensor multiplication.
Claim 23
Dependent Claim
22 words
A method for generating an image, as in claim 18, wherein: non-rational elements of F k -1 are approximated by rational elements.
Claim 24
Dependent Claim
26 words
A method for generating an image, as in claim 19, wherein: a function of multiplying by a rational number is implemented by shift and add operations.
Claim 25
Independent Claim
160 words
A method for generating an image, comprising: sensing signals representing said image from a data channel; decoding said sensed signals into DCT form data; absorbing a diagonal matrix D k into a matrix having elements η ij to form a dequantization matrix having elements η ij ; dequantizing said DCT form data with said dequantization matrix; converting said DCT data into YUV data by multiplying a plurality of subsets of said DCT data having k 2 points by a factored transform matrix F k t ○ × F k t , wherein: A.sub.k.sup.-1 ○ × A.sub.k.sup.-1 =(F.sub.k.sup.t ○ × F.sub.k.sup.t)(D.sub.k ○ × D.sub.k); A k -1 ○ × A k -1 is a transform matrix for converting subsets of DCT data into YUV data; and D k ○ × D k is a k 2 ×k 2 diagonal matrix; converting said YUV data into RGB form data; and applying said RGB form data to a display to generate said image.
Claim 26
Independent Claim
160 words
A method for generating an image, comprising: sensing signals representing said image from a data channel; decoding said sensed signals into DCT form data; absorbing a diagonal matrix D k into a matrix having elements η ij to form a dequantization matrix having elements η ij ; dequantizing said DCT form data with said dequantization matrix; converting said DCT data into YUV data by multiplying a plurality of subsets of said DCT data having k 2 points by a factored transform matrix F k t ○ × F k t , wherein: A.sub.k.sup.-1 ○ × A.sub.k.sup.-1 =(F.sub.k.sup.t ○ × F.sub.k.sup.t)(D.sub.k ○ × D.sub.k); A k -1 ○ × A k -1 is a transform matrix for converting subsets of DCT data into YUV data; and D k ○ × D k is a k 2 ×k 2 diagonal matrix; converting said YUV data into RGB form data; and applying said RGB form data to a display to generate said image.
Claim 27
Dependent Claim
51 words
A method for generating an image, as in claim 21, wherein: D k ○ × D k is the k 2 ×k 2 diagonal matrix in which the jj-th element is an inverse of a first entry in a j-th row of A k -1 ○ × A k -1 -k.
Claim 28
Dependent Claim
28 words
A method for generating an image, as in claim 21, wherein: a (jk+i)-th element of D k ○ × D k is absorbed to form said dequantization matrix.
Claim 29
Dependent Claim
27 words
A method for generating an image, as in claim 23, wherein: non-rational elements of F k t ○ × F k t are approximated by rational elements.
Claim 30
Dependent Claim
26 words
A method for generating an image, as in claim 24, wherein: a function of multiplying by a rational number is implemented by shift and add operations.
Claim 31
Independent Claim
161 words
A method for generating an image, comprising: sensing signals representing said image from a data channel; decoding said sensed signals into DCT form data; absorbing a diagonal matrix D k -1 into a matrix having elements η ij to form a dequantization matrix having elements η ij ; dequantizing said DCT form data with said dequantization matrix; converting said DCT data into YUV data by multiplying a plurality of subsets of said DCT data having k 2 points by a factored transform matrix F k -1 ○ × F k -1 wherein: A.sub.k.sup.-1 ○ × A.sub.k.sup.-1 =(F.sub.k.sup.-1 ○ × F.sub.k.sup.-1)(D.sub.k.sup.-1 ○ × D.sub.k.sup.-1); A k -1 ○ × A k -1 is a transform matrix for converting subsets of DCT data into YUV data; and D k -1 ○ × D k -1 is a k 2 ×k 2 diagonal matrix; converting said YUV data into RGB form data; and applying said RGB data to a display to generate said image.
Claim 32
Independent Claim
161 words
A method for generating an image, comprising: sensing signals representing said image from a data channel; decoding said sensed signals into DCT form data; absorbing a diagonal matrix D k -1 into a matrix having elements η ij to form a dequantization matrix having elements η ij ; dequantizing said DCT form data with said dequantization matrix; converting said DCT data into YUV data by multiplying a plurality of subsets of said DCT data having k 2 points by a factored transform matrix F k -1 ○ × F k -1 wherein: A.sub.k.sup.-1 ○ × A.sub.k.sup.-1 =(F.sub.k.sup.-1 ○ × F.sub.k.sup.-1)(D.sub.k.sup.-1 ○ × D.sub.k.sup.-1); A k -1 ○ × A k -1 is a transform matrix for converting subsets of DCT data into YUV data; and D k -1 ○ × D k -1 is a k 2 ×k 2 diagonal matrix; converting said YUV data into RGB form data; and applying said RGB data to a display to generate said image.
Claim 33
Dependent Claim
53 words
A method for generating an image, as in claim 26, wherein: D k -1 ○ × D k -1 is the k 2 ×k 2 diagonal matrix in which the jj-th element is an inverse of a first entry in a j-th row of A k -1 ○ × A k -1 .
Claim 34
Dependent Claim
30 words
A method for generating an image, as in claim 26, wherein: a (jk+i)-th element of D k -1 ○ × D k -1 is absorbed to form said dequantization matrix.
Claim 35
Dependent Claim
27 words
A method for generating an image, as in claim 28, wherein: non-rational elements of F k -1 ○ × F k -1 are approximated by rational elements.
Claim 36
Dependent Claim
26 words
A method for generating an image, as in claim 29, wherein: a function of multiplying by a rational number is implemented by shift and add operations.
Claim 37
Dependent Claim
178 words
An image transmitter, comprising: an RGB data generator for representing an image with RGB form data; an RGB to YUV transformer coupled to said RGB data generator for converting said RGB form data into YUV form data; a YUV to DCT transformer coupled to said RGB to YUV transformer for converting said YUV data into DCT form data by multiplying a factored transform matrix F k by a plurality of subsets of said YUV data having k points wherein: A.sub.k =D.sub.k F.sub.k ; A k is a transform matrix for converting subsets of YUV data into DCT data; and D k is a k×k diagonal matrix; a quantization means coupled to said YUV to DCT transformer for quantizing said DCT data with a quantization matrix having elements η ij and generated by absorbing D k into a matrix having elements η ij ; and a driver means coupled to said quantization means and a data channel for converting said quantized DCT data into signals for transmission over said data channel and applying said signals to said data channel.
Claim 38
Dependent Claim
178 words
An image transmitter, comprising: an RGB data generator for representing an image with RGB form data; an RGB to YUV transformer coupled to said RGB data generator for converting said RGB form data into YUV form data; a YUV to DCT transformer coupled to said RGB to YUV transformer for converting said YUV data into DCT form data by multiplying a factored transform matrix F k by a plurality of subsets of said YUV data having k points wherein: A.sub.k =D.sub.k F.sub.k ; A k is a transform matrix for converting subsets of YUV data into DCT data; and D k is a k×k diagonal matrix; a quantization means coupled to said YUV to DCT transformer for quantizing said DCT data with a quantization matrix having elements η ij and generated by absorbing D k into a matrix having elements η ij ; and a driver means coupled to said quantization means and a data channel for converting said quantized DCT data into signals for transmission over said data channel and applying said signals to said data channel.
Claim 39
Dependent Claim
193 words
A image receiver, comprising: a sensor for sensing coded data from a data channel; a decoder coupled to said sensor for decoding data sensed from said data channel into DCT form data; a dequantizer coupled to said decoder for quantizing said DCT form data from said decoder with a dequantization matrix, said dequantization matrix formed by absorbing a diagonal matrix D k into a matrix having elements η ij to form said dequantization matrix having element η ij , a DCT to YUV transformer coupled to said dequantizer for converting dequantized DCT data from said dequantizer into YUV form data by multiplying a factored transform matrix F k t by a plurality of subsets of said dequantized DCT data having k points wherein: A.sub.k.sup.-1 =D.sub.k F.sub.k.sup.t ; A k -1 is a transform matrix for converting subsets of DCT data into YUV data; and D k is a k×k diagonal matrix; a YUV to RGB transformer coupled to said DCT to YUV transformer for conveying YUV data from said DCT to YUV transformer into RGB form data; and a driver for applying said RGB form data to a display to generate said image.
Claim 40
Dependent Claim
193 words
A image receiver, comprising: a sensor for sensing coded data from a data channel; a decoder coupled to said sensor for decoding data sensed from said data channel into DCT form data; a dequantizer coupled to said decoder for quantizing said DCT form data from said decoder with a dequantization matrix, said dequantization matrix formed by absorbing a diagonal matrix D k into a matrix having elements η ij to form said dequantization matrix having element η ij , a DCT to YUV transformer coupled to said dequantizer for converting dequantized DCT data from said dequantizer into YUV form data by multiplying a factored transform matrix F k t by a plurality of subsets of said dequantized DCT data having k points wherein: A.sub.k.sup.-1 =D.sub.k F.sub.k.sup.t ; A k -1 is a transform matrix for converting subsets of DCT data into YUV data; and D k is a k×k diagonal matrix; a YUV to RGB transformer coupled to said DCT to YUV transformer for conveying YUV data from said DCT to YUV transformer into RGB form data; and a driver for applying said RGB form data to a display to generate said image.
References Cited (Backward Citations)
US4152772A
Cited
US3920974A
Cited
US3971927A
Cited
US4196448A
Cited
US4385363A
Cited
US4675836A
Cited
US4679163A
Cited
US4841464A
Cited
US4797847A
Cited
US4805017A
Cited
US4829465A
Cited
US4791598A
Cited
US5029122A
Cited
US5001559A
Cited
US4974078A
Cited
US5021891A
Cited
US5253078A
Cited
US5333212A
Cited
US5212742A
Cited
US5321725A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-06-04 | 1999-12-04 | 2000-06-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-06-04 | 2003-12-04 | 2004-06-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-06-04 | 2007-12-04 | 2008-06-04 | $7700.00 | Window Closed / Lapsed |