# rate-distortion optimization with alternative references for
UGC video compression

###### Abstract

User generated content (UGC) refers to videos that are uploaded by users and
shared over the Internet. UGC may have low quality due to noise and previous
compression. When re-encoding UGC for streaming or downloading, a traditional
video coding pipeline will perform rate-distortion (RD) optimization to choose
coding parameters. However, in the UGC video coding case, since the input is
not pristine, quality “saturation” (or even degradation) can be observed,
i.e., increased bitrate only leads to improved representation of coding
artifacts and noise present in the UGC input. In this paper, we study the
saturation problem in UGC compression, where the goal is to identify and avoid
during encoding, the coding parameters and rates that lead to quality
saturation. We proposed a geometric criterion for saturation detection that
works with rate-distortion optimization, and only requires a few frames from
the UGC video. In addition, we show how to combine the proposed saturation
detection method with existing video coding systems that implement rate-
distortion optimization for efficient compression of UGC videos.

Index Terms—  user generated content, video compression, rate-distortion
optimization, denoising, quality saturation

##  1 Introduction

Videos that are created by users and then uploaded to video sharing services
(e.g. YouTube) are commonly referred to as user generated content (UGC) [1].
Service providers re-encode UGC videos at multiple resolutions and quality
levels for streaming. The traditional video coding pipeline assumes the input
video is pristine and makes use of rate-distortion (RD) optimization to ensure
efficient bitrate allocation [2, 3]. However, when encoding UGC videos, which
may have low quality due to previous compression, a traditional RD
optimization (RDO) framework that uses the UGC input as reference will
allocate bitrate to preserve undesirable artifacts. To illustrate this idea
consider the example of Figure 1 where a previously compressed image is re-
encoded with JPEG and two no-reference image quality assessment metrics, NIQE
[4] and BRISQUE [5], are used to evaluate the perceptual quality of the re-
encoded image. As shown by 1(c) and 1(d), the perceptual quality does not
improve (i.e., it “saturates”) when the rate is $R\approx 1.25bpp$. While
perceptual quality saturates, mean-squared-error (MSE) continues to decrease
(1(b)), which suggests that additional rate is mostly helping represent coding
artifacts in the UGC. Thus for this specific UGC image, rate should not be
increased beyond $1.25bpp$.

Following [6], we define the UGC compression problem as: _Given an UGC signal
and a compression system (e.g., JPEG, H.264), choose coding parameters to
accurately represent the perceptually meaningful parts of the signal, while
avoiding allocating resources to encode compression artifacts and noise._
Recent approaches to choose coding parameters for UGC are based on no-
reference quality metrics and content quality classification approaches [5, 7,
8, 9, 10, 11, 12]. However, these strategies are out-of-the-loop (i.e., they
are applied before encoding or after decoding, as in the example from Figure
1), and usually require training on a large-scale dataset. In [6], we
addressed the UGC compression problem from an RD theoretic perspective, where
the signal to be encoded is noisy and distortion is computed with respect to
an unavailable pristine reference. Using the noisy source coding theorem [13,
14], we showed that a theoretically optimal UGC compression system applies an
optimal denoiser to the UGC video followed by optimal source coding of the
denoised UGC. For a practical UGC video compression system, we proposed using
off-the-shelf denoisers to compute a denoised UGC to be used as an alternative
reference for distortion computation. We showed that quality saturation
occurs, and proposed a method to detect it.

In this paper, we address several of the limitations of our previous approach
[6] and work towards developing a practical UGC compression system. While in
theory a denoised UGC should be used both as a reference and as a source, in
[6] it was only used as a reference. In this work, we provide further evidence
to support that choice. We show that there is little perceptual difference
between encoding the UGC and encoding the denoised UGC (see Section 3.1). In
addition, the RD curve from encoding denoised UGC does not have a MSE
saturation region, which makes it difficult to decide when to stop increasing
the bitrate. Finally, encoding a denoised UGC requires denoising the whole UGC
video which comes with a high computational cost, while the proposed UGC
compression approach only requires denoising a few video frames for saturation
detection. We also show that the saturation criterion in [6] does not always
work and depends on the denoising method. As an alternative, we propose a new
saturation detection criterion (Section 2.2). Our approach is more principled,
while also being more robust to the choice of denoiser. Finally, we propose a
low complexity saturation detection method for the whole video by performing
RDO with a simplified codec, and using only a subset of frames (Section 2.3).
Our method returns a _saturation parameter_ ($\lambda^{*}$) that controls the
RD trade-off and can be given as input to a traditional video coding system
that performs the actual encoding and RDO (see Figure 3). Our proposed method
serves as a practical plug-in module that can operate with any codec
implementing RDO.

(a)

(b)

(c)

(d)

Fig. 1:  An example of UGC compression problem. (a) A UGC image generated from
KADID-10k[15]. (b) Rate and distortion curve for encoding UGC. (c) and (d)
rate and quality of encoded UGC. NIQE and BRISQUE are two popular no-reference
quality metrics.

##  2 Quality saturation and RDO

In this section we describe our pipeline. We first introduce an elementary
inequality that relates various distortion metrics and use it to define a
saturation region. Then we describe the proposed UGC compression system that
performs RDO.

###  2.1 Geometric relation between different distortions

We consider a traditional video compression system that encodes the UGC video
$\mathbf{U}$ with parameters $\theta$, and produces a decoded UGC video
$\hat{\mathbf{U}}(\theta)$. For such a system, there exist a set of parameters
$\Theta=\\{\theta_{1},\theta_{2},\cdots\\}$, so that
$\lim_{k\rightarrow\infty}\|\mathbf{U}-\hat{\mathbf{U}}(\theta_{k})\|=0$, and
thus $\hat{\mathbf{U}}(\theta_{k})\rightarrow\mathbf{U}$, and the rate of the
encoded representation of $\hat{\mathbf{U}}(\theta_{k})$ increases with $k$.
Examples of $\theta_{k}$ include QP parameters used in H.264. A traditional
video coding system, would use the distortion
$\|\hat{\mathbf{U}}(\theta_{k})-\mathbf{U}\|^{2}$ to measure quality and
perform RDO. In [6] we proposed using
$\|\hat{\mathbf{U}}(\theta_{k})-\mathbf{Z}\|^{2}$ to compute distortion, where
$\mathbf{Z}$ is a de-noised signal obtained from $\mathbf{U}$. We showed
experimentally that the corresponding RD curve saturates at higher bitrates,
and $\|\hat{\mathbf{U}}(\theta_{k})-\mathbf{Z}\|^{2}$ converges to
$\|\mathbf{U}-\mathbf{Z}\|^{2}$. We can formalize this observation as follows.
Using the identity
$\|\mathbf{x}-\mathbf{z}\|^{2}-\|\mathbf{y}-\mathbf{z}\|^{2}=\|\mathbf{x}-\mathbf{y}\|^{2}+2\langle\mathbf{x}-\mathbf{y},\mathbf{y}-\mathbf{z}\rangle$,
valid for any $\mathbf{x},\mathbf{y},\mathbf{z}$, and the triangular
inequality, the distortions are related as follows:

$\displaystyle\left|\|\hat{\mathbf{U}}(\theta)-\mathbf{Z}\|^{2}-\|\mathbf{U}-\mathbf{Z}\|^{2}\right|\leq$
(1)
$\displaystyle\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|^{2}+2\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|\|\mathbf{U}-\mathbf{Z}\|$
(2)

for any reference $\mathbf{Z}$ and any coding parameter $\theta\in\Theta$.
From (2), we can see that convergence occurs faster at low rates than at high
rates, and detecting the transition from one regime to the other will be
helpful to detect saturation. More precisely, we observe:

High bitrate, low distortion regime. When
$\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|$ is small, then
$|\|\hat{\mathbf{U}}(\theta)-\mathbf{Z}\|^{2}-\|\mathbf{U}-\mathbf{Z}\|^{2}|=\mathcal{O}(\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|)$.
In this region, distortion decays more slowly and thus quality has saturated.

Low bitrate, high distortion regime. When
$\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|$ is larger, then
$|\|\hat{\mathbf{U}}(\theta)-\mathbf{Z}\|^{2}-\|\mathbf{U}-\mathbf{Z}\|^{2}|=\mathcal{O}(\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|^{2})$.
In this region, distortion decays at the same rate as a traditional system.

