Method and system for fast implementation of subpixel interpolation

A subpixel interpolator includes an input memory capable of storing video information formed from full pixels. The subpixel interpolator also includes at least one interpolation unit capable of performing subpixel interpolation to generate half-pixels and quarter-pixels in parallel. Multiple half-pixels and multiple quarter-pixels are generated concurrently during the subpixel interpolation. In addition, the subpixel interpolator includes an output memory capable of storing at least some of the full pixels, half-pixels, and quarter-pixels. In some embodiments, the at least one interpolation unit includes a horizontal half-pixel interpolation unit, two vertical half-pixel interpolation units, and a quarter-pixel interpolation unit, all of which may operate in parallel. In particular embodiments, the interpolation units are formed from adders and shifters and do not include any multipliers.

TECHNICAL FIELD

This disclosure is generally directed to video compression systems and more specifically to a method and system for fast implementation of subpixel interpolation.

BACKGROUND

Image compression systems are becoming more and more useful in various applications. For example, video compression is often used to compress video information for storage on a digital versatile disc (DVD) or a hard disk drive (HDD). As another example, video compression is often used during real-time streaming of video information over a network or communication channel, such as the Internet, a digital subscriber line (DSL), a direct broadcast satellite (DBS) system, multimedia services over packet networks (MSPN), and cable television (CATV) networks. In addition, video compression is used in many other applications, such as computer games, video games, videoconferencing systems, videophones, interactive storage media (ISM), and remote video surveillance (RVS) systems.

Several video compression standards have been developed in the last two decades. One of the latest standards is the International Telecommunication Union-Telecommunications (ITU-T) H.264 standard. The H.264 standard is also known as Advanced Video Coding (AVC) or Moving Picture Experts Group 4 (MPEG-4) Part 10. The H.264 standard provides many benefits over previous standards, including improved rate distortion and lower bit rates. Among its features, the H.264 standard supports subpixel motion compensation.

Subpixel motion compensation is often computationally complex and computationally intensive. Because of this, the use of subpixel motion compensation, as part of the H.264 standard or other standard, often requires large amounts of processing time and resources. As a result, its use typically slows the performance of video compression and/or decompression systems.

SUMMARY

This disclosure provides a method and system for fast implementation of subpixel interpolation.

In a first embodiment, a method includes receiving video information comprising full pixels. The method also includes performing subpixel interpolation to generate half-pixels and quarter-pixels in parallel. Multiple half-pixels and multiple quarter-pixels are generated concurrently during the subpixel interpolation.

In a second embodiment, a subpixel interpolator includes an input memory capable of storing video information formed from full pixels. The subpixel interpolator also includes at least one interpolation unit capable of performing subpixel interpolation to generate half-pixels and quarter-pixels in parallel. Multiple half-pixels and multiple quarter-pixels are generated concurrently during the subpixel interpolation. In addition, the subpixel interpolator includes an output memory capable of storing at least some of the full pixels, half-pixels, and quarter-pixels.

In a third embodiment, a system includes a source of video information comprising full pixels and a subpixel interpolator. The subpixel interpolator includes an input memory capable of storing the full pixels. The subpixel interpolator also includes at least one interpolation unit capable of performing subpixel interpolation to generate half-pixels and quarter-pixels in parallel. Multiple half-pixels and multiple quarter-pixels are generated concurrently during the subpixel interpolation. In addition, the subpixel interpolator includes an output memory capable of storing at least some of the full pixels, half-pixels, and quarter-pixels.

DETAILED DESCRIPTION

FIG. 1illustrates an example video system100according to one embodiment of this disclosure. In the illustrated example, the system100includes a video encoder102, a video decoder104, and a display device106. The video system100shown inFIG. 1is for illustration only. Other embodiments of the video system100may be used without departing from the scope of this disclosure.

In one aspect of operation, the video encoder102compresses video information, and the video decoder104receives and decompresses the video information. For example, the video encoder102and the video decoder104may each support the International Telecommunication Union-Telecommunications (ITU-T) H.264 standard. To implement the H.264 standard or other compression scheme, the video encoder102and the video decoder104are capable of performing subpixel interpolation. Subpixel interpolation allows the video encoder102and the video decoder104to identify and operate on subpixels or fractional pixels for images being compressed or decompressed. The subpixels or fractional pixels are identified using pixels contained in the images being compressed or decompressed.

In some embodiments, the video encoder102and the video decoder104each includes one or more subpixel interpolation units and a memory arrangement. The interpolation units generate the subpixels by performing interpolation using the original image pixels, and the memory arrangement stores the values of the various pixels and subpixels. The interpolation units are capable of operating in parallel, which helps to reduce the amount of time needed to perform the interpolation process. In addition, the memory arrangement helps to decrease the number of load and store operations during the interpolation process, which also helps to reduce the amount of time needed to perform the interpolation process.

In the illustrated example, the video encoder102generates compressed video information. In this document, the phrase “video information” refers to information representing a sequence of video images. The video encoder102represents any suitable apparatus, system, or mechanism for producing or otherwise providing compressed video information. For example, the video encoder102could represent a streaming-video transmitter capable of transmitting streaming video to a video decoder104over a data network108, such as the Internet, a digital subscriber line (DSL), a wireless network, a direct broadcast satellite (DBS) system, multimedia services over packet networks (MSPN), and a cable television (CATV) network. The video encoder102could also represent a digital versatile disc (DVD) burner or other optical disc burner capable of storing compressed video information on a DVD or other optical disc110. The video encoder102could further represent a digital video recorder capable of compressing video information for storage on a hard disk drive (HDD)112. The video encoder102includes any hardware, software, firmware, or combination thereof for compressing video information.

