# Bidirectional Temporal Diffusion Model for Temporally Consistent Human
Animation

Tserendorj Adiya3, Jae Shin Yoon2 Jungeun Lee1 Sanghun Kim1 Hwasup Lim1

1Korea Institute of Science and Technology 2Adobe 3AI Center, CJ Corporation

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Work
done during internship at Korea Institute of Science and Technology.

###### Abstract

We introduce a method to generate temporally coherent human animation from a
single image, a video, or a random noise. This problem has been formulated as
modeling of an auto-regressive generation, i.e., to regress past frames to
decode future frames. However, such unidirectional generation is highly prone
to motion drifting over time, generating unrealistic human animation with
significant artifacts such as appearance distortion. We claim that
bidirectional temporal modeling enforces temporal coherence on a generative
network by largely suppressing the appearance ambiguity. To prove our claim,
we design a novel human animation framework using a denoising diffusion model:
a neural network learns to generate the image of a person by denoising
temporal Gaussian noises whose intermediate results are cross-conditioned
bidirectionally between consecutive frames. In the experiments, our method
demonstrates strong performance compared to existing unidirectional approaches
with realistic temporal coherence. Project Page.

##  1 Introduction

Humans express their own space-time continuum in the form of appearance and
motion. While existing generative models Isola et al. (2017); Sarkar et al.
(2021) have been successful to restore the space, i.e., high-quality image
generation with diverse human appearance, they often fail to decode the time,
e.g., temporally incoherent human motion. In this paper, we introduce a method
for temporal modeling of a generative network to synthesize temporally
consistent human animations. Our method can generate a human animation from
three different modalities: a random noise, a single image, and a single video
as shown in Figure. 1. Such generated human animations enable a number of
applications including novel content creation for non-expert media artists and
pre-visualization of human animation that can be further refined by
professional video creators.

The temporal modeling for human animation has been often formulated as a video
auto-regression problem: using past frames as a condition to decode future
frames. While such unidirectional generation (forward auto-regression) has
shown smooth animation results, it often suffers from texture drifting, e.g.,
the texture on the clothing of a person such as a skirt in Figure 2 is largely
distorted along its dynamic movements. This is mainly due to the significant
motion-appearance ambiguity where there exist infinite solutions to decide the
future state of human appearance even with the same motion, which amplifies
the artifacts (e.g., distortion) over time.

To suppress such motion-appearance ambiguity, we model a human appearance
bidirectionally: a generative network decodes the human appearance in the
context of both forward and backward image regression whose intermediate
features are cross-conditioned over time. Our key observation is that the
bidirectional temporal consistency in feature space highly suppresses the
motion-appearance ambiguity, which prevents from the texture drifting while
maintaining its temporal smoothness.

Figure 1: Our method generates temporally coherent human animation from
various modalities. Figure 2: Results from a unidirectional generative model
with texture drifting over time.

We realize the idea of bidirectional temporal modeling by utilizing a
generative denoising diffusion model Ho et al. (2020). A denoising network
learns to iteratively remove temporal Gaussian noises to generate the human
animation guided by conditioning poses and appearance style. Inspired by
message passing algorithms in dynamic programming Felzenszwalb & Zabih (2010);
Arora et al. (2009), we recursively cross-condition the intermediate results
between consecutive frames in a bidirectional way as shown in Figure 3; where
the temporal context of human appearance is locally consistent for consecutive
frames at the first denoising step, and it is progressively refined at every
denoising iteration to be globally coherent for entire frames.

In the experiments, we demonstrate that our bidirectional denoising diffusion
model generates human animations from a single image with a strong temporal
coherence, outperforming the results from unidirectional generative models. We
also show that learning from multiple frames, i.e., a person-specific video,
can further improve the physical plausibility of the generated human
animation. Finally, we showcase that our method can generate human animations
with diverse clothing styles and identities without any conditioning images.

Contribution (1) We propose a bidirectional temporal diffusion model that can
generate temporally coherent human animation from random noise, a single
image, or a video. (2) Inspired by dynamic message passing algorithms, we
introduce the feature cross-conditioning between consecutive frames with
recursive sampling, which allows embedding the motion context on the iterative
denoising process in a locally and globally consistent way. (3) We
quantitatively and qualitatively demonstrate that our method shows a strong
temporal coherence compared to existing unidirectional methods. For an
accurate evaluation, we newly create high-quality synthetic data of people in
dynamic movements using graphics simulation, which provides ground-truth data,
i.e., different people in the perfectly same motion.

##  2 Related Works

Human Motion Transfer Given a sequence of guiding body poses and the style of
human appearance, it aims to generate the human animation that satisfies the
conditioning motion and style. Many existing pose transfer methods have
utilized 2D keypoints as conditioning body pose maps Chan et al. (2019);
Balakrishnan et al. (2018); Esser et al. (2018); Liu et al. (2019a). However,
these approaches often fail to extract the physical implications from the
keypoints maps, resulting in temporally unnatural human animation.

To address this motion consistency issue, methods such as EDN Chan et al.
(2019), V2V Wang et al. (2018), and DIW Wang et al. (2021) leveraged Markovian
independence to generate auto-regressive frames. These approaches utilize
Densepose Güler et al. (2018) as a 2D pose conditioning and learn motion-
dependent appearance for a specific person, producing realistic animation
results for unseen motions. Recent advancements in this area involve embedding
3D velocities from the SMPL Loper et al. (2015) model as pose conditioning
Yoon et al. (2022), leading to the better generation of complex
transformations. However, these methods require extensive training on the
videos of a single individual, limiting their generalizability to diverse
people.

To synthesize human animations of diverse people using a single model, several
works have studied human motion transfer from a single image. Solutions
include applying affine transformations Balakrishnan et al. (2018); Zhou et
al. (2019), flow-based warping Wang et al. (2019); Zhao & Zhang (2022);
Siarohin et al. (2021; 2019), or assuming a base 3D human model and texture
mapping with DensePose Neverova et al. (2018); Huang et al. (2021) or the SMPL
model Li et al. (2019); Liu et al. (2019b). However, these methods struggle to
represent diverse surface transformations in clothing, i.e., the clothing
texture looks static even under the pose changes, resulting in unnatural
animations.

Generative Diffusion Models Recently, diffusion models have demonstrated
outstanding performance in high-quality image generation Ho et al. (2020);
Nichol & Dhariwal (2021); Song et al. (2020b), text-to-image translation
Rombach et al. (2022); Preechakul et al. (2022); Saharia et al. (2022a);
Ramesh et al. (2021), image super-resolution Saharia et al. (2022b), image
restoration Kawar et al. (2022); Wang et al. (2022) view synthesis Watson et
al. (2022). Compared to generative adversarial networks (GANs) Isola et al.
(2017); Karras et al. (2019), diffusion models enable more stable training and
reduced mode collapse, leading to diverse and high-quality generation results.

The initial diffusion model was based on Song’s Song & Ermon (2019) score-
matching approach, which estimates gradients using Langevin dynamics to infer
data distributions. Subsequently, the DDPM Ho et al. (2020) method was
introduced, leveraging weighted variational bounds and becoming widely
adopted. Later, NCSN Song & Ermon (2019) and its equivalent from ODE Song et
al. (2020b) emerged, presenting a more general form.

One notable drawback of Markov Chain Monte Carlo (MCMC) based inference in
diffusion models is the longer inference time compared to GANs. DDIM Song et
al. (2020a) addresses this issue by interpreting the diffusion process as an
implicit function that significantly reducing sampling time while preserving
generation quality.

Diffusion models, as referenced in recent studies such as Ho et al. (2022b);
Yang et al. (2023); Ho et al. (2022a); Singer et al. (2022); Zhou et al.
(2022); Esser et al. (2023); Guo et al. (2023), have become increasingly
popular in the field of video generation. These models often utilize
techniques like cross-attention and 3D U-Nets to ensure videos remain
consistent over time. Despite their potential, most of these methods face
challenges in generating longer videos without encountering issues like shape
drifting and appearance jitters. This paper presents a new and practical
approach to overcome these limitations. Our method, which is distinct from
previous work, employs a 2D-Unet based framework to create temporally coherent
animations. Notably, our approach is effective in generating animations of
humans and is not constrained by video length.

Figure 3: The left illustration represents a unidirectional diffusion model,
and the right one provides an overview of our proposed bidirectional temporal
diffusion model (BTDM). The dotted arrows indicate the direction of
conditioning, and $k$ and $t$ represent the denoising step and time interval,
respectively.

##  3 Method

Conventional Denoising Diffusion Probabilistic Models (DDPM) work by gradually
diffusing isotropic Gaussian noise onto a data sample $y\in\mathcal{D}$ across
$K$ steps along a Markovian chain. The process is reversed, such that $y$ is
approximated from the $\mathcal{N}(0,I)$ distribution.

One can extend these conventional DDPM to generate a human animation driven by
a sequence of human pose maps $\mathcal{S}=\\{s_{1},...,s_{T}\\}$ (e.g.,
densepose Güler et al. (2018)) in an auto-regressive way. For example, a
network is designed to generate future frames dependent on previous frames by
gradually diffusing isotropic Gaussian noise onto the training sample
$y_{t}\in Y=\\{y_{1},...,y_{T}\\}$ under the conditional Markovian
independence, i.e.,
$p(Y)=\prod_{t=1}^{T}p(y_{t}|y_{t-1};s_{t}\in\mathcal{S})$. However, such
autoregressive models often suffer from texture drifting due to the motion-
appearance ambiguity that is inherent in unidirectional prediction.

To suppress the motion-appearance ambiguity, we design a bidirectional
temporal diffusion model (BTDM) as shown in Figure 3. BTDM learns motion-
dependent appearances in both forward and backward directions along the time
axis. The denoising results from each step in either time direction serve as
mutual conditions for generating human animation. Our model can generate
realistic animations unconditionally, as well as conditionally from a single
image or video.

###  3.1 Bidirectional Temporal Diffusion Model

Given a pose sequence $S$ and its corresponding image sequence $Y$, modeling
their mapping bidirectionally along the time axis that follows Markovian
independence results in:

$p_{f}(Y|S):=\prod_{t=1}^{T}p(y_{t}|y_{t-1},s_{t}),\quad\quad
p_{b}(Y|S):=\prod_{t=1}^{T}p(y_{t-1}|y_{t},s_{t-1})$ (1)

In this setup, $p_{f}$ represents the forward direction along the time axis,
and $p_{b}$ signifies the backward direction. We define a marginal
distribution with isotropic Gaussian process that gradually adds increasing
amounts of noise to the data sample as the signal-to-noise-ratio
$\lambda(\cdot)$ decreases, following Salimans & Ho (2021):