Transition point. Transition from quadratic decay (low bitrates) to linear
decay (higher bitrates) occurs approximately when both terms on the right side
of (2) are equal, i.e.,
$\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|=2\|\mathbf{U}-\mathbf{Z}\|$.

Fig. 2: An illustration for our proposed saturation detection method. Each
node represents a position of $\hat{\mathbf{U}}(\theta)$. The length of red
line is the minimal distortion which can be achieved by $\theta=b$.

###  2.2 Saturation region detection

We now use the results from the previous section to detect saturation, i.e.,
when $\hat{\mathbf{U}}(\theta)$ is sufficiently close to $\mathbf{U}$. From
(1) we see that in the saturation region, distortion decreases more slowly.
Thus our goal will be to identify the transition point from quadratic to
linear behavior. Without loss of generality, suppose the coding parameter
$\theta$ belongs to a closed interval $\Theta=[a,b]$, with a higher $\theta$
resulting in higher bitrate and lower distortion. We define the saturation
region $[\theta^{*},b]$ as the largest interval (the one with the smallest
$\theta^{*}$) such that:

$\left|\|\hat{\mathbf{U}}(\theta)-\mathbf{Z}\|^{2}-\|\mathbf{U}-\mathbf{Z}\|^{2}\right|\leq\|\hat{\mathbf{U}}(b)-\mathbf{U}\|^{2},\forall\theta\in[\theta^{*},b].$
(3)

We say that $\theta^{*}$ is the saturation onset or saturation point. Note
that

$\displaystyle\|\hat{\mathbf{U}}(b)-\mathbf{U}\|^{2}$
$\displaystyle\leq\|\hat{\mathbf{U}}(b)-\mathbf{U}\|^{2}+2\|\hat{\mathbf{U}}(b)-\mathbf{U}\|\|\mathbf{U}-\mathbf{Z}\|$
(4)
$\displaystyle\leq\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|^{2}+2\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|\|\mathbf{U}-\mathbf{Z}\|$
(5)

$\forall\theta\in[a,b]$, thus (3) is stronger than (2). The region (3) is
illustrated in Figure 2. Each circle centered at $\mathbf{U}$ has radius
$\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|$, representing possible positions of
$\hat{\mathbf{U}}(\theta)$. The radius of the smallest circle is
$\|\hat{\mathbf{U}}(b)-\mathbf{U}\|$. The saturation region is delimited by
two circles centered at $\mathbf{Z}$. The largest and smallest circles have
equation

$\displaystyle\|\hat{\mathbf{U}}(\theta)-\mathbf{Z}\|^{2}$
$\displaystyle={\|\mathbf{U}-\mathbf{Z}\|^{2}+\|\hat{\mathbf{U}}(b)-\mathbf{U}\|^{2}}=\Delta^{2},\textnormal{
and }$ (6) $\displaystyle\|\hat{\mathbf{U}}(\theta)-\mathbf{Z}\|^{2}$
$\displaystyle={\|\mathbf{U}-\mathbf{Z}\|^{2}-\|\hat{\mathbf{U}}(b)-\mathbf{U}\|^{2}}=\delta^{2},$
(7)

with radius $\Delta$ and $\delta$, respectively. The blue and red points in
Figure 2 show how the saturation $\theta^{*}$ is detected, as we enter the
shaded blue region. As $\theta$ increases, $\hat{\mathbf{U}}(\theta)$
approaches $\mathbf{U}$, so that $\|\hat{\mathbf{U}}(\theta)-\mathbf{U}\|$ is
getting smaller and $\|\hat{\mathbf{U}}(\theta)-\mathbf{Z}\|$ is saturating.

###  2.3 Rate-distortion optimization with alternative reference

The encoder-decoder parameters in a traditional video codec are obtained using
RDO [2, 3] by solving the optimization problem

$\min_{\boldsymbol{\alpha}}D(\boldsymbol{\alpha})+\lambda
R(\boldsymbol{\alpha}),$ (8)

where $J=D(\boldsymbol{\alpha})+\lambda R(\boldsymbol{\alpha})$ is the
Lagrange cost, $\boldsymbol{\alpha}$ is a set of coding parameters (e.g., mode
decision, quantization parameters, transform size, etc.),
$D(\boldsymbol{\alpha})$ is the MSE distortion between the encoded UGC
$\hat{\mathbf{U}}(\boldsymbol{\alpha})$ and the input $\mathbf{U}$.
$R(\boldsymbol{\alpha})$ is the rate of
$\hat{\mathbf{U}}(\boldsymbol{\alpha})$. The parameter $\lambda>0$ controls
the trade-off between rate and distortion. When $\lambda$ is small, solutions
with higher bitrate are encouraged, and thus when encoding UGC, a small
$\lambda$ leads to quality saturation. 3(a) depicts the proposed UGC
compression system. It consists of a traditional video compression system that
performs RDO, along with a saturation detection module, which takes an input
UGC video, and returns a saturation $\lambda^{*}$. In a traditional
compression system, a typical input parameter is the “QP” value which can be
easily converted into an input $\lambda$ [16]. If $\lambda<\lambda^{*}$, the
input “QP” parameter is in the saturation region, thus the encoder performs
RDO with parameter $\lambda^{*}$. When $\lambda\geq\lambda^{*}$, the encoder
performs RDO as normal with parameter $\lambda$. The saturation detection
module depicted in 3(b) also utilizes RDO. Because saturation detection
requires a RD curve covering a wide range of RD pairs, in order to reduce
computational complexity we consider a simplified system where only a few
frames are considered (e.g., $1$ per second). For encoding, we use JPEG and
allow different quantization parameters for each patch.

The UGC video $\mathbf{U}$, and the denoised UGC $\mathbf{Z}$ are partitioned
into $N$ non overlaping patches. For each patch, there is a single coding
parameter $\alpha_{k}$ that will be optimized. The rate and distortion of the
$k$th patch are denoted by $R(\alpha_{k})$ and $D(\alpha_{k})$, respectively.
$D(\alpha_{k})=\|\hat{\mathbf{U}}_{k}(\alpha_{k})-\mathbf{Z}_{k}\|^{2}$ is the
distortion between the encoded $k$th patch $\hat{\mathbf{U}}_{k}(\alpha_{k})$
and the denoised $k$th patch $\mathbf{Z}_{k}$. Given $\lambda>0$, we solve the
RDO problem

$\min_{\alpha_{1},\cdots,\alpha_{N}}\sum_{k=1}^{N}D(\alpha_{k})+\lambda\sum_{k=1}^{N}R(\alpha_{k}).$
(9)

The vector of optimal coding parameters that solves (9) is denoted by
$\boldsymbol{\alpha}_{\lambda}$, while the optimal total rate is denoted by
$R(\boldsymbol{\alpha}_{\lambda})$ and the optimal total distortion (MSE
between encoded UGC and denoised UGC) is given by
$D(\boldsymbol{\alpha}_{\lambda})$. We apply RDO and solve (9) for a wide
range of $\lambda$ to obtain an RD curve with pairs
$(D(\boldsymbol{\alpha}_{\lambda}),R(\boldsymbol{\alpha}_{\lambda}))$, from
which saturation can be detected. Given
$\lambda\in[\lambda_{min},\lambda_{max}]$ and
$D(\boldsymbol{\alpha}_{\lambda})=\|\hat{\mathbf{U}}(\boldsymbol{\alpha}_{\lambda})-\mathbf{Z}\|^{2}$,
we can rewrite the saturation equation (3) and define saturation
$\lambda^{*}_{Z}$ as the largest value satisfying

$\left|\|\hat{\mathbf{U}}(\boldsymbol{\alpha}_{\lambda})-\mathbf{Z}\|^{2}-\|\mathbf{U}-\mathbf{Z}\|^{2}\right|\leq\|\hat{\mathbf{U}}(\boldsymbol{\alpha}_{\lambda_{min}})-\mathbf{U}\|^{2},$
(10)

for all $\lambda\in[\lambda_{min},\lambda^{*}_{Z}]$. In a traditional codec,
distortion is computed with respect to $\mathbf{U}$. Since $\lambda^{*}_{Z}$
is the saturation we found when $\mathbf{Z}$ is the reference, it controls the
rate-distortion trade-off using this particular choice of distortion. We still
need to find the saturation $\lambda^{*}_{U}$ appropriate for the case where
$\mathbf{U}$ is the reference used for distortion computation, and that can be
provided as input to a traditional codec performing RDO. Once we obtain
$\lambda^{*}_{Z}$, the saturation rate is given by
$R(\boldsymbol{\alpha}_{\lambda^{*}_{Z}})$. As we do not want to operate at a
rate larger than $R(\boldsymbol{\alpha}_{\lambda^{*}_{Z}})$, we define the
saturation $\lambda^{*}_{U}$ as the smallest value such that