The video decoder104decompresses the compressed video information provided by the video encoder102. The video decoder104represents any suitable apparatus, system, or mechanism for decompressing video information. For example, the video decoder104could represent a streaming-video receiver capable of receiving streaming video from the video encoder102over a network108. The video decoder104could also represent a DVD player or other optical disc player capable of retrieving compressed video information from an optical disc110. The video decoder104could further represent a digital video recorder capable of decompressing video information stored on a hard disk drive112. The video decoder104includes any hardware, software, firmware, or combination thereof for decompressing video information.

In the illustrated example, the video decoder104decompresses the compressed video information and provides the decompressed video information to a display device106for presentation to a viewer. The display device106represents any suitable device, system, or structure for presenting video information to one or more viewers. The display device106could, for example, represent a television, computer monitor, or projector. The video decoder104could provide the decompressed video information to any other or additional destination(s), such as a video cassette player (VCR) or other recording device.

While shown inFIG. 1as separate components, the video encoder102and the video decoder104could operate within a single device or apparatus. For example, the video encoder102and the video decoder104could operate within a digital video recorder or other device. The video encoder102could receive and compress video information for storage on the hard disk drive112, and the video decoder104could retrieve and decompress the video information for presentation.

In the illustrated embodiment, the video encoder102includes a video source114. The video source114provides a video information signal116containing video information to be compressed by the video encoder102. The video source114represents any device, system, or structure capable of generating or otherwise providing uncompressed video information. The video source114could, for example, include a television receiver, a VCR, a video camera, a storage device capable of storing raw video data, or any other suitable source of video information. WhileFIG. 1illustrates the video source114as forming part of the video encoder102, the video source114could also reside outside of the video encoder102.

A combiner118is coupled to the video source114. In this document, the term “couple” and its derivatives refer to any direct or indirect communication between two or more elements, whether or not those elements are in physical contact with one another. The combiner118receives the video information signal116containing uncompressed video information from the video source114. The combiner118also receives a feedback video signal148from other components in the video encoder102. The feedback video signal148is associated with video information that has already been compressed by the video encoder102. The combiner118identifies any differences between the video information signal116and the feedback video signal148. The combiner118then outputs the identified differences as a residual signal120. The combiner118represents any hardware, software, firmware, or combination thereof for combining signals, such as a subtractor.

The residual signal120is provided to a transform/quantize unit122. The transform/quantize unit122implements various functions to process the residual signal120. For example, the transform/quantize unit122may implement a transform function to convert the residual signal120(in the spatial domain) into discrete cosine transform (DCT) coefficients (in the frequency domain). The transform/quantize unit122may also quantize the DCT coefficients and output quantized DCT coefficients124. In some embodiments, the transform/quantize unit122operates on blocks of pixels from images being compressed (such as 16×16 macroblocks) and produces blocks of quantized DCT coefficients124. The transform/quantize unit122includes any hardware, software, firmware, or combination thereof for transforming and quantizing video information.

The quantized DCT coefficients124are provided to an entropy encoder126. The entropy encoder126encodes the quantized DCT coefficients124(along with other information) to produce compressed video information128. The entropy encoder126may implement any suitable encoding technique, such as context adaptive based arithmetic coding (CABAC) and/or context adaptive variable length coding (CAVLC). The entropy encoder126includes any hardware, software, firmware, or combination thereof for encoding quantized DCT coefficients124and other information.

The quantized DCT coefficients124are provided to an inverse transform/quantize unit130. The inverse transform/quantize unit130processes the quantized DCT coefficients124and attempts to reverse the processing performed by the transform/quantize unit122. For example, the inverse transform/quantize unit130could implement an inverse quantization function to produce DCT coefficients. The inverse transform/quantize unit130could also implement an inverse-DCT transform to produce a reconstructed residual signal132. The reconstructed residual signal132might match the original residual signal120, or the reconstructed residual signal132may be similar to the residual signal120but have some differences. The inverse transform/quantize unit130includes any hardware, software, firmware, or combination thereof for performing inverse transform and inverse quantization functions.

The reconstructed residual signal132is provided to a combiner134. The combiner134also receives the feedback video signal148. The combiner134then combines the reconstructed residual signal132and the feedback video signal148to produce a combined signal136. The combiner134represents any hardware, software, firmware, or combination thereof for combining signals, such as an adder.

The combined signal136is provided to a deblocking filter138. The deblocking filter138reduces blocking artifacts in images being decompressed, such as blocking artifacts located along the boundaries of different 16×16 macroblocks. This produces filtered video information140. The deblocking filter138represents any hardware, software, firmware, or combination thereof for reducing blocking artifacts.

The filtered video information140is provided to a motion estimator142and a motion compensator144. The motion estimator142also receives the original video information signal116and the feedback video signal148. The motion estimator142uses the received information to identify motion within video images being compressed. For example, the motion estimator142could implement field-based or frame-based motion estimation to identify motion. The motion estimator142then outputs motion vectors146, which represent the identified motion in the images. The motion vectors146are provided to the entropy encoder126for coding as part of the compressed video information128and to the motion compensator144. The motion estimator142includes any hardware, software, firmware, or combination thereof for estimating motion in video images.

The motion compensator144receives the filtered video information140and the motion vectors146. The motion compensator144uses the motion vectors146to alter the filtered video information140and re-introduce motion into the filtered video information140. This produces the feedback video signal148, which may or may not exactly match the original video information signal116. The motion compensator144includes any hardware, software, firmware, or combination thereof for altering video information to introduce motion into video images.

In the illustrated example, an intra prediction unit150is used to process the video information when an intra prediction mode is used. The intra prediction mode is defined in the H.264 standard and analyzes 16×16 macroblocks in 4×4 blocks or partitions. In some embodiments, when intra prediction mode is used, the transform/quantize unit122implements the intra prediction mechanism on the 4×4 partitions. The intra prediction unit150implements a reverse of this process and generates the feedback video signal148when the video encoder102operates in the intra prediction mode.

