IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,

VOL. 28, NO. 7,

JULY 2006

1

Full-Frame Video Stabilization with
Motion Inpainting
Yasuyuki Matsushita, Member, IEEE, Eyal Ofek, Member, IEEE, Weina Ge,
Xiaoou Tang, Senior Member, IEEE, and Heung-Yeung Shum, Fellow, IEEE
Abstract—Video stabilization is an important video enhancement technology which aims at removing annoying shaky motion fromvideos. We propose a practical and robust approach of video stabilization that produces full-frame stabilized videos with good visualquality. While most previous methods end up with producing smaller size stabilized videos, our completion method can produce fullframe videos by naturally filling in missing image parts by locally aligning image data of neighboring frames. To achieve this, motion
inpainting is proposed to enforce spatial and temporal consistency of the completion in both static and dynamic image areas. In
addition, image quality in the stabilized video is enhanced with a new practical deblurring algorithm. Instead of estimating point spreadfunctions, our method transfers and interpolates sharper image pixels of neighboring frames to increase the sharpness of the frame.
The proposed video completion and deblurring methods enabled us to develop a complete video stabilizer which can naturally keep theoriginal image quality in the stabilized videos. The effectiveness of our method is confirmed by extensive experiments over a wide
variety of videos.
Index Terms—Video analysis, video stabilization, video completion, motion inpainting, sharpning and deblurring, video enhancement.

æ
1

INTRODUCTIONV

IDEO enhancement

has been steadily gaining in importance with the increasing prevalence of digitalvisual media. One of the most important enhancements isvideo stabilization, which is the process for generating a
new compensated video sequence where undesirable image
motion is removed. Often, home videos captured with ahandheld video camera suffer from a significant amount of
unexpected image motion caused by unintentional shake ofa human hand. Given an unstable video, the goal of video
stabilization is to synthesize a new image sequence as seenfrom a new stabilized camera trajectory. A stabilized video
is sometimes defined as a motionless video where thecamera motion is completely removed. In this paper, we
refer to stabilized video as a motion compensated video
where only high frequency camera motion is removed.
In general, digital video stabilization involves motion
compensation and, therefore, it produces missing image
pixels, i.e., pixels which were originally not observed in theframe. Previously, this problem had been handled by either
trimming the video to obtain the portion that appears in all
frames, or constructing image mosaics by accumulatingneighboring frames to fill up the missing image areas (seeFig. 1). In this paper, we refer to mosaicing as the image
stitching with a global transformation.

. Y. Matsushita, E. Ofek, X. Tang, and H. Shum are with Microsoft
Research Asia, 3/F, Beijing Sigma Center, No. 49, Zhichun Road, Hai Dian
District, Beijing, China 100080.
E-mail: {yasumat, eyalofek, xitang, hshum}@microsoft.com.
. W. Ge is with Department of Computer Science and Engineering,Pennsylvania State University, 310 IST Building, University Park, PA
16802. E-mail: ge@cse.psu.edu.
Manuscript received 22 Aug. 2005; revised 5 Dec. 2005; accepted 19 Dec.
2005; published online 11 May 2006.
Recommended for acceptance by H. Sawhney.
For information on obtaining reprints of this article, please send e-mail to:tpami@computer.org, and reference IEEECS Log Number TPAMI-0451-0805.
0162-8828/06/$20.00 ß 2006 IEEE

The trimming approach has the problem of reducing theoriginal video frame size since it cuts off the missing image
areas. Moreover, sometimes due to severe camera-shake,
there might be a very small common area among neighboring frames which results in very small video frames. On theother hand, mosaicing works well for static and planar
scenes, but produces visible artifacts for dynamic or
nonplanar scenes. This is due to the fact that mosaicing
methods usually register images by a global geometrictransformation model which is not sufficient to represent
local geometric deformations. Therefore, they often generate unnatural discontinuity in the frame as shown in the
midbottom of Fig. 1.
In this paper, we propose an efficient video completion
method which aims at generating full-frame stabilized
videos with good visual quality. At the heart of thecompletion algorithm, we propose a new technique, motion
inpainting, to propagate local motion information which isused for natural stitching of multiple images. We also
propose a practical motion deblurring method in order toreduce the motion blur caused by the original camera
motion in the video. These methods enable us to develop ahigh-quality video stabilizer that maintains the visualquality of the original video after stabilization.

1.1 Prior Work
There are typically three major stages constituting a video
stabilization process: camera motion estimation, motion
smoothing, and image warping. The video stabilization
algorithms can be distinguished by the methods adopted inthese stages. After briefly overviewing prior methods byfollowing these steps, we review prior work on video
completion and motion deblurring.
Video stabilization is achieved by first estimating theinterframe motion of adjacent frames. The interframe
motion describes the image motion which is also called
global motion. The accuracy of the global motion estimationis crucial as the first step of the stabilization.
Published by the IEEE Computer Society

2IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,

VOL. 28,

NO. 7, JULY 2006

Fig. 1. Top row: stabilized image sequence. The red area represents the missing image area due to the motion compensation. Bottom row: from left
to right, result of trimming (dotted rectangle becomes the final frame area), mosaicing, and our method.

There are two major approaches for global motion
estimation. One is the feature-based approach [1], [2], [3],[4]; the other is the global intensity alignment approach [5],[6], [7], [8]. Feature-based methods are generally faster thanglobal intensity alignment approaches, while they are more
prone to local effects. A good survey on image registration
is found in [9].
After computing the global transform chain, the second
step is removing the annoying irregular perturbations. There
are approaches which assume a camera motion model [3],[10], [11], [12], e.g., camera is fixed, or camera moves on aplanar surface. It works well when the assumed camera
motion model is correct; however, it is preferable to use amore general camera motion model since there exist many
situations where camera motion cannot be approximated bysuch simple models, e.g., handheld camera motion. Morerecently, Litvin et al. [14] proposed to use a Kalman filter tosmooth the general camera motion path, and Pilu [13]proposed an optimal motion path smoothing algorithm withconstraints imposed by a finite image sensor size.
Filling in missing image areas in a video is called video
completion. In [14], mosaicing is used to fill up the missing
image areas in the context of video stabilization. However,
the method does not address the problem of nonplanar
scenes and moving objects that may appear at the boundaryof the video frames, which might cause significant artifacts.
Wexler et al. [15] filled in the holes in a video by sampling
spatio-temporal volume patches from different portions of
the same video. This nonparametric sampling-based approach produces a good result; however, it is extremelycomputationally intensive. Also, it requires a long video
sequence of a similar scene to increase the chance of finding
correct matches, which is not often available in the context
of video stabilization. Jia et al. [16] took a different approach
to solve the same problem by segmenting the video into twolayers, i.e., a moving object layer and a static backgroundlayer. One limitation of this approach is that the moving
object needs to be observed for a long time, at least for asingle period of its periodic motion. In other words, it
requires the cyclic transition of the color patterns in order tofind good matching. Therefore, the method is not suitablefor filling in the video boundaries where a sufficientamount of observation is not guaranteed. More recently,
Cheung et al. showed an effective video fill-in result in their

