Automated stabilization method for digital image sequences

[0002] The present invention generally relates to digital image processing and more particularly to a system and method for removing unwanted motion in digital image sequence.

[0003] Digital image sequences, such as those obtained from digital video cameras or from the scanning of motion picture film, often contain unwanted motion between successive frames in the sequence. There are many potential causes of this unwanted motion, including camera shake at the time of image capture, or frame-to-frame positioning errors (also known as jitter or hop and weave) when a film sequence is scanned. The process of removing this unwanted motion is termed image stabilization.

[0004] Some systems use optical, mechanical, or other physical means to correct for the unwanted motion at the time of capture of scanning. However, these systems are often complex and expensive, and they cannot correct for unwanted motion in a digital image sequence that was produced by an unknown and uncharacterized device. To provide stabilization for a generic digital image sequence, several digital image processing methods have been developed and described in the prior art.

[0005] A number of digital image processing methods use a specific camera motion model to estimate one or more parameters such as zoom, translation, rotation, etc. between successive frames in the sequences. These parameters are computed from a motion vector field that describes the correspondence between image points in two successive frames. The resulting parameters can then be filtered over a number of frames to provide smooth motion. An examples of such a system can be found in U.S. Pat. No. 5,629,988 to Burt et al. A fundamental assumption in these systems is that a global transformation dominates the motion between adjacent frames. In the presence of significant local motion, such as multiple objects moving with independent motion trajectories, these methods may fail due to the computation of erroneous global motion parameters.

[0006] Other image processing methods for digital image stabilization are designed primarily for digital video camera applications where system constraints include minimal buffering requirements and near real-time processing. As a result, these methods are limited to applying unwanted motion correction between only two frames at a given time, which prohibits filtering of the motion parameters over multiple frames. An example of such a system is described in U.S. Pat. No. 5,748,231 to Park et al. In this method, a weighted average motion vector is computed from the motion vector field corresponding to two successive frames. The weightings are determined from various statistical measures that indicate the reliability of a given motion vector. The weighted average motion vector is then applied to remove the motion between two successive frames. This type of processing results in all motion (including desired camera motion such as pans) being removed from the sequence, not just unwanted motion. Again, these methods assume the image sequences contain a dominant global motion, and they may fail in the presence of significant local motion.

[0007] Still other digital image processing methods for removing unwanted motion make use of a technique known as phase correlation for precisely aligning successive frames. An example of such a method has been reported by Eroglu et al. (“A fast algorithm for subpixel accuracy image stabilization for Digital Film and Video, ” in Proc. SPIE Visual Communications and Image Processing, Vol. 3309, pp. 786-797, 1998). However, these methods require that the sequence has no local motion, or alternatively, a user must select a region in consecutive frames that has no local motion. The dependence upon areas with no local motion and the necessity for user intervention are major drawbacks of these methods.

[0008] The invention solves the problem of removing unwanted motion from a digital image sequence without removing desired motion (e.g., pan, zoom, etc.). It does so without excessive computational requirements, and it is a fully automated process. Furthermore, it is robust in the presence of significant local motion in the image sequence.

[0009] The present invention overcomes the limitations of conventional systems by using a simple model that is based on the observation that the cumulative motion vectors corresponding to the desired motion will generally vary smoothly from frame-to-frame. Further, the invention uses a motion vector histogram with a simple threshold, and does not rely on a specific camera transformation model (or the absence of local motion). It is, therefore, an object of the present invention to provide a structure and method that uses a motion vector histogram in determining the unwanted motion components in digital image sequence.

[0010] One embodiment of the invention is a method for stabilizing a digital image sequence consisting of a number of successive frames. The method includes: calculating a motion vector field between adjacent frames; forming a motion vector histogram from horizontal and vertical components of the motion vector field; applying a threshold to the motion vector histogram to produce a thresholded motion vector histogram; generating average horizontal and vertical motion components from the thresholded motion vector histogram; filtering the average horizontal and vertical motion components over a number of frames to identify unwanted horizontal and vertical motion components for each of the frames; and stabilizing the image sequence by shifting each frame according to the corresponding unwanted horizontal and vertical motion components.