The video decoder104could include many similar components as the video encoder102shown inFIG. 1. For example, the video decoder104could include the inverse transform/quantize unit130, the combiner134, the deblocking filter138, the motion compensator144, and the intra prediction unit150. The video decoder104could also include an inverse entropy coder that implements the inverse of the coding function used by the entropy coder126. The inverse entropy coder could receive the compressed video information128, provide quantized DCT coefficients124to the inverse transform/quantize unit130, and provide motion vectors146to the motion compensator144. In this way, the video decoder104decompresses the video information128and recovers the video information signal116for presentation to a viewer.

In one aspect of operation, the video encoder102and the video decoder104implement subpixel interpolation. For example, the motion compensator144in the video encoder102and the video decoder104could implement subpixel motion compensation, which uses subpixel interpolation. Subpixel interpolation is typically computationally complex and computationally intensive. As described in more detail below, the video encoder102and/or the video decoder104includes one or more subpixel interpolation units and a memory arrangement that help to reduce the complexity of the subpixel interpolation and increase the speed of the subpixel interpolation.

In particular embodiments, the video encoder102and the video decoder104implement the H.264 compression scheme. The H.264 compression scheme supports several advanced video coding techniques, such as directional spatial prediction, multi-frame references, weighted prediction, de-blocking filtering, variable block size, and quarter-sample accurate motion compensations. The H.264 compression scheme also supports a small, block-based, integer, and hierarchical transform, as well as CABAC and CAVLC coding.

The H.264 standard uses a tree-structured motion compensation method. This method supports variable motion compensation block or partition sizes that range from 4×4 to 16×16. For luminance samples, each 16×16 macroblock is formed from one or more 16×16, 16×8, 8×16, or 8×8 blocks. Each 8×8 block can be further partitioned into 8×4, 4×8, or 4×4 blocks. This provides more flexibility in the selection of motion compensation blocks and allows a large number of variable block size combinations to be used to match the shape of different objects in a video image.

Each block or partition in an inter-coded macroblock is described by a motion vector146. The motion vector146of a partition in a current frame is predicted from an area of the same size in a reference frame. The offset between two motion vectors146is encoded and transmitted with the choice of partition. In the H.264 standard, the offset between two motion vectors146has a quarter-pixel resolution. This resolution allows a motion vector146to be calculated with better precision, increasing coding efficiency.

AlthoughFIG. 1illustrates one example of a video system100, various changes may be made toFIG. 1. For example,FIG. 1illustrates that compressed video information may be supplied to a video decoder104over a network108, using an optical disc110, or on a hard disk drive112. The video encoder102could place the compressed video information on any other suitable storage medium or otherwise communicate the information to the video decoder104in any suitable manner. Also,FIG. 1illustrates one example embodiment of the video encoder102. Other embodiments of the video encoder102may be used. In addition, the video encoder102and the video decoder104could be combined into a single device or apparatus.

FIG. 2illustrates an example subpixel interpolator200according to one embodiment of this disclosure. The subpixel interpolator200shown inFIG. 2is for illustration only. Other embodiments of the subpixel interpolator200may be used without departing from the scope of this disclosure. Also, for ease of explanation, the subpixel interpolator200ofFIG. 2is described as operating within the system100ofFIG. 1. The subpixel interpolator200could be used in any other system or device.

The subpixel interpolator200supports subpixel interpolation and therefore subpixel motion compensation within the video encoder102and/or the video decoder104ofFIG. 1. The subpixel interpolator200may be used, for example, within the motion compensator144in the video encoder102or in the video decoder104ofFIG. 1.

In this example, the subpixel interpolator200includes an input buffer202that receives and stores video information to be processed. For example, the input buffer202could receive a 16×16 macroblock from the de-blocking filter138ofFIG. 1. The 16×16 macroblock contains data values representing a 16×16 block of pixels in an image. The original image pixels may be referred to as “full” pixels (as opposed to “fractional” pixels such as half-pixels and quarter-pixels). The size of the input buffer202shown inFIG. 2is for illustration only. The input buffer202could store any other suitable amount of information, such as multiple 16×16 macroblocks or other blocks of data. The input buffer202represents any suitable storage device or devices.

A subset or portion of the data stored in the input buffer202is transferred to a set of vector registers204. The vector registers204store a subset of the full pixel values from the macroblock stored in the input buffer202. For example, the vector registers204could represent nine sets of six registers, where each set stores six full pixel values from a single row of the macroblock in the input buffer202. In this way, the vector registers204may contain fifty-four full pixel values to be used during the subpixel interpolation process. The vector registers204represent any suitable storage device or devices.

The full pixel values stored in the vector registers204are provided to a horizontal half-pixel interpolation unit206. The horizontal half-pixel interpolation unit206uses the full pixel values to interpolate the values of half-pixels, which are located horizontally between pairs of full pixels in an image. In some embodiments, the horizontal half-pixel interpolation unit206interpolates half-pixel values for multiple rows of the input macroblock in parallel, which helps to reduce the time needed to generate the half-pixel values. The horizontal half-pixel interpolation unit206includes any hardware, software, firmware, or combination thereof for interpolating half-pixel values in the horizontal direction. One example of a portion of the horizontal half-pixel interpolation unit206is shown inFIG. 3, which is described below.

The horizontal half-pixel interpolation unit206provides the identified half-pixel values to a vertical half-pixel interpolation unit208a. The vector registers204provide full pixel values to a vertical half-pixel interpolation unit208b. The vertical half-pixel interpolation units208a-208buse these pixel values to interpolate values of half-pixels located vertically between pairs of full pixels or between pairs of half-pixels (which were generated by the horizontal half-pixel interpolation unit206). In some embodiments, the vertical half-pixel interpolation units208a-208binterpolate half-pixel values for multiple columns of the input macroblock in parallel, which helps to reduce the time needed to identify the half-pixel values. Each of the vertical half-pixel interpolation units208a-208bincludes any hardware, software, firmware, or combination thereof for interpolating half-pixel values in the vertical direction. One example of a portion of the vertical half-pixel interpolation units208a-208bis shown inFIGS. 4A and 4B, which are described below.