video epitomes framework [17]. The method again requires
a similar video patch in the different portion of the same
video; therefore, it fundamentally requires the periodic
motion in order to achieve completion.
Motion blur is another problem in video stabilization as
the original camera motion trajectory is replaced with amotion compensated trajectory in the stabilized video.
Motion blur is a fundamental image degradation process
which is caused by moving scene points traverse several
pixels during the exposure time. Motion deblur has beenstudied extensively in the literature. In many single frame
deblurring techniques, motion deblur is achieved by image
deconvolution; however, the point spread function (PSF) is
necessary to be estimated. Image deconvolution without
knowing the PSF is called blind image deconvolution [18],[19], [20], [21], [22], relying on either image statistics or anassumption of very simple motion models. Although thesemethods are effective under specific conditions, theseassumptions, e.g., a simple motion model, do not hold inmany practical situations. Image deblurring methods bydeconvolution require very accurate PSFs that are often
hard to obtain. One exception is Ben-Ezra and Nayar’s
method [23] which explicitly measures motion PSFs with a
special hardware to avoid difficulty in PSF estimation.
We take a different approach of reducing image blurrinesscaused by motion blur. Our method is similar to Adelson [24]and Bergen [25] which were proposed independently. In
their methods, a sharper image is produced from source
images taken of an object at substantially identical fields ofview but with different focuses. The image composition is
performed by evaluating the energy levels of the highfrequency component in the images, by taking the image
pixels which have greater energy levels (sharper pixels). In
our context, since we need to deal with a dynamic scene
captured with a moving camera, we integrate the global
image alignment and an adaptive pixel selection process inorder to achieve the pixel transfer. Recently, Ben-Ezra et al.
[26] have developed a superresolution method with a jitter
camera by applying an adaptive sampling of stationary
image blocks and compositing them together. Although it
requires a special hardware, it is able to increase theresolution of the original videos.

MATSUSHITA ET AL.: FULL-FRAME VIDEO STABILIZATION WITH MOTION INPAINTING

3

a method to transfer sharper pixels to corresponding blurry
pixels to increase the sharpness and to generate a video ofconsistent sharpness as done by Adelson [24] and Bergen[25]. The proposed deblurring method is different fromsuperresolution methods such as [30], [19] in that our
method transfers pixels from sharper frames and replaces
pixels by weighted interpolation. Therefore, our method
does not increase the resolution of the frames, but restores
resolution of blurry frames using other frames.
In the rest of this paper, Section 2 describes global andlocal motion estimation and smoothing methods which areused in our deblurring and completion methods. The video
completion algorithm based on motion inpainting is
described in Section 4. Section 3 presents the proposed
image deblurring method. In Section 5, we show results ofboth stabilization and additional video enhancement
applications. Conclusions are drawn in Section 6.

2

Fig. 2. Flow chart of the full-frame video stabilization.

1.2 Proposed Approach
The limitations of the previous approaches and practicaldemands motivated us to develop effective completion anddeblurring methods for generating full-frame stabilized
videos with good visual quality. This paper has two primarycontributions in the process of video stabilization (Fig. 2).
1.2.1 Video Completion with Motion Inpainting
First, a new video completion method is proposed which isbased on motion inpainting. The idea of motion inpainting
is propagating local motion, instead of color/intensity as inimage inpainting [27], [28], into the missing image areas.
The propagated motion field is then used to help naturally
fill up missing image areas even for scene regions that are
nonplanar and dynamic. Using the propagated local motion
field as a guide, image data from neighboring frames are
locally warped to maintain spatial and temporal continuities of the stitched images. Image warping based on local
motion was used in the deghosting algorithm for panoramic
image construction by Shum and Szeliski [29]. Our method
is different from theirs in that we propagate the local
motion into an area where the local motion cannot bedirectly computed.
1.2.2 Practical Motion Deblurring Method
Second, we address the problem of motion blur in thestabilized videos. While motion blur in original videos
looks natural, it becomes a visible artifact in stabilized
videos because it does not correspond to the compensatedcamera motion. Furthermore, image stitching without
appropriate deblurring results in inconsistent stitching of
blurry and sharp images. To solve this problem, wedeveloped a practical deblurring method which does not
require accurate point spread functions (PSFs) which areoften hard to obtain. Instead of estimating PSFs, we propose

MOTION ESTIMATION AND SMOOTHING

This section describes global and local motion estimation
methods which are used in the proposed method.
Section 2.1 describes the method to estimate interframe
image transformation or global motion. Local motion,
which deviates from the global motion, is estimatedseparately after global image alignment as described in
Section 2.2. The global motion is used for two purposes,
stabilization and image deblurring, while the local motion isused mainly for video completion. Section 2.3 describes the
motion smoothing algorithm which is essential for stabilizing global motion.

2.1 Global Motion Estimation
We first explain the method of estimating global motion
between consecutive images. In the case that a geometrictransformation between two images can be described by ahomography (or 2D perspective transformation), the relationship between two overlapping images IðpÞ and I 0 ðp0 Þ
can be written by p  Tp0 . p ¼ ½x y 1T and p0 ¼ ½x0 y0 1T are
pixel locations in projective coordinates, and  indicatesequality up to scale since the 3  3 matrix T is invariant toscaling.
Global motion is estimated by aligning pair-wise
adjacent frames assuming a geometric transformation as
detailed in [29]. In our method, an affine model is assumed
between consecutive images. We use the hierarchicalmotion estimation framework, where an image pyramid isfirst constructed in order to reduce the area of search bystarting computation with the coarsest level [5], [31]. By
applying the parameter estimation for every pair of adjacentframes, a global transformation chain is obtained.
Throughout this paper, we denote the discrete pixel
locations in the image coordinate It as pt ¼ fpit ¼ ðxi ; yi Þg.
The subscript t indicates the index of the frame. We also
denote the global transformation Tji to represent thecoordinate transform from frame i to j. Therefore, thetransformation of image It to the It1 coordinate can be
described as It ðTt1t pt Þ. Note that transformation T only
describes the coordinate transform; hence, It1 ðTtt1 pt Þ has
the pixel values of frame t  1 in the coordinates of frame t,
for instance.

4

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,

St ¼

X

VOL. 28,

NO. 7, JULY 2006

Tit ? GðkÞ;

ð1Þ

i2N t
1
where GðkÞ ¼ pﬃﬃﬃﬃek =2 is a p
Gaussiankernel, and ? is the
ﬃﬃﬃ
2
convolution operator, and  ¼ k is used. Using the obtained
matrices S0 ; . . . ; St , the original video frames can be warped
to the motion compensated video frames (see Fig. 3) by2

2

It0 ðp0t Þ

