1

Interactive Video Completion
Makoto Okabe, Keita Noda, Yoshinori Dobashi, Member, IEEE, and Ken Anjyo, Member, IEEE
Abstract—We propose an interactive video completion method aiming for practical use in a digital production workplace. The results ofearlier automatic solutions often require considerable amount of manual modifications to make them usable in practice. To reduce sucha laborious task, our method offers an efficient editing tool. Our iterative algorithm estimates the flow fields and colors in space-timeholes in the video. As in earlier approaches, our algorithm uses an L1 data term to estimate flow fields. However, we employ a novelL2 data term to estimate temporally coherent color transitions. Our GPU implementation enables the user to interactively complete avideo by drawing holes and immediately removes objects from the video. In addition, our method successfully interpolates sparse
modifications initialized by the designer. According to our subjective evaluation, the videos completed with our method look significantly
better than those with other state-of-the-art approaches.
Index Terms—Image and video inpainting, interactive technique, subjective evaluation, optical flow, image-based rendering.

F

1

I NTRODUCTIONV

IDEO completion is one of the most highly demanded
skills in the digital production workplace, because
postproduction designers must always complete tasks suchas the removal of objects, logos, annotations, and noises
from videos. As there are few practical methods for video
completion, these tasks rely heavily on designers’ manual
edits to create convincing natural-looking results. However,such manual video completion is very demanding. Hence,
we set out to develop a practical method to help designers.
A lot of practical methods have been proposed for image
completion rather than video completion, some of which arewidely implemented in commercial image editing software
products. State-of-the-art image completion algorithms arecomputationally efficient, thus allowing the users to work
interactively through trial and error: this is crucial to obtainsatisfactory results, because the image automatically completed by a computer is often far from perfect.
However, video completion remains challenging for two
reasons:

1)

2)

•

•

1)

Computational complexity increases with the number of video frames, which makes it difficult for theuser to work interactively by trial and error.
The quality of the completed video is often not satisfactory due to failures in estimating the dynamic
motion of the camera and objects.

For example, the previous methods developed by [1], [2],[3], [4], [5], [6], [7] suffer from these two problems: they arecomputationally costly and their results contain a significant•

number of visible artifacts, caused by the loss of temporal
coherence. Bokov et al. proposed an efficient method that ismore than 100 times faster than the previous method [8],which takes 75 seconds to complete a 90-frame ‘camel’video with a resolution of 854 × 480 pixels. Murase et al.
recently proposed a more efficient method that completes
a video with a resolution of 832 × 448 pixels in video
rate, e.g., 32 frames per second (FPS) [9]. However, visible
artifacts are often found in the results produced by these
efficient algorithms. Furthermore, such artifacts are difficult
to modify manually. Note that given a completed video
with such artifacts, digital artists have to remove them by
typically performing manual image editing frame by frame.
To address these issues, we propose a novel algorithm
based on a flow-guided color estimation approach, which
we demonstrate is useful for practical usage (Fig. 1). We
present three technical contributions:M. Okabe and K. Noda are with Graduate School of Engineering, Shizuoka
University, 3-5-1 Johoku, Naka-ku, Hamamatsu, Shizuoka, 432-8561,
Japan.
E-mail: m.o@acm.org, noda.keita.17@shizuoka.ac.jp
Y. Dobashi is with Graduate School of Information Science and Technology, Hokkaido University, Kita-ku, Kita 14, Nishi 9, Sapporo, 060-0814,
Japan.
E-mail: doba@ime.ist.hokudai.ac.jp
K. Anjyo is with OLM Digital, Inc. and CMIC, Victoria University of
Wellington, Dens Kono Bldg., Room 302 OLM Digital ViPlus, 1-8-8
Wakabayashi, Setagaya, Tokyo, 154-0023, Japan.
E-mail: anjyo@acm.org

2)

3)

Our iterative algorithm estimates flow fields andcolors in the holes alternately. We propose to use
the L1 data term for flow field estimation but theL2 data term for color estimation. This is a technically simple modification, but the quality of thecompleted video is significantly improved: the L2
data term successfully removes temporally visible
artifacts caused by the L1 data term (Fig. 1-a and 1b).
Our L2 data term also allows the user to modify
the completed video efficiently. We demonstratethat the manual modification on single or a few
frames yields dramatic improvements in the qualityof the completed video. It is impossible to achieve
such improvements using the L1 data term (Fig. 1-c
and 1-d).
Our method is computationally efficient enough forinteractive video completion. The user interactively
draws a mask and our method immediately removes objects from the video. Such a user interaction has never been demonstrated in the previous
papers.

2

Fig. 1. We removed the flamingo specified by the mask from the input video. The time required to process a 80-frame ‘flamingo’ video at a pixel
resolution of 854 × 480 was 4.3 seconds. The top row shows frames from the completed videos and the bottom row shows the correspondingx − time slice along the yellow line. The result based on the L1 data term has artifacts (a), which are clearly visible as seams in the x − timeslice. On the other hand, our result based on the L2 data term has smoother color transitions (b): our result still suffers from ghosting artifacts but
was more desirable for the audience (see Sec. 4.8). To remove the artifacts, we manually modified a frame and reapplied our algorithm. The result
based on the L1 data term still contains artifacts (c), but artifacts were successfully removed from the result based on the L2 data term (d). Our
supplementary video shows the differences more clearly.

