FIELD

The present invention relates to video compression generally, and to a method for interframe prediction in video compression.

BACKGROUND

In video compression, an interframe is a frame which is predicted based on a past encoded frame and optionally future encoded frame by using temporal and/or spatial redundancy between the frames. Usually these frames are adjacent frames in a video sequence. Frequently, the only difference between the past and optionally encoded future frames, hereinafter referred to as “reference frames” and the predicted frame is due to movement of the camera or of an object in the predicted frame. In predicting the frame, the encoder will search for matching data in the reference frames and, using motion estimation, will generate a motion vector pointing to the location of the data in the reference frame. Usually, the match is not exact, and the encoder will compute the difference between them as residual values or “residual”, which may be expressed by the equation residual=actual pixels—predicted pixels.

One technique for motion estimation involves block matching which involves dividing the predicted frame into blocks of data (pixels) and searching for similar blocks in the reference frames. The encoder then generates a motion vector which points to the location of the similar blocks in the reference frames. The frames may be partitioned into blocks of 16×16 pixels and into smaller blocks such as 16×8 pixels, 8×16 pixels, 8×8 pixels, 8×4 pixels, 4×8 pixels, and 4×4 pixels. The accuracy of the motion vector may be defined in pixels or partial pixels, for example, 1 pixel, half pixel, ¼ pixel, ⅛ pixel and so on. Generally, a greater accuracy is achieved by a smaller displacement resolution or motion vector resolution (e.g. ⅛ pixel) although this requires a greater number of bits to encode the motion vector and consequently requiring a greater bandwidth which may not be available.FIG. 1schematically shows a section of a frame100with exemplary block partition sizes including a block 16×16 pixels102, a block 8×16 pixels104, a block 16×8 pixels106, a block 8×8 pixels108, a block 4×8 pixels110, a block 4×8 pixels112, and two blocks 4×4 pixels114.

Encoder generating of the motion vector may be described by a three, optionally four step motion vector coding process. The coding process is shown inFIG. 2in flowchart200and described herein below. The number of bits which are required to describe a certain block depends on the block size partitioning of the frame, the motion vector accuracy, the motion vector prediction error, and the code length sent to the decoder which may be a variable code length (VCL).

At an optional step202, the frame may be partitioned into small block sizes, for example 4×4 pixels and motion estimation is performed to determine the motion vector with a high degree of accuracy, for example ¼ pixel.

At step204, the frame may be partitioned into blocks of any suitable size (e.g. 16×8 pixels, 8×16 pixels, 8×8 pixels, 8×4 pixels, 4×8 pixels, and 4×4 pixels). If optional step202was performed, the frame may be partitioned into larger block sizes based on the results of step202if larger block sizes yield the same or similar results as the 4×4 pixels block size. Information associated with the size of the blocks may be coded using variable length coding and transmitted from the encoder to the decoder.

At step206, the accuracy of the motion vector is determined. The accuracy may be a full pixel, ½ pixel, ¼ pixel, or smaller. If optional step202was performed, the accuracy which was chosen in step206may be lower than the accuracy used in step202. For example, if the accuracy used in step202was ¼ pixel, then the accuracy in this step206may be lower, such as ½ pixel or a full pixel if these accuracies yield the same or comparable results as in step202. As in step204, information associated with the accuracy may be coded using variable length coding and transmitted from the encoder to the decoder.

At step207, perform motion estimation using the accuracy from step206. Alternatively, the results of the motion estimation of step202may be used.

At208the video block may be predicted based on the reference block in the reference frame. The prediction error associated with the motion vector may be determined from the reference block. An example of a predictor for the X value of the motion vector may be:
n=ΔXn-1, en=ΔXn−n.

At step209, predict the motion vector from previously encoded motion vectors and calculate motion vector prediction error.

SUMMARY

There is provided, in accordance with an embodiment of the present invention, a method of performing inter-frame prediction in video compression, the method may include partitioning a video frame into superblocks, each superblock may include a plurality of macroblocks; determining an upper boundary on attributes associated with residual blocks of the plurality of macroblocks based on pre-defined constraints on the total number of bits allocated for motion vector descriptions in a superblock; and determining for each macroblock in a superblock a partition size and a motion vector resolution which may yield for all macroblocks in the superblock a motion vector description and a corresponding residual with attributes less than or equal to the upper boundary. Each macroblock of the plurality of macroblocks may include 16×16 pixels.

In some embodiments, the method may include determining a number of bits required to code a motion vector for each of the block partitionings based on predetermined pixel accuracies.

In some embodiments, the method may include determining a residual complexity in a residual block associated with each of the block partitioning.

In some embodiments, the method may include comparing for each block partitioning, the number of bits required to code a motion vector and a residual complexity value associated with the residual block.

In some embodiments, the method may include discarding all block partitionings associated with motion vectors requiring the same number of bits for coding except for the block partitioning with a least residual complexity value.

In some embodiments, the method may include assigning an upper boundary requirement to residual complexity values of residual blocks.

There is provided, in accordance with an embodiment of the present invention, an encoder for generating fixed-rate motion vectors for video compression, the encoder may be configured to partition a video frame into superblocks, each superblock may include a plurality of macroblocks; to determine an upper boundary on attributes associated with residual blocks of the plurality of macroblocks based on pre-defined bit constraints on the total number of bits allocated for motion vector descriptions in a superblock; and to determine for each macroblock in a superblock a partition size and a motion vector resolution which may yield for all macroblocks in the superblock a motion vector description and a corresponding residual with attributes less than or equal to the upper boundary. Optionally, each macroblock of the plurality of macroblocks includes 16×16 pixels.

In some embodiments the encoder may determine a number of bits required to code a motion vector for each of the block partitionings based on a predetermined motion vector resolution. In some embodiments the encoder may determine a residual complexity in a residual block associated with each of the block partitioning.

In some embodiments the encoder may compare for each block partitioning, the number of bits required to code a motion vector and a residual complexity value associated with the residual block. In some embodiments the encoder may discard all block partitionings associated with motion vectors requiring the same number of bits for coding except for the block partitioning with a least residual complexity value. In some embodiments the encoder may assign an upper boundary requirement to residual complexity values of residual blocks.

In some embodiments, the attributes may include a residual complexity. Optionally, the attributes may include a measure of a total energy in the residual blocks. Optionally, the attributes may include a measure of entropy of the quantized DCT taps of the residual blocks.

In some embodiments, the partition size may include any one of a 16×16 pixel size, 16×8 pixel size, 8×16 pixel size, 8×8 pixel size, 8×4 pixel size, 4×8 pixel size, and 4×4 pixel size. In some embodiments, the motion vector resolution may include any one of a full pixel, a half pixel, and a quarter pixel.