$R(\boldsymbol{\beta}_{\lambda})\leq
R(\boldsymbol{\alpha}_{\lambda^{*}_{Z}}),\quad\lambda\in[\lambda^{*}_{U},\lambda_{max}],$
(11)

where $\boldsymbol{\beta}_{\lambda}$ is the minimizer of the RDO of (9) with
parameter $\lambda$ and using the traditional distortion
$D(\alpha_{k})=\|\hat{\mathbf{U}}_{k}(\alpha_{k})-\mathbf{U}_{k}\|^{2}$.

(a) UGC compression system

(b) Saturation detection system

Fig. 3:  An illustration of how our proposed method work with existing video
codecs. (b) shows how our saturation detection method works with encoder as a
practical plug-in module. (c) shows the details of our saturation detection
method.

##  3 Experiment

###  3.1 Encoding the de-noised references

For this experiment, we use the KADID-10k dataset [15, 17], which has $81$
pristine images named from ’I01’ to ’I81’. For each pristine image, we used
the H.264 in Ffmpeg to simulate UGC images with compression noise using
quantization values from $23$ to $51$. Then, for each UGC image, we applied
three different video/image restoration methods: De-Blocking (DB) from ffmpeg,
Artifact Removal [18] (AR) and Practical Blind Denoising [19] (PBD). We encode
each image (UGC or de-noised UGC) with JPEG [20], using $86$ different quality
values ($QV=10,11,...,95$). Then, we use Naturalness Image Quality Evaluator
(NIQE) [4] to evaluate the quality of the compression results. Note that we
could still apply the idea from Figure 2 to detect the saturation. Since RDO
is not used in this experiment, we detect the saturation $\theta^{*}$ (JPEG
$QV^{*}$) instead of $\lambda$ using constraint (3). Choosing different
$\mathbf{Z}$, we may obtain different saturation points as is shown in
LABEL:fig:Histogram left. Also, we mark the location of averaged saturation
point considering all the saturation points detected by different $\mathbf{Z}$
with crossing. There are very clear turning points on the curves, which
indicates that the saturation behavior exists when encoding either UGC or de-
noised references. To further understand the saturation phenomenon, we
calculated the average slope between the detected saturation point and points
to its left and its right. As is shown in LABEL:fig:Histogram right, the left
slopes are almost all negative (since quality improves before saturation)
while the right slopes appear randomly distributed around zero. This provides
evidence of successful saturation detection.

Fig. 5: RD curves for ‘S11’ UGC video sequence with $QP=35$. In Denoised
references are DB (left) and AR (right). In each figure, the red RD curve uses
$\mathbf{U}$ as reference, while the blue RD curve uses $\mathbf{Z}$ as
reference. The green line represents the distortion between $\mathbf{U}$ and
$\mathbf{Z}$. The two light blue lines are the upper and lower bounds from the
proposed saturation detection method (10).  Fig. 6: Video quality evaluation
versus rate. We show results for 6 UGC videos generated from ’S18’ and ’S19’
with 3 different $QP$. In each figure, blue points represent encoded UGC with
H.264 at different rates. The vertical lines represents the rate when re-
compressing the UGC video with detected $QP(\lambda^{*}_{U})$ using different
$\mathbf{Z}$.

###  3.2 Saturation Detection on UGC Videos

The video dataset BVI-CC [21, 22] contains 9 pristine video sequences (named
’S11’ to ’S19’) with two resolutions: $3840\times 2160$ and $1920\times 1080$.
Each video is $5$ seconds long, with $60$ frames per second. For convenient,
we used the $1920\times 1080$ videos and down-sampled them into $480\times
360$. We took the down-sampled videos as the pristine videos and used H.264 in
Ffmpeg to create UGC videos with $QP$ ranging from 23 to 51. Then we uniformly
sampled 5 frames out of 300 for saturation detection. On each video, we
applied three different image/video restoration methods: De-Blocking (DB) from
Ffmpeg, Artifacts Removal [18] (AR) and Practical Blind Denoising [19] (PBD).
Then, each frame and its DB, AR and PBD references were uniformly divided into
90 patches of size $48\times 40$. We encoded each patch with JPEG [20], using
$20$ different quality values ($QV_{n}$, $n=1,\cdots,20$) ranging from from
$19$ (worst) to $95$ (best). Since JPEG has only one quality factor, for each
patch, the minimization of RDO object function (8) could be easily achieved by
traversing all possible $QV_{n}$. Figure 5 shows the RD curves of a UGC video
($QP=35$) with two different de-noised references, DB and AR. In each figure,
the red curve takes $\mathbf{U}$ as reference while the blue curve takes
$\mathbf{Z}$ as reference. Each point on a curve represents compressing
patches by JPEG via RDO toward a specific $\lambda$. Figure 5 shows that blue
curves converge to the green line, which is $||\mathbf{U}-\mathbf{Z}||^{2}$.
Using the proposed saturation detection method (10), the saturation
$\lambda^{*}_{Z}$ could be found at the intersection of the blue curve and the
upper light blue line, which is the upper bound of saturation in (10). Then,
we could find the $\lambda^{*}_{U}$ from the red curve using (11). In [6],
saturation is detected by the intersection of blue and red RD curves. However,
when $\mathbf{Z}$ is computed with AR, the blue curves are always under the
red curves and there is no intersection, thus the saturation detection method
from[6] would fail in this case. Nevertheless, the saturation exists and could
be detected by our method.

###  3.3 Experiments with real H.264 codec

To evaluate the saturation detected, we re-compressed the UGC video with
Ffmpeg H.264 codec using $52$ different $QP$ and evaluated the results. Since
Ffmpeg does not accept $\lambda$ as an input (which is the output of our
saturation detection method), we use the following relation [16], valid for
$QP=0,1,...,51$,

$\lambda(QP)=0.852\times 2^{(QP-12)/3},$ (12)

to translate the saturation $\lambda^{*}_{U}$ in to $QP(\lambda^{*}_{U})$.
Choosing a $QP<QP(\lambda^{*}_{U})$ will result in waste of rate and no
improvement on quality. We use NIQE and a no-reference quality metric for UGC
video, VIDE [23] for quality evaluation. Note lower NIQE value means better
quality while higher VIDE value represents better quality. Figure 6 shows the
quality of re-compressed UGC videos H.264 at different rates. For any UGC
video in Figure 6, we could see clearly the saturation happens with both of
the NIQE and VIDE. Furthermore, our detected saturation $\lambda^{*}_{U}$
accurately marks the turning point of the quality curves, which shows the
correctness and accuracy of our proposed method. We also see that when $QP=25$
and $\mathbf{Z}$ is DB, the saturation detected (blue line) is worse than
$\mathbf{Z}$ is AR or PBD. This indicates that DB may not be adaptive enough
to UGC input with good quality, while AR and PBD produce better results.

##  4 Conclusion

In this paper, we proposed a practical system for quality saturation detection
that can be combined with traditional compression systems for UGC video
compression. The proposed saturation detection is based on RDO implemented on
a simplified low complexity encoder. We illustrate the effectiveness of the
proposed method using H.264 to compress previously compressed UGC. Our results
show that the quality saturation region detected by our method is consistent
with the saturation region found using no reference video quality metrics. We
also show that our saturation detection method is robust to the choice of
denoiser. However, our saturation detection fails when the input UGC quality
is very low, and thus there is no hope that a good denoiser exists. When the
UGC quality is high, and thus no saturation is expected, the proposed method
fails when the denoising algorithm does not set its parameters correctly and
over smooths the input UGC. The proposed framework can be complement and
enhanced by exploiting existing approaches for quality detection, content type
classification and no reference visual quality metrics.