We demonstrate the successful completion of a variety ofvideos using our prototyping system. According to our
subjective evaluation, the quality of the videos completed
by our method is significantly better than those completedusing state-of-the-art methods. The result of our subjective
evaluation clearly indicates that our L2 scheme proves to besuperior to the L1 scheme of all the other methods.

2

P REVIOUS W ORK

There are two main approaches to automatic video completion: one is the patch-based approach and the other is theflow-guided color estimation approach.
Wexler et al. proposed the first patch-based method forvideo completion [1]. They used a 5 × 5 × 5 space-time
patch and iterated a pair of operations: 1) nearest neighborpatch searches and 2) calculation of the weighted averages
to fill in the holes. They showed that the problem of video
completion can be formalized as a maximum likelihood
estimation and their iterative optimization is an expectation
maximization (EM)-like algorithm. Newson et al. extended
Wexler et. al.’s method by introducing PatchMatch anddeveloping an efficient algorithm [4].
To improve temporal coherence of completed videos,
not only colors but also flow fields in space-time holes
are estimated [10], [11]. Le et al. extended Newson et al.’s
algorithm by taking flow fields into account [7]. They did
not use a cube-shaped patch, but instead chose a patch withx − y slices that are varied based on the flow field. This
improves the quality of the completed video dramaticallycompared with the previous methods and often produces
the best results.
Roxas et al. proposed a flow-guided color estimation
method [5]. They introduced an energy function for video
completion by extending the energy function used for optical flow estimation. Huang et al. proposed an energyfunction that combines the patch-based approach with flowguided color estimation [6]. They proposed an iterative
optimization algorithm to minimize the energy function,
where the patch-based approach, flow-guided color estimation, and flow field estimation are iterated until they
converge. However, the computational complexity of thisoptimization algorithm is high, and it takes 3 hours to complete a 90-frame video with a resolution of 854 × 480 pixels,
thus prohibiting practical usage. Bokov et al. proposed an efficient method that is more than 100 times faster than Huang
et al.’s method [8]. As the bottleneck of the flow-guided
color estimation is the optical flow estimation, Bokov et al.
efficiently estimated flow fields by applying a fast opticalflow algorithm to a sparse grid in the image space [12].
This successfully reduced the computational complexity.
Instead of an iterative optimization algorithm to minimize
the energy function, the flow-guided color estimation issolved only once. Recently, Murase et al. more efficiently
estimated flow fields of occluded background regions using
convolutional neural networks (CNNs) [9]. This methodcompletes a video with a resolution of 832 × 448 pixels
in video rate, e.g., 32 FPS. These methods work well for avariety of videos, but the completed videos tend to containvisible artifacts, especially space-time seams in dynamic
regions. To address these issues, we propose a fast flowguided color estimation method that produces significantly
better results.
The approach of estimating colors and flow fields atthe same time is applied to other video editing problems:for example, Nandoriya et al. removed reflections from a
video [13]. The propagation of colors along the known flow
fields of a video is another issue: Sadek et al. propagated
the user’s edit on a frame throughout the video with lessnoticeable artifacts [14].

33F LOW- GUIDED C OLOR E STIMATIONOur goal is to complete space-time holes in videos andproduce natural-looking results. Let V denote the video and
W , H , and T be its width, height, and number of frames,
i.e., V is the space-time volume with dimensions W ×H ×T
voxels. Let p be the voxel position (x, y, t). V(p) gives thevoxel value at p, which corresponds to a scalar intensity
value from 0 to 1. Let Ff denote the forward flow fieldof V. The flow vector at p is Ff (p) = (dx, dy, 1), whichindicates that a voxel position p = (x, y, t) at t-th frame
moves to p + Ff (p) = (x + dx, y + dy, t + 1) at (t + 1)-thframe. Similarly, let Fb denote the backward flow field, i.e.,
Fb (p) = (dx, dy, −1). Let P = {(x, y, t)|1 ≤ x ≤ W, 1 ≤y ≤ H, 1 ≤ t ≤ T } be the set of voxel positions in thespace-time volume. Let H be the set of voxel positions inthe space-time holes in V. We describe the naturalness of acompleted video using the following energy function:

E = Ef + Eb ,

(1)

where

Ef =

X

wf (p)λ|V(p) − V(p + Ff (p))| +p∈P|∇Ff,x (p)| + |∇Ff,y (p)|,

(2)

and

Eb =

X

wb (p)λ|V(p) − V(p + Fb (p))| +p∈P|∇Fb,x (p)| + |∇Fb,y (p)|.

(3)

wf (p) and wb (p) are weights on the data terms used when
computing the flow fields. Each of F∗,x and F∗,y represents
x or y component of F∗ respectively, and ∇ represents thegradient operator (∂/∂x, ∂/∂y). We want to compute V, Ff ,and Fb that minimize E , i.e., we want to solve arg min E .
V,Ff ,Fb

