Motion estimation and compensation for video compression
View Patent ↗An encoding method for reducing motion video data sizes using a multitude of variable-sized data blocks that are derived from spatial translation vectors and the motion field of an image. Using variable-block sizes to characterize the groups of picture elements (pixels) in an image frame allows for the inter-mixing of coarse (for static areas) and fine (for areas of complex motion) resolution data descriptions in the same descriptive data block. A comparison of motion event areas is made between successive video frames, and a motion displacement vector is calculated for each pixel location in the frame. A data tree is constructed from these pixel motion vectors and is pruned to eliminate static areas. The remaining leaves of the pruned tree are encoded differentially and applied to a lossless arithmetic encoder to provide a significantly reduced data block that still retains the highest resolution of the image.
1. A method for encoding motion video information, comprising the steps of:
a) deriving a plurality of image motion vectors using a derivation algorithm;
b) creating a data tree comprised of said motion vectors using a construction algorithm, each node of said tree comprising a unique motion vector;
c) reducing said tree using a pruning algorithm;
d) encoding leaves of said reduced tree using a differentiation algorithm; and
c) creating a plurality of descriptive data elements, each data element further comprising:
a header portion; and
a data portion.
2. The method according to claim 1 , wherein the construction algorithm is a Markov random field (MRF) formulation using selected parameters.
3. The method according to claim 2 , wherein the selected parameters comprise a four-dimensional lattice (spatio-temporal+scale) with local four-dimensional smoothness constraints.
4. The method according to claim 1 , wherein the pruning algorithm is a Breidman-Friedman-Olshen-Stone (BFOS) algorithm.
5. The method according to claim 1 , wherein the differentiating algorithm performs a differentiation between successive leaves of said pruned tree using a “U-shaped” scan trajectory.
6. The method according to claim 1 , wherein the header portion of said each data element comprises a data signal incorporating a level of the tree where said data portion was derived.
7. The method according to claim 1 , wherein the data portion of said each data element comprises a data signal representing an encoded motion vector.
8. The method according to claim 1 , further including the step of encoding a differential data block losslessly using an adaptive arithmetic algorithm.
9. The method of claim 1 , further including the step of encoding a differential data block losslessly using a Huffman algorithm.
10. A method for encoding motion video information for transmission of a video image comprising the steps of:
a) selecting a first image mask comprised of a predetermined number of picture elements;
b) applying said mask to an image to identify each one of a unique plurality of picture elements at a predetermined location in an image frame;
c) comparing each one of said plurality of picture elements with a like plurality of identified picture elements at said location in a previous frame;
d) selecting a second image mask which includes a smaller number of picture elements than the previous image mask if said picture elements in the comparison are not identical;
c) repeating steps b and c if said picture elements in the comparison are not identical; and
f) if all picture elements of said comparison are identical, creating and storing a data signal indicating the location of the comparison and the size of the image mask.
11. The method according to claim 10 , wherein the predetermined number of picture elements is 256 spatially arranged in a 16 by 16 block.
12. The method according to claim 10 , wherein the predetermined number of picture elements is 64 spatially arranged in an 8 by 8 block.
13. The method according to claim 10 , wherein each second image mask has a resolution that is half that of said previous image mask.
14. A method for encoding motion video displacement information between two successive frames of a video image comprising the steps of:
a) selecting a first image mask comprised of a predetermined number of pixels;
b) applying said mask to an image to identify each one of a unique plurality of pixels at a predetermined location in an image frame;
c) comparing each one of said plurality of pixels with a like plurality of pixels at one of a plurality of locations in a search field of a previous frame;
d) repeating step c at a next one of the plurality of locations in said search field if said pixels in the comparison are not generally identical;
e) if all pixels of said comparison are generally identical, creating and storing a data signal indicating the x-y displacement of the comparison and the size of the image mask; and
f) if all pixels of said comparison are generally identical, but not exactly identical, reducing the number of pixels in the first image mask by half and repeating steps b through e.
15. The method of claim 14 , wherein the predetermined number of pixels is 256 spatially arranged in a 16 by 16 block.
16. The method of claim 14 , wherein the predetermined number of pixels is 64 spatially arranged in an 8 by 8 block.