Half-pixel values from the horizontal half-pixel interpolation unit206and the vertical half-pixel interpolation units208a-208bare stored in an intermediate buffer210. Full pixel values from the vector registers204are also stored in the intermediate buffer210. The intermediate buffer210represents any suitable storage device or devices capable of storing pixel data.

The full pixel values and the half-pixel values stored in the intermediate buffer210are provided to a quarter-pixel interpolation unit212. The quarter-pixel interpolation unit212uses the pixel values to interpolate values for quarter-pixels. The quarter-pixels are located horizontally, vertically, and diagonally between full pixels and half-pixels or between half-pixels. In some embodiments, the quarter-pixel interpolation unit212interpolates quarter-pixel values for multiple rows and columns of the input macroblock in parallel, which helps to reduce the time needed to identify the quarter-pixel values. The quarter-pixel interpolation unit212includes any hardware, software, firmware, or combination thereof for interpolating quarter-pixel values. One example of a portion of the quarter-pixel interpolation unit212is shown inFIG. 5, which is described below.

The full pixel values and half-pixel values stored in the intermediate buffer210are provided to an output buffer214. The quarter-pixel values from the quarter-pixel interpolation unit212are also provided to the output buffer214. The output buffer214stores the pixel data for retrieval by a component external to the subpixel interpolator200. For example, the output buffer214may store the pixel data so that the motion compensator144may retrieve and analyze the pixel data. The output buffer214represents any suitable storage device or devices capable of storing pixel data.

The subpixel interpolator200shown inFIG. 2helps to reduce the complexity and increase the speed of subpixel interpolations. For example, the vector registers204and buffers202,210,214are capable of storing groups of pixel values (full, half, and/or quarter). This helps to reduce the number of load and store operations needed during the interpolation process. Also, conventional devices implementing the H.264 standard usually perform a transpose operation after the horizontal interpolation to transfer data from rows to columns for vertical interpolation. The subpixel interpolator200uses the vector registers204to eliminate the need for the transpose operation, which also helps to reduce the time needed to perform the interpolation process. Further, data from the vector registers204is fed directly to the interpolation units206,208b, and data from the interpolation unit206is fed directly to the interpolation unit208a. Furthermore, as explained in more detail below, the architecture of the subpixel interpolator200is designed in a pipelined fashion, allowing many subpixels to be generated per clock cycle after an initial latency.

In addition, both vertical and horizontal interpolation can be performed concurrently. In this embodiment, the subpixel interpolator200processes nine lines of pixels and generates four sets of outputs in parallel. This allows, for example, the subpixel interpolator200to generate a first set of half-pixels, a second set of half-pixels, and a third set of half-pixels. The subpixel interpolator200also generates a first set of quarter-pixels using the first set of half-pixels, where the first set of quarter-pixels are generated concurrently with the second set of half-pixels. The subpixel interpolator200further generates a second set of quarter-pixels using the second set of half-pixels, where the second set of quarter-pixels generated concurrently with the third set of half-pixels. In particular embodiments, the half-pixel and quarter-pixel interpolations are performed in-place, and seventeen half-pixels and forty-eight quarter-pixels are computed per cycle. This helps to increase the throughput of the subpixel interpolator200. In this document, the term “concurrent” and its derivatives and the phrase “in parallel” refer to an overlap in the performance of two or more activities, whether the overlap is complete or partial.

In particular embodiments, each 16×16 input macroblock is processed by the subpixel interpolator200, and the subpixel interpolator200outputs fifteen 16×16 blocks. The fifteen 16×16 output blocks contain full pixels, half-pixels, and quarter-pixels. Also, in particular embodiments, the subpixel interpolator200shown inFIG. 2could be implemented as a co-processor for use with a processor performing video compression or decompression. The co-processor could represent a four-way very long instruction word (VLIW) processor capable of performing one load, one store, and two arithmetic operations per instruction. The instructions could represent single instruction multiple data (SIMD) instructions.

AlthoughFIG. 2illustrates one example of a subpixel interpolator200, various changes may be made toFIG. 2. For example, the size of the input macroblock (16×16) and the size of the set of vector registers204(9×6) are for illustration only.

FIG. 3illustrates an example horizontal half-pixel interpolator300according to one embodiment of this disclosure. The embodiment of the horizontal half-pixel interpolator300shown inFIG. 3is for illustration only. Other embodiments of the horizontal half-pixel interpolator300could be used without departing from the scope of this disclosure. Also, for ease of explanation, the horizontal half-pixel interpolator300is described as forming part of the horizontal half-pixel interpolation unit206in the subpixel interpolator200ofFIG. 2. The horizontal half-pixel interpolator300could be used in any other system or device.

In this example, the horizontal half-pixel interpolator300includes six input registers302a-302f. The input registers302a-302fare capable of storing six different pixel values, such as full pixel values received from the vector registers204. The input registers302a-302fform a stage-shift register304, where the full pixel values are shifted from one register to another. The first input register302areceives the full pixel value from one of the vector registers204. Each remaining input register302b-302freceives a full pixel value from a previous input register302a-302e, respectively. The input registers302a-302finclude any structure capable of storing pixel values.

The horizontal half-pixel interpolator300also includes eight adders306a-306hand four shifters308a-308d. Each of the adders306a-306hincludes any hardware, software, firmware, or combination thereof for adding two or more input values. Each of the shifters308a-308dincludes any hardware, software, firmware, or combination thereof for shifting values by one or more bit positions in one or more directions.

Each of the adders306a-306creceives and sums two full pixel values from two of the input registers302a-302f. The adder306dreceives and sums the output of the adder306aand a constant value310. The adder306ereceives and sums the output of the adder306band the output of the shifter308a. The shifter308ashifts the output of the adder306bto the left by two bit positions (equivalent to multiplying the output of the adder306bby 4). In effect, the adder306eoutputs a value equal to five times the output of the adder306b.

