Methods and apparatus for parallel implementations of 4:4:4 coding

There are provided methods and apparatus for parallel implementations of 4:4:4 coding. A video encoder for encoding video signal data for an image block includes an encoder for encoding all color components of the image block by selecting a common block partition and a common spatial prediction mode. The common block partition and the common spatial prediction mode are selected by concurrently evaluating all of the color components in parallel.

FIELD OF THE INVENTION

The present invention relates generally to video encoding and decoding and, more particularly, to methods and apparatus for parallel 4:4:4 video encoding and decoding.

BACKGROUND OF THE INVENTION

In a first prior art approach, an independent block partition and, hence, independent spatial predictors are selected for each color component. For example, the 16×16 block partition with one spatial prediction mode may be selected for the red channel, an 8×8 block partition with four spatial prediction modes may be selected for the green channel, and a 4×4 block partition with sixteen spatial prediction modes may be selected for the blue channel.

Conversely, in a second prior art approach, a common block partition is used for all three channels, which is consistent with a definition of macroblock type in a third prior art approach. In addition, a common set of spatial predictors are used for all three channels. Following the above example, in the case of the second prior art approach, the mode selector might have selected an 8×8 block partition as the macroblock type, and each channel would use exactly the same four spatial prediction modes by minimizing the predefined cost function. Obviously, the common mode approach greatly reduces the decoder complexity compared with the independent mode where three spatial prediction modes instead of a single spatial prediction mode have to be decoded for every coding block. In the meantime, since using a common prediction mode instead of three separate modes reduces the total number of bits to encode the spatial prediction information, the common mode solution results in better overall compression performance compared with the independent mode, especially for the mid and low bitrate range. A typical prior art implementation of the common mode method proceeds by examining each channel in turn (i.e., serially) to determine the best spatial predictors. This is a disadvantage when compared to the implementation of the independent channel method, since in that case the optimum spatial predictor for each channel can be derived in parallel in a straightforward way, thus potentially increasing the speed at which the video data is encoded.

SUMMARY OF THE INVENTION

These and other drawbacks and disadvantages of the prior art are addressed by the present invention, which is directed to methods and apparatus for parallel 4:4:4 video encoding and decoding.

According to an aspect of the present principles, there is provided a video encoder for encoding video signal data for an image block. The video encoder includes an encoder for encoding all color components of the image block by selecting a common block partition and a common spatial prediction mode. The common block partition and the common spatial prediction mode are selected by concurrently evaluating all of the color components in parallel.

According to another aspect of the present principles, there is provided a video encoder for encoding video signal data for an image block. The video encoder includes an encoder for encoding all color components of the image block by selecting a common block partition and a common spatial prediction mode. The common block partition and the common spatial prediction mode are selected using a hybrid serial-parallel approach that serially evaluates spatial prediction modes in a set of spatial prediction modes from which the common spatial prediction mode is selected, and that simultaneously evaluates all of the color components in parallel to accomplish a decision for each of the spatial prediction modes in the set.

According to yet another aspect of the present principles, there is provided a method for encoding video signal data for an image block. The method includes encoding all color components of the image block by selecting a common block partition and a common spatial prediction mode. The common block partition and the common spatial prediction mode are selected by concurrently evaluating all of the color components in parallel.

According to still another aspect of the present principles, there is provided a method for encoding video signal data for an image block. The method includes encoding all color components of the image block by selecting a common block partition and a common spatial prediction mode. The common block partition and the common spatial prediction mode are selected using a hybrid serial-parallel approach that serially evaluates spatial prediction modes in a set of spatial prediction modes from which the common spatial prediction mode is selected, and that simultaneously evaluates all of the color components in parallel to accomplish a decision for each of the spatial prediction modes in the set.

DETAILED DESCRIPTION

The present invention is directed to methods and apparatus for parallel 4:4:4 video encoding. Advantageously, the present invention provides methods and apparatus for selecting an optimum spatial prediction mode for intra coded pictures using all three color channels simultaneously when the common block partition and spatial prediction encoding method is employed.