$q(y_{t}^{1:K}|y_{t}^{0}):=\prod_{k=1}^{K}q(y_{t}^{k}|y_{t}^{k-1}),\quad\quad
q(y_{t}^{k}|y_{t}^{k-1}):=\mathcal{N}(y_{t}^{k};\sqrt{\sigma(\lambda(k))}y_{t}^{k-1},\sigma(-\lambda(k))\textbf{I})$
(2)

where $\sigma(\cdot)$ is the sigmoid function, $K$ is the number of diffusion
step, and I denotes the identity.

Both the motion-dependent appearance distribution in Equation 1 and the
diffusion process in Equation 2 follow a Markovian chain. Ideally, we should
predict $y_{t}$ and $y_{t-1}$ using perfectly denoised $y_{t-1}^{0}$ (in the
forward direction) or $y_{t}^{0}$ (in the backward direction) as conditions.
However, such perfectly denoised images are not available during inference,
which leads to overfitting to the training data and amplifies the error from
motion-appearance ambiguity. For this reason, we integrate these two
independent Markovian chains as follows:

$p_{f}(Y^{k}|S):=\prod_{t=1}^{T}p(y_{t}^{k}|y_{t-1}^{k},s_{t}),\quad\quad
p_{b}(Y^{k}|S):=\prod_{t=1}^{T}p(y_{t-1}^{k}|y_{t}^{k},s_{t-1}),$ (3)

where by utilizing the noisy $y_{k}$ as a condition, we concurrently diminish
the reliance of motion-dependent appearance generation on the preceding frame
and avert overfitting to the condition, thereby alleviating artifacts when
generating unseen conditions and improving the model’s generalization
performance. This approach also yields more temporally consistent animations
by highly limiting the motion diversity between consecutive frames.

Although $p_{f}$ and $p_{b}$ are independent, $p(y_{t}|y_{t-1})$ and
$p(y_{t-1}|y_{t})$ are concurrently defined on the time axis $t$. This allows
us to optimize both probabilities simultaneously. Therefore, the objective
function for training is defined as follows:

$\begin{split}L=\mathop{\mathbb{E}_{t\sim[1,T],k\sim[1,K],y^{k}\sim
q_{k},d_{f},d_{b},c}}\Big{[}\frac{1}{2}\big{(}||&f_{\theta}(y_{t}^{k},y_{t-1}^{k},\lambda(k),s_{t},c,d_{f})-y_{t}^{0}||_{2}^{2}\\\
+||&f_{\theta}(y_{t-1}^{k},y_{t}^{k},\lambda(k),s_{t-1},c,d_{b})-y_{t-1}^{0}||_{2}^{2}\big{)}\Big{]}\end{split}$
(4)

where $f_{\theta}$ is a neural network whose task is to denoise the frame
$y_{t-1}^{k}$, $y_{t}^{k}$ given a different noisy frame $y_{t}^{k}$,
$y_{t-1}^{k}$ and given pose $s_{t}$, $s_{t-1}$. The $\lambda$ is the log
signal-to-noise-ratio function dependent on $k$, and $c$ is a single image
condition that determines the appearance of a target person. The notation
$d_{f},d_{b}$ are learnable positional encoding vectors for distinguishing
temporal direction. Following the method used in Ramesh et al. (2022), we
adapt our model to predict clean images instead of noise.

Figure 4: The illustration of (a) our BTU-Net and (b) bidirectional attention
block. The dotted squares in (a) represents bidirectional attention block. The
small blue and pink squares in (a) indicate the intermediate feature of
$E_{p}$ and $E_{a}$, respectively.

###  3.2 Bidirectional Temporal U-Net

To enable BTDM, we construct a Bidirectional Temporal U-Net (BTU-Net) by
modifying the U-Net architecture, as shown in Figure 4. This architecture
consists of a network, $E_{a}$, that encodes a single image condition $c$;
another network, $E_{p}$, that encodes poses $s$ corresponding to $t-1$ and
$t$; and a pair of U-Nets, $f_{\theta}$, that accept $y_{t-1}^{k}$ and
$y_{t}^{k}$ as input and predict the denoised human images temporally in both
forward and backward directions. The multi-scale intermediate features are
modulated by pose features, noise ratio $\lambda$, and temporal direction
vectors ($d_{f}$ and $d_{b}$) using existing Feature-wise Linear Modulation
layer (FiLM) Perez et al. (2018). This pair of U-Nets shares weights and
applies attention between the features encoded by $E_{a}$ and intermediate
features of $f_{\theta}$, as shown in the bidirectional attention block in
Figure 4(b), which is composed of appearance and spatiotemporal block. Each
block utilizes multi head attention Vaswani et al. (2017).

Appearance Block The yellow box in Figure 4(b), the appearance attention block
is composed of parallel multi-head attention mechanisms with weight sharing.
For the multi-head attention, features from times $t$ and $t-1$ of
$f_{\theta}$ are used as the query, while the appearance features of $E_{a}$
are employed as the key and value. This block is specifically designed to
learn the correlation between the appearance features encoded by $E_{a}$ and
the intermediate features of $f_{\theta}$. Through the multi-head attention
mechanism, it attends to global context correlations, facilitating the
effective transfer of appearance features to $f_{\theta}$ even during rapid
actions (those with substantial pose changes relative to frame intervals).
This, in turn, enables the generation of novel poses effectively.

Spatiotemporal Block The spatiotemporal attention block takes the output
feature pairs from the appearance attention block as inputs and, as
illustrated in Figure 4 (b), performs cross attention. Such a structure
effectively enables the learning of the temporal correlations of spatial
features between times $t$ and $t-1$. Furthermore, by making the features for
generating $t$ dependent on $t-1$ and vice versa, a temporally bidirectional
structure is achieved. This design facilitates the efficient learning of
temporal correlations.

We adopt the bidirectional attention block for the feature at specific
resolutions, i.e., $32\times 32$, $16\times 16$, and $8\times 8$. More details
on the architecture can be found in Appendix B.3.

###  3.3 Training and Inference for Various Tasks

Single Image Animation Our BTDM, trained on multiple videos, can be directly
applied to generate realistic human animation results for unseen people and
poses. Similar to existing one-shot generation methods Wang et al. (2018), we
further fine-tune our BTU-Net on the given single image to enhance the visual
quality. For this, the conditioning image $c$ is set as a single image
sequence $Y=\\{c\\}$ and the pose sequence $S=\\{g(c)\\}$, where $g(\cdot)$ is
a pose estimation function (e.g. DensePose). This setup aligns with the
training process outlined in Equation 4.

Person-Specific Animation Our method can be applied to the task of generating
novel animations by training a single person’s video. To adapt our method to
this task, we train our BTDM framework using the objective function from
Equation 4, excluding the image condition $c$.

Unconditional animation Moreover, our method facilitates the creation of
temporally consistent animations without any appearance-related conditions.
For such unconditional generation, we trained our model with the condition $c$
set to $\emptyset$ of Equation 4.

During the inference stage, to effectively utilize our BTDM, we employ a
bidirectional recursive sampling method across all tasks. More details about
this method can be found in Appendix A.

##  4 Experiments

We validate our bidirectional temporal diffusion model on two tasks:
generating human animation from a single image and generating human animation
by learning from a person-specific video. We also show that our model can
generate diverse human animation with an unconditional setting (i.e.,
generating human animation from random noise).

###  4.1 Single Image Animation

Dataset We use two datasets that can effectively validate the quantity and
quality of temporal coherence in the generated human animation. 1) Graphics
simulation: for quantitative evaluation, we construct a high-quality synthetic
dataset using a graphics simulation tool for soft 3D clothing animation
Reallusion (b) which provides perfect ground truth data for the motion
transfer task (i.e., different people in the exact same motion, which does not
exist from real-world videos) with physically plausible dynamic clothing
movements. The dataset includes a total of 80 training videos and 19 testing
videos, each of which lasts 32 seconds at 30 FPS. We customize the 3D human
appearance using CharacterCreator Reallusion (a), and we use Mixamo motion
data Adobe  for animation. The pose map is obtained by rendering the IUV
surface coordinates of a 3D body model (i.e., SMPLLoper et al. (2015)). Please
see the appendix D for more details of our graphics simulation data. 2) UBC
Fashion dataset Zablotskaia et al. (2019): it consists of 500 training and 100
testing videos of individuals wearing various outfits and rotating 360
degrees. Each video lasts approximately 12 seconds at 30 FPS. We apply
DensePose Güler et al. (2018) to obtain pose UV maps. We use this dataset for
the qualitative demonstration on real images since it does not provide ground
truth data with the exact same motion.

Baselines We compare our method to existing unidirectional temporal models:
Thin-Plate Spline Motion Model for Image Animation (TPSMM) Zhao & Zhang (2022)
and Motion Representations for Articulated Animation (MRAA) Siarohin et al.
(2021) are designed to predict forward optical flow to transport the pixel
from a source to target pose, following a rendering network. Both methods were
trained on each dataset from scratch using the provided scripts and
recommended training setup. All methods are trained at a resolution of
256$\times$256.

Metric To evaluate the quality of the generated human animations, we employ
five key metrics: 1) SSIM (Structural Similarity Index) Wang et al. (2004):
quantifies the structural similarity between the generated and ground truth
images based on local patterns of pixel intensities and contrast spaces. 2)
LPIPS (Learned Perceptual Image Patch Similarity) Zhang et al. (2018):
cognitive similarity between synthesized images and ground truth images by
comparing the perceptual features extracted from both, utilizing a pre-trained
deep neural network. 3) tLPIPS (Temporal Learned Perceptual Image Patch
Similarity) Chu et al. (2020): extends the LPIPS measure to temporal domain,
evaluating the plausibility of change across consecutive frames. It is defined
as
$\mathrm{tLPIPS}=||\mathrm{LPIPS}(y_{t},y_{t-1})-\mathrm{LPIPS}(g_{t},g_{t-1})||$,
where $y$ and $g$ represent the synthesized and ground truth images,
respectively. 4) tOF Chu et al. (2020): pixel-wise difference of the estimated
optical flow between each sequence and the ground truth. 5) FID (Fréchet
Inception Distance) Heusel et al. (2017): measures the distance between the
distributions of synthesized and real images in the feature space of a pre-
trained Inception network.

Result The quantitative results for the graphics simulation data are presented
in Table 1. Our BTDM method outperforms other methods in all metrics. As can
be seen in Figure 5, our method closely resembles the source image, and the
appearance changes depending on the movement are more realistic than other
baseline methods. TPSMM and MRAA undergo significant artifacts such as texture
distortion and blur due to errors in the forward optical flow prediction. In
particular, the models from baseline methods highly confuse on the motion with
large dynamics. The same trend is observed in the UBC Fashion data.
Specifically, when the appearance of a driven video significantly differs from
the source image in TPSMM or MRAA methods, abnormal artifacts often occur such
as the loss of identity. Moreover, our method is found to preserve fine
details considerably better.