The adder306freceives and sums the outputs of the shifters308b-308c. The shifters308b-308cshift the output of the adder306cto the left by four bit positions (equivalent to multiplying the output of the adder306cby 16) and two bit positions, respectively. In effect, the adder306foutputs a value equal to twenty times the output of the adder306c.

The adder306greceives the outputs of the adders306eand306f. The adder306gsubtracts the output of the adder306efrom the output of the adder306f. The adder306hreceives and sums the outputs of the adders306dand306g. The shifter308dshifts the output of the adder306hto the right by five bit positions (equivalent to dividing the output of the adder306hby 32). The output of the shifter308drepresents one half-pixel value computed using the six full pixel values stored in the input registers302a-302f.

In the illustrated embodiment, the adders306a-306hand the shifters308a-308dform a four-stage pipelined architecture. The first stage is represented by the adders306a-306c. The second stage is represented by the adders306d-306fand shifters308a-308c. The third stage is represented by the adder306g, and the fourth stage is represented by the adder306hand the shifter308d. Because there are four stages, the horizontal half-pixel interpolator300has a latency of three cycles, and after that one half-pixel is generated per clock cycle. This embodiment of the horizontal half-pixel interpolator300does not require the use of multipliers, which may slow the operation of the horizontal half-pixel interpolator300.

In the embodiment of the subpixel interpolator200shown inFIG. 2, nine horizontal half-pixel interpolators300could be used in the horizontal half-pixel interpolation unit206. In this embodiment, the nine horizontal half-pixel interpolators300receive full pixel values from nine different rows in the vector registers204. The nine horizontal half-pixel interpolators300then calculate nine different horizontal half-pixels concurrently. Other embodiments of the horizontal half-pixel interpolation unit206using other numbers of horizontal half-pixel interpolators300may be used.

AlthoughFIG. 3illustrates one example of a horizontal half-pixel interpolator300, various changes may be made toFIG. 3. For example, other structures that provide the same functionality as the horizontal half-pixel interpolator300shown inFIG. 3may be used.

FIGS. 4A and 4Billustrate an example vertical half-pixel interpolator400and an arrangement450of vertical half-pixel interpolators400according to one embodiment of this disclosure. The embodiment of the vertical half-pixel interpolator400shown inFIG. 4Aand the arrangement450shown inFIG. 4Bare for illustration only. Other embodiments of the vertical half-pixel interpolator400and other arrangements450could be used without departing from the scope of this disclosure. Also, for ease of explanation, the vertical half-pixel interpolator400and arrangement450are described as forming part of the vertical half-pixel interpolation units208a-208bin the subpixel interpolator200ofFIG. 2. The vertical half-pixel interpolator400and arrangement450could be used in any other system or device.

InFIG. 4A, the vertical half-pixel interpolator400includes six input registers402a-402f. The input registers402a-402fare capable of storing six different pixel values used to generate half-pixel values. For example, if the vertical half-pixel interpolator400is used in the vertical half-pixel interpolation unit208aofFIG. 2, the pixel values stored in the input registers402a-402frepresent half-pixel values generated by the horizontal half-pixel interpolation unit206. If the vertical half-pixel interpolator400is used in the vertical half-pixel interpolation unit208bofFIG. 2, the pixel values stored in the input registers402a-402frepresent full pixel values from the vector registers204. The input registers402a-402finclude any structure capable of storing pixel values.

The vertical half-pixel interpolator400also includes eight adders404a-404hand four shifters406a-406d. Each of the adders404a-404hincludes any hardware, software, firmware, or combination thereof for adding two or more input values. Each of the shifters406a-406dincludes any hardware, software, firmware, or combination thereof for shifting values by one or more bit positions in one or more directions.

Each of the adders404a-404creceives and sums pixel values from two of the input registers402a-402f. The adder404dreceives and sums the output of the adder404aand a constant value408. The adder404ereceives and sums the output of the adder404band the output of the shifter406a, which shifts the output of the adder404bto the left by two bit positions. The adder404freceives and sums the outputs of the shifters406b-406c, which shift the output of the adder404cto the left by four bit positions and two bit positions, respectively. The adder404greceives and subtracts the output of the adder404efrom the output of the adder404f. The adder404hreceives and sums the outputs of the adders404dand404g. The shifter406dshifts the output of the adder404hto the right by five bit positions. The output of the shifter406drepresents one half-pixel value computed using the six pixel values (full pixel values or half-pixel values) stored in the input registers402a-402f

In the illustrated embodiment, the adders404a-404hand the shifters406a-406dform a four-stage pipelined architecture. The vertical half-pixel interpolator400has a latency of three cycles, and after that one half-pixel is generated per clock cycle. This embodiment of the vertical half-pixel interpolator400also does not require the use of multipliers.

In the embodiment of the subpixel interpolator200shown inFIG. 2, four vertical half-pixel interpolators400could be used in each of the vertical half-pixel interpolation units208a-208bfor a total of eight vertical half-pixel interpolators400. This allows the vertical half-pixel interpolation units208a-208bto calculate eight different vertical half-pixels concurrently. Other embodiments of the vertical half-pixel interpolation units208a-208busing other numbers of vertical half-pixel interpolators400may be used.

InFIG. 4B, an arrangement450is illustrated, which may be used in the vertical half-pixel interpolation unit208b. As explained below, a similar arrangement may be used in the vertical half-pixel interpolation unit208a.

In this example, the arrangement450includes four of the vertical half-pixel interpolation units400(VHIU0-VHIU3). Each may have the same or similar structure as shown inFIG. 4A. The arrangement450also includes a column502of vector registers204, which in the example above inFIG. 2includes nine vector registers. The arrangement450further includes a permutation unit504, which routes data from the column502of vector registers204to the vertical half-pixel interpolation units400.