## References

  * [1] Yilin Wang, Sasi Inguva, and Balu Adsumilli,  “YouTube UGC dataset for video compression research,”  in 2019 IEEE 21st International Workshop on Multimedia Signal Processing (MMSP). IEEE, 2019, pp. 1–5.
  * [2] Antonio Ortega and Kannan Ramchandran,  “Rate-distortion methods for image and video compression,”  IEEE Signal processing magazine, vol. 15, no. 6, pp. 23–50, 1998\.
  * [3] Gary J Sullivan and Thomas Wiegand,  “Rate-distortion optimization for video compression,”  IEEE signal processing magazine, vol. 15, no. 6, pp. 74–90, 1998\.
  * [4] Anish Mittal, Rajiv Soundararajan, and Alan C Bovik,  “Making a “completely blind” image quality analyzer,”  IEEE Signal processing letters, vol. 20, no. 3, pp. 209–212, 2012\.
  * [5] Anish Mittal, Anush Krishna Moorthy, and Alan Conrad Bovik,  “No-reference image quality assessment in the spatial domain,”  IEEE Transactions on image processing, vol. 21, no. 12, pp. 4695–4708, 2012.
  * [6] Eduardo Pavez, Enrique Perez, Xin Xiong, Antonio Ortega, and Balu Adsumilli,  “Compression of user generated content using denoised references,”  in 2022 IEEE International Conference on Image Processing (ICIP), 2022, pp. 4188–4192.
  * [7] Yilin Wang, Junjie Ke, Hossein Talebi, Joong Gon Yim, Neil Birkbeck, Balu Adsumilli, Peyman Milanfar, and Feng Yang,  “Rich features for perceptual quality assessment of UGC videos,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 13435–13444.
  * [8] Sam John, Akshay Gadde, and Balu Adsumilli,  “Rate distortion optimization over large scale video corpus with machine learning,”  in 2020 IEEE International Conference on Image Processing (ICIP). IEEE, 2020, pp. 1286–1290.
  * [9] Suiyi Ling, Yoann Baveye, Patrick Le Callet, Jim Skinner, and Ioannis Katsavounidis,  “Towards perceptually-optimized compression of user generated content (UGC): Prediction of UGC rate-distortion category,”  in 2020 IEEE International Conference on Multimedia and Expo (ICME). IEEE, 2020, pp. 1–6.
  * [10] Zhengzhong Tu, Chia-Ju Chen, Yilin Wang, Neil Birkbeck, Balu Adsumilli, and Alan C Bovik,  “Efficient user-generated video quality prediction,”  in 2021 Picture Coding Symposium (PCS). IEEE, 2021, pp. 1–5.
  * [11] Xiangxu Yu, Neil Birkbeck, Yilin Wang, Christos G Bampis, Balu Adsumilli, and Alan C Bovik,  “Predicting the quality of compressed videos with pre-existing distortions,”  IEEE Transactions on Image Processing, vol. 30, pp. 7511–7526, 2021\.
  * [12] Yilin Wang, Hossein Talebi, Feng Yang, Joong Gon Yim, Neil Birkbeck, Balu Adsumilli, and Peyman Milanfar,  “Video transcoding optimization based on input perceptual quality,”  in Applications of Digital Image Processing XLIII. SPIE, 2020, vol. 11510, pp. 201–211.
  * [13] R. Dobrushin and B. Tsybakov,  “Information transmission with additional noise,”  IRE Transactions on Information Theory, vol. 8, no. 5, pp. 293–304, 1962.
  * [14] T. Berger,  Rate Distortion Theory: A Mathematical Basis for Data Compression,  Prentice-Hall electrical engineering series. Prentice-Hall, 1971.
  * [15] Hanhe Lin, Vlad Hosu, and Dietmar Saupe,  “KADID-10k: A large-scale artificially distorted iqa database,”  in 2019 Tenth International Conference on Quality of Multimedia Experience (QoMEX). IEEE, 2019, pp. 1–3.
  * [16] Iain E Richardson,  The H. 264 advanced video compression standard,  John Wiley & Sons, 2011.
  * [17] Hanhe Lin, Vlad Hosu, and Dietmar Saupe,  “DeepFL-IQA: Weak supervision for deep IQA feature learning,”  arXiv preprint arXiv:2001.08113, 2020.
  * [18] Jiaxi Jiang, Kai Zhang, and Radu Timofte,  “Towards flexible blind JPEG artifacts removal,”  in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 4997–5006.
  * [19] Kai Zhang, Yawei Li, Jingyun Liang, Jiezhang Cao, Yulun Zhang, Hao Tang, Radu Timofte, and Luc Van Gool,  “Practical blind denoising via Swin-Conv-UNet and data synthesis,”  arXiv preprint, 2022.
  * [20] Alex Clark,  “Pillow (pil fork) documentation,”  Readthedocs. Https://Buildmedia. Readthedocs. Org/Media/Pdf/Pillow/Latest/Pillow. Pdf, 2015.
  * [21] Angeliki V Katsenou, Fan Zhang, Mariana Afonso, and David R Bull,  “A subjective comparison of AV1 and HEVC for adaptive video streaming,”  in 2019 IEEE International Conference on Image Processing (ICIP). IEEE, 2019, pp. 4145–4149.
  * [22] Fan Zhang, Angeliki V Katsenou, Mariana Afonso, Goce Dimitrov, and David R Bull,  “Comparing VVC, HEVC and AV1 using objective and subjective assessments,”  arXiv preprint arXiv:2003.10282, 2020.
  * [23] Zhengzhong Tu, Yilin Wang, Neil Birkbeck, Balu Adsumilli, and Alan C Bovik,  “UGC-VQA: Benchmarking blind video quality assessment for user generated content,”  IEEE Transactions on Image Processing, 2021.


tcb@breakable

#  ChatPattern: Layout Pattern Customization via Natural Language

Zixiao Wang  CUHK ,  Yunheng Shen  Tsinghua University ,  Xufeng Yao  CUHK ,
Wenqian Zhao  CUHK ,  Yang Bai  CUHK ,  Farzan Farnia  CUHK and  Bei Yu  CUHK

###### Abstract.

Existing works focus on fixed-size layout pattern generation, while the more
practical free-size pattern generation receives limited attention. In this
paper, we propose ChatPattern, a novel Large-Language-Model (LLM) powered
framework for flexible pattern customization. ChatPattern utilizes a two-part
system featuring an expert LLM agent and a highly controllable layout pattern
generator. The LLM agent can interpret natural language requirements and
operate design tools to meet specified needs, while the generator excels in
conditional layout generation, pattern modification, and memory-friendly
patterns extension. Experiments on challenging pattern generation setting
shows the ability of ChatPattern to synthesize high-quality large-scale
patterns.

††copyright: none

##  1\. Introduction

High-quality Very-Large-Scale Integration (VLSI) layout pattern libraries are
foundational to numerous Design for Manufacturability (DFM) studies, such as
refining design rules, formulating Optical Proximity Correction (OPC) recipes
(gao2014mosaic, ), conducting lithography simulations (kuang2013efficient, ;
yu2015layout, ), and detecting layout hotspots (chen2019faster, ).
Contemporary machine-learning-based lithography design applications typically
require an extensive array of layout patterns to train their networks, yet
assembling a large-scale pattern library is cost-prohibitive due to the
intricate logic-to-chip design cycle.

Prior to the advent of machine learning, rule-based methods
(reddy2018enhanced, ) were employed to synthesize layout patterns
automatically, with simple hand-drafted augmentations like flipping and
rotation used to expand the fundamental layout pattern units. These units
would then be assembled randomly to create larger designs. However, the
diversity and volume of patterns generated by these rule-based methods often
fell short of user expectations. Conversely, recent learning-based methods
(yang2019deepattern, ; zhang2020layout, ; wen2022layoutransformer, ;
wang2023diffpattern, ) have demonstrated the ability to generate a plethora of
diverse layout patterns that closely match the dataset distribution. One
notable technique, the squish pattern trick (gennari2014topology, ), has been
instrumental in reducing computational and memory demands by condensing a
layout pattern patch into a compact 2D-topology matrix, upon which generative
models are trained. Once the topology matrices are generated, legalization
technologies are employed to recover the topology matrices to layout patterns.

Despite these advancements, learning-based methods still lack the capability
for fine-grained modifications. For instance, when a training set comprises
various pattern categories, these methods cannot determine the class of the
generated pattern. Editing a specific section of a layout according to
particular rules is a frequent necessity, especially with large layouts, to
accommodate specific applications (sun2022efficient, ; zhao2022adaopc, ), but
none of existing methods support pattern edition. And the size of generated
topology matrix is usually fixed due to the limitation of network architecture
and device memory. The fixed pattern size restricts the application of the
generated patterns in downstream tasks which requires different pattern size.