###  4.2 Person-specific Animation

Dataset To evaluate the performance of our method in the task of person-
specific animation, we use five videos from Yoon et al. (2022). Each video
comprises between 6K and 15K frames, featuring a person performing a diverse
range of dynamic actions. The pose UV map is obtained using DensePoseGüler et
al. (2018).

Baseline We compare our method to V2V Wang et al. (2018), EDN Chan et al.
(2019), HFMT Kappel et al. (2021), DIW Wang et al. (2021), and MDMT Yoon et
al. (2022), which utilized a generative network in a temporally unidirectional
way. All methods were trained on the training set of each video and evaluated
on the test set.

Metrics We use SSIM, LPIPS, and tLPIPS as used in Section 4.1.

Table 1: Quantitative results for single image animation tested on simulation data.  Methods | SSIM$\uparrow$ | LPIPS$\downarrow$ | tLPIPS$\downarrow$ | tOF | FID$\downarrow$
---|---|---|---|---|---
MRAA Siarohin et al. (2021) | 0.894 | 0.140 | 0.011 | 13.58 | 67.68
TPS Zhao & Zhang (2022) | 0.915 | 0.077 | 0.005 | 11.92 | 48.76
Ours | 0.958 | 0.036 | 0.003 | 8.93 | 11.14
Figure 5: Qualitative comparisons for the single image animation task on
graphics simulation (left) and UBC Fashion data (right).

Result The evaluation results for our method and the baselines on the test
sequences from the five videos are displayed in Table 2. Our approach exhibits
a performance that is either comparable to or surpasses that of other state-
of-the-art methods in the LPIPS and tLPIPS metrics. Note that, while our model
can synthesize the background, we only evaluate the quality of the foreground
synthesis for consistent and fair comparison across baseline methods where we
use existing segmentation method Gong et al. (2018) to remove the background.
for evaluation. Specifically, our method outshines all others in the SSIM
evaluation with a diffusion-based generative framework. The highest average
score implies that our method performs consistently better than other methods
in terms of temporal coherence and visual plausibility across assorted
appearance and motion styles.

Further qualitative results are demonstrated in Figure 6 where the baseline
methods often lose context or become blurred in complex poses, leading to
physically implausible human animation. Our method demonstrates robustness to
dynamic movements and strong temporal coherence, yielding clear and stable
results. Please also refer to the demo video.

Table 2: Quantitative results of person-specific animation. Each of the three values are in the order of LPIPS($\downarrow$)$\times$102, tLPIPS($\downarrow$)$\times$103, and SSIM($\uparrow$)$\times$10, respectively. The number of images used for training is indicated in parentheses, e.g., (6K).  Methods | Data 1 (6K) | Data 2 (10K) | Data 3 (10K) | Data 4 (15K) | Data 5 (15K) | Average
---|---|---|---|---|---|---
V2V | 1.84/2.95/9.69 | 3.03/3.83/9.60 | 11.51/3.80/9.05 | 3.06/2.98/9.40 | 4.01/4.04/9.49 | 4.69/3.52/9.45
EDN | 2.74/3.86/9.57 | 3.98/5.40/9.46 | 13.12/4.52/8.96 | 4.90/5.09/9.22 | 5.00/4.82/9.34 | 5.95/4.74/9.31
HFMT | 3.68/4.41/9.48 | 6.39/8.54/9.26 | 13.27/4.62/8.91 | 6.08/3.22/9.10 | 6.86/4.53/9.21 | 7.26/5.06/9.19
DIW | 1.83/2.88/9.68 | 2.70/4.11/9.61 | 11.89/4.09/9.03 | 2.83/4.66/9.45 | 4.14/5.20/9.48 | 4.68/4.19/9.45
MDMT |  1.76/2.58/9.73 |  2.68/3.77/9.65 | 10.48/3.12/9.11 | 2.81/2.86/9.45 |  3.81/4.12/9.50 |  4.31/3.29/9.49
Ours | 1.90/2.83/9.72 | 2.91/3.76/9.65 |  10.32/2.52/9.28 |  2.78/2.85/9.57 | 4.07/4.26/9.51 | 4.39/3.22/9.55
Figure 6: Qualitative comparison between the state-of-the-art methods and our approach for the task of generating person-specific human animation. Table 3: Quantitative results on ablation study with graphics simulation data.  Methods | SSIM$\uparrow$ | LPIPS$\downarrow$ | tLPIPS$\downarrow$
---|---|---|---
Ours w/ Unidirectional Model | 0.937 | 0.052 | 0.005
Ours | 0.958 | 0.036 | 0.003
Figure 7: Qualitative results of unconditional animation generation with UBC
Fashion data. The top row shows various people generated unconditionally,
while the bottom row displays samples of the generated sequences.

###  4.3 Ablation study

To evaluate the effect of the module in our method, we perform an ablation
study. The quantitative results are in Table 3, and please refer to the
supplementary materials for visual comparison.

Unidirectional vs. Bidirectional We compare our bidirectional temporal
diffusion model with the unidirectional one. For this, we trained the same
BTU-Net in a unidirectional manner using the same loss. The bidirectional
approach demonstrates far more spatiotemporal consistency based on tLPIPS in
Table 3. Our main observation is that due to significant motion-appearance
ambiguity, the generated texture sometimes diverges at the end of the frame
under highly dynamic human movements. Based on the improvements in LPIPS, we
can notice such strong temporal coherence helps with improving the visual
quality as well.

Number of Images for Fine-Tuning For single-image animation, we fine-tune the
model on a single image. We found that the quality improves as the number of
fine-tuning images increases. In the supplementary material, we introduce the
experiments about the impact of the number of fine-tuning images on rendering
quality.

Unconditional Human Animation Generation Figure 7, we demonstrate that our
method can generate human animation with diverse appearances without
conditioning any images or videos.

##  5 Conclusion

We introduce a new method to synthesize temporally coherent human animation
from a single image, a video, or a random noise. We address the core challenge
of temporal incoherence from existing generative networks that decode future
frames in an auto-regressive way. We argue that such unidirectional temporal
modeling of a generative network involves a significant amount of motion-
appearance ambiguity, leading to the artifacts such as texture drifting. We
suppress the motion-appearance ambiguity by newly designing a bidirectional
temporal diffusion model (BTDM): a denoising network progressively removes
temporal Gaussian noises whose intermediate results are cross-conditioned over
consecutive frames, which allows conditioning locally and globally coherent
motion context on our video generation framework. We perform the evaluation on
two different tasks, i.e., human animation from a single image and person-
specific human animation, and demonstrate that BTDM shows strong temporal
coherence, which also helps to improve the visual quality, compared to
existing methods.

Limitation While BTDM produces temporally coherent human animations, there
exist several limitations. Since our model generates the video as a function
of the estimated body poses, the errors in the pose estimation affect the
rendering quality, e.g., the misdetection of hands produces some appearance
distortion around the hand. Due to the inherent ambiguity of 2D pose
representation, our method sometimes shows weakness in the sequence with 3D
human rotations. Our potential future work is to improve 3D awareness and
completeness by utilizing a complete 3D body model, e.g., SMPL Loper et al.
(2015), in our bidirectional temporal diffusion framework.

##  6 Acknowledgement

This work was supported by Institute of Information communications Technology
Planning Evaluation (IITP) grant funded by the Korea government(MSIT)
(No.RS2023-00225630, Development of Artificial Intelligence for Text-based 3D
Movie Generation).

