Method for image compression implementing fast two-dimensional discrete cosine transform

• US 5,642,438 A
• Filed: 03/17/1995
• Issued: 06/24/1997
• Est. Priority Date: 12/20/1991
• Status: Expired due to Term

• Current Assignee: XVD Technology Holdings Ltd.
• Original Assignee: Alaris, Inc., GT Technologies
• Inventors: Babkin, Vladimir
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Patel, Jayanti K.
• Application Number:
  US08/405,901
• Time in Patent Office: 830 Days
• Field of Search: 382/250, 364/725, 348/405
• US Class Current: 382/250
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: G06T 9/007 Transform coding, e.g. discrete cosine transform

Abstract

A method and apparatus for the realization of two-dimensional discrete cosine transform (DCT) for an 8*8 image fragment with three levels of approximation of DCT coefficients. A first embodiment uses two multiplications for a pixel. A second embodiment does not use multiplications. The accuracy of approximation of DCT coefficients in the second embodiment is coordinated with distortion defined by a given quantization matrix. The Discrete Algebraic Transform (DAT) is presented. The DAT is a good approximation of the DCT and can be used in any combination with DCT.

Claims

1. A computer implemented method for compressing an image using a discrete algebraic transform (DAT) using a first circuit, said image being represented by one or more 8*8 picture fragments and stored in a memory coupled to said first circuit, said memory storing the results of said DAT, each of said one or more 8*8 picture fragments having a property of separability, said first circuit for producing non-normalized components, said method comprising the computer implemented steps of:

said first circuit generating a one-dimensional transform for producing non-normalized components given in the form;

##EQU14## where f(.) are the input values of a transform corresponding to one of said 8*8 picture fragment, F(.) are transformed non-normalized values, B=1+√

2, L=5+Δ

, G=(3+Δ

/2)√

2, M=(2+Δ

/2)√

2, and Δ

is a parameter, selection of which, allows an approximation of a transform matrix of DCT by a transform matrix of DAT.

2. The method of claim 1, wherein:

a forward and an inverse DAT may be used in any combination with a forward and an inverse DCT.

3. A computer implemented method of image compression, transforming an 8×

8 block of image pixel signals into corresponding frequency signals, said computer including a memory and being coupled to a processor, said method comprising the steps of;

said computer using pixel signals representing columns of said 8×

8 block of image pixel signals and approximate representations of discrete cosine transform (DCT) matrix terms to generate first intermediate results, said DCT matrix terms being represented in a form a+√

2b, where a represents a rational part and b represents an algebraic part, said first intermediate results, being represented in said form, including a first rational part and a first algebraic part;

said computer using said first intermediate results to generate second intermediate results, said second intermediate results including a second rational part, a third rational part, a second algebraic part and a third algebraic part, said second rational part being generated from a transform of said first algebraic part, said second algebraic part being generated from a transform of said first rational part, said third rational part being generated from a transform of said first rational part, said third algebraic part being generated from a transform of said first algebraic part;

said computer combining, using addition, said second rational part with said second algebraic part to generate first signals corresponding to an algebraic part of said frequency signals;

said computer combining, using addition, said third rational part with twice said third algebraic part to generate second signals corresponding to a rational part of said frequency signals; and

said computer storing said algebraic part and said rational part of said frequency signals in said memory.

4. The method of claim 3 wherein said first signals and said second signals represent non-normalized frequency components of said 8×

8 block of image pixel signals.

5. The method of claim 4 further comprising the steps of:

normalizing said non-normalized frequency components of said 8×

8 block of image pixel signals.

6. The method of claim 3 wherein said first intermediate results are generated using the following DCT matrix term approximations:

##EQU15## where Δ

defines a level of precision.

7. The method of claim 6 wherein Δ

is one of zero and 1/32 and 1/32-1/256.

8. In a computer system comprising a processor and a memory, a computer implemented method of compressing digitized image data, transforming image pixel signals into corresponding frequency signals, said method comprising the computer implemented steps of:

said processor segmenting said image pixel signals into n×

n blocks of image pixel signals, where n is a multiple of 8;

for each n×

n block, said processor performing the following steps;

accessing said block of image pixel signals from said memory,

generating frequency signals having a rational part and an algebraic part; and

said processor storing said frequency signals in said memory.

9. The method of claim 8, wherein said step of generating frequency signals further comprises the steps of:

said processor applying approximate representations of discrete cosine transform (DCT) matrix terms to said pixel signals representing columns of said n×

n block of image pixel signals to generate first intermediate results, said DCT matrix terms being represented in a separable form having a rational part and an algebraic part, a+√

2b, where a represents said rational part and b represents said algebraic part, said first intermediate results, being represented in said separable form, including a first rational part and a first algebraic part;

said processor generating second intermediate results using said first intermediate results, said second intermediate results including a second rational part, a third rational part, a second algebraic part and a third algebraic part, said second rational part being generated from a transform of said first algebraic part, said second algebraic part being generated from a transform of said first rational part, said third rational part being generated from a transform of said first rational part, said third algebraic part being generated from a transform of said first algebraic part;

said processor adding said second rational part with said second algebraic part to generate first signals corresponding to the algebraic part of said frequency signals; and

said processor adding said third rational part with twice said third algebraic part to generate second signals corresponding to the rational part of said frequency signals.