[0011] The thresholding of the motion vector histogram removes undesirable motion vectors that are likely to be unreliable or correspond to objects that have a small spatial extent. This threshold can be changed for each frame by an adaptive means or can be fixed at a pre-specified level. The unwanted horizontal and vertical components correspond to high temporal frequencies, and they can be computed by applying a highpass filter to the average horizontal and vertical components. The degree of highpass filtering is user-adjustable. The stabilizing includes a displacement of each frame by the corresponding unwanted horizontal and vertical components.

[0012] Another embodiment of the invention is a computerized digital imaging system for stabilizing a digital image sequence formed from a number of successive frames including: a motion estimation unit for calculating a motion vector field between adjacent frames; a histogram generator unit for forming a motion vector histogram from horizontal and vertical components of the motion vector field; a thresholding unit for applying a threshold to the motion vector histogram to produce a thresholded motion vector histogram; and averaging unit for generating average horizontal and vertical components from the thresholded motion vector histogram; a filtering unit for filtering the average horizontal and vertical components over a number of frames to identify unwanted horizontal and vertical components for each of the frames, and a stabilizing unit for stabilizing the image sequence by translating each frame according to the corresponding unwanted horizontal and vertical components. The thresholding unit removes motion vectors that are likely to be unreliable or correspond to objects that are temporally transient or have a small spatial extent. The system further includes a threshold determination unit for adaptively computing a threshold for each frame, or alternatively, the threshold may be fixed at a pre-specified level. The filter includes a highpass filter for identifying the unwanted horizontal and vertical components. The system further includes a user interface for adjusting the degree of highpass filtering. The stabilizing unit includes a displacement unit for shifting each frame by the corresponding unwanted horizontal and vertical components.

[0013] One advantage produced by the invention is that unwanted global motion is removed from a digital image sequence in a fully automated operation. With the invention, no user intervention is required, although the user has access to some system parameters to control usage and degree of stabilization. Also, the invention has robust performance to different scene content. Thus, the sequence may contain substantial local motion without significantly affecting the removal of the unwanted global motion. Moreover, the desired camera motion (pan, zoom, etc.) is not removed during the inventive stabilization process.

[0014] Further, with the invention, there is a minimal computational load. The estimation of the motion vector field is the most time-consuming component. However, this can be done efficiently with block-based motion estimation methods. Additionally, the invention allows stabilization to sub-pixel levels (e.g., below human perceptual thresholds). Finally, the use of the motion vector histogram offers the potential for further improvements, including the tracking of multiple motion vector clusters for improved estimates of unwanted motion.

[0015] The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of preferred embodiments of the invention with reference to the drawings, in which:

[0016] FIG. 1 is a schematic diagram illustrating an automated image stabilization method system according to the invention;

[0017] FIG. 2 is a diagram illustrating a two-dimensional (2-D) motion vector histogram according to the invention;

[0018] FIG. 3 is a graph illustrating unwanted motion according to the invention; and

[0019] FIG. 4 is a graph illustrating the removal of unwanted motion according to the invention and

[0020] FIG. 5 is a hardware embodiment of a computer system for operating the invention.

[0021] The invention removes unwanted global motion in a digital image sequence. Unwanted motion adversely impacts overall image quality and potentially reduces performance of current compression systems such as MPEG-2. The present invention is especially useful with film-originated source material (i.e., motion pictures that have been scanned into digital form) containing unwanted jitter (also known as hop/weave), which arises from various physical components in the imaging chain (e.g., perforation nonuniformities, media instability, mechanical aspects of capture/duplication/projection devices, etc.). However, as would be known by one ordinarily skilled in the art given this disclosure, the same method could also be used to stabilize unwanted camera motion in video-originated sequences.

[0022] As shown in FIG. 1, each frame from the original unstabilized sequence 100 is first processed with the preceding frame using a motion estimation unit 102 to form a motion vector field MVF(t) that indicates correspondence points between the current frame at a given time t and the preceding frame at time t−1. As is known by one ordinarily skilled in the art, the computation of a motion vector field is only valid for successive frames that share at least some similarity. If the sequence consists of multiple scenes (i.e., frames with significantly different image content), it is first necessary to segment the sequence into individual scenes (whether each scene has a continuity of image content) prior to the computation of motion vectors. This process of segmenting a sequence into individual scenes is sometimes known as scene change detection, and there have been numerous descriptions of such conventional methods. Alternatively, manual methods for scene detection can be used, where a person marks each scene change after viewing the sequence. Scene change detection is not a large part of the present invention, and it is assumed that such processing has been done prior to the application of the inventive image stabilization.