The present description illustrates the principles of the present invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the invention and are included within its spirit and scope.

Reference in the specification to “one embodiment” or “an embodiment” of the present principles means that a particular feature, structure, characteristic, and so forth described in connection with the embodiment is included in at least one embodiment of the present principles. Thus, the appearances of the phrase “in one embodiment” or “in an embodiment” appearing in various places throughout the specification are not necessarily all referring to the same embodiment.

Turning toFIG. 1, an exemplary video encoder is indicated generally by the reference numeral100. A non-inverting input of a combiner110and a first input of a motion and spatial prediction estimator180are available as inputs of the encoder100.

An output of the combiner110is connected in signal communication with an input of a transformer120. An output of the transformer120is connected in signal communication with an input of a quantizer130. An output of the quantizer130is connected in signal communication with an input of variable length coder (VLC)140. An output of the variable length coder140is available as an output of the video encoder100.

The output of the quantizer130is further connected in signal communication with an input of an inverse quantizer150. An output of the inverse quantizer150is connected in signal communication with an input of an inverse transformer160. An output of the inverse transformer160is connected in signal communication with an input of a deblocking filter195. The output of the deblocking filter195is connected in signal communication with an input of a reference picture store170. A bi-directional input/output of the reference picture store170is connected in signal communication with a second input of the motion and spatial prediction estimator180. An output of the motion and spatial prediction estimator180is connected in signal communication with a first input of a motion compensator and spatial predictor190. An output of the reference picture store170is connected in signal communication with a second input of the motion compensator and spatial predictor190. The output of the motion compensator and spatial predictor190is connected in signal communication with an inverting input of the combiner110.

Turning toFIG. 2, an exemplary method for 4:4:4 video coding by encoding all three color channels is indicated generally by the reference numeral200. The method200includes a start block205that passes control to a loop limit block210. The loop limit block210performs a loop for each image in the sequence, where all three color components (red, green, and blue) are considered, and passes control to a loop limit block215. The loop limit block215performs a loop for each block in an image, and passes control to a function block220. The function block220forms a motion compensated or spatial prediction of the current image block for all color components, and passes control to a function block225. The function block225subtracts the motion compensated or spatial prediction from the current image block to form a prediction residual, and passes control to a function block230. The function block230transforms and quantizes the prediction residual, and passes control to a function block235. The function block235inverse transforms and quantizes the prediction residual to form a coded prediction residual, and passes control to a function block240. The function block240adds the coded residual to the prediction to form a coded picture block, and passes control to a loop limit block245. The end loop block245ends the loop over each block in the image and passes control to a loop limit block250. The loop limit block250ends loops over each image in the sequence, and passes control to an end block255.

Turning toFIG. 3, an exemplary method for determining the optimum spatial predictor for all three color channels in parallel as per function block220ofFIG. 2is indicated generally by the reference numeral300. The method300includes a start block305that passes control to a loop limit block310. The loop limit block310performs a loop, for each block partition (thus, performing three loops, one for 16×16 partitions, one for 8×8 partitions, and one for 4×4 partitions), in a block and passes control to a loop limit block315. The loop limit block315performs a loop, for each spatial mode for a particular block partition (the number of loops depends on the block partition) and passes control to a loop limit block320. The loop limit block320performs a loop for each color component in an image (thus, performing three parallel loops, one for red, one for green, and one for blue), and passes control to a function block325. The function block325forms a spatial prediction of the current image block for the corresponding block partition, spatial prediction mode, and color component (based on which loop from loop limit blocks310,315, and320), and passes control to a function block330. The function block330determines the cost function for the spatial prediction, and passes control to loop limit block335. The loop limit block335ends the parallel loops over each color component in the image, and passes control to block340. The function block340evaluates and stores the lowest cost spatial predictor of the color components determined by loop limit block320, and passes control to an end loop block345. The end loop block345ends the loop over each spatial prediction mode and passes control to a function block350. The function block350evaluates and stores the lowest cost spatial predictor of the spatial predictor modes determined by loop limit block315, and passes control to an end loop block355. The end loop block355ends the loop over each block partition determined by loop limit block310and passes control to a function block360. The function block360evaluates and stores the lowest cost spatial predictor of the block partitions determined by loop limit block310, and passes control to an end block365.