Additionally, the task of manually synthesizing millions of desired layout
patterns using flexible generation tools can be labor-intensive. Pattern
library builders must not only master complex generation tools but also
comprehend the specialized requirements from downstream users, often
communicated in a blend of natural language and professional jargon. Moreover,
builders may not always be available or able to respond promptly. To bridge
this gap, Large Language Models (LLMs) have proven adept at handling complex
tasks across various domains (zhou2023dbgpt, ; he2023chateda, ). However,
their application as layout pattern library builders remains unexplored.

In response, this paper introduces $\mathsf{ChatPattern}$, an indefatigable
layout pattern builder designed to tailor a pattern library to specific
requirements articulated in natural language. As illustrated in Figure 1,
$\mathsf{ChatPattern}$ is composed of two principal components: an expert LLM
agent holding design tools and documentation, capable of understanding and
executing tasks based on natural language instructions, and a flexible,
controllable layout pattern generative model that surpasses existing methods
by offering conditional layout generation, precise pattern modification, and
unrestricted pattern extension. The contributions of this work are fourfold:

  * •

The presentation of ChatPattern, the inaugural LLM-powered layout pattern
generation framework.

  * •

The integration of an expert LLM agent as a pattern library builder,
proficient in processing natural language inputs and autonomously operating
the necessary tools to fulfill requirements.

  * •

The development of a versatile layout pattern generative model that
outperforms existing methods in conditional pattern generation, layout
modification, and free-size pattern extension.

  * •

The expansion of the scope of the layout pattern generation task, prompting
researchers to focus on more realistic yet challenging tasks such as free-size
layout pattern generation.

Figure 1. An illustration of ChatPattern.

##  2\. Preliminaries

###  2.1. The Scope of $\mathsf{ChatPattern}$

$\mathsf{ChatPattern}$ is an AI agent that offers a conversational interface,
enabling users to use natural language to guide the creation of pattern
libraries that meet their specific layout generation needs.

######  Problem 1 (Target of $\mathsf{ChatPattern}$).

Create a framework powered by a large language model that can understand and
process natural language instructions, and produce a library of legal layout
patterns that meet user needs by utilizing a layout pattern generation tool.

###  2.2. Fixed-size Layout Pattern Generation

Contemporary research in layout pattern synthesis predominantly focuses on
creating patterns of a predetermined dimension. This research domain has
witnessed significant contributions that leverage squish-pattern
representation (yang2019deepattern, ; zhang2020layout, ; wang2023diffpattern,
). These methods learn to fit the distribution of the binary topology matrix
of Squish Pattern (gennari2014topology, ). And the generated topology matrix
will be further legalized in post-processing to yield a legal layout pattern.

Squish Pattern Representation. A layout pattern, comprising a series of non-
overlapping polygons, can be effectively modeled using a squish pattern. The
squish pattern is a compact representation of layout pattern that encodes
layout topology and geometry into a matrix $\bm{T}$ and vectors
$\bm{\Delta}_{x},\,\bm{\Delta}_{y}$. It divides the layout into grids using
scan lines along polygon edges, storing intervals in the $\bm{\Delta}$
vectors. Matrix entries are binary, denoting shapes or emptiness. Topology
matrix will be further normalized to a fixed-size square for uniformity as
introduced in (yang2019detecting, ). Figure 2 illustrates how squish pattern
works.

Figure 2. Squish Pattern Representation.

Topology Generation via Unconditional Discrete Diffusion. Discrete diffusion
model (austin2021structured, ) is a type of generative model where the value
of every image pixel is limited in a pre-defined discrete space. Similar to
normal diffusion models (ho2020denoising, ; song2020denoising, ), noise is
added to input images in forward process, and a model with learnable parameter
$\theta$ learns to remove noise in reverse process. Given that
$x_{k}\in\\{0,1\\}$ is an entry in the topology matrix $\bm{T}$, a transition
probability matrix $[\bm{Q}_{k}]_{ij}=q(x_{k}=j|x_{k-1}=i)$ is defined to
describe the state transition probability for each $\bm{x}$ at the $k$-th of
$K$ forward step,

(1)
$\bm{q}\left(\bm{x}_{k}\mid\bm{x}_{k-1}\right):=\operatorname{Cat}\left(\bm{x}_{k};\bm{p}=\bm{x}_{k-1}\bm{Q}_{k}\right),$

where $\operatorname{Cat(\bm{x}|\bm{p})}$ denote the categorical distribution
of $\bm{x}$ given $\bm{p}$. And the forward process can be defined as,

(2) $\displaystyle\bm{q}\left(\bm{x}_{k}|\bm{x}_{0}\right)$
$\displaystyle=\operatorname{Cat}\left(\bm{x}_{k};\bm{p}=\bm{x}_{0}\overline{\bm{Q}}_{k}\right),$
(3) $\displaystyle\bm{Q}_{k}$
$\displaystyle=\begin{bmatrix}1-\beta_{k}&\beta_{k}\\\
\beta_{k}&1-\beta_{k}\end{bmatrix},$ (4) $\displaystyle\beta_{k}$
$\displaystyle=\frac{(k-1)\left(\beta_{K}-\beta_{1}\right)}{K-1}+\beta_{1},~{}k=1,...,K,$

where $\overline{\bm{Q}}_{k}=\bm{Q}_{1}\bm{Q}_{2}\ldots\bm{Q}_{k}$ and
$\beta_{1}$ and $\beta_{K}$ are hyper-parameters.

After sampling a noised topology $\bm{T}_{k}$ from the input topology
$\bm{T}_{0}$ via Equation 2, the model learns to denoise the topology and
predicts the logits of the posterior distribution
$\bm{p}_{\bm{\theta}}\left(\bm{x}_{0}|\bm{x}_{k}\right)$. Therefore, the
$k$-th reverse step can be calculated as following:

(5)
$\bm{p}_{\bm{\theta}}\left(\bm{x}_{k-1}|\bm{x}_{k}\right)=\sum_{\widetilde{\bm{x}}_{0}}\bm{q}\left(\bm{x}_{k-1}|\bm{x}_{k},\widetilde{\bm{x}}_{0}\right)\bm{p}_{\bm{\theta}}\left(\widetilde{\bm{x}}_{0}|\bm{x}_{k}\right),$

where the term $\widetilde{\bm{x}}_{0}$ will visit every possible state of
$\bm{x}_{0}$. Finally, we can denoise a sampled noise $\bm{T}_{K}$ and
synthesize a topology $\bm{T}_{0}$ with the well-trained model by recursively
calling the reverse step,

(6)
$p_{\theta}(\bm{T}_{0}|\bm{T}_{K})=p_{\theta}(\bm{T}_{0}|\bm{T}_{1})\prod_{k=2}^{K}p_{\theta}(\bm{T}_{k-1}|\bm{T}_{k}).$

Topology Legalization. The generated topology matrix will be further enriched
to patterns by matching them with suitable geometry vectors. The generated
patterns should satisfy several pre-defined design rules of IC layout
(zhang2020layout, ; wen2022layoutransformer, ) as illustrated in Figure 3.

Figure 3.  Design rule illustrations. ‘Space’ means distance between adjacent
polygons. ‘Width’ measures shape size in one direction. ‘Area’ denotes area of
a polygon.

######  Definition 1 (Legality).

We treat a layout pattern as a legal one if the layout pattern is DRC-clean,
given the design rules.

(7) $\text{Legality}=\frac{\\#\text{Legal Patterns}}{\\#\text{Generated
Patterns}}$

Figure 4. A working pipeline of LLM agent in $\mathsf{ChatPattern}$. Dash
lines denote the optional paths.

###  2.3. Free-size Layout Pattern Generation

Compared with fixed-size layout pattern generation task, we aim to synthesize
layout patterns with any given size, which is a more challenging task given
the limited model output size, device memory, and varied requirements. We
adopt the widely-used evaluation metric (yang2019deepattern, ;
wang2023diffpattern, ; wen2022layoutransformer, ; zhang2020layout, ),
Diversity, to evaluate the quality of generated pattern library. A greater
pattern diversity $H$ indicates that the library contains more widely
distributed patterns.

######  Definition 2 (Diversity).

The diversity of the patterns library, denoted by $H$, is defined as the
Shannon Entropy of the distribution of the pattern complexities as follows:

(8) $H=-\sum_{i}\sum_{j}P(c_{xi},c_{yj})\log{P(c_{xi},c_{yj})},$

