# Representation Learning of Logic Circuits

Min Li1, Sadaf Khan1, Zhengyuan Shi1, Naixing Wang2, Yu Huang2 and Qiang Xu1
2Huawei Technologies Co., Ltd., China
{mli, skhan, zyshi21<EMAIL_ADDRESS>1 The Chinese University of Hong
Kong, Shatin, Hong Kong S.A.R.

###### Abstract

Applying deep learning (DL) techniques in the electronic design automation
(EDA) field has become a trending topic in recent years. Most existing
solutions apply well-developed DL models to solve specific EDA problems. While
demonstrating promising results, they require careful model tuning for every
problem. The fundamental question on ”How to obtain a general and effective
neural representation of circuits?” has not been answered yet. In this work,
we take the first step towards solving this problem. We propose DeepGate, a
novel representation learning solution that effectively embeds both logic
function and structural information of a circuit as vectors on each gate.
Specifically, we propose transforming circuits into unified and-inverter graph
format for learning and using signal probabilities as the supervision task in
DeepGate. We then introduce a novel graph neural network that uses strong
inductive biases in practical circuits as learning priors for signal
probability prediction. Our experimental results show the efficacy and
generalization capability of DeepGate.

##  I Introduction

The rise of deep learning (DL) has aroused much interest in applying it to
solve various electronic design automation (EDA) problems that otherwise rely
on some heuristics or hand-engineered rules, as surveyed in [1]. The most
natural representation of circuits and netlists is a graph. With the recent
success of graph neural networks (GNNs) [2, 3] in modeling non-structured
data, various works have explored its potential on EDA problems such as
congestion prediction [4] and testability analysis [5]. These works focus on
learning a particular function that takes the circuit graph as input and
directly maps it to output for desired EDA tasks, without considering the
internal computational process in the circuits.

Recently, a notable trend in the deep learning community is to employ pre-
trained models for many downstream tasks rather than learning a specific model
for each task from scratch [6]. For example, a series of convolutional neural
networks (CNNs) are pre-trained on the ImageNet dataset [7]. They perform well
on other computer vision (CV) tasks such as image segmentation [8] and object
detection [9] by fine-tuning with a small amount of task-specific data.
Similarly, pre-trained Transformer-based language models (e.g., GPT [10] and
BERT [11]) have achieved unparalleled performance on various natural language
processing (NLP) tasks.

Whereas in the EDA domain, despite all the recent efforts in learning-based
solutions [1], obtaining a general and effective circuit representation that
serves as the basis for solving various EDA tasks has not been addressed yet.
In this work, we take the first step towards this direction by introducing a
novel GNN-based solution for the representation learning of logic gates,
namely DeepGate, which is aware of the logic computation procedure and the
structural information of combinational circuits.

Naturally, logic circuits can be modeled as directed acyclic graphs (DAGs), in
which logic gates appear in a specific topological order. Therefore, one could
collect many logic circuits and resort to existing DAG-GNN architecture [12,
13] to learn the node embedding for each logic gate with some supervision
tasks (e.g., Boolean satisfiability [14]). However, we argue that such
straightforward solutions cannot effectively extract information from circuit
graphs.

Firstly, logic circuits could follow different design styles and use diverse
technology libraries containing various logic gate types, leading to
heterogeneous circuit graphs with mixed distributions that are challenging to
learn. In DeepGate, we propose to conduct learning on a general intermediate
representation of logic circuits, i.e., and-inverter graph (AIG), with the
help of logic synthesis tools [15]. The benefits are twofold: (i). Such a
unified format constrains the circuit graph distribution without changing
circuit functionalities. All the transformed circuits only feature two types
of logic gates (i.e., 2-input AND gate and inverter); (ii). The logic
synthesis procedure naturally introduces a strong inductive bias of practical
circuits for effective learning with GNN models.

Secondly, the effectiveness of representation learning heavily relies on
supervision tasks. For example, when pre-training CV models, the image class
labels of the ImageNet dataset serve as the cornerstone. In contrast,
considering the difficulty in annotating a textual dataset as large as
ImageNet, self-supervised tasks are used instead in NLP pre-trained model
development. For effective circuit representation learning, we propose to use
the signal probability (i.e., the probability of being logic ‘1’) for every
node as rich supervision because it embeds the genuine logic relationship of
each node in the circuits. To be specific, we perform logic simulations with a
large amount of random patterns to obtain faithful probability values for
supervision.

Last but most important, existing GNN models are general solutions designed to
extract information from all kinds of graphs, while circuit graphs are a
unique type of graph with logic relationships between nodes. In this work, we
design a dedicated GNN model for circuit graphs, significantly enhancing the
learning effectiveness.

We summarize the contributions of this work as follows:

  * •

To the best of our knowledge, DeepGate is the first work for the general and
effective circuit representation learning problem. Specially, we propose a
novel design flow to tackle this problem: (i). circuit transformation in AIG
form; (ii). supervision with logic-simulated probabilities; (iii).
representation learning with a dedicated GNN model for circuit graphs.

  * •

We propose a novel GNN model for circuit graphs that exploits unique circuit
properties, including attention mechanisms that mimic the logic computation
procedure and reversed propagation layers that consider logic implication
effects.

  * •

Reconvergence structures are inevitable due to logic sharing in multi-level
logic networks, and they are the main challenges for logic analysis [16]. We
treat them as first-class citizen and introduce novel solutions in our GNN
model.

We learn the representations of logic gates with many small subcircuits
extracted from benchmark circuits. Experimental results performed on large
circuits show the efficacy and generalization capability of DeepGate. We
organize the remainder of this paper as follows. We review related works in
Section II. Section III introduces the DeepGate architecture, while in Section
IV, we present the experimental results on various circuits. Finally, Section
V concludes this paper.

##  II Related Works

Figure 1: The Circuit Representation as DAG

###  II-A Graph Neural Networks

Graph neural networks [3, 2] have received a lot of attention for their
effectiveness in modeling non-structured data. By learning vectorial
representations on graphs via feature propagation and aggregation, GNNs show
convincing results in various domains [17, 18, 19]. The most popular GNN model
employs a message-passing neural network architecture, which computes
representation/hidden states $\mathbf{h}_{v}^{\ell}$ for node $v$ in a graph
$\mathcal{G}$ at every layer $\ell$ and a final graph representation
$\mathbf{h}_{\mathcal{G}}$, as in [18]:

$\footnotesize\mathbf{h}_{v}^{\ell}=\text{COMBINE}^{\ell}(\mathbf{h}_{v}^{\ell-1},\text{AGGREGATE}^{\ell}(\\{\mathbf{h}_{u}^{\ell-1}|u\in\mathcal{N}(v)\\})),\ell=1,.,L$
(1)
$\small\mathbf{h}_{\mathcal{G}}=\text{READOUT}(\\{\mathbf{h}_{v}^{L},v\in\mathcal{V}\\})$
(2)

wherein $N(v)$ denotes neighboring nodes of node $v$ and $L$ is the number of
layers. The parameterized function $\text{AGGREGATE}^{\ell}$ aggregates
messages from neighboring nodes $N(v)$, and $\text{COMBINE}^{\ell}$ obtains an
updated hidden state after aggregation. Finally, the function
$\text{READOUT}^{\ell}$ retrieves the states of all nodes $\mathcal{V}$ and
produces the graph neural representation. A notable GNN architecture is the
graph attention network (GAT) [20] that considers the importance of different
neighbors during aggregation.

Directed acyclic graphs (DAGs) are a special type of graphs, yet broadly seen
across many domains, including circuit modeling (see Fig. 1). Recently, few
studies have been dedicated to DAG-GNN designs [12, 13], which propagate the
message following the topological ordering between nodes and only consider the
predecessors in the $\text{AGGREGATE}^{\ell}$ function, as demonstrated in
Equation (3).

$\footnotesize\mathbf{h}_{v}^{\ell}=\text{COMBINE}^{\ell}(\mathbf{h}_{v}^{\ell-1},\text{AGGREGATE}^{\ell}(\\{\mathbf{h}_{u}^{\ell}|u\in\mathcal{P}(v)\\})),\ell=1,...,L$
(3)

The major difference between Eq. (3) and Eq. (1) is that in DAG-GNN, the
aggregation function for $v$ will be only executed after all of its
predecessors’ hidden states have already been computed.

Besides stacking $L$ layers to increase the depth of the network, one can also
apply the same model for $T$ times in the recurrent fashion to generate the
final embedding [14]:

$\footnotesize\mathbf{h}_{v}=\text{COMBINE}(\mathbf{h}_{v}^{t-1},\text{AGGREGATE}(\\{\mathbf{h}_{u}^{t}|u\in\mathcal{P}(v)\\})),t=1,...,T$
(4)

Using the taxonomy defined in [21], we name the two variants of DAG-GNNs
described in Equations (3)–(4) as DAG-ConvGNNs and DAG-RecGNNs, respectively.

###  II-B GNN-Based Solutions for EDA Problems

Existing GNN-based EDA solutions use an end-to-end flow for specific EDA tasks
wherein the labels are usually extracted from commercial EDA tools.

To the best of our knowledge, the first GNN-based EDA technique is applied to
the test point insertion (TPI) problem, which is formulated as a node binary
classification problem and solved with a graph convolutional network [5]. The
ground-truth labels are collected from commercial TPI tools, revealing whether
a particular node is ”easy to observe” or not. CongestionNet [4] models the
circuit as an undirected graph and trains a GAT model to predict the
congestion of the final physical design on a per-cell basis. GRANNITE [22]
conducts power estimation using a DAG-GNN model. Gate netlists are mapped onto
graphs with per-node (gate) and per-edge (net) features. They achieved good
accuracy (less than 5.5% error across a diverse set of benchmarks) for fast
(¡1 second) average power estimation on designs up to 50k gate. Recently, [23]
proposes a GAT-based model named $Net^{2}$ for pre-placement net length
estimation.

To solve a particular EDA problem, the above techniques typically pre-compute
many node/edge features (e.g., SCOAP testability measures in [5]) and use
existing GNN models to aggregate these features for solution findings.
Consequently, the learned node features cannot be transferred among related
tasks, despite using the same circuit graphs as inputs. More importantly, an
effective representation for circuits should be aware of their logic
functions. However, existing solutions ignore it and only consider the
structural information in their learning procedure.

Motivated by the above, we propose to learn a general and effective circuit
representation without pre-computing any specific features, as detailed in the
following section.

##  III Proposed Solution

Figure 2: The Overview of DeepGate.

###  III-A Overview of DeepGate

Figure 2 presents the overview of the proposed DeepGate solution, consisting
of two stages for the neural representation learning of logic gates:

  * •

Circuit Data Preparation: Given a pool of circuit designs, we use logic
synthesis tools to transform them into a unified AIG format. We then perform
logic simulations on the circuits with sufficient random patterns to obtain
the signal probability (i.e., the probability of node being logic ‘1‘) on
every node as supervision. We elaborate the details in Section III-B.

  * •

Probabilities Prediction with DeepGate: Given a circuit dataset and the logic-
simulated probabilities as the supervision task, we introduce a novel GNN
model dedicated for circuit graph analysis to learn the neural representations
of logic gates, as detailed in Section III-C.

###  III-B Circuit Data Preparation

Some circuits are at the register-transfer level, while others are gate-level
netlists mapped with various libraries. Such heterogeneity across circuits is
a challenge for GNN model development. To tackle this problem, we resort to
the logic synthesis tool ABC [15] and transform all circuits into the unified
AIG format. If the original circuit is too large, we extract small sub-
circuits with circuit sizes ranging from $30$ to $3k$ gates. Note that, we
test the effectiveness of DeepGate on much larger circuits for its
generalization capabilities.

The benefits of such circuit pre-processing flow include: (i). Only two logic
gate types (i.e., 2-input AND gate and 1-input Not gate) are considered, which
would dramatically reduce representation learning difficulty; (ii). Applying
logic synthesis introduces strong relational inductive bias into the resulting
circuit graphs; (iii). The constraint on circuit size facilitates efficient
GNN training with both reduced sizes of circuit graphs and less time for
preparing supervision labels.

There are many possibilities to annotate a circuit, e.g., the satisfiability
of the circuit [14]. However, a good supervision task should satisfy the
following condition: the labels should be easily obtained while retaining rich
information for both the logic function and the structural information of the
circuits. In DeepGate, we propose to use the signal probability on every node
as supervision, which satisfies the above requirements: (i). It is relatively
easy to obtain highly-accurate probability values by running logic simulations
on many random input patterns, especially when the circuit size is limited;
(ii). A unique yet important property of logic circuits that makes circuit
analysis challenging is the reconvergence structures, and logic simulation is
arguably the only way to obtain the actual value for such structures; (iii).
The logic probability of each gate itself plays an essential role in many EDA
tasks.

###  III-C GNN Model in DeepGate

Given circuit graphs in AIG form, the objective of our GNN model is to
estimate the probability of every node such that it would be as close to the
genuine signal probability as possible. Different from existing DAG-ConvGNNs
[13, 12] and DAG-RecGNNs [14] models that focus on learning the topological
information in the graph, DeepGate is designed to learn both the circuit
structural information and the computational behaviour of logic circuits, and
embed them as vectors on every logic gate.

We now elaborate on the detailed GNN model design in DeepGate. Given a circuit
graph $\mathcal{G}$, we embed the gate type of each node $v$ with one-hot
encoding in $\mathbf{x}_{v}$. To be specific, as only primary inputs (PIs),
And gates and Not gates are present in AIGs, we assign a $3$-d vector for each
node according to its gate type. It should be noted that instead of relying on
the probability-based measurements in previous works [22, 5], our model only
requires gate type information for the representation learning. We also have
hidden states $\mathbf{h}_{v}$ for every node, which is initialized randomly.
Given these, DeepGate resorts to attention-based aggregation design [13, 20]
and the gated recurrent unit (GRU) [12] as the update function.

Aggregation. We use the attention mechanism in the additive form to
instantiate the AGGREGATE function in Equation (3), wherein the aggregated
message $\mathbf{m}_{v}^{t}$ for a node $v$ at $t^{th}$ iteration is computed
by:

$\small\mathbf{m}_{v}^{t}=\sum_{u\in\mathcal{P}(v)}\alpha_{uv}^{t}\mathbf{h}_{u}^{t}\text{\quad
where\quad}\alpha_{uv}^{t}=\mathop{softmax}\limits_{u\in\mathcal{P}(v)}(w_{1}^{\top}\mathbf{h}_{v}^{t-1}+w_{2}^{\top}\mathbf{h}_{u}^{t})$
(5)

where $\alpha_{uv}^{t}$ is a weighting coefficient that is computed by
following the query-key design as in usual attention mechanisms. To be
specific, $\mathbf{h}_{v}^{t-1}$ serves as query, and representation of
predecessors from current iteration $t$, $\mathbf{h}_{u}^{t}$, serves as key.
The intuition behind using the attention mechanism for aggregation is that
when we do the logic computation in digital circuits, the controlling value of
a logic gate determines the output of that gate. Therefore, controlling values
are far more important than non-controlling values. To mimic this behaviour,
the attention mechanism can learn to assign high weights for controlling
inputs of gates and give less importance to the rest of the inputs.

Combine. We then use the GRU to instantiate the COMBINE function for updating
the hidden state of target node $v$:

$\mathbf{h}_{v}^{t}=GRU([\mathbf{m}_{v}^{t},\mathbf{x}_{v}],\mathbf{h}_{v}^{t-1})$
(6)

wherein $\mathbf{m}_{v}^{t}$, $\mathbf{x}_{v}$ are concatenated together and
treated as input, while $\mathbf{h}_{v}^{t-1}$ is the past state of GRU.

On the one hand, DeepGate adopts the recursive DAG-GNNs functional defined in
Equation (4). The reasons for using the recurrent architecture are two-fold:
(i). it is unrealistic for GNNs to capture the circuit’s functional and
structural information with a single forward propagation; (ii). the recurrent
learning procedure facilitates reaching stabilized node embeddings quickly.

On the other hand, our proposed GNN model differs from previous DAG-GNNs [14,
13, 12] that initialize $\mathbf{h}_{v}^{0}$ as $\mathbf{x}_{v}$ and treat the
aggregated message as the state of recurrent function. In contrast, we fix the
gate type information of nodes $\mathbf{x}_{v}$ as inputs for all iterations.
Such employment can avoid the information vanishing of gate properties during
the long-term recursive propagation.

Reversed Propagation Layer. In DeepGate, we also consider backward information
propagation, i.e., processing the graph in reversed topological order. One of
the main reasons to introduce the backward layers in our framework is that
logic implication and backtracking in the reversed order can be highly useful
for predicting the states of nodes. It also helps stabilize training, as
proved in sequence-to-sequence learning tasks [24].

Regressor. After $T$ iterations, we pass the hidden states of nodes
$\mathbf{h}_{v}^{T}$ into a multi-layer perceptron (MLP), which computes a
single scalar for every node to regress the simulated probabilities. The
weights of MLP are shared for nodes with the same gate types. We train the
network to minimize the L1 loss between the prediction $\hat{y}_{v}$ and the
true probability $y_{v}$.

Figure 3: Information Propagation at Reconvergence Node using Skip Connection

###  III-D Skip Connection for Reconvergence Structure with Positional
Encoding

In the previous section we have described the core components of DeepGate
necessary for predicting the logic probabilities of nodes. However, the logic
inference on reconvergence nodes is different from normal nodes and such
structures are inevitable due to logic sharing in multi-level logic networks.
Hence, they are the main challenge for logic probability analysis. To
accommodate their impact, we introduce the improvement into DeepGate to enable
special processing for reconvergence nodes as shown in Figure 3.

Firstly, we maintain the information of reconvergence nodes during circuit
data preparation, including its corresponding source fan-out node, and the
logic level difference between the source nodes and reconvergence nodes.
Secondly, we add direct edges between the fan-out node and the reconvergence
node, named skip connection here. The new edges facilitate the information
exchange from fan-out nodes to reconvergence nodes. Last but not least, we
leverage the positional encoding technique [25] to differentiate the skip
connection and the normal connection. To be specific, the function $\gamma(D)$
is a mapping of logic level difference $D$ between source fan-out node and
reconvergence node into a higher dimensional space $\mathbb{R}^{2L}$:

$\footnotesize\gamma(D)=(\sin(2^{0}\pi D),\cos(2^{0}\pi
D),\cdots,\sin(2^{L-1}\pi D),\cos(2^{L-1}\pi D))$ (7)

The impact of the fanout node on the reconvergence nodes depends upon the
distance between them. Generally speaking, the longer the distance is, the
lesser impact it has on the reconvergence node. The above function can induce
the knowledge of how much fanout node can impact the result of reconvergence
node into the model. We assign the encoded vector as the edge attributes to
skip connection and incorporate it into the coefficient calculation described
in Equation (5) as the third input.

##  IV Experiments

###  IV-A Datasets

TABLE I: The Statistics of Circuit Training Dataset Benchmark | #Subcircuits | #Node | #Level
---|---|---|---
EPFL | 828 | [52–341] | [4–17]
ITC99 | 7,560 | [36–1,947] | [3–23]
IWLS | 1,281 | [41–2,268] | [5–24]
Opencores | 1,155 | [51–3,214] | [4–18]
Total | 10,824 | [36–3,214] | [3–24]

We extract many sub-circuits from four circuit benchmark suites: ITC’99 [26],
IWLS’05 [27], EPFL [28] and OpenCore [29], and follow the circuit data
preparation flow described in Section III-B to transform all circuits into a
unified AIG format. We conduct logic simulations with up to $100k$ random
input patterns to obtain an accurate signal probability on every node.

Table I presents the statistics of the circuit dataset. #Subcircuits shows the
total number of subcircuits extracted from each benchmark. As shown in the
table, the constructed circuit dataset covers circuit sizes ranging from tens
to thousands of nodes with different logic levels. Finally, there are $10,824$
circuits in total, and we create $90/10$ training/test splits for model
training and evaluation.

###  IV-B Evaluation Metric and Baselines

To evaluate the performance of different GNN models, we calculate the average
value of the absolute differences between the simulated probability $y_{v}$
and the predicted $\hat{y}_{v}$ from DeepGate for all nodes $\mathcal{V}$ in
the circuits, as shown in equation (8). The smaller the value is, the better
the model performs.

$Avg.~{}Prediction~{}Error=\frac{1}{N}\sum_{v\in\mathcal{V}}{\left|y_{v}-\hat{y}_{v}\right|}$
(8)

We consider three GNN models: GCN, DAG-ConvGNN, and DAG-RecGNN. GCN model
treats the circuit graphs as undirected graphs in representation learning.
DAG-ConvGNN model follows the settings defined in Equation (3). For DAG-RecGNN
model, we adopt the same COMBINE function and the reversed propagation layer
design in DeepGate, as depicted in Section III-C. As for the GNN model in
DeepGate, it contains additional attention mechanism and skip connection (SC).
Under every setting, we evaluate 4 different aggregator designs, which include
representative works for DAG learning, i.e., Convolutional Sum (abbreviated as
Conv. Sum) [30], Attention [20, 13], GatedSum [12] and DeepSet [14].

In order to make the comparison fair, we instantiate all models with $d=64$
for the node hidden states $\mathbf{h}_{v}$ and design the other parameterized
functions to have a similar number of tunable parameters. For DAG-RecGNNs and
our DeepGate model, a forward layer is followed by a reversed layer, and
$T=10$ iterations of message passing are performed to obtain the final
embeddings. We choose $L=8$ in Equation (7) for the skip connection setting.
For training, all models are optimized for $60$ epochs using the ADAM
optimizer with a learning rate of $1\times 10^{-4}$. We use the topological
batching technique introduced in [13] to accelerate the training.

TABLE II: The Performance Comparison of DeepGate with other GNN models for Logic Probability Prediction Model | Aggregator | Avg. Prediction Error
---|---|---
GCN | Conv. Sum | 0.1386
| Attention | 0.1840
| DeepSet | 0.2541
| GatedSum | 0.1995
DAG-ConvGNN | Conv. Sum | 0.2215
| Attention | 0.2398
| DeepSet | 0.2431
| GatedSum | 0.2333
DAG-RecGNN | Conv. Sum | 0.0328
(T=10) | DeepSet | 0.0302
| GatedSum | 0.0329
DeepGate | Attention w/o SC | 0.0234
(T=10) | Attention w/ SC | 0.0204

###  IV-C Probability Prediction

####  IV-C1 Comparison of DeepGate with Baseline Solutions

Table II compares DeepGate with other baseline solutions in terms of
prediction error. From this table, we have several observations: First, both
GCN and DAG-ConvGNN are subject to poor performance for probability
prediction, mainly due to their lack of ability to model the computational
behaviours of circuits. For instance, the best GCN model, equipped with Conv.
Sum, gives $0.1386$ of prediction error, which in turn is even higher than the
worst performing model of DAG-RecGNN. Therefore, only by incorporating the
logical ordering into the model design and conducting the propagation
recurrently, will make the model perform well. It shows the advantage of DAG-
RecGNN implementation with dedicated recurrent scheme and reversed layer
design discussed in Section III-C over simpler GNN architectures. Second,
among all models, DeepGate with attention alone achieves significant
prediction error reduction. It brings $22.76\%$ relative improvement compared
with the best baseline solution, which is the DAG-RecGNN model equipped with
DeepSet aggregator. Hence, using the dedicated attention mechanism benefits
logic representation learning. Third, equipped with skip connection design,
DeepGate can further reduce the prediction error from $0.0234$ to $0.0204$,
which reveals the efficacy of introducing the reconvergence knowledge into the
model design. To summarize, with only the gate type information and the
connectivity between gates, DeepGate learns to predict highly-accurate
probabilities for logic gates.

As we observe that DAG-RecRNN with DeepSet aggregator (abbreviated as DeepSet
for the following discussion) performs better than the other baselines, in
later results, we only compare DeepGate (w/ skip connection) with it.

####  IV-C2 Results on Large Circuits

Furthermore, we evaluate DeepGate on five circuit designs that are
substantially larger than the circuits it saw during training. The circuit
statistics and the prediction error of both DeepGate and DeepSet are shown in
Table III. The number of gates in these designs is two orders of magnitude
more than that of the training circuits.

We can observe that DeepGate achieves similar prediction accuracy as that on
small circuits, and it outperforms DeepSet in these large circuits by a large
margin. Such results clearly demonstrate the generalization capability of
DeepGate. In particular, DeepGate achieves $73.56\%$ prediction error
reduction on Arbiter. This is because, the Arbiter circuit is designed to
accommodate access from multiple requests, and it contains repetitive logic
units with many reconvergence structures. As DeepGate treats such structures
as a first-class citizen in the GNN model, it can generate much more accurate
predictions.

TABLE III: The Performance Comparison of DeepGate and DeepSet on Five Large Circuits Design | #Nodes | Levels | DeepSet | DeepGate | Reduction
---|---|---|---|---|---
Arbiter | 23.7K | 173 | 0.0277 | 0.0073 | 73.56%
Squarer | 36.0K | 373 | 0.0495 | 0.0346 | 30.16%
Multiplier | 47.3K | 521 | 0.0220 | 0.0159 | 27.94%
80386 Processor | 13.2K | 122 | 0.0534 | 0.0387 | 27.56%
Viper Processor | 40.5K | 133 | 0.0520 | 0.0389 | 25.18%

###  IV-D Discussion

####  IV-D1 Effectiveness of Circuit Transformation

DeepGate uses the logic synthesis tool to transform the circuits from
different sources into unified AIG forms. One may wonder the performance of
DeepGate if the network is directly trained on the original circuits, wherein
other gate types (e.g., XOR, NAND, NOR, and OR) are also included. To
investigate the effectiveness of the circuit transformation in DeepGate, we
conduct the controlled experiments on EPFL and IWLS benchmarks, as shown in
Table IV.

Take EPFL as an example, we extract $375$ sub-circuits from the original
designs, and develop two versions: the ones with the original $6$ gates types
and the other with AIG transformation. For each version, we train the DeepGate
model from scratch. The only difference is that for the former version of the
dataset, we assign $7$-d one-hot encoding for the node feature
$\mathbf{x}_{v}$. As can be observed from Table IV, DeepGate trained on AIGs
performs better than the one trained on the original circuits by a large
margin ($33.94\%$ relative prediction error reduction on EPFL). The same
observation can be obtained from the results on IWLS circuits.

Such improvements originate from the benefit of circuit transformation because
when only two logic gate types are considered, representation learning
difficulty is reduced dramatically without any impact on circuit
functionalities. Also, we manually check the usage frequency of different gate
types in the original formats, and observe that some gates types (e.g., XOR
and NAND) are used much less frequently. Such in-balanced gate distributions
may lead to insufficient training, causing higher prediction errors.

Additionally, we directly apply the pre-trained DeepGate model on the merged
AIG dataset, as shown in Section IV-A for comparison. As can be observed,
DeepGate trained on the dataset consisting of different benchmarks can further
reduce the prediction errors by $51.37\%$. It supports the claim that unifying
different circuit designs into a common intermediate representation can help
the model learn a better representation of logic gates.

TABLE IV: The Performance of DeepGate with and without Circuit Transformation | w/o Tran. | w/ Tran. | Pre-trained
---|---|---|---
EPFL | 0.0442 | 0.0292 | 0.0142
IWLS | 0.0447 | 0.0342 | 0.0209

####  IV-D2 Impact of Recurrence Iterations

During the inference phase, the number of iterations $T$ can be set as
different values. The higher the value, the higher the computational cost.

We enumerate different values for $T$, ranging from $1$ to $50$. We observe
that our GNN model is able to decrease the prediction loss as $T$ increases.
However, the prediction error converges quickly at around $T=10$, despite the
circuit size. Such experimental results further demonstrate the scalability of
the proposed DeepGate solution.

##  V Conclusion and Future Work

This paper proposes DeepGate, a novel representation learning solution that
effectively embeds both logic functions and structural information of a
circuit as vectors on each gate. In DeepGate, we construct easy-to-learn
circuit graphs by transforming circuits into unified AIG format and introduce
a novel GNN model with circuit knowledge as priors for effective
representation learning. Using informative signal probability as supervision
tasks on small sub-circuits, we show DeepGate can generalize to large circuits
with accurate predictions without any pre-computed features.

While showing promising results, the current implementation of DeepGate can
still be significantly improved. For example, we could introduce other
informative supervision tasks (e.g., logic inference and Boolean
satisfiability) to achieve better representations for logic gates. We could
also add more circuits for training to build a large-scale foundation model
for logic circuits [31]. Moreover, in our future work, we plan to apply the
representations learned in DeepGate onto many downstream EDA tasks (e.g.,
power estimation, logic reduction, and equivalence checking). These tasks are
directly related to signal probability analysis, and we believe DeepGate can
achieve satisfactory results without much effort in finetuning the model.

## References

  * [1] G. Huang, J. Hu, Y. He, J. Liu, M. Ma, Z. Shen, J. Wu, Y. Xu, H. Zhang, K. Zhong _et al._ , “Machine learning for electronic design automation: A survey,” _TODAES_ , vol. 26, no. 5, pp. 1–46, 2021.
  * [2] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [3] W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _NIPS_ , 2017, pp. 1025–1035.
  * [4] R. Kirby, S. Godil, R. Roy, and B. Catanzaro, “Congestionnet: Routing congestion prediction using deep graph neural networks,” in _2019 VLSI-SoC_. IEEE, pp. 217–222.
  * [5] Y. Ma, H. Ren, B. Khailany, H. Sikka, L. Luo, K. Natarajan, and B. Yu, “High performance graph convolutional networks with applications in testability analysis,” in _DAC_ , 2019, pp. 1–6.
  * [6] X. Han, Z. Zhang, N. Ding, Y. Gu, X. Liu, Y. Huo, J. Qiu, L. Zhang, W. Han, M. Huang _et al._ , “Pre-trained models: Past, present and future,” _AI Open_ , 2021.
  * [7] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” _NIPS_ , pp. 1097–1105, 2012.
  * [8] S. Minaee, Y. Y. Boykov, F. Porikli, A. J. Plaza, N. Kehtarnavaz, and D. Terzopoulos, “Image segmentation using deep learning: A survey,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2021.
  * [9] S. Ren, K. He, R. Girshick, and J. Sun, “Faster r-cnn: Towards real-time object detection with region proposal networks,” _NIPS_ , pp. 91–99, 2015\.
  * [10] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell _et al._ , “Language models are few-shot learners,” _arXiv preprint arXiv:2005.14165_ , 2020.
  * [11] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [12] M. Zhang, S. Jiang, Z. Cui, R. Garnett, and Y. Chen, “D-vae: A variational autoencoder for directed acyclic graphs,” 2019.
  * [13] V. Thost and J. Chen, “Directed acyclic graph neural networks,” in _ICLR_ , 2021.
  * [14] S. Amizadeh, S. Matusevych, and M. Weimer, “Learning to solve circuit-SAT: An unsupervised differentiable approach,” in _ICLR_ , 2019.
  * [15] R. Brayton and A. Mishchenko, “Abc: An academic industrial-strength verification tool,” in _CAV_. Springer, 2010, pp. 24–40.
  * [16] M. Roberts and P. Lala, “Algorithm to detect reconvergent fanouts in logic circuits,” _IEEE Proceedings Computers and Digital Techniques_ , 1987.
  * [17] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec, “Open graph benchmark: Datasets for machine learning on graphs,” _arXiv preprint arXiv:2005.00687_ , 2020.
  * [18] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chemistry,” in _ICML_ , 2017, pp. 1263–1272.
  * [19] L. Wu, P. Sun, R. Hong, Y. Fu, X. Wang, and M. Wang, “Socialgcn: An efficient graph convolutional network based model for social recommendation,” _arXiv preprint arXiv:1811.02815_ , 2018.
  * [20] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” _ICLR_ , 2017.
  * [21] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _IEEE transactions on neural networks and learning systems_ , vol. 32, no. 1, pp. 4–24, 2020.
  * [22] Y. Zhang, H. Ren, and B. Khailany, “Grannite: Graph neural network inference for transferable power estimation,” in _DAC_. IEEE, 2020, pp. 1–6.
  * [23] Z. Xie, R. Liang, X. Xu, J. Hu, Y. Duan, and Y. Chen, “Net2: A graph attention network method customized for pre-placement net length estimation,” in _ASP-DAC_. IEEE, 2021, pp. 671–677.
  * [24] I. Sutskever, O. Vinyals, and Q. V. Le, “Sequence to sequence learning with neural networks,” 2014.
  * [25] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _NIPS_ , 2017, pp. 5998–6008.
  * [26] S. Davidson, “Characteristics of the itc’99 benchmark circuits,” in _ITSW_ , 1999.
  * [27] C. Albrecht, “Iwls 2005 benchmarks,” in _IWLS_ , 2005.
  * [28] L. Amarú, P.-E. Gaillardon, and G. De Micheli, “The epfl combinational benchmark suite,” in _IWLS_ , no. CONF, 2015.
  * [29] O. Team, “Opencores,” https://opencores.org/.
  * [30] D. Selsam, M. Lamm, B. Bünz, P. Liang, L. de Moura, and D. L. Dill, “Learning a sat solver from single-bit supervision,” _arXiv preprint arXiv:1802.03685_ , 2018.
  * [31] R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S. Bernstein, J. Bohg, A. Bosselut, E. Brunskill _et al._ , “On the opportunities and risks of foundation models,” _arXiv preprint arXiv:2108.07258_ , 2021.


# Learned Lossless Image Compression Through Interpolation With Low Complexity

Fatih Kamisli The author is with the Department of Electrical and Electronics
Engineering at the Middle East Technical University, Ankara, Turkey. (email:
kamisli@metu.edu.tr)Codes are available at https://github.com/metu-
kamisli/LLICTI

###### Abstract

With the increasing popularity of deep learning in image processing, many
learned lossless image compression methods have been proposed recently. One
group of algorithms that have shown good performance are based on learned
pixel-based auto-regressive models, however, their sequential nature prevents
easily parallelized computations and leads to long decoding times. Another
popular group of algorithms are based on scale-based auto-regressive models
and can provide competitive compression performance while also enabling simple
parallelization and much shorter decoding times. However, their major drawback
are the used large neural networks and high computational complexity. This
paper presents an interpolation based learned lossless image compression
method which falls in the scale-based auto-regressive models group. The method
achieves better than or on par compression performance with the recent scale-
based auto-regressive models, yet requires more than 10x less neural network
parameters and encoding/decoding computation complexity. These achievements
are due to the contributions/findings in the overall system and neural network
architecture design, such as sharing interpolator neural networks across
different scales, using separate neural networks for different parameters of
the probability distribution model and performing the processing in the
YCoCg-R color space instead of the RGB color space.

###### Index Terms:

Image compression, Artificial neural networks, Entropy coding, Lossless
compression

##  I Introduction

Most image and video communication applications use lossy compression,
however, there are also applications that require lossless compression.
Lossless compression allows the original data to be perfectly reconstructed
from the compressed bitstream without any loss of information. For example,
medical imaging, satellite imaging, professional photography and digital
cinema are applications where lossless image or video compression is used.
This paper presents a novel learned lossless image compression method.

Classical lossless image compression methods are based on pixel [1, 2, 3, 4]
or block based prediction [5, 6, 7], inter-to-integer transforms [8] or both
[9]. In the prediction based methods, the compression is typically performed
in a raster scan order of pixels or blocks. A pixel or a block of pixels is
predicted using previously coded left and upper neighbor pixels or neighboring
left and upper pixels of the block, and the prediction error pixel or block is
then entropy coded. Then the compression of the next pixel or block starts.
The prediction error pixels are typically more decorrelated than the original
pixels, allowing good compression performance with simple entropy codes. For
example, JPEG-LS [1] is based on a pixel based prediction algorithm and
lossless compression in HEVC [7, 10] is based on a block based prediction
algorithm.

In the integer-to-integer transform based lossless compression methods, the
integer-valued image pixels are transformed into a transform domain with
integer-valued coefficients [11, 8, 9]. The transformation is invertible and
thus no loss of information occurs. For example, lossless compression in
JPEG2000 is based on the integer 5/3 wavelet transform [11, 12, 13]. The
obtained transform coefficients are again more decorrelated than the image
pixels and allow for good compression performance with simple entropy codes.
It can also be useful to use the prediction and integer-to-integer transform
methods together in some contexts [9].

With the high expressive power of artificial neural networks and the recent
advances and interest in deep learning, lossy [14, 15, 16, 17] and lossless
[18, 19, 20] image compression methods with neural networks have been
proposed. The state of the art in learned lossy [17, 21] and lossless [19, 20]
image compression is on par with or exceeds the compression performance of
state of the art classical compression methods [22, 4].

Recent learned lossless image compression methods can be roughly categorized
to three groups: methods based on pixel-based auto-regressive models, methods
based on integer discrete flows and methods based on scale-based auto-
regressive models. Methods based on pixel-based auto-regressive models are
similar to the methods based on classical pixel based prediction methods in
the sense that they encode/decode the image in a pixel-by-pixel manner yet use
neural networks to obtain the probabilities of the pixel to be coded/decoded
from previously encoded/decoded neighbor pixels. While achieving quite good
compression performance, their major drawback is the long decoding times due
to the sequential runs of the neural network for every pixel in the image [23,
24]. Methods based on integer discrete flows are similar to classical systems
based on inter-to-integer transforms as discrete flows are neural network
based systems mapping integer pixels to integer latent/transform variables.
Their major drawback is that they require quite big neural networks for good
compression performance [25]. Methods based on scale-based auto-regressive
models decompose the original image into a multiple scale representation,
encode/decode first the lowest resolution scale and then encode/decode the
remaining scales sequentially conditioned on previously encoded/decoded
scales. These systems typically fare better than the previous two in terms of
encoding/decoding speed and/or neural networks size [18, 19, 20].

This paper presents a learned lossless image compression algorithm that falls
in the scale-based auto-regressive model category. The system first
encodes/decodes a sub-sampled grid of the original image grid (e.g. every
$32^{nd}$ pixel horizontally and vertically) using simple fixed-length codes.
Then it progressively interpolates (i.e. produces probability distributions
of) finer sub-sampled grids of the original image grid conditioned on all
previously encoded/decoded grids so far, to achieve the encoding/decoding of
the entire image. The interpolators are all neural network based and learned
from a dataset.

The contributions of this paper are as follows. The system presented achieves
better than or on par compression performance with the recent literature, yet
requires more than 10x less neural network parameters and encoding/decoding
computational complexity [18, 19, 20]. These achievements are due to the
contributions/findings in the overall system and neural network architecture
design, such as

  * •

using the same interpolator neural networks in different scales,

  * •

using separate neural networks for different parameters of the probability
distribution and

  * •

performing the processing in the YCoCg-R color space instead of the RGB color
space,

which all help to improve compression performance and/or reduce complexity, as
detailed in Section III and IV.

The remainder of the paper is organized as follows. Section II reviews recent
work on learned lossless image compression with scale-based auto-regressive
models. Section III presents the proposed method of learned lossless image
compression through interpolation. Section IV presents experimental results
and comparisons and Section V concludes the paper.

##  II Scale-based auto-regressive models

In L3C [18], which is the first to propose a scale-based auto-regressive
model, a three scale model is used. First, all scale representations denoted
$z^{(i)},~{}i=1,2,3$ are obtained at the encoder by processing the previous
scale representation with encoder neural networks $E^{(i)}(.)$ and then
quantizing the scale representation variables to the nearest integer:

$\displaystyle x^{(i+1)}$ $\displaystyle\leftarrow E^{(i)}(x^{(i)}),$
$\displaystyle z^{(i+1)}$ $\displaystyle\leftarrow Q(x^{(i+1)})\qquad i=0,1,2$
(1)

The original image is the initial scale representation $x^{(0)}$ and $Q(.)$ is
the quantization operator. Each scale representation has half the horizontal
and vertical resolution of the previous scale. The last scale’s probability
distribution is assumed uniform and each preceding scale’s probability
distribution is conditioned on the next scale:

$\displaystyle p(z^{(3)})\sim uniform$ (2) $\displaystyle
p(z^{(i-1)}|z^{(i)})\qquad i=3,2$ (3) $\displaystyle p(x^{(0)}|z^{(1)})$ (4)

Based on the probability models, first, the last scale $z^{(3)}$ is
transmitted by the encoder to the decoder with simple fixed length codes.
Then, starting with $z^{(3)}$, both the encoder and decoder process the scale
representation $z^{(i)}$ with neural networks to obtain the conditional
probability distribution of the previous scale $p(z^{(i-1)}|z^{(i)})$ and
encode/decode it. This is repeated until the original image is
encoded/decoded.

The lossless image compression through super resolution (SReC) [19] paper has
a framework similar to L3C but the major differences are how the multiscale
representations are obtained and the progressive modeling of the probability
distribution of each scale. Unlike in L3C, the scale representations $x^{(i)}$
are obtained simply by average pooling every 2x2 pixel group of the previous
scale and rounding to the nearest integer:

$\displaystyle x^{(i+1)}$ $\displaystyle\leftarrow
AvgPool_{2x2}(x^{(i)})\qquad i=0,1,2$ (5)

Each scale representation’s pixels are split to four groups based on even and
odd rows and columns:

$\displaystyle\\{x^{(i)}_{00},x^{(i)}_{01},x^{(i)}_{10},x^{(i)}_{11}\\}$
$\displaystyle\leftarrow x^{(i)}$ (6)

Starting with the second last scale ($i=3$), each scale’s probability
distribution is progressively obtained by modeling each group’s probability
distribution conditioned on the next scale and the previous groups in the same
scale:

$\displaystyle p(x^{(i-1)}_{00}|x^{(i)}),$ (7) $\displaystyle
p(x^{(i-1)}_{01}|x^{(i)},x^{(i-1)}_{00}),$ (8) $\displaystyle
p(x^{(i-1)}_{10}|x^{(i)},x^{(i-1)}_{00},x^{(i-1)}_{01}),$ (9)

The last group’s pixels ($x^{(i-1)}_{11}$) are obtained from the first three
groups and the next scale since the next scale was obtained by average
pooling:

$\displaystyle x^{(i-1)}_{11}$ $\displaystyle\leftarrow
4x^{(i)}-x^{(i-1)}_{00}-x^{(i-1)}_{01}-x^{(i-1)}_{10}+\\{-1/0/1/2\\},$ (10)

Note that some additional bits (represented by $\\{-1/0/1/2\\}$ in the above
equation) are transmitted by the encoder to accurately find the
$x^{(i-1)}_{11}$ pixels due to the rounding operation in the average pooling.
Finally, all groups can then be combined to form the scale’s representation:

$\displaystyle x^{(i-1)}$
$\displaystyle\leftarrow\\{x^{(i-1)}_{00},x^{(i-1)}_{01},x^{(i-1)}_{10},x^{(i-1)}_{11}\\}$
(11)

Equations (7)-(11) are repeated for the next scales ($i=2,1$) to complete the
probability model of the entire image.

Based on the probability models, first, the last scale $x^{(3)}$ is
transmitted by the encoder to the decoder with simple fixed length codes.
Then, both the encoder and decoder process the scale representation $x^{(3)}$
with neural networks to obtain the conditional probability distribution of the
initial group in the previous scale $p(x^{(i-1)}_{00}|x^{(i)})$ and
encode/decode it. Similar processing with neural networks is performed to
obtain the conditional probability distribution of the other groups based on
Equation (8) and (9) and they are encoded/decoded. Then Equation (10) and (11)
are applied to obtain the previous scale representation $x^{(i-1)}$. Then the
processing starts again with Equation (7) for the new scale. This is repeated
until the original image $x^{(0)}$ is encoded/decoded.

In MSPSM [20], the overall framework is similar to that of SReC but the scale
representations $x^{(i)}$ are obtained by not average pooling but simply
splitting the original image into 4 groups based on even and rows and columns
or 6 groups for improved performance. Then the initial group is split again to
form the next scale. Starting with the initial group in the last scale, each
group’s probability distribution is modeled conditioned on the previous groups
in a progressive manner. Note that since groups are obtained by splitting,
once all groups in a scale are decoded, the previous scale’s initial group is
readily available.

The compression performance of L3C is better than all classical lossless
compression systems except FLIF [4]. SReC improves the compression performance
over L3C significantly and outperforms also FLIF. MSPSM presents three models
with increasing complexity and the compression performance of the first one is
similar to that of SReC while the latter two have better performance. While
L3C, SReC and MSPSM provide state of the art lossless compression performance
and reasonable encoding/decoding speeds on GPUs they require neural networks
with millions of parameters (L3C: 5.0M, SReC: 4.2M, MSPSM:1.9M/9.9M) and high
computational complexity. This paper presents a scale-based auto-regressive
system that has similarities to SReC and MSPSM but several modifications in
the overall system and neural network design are proposed, which all help to
improve compression performance and/or reduce complexity, to achieve the same
compression performance as SReC and the first model in MSPSM with 10x (or
more) less parameters and computational complexity.

##  III Learned Lossless Image Compression Trough Interpolation (LLICTI)

This section presents the proposed method of learned lossless image
compression through interpolation (LLICTI) in four sub-sections.

###  III-A Overall System Architecture and Decoding Procedure

A multi-scale representation of the original input image is obtained at the
encoder by first splitting it into 4 subbands based on even and odd indices of
the rows and columns. This splitting is then repeated on the first subband of
each scale to obtain a multi-scale representation of the original image. The
obtained multi-scale representation with subbands $x_{mn}^{(i)}$, where $i$
denotes the scale index and $(m,n)\in\\{(0,0),(0,1),(1,0),(1,1)\\}$ denote the
subband index, can be represented as follows if the original image is denoted
$x_{00}^{(0)}$ and there are $S$ scales (see also Figure 1):

$\displaystyle\\{x^{(i+1)}_{00},x^{(i+1)}_{01},x^{(i+1)}_{10},x^{(i+1)}_{11}\\}$
$\displaystyle\leftarrow x_{00}^{(i)}\qquad i=0,...,S-1$ (12)

Figure 1: Multi-scale representation of original image $x_{00}^{(0)}$ in
LLICTI.

The decoding procedure starts with the last scale by decoding the
$x^{(S)}_{00}$ subband with fixed length codes of their pixel values in RGB
color space. The pixels decoded with fixed length codes is $\frac{1}{4^{S}}$
of all original image pixels and is a negligible fraction for large $S$, such
as $S=5$ which we use in our experiments.

The processing steps to decode the remaining subbands in this scale are
summarized in Figure 2. First, the $x^{(S)}_{00}$ subband is processed at the
decoder with an $\boldsymbol{i}$nterpolator $\boldsymbol{c}$onvolutional
$\boldsymbol{n}$eural $\boldsymbol{n}$etwork ($iCNN^{(S)}_{11}$) to obtain the
probability distribution parameters of the next subband $x^{(S)}_{11}$, which
is then decoded by an entropy decoder from the bitstream. Next, $x^{(S)}_{00}$
and $x^{(S)}_{11}$ subbands are the inputs to another interpolator
convolutional neural network ($iCNN^{(S)}_{01}$) to obtain the probability
distribution parameters of the $x^{(S)}_{01}$ subband, which is then decoded.
Then, in a similar manner, the $x^{(S)}_{10}$ subband is decoded. Finally, all
the decoded subbands are combined to obtain the initial subband of the next
scale to decode:

$\displaystyle
x_{00}^{(i-1)}\leftarrow\\{x^{(i)}_{00},x^{(i)}_{01},x^{(i)}_{10},x^{(i)}_{11}\\}\qquad
i=S$ (13)

To decode the next scales, the above described processing steps are repeated
for each scale ($i=S-1,...,1$), yielding the decoding of the original image
$x_{00}^{(0)}$. The encoder performs similar and appropriate processing to
encode the image.

Figure 2: Decoding procedure for one scale. Three interpolator convolutional
neural networks ($iCNN$) are used in each scale.

Note that the described decoding procedure corresponds to an interpolation
based scheme which starts with an image grid of every $(2^{S})^{th}$ pixel
(i.e. $x^{(S)}_{00}$) and interpolates progressively missing pixels of the
grid populating the entire image, thus the name of the method.

###  III-B Probability Model

The probability model of an original image, upon which the system architecture
and decoding procedure in Section III-A is based on, can be described as
follows. The pixels in the initial subband of the last scale $x^{(S)}_{00}$
are assumed to follow a uniform distribution:

$\displaystyle p(x^{(S)}_{00})~{}\sim~{}$ $\displaystyle uniform$ (14)

The probability distribution of the initial subband of the preceding scale
$p(x^{(S-1)}_{00})$ is then factorized as the product of conditional
distributions of each subband of the scale conditioned progressively on
preceding subbands:

$\displaystyle p(x^{(i-1)}_{00})=~{}$ $\displaystyle p(x^{(i)}_{00})\times$
$\displaystyle p(x^{(i)}_{11}~{}|~{}x^{(i)}_{00})\times$ $\displaystyle
p(x^{(i)}_{10}~{}|~{}x^{(i)}_{00},x^{(i)}_{11})\times$ $\displaystyle
p(x^{(i)}_{01}~{}|~{}x^{(i)}_{00},x^{(i)}_{11},x^{(i)}_{10}),\qquad i=S$ (15)

Note that Equation (15) can be applied recursively for each scale
($i=S-1,...,1$) to factorizate the distribution of the original image
$x^{(0)}_{00}$ into the conditional distributions of subbands, conditioned on
previous subbands, with an initial marginal distribution given in Equation
(14).

To describe each conditional distribution in Equation (15), let $Y^{(i)}_{mn}$
denote the collection of subbands that $x^{(i)}_{mn}$ conditions on. Further,
let $x^{(i)}_{mn}[u,v]$ denote the pixel at spatial location $(u,v)$ and
$C^{(i)}_{mn}[u,v]$ denote the collection of pixels in $Y^{(i)}_{mn}$ that the
pixel $x^{(i)}_{mn}[u,v]$ conditions on through the receptive field of the
interpolator CNN ($iCNN^{(i)}_{mn}$). Then each conditional distribution in
Equation (15) is factorized as follows:

$\displaystyle p(x^{(i)}_{mn}~{}|~{}Y^{(i)}_{mn})=\prod_{u,v}p($
$\displaystyle x^{(i)}_{mn}[u,v]~{}|~{}C^{(i)}_{mn}[u,v]),$
$\displaystyle(m,n)\in\\{(1,1),(1,0),(0,1)\\}$ (16)

To describe the conditional distributions of each pixel in Equation (16), let
us simplify the notation by dropping the spatial location, subband and scale
indices and simply denote a pixel by $x$ and the collection of pixels it is
conditioned on by $C$. Then, the conditional distribution of each pixel in
Equation (16) can be further factorized over distributions of its RGB color
components ($x=\\{x^{(r)},x^{(g)},x^{(b)}\\}$), i.e. sub-pixels111Here, we
follow the convention in the related previous research and use sub-pixel to
denote each color component and pixel to denote all color components together,
as follows:

$\displaystyle p(x^{(r)},x^{(g)},x^{(b)}|C)=~{}$ $\displaystyle
p(x^{(r)}|C)\times$ $\displaystyle p(x^{(g)}|C,x^{(r)})\times~{}$
$\displaystyle p(x^{(b)}|C,x^{(g)},x^{(b)})$ (17)

Each conditional distribution in Equation (17) is modeled with a discretized
Gaussian mixture model (GMM) given below in Equation (18), where $F(.)$
denotes the cumulative distribution function (CDF) of the standard Gaussian
distribution and $\mu^{(c)}_{i}$, $\sigma^{(c)}_{i}$ and $\pi^{(c)}_{i}$ are
the mean, standard deviation and the weight of the $i^{th}$ mixture of the
GMM, respectively, of sub-pixel $x^{(c)}\in\\{x^{(r)},x^{(g)},x^{(b)}\\}$:

$\displaystyle
p(x^{(c)};~{}{{\pi^{(c)},\mu^{(c)},\sigma^{(c)}}})=\sum_{i=1}^{K}\pi^{(c)}_{i}[$
$\displaystyle F(\frac{x^{(c)}+0.5-\mu^{(c)}_{i}}{\sigma^{(c)}_{i}})$
$\displaystyle-$ $\displaystyle
F(\frac{x^{(c)}-0.5-\mu^{(c)}_{i}}{\sigma^{(c)}_{i}})]$ (18)

The GMM parameters $\mu^{(c)}_{i}$, $\sigma^{(c)}_{i}$ and $\pi^{(c)}_{i}$ are
produced by the respective interpolator CNN processing the conditioning pixels
$C$. The conditioning of each sub-pixel on also the preceding sub-pixels in
Equation (17) is accomplished with the simple but efficient method of Salimans
in PixelCNN++ [26], which simply updates the means by multiplication of
preceding sub-pixels with scaling coefficients ($\\{a,b,c\\}=\alpha$) that are
produced also by the interpolator convolutional neural network:

$\displaystyle\mu^{(r)}=$ $\displaystyle\mu^{(r)}(C)$
$\displaystyle\mu^{(g)}=$ $\displaystyle\mu^{(g)}(C)+a(C)x^{(r)}$
$\displaystyle\mu^{(b)}=$ $\displaystyle\mu_{(b)}(C)+b(C)x^{(r)}+c(C)x^{(g)}$
(19)

###  III-C General Neural Network Architecture of One Interpolator

The neural network architecture used for all interpolators $iCNN^{(i)}_{mn}$,
$i=1,...,S$ and $(m,n)\in\\{(1,1),(1,0),(0,1)\\}$ in the proposed LLICTI
system is shown in Figure 3. It has $L$ layers, where layer 2 to $L$ comprise
convolution layers with 1x1 kernel size, stride of 1 and (except the last
layer) ReLU activation functions. The first layer contains one, two or three
convolutional layers, depending on how many previous subbands $x_{mn}^{(i)}$
are inputs to this interpolator (see Figure 2). The outputs are added and
processed with ReLU activation.

Figure 3: Architecture of interpolator Convolutional Neural Network at scale
$i$ for sub-band $x_{10}$ ($iCNN_{10}^{(i)}$). The architectures for the other
two interpolators of a scale, $iCNN_{01}^{(i)}$ and $iCNN_{11}^{(i)}$, are
similar and lack the bottom and bottom two convolutional layers in Layer 1,
respectively.

Since all layers, except the first, have filters with kernel size 1x1, the
receptive field of the $iCNN$ or the pixels of the previous subbands used for
interpolation are determined by the kernel sizes of the first layer
convolutions. Due to the relative positions of different subbands on the
sampling grid, the kernel sizes were determined based on the input subband and
the subband to be interpolated, as shown in Figure 4.

Figure 4: Interpolator layer 1 kernel sizes.
$x_{00}^{(i)}(4\text{x}4)\rightarrow x_{11}^{(i)}$
$x_{00}^{(i)}(3\text{x}4),x_{11}^{(i)}(4\text{x}3)\rightarrow x_{01}^{(i)}$
$x_{00}^{(i)}(4\text{x}3),x_{11}^{(i)}(3\text{x}4),x_{01}^{(i)}(4\text{x}4)\rightarrow
x_{10}^{(i)}$

To train the parameters of all interpolator convolutional neural networks, the
cross entropy loss function

$\mathbb{E}_{q(x_{00}^{(0)})}[-\log p(x_{00}^{(0)})]$ (20)

is used, where $q(.)$ is the true distribution of the image and $p(.)$ is the
distribution of the image obtained by the presented probability model in
Equations (14)-(19). In practice, the loss simply becomes the sum of all
$-\log p(.)$ quantities of all interpolated pixels in the training batch where
$p(.)$ are the probability distributions provided by the interpolators for
each interpolated pixel.

###  III-D System and NN Architecture Parameters to Analyze

The proposed LLICTI system described so far has 3 interpolators ($iCNN$) per
scale, for a total of $3S$ interpolators overall, where $S$ is the total
number of scales. There are many parameters of the overall system and the
$iCNN$ architecture that we will analyze. In Section IV-B, we examine

  * •

whether compressing pixels in the RGB or YCoCg-R color space,

  * •

whether obtaining probability distribution parameters $\pi,\mu,\sigma,\alpha$
using a single or using multiple independent interpolator CNNs

  * •

whether using the same interpolator CNN (i.e. with same weights) in several
scales

performs better in terms of compression-complexity trade-off. We also examine
standard neural network architecture parameters such as, the number of layers
and the number of channels of each layer for better compression-complexity
trade-off.

##  IV Experiments and Results

This section first presents experimental settings and then provides
experimental analyses and results of the proposed learned lossless image
compression through interpolation (LLICTI) systems. Comparisons with the
literature in terms of compression performance, number of used parameters,
encoding/decoding times and computational complexity estimates are also
provided.

###  IV-A Experimental Settings

All LLICTI systems to be discussed in Section IV-B are trained with the Open
Images training dataset prepared by the authors of L3C [18]. The Adam
optimizer [27] is used for optimization with a batch size of 64. The learning
rate is initialized to $10^{-4}$ and is reduced with a decay factor of $0.5$
(up to a minimum of $10^{-5}$) when the validation cost plateaus. The training
takes typically around $500K$ weight updates.

The LLICTI systems are tested with the Open Images test dataset prepared again
by the authors of L3C [18], which includes 500 images. The arithmetic coder
provided by [18], which runs on the CPU [28], is used for encoding to and
decoding from a bitstream during the tests. Note that all neural network
operations are performed on the GPU and the obtained probability tables are
copied to the CPU memory and the arithmetic encoding/decoding operations are
performed on the CPU in our tests of LLICTI. PyTorch [29] is used to implement
both training and testing. Our codes are available on GitHub [30].

###  IV-B Experimental Analysis and Ablation Study

The following experiments summarized in Table I are conducted to analyze
several parameters of the overall compression system and the interpolator CNN
architecture, as discussed in Section III-D. Note that all interpolators
($iCNN^{(i)}_{mn}$ $i=1,...,S$ and $(m,n)\in\\{(1,1),(1,0),(0,1)\\}$) can be
trained independently from each other since their inputs can be obtained
directly from the original image and their outputs contribute to the cost
(i.e. total bitrate) independently. Considering also the fact that compression
of scale 1 subbands $x_{mn}^{(1)}$, $(m,n)\in\\{(1,1),(1,0),(0,1)\\}$ is more
important (as they comprise 4 times as many pixels as scale 2, which comprises
4 times as many pixels as scale 3 etc) than that of other scale subbands, the
initial experiments discussed below are conducted by compressing only scale 1
subbands (i.e. $x_{00}^{(1)}$ is assumed available and
$x_{11}^{(1)},x_{01}^{(1)},x_{10}^{(1)}$ are compressed).

TABLE I: Analysis of system and neural network architecture parameters Experiment # |  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
(Reference Experiment) |  |  | (1) | (2) | (3) | (4) | (5) | (4) | (7) | (8) | (9) | (10) | (11) | (12) | (13)
Color space: RGB/YCoCg-R |  | RGB | YCC | YCC | YCC | YCC | YCC | YCC | YCC | YCC | YCC | YCC | YCC | YCC | YCC
($\pi,\mu,\sigma,\alpha$): Joint/Separate |  | JNT | JNT | SEP | SEP | SEP | SEP | SEP | SEP | SEP | SEP | SEP | SEP | SEP | SEP
# Layers in $iCNN$ |  | 4 | 4 | 4 | 3 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3
# Channels | Scale 1 | 96 | 96 | 44 | 44 | 44 | 64 | 60 | - | - | - | - | - | 60 | 88
Scale 2 | - | - | - | - | - | - | - | 44 | 32 | - | - | - | $\uparrow$ | $\uparrow$
Scale 3 | - | - | - | - | - | - | - | - | - | 36 | 24 | 24 | - | $\uparrow$
Scale 4 | - | - | - | - | - | - | - | - | - | 30 | 20 | $\uparrow$ | - | $\uparrow$
Scale 5 | - | - | - | - | - | - | - | - | - | 30 | 20 | $\uparrow$ | - | $\uparrow$
Share $iCNN$ across scales |  | - | - | - | - | - | - | - | - | - | F | F | T | T | T
Compression (bpp) | Scale 1 | 5.781 | 5.736 | 5.607 | 5.605 | 5.658 | 5.624 | 5.524 | - | - | - | - | - | 5.525 | 5.465
Scale 2 | - | - | - | - | - | - | - | 1.852 | 1.862 | - | - | - | 1.868 | 1.841
Scale 3 | - | - | - | - | - | - | - | - | - | 0.551 | 0.556 | 0.556 | - | 0.553
Scale 4 | - | - | - | - | - | - | - | - | - | 0.158 | 0.159 | 0.158 | - | 0.160
Scale 5 | - | - | - | - | - | - | - | - | - | 0.044 | 0.044 | 0.044 | - | 0.045
Total # Parameters ($\times 10^{3}$) |  | 93 | 93 | 94 | 72 | 49 | 72 | 109 | 72 | 48 | 144 | 88 | 34 | 109 | 188

Note that a primary goal of the LLICTI method is to obtain a lossless image
compression system that has significantly less complexity than other similar
systems in the literature while achieving the best possible compression
performance. In particular, the goal is to have at least 10x less parameters
in the LLICTI system than the smallest neural network in the related
literature, which is the normal model in MSPSM with $1.8$M parameters. The
parameters, in particular number of layers and channels, of the LLICTI systems
in the following experiments were chosen to chase that goal.

The first conducted experiment is experiment 1, which can be considered the
default system and compresses pixels in the RGB color space, uses a single
(i.e. joint) interpolator CNN to obtain all probability distribution
parameters ($\pi,\mu,\sigma,\alpha$), has $L=4$ layers in the interpolator
CNNs and has $C=96$ channels in each convolutional layer. This system achieves
a compression performance of 5.781 bits per pixel (bpp) and requires 93K
parameters. Note that the 5.781 bpp is obtained by dividing the total number
of bits used for encoding $x_{11}^{(1)},x_{01}^{(1)}$ and $x_{10}^{(1)}$ by
the total number of pixels in the original image, and the bits required for
compressing $x_{00}^{(1)}$ are not considered in this and following similar
experiments.

Next, it is investigated whether/how the color space of input pixels can
improve compression-complexity trade-off and experiment 2 is conducted, where
the original image is converted to the YCoCg-R color space [31], which is
integer-to-integer invertible, and then compressed. While the interpolator
CNNs can learn the dependencies in the RGB color space and account for them,
it may be beneficial in terms of compression-complexity trade-off to provide
the input to the neural networks in a decorrelated color space and allocate
neural network capacity to learn other dependencies. The system in experiment
2 achieves an improved compression performance of 5.736 bpp and requires the
same 93K parameters. Hence, YCoCg-R color space is used in the next
experiments.

Next, it is investigated whether each interpolator CNN should comprise a
single CNN that produces all parameters ($\pi,\mu,\sigma,\alpha$) required for
the probability distribution model or whether each interpolator should
comprise 4 separate CNNs, each producing one of the parameters. Since each of
these parameters affect the probability distribution (and thus the cost
function) in different ways, learning them trough separate neural networks
could be better in terms of compression-complexity trade-off. Hence,
experiment 3 is conducted, which differs from its reference (experiment 2), by
the use of 4 separate CNNs for each interpolator and the reduced number of
channels (from 96 to 44) in each CNN to keep the total number of parameters
similar. The system in experiment 3 achieves an improved compression
performance of 5.607 bpp and requires a similar 94K parameters. Hence, in the
next experiments, for each interpolator, 4 separate CNNs are used, each of
which produces one of the parameters ($\pi,\mu,\sigma,\alpha$).

Next, the number of layers and channels in the interpolator CNNs are examined
in experiments 4-7. In experiment 4, the number of layers in the interpolator
CNNs are reduced from 4 to 3 and almost the same compression performance of
5.605 bpp as reference experiment 3 is achieved, while the required number of
parameters drops from 94K to 72K. Based on this result, the number of layers
in the interpolator CNNs are further reduced to 2 in experiment 5, however,
the compression performance deteriorated to 5.658 bpp while 49K parameters
were required. Thus experiment 6 is conducted, where the number of layers is
kept at 2 but the number of channels is increased to 64 to achieve the same
number of parameters (72K) as experiment 4. The achieved compression
performance is 5.624 bpp, which is inferior to the result of experiment 4.
Hence, experiment 7 is conducted, which keeps the number of layers at 3 and
increases the number of channels to 60 to achieve a compression performance of
5.524 bpp with 109K required parameters.

It is now assumed that several parameters of the overall system and the
interpolator CNN architecture have been identified for better compression-
complexity trade-off. In particular, compressing pixels in the YCoCg-R space,
using 4 separate CNNs for each interpolator to obtain parameters
($\pi,\mu,\sigma,\alpha$) and using 3 layers in the interpolator CNNs have
been identified to provide better compression-complexity trade-off and will be
used in the next experiments.

Next, in experiments 8 and 9, compressing scale 2 subbands (i.e.
$x_{00}^{(2)}$ is assumed available and
$x_{11}^{(2)},x_{01}^{(2)},x_{10}^{(2)}$ are compressed) is considered and
only the number of channels in the interpolator CNNs are examined. In
experiment 8, 44 channels are used to achieve a compression performance of
1.852 bpp with 72K required parameters. In experiment 9, the number of
channels is reduced to 32 and a slightly worse compression performance of
1.862 bpp is obtained with 48K required parameters.

In experiments 10 and 11, scale 3, 4, and 5 subbands are compressed. In
experiment 10, 36, 30 and 30 channels are used to achieve a compression
performance of 0.551 bpp, 0.158 bpp and 0.044 bpp for scales 3, 4 and 5,
respectively, with a total 144K required parameters. In experiment 11, the
number of channels is reduced to 24, 20 and 20 for scales 3, 4 and 5,
respectively, and the obtained compression performance is slightly inferior
but the required total number of parameters drops by a significant amount to
88K.

Next, it is investigated whether using the same interpolator CNN (i.e. with
same weights) in several scales is beneficial for compression-complexity
trade-off. Although the dependency of pixels in different scales may be
different, it is likely that there are significant amount of common features
and sharing interpolator CNNs across scales may improve the compression-
complexity trade-off. Hence, in experiment 12, the interpolator CNNs for scale
3 with 24 channels are shared across scales 3, 4 and 5 (Note that they are
trained from scratch using the total cost of the three scales.) The
compression performance is almost identical to that of the reference
experiment 11 for all scales but the total number of required parameters drops
significantly from 88K to 34K. This is a surprising and significant result.
Inspired by this result, experiment 13 is conducted, where the interpolator
CNNs (with the same 60 channels as in experiment 7) are shared across scales 1
and 2. The obtained compression performance of 5.525 bpp for scale 1 is
identical to that of experiment 7 and scale 2 is compressed at a competitive
1.868 bpp (see experiments 8, 9). Hence, sharing interpolator CNNs across
scale 1 and 2 proved to be also very beneficial in terms of compression-
complexity trade-off.

Finally, experiment 14 is conducted, where the same interpolator CNNs are
shared across all scales 1-5 and the number of channels in the convolution
layers is set to 88 to achieve a total 188K parameters, which is 10x less (our
initial goal) than the smallest neural network in the literature [20]. The
compression performance is the best so far in the experiments for scales 1 and
2, achieving 5.465 bpp and 1.841 bpp, respectively. The compression
performance for the remaining scales 3-5 is also very competitive as can be
seen in Table I. The total bitrate for all scales becomes 8.064 bpp (which dos
not include the 0.023 bpsp bitrate of $x_{00}^{(5)}$ that is to be coded with
fixed-length codes of 8 bits per symbol.) Hence, the system and the neural
network architecture for the interpolators in experiment 14 is chosen to be
the best in terms of compression-complexity trade-off and is compared to other
systems in the literature in the next section.

###  IV-C Comparisons with Related Literature

This section compares the proposed LLICTI to other lossless image compression
systems in the literature in terms of compression performance, number of
required parameters, encoding/decoding times and computational complexity. The
comparison results are summarized in Table II. (Note that in these results of
the LLICTI system, all necessary information is written into the bitstream
including $x_{00}^{(5)}$ and control information, such as the number of
scales, height and width of every scale and the image. The LLICTI system can
also compress arbitrary sized images.)

TABLE II: Comparisons with Related Literature | Method | bpsp(bpp) | Param- | Enc/Dec | Enc/Dec
---|---|---|---|---|---
|  |  | eters | Computat. | Time
|  |  |  | (KMAC/pix) | (sec)
Traditional Methods | PNG | 4.01(12.03) | - | - | -
JPEG2000 | 3.06(9.18) | - | - | -
WebP | 3.05(9.15) | - | - | -
FLIF [4] | 2.87(8.61) | - | - | -
Learning Based Methods | L3C [18] | 2.99(8.97) | 5.01 M | 686/428 | 0.67/0.61
SReC [19] | 2.70(8.10) | 4.20 M | 878/878 | 0.56/0.59
MSPSM(norm)[20] | 2.71(8.14) | 1.87 M | - | -
MSPSM(big) [20] | 2.63(7.88) | 1.87 M | - | -
LLICTI (Ours) | 2.70(8.10) |  0.19 M | 66/66 |  0.53/0.70

####  IV-C1 Compression performance and number of parameters

The compression performance results for the Open Images test dataset [18] are
given in terms of bits per sub-pixel (bpsp) and bits per pixel (bpp). The best
performing traditional method is FLIF [4] and it achieves an average
compression performance of 2.87 bpsp. Among the learning based methods, the
first proposed scale-based auto-regressive method L3C [18] achieves a
compression performance of 2.99 bpsp. Next, SReC [19], MSPSM(normal) [20] and
the proposed LLICTI achieve a compression performance of 2.70 bpsp. A common
feature of these three scale-based auto-regressive methods is that they
perform the compression/probability-modeling of each scale in 3 progressive
steps. MSPSM(big) achieves an improved compression performance of 2.63 bpsp as
it performs the compression/probability-modeling of each scale in 6
progressive steps [20].

If the learned systems are compared in terms of number of parameters of the
neural networks that they use, it can be seen that the proposed LLICTI method
uses 0.19 M (188K) parameters, which is about 10x less than MSPSM, 22x less
than SReC and 26x less than L3C. Despite the significantly less number of
parameters of LLICTI, compression performance similar to these methods was
achieved. The improved compression-complexity trade-off of LLICTI is due to
several factors, such as simpler neural network design, sharing the same
interpolator neural networks across different scales, using separate neural
networks for different parameters of the probability distribution and
performing the compression in the YCoCg-R color space instead of the RGB color
space.

####  IV-C2 Computational complexity and encoding/decoding times

The computational complexity of the neural network calculations for encoding
and decoding in the learning based systems are compared using the multiply-
accumulate (MAC) operations counter tool in [32]. As shown in Table II, the
proposed LLICTI system requires more than 10x less MACs than L3C and SReC for
both encoding and decoding, which is mainly due to the less number of
parameters of the used neural networks. (Note that MSPSM is not included in
computation or encoding/decoding times comparisons since their codes are not
shared.)

The average encoding and decoding time of an image (averaged over all 500
images on the Open Images test dataset where the average image resolution is
$\sim$768x576) measured on our computing system with an NVIDIA GeForce RTX
2080 GPU and Intel i7-9700 CPU are also given in Table II. L3C, SReC and the
proposed LLICTI achieve similar average encoding/decoding times under one
second and close to half a second. However, the implementations of L3C and
SReC enjoy an advantage over that of LLICTI. In particular, implementations of
L3C and SReC don’t copy the calculated CDFs (necessary for arithmetic coding
on the CPU) from GPU to CPU but use a custom CUDA kernel to store the CDFs in
managed/unified memory accessible from both CPU and GPU (see L3C appendix [18]
and GitHub page [33].) On the other hand, LLICTI implementation moves the CDF
tensors from GPU to CPU for arithmetic coding. If the LLICTI implementation
would also store CDF tensors in unified/managed memory, its encoding/decoding
times are likely to decrease. Lastly, while encoding/decoding times of MSPSM
could not be obtained on our computing system (since their codes are not
shared), it is reported in their paper [20] that their encoding/decoding times
are about $20\%$ and $100\%$ longer than those of SReC, for their normal and
big systems, respectively.

##  V Conclusions

This paper presented a learned lossless image compression method based on a
progressive interpolation scheme. First, a subset of pixels of the original
image grid (e.g. every $32^{nd}$ pixel horizontally and vertically) is
encoded/decoded using simple fixed-length codes. Then, finer sub-sampled grids
of the original image grid are progressively interpolated (i.e. their
probability distributions are obtained) conditioned on previously
encoded/decoded grids so far, to encode/decode all pixels of the image grid.
The interpolators are neural network based and learned from a dataset.

The presented method was shown to achieve better than or on par compression
performance with the recent scale-based auto-regressive models literature, yet
required 10x or more less neural network parameters and encoding/decoding
computation complexity. The improved compression-complexity trade-off was
attributed to several contributions/findings in the overall system and neural
network architecture design, such as using the same interpolator neural
networks in different scales, using separate neural networks for different
parameters of the probability distribution and performing the processing in
the YCoCg-R color space instead of the RGB color space.

## Acknowledgment

We would like to thank Sinem Gumus for obtaining the encoding/decoding times
of several compression methods on the same computing system.

## References

  * [1] W. B. Pennebaker and J. L. Mitchell, _JPEG: Still image data compression standard_. Springer Science & Business Media, 1992.
  * [2] T. Boutell and T. Lane, “Png (portable network graphics) specification version 1.0,” _Network Working Group_ , pp. 1–102, 1997.
  * [3] M. J. Weinberger, G. Seroussi, and G. Sapiro, “The loco-i lossless image compression algorithm: Principles and standardization into jpeg-ls,” _IEEE Transactions on Image processing_ , vol. 9, no. 8, pp. 1309–1324, 2000\.
  * [4] J. Sneyers and P. Wuille, “Flif: Free lossless image format based on maniac compression,” in _2016 IEEE international conference on image processing (ICIP)_. IEEE, 2016, pp. 66–70.
  * [5] Google, “An image format for the web,” https://developers.google.com/speed/webp, 2022, last accessed 12 October 2022.
  * [6] Y.-L. Lee, K.-H. Han, and G. J. Sullivan, “Improved lossless intra coding for h. 264/mpeg-4 avc,” _IEEE Transactions on Image Processing_ , vol. 15, no. 9, pp. 2610–2615, 2006.
  * [7] M. Zhou, W. Gao, M. Jiang, and H. Yu, “Hevc lossless coding and improvements,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 22, no. 12, pp. 1839–1843, 2012.
  * [8] A. R. Calderbank, I. Daubechies, W. Sweldens, and B.-L. Yeo, “Lossless image compression using integer to integer wavelet transforms,” in _Proceedings of International Conference on Image Processing_ , vol. 1. IEEE, 1997, pp. 596–599.
  * [9] F. Kamisli, “Lossless image and intra-frame compression with integer-to-integer dst,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 29, no. 2, pp. 502–516, 2017.
  * [10] S. R. Alvar and F. Kamisli, “On lossless intra coding in hevc with 3-tap filters,” _Signal Processing: Image Communication_ , vol. 47, pp. 252–262, 2016.
  * [11] D. Le Gall and A. Tabatabai, “Sub-band coding of digital images using symmetric short kernel filters and arithmetic coding techniques,” in _ICASSP-88., International Conference on Acoustics, Speech, and Signal Processing_. IEEE, 1988, pp. 761–764.
  * [12] M. Rabbani and R. Joshi, “An overview of the jpeg 2000 still image compression standard,” _Signal processing: Image communication_ , vol. 17, no. 1, pp. 3–48, 2002.
  * [13] C. Christopoulos, A. Skodras, and T. Ebrahimi, “The jpeg2000 still image coding system: an overview,” _IEEE transactions on consumer electronics_ , vol. 46, no. 4, pp. 1103–1127, 2000.
  * [14] J. Ballé, V. Laparra, and E. P. Simoncelli, “End-to-end optimized image compression,” _arXiv preprint arXiv:1611.01704_ , 2016.
  * [15] J. Ballé, D. Minnen, S. Singh, S. J. Hwang, and N. Johnston, “Variational image compression with a scale hyperprior,” _arXiv preprint arXiv:1802.01436_ , 2018.
  * [16] D. Minnen, J. Ballé, and G. D. Toderici, “Joint autoregressive and hierarchical priors for learned image compression,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [17] D. Minnen and S. Singh, “Channel-wise autoregressive entropy models for learned image compression,” in _2020 IEEE International Conference on Image Processing (ICIP)_. IEEE, 2020, pp. 3339–3343.
  * [18] F. Mentzer, E. Agustsson, M. Tschannen, R. Timofte, and L. Van Gool, “Practical full resolution learned lossless image compression,” in _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_. IEEE Computer Society, 2019, pp. 10 621–10 630.
  * [19] S. Cao, C.-Y. Wu, and P. Krähenbühl, “Lossless image compression through super-resolution,” _arXiv preprint arXiv:2004.02872_ , 2020.
  * [20] H. Zhang, F. Cricri, H. R. Tavakoli, N. Zou, E. Aksu, and M. M. Hannuksela, “Lossless image compression using a multi-scale progressive statistical model,” in _Proceedings of the Asian Conference on Computer Vision_ , 2020\.
  * [21] A. B. Koyuncu, H. Gao, A. Boev, G. Gaikov, E. Alshina, and E. Steinbach, “Contextformer: A transformer with spatio-channel attention for context modeling in learned image compression,” in _European Conference on Computer Vision_. Springer, 2022, pp. 447–463.
  * [22] B. Bross, Y.-K. Wang, Y. Ye, S. Liu, J. Chen, G. J. Sullivan, and J.-R. Ohm, “Overview of the versatile video coding (vvc) standard and its applications,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 31, no. 10, pp. 3736–3764, 2021.
  * [23] I. Schiopu and A. Munteanu, “Deep-learning-based lossless image coding,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 30, no. 7, pp. 1829–1842, 2020.
  * [24] S. Gumus and F. Kamisli, “A learned pixel-by-pixel lossless image compression method with 59k parameters and parallel decoding,” _arXiv preprint arXiv:2212.01185_ , 2022.
  * [25] E. Hoogeboom, J. W. Peters, R. van den Berg, and M. Welling, “Integer discrete flows and lossless compression,” in _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , 2019, pp. 12 145–12 155.
  * [26] T. Salimans, A. Karpathy, X. Chen, and D. P. Kingma, “PixelCNN++: Improving the pixelCNN with discretized logistic mixture likelihood and other modifications,” in _International Conference on Learning Representations_ , 2017. [Online]. Available: https://openreview.net/forum?id=BJrFC6ceg
  * [27] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [28] F. Mentzer, “torchac: Fast arithmetic coding for pytorch,” https://github.com/fab-jul/torchac, Dec. 2022.
  * [29] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [30] F. Kamisli, “Learned lossless image compression through interpolation,” https://github.com/metu-kamisli/LLICTI, Dec. 2022.
  * [31] H. Malvar and G. Sullivan, “Ycocg-r: A color space with rgb reversibility and low dynamic range,” _ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q_ , vol. 6, 2003\.
  * [32] V. Sovrasov, “Flops counter for convolutional networks in pytorch framework,” https://github.com/sovrasov/flops-counter.pytorch, Nov. 2022, last accessed November 2022.
  * [33] F. Mentzer, “Practical full resolution learned lossless image compression,” https://github.com/fab-jul/L3C-PyTorch, Dec. 2022.