10. The method of claim 9 wherein said first results are generated using the following approximate representations of DCT matrix terms in said separable form, a+√

2b;

##EQU16## where Δ

defines a level of precision.

11. The method of claim 10 wherein Δ

is one of zero and 1/32 and 1/32-1/256.

12. In a computer system comprising a processor and a memory, a computer implemented method of compressing digitized image data representing a digitized image to generate compressed digitized image data, said method comprising the computer implemented steps of:

said processor segmenting said digitized image data into n×

n blocks, where n is a multiple of 8;

for each of said n×

n blocks, said processor generating frequency components using approximate representations of DCT matrix terms represented in an algebraic form having a rational part and an algebraic part;

said processor normalizing said frequency components; and

said processor quantizing said normalized frequency components using said quantization matrix;

said processor further compressing said quantized normalized frequency components to generate said compressed digitized image data;

said processor storing said compressed digitized image data in said memory.

13. The method of claim 12, wherein said frequency components can be computed with three precision levels using the following approximate representations of DCT matrix terms:

##EQU17## where Δ

defines a level of precision from said predetermined set of transform accuracy values, {0, 1/32, 1/32-1/256}.

14. A computer implemented method of image compression implementing fast two-dimensional discrete cosine transform (DCT) for 8×

8 picture fragments producing, without multiplication, transformed non-normalized components as an intermediate step to generating compressed image data representing a compressed image, said method comprising the computer implemented steps of;

accessing the columns and rows of each of said 8×

8 picture fragments;

applying approximate representations of DCT matrix terms on the columns (rows) to generate first intermediate results representing one-dimensional DCT values of non-normalized components, wherein each approximate representation of DCT matrix terms is represented by an algebraic form having a rational part and an algebraic part and each of said first intermediate results are in said algebraic form;

performing a one-dimensional transform on the rows (columns) separately for the rational and the algebraic part of each of said first intermediate results to produce second intermediate results in said algebraic form;

combining pairs of rational and algebraic parts of said second intermediate results in a predetermined manner to produce said transformed non-normalized components having said algebraic form;

normalizing said transformed non-normalized components to produce normalized transform values;

quantizing said normalized transform values to produce quantized values;

completing the compression of said quantized values to generate said compressed image data.

15. The method of claim 14, wherein:

said algebraic form is a+√

2b, where a represents said rational part and b represents said algebraic part;

each of said second intermediate results include a first rational part, a second rational part, a first algebraic part, and a second algebraic part, said first rational part and said first algebraic part obtained as a result of transforming the algebraic parts of one of said first intermediate results, said second rational part and said second algebraic part obtained as a result of transforming the rational part of one of said first intermediate results;

said step of combining includes, for each of said second intermediate results, the steps of;

adding said first rational part and said second algebraic part to obtain said algebraic part of one of said transformed non-normalized components, and

adding said second rational part and twice said first algebraic part to obtain said rational part of one of said transformed non-normalized components.

16. The method of claim 15, wherein said transformed non-normalized components can be computed with three precision levels using the following representation of DCT matrix terms:

##EQU18## where Δ

defines three selectable levels of precision and has values;

0 for zero precision, 1/32 for normal precision, and 1/32-1/256 for double precision.

17. A computer implemented method of image compression implementing fast two-dimensional discrete cosine transform (DCT) for n×

n picture fragments, where n is a multiple of 8, producing, without multiplication, transformed non-normalized components as an intermediate step to generating compressed image data representing a compressed image, said method comprising the computer implemented steps of;

accessing the columns and rows of each of said n×

n picture fragments;

applying approximate representations of DCT matrix terms on the columns (rows) to generate first intermediate results representing one-dimensional DCT values of non-normalized components, wherein each approximate representation of DCT matrix terms is represented by an algebraic form having a rational part and an algebraic part and each of said first intermediate results are in said algebraic form;

performing a one-dimensional transform on the rows (columns) separately for the rational and the algebraic part of each of said first intermediate results to produce second intermediate results in said algebraic form;

combining pairs of rational and algebraic parts of said second intermediate results in a predetermined manner to produce said transformed non-normalized components having said algebraic form;

normalizing said transformed non-normalized components to produce normalized transform values;

quantizing said normalized transform values to produce quantized values;

completing the compression of said quantized values to generate said compressed image data.

18. The method of claim 17, wherein:

said algebraic form is a+√

2b, where a represents said rational part and b represents said algebraic part;

each of said second intermediate results include a first rational part, a second rational part, a first algebraic part, and a second algebraic part, said first rational part and said first algebraic part obtained as a result of transforming the algebraic parts of one of said first intermediate results, said second rational part and said second algebraic part obtained as a result of transforming the rational part of one of said first intermediate results;

said step of combining includes, for each of said second intermediate results, the steps of;

adding said first rational part and said second algebraic part to obtain said algebraic part

of one of said transformed non-normalized components, and

adding said second rational part and twice said first algebraic part to obtain said rational part of one of said transformed non-normalized components.

19. The method of claim 18, wherein said transformed non-normalized components can be computed with three precision levels using the following representation of DCT matrix terms:

##EQU19## where Δ

defines three selectable levels of precision and has values;

0 for zero precision, 1/32 for normal precision, and 1/32-1/256 for double precision.