where $P(c_{xi},c_{yj})$ is the probability of a pattern with complexity
$(c_{xi},c_{yj})$ sampled from the library, and $c_{x}$ and $c_{y}$ are the
numbers of scan lines subtracted by one along the x-axis and y-axis,
respectively.

Based on the above evaluation metrics, the pattern generation problem can be
formulated as follows,

######  Problem 2 (Free-size Layout Pattern Extension).

Given a set of design rules and target pattern size, the objective of pattern
generation is to synthesize a legal pattern library such that the pattern
diversity of the layout patterns in the library is maximized.

##  3\. Algorithm

$\mathsf{ChatPattern}$ seamlessly integrates a front-end powered by a Large
Language Model with a back-end that employs a conditional discrete-diffusion
model for layout pattern generation.

###  3.1. Pattern Customization via Expert LLM agent

$\mathsf{ChatPattern}$, leveraging LLM technology, automates pattern library
customization. Its primary function is to interpret user requirements
expressed in natural language, breaking down complex demands into manageable
sub-tasks. These sub-tasks are subsequently processed using specialized
pattern generation tools. The detailed operational pipeline of
$\mathsf{ChatPattern}$ is illustrated in Figure 4.

Requirement Auto-Formatting. Given the complexity of user requests in the
Layout Pattern Generation workflow, the LLM agent first translates these
requests into a structured format using a pre-defined template. This template
contains all relevant parameters and requirements for utilization by the
pattern generation API functions. The template can be summarized by the LLM
agent according to the description of functions or provided by the function
provider. The arguments can be further divided into required ones, which
decide the basic parameter (e.g., pattern count and size) of this task, and
optional ones, which are for fine-grained control. An important thing is that
one task given by a user can be decomposed into several requirement lists,
each for one simple sub-task, to limit the complexity of one task and reduce
mistakes. For example, the user request shown in Figure 4 is factorized into
two sub-tasks.

Task Planning and Execution. During the last step, $\mathsf{ChatPattern}$
identifies and plans the necessary sub-tasks for fulfilling the user’s
request. For each planned sub-task, $\mathsf{ChatPattern}$ schedules a series
of structured tasks, which are then addressed using various pattern generation
tools like topology generation and legalization. The task planning process is
exemplified in Figure 4. For execution, $\mathsf{ChatPattern}$ utilizes a
Python interpreter or API calls, supported by the layout pattern generation
back-end model. Compared with a rule-based arguments-program translator, the
LLM agent can address failed cases based on feedback or logs derived from
function calls. For example, in the legalization phase, the legalization can
easily fail especially for large topology matrices due to the violation of
design rules. Applying topology selection and dropping the failed cases can
guarantee the legality of the final result, while a lot of effort on topology
matrix generation is wasted. Alternative choices for LLM agent are modifying
the failed regions with different conditions and trying different initial
states, which save time and computation.

Tool Function Learning and Application. The core concept of pattern generation
through an LLM agent lies in its ability to operate without directly accessing
the generated matrix of zeros and ones. This matrix could surpass the token
length limit of the LLM, rendering it incapable of extracting information from
such low-level data. The LLM agent instead relies on the route to the end
results and comprehension of select overarching characteristics, such as
complexity, physical dimensions, or error locations. To construct a pattern
library, certain fundamental tools or APIs are indispensable: (1) Random
Topology Generation, which creates random topologies subject to specific
conditions, and (2) Topology Legalization, which transforms a topology into a
compliant layout pattern. These functions constitute the cornerstone for
squish-pattern-based layout pattern generation. Yet, the scope of the
generated topology might be constrained by the model size or device capacity,
and it might not always conform to the legalization process. Thus,
supplementary functions for advanced customization are available: (1) Topology
Extension augments a topology to a designated size within certain parameters,
and (2) Topology Modification revises parts of a topology, offering a time-
efficient alternative to discarding non-compliant topologies, particularly for
expansive patterns. Additional high-level functions may be integrated to
bolster the model’s capabilities, allowing the LLM agent to capitalize on
backend tool enhancements with no need for internal changes.

Learning from Documents and Experience. Documents are reservoirs of high-level
knowledge, instrumental in the pattern design process. In the free-size layout
pattern generation task, the selection of the extension algorithm plays a
pivotal role in determining the quality of the output. Informed algorithm
selection can be enhanced through statistical analysis of historical data.
Additionally, equipping a model with a standardized operational pipeline at
inception can lead to a marked increase in performance. The practice of
documenting work history and scrutinizing exceptional cases is equally
valuable, laying the groundwork for the model’s ongoing refinement.

###  3.2. Flexible Layout Pattern Generative Model

The pattern generator provides tool support for LLM agent front-end. Our
generative model utilizes a conditional discrete diffusion model to fit the
topology distributions from multi-source and synthesize topology for further
legalization. However, compared with previous work, $\mathsf{ChatPattern}$
leverages three novel characters to enable the ability to generate complex
topology matrix and meet highly customized requirements.

Property-Conditional Topology Generation. Patterns in a dataset do not always
share the design rules or physical properties. For example, the distribution
of patterns from the 7-nm manufacturing process is different from that of
130-nm. The diversity of materials and design rules etc. enlarges the
difference. Establishing a dataset and training individual models for each
kind of patterns is not a sound choice, while directly training a model on the
mixture dataset will raise some concerns about the design rules conflict. To
address this issue, we add conditions to the reverse process of the diffusion
model and the distribution of the generated topology matrix can be specified.
Different from the cases in normal image generation, the condition design in
pattern generation should consider the design rules, materials, and
manufacturing process. The $k$-th step of distribution specified reverse
process can be defined as,

(9)
$\bm{p}_{\bm{\theta}}\left(\bm{x}_{k-1}|\bm{x}_{k},c\right)=\sum_{\widetilde{\bm{x}}_{0}}\bm{q}\left(\bm{x}_{k-1}|\bm{x}_{k},\widetilde{\bm{x}}_{0}\right)\bm{p}_{\bm{\theta}}\left(\widetilde{\bm{x}}_{0}|\bm{x}_{k},\bm{c}\right),$

where $\bm{c}$ denotes the conditions. An illustration of the training and
sampling process is shown in Figure 5. During the training process, the model
optimizes the loss function,

(10)
$L=D_{\mathrm{KL}}\left(\bm{q}\left(\bm{x}_{k-1}|\bm{x}_{k},\bm{x}_{0}\right)\parallel\bm{p}_{\theta}\left(\bm{x}_{k-1}|\bm{x}_{k},\bm{c}\right)\right)-\lambda\log\bm{p}_{\bm{\theta}}\left(\bm{x}_{0}|\bm{x}_{k},\bm{c}\right).$

When the training process is finished, a topology matrix with condition
$\bm{c}$ can be generated by a $K$-step reverse process,

(11)
$p_{\theta}(\bm{T}_{0}|\bm{T}_{K},\bm{c})=p_{\theta}(\bm{T}_{0}|\bm{T}_{1},\bm{c})\prod_{k=2}^{K}p_{\theta}(\bm{T}_{k-1}|\bm{T}_{k},\bm{c}),$

where $\bm{T}_{K}$ is a randomly-sampled noise.

Figure 5. Illustration of conditional pattern generation. Figure 6.
Illustration of pattern modification.

Pattern Modification. Given an existing pattern topology matrix
$\bm{T}_{0}^{\text{known}}$, making modifications to any desired region on it
can be useful when dealing with failed topology. We denote kept pixels as
$\bm{M}\odot\bm{T}_{0}^{\text{known}}$ and denote the masked pixels as
$(1-\bm{M})\odot\bm{T}_{0}^{\text{known}}$. Since in every reverse step of
Equation 11, $\bm{T}_{k-1}$ depends solely on $\bm{T}_{k}$, we replace the
kept region in $\bm{T}_{k}$ by the noised pixels in given topology,
$\bm{M}\odot\bm{T}_{k}^{\text{known}}$. The noised topology
$\bm{T}_{k}^{\text{known}}$ is obtained by the forward process in Equation 2.
And $(1-\bm{M})\odot\bm{T}_{k-1}^{\text{unknown}}$ will be generated by the
model with the condition of $\bm{M}\odot\bm{T}_{k}^{\text{known}}$. And
different with general image generation(ho2020denoising, ; lugmayr2022repaint,
), the modification of patterns should consider the design rules and the
condition $\bm{c}$ should match the distribution of given topology matrix
$\bm{T}_{0}^{\text{known}}$,