We set λ to 0.1 in all of our experiments.
The first terms of Eqs. 2 and 3 are the data terms representing the similarity between the voxel values of adjacentframes. The other terms are smoothness terms representing
the smoothness of the forward and backward flow fields.
Eqs. 2 and 3 are all derived from the energy function of the
optical flow estimation, which consists of an L1 data term
and the sum of the total variation (TV) of the flow field [15].
The energy function of Eq. 1 is non-convex and may havean infinite number of local minima. To complete the video
with a good local minimum, we begin with an initial video,and estimate V iteratively by refining this video to decrease
the energy function. We show our iterative algorithm in
Algorithm 1.
We compute the initial flow fields Ff and Fb (line 2 inAlgorithm 1). We set wf (p) and wb (p) as follows:(
0 p ∈ H or p + Ff (p) ∈ H,
wf (p) =(4)
1 otherwise,(
0 p ∈ H or p + Fb (p) ∈ H,
wb (p) =(5)
1 otherwise.
We then compute the flow fields by applying the TVL1 optical flow estimation algorithm [15]. Since the data
terms are ignored in the holes (H), the flows estimatedAlgorithm 1 Our iterative algorithm
Input: V: an input video,
H: a set of voxel positions in the space-time holes
Output: V: a completed video
1: Downsample V to (L − 1)-th pyramid level
2: Initialize Ff and Fb
by setting wf (p) and wb (p) based on Eqs. 4 and 5
and applying TV-L1 algorithm
3: for l from L − 1 to 0 do
4:
Set wf (p) and wb (p) based on Eqs. 6 and 7
5:
for i from 1 to 3l do
6:Fix Ff and Fb and update V
by minimizing Eq. 10 for all p ∈ H
7:
Fix V and update Ff and Fb
by applying TV-L1 algorithm
8:
end for9:
Upsample V, Ff , and Fb .
10: end foroutside the holes (H) are interpolated into the holes (H).
In the TV-L1 optical flow estimation algorithm, an iterative
optimization algorithm is applied to the relaxed versionof the problem, where the data and smoothness terms areminimized alternately until they converge. We apply the TVL1 algorithm independently for forward and backward flow
fields: we minimize Eq. 2 to initialize Ff ; we minimize Eq. 3
to initialize Fb .
During each iteration (from line 5 to line 8 in Algorithm 1), we alternate between the completed video (V) andthe flow fields (Ff and Fb ) as the variable with respect towhich E is minimized. We first fix Ff and Fb and minimize
E to update V. We are interested only in the data terms
here, which can be minimized using the algorithms appliedin previous methods [5], [6], [8]. However, the results produced by the previous methods contain significant visible
artifacts, since minimization of the L1 data terms brings
temporally incoherent solutions. To address this issue, weestimate the voxel value by minimizing E based on theL2 data terms rather than the L1 data terms: note that thesolution using the L2 data terms is one of the solutions of
the L1 data terms (as described in Sec. 3.2.1), but our results
have much less artifacts. We then fix V and minimize E toupdate Ff and Fb . We set wf (p) and wb (p) as follows:(α p ∈ H or p + Ff (p) ∈ H,
wf (p) =(6)
1 otherwise,(
α p ∈ H or p + Fb (p) ∈ H,
wb (p) =(7)
1 otherwise,
where α is the user-specified parameter. We then apply theTV-L1 optical flow estimation algorithm. The flow fields are
improved with respect to the previous iteration.
We extend this iterative algorithm to the multiresolutional approach to efficiently obtain the final result(from line 3 to line 10 in Algorithm 1). We start with acoarse version of V (line 1 in Algorithm 1). Ff and Fb
are initialized in the coarse resolution. We then use bilinear
interpolation to upsample V, Ff , and Fb and switch toa finer level once the coarser level is finished. We let L4denote the number of pyramid levels. In our experiments,
the number of iterations of our iterative algorithm for lth pyramid level is 3l , where l ∈ {0, ..., L − 1}, and 0-thand (L − 1)-th levels correspond to the finest and coarsest
resolutions, respectively. We have chosen 3l as the numberof iterations, since it gives good convergence of our iterativealgorithm.
In Sec. 3, we describe our method assuming that the
input is a grayscale video, i.e., each voxel of V has anintensity value. When the input video is multi-channel, e.g.,each voxel has red-green-blue (RGB) color channels, weapply the method described in Sec. 3 for each color channel
independently. However, since, the flow fields Ff and Fb
must be the same for all the color channels, we compute theflow fields by applying the TV-L1 algorithm to the grayscale
video whose intensity value is computed as the average of
all the color channels.
3.1

Differences from Previous Methods

Our energy function of Eq. 1 is different from any other energy functions used in the previous methods. Roxas et al.’senergy function is similar to ours but they added an energy
term to guarantee the temporal smoothness of flow fields.
Also, while wf (p) and wb (p) are constant in our method,they were unknown variables to be optimized in Roxas
et al.’s method. As the result, the minimization required acomplex optimization algorithm whose computational cost
was high. A part of Huang et al.’s energy function is alsosimilar to ours but they added an energy term to guarantee
the similarity between corresponding local patches. They
minimized the added term by a patch-based texture synthesis method but this was computationally expensive. Bokov
et al. defined no energy function, and they used neither
an iterative optimization algorithm nor a multi-resolutional
approach. As the result, the method was fast but it produced
visible artifacts especially when the camera motion was
dynamic.
We design our energy function inspired by these methods but it is more simple compared with the previous
methods. Since we compute only V, Ff , and Fb , our optimization algorithm has also become simple that can produce
significantly better results more efficiently than the previous
methods.
3.2

values. Fig. 2 shows how these tracking and sampling are
performed in the x − time slice. Let p0 be equal to p. We
define pu so that pu+1 = pu +Ff (pu ) for u ≥ 0 and pu−1 =pu + Fb (pu ) for u ≤ 0. The method computes the forward
and backward trajectories of a particle starting from p0 until
it leaves the holes. Let pF and pB be the positions of theendpoints of the trajectories: the suffixes F and B denote
temporal distances from p to the endpoints (see Fig. 2).

Fig. 2. Starting from p0 , we track the forward and backward flow fields
and sample the voxel values at pF and pB .

Roxas et al. [5] and Bokov et al. [8] determined the voxel
value V(p) so that V(p) = V(pF ) or V(p) = V(pB ). Since
Huang et al. had an initial solution computed by their patchbased approach, V(p) was iteratively updated. However,unless such an initial solution is given, their method also
gives the voxel value near to either V(pF ) or V(pB ) [6].
All of these methods bring temporally incoherent results.
To address this issue, we compute the weighted average
1
as weights. Ourof V(pF ) and V(pB ) using F1 and B
method dramatically suppresses artifacts caused by temporal incoherence.
3.2.1

Mathematical Discussion

The previous methods use one of V(pF ) and V(pB ) to determine the voxel value V(p). This can be considered as theminimization of the following energy function consisting of
L1 terms:

Minimizing Data Terms

Since only data terms are related to the update of V, werewrite Eq. 1 as follows:X
E data =|V(p) − V(p + Ff (p))|
p∈H

+

X

|V(p) − V(p + Fb (p))|.

(8)

p∈H

p + Ff (p) and p + Fb (p) do not often point to a grid point
in W × H × T voxels. Hence, it is necessary to estimate
V(p+Ff (p)) and V(p+Fb (p)) by interpolating the valuesof the neighboring voxels. As the result, the minimization of
Eq. 8 gives a blurry completed video.
To address this issue, the previous methods tracked theforward and backward flow fields and sampled the voxel

1

Epdata,L =F−1X|V(pu ) − V(pu+1 )|,

(9)

u=B

where we assume V(pF ) and V(pB ) as known variablesand {V(pu )|B < u < F } as the set of unknown variables.
This energy function is derived from Eq. 8 by removing
spatial relations between p and its neighboring voxels andintroducing temporal relations along the trajectory throughp. The optimization problem of Eq. 9 can be establishedindependently at each voxel position p. Fig. 3 illustrates thesolutions of the minimization of Eq. 9. All the red, green,
and blue lines minimize Eq. 9 but the red and blue lines
have a temporally sudden change in the voxel values. These
cause significant visible artifacts of temporal incoherence
but all the previous methods are intended to minimize Eq. 9.

5

where β is the user-specified parameter that controls thestrength of attenuation. We then minimize the following
energy function to update V:
X X|V(p) − V(q) − gp,q |2 ,(12)
E contrast =p∈P q∈Np

Fig. 3. Each of the red, green, and blue lines is the plot of {V(pu )|B <u < F } that minimizes Eq. 9. Only the green line minimizes Eq. 10.
The red and blue lines have a sudden change but the green line has thesmooth transition.

To address this issue, we minimize the following energyfunction consisting of not L1 but L2 terms:
2

Epdata,L

=

F
−1
X

|V(pu ) − V(pu+1 )|2 .

where Np represents {p + (1, 0, 0), p + (0, 1, 0)}. We solve
this minimization per frame using a Poisson solver [17] andit takes 10 milliseconds for a 854 × 480 frame. The numberof Jacobi iterations is 200 per frame. At each Jacobi iteration,
we do not update V(p) at p ∈ H. The result is shown in
Fig. 4-c, where artifacts are successfully removed. We apply
this contrast attenuation not always but when required.

(10)

u=B

The minimization of Eq. 10 enforces smooth transitions
between V(pF ) and V(pB ), i.e., only the green line in Fig. 3
2
can be the solution. Epdata,L can be minimized exactly by
dE data,L2= 0: this turns out to besolving the linear system pdV
equivalent to the weighted average of V(pF ) and V(pB )1
as weights.
using F1 and B
3.3

Remaining Regions

There often remain voxels whose intensity value has notbeen estimated by the process described above, because
it is impossible to estimate V(p) when the forward andbackward trajectories go out from the space-time volume V
before pF and pB are found. We complete such remaining
regions using the image completion technique [16] similarly
to [6], [8]. In the current completed video, we first findthe frame where the area of remaining regions is largest.
We then apply image completion to the found frame andinsert it back to the completed video. The voxels of theinserted frame belong to H now, and we finally minimize
Eq. 10 to update V. We repeat this process while there exist
remaining regions in V.

3.4

Contrast Attenuation

The process described above causes artifacts in some cases.
Fig. 4 shows an example. After removing the car from Fig. 4a, we see artifacts of many undesirable edges on the road in
Fig. 4-b. We explain about the situation where such an edge
tends to be produced. Let q be the voxel position spatiallyneighboring to p. Let qF 0 and qB 0 be the positions where
the forward and backward trajectories through q first go
outside the holes. Edges on the road shown in Fig. 4-b tend
to be produced when F and F 0 are very different or B and
B 0 are very different. To solve the problem, we attenuate thecontrast between p and q in such a situation. We computethe desirable contrast between them as follows:gp,q= (V(p) − V(q))× exp(−β(|F − F 0 | + |B − B 0 |)),

(11)

Fig. 4. After removing the car from (a), we see artifacts of many undesirable edges on the road in (b), which are successfully removed by ourcontrast attenuation in (c).

4

R ESULTS AND D ISCUSSION

We applied our method to 33 videos. We downloaded pairsof videos of inputs and space-time holes from the projectpages of the previous methods [4], [6], [7], [8]. All videos arefrom the DAVIS dataset [18]. The results and comparisonsare shown in the supplementary video and material. The
values of the open parameters (L and α) and the timerequired to produce each result are shown in the video ofthe supplementary material.
4.1

Computational Complexity

We used a desktop personal computer (PC) with an Intel(R)Core(TM) i7 4.0 GHz central processing unit (CPU), 32.0 GB
of memory, and an NVIDIA GeForce GTX 1080 Ti graphics
processing unit (GPU). We implemented our method so that
almost all of the computations were performed by the GPU.
The TV-L1 optical flow estimation is so suitable for GPU
implementation, which enables to develop a computationally efficient system. It took 4.1 seconds to complete the‘camel’ video, which has a resolution of 854 × 480 pixels
and a duration of 90 frames. We set L and α to 1 and 0.0.
Table 1 shows a comparison between the computation timerequired using our method and those of previous methods.
We did not measure the computation time for each previous
method; rather, we referred to the values quoted in each
paper.
The optical flow estimation is the most time-consuming
task in our algorithm. For example, it took 88% of the total
computation time to estimate the flow fields in the caseof the ‘camel’ video. The computational complexity of theTV-L1 optical flow algorithm is proportional to the numberof iterations in it. We usually use 50 or 100 iterations at
each pyramid level in the optical flow algorithm, but 1000
iterations are used to compute flow fields more carefully for6MethodTime[6]
3 hours[7]
50 minutes[8]
75 seconds
Our method
4.1 seconds
TABLE 1
Computation times required to complete the ‘camel’ video.

‘elephant’, ‘goat’, and ‘kite-surf’, because they have complex
motions and occlusions.
The computational complexity of our method is also
affected by the number of pyramid levels L. In the case ofthe ‘parkour’ video, it took 5.4 seconds for L = 1 (Fig. 10-a),
6.7 seconds for L = 2 (Fig. 10-b), and 11 seconds for L = 3(Fig. 10-c). Another open parameter α does not affect thecomputational complexity.
4.2

Comparison of Completed Videos

Our method estimates the color by minimizing E based on
the L2 data terms rather than the L1 data terms. Technically,
this is a simple extension, but it dramatically improves
the quality of the completed videos. Fig. 5 shows typicalexamples. As the L1 data terms bring temporally incoherent
solutions, the colors of the voxels change suddenly, producing visible artifacts. The top row of Fig. 5 shows frames fromthe results for the ‘parkour’ video. The wall is broken in the
result from [6] but is successfully reconstructed by our L2
data terms. The bottom row of Fig. 5 shows frames fromthe results for the ‘kite-surf’ video. There are clearly visible
seams between the blue water and the white splash in the
result by [8], but these are successfully smoothed by our L2
data terms. Such visible artifacts occur more often when the
motions in the completed holes are more dynamic. Note thatsuch artifacts have to be removed to produce satisfactory
digital contents: digital artists often have to perform manual
image editing frame by frame. The results based on our L2
data terms can significantly reduce their burden.

4.3

Interactive Video Completion

Our method is computationally efficient, which means that
we can provide an effective interactive tool. Figs. 6 and 7
show examples. The user interactively selects a frame anddraws a mask to specify the objects that they want to remove. Once the drawing operation is complete, our system
immediately interpolates between the user-drawn masks tocreate the space-time holes H and achieve video completion.
It took 1 minute in total to remove the rollerblader fromthe 35-frame video with a resolution of 854 × 480 pixels
in Fig. 6. It took 2.5 minutes in total to remove the bikefrom the 80-frame video with the same resolution in Fig. 7.
Such a user interaction has never been demonstrated in theprevious papers.
The reason why the user can remove the object fromthe video in such a short time is that the user can draw
rough masks. As shown in Figs. 6 and 7, the drawn masks
specify not only pixels of the target object but also pixels
outside it. However, our method can efficiently completessuch outside pixels by sampling corresponding pixels fromthe other frames.
Roughly drawn masks are often sufficient for video
completion; hence, we computed the interpolation with aquarter of the original resolution for efficiency. We compute this interpolation by extending the image colorization
method [19] to the spatio-temporal volume. Let M denotethe interpolated mask that is the space-time volume withdimensions W × H × T voxels. Each voxel of M has anintensity value from 0 to 1. We minimize the following
energy function to compute M:
X X
E mask =γ(p, q)|M(p) − M(q)|2p∈P q∈Np+ 0.5γ(p, pf )|M(p) − M(pf )|2+ 0.5γ(p, pb )|M(p) − M(pb )|2 ,(13)

where Np represents {p + (1, 0, 0), p + (0, 1, 0)}, pf =p + Ff (p), and pb = p + Fb (p). We use the weighting|V(p)−V(q)|2function γ(p, q) = exp(−) to preserve theσ2spatio-temporal edges of V during the interpolation. We
solve this minimization using a Poisson solver. At each
Jacobi iteration, we do not update M(p) in frames where
the user has drawn a mask. Finally, we compute the set ofvoxel positions of the holes H as

H = {p|M(p) > 0.5},(14)

and apply our method to complete the video.
4.4

Fig. 5. Comparison between the results based on the L1 data terms(left) and those based on the L2 data terms (right). The L1 data terms
produce visible artifacts, which are successfully removed by our L2 data
terms.

Manual Modification of Completed Videos

We now demonstrate that our approach based on the L2
data terms is useful for both automatic video completionand manual modification of the results. There are visible
artifacts in the results based on the L1 data term (Fig. 1a), which are clearly visible as seams in the x − time slice.
The results for the L2 data term also contain artifacts, i.e.,
the flamingo has double legs (Fig. 1-b). To remove these
artifacts, we modified frame 40 using the clone stamp toolin Adobe Photoshop. We inserted the modified frame into
the input and reapplied our algorithm. Fig. 1-c and d showframe 28 of the results. The results based on the L1 data term

7

ever, this technique often fails to produce an aestheticallypleasing result. Fig. 9 shows examples of such failures in
the remaining regions. The rail in the ‘train’ video is broken(Fig. 9-a). The synthesized textures around the fallen tree
look unnatural in the ‘rhino’ video (Fig. 9-c). We thenselected a single frame from the completed video and manually modified it using the clone stamp tool. We inserted
the modified frame into the input video, then reapplied ouralgorithm to produce better results, such as Fig. 9-b and 9d. Since our method is fast, the user can easily repeat suchmanual modifications.
Fig. 6. It took 1 minute in total to remove the rollerblader from the 35frame video with a resolution of 854 × 480 pixels. The top row shows
the user-drawn masks and the buttom row shows the frames of thecompleted video.

Fig. 9. Manual modifications on automatically completed remaining regions (a and c) produce better results (b and d).

4.6
Fig. 7. It took 2.5 minutes in total to remove the bike from the 80-frame
video with a resolution of 854 × 480 pixels. The top row shows the userdrawn masks and the buttom row shows the frames of the completed
video.

still contain artifacts that are visible as temporal disconnections in the x − time slice (Fig. 1-c). These artifacts are more
noticeable in the supplementary video. On the other hand,the double legs artifacts were successfully removed by themethod based on the L2 data term (Fig. 1-d).
Our method is also useful to modify multiple frames toremove artifacts. For example, the fence in the completed‘parkour’ video was broken by artifacts at frame 65 (Fig. 8a). To fix the fence, we manually modified frames 62, 70, 73,
and 75 and reapplied our algorithm. While the fence in the
result based on the L1 data term is still broken (Fig. 8-b),that based on the L2 data term is better fixed (Fig. 8-c).

Open Parameters

Our iterative algorithm has two open parameters: the number of pyramid levels L and α that affects weights for thedata terms in Eq. 1. The larger L and α bring temporallysmoother color transitions. Fig. 10-a shows the result basedon L = 1, where many ghosting artifacts are visible. This isbecause the images sampled by tracking Ff and Fb , whichcorrespond to V(pF ) and V(pB ), look so different. On theother hand, when we set L to 3, Ff and Fb are optimized
so that V(pF ) and V(pB ) produce similar images, which
results in more natural-looking completed video (Fig. 10-c).

Fig. 10. The effects of the number of pyramid levels. Ghosting artifacts
are visible in the result on L = 1 (a), which are removed in the result on
L = 3 (c).

4.7
Fig. 8. Our method, based on the L2 data term, better fixes the broken
fence after modification of multiple frames.

4.5

Manual Modification on Remaining Regions

Our method automatically completes the remaining regions
by applying an image completion technique (Sec. 3.3). How-

Contrast Attenuation

We applied contrast attenuation (Sec. 3.4) to ‘bmx-bumps’,‘breakdance-flare’, ‘car-shadow’, and ‘motorbike’. We set β
to 1 for the ‘breakdance-flare’ video and 10 for the othervideos. It successfully removes artifacts in some cases asshown in Fig. 4. On the other hand, since it does not taketemporal coherence into account but processes each frame
independently, flickering artifacts often appear, which are8clearly visible in the completed ‘breakdance-flare’ video.
To avoid such artifacts, we apply contrast attenuation only
to sparsely selected frames, insert them back to the input
video, and reapply our algorithm. The modified version of
the completed ‘rhino’ video was produced in such a way
that, after the manual modification (Sec. 4.5), we applied
the contrast attenuation to 0-th, 20-th, 60-th, 75-th, and 89-th
frames. We then inserted them back into the corresponding
frames of the original video and our video completion
algorithm was reapplied.
4.8

Subjective Evaluations

We subjectively evaluated the visual quality of the completed videos. This evaluation clearly indicates that our L2scheme proves to be superior to the L1 scheme of all theother previous methods. The researchers seem to believethat the L1 scheme is the best. However, this evaluation
reveals that this belief is not true and our L2 scheme isactually better.
We used 24 students (19 males and 5 females) as participants, all of whom major in computer science or engineeringand are not familiar with video completion. First, we evaluated our method (without any manual modification) and thethree methods presented in [4], [6], [8], as the experimental
results obtained using these methods were produced using
the space-time holes on the project page for [6]. We used 25
input videos; hence, there were four completed videos foreach input video, i.e., each subject evaluates 100 (= 25 × 4)
videos. We did not include ‘dance-twirl’ in this subjective
evaluation, since the completed videos had a different duration. We dilated the space-time holes for the ‘elephant’ resultof our method to avoid the influence of sand and dust.
For each input video, we asked the subject to watch boththe input and completed videos. We then asked the subject
to sort the completed videos based on quality, i.e., whether
the completed video looks natural and is free from visible
artifacts. We asked the subjects to repeat this task for all 25
input videos, which were presented in a random order. We
allowed each subject to freely change the size of the video
player and watch each video as many times as they liked.
Thus, we obtained 600 (= 24 subjects × 25 input videos)rankings. Fig. 11 shows the number of being ranked 1st foreach input video.
The videos completed by our method were evaluated as
the best, i.e., they were ranked 1st most often, for 21 of the
25 input videos. The input videos that were ranked higher
when completed using other methods were the bottom fourin Fig. 11, i.e., ‘motorbike’, ‘breakdance’, ‘rollerblade’, and‘breakdance-flare’. Our results of ‘motorbike’ and ‘breakdance’ were 2nd ranked, but they are almost comparable
to those of the other methods.
We performed manual modifications on the results thatwere unsatisfactory, and asked subjects to watch thesemodified versions. Fig. 12 shows the result. Our manualmodifications for ‘flamingo’ (Fig. 1) and ‘parkour’ (Fig. 8)
successfully improve the quality of the completed videos.
The reason for our poorer performance on the ‘elephant’,‘rhino’, and ‘train’ videos in Fig. 11 was that the qualityof our image completion on the remaining regions (Sec. 3.3)
was poor (see Fig. 9-a and 9-c). We then modified each result

Fig. 11. Results of the subjective evaluation. Each bar represents thenumber of subjects who ranked the corresponding method 1st.

by manually modifying a specific frame and reapplied ouralgorithm. These modified videos (as in Fig. 9-b and 9-d)
were ranked highest, i.e., they were ranked 1st most often.
Our result for the ‘rollerblade’ video was not as good as
those obtained using the other methods. We then asked
each participant to evaluate the interactive video completion
result, in which the rollerblader’s shadows were better
removed (Fig. 6), and it was ranked highest.

Fig. 12. Results of the subjective evaluation for the manually modified
versions. Each bar represents the number of subjects who ranked thecorresponding method 1st.

We also evaluated our method and the method presented
in [7] independent of the other three methods, as Le et al.
used different space-time holes. We used 32 input videos,
and there were two completed videos for each input video,
which we asked the subjects to rank.
The videos completed by our method were ranked
1st for 25 of the 32 videos. The remaining seven videos
were ‘blackswan’, ‘breakdance’, ‘drift-chicane’, ‘kite-walk’,‘mallard-water’, ‘motorbike’, and ‘rollerblade’. As Le et al.’s
method uses a patch-based approach, it is good at synthesizing dynamic textures, e.g., repetitive motion of clapping
hands, smoke, and water surface, which our method fails
to complete. Our method did not remove the shadows forthe ‘rollerblade’ as efficiently as Le et al.’s method. Wethen asked each participant to evaluate the interactive video
completion result again (Fig. 6), and it was ranked highest.

9

5

C ONCLUSION AND F UTURE W ORK

We have proposed a practical video completion method.
Our method is computationally efficient that allows theuser to perform video completion by interactively drawing
masks. Our method minimizes the energy function basedon the L2 data terms to estimate temporally coherent colortransitions, which not only produces natural-looking results
but also is useful for manual modifications on single ormultiple selected frames. The subjective evaluation results
also illustrate very well that our method has superiority
over previous video completion approaches.
However, there still exist lots of avenues for making our
method a production-ready tool for video completion.
1)

2)

3)

4)