Fig. 3. Illustration of the global transformation chain T defined over theoriginal video frames Ii , and the transformation S from the original pathto the smoothed path. The bottom frame sequence is the motion
compensated sequence.

2.2 Local Motion Estimation
Local motion describes the motion which deviates from theglobal motion model, e.g., motion of moving objects orimage motion due to nonplanar scenes. Local motion isestimated by computing optical flow between frames after
applying a global transformation, using only the common
coverage areas between the frames.
A pyramidal version of Lucas-Kanade optical flow
computation [32], [33] is applied to obtain the local
00motion field Ftt ðpt Þ ¼ ½uðpt Þvðpt ÞT . Ftt ðpt Þ represents the
optical flow field from frame It ðpt Þ to It0 ðTtt0 p0t Þ, and u
and v are the flow vector elements along the x andy-direction, respectively.
2.3 Removal of Undesired Motion
A stabilized motion path is obtained by removing undesired motion fluctuation. As assumed in [14], theintentional image motion in videos is usually slow andsmooth; therefore, we treat the high frequency component
in the global motion chain as the unintentional motion.
Previous motion smoothing methods smooth out thetransformation chain itself or the cumulative transformation
chain with an anchoring frame. Our method, on the other
hand, smoothes temporally local transformations in order toaccomplish motion smoothing.
When smoothing is applied to the original transformation
chain T10 ; . . . ; Tii1 as it is done in prior works, the smoothed~ i is obtained. In this case, a~ 1; . . . ; Ttransformation chain T0i10motionQcompensated frame Ii is obtained by transforming Ii
i
n
~ nþ1
with
n¼0 Tnþ1 Tn . This cascade of the original andsmoothed transformation chain often generates accumulation error. In contrast, our method is free from accumulative
error because our method locally smoothes displacementfrom the current frame to the neighboring frames.
Instead of smoothing out the transformation chain
along the video, we directly compute the transformation
S from a frame to the corresponding motion compensatedframe using only the neighoring transformation matrices.
We denote the indices of neighboring frames as
N t ¼ fj : t  k  j  t þ kg. Let us assume that frame It
is located at the origin of the image coordinate, alignedwith the major axes.
We can calculate the spatial position of each neighboring
frame Is , relative to frame It , by the global transformation Tst .
We seek the correcting transformation S from the originalframe It to the motion compensated frame It0 by

It ðSt pt Þ:ð2Þ

Fig. 4 shows the result of our motion smoothing methodwith k ¼ 6 in (1). In Fig. 4, x and y-translation elements ofthe camera motion path are displayed. As we can see in
Fig. 4, abrupt displacements which are considered to be
unwanted camera motion are well reduced by our motion
smoothing. The smoothness of the new camera motion pathcan be controlled by changing k, with a larger k yielding asmoother result. We found that annoying high frequency
motion is well removed by setting k ¼ 6, i.e., about 0.5 sec
with NTSC. k can be increased when a smoother video ispreferred.

3

IMAGE DEBLURRING

After stabilization, motion blur, which is not associated to
the new motion of the video, becomes a noticeable noisethat needs to be removed. As mentioned in Section 1, it isoften difficult to obtain accurate PSFs from a free-motion
camera; therefore, image deblurring using deconvolution is
unsuitable for our case. In order to sharpen blurry frames
without using PSFs, we developed a new interpolationbased deblurring method. The key idea of our method istransferring sharper image pixels from neighboring frames
to corresponding blurry image pixels.
Our method first evaluates the “relative blurriness” of
the image by measuring how much of the high frequency
component has been removed from the frame in comparison to the neighboring frames. Image sharpness, which is
the inverse of blurriness, has been long studied in the fieldof microscopic imaging where accurate focus is essential[34], [35]. We use the inverse of the sum of squared gradientmeasure to evaluate the relative blurriness because of its
robustness to image alignment error and computational
efficiency. By denoting two derivative filters along the x
and y-directions by fx and fy , respectively, the blurrinessmeasure is defined by1
bt ¼ P 
2 
2  :
ðfx ? It Þðpt Þ þ ðfy ? It Þðpt Þpt

ð3ÞThis blurriness measure does not give an absoluteevaluation of image blurriness, but yields relative image
blurriness among similar images when compared to theblurriness of other images. Therefore, we restrict themeasure to be used in a limited number of neighboring
frames where significant scene change is not observed.
Also, the blurriness is computed using a common coveragearea which is observed in all neighboring frames. Relatively
blurry frames are determined by examining bt =bt0 ; t0 2 N t ,e.g., when bt =bt0 is larger than 1, frame It0 is considered to be
sharper than frame It .
Once relative blurriness is determined, blurry frames
are sharpened by transferring and interpolating corresponding pixels from sharper frames. To reduce relianceon pixels where a moving object is observed, a weightMATSUSHITA ET AL.: FULL-FRAME VIDEO STABILIZATION WITH MOTION INPAINTING

5

Fig. 4. Original motion path (dotted line) and smoothed motion path (solid line) with our displacement smoothing. Translations along X and Y direction
are displayed.

factor which is computed by a pixel-wise alignment error
Ett0 from It0 to It is used:


