Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-06-15
2001-07-24
Britton, Howard (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06266373
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a system for determining values of half-pels from a reference frame of pixels. The invention has particular utility in connection with motion compensation performed during decoding of half-pel encoded video data.
2. Description of the Related Art
Video coding systems, such as motion picture experts group (hereinafter “MPEG”) coding, code video data using motion vectors. These motion vectors define movement of an object (e.g., a macroblock) in the video data from a reference, or anchor, frame to a current frame. Each motion vector consists of a horizontal, or “x”, component and a vertical, or “y” component, and is the representation of the distance that the object has moved in the time between the reference frame and the current frame.
In some coding systems, motion vectors are restricted to integer values. In these coding systems, the values of pixels in the current frame are specified in terms of values of actual pixels in the reference frame. This type of coding is known as full-pel (i.e., full-pixel) coding. In other coding systems, however, an example of which is MPEG, the motion vectors can have half-integer values. In these systems, the values of pixels in the current frame are not specified solely in terms of pixels that actually exist, but rather can be specified in terms of “virtual” pixels that are interpolated from existing pixels in the reference frame. This type of coding is known as half-pel (i.e., half-pixel) coding.
Motion compensation is a process which can be used to decode video data that has been coded using a half-pel coding system such as MPEG. In the case of half-pel coded video data, the motion compensation process recreates frames of video data from virtual pixels such as those described above. More specifically, in motion compensation of half-pel coded video, a motion vector is used to retrieve data for an object from a reference frame. An object is then generated which is comprised of half-pels that have been interpolated from actual pixels in the reference frame. It is noted that this object is merely a construct that used to improve the motion compensation process, and that the object is not actually displayed. After the object has been generated, a next half-pel motion vector is used to retrieve data from the object, and then to generate and display an actual object at the proper location within the current frame.
The motion compensation process described above interpolates half-pel values by a process which is known in the art as half-pel prediction filtering. Half-pel prediction filtering comprises averaging the value of a pixel corresponding to an integer (i.e., non-half-pel) part of the motion vector with a value of that pixel's nearest neighboring pixel in the direction of increasing motion. In a case that the horizontal component of the motion vector comprises the half-pel part of the motion vector, the averaging is performed with the pixel immediately to the right of the pixel of interest. In a case that the vertical component of the motion vector comprises the half-pel part of the motion vector, the averaging is performed with the pixel immediately below the pixel of interest. In a case where both components comprise a half-pel, the averaging is performed in both the horizontal and vertical directions and with the pixel diagonally adjacent to the pixel of interest.
Thus, as is clear from the foregoing, the motion compensation requires retrieving at least one other pixel, and potentially three other pixels, to interpolate a single half-pel. In the case of a 16×16 pixel MPEG macroblock, for example, this means that an array of 17×17 pixels must be retrieved from a frame memory in order to perform motion compensation on the macroblock. Thus, an extra 33 pixels (the difference between 17×17 pixels and 16×16 pixels), or 13% more pixels, are required to perform motion compensation on the macroblock. Certain modes of MPEG-2 use two motion vectors for each macroblock. In these modes, an array of 18×17 pixels must be retrieved from a frame memory in order to perform motion compensation. Thus, in these cases, an extra 50 pixels, or about 20% more pixels, are required to perform motion compensation on the macroblock. Retrieval and processing of extra pixels in both cases increase the time that it takes to process each macroblock.
More specifically, in conventional decoding systems, all pixels in a particular macroblock are stored sequentially in a frame-store memory. If all of these pixels are processed sequentially, a timing “gap”, which is proportionate to the number of extra pixels (e.g., 33 or 50 pixels), will be introduced between every two successive macroblocks in a frame of video data. This timing gap is typically introduced into both luminance and chrominance pixels in the macroblocks. To compensate for the timing gap, conventional MPEG decoders often include a high speed processing clock, together with additional hardware such as data buffers or the like. However, this solution increases the complexity of the timing and control circuitry used in such decoders, and often necessitates the use of an additional clocking frequency in a digital video receiver that includes such a decoder.
Thus, there exists a need for way to perform half-pel interpolation, particularly in the area of motion compensation, which does not introduce substantial timing gaps into video data during decoding, and which does not require significant amounts of additional hardware (e.g., memory) or an overly complex timing and control strategy.
SUMMARY OF THE INVENTION
The present invention addresses the foregoing needs by storing pixel data from a pixel array in one of a plurality of different memory segments based on a location of the pixel data in the pixel array. The invention then reads pixel data from each of the plurality of memory segments and determines a value of at least one half-pel based on the read pixel data. By storing pixel data in different memory segments and reading that pixel data from the different memory segments, it is possible to process pixels non-sequentially and, as a result, reduce any time gaps between consecutive macroblocks in a frame without the use of additional timing mechanisms and overly-complex control circuitry.
Thus, according to one aspect, the present invention is a method of, and a corresponding apparatus for, interpolating half-pels from a pixel array. The invention stores pixel data for each pixel in one of a plurality of different memory areas based on a location of the pixel within the pixel array, and determines a specific address in each one of the plurality of memory areas based on a target pixel in the pixel array. Each specific address is determined in the invention based on a location of the target pixel in the pixel array. The invention also reads, from each of the plurality of memory areas, pixel data from determined specific addresses, and determines a value of at least one half-pel for the target pixel based on the read pixel data.
In preferred embodiments of the invention, the pixel data is read from each one of the memory areas substantially concurrently. By reading the pixel data from each of the memory areas substantially concurrently, the invention reduces processing time by further reducing any timing gaps between consecutive macroblocks in a frame.
In particularly preferred embodiments, the invention is capable of interpolating half-pels by averaging a target pixel with one or more of three adjacent pixels. In these embodiments, an address of each adjacent pixel in its respective memory area is determined based on a location of the target pixel in the pixel array. Specifically, in a case that the target pixel is located in an even row and an even column in the pixel array, a specific address for each of three pixels adjacent to the target pixel is the same as a specific address for the target pixel. In a case that the target pixel is located in an even row and an odd column in the pixel
Bakhmutsky Michael
Wittig Karl
Britton Howard
Gross Russell
U.S. Philips Corporation
LandOfFree
Pixel data storage system for use in half-pel interpolation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pixel data storage system for use in half-pel interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pixel data storage system for use in half-pel interpolation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2443085