Abstract:
A method and apparatus for digital image stabilization. The method comprises segmenting an exposure time to have multiple partial-exposure images of a scene and manipulating the partially exposed images to produce a stable image.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims priority from provisional application No. 60/953,550, filed Aug. 2, 2007. The following co-assigned, co-pending patent applications disclose related subject matter: application Ser. No. 11/379,835, filed Apr. 24, 2006, which claims priority to provisional patent application 60/676,088, filed Apr. 28, 2005. 
    
    
     BACKGROUND OF THE INVENTION 
     The present invention relates to digital signal processing, and more particularly to image stabilization methods and imaging devices with electronic stabilization. 
     Image stabilization (IS) is the task of eliminating jitter from video sequences captured by handheld cameras. Jitter is typically due to the undesired shake of the hand during video recording, and becomes a more severe problem when higher zoom ratios are used. Eliminating jitter from video sequences has been an increasingly important problem for consumer digital cameras and camera phones. There are a few different approaches to the solution of the image stabilization problem. One particular approach is to use digital image processing techniques to eliminate jitter. This approach is generally called “digital image stabilization” (DIS). 
     A typical digital image stabilization method can be summarized as follows: 
     Step 1: Motion vector computation: Compute a number of candidate motion vectors between two frames by finding the correlations between blocks of pixels. 
     Step 2: Global motion vector determination: Process the candidate motion vectors from step 1 using a number of heuristics to find the global jitter motion between the two frames. 
     Step 3: Motion compensation: Compensate for the estimated jitter motion by digitally shifting the output image in the reverse direction of the motion. 
     SUMMARY OF THE INVENTION 
     The present invention provides a method and apparatus for digital image stabilization. The method comprises segmenting an exposure time to have multiple partial-exposure images of a scene and manipulating the partially exposed images to produce a stable image. 
    
    
     
       BRIEF DESCRIPTION 
         FIG. 1  is an embodiment method for motion estimation; 
         FIG. 2  is an exemplary embodiment of a block boundary summation; 
         FIG. 3  is an exemplary embodiment of a SAD shift response; 
         FIG. 4  is an exemplary embodiment of an image pipeline; 
         FIG. 5  is an exemplary embodiment of a processor utilized in motion estimation; and 
         FIG. 6  is an exemplary embodiment of a blurry image. 
     
    
    
     DESCRIPTION OF THE INVENTION 
     1. Overview 
     The first embodiment method of digital image stabilization (DIS), such as for hand-held video devices, by segment exposure time and fuse images taken during exposure segments after alignment where the alignment uses large changes in SAD of within-image row and column shifts. In effect, embodiments use the column and row sums to identify good features for image registration. This approach detects the feature points effectively and is also robust to repetitive patterns that are undesirable for motion estimation. 
     Another important advantage is that it uses two 1D operations, which significantly reduces its computational complexity. Prior art uses more complicated 2D operators to identify feature locations. Our solution also uses a hierarchical solution to create a fusion mask. This hierarchical method detects image structure in the difference image at different scales and identifies image alignment errors accurately. It also has low complexity due to simple filtering and thresholding operations.  FIG. 1  illustrates high level functions. 
     In one embodiment, systems include camcoders, digital cameras, video cellphones, video display devices, et cetera.  FIG. 4  shows a generic image processing pipeline and one embodiment for stabilization that could be performed in the MPEG/JPEG functions and integrate with motion vector determination. Indeed, unstabilized video could be displayed with this embodiment stabilization applied as part of the display process. 
     In one embodiment, systems may be implemented with any of several types of hardware: digital signal processors (DSPs), general purpose programmable processors, application specific circuits, or systems on a chip (SoC) such as combinations of a DSP and a RISC processor together with various specialized programmable accelerators.  FIG. 5  illustrates an example of a processor for digital camera applications with a video processing subsystem in the upper left. A stored program in an onboard or external (flash EEP)ROM or FRAM could implement the signal processing. Analog-to-digital converters and digital-to-analog converters can provide coupling to the real world, modulators and demodulators (plus antennas for air interfaces) can provide coupling for transmission waveforms, and packetizers can provide formats for transmission over networks such as the Internet. 
     In another embodiment, methods apply to low light environments where a typical digital camera captures images using long exposure times that may result in a blurry image as shown on the top of  FIG. 6 . In this embodiment, methods shown on the bottom of  FIG. 6  where we divide the exposure time into smaller segments and capture multiple short exposure images. These images are not blurred; however, they are noisy due to short exposure. Our goal is to align and fuse these images to create an image that is both sharp and noise-free. 
     There are three main blocks of our method as shown in  FIG. 1 . Since multiple images are required for this method, memory requirements would be very high if we had to buffer raw images. Memory size is an important limitation in camera phones and digital cameras; therefore, we have designed our method to work on JPEG encoded image files, which take less space. We decode blocks from input JPEG files, produce the final image block, and encode it into JPEG. 
     A step by step description of one embodiment image for stabilization method is as follows: 
     PART 1: Motion Estimation 
     Let N be the number of JPEG images stored in external memory. N should be at least 2. Having more images is better. N=4 is recommended. We select one of these N images as the base image. This selection can be made randomly, or the last image can be selected as the base image because it is likely to have the least amount of blur. (The camera may move more during the capture of the early images while the user is pressing the shutter button, which suggests that the last image may have the least amount of blur.) Base image will form the final image and all other images, which we call enhancement images, will be fused to the base image to reduce the noise level. We follow the following procedure to estimate motion between the base image and all other enhancement images: 
     (1) Decode one block from the base image. Block size changes depending on image size. Typically, we would like to have 16 blocks in the image arranged in a 4×4 grid. We will refer to these blocks as “main blocks”. We use only the Y component of the image for steps 1 through 10 below. Cb and Cr components are used only in step (11). 
     (2) Divide the main block into smaller blocks, which we will refer to as “sub-blocks”. Typically, we would like to have 16 sub-blocks arranged in a 4×4 grid inside a main block. 
     (3) For each sub-block, compute two boundary signals. Boundary signals are the row and column sums for each sub-block as shown in  FIG. 2 . 
     (4) Compute the sum-of-absolute-differences (SADs) of each boundary signal with itself for different shifts in the range −20 to +20. SAD at shift=0 should be equal to zero. Starting at shift 0, as we move towards negative or positive shifts, the SAD is expected to increase. An example is shown in  FIG. 3 . 
     (5) Starting at shift=0, proceed towards negative shifts and find the shift where the SAD value stops increasing. In other words, find Sl where SAD at Sl−1 is smaller than the SAD at Sl. (In the figure above, Sl is around −11). Then, find the smallest SAD, Tl, for shifts larger than Sl in the negative direction. In the figure above, Tl is around 1300 and is achieved around shift (−16). Repeat the same procedure for positive shift and identify Tr. In the figure above, Tr is around 1200 and is achieved around shift 17. Tr and Tl are indicators of the image content in this block. Small Tr and Tl values indicate mostly a flat block or a block with repetitive patterns. Both types of blocks would be unreliable for motion estimation and should be avoided. Blocks with large Tr and Tl values indicate good image features for motion estimation. Compute Tmin, the minimum of Tr and Tl for each sub-block. Rank all 16 sub-blocks in a main block in terms of Tmin values from the largest to the smallest. Pick the sub-blocks with largest Tmin values as features for motion estimation. We typically select the best 2 sub-blocks from each main block. 
     (6) For each sub-block in the main block, compute the mean pixel value. Then, compute the average absolute deviation from the mean pixel value by computing the absolute difference of each pixel from the mean and by computing the average of all absolute differences. Among all 16 sub-blocks, pick the lowest average absolute deviation as an estimate of the noise level in this main block. Then, among all main blocks, pick the smallest absolute deviation as an estimate of the noise level in the entire image. 
     (7) For each sub-block that was selected for motion estimation, decode the search area that corresponds to this sub-block from the enhancement images one by one. Create a hierarchical representation of the sub-block and the search area. Compute a motion vector for the sub-block using coarse-to-fine search with SADs. 
     (8) Fit a parametric affine model to all motion vectors using a least squares optimization procedure. This involves solving an equation in the form Ax=b where A and b include motion vector information and x includes the unknown affine parameters. After the affine parameters are determined, compute the error for each motion vector according to this affine model. Remove the motion vector that has the largest error and recompute the affine model. Repeat this iterative procedure until the largest error is less than some threshold. Typically, 2 is a good value for the threshold. 
     PART2 Image Warping and Fusion 
     (9) Decode each main block from the base image. For each main block, decode the corresponding blocks from other images one by one. Warp these blocks according to the affine transform computed in step 8. After being warped, these blocks will be aligned with the base image block. 
     (10) Compute the difference between the base block and the warped block. Ideally, this difference should be entirely noise. However, due to moving objects, motion estimation errors, or lens distortion effects, there may be alignment errors. These alignment errors result in large values in the difference image. We will identify the location of alignment errors by thresholding the difference image. In order to achieve better accuracy, we will use a hierarchical thresholding method. Filter the difference image vertically and horizontally with the following 2-tap filter: [1 1]. The resulting image is the first level of the hierarchical representation. Filter this first level vertically and horizontally with the following filter to create the second level: [1 0 1]. Filter the second level with the following filter vertically and horizontally to create the third level: [1 0 0 0 1]. Threshold the absolute values of all three levels such that if the absolute value of a pixel is larger than the threshold, it is set to 1. Compute the OR function of the corresponding pixels from all three levels. This final binary image, which we call the mask, determines which pixels will be fused. Only the pixels that correspond to 0 in the mask will be used for fusion. The threshold values used above should be adjusted depending on the noise level in the image. We have computed the noise level in step 6. Compute the threshold values based on the estimated noise level as follows: T 1 =4*noiseLev, T 2 =2*noiseLev, T 3 =1*noiseLev, where noiseLev is from step 6, and T 1 , T 2 , and T 3  are thresholds for levels 1, 2, and 3 respectively. 
     (11) Fuse images by averaging corresponding pixels. Average only pixels that are assigned to 0 in the mask computed in step 10. Repeat this procedure for Y, Cb, and Cr components of the image.