Method and apparatus for the realization of two-dimensional discrete cosine transform for an 8*8 image fragment

• US 5,539,836 A
• Filed: 01/03/1994
• Issued: 07/23/1996
• Est. Priority Date: 12/20/1991
• Status: Expired due to Fees

• Current Assignee: Alaris, Inc., GT Technologies, XVD Technology Holdings Ltd.
• Original Assignee: Alaris, Inc., GT Technologies
• Inventors: Babkin, Vladimir
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US08/176,884
• Time in Patent Office: 932 Days
• Field of Search: 382/56, 358/433, 364/725, 364/757
• 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 system for generating and transmitting a representation of frequency components of a time domain signal, said time domain signal being represented as a group of eight image signals, said time domain signal representing an image, said representation of frequency components of said time domain signal corresponding to a compressed representation of said image, the system comprising:

first means for developing signals representing sums and differences of predetermined combinations of signal samples, having a set of eight inputs coupled to receive signal samples and a set of eight outputs at which said sum and difference signals are developed;

second means for developing signals representing sums and differences of predetermined combinations of auxiliary samples, having a set of four inputs to receive auxiliary samples of sums coupled to a predetermined set of outputs of said first means for developing signals and a set of four outputs at which said sum and difference signals are developed;

third means for developing signals representing sums and differences of predetermined combinations of said auxiliary samples, having a set of four inputs to receive auxiliary samples of differences coupled to a predetermined set of outputs of said first means for developing signals and a set of four outputs at which said third means develops said sum and difference signals;

fourth means for developing signals representing sums and differences of predetermined combinations of said auxiliary samples of sums, having a set of two inputs coupled to a predetermined set of outputs of said second means for developing signals, and a set of two outputs at which said fourth means develops said sum and difference signals;

fifth means for developing signals representing sums and differences of predetermined combinations of said auxiliary samples of differences, having a set of two inputs coupled to a predetermined set of outputs of said second means for developing signals, and a set of two outputs at which said fifth means develops said sum and difference signals;

precision control, adder and subtraction means having a set of four inputs coupled to a predetermined set of outputs of said third means for developing signals, and a set of four outputs at which said precision control, adder and subtraction means develops signals representing transformed auxiliary samples;

sixth means for developing signals representing sums and differences of predetermined combinations of said auxiliary samples, having a set of four inputs coupled to a predetermined set of outputs of said precision control, adder and subtraction means, and a set of four outputs at which said sixth means develops said sum and difference signals; and

a memory being coupled to said sixth means, said memory for receiving information from said set of four outputs at which said sixth means develops said sum and difference signals, said memory having an output for transmitting said information.

2. The system of claim 1, wherein said precision control, adder and subtraction means comprises:

four precision control means each having a set of inputs coupled to said set of outputs of said third means to receive auxiliary samples;

adder means having a set of two inputs coupled to said set of inputs and a set of outputs from precision control means for developing auxiliary sample signals;

a group of two adder means each having a set of two inputs, each coupled to a set of outputs of one precision control means and a set of inputs of another precision control means, and a set of outputs to develop signals representing auxiliary samples; and

subtraction means having a set of two inputs coupled to said set of inputs and a set of outputs of a precision control means to develop signals representing auxiliary samples.

3. The system of claim 1 wherein said precision control means have a minimum precision level set of outputs at which precision control means develops signals representing a number, corresponding to an input signal, multiplied by two.

4. The system of claim 1, wherein said precision control means has a medium precision level and comprises:

a set of inputs to receive auxiliary samples;

precision control means which has a low precision level having a set of inputs to receive said auxiliary samples and a set of outputs;

multiplication means having a set of inputs to receive said auxiliary samples and a set of outputs at which multiplication means develops signals representing a number corresponding to an input signal multiplied by 1/64; and

an adder having two sets of inputs coupled to a set of outputs of said precision control means which have low precision level and to a set of outputs of said multiplication means and a set of outputs at which an adder develops signals representing a sum of numbers corresponding to input signals.

5. The system of claim 1, wherein said precision control means has a maximum precision level and comprises:

a set of inputs to receive auxiliary samples;

precision control means which has a medium precision level having a set of inputs to receive said auxiliary samples and a set of outputs;

multiplication means having a set of inputs to receive said auxiliary samples and a set of outputs at which multiplication means develops signals representing a number corresponding to an input signal multiplied by 1/512; and

subtraction means having two sets of inputs coupled to a set of outputs of said precision control means which have medium precision level and to a set of outputs of said multiplication means and a set of outputs at which subtraction means develops signals representing a difference of numbers corresponding to input signals.

6. A computer system for generating signals of frequency components of a time domain signal, said time domain signal corresponding to an image, said time domain signal being represented as a group of eight signals, said frequency components corresponding to a compressed said image, the system comprising:

first circuit for developing signals representing sums and differences of predetermined combinations of signal samples, having a set of eight inputs coupled to receive signal samples and a set of eight outputs at which said sum and difference signals are developed;

second circuit for developing signals representing sums and differences of predetermined combinations of auxiliary samples, having a set of four inputs to receive auxiliary samples of sums coupled to a predetermined set of outputs of said first circuit for developing signals and a set of four outputs at which said sum and difference signals are developed;

third circuit for developing signals representing sums and differences of predetermined combinations of said auxiliary samples, having a set of four inputs to receive auxiliary samples of differences coupled to a predetermined set of outputs of said first circuit for developing signals and a set of four outputs at which said third circuit develops said sum and difference signals;

fourth circuit for developing signals representing sums and differences of predetermined combinations of said auxiliary samples of sums, having a set of two inputs coupled to a predetermined set of outputs of said second circuit for developing signals, and a set of two outputs at which said fourth circuit develops said sum and difference signals;

fifth circuit for developing signals representing sums and differences of predetermined combinations of said auxiliary samples of differences, having a set of two inputs coupled to a predetermined set of outputs of said second circuit for developing signals, and a set of two outputs at which said fifth circuit develops said sum and difference signals;

precision control, adder and subtraction means having a set of four inputs coupled to a predetermined set of outputs of said third circuit for developing signals, and a set of four outputs at which said precision control, adder and subtraction means develops signals representing transformed auxiliary samples;

sixth circuit for developing said signals representing sums and differences of predetermined combinations of said auxiliary samples, having a set of four inputs coupled to a predetermined set of outputs of said precision control, adder and subtraction means, and a set of four outputs at which said sixth circuit develops said sum and difference signals;

storage circuit, being coupled to said sixth circuit, for storing information from said set of four outputs at which said sixth circuit develops said sum and difference signals.

7. The computer system of claim 6 wherein said first, second, third, fourth, fifth, and sixth circuits are formed on a single integrated circuit.