0
ð4Þ
Ett0 ðpt Þ ¼ It0 ðTtt pt Þ  It ðpt ÞÞ:High alignment error is caused by either moving objects
or error in the global transformation. Using the inverse of
pixel-wise alignment error E as a weight factor for theinterpolation, blurry pixels are replaced by interpolating
sharper pixels. The deblurring can be described byP
0It ðpt Þ þ t0 2N wtt0 ðpt ÞIt0 ðTtt pt Þ
^
P
;
ð5Þ
It ðpt Þ ¼
1 þ t0 2N wtt0 ðpt Þ
where w is the weight factor which consists of the pixelwise alignment error Ett0 and relative blurriness bt =bt0 ,expressed as(0
if bbt0 < 1tt
ð6Þ
wt0 ðpt Þ ¼ bt
b 0 E t ðp Þþ otherwise:
t

t0

t

 2 ½0; 1 controls the sensitivity on the alignment error,e.g., by increasing , the alignment error contributes less to
the weight. The weighting factor is defined in a way theinterpolation uses only frames which are sharper than thecurrent frame. This nonlinear operation approximates a
temporal bilateral filter [36] which avoids oversmoothingcaused by irrelevant image pixels.
Fig. 5 shows the result of our deblurring method. As we
can see in Fig. 5, blurry frames in the top row are well
sharpened in the bottom row. Note that since our method
considers the pixel-wise alignment error, moving objects arewell preserved without yielding ghost effects, which areoften observed with simple frame interpolation methods.

4

VIDEO COMPLETION WITH MOTION INPAINTING

Our video completion method locally adjusts image pixels
from neighboring frames using the local motion field inorder to obtain seamless stitching of the images in the
missing image areas. At the heart of our algorithm, motion
inpainting is proposed to propagate the motion field into themissing image areas where local motion cannot be directlycomputed. The underlying assumption is that the local
motion in the missing image areas is similar to that ofadjoining image areas. The flow chart of the algorithm isillustrated in Fig. 6. First, the local motion from theneighboring frame is estimated over the common coverage
image area. The local motion field is then propagated into
missing image areas. Note that unlike prior image inpainting works, we do not propagate color but propagate local
motion. Finally, the propagated local motion is used as a
guide to locally warp image pixels to achieve smoothstitching of the images.
Let Mt be the missing pixels, or undefined image pixels,
in the frame It . We wish to complete Mt for every frame t
while maintaining visually plausible video quality.

4.1 Mosaicing with Consistency Constraint
As a first step of video completion, we attempt to cover thestatic and planar part of the missing image area bymosaicing with an evaluation of its validity. When the
global transformation is correct and the scene in the missing
image area is static and planar, mosaics generated bywarping from different neighboring frames should beconsistent with each other in the missing area. Therefore,
it is possible to evaluate the validity of the mosaic by testing
the consistency of the multiple mosaics which cover thesame pixels. We use the variance of the mosaic pixel values
to measure the consistency; when the variance is high, themosaic is less reliable at the pixel. For each pixel pt in the
missing image area Mt , the variance of the mosaic pixel
values is evaluated by
vt ðpt Þ ¼

2
1 X
0
0
It0 ðTtt pt Þ  I t0 ðTtt pt Þ ;n  1 t0 2N

ð7Þ

t

where
0

I t0 ðTtt pt Þ ¼

1X
0
It0 ðTtt pt Þ;
n t0 2N

ð8Þtand n is the number of neighboring frames. For color
images, we use the intensity value of the pixel which iscomputed by 0:30R þ 0:59G þ 0:11B [37]. A pixel pt is filled
in by the median of the warped pixels only when thecomputed variance is lower than a predefined threshold T :0mediant0 It0 ðTtt pt Þ if vt < Tð9ÞIt ðpt Þ ¼
keep it as missing
otherwise:
If all missing pixels Mt are filled with this mosaicing
step, we can skip the following steps and move to the next
frame.

6

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,

VOL. 28,

NO. 7, JULY 2006

Fig. 5. The result of image deblurring. Top of the image pairs: original blurry images, and bottom: deblurred images with our method.

Fig. 6. Video completion. Local motion is first computed between the current frame and a neighboring frame. Computed local motion is thenpropagated with motion inpainting method. The propagated motion is finally used to locally adjust image pixels.

4.2 Local Motion Computation
From this step, each neighboring frame It0 is assigned apriority to be processed based on its alignment error. It is
often observed that the nearer frame shows a smalleralignment error, and thus has a higher processing priority.
The alignment error is computed using the common
0coverage area of It ðpt Þ and It0 ðTtt pt Þ byXIt ðpt Þ  It0 ðTt0 pt Þ:
ett0 ¼ð10Þtpt

Local motion is estimated by the method described in
Section 2.2.

4.3 Motion Inpainting
In this step, the local motion data in the known image areas
is propagated into the missing image areas. The propagation starts at pixels on the boundary of the missing image

area. Using motion values of neighboring known pixels,
motion values on the boundary are defined, and theboundary gradually advances into the missing area M
until it is completely filled as illustrated in Fig. 7.
Suppose pt is a pixel in a missing area M on image It .
Let qt 2 Hðpt Þ be the pixels of the neighborhood of pt , that
already has a defined motion value by either the initial local
motion computation or prior extrapolation of motion data.
With an assumption that the local motion variation is locallysmall, the local motion Fðpt Þ can be written as the following
equation using the local motion defined on neighboring
pixel qt :2
3
@F1 ðqt Þ @F1 ðqt Þ u@x@yFðpt ; qt Þ  Fðqt Þ þ 4 @F ðq Þ @F ðq Þ 5
2
2 t
t
v
ð11Þ
@x

@y

¼ Fðqt Þ þ rFðqt Þðpt  qt Þ;MATSUSHITA ET AL.: FULL-FRAME VIDEO STABILIZATION WITH MOTION INPAINTING

7

Fig. 7. Motion inpainting. (a) Motion field is propagated on the advancing front @M into M. (b) The color similarities between pt and its neighbors qt
are measured in the neighboring frame It0 after warped by local motion of qt . The computed color similarities are then used as weight factors for the
motion interpolation.

by the first order approximation of Taylor series expansion.
0
In (11), we denote F ¼ Ftt and use F1 and F2 to represent
the first and second (x-direction and y-direction) components in the motion vector, respectively. Also, we use ½x yTfor the pixel coordinate of qt and ½u vT to represent
displacement from pixel qt to pt , i.e., ½u vT ¼ pt  qt .
The motion value for pixel pt is generated by a weighted
average of the motion vectors of the pixels Hðpt Þ:P
qt 2Hðpt Þ wðpt ; qt Þ Fðqt Þ þ rFðqt Þðpt  qt ÞP;Fðpt Þ ¼
qt 2Hðpt Þ wðpt ; qt Þð12Þ
where the weighting factor wðpt ; qt Þ controls the contribution of the motion value of qt 2 Hðpt Þ to pixel pt .
The weighting factor wð; Þ is designed to reflect two
important factors: geometric distance and the pseudosimilarity of colors between p and q. The geometric distancecontrols the contribution to the new local motion vector,
e.g., the nearer q governs the new local motion on p more.
We define the geometric distance factor g bygðpt ; qt Þ ¼

1;
jjpt  qt jj

ð13Þ

which is evaluated on It image plane. The second factor,
pseudosimilarity of colors, attempts to rely on the motion
vector where its pixel color is similar to color value of thetarget pixel. The factor is considered as a measure formotion similarity, assuming that neighboring pixels ofsimilar colors belong to the same object in the scene and,thus, they will likely move in a similar motion. Since thecolor of pixel pt is unknown in frame It , we use theneighboring frame It0 for the estimation of pseudosimilarity
of colors. As illustrated in Fig. 7, qt0 are first located in theneighboring image It0 in Fig. 7b using qt and their local
motion. Using the geometric relationship between qt and pt
in Fig. 7a, pt0 are tentatively determined in It0 . Using pt0 and
qt0 , we measure the pseudosimilarity of colors by1cðpt ; qt Þ ¼;
jjIt0 ðqt0 þ pt  qt Þ  It0 ðqt0 Þjj þ 

ð14Þ

where  is a small value for avoiding division by zero. When
qt0 or qt0 þ pt  qt also fall into the missing region, we leave~
pt missing and proceed to the next missing pixel. Although
the measure does not capture the exact color similarity
between pt and qt , the color similarity between pt0 and qt0
on image It0 gives an approximation. For this approximation, we rely on the fact that the local pixel arrangement
does not vary dramatically in the small time frame. We are
currently using the l2 -norm for the color difference in RGB
space for the sake of computation speed, but different color
spaces, richer measures or intensity difference could
alternatively be used.
Using these two factors g and c, we define the weighting
factor by their product:wðpt ; qt Þ ¼ gðpt ; qt Þcðpt ; qt Þ:ð15Þ

To summarize, with the geometric factor g, the effect fromdistant pixels decreases. On the other hand, pseudosimilarity of colors c approximates anisotropic propagation of
local motion using the color similarity measure on theneighboring frame It0 .
The actual scanning and composition in the missing area
M is achieved using the Fast Marching Method (FMM) [38]as described by [39] in the context of image inpainting. Let@M be the group of all boundary pixels of missing image
area M (pixels which have a defined neighbor). Using
FMM, we are able to visit each undefined pixel only once,
starting with pixels of @M, and advancing the boundary
inside M until all undefined pixels are assigned motion
values as shown in Fig. 7. The pixels are processed inascending distance order from the initial boundary @M,such that pixels close to the known area are filled first. The
result of this process is a smooth extrapolation of the local
motion flow to the undefined area in a manner that
preserves object boundaries with color similarity measure.

4.4 Local Adjustment with Local WarpingOnce the optical flow field in the missing image area Mt is
obtained, we use it as a guide to locally warp It0 in order togenerate a smooth stitching even including moving objects.
It ðpt Þ00It0 ðTtt ðFtt pt ÞÞ:

ð16Þ

If some missing pixels still exist in It , the algorithm goesback to Step 1 and uses the next neighboring frame.
After the loop of Steps (a)-(c), most of the cases of
missing pixels are filled; however, sometimes there still8

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,

VOL. 28,

NO. 7, JULY 2006

Fig. 8. Result of video stabilization #1. Top row: Original input sequence. Middle row: stabilized sequence which still has missing image areas.
Bottom row: stabilized and completed sequence. The grid is overlaid for better visualization.

remain missing image pixels which are not covered bywarped neighboring images. In fact, the coverage of themissing image pixels is not guaranteed. Experimentally,
even though such remaining areas exist, they are always
small; therefore, we simply interpolate the neighboring
pixels to fill up the areas. Richer methods such as
nonparametric sampling [40], [15] or diffusion methods
can also be used to produce higher quality completion thanblurring, with additional computational cost.

4.5 Summary of the Algorithm
To summarize, we have the following algorithm for fillingin the missing image area M.
Goal: Let Mt be a set of missing image pixels in image It .
Fill in Mt using the neighboring frames fItk ; . . . ; Itþk g.
Mosaic with consistency checking
Compute ett0 where t0 : t  k  t0  t þ kWhile Mt 6¼ 0
for t ¼ argt0 minðett0 Þ to argt0 maxðett0 ÞCompute local motion from It to It00
Motion Inpainting to obtain full motion field Ftt0tFill in Mt by It0 with local motion information Ft
end of for-loop for t
end of while-loop for Mt
At the heart of the algorithm, motion inpainting ensuresspatial and temporal consistency of the stitched video.

5

EXPERIMENTAL RESULTS

To evaluate the performance of the proposed method, we
have conducted extensive experiments on 30 video clips(about 80 minutes in total) to cover different type of scenes.
We set the number of neighboring frames to be 2k ¼ 12
throughout the experiment.
In the following, we first show the result of video
completion in Section 5.1. Quantitative evaluation of thequality of resulting videos and computational performance
analysis are also described in Section 5.2 and Section 5.3,
respectively. We also show practical applications of ourvideo completion method in Section 5.4.

5.1 Video Completion Results
In our experiment, a 5  5 size filter h is used to perform
motion inpainting. In Fig. 8 and Fig. 9, the result of video
stabilization and completion is shown. In the two figures,the top row shows the original input images, and thestabilized result is in the middle row which contains asignificant amount of missing image areas. The missing
image areas are naturally filled in with our video completion method as shown in the bottom row.
Fig. 10 shows a comparison result. Fig. 10a shows theresult of our method, and the result of direct mosaicing isshown in Fig. 10b. As we can see clearly in Fig. 10b, themosaicing result looks jaggy on the moving object (sincemultiple mosaics are used), while our result Fig. 10a looks
more natural and smoother.
Fig. 11 shows our video completion results over different
scenes. The top-left pair of images shows a successful result ina scene containing a fast moving plane. The top-right pairshows the case of a nonplanar scene, and in the left-bottom
pair, an ocean wave is naturally composited with our method.
Similar to Fig. 10a, our method accurately handles local
motion caused by either moving objects or nonplanar scenes.
5.1.1 Failure Cases
Our method sometimes produces visible artifacts. Most of
the failure cases are observed when the global and/or local
motion estimation fails. Fig. 12 shows the failure example
due to the incorrect estimation of the global motion. The
filled-in image area of the completion result shown in
Fig. 12b becomes skewed due to the inaccurate stitching.
Another source of artifacts is the limited ability of the
motion inpainting, i.e., it is not capable of producing abruptchanges of motion in the missing image areas. Fig. 13 showssuch an example. In the figure, a boy swings down his arms,
but this motion is not observed in the input image sequence(top row) due to the limited field-of-view. The local motion
is computed over the input image sequence; however, it
does not contain sufficient information to describe the arms’
motion. As a result, the resulting images contain visible
artifacts as shown in the middle row. The ground truth
images are shown in the bottom row for the comparison.

MATSUSHITA ET AL.: FULL-FRAME VIDEO STABILIZATION WITH MOTION INPAINTING

9

Fig. 9. Result of video stabilization #2. Top row: Original input sequence. Middle row: stabilized sequence which still has missing image areas.
Bottom row: stabilized and completed sequence. The grid is overlaid for better visualization.

Fig. 10. Comparison of completion results. (a) Our method and (b) mosaicing. The rectangular areas in the images in the top row are closed up in thebottom row.

Fig. 11. Result of video completion over different types of scenes. In each pair, (a) is the stabilized image with missing image area (filled in by red),and (b) is the completion result.

5.2 Quantitative Evaluation of Video Completion
We have measured the quality of video completion in two
different ways: 1) deviation from the ground truth and2) evaluation of spatio-temporal smoothness. When the
produced video is close to the ground truth, it is reasonable
to say that the video is natural. The second evaluation is
performed on the results which are not close to the groundtruth, since they may still be “natural” although thedeviation from the ground truth is large. The goal of video