(12) $\displaystyle\bm{T}_{k-1}^{\text{known}}$
$\displaystyle\sim\bm{q}\left(\bm{T}_{k-1}|\bm{T}_{0}^{\text{known}}\right),$
$\displaystyle\bm{T}_{k-1}^{\text{unknown}}$
$\displaystyle\sim\bm{p}_{\bm{\theta}}\left(\bm{T}_{k-1}|\bm{T}_{k},\bm{c}\right),$
$\displaystyle\bm{T}_{k-1}$
$\displaystyle=\bm{M}\odot\bm{T}_{k-1}^{\text{known}}+(1-\bm{M})\odot\bm{T}_{k-1}^{\text{unknown}},$

where $\bm{T}_{0}^{\text{known}}$ shares the design rules with patterns in
condition $\bm{c}$. An illustration of pattern modification can be found in
Figure 6.

Pattern Extension. Extending a given pattern to a larger one is a practical
function since the model output usually takes a fixed size while the required
patterns can vary among a large range. Pattern extension can be achieved via
In-Painting and Out-Painting with pattern modification techniques. An
illustration of In-Painting extension and Out-Painting extension can be found
in Figure 7. By modifying the adjacency border and corner of a concatenated
topology matrix, we can merge the shape from both sides and synthesize a
larger topology matrix, which we denoted as In-Painting. We treat the
extending method that directly generates a new border of an existing pattern
as Out-Painting.

By recursively extending a given pattern, we can extend the pattern to any
desired size without considering memory limitation, since only the region in
working space will be taken into computation. If we assume the target size of
topology is $[W,H]$ and the window size of the model is $[L,L]$, the number of
sampling for In-Painting can be calculated by,
$N_{\text{in}}=(2\lceil\frac{W}{L}\rceil-1)(2\lceil\frac{H}{L}\rceil-1)$. With
a stride $S$, the number of sampling for Out-Painting is
$N_{out}=(\lceil\frac{W-L}{S}\rceil+1)(\lceil\frac{H-L}{S}\rceil+1)$.

Figure 7. Pattern extension via In-Painting and Out-Painting.

Legalization. We utilize the non-linear legalization function proposed in
DiffPattern(wang2023diffpattern, ) and denoted it as,

(13) $\text{Legalization}(\cdot)=f_{\mathcal{R}}(\bm{F},\bm{T}),$

where $\mathcal{R}$ is the set of design rules, $\bm{T}$ is the topology and
$\bm{F}$ is the physical size of layout pattern. When the legalization fails,
the unreasonable region can be located and returned due to the explainable
feature of the legalization function.

##  4\. Experimental Results

Table 1.  Comparison on Legality and Diversity on legal patterns. ‘/’ refers
to not applicable.

[tb!]

Task | Set/Method | Training Set∗ | Size | Layer-10001 | Layer-10003 | Total†
---|---|---|---|---|---|---
Legality ($\uparrow$) | Diversity ($\uparrow$) | Legality ($\uparrow$) | Diversity ($\uparrow$) | Legality ($\uparrow$) | Diversity ($\uparrow$)
Fixed-size | Real Patterns | / | $128^{2}$ | / | 10.731 | / | 8.769 | / | 10.625
CAE+LegalGAN () | Layer-10001 | 3.74% | 5.814 | / | / | / | /
VCAE+LegalGAN (zhang2020layout, ) | Layer-10001 | 84.51% | 9.867 | / | / | / | /
LayouTransformer () | Layer-10001 | 89.73% | 10.527 | / | / | / | /
DiffPattern () | Layer-10001/10003 | 99.97% | 10.711 | 99.98% | 8.578 | 99.98% | 10.633
ChatPattern | Layer-10001/10003 |  99.97% | 10.796 | 99.99% | 8.625 | 99.98% | 10.650
Free-size | Real Patterns | / | $256^{2}$ | / | 12.702 | / | 10.696 | / | 12.695
() w/ Concatenation | Layer-10001/10003 | 57.78% | 10.719 | 93.69% | 10.511 | 75.74% | 11.706
$\mathsf{ChatPattern}$ | Layer-10001/10003 | 87.36% | 11.154 | 99.78% | 10.556 | 93.57% | 11.830
Real Patterns | / | $512^{2}$ | / | 13.435 | / | 12.139 | / | 13.787
() w/ Concatenation | Layer-10001/10003 | 0.29% | 5.714 | 40.83% | 11.555 | 20.56% | 11.359
$\mathsf{ChatPattern}$ | Layer-10001/10003 | 36.42% | 10.401 | 98.86% | 11.620 | 67.64% | 12.133
Real Patterns | / | $1024^{2}$ | / | 13.573 | / | 12.644 | / | 14.109
() w/ Concatenation | Layer-10001/10003 | 0.00% | 0.000 | 0.64% | 6.926 | 0.32% | 6.926
$\mathsf{ChatPattern}$ | Layer-10001/10003 | 1.19% | 6.438 | 94.96% | 11.981 | 47.80% | 11.992

  * $*$

All training datasets are the 128$\times$128 version.

  * $\dagger$

We collected generated samples from both Layer-10001/10003 and evaluated them
together.

###  4.1. Layout Pattern Generation

Datasets. We follow previous works (wang2023diffpattern, ;
wen2022layoutransformer, ) to obtain the dataset of small layout pattern
images with the size of 2048$\times$2048 $nm^{2}$ by splitting the layout map
from ICCAD contest 2014. The size of the extracted topology matrix is fixed as
128$\times$128 in squish pattern representation in the baseline setting. There
are two different style layouts, denoted as Layer-10001 and Layer-10003.
Layer-10001 is widely used in previous methods and we introduce layer-10003 to
evaluate the model ability of style specification. Furthermore, by splitting
the layout map into 4$\times$, 16$\times$ and 64$\times$ larger size with
overlap, we also obtained 4$\times$, 16$\times$ and 64$\times$ larger topology
matrix in squish pattern representation correspondingly.

((a)) Layer-10001 style ((b)) Layer-10003 style

Figure 8. Example of 256$\times$256 topology matrix generated by In-Painting
(without legalization).

Diffusion Model Configuration. Following the common settings (ho2020denoising,
; austin2021structured, ), we use a U-Net (ronneberger2015u, ) as our backbone
in the conditional discrete diffusion model. The implementation of U-net
follows that in (ho2020denoising, ). To extract the embedding of the
condition, we use a stack of 3 linear layers. The condition embedding is added
into the embedding of the time step to control the style of the generated
patterns.

((a)) Layer-10001 style ((b)) Layer-10003 style

Figure 9. 512$\times$512 topology matrix generated by Out-Painting.

Training & Testing Details. To keep the same size with previous squish-
pattern-based methods (wang2023diffpattern, ; zhang2020layout, ), we train
$\mathsf{ChatPattern}$ on the 128$\times$128 union-datasets (Layer-10001 and
Layer-10003) with class conditions for $1.0$M iterations with a batch size of
$128$. The network is optimized by an Adam optimizer with a learning rate
2e-4. Drop out is $0.1$ the grad clip is set to $1$, and the loss coefficient
$\lambda$ is set to 1e-3. Diffusion length $K=1000$ and the noise schedule
$\beta_{k}$ is linearly increased from $0.01$ to $0.5$. The training procedure
takes about $250$ GPU hours in total. The back-end of $\mathsf{ChatPattern}$
is trained on 128$\times$128 dataset and the size of directly generated
typologies is fixed at 128$\times$128\. The topology matrix sampled from the
network will be further legalized as explained in Section 3.2. We have noticed
previous work (wang2023diffpattern, ) applies topology selection and pushes
the legality to 100%. Since every squish-pattern-based method can reach 100%
legality via selection, we remove the selection step from all methods when
evaluating their performance to compare the model directly. We further forbid
our pattern modification function calling in both fixed-size and free-size
pattern generation tasks to have a fair comparison.