The present principles are directed to a method and apparatus for parallel implementation of the Advanced 4:4:4 Profile for the International Organization for Standardization/international Electrotechnical Commission (ISO/IEC) Moving Picture Experts Group-4 (MPEG-4) Part 10 Advanced Video Coding (AVC) standard/International Telecommunication Union, Telecommunication Sector (ITU-T) H.264 recommendation (hereinafter the “MPEG-4 AVC standard”).

In the common prediction mode method of the above-referenced second prior art approach, each channel uses the same block partition and the same spatial prediction modes. A comparison is described herein between the common prediction mode method of the above-referenced second prior art approach and the independent mode selection method of the first prior art approach, the latter where each channel may have independent block partitions and independent spatial prediction modes. It is shown herein in accordance with an embodiment of the present principles that for the case of maximum parallelism, only one additional comparison is performed for the common mode case as compared to the independent mode case. It is also shown herein, with respect to a case of a hybrid serial/parallel solution where the channels are encoded in parallel but the processes themselves are serial, that the common-mode method requires no more memory or space than the independent mode method.

In this analysis of parallelism we note that there are many possible implementation schemes and we will only be discussing a subset of the possible solutions. However, given the teachings of the present principles provided herein, one of ordinary skill in this and related arts will contemplate these and various other parallel implementation schemes in accordance with the present principles, while maintaining the scope of the present principles.

An embodiment will now be described regarding the parallel analysis of independent mode selection with respect toFIGS. 4 and 5.

Turning toFIG. 4, a spatial predictor selection apparatus with independent block partition for the red color component (also referred to as the red channel or the R channel) is indicated generally by the reference numeral400. The apparatus400includes a Pred_16×16 processing unit410, a Pred_8×8 processing unit420, a Pred_4×4 processing unit430, and a final mode selection unit440. The three processing units Pred_16×16410, Pred_8×8420, and Pred_4×4430select the best prediction mode(s) from the 16×16, 8×8, and 4×4 block partitions respectively. The output of the processing units is a cost function Ci, best prediction residue ΔRi, and the set of the best prediction modes as determined by the cost function, Pred_modei, where i is in the set {16×16, 8×8, 4×4}. By selecting the smallest cost function among the three values, the final mode selection unit440selects the final BlockPartition and Pred_modeBlockPartitionfor each of the 16×16 blocks of the red channel.

Turning toFIG. 5, the Pred_16×16 processing unit410ofFIG. 4is further shown. The Pred_16×16 processing unit410includes mode processing units501-504for modes1-4, respectively, and a mode selection unit510. Each of the modes is examined by the mode processing units in parallel to determine the cost function C16×16,j(R), where j indicates the mode number. The best mode is then selected by the mode selection unit510using the minimization function and the Pred_modeiand ΔR are output there from.

In the case of Pred_8×8 processing units there are 4 mode processing units and 9 prediction modes for a total of 36 possible cost functions and associated residuals. In the case of Pred_4×4, there are 16 mode processing units and 9 possible modes for a total of 144 possible cost functions and residuals. Thus, in total, there are 184 independent mode processing units required before the cost function selection.

This same scheme as described inFIG. 4andFIG. 5can also be implemented for the G and B channels in a completely independent manner and, thus, can be parallelized for all three channels. Thus, there are a total of 552 independent processing units required for complete parallelism.