## References

  * (1) Adobe.  Adobe mixamo.  https://www.mixamo.com/#/.
  * Arora et al. (2009) Sanjeev Arora, Constantinos Daskalakis, and David Steurer.  Message passing algorithms and improved lp decoding.  In _Proceedings of the forty-first annual ACM symposium on Theory of computing_ , pp. 3–12, 2009.
  * Balakrishnan et al. (2018) Guha Balakrishnan, Amy Zhao, Adrian V Dalca, Fredo Durand, and John Guttag.  Synthesizing images of humans in unseen poses.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 8340–8348, 2018.
  * Chan et al. (2019) Caroline Chan, Shiry Ginosar, Tinghui Zhou, and Alexei A Efros.  Everybody dance now.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pp. 5933–5942, 2019.
  * Chu et al. (2020) Mengyu Chu, You Xie, Jonas Mayer, Laura Leal-Taixé, and Nils Thuerey.  Learning temporal coherence via self-supervision for gan-based video generation.  _ACM Transactions on Graphics (TOG)_ , 39(4):75–1, 2020.
  * Esser et al. (2018) Patrick Esser, Ekaterina Sutter, and Björn Ommer.  A variational u-net for conditional appearance and shape generation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 8857–8866, 2018.
  * Esser et al. (2023) Patrick Esser, Johnathan Chiu, Parmida Atighehchian, Jonathan Granskog, and Anastasis Germanidis.  Structure and content-guided video synthesis with diffusion models.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 7346–7356, 2023.
  * Felzenszwalb & Zabih (2010) Pedro F Felzenszwalb and Ramin Zabih.  Dynamic programming and graph algorithms in computer vision.  _IEEE transactions on pattern analysis and machine intelligence_ , 33(4):721–740, 2010.
  * Gong et al. (2018) Ke Gong, Xiaodan Liang, Yicheng Li, Yimin Chen, Ming Yang, and Liang Lin.  Instance-level human parsing via part grouping network.  In _Proceedings of the European conference on computer vision (ECCV)_ , pp. 770–785, 2018.
  * Güler et al. (2018) Rıza Alp Güler, Natalia Neverova, and Iasonas Kokkinos.  Densepose: Dense human pose estimation in the wild.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 7297–7306, 2018.
  * Guo et al. (2023) Yuwei Guo, Ceyuan Yang, Anyi Rao, Yaohui Wang, Yu Qiao, Dahua Lin, and Bo Dai.  Animatediff: Animate your personalized text-to-image diffusion models without specific tuning.  _arXiv preprint arXiv:2307.04725_ , 2023.
  * Heusel et al. (2017) Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  _Advances in neural information processing systems_ , 30, 2017.
  * Ho et al. (2020) Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Advances in Neural Information Processing Systems_ , 33:6840–6851, 2020.
  * Ho et al. (2022a) Jonathan Ho, William Chan, Chitwan Saharia, Jay Whang, Ruiqi Gao, Alexey Gritsenko, Diederik P Kingma, Ben Poole, Mohammad Norouzi, David J Fleet, et al.  Imagen video: High definition video generation with diffusion models.  _arXiv preprint arXiv:2210.02303_ , 2022a.
  * Ho et al. (2022b) Jonathan Ho, Tim Salimans, Alexey Gritsenko, William Chan, Mohammad Norouzi, and David J Fleet.  Video diffusion models.  _arXiv preprint arXiv:2204.03458_ , 2022b.
  * Huang et al. (2021) Zhichao Huang, Xintong Han, Jia Xu, and Tong Zhang.  Few-shot human motion transfer by personalized geometry and texture modeling.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 2297–2306, 2021.
  * Isola et al. (2017) Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A Efros.  Image-to-image translation with conditional adversarial networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 1125–1134, 2017.
  * Kappel et al. (2021) Moritz Kappel, Vladislav Golyanik, Mohamed Elgharib, Jann-Ole Henningson, Hans-Peter Seidel, Susana Castillo, Christian Theobalt, and Marcus Magnor.  High-fidelity neural human motion transfer from monocular video.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 1541–1550, 2021.
  * Karras et al. (2019) Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 4401–4410, 2019.
  * Kawar et al. (2022) Bahjat Kawar, Michael Elad, Stefano Ermon, and Jiaming Song.  Denoising diffusion restoration models.  _Advances in Neural Information Processing Systems_ , 35:23593–23606, 2022.
  * Li et al. (2019) Yining Li, Chen Huang, and Chen Change Loy.  Dense intrinsic appearance flow for human pose transfer.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 3693–3702, 2019.
  * Liu et al. (2019a) Lingjie Liu, Weipeng Xu, Michael Zollhoefer, Hyeongwoo Kim, Florian Bernard, Marc Habermann, Wenping Wang, and Christian Theobalt.  Neural rendering and reenactment of human actor videos.  _ACM Transactions on Graphics (TOG)_ , 38(5):1–14, 2019a.
  * Liu et al. (2019b) Wen Liu, Zhixin Piao, Jie Min, Wenhan Luo, Lin Ma, and Shenghua Gao.  Liquid warping gan: A unified framework for human motion imitation, appearance transfer and novel view synthesis.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 5904–5913, 2019b.
  * Loper et al. (2015) Matthew Loper, Naureen Mahmood, Javier Romero, Gerard Pons-Moll, and Michael J Black.  Smpl: A skinned multi-person linear model.  _ACM transactions on graphics (TOG)_ , 34(6):1–16, 2015.
  * Neverova et al. (2018) Natalia Neverova, Riza Alp Guler, and Iasonas Kokkinos.  Dense pose transfer.  In _Proceedings of the European conference on computer vision (ECCV)_ , pp. 123–138, 2018.
  * Nichol & Dhariwal (2021) Alexander Quinn Nichol and Prafulla Dhariwal.  Improved denoising diffusion probabilistic models.  In _International Conference on Machine Learning_ , pp. 8162–8171. PMLR, 2021.
  * (27) Nvidia.  Nvidia omniverse.  https://www.nvidia.com/en-us/omniverse/.
  * Perez et al. (2018) Ethan Perez, Florian Strub, Harm De Vries, Vincent Dumoulin, and Aaron Courville.  Film: Visual reasoning with a general conditioning layer.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * (29) Sony Pictures.  Lucasfilm and sony pictures imageworks release alembic 1.0.  Sony Pictures Imageworks, Lucasfilm (August 9, 2011).
  * Preechakul et al. (2022) Konpat Preechakul, Nattanat Chatthee, Suttisak Wizadwongsa, and Supasorn Suwajanakorn.  Diffusion autoencoders: Toward a meaningful and decodable representation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 10619–10629, 2022.
  * Ramesh et al. (2021) Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-shot text-to-image generation.  In _International Conference on Machine Learning_ , pp. 8821–8831. PMLR, 2021.
  * Ramesh et al. (2022) Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ , 2022.
  * Reallusion (a) Reallusion.  Character creator.  https://www.reallusion.com/character-creator/, a.
  * Reallusion (b) Reallusion.  iclone8.  https://www.reallusion.com/iclone/, b.
  * Rombach et al. (2022) Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 10684–10695, 2022.
  * Saharia et al. (2022a) Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  _Advances in Neural Information Processing Systems_ , 35:36479–36494, 2022a.
  * Saharia et al. (2022b) Chitwan Saharia, Jonathan Ho, William Chan, Tim Salimans, David J Fleet, and Mohammad Norouzi.  Image super-resolution via iterative refinement.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022b.
  * Salimans & Ho (2021) Tim Salimans and Jonathan Ho.  Progressive distillation for fast sampling of diffusion models.  In _International Conference on Learning Representations_ , 2021.
  * Sarkar et al. (2021) Kripasindhu Sarkar, Lingjie Liu, Vladislav Golyanik, and Christian Theobalt.  Humangan: A generative model of human images.  In _2021 International Conference on 3D Vision (3DV)_ , pp. 258–267. IEEE, 2021.
  * Siarohin et al. (2019) Aliaksandr Siarohin, Stéphane Lathuilière, Sergey Tulyakov, Elisa Ricci, and Nicu Sebe.  First order motion model for image animation.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Siarohin et al. (2021) Aliaksandr Siarohin, Oliver J Woodford, Jian Ren, Menglei Chai, and Sergey Tulyakov.  Motion representations for articulated animation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 13653–13662, 2021.
  * Singer et al. (2022) Uriel Singer, Adam Polyak, Thomas Hayes, Xi Yin, Jie An, Songyang Zhang, Qiyuan Hu, Harry Yang, Oron Ashual, Oran Gafni, et al.  Make-a-video: Text-to-video generation without text-video data.  _arXiv preprint arXiv:2209.14792_ , 2022.
  * Song et al. (2020a) Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  In _International Conference on Learning Representations_ , 2020a.
  * Song & Ermon (2019) Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  _Advances in neural information processing systems_ , 32, 2019.
  * Song et al. (2020b) Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  In _International Conference on Learning Representations_ , 2020b.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang et al. (2018) Ting-Chun Wang, Ming-Yu Liu, Jun-Yan Zhu, Guilin Liu, Andrew Tao, Jan Kautz, and Bryan Catanzaro.  Video-to-video synthesis.  _arXiv preprint arXiv:1808.06601_ , 2018.
  * Wang et al. (2019) Ting-Chun Wang, Ming-Yu Liu, Andrew Tao, Guilin Liu, Bryan Catanzaro, and Jan Kautz.  Few-shot video-to-video synthesis.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Wang et al. (2021) Tuanfeng Y Wang, Duygu Ceylan, Krishna Kumar Singh, and Niloy J Mitra.  Dance in the wild: Monocular human animation with neural dynamic appearance synthesis.  In _2021 International Conference on 3D Vision (3DV)_ , pp. 268–277. IEEE, 2021.
  * Wang et al. (2022) Yinhuai Wang, Jiwen Yu, and Jian Zhang.  Zero-shot image restoration using denoising diffusion null-space model.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Wang et al. (2004) Zhou Wang, Alan C Bovik, Hamid R Sheikh, and Eero P Simoncelli.  Image quality assessment: from error visibility to structural similarity.  _IEEE transactions on image processing_ , 13(4):600–612, 2004.
  * Watson et al. (2022) Daniel Watson, William Chan, Ricardo Martin Brualla, Jonathan Ho, Andrea Tagliasacchi, and Mohammad Norouzi.  Novel view synthesis with diffusion models.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Yang et al. (2023) Ruihan Yang, Prakhar Srivastava, and Stephan Mandt.  Diffusion probabilistic modeling for video generation.  _Entropy_ , 25(10):1469, 2023.
  * Yoon et al. (2022) Jae Shin Yoon, Duygu Ceylan, Tuanfeng Y Wang, Jingwan Lu, Jimei Yang, Zhixin Shu, and Hyun Soo Park.  Learning motion-dependent appearance for high-fidelity rendering of dynamic humans from a single camera.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 3407–3417, 2022.
  * Zablotskaia et al. (2019) Polina Zablotskaia, Aliaksandr Siarohin, Bo Zhao, and Leonid Sigal.  Dwnet: Dense warp-based network for pose-guided human video generation.  _arXiv preprint arXiv:1910.09139_ , 2019.
  * Zhang et al. (2018) Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang.  The unreasonable effectiveness of deep features as a perceptual metric.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 586–595, 2018.
  * Zhao & Zhang (2022) Jian Zhao and Hui Zhang.  Thin-plate spline motion model for image animation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 3657–3666, 2022.
  * Zhou et al. (2022) Daquan Zhou, Weimin Wang, Hanshu Yan, Weiwei Lv, Yizhe Zhu, and Jiashi Feng.  Magicvideo: Efficient video generation with latent diffusion models.  _arXiv preprint arXiv:2211.11018_ , 2022.
  * Zhou et al. (2019) Yipin Zhou, Zhaowen Wang, Chen Fang, Trung Bui, and Tamara Berg.  Dance dance generation: Motion transfer for internet videos.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops_ , pp. 0–0, 2019.

##  Appendix A Bidirectional Recursive Sampling

To effectively utilize our Bidirectional Temporal Diffusion Model (BTDM)
during the inference stage, we have employed a bidirectional recursive
sampling method, which proceeds as follows.

Algorithm 1 Bidirectional Recursive Sampling

Input: Initial noisy inputs $Y^{k}=\\{y_{1}^{k},...,y_{t}^{k}\\}$, driven pose
sequence $\mathcal{S}=\\{s_{1},...,s_{T}\\}$.

Output: Denoised animation $Y^{0}=\\{y_{1}^{0},...,y_{t}^{0}\\}$

for $k=K-1$ to $0$ step $-1$ do

if $K-k$ is odd then

Direction: Forward

for $t=1$ to $T$ do

$y_{t}^{k-1}=f_{\theta}(y_{t}^{k},y_{t-1}^{k},\lambda(k),s_{t},d_{f})$

end for

else

Direction: Backward

for $t=T$ to $1$ step $-1$ do

$y_{t-1}^{k-1}=f_{\theta}(y_{t-1}^{k},y_{t}^{k},\lambda(k),s_{t-1},d_{b})$

end for

end if

end for

Although it’s possible to reverse the entire sequence (starting in the
backward direction and then moving to the forward, followed by backward
again), we observed no significant differences in the outcomes between these
two cases.

##  Appendix B Implementation Details

###  B.1 Single image animation

Our method is trained at a resolution of 256x256, similar to all other
methods. We generates 64x64 animations via the BTU-Net, which are subsequently
upscaled to 256x256 using the SR3 Saharia et al. (2022b).We trained both the
BTU-Net and SR3 from scratch on the entire training dataset, for 50k and 100k
iterations with a batch size of 32, respectively. We set the denoising step to
$K=1000$ and the learning rate to 1e-5. During testing, we fine-tune model
with test appearance condition for 300 iterations with a learning rate of
1e-5. It should be noted that we employ $K=50$ at test time for expedited
generation.