[0023] The motion vector field can be formed using a variety of methods, but in a preferred embodiment, the vector field is formed using block-based motion estimation for efficient computations. As is well known to those ordinarily skilled in the art, block-based motion estimation involves forming b×b blocks of pixels from the current frame, and for each block, finding a b×b block in the preceding frame that is the best match according to some error metric. A typical value for b is 8 or 16 pixels, and mean-squared error (MSE) or mean absolute distortion (MAD) is often used as the error metric. The output of the block matching process is a n×m set of motion vectors, which comprise the motion vector field. Increasing n and/or m (i.e., increasing the density of the motion vector field) may lead to improved performance of the current invention, but the drawback is that the number of computations is increased. The invention performs adequately with moderate values for n and m. As would also be readily known by those ordinarily skilled in the art given this disclosure, other motion estimation methods, such as optical flow, could certainly be used and may provide improved performance at the expense of increased computations. As each frame is sent to the motion estimation unit 102, it is also sent to a buffer 101, which stores N frames in order to allow the unwanted motion to be removed from the original sequence during a subsequent stabilization stage 107.

[0024] The motion vector field from each pair of adjacent frames is then processed with a histogram generator unit 103 to produce a total 2-D motion vector histogram, H_total(x,y,t) of horizontal (x) and vertical (y) translation values at a given time t. The histogram generator unit 103 computes the histogram by summing the number of occurrences of a particular (x,y) translation pair over the motion vector field. An example of a motion vector histogram is shown in FIG. 2. In this figure, the x and y translation values can each vary from −15 pixels to +15 pixels.

[0025] As illustrated in FIG. 2, a 2-D histogram of the motion vector components will typically contain one or more clusters 200 with a significant number of counts, where the clusters indicate regions within the image that are moving with the same velocity and direction. There will also be numerous clusters 201 continuing only a few counts, which indicates either small spatial regions or, more commonly, indicate inaccurate motion vectors (which results from noise, ambiguous signal content in the image, etc.).

[0026] Since these motion vectors clusters 201 are likely to be misleading in subsequent processing, they are preferably discarded. As would be known by one ordinarily skilled in the art given this disclosure, any number of techniques can be used to promote the removal of the clusters 201 having only a few counts. In a preferred embodiment, the removal is performed by applying a simple threshold filter to the histogram count values, i.e., retaining only those histogram values that equal or exceed a threshold T. Referring to FIG. 1, this thresholding process is performed by a thresholding unit 104. The output of the thresholding unit is a thresholded motion vector histogram H_thresh(x,y,t).

[0027] Besides thresholding, other methods can also be introduced to reduce the number of unreliable motion vectors including discarding vectors based on: 1) the variance of a block (where low variance blocks are essentially matching noise, not features), 2) the summed error between corresponding points in matched blocks (where high error indicates the blocks are not similar), and 3) the number of blocks that match with equivalent error (where there is no way to distinguish which matched block is the proper one). All of these methods can be applied in addition to the histogram thresholding, but are not necessary to the proper functioning of the current invention.

[0028] The present invention is not particularly sensitive to any specific histogram threshold value, and the threshold T can be set to a fixed value for all frames in a sequence. However, as would be known by one ordinarily skilled in the art given this disclosure, setting the threshold too high may result in only a few vectors being retained, which can lead to unstable behavior. Likewise, setting threshold too low may result in the inclusion of inaccurate motion vectors. To reduce the potential for poor performance caused by an inappropriate threshold, it is possible to adapt the threshold for each frame. To determine this adaptive threshold, the invention models the total motion vector histogram as the sum of two components:

[0029] H_total(x,y,t)=H_reliable(x,y,t)+H_unreliable(x,y,t)  (1)

[0030] where H_reliable(x,y,t) is the histogram component corresponding to reliable motion vectors at time t, and H_unreliable(x,y,t) is the histogram component corresponding to unreliable motion vectors at time t.

[0031] Modeling these histogram components as random variables, it is easy to derive a relationship for the means of the histograms:

[0032] μ_total=μ_reliable+μ_unreliable  (2)