An embodiment will now be described regarding the parallel analysis of common-mode selection with respect toFIGS. 6 and 7. Turning toFIG. 6, a spatial predictor selection apparatus with common block partition for the red, green, and blue color components is indicated generally by the reference numeral600. The apparatus600includes a Pred_16×16 processing unit610, a Pred_8×8 processing unit620, a Pred_4×4 processing unit630, and final mode selection unit640. The apparatus600is similar to apparatus400shown inFIG. 4, except the inputs are now all three channels. The cost function CC and Pred_mode are also now a function of all three channels rather than a single channel. However, the parallelism inherent in this stage is exactly as that shown inFIG. 4.

Turning toFIG. 7, the Pred_16×16 processing unit610ofFIG. 6is further shown. The Pred_16×16 processing unit610includes mode processing units701-712, the RGB cost functions CC721-724, and mode selection unit730. In this case, there are three processing units for each mode. Compared toFIG. 4, there is an additional decision block to choose the best mode which is common to all three colors. In this case there are 12 mode processing units which may operate in parallel. Similarly, for the Pred_8×8 case there are 108 mode processing units and for the Pred_4×4 case there are 432 mode processing units. In total, this is the same number of parallel mode processing units as specified above for the independent mode selection case. The main difference is that there is one more decision layer required to determine the best common mode cost function among the three channels.

An embodiment will now be described regarding serial parallel hybrids with respect toFIGS. 8, 9, and 10.

Herein above, an example implementation for maximum parallelism is described, i.e., a case where the minimum number of cascaded elements (and, thus, the minimum time) are required. However, due to memory or space limitations, it may not be possible to completely parallelize the solution. Here, we examine the case for the independent mode selection where we allow a serial solution within channels, but the minimum amount of parallelism required is that all three channels are to be processed simultaneously. This case is shown inFIG. 8for the Pred_mode16×16case, wherein only the R channel is shown for the sake of illustration and brevity. The G and B channels are simply replicated versions of the R channel. In a serial manner, one can iterate from mode1through mode4, at each step evaluating the cost function and then storing a copy of the current best cost, prediction modes, and residuals. At the end the best cost, prediction modes, and residuals are available to be compared to the other block partitions, and only one copy of these values is required to be stored. As was true of the completely parallel solution, no communication is required between the channels. Since three channels are independent we require storing only one copy for each channel simultaneously, for a total of three copies.

Turning toFIG. 8, a serial method for implementing an independent mode for the red channel is indicated generally by the reference numeral800. It is to be appreciated that the green and blue channels are implemented similarly. Thus, given the teachings of the present principles provided herein, one of ordinary skill in this and related arts will readily implement a similar serial method for implementing an independent mode for the green and blue channels, while maintaining the scope of the present principles.

The method800includes a start block802that passes control to a function block805. The function block805processes mode1, and passes control to a function block810. The function block810outputs C16×16(R)=C16×16, 1(R), ΔR=ΔRmode 1, and passes control to a function block815. The function block815processes mode2, and passes control to a decision block820. The decision block820determines whether or not C16×16, 2(R)<C16×6(R). If so, then control is passed to a function block825. Otherwise, control is passed to a function block845. The function block825processes mode3, and passes control to a decision block830. The decision block830determines whether or not C16×16, 3(R)<C16×16(R). If so, then control is passed to a function block835. Otherwise, control is passed to a function block850.

The function block835processes mode4, and passes control to a decision block840. The decision block840determines whether or not C16×16, 4(R)<C16×16(R). If so, then control is passed to a function block860. Otherwise, control is passed to a function block855. The function block860outputs C16×16(R), ΔR, Pred_mode16×16(R), and passes control to an end block865.

The function block845outputs C16×16(R)=C16×16, 2(R), ΔR=ΔRmode2, and passes control to the function block825.

The function block850outputs C16×16(R)=C16×16, 3(R), ΔR=ΔRmode3, and passes control to the function block835.

The function block855outputs C16×16(R)=C16×16, 4(R), ΔR=ΔRmode4, and passes control to the function block860.

