Image analysis – Image transformation or preprocessing
Reexamination Certificate
1996-09-26
2001-01-30
Bella, Matthew C. (Department: 2721)
Image analysis
Image transformation or preprocessing
C382S232000, C382S248000, C382S250000, C382S284000, C382S302000, C345S519000, 36, 36, 36
Reexamination Certificate
active
06181831
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to frequency-domain signal processing, and particularly to video signal processing in the spatial frequency domain.
2. Description of the Prior Art
Motion estimation is used in many video signal processing schemes, and in particular video compression schemes, in order to reduce the amount of data which has to be transmitted or stored to represent a series of images (e.g. fields or frames). This benefit can be achieved because there is often a great deal of redundancy present in a video sequence. In particular, many areas of an image stay the same or are simply displaced from image to image. Thus, a reasonably good replica of a frame can be constructed from appropriately selected areas of previous frame(s), referred to here as reference frames.
For this type of processing, frames are generally broken down into square or rectangular areas (arrays of pixels) known as macroblocks. For example, in one previously proposed system, a macroblock comprises an array of 16×16 pixels. For each macroblock, one or more motion vectors is computed and transmitted or stored. The motion vectors point to areas on previous frame(s) which most closely resemble the content of the macroblock.
At the decoder, the motion vectors, together with error data (representing the difference between the actual or original frame and a replica predicted from the reference frame(s) using the motion vectors) are used to reconstruct each frame.
The process of computing the motion vectors at the encoder is generally referred to as motion estimation, and the process of generating the replica or reconstructed frames is generally referred to as motion compensation.
Many video compression schemes which use motion-based processing also try to reduce further the redundancy present in the video data, by first transforming the spatial domain data into a corresponding set of frequency domain coefficients which represent different spatial frequency components of the video data, and then reducing the amount of information by quantising these coefficients. A common technique for transforming the data to and from the frequency domain is the discrete cosine transform (DCT).
The discrete cosine transform is a block-based, process, so that an array of DCT coefficients is generated from each macroblock, independently of other macroblocks in the image. Usually, the array of coefficients (referred to here as a DCT block) is the same size (i.e. the same number of elements) as the original macroblock.
Therefore, if there is a need to generate a block of DCT coefficients based on a different block structure, it is necessary to decode the DCT data back to spatial (pixel) data and then recode in accordance with the required block structure. This can be processor-intensive and time-consuming.
SUMMARY OF THE INVENTION
This invention provides a method of generating an output array of image spatial frequency coefficients from input arrays of image spatial frequency coefficients overlapped by the required array, the spatial frequency coefficients being transformable to image pixel values by a predetermined spatial frequency transformation, the method comprising the steps of:
matrix-multiplying each input array by one or more respective matrices having coefficients derivable by applying the inverse of the predetermined spatial frequency transformation to respective translation matrices which, if matrix-multiplied by that input array, would provide a translation of the overlapped portion of that input array to an overlapping position in the output array; and
matrix-adding the respective matrix products generated from each overlapped input array.
The invention involves a recognition of the counter-intuitive feature of spatial frequency coefficients such as DCT coefficients, that a required array overlapping a number of input arrays of coefficients can be generated simply by matrix-multiplying each input array which is overlapped by an array position in the output array by suitable pre- and post-matrices.
This now means that motion compensation can be performed in the DCT domain. This is potentially very useful in applications such as, for example, converting one GOP format into another GOP format.
Preferably the predetermined spatial frequency transformation is the inverse discrete cosine transform.
For use in motion compensation techniques, it, is preferred that the method comprises the step of detecting portions of the input arrays overlapped by the output array in response to a motion vector associated with the output array.
Preferably the one or more matrices comprise a pre-multiplying matrix and a post-multiplying matrix.
The invention also provides video signal processing apparatus for generating an output array of image spatial frequency coefficients from input arrays of image spatial frequency coefficients overlapped by the required array, the spatial frequency coefficients being transformable to image pixel values by a predetermined spatial frequency transformation, the apparatus comprising:
means for matrix-multiplying each input array by one or more respective matrices having coefficients derivable by applying the inverse of the predetermined spatial frequency transformation to respective translation matrices which, if matrix-multiplied by that input array, would provide a translation of the overlapped portion of that input array to an overlapping position in the output array; and
means for matrix-adding the respective matrix products generated from each overlapped input array.
REFERENCES:
patent: 3905018 (1975-09-01), Gary
patent: 4134134 (1979-01-01), Lux
patent: 4163258 (1979-07-01), Ebihara et al.
patent: 4245248 (1981-01-01), Netravali et al.
patent: 4442454 (1984-04-01), Powell
patent: 4447886 (1984-05-01), Meeker
patent: 4751742 (1988-06-01), Meeker
patent: 4754492 (1988-06-01), Malvar
patent: 5170264 (1992-12-01), Saito et al.
patent: 5301242 (1994-04-01), Gonzales et al.
patent: 5325215 (1994-06-01), Shibata et al.
patent: 5414780 (1995-05-01), Carnaham
patent: 5428693 (1995-06-01), Murakami et al.
patent: 5642438 (1997-06-01), Babkin
patent: 5663763 (1997-09-01), Yagasaki et al.
Bella Matthew C.
Chawan Sheela
Frommer William S.
Frommer Lawrence & Haug LLP.
Shallenburger Joe
LandOfFree
Spatial frequency-domain video signal processing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Spatial frequency-domain video signal processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spatial frequency-domain video signal processing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2509247