Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1999-03-02
2003-03-18
Johns, Andrew W. (Department: 2627)
Image analysis
Image compression or coding
Transform coding
C382S248000, C382S253000, C382S276000, C382S304000, C348S395100, C348S403100, C358S438000, C708S626000
Reexamination Certificate
active
06535646
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to transformations on data, and, in particular discloses an efficient method of implementing a discrete cosine transform
BACKGROUND OF THE INVENTION
Image transformations utilising, for example, the discrete cosine transform (DCT) are fundamental in data compression algorithms such as image compression algorithms or the like. Further, other transformations such as the Hadamard and the Karhunen-Loeve transform have been utilised in the process of reducing the number of coefficients required to represent and image. In particular, the discrete cosine transform has become a key element in fundamental multi-media algorithms such as JPEG and MPEG. The capability of the discrete cosine transform for compacting the energy of the signal into a few coefficiencies exploited for both sound and image compression. For a detailed discussion of the JPEG image compression standard, reference is made to the standard text “JPEG-still Image Data Compression Standard” by Pennebaker and Mitchell.
Due to the importance of the discrete cosine transform, a large number of efficient implementations have been proposed.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide for an efficient alternative form of implementation of linear transforms such as the discrete cosine transform.
In accordance with a first aspect of the present invention, there is provided a linear transform apparatus for implementing a linear transform on input data values to produce linear transformed output data, the apparatus comprising: input means for inputting input data values one after another to each of a series of multiplication means; a series of multiplication means interconnected with the input means for multiplying a current input data value by a constant to produce a current multiplier output; an interconnection network interconnecting the series of multiplication means to predetermined ones of a series of signed accumulator means; a series of signed accumulator means each interconnected to the interconnection network, each of the signed accumulator means producing an intermediate accumulator output by accumulating a corresponding one of the current multiplier outputs with a corresponding previous intermediate accumulator output, each of the signed accumulator means outputting the intermediate accumulator output as a corresponding linear transformed output data value.
Preferably, the apparatus operates during predetermined clocking periods and the interconnection network interconnects current multiplier outputs to corresponding ones of the signed accumulator means in a single clocking period.
The linear transformed output data values can comprise a discrete cosine transform of the input data values or inverse discrete cosine transform of the input data values depending on requirements.
The interconnection network preferably can include a plurality of cross bars interconnecting predetermined ones of the multiplier means with each of predetermined ones of the signed accumulator means.
The series of the multiplication means can be implemented as a series of shifters and adders in addition to a series of partial sums.
In accordance with a further aspect of the present invention, there is provided a linear transform apparatus for implementing a linear transform on input data values to produce linear transformed output data, the apparatus comprising: input means for inputting input data values one after another to a series of multiplication means; memory storage means for storing a predetermined series of constants, and outputting a number of the constants, as determined by a corresponding input data value index, to corresponding ones of the series of multiplication means; a series of multiplication means interconnected with the memory storage means and the input means for multiplying outputted constants stored in the memory means by a current input data value to produce a current multiplier output; a series of signed accumulator means each interconnected to a single corresponding multiplication means, the signed accumulator means producing an intermediate accumulator output by accumulating a corresponding the current multiplier output with a previous intermediate output, each of the signed accumulator means outputting the intermediate accumulator output as a corresponding linear transformed output data value.
In accordance with a further aspect of the present invention, there is provided a method of implementing a linear transform on a series of input data values, the method comprising the steps of: simultaneously multiplying the a current one of the input data values by a constant value to produce a series of multiplier output values; simultaneously accumulating the multiplier output values with previous accumulations of the multiplier output values to produce intermediate transformed values; after a predetermined number of cycles outputting the intermediate transformed values as a linear transform of the input data values.
REFERENCES:
patent: 4633386 (1986-12-01), Terepin
patent: 4829465 (1989-05-01), Knauer et al.
patent: 5159567 (1992-10-01), Gobert
patent: 5243551 (1993-09-01), Knowles
patent: 5434808 (1995-07-01), Cohen
patent: 5452466 (1995-09-01), Fettweis
patent: 5701263 (1997-12-01), Pineda
patent: 5867414 (1999-02-01), Kao
patent: 2179770 (1987-03-01), None
Davis & Bujold P.L.L.C.
Johns Andrew W.
Mariam Daniel G.
LandOfFree
Discrete cosine transform method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Discrete cosine transform method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discrete cosine transform method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3019442