In the example shown inFIG. 2, the vector registers204include six rows and nine columns of registers. Denote the fifty-four vector registers204as R0through R53. In this example, the first row includes R0-R5, the second row includes R6-R11, and the last row includes R48-R53. Data from the vector registers204is fed to the horizontal half-pixel interpolation unit206by row, and data from the vector registers204is fed to the vertical half-pixel interpolation unit208bby column.

To enable providing data to the vertical half-pixel interpolators400by column, the arrangement450uses the permutation unit504. The permutation unit504represents a Single Instruction Multiple Data (SIMD) permutation unit embedded in the vertical half-pixel interpolation unit208b. The permutation unit504selects the appropriate inputs for each of the four vertical half-pixel interpolators400. In particular, the first and last register values R1and R49are each provided to a single vertical half-pixel interpolator. The second and eighth register values R7and R43are each provided to two vertical half-pixel interpolators. The third and seventh register values R13and R37are each provided to three vertical half-pixel interpolators. The fourth, fifth, and sixth register values R19, R25, and R31are each provided to four vertical half-pixel interpolators. A single SIMD instruction is used to activate vertical half-pixel interpolation unit208band provide data from the column502of registers to the vertical half-pixel interpolators400. Four half-pixels are then computed in parallel.

The column502of vector registers shown inFIG. 4Brepresents the second column in the set of vector registers204. During a subsequent clock cycle, the permutation unit504could retrieve and provide data from the third column in the set of vector registers204. During another subsequent clock cycles, the permutation unit504could retrieve and provide data from other columns in the set of vector registers204. In this way, the vertical half-pixel interpolation unit208bavoids the use of transpose operations.

As noted above, a similar arrangement could be used in the vertical half-pixel interpolation unit208a. As shown inFIG. 4B, the data provided to the vertical half-pixel interpolation unit208bcomes from the vector registers204. As shown inFIG. 2, the data provided to the vertical half-pixel interpolation unit208acomes from the horizontal half-pixel interpolation unit206. As a result, the same or similar permutation unit504may be used in the vertical half-pixel interpolation unit208awith a different input source of data.

AlthoughFIGS. 4A and 4Billustrate one example of a vertical half-pixel interpolator400and an arrangement450of vertical half-pixel interpolators400, various changes may be made toFIGS. 4A and 4B. For example, other structures that provide the same functionality as the vertical half-pixel interpolator400shown inFIG. 4Amay be used. Also, other arrangements that route pixel data to the vertical half-pixel interpolators400may be used.

FIG. 5illustrates an example quarter-pixel interpolator500according to one embodiment of this disclosure. The embodiment of the quarter-pixel interpolator500shown inFIG. 5is for illustration only. Other embodiments of the quarter-pixel interpolator500could be used without departing from the scope of this disclosure. Also, for ease of explanation, the quarter-pixel interpolator500is described as forming part of the quarter-pixel interpolation unit212in the subpixel interpolator200ofFIG. 2. The quarter-pixel interpolator500could be used in any other system or device.

In this example, the quarter-pixel interpolator500includes two input registers502a-502b. The input registers502a-502bare capable of storing two different pixel values. The pixel values may represent a full pixel value and a half-pixel value or two half-pixel values. The input registers502a-502binclude any structure capable of storing pixel values.

The quarter-pixel interpolator500also includes two adders504a-504band a shifter506. Each of the adders504a-504bincludes any hardware, software, firmware, or combination thereof for adding two or more input values. The shifter506includes any hardware, software, firmware, or combination thereof for shifting values by one or more bit positions in one or more directions.

The adder504areceives and sums the pixel values from the input registers502a-502b. The adder504dreceives and sums the output of the adder504aand a constant value508. The shifter506shifts the output of the adder504bto the right by one bit position (equivalent to dividing the output of the adder504bby 2). The output of the shifter506represents one quarter-pixel value computed using the two pixel values stored in the input registers502a-502b.

In the illustrated embodiment, the adders504a-504band the shifter506form a two-stage pipelined architecture. The quarter-pixel interpolator500has a latency of one cycle, and after that one quarter-pixel is generated per clock cycle. This embodiment of the quarter-pixel interpolator500does not require the use of multipliers.

In the embodiment of the subpixel interpolator200shown inFIG. 2, forty-eight quarter-pixel interpolators500could be used in the quarter-pixel interpolation unit212. This allows the quarter-pixel interpolation unit212to calculate forty-eight different quarter-pixels concurrently. Other embodiments of the quarter-pixel interpolation unit212using other numbers of quarter-pixel interpolators500may be used.

Collectively, the subpixel interpolator200generates up to nine horizontal half-pixels, eight vertical half-pixels, and forty-eight quarter-pixels each clock cycle. If a 16×16 macroblock is received as input, the output of the subpixel interpolator200could be organized as a 64×64 block. Denote the top-left pixel of the 64×64 output block as o0,0and the bottom-right pixel as o63,63. Table 1 illustrates the subpixel interpolation process performed by the subpixel interpolator200. In this table, the output values ov,hare indexed first by their vertical index v and then by their horizontal index h.

As shown in Table 1 and discussed above, there is a three-cycle latency before the first half-pixel values are generated. After that, nine horizontal half-pixels and eight vertical half-pixels may be produced per clock cycle, and it will take fifteen cycles to process the remaining pixels in each line of the 16×16 macroblock. Also, two extra clock cycles are needed to complete the quarter-pixel calculations. As a result, computation of the quarter-pixels for each line of the 16×16 macroblock will take twenty-one clock cycles. Because four lines of the 16×16 macroblock may be processed concurrently, computation of all fractional pixels for a 16×16 macroblock will take eighty-four clock cycles.

AlthoughFIG. 5illustrates one example of a quarter-pixel interpolator500, various changes may be made toFIG. 5. For example, other structures that provide the same functionality as the quarter-pixel interpolator500shown inFIG. 5may be used.