[0033] where μ_totalis the mean of H_total(x,y,t), μ_reliableis the mean of H_reliable(x,y,t), and μ_unreliableis the mean of H_unreliable(x,y,t). Because the histogram values are always positive, the mean of the total histogram is always greater than the mean of the histogram for the unreliable vectors. By selecting the threshold to be the mean of the total histogram values (i.e., T=μ_total), it is generally assured that most of the unreliable vectors will be below the threshold and hence will not be included in subsequent calculations. It may also be desirable to elevate this threshold by some amount to reduce further the possibility of including unreliable vectors. One approach is to use the weighted sum of the total histogram average and the peak value of the histogram, P:

[0034] T=a*μ_Total+(1−a)*P  (3)

[0035] where a is a number between 0 and 1. If a=0, the threshold is the peak value of the histogram, which corresponds to retaining only the mode of the histogram.

[0036] In the present invention, it may also be advantageous to process the histogram prior to computing the threshold and/or applying the threshold to the histogram. Such preprocessing can include smoothing the histogram with simple linear filters. This smoothing process reduces local variations in the histogram which can lead to more robust exclusion of unreliable motion vectors, while still retaining reliable motion vectors.

[0037] Another aspect of the invention is a histogram processing method that computers separate one-dimensional (1-D) motion vector histograms for the x and y translation components. The motivation for this processing is that, in certain image regions, the x component may be accurate while the y component is inaccurate, or vice versa. By forming 1-D histograms and computing individual thresholds, T_xand T_y, for the horizontal and vertical components, respectively, it is possible that more reliable vectors for both the x and y components may be retained.

[0038] Referring again to FIG. 1, the thresholded motion vector histograms is then sent to an averaging unit 105 to compute average horizontal and vertical translation vectors for each of the frames. After thresholding to eliminate the unreliable vectors, the following relationship exists:

[0039] H_thresh(x,y,t)≈H_reliable(x,y,t).  (4)

[0040] That is, the thresholded motion vector histogram contains primarily reliable motion vectors.

[0041] The average horizontal and vertical translation vectors at a given time t are then computed as: $\begin{array}{cc}\stackrel{\_}{x}\left(t\right)=\sum _{x,y}x*H_{\mathrm{thresh}}\left(x,y,t\right)/\sum _{x,y}{H}_{\mathrm{thresh}}\left(x,y,t\right),& \left(5\right)\\ \stackrel{\_}{y}\left(t\right)=\sum _{x,y}y*H_{\mathrm{thresh}}\left(x,y,t\right)/\sum _{x,y}{H}_{\mathrm{thresh}}\left(x,y,t\right),& \left(6\right)\end{array}$

[0042] where {overscore (x)}(t) is average horizontal translation vector and {overscore (y)}(t) is the average vertical translation vector at time t. The invention uses simple averages of the histogram values because adjacent frames in sequence (assuming they come from the same scene) will contain roughly the same object undergoing smoothly varying local motion. This is expected as physical objects have mass, and thus cannot change speed or direction instantaneously. Regardless of the number and extent of moving objects, it is expected that the cumulative motion (i.e., the average horizontal and vertical motion vectors) will be smoothly varying from frame-to-frame. Further, besides local motion, there is also global motion such as desired camera motion (pan, zoom, etc.) and unwanted motion (jitter, camera shake, etc.). The desired camera motion is also typically smooth (particularly in professional cinema), but the unwanted motion will be rapidly and randomly varying. As a result, the average motion of all objects in the scene will tend to vary smoothly from frame-to-frame, while the global motion components introduced by the unwanted motion of jitter, camera shake, etc. generally will not vary smoothly.

[0043] Because the unwanted motion components vary more rapidly than the desired motion, the invention filters the average horizontal and vertical motion vectors over a number of frames to extract unwanted motion, using a temporal filtering unit 106 in FIG. 1. As explained above, the average horizontal and vertical translations should change gradually from frame to frame in the case of the desired motion. Therefore, any motion that deviates from a smoothly varying trend will be identified as unwanted motion. For example, and shown in FIG. 3, the average horizontal or vertical component is plotted against time for frames 1-6. As shown, frame 4 deviates from the smooth progression of frames 1-3, 5 and 6. Therefore, frame 4 is identified as having unwanted motion and thus requires stabilization.

