Abstract:
An estimated total camera motion between temporally proximate image frames is computed. A desired component of the estimated total camera motion is determined including distinguishing an undesired component of the estimated total camera motion, and including characterizing vector values of motion between the image frames. A counter is incremented for each pixel group having a summed luminance that is greater than a threshold. A counter may be decremented for pixels that are under a second threshold, or a zero bit may be applied to pixels below a single threshold. The threshold or thresholds is/are determined based on a dynamic luminance range of the sequence. The desired camera motion is computed including representing the vector values based on final values of counts for the image frames. A corrected image sequence is generated including the desired component of the estimated total camera motion, and excluding the undesired component.

Description:
PRIORITY 
     This application claims the benefit of priority to U.S. provisional patent application 60/944,046, filed Jun. 14, 2007, which is incorporated by reference. 
    
    
     BACKGROUND 
     1. Field of the Invention 
     The invention is in the field of motion estimation for frame stabilization using image-processing techniques. It is desired to have a technique with reduced complexity and that is suitable for hardware implementations. It is also desired to have a technique that can be used for fast global and local motion estimation, as well as image registration. 
     2. Description of the Related Art 
     Video sequences are known to be captured with hand-held digital still cameras often containing unwanted motion as a result of hand jitter. The motion caused by hand jitter can reduce the quality of the recorded video sequences. This movement is a biological phenomenon and the effect it has on the recorded video sequences is amplified by small and lightweight modern cameras. To reduce the influence of the hand-jitter motion, multiple image stabilization approaches have been proposed. When selecting one, a trade-off is to be made between different parameters of the system such as weight, performance, and cost. 
     One approach is optical image stabilization (OIS) which provides high performance. However, OIS is an expensive solution, and it has been used on high-end digital single lens reflex cameras, video cameras, and binoculars. 
     A second approach is electronic image stabilization (EIS) which involves use of extra hardware such us gyroscopic sensors. Gyroscopes are used to detect and measure the amplitude of the hand jitter and the image is shifted in software by a certain number of pixels. The system using gyroscopes has an advantage over optical image stabilization because there are no moving parts, and the power dissipation is much lower. Although continuously shrinking in size and price, the use of gyroscopic sensors is still an expensive option for camera or phones manufactures. 
     In the paper by Aaron Deever, entitled “In-camera all-digital video stabilization”, published in ICIS&#39;06 conference, Rochester, May 2006, the problem of video stabilization was investigated with particular focus on in-camera, all-digital video stabilization or digital image stabilization (DIS). Algorithms for global camera motion estimation and jitter calculation were proposed by Deever. Computational constraints imposed by an in-camera solution are also discussed. 
     An image stabilizing apparatus for correcting motion of an image recording apparatus by using a bit-plane matching technique, and an image stabilizing method, are described in U.S. Pat. No. 6,535,244, entitled, “Image stabilizing apparatus using bit-plane Matching and Image Stabilizing Method Using the Same”. In the image stabilizing apparatus, a field memory stores input digital image information. A motion detecting circuit calculates an amount of movement of input image information between two screens by using bit-plane matching technique and outputs a motion vector of the image recording apparatus. A motion correcting circuit corrects the motion of the image recording apparatus by moving image information stored in the field memory in an opposite direction to the direction of the motion vector. 
     A method and apparatus for motion estimation is also described in United States published patent application no. US2006/171464. A method and apparatus are described for motion estimation in which the amount of computation can be reduced. The method for motion estimation includes storing an interblock match difference calculated for a previous matching block to be motion estimated. An interblock match difference is calculated for a current matching block to be motion estimated using the stored interblock match difference. Motion estimation is performed on the current matching block using the interblock match difference calculated for the current matching block. 
     SUMMARY OF THE INVENTION 
     A digital image stabilization method is provided. A sequence of temporally proximate image frames is acquired. An estimated total camera motion between the image frames is computed. A desired component of the estimated total camera motion is determined including distinguishing an undesired component of the estimated total camera motion, and including characterizing vector values of motion between the image frames. A counter is incremented for each pixel group having a summed luminance that is greater than a first threshold. The counter is decremented for each pixel group having a summed luminance that is less than a second threshold. The first and second thresholds are determined as percentages of a dynamic luminance range of the sequence. The desired camera motion is computed including representing the vector values based on final values of counts for the image frames. A corrected image sequence is generated including the desired component of the estimated total camera motion, and excluding the undesired component. The corrected image sequence or a further processed version, is rendered, stored, displayed, transmitted and/or transferred. 
     A further digital image stabilization method is provided. A sequence of temporally proximate image frames is acquired. An estimated total camera motion between the image frames is computed. A desired component of the estimated total camera motion is determined including distinguishing an undesired component of the estimated total camera motion, and including characterizing vector values of motion between the image frames. A counter is incremented for each pixel group having a summed luminance that is greater than a threshold. The threshold is determined based on a dynamic luminance range of the sequence. The desired camera motion is computed including representing the vector values based on final values of counts for the image frames. A corrected image sequence is generated including the desired component of the estimated total camera motion, and excluding the undesired component. The corrected image sequence or a further processed version, is rendered, stored, displayed, transmitted and/or transferred. 
     Binary incrementation may be applied in the method. A bit  1  may be generated for a vector element that is above the threshold. A bit  0  may be generated for a vector element that is not above the threshold. An exclusive OR operation may be applied between a first binary vector and a delayed version of another binary vector. The method may include applying low pass temporal filtering. 
     The first and second groups of pixels may include one or more rows or columns of pixels. The undesired component of the estimated total camera motion may include a jitter component. The method may include compensating for the jitter component through an image shift/warp function. The desired component of the estimated total camera motion may include a panning component. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  schematically illustrates in a block diagram an image stabilization method in accordance with certain embodiments. 
         FIG. 2   a  shows two plots illustrating horizontal projection vectors for two images in a motion sequence. 
         FIG. 2   b  is a plot that illustrates an average magnitude distance function for the horizontal projection vectors of  FIG. 2   a.    
         FIG. 3  is a plot of pixel values, indicating a pair of thresholds displaced around the average of a pair of maximum/minimum values, and an output of a comparator for one row. 
         FIG. 4   a  shows two plots of horizontal sign projection vectors for two images of a motion sequence. 
         FIG. 4   b  is a plot illustrating an average magnitude distance function for the horizontal sign projection vectors of  FIG. 4   a.    
         FIGS. 5   a - 5   b  illustrates the binary vectors for the two images of  FIGS. 4   a - 4   b.    
         FIG. 6  shows a plot illustrating the sum of XOR output values. 
         FIG. 7   a  shows plots of horizontal displacements that are respectively estimated by the BI, SP, IP and PC methods for a burst of multiple images. 
         FIG. 7   b  shows plots of vertical displacements that are respectively estimated by the BI, SP, IP and PC methods for a burst of multiple images. 
         FIG. 8  shows plots of horizontal displacements that are respectively estimated by the BI, SP, IP and PC methods. 
         FIG. 9  shows plots of vertical displacements that are respectively estimated by the BI, SP, IP and PC methods. 
     
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
     Techniques for estimating global motion between two consecutive images of a movie are provided. The technique can also be used for image registration. It is very fast and simple to implement because it uses mostly bit operations. It doesn&#39;t use any multiplications, sum of absolute values. 
     Implementations: Matlab code and In-camera hardware implementation. The software required to estimate the displacements may include a C demo. 
     Global Motion Estimation Techniques for Image Stabilization 
     Two categories of global motion estimation methods are proposed. The first one, called Sign Projection (SP) is obtained by modifying the integral projection estimation method using two thresholds for pixel values. The second category, called binary incrementation (BI), is obtained by using only one threshold for generating binary vectors from two images. It is shown that the proposed approaches provide similar motion estimation accuracy with the integral projection (IP) and phase correlation (PC) methods. Also, they have reduced numerical complexity and memory requirements, leading to shorter processing times as well as lower power consumption. 
     Unlike the techniques described briefly in the background above, the embodiment described hereunder relate use digital image stabilization (DIS) techniques in order to determine an undesired image jitter and shake and compensate by digitally shifting pixel data. These methods do not need extra hardware and the power consumption can be extremely reduced. The methods presented in this paper are particularly advantageous in devices with limited computational power or memory. One such device is a mobile phone equipped with a digital camera. The optical image stabilization is not a viable solution, because the mobile phone has to support heavy shocks. The electronic image stabilization adds extra hardware costs and complicates the mobile phone design. Therefore, in this case, the most efficient stabilization system is the digital image stabilization. 
     In this paper, the captured video data is stabilized prior to compression and storage. The proposed methods estimate the global motion that indicates the relative motion of the camera with respect to the image background. Global motion estimation has been largely used in video coding or video analysis applications. All the stabilization techniques presented in this paper are not suitable for local motion estimation. 
     Motion estimation is known to be one of the most computation intensive parts of video systems. A typical image stabilization algorithm is illustrated in  FIG. 1 .  FIG. 1  illustrates an image stabilization algorithm involving receiving an image by way of an image input sequence and output of a modified image by way of an output image sequence. The illustrated method includes motion estimation, wherein the motion between frames is estimated using the input image sequence. The illustrated method involves a trajectory and jitter estimation sequence, wherein the desired camera motion is computed. The components caused by camera jitter and camera pan are distinguished. Jitter is estimated and compensated through an image shift or warp function. 
     Motion estimation may be provided using a block-matching algorithm (BMA), in which image frames are divided into non-overlapping rectangular blocks. The best match to the current block of pixels is searched for in the previous frame of the sequence within a certain search area in respect to the location of the current block. The optimal search is called the full search (FS) algorithm and searches locations to find the best match. A related article J. Feng, K.-T. Lo, H. Mehrpour, and A. E. Karbowiak, entitled “Adaptive block matching motion estimation algorithm using bit plane matching,” in Proc. ICIP&#39;, 1995, pp. 496-499 is incorporated by reference. The average magnitude distance function (AMDF) can be considered in the matching process. Basically, the vectors “slide” one over the other and the sum of the absolute difference is computed. The full search technique is complex. 
     Simpler, sub-optimal methods may be used, such us the phase correlation method (see, e.g., Kuglin C D., Hines D C., “The phase correlation image alignment method,” in Proc. Int. Conf. Cybernetics and Society, IEEE, Bucharest, Romania, September 1975, pp. 163-165, incorporated by reference) and the integral projection method see K. Sauer and B. Schwartz, 1996, “Efficient Block Motion Estimation Using Integral Projections”, IEEE Trans. Circuits, Systems for video Tech., vol. 6, No. 5, October, pp. 513-518, incorporated by reference) have been proposed. The phase correlation method is based on a phase shift theorem. Applying an inverse Fourier transform to the phase shift gives a delta function offset, from which the translational motion in the image pair is found. This technique is robust, but still somewhat complex, because it involves the use of a Fourier transform procedure. 
     Another technique based on integral projection can be used to obtain a robust estimate of the global motion between two frames. In this further technique, a pair of one-dimensional vectors is computed by summing the elements of each column or row respectively. The projection vectors are correlated to find the best offset corresponding to the matched frames. 
     Further global motion estimation methods are described below. These descriptions are followed by quantitative analysis of the performance of the preferred methods compared with integral projection and phase correlation methods. 
     Low Complexity Global Motion Estimation Methods 
     Certain proposed methods are derived from the integral projection method. They are inspired from standard methods used to determine the fundamental frequency of the speech signal (see, e.g., Deller, J. Hansen, J. Proakis, Discrete-Time Processing of Speech Signals, 2nd. edition, Wiley-IEEE Press, 1999, incorporated by reference). For this purpose, the speech signal is “centrally clipped” in order to reduce the dynamic range of the signal and simplify the hardware or software implementation. Further, the complexity is significantly reduced if a level clipping or a limitation function is applied. Then the autocorrelation function or the average magnitude distance function (AMDF) is computed and the fundamental period of the signal is found.  FIG. 2A  shows two plots of computed horizontal projection vectors. The AMDF values for different displacement values are illustrated by the plot in  FIG. 2B . The minimum of this function shows that the horizontal displacement value is 6. It can be observed from  FIGS. 2A-2B  that the computed projection and AMDF vectors have large values. Therefore, the memory requirements of the integral projection method are high. 
     Sign Projection Method 
     A pair of one-dimensional vectors (horizontal and vertical) is computed from the pixel values of each frame or image plane. Instead of summing all elements and obtaining a high final value, e.g., as described by Deevers (incorporated by reference above), a lower value may be obtained by incrementing or decrementing the value based on results of comparisons of elements using one or two (or more) thresholds. This method is referred to as the Sign Projection method. For each row, one is added (+1) to a count if the value on the image plane is higher than a second threshold, while one is subtracted (−1) from a count if the value is lower than a first threshold. These thresholds are computed as a percentage of the dynamic range given by the maximum and minimum values of the image elements. They are symmetric in rapport with the average value of each image. An example obtained for one image row is provided in  FIG. 3 . 
     Referring to  FIG. 3 , further details as to how the thresholds are determined is now provided for embodiments including two thresholds and alternative embodiments including a single threshold. An average value determined as an average a minimum value minI and a maximum value maxI is provided at a value around 55 in  FIG. 3 . Two thresholds are separated from this average value by an amount d, where d=(p−½)*(maxI−minI). So the thresholds are computed as, Th_low=(maxI+minI)/2−(p−½)*(maxI−minI), and Th_high=(maxI+minI)/2+(p−½)*(maxI−minI), where p is the percentage between 0.5 and 1, minI is the minimum pixel value of the image crop and maxI is the maximum pixel value of the image crop. The output of the comparator is also shown in  FIG. 3  only having values between minus one (−1) and plus one (+1). 
     A preferred range of percentages for the thresholds is between 55% (0.55) and 80% (0.8). It would be smaller for small image crops (e.g. 512×512) and larger for large image crops. There is no optimum percentage, because the accuracy of the results depends on the size of the images, their content, and possible rotations, among other factors. However, typically 60% (0.6) leads to stable results for both situations, i.e., the one and two threshold embodiments. If less than 55% (0.5-0.54) is used, some unstable results have been observed to occur. That is, there would be an undesired probability of obtaining very similar vectors even in case of large displacements between pictures. 
     An alternative embodiment includes “centrally clipping” the image around a value determined from the histogram of the image (e.g. around the value of its maximum). 
     In a version with one threshold, generally the lower threshold is used and may be computed as in the two threshold embodiment. A counter counts the number of pixels above the threshold and a vector is obtained. The binary vector is generated as follows: a bit  1  is generated if each vector element is above the vector&#39;s average value, while otherwise a bit  0  is generated. Other alternatives for generating the binary vector include comparing the vector&#39;s elements with its median value or with half of the sum of its maximum and minimum values. 
       FIG. 4A  includes plots illustrating modified horizontal vectors obtained from two images.  FIG. 4A  illustrates that the dynamic range of the vectors may be reduced by many orders of magnitude in comparison with those of the original method illustrated at  FIG. 2A .  FIG. 4B  illustrates the average magnitude distance function for the horizontal sign projection vectors of  FIG. 4A . The maximum possible values of the modified vectors are given by the size of the images. The same displacement value is obtained by the matching process although the dynamic range of the computed AMDF values is much lower than those of the original integral projection method. The operation is repeated for each column in both images. The numerical complexity and memory requirements of the SP method are relatively low. The integer additions are replaced with comparisons and counting is used in the first phase. Also, the dynamic range of variables is much lower in comparison with those of the IP or PC methods. IN certain embodiments, only about five (5) additions and five (5) multiplications are involved in computing the thresholds for both images. The IP method involves about 2 integer additions per pixel, while the complexity of the PC method is higher, because it involves three 2-D FFT&#39;s (Fast Fourier Transforms) whose complexity depends on the particular implementation. Also, the estimations are robust in moderating variations of the thresholds. 
     Binary Incrementation Method 
     Further significant numerical complexity reduction can be obtained if only one threshold is used. In this alternative embodiment, each pixel value of two consecutive frames is compared with only one threshold. This threshold also depends on the dynamic range of the image values and vectors elements. For each line of the image, a counter counts the number of pixels above the threshold and a vector is obtained. A bit  1  is generated if each vector element is above its average (or median value), and otherwise a bit  0  is generated. The procedure is repeated for each column of the image plane for both images. Therefore, two pairs of binary vectors (corresponding to horizontal and vertical computations) are obtained. An example of such computed binary vectors is shown in  FIGS. 5A-5B . Binary vectors for two images are illustrated by the plots of  FIGS. 5A-5B . 
     For each pair of binary vectors, an exclusive OR (XOR) operation is performed between one vector and delayed versions of the other vector. The output of the XOR block should be zero in case of a perfect match. The number of bits “ 1 ” shows the mismatch between the vectors for different displacement values. The horizontal and vertical displacement values are given by the positions where the output reaches its minimum (e.g., at a displacement value of six (6) in  FIG. 6 ). This is referred to as the global motion estimation method or the binary incrementation method. The numerical complexity and memory requirements of this last method are very low in comparison with similar binary methods as well as with other considered methods. Only slightly more than one comparison per pixel is involved in generating the binary vectors. There is no need to keep the full binary matrices in the memory, unlike methods described in S. Ko, S. Lee, S. Jeon, and E. Kang. Fast digital image stabilizer based on gray-coded bit-plane matching, IEEE Transactions on Consumer Electronics, vol. 45, no. 3, pp. 598-603, August 1999; and B. Natarajan, V. Bhaskaran, and K. Konstantinides, “Low-complexity block-based motion estimation via one-bit transforms,” IEEE Trans. Circuit Syst. Video Technol., vol. 7, no. 5, pp. 702-706, August 1997, which are incorporated by reference). Also, there are no multiplications or integer additions needed, although in alternative embodiments they may be used (i.e., such functions are not explicitly excluded). Therefore, very efficient hardware implementations are possible. The method gives robust displacement estimations on sufficiently large regions of both images (e.g., a few hundred samples for each direction). 
     A low-pass temporal filtering may be next applied. This low-pass temporal filtering serves to assist in removing unwanted hand jitter and retaining any intentional panning movement. A jitter improved calculation method may be used such as that proposed in the Deevers article incorporated by reference above. If A[n] is the accumulated jitter for frame n, v[n] is the computed motion estimate for frame n, and a is the dampening factor, the accumulation formula is as follows:
 