Since the success of video completion relies on thequality of masks to specify space-time holes, we arealso interested in extraction of good masks from the
input video like [20]. To address these issues, we areinterested in exploiting more semantic information,e.g., that would be provided by deep learning based
approaches for image and video understanding.
Theoretically, our method works on high res videos,such as 4K or 8K, but it often becomes inefficientdue to out of memory. Our method consumes a large
amount of memory, especially to keep the forward
and backward flow fields at the same time. For
example, we require 3.2 GB of memory to keep themfor a 100-frame video at 2K resolution. This will
be problematic when completing a longer, higherresolutional video. We want to investigate the way
to use memory more efficiently.
We want to fix our failure cases of repetitive motions, fluid motions, etc. The patch-based approachis good at synthesizing such dynamic textures, but
the methods based on it are usually computationallyexpensive. We want to explore an efficient patchbased approach that enables the user to interactive
edits of completed videos.
The current contrast attenuation is not easy-to-use
for two reasons: 1) it does not take temporal coherence into account, which often causes flickering
artifacts; 2) as the result, this is currently an optional
tool, i.e., the user has to decide whether it should beapplied or not. We want to improve the algorithm
and propose an easier-to-use tool.

ACKNOWLEDGEMENTS
We would like to thank the anonymous reviewers for theirinsightful and constructive comments. Many thanks also go
to So Hashimoto, and Ayumi Kimura for discussions andencouragements. This work was partially supported by JSPS
KAKENHI Grant Numbers JP15H05924 and JP18K11352.