Turning toFIG. 9, an exemplary method for determining the optimum spatial predictor for all three color channels in a hybrid serial-parallel fashion as per function block220ofFIG. 2is indicated generally by the reference numeral900. The method900includes a start block905that passes control to a loop limit block910. The loop limit block910performs a loop in sequence, for each block partition (thus, performing three loops, one for 16×16 partitions, one for 8×8 partitions, and one for 4×4 partitions), in a block and passes control to a loop limit block915. The loop limit block915performs a loop in sequence, for each spatial mode for a particular block partition (the number of loops depends on the block partition) and passes control to a loop limit block920. The loop limit block9020performs a loop for each color component in an image (thus, performing three parallel loops, one for red, one for green, and one for blue), and passes control to a function block925. The function block925forms a spatial prediction of the current image block for the corresponding block partition, spatial prediction mode, and color component (based on which loop from loop limit blocks910,915, and920), and passes control to a function block930. The function block930determines the cost function for the spatial prediction, and passes control to loop limit block935. The loop limit block935ends the parallel loops over each color component in the image, and passes control to block940. The function block940evaluates and stores the lowest cost spatial predictor of the color components determined by loop limit block920, and passes control to an end loop block945. The end loop block945ends the loop over each spatial prediction mode and passes control to a function block950. The function block950evaluates and stores the lowest cost spatial predictor of the spatial predictor modes determined by loop limit block915, and passes control to an end loop block955. The end loop block1055ends the loop over each block partition determined by loop limit block910and passes control to a function block960. The function block960evaluates and stores the lowest cost spatial predictor of the block partitions determined by loop limit block910, and passes control to an end block965.

The only restriction here as compared to the case corresponding toFIG. 8is that we proceed in a synchronous manner for all three channels when examining the cost for each prediction mode. Thus, in this case, the red, green, and blue channels are evaluated and all three sets of costs, prediction modes, and residuals are stored. A cost function that is a function of all three costs is evaluated; this step is an additional one when compared to the independent mode case in the previous paragraph. Second, all three channels are evaluated for the next mode. If the combined cost function is better for the next mode, then all three channels' prediction modes and residuals are stored. This continues for the total number of modes required (4 in the 16×16 case). Thus, even for a serial implementation of the common mode case, there is no additional storage required when compared to the serial independent mode implementation when the channels are to be implemented in parallel.

Turning toFIG. 10, a hybrid method for implementing a common mode for the color channels is indicated generally by the reference numeral1000.

The method1000includes a start block1005that passes to a function block1011, a function block1012, and a function block1013. The function block1011processes mode1for the red color channel, and passes control to a function block1015. The function block1012processes mode1for the green color channel, and passes control to the function block1015. The function block1013processes mode1for the blue color channel, and passes control to the function block1015. The function block1015outputs CC16×16(R, G, B)=CC16×16, 1(R, G, B), ΔR=ΔRmode1, ΔG=ΔGmode1, ΔB=ΔBmode1, Pred_mode16×16(R, G, B)=Mode1, and passes control to a function block1021, a function block1022, and a function block1023. The function block1021processes mode2for the red color channel, and passes control to a function block1025. The function block1022processes mode2for the green color channel, and passes control to the function block1025. The function block1023processes mode2for the blue color channel, and passes control to the function block1025.

The function block1025outputs CC16×16, 2(R, G, B), and passes control to a decision block1030.

The decision block1030determines whether or not CC16×16, 2<CC16×16. If, so, then control is passed to a function block1035. Otherwise, control is passed to a function block1041, a function block1042, and a function block1043.

The function block1041processes mode3for the red color channel, and passes control to the function block1050. The function block1042processes mode3for the green color channel, and passes control to the function block1050. The function block1043processes mode3for the blue color channel, and passes control to the function block1050.

The function block1050outputs CC16×16, 3(R, G, B), and passes control to a decision block1055.

The decision block1055determines whether or not CC16×16, 3<CC16×16. If so, then control is passed to a function block1058. Otherwise, control is passed to a function block1061, a function block1062, and a function block1063