completion is generating visually natural videos, which is
not necessarily equivalent to being close to the groundtruth. We measure the “naturalness” by the spatio-temporalsmoothness of the video.

5.2.1 Deviation from the Ground Truth
In order to make a comparison with the ground truth, wehave cropped captured videos to produce smaller field-ofview videos and applied our video completion technique.

10IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,

VOL. 28,

NO. 7, JULY 2006

Fig. 12. Failure case #1. The filled-in area is skewed due to the inaccurate global/local motion estimation result. Dashed rectangle areas in the top
row are closed-up in the bottom row. (a) Original. (b) Our method. (c) The ground truth.

Fig. 13. Failure case #2. Top row: original input images with missing image areas. Middle row: result of video completion. Bottom row: the groundtruth. The artifacts are caused by the fact that motion inpainting is not able to produce the sudden changes of local motion in missing image areas.

In this way, we are able to compare the intensity differencesin the filled-in image areas between the produced video andthe ground truth. Fig. 14 shows the comparison with theground truth. In this experiment, five different video clips
are chosen as shown in the figure. The first column shows
the input images with missing image areas, and the second
column shows the result of video completion. The groundtruth is shown in the third column, and the right-mostcolumn shows the intensity difference between the resulting
image and the ground truth. The intensity is calculated by
0:30R þ 0:59G þ 0:11B [37]. In Fig. 14, the images where
moving objects appear at the boundaries of the missing
image areas are selected in order to assess the performanceof motion inpainting. Table 1 shows the mean absolutedifference (MAD) of intensity compared to the groundtruth. The mean is taken using image pixels of the filled-in
image areas. As shown in the table, our method outperforms the simple mosaicing method significantly.