###  B.2 Person specific animation

The training settings for the BTU-Net and SR3 Saharia et al. (2022b) are
identical to those used in the Single image animation setup, with the
exception that both the BTU-Net and SR3 Saharia et al. (2022b) are trained for
100 epochs each without fine-tuning.

###  B.3 BTU-Net architecture

The detailed structural information of the BTU-Net’s layers is illustrated in
Figure 8. Due to the complexity of the arrows, the input directions for
$E_{a}$ and $E_{p}$ have been omitted. Directions are provided in Figure 4 of
main manuscript. The notation ’$\times digit$’ below the dashed block
indicates how many times that block structure is repeated.

Figure 8: Architecture of BTU-Net.

###  B.4 Training and Inference Speed Analysis

In particular, training the BTU-Net and SR3 models using the UBC fashion
dataset requires 15 and 30 epochs, respectively, on a setup of four A100 GPUs,
completed within 67 hours. Fine-tuning these models for 300 iterations takes
approximately 210 seconds. During inference, processing each frame takes
roughly 1.4 to 1.9 seconds on a single A100 GPU.

##  Appendix C Ablation Study

###  C.1 Comparison of Bidirectional and Unidirectional Approaches

Figure 9: Qualitative comparison of Bidirectional and Unidirectional methods.

Figure 9 demonstrates the qualitative results of bidirectional and
unidirectional temporal training via our BTU-Net. The unidirectional approach
struggles to generate images fitting the pose condition, tending to replicate
the texture of the front image input as the condition instead. Unlike the
unidirectional approach, the bidirectional model successfully creates images
that meet the pose condition.

Figure 10: Quantitative comparison of the number of images used for fine-
tuning. ”Graphic” and ”UBC” notates graphic simulated data and UBC fashion
data results respectively.

###  C.2 Number of Images for Fine-Tuning

We also evaluate the performance depending on the number of images used for
fine-tuning. The performance comparison results are shown in Figure 10 and
Figure 11. As the number of images used for fine-tuning increases, performance
improves across various metrics. Notably, the trend between the increase in
image count and metric scores is not linear but shows signs of convergence.

Figure 11: Qualitative comparison of the number of images used for fine-
tuning.

###  C.3 User Study

We conduct quantitative results of an user study in which people evaluated
videos generated by our method and baseline methods. A total of 42
participants took part in this study, which involved tasks for single image
animation and person specific animation. Each evaluation required participants
to watch comparison videos at least twice and make selections based on two
questions: “Which video preserves the identity best?” and “Which video looks
most realistic to you?”. For the person specific animation task, the
experiment was conducted excluding the first question. As shown in Figure 12,
it can be seen that our BTMD results are much more realistic and maintain
identity better when evaluated by people, compared to other baseline methods.

Figure 12:  Quantitative result of human evaluations. Graphs (a) and (b)
represent the results for the single image animation task, showing the
proportion of choices made for two different questions. Graph (c) shows the
results for the person-specific animation task.

###  C.4 Unconditional Animation Generation

We demonstrate that our method can generate human animations featuring diverse
clothing styles and identities, even without any image conditions. Results
from unconditional generation experiments on both datasets are illustrated in
Figures 13 and 14.

Figure 13: Sample sequences from unconditional generation on UBC fashion data.
Figure 14: Samples from unconditional generation on Graphic simulated data.

##  Appendix D Graphic simulated dataset

Graphic simulated dataset is comprised of approximately 98,000 images, each
rendered at a resolution of 512x512. These images illustrate various dynamic
movements (such as dance, exercise, etc.) of 3D human models with a total of
99 different appearances. The 3D human models in this dataset are created
using Character Creator 4 Reallusion (a), and we simulate the soft cloth
motion in iClone8 Reallusion (b). Mixamo Adobe  human motions, are exported as
an Alembic Pictures  file. For realistic rendering, we employ Ray Tracing
Texel (RTX) rendering and the Nvidia Omniverse Nvidia  as the rendering tool.
Figure 15 shows a few samples from our graphically simulated data.

Figure 15: Samples of Graphic Simulation Dataset

##  Appendix E More visual results

###  E.1 Single Image animation

Additional visual results conducted with graphic simulated and UBC fashion
data for the single image animation task are shown in Figures 17 and 18.

###  E.2 Person-specific animation

For a fair comparison evaluation in the person-specific human animation task,
we evaluate the results using only the foreground. However, our method is
capable of background synthesis, and the visual results are shown in Figure
16.

Figure 16:  Samples from person-specific animation results with background.
Figure 17:  More single image animation results on Graphic simulated data.
Figure 18:  More single image animation results on UBC fashion data.


# Scalable Multiple Patterning Layout Decomposition Implemented by a
Distribution Evolutionary Algorithm 111This work was supported in part by the
National Key R& D Program of China (2021ZD0114600).

Yu Chen<EMAIL_ADDRESS>Yongjian Xu<EMAIL_ADDRESS>Ning Xu
<EMAIL_ADDRESS>
###### Abstract

As the feature size of semiconductor technology shrinks to 10 nm and beyond,
the multiple patterning lithography (MPL) attracts more attention from the
industry. In this paper, we model the layout decomposition of MPL as a
generalized graph coloring problem, which is addressed by a distribution
evolutionary algorithm based on a population of probabilistic model (DEA-PPM).
DEA-PPM can strike a balance between decomposition results and running time,
being scalable for varied settings of mask number and lithography resolution.
Due to its robustness of decomposition results, this could be an alternative
technique for multiple patterning layout decomposition in next-generation
technology nodes.

###### keywords:

multiple patterning lithography , layout decomposition , distribution
evolutionary algorithm

††journal:

##  1 Introduction

Multiple patterning lithography (MPL) improves the resolution limit of
existing lithography technologies, which could then meet the challenge of
further decrease of feature size for the next-generation technology nodes [1].
Given a layout specified by features in polygonal shapes, a layout graph (LG)
is an undirected graph whose nodes are the given layout’s features and where
an edge exists if and only if two polygonal shapes are beyond the lithography
resolution limit [2]. Multiple patterning layout decomposition (MPLD)
partitions a layout into several sections (masks), which is then modelled as a
graph coloring problem (GCP).

The GCP can be generally formulated as an integer optimization problem, and a
variety of integer linear programming (ILP) methods have been developed to
address the MPLD problem [3, 4, 5, 6]. Since the GCP is NP-complete, the ILP
methods cannot decompose large-scale layouts efficiently, and it was relaxed
to a semidefinite programming (SDP) [7] problem or a linear programming (LP)
problem [8]. Although the SDP and LP methods leads to scalability of MPLD to
large-scale cases, additional repair processes are needed to get the feasible
solutions of GCP, and the relaxation would mathematically lead to solutions
different from those of the original MPLD problem. Accordinly, the MPLD
problem was also addressed by heuristics [9, 10, 11, 12, 13], and some layout
decomposition works based on hybrid lithography have been investigated [14,
15].

According to the number of colors (masks), MPLD problems can be categorized as
the double pattering layout decomposition (DPLD) problem [16, 17, 18, 19, 20],
the triple pattering layout decomposition (TPLD) problem [21, 22, 23, 24, 25,
26, 27] and the quadruple pattering layout decomposition (QPLD) problem [28],
etc. Because the uncolorable modules for varied settings of color number
contain different connection topologies, most of the algorithms for MPLD
problems are not scalable for varied settings of color number. Yu and Pan [28]
proposed an SDP model for QPLD, where extra color assignment strategies are
introduced, and the proposed algorithm could be applicable to a $k$ patterning
layout decomposition problem with $k\geq 4$. Lin _et al,_ [29] proposed a new
and effective algorithm for TPLD and QPLD. By utilizing the features in the
polyhedron space of the feasible set, the ILP formulation is approximated by
the LP relaxation. Jiang and Chang [30] modelled the MPLD problem as an exact
cover problem to construct a fast and exact MPLD framework based on augmented
dancing links, which can consider the basic and complex coloring rules
simultaneously, can maintain density balancing, and can handle quadruple
patterning and beyond.

Recently, Li _et al._ [31, 32] proposed an open source layout decomposer named
as the _OpenMPL_ , where a general framework of MPLD is developed for varied
settings of mask number and several alternative optimization schemes including
the ILP and the SDP. Although _OpenMPL_ incorporates several simplification
strategies of the layout graph, the ILP algorithm still suffers from high
computational complexity and the solution of SDP is of low quality as usual.
In order to develop a scalable MPLD framework that strikes a good balance
between the running time and the solution quality, we propose to address it
via a distribution evolutionary algorithm based on a population of probability
distribution (DEA-PPM) [33], which is based on a novel probability model
updated by an orthogonal transformation and a gradual renewal strategy of the
distribution model. Meanwhile, the solution space is exploited by deploying a
related solution population refined by a tabu search (TS). As a result, the
DEA-PPM relying on small populations is expected to achieve robust results on
varied settings of the MPLD problem.

The remainder of this paper is organized as follows. Section 2 briefly
introduces the framework of _OpenMPL_. In Section 3, the details of DEA-PPM
are presented, and Section 4 verifies the competitiveness of DEA-PPM by
experimental results. Finally, we conclude the work in Section 5.

##  2 Multiple Patterning Layout Decomposition based on the OpenMPL

###  2.1 The Multiple Patterning Layout Decomposition Problem

To address the MPLD problem,the layout is represented by a decomposition graph
(DG) consisting of a set of nodes $V$ and two sets of edges, $CE$ and $SE$,
which contain the conflicting edges and stitch edges, respectively [34].
Accordingly, the goal of MPLD is to assign nodes of $V$ with $k$ colors,
trying to achieve a nice trade-off between the numbers of conflict and stitch,
respectively defined by

$c_{uv}=\begin{cases}&\text{1}\quad\mbox{if }(u,v)\in CE,\\\
&\text{0}\quad\mbox{otherwise,}\end{cases}$ (1)

and

$s_{uv}=\begin{cases}&\text{1}\quad\mbox{if }(u,v)\in SE,\\\
&\text{0}\quad\mbox{otherwise.}\end{cases}$ (2)

Then, minimization of conflicts and stitches can be formulated as

$min\quad f(\mathbf{x})=\sum_{\left(u,v\right)\in
CE}c_{uv}+\alpha\times\sum_{\left(u,v\right)\in SE}s_{uv},$ (3)