The function block1061processes mode4for the red color channel, and passes control to a function block1070. The function block1062processes mode4for the green color channel, and passes control to the function block1070. The function block1063processes mode4for the blue color channel, and passes control to the function block1070.

The function block1070outputs CC16×16, 4(R, G, B), and passes control to a decision block1075. The decision block1075determines whether or not CC16×16, 4<CC16×16. If so, then control is passed to a function block1080. Otherwise, control is passed to a function block1085.

We note that the 8×8 and 4×4 cases may be evaluated in a similar manner. The result does not change if the 8×8 and 4×4 cases are evaluated in parallel or serially, as long as the same degree of parallelism is available in the independent mode and common mode cases.

Thus, as shown herein, contrary perhaps to initial intuition, the common mode selection method can be parallelized, in the sense of processing all three channels simultaneously, to the same degree that an independent mode selection method can in the proposed Advanced 4:4:4 Profile of the MPEG-4 AVC standard.

A description will now be given of some of the many attendant advantages/features of the present invention, some of which have been mentioned above. For example, one advantage/feature is a video encoder for encoding video signal data for an image block, the video encoder including an encoder for encoding all color components of the image block by selecting a common block partition and a common spatial prediction mode. The common block partition and the common spatial prediction mode are selected by concurrently evaluating all of the color components in parallel. Another advantage/feature is the video encoder as described above, wherein the common block partition is a sub-macroblock partition. Moreover, another advantage/feature is the video encoder as described above, wherein the encoder uses a lowest cost function to select the common spatial prediction mode. Further, another advantage/feature is the video encoder as described above, wherein the encoder selects the common block partition from among a set of different block partitions, and evaluates the different block partitions in parallel for each of the color components. Also, another advantage/feature is the video encoder that selects the common block partition from among a set of different block partitions and evaluates the different block partitions in parallel for each of the color components as described above, wherein the encoder selects the common spatial prediction mode from among a set of different spatial prediction modes, and evaluates the different spatial prediction modes in parallel for each of the different block partitions.

Additionally, another advantage/feature is a video encoder for encoding video signal data for an image block, the video encoder including an encoder for encoding all color components of the image block by selecting a common block partition and a common spatial prediction mode. The common block partition and the common spatial prediction mode are selected using a hybrid serial-parallel approach that serially evaluates spatial prediction modes in a set of spatial prediction modes from which the common spatial prediction mode is selected, and that simultaneously evaluates all of the color components in parallel to accomplish a decision for each of the spatial prediction modes in the set. Another advantage/feature is the video encoder as described above, wherein the common block partition is a sub-macroblock partition. Moreover, another advantage/feature is the video encoder as described above, wherein the encoder uses a lowest cost function to select the common spatial prediction mode. Further, another advantage/feature is the video encoder as described above, wherein the encoder selects the common spatial prediction mode from among a set of different spatial prediction modes, and serially evaluates the different spatial prediction modes for each of the different block partitions. Also, another advantage/feature is the video encoder as described above, wherein the encoder selects the common block partition from among a set of different block partitions, and evaluates the different block partitions in parallel for each of the color components. Additionally, another advantage/feature is the video encoder as described above, wherein the encoder selects the common block partition from among a set of different block partitions, and serially evaluates the different block partitions for each of the color components.

These and other features and advantages of the present invention may be readily ascertained by one of ordinary skill in the pertinent art based on the teachings herein. It is to be understood that the teachings of the present invention may be implemented in various forms of hardware, software, firmware, special purpose processors, or combinations thereof.

Although the illustrative embodiments have been described herein with reference to the accompanying drawings, it is to be understood that the present invention is not limited to those precise embodiments, and that various changes and modifications may be effected therein by one of ordinary skill in the pertinent art without departing from the scope or spirit of the present invention. All such changes and modifications are intended to be included within the scope of the present invention as set forth in the appended claims.