5.2.2 Evaluation of Spatio-Temporal Smoothness
Sometimes, the deviation from the ground truth becomeslarge while the resulting video still looks natural. In fact, thegoal of the video completion is producing the visually natural
videos, which is not necessarily the same as producing videos
which are close to the ground truth. We consider that thenaturalness of the video can be partly evaluated by the spatial
and temporal consistency. The spatial consistency can bemeasured by how seamlessly missing image areas are filledin, while the temporal consistency can be evaluated bysmoothness of pixel transitions between successive frames at
temporal boundaries. If the spatial consistency is notachieved, a video frame may suffer from noticeable unnatural
seams. And, if the temporal consistency is violated, temporal
artifacts such as flickering may result in the video. We do notconsider that the spatial and temporal continuity of the video
can fully assess the quality of the resulting video. However,smooth transition of pixel values along spatial and temporalaxes is one important aspect of the statistics of natural videos.
TABLE 1Comparison with the Ground Truth

The numbers show the mean absolute difference of intensity in the filledin areas compared to the ground truth. Scene number corresponds tothe scenes shown in Fig. 14 from top to bottom.

MATSUSHITA ET AL.: FULL-FRAME VIDEO STABILIZATION WITH MOTION INPAINTING

11

Fig. 14. Comparison with the ground truth. (a) Input images with missing image areas, (b) results of video completion with motion inpainting, (c) the
ground truth, and (d) difference between the results and the ground truth (in intensity).

We use the magnitude of three-dimensional intensity
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
gradients jjrIjj ¼ rI  rI , where
2 @I 3@x
2
3
6 7
Iðx þ 1; y; tÞ  Iðx  1; y; tÞ
6 @I 7
7 4
5
rI ¼ 6ð17Þ
6 @y 7  Iðx; y þ 1; tÞ  Iðx; y  1; tÞ ;4 5
Iðx; y; t þ 1Þ  Iðx; y; t  1Þ@I@tin order to measure the spatio-temporal smoothness. We
define the normalized discontinuity measure D as theinverse of spatio-temporal smoothness that can be written as:
D¼

nX

jjrIi jj=n;

ð18Þ

i

where n is the number of pixels.
The discontinuity is measured on the spatio-temporalboundaries where images are stitched together. Since thediscontinuity D does not provide absolute measure, we
compared the discontinuity between our method and asimple mosaicing method. We denote the discontinuity of
our method and mosaicing with DO and DM , respectively.
In order to assess the quality difference, we pick upboundary pixels p which are in motion, i.e., where the0
local motion Ftt ðpÞ 6¼ ½0 0T . We directly compare thespatio-temporal smoothness in our result with that of themosaicing result in order to see which provides smootherresult using the average discontinuity DA obtained from thesurrounding image areas. The average discontinuity DA is

used as a standard discontinuity in the video. The relativesmoothness is evaluated byððDM  DA Þ  ðDO  DA ÞÞ=ðDM  DA Þ ¼
ðDM  DO Þ=ðDM  DA Þ:
In this experiment, we have used seven different video clips(about 8,000 frames in total). The measured smoothness was
generally higher using our method, and a 11.2 percent
smoother result on average compared to the mosaicing
method was obtained, ranging in 5:9  23:5%.

5.3 Computational Cost
In order to clarify the bottleneck of the computation forfurther development, we have measured the computational
cost for each algorithm component.
The computational cost of our current research implementation is about 2.2 frames per second for a video in thesize of 720  486 with a Pentium4 2.8 GHz CPU. Letting thenumber of frames in the video be N and the smoothness
parameter be k, the computational cost of the algorithm
blocks and the number of computations are summarized inTable 2. Note that the computational cost is measured
without any hardware acceleration. As shown in Table 2,
the computational time is proportional to the number offrames N and is also roughly proportional to the smoothness parameter k. Among the algorithm blocks, most of thecomputation time is spent on local motion estimation.
Therefore, it is important to speed up the local motion
estimation part for the realization of real-time implementa-

12IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,

VOL. 28,

NO. 7, JULY 2006

TABLE 2
Summary of Computational Cost

The computational time is proportional to the number of frames N. The percentage is measured when the smoothness k ¼ 6. The number of times
represents the count of operations of each computation block.

Fig. 15. Sensor dust removal. (a) Spots on the camera lens are visible in the original video. (b) The spots are removed from the entire sequence bymasking out the spot areas and applying our video completion method.

tion. Utilizing GPU power as it is done in [41], it will bepossible to significantly improve the speed.

5.4 Other Video Enhancement Applications
In addition to video stabilization, the video completion anddeblurring algorithms we developed in this paper can also
be used in a range of other video enhancement applications.
We show two interesting ones here: sensor dust removalfrom a video, caused by dirt spots on the video lens or
broken CCD, and overlaid text/logo removal. They can beconsidered as a problem of filling up specific image areas
which are marked as missing. This can be naturally applied
to time-stamp removal from a video. In particular, when astabilizing process is applied to a video, it is essential toremove these artifacts from the video since they become
shaky in the final stabilized video. In this experiment, we
manually marked artifacts as missing image areas. The
missing image areas are then filled up by our video
completion method.
Fig. 15 shows the result of sensor dust removal. Fig. 15a
is a frame from the original sequence, and circles indicate
the spots on the lens. The resulting video frames are freefrom these dirt spots as they are filled up naturally as
shown in the right image. Fig. 16 shows the result of text
removal from a video. The first row shows the original
sequence, and some text is overlaid in the second row.
Marking the text areas as missing image areas, our video
completion method is applied. The bottom row shows theresult of the completion. The result looks almost identical tothe original images since the missing image areas arenaturally filled up. The absolute intensity difference of theoriginal and result images is taken in Fig. 17d. The result
image is not identical to the original image; however, thedifference is small, and more importantly, visual appearance is well preserved.

6

DISCUSSION AND CONCLUSION

