Abstract:
A method and an apparatus for video stabilization is disclosed for detecting and eliminating unwanted camera motion from a sequence of video images. Motion vectors are first generated based on sample points using a block matching technique, from which a number of possible camera motions are estimated. Among the estimated camera motions, unwanted or undesirable camera motions are then detected and parameterized. A frame remapping process is then applied to relocate the pixels in the current frame, which acts in opposition to the dislocation of pixels due to unwanted camera motions in order to achieve video stabilization.

Description:
TECHNICAL FIELD  
       [0001]     The present invention relates to a method and an apparatus for video stabilization, which involves the detection, estimation and removal of unwanted camera motions from the incoming video images. The method and apparatus described herein can be incorporated into both the pre-processing and post-processing stage of typical video processing system, including but not limited to video recording and playback systems.  
       BACKGROUND  
       [0002]     Video taken from a shaky camera can be quite displeasing to an audience, often causing uneasiness and nausea. Shaky motions are, however, sometimes unavoidable. For example, an outdoor highly-mounted camera will shake under windy conditions. Also, personal video cameras are abundantly available for personal use, but it is not easy for a non-professional photographer to keep a camera stable while shooting. Failure to maintain the stability of a video camera while shooting introduces unwanted motions in the recorded video, which can result in poor quality or distracting videos. Consequently, it is desirable to stabilize the incoming video images before recording takes place, or to filter out the unwanted camera motions in a recorded video. Such tasks are collectively referred as video stabilization.  
         [0003]     Existing video stabilization techniques can be broadly classified into two main categories: optical stabilization techniques and signal processing techniques. Optical stabilization techniques stabilize the optics portion (e.g., lens/prism) of a camera by moving the optical parts in opposition to the shaking of a camera. Such techniques generally result in little or no change in the efficiency of the camera operation or the quality of the recorded image, but add significant cost to the camera and require components that are prone to mechanical wear. Moreover, such techniques work only in the video recording phase and thus are not suitable for correcting a previously-recorded video tainted by unwanted camera motions.  
         [0004]     Signal processing techniques, on the other hand, generally involve analyzing a video signal to detect and estimate camera movements, and then transform the video signals such that the effect of unwanted camera movements are compensated. With recent advances in digital signal processing equipment and techniques, signal processing techniques, in particular those involving digital signal processing, appear to be a more economical and reliable method for video stabilization. In addition, the digital signal processing offers a feasible way of stabilizing a pro-recorded video.  
         [0005]     Many prior works approach the problem of video stabilization from the digital signal processing perspective. However, they can suffer from a number of deficiencies. For example, they often rely heavily on the correct extraction of features such as edges, corners, etc., to identify reference area/points for camera movement estimation, meaning that some kind of sophisticated and time consuming feature extractors have to be incorporated into the video stabilization methods. Furthermore, even if reference area/points can be identified from good feature extractors, these reference area/points have to then go through another selection process to filter out some of the reference area/points that correspond to foreground objects, which usually contribute errors of the camera movement estimation. This selection process is essentially a segmentation process which segments foreground objects from the background. This, however, is not an easy task as segmentation is still a fundamental research problem that has not been fully resolved. Finally, the extracted features have to be tracked across a number of frames before the camera movement can be estimated, which further introduces inaccuracies when the tracking techniques employed are not robust enough. Related prior works can be found in U.S. Patent Application Publication No. 2003/0090593 to Xiong and in U.S. Pat. No. 5,053,876 to Blissett et al.  
         [0006]     Some other prior works, such as those in U.S. Pat. No. 5,973,733 to Gove and U.S. Pat. No. 6,459,822 to Hathaway et al., rely on motion vectors derived from block matching techniques for the camera motion analysis. These prior works generally partition a video frame into non-overlapping blocks, and all of these blocks must be involved in the motion estimation process. Motion vectors obtained under this approach are reasonably good in representing the true motions in a scene under the assumption that the motion discontinuities only occur at the regularly spaced block boundaries. However, this assumption is not likely to hold for typical operational environment. Moreover, since all the blocks must be involved in the motion estimation process, it does not offer a flexible way to scale computation requirement up or down to meet different computation constraints.  
         [0007]     Additional references that include camera motion estimation methods, but are not particularly focused on video stabilization, include U.S. Pat. No. 6,710,844 to Han et al., U.S. Pat. No. 5,742,710 to Hsu et al., U.S. Pat. No. 6,349,114 to Mory, U.S. Pat. No. 6,738,099 to Osberger, U.S. Pat. No. 5,751,838 to Cox et al., U.S. Pat. No. 6,707,854 to Bonnet et al., and U.S. Pat. No. 5,259,040 to Hanna. Methods described in these references, however, suffer the same aforementioned problems.  
         [0008]     What is desired is a robust and efficient video stabilization method that neither depends on feature extraction and segmentation, nor relies on an assumption that cannot reliably hold under normal operating conditions.  
       SUMMARY  
       [0009]     Disclosed herein is a method and apparatus for providing computationally efficient and robust video stabilization that favors both software and hardware implementation.  
         [0010]     According to the present disclosure, a set of sample blocks can be derived from a set of sample points, for example where each sample block is centered about the associated sample point. Motion vectors for these blocks can then be generated by a block matching technique using a current frame and a reference frame. These sample block motion vectors, representing the motion of the associated sample points, can then be used for camera motion estimation.  
         [0011]     The camera motion can be estimated based on a valid subset of motion vectors according to the affine camera motion model. A subset can be considered valid if the associated sample blocks are not collinear. By considering different combinations of subsets of non-collinear blocks out of the set of sample blocks, a set of possible camera motion parameters can thus be obtained.  
         [0012]     The final camera motion can be obtained by searching over a space of possible camera motion parameters. By evaluating the likelihood of the existence of unwanted motion for each possible motion parameter according to a similarity measurement, a final estimated camera motion can be selected as a motion parameter that results in a best similarity measurement. The best similarity measurement is then compared against a threshold to determine whether the final motion parameter actually represents an unwanted camera motion.  
         [0013]     The final motion parameter can be used to remap the current frame to generate an output frame in order to eliminate the detected unwanted camera motion, thus resulting in stabilized video. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]     Embodiments are illustrated by way of example in the accompanying figures, in which like reference numbers indicate similar parts, and in which:  
         [0015]      FIG. 1  shows a block diagram of a video stabilization apparatus;  
         [0016]      FIG. 2  shows a more detailed block diagram of the video stabilization apparatus shown in  FIG. 1 ;  
         [0017]      FIGS. 3A-3E  show different combinations of three blocks out of an exemplary set of four sample points; and  
         [0018]      FIG. 4  shows examples of types of camera motions that can be stabilized using a system such as that shown in  FIG. 1 . 
     
    
     DETAILED DESCRIPTION  
       [0019]      FIG. 1  shows a block diagram of a video stabilization apparatus  10 . Such a video stabilization apparatus  10  can be a stand-alone device or can be integrated into another device, for example a video recording device, a video processing device, a video playback device, or a computer. Digitized video frames  12  are passed in succession to a memory  14 . The memory  14  is in communication with a processor  16  for performing video stabilization processes as described below. Stabilized video frames  18  are successively output from the memory  14 .  
         [0020]      FIG. 2  shows a more detailed block diagram of the video stabilization unit  10 . As shown in  FIG. 2 , the video stabilization unit  10  includes various memory units, including a current frame memory  20 , a reference frame memory unit  29 , and an output frame memory unit  27 , which are collectively shown as the memory  14  in  FIG. 1 . The memory units  20 ,  27 , and  29  can thus be implemented in a single memory device as shown in  FIG. 1  and/or in separate memory devices as shown in  FIG. 2 . The video stabilization unit  10  also includes various processing units, including a motion estimation unit  22 , a camera motion estimation unit  23 , a camera motion selection unit  24 , a frame remapping unit  25 , and a reference frame rendering unit  28 , which are collectively shown as the processor  16 . Thus, in the embodiment shown in  FIG. 1 , the processor  16  is software-controlled to perform the various functions of the units  22 - 25  and  28  shown in  FIG. 2 .  FIG. 2  can be considered to also be representative of an alternative embodiment where the units  22 - 25  and  28  are processing circuits.  
         [0021]     The current frame memory unit  20  is for receiving and storing the input video frames  12  as they are successively input to the video stabilization apparatus  10 . At any instant, a video frame  12  stored in the memory unit  20  can be considered a current video frame, whereas a video frame stored in the memory unit  29 , for example a previously stabilized video frame, can be considered a reference video frame. The current and reference video frames are provided to a motion estimation unit  22 , where they can be used for deriving motion vectors based on set of sample points  31  (shown in  FIG. 3A ). A process for determining the motion vectors is described below.  
         [0022]     Referring now also to  FIGS. 3A-3E , the motion estimation unit  22  first constructs a set of sample blocks  32  from the set of sample points  31 . Locations of the sample points  31  can be pre-defined or randomly selected. Let B(m, n) denote a sample block  32  centered about a sample point  31  at the m th  column and n th  row in a current frame, for example where a frame is composed of columns and rows of pixel data. Consider a set of N sample blocks  32  {B 1 , B 2 , . . . , B N } where B i =B(m i , n j ), the motion estimation unit  22  uses the current and reference video frames to determine a motion vector V i  for each block B i  using any existing block-matching motion estimation technique. Note that in each frame the set of sample points  31  can be altered to adapt to the changes in scene composition or operational environment. The number of sample points  31  can also be changed to satisfy different computation requirements.  
         [0023]     After the motion vectors of the set of sample blocks  32  are obtained, these motion vectors are then provided to a camera motion estimation unit  23 . The camera motion estimation unit  23  estimates the camera motion for combinations of valid subsets of the set of N motion vectors, a subset being valid under a condition that the associated sample points are not collinear. For example, consider a scenario where there are only four sample points  31  as depicted in  FIG. 3A , and the size of the subsets is set such that each subset includes three sample blocks  32 .  FIGS. 3B  to  3 D show the valid subsets of sample blocks  32  for camera motion estimation, in which the three shaded sample blocks  32  under consideration are not collinear.  FIG. 3E  shows an invalid subset of sample blocks  32  for camera motion estimation, in which the three shaded blocks under consideration are collinear. The reason for this restriction is given below, after the camera motion estimation method is detailed.  
         [0024]     The camera motion estimation unit  23  can estimate the camera motion, for example according to the six parameter affine motion model. Denoting the coordinate of the pixel at the m th  column and the n th  row as [m, n, 1] T , and assuming all pixel movements are due to camera motion, then, for any pixel at coordinate [m i , n i , 1] T  in the current frame, the pixel coordinate [m′ i , n′ i , 1] T  of the corresponding pixel in the reference frame is as follows:  
               [           m   i   ′               n   i   ′             1         ]     =       [             am   i     +     bn   i     +   c                 d   ⁢           ⁢     m   i       +     en   i     +   f             1         ]     =       [         a       b       c           d       e       f           0       0       1         ]     ⁡     [           m   i               n   i             1         ]                 (   1   )             
 
         [0025]     Suppose there are three sample blocks  32  B i , B j  and B k  centered about the sampling points with coordinates [m i , n i , 1] T , [m j , n j , 1] T  and [m k , n k , 1] T  respectively, whose corresponding motion vectors are V i =[p i , q i , 0] T , V j =[p j , q j , 0] T  and V k =[p k , q k , 0] T . The corresponding locations of these blocks in the reference frame are then [m i +p 1 , n i +q i , 0] T , [m j +p j , n j +q i , 0] T , [m k +p k , n k +q k , 0] T . If the assumption that the motion vectors represent the true motion of the sample points  31  holds, then:  
               [             m   i     +     p   i               m   j     +     p   j               m   k     +     p   k                   n   i     +     q   i               n   j     +     q   j               n   k     +     q   k               1       1       1         ]     =       [           m   i   ′           m   i   ′           m   k   ′               n   i   ′           n   i   ′           n   k   ′             1       1       1         ]     =       [         a       b       c           d       e       f           0       0       1         ]     ⁡     [           m   i           m   j           m   k               n   i           n   j           n   k             1       1       1         ]                 (   2   )             
 
 After some matrix manipulations, it yields:  
               [           p   i           p   j           p   k               q   i           q   j           q   k             0       0       0         ]     =       [           a   -   1         b       c           d         e   -   1         f           0       0       0         ]     ⁡     [           m   i           m   j           m   k               n   i           n   j           n   k             1       1       1         ]               (   3   )             
 
 Now, provided that the three sample blocks, B i , B j , and B k  are not collinear with each other, then, the affine motion transformation matrix A can be derived as follows:  
             A   =       [         a       b       c           d       e       f           0       0       1         ]     =           [           p   i           p   j           p   k               q   i           q   j           q   k             0       0       0         ]     ⁡     [           m   i           m   j           m   k               n   i           n   j           n   k             1       1       1         ]         -   1       +     [         1       0       0           0       1       0           0       0       1         ]                 (   4   )             
 
         [0026]     From Equation (4), it can be seen that the camera motion, parameterized in the form of a transformation matrix, can be estimated from the motion vectors, provided that the three sample blocks  32  in consideration are not collinear. By using Equation (4), the camera motion estimation unit  23  can estimate a number of possible camera motion parameters by considering different subsets of the N non-collinear sample blocks  32 .  
         [0027]      FIG. 4  shows some typical unwanted camera motions, by which an input video frame  12  of a scene  13  is tainted. The affine camera motion model described in this invention can handle all, but not limited to, these typical motions.  
         [0028]     Referring again to  FIG. 2 , after the camera motion estimation unit  23  completes the camera motion estimation process, all of the camera motion parameters calculated by the camera motion estimation unit  23  are provided to the camera motion selection unit  24 . The camera motion selection unit  24  evaluates each of the received camera motion parameters to see if any represent unwanted camera motion. One method of evaluating a camera motion parameter is to remap the pixel coordinate of each pixel in the current image, according to Equation (1) using the camera motion parameter under consideration, to a new coordinate according to the camera motion parameter, and relocate the pixel to that remapped coordinate accordingly to construct a remapped image. If the remapped image is similar to the reference image, it is reasonable to assume that estimated camera motion is accurate. To evaluate the similarity between the remapped and reference frame, the majority area of the remapped image can be compared with that in the reference image according to some similarity measurements. Examples of such similarity measurements that can be used include frame difference, sum of squared differences. The camera motion parameter that yields the most desirable similarity measurement can be chosen as the final camera motion parameter.  
         [0029]     On the other hand, rather than constructing a complete remapped image, it is also possible to remap only a subset of pixel coordinates of the pixels in the current image to form a partially remapped image, such that only these remapped pixels contribute to the similarity measurement for selecting the best camera motion parameter. The camera motion selection unit  24  can also reject all of the received camera motion parameters if the best similarity measurement indicates no camera motion appears to be unwanted or undesirable motion. Under this situation, the camera motion selection unit  24  should return an affine transformation that has no effect in the subsequent frame remapping process, for example:  
       A   =     [         1       0       0           0       1       0           0       0       1         ]         
 
         [0030]     The frame remapping unit  25  will then receive the final camera motion parameter from camera motion selection unit  24 . In essence, the frame remapping unit  25  takes the final camera motion parameter and employs Equation (1) to remap all the pixel coordinates in the current frame to another set of pixel coordinates. Each pixel will then be relocated to its remapped coordinate accordingly to form the remapped output frame. It should be noted that the pixel coordinates remapping process can also be done on a sub-pixel basis to improve stabilization performance, provided that appropriate interpolation methods are used for the relocation of the pixel at sub-pixel accuracy. The remapped output frame will then be stored in the output frame memory unit  27  to serve as the stabilized video frame  18 .  
         [0031]     The reference frame rendering unit  28  reads the stabilized video frame from the output frame memory unit  27  and prepares a reference frame for a next iteration of the stabilization process. The reference frame rendering unit  28  can update the reference frame memory unit  29  by cloning the content in output frame memory unit  27  at each iteration, or it can do so periodically at a pre-defined sampling frequency. Another method of preparing the reference frame is to consider the similarity measurement taken from camera motion selection unit  24  and determine whether the estimated camera motion attains a certain predetermined level of confidence. If the confidence is higher than the pre-defined threshold, then the reference frame rendering unit  28  updates the reference frame. Otherwise, a previously-prepared reference frame can be retained in the reference frame memory unit  29  for the next iteration.  
         [0032]     The process described above can be repeated for the each incoming video frame  12 . Referring again to  FIG. 4 , after the above process for stabilization, the stabilized video frames  18 , with unwanted motions removed, can be obtained.  
         [0033]     While various embodiments in accordance with the principles disclosed herein have been described above, it should be understood that they have been presented by way of example only, and are not limiting. Thus, the breadth and scope of the invention(s) should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the claims and their equivalents issuing from this disclosure. Furthermore, the above advantages and features are provided in described embodiments, but shall not limit the application of such issued claims to processes and structures accomplishing any or all of the above advantages.  
         [0034]     Additionally, the section headings herein are provided for consistency with the suggestions under 37 CFR 1.77 or otherwise to provide organizational cues. These headings shall not limit or characterize the invention(s) set out in any claims that may issue from this disclosure. Specifically and by way of example, although the headings refer to a “Technical Field,” such claims should not be limited by the language chosen under this heading to describe the so-called technical field. Further, a description of a technology in the “Background” is not to be construed as an admission that technology is prior art to any invention(s) in this disclosure. Neither is the “Summary” to be considered as a characterization of the invention(s) set forth in issued claims. Furthermore, any reference in this disclosure to “invention” in the singular should not be used to argue that there is only a single point of novelty in this disclosure. Multiple inventions may be set forth according to the limitations of the multiple claims issuing from this disclosure, and such claims accordingly define the invention(s), and their equivalents, that are protected thereby. In all instances, the scope of such claims shall be considered on their own merits in light of this disclosure, but should not be constrained by the headings set forth herein.