Efficient multi-frame motion estimation for video compression

Abstract

There is disclosed a method of digital signal compression, coding and representation, and more particularly a method of video compression, coding and representation system that uses multi-frame motion estimation and includes both device and method aspects. The invention also provides a computer program product, such as a recording medium, carrying program instructions readable by a computing device to cause the computing device to carry out a method according to the invention.

1 .- 48 . (canceled) 
     
     
         49 . A method comprising:
 for a macroblock in a current video frame:
 classifying by a computing device, one or more corresponding reference macroblocks from one or more reference video frames; and 
 performing by the computing device, one or more motion estimations for the macroblock with respect to the one or more reference macroblocks; and 
 generating by the computing device, a resulting motion vector from the one or more motion estimations; 
   wherein, for one or more macroblocks from a same class, motion estimation is performed on fewer than all of the one or more macroblocks from the same class.   
     
     
         50 . The method of  claim 49 , wherein performing comprises, for one or more macroblocks from the same class, performing motion estimation only once. 
     
     
         51 . The method of  claim 50 , wherein performing comprises, for one or more macroblocks from the same class, performing motion estimation only for a macroblock in a most recent reference frame in from the same class. 
     
     
         52 . The method of  claim 49 , wherein classifying macroblocks comprises classifying based at least in part on image and/or video features. 
     
     
         53 . The method of  claim 52 , wherein classifying based at least in part on image and/or video features comprises classifying based at least in part on pixel locations, region types, and/or edge features. 
     
     
         54 . The method of  claim 52 , wherein classifying based at least in part on pixel locations comprises classifying based at least in part on integer and sub-integer locations. 
     
     
         55 . The method of  claim 54 , wherein classifying based at least in part on sub-integer locations comprises classifying based at least in part on half-pixel and quarter-pixel locations. 
     
     
         56 . The method of  claim 52 , wherein classifying based at least in part on region types comprises classifying based at least in part on smooth, edge, and/or texture region types. 
     
     
         57 . The method of  claim 52 , wherein classifying based at least in part on edge features comprises classifying based at least in part on vertical edges, horizontal edges, and angled edges. 
     
     
         58 . The method of  claim 52 , wherein classifying based at least in part on edge features comprises classifying based at least in part on edge width. 
     
     
         59 . The method of  claim 49 , further comprising:
 performing, by the computing device, an initial motion estimation for the macroblock with respect to a corresponding reference macroblock from a most recent reference frame; and   determining, by the computing device, whether the initial motion estimation is sufficient for encoding the macroblock.   
     
     
         60 . The method of  claim 59 , wherein determining whether the initial motion estimation is sufficient for encoding the macroblock comprises determining whether a distortion based on the initial motion estimation is smaller than a threshold by the computing device. 
     
     
         61 . The method of  claim 59 , wherein determining whether the initial motion estimation is sufficient for encoding the macroblock comprises determining whether the macroblock in the video frame does not have a strong texture by the computing device. 
     
     
         62 . The method of  claim 59 , further comprising, in response to determining that the motion estimation is sufficient, generating by the computing device, a resulting motion vector from the motion estimation and performing no additional motion estimations. 
     
     
         63 . The method of  claim 59 , further comprising, in response to determining that the motion estimation is insufficient, performing by the computing device, one or more additional motion estimations with respect to at least one other macroblock from an other reference frame, and generating by the computing device, a resulting motion vector from the additional motion estimation or estimations. 
     
     
         64 . The method of  claim 49 , wherein:
 classifying comprises classifying macroblocks based at least in part on pixel locations; and   wherein the method further comprises, for at least one of the reference macroblocks, updating by the computing device, respective pixel locations for the respective at least one macroblocks.   
     
     
         65 . The method of  claim 64 , wherein updating respective pixel locations comprises, for a reference macroblock:
 computing by the computing device, a first distortion between the macroblock from the current video frame and the reference macroblock for an integer-pixel motion estimation;   computing by the computing device, a second distortion between the current macroblock and the reference macroblock for a half-pixel motion estimation; and   in response to determining that the second distortion is lower than a threshold, wherein the threshold is based at least in part on the first distortion, updating by the computing device, a sub-pixel location type for the reference macroblock to be integer-pixel.   
     
     
         66 . An article of manufacture including a computer-readable medium having instructions stored thereon configure to enable a computing device, in response to execution of the instructions by the computing, to perform operations comprising:
 for a macroblock in a current video frame:
 classifying one or more corresponding reference macroblocks from one or more reference video frames; and 
 performing one or more motion estimations for the macroblock with respect to the one or more reference macroblocks; and 
 generating a resulting motion vector from the one or more motion estimations; 
   wherein, for one or more macroblocks from a same pixel-location class, motion estimation is not performed for at least one of the macroblocks.   
     
     
         67 . The article of  claim 66 , wherein the method further comprises:
 performing an initial motion estimation for the macroblock with respect to a corresponding reference macroblock from a most recent reference frame;   determining whether the motion estimation is sufficient for encoding the macroblock;   in response to determining that the motion estimation is sufficient, generating a resulting motion vector from the motion estimation and performing no additional motion estimations; and   in response to determining that the motion estimation is insufficient, performing one or more additional motion estimations with respect to at least one other macroblock from an other reference frame, and generating a resulting motion vector from the additional motion estimation or estimations.   
     
     
         68 . The article of  claim 67 , wherein determining whether the initial motion estimation is sufficient comprises determining whether a distortion based on the initial motion estimation is smaller than a threshold. 
     
     
         69 . The article of  claim 67 , wherein determining whether the initial motion estimation is sufficient comprises determining whether the macroblock in the video frame does not have a strong texture. 
     
     
         70 . The article of  claim 66 , wherein the operations further comprise, for at least one of the other macroblocks, updating respective pixel locations for the respective at least one macroblocks. 
     
     
         71 . The article of  claim 70 , wherein updating respective pixel locations comprises, for a reference macroblock:
 computing a first distortion between the macroblock from the current video frame and the reference macroblock for an integer-pixel motion estimation;   computing a second distortion between the macroblock from the current video frame and the reference macroblock for a half-pixel motion estimation; and   in response to determining that the second distortion is lower than a threshold, the threshold based at least in part on the first distortion, updating a sub-pixel location type for the reference macroblock to be integer-pixel.   
     
     
         72 . An article of manufacture including a computer-readable medium having instructions stored thereon configure to enable a computing device, in response to execution of the instructions by the computing, to perform operations comprising, for a current macroblock in a video frame:
 performing by an computing device, an initial motion estimation for the macroblock with respect to a corresponding most recent reference macroblock from a most recent reference frame;   in response to determining that a distortion based on the initial motion estimation is smaller than a threshold, generating by the computing device, a resulting motion vector from the initial motion estimation;   in response to determining that a distortion based on the initial motion estimation is larger than the threshold:
 performing by the computing device, one or more additional motion estimations with respect to at least one other macroblock from an other reference frame, and generating a resulting motion vector from the additional motion estimations; and 
 after performing one motion estimation for one or more reference frames with corresponding macroblocks from a same pixel-location class, terminating performing by the computing device, the one or more additional motion estimations for the same pixel-location class. 
   
     
     
         73 . The method of  claim 70 , further comprising, for at least one of the other macroblocks, updating by the computing device, respective pixel locations for the respective at least one macroblocks.