R EFERENCES[1][2]

Y. Wexler, E. Shechtman, and M. Irani, “Space-time completion ofvideo,” IEEE TPAMI, vol. 29, no. 3, 2007.
M. Granados, J. Tompkin, K. Kim, O. Grau, J. Kautz, andC. Theobalt, “How not to be seen-object removal from videos of
crowded scenes,” Computer Graph. Forum, vol. 31, no. 2pt1, pp.
219–228, 2012.

[3]

M. Granados, K. I. Kim, J. Tompkin, J. Kautz, and C. Theobalt,“Background inpainting for videos with dynamic objects and afree-moving camera,” in Proc. ECCV 2012, 2012, pp. 682–695.
[4] A. Newson, A. Almansa, M. Fradet, Y. Gousseau, and P. Pérez,“Video inpainting of complex scenes,” SIAM Journal on Imaging
Sciences, vol. 7, no. 4, 2014.
[5] M. Roxas, T. Shiratori, and K. Ikeuchi, “Video completion via
spatio-temporally consistent motion inpainting,” IPSJ Transactions
on Computer Vision and Applications, vol. 6, pp. 98–102, 2014.
[6] J.-B. Huang, S. B. Kang, N. Ahuja, and J. Kopf, “Temporally
coherent completion of dynamic video,” in Proc. SIGGRAPH Asia
2016, 2016, pp. 196:1–196:11.
[7] T. T. Le, A. Almansa, Y. Gousseau, and S. Masnou, “Motionconsistent video inpainting,” in Proc. IEEE ICIP 2017, 2017, pp.
2094–2098.
[8] A. Bokov and D. Vatolin, “100+ times faster video completionby optical-flow-guided variational refinement,” in Proc. IEEE ICIP
2018, 2018, pp. 2122–2126.
[9] R. Murase, Y. Zhang, and T. Okatani, “Video-rate video inpainting,” in Proc. IEEE WACV 2019, 2019, pp. 1553–1561.
[10] T. Shiratori, Y. Matsushita, S. B. Kang, and X. Tang, “Video
completion by motion field transfer,” in Proc. CVPR 2006, 2006,
pp. 411–418.
[11] M. Strobel, J. Diebold, and D. Cremers, “Flow and color inpainting
for video completion,” in Proc. CVPR 2014, 2014, pp. 293–304.
[12] T. Kroeger, R. Timofte, D. Dai, and L. Van Gool, “Fast Optical Flowusing Dense Inverse Search,” in Proc. ECCV 2016, 2016.
[13] A. Nandoriya, M. Elgharib, C. Kim, M. Hefeeda, and W. Matusik,“Video reflection removal through spatio-temporal optimization,”in IEEE ICCV, 2017, pp. 2411–2419.
[14] R. Sadek, G. Facciolo, P. Arias, and V. Caselles, “A variationalmodel for gradient-based video editing,” International Journal ofComputer Vision, vol. 103, pp. 127–162, 2013.
[15] C. Zach, T. Pock, and H. Bischof, “A duality based approach forrealtime tv-l1 optical flow,” in Proc. DAGM, 2007, pp. 214–223.
[16] C. Barnes, E. Shechtman, A. Finkelstein, and D. B. Goldman,“Patchmatch: A randomized correspondence algorithm for structural image editing,” in Proc. SIGGRAPH 2009, 2009.
[17] P. Pérez, M. Gangnet, and A. Blake, “Poisson image editing,” inProc. SIGGRAPH 2003, 2003, pp. 313–318.
[18] F. Perazzi, J. Pont-Tuset, B. McWilliams, L. Van Gool, M. Gross,and A. Sorkine-Hornung, “A benchmark dataset and evaluation
methodology for video object segmentation,” in Proc. CVPR 2016,2016.
[19] A. Levin, D. Lischinski, and Y. Weiss, “Colorization using optimization,” in Proc. SIGGRAPH 2004, 2004, pp. 689–694.
[20] T. T. Le, A. Almansa, Y. Gousseau, and S. Masnou, “Removing
objects from videos with a few strokes,” in Proc. SIGGRAPH Asia
2018 Technical Briefs, 2018, pp. 22:1–22:4.