FIG. 6illustrates an example half-pixel interpolation600involving an image macroblock according to one embodiment of this disclosure. In particular,FIG. 6illustrates an example half-pixel interpolation600performed by the horizontal half-pixel interpolation unit206and the vertical half-pixel interpolation units208a-208bin the subpixel interpolator200ofFIG. 2, where each interpolation makes use of six full pixels (e.g., three on either side of a subject pixel for horizontal interpolation and three above and three below a subject pixel for vertical interpolation). The subpixel interpolator200ofFIG. 2may operate in any other suitable manner without departing from the scope of this disclosure.

The vector registers204in the subpixel interpolator200store nine rows of six full pixel values (every fourth pixel inFIG. 6). In this example, full pixels are denoted as pixels with left-to-right diagonal hatching, such as pixel602, inFIG. 6. Half-pixels interpolated by the subpixel interpolator200during a first iteration/clock cycle are denoted as pixels with right-to-left diagonal hatching, such as pixel604, inFIG. 6. Half-pixels interpolated by the subpixel interpolator200during a second iteration/clock cycle are denoted as pixels with stipling, such as pixel606, inFIG. 6.

Take the second iteration as an example. Each horizontal half-pixel interpolator300in the interpolation unit206receives the values of six full pixels602in one of the rows inFIG. 6. Using those full pixels602, the nine horizontal half-pixel interpolators300generate the half-pixels606shown in column608ofFIG. 6.

Each vertical half-pixel interpolator400in the interpolation unit208breceives six of the nine full pixels602in column610ofFIG. 6. Those vertical half-pixel interpolators400then generate the four half-pixels606shown in column610ofFIG. 6. Also, each vertical half-pixel interpolator400in the interpolation unit208areceives six of the nine half-pixels604in column612ofFIG. 6. The half-pixels604in column612were generated by the horizontal half-pixel interpolation unit206during the first iteration. These vertical half-pixel interpolators400then generate the four half-pixels606shown in column612ofFIG. 6.

In this way, the horizontal half-pixel interpolation unit206and the vertical half-pixel interpolation units208a-208bmay generate seventeen half-pixel values in parallel. This architecture helps to reduce the delay associated with the subpixel interpolation process and increase the throughput of the subpixel interpolator200.

AlthoughFIG. 6illustrates one example of a half-pixel interpolation600involving an image macroblock, various changes may be made toFIG. 6. For example, the half-pixel interpolation could occur in any other suitable manner, such as when more or less half-pixels are generated per iteration.

FIG. 7illustrates an example quarter-pixel interpolation700involving an image macroblock according to one embodiment of this disclosure. In particular,FIG. 7illustrates an example quarter-pixel interpolation700performed by the quarter-pixel interpolation unit212in the subpixel interpolator200ofFIG. 2. The subpixel interpolator200ofFIG. 2may operate in any other suitable manner without departing from the scope of this disclosure.

In this example, full pixels are again denoted as gray pixels, such as pixel702, inFIG. 7. Half-pixels interpolated by the subpixel interpolator200(both vertical and horizontal) are denoted as hatched pixels, such as pixel704, inFIG. 7. Quarter-pixels interpolated by the subpixel interpolator200are denoted as cross-hatched pixels, such as pixel706, inFIG. 7.

As shown inFIG. 7, each quarter-pixel706is located horizontally, vertically, or diagonally between a full pixel702and a half-pixel704or between two half-pixels704. Each quarter-pixel706is determined using those two surrounding pixel values.

The quarter-pixel interpolation unit212may calculate forty-eight different quarter-pixel values during each clock cycle/iteration of the quarter-pixel interpolation unit212. This may be done in parallel with the half-pixel interpolation units206,208a-208b. For example, the half-pixel interpolation units206,208a-208bmay generate seventeen half-pixels. The quarter-pixel interpolation unit212receives those half-pixels and generates forty-eight quarter pixels. As the quarter-pixel interpolation unit212is generating those quarter-pixels, the half-pixel interpolation units206,208a-208bmay be generating another seventeen half-pixels, which are later received by the quarter-pixel interpolation unit212. In this way, the interpolation units206,208a-208b,212may operate concurrently to quickly generate fractional pixels.

As shown inFIG. 7, the subpixel interpolator200calculates three half-pixels704and twelve quarter-pixels706for each full pixel702in an image. For 16×16 macroblocks, this means that the subpixel generator200outputs 3,840 (16*16*15) full and fractional pixels per macroblock. These half-pixels704and quarter-pixels706may be used to provide improved motion compensation when compressing/decompressing video information. Using the architecture shown inFIGS. 2-5, these half-pixels704and quarter-pixels706may be generated with less delay and lower computational overhead than conventional H.264 and other video encoders/decoders.

AlthoughFIG. 7illustrates one example of a quarter-pixel interpolation700involving an image macroblock, various changes may be made toFIG. 7. For example, the quarter-pixel interpolation could occur in any other suitable manner, such as when more or less quarter-pixels are generated per iteration.

FIG. 8illustrates additional details of an example half-pixel and quarter-pixel interpolation800involving an image macroblock according to one embodiment of this disclosure.FIG. 8uses the same shading to distinguish full pixels, half-pixels, and quarter-pixels asFIG. 7.

InFIG. 8, upper-case letters denote full pixels (such as luminance pixels), while lower case letters denote half-pixels and quarter-pixels. The half-pixels, such as pixels b and h, are calculated by horizontal half-pixel interpolators300and vertical half-pixel interpolators400. In the embodiments shown inFIGS. 3 and 4, each of the interpolators300,400acts as a six-tap finite impulse response (FIR) filter. In the H.264 standard, the coefficients of the six-tap FIR filter are (1, −5, 20, 20, −5, 1)/32. The horizontal half-pixel interpolators300calculate each half-pixel using six full pixel values in a row. The vertical half-pixel interpolators400calculate each half-pixel using six full pixel values or six half-pixel values in a column.

