Method and apparatus for motion vector estimation for an image sequence
A method and apparatus for motion vector estimation for a plurality of image frames including retrieving a reference hash value associated with a reference frame, wherein the reference hash value represents a spatially oriented block of pixels, generating a plurality of image hash values including a first hash value for a first area represented by a spatially oriented block of pixels of an image frame and computing a motion vector estimate using a plurality of first hash values and the reference hash value is disclosed.
1. A method of determining a motion vector, comprising:
partitioning all pixels of a reference image into a plurality of non-overlapping blocks, each non-overlapping block of the plurality of non-overlapping blocks having first pixel dimensions;
generating, by a computer comprising one or more processors, a reference hash list comprising a reference hash value for each non-overlapping block of the plurality of non-overlapping blocks;
partitioning an input image into a plurality of overlapping blocks comprising all possible block positions of blocks of the first pixel dimensions;
generating, by the computer, a plurality of input hash values, wherein the plurality of input hash values comprises an input hash value for each overlapping block of the plurality of overlapping blocks;
generating, for each reference hash value, of the reference hash list, that matches only one of a spatially associated selection of input hash values of the plurality of input hash values, a pixel offset to generate a pixel offset list, wherein the pixel offset is a spatial offset between the each reference hash value and the only one of the spatially associated selection, and wherein the pixel offset list is generated by using only the reference hash list as a reference to the reference image; and
encoding the input image using a most common pixel offset of the pixel offset list as a motion vector estimate.
2. The method of claim 1 , wherein encoding the input image comprises matching at least two reference hash values of the reference hash list to at least two input hash values of the plurality of input hash values to confirm a first image block of the input image matches a first reference block of the reference image, the first image block having the first pixel dimensions and comprising a portion of pixels of at least two of the plurality of overlapping blocks associated with the at least two input hash values, wherein the at least two of the plurality of overlapping blocks and at least two of reference blocks associated with the at least two reference hash values comprise a common spatially adjacent arrangement.
3. The method of claim 1 , wherein a pixel value of the input image is used in generating a number of the input hash values, the number equal to a pixel width of the first pixel dimensions times a pixel height of the first pixel dimensions, and wherein at least one of the pixel width or the pixel height is at least eight pixels.
4. The method of claim 1 , wherein encoding the input image comprises a fixed partitioning of encoded images into non-overlapping encoded blocks of matching pixel dimensions; and identifying all of the non-overlapping encoded blocks that match pixel values of the reference image, wherein the pixel values are offset by the motion vector estimate.
5. The method of claim 4 , wherein encoding the input image comprises identifying an unchanged non-overlapping encoded block if a corresponding input hash value of the input hash values matches a spatially common reference hash value of the reference hash list.
6. The method of claim 4 , wherein the matching pixel dimensions comprise at least one of the first pixel dimensions or one pixel dimension of at least 8 pixels.
7. The method of claim 1 , wherein the spatially associated selection of the input hash values is selected based on a defined search area and is exclusive of a null motion vector.
8. The method of claim 1 , further comprising repeated encodings of updates to the input image, wherein each encoding of the repeated encodings comprises identifying a single motion vector estimate as an only motion vector.
9. The method of claim 1 , wherein encoding the input image comprises using at least two input hash values to confirm a block having the first pixel dimensions matches a non-aliased block of the reference image.
10. The method of claim 1 , wherein the pixel offset list comprises information from at least one of previous motion vector estimates or hints from rendering of the input image.
11. The method of claim 1 , wherein matching only one of the spatially associated selection of input hash values comprises determining matches between one reference hash value of the reference hash list and more than one of the plurality of input hash values, and ignoring the one reference hash value in generating the pixel offset list.
12. The method of claim 1 , wherein the motion vector estimate identifies a spatial displacement between a first non-overlapping block of the plurality of non-overlapping blocks and a first overlapping block of the plurality of overlapping blocks.
13. The method of claim 1 , wherein encoding the input image comprises encoding the motion vector estimate and an identification of an input portion, the input portion comprising a selection of non-overlapping common dimension blocks of the input image matching an equivalent portion of the reference image at a pixel offset vector defined by the motion vector estimate, wherein the first pixel dimensions and the non-overlapping common dimension blocks each comprise a size of at least eight pixels in one dimension.
14. The method of claim 1 , wherein the reference image and the input image are each partitioned into rows and columns of blocks of the first pixel dimensions.
15. The method of claim 1 , wherein the first pixel dimensions are fixed and known by a decoder.
16. An apparatus for encoding an image comprising:
at least one processor enabled to generate an input image and a reference image; and
an encoder, coupled to the at least one processor, comprising:
a block hash code calculator enabled to generate (i) a reference hash list comprising reference hash values from reference blocks generated by spatially partitioning the reference image into a maximum number of unique non-overlapping blocks of a common size and (ii) a plurality of input hash values from input blocks generated by spatially partitioning the input image into a maximum number of unique overlapping blocks of the common size;
memory enabled to store portions of both the reference hash values and the plurality of input hash values;
a motion vector estimator for generating, for each reference hash value of the reference hash list that matches only one of a spatially associated selection of input hash values of the plurality of input hash values, a pixel offset to generate a pixel offset list, wherein the pixel offset is spatial offset between the each reference hash value and the only one of the spatially associated selection, and wherein the pixel offset list is generated by using only the reference hash list as a reference to the reference image; and
an image encoder enabled to encode the input image using a most common pixel offset of the pixel offset list as a motion vector estimate.