where $\alpha$ is the weight parameter, set as $0.1$ in this paper [32]. For
cases $k=2,3,4$, problem (3) corresponds to the DPLD problem, the TPLD problem
and the QPLD problem, respectively.

###  2.2 Framework of the OpenMPL

As presented in _OpenMPL_ [31, 32], the work flow of MPLD starts with
generation of the decompositon graph $G$. Then, size of graph $G$ is reduced
by the graph simplification operations, and candidate stitches are inserted to
get a modified conflicting graph $G^{\prime}$. Before addressing the layout
decomposition, $G^{\prime}$ is further simplified to a reduced graph
$G^{\prime\prime}$. Establishing an optimization model for $G^{\prime\prime}$,
one can employ a selected optimization algorithm to get the colored graph
$G^{\prime\prime}$. At last, the decomposition result of layout can be
obtained by recovering the coloring result of $G^{\prime\prime}$ to that of
the original conflicting graph $G$. Details of the framework of _OpenMPL_ are
referred to [31, 32].

_OpenMPL_ incorporates an ILP approach, an SDP approach and a flexible exact
cover-based approach as three alternative routines of MPLD. To improve the
efficiency of layout decomposition, we proposed to address it by a
distribution evolutionary algorithm based on a population of probability
models (DEA-PPM) [33], and get the work flow of layout decomposition
illustrated in Fig. 1.

Figure 1: The workflow of layout decomposition based on the _OpenMPL_.

##  3 A Distribution Evolutionary Algorithm Based on a Population of
Probability Model

###  3.1 The framework of DEA-PPM

Input: $G=(V,E)$, color number $k$

Output: $\mathbf{x}^{*}_{G}$

1

2initialize $\mathbf{Q}(0)$;

3 sample $\mathbf{Q}(0)$ to generate $\mathbf{P}(0)$; $/*$ _uinform
initialization_ $*/$

4

5denote the optimal solution in $\mathbf{P}(0)$ as $\mathbf{x}^{*}_{G}$;

6 $\mathbf{p}_{1}=\mathbf{x}^{*}_{G}$, $\mathbf{p}_{2}=\mathbf{x}^{*}_{G}$;

7 $t\leftarrow 1$;

8

9while  _termination-condition 1 is not satisfied_ do

10 $\mathbf{Q}^{\prime}(t)=OrthExpQ(\mathbf{Q}(t-1),\mathbf{P}(t-1))$; $/*$
_orthogonal exploration_ $*/$

