Temporal Motion Vector Filtering

Abstract

Methods and apparatus, including computer program products, implementing and using techniques for performing temporal motion vector filtering in digital video are disclosed. A recursive hierarchical process is used to determine a motion vector. In the recursive hierarchical process, a neighborhood of old motion vectors is filtered to generate a first estimated motion vector for an image patch in a pair of two image frames. The filtering process uses multiple vectors in a neighborhood around the old motion vector to improve the prediction of the first estimated motion vector. The temporal vector partitioning process separates motion vectors associated with an object from motion vectors associated with a background before selecting a best motion vector, which improves the selection process. The process also works well in the absence of object/background boundaries, as in this case the outlier (incorrect) vector or vectors will be separated out from the good vectors.

1 - 16 . (canceled) 
     
     
         17 . A computer-readable storage device having computer-executable instructions stored thereon that, in response to execution by one or more computing devices, cause the one or more computing devices to:
 obtain a previous motion vector generated at a highest resolution level in a previous frame;   project the previous motion vector at a lowest resolution level in a current frame;   generate a plurality of motion vectors at the lowest resolution level in the current frame using the previous motion vector as a base vector;   identify a best motion vector from the plurality of motion vectors that most accurately reflects displacement of an image patch; and   propagate the best motion vector generated at the lowest resolution level in the current frame to a higher resolution level.   
     
     
         18 . The computer-readable storage device of  claim 17 , wherein the instructions further cause the one or more computing devices to:
 for each resolution level in the current frame, propagate a best motion vector to a next highest resolution level until the highest resolution level is reached.   
     
     
         19 . The computer-readable storage device of  claim 17 , wherein obtaining a previous motion vector further comprises:
 determining whether a scene break occurred between the previous frame and the current frame; and   if a scene break occurred, setting the previous motion vector to equal a zero vector.   
     
     
         20 . The computer-readable storage device of  claim 17 , wherein identifying a best motion vector further comprises partitioning the plurality of motion vectors into a first vector cluster and a second vector cluster. 
     
     
         21 . The computer-readable storage device of  claim 20 , wherein partitioning the plurality of motion vectors further comprises:
 determining a first seed vector and a second seed vector by identifying two vectors among the plurality of vectors that are furthest apart from each other;   associating the first seed vector with the first vector cluster;   associating the second seed vector with the second vector cluster; and   for each other vector in the plurality of vectors:   determining whether the other vector is closer to one of the first seed vector and the second seed vector;   associating the other vector with the first vector cluster in response to determining that the other vector is closer to the first seed vector; and   associating the other vector with the second vector cluster if the other vector is closer to the second seed vector.   
     
     
         22 . The computer-readable storage device of  claim 20 , wherein partitioning the plurality of motion vectors further comprises selecting from the plurality of motion vectors a subset of motion vectors that are within diagonally adjacent grid regions and excluding motion vectors that are not within the diagonally adjacent grid regions. 
     
     
         23 . The computer-readable storage device of  claim 17 , wherein identifying a best motion vector further comprises:
 for a motion vector in the plurality of potential motion vectors, centering a first window on a pixel that forms an origin of the motion vector and centering a second window on a pixel that forms an end point of the motion vector; and   determining a sum of absolute differences of luma values for the pixels in the first window and pixels at corresponding positions in the second window.   
     
     
         24 . An apparatus comprising:
 one or more processors configured to execute modules that include executable instructions, the modules comprising:
 a generator configured to generate a plurality of motion vectors; 
 a tester configured to identify a best motion vector from the plurality of motion vectors that most accurately reflects displacement of an image patch; and 
 a propagator configured to:
 determine whether the best motion vector corresponds to a highest resolution level in a current frame; 
 if the best motion vector corresponds to the highest resolution level in the current frame, the propagator is further configured to propagate the best motion vector to a lowest resolution level in a subsequent frame, and 
 if the best motion vector does not correspond to the highest resolution level in the current frame, the propagator is further configured to propagate the best motion vector to a next higher resolution level in the current frame. 
 
   
     
     
         25 . The apparatus as recited in  claim 24 , wherein the tester is further configured to:
 partition the motion vectors into a plurality of vector clusters comprising a first vector cluster and a second vector cluster by:   determining a first seed vector and a second seed vector that are furthest apart in the plurality of vectors; and   for each other motion vector in the plurality of motion vectors:
 determining whether the other motion vector is closer to one of the first seed vector and the second seed vector; 
 associating the other motion vector with the first vector cluster in response to determining that the other motion vector is closer to the first seed vector; and 
 associating the other motion vector with the second vector cluster in response to determining that the other motion vector is closer to the second seed vector. 
   
     
     
         26 . The apparatus as recited in  claim 24 , wherein the tester is further configured to select from the plurality of motion vectors a subset of motion vectors that are within diagonally adjacent grid regions and to exclude motion vectors that are not within the diagonally adjacent grid regions. 
     
     
         27 . The apparatus as recited in  claim 24 , wherein the propagator is further configured to:
 determine whether a scene break occurred between a previous frame and the current frame; and   if a scene break occurred, set the previous motion vector to equal a zero vector.   
     
     
         28 . A computer-implemented method performed under control of one or more computing devices, the method comprising:
 obtaining a previous motion vector generated at a highest resolution level in a previous frame;   projecting the previous motion vector at a lowest resolution level in a current frame;   generating a plurality of motion vectors at the lowest resolution level in the current frame using the previous motion vector as a base vector;   identifying a best motion vector from the plurality of motion vectors that most accurately reflects displacement of an image patch; and propagating the best motion vector generated at the lowest resolution level in the current frame to a higher resolution level.   
     
     
         29 . The computer-implemented method of  claim 28 , further comprising:
 for each resolution level in the current frame, propagating a best motion vector to a next highest resolution level until the highest resolution level is reached.   
     
     
         30 . The computer-implemented method of  claim 28 , wherein obtaining a previous motion vector further comprises:
 determining whether a scene break occurred between the previous frame and the current frame; and   if a scene break occurred, setting the previous motion vector to equal a zero vector.   
     
     
         31 . The computer-implemented method of  claim 28 , wherein identifying a best motion vector further comprises partitioning the plurality of motion vectors into a first vector cluster and a second vector cluster. 
     
     
         32 . The computer-implemented method of  claim 31 , wherein partitioning the plurality of motion vectors further comprises:
 determining a first seed vector and a second seed vector by identifying two vectors among the plurality of vectors that are furthest apart from each other;   associating the first seed vector with the first vector cluster;   associating the second seed vector with the second vector cluster; and   for each other vector in the plurality of vectors:
 determining whether the vector is closer to one of the first seed vector and the second seed vector; 
 associating the vector with the first vector cluster if the vector is closer to the first seed vector; and associating the vector with the second vector cluster if the vector is closer to the second seed vector. 
   
     
     
         33 . The computer-implemented method of  claim 31 , wherein partitioning the plurality of motion vectors further comprises selecting from the plurality of motion vectors a subset of motion vectors that are within diagonally adjacent grid regions and excluding motion vectors that are not within the diagonally adjacent grid regions. 
     
     
         34 . The computer-implemented method of  claim 28 , wherein identifying a best motion vector further comprises:
 for a motion vector in the plurality of potential motion vectors, centering a first window on a pixel that forms an origin of the motion vector and centering a second window on a pixel that forms an end point of the motion vector; and   determining a sum of absolute differences of luma values for the pixels in the first window and pixels at corresponding positions in the second window.