[0044] To compute the unwanted motion that must be removed from frame 4, standard filtering techniques can be applied to the time series formed from the average translation vectors. The unwanted motion is assumed to consist of high frequency components, and highpass filtering can be used to directly extract this unwanted motion. Alternatively, lowpass filtering can be used to extract the desired low frequency motion, and the resulting smoothed translation vectors can then be subtracted from the average motion vectors to compute the unwanted high frequency components. These two approaches for extracting the unwanted motion are entirely equivalent. The desired motion and corresponding unwanted motion components of frame 4 are shown in FIG. 4. This unwanted motion component can be used to determine the amount of horizontal and/or vertical stabilization required to correct frame 4.

[0045] In a preferred embodiment to reduce buffering requirements, a simple FIR (finite impulse response) highpass filter is used to extract the unwanted high frequency motion from the item series of average horizontal and vertical translations. The length of the filter, N, which corresponds to number of frames that must be buffered, has a significant impact on the removal of unwanted frequency components from the global motion estimate. A tradeoff occurs between the lowest frequency that can be removed and the number of frames that must be buffered. A user is preferably given the option of having direct control over the degree of filtering in both the horizontal and vertical directions, and the impact of removing certain components of the unwanted motion can be viewed interactively. Besides the length of the filter, a user can also be given control over the maximum rate-of-change of the desired motion, thus providing an adjustment of the slew rate of the desired motion.

[0046] The user of the motion vector histogram in extracting unwanted motion also provides another benefit that is not readily apparent. As mentioned previously, the clusters 200 in FIG. 2 represent regions in an image that are moving with the same velocity and directions. It is possible to track each of these motion vector clusters as separate entities over successive frames, thereby producing multiple estimates for the unwanted motion. These multiple estimates can then be combined in a variety of ways to produce a single estimate for the unwanted motion. For example, a weighted sum of the individual estimates could be formed, where the weights are determined by the degree of confidence in each individual estimate.

[0047] Now, the output of the temporal filtering unit 106 in FIG. 1 is an estimate of the unwanted global motion in both the horizontal and vertical directions at a given time t. The unwanted horizontal motion is denoted as x_u(t) and the unwanted vertical motion is denoted as y_u(t). Given this estimate, the corresponding input frame for time t is stabilized relative to the reference frame (which is typically the first frame in the sequence) using a stabilizing unit 107. The stabilization process is done through simple horizontal and vertical displacements of the current frame. The estimates for the unwanted motion will typically be non-integer values, which means a standard image interpolation method (such as bilinear or cubic interpolation) is required to allow sub-pixel displacements. Sub-pixel displacements are also required to put any unwanted, but uncompensated, motion to levels below the human perceptual thresholds.

[0048] While the overall methodology of the invention is described above, the invention can be embodied in any number of different types of systems and executed in any number of different ways, as would be known by one ordinarily skilled in the art. For example, as illustrated in FIG. 5, a typical hardware configuration of an information handling/computer system in accordance with the invention preferably has at least one processor or central processing unit (CPU) 400. The CPU 400 is interconnected via a system bus 401 to a random access memory (RAM) 402, read-only memory (ROM) 403, input/output (I/O) adapter 404 (for connecting peripheral devices such as disk units 405 and tape drives 406 to the bus 401), communication adapter 407 (for connecting an information handling system to a data processing network) user interface adapter 408 (for connecting peripheral 409, 410, 411 such as a keyboard, mouse, digital image input unit, microphone speaker and/or other user interface device to the bus 401), a printer 412, and a display adapter 413 (for connecting the bus 401 to a display device 414). The invention could be implemented using the structure shown in FIG. 5 by including the inventive method within a computer program stored on the storage device 405. Such a computer program would act on an unstabilized time series of image frames supplied through the interface units 409, 410, 411 or through the network connection 407. The system would then automatically produce the desired stabilized digital image frame series output on the display 414, through the printer 412 or back to the network 407.

[0049] The invention removes jitter from film-originated sequences as part of the image processing that is performed during, for example, the telecine acquisition process. However, as would be known by one ordinarily skilled in the art given this disclosure, the invention is not limited to such an application and could be applied to video-originated sequences to remove unwanted translational camera motion. Moreover, the invention operates in a fully automated manner with no user invention, although the user may be given control over some system parameters to control the degree of stabilization. The invention has relatively low complexity and could operate in real-time on an image sequence given sufficient computer hardware. Finally, the user of a motion vector histogram to extract unwanted motion provides the opportunity to track multiple motion vector clusters, which can result in improved estimates for the unwanted motion as compared to computing a simple average from all motion vectors.

[0050] While the invention has been described in terms of preferred embodiments, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.