11 $\mathbf{P}^{\prime}(t)=SampleP(\mathbf{Q}^{\prime}(t),\mathbf{P}(t-1)$;
$/*$ _sampling with inheritance_ $*/$

12
$(\mathbf{P}(t),\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{x}^{*}_{G})=RefineP(\mathbf{P}^{\prime}(t),\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{x}^{*}_{G})$;

13 $/*$ _refinement of the solution population_ $*/$

14

15
$\mathbf{Q}(t)=RefineQ(\mathbf{P}^{\prime}(t),\mathbf{P}(t),\mathbf{Q}^{\prime}(t))$;
$/*$ _refinement of the distribution population_ $*/$

16 $t\leftarrow t+1$;

17

18 end while

19

Algorithm 1 The framework of DEA-PPM

The framework of DEA-PPM for GCPs is presented in Algorithm 1 [33]. It is
implemented based on a distribution population
$\mathbf{Q}(t)=(\mathbf{q}^{[1]}(t),\dots,\mathbf{q}^{[np]}(t))$ and a
solution population
$\mathbf{P}(t)=(\mathbf{x}^{[1]}(t),\dots,\mathbf{x}^{[np]}(t))$, where
$\mathbf{x}^{[i]}(t)$ corresponds to $\mathbf{q}^{[i]}(t)$ one by one for all
$i\in\\{1,\dots,np\\}$. For $k$-colroing of a decompostion graph $G$, DEA-PPM
first initializes the distribution population $\mathbf{Q}(0)$ and the solution
population $\mathbf{P}(0)$, and color $G$ by the iterative loop illustrated by
Lines 6-12 of Algorithm 1.

The iterative loop attempts to obtain the optimal $k$-coloring assignment of
$G$ by simultaneously evolving the distribution population $\mathbf{Q}(t)$ and
the solution population $\mathbf{P}(t)$. In order to obtain the enhanced
global exploration, it first performs orthogonal exploration on
$\mathbf{Q}(t)$ to obtain $\mathbf{Q}^{\prime}(t)$. Then, it generates an
intermediate solution population $\mathbf{P}^{\prime}(t)$ and performs a
refinement process on $\mathbf{P}^{\prime}(t)$ to obtain $\mathbf{P}(t+1)$.

Additionally, $\mathbf{Q}^{\prime}(t)$ is refined to obtain $\mathbf{Q}(t+1)$,
and the contents of the loop body are repeatedly executed, updating
$\mathbf{x}^{*}_{G}$ until termination condition 1 is met. While numbers of
conflicts and stitches are optimized to zero or the maximum number of
iterations is reached, the iteration process is ceased and it outputs the
corresponding $k$-coloring assignment of $G$. Details of the DEA-PPM is
referred to Ref. [33].

###  3.2 Refinement of the solution population

Because the MPLD problem minimizes the number of stitches as well as that of
the conflicts, model (3) of MPLD is slightly different with that of the GCP.
Accordingly, the refinement process of DEA-PPM, presented in Algorithm 2 is
slightly modified to accommodate the MPLD problem well.

1

Input: $\mathbf{P},\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{x}^{*}_{G}$

Output: $\mathbf{P},\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{x}^{*}_{G}$

2 $iter\leftarrow 0$, $iter\\_stag\leftarrow 0$;

3 $\mathbf{c}_{1}=\mathbf{x}^{*}_{G^{\prime}}$;

4 $w_{2}\leftarrow 0$

5while  _$iter\\_stag <6$_ do

6 $\mathbf{P}^{\prime}=MGPX(\mathbf{P},\mathbf{p}_{1},\mathbf{p}_{2})$;

7 $\mathbf{P}^{\prime}=Tabu(\mathbf{P}^{\prime})$;

8 record the best solution in $\mathbf{P}^{\prime}$ as $\mathbf{b}$;

9 if  _$f(\mathbf{b}) <f(\mathbf{p}_{1})$_ then

10 $w_{2}=1$;

11 $iter\\_stag=0$;

12 $\mathbf{c}_{1}=\mathbf{p}_{1},\mathbf{p}_{1}=\mathbf{b}$;

13 else

14 $iter\\_stag=iter\\_stag+1$;

15 end if

16

17 if  _$f(\mathbf{b}) <f(\mathbf{x}^{*}_{G^{\prime}})$_ then

18 $\mathbf{x}^{*}_{G^{\prime}}=\mathbf{b}$;

19

20 end if

21

22 if  _$mod(iter,3)==0\ &\&w_{2}==1$_ then

23 $\mathbf{p}_{2}=\mathbf{c}_{1}$;

24 $w_{2}=0$;

25

26 end if

27 $\mathbf{P}=\mathbf{P}^{\prime}$;

28 $iter=iter+1$;

29

30 end while

31$\mathbf{P}^{\prime}=Tabu(\mathbf{P})$;

32 $\mathbf{p}_{1}=\mathbf{b}$;

Algorithm 2
$RefineP(\mathbf{P},\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{x}^{*}_{G})$

As presented in Algorithm 2, the iteration budget of _while_ loop is set as
$6$ in this research. Each iteration of the _while_ loop starts with a multi-
parent greedy partition crossover (MGPX) and a tailored tabu search (TS), and
ends with update of the solutions $\mathbf{p}_{1}$, $\mathbf{p}_{2}$ and
$\mathbf{x}^{*}_{G}$. The MGPX is referred to Ref. [33], and the TS process is
presented in Algorithm 3. The TS process for all $\mathbf{x}\in\mathbf{P}$
starts with initialization of the tabu list $\mathbf{T}$, which is a $k\times
n$ matrix where element $T_{jv}$ represents the tabu level of coloring vertex
$v$ with color $j$. Then, an iterative process is performed to improve the
quality of $\mathbf{x}$ and to update the tabu list $\mathbf{T}$.

Input: $\mathbf{P}$

Output: $\mathbf{P}$

1 for  _$\mathbf{x}\in\mathbf{P}$_ do

2 $count\leftarrow 0$;

3 $\mathbf{y}=\mathbf{x}$;

4 initialize the tabu list $\mathbf{T}$ to a $k\times n$ zero matrix;

5 while  _termination-condition 2 is not satisfied_ do

6 choose the best legal mutation $<v,i,j>$;

7 perform the $<v,i,j>$ in $\mathbf{y}$;

8 Update $T_{jv}$ of the tabu list $\mathbf{T}$;

9 if  _$f(\mathbf{y}) <f(\mathbf{x})$_ then

10 $\mathbf{x}=\mathbf{y}$;

11 end if

12 $count=count+1$;

13

14 end while

15

16 end for

Algorithm 3 $Tabu(\mathbf{P})$

Improvement of a solution $\mathbf{x}$ is achieved by the _promising_
mutations that generate promising solutions. For a vertex $v$ assigned with
color $i$, a random mutation $<v,i,j>$ ($j\neq i$) is performed to assign $v$
with color $j$. While $<v,i,j>$ is not forbidden by the tabu list
$\mathbf{T}$, it generates a candidate solution that would replace the
coloring scheme $\mathbf{x}$. To get solutions improved as far as possible,
the best promising mutation that contributes to the smallest numbers of
conflicts and stitches is employed to generate the promising solution
$\mathbf{y}$, by which the present solution $\mathbf{x}$ is updated if
$f(\mathbf{y})<f(\mathbf{x})$.

A random mutation $<v,i,j>$ is forbidden by the tabu list if the iteration
number $count$ is less than $T_{jv}$. If a solution $\mathbf{y}$ is generated
by implementing $<v,i,j>$, the corresponding element of $T$ is updated by

$T_{j,v}=count+0.6*(10*y_{c}+y_{s})+r,$

where $count$ is the iteration number of TS, $y_{c}$ is the number of
conflicts in $\mathbf{y}$, $y_{s}$ is the number of stitches in $\mathbf{y}$,
and $r$ is an integer randomly sampled in $\\{1,\dots,10\\}$.

The iteration of TS is repeated until _termination condition 2_ is satisfied,
that is, a solution without stitches and conflicts is obtained or the number
of iterations reaches the iteration budget $5*|V|$.

##  4 Experimental Results

Competitiveness of the proposed MPLD algorithm is validated by result
comparison for the ISCAS benchmark problems. The _OpenMPL_ decomposer is
implemented by C++ on a laptop equipped with Intel Core 1.10 GHz CPU and a
virtual Linux machine. By testing the performance of DEA-PPM on the ISCAS
benchmarks, we compare the results by the stitch numbers(‘st#’), the conflict
numbers(‘cn#’), the cost values(‘cost’) and the CPU running times(‘time’) of
ILP, SDP and DEA-PPM. Because DEA-PPM is a stochastic optimization algorithm,
the reported results are average values of 10 independent runs, and we also
investigate the standard deviations of results to demonstrate its robustness.
The scalability of DEA-PPM is validated by varied settings of both the number
of masks and the minimum coloring space $min_{cs}$. To perform a fair
comparison, the _OpenMPL_ decomposer is run in the single-thread mode. An
illustration of the decomposition results is presented for DEA-PPM in Fig. 2.

(a) The result of TPLD. (b) The result of QPLD.

Figure 2: Decomposition results of the layout benchmark _C432_ obtained by the
DEA-PPM.

###  4.1 Comparison for the TPLD problem with $min_{cs}=120/100$nm

As presented in [32], _OpenMPL_ works well for TPLD of the ISCAS benchmarks,
where the minimum coloring spacing $min_{cs}$ is set as _120nm_ for the
benchmarks _C432-C7552_ and _100nm_ for the benchmarks _S1488-S15850_. Then,
we compare the decomposition results of DEA-PPM with those of the ILP and the
SDP.

The decomposition results of three algorithms are presented in Tab. 1. For the
small value of $min_{cs}$, vertexes of the decomposition graph would be
incident to less edges. The results demonstrate that the proposed DEA-PPM, as
a stochastic optimization algorithm, can always achieve the same results as
ILP with less running time. Because the SDP method addresses a continuously
relaxed problem of model (3), it runs faster than ILP and DEA-PPM, but cannot
always converge to the global optimal solutions at all time. Consequently, the
decomposition results obtained by the SDP method are generally the same as or
worse than those of ILP and DEA-PPM.

It is surprising that the standard deviation of cost is zero, which shows that
all independent runs of DEA-PPM converge to the global optimal solution of
model (3). Furthermore, the standard deviations of running time are collected
in Fig. 3. It is demonstrated that the standard deviation of running time is
ignorable for most of the benchmark layouts, except that the standard
deviations of running time are about a few seconds for the cases _S35392_ ,
_S38584_ and _S15850_.

Table 1: Result comparison for the TPLD with $min_{cs}=120/100nm$

Circuit | ILP | SDP | DEA-PPM
---|---|---|---
st# | cn# | cost | time(s) | st# | cn# | cost | time(s) | st# | cn# | cost | time(s)
C432 | 4 | 0 | 0.4 | 0.38 | 4 | 0 | 0.4 | 0.09 | 4 | 0 | 0.4 | 0.30
C499 | 0 | 0 | 0 | 0.31 | 0 | 0 | 0 | 0.13 | 0 | 0 | 0 | 0.25
C880 | 7 | 0 | 0.7 | 0.52 | 7 | 0 | 0.7 | 0.14 | 7 | 0 | 0.7 | 0.46
C1355 | 3 | 0 | 0.3 | 1.16 | 3 | 0 | 0.3 | 0.17 | 3 | 0 | 0.3 | 0.59
C1908 | 1 | 0 | 0.1 | 0.6 | 1 | 0 | 0.1 | 0.28 | 1 | 0 | 0.1 | 0.52
C2670 | 6 | 0 | 0.6 | 1.29 | 6 | 0 | 0.6 | 0.51 | 6 | 0 | 0.6 | 0.60
C3540 | 8 | 1 | 1.8 | 2.31 | 8 | 1 | 1.8 | 0.82 | 8 | 1 | 1.8 | 1.59
C5315 | 9 | 0 | 0.9 | 2.02 | 9 | 0 | 0.9 | 1.49 | 9 | 0 | 0.9 | 1.84
C6288 | 205 | 1 | 21.5 | 12.57 | 203 | 7 | 27.3 | 4.32 | 205 | 1 | 21.5 | 10.48
C7552 | 23 | 0 | 2.3 | 6.97 | 23 | 0 | 2.3 | 1.38 | 23 | 0 | 2.3 | 3.27
S1488 | 2 | 0 | 0.2 | 0.58 | 2 | 0 | 0.2 | 0.31 | 2 | 0 | 0.2 | 0.42
S38417 | 54 | 19 | 24.4 | 17.62 | 46 | 27 | 31.6 | 9.31 | 54 | 19 | 24.4 | 16.13
S35932 | 40 | 44 | 48 | 43.49 | 20 | 64 | 66 | 27.5 | 40 | 44 | 48 | 32.18
S38584 | 116 | 36 | 47.6 | 41.37 | 105 | 48 | 58.5 | 28.37 | 116 | 36 | 47.6 | 35.83
S15850 | 97 | 34 | 43.7 | 35.53 | 83 | 48 | 56.3 | 22.62 | 97 | 34 | 43.7 | 33.68

Figure 3: Standard deviations of running time for the TPLD problem with
$min_{cs}=120/100nm$.

###  4.2 Comparison for the TPLD problem with $min_{cs}=160$nm

To demonstrate the scalability of our proposed method for various lithography
technologies, we investigate the TPLD of ISCAS benchmarks by setting the
minimum coloring spacing $min_{cs}=160nm$. Because the lithography resolution
is lower, there could be more conflicting edges in the layout graph, and more
stitches would be inserted to get the decomposition graph colorable.
Accordingly, the community structure of the decomposition graph could be
fuzzier, and decomposition of the layouts is more challenging.

The experimental results collected in Table 2 show that DEA-PPM can deal well
with the low-resolution TPLD problem. Compared with the ILP, DEA-PPM
contributes to a decrease of more than one order of magnitude of the running
time at the expense of a bit increase of the cost values. Meanwhile, the cost
values optimized by DEA-PPM are much smaller than the results of SDP, while
the running time of DEA-PPM is a bit greater that of SDP. The histograms
illustrated in Fig. 4 show that the standard deviations of cost values are
smaller than $3$, and those of running time are not more than $10$ seconds.
Accordingly, DEA-PPM is also robust when applied to address the TPLD problem
with $min_{cs}=160nm$.

Table 2: Result comparison for the TPLD with $min_{cs}=160nm$

Circuit | ILP | SDP | DEA-PPM
---|---|---|---
st# | cn# | cost | time(s) | st# | cn# | cost | time(s) | st# | cn# | cost | time(s)
C432 | 17 | 76 | 77.7 | 113.02 | 19 | 80 | 81.9 | 5.29 | 17.1 | 76.9 | 78.61 | 6.92
C499 | 48 | 278 | 282.8 | 339.77 | 48 | 279 | 283.8 | 10.48 | 48 | 278.2 | 283 | 16.40
C880 | 123 | 103 | 115.3 | 244.9 | 113 | 115 | 126.3 | 9.26 | 122.4 | 103.7 | 115.94 | 12.06
C1355 | 116 | 114 | 125.6 | 356.94 | 109 | 122 | 132.9 | 21.59 | 118.3 | 113.9 | 125.73 | 17.26
C1908 | 109 | 150 | 160.9 | 136.82 | 100 | 162 | 172 | 12.18 | 106.2 | 150.7 | 161.32 | 16.95
C2670 | 369 | 354 | 390.9 | 3506.45 | 358 | 386 | 421.8 | 35.71 | 369.4 | 357.2 | 394.14 | 41.05
C3540 | 506 | 334 | 384.6 | 368.65 | 482 | 362 | 410.2 | 25.08 | 504 | 336.4 | 386.8 | 40.27
C5315 | 487 | 779 | 827.7 | 975.58 | 467 | 819 | 865.7 | 42.6 | 487 | 786.2 | 834.9 | 71.04
C6288 | 384 | 616 | 654.4 | 878.71 | 366 | 653 | 689.6 | 53.76 | 386.1 | 622.3 | 660.91 | 58.47
C7552 | 858 | 843 | 928.8 | 3376.73 | 808 | 933 | 1013.8 | 68.12 | 851.1 | 850.6 | 935.71 | 89.28

(a) Standard deviations of cost values. (b) Standard deviations of running
time.

Figure 4: Standard deviations of results obtained by the DEA-PPM for the TPLD
problem with $min_{cs}=160nm$.

###  4.3 Comparison for the QPLD problem with $min_{cs}=200nm$

Besides varied settings of the lithography resolution, we further test the
scalability of DEA-PPM by investigating the QPLD problem, where the minimum
coloring spacing is set as $200nm$ for 10 ISCAS benchmarks. The test results
are listed in Table 3, and Fig. 5 illustrates the standard deviations of both
cost values and running time for 10 independent runs. Since the ILP cannot
address the _C6288_ benchmark in 1 hour, we denote the corresponding results
by ‘-’.

The obtained cost values of DEA-PPM are generally better than that of SDP, and
its running time is much shorter than that of ILP. It is surprising that
compared with the ILP, DEA-PPM achieves better cost values on cases _C432_ ,
_C6288_ and _C7552_ with much shorter running time. Although the running time
of DEA-PPM is a bit longer than that of SDP, the obtained better cost values
still demonstrate its competitiveness on the QPLD problem. Fig. 5 demonstrates
that the standard deviations of cost value is about $0.5$ for all $10$
benchmarks, and the running time varies with standard deviations less than $5$
seconds for most benchmarks except for _C3540_.

Table 3: Result comparison for the QPLD with $min_{cs}=200nm$

Circuit | ILP | SDP | DEA-PPM
---|---|---|---
st# | cn# | cost | time(s) | st# | cn# | cost | time(s) | st# | cn# | cost | time(s)
C432 | 4 | 14 | 14.4 | 61.38 | 4 | 12 | 12.4 | 1.61 | 4 | 13.6 | 14 | 1.79
C499 | 29 | 7 | 9.9 | 123.71 | 29 | 8 | 10.9 | 8.14 | 28.9 | 7.1 | 9.99 | 4.72
C880 | 4 | 6 | 6.4 | 4.1 | 4 | 7 | 7.4 | 0.58 | 4 | 6.5 | 6.9 | 1.36
C1355 | 4 | 12 | 12.4 | 13.44 | 4 | 12 | 12.4 | 1.41 | 4 | 12 | 12.4 | 1.65
C1908 | 10 | 24 | 25 | 50.42 | 10 | 24 | 25 | 3.94 | 10 | 24 | 25 | 3.98
C2670 | 11 | 24 | 25.1 | 225.96 | 12 | 25 | 26.2 | 5.98 | 11 | 24 | 25.1 | 4.25
C3540 | 18 | 39 | 40.8 | 49.94 | 20 | 43 | 45 | 4.26 | 18 | 39 | 40.8 | 46.22
C5315 | 31 | 38 | 41.1 | 90.47 | 30 | 40 | 43 | 5.63 | 31 | 38 | 41.1 | 8.77
C6288 | - | - | - | - | 10 | 299 | 300 | 18.32 | 8.3 | 297.9 | 298.73 | 31.09
C7552 | 38 | 60 | 63.8 | 706.97 | 36 | 61 | 64.6 | 7.66 | 38 | 59.1 | 62.9 | 11.48

(a) Standard deviations of cost values. (b) Standard deviations of running
time.

Figure 5: Standard deviations of results obtained by the DEA-PPM for the QPLD
problem with $min_{cs}=200nm$.

##  5 Conclusion

To develop a scalable layout decomposition scheme adapted for a variety of
lithography resolution with different number of masks, we proposed to model
the huge-scale decomposition problem as an extended graph coloring problem,
which is addressed by a distribution evolutionary algorithm based on a
population of probability models (DEA-PPM).

Since the DEA-PPM employs a distribution evolution scheme assisted by the tabu
search, it is scalable to varied settings of the MPL layout decomposition
problem. Experimental results on ISCAS benchmarks demonstrate that DEA-PPM can
strike a good balance between the optimization results and the running time.
Despite that DEA-PPM is generally superior to ILP and inferior to SDP in terms
of running time, it can obtain for some benchmarks both smaller cost values
and less running time, which show that the proposed decomposition method is
competitive to the existing decomposition schemes.

Despite the stochastic nature of DEA-PPM, its tailored search strategies leads
to small standard deviations of decomposition results, which shows that the
proposed method could be an alternative method for the MPLD of layout.

## Acknowlegement

We thank Dr. Ning Li for his constructive suggestions to this work.

## References

  * [1] Y. Ma, X. Zeng, B. Yu, Methodologies for layout decomposition and mask optimization: A systematic review, 2017 IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC) (2017) 1–6.
  * [2] A. B. Kahng, C.-H. Park, X. Xu, H. Yao, Layout decomposition for double patterning lithography, in: 2008 IEEE/ACM International Conference on Computer-Aided Design, IEEE, 2008, pp. 465–472.
  * [3] B. Yu, K. Yuan, B. Zhang, D. Ding, D. Z. Pan, Layout decomposition for triple patterning lithography, 2011 IEEE/ACM International Conference on Computer-Aided Design (ICCAD) (2011) 1–8.
  * [4] B. Yu, S. Roy, J.-R. Gao, D. Z. Pan, Triple patterning lithography layout decomposition using end-cutting, Journal of Micro/Nanolithography, MEMS, and MOEMS 14 (2014).
  * [5] M. Y. Lin, Y.-L. Li, K.-W. Lin, Color balancing aware double patterning, 2017 International Conference on Applied System Innovation (ICASI) (2017) 284–287.
  * [6] X. Li, Z. Zhu, W. xing Zhu, Discrete relaxation method for triple patterning lithography layout decomposition, IEEE Transactions on Computers 66 (2017) 285–298.
  * [7] B. Yu, Y.-H. Lin, G. Luk-Pat, D. Ding, K. Lucas, D. Z. Pan, A high-performance triple patterning layout decomposer with balanced density, 2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD) (2013) 163–169.
  * [8] Y. Lin, X. Xu, B. Yu, R. Baldick, D. Z. Pan, Triple/quadruple patterning layout decomposition via linear programming and iterative rounding, Journal of Micro/Nanolithography, MEMS, and MOEMS 16 (2017).
  * [9] S.-Y. Fang, Y.-W. Chang, W.-Y. Chen, A novel layout decomposition algorithm for triple patterning lithography, DAC Design Automation Conference 2012 (2012) 1181–1186.
  * [10] J. Kuang, E. F. Y. Young, An efficient layout decomposition approach for triple patterning lithography, 2013 50th ACM/EDAC/IEEE Design Automation Conference (DAC) (2013) 1–6.
  * [11] Y. Zhang, W.-S. Luk, Y. Yang, H. Zhou, C. Yan, D. Z. Pan, X. Zeng, Layout decomposition with pairwise coloring and adaptive multi-start for triple patterning lithography, ACM Transactions on Design Automation of Electronic Systems (TODAES) 21 (2015) 1 – 25.
  * [12] X. Ke, L. V. Wen, S. Liu, Ant colony algorithm for layout decomposition in double/multiple patterning lithography, 2015 China Semiconductor Technology International Conference (2015) 1–3.
  * [13] K.-J. Chen, S.-Y. Fang, Printability enhancement with color balancing for multiple patterning lithography, IEEE Transactions on Emerging Topics in Computing 7 (2019) 244–252.
  * [14] Y. Yang, W.-S. Luk, H. Zhou, C. Yan, X. Zeng, D. Zhou, Layout decomposition co-optimization for hybrid e-beam and multiple patterning lithography, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 35 (2015) 1532–1545.
  * [15] X. Li, J. Li, H. Wu, Y.-C. Chen, Discrete relaxation method for hybrid e-beam and triple patterning lithography layout decomposition, Journal of Ambient Intelligence and Humanized Computing (2021) 1–11.
  * [16] K. Yuan, J.-S. Yang, D. Z. Pan, Double patterning layout decomposition for simultaneous conflict and stitch minimization, IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 29 (2) (2010) 185–196.  doi:10.1109/TCAD.2009.2035577.
  * [17] J.-S. Yang, K. Lu, M. Cho, K. Yuan, D. Z. Pan, A new graph-theoretic, multi-objective layout decomposition framework for double patterning lithography, in: 2010 15TH ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE (ASP-DAC 2010), Asia and South Pacific Design Automation Conference Proceedings, 2010, pp. 623+, 15th Asia and South Pacific Design Automation Conference, Taipei, TAIWAN, JAN 18-21, 2010.
  * [18] A. B. Kahng, C.-H. Park, X. Xu, H. Yao, Layout decomposition approaches for double patterning lithography, IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 29 (6) (2010) 939–952.  doi:10.1109/TCAD.2010.2048374.
  * [19] C.-H. Hsu, Y.-W. Chang, S. R. Nassif, Simultaneous layout migration and decomposition for double patterning technology, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 30 (2) (2011) 284–294.  doi:10.1109/TCAD.2010.2079990.
  * [20] W. Zhao, H. Yao, Y. Cai, S. Sinha, C. Chiang, Fast and scalable parallel layout decomposition in double patterning lithography, INTEGRATION-THE VLSI JOURNAL 47 (2) (2014) 175–183.  doi:10.1016/j.vlsi.2013.09.002.
  * [21] B. Yu, G. Garreton, D. Z. Pan, Layout compliance for triple patterning lithography: An iterative approach, in: P. Ackmann, N. Hayashi (Eds.), PHOTOMASK TECHNOLOGY 2014, Vol. 9235 of Proceedings of SPIE, SPIE; BACUS, 2014, conference on Photomask Technology, Monterey, CA, SEP 16-18, 2014.  doi:10.1117/12.2066034.
  * [22] S.-Y. Fang, Y.-W. Chang, W.-Y. Chen, A novel layout decomposition algorithm for triple patterning lithography, IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 33 (3) (2014) 397–408.  doi:10.1109/TCAD.2013.2288678.
  * [23] B. Yu, S. Roy, J.-R. Gao, D. Z. Pan, Triple patterning lithography layout decomposition using end-cutting, JOURNAL OF MICRO-NANOLITHOGRAPHY MEMS AND MOEMS 14 (1) (JAN 2015).  doi:10.1117/1.JMM.14.1.011002.
  * [24] B. Yu, K. Yuan, D. Ding, D. Z. Pan, Layout decomposition for triple patterning lithography, IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 34 (3) (2015) 433–446.  doi:10.1109/TCAD.2014.2387840.
  * [25] Y. Zhang, W.-S. Luk, Y. Yang, H. Zhou, C. Yan, D. Z. Pan, X. Zeng, Layout decomposition with pairwise coloring and adaptive multi-start for triple patterning lithography, ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS 21 (1) (NOV 2015).  doi:10.1145/2764904.
  * [26] X. Ke, H. Jiang, W. Lv, S. Liu, Native conflict awared layout decomposition in triple patterning lithography using bin-based library matching method, in: A. Erdmann, J. Kye (Eds.), OPTICAL MICROLITHOGRAPHY XXIX, Vol. 9780 of Proceedings of SPIE, SPIE; Cymer, 2016, conference on Optical Microlithography XXIX, San Jose, CA, FEB 23-25, 2016.  doi:10.1117/12.2219144.
  * [27] Y. Kohira, C. Kodama, T. Matsui, A. Takahashi, S. Nojima, S. Tanaka, Yield-aware mask assignment by positive semidefinite relaxation in triple patterning using cut process, JOURNAL OF MICRO-NANOLITHOGRAPHY MEMS AND MOEMS 15 (2) (APR 2016).  doi:10.1117/1.JMM.15.2.021207.
  * [28] B. Yu, D. Z. Pan, Layout decomposition for quadruple patterning lithography and beyond, 2014 51st ACM/EDAC/IEEE Design Automation Conference (DAC) (2014) 1–6.
  * [29] Y. Lin, X. Xu, B. Yu, R. Baldick, D. Z. Pan, Triple/quadruple patterning layout decomposition via linear programming and iterative rounding, JOURNAL OF MICRO-NANOLITHOGRAPHY MEMS AND MOEMS 16 (2) (APR 2017).  doi:10.1117/1.JMM.16.2.023507.
  * [30] I. Hui-Ru, H.-Y. Chang, Multiple patterning layout decomposition considering complex coloring rules and density balancing, IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 36 (12) (2017) 2080–2092.  doi:10.1109/TCAD.2017.2681068.
  * [31] W. Li, Y. Ma, Q. Sun, Y. Lin, I. H.-R. Jiang, B. Yu, D. Z. Pan, Openmpl: An open source layout decomposer: Invited paper, 2019 IEEE 13th International Conference on ASIC (ASICON) (2019) 1–4.
  * [32] W. Li, Y. Ma, Q. Sun, L. Zhang, Y. Lin, I. H.-R. Jiang, B. Yu, D. Z. Pan, Openmpl: An open-source layout decomposer, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 40 (11) (2021) 2331–2344.  doi:10.1109/TCAD.2020.3042175.
  * [33] Y. Xu, H. Cheng, Y. Chen, C. Xie, A distribution evolutionary algorithm for graph coloring, arXiv preprint arXiv:2203.15162 (2022).
  * [34] K. Yuan, D. Z. Pan, Wisdom: Wire spreading enhanced decomposition of masks in double patterning lithography, in: 2010 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), IEEE, 2010, pp. 32–38.