In this embodiment, the values of the half-pixels b and h can be represented using the formulas:
b=(E−5F+20G+20H−5I+J+16)/32  (1)
h=(A−5C+20G+20M−5R+T+16)/32.  (2)
Each result may be rounded up to the nearest integer. Values for the half-pixels aa, bb, s, gg, and hh are calculated in the same way as b. Values for cc, dd, m, ee, and ff are calculated in the same way as h. The value for the half-pixel j can be calculated by applying the six-tap filter horizontally (using cc, dd, h, m, ee, and ff) or vertically (using aa, bb, b, s, gg, and hh), which is represented using the formulas:
j=(cc−5dd+20h+20m−5ee+ff+16)/32  (3)
j=(aa−5bb+20b+20s−5gg+hh+16)/32.  (4)

Once the half-pixel values are available, the quarter-pixel interpolators500calculate the quarter-pixel values. The quarter-pixel values are calculated using linear interpolation, and the results are rounded up to the nearest integer. For example, values of the quarter-pixels a, d, and e can be represented using the formulas:
a=(G+b+1)/2  (5)
d=(G+h+1)/2  (6)
e=(b+h+1)/2.  (7)
Values for the remaining quarter pixels may be calculated in a similar manner.

AlthoughFIG. 8illustrates additional details of one example of half-pixel and quarter-pixel interpolation involving an image macroblock, various changes may be made toFIG. 8. For example, more or less half-pixels and quarter-pixels could be generated and used in each iteration of the subpixel interpolator200.

FIG. 9illustrates an example eighth-pixel interpolation900involving an image macroblock according to one embodiment of this disclosure. In some embodiments, the subpixel interpolator200ofFIG. 2may need to identify eighth-pixel values, such as when 4:2:0 sampling is used and quarter-pixel luminance values require eighth-pixel chrominance values.

In this example, the full pixels are again denoted as gray pixels, such as pixel902, inFIG. 9. The eighth-pixels are denoted as cross-hatched pixels, such as pixel904inFIG. 9. In this example, eighth-pixels904are calculated using linear interpolation involving the four surrounding full pixels902. However, the eighth-pixels904could be calculated in any other suitable manner. For example, the eighth-pixels904could be calculated using neighboring half-pixels or quarter-pixels or a combination of full, half-, and/or quarter-pixels.

AlthoughFIG. 9illustrates an example eighth-pixel interpolation900involving an image macroblock, various changes may be made toFIG. 9. For example, the eighth-pixel904could be generated in any other suitable manner.

FIG. 10illustrates an example method1000for fast implementation of subpixel interpolation according to one embodiment of this disclosure. For ease of explanation, the method1000is described with respect to the subpixel interpolator200ofFIG. 2. The method1000could be used by any other device and in any other system.

The subpixel interpolator200receives a macroblock containing video information at step1002. This may include, for example, the subpixel interpolator200receiving a 16×16 macroblock and storing the macroblock in an input buffer202. The 16×16 macroblock may contain 256 full pixel values.

The subpixel interpolator200selects a subset of the full pixel values in the macroblock at step1004. This may include, for example, the subpixel interpolator200storing six full pixel values from each of nine rows of the macroblock in the vector registers204.

The subpixel interpolator200generates horizontal half-pixels using the subset of full pixels at step1006. This may include, for example, each horizontal half-pixel interpolator300in the interpolation unit206receiving full pixel values from the vector registers204. This may also include the various stages of the horizontal half-pixel interpolators300adding and shifting values to produce the horizontal half-pixels. This may further include storing the horizontal half-pixels in the intermediate buffer210.

The subpixel interpolator200generates vertical half-pixels using the subset of full pixels at step1008. This may include, for example, each vertical half-pixel interpolator400in the interpolation unit208breceiving full pixel values from the vector registers204. This may also include the various stages of the vertical half-pixel interpolators400adding and shifting values to produce the vertical half-pixels. This may further include storing the vertical half-pixels in the intermediate buffer210.

The subpixel interpolator200generates vertical half-pixels using the horizontal half-pixels at step1010. This may include, for example, each vertical half-pixel interpolator400in the interpolation unit208areceiving the horizontal half-pixels from the interpolation unit206. This may also include the various stages of the vertical half-pixel interpolators400adding and shifting values to produce the vertical half-pixels. This may further include storing the vertical half-pixels in the intermediate buffer210.

The subpixel interpolator200generates quarter-pixels using the full pixels and half-pixels at step1012. This may include, for example, each quarter-pixel interpolator500in the interpolation unit212receiving a full pixel and a half-pixel or two half-pixels from the intermediate buffer212. This may also include the various stages of the quarter-pixel interpolators500adding and shifting values to produce the quarter-pixels.

The subpixel interpolator200stores the various full pixels, half-pixels, and quarter-pixels at step1014. This may include, for example, storing the full pixels, half-pixels, and quarter-pixels in the output buffer214. At this point, the pixel data in the output buffer214may be retrieved and used in any suitable manner. For example, the pixel data could be retrieved and used to perform motion compensation. However, the pixel data could be used for any other suitable purpose.

The subpixel interpolator200determines if the processing of the macroblock is complete at step1016. If not, the subpixel interpolator200returns to step1004to select another subset of pixels from the current macroblock. Otherwise, the processing of the macroblock is complete, and the method1000ends. At this point, any suitable actions may occur, such as repeating the method1000for a new macroblock.

AlthoughFIG. 10illustrates one example of a method1000for fast implementation of subpixel interpolation, various changes may be made toFIG. 10. For example, althoughFIG. 10illustrates the steps of the method1000occurring serially, various steps shown inFIG. 10may be performed in parallel. As a particular example, steps1006-1010could be performed in parallel to produce a new set of half-pixels and to produce a set of quarter-pixels using a prior set of half-pixels during each iteration of the subpixel interpolator200.