Fixed-size Pattern Generation. We compare our method with previous layout
pattern generation methods, CAE (yang2019deepattern, ), VCAE (zhang2020layout,
), LegalGAN (zhang2020layout, ) and LayouTransformer (wen2022layoutransformer,
) on the widely used benchmark 128$\times$128 Layer-10001. And we further re-
implemented the previous SOTA, DiffPattern(wang2023diffpattern, ), on
Layer-10001 and Layer-10003 individually since directly mixing patterns from
different distributions can easily lead to a conflict for
(wang2023diffpattern, ), as we discussed in Section 3.2. We report the result
on 10,000 samples generated by $\mathsf{ChatPattern}$ for each class. The
legality and the diversity of legal patterns on each dataset are reported in
Table 1. According to the results, on the 128$\times$128 pattern generation
task, $\mathsf{ChatPattern}$ gets a reasonable improvement compared with
previous SOTA thanks to its ability to utilize a multi-source training
dataset. However, both $\mathsf{ChatPattern}$ and the existing models have
already fitted the distribution of real patterns well in the simple
128$\times$128 benchmarks.

Free-size Pattern Generation. $\mathsf{ChatPattern}$ is specialized in free-
size pattern generation, a task highly applicable to real-world scenarios. For
this task, we established three distinct experimental size settings to
quantitatively assess the model. The sizes of the target topology matrices
ranged from $256^{2}$ to $1024^{2}$. We generated 10,000 samples for each
class across all size levels, examining their Legality and Diversity as we did
in the fixed-size pattern generation tasks. Additionally, patterns extracted
from real datasets served as references and are duly noted in the results
table. The baseline is the SOTA in fixed-size pattern generation, DiffPattern
(wang2023diffpattern, ). To create larger patterns, the baseline method can
only stitches together small patches of the same class, but the method often
breaches design rules. For instance, when patch size reaches $512^{2}$, the
legality of patterns generated by DiffPattern with concatenation plummets to
nearly zero (0.29%) and under half (40.83%) for the Layer-10001 and
Layer-10003 datasets, respectively. Our tests with $\mathsf{ChatPattern}$
cover all the aforementioned settings. $\mathsf{ChatPattern}$ leverages its
extension function, utilizing both out-painting and in-painting algorithms, to
synthesize high-quality patterns. We have illustrated some instances in Figure
8 and Figure 9. The LLM agent is initialized with a predefined working
pipeline, as depicted in Figure 4. The accompanying documentation includes
statistical data on pattern extension through various algorithms, as seen in
Figure 10. This documentation provides an insight that out-painting typically
yields better legality, while in-painting excels in diversity under certain
conditions. The user’s request was simply to generate 10,000 patterns for each
experimental setting. Results tabulated in Table 1 demonstrate
$\mathsf{ChatPattern}$’s superiority over the baseline, particularly in the
demanding task of generating large patterns of sizes $512^{2}$ and above.

###  4.2. Evaluation of LLM agent

We take the user requirement in Figure 4 as a running example to show the LLM
agent’s ability on requirement auto-formatting and unseen mistake-processing.

Requirement Auto-formatting. The LLM agent is required to fill out a standard
requirement list to make sure the target of every sub-task is specific and can
be handled within a simpler script. An example of the requirement list is
following.  # Requirement - subtask 1 ## Basic Part: Topology Size: [200,
200], Physical Size: [1500, 1500] nm, Style: Layer-10001, Count: 50000, ##
Advanced Part: Extension Method: Out (Default: Out), Drop Allowed: True
(Default: True), Time Limitation: None (Default: None).

Figure 10. Evaluation of In-Painting and Out-Painting.

Unseen Mistake-processing. As explored in Section 3, the generation of
extensive topology matrices poses significant time demands. Should the
legalization process fail, the function earmarks the errors within a log. We
present a case where the LLM agent adeptly navigates unanticipated mistakes
during legalization. It is noteworthy that such error-handling expertise is
not pre-coded within the standard operational procedures or the experiential
documentation. This instance serves to highlight the LLM agent’s intrinsic
capacity to address unforeseen complications.

% In previous attempts, one pattern can’t pass the legalization. Thought:
Since legalization has failed twice in the same region, I will try to in-paint
that specific area with the same style and then attempt legalization again.
Action: Topology_Modification Action Input: ”topology_path”:${path}, ”upper”:
12, ”left”: 56, ”bottom”: 33, ”right”: 73, ”style”: ”Layer-10001”, ”seed”: 42
% Continue Processing

##  5\. Conclusion

In this paper, we introduced $\mathsf{ChatPattern}$, a novel framework for
pattern generation utilizing a LLM. $\mathsf{ChatPattern}$ provides a user-
friendly interface that accepts natural language inputs to tailor the pattern
library to specific needs. And $\mathsf{ChatPattern}$ enables a flexible
pattern generation back-end and extends the task of pattern generation to a
more demanding yet challenging setting, free-size pattern generation.
Nonetheless, $\mathsf{ChatPattern}$ still lacks global guidance when
generating large patterns and can not handle complex oversized patterns well,
which we left for future exploration.

## References

  * (1) J.-R. Gao, X. Xu, B. Yu, and D. Z. Pan, “Mosaic: Mask optimizing solution with process window aware inverse correction,” in _DAC_ , 2014, pp. 1–6.
  * (2) J. Kuang and E. F. Young, “An efficient layout decomposition approach for triple patterning lithography,” in _DAC_ , 2013, pp. 1–6.
  * (3) B. Yu, K. Yuan, D. Ding, and D. Z. Pan, “Layout decomposition for triple patterning lithography,” _TCAD_ , vol. 34, no. 3, pp. 433–446, 2015.
  * (4) R. Chen, W. Zhong, H. Yang, H. Geng, X. Zeng, and B. Yu, “Faster region-based hotspot detection,” in _DAC_ , 2019, pp. 1–6.
  * (5) G. R. Reddy, C. Xanthopoulos, and Y. Makris, “Enhanced hotspot detection through synthetic pattern generation and design of experiments,” in _VTS_ , 2018, pp. 1–6.
  * (6) H. Yang, P. Pathak, F. Gennari, Y.-C. Lai, and B. Yu, “Deepattern: Layout pattern generation with transforming convolutional auto-encoder,” in _DAC_ , 2019, pp. 1–6.
  * (7) X. Zhang, J. Shiely, and E. F. Young, “Layout pattern generation and legalization with generative learning models,” in _ICCAD_ , 2020, pp. 1–9.
  * (8) L. Wen, Y. Zhu, L. Ye, G. Chen, B. Yu, J. Liu, and C. Xu, “Layoutransformer: Generating layout patterns with transformer via sequential pattern modeling,” in _ICCAD_ , 2022.
  * (9) Z. Wang, Y. Shen, W. Zhao, Y. Bai, G. Chen, F. Farnia, and B. Yu, “Diffpattern: Layout pattern generation via discrete diffusion,” _arXiv preprint arXiv:2303.13060_ , 2023.
  * (10) F. E. Gennari and Y.-C. Lai, “Topology design using squish patterns,” Sep. 9 2014, uS Patent 8,832,621.
  * (11) S. Sun, Y. Jiang, F. Yang, B. Yu, and X. Zeng, “Efficient hotspot detection via graph neural network,” in _DATE_ , 2022, pp. 1233–1238.
  * (12) W. Zhao, X. Yao, Z. Yu, G. Chen, Y. Ma, B. Yu, and M. D. Wong, “Adaopc: A self-adaptive mask optimization framework for real design patterns,” in _ICCAD_ , 2022, pp. 1–9.
  * (13) G. L. Xuanhe Zhou, Zhaoyan Sun, “Db-gpt: Large language model meets database,” 2023.
  * (14) Z. He, H. Wu, X. Zhang, X. Yao, S. Zheng, H. Zheng, and B. Yu, “Chateda: A large language model powered autonomous agent for eda,” _arXiv preprint arXiv:2308.10204_ , 2023.
  * (15) H. Yang, P. Pathak, F. Gennari, Y.-C. Lai, and B. Yu, “Detecting multi-layer layout hotspots with adaptive squish patterns,” in _DAC_ , 2019, pp. 299–304.
  * (16) J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. van den Berg, “Structured denoising diffusion models in discrete state-spaces,” _NeurIPS_ , vol. 34, pp. 17 981–17 993, 2021.
  * (17) J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” _NeurIPS_ , vol. 33, pp. 6840–6851, 2020.
  * (18) J. Song, C. Meng, and S. Ermon, “Denoising diffusion implicit models,” in _ICLR_ , 2020.
  * (19) A. Lugmayr, M. Danelljan, A. Romero, F. Yu, R. Timofte, and L. Van Gool, “Repaint: Inpainting using denoising diffusion probabilistic models,” in _CVPR_ , 2022, pp. 11 461–11 471.
  * (20) O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” in _MICCAI_. Springer, 2015, pp. 234–241.