We have proposed video completion and deblurring
algorithms for generating full-frame stabilized videos. A
new efficient completion algorithm based on motion
inpainting is proposed. Motion inpainting propagatesmotion into missing image areas, and the propagated motion
field is then used to seamlessly stitch images. We have also
proposed a practical deblurring algorithm which transfers
and interpolates sharper pixels of neighboring frames
instead of estimating PSFs. The proposed completion
method implicitly enforces spatial and temporal consistency
supported by motion inpainting. Spatial smoothness of theimage stitch is indirectly guaranteed by the smoothness ofthe extrapolated optical flow. Also, temporal consistency on
both static and dynamic areas is given by optical flow fromthe neighboring frames. These properties make the resulting
videos look natural and coherent.

6.1 Limitations
Our method strongly relies on the result of global motion
estimation which may become unstable when a moving
object covers large amounts of image area, for example. We
are using a robust technique to eliminate outliers; however, itMATSUSHITA ET AL.: FULL-FRAME VIDEO STABILIZATION WITH MOTION INPAINTING

13

Fig. 16. Result of overlaid text removal from the entire sequence of a video. Top row: original image sequence. Middle row: the input with overlaid
text. Bottom row: result of overlaid text removal.

Fig. 17. Comparison of the ground truth and the text removal result. (a) A frame from the original video, (b) a text is overlaid on the original video,(c) result of text removal, and (d) absolute intensity difference between the original and result frame.

fails when more than half the area of the image is occluded bya moving object. Local motion estimation also has limitations, and may generate wrong results for very fast moving
objects where the local motion estimation is difficult. In thesecases, neighboring frames will not be warped correctly, andthere will be visible artifacts at the boundary. To increase thesmoothness at the boundaries, we will be able to use further
methods, such as boundary matting [42] and graphcut-based
synthesis [43], [44] upon our method.
The proposed method has been tested on a wide varietyof video clips to verify its effectiveness. In addition, we
have demonstrated the applicability of the proposed
method for practical video enhancement by showing sensor
dust removal and text removal results.

REFERENCES
[1]
[2]
[3]
[4]
[5]
[6]

I. Zoghlami, O. Faugeras, and R. Deriche, “Using Geometric
Corners to Build a 2D Mosaic from a Set of Images,” Proc. IEEE
Conf. Computer Vision and Pattern Recognition, pp. 420-425, 1997.
D. Capel and A. Zisserman, “Automated Mosaicing with SuperResolution Zoom,” Proc. IEEE CS Conf. Computer Vision and Pattern
Recognition, pp. 885-891, 1998.
A. Cenci, A. Fusiello, and V. Roberto, “Image Stabilization by
Feature Tracking,” Proc. 10th Int’l Conf. Image Analysis andProcessing, pp. 665-670, 1999.
M. Brown and D. Lowe, “Recognizing Panoramas,” Proc. Int’l
Conf. Computer Vision, pp. 1218-1225, 2003.
J. Bergen, P. Anandan, K. Hanna, and R. Hingorani, “HierarchicalModel-Based Motion Estimation,” Proc. Second European Conf.
Computer Vision, pp. 237-252, 1992.
R. Szeliski, “Image Mosaicing for Tele-Reality Applications,”
technical report, CRL-Digital Equipment Corp., 1994.

[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]

[15]
[16]

[17]
[18]

T.-J. Cham and R. Cipolla, “A Statistical Framework for Longrange
Feature Matching in Uncalibrated Image Mosaicing,” Proc. IEEE
Conf. Computer Vision and Pattern Recognition, pp. 442-447, 1998.
Z. Zhu, G. Xu, Y. Yang, and J. Jin, “Camera Stabilization Based on
2.5D Motion Estimation and Inertial Motion Filtering,” Proc. IEEE
Int’l Conf. Intelligent Vehicles, vol. 2, pp. 329-334, 1998.
R. Szeliski, “Image Alignment and Stitching: A Tutorial,”
Technical Report MSR-TR-2004-92, Microsoft Corp., 2004.
M. Hansen, P. Anandan, K. Dana, G. van der Wal, and P. Burt,“Real-Time Scene Stabilization and Mosaic Construction,” Proc.
IEEE Conf. Computer Vision and Pattern Recognition, pp. 54-62, 1994.
C. Buehler, M. Bosse, and L. McMillan, “Non-Metric Image-Based
Rendering for Video Stabilization,” Proc. IEEE Conf. Computer
Vision and Pattern Recognition, vol. 2, pp. 609-614, 2001.
Z. Duric and A. Resenfeld, “Shooting a Smooth Video with a Shaky
Camera,” J. Machine Vision and Applications, vol. 13, pp. 303-313,
2003.
M. Pilu, “Video Stabilization as a Variational Problem andNumerical Solution with the Viterbi Method,” Proc. IEEE Conf.
Computer Vision and Pattern Recognition, vol. 1, pp. 625-630, 2004.
A. Litvin, J. Konrad, and W. Karl, “Probabilistic Video
Stabilization Using Kalman Filtering and Mosaicking,” Proc.
IS&T/SPIE Symp. Electronic Imaging, Image, and Video Comm.,
pp. 663-674, 2003.
Y. Wexler, E. Shechtman, and M. Irani, “Space-Time Video
Completion,” Proc. IEEE Conf. Computer Vision and Pattern
Recognition, vol. 1, pp. 120-127, 2004.
J. Jia, T. Wu, Y. Tai, and C. Tang, “Video Repairing: Inference ofForeground and Background under Severe Occlusion,” Proc. IEEE
Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 364-371,
2004.
V. Cheung, B.J. Frey, and N. Jojic, “Video Epitomes,” Proc. IEEE
Conf. Computer Vision and Pattern Recognition (CVPR), pp. 42-49,
2005.
R. Fabian and D. Malah, “Robust Identification of Motion andOut-of-Focus Blur Parameters from Blurred and Noisy Images,”
CVGIP: Graphical Models and Image Processing, vol. 53, no. 5,
pp. 403-412, 1991.