| A[n]=α[n− 1]+α[ n].  
 
     An improved accumulation formula is better suited to retaining the intentional panning motion. Next, the image shift is performed using the maximum buffer area of the image sensor. 
     Experiments and Results 
     The inventors have investigated the efficiency of the proposed stabilization methods for recorded short movies or burst sequence pictures. Firstly, the considered methods were tested by computing the displacements between pictures taken by a Nikon D100 camera on burst pictures mode operation. This mode provides a sequence of high quality JPEG pictures, but slightly shifted one to the next, due to the hand jitter. The value of the dampening factor α was 0.95. It can be seen from  FIGS. 7A-7B  that the global motion values indicated by all methods are close. Some differences are explained by small rotations that occur between consecutive pictures.  FIGS. 7A-7B  show plots of displacements estimated by the BI, SP, IP and PC methods for a burst of pictures. 
     Next, the considered algorithms were also tested on a lower quality video (320×240 pixels). As shown in  FIG. 8  and  FIG. 9 , there are more differences between the displacement estimates of the considered methods.  FIG. 8  illustrates the horizontal displacements estimated by the BI, SP, IP and PC methods, while  FIG. 9  illustrates the vertical displacements. The integral projection, sign projection and binary incrementation methods provide displacement estimates that are more sensitive than phase compensation method estimates in case of low quality frame sequences. Furthermore, these methods are affected by luminance variations and small intra-frame movements. Overall, the provided stabilization methods reduce the hand jitter effect and improve the visual quality of a large variety of video sequences. It is noted that, if some individual frames are blurry, the digital image stabilization technique is not designed to itself reduce the perceived blur. 
     The sign projection and binary incrementation methods described above are provided for global motion estimation. The performance for digital video stabilization is demonstrated to provide advantageously efficient and accurate motion estimation compared with more complex global motion estimation methods. The methods are obtained by central clipping and/or otherwise limiting the pixel values of consecutive frames or images. Due to their simplicity, these methods have an efficient hardware or software implementation. Performance can be further improved for small block sizes. 
     While an exemplary drawings and specific embodiments of the present invention have been described and illustrated, it is to be understood that that the scope of the present invention is not to be limited to the particular embodiments discussed. Thus, the embodiments shall be regarded as illustrative rather than restrictive, and it should be understood that variations may be made in those embodiments by workers skilled in the arts without departing from the scope of the present invention as set forth in the appended claims, and structural and functional equivalents thereof. 
     In addition, in methods that may be performed according to preferred embodiments herein and that may have been described above, the operations have been described in selected typographical sequences. However, the sequences have been selected and so ordered for typographical convenience and are not intended to imply any particular order for performing the operations, except for those where a particular order may be expressly set forth or where those of ordinary skill in the art may deem a particular order to be necessary. 
     In addition, all references cited above herein, as well as the background, invention summary, abstract and brief description of the drawings, are all incorporated by reference into the detailed description of the preferred embodiments as disclosing alternative embodiments. 
     In addition, the following are incorporated by reference: United States published applications nos. US2006/0204110, US20050068452, US2006/0098890, US2006/0285754, US2007/0189748, and US2007/0269108, and U.S. application Ser. Nos. 11/753,098, 11/752,925, 11/573,713, 10/764,339, 11/624,683, 11/690,836, 11/764,578, 11/856,721, 11/859,164, 10/985,657, 10/985,650, 10/986,652, 61/023,774,60/913,331, and 60/945,558. 
     The following are also incorporated by reference: K. Uomori, A. Morimura, H. Ishii, T. Sakaguchi and Y. Kitamura. Automatic image stabilizing system by full-digital signal processing. IEEE Transactions on Consumer Electronics, Vol. 36, No. 3, pp. 510-519, August 1990; and “Automatic multidimensional deconvolution” J. Opt. Soc. Am. A, vol. 4(1), pp. 180-188, January 1987 to Lane et al. “Some Implications of Zero Sheets for Blind Deconvolution and Phase Retrieval”, J. Optical Soc. Am. A, vol. 7, pp. 468-479, 1990 to Bates et al. Iterative blind deconvolution algorithm applied to phase retrieval”, J. Opt. Soc. Am. A, vol. 7(3), pp. 428-433, March 1990. to Seldin et al.; “Deconvolution and Phase Retrieval With Use of Zero Sheets,” J. Optical Soc. Am. A, vol. 12, pp. 1,842-1,857, 1995 to Bones et al., “Digital Image Restoration”, Prentice Hall, 1977 authored by Andrews, H. C. and Hunt, B. R; and “Motion Deblurring Using Hybrid Imaging”, by Moshe Ben-Ezra and Shree K. Nayar, from the Proceedings IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003.