Browse Prior Art Database

Approximate Scaled DCT for Multiplication Free Transform Coding

IP.com Disclosure Number: IPCOM000121259D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 2 page(s) / 47K

Publishing Venue

IBM

Related People

Feig, E: AUTHOR [+2]

Abstract

The most common form of lossy coding of continuous tone image data involves discrete cosine transforms (DCTs) followed by quantization and then entropy coding, such as Huffman or arithmetic coding. On many architectures, the DCT is the major cost of the computation because of the many multiplications needed; also, if the quantization matrix is not composed of entries which are integer powers of 2, then the quantization step will be costly. Disclosed here is a transform very similar to the DCT which will need no multiplication for implementation, which will obtain compressing gains very close to that of the DCT.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 81% of the total text.

Approximate Scaled DCT for Multiplication Free Transform Coding

      The most common form of lossy coding of continuous tone
image data involves discrete cosine transforms (DCTs) followed by
quantization and then entropy coding, such as Huffman or arithmetic
coding.  On many architectures, the DCT is the major cost of the
computation because of the many multiplications needed; also, if the
quantization matrix is not composed of entries which are integer
powers of 2, then the quantization step will be costly.  Disclosed
here is a transform very similar to the DCT which will need no
multiplication for implementation, which will obtain compressing
gains very close to that of the DCT.

      Recalling the scaled-DCT factorization of [*], we have the DCT
matrix C written as

      C = D R M S
where D is a diagonal matrix, which computationally is absorbed into
the quantization process, R and S are matrices whose products involve
additions only, and
The matrix M is replaced by

      Products by the rational factors forming the matrix N involve
only shifts and additions.  For example, .75=1-.25, and its product
can be computed with a shift (forming the product by .25) followed by
a difference (which we also call addition).  Similarly, one can
design procedures for products by .9375=1-1/16 and .375=.25+.125.

      The product of a vector by the matrix N can be done with 8
additions and 8 shifts.  If the two-dimensional transform is done in
row- column fa...