Motion estimation using predetermined pixel patterns and subpatterns
View Patent ↗A method and system is provided for calculating motion vectors of macroblocks in a digital image of a digital video stream. The method and system reduces the computational overhead of calculating motion vectors computing difference measures using a predetermined pattern of pixels in each macroblock rather than all the pixels of the macroblock. Reduction of computational overhead can be further enhanced first using a subpattern, i.e., a sub-sample of the predetermined pattern on a subset of the macroblocks to determine close matching macroblocks and then using the predetermined pattern to determine the best matching macroblock from within the close matching macroblocks.
1. A method of determining a first motion vector and a second motion vector for a first macroblock and a second macroblock, respectively, of a present image from a previous image, the method comprising:
selecting a predetermined pattern of pixels in the previous image;
computing a first-macroblock difference measure for each of a first plurality of pixel blocks in the previous image to form a plurality of first-macroblock difference measures for the first macroblock using the predetermined pattern of pixels;
selecting a first origin block from the first plurality of pixel blocks having a lowest first-macroblock difference measure;
computing the first motion vector using the first origin block and the first macroblock;
computing a second-macroblock difference measure for each of a second plurality of pixel blocks in the previous image to form a plurality of second-macroblock difference measures for the second macroblock using the predetermined pattern of pixels;
selecting a second origin block from the second plurality of pixel blocks having a lowest second-macroblock difference measure; and
computing the second motion vector using the second origin block and the second macroblock.
2. The method of claim 1 , wherein the predetermined pattern of pixels includes less than or equal to half of the pixels in the previous image.
3. The method of claim 1 , wherein the predetermined pattern of pixels includes a fourth of the pixels of the previous image.
4. The method of claim 1 , wherein the y-coordinate modulo four of each pixel in the predetermined pattern of pixels has a y-coordinate is equal to three or zero.
5. The method of claim 1 , wherein computing a first-macroblock difference measure for each of a first plurality of pixel blocks in the previous image to form a plurality of first-macroblock difference measures for the first macroblock using the predetermined pattern of pixels further comprises:
computing an absolute difference between each pixel in both the pixel block and the predetermined pattern with a corresponding pixel in the first macroblock to create a plurality of absolute differences; and
summing the plurality of absolute differences to compute the difference measure.
6. The method of claim 1 , wherein computing a first-macroblock difference measure for each of a first plurality of pixel blocks in the previous image to form a plurality of first-macroblock difference measures for the first macroblock using the predetermined pattern of pixels further comprises:
computing a squared difference between each pixel in both the pixel block and the predetermined pattern with a corresponding pixel in the first macroblock to create a plurality of squared differences; and
summing the plurality of squared differences to compute the difference measure.
7. A method of determining a first motion vector and a second motion vector for a first macroblock and a second macroblock, respectively, of a present image from a previous image, the method comprising:
selecting a predetermined pattern of pixels in the previous image;
selecting a subpattern of pixels from the predetermined pattern of pixels;
computing a first first-macroblock difference measure for each of a first plurality of first-macroblock pixel blocks in the previous image to form a plurality of first first-macroblock difference measures using the subpattern of pixels;
selecting a first closest first-macroblock matching pixel block from the first plurality of first-macroblock pixel blocks having a lowest first first-macroblock difference measure;
computing a first accurate first-macroblock difference measure for the first closest first-macroblock matching pixel block using the predetermined pattern of pixels;
computing a first second-macroblock difference measure for each of a first plurality of second-macroblock pixel blocks in the previous image to form a plurality of first
second-macroblock difference measures using the subpattern of pixels;
selecting a first closest second-macroblock matching pixel block from the first plurality of second-macroblock pixel blocks having a lowest first second-macroblock difference measure; and
computing a first accurate second-macroblock difference measure for the first closest second-macroblock matching pixel block using the predetermined pattern of pixels.
8. The method of claim 7 , wherein the predetermined pattern of pixels includes a fourth of the pixels of the previous image.
9. The method of claim 7 , wherein the y-coordinate modulo four of each pixel in the predetermined pattern of pixels has a y-coordinate is equal to three or zero.
10. The method of claim 7 , wherein the subpattern of pixels includes a fourth of the pixels of the predetermined pattern.
11. The method of claim 7 , wherein computing a first first-macroblock difference measure for each of a first plurality of first-macroblock pixel blocks in the previous image to form a plurality of first first-macroblock difference measures using the subpattern of pixels comprises:
computing an absolute difference between each pixel in both the first-macroblock pixel block and the subpattern with a corresponding pixel in the first macroblock to create a plurality of absolute differences; and
summing the plurality of absolute differences to compute the first difference measure.
12. The method of claim 7 , wherein computing a first first-macroblock difference measure for each of a first plurality of first-macroblock pixel blocks in the previous image to form a plurality of first first-macroblock difference measures using the subpattern of pixels comprises:
computing an absolute difference between each pixel in both the first-macroblock pixel block and the predetermined pattern with a corresponding pixel in the first macroblock to create a plurality of absolute differences; and
summing the plurality of absolute differences to compute the first accurate difference measure.
13. The method of claim 7 , further comprising
computing a second first-macroblock difference measure for each of a second plurality of first-macroblock pixel blocks in the previous image to form a plurality of second first-macroblock difference measures using the subpattern of pixels;
selecting a second closest first-macroblock matching pixel block from the second plurality of first-macroblock pixel blocks having a lowest first-macroblock difference measure; and
computing a second accurate first-macroblock difference measure for a second closest first-macroblock matching pixel block using the predetermined pattern of pixels.
14. The method of claim 13 , further comprising:
selecting the first closest first-macroblock matching pixel block as an origin block when the first accurate first-macroblock difference measure is less than or equal to the second accurate first-macroblock difference measure;
selecting the second closest first-macroblock matching pixel block as the origin block when the second accurate first-macroblock difference measure is less the first accurate first-macroblock difference measure; and
computing the motion vector using the origin block and the first macroblock.
15. A video encoder configured to determine a first motion vector and a second motion vector for a first macroblock and a second macroblock, respectively, of a present image from a previous image, the video encoder comprising:
a frame buffer configured to store the first macroblock, the second macroblock and the previous image;
a first first-phase processing unit coupled to the frame buffer and configured to compute a first plurality of first-macroblock difference measures and a first plurality of second-macroblock difference measures using a predetermined pattern of pixels; and
a comparator coupled to the first first-phase processing unit and configured to select a first origin block based on the first plurality of first-macroblock difference measures and a second origin block based on the plurality of second-macroblock difference measures.
16. The video encoder of claim 15 , further comprising a cache coupled between the frame buffer and the first first-phase processing unit.
17. The video encoder of claim 15 , further comprising a second first-phase processing unit coupled to the frame buffer and configured to compute a second plurality of first-macroblock difference measures and a second plurality of second-macroblock difference measures using the predetermined pattern.
18. The video encoder of claim 15 , further comprising a first second-phase processing unit coupled to the first first-phase processing unit and the comparator, wherein the first second-phase comparator is configured to compute a difference measure using a subpattern of pixels.
19. The video encoder of claim 18 , further comprising:
second first-phase processing unit coupled to the frame buffer and configured to compute a second plurality of first-macroblock difference measures and a second plurality of second-macroblock difference measures using the predetermined pattern; and
a second second-phase processing unit coupled to the second first-phase processing unit and the comparator, wherein the second second-phase comparator is configured to compute a difference measure using the subpattern of pixels.