I want you to code this by following all criteria and formulas. I have previously implemented this  - '''
\begin{figure}
  \centering
    \vspace{-1em}
  \includegraphics[width=\linewidth]{figs/preprocessing_overview.pdf}
  \vspace{-1.5em}
  \caption{Our preprocessing pipeline annotates both the source repository and the target video with phonemes and registers a $254$-parameter 3D head model to each frame of each video.
%    Overview for the preprocessing pipeline.  We preprocess both the
%    repository and the target video with phoneme alignment and 3D head
%    model registration.  This gives us the phoneme label, start and
%    end time for every phoneme in the videos, as well as $254$ face
%    parameters at each frame.
  }
    \vspace{-1em}
  \label{fig:preprocessing_overview}
\end{figure}

\begin{figure*}
  \vspace{-1em}
  \centering
  \includegraphics[width=\textwidth]{figs/synthesis_overview.pdf}
  \vspace{-2em}
  \caption{Our synthesis pipeline adapts the pipeline of
    Fried~\etal~\shortcite{Fried_2019} by introducing a fast phoneme
    search and stitching step (yellow), and a self-supervised neural retargeting step (yellow). 
    % \maneesh{Only ``f'' should be highlighted in word ``fog''. Might be clearer  to use a ``v'' word rather than an ``f'' word to stress the fact that we are considering visemes, not just phonemes.}\david{I'm trying to show overlapped subsequences here: fog for F-AH-K and ox for AH-K-S. But maybe there's no need to delve that deep in details here?} \maneesh{Showing the overlap makes the figure way too confusing. We should go back to what we had earlier.}
    The input to our pipeline is a target video (green) and an edit (green) -- here
    changing the word ``spider'' to ``fox''.
    Our fast phoneme search
    finds phonemes in the repository that visually match the desired edit 
    -- here the ``v'' in volume and the ``ox''
    in box.  We then stitch together the corresponding facial
    expression parameters of the 3D head model for the source
    repository actor, and use a novel neural retargeting model to
    translate those parameters into those for the target actor.
    Next, we expand the retargeted expression parameters to the full
    face parameters (e.g. pose, illumination) for the target actor.
    Finally we render photorealistic frames from the parameters using
    a neural rendering approach that first composites the lower part
    of the face rendered from the 3D head model, with background
    pixels from the original target video and then uses a generative
    adversarial network (GAN) to map the composites to photorealistic
    frames.  }
  \label{fig:synthesis_overview}
\end{figure*}

\section{Method}
\label{sec:method}

Given a short talking-head video of a {\em target actor} (often 2-3
minutes in length), and an edit of the video transcript, our system
synthesizes new video of the target actor matching the edit. An
edit is specified as a replacement of one continuous sequence of words
in the original transcript with a new sequence of words.  Since a
short target actor video is unlikely to contain all the lip motions
necessary to convincingly synthesize the sequence of phonemes in the
edit, we leverage a large {\em repository} of video from a different,
{\em source actor}.
%that contains the most common phoneme combinations
%(coarticulations) in English.
%
%Specifically, we pre-capture an hour of
%a source actor speaking the TIMIT corpus\,\cite{garofolo1993timit} and
%retarget the lip motions of the source actor to the target actor
%during synthesis.
Specifically, we pre-capture an hour of a source actor speaking the
TIMIT corpus\,\cite{garofolo1993timit} which includes the most common
phoneme combinations (coarticulations) in English and we retarget
their lip motions to the target actor during synthesis.


Our approach for quickly synthesizing the edited result is based on
the approach of Fried et al.\,\shortcite{Fried_2019} but involves
several critical modifications.  As in Fried et al.,
%\ohad{wording a bit confusing, since Fried19's repository is not the
%same as ours (different person)},
our {\em preprocessing pipeline} (\Cref{fig:preprocessing_overview})
annotates both the repository and target videos with phonemes and
registers a parametric 3D head model to the face in each frame of each
video. Our {\em synthesis pipeline} (\Cref{fig:synthesis_overview})
provides a new, fast phoneme search algorithm that finds subsequences
of phonemes in the source video that match the desired edit. It then
stitches together the corresponding parameters of the 3D head model
for the source actor across subsequence boundaries to smooth the lip
motions.  We introduce a new self-supervised neural
retargeting step that adapts the parameters representing the lip
motion of the source actor to those of the target actor and blend the
resulting parameters into the target video.  Finally we render
photorealistic frames from the parameters using neural rendering\,\cite{tewari2020state}.
%\maneesh{cut next sentence for space?}\david{No objections.}
%The speed of our synthesis
%pipeline enables iterative editing and our tool provides additional
%controls for refining lip motions, inserting non-verbal mouth gestures
%and manipulating speaking style. 

We briefly summarize how we adapt each step in Fried et al.'s
pipelines to our problem in Sections~\ref{sec:preprocessing_overview}
and~\ref{sec:synthesis_overview}. We then present the details of our
new algorithms; fast phoneme search and stitching in \Cref{sec:search} and neural retargeting algorithm in
\Cref{sec:retargeting}.  In~\Cref{sec:interaction}, we
describe the iterative refinement and performance controls enabled by
our approach.

%% \maneesh{This high-level summary of the approach might be useful for
%%   the intro or abstract.}  We achieve this by representing the face
%% shape at each frame of the video with parameters for a 3D head model,
%% then synthesizing a time series of parameters that animates the face
%% to speak the new words, and finally rendering the parameters into
%% photorealistic frames of a talking head to replace the frames that
%% speak the original words.

\subsection{Preprocessing Pipeline}\label{sec:preprocessing_overview}
Our preprocessing pipeline annotates each frame of the repository and
the target videos in two main steps, (1) phoneme alignment and (2)
registration of a parametric 3D head model. These resulting phoneme
and face parameter annotations are used by our synthesis pipeline to
establish correspondences between the target video and source
repository.  Note that the repository is only annotated {\em once} and
the resulting {\em annotated repository} is then bundled as part of the
system. In contrast, the target video must be annotated each time a
new target video is given as input.

\paragraph{Phoneme Alignment}
The phoneme alignment step takes as input a video (repository or
target) paired with its text transcript, and computes the identity and
timing of the phonemes in the video.  Specifically, we use
P2FA\,\cite{yuan2008p2fa,rubin2013p2fa} to convert the transcript into
phonemes and align them to the audio speech track of the video.  This
produces an ordered sequence $V=(v_1, \ldots, v_n)$ of phonemes, where
each phoneme $v_i$ contains its name, start time and end time.
% We manually fix gross misalignments if they occur (about 10 instances in
%an hour-long video). \maneesh{Delete point about misalignments for space.}
If the transcript is not available, we can
obtain one using a transcription service such as Google Cloud
Speech-to-Text\,\shortcite{googlecloudstt}, or
rev.com\,\shortcite{rev}.

\paragraph{3D Head Model Registration}
We fit a parametric head
model\,\cite{blanz1999facemodel,ThiesZSTN2016a} to each frame of
video using a monocular head
tracker\,\cite{garrido2016reconstruction}.  At every frame, the fitted
model includes 80 parameters for 3D facial geometry, 80 for facial
reflectance, 3 for head pose, 27 for scene illumination and 64 for
face and lip expressions.  In the fitting procedure we hold the facial
geometry and reflectance parameters constant across all the frames of
the same actor, but we allow the pose, illumination and expression to
vary across time.

\subsection{Synthesis Pipeline}
\label{sec:synthesis_overview}

Our synthesis technique is based on matching phonemes in the edit
to phonemes in the repository. Therefore, we first convert the input
text of the edit from words into a sequence of phonemes $W=(w_1,
\ldots, w_m)$, where each phoneme contains its name, start time and
end time.
% \maneesh{I shorted prev. 2 sentences. Orig. longer version is in comments.}
%Our synthesis pipeline takes a target video and an edit as input, and
%generates a video of the target actor that matches the edit.  Since
%our synthesis technique is based on matching phonemes in the edit to
%phonemes in the repository, we start by converting the text of the
%edit into a sequence of phonemes $W=(w_1, \ldots, w_m)$, where each
%phoneme contains its name, start time and end time.
%
Specifically, we convert the edit into audio using either
%\maneesh{either a library of voice recordings of the target actor},
text-to-speech voice
synthesis\,\cite{wavenet2016,googlecloudtts} or voice cloning techniques\,\cite{kumar2019lyrebird,lyrebird}, 
and then apply P2FA\,\cite{yuan2008p2fa,rubin2013p2fa} to
time-align the resulting speech to the phonemes of the edit.
%
Note that our synthesis algorithm only uses the timing of the phonemes
and does not use any other aspect of the synthesized speech audio
signal.
%\maneesh{Do we need prev sentence?}
%
%% Specifically, we use either
%% text-to-speech\,\cite{wavenet2016,googlecloudtts} or voice
%% cloning\,\cite{jia2018sv2tts,jin2017voco,kumar2019lyrebird} to convert
%% the edit into audio and then apply
%% P2FA\,\cite{yuan2008p2fa,rubin2013p2fa} to time-align the resulting
%% speech to the phonemes of the edit.
%
% If the user later captures a recording of the target actor saying the
% new content, they can re-run our fast synthesis pipeline with the new
% timings obtained from the real recording. \maneesh{May want to update
%   last line depending on how we talk about real-voice results.}
% \david{If the user is the target actor, they can record speaking the
%   new content in real time and use our fast synthesis pipeline with
%   timings from the real recording.} \maneesh{Previous sentence is the
%   more likely scenario and should be combined with the sentence about
%   recording the actor later.}
% \maneesh{Can next sentence (not highlighted) replace sentence starting at ... If the user later captures ...}
If the user has access to the audio of the target actor saying the new
content (either from a prerecorded library of the actor's speech or
recorded by the actor in real-time during editing) they can run
our fast synthesis pipeline with the timings obtained from the
real-voice recordings. 



\paragraph{Fast Phoneme Search and Stitching}
The fast phoneme search and stitching step is designed to quickly find the best
subsequences of phonemes in the repository and then stitch together the corresponding
expression parameters of the source actor 3D head model, in order to produce the
the edit $W$ we wish to synthesize.
% \maneesh{We need to say more about the stitching as we did in the previous version of the paper -- from what is written here it is unclear what stitching does. Need to say it ... stitches together the corresponding expression parameters of the source actor 3D head model to produce the edit $W$ we wish to synthesize....
  % while conforming to the phoneme timing specified in the edit $W$ we wish to synthesize.}
Our new algorithm 
operates three orders of magnitude faster than
Fried~\etal~\shortcite{Fried_2019} and finds the best repository
subsequences in seconds rather than hours. We present this fast
algorithm in detail in~\Cref{sec:search}.
%\maneesh{May want to elevate into intro that we are 1000x faster than Fried19.}
%The result
%of this step is a set of phoneme subsequences from the repository that
%match the edit. \maneesh{Perhaps kill final sentence for space.}
%This step turns the edit into phoneme subsequences found in the repository.

% \paragraph{Subsequence Stitching} \david{Needs to be rewritten. Probably should not be its own subsection.
% It should briefly talk about the forced MBP closure, blending
% overlapping intervals and Gaussian smoothing across each boundary.}
% \maneesh{I wonder if we should just combine this step with fast phoneme search in our pipeline and talk about what we do new at the end of section 3.3. Will require changing Fig 3 a bit to remove Subsequence stitching as a step. Could change name of Fast Phoneme Search to Fast Phoneme Search and Stitching}
% The stitching step takes the subsequences of phonemes found in the
% repository, looks up the corresponding expression parameters of the 3D
% head model and combines them together into a continuous sequence that
% conforms to the phoneme timing specified in the edit.  More
% specifically, we linearly retime the expression parameters
% corresponding to each phoneme in each repository subsequence to match
% the phoneme duration specified in the edit.  We then connect adjacent
% subsequences by smoothing over a window of 4 frames around the
% subsequence boundaries, to obtain a single temporally coherent
% sequence of source actor expression parameters corresponding to the
% edit.
%\maneesh{We are switching between calling them ``head parameters'' and ``face parameters''. Need to make consistent.}

\paragraph{Neural Retargeting}
The retargeting step converts a sequence of expression parameters for the source actor into those for
the target actor.
We introduce a
learned retargeting model, trained in a self-supervised manner from
corresponding pairs of 
repository and target video sequences and transforms the expression
parameters as detailed in~\Cref{sec:retargeting}.
%
%% Our retargeting method needs only a few minutes of video from target
%% actor and significantly lowers the data requirement on the target
%% video to about 2--3 minutes for high-quality results.  \ohad{we can
%%   add: "compared to, e.g., the method of Fried~et~al. which requires
%%   ~1.5 hours"}.
%
The result is a sequence of target actor
face expression parameters corresponding to the edit.


\paragraph{Expansion to Full Parameters}
Next, we combine the synthesized target actor expression parameters
with geometry, reflectance, pose and illumination parameters from the
input target video to 
produce a sequence of full face parameters for the target
actor corresponding to the edit.
%Next, we augment the newly synthesized target actor expression
%parameters with head pose and illumination parameters from the target
%video, to produce a sequence of full face parameters for the target
%actor.
Specifically, we take an interval of frames around the edit location
in the target video, retime it to account for the duration of the
edit, and use the geometry, reflectance, pose and illumination
parameters from the retimed interval.
%
%% \maneesh{I edited the
%%   next sentence, but I'm not sure I really understand what we are
%%   doing. I'm also not sure we need to include it as it is a detail.}
%% To ensure that the synthesized expression parameters fit seamlessly
%% back in the target video, we smooth the expression parameters at both
%% ends of the edit boundary with respect to the original expression
%% parameters in the target video.

\paragraph{Neural Rendering}
The neural rendering step takes the sequence of full face
parameters for the target actor and first generates a composite image
in which the lower face region is a rendering of the 3D head
model, while the upper part of the head and the surrounding background
are from the original target video, but retimed to match the length of
the edit. It then uses a GAN trained on the target video to
complete the image-to-image translation from composite image to
photorealistic frame.

%% The neural rendering step produces the final frames corresponding
%% to the edit by synthesizing each frame from the full face
%% parameters for the target actor.  We produce an intermediate
%% composite image by masking out the lower face region in the
%% original frame, replacing it with the synthetic render of the lower
%% face of the 3D head from the new face parameters, and finally use a
%% GAN (based on Fried~\etal~\shortcite{Fried_2019}) trained on the
%% target video to complete the image-to-image translation from
%% composite image to photorealistic frame.

\input{method-search}

\input{method-retargeting}

\input{method-interaction}

\input{method-runtime.tex}

%%  LocalWords:  photorealistic retargeting retimed coarticulations
%%  LocalWords:  viseme coarticulation retargeted datasets TIMIT PCA
%%  LocalWords:  dataset renderer Preprocessing misalignments Garrido
%%  LocalWords:  crowdsourcing reflectance blendshapes et retarget al
%%  LocalWords:  preprocessing visemes subsequence Ohad RNN relu pre
%%  LocalWords:  regularizer Hyperparameters minibatch Tensorflow len
%%  LocalWords:  memoization bigram unigram bigrams runtime retime
%%  LocalWords:  retiming subsequences lbl GAN iteratively
%%  LocalWords:  levenshtein googlecloudstt


\subsection{User Controls} \label{sec:interaction}
%As we will show in Section~\ref{sec:runtime} our synthesis pipeline
%can generate video corresponding to a typical edit in about
%40 seconds.
This speed of our synthesis pipeline opens
the door to interactive user controls for iteratively refining the
edit and further manipulating the the facial performance.

%% \begin{figure}
%% \centering
%% \includegraphics[width=\linewidth]{figs/ui.pdf}
%% \caption{The user interface of our tool.}
%% \label{fig:ui}
%% \end{figure}

\paragraph{Refinement Control: Smoothing jumpy transitions}
Our synthesis pipeline stitches together different subsequences of
expression parameters from the source repository by smoothing over a
window of 4 frames around the transition boundary
(Section~\ref{sec:search} Fast Phoneme Search and Stitching).  At
times however, some transitions may still appears jumpy even after
this smoothing.
%\maneesh{the smoothing introduced by} retargeting model inference.
%\maneesh{Unclear why we are mentioning retargeting inference when we
%  first talked about stitching.  I added something about smoothing
%  introduced, but I don't really understand why retargeting would
%  introduce smoothing.}
We allow the user to inspect the result and
further refine it by manually specifying the interpolation radius (in
number of frames) at user-specified transition boundaries to better smooth out visibly
jumpy transitions.

\paragraph{Refinement Control: Adjusting mouth closure}
%\david{Need to rewrite this paragraph. Instead of mentioning forced
%  MBP closure in previous sections, an alternative is to introduce it
%  here. Since we force-blend MBP shapes automatically already, this
%  control is really for adjusting the strength of the blend.}
%\maneesh{I don't think we need to be so detailed about this and can keep it mostly as is. We should discuss.}
%\david{Most content here are now in \Cref{sec:search} when introducing forced MBP mouth closures.}
% \maneesh{Updated section... May want to call it ``Adjusting mouth closure'' I'm not sure. Old version of paragraph is in comments.}
As noted in Section~\ref{sec:search} mouth closure on \textbackslash
m, \textbackslash b and \textbackslash p phonemes is crucial for the
mouth motions to appear realistic. Thus our stitching procedure
automatically inserts 2 closed mouth frames at the beginnings of these
three phonemes to ensure the mouth closes correctly for them. We
further allow users refine any synthesized result by
extending (or reducing) the length of the inserted closed mouth
frames.
%
%% Our automated pipeline sometimes fails to fully close the mouth of the
%% target actor properly, such as at the beginning of \textbackslash m,
%% \textbackslash b, \textbackslash p phonemes, due to either inaccurate
%% phoneme alignment in the repository or smoothing from subsequence
%% stitching.  We allow the user to inspect the result and further refine
%% it by blending in a manually-annotated closed-mouth expression from
%% the repository at the specified location with different effect radius
%% before the retargeting.  Note that we manually annotate the closed
%% mouth expressions in the repository once during repository
%% preprocessing, and later automatically use the one closest to the
%% current parameter values at the specified location when the user
%% inserts it.


\paragraph{Performance Control: Inserting mouth gestures}
%\david{recent rewrite}
Users can also insert non-verbal mouth gestures (e.g. a smile)
into an edit. To enable such performance control we manually annotate
mouth gestures including {\em rest, closed-mouth smile, regular teeth-showing
smile, big open-mouth smile, sad, scream, mouth gesturing left} and
{\em mouth gesturing right,} in the repository video.  These segments can
then be retrieved by our fast phoneme search just like any other
phoneme annotation.
%\maneesh{I think showing some more of these in our results would help
%  -- the mouth left and right gestures are a bit uncommon -- it would
%  be great to think of examples that make sure of scream, and sad.}
%\maneesh{Make sure all expressions are shown in some example in the supplemental materials and show generalization -- that is input target video did not contain a gesture but we can still synthesize it.}

Since the annotations are on the repository, this manual annotation only
needs to be done once during repository preprocessing.  Note however, that 
users do not label the target video with these mouth gestures and our
retargeting network is never explicitly trained with corresponding
pairs of mouth gesture frames between the repository and target
videos. Nevertheless, we have found that our retargeting network is
able to generalize to unseen expressions and produce good quality
expression parameters for the target actor.
%\maneesh{Would be good to show more results of just the gestures generalizing to new target actors.}

With these annotations, the user can add special {\em mouth gesture
  directives} like [smile] anywhere in their edit of the
transcript, and our tool constructs a ``generalized phoneme'' edit
sequence $W$ that contains phonemes and such directives.  Any mouth
gesture that appears in $W$ is given a default duration of $0.5$
seconds that the user can override with an explicit duration
e.g. [smile:1.5s].  We employ a special substitution cost in
$\cmatch$ described in \Cref{sec:search} for ``gesture phonemes'' that
is set to infinity for a non-match to ensure that we retrieve the
correct ``phoneme'' match for the gesture.  When there are multiple
candidates, $\cmatch$ takes duration into account and picks the
gesture with duration closest to the query.  The rest of the editing
pipeline (\Cref{sec:synthesis_overview}) is otherwise unmodified.
% \ohad{there are way too many ``quotation marks'' in this paragraph}

\paragraph{Performance Control: Adjusting speaking style}
%\david{recent rewrite}
Our tool allows the user to select a different speaking style for the
synthesized result by using a version of the repository with the
desired style. In addition to the default repository which captures a
``neutral'' speaking style, we have recorded an ``energetic''
repository of our source actor with more pronounced mouth movements,
and a ``mumble'' repository with significantly less mouth movements. Figure~\ref{fig:sessions} (third row) shows
frames from these alternative repositories.


Importantly, we do not have to retrain our neural retargeting model
(\Cref{sec:retargeting}) for each additional style repository.  We
train this retargeting model once using only the default neutral
repository.
%
We have found that our default retargeting model can extrapolate to
retarget subsequences of source actor face parameters retrieved from
other speaking style repositories of the same actor.  Moreover, the
other repository videos can be captured at different times, with
different background and the source actor can even be wearing
different clothes or have a different hairstyle. 
%\maneesh{probably should say this point earlier or reinforce in limitations section..}
Thus, our tool generates videos with different speaking styles by
using one of the alternative style repositories in the fast phoneme
search step, but leaves the remainder of the synthesis pipeline
unchanged.
%\maneesh{Make sure supplemental materials contains examples of each style we say we can do. Since a reviewer asked about this one I wonder if we can find an even more exaggerated example -- perhaps on David or Ayush.}
%\maneesh{Again, would be good to show this in some more detail in our results. In fact I think a reviewer asked bout this one specifically, so adding more results on this would be very helpful.}

%% retarget subsequence retrieved from
%% different versions of the repository with the same source actor but
%% speaking with different styles.


%% Recall that our neural retargeting model maps the source actor expression
%% parameters to target actor parameters (\Cref{sec:retargeting}).


%% When the user chooses a different speaking style, we
%% still apply the neutral retargeting model as we have found that it can extrapolate
%% to subsequences retrieved from
%% different versions of the repository with the same source actor

%% We have found that the same retargeting model trained on the
%% natural style repository can extrapolate to subsequence retrieved from
%% different versions of the repository with the same source actor but
%% speaking with different styles.

%% Moreover, the other repository videos
%% can be captured at different times, with different background and the
%% source actor can even be wearing different clothes or have a different
%% hairstyle.

%% In particular, we have recorded an
%% ``energetic'' repository of our source actor with more pronounced
%% mouth movements, and a ``mumble'' repository with significantly less
%% mouth movements.


%% Our system can then generate videos with a different
%% speaking style by using one of the alternative repositories. Note that our
%% neural retageting pipeline 
%% The rest of the synthesis pipeline
%% described in \Cref{sec:synthesis_overview} works unchanged.

%% \maneesh{May need to make a bigger deal of this. Mention this in
%%   limitations -- recording source actor takes time, but can likley do
%%   it in more than one setting and sitting.} 

% LocalWords:  iteratively subsequences Subsequence subsequence
% LocalWords:  retargeting preprocessing retarget


\subsection{Neural Retargeting}\label{sec:retargeting}
Given a stitched-together sequence of face expression parameters for
the source actor in the repository, the goal of retargeting is to
generate a matching sequence of expression parameters for the target actor.
%\ohad{should we add a sentence explaining why these two sets of
%  parameters are different in the first place?}
We have developed a self-supervised neural network model for retargeting
and in Section~\ref{sec:eval_algo_data} we show that
using a neural network for retargeting produces
%%with self-supervision based on
%%corresponding pairs repository and target video 
%%visemes
%%produces
higher-quality results than baseline
methods such as directly copying source actor expression parameters to
the target actor, or applying a linear retargeting model.

%as we will show in \Cref{sec:eval_retarget}.  \maneesh{May want to
%  move the comparison to end of this section.}

\begin{figure}
\centering
\includegraphics[width=\linewidth]{figs/correspondence.pdf}
\caption{To automatically build training data for our neural
  retargeting model, we consider a sequence of phonemes $S$ (red) in
  the repository and find up to two best matches $T^A$ and $T^B$ (red)
  in the target video.
%
%
%  Phonemes in the video are represented as cells. For a
%  sequence $S$ (red) in the repository, we find up to two best matches
  %  $T^A$ and $T^B$ (red) in the target video.
  We then find
  matches for the next repository sequence (green) starting at
  the last phoneme of the previous sequence.  The overlap allows
  us to capture the phoneme transition out of the final phoneme in the red subsequence.}
\label{fig:build_correspondence}
\end{figure}

\paragraph{Self-supervised training data}
%\david{recent rewrite}
To train our retargeting network we require sequences of expression
parameters for the source and target actor that correspond to one
another with respect to their mouth motions.  Assuming that uttering
the same sequence of visemes will produce similar mouth motions, we
automatically construct corresponding pairs of training data by
finding the longest matching sequences of phonemes between the source
repository video and the target video, as follows.

Since we apply our retargeting model to a stitched-together
subsequences of phonemes that can come from anywhere in the source
repository, we would like the training sequences to cover as much of
the repository as possible.
Therefore, we start from the first phoneme $s_1$ in the
repository, and find the longest sequence $S=(s_1,\ldots,s_k)$ for
which there is at least one corresponding sequence
$T=(t_1,\ldots,t_k)$ in the target video where $t_i$ and $s_i$ belongs
to the same viseme group (i.e. phonemes that require the same lip expressions
are in the same viseme group).
We take up to two best matches in the
target video with respect to $\cmatch$ score defined in
\Cref{sec:search}, and call them $T^A=(t^A_1,\ldots,t^A_k)$ and
$T^B=(t^B_1,\ldots,t^B_k)$.  We add the pairs $(S,T^A)$ and $(S,T^B)$
to the set of phoneme sequences in correspondence, and continue the
scan through the source repository at $v_k$, until we finish scanning
through the entire repository for subsequence matches
(\Cref{fig:build_correspondence}).  To quickly find the best $T^A$ and
$T^B$ sequences in the target video, we apply fast search techniques discussed
in \Cref{sec:search}.
%
Finally, to convert each resulting phoneme sequence pair into a parameter
sequence pair, we linearly retime the target video phoneme interval to
the corresponding repository interval and similarly interpolate the
% corresponding
expression parameters.
The retargeting model is trained once for each new target video.
%\maneesh{Are we now doing this in a context aware way? Also have we
%  tried using more than the top two matches? I wonder if considering
%  more matches would help us get the mouth to open when it should.}
%\david{
%  Our neural retargeting step is unchanged from January submission.
%}
%\maneesh{ok, but in the paper here we say we use the score defined in section 3.3 and that score is described in a context-aware way so the assumption  would be that we would be doing this here in a context aware way. My sense is that we should try the context aware approach if we are not doing it that way now.}

%% Note that because of coarticulation effects, the phonemes at the start
%% and end of a sequence may not produce similar mouth motions in the
%% corresponding repository and target videos. We therefor discard first
%% half of the frames in the first phoneme interval and last half in the
%% last interval, effectively discarding all single-phoneme sequence
%% pairs. \maneesh{This is a detail we might consider removing later.}

\begin{figure}
\centering
\includegraphics[width=\linewidth]{figs/network.pdf}
\caption{The retargeting network with the unrolled recurrent unit $F$, which looks two frames back at each time step and uses the previous two outputs as its state.
The diagram shows how the RNN processes the input of $T$ frames of source actor parameters $(s_1, s_2,\ldots,s_T)$ and produces the prediction for $T$ frames of target actor parameters $(t_1, t_2,\ldots,t_T)$.}
\label{fig:retargeting_network}
\end{figure}

\paragraph{Neural Network Architecture}
%\david{recent rewrite}
We employ a recurrent neural network (RNN) manually unrolled for $T$
time-steps to encode the temporal dynamics of the facial expressions
and regress from source parameters to target parameters
(\Cref{fig:retargeting_network}).  The resulting network takes as
input $T$ frames of $64$ expression parameters for the source actor,
and outputs $T$ frames of $64$ parameters for the target actor.  At
the core of the network is the recurrent unit that is made up of $3$
fully connected layers of $1024$ nodes with relu activation. The
inputs to the recurrent unit are $64$ expression parameters of the
current time-step, as well as the parameters and outputs of the
recurrent unit for the previous $H$
%\maneesh{I am a little lost. Is H shown in the figure at all? Feels
%like it should be.} \david{The figure only shows the case for $H=2$
%which is what we used.}
time-steps.  To facilitate
learning of deviations from the identity transformation, the output
layer of the recurrent unit with $64$ nodes and no activation produces
the residual values that are added to the input source parameters
element-wise to obtain the prediction for the target parameters for
the current time-step. We zero-pad the unavailable inputs at the
first $H$ time-steps. We empirically found that setting $H=2$ and
$T=7$ produced high-quality retargeting results.

\paragraph{Loss function}
%\david{recent rewrite}
Our loss function is a linear combination of a data term and a
temporal regularizer with regularization weight $\lambda$:
$$\mathcal{L} = \frac{1}{T}\sum_{i=1}^T \|F(s_i)-t_i\|_1 +
\lambda\|F^{(2)}(s_i)\|_2$$
where $s_i,t_i$ are $64$-dimensional vectors representing the $i$th time-step of the source and target parameters
respectively,
$F(s_i)$ is a $64$-dimensional vector of the predicted target actor parameters and
$F^{(2)}(s_i)$ is a $64$-dimensional vector that is the second temporal difference
vector, or acceleration, of the predicted values.
Empirically
we found that using an $L_1$ norm for the data term significantly outperforms
$L_2$ by generating more expressive motions and better preserving mouth closures.
The temporal regularization term is needed to make the network
predict temporally stable parameters.

\paragraph{Hyperparameters and training}
Since the network takes a fixed-size input of $T$ frames, we run a
sliding window on each matching parameter sequences to obtain the
training examples.  Experimentally we set the temporal window $T=7$
frames.  For training we set $\lambda=10$, and dropout rate at 25\%,
50\% and 25\% for the three layers in the recurrent unit,
respectively.  To train the network we use stochastic gradient descent
with the Adam solver\,\cite{Kingma2014Adam} and set an initial learning
rate of $0.0002$ with an exponential decay rate of $0.5$.  We employ
gradient clipping\,\cite{pascanu2013clipping} to avoid exploding
gradients.  We train the network with minibatch size $100$ and
training typically converges within $100$ epochs.

\paragraph{Inference}
At inference time, we convert a sequence of source actor expression
parameters into target actor parameters.  Since our retargeting model
accepts fixed-size $T$ frames of input and produces $T$ frames of
output, we run a sliding window of length $T$ over the new sequence of
source actor expression parameters at inference time. Each frame is
covered by exactly $T$ such sliding windows.  In order to obtain a
more temporally stable output, at each frame we average the $T$
outputs produced by those $T$ sliding windows as the final output of
the frame.  The result is a synthesized sequence of target actor
expression parameters that animate the face to speak the new content
of the edit with the desired timing.
We then proceed to expand these expression parameters into parameters
for the whole head and use neural rendering to generate the video frames
(\Cref{sec:synthesis_overview}).

\vspace{0.5em}
Training our retargeting model typically requires 2--3 minutes of
target actor video speaking arbitrary speech to produce high-quality
synthesis results. Retargeting allows our tool to leverage the large
repository of controlled source actor video (speech consists of TIMIT
sentences) to generate the target actor lip motions and opens our tool
to many practical applications where large amounts of controlled
target actor video are not available.

% LocalWords:  retargeting na ve eval retarget uncanniness viseme RNN
% LocalWords:  visemes subsequence bigram retime coarticulation Ohad
% LocalWords:  relu regularizer th Hyperparameters minibatch TIMIT NN
% LocalWords:  Tensorflow cmatch subsequences


\subsection{Implementation Details}
\label{sec:runtime}
%\maneesh{I think this stuff on running time should either go in an implementation section before results -- and also show the source actor video, or somewhere in the results section.}
%\maneesh{I think we should call this implementation and open by describing the machine that we've implemented on -- NVIDIA GTX... Then give running times.}
We implemented the fast phoneme search in Python and both our neural
retargeting model and the GAN renderer in
TensorFlow\,\cite{tensorflow2015}.  The monocular head tracker and
renderer are written in C++ with shader language extensions.

In preprocessing the repository and target videos, phoneme
alignment takes one third of the video time, and face registration takes
110 ms per frame.  It takes 30 minutes to generate training data for
our neural retargeting model and another 30 minutes to train it on one NVIDIA
GTX 1080Ti.  Training the GAN for neural rendering takes 17 hours on
one NVIDIA Tesla V100.
%Preprocessing, retargeting model training and
%neural renderer training is done once for each target video.


In our synthesis pipeline, 
our fast
phoneme search requires 5 seconds for a 
typical edit of
5 words containing 20 phonemes.  Retargeting inference speed is 10K
fps.  Composite images are rendered at 12 fps and final GAN rendering
takes 7 fps on two NVIDIA GTX 1080Ti. All together, a typical 5 word edit takes
around $30$ seconds for the full video generation (\Cref{tab:runtime}).
%We have also
%profiled our tool on edits of varying length and the runtime summary
%is in \Cref{tab:runtime}.

\begin{table}\small
\centering
\begin{tabular}{cccSSS}
\toprule
{\#words} & {\#phonemes} & {\#frames} & {search (s)} & {render (s)} & {total (s)} \\
\midrule
1 & 4  & 24  & 1.51  & 9.96  & 12.39 \\
% 2 & 10 & 32  & 2.12  & 10.00 & 15.45 \\
3 & 15 & 49  & 2.67  & 12.94 & 20.30 \\
% 4 & 18 & 53  & 4.18  & 13.56 & 22.26 \\
% 5 & 23 & 66  & 6.21  & 16.74 & 28.25 \\
6 & 25 & 72  & 5.32  & 17.74 & 28.95 \\
% 7 & 27 & 71  & 6.68  & 17.70 & 29.89 \\
8 & 39 & 105 & 7.57  & 24.33 & 37.97 \\
% 9 & 45 & 109 & 9.58  & 25.58 & 41.43 \\
10& 49 & 134 & 11.60 & 31.19 & 50.60 \\
% 19& 71 & 174 & 15.41 & 39.21 & 63.02 \\
\bottomrule
\end{tabular}
\caption{Runtime of our tool on a variety of edit lengths.
Search time scales roughly linearly with the number of phonemes, and render time scales linearly with the number of frames.
Even for long edits of 10 words, our system can generate video in approximately a minute.}
\label{tab:runtime}
\vspace{-3em}
\end{table}

It should be possible to further reduce the feedback time by
parallelizing our synthesis pipeline.  Phoneme search could be
distributed where each worker job is responsible for searching a
fraction of the repository.  Both parts of the neural rendering step
-- forming the composite images from target actor head parameters and
applying the GAN to generate photorealistic frames -- are
parallelizable by distributing the frames.  \new{We have performed
  initial experiments on parallelizing the GAN rendering which is the main bottleneck in our pipeline. Distributing the GAN rendering
  across a cluster of 8 NVIDIA Tesla V100s
  achieved a rendering rate of 24fps, a 3.4x speedup from the original 7fps for this step. Note that this speed up rate includes image compression overhead. Overall this experiment cuts the end-to-end synthesis time from $40$
  to $20$ seconds for a typical 8-word sentence.}  Similarly parallelizing the other parts of the pipeline and using sufficient hardware we believe that the end-to-end video generation feedback time could
be reduced significantly.  Streaming the frames as they are ready
could also further reduce the latency from issuing an edit to seeing
the first frames of the result, enabling real-time interactive editing
sessions.
%\maneesh{Perhaps should say this more strongly and emphasize it more. Make the case that we should be able to get to interactive rates.}

% LocalWords:  retargeting GAN renderer shader preprocessing GTX
% LocalWords:  cccSSS parallelizing photorealistic parallelizable


\subsection{Fast Phoneme Search and Stitching}\label{sec:search}
Our synthesis pipeline takes an edit $W$ specified as a sequence of
phonemes with timings $(w_1, \ldots, w_m)$ and starts by finding
matching subsequences of video in the source repository $V$, that can be
combined to produce $W$.
% \david{Do we talk about vanilla Fried'19 here or
% go straight to context-aware search? I think it's more clear to recap Fried19 as is done here,
% and talk about the improvement later, although that might make the novelty appear more incremental.}
% \maneesh{I think we just want to lightly lace it into what is already here. Isn't it just that we partition the edit into slightly overlapping subsequences?}
More precisely, we partition the edit $W$
into phoneme subsequences $(W_1, W_2, \ldots, W_k)$ and for each
subsequence $W_i$ find its best match $V_i$ in the repository $V$.
%
Fried~\etal\,\shortcite{Fried_2019} use a brute-force method that
considers all possible partitions $\mbox{split}(W)$ of the edit $W$,
and all possible matches with subsequences of $V$ to find $(V_1, V_2,
\ldots, V_k)$ that minimizes the objective:
$$C(W,V)=\min_{\substack{
    (W_1,W_2,\ldots,W_k)\in\mbox{split}(W)\\ (V_1,V_2,\ldots,V_k)
}}\sum_{i=1}^k \cmatch(W_i,V_i) + C_{\mbox{len}}(W_i)$$ where
$\cmatch$ is a custom Levenshtein edit
distance\,\shortcite{levenshtein1966} between two phoneme subsequences
that takes into account the phoneme label, the viseme label and the
timing difference, and $C_{\mbox{len}}$ penalizes short subsequences.
In order to find subsequences that transition well at their
  endpoints, during the search, we expand each subsequence $W_i$ by a
  single phoneme on either end. Thus, adjacent subsequences overlap by
  two {\em context} phonemes.  We find that this new {\em context expansion}
  approach better captures co-articulation effects between the
  subsequences, than the algorithm of Fried et al. which does not use
  context expansion (see user studies in \Cref{sec:user_study}).
%  Note that unlike Fried et al, we
%  expand each $W_i$ by one phoneme on either side during this search so that adjacent subsequences overlap by a phoneme.
%  In practice we have found that we
%  obtain better transitions between the matching phoneme subsequences using
%  this {\em context aware approach} as the overlapping phonemes better
%  account for coarticulation effects.}
%\david{In order to find subsequences that transition better from one into the next, we
%employ a new \emph{context aware} scheme where each $W_i$ is expanded to include the phoneme before and after.}
%\maneesh{Prev sentence is a little unclear -- I put an alternate version earlier. What do you think?}

We further modify Fried et al.'s search algorithm in three key
ways to obtain a speedup of over 3 orders of magnitude: (1) we propose
a fast alternative to to the Levenshtein distance, (2) we reduce the
size of the search space on $W_i$ and, (3) given $W_i$, we use a
viseme-based indexing scheme to quickly find the optimal $V_i$.
%\maneesh{Move context awareness to here as ... In addition, unlike Fried et al., we expand each subsequence $W_i$ by one phoneme (i.e. a context phoneme) on either side so that the resulting matches from the repository overlap by a phoneme on each end. In practice we have found that we obtain better transitions between the phoneme subsequences using this {\em context aware approach} as the context phonemes better handle coarticulation effects.}
Finally, we stitch together source actor expression parameters corresponding to the $V_i$s
to produce a single coherent sequence of expression parameters.
% \maneesh{Probably need to mention  stitching in a short sentence here as we will not how a paragraph or two on that.}

\paragraph{(1) Fast alternative to edit distance}
The full Levenshtein edit distance allows substitution, insertion and
deletion of phonemes when computing $\cmatch$.  However, we have observed that when the
matching subsequences between the edit $W$ and the repository
video $V$ contain phoneme insertions or deletions, the final
synthesized video appears out-of-sync with the audio; it either
contains extraneous mouth motions due to phoneme insertion, or it 
misses mouth motions due to deletion. In practice we find it is beneficial
to disallow insertions and deletions and only allow phoneme
substitutions.  Given a subsequence $W_i$ of the edit $W$, this approach
forces $\cmatch$ to only consider subsequences $V_j$ of the
repository $V$ that contain the same number of phonemes as $W_i$.  We
can therefore replace the Levenshtein distance with the sum of
element-wise substitution cost which requires linear time in the
number of phonemes rather than the quadratic time required for
computing the full Levenshtein distance\,\cite{wagner1974string}.

\paragraph{(2) Reduce search space for partitioning}
The brute force search considers all possible partitions of $W$ into
$(W_1,\ldots,W_k)$. But, an extremely long edit subsequence $W_i$ is
unlikely to have a good match with a repository subsequence $V_i$.
Thus, we can reduce the search space of possible partitions by capping
the maximum length of the $W_i$'s to $L$.  In our experience, 
99\% of the matches found by the brute force search
are of length $6$ or less, and we therefore set $L=6$.
This approach reduces the number of partitions to search.
More importantly, it typically reduces the number of distinct $W_i$'s we need to
consider by over an order of magnitude, especially when $W$ the full edit
sequence is itself very long.

\paragraph{(3) Viseme-based index to search repository}
For each edit subsequence $W_i$ we consider in our search space, we
must find the optimal $V_i$ in the repository with respect to
$\cmatch$.  Instead of checking all possible subsequences in the
repository, we impose an additional constraint on $V_i$ that restricts
the set of $V_i$ we consider to only the most likely match candidates
and allows us to build an index structure on the set of $V_i$ to
retrieve the likely candidates quickly.

As in Fried et al., our $\cmatch$ cost function considers phonemes to
match when they appear visually similar -- that is, their
corresponding visemes match. By imposing the restriction that $V_i$
start with the same viseme n-gram as $W_i$ we can pre-compute an index
for the repository using viseme n-grams as the key and the location of
the n-gram in the source repository video as the value.
%
At search time, we look up all possible candidate $V_i$'s using this
index and only compute the $\cmatch$ for them.  While this indexing
approach speeds up the search significantly it also reduces the space
of subsequence matches the search considers. In general, the longer the n-gram
key, the stronger the reduction and the more likely it is that no good
match will be found. In practice, we find that using a bi-gram index
best balances this trade-off between search speed and result quality.

\paragraph{Stitching}
% \maneesh{updated section.}
After we find the best matching phoneme subsequences $V_1,\ldots,V_k$
from the repository, we look up the expression parameters of the
source actor's 3D head model corresponding to each phoneme, and
linearly re-time them to match the phoneme durations specified in the
edit.  We then stitch together adjacent subsequences by first linearly
blending the the expression parameters across the overlapping context
phonemes and then applying a Gaussian filter over a window of 4 frames
around the transition boundaries between the subsequences to further
smooth the transition.

We have found in practice, that errors in tracking expression
parameters, timing misalignments and our linear blending can sometimes
fail to fully close the mouth of the 3D head model at the beginning of
\textbackslash m, \textbackslash b, and \textbackslash p phonemes. However,
proper mouth closures for these phonemes is crucial for producing
perceptually realistic results\,\cite{agarwal2020}.  We therefore force the desired
mouth closure by linearly blending in a closed-mouth expression from
the repository at the beginning of all \textbackslash m,
\textbackslash b, and \textbackslash p phonemes with a default length of 2
frames.  Note that the closed-mouth expressions are manually annotated
once during repository preprocessing and we automatically use the one
closest to the parameter values at the point of insertion.

%% \david{Phoneme misalignments and the blending procedure can sometimes
%%   fail to fully close the mouth of the 3D head model, such as at the
%%   beginning of \textbackslash m, \textbackslash b, \textbackslash p
%%   phonemes.  Proper mouth closures at the right time are crucial to
%%   the perceived realism of results \cite{agarwal2020}.
%% We therefore
%%   force the desired mouth closure by linearly blending in a
%%   closed-mouth expression from the repository at the beginning of all
%%   \textbackslash m, \textbackslash b, \textbackslash p phonemes with a
%%   default effect radius of 2 frames.  Note that the closed-mouth
%%   expressions are manually annotated once during repository
%%   preprocessing and we automatically use the one closest to the
%%   parameter values at the point of insertion.  }
% \david{Mouth closures at \textbackslash m, \textbackslash b, \textbackslash p phonemes are crucial to the perceived realism of results \cite{agarwal2020},
% but misalignments of phonemes and the blending procedure can sometimes fail to close the mouth of the 3D head model fully.
% We therefore force the desired mouth closure by linearly blending in a manually-annotated closed-mouth expression from the repository at the beginning of all \textbackslash m, \textbackslash b, \textbackslash p phonemes. 
% }
% \maneesh{Needs more detail and also a better lead in -- talk about the misalignment problem, then about the realism. How did we obtain the closemouthed frames. How long do we blend them in for? }

\vspace{0.5em}
Overall, the fast search strategy reduce the runtime of
the phoneme search process by three orders of magnitude compared to
the brute-force approach.  It takes around $5$ seconds to find
and stitch snippets $V_1,\ldots,V_k$ for an edit $W$ of $20$
phonemes in an hour-long repository.

% \david{Added two paragraphs here to talk about the algorithmic changes}
% Simply concatenating phoneme subsequences $V_i$ and $V_{i+1}$ can introduce transition artifacts because the phoneme after $V_i$ in the repository may be very dissimilar to the phoneme before $V_{i+1}$.
% We therefore employ a \emph{context-aware} searching algorithm, where we slighly expand each segment $W_i$ of the partition to include the phoneme before and after, so that $W_i$ and $W_{i+1}$ have two overlapping phonemes.
% The search procedure then finds overlapping phoneme subsequences $V_1,\ldots,V_k$ from the repository to form the edit.
% \david{A detail that can probably be cut:} In the event that no matches can be found for the expanded $W_i$, we fall back to include only the context phoneme before or the one after, and if still no match can be found, finally fall back to the original segment without context expansion.

% From the subsequences $V_1,\ldots,V_k$, we look up from the repository the corresponding expression parameters of the 3D head model.
% We then linearly retime the expression parameters corresponding to each phoneme in each repository subsequence to match the phoneme duration specified in the edit.
% Finally, we combine them into one continuous sequence of parameters.
% Specifically, we transition from one subsequence to the next by linearly blending over the overlapped region.
% To further smooth the transitions, we run a Gaussian filter on the blended values in the overlapped region.
% \david{A detail that can probably be cut:} If the overlapped region is shorter than 4 frames, we filter a larger window of 4 frames around the boundary.

% Mouth closures at \textbackslash m, \textbackslash b, \textbackslash p phonemes are crucial to the perceived realism of the result. \david{Is there a source to cite?}
% However, misalignments of phonemes and the blending procedure can sometimes fail to close the mouth of the 3D head model fully.
% We therefore force the desired mouth closure by linearly blending in a manually-annotated closed-mouth expression from the repository at the beginning of all \textbackslash m, \textbackslash b, \textbackslash p phonemes.
% \david{Should we have a forward-pointer to mouth-closure refinement control? I don't think we should.}

% \david{An attempt at a conclusion sentence}
% In summary, the fast phoneme search and stitching algorithm converts the input edit into a temporally coherent sequence of expression parameters of the source actor, which both conform to the timing specified by the edit and close the mouth at the desired time. It is three orders of magnitude faster compared to the brute-force approach, taking around $5$ seconds to process an edit of $20$ phonemes in an hour-long repository.


% \maneesh{Can you write a version of the paragraph. Once you've done that we can figure out how best to lace into this section. Also where to we insert mouth closure for m b p?}

%which enables our
%interactive editing work flow.

%% \maneesh{Can probably cut last sentence.}
%% The resulting snippets are later
%% stitched together and retargeted to the target actor in subsequent
%% steps of the synthesis pipeline as described in
%% \Cref{sec:synthesis_overview}.

% LocalWords:  subsequences subsequence len Levenshtein levenshtein
% LocalWords:  viseme visemes pre et al durations misalignments
% LocalWords:  preprocessing
'''