14

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,[19] B. Bascle, A. Blake, and A. Zisserman, “Motion Deblurring andSuper-Resolution from an Image Sequence,” Proc. Fourth European
Conf. Computer Vision, vol. 2, pp. 573-582, 1996.
[20] P. Jansson, Deconvolution of Image and Spectra, second ed.
Academic Press, 1997.
[21] A. Rav-Acha and S. Peleg, “Restoration of Multiple Images with
Motion Blur in Different Directions,” Proc. Fifth IEEE Workshop
Application of Computer Vision, pp. 22-28, 2000.
[22] Y. Yitzhaky, G. Boshusha, Y. Levy, and N. Kopeika, “Restorationof an Image Degraded by Vibrations Using Only a Single Frame,”
Optical Eng., vol. 39, no. 8, pp. 2083-2091, 2000.
[23] M. Ben-Ezra and S. Nayar, “Motion-Based Motion Deblurring,”
IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 6,
pp. 689-698, June 2004.
[24] E. Adelson, “Depth-of-Focus Image Processing Method,” US
Patent 4,661,986, 1987.
[25] J.R. Bergen, “Method and Apparatus for Extended Depth of Field
Imaging,” US Patent 6,201,899, 2001.
[26] M. Ben-Ezra, A. Zomet, and S.K. Nayar, “Video Super-Resolution
Using Controlled Subpixel Detector Shifts,” IEEE Trans. PatternAnalysis and Machine Intelligence, vol. 27, no. 6, pp. 977-987, June
2005.
[27] M. Bertalmio, G. Sapiro, V. Caselles, and C. Ballester, “Image
Inpainting,” Proc. SIGGRAPH Conf., pp. 417-424, 2000.
[28] A. Criminisi, P. Perez, and K. Toyama, “Object Removal by
Exemplar-Based Inpainting,” IEEE Conf. Computer Vision and
Pattern Recognition, vol. 2, pp. 721-728, 2003.
[29] H.-Y. Shum and R. Szeliski, “Construction of Panoramic Mosaics
with Global and Local Alignment,” Int’l J. Computer Vision, vol. 36,
no. 2, pp. 101-130, 2000.
[30] M. Irani and S. Peleg, “Improving Resolution by Image Registration,” CVGIP: Graphical Models and Image Processing, pp. 231-239,
1991.
[31] P. Anandan, “A Computational Framework and an Algorithm for
the Measurement of Visual Motion,” Int’l J. Computer Vision, vol. 2,
no. 3, pp. 283-310, 1989.
[32] B. Lucas and T. Kanade, “An Iterative Image Registration
Technique with an Application to Stereo Vision,” Proc. Int’l Joint
Conf. Artificial Intelligence, pp. 674-679, 1981.
[33] J. Bouguet, “Pyramidal Implementation of the Lucas Kanade
Feature Tracker: Description of the Algorithm,” OpenCV Document, Intel, Microprocessor Research Labs, 2000.
[34] E. Krotkov, “Focusing,” Int’l J. Computer Vision, vol. 1, no. 3,
pp. 223-237, 1987.
[35] N. Zhang, M. Postek, R. Larrabee, A. Vladar, W. Keery, and S.
Jones, “Image Sharpness Measurement in the Scanning Electron
Microscope,” The J. Scanning Microscopies, vol. 21, pp. 246-252,
1999.
[36] C. Tomasi and R. Manduchi, “Bilateral Filtering for Gray andColor Images,” Proc. Int’l Conf. Computer Vision, pp. 836-846, 1998.
[37] J. Foley, A. vanDam, S. Feiner, and J. Hughes, Computer Graphics:
Principles and Practice. Addison-Wesley, 1996.
[38] J. Sethian, Level Set Methods: Evolving Interfaces in Geometry, Fluid
Mechanics, Computer Vision and Materials Sciences. Cambridge
Univ. Press, 1996.
[39] A. Telea, “An Image Inpainting Technique Based on the Fast
Marching Method,” J. Graphics Tools, vol. 9, no. 1, pp. 23-34, 2004.
[40] A. Efros and T. Leung, “Texture Synthesis by NonparametricSampling,” Proc. Int’l Conf. Computer Vision, pp. 1033-1038, 1999.
[41] R. Strzodka and C. Garbe, “Real-Time Motion Estimation and
Visualization on Graphics Cards,” Proc. IEEE Visualization Conf.,
pp. 545-552, 2004.
[42] C. Rother, V. Kolmogorov, and A. Blake, “‘Grabcut’: Interactive
Foreground Extraction Using Iterated Graph Cuts,” ACM Trans.
Graphics, vol. 23, no. 3, pp. 309-314, 2004.
[43] Y. Boykov and M. Jolly, “Interactive Graph Cuts for Optimal
Boundary and Region Segmentation of Objects in N-D Images,”
Proc. Int’l Conf. Computer Vision, pp. 105-112, 2001.
[44] V. Kwatra, A. Schödl, I. Essa, G. Turk, and A.F. Bobick, “Graphcut
Textures: Image and Video Synthesis Using Graph Cuts,” ACM
Trans. Graphics, vol. 22, no. 3, pp. 277-286, 2003.

VOL. 28,

NO. 7, JULY 2006

Yasuyuki Matsushita received the BEng,
MEng, and PhD degrees in electrical engineering from the University of Tokyo in 1998, 2000,
and 2003, respectively. Currently, he is a
researcher in Visual Computing Group at Microsoft Research Asia. His research interests
include photometric methods in computer visionand video improvement algorithms. He is amember of IEEE.

Eyal Ofek received the BS degree in mathematics, physics, and computer science in 1987,
the MS degree in computer science in 1992, and
the PhD degree in computer science in 2000, allfrom the Hebrew University. He is a researcher
at Microsoft Virtual earth, previously at Microsoft
Research Asia. His interests are in IBR, visionbased interaction, and rendering. He is amember of the IEEE.

Weina Ge received the BS degree in computerscience from Zhejiang University in 2005. She iscurrently a PhD candidate and research assistant in the Computer Science and Engineering
Department at Penn State University. Her
research interests include computer vision,
image retrieval, and data mining.

Xiaoou Tang received the BS degree from the
University of Science and Technology of China,
Hefei, in 1990, the MS degree from the
University of Rochester, New York, in 1991,
and the PhD degree from the Massachusetts
Institute of Technology, Cambridge, in 1996. He
was a professor and the director of Multimedia
Lab in the Department of Information Engineering, the Chinese University of Hong Kong until
2005. Currently, he is the group manager of the
Visual Computing Group at Microsoft Research Asia. He is a local chairof the IEEE International Conference on Computer Vision (ICCV) 2005,
an area chair of ICCV07, a program chair of ICCV09, and a generalchair of the IEEE ICCV International Workshop on Analysis andModeling of Faces and Gestures 2005. He is a guest editor of thespecial issue on underwater image and video processing for the IEEE
Journal on Oceanic Engineering and the special issue on image andvideo-based biometrics for IEEE Transactions on Circuits and Systems
for Video Technology. He is an associate editor of the IEEE
Transactions on Pattern Analysis and Machine Intelligence (TPAMI).
His research interests include computer vision, pattern recognition, andvideo processing. He is a senior member of the IEEE.
Heung-Yeung Shum received the PhD degree
in robotics from the School of Computer
Science, Carnegie Mellon University in 1996.
He worked as a researcher for three years in the
Vision Technology Group at Microsoft Research
Redmond. In 1999, he moved to Microsoft
Research Asia where he is currently the managing director. His research interests include
computer vision, computer graphics, human
computer interaction, pattern recognition, statistical learning, and robotics. He is on the editorial boards of the IEEE
Transactions on Pattern Analysis and Machine Intelligence (TPAMI), theInternational Journal on Computer Vision (IJCV), and Graphical Models.
He was the general cochair of the 10th International Conference on
Computer Vision (ICCV 2005, Beijing). He is a fellow of the IEEE.