Idempotent Learned Image Compression with Right-Inverse
Authors: Yanghao Li
Tongda Xu
Yan Wang
Jingjing Liu
Ya-Qin Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: learned image compression
idempotent compression
right-inverse
TL;DR: We propose to achieve idempotent compression using right-inverse, which is significantly better than idempotent compression using strict inverse.

Abstract: We consider the problem of idempotent learned image compression (LIC).
The idempotence of codec refers to the stability of codec to re-compression.
To achieve idempotence, previous codecs adopt invertible transforms such as DCT and normalizing flow.
In this paper, we first identify that invertibility of transform is sufficient but not necessary for idempotence. Instead, it can be relaxed into right-invertibility. And such relaxation allows wider family of transforms.
Based on this identification, we implement an idempotent codec using our proposed blocked convolution and null-space enhancement.
Empirical results show that we achieve state-of-the-art rate-distortion performance among idempotent codecs. Furthermore, our codec can be extended into near-idempotent codec by relaxing the right-invertibility. And this near-idempotent codec has significantly less quality decay after $50$ rounds of re-compression compared with other near-idempotent codecs.

Idempotent Learned Image Compression with Right-Inverse
Yanghao Li, Tongda Xu, Yan Wang' Jingjing Liu, Ya-Qin Zhang'
Institute for Al Industry Research (AIR), Tsinghua University Liyangha180mails tsinghua. edu. en,
wangyan@air: tsinghua. edu. en
Abstract
We consider the problem of idempotent learned image compression (LIC). The idempotence of codec refers to the stability of codec to re-compression. To achieve idempotence, previous codees adopt invertible transforms such as DCT [Wallace] [991] and normalizing flow (Papamakarios identify that invertibility of transtorm is sufficient but not necessary for idem- potence. Instead, it can be relaxed into right- invertiiiiiiiilitty.. And such relaxation allows wider family of transforms. Based on this identification, we then implement idempotent codec using our proposed blocked convolution and null-space en- hancement. Empirical results show that we achieve ttate-of-the-ar rate-distortion performance among idempotent codecs. Furthermore, be extended into near-idempotent codec by relaxing the right-invertibility. And this near-idempotent codec has significantly less quality decay after 50 rounds of re-compression compared with other near-idempotent codecs.
al. 2021]. In this paper, we first
idempotent codec
Introduction
Learned Image Compression (LIC) has been widely studied in recent years BBllé et al. 2017 2018 Minnen et al. 2018 Cheng et al. 2020 Minnen et al., 2020 He et al. 2021 2022 and has shown promising rise-risto (RD) performance. However, the loss caused by re- compression is much more severe in LIC compared with traditional codec, which seriously limits the practical application of LIC [Kim et al. 2020). In this paper, we study the idempotence of LIC, which refers to the stability of codec to re-compression. More specifically, denote the original image as æ. the encode-then-decote procedure f()), and the reconstructed image as (xx), we say codec idempotent if:
f(z) = f(fxx))
(1)
For traditional codecs such as JPEG [Wallace] 1991 and JPEG2000 TTubmann al. 2002 idempo- tence is easily achieved. This is because those codecs adopt invertible transforms such as Discrete Cosine transform (DCT) and Discrete Wavelet transform (DWT). And the only on-invertible oper- ation is the scalar quantization. As scalar quantization using rounding is naturally idempotent, the idempotence of the whole codec can be easily assured. For LIC, however, neural-network-biig transform is introduced for expressiveness. And as most neural networks are non-invertible, the idempotence of LIC is not trivial.
natural solution to this problem replacing the non-invertible encoding transform with invertible ones. [Helminger al. [222]] construct the encoding transform with only invertible normalizing flow PPapamakarios et al. 2021]. However, due to the limited expressiveness of invertible operations, dramatic RD performance drop is observed. Another line of works are targeted reaeteeempoeeece. which means that they achieve a small fxx) f(f(z)), but not f(z) = f(f(x)). These works
"Correspondnng author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

adopt partially invertible encoding transform [Cai et al. 2022] or use additional regularization loss [Kim et al. 2020] to constrain re-compression loss, but none of them is able achieve idempotence like JPEG and JPEG2000.
In this work, first identify that invertibility is sufficient but not necessary for idempotent codecs. Instead, it can be relaxed into fightinneettbiiitty and such relaxation allows for more flexible and expressive encoding transforms. Based on this observation, we investigate practical implementation of right-inverse, and propose a highly efficient blocked convolution to overcome the forbidding Additionally, we leverage the null space decomposition [Schwab] et al., 2019 Wang et al.) 2022a|b) b to further boost the expressiveness of the right- night-nnvertille encoding transform. Empirically. we achieve state-of-the th--hhe-rtt RD performance among existing idempotent codecs. Further, our idempotent codec can be easily extended into a near-idempotent codec, which also achieves tfateoffthe--ae re-compression performance among near-idempotent codecs.
time complexity of fight-inverss
2 Sufficiency of Right-Invertibility for Idempotence
Most modern LIC [Ballé et al. 2017 2018 Cheng et al. 2020 He et al. 2022 are composed of four components: the encoding transform E. the decoding transform D, the quantization Q. and the entropy model. On the encoder side, the encoding transform E transform the input image to some latent representation, which is then quantized by Q to give the code y. The entropy model models the entropy of code y, and is then used losslessly compress y to a bitstream, On the decoder side, the received bitstream losslessly decompressed code y with the help of the entropy model. After that, the decoding transform D transforms the y to the decompressed 2. This procedure can be represented as
y = Qo E(x), = D(y).
(2)
Note that the code y is losslessly encoded and decoded, regardless of how good the entropy model is. Therefore entropy model does not influence the distortion, and is thus omitted for simplicity.
Using similar notations, the re-compression eycle can be represented as
yn Q E(Ix-1), 2, Dy,,) D o Q E(En-1), where To is the original image, yn is the code after times' re-compression, and T, is the corre- sponding decompressed image. We say a codec idempotent if and only if
(3)
Tpp = xi = DoQ o E(so), Vn 2 1.
An obvious sufficient condition for idempotence (or for Eq.
is
D=
(5)
In other words, D and E are inverse of each other. Then, the only difference between .i and x,, is the number of applications of quantization operation Q:
In D Q o E-D o Q o E(zn-2) = = = D Q" o E(zo).
(6)
This re-compression procedure is idempotent as long as Q is idempotent. Usually Q is a scalar quantization implemented by rounding, then this procedure is naturally idempotent. The invertibility of encoding transform is satisfied in traditional image codecs like JPEG and JPEG2000, and can also be achieved using normalizing flow [Helminger et al. 202T]. thus these codecs are idempotent. However, invertibility of E (Eq, 5) is sufficient but not necessary. We notice that for o D in Eq. to be canceled out, it is sufficient to have
Eo D(v) ys.
which is exactly the definition of iightiivvettibility.
Relaxing the requirement for E from invertibility to right-invertiiility brings two advantages. On the one hand, the family of right-invertible functions is much less constrained than the family of invertible functions, which means we have wider choices for E and its easier to improve the expressiveness of E. On the other hand, the sufficient condition for E to be invertible is that E is bijective, and the sufficient condition for E to right-invertible is that E can transform different input images x into the same code to save the bits for distinguishing them, while bijective F. always transforms different input images into different codes. later shown the experiment section 4.3 this bit saving property benefits the RD performance of lossy compression.
surjective [Mac Lane 2013). A surjective

---

y1
KK*
K
Xx
X4
9
3%
CE
CE-1
3%.
Xig
R1
y
coupling
null-space enhancement
enhancement
(a) convolution as matrix multiplication: naive (upper) and blocked (lower)
(b) blocked receptive field
(c) right-invertible convolution
Right-Invertible Convolution. (a) Naive convolution matrix (upper) and blocked convolu- tion matrix (lower). (b) Receptive field pattern for the proposed blocked convolution. (c) Null-space enhancement (NE) and coupling enhancement (CE) to improve expressiveness.
Figure 1:
3 Practical Design of Right-Invertible Codec
In the previous section, have shown that if an encoding transform and quantization Q are right-invertible, we only need the decoding transform D to be the right-inverse of E' to formulate an idempotent codec. Since the success of LIC is, large extent, owing to the expressive power of the learned encoding and decoding transforms, our task becomes how to design an expressive yet right-innnee right-inverttbble encoding transform. As composition of surjections is still surjective [Mac Lane 2013]. this task can be further decomposed into designing small components of right-invertille transforms and combining them altogether. Specifically, we construct the encoding transform E in Fj, and make each F, right-invertible sub-transform.
composition form E Fn, -
This section is organised follows: Sec. 3.1 Sec.. 3.3 we discuss how design expressive yet night-invertible atom transforms used in LIC, such as convolution, normalization and quantization. In we discuss how to organize those atom transforms into an idempotent codec. And In Sec.
Sec. 3.4
3.5
we discuss how to relax this idempotent codec into near-idempotent codec.
3.1
Efficient Expressive Right-Invertible Convolution
Convolution is of great importance to LIC and makes up the majority of computation cost. Here, we discuss how to implement right-invertible convolution with efficiency and expressiveness. The overall design of right-invertible convolution is illustrated in c).
3.1.1 Blocked Convolution for Efficiency
The right-inverse convolution can calculated in serial (if exists), but the time complexity is forbiddingly high. To why, consider 1-d convolution with kernel size 5, padding 2, stride 2, and channel 1. The input and output are x = (#1, 02, #2,,,,,,,,, (12) and = (y1, y2,.., ys) respectively.
The serial solution of right-inverse goes as follows: first solve (.1, 22, 223) given /1, then solve (xa, 25) given 3/2 and already solved (I1, ø2, x3), and so on till the whole x is solved. This serial solution cannot be made parallel because solving (Iz, Ir) needs (I1, ø2, 2z) to be already solved, and is thus extremely time-consuming. The fundamental reason for the dependency in solving æ is that, some field. Therefore, if we make the receptive field non-overlapping, then parallel solution right-inverse becomes possible.
is involved in the forward calculation of different V/. i.c., the overlapping receptive
convolution for inverse KKngmaa and Dhariwal 2018 we propose blocked convolution for right-inverse. Blocked convolution is also non-overlapping. but extends invertibility to right-invertibillty. shown in Sec. 4.3 this extension boots the the R-D performance of idempotent LIC by a large margin.
Inspired by the non-overlapping

---

With this con-ovellapping blocked convolution, we can make solution of Following the previous example, using the same imput and output with 4 blocked-convooltion kernel, for now, solving (#1, .... .......4))) only needs to know U2), and solving (Z.,..., #t)) only needs to know (ys: 1/4), and these procedures can be made parallel. Matrix multiplication equivalents of normal convolution and blocked convolution are depicted in the upper and lower parts of Fig [a] respectively, using the well-known GEMM [GEM] formation. And an analysis of time complexity of 2D convolution can be found in appendix A.1
parallel.
3.1.2 Null-Space Enhancement and Coupling Enhancement for Expressiveness
Null-Space Enhancement
To solve the right-inverse of the proposed blocked convolution in parallel, we adopt the widely-used Moore-Penrose pseudo-inverse Moo as
X = YK*
(8)
where Y E BRo is the output of blocked convolution, X E R is the solved right-inverse and K RdxD the Moore-Penree pseudo-inverse of the kernel K Dxd b is the batch size, D and d are the input and output dimension of convolution in GEMM formation GEM
However, simple Moore-Penrose pscudo-inverse does not have enough expressiveness. This is because right-inverse of surjection might not be unique [Mcc Lane 2013). and the Moore-Penrose pseudo-inverse might be the optimal choice calculate the right-inverse for blocked convolution. Therefore, we leverage the null-space decomposition [Schwab et al. 2019 Wang et al., [202a b to identify a right-inverse that is most suitable. More specifically, Eq. can extended
x YK + F(I - -K*).
(9)
Here F E 126xD can be an arbitrarily chosen variable. Utilizing this property, we propose to learn function f(Y) to identify an F that is the most suitable as:
= Y + f(Y)
(10)
We call this approach null-space enhancement (NE). In this way, right-inverse X can be made more than just linear transformation Y and thus become more expressive. Ablation study of the proposed null-space enhancement can be found in Sec 4.3 Derivation of Eq 9 and parameterization of kernel
K can be found in appendix A.2
Coupling Enhancement
The proposed blocked convolution makes the calculation of right-inverse maralel-ffieendly but it also restricts the receptive field to a blocked pattern (Fig. [b). This restriction limits the exchange of information across different spatial locations. To overcome this drawback, propose to introduce coupling enhancement (CE) after the blocked convolution.
Specifically, we implement a coupling structure (Dinh et al. [016]. and utilize normal convolutions without blocked limitation as its scale and translation functions. This structure is formulated as
[ 222] 51 = 3,, y/2 22 ② exp (s(x))) + ((x)), y = [yn ya]
(11)
Here, x and y are the input and output, respectively. [:] is the split/concatenate operation along the channel dimension, and @ is the element-wise multiplication. s(-) and t(-) are the scale and translation functions, respectively. This structure is fully invertible as
(12) Note that the invertibility of this coupling structure does not require the invertibility of the scale and translation functions s(.) and t(-), thus s(-) and t(-) can be arbitrary learned transforms. Since the proposed coupling enhancement utilize normal convolutions as its s(-) and t(.), its receptive field is not restricted to be blocked, and can thus serve enhancement of expressiveness.
y 1/1 V2l 31 y1. 22 (y2 t(x1))/ exp (s(x1)), [x] 222]
3.2 Right- Riight-nneettble Generalized Divisive Normalization
The widely-used generalized normalization (GDN) et al. 2013 LIC invertible in theory, and is thus qualified as surjection. However, the inverse of GDN has to be solved for every input

---

conv
GDN
comv
ricorv
C-GDM
riconv
nicony
fight-inverse ghttinnerttible
AE
hyper
AE
hyper
convolution (no weights)
decony
IGDN
deconv
AD
riconv
C-
NE riconve
AD
C-GDN
inverse of c-GDN (no weights)
NE
(a) baseline framework
(b) proposed framework
Comparison between (a) baseline framework (Ballé al. 2018) and (b) proposed framework. To make the framework idempotent, we replace conv/decony with right-invertibe convolution (described in Sec. (.I). GDN/GGNN with c-GDN (described in Sec. (32), and quantization
Figure 2:
Q with idempotent quantization Qi (described in Sec, 3.3) Both frameworks use the same mean-scale
Gaussian entropy model [Minnen al. 2018 AE/DD are arithmetic encoder/decoder, respectively.
image an iterative manner, and is even not guaranteed to converge in finite steps. Therefore, the original GDN is not suitable for idempotent compression.
We propose a coupling GDN layer (c-GDN) that combines the coupling structure (Dinh al. 2016] and GDN. The inverse of c-GDN layer can be solved in much simpler analytical manner. Specifically, we implement a coupling structure [Dinh et al. 2016] with normal GDN as its scale and translation functions (s(-) and t(-)). And just like the aforementioned coupling enhancement, the forward and inverse of this c-GDN layer can be calculated according to Eq. 11 and Eq. [2] respectively, We demonstrate empirically in Sec. 4.3 that the proposed c-GDN layer can achieve comparable RD performance with the original GDN.
3.3 Right-Invertible Quantization
As previously discussed, the vanilla scalar quantization using rounding is naturally idempotent. However, the widely adopted mean-shift trick quantization for mean-scale Gaussian entropy model Minnen et al.,, 2018 is not guaranteed to be idempotent. As proposed by [Minnen et al. 2020). the
mean shifted quantization can be formulated as
Q y
(13)
where L.1 is scalar quantization and is the predicted mean of y. Let y1 denote the result after the first application of Q, then idempotence requires that Q(y)) yı, which in turn requires y/ | to be integer. However, no existing method can meet this requirement, thus Q is not ensured to be idempotent.
propose two types of circumvention to solve this issue. For the first-type cireumvention, we change the quantization into
Q+ = y 1 + [p]]
(14)
By adding 1.1 around the predicted mean 14, force the quantization result be integer, thus [[4] is guaranteed to be integer from the second application of Qi and then Q: is idempotent.
For the second-type circumvention, we resort to the original definition of mean-scale Gaussian entropy model [Minnen et al. 2018), and calculate the quantized CDF (cumulative distribution function) regarding Q,(y) y on the fly during inference.
3.4 Overall Framework of Right-Invertible Codec
The overall framework depicted in Fig. 2 Following prior works [Ballé al.) 2017 2018 Cheng et al.) 2020, He et al., 2022 in LIC, We use the mainstream four-stage framework in our work. Specifically,
encoding transform divided into four stages, and each stage decreases resolution by factor of 2. For the first 3 stages, each stage starts with right-invertible convolution layer (described in Sec. 3.Tp and ends with a c-GDN normalization layer (described in Sec. 3.2). The last stage only consists of one right-invertible convolution layer.
5

---

[idemp] JPEC2000
34
[idemp] proposed
pan
[idemp] Helminger2021
[ddemp] proposed (34.77)
32
freat id] proposed
[idempp] Helminger2021 (32
proposed
[near proposed
Treat id] Kim2020
[near id] Cai2022 (36.41)
Kim2020 (50)
Kim2020 (34.78)
Inon id] He2022
[non kd] Cheng2020 (36. 62)
Id] He2022
VTM444
(36.63)
0.2
0.4
0.6
0.8
1.0
1.2
1.4
1.6
1.8
2.0
10
20
30
40
50
bpp
iterations
(a)
(b)
Figure 3: Performance of different codecs on Kodak. Idempotent codecs are marked as idemp. near-idempotent codec are marked near id and non-idempotent codecs are marked as non id. (a) First-time and re-compression (upto 50 times) RD performance of different codecs. Idempotent codecs only report first-time RD performance (re-compression RD performance is the same). (b) PSNR drop during re-compression (upto 50 re-compression) of different codecs. Note that idempotent codecs are straight lines and cover each other in the figure.
The decoding transform is built to be right-inverss of the encoding transform. Note that not all layer in the decoding transform has its own weights. Specifically, for c-GDN normalization layers, there is no additional weights since they are the inverse of their counterparts in the encoding transform. For right-invertible convolution layers, the only additional weights appear in the null-space enhancement (Sec. 3.1
Entropy model does influence idempotence in the proposed framework, thus use the off- shelf mean-scale Gaussian entropy model [Minnen et al. 2018 for its availability and efficiency. Additionally, we use the right-invertible quantization (described in Sec. 3.3 for quantizing the code.
3.5 Extension Near-Idempotent Learned Image Codec
Idempotent codec can make sure that the RD performance keeps unchanged during any times of re-compression. However, this strict idempotence comes with price that the decoding transform must be the right-inverse of encoding transform. This limitation reduces the expressiveness of transforms and empirically harmful to the first-time RD performance.
To adapt to the cases where first-time RD performance also matters, we propose to extend our idempotent codec near-idempotent codec by relaxing the right-invertibilltty The relaxation of right- invertibility is simple yet effective: we change the first right-invertible convolution layer (described in [) be non-surjective, and keep all the rest layers surjective. This is done by allowing D to be smaller than d for the kernel K in the first right-invertible convolution layer. By keeping the iebb-invertibility of most layers, our near-idempotent codec more stable re-compression than existing near-idempotent codecs Kim et al. 2020 better first-time RD performance.
Cai et al. 2022), while achieving comparable or
Experiments
4.1 Experiment Setup
All the models are trained on the training split of open-images dataset (Kuznetoova et al. 2020 and all the evaluations conducted the Kodak dataset [Franzen] 1999
sketch the training schedule accordingly from existing literature Ballé et 2017 2018 Minnen
et al. 2018 2020 Cheng et al. 2020). Images are randomly cropped to 256 x 256 for training, and batch size 16 is used. All the models are trained using an Adam optimizer. The learning rate initially set to 10 and decays by a factor of 10 when plateaued.

---

We choose four bitrate level accoding to the benchmark setting in Kim et al. 2020]. Specifically, we set À {18, 67, 250, 932) x 10-4, and models trained with these À reaches average bitrates from 0.2-1.5 on Kodak dataset. Following prior works [Ballé et al. 2017 2018), we use smaller code channels (192) for lower-bpp nower-hpppooines,,
points, and use bigger code channels (320) for higher-bpp points. The learned function f(() in Eq i0 implemented with a residual block.
All the experiments are conducted on computer with AMD EPYC 7742 64-Core Processor and 8 Nivida A30 GPU, All the code is implemented based Python 3.9, Pytorch 1.12 and CompressAT Bégaint al. 2020
4.2
Overall Performance
4.2.1
Results of Idempotent Codec
We compare with [Helminger et al., 2021]. which the only prior LIC that achieves idempotent lossy compression to the best of our knowledge. We also compare with traditional idempotent codecs such as JPEG2000.
We report first-time compression RD performance of the above idempotent codecs in Fig. B aa), and detailed BD-BR and BD-PSNR are listed in Tab. Multi-time re-compression RD performance does not change for idempotent codecs. From the result we see that, our proposed framework exceeds prior art [Helminger et al. 2021 by large margin, which clearly validates the superiority of right-inverse over strict inverse on the idempotent lossy compression task.
We also compare the FLOPs and encode-decode time in Tab. The proposed idempotent framework is also more efficient than [Helminger et al. 2021].
The results clearly shows that the
Table 1: The BD-BR, BD-PSNR, FLOPs and encode-decode time of different methods on Kodak dataset. FLOPs and enc-dec time are calcualted on an input of shape 256 x 256 x 3.
Methods
BD-BR (%)
BD-PSNR (dB) t GFLOPs 4 time (ms)
Idempotent Codec
JPEG2000
0.00
0.00
Helminger et al. 2021
4.83
-0.21
15.89
185 110
Proposed Idempotent
-28.75
1.63
8.40
4.2.2 Results of Near-Idempotent Codec
For near-idempotent codecs, compare against prior work (Kim al. 2020], well [Cai ct al. 2022] which utilizes a partially invertible structure. To demonstrate the advantages over non-idempotent codecs, we also compare with non-idempotent learned codecs (Ballé al. 2018 Cheng et al. 2020 He et al. 2022] as well as traditional codecs BPG and VTM.
Following the benchmark protocol in [Kim et al.) 2020 report the PSNR drop of the above codecs upto 50 re-compression. RD trade-off points whose first-time hpp is closest to but not greater than 0.8 bpp are chosen for each codec. The results is shown in Fig. (3)b) and listed in detail in Tab. From the result we see that, in the near-idempotent setting, the PSNR drop of proposed framework is 0.87dB, whereas [Kim et al.) (2200) and (Cai et al. 2022 has more than 2dB PSNR drop. Additionally, the PSNR drop of the proposed framework almost converges within 10 re-compression, while other near-idempotent frameworks still experience evident PSNR drop after 30 even 50 re-compression. Codecs that do not consider idempotence suffers a much more severe drop of PSNR during re-compression.
We also provide the RD performance of the proposed idempotent and near-idempotent frameworks, as shown in Fig ((). is clear that near-idempotent framework has much better first-time compression RD performance than idempotent framework. In terms of re- re-compression RD performance, however, near-idempotent can only reach similar RD performance with much higher computation cost (8.40 GFLOPs v.s. 48.78 GFLOPs in Tab and Tabī)..
These results clearly demonstrate that, even if we break the right-invertibiliiy of the first layer in order to get higher first-time RD performance, the performance drop during re-compression still acceptable and highly controllable, opposed to prior works [Kim et al. 2020 Cai et al. 2022]
7

---

Table 2: PSNR drop during 50 re-compression of different non-idempotent and near idempotent
codecs. FLOPs and encode-decode time tested under the same condition as Tab. T
PSNR Drop (dB)
4
GFL.PPs 4
time (ms) 4
round =
5
10
25
50
Non-ldempotent Codec
BPG
1.16
1.93
2.10
2.19
VTM
1.19
2.09
4.50
7.18
Ballé et al. 2018
2.18
3.17
5.65
8,46
6.23
Cheng al. 2020
2.44
4.76
8.59
12.40
51.99
>1000
Near- Near-Idempene Idempoeent Codec
Kim et al. 2020)
0.18
0.61
3.18
8.26
6.23
80
Can al. 2022
1,36
2.01
2.75
131.46
240
Proposed Near Near- Edempoenmtt
0.74
0.83
0.87
0.87
48.78
115
W.D. C-en
NE
Inv.
36
comvixl
30
0.4
1.5
(a) RD performance of different architectures Kodak
(b) Influence of coupling enhancement (better viewed zoomed-in)
Figure 4: Ablation studies for different architectures. (a) Re-compression RD performance of different idempotent architectures on Kodak dataset (except for w. GDN, for which we report first-time compression as non-idempotent). (b) qualitative results for w. (right) or w.o. (left) coupling
enhancement.
4.3
Ablation Studies
Inverse Right-Inverse The importance of right-inverse for idempotent lossy compression already be seen from the difference between the proposed framework and [Helminger et al.) [021]] in Fig. a) and Tab. To further demonstrate this importance, proposed framework is changed from right-invertible to invertible. Specifically, we increase the output dimension of the proposed blocked convolution (Sec. 3.1) to its input dimension, that becomes fully invertible. We also test what happens if the proposed blocked convolution is replaced with invertible transform is fully invertible.
test what happens if the
convolution Kingmma and Dhariwal 2018 For both cases, the encoding
Fig. (a) shows that both invertible blocked convolution (inv.) and invertible 1 x 1 convo- lution (w convix1) suffer dramatic RD performance degradation compared with the proposed right-invertible framework (proposed). This result further demonstrated that it is important for idempotent LIC to have right-inverse rather than inverse.
Impact of Null-Space Enhancement Null-space enhancement is introduced in our framework to enable an adaptive right-inverse for linear layers rather than a fixed Moore-Penrose psudo-inverse. As is shown in Fig. 4 for the two lower-bpp points, the framework with null-space enhancement

---

(proposed) has a 1 dB advantage over the framework without null-space enhancement (w. NE), whereas for the two higher-bpp points this advantage shrinks to be smaller than 0.5 dB. The reason is that the two lower-bpp points have a smaller code channels (192) than the two higher-bpp points (320). A smaller code channel means larger null space, and thus null-space enhancement can make larger improvement.
Impact of Coupling Enhancement Coupling enhancement improves the receptive field of convo- lution. The proposed blocked convolution is parallel friendly, but also restricts the receptive field. Qualitatively, this constraint results in obvious deterioration in the flat area, such as the wall, the sky and the face, as is shown in the left column of Fig. 4b). By introducing coupling enhancement after blocked convolution, the restriction is lifted and the block artifact on the reconstructed images are removed, as is shown in the right column of Fig. I). Quantitatively, the RD performance is also improved by coupling enhancement, which shown by comparing proposed and w.o o. c-en in Fig. 4 (a).
Impact of Right-Invertible Quantization As is pointed out in Sec. 3.3 the mean-shifted quantization is not guaranteed to be idempotent, and we propose two alternatives to circumvent this issue. In the proposed framework, we use the second-type circumvention. Here we compare these two choices. As is shown in Fig. a), first-type circumvention (w.int mean) performs slightly worse than second-type cireumvention (proposed). This is because first-type circumvention forces the mean to be integer, whereas second-type does not has this constraint. However, the second-type cireumvention requires calculating the quantized CDF on the fly during inference.
Impact of Right-Invertible GDN To make the inverse of GDN layer actually computable in the proposed framework, we combine the coupling structure [Papamakarios et al.) 2021 with GDN, is described in Sec. 3.2 Here we demonstrate that such workaround does not affect the RD performance. Specifically, we change the c-GDN and c-GDN-1 layer our framework (Fig. b)) back to GDN and iGDN layer [Ballé et al. 2015). Note that this change makes the framework non-idempotent, and only used to test the RD performance. From the results in Fig. 4a we see that, Whether to use coupling GDN (proposed) or original GDN (w. GDN) has negligible influence on RD performance. Thus coupling GDN is an efficient and effective replacement for GDN in idempotent compression framework.
5
Related Work
The idempotence has been a crucial consideration for lossy image codecs. For image codecs without prediction encoding like JPEG [Wallace 1991] and JPEG2000 [TTaubman et al. 2002). idempotence naturally assured invertible encoding transforms like DCT DWT is adopted. As long as
the quantization is idempotent (which is true for scalar quantization), the whole codec becomes
idempotent (Joshi al. 2000 Richter al. 2017].
The idempotence of learned image compression is firstly studied by [Kim 2020 which proposes near-idempooence solution that alleviates re-compression loss but does not eliminate it. (Cai et al., 2022) further improves over [Kim et al.) 2020) while it is not able to achieve strict idempotence. Helminger et al. 2021 is the first LIC that achieves idempotence, using fully invertible normalizing flow as encoding transform. However, it's RD performance dramatically falls behind modern LIC.
Our work is also related to SurVAE flow Nielsen al., 2020). On the one hand, the idempotence of LIC requires the encoding transform to be surjective, which is similar to the goal of Sur flow. The difference is, consider deterministic right inverse, whereas SurVAE flow considers stochastic right inverse. On the other hand, the techniques proposed in this paper. such as blocked convolution and null-space enhancement, can be used to improve SurVAE flow.
6 Discussion & Conclusion
To conclude, we first identify that invertibility sufficient but not necessary for idempotent codec, and it can be instead relaxed to right-invertibility. Based on this identification, we investigate the practical implementation of right-inverse with efficiency and expressiveness. Empirically, We show that the proposed method achieves state-of-the-art RD performance among idempotent codecs. Furthermore,

---

our codec can be easily relaxed into a near sear-idempttent codec, which also achieves state-of-ther re-compression performance among near-idempotent codecs.
For future work, one possible direction constructing right-invertible transform without function composition. Currently, the right-invertible transform is constructed using composition of surjections. Such construction strictly restricts the latent dimension to be non-increasing throughout the transform. This restriction is conflict with the prevalent design logic of neural network and is detrimental to expressiveness. It would be interesting to see if this restriction could be removed and how much the performance could be improved.
Acknowledgements
Funded by Baidu Inc. through Apollo-AIR Joint Research Center.
References
Matrix multiplication background user's guide.
URL
https://docs.nvidia com/
.tml
Moore-penrose inverse. URL http://www.kkpaaaa..o///////ooa/
J. Ballé, V. Laparra, and E. P. Simoncelli. Density modeling of images using generalized normaliza- tion transformation. arXiv preprint 15 2015.
J. Ballé, V. Laparra, and E. P. Simoncelli. End-to-end optimized image compression. In 5th International Conference on Learning Representations, ICLR 2017, 2017.
J. Ballé, D. Minnen, S. Singh, S. J. Hwang, and N. Johnston. Variational image compression with scale hyperprior. International Conference on Learning Representations, 2018.
J. Bégaint, F. Racapé, S. Feltman, and A. Pushparaja. Compressai: a pytorch library and evaluation platform for end-to-end compression research. arXiv preprint arXiv:201 1.03029, 2020.
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 applications. IEEE Trunsactions on Circuits and Systems for Video Technology, 31 31(10))3736-377 37663774, 2021.
Cai, Zhang, L. Chen, L. Yan, S. Zhong, and X. Zou. High-fidelity variable-rate image compression via invertible activation transformation. In Proceedings of the 30th ACM International Conference on Multimedia, pages 2021-2031, 2022.
Z. Cheng. H. Sun, M. Takeuchi, and J. Katto. Learned image compression with discretized gaussian mixture likelihoods and attention modules. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7939-7948, 2020.
L. Dinh, J. DicksDic,,,,in, and Bengio. Density estimation using real nvp. arXiv preprint 1605 2016.
R. Franzen. Kodak lossless true color image suite. source: htt:://rk.. ud/graphics/kodkk, 4(2), 1999.
D. He, Y. Zheng, B. Sun, Y. Wang, and H. Qin. Checkerboard context model for efficient learned image compression. Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition, pages 14771-14780, 2021.
D. He, Z. Yang, W. Peng, R. Ma, H. Qin, and Y. Wang. Elic: Efficient learned image compression with unevenly grouped space-channel contextual adaptive coding. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 5718-5727, 2022.
L. Helminger, A. Djelouah, M. Gross, and C. Schroers. Lossy image compression with normalizing flows. Neural Compression: From Information Theory to Soplications-Worrllhe ICLR 2021, 2021.
10

---

R. L. Joshi, M. Rabbani, and M. A. Lepley. Comparison of multiple compression cycle performance for jpeg and jpeg 2000. In Applications of Digital Image Processing XXIII, volume 4115, pages 492-501. SPIE, 2000.
J.-H. Kim, S. Jang. J.-H. Choi, and J.-S. Lee. Instability of successive deep image compression. In Proceedings of the 28th ACM Interaational Conference on Multimedia, pages 247-255, 2020.
D. P. Kingma and P. Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. Advances in neural information processing systems, 31, 2018.
A. Kuznetsova, H. Rom, N. Alldrin, J. Uijlings, I. Krasin, J. Pont-Tuset, S. Kamali, S. Popov, M. Malloci, A. Kolesnikov, et al. The open images dataset v4: Unified image classification, object detection, and visual relationship detection scale. International Journal of Computer Vision, 128 19)11956-1981, 2020.
M. Lezcano-Casado. Trivializations for gradient-based optimization manifolds. In Advances in Neural Information Processing Systems, NeurIPS, pages
2019.
S. Mac Lane. Categories for the working mathematician, volume 5. Springer Science & Business Media, 2013.
D. Minnen, Ballé, and G. D. Toderici. Joint autoregressive and hierarchical priors for learned image compression. Advances in neural information processing systems, 31, 2018.
D. Minnen, S. Singh, and J. Ballé. Channel-wise autoregressive entropy models for learned image compression. 2020 IEEE International Conference on Image Processing (ICIP), pages 3339- 3343. IEEE, 2020.
D. Nielsen, P. Jaini, E. Hoogeboom, O. Winther, and M. Welling. Survae flows: Surjections to bridge the gap between vaes and flows. Advances in Neural Information Processing Systems, 33: 12685-12696, 2020.
G. Papamakarios, E. Nalisnick, D. J. Rezende, S. Mohamed, and B. Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. The Journal of Machine Learning Research, 22(1): 2617-2680, 2021.
K. H. Randall. Cilk: Efficcint multithreaded computing. Phl) thesis, Massachusetts Institute of Technology, 1998.
T. Richter, J. Keinert, A. Descampe, G. Rouvroy, and A. Willeme. coltiigenneration-robeee coding with jpeg xs. In 2017 IEEE International Symposium on Multimedia (ISM), pages 6-13, IEEE, 2017.
J. Schwab, S. Antholzer, and M. Haltmeier. Deep null space learning for inverse problems: conver- gence analysis and rates. Inverse Problems, 35(2):025008, 2019.
G. J. Sullivan, J.-R. Ohm, W.-J Han, and T. Wiegand. Overview of the high efficiency video coding (heve) standard. IEEE Transactions on circuits and systems for video technology, 22(12): 1649-1668, 2012.
D. S. Taubman, M. W. Marcellin, and M. Rabbani. Jpeg2000: Image compression fundamentals, standards and practice. Journal of Electronic Imaging, 11(2):28--277, 2002.
G. K. Wallace. The jpeg still picture compression standard. Communications of the ACM, 34(4): 30-44, 1991.
Y. Wang, Y. Hu, J. Yu, and J. Zhang. Gan prior based null-space learning for consistent super- resolution. arXiv preprint arXiv:2211.13524 2022a.
Y. Wang, Yu, and Zhang. Zero-shot image restoration using denoising diffusion null-space model. arXiv preprint arXiv:22 2022b.

---

Appendices
A Additional Explanation for the Methods
A.1 Complexity Analysis of Block Convolution
To discuss this problem, consider 2-dimension convolution with kernel size K x K, stride S x S, input spatial size x W, imput channel C₁ and output channel C.. Assuming the in in-place parallel matrix multiplication (Randal 1998 is used.
For serial method, as is described in Line 104-109, we first subtract the influence of the already-solved pixels, which takes OCC, time. Then we solve for the rest pixels, which takes OCC.) time. The point is, this subtract-ther then-solve procedure needs to be done (HW/552) times, in serial, so the overall complexity O HW
g (C,K²+ + Co)).
For parallel method implemented with the proposed blocked convolution, we can solve for all pixels with (C.) time complexity.
We can see that, compared with the parallel method, time complexity of serial method is forbiddingly higher and not viable for practical usages. In terms of re-compression performance, both serial method and parallel method are right-inverse, so idempotence can achieved for both.
A.2 More on Null-space Enhancement
Parameterization of Surjective Linear Transform
For linear transform with kernel K E Rxx to be surjective, K must have full column rank, i.e., must be less or equal to D and the rank of K is d. The vanilla parameterization of K as matrix cannot ensure this property. Thus, use singular value decomposition (SVD) parameterization to ensure that K is surjective. Specifically, orthonormal matrix, S is d diagonal matrix with non-zero diagonal elements, and V is d d orthonormal matrix. With this decomposition, K is guaranteed to have full column rank, and is thus surjective. Accordingly, Eq. 10 is parameterized
is decomposed as = USVT, where U is a D x
(15) where 5 the inverse of non-zero diagonal matrix For orthonormal matrix U and V, we adopt the parameterization in (Lezcano-Casade 2019). The matrix S is diagonal and trivial to parameterize. To avoid arithmetic overflow, we restrict the diagonal elements to be within [0.1, 10).
= YVV + f(Y) - UUT)
Derivation of Null-space equality
E E F X Y YK*K** K + F(I KK+) is solution to Y = X..
Proof. From the property of Moore- Moore-Penrose pseudo-inverss
Moo we know that
KK* = K.
(16)
Additionally, for orthonormal K (with linearly independent columns), we have
kt = T.
(17)
Then, right-multiply X(Y;K) by K, we get
XK YK+ K + F(I KK
(18)
Y FK=
B
More Experimental Results
B.1
More Experiment Setup
The detailed encoding and decoding transform illustrated in Fig. 5 extend the idempotent framework cear-idempotent framework, we change the first blocked convolution in the encoding
12

---

encoding
decoding
encoding
decoding
Jblocked(3, 10)
RBBB
NE f=RBD
blocked 128)
c-enhance(5x5)
c-enhance(3xx3
c-GDN
c-GDN
Jblocked(10, 38)
NE RBBBU
(blocked(128, 128)
NE f=RBU
c-enhance(5x5)
c-enhance(3x3)
c-GDN
c-GDN
[blocked(38, 150)
NE f=RBU
Jblocked(128, 128)
NE R=BBU
c-enhance(5x5)
c-enhance(3x3)
c-GDN
c-GDN
Lblocked(150, 192)
f=RBU
(blocked(128, 192)
NE f=BBU
C-enhance(5x5)
c-enhancee3x33
(a) Details of the proposed imdempotent framework (b) Details of the proposed near-imdempotent framework
Detailed encoding and decoding transform for the proposed idempotent and near- idempotent framework. blocked refers the proposed blocked convolution. The (input, output) channels are annotated in the brackets, and stride is annotated using down-arrow. NE refers to the proposed null-space enhancement, and learned parametric function. Here RBU/RBD are the residual block used for upsamplig//downsampiing (Fig. b)). respectively. c-enhance refers to the proposed coupling enhancement using coupling structure (Fig. ((a)). The kernel size of the convolution is annotated in the brackets. c-GDN refers to the proposed right-invertible normalization using coupling structure (Fig. ())). Blanked rectangular refer to the right-inverse/nnvers of the corresponding layer, and has additional weights.
Figure 5:
3/1
8(-)
x-))
(-)
leakyReLU
TeakyReLU
231
91
COnV333
leakyRel
deconv3x3
leakyReL U
conv3x3.
deconv3x3
forward
inverse
RBD
RBU
(a) Couping structure used c-enhence and c-GDN
(b) Residual block used null-space enhancement
Figure 6: Submodules used in the proposed framework: (a) coupling structure used in e-enhance and
C-GDN; (b) residual block downsampling (RBD) and residual block upsampling (RBU) used in the f()) of null-space enhancement.
13

---

[idemp] proposed GDN
[idemp] RB
36
[iderrp] proposed RB
22
[near id] proposed (35.79)
[near proposed
[near id] proposed w. conv (35.91)
Balle2018
0.2
0.4
0.6
0.8
1.0
10
20
30
50
bpp
iterations
(a)
(b)
Figure 7: Additional experiments on: (a) extendability of the proposed idempotent framework (b)
functionality of different components of the proposed near-idempotent framework.
transform non-surjective by increasing its output channel number from 10 128. Since this blocked convolution is no longer surjective, it is no longer right-invertible. However, its corresponding layer in the decoding transform can be make surjective and right-invertible. Thus, we make its corresponding layer in the decoding transform surjective, and use the null-space enhancement on the encoding side.
Coupling structure [Dinh al. 2016) used in coupling enhancement (c-enhance) and coupling GDN (c-GDN) is illustrated Fig. ((a) For c-enhance, the scale s(.) and translation ((-) are convolution. For c-GDN, the scale s(-) and translation t(-) GDN [Ballé al., 2015). Following the usage guideline in [Dinh et al. 2016), we concatenate two coupling structure with the opposite way of splitting in one c-enhance/c-GDN.
We provide additional experiments on (a) extendability the proposed idempotent framework (b) funetionality of different components of the proposed near-idempotent framework. Specifically, to demonstrate the extendability of the proposed idempotent framework, we replace GDN with residual blocks suggested by (He al., 2022] (RB x for residual block, RBx3 for three residual blocks), and report the RD performance in Fig 7 [a). is clear that, replacing GDN with the more recent residual blocks would also improve framework is compatible with the recent advances in LIC and has good extendability.
framework
similar degree. Thus proposed
To analysis the functionality of different components of the proposed near-idempotent framework. we test what happens if the modification to each component is not applied, and report the PSNR drop during re-compression in Fig b)). Specifically, we test keeping the GDN layers unchanged (* gdn or keeping the convolution layers unchanged (w. conv). Keeping both the GDN layers and the convolution layers would reduee to baseline Balle2018. The results shows that keeping more layers unchanged may slightly improve first-time compression performance, but evidently harmful to re-compression performance. The proposed near-idempotent framework has the best re-compression performance among these settings.
We include the implement of other codecs as follows. For codecs that have open-source implementa- tions, we use that implementation. For codecs that do not have open-source implementations, we either use the data provided in the paper, re-implement by ourselves if the detailed architecture is provided.
Implementations from AompressAl [Bégaint et al. 2020]: Balle et al. 2017] Balle201 8 Ballé et al. 2018), Cheng2020 Chennnggnnnnn et 2020 JPEG2000 Taubman et al. 2002). BPG444 Sullivan et al. 2012), VTM444 Bross et al. 2021
Data from the original papers: Helminger2021 Helminger et al. 2022
2021 Cai2022 Cai et
Our re-implementation: Kim2020 Kim et al. 2020). Specifically, we re-implement the loss proposed in this work on Balle2018 [Ballé al. 2018
14

---

B.2
More Quantitative & Qualitative Results
See Fig. for more quantitative results.
See Fig.
12 15 for more qualitative results.
C
More Discussion
C.1 Limitation
In this work, the surjective encoding transform is constructed using function composition of simple surjections. This construction strategy limits the latent dimension to non-increasing throughout the encoding transform. This limitation contradicts the mainstream design logic of neural network, and is harmful to expressiveness.
A function composition of surjections is always surjection, but surjection needs not to be function composition of surjections [Mac Lane 2013). Thus this restriction could be lifted by more advanced construction strategy of surjection.
C.2 Broader Impact
Improve the rate-distortion of re-compression has positive social impact. Re-compression constantly happens the transmission and redistribution image data. Reducing the bitrate can save the resources, energy and the carbon emission during these processes.
C.3 Reproducibility Statement
All theoretical results are proven in Appendix. A For experimental results, all the datasets used are publicly available, and the implementation details are provided in Appendix, [B] Furthermore, the source code for reproducing experimental results are provided in supplementary materials.
15

---

38
36
[idemp] JPEG2000
[idemp) praposed
[idemp] Helminger2021
[near [d] proposed
32
Inear id] proposed (50)
[ncor [d] Kim2020
Kim2020
[near id] Ca/2022
30
[near
[non He2022
[non [d] Hc2022 (50)
BPG444
[nan (d] BPG444 (50)
Inon
[non VTM444 (50)
26 0.0
Figure 8: PSNR-BPP curve on Kodak. Idempotent codecs are marked as idemp, near-idempotent codec are marked near id and non-idempotent codecs marked as non id. First-time com- pression performance is plotted in dotted line, and re-compression performance (upto 50 times) is plotted in solid line.
[idemp] JPEG2000
[idemp] progosed
Inear id] proposed
22
[near id]
Inear id] Kim2020
[near id]
(50)
[near id] Cai2022
20
Inear id] Cal2022 (32)
Inon id] He2022 (50)
Inon id] BPG444 (50)
18-
Inon id] VTM444
16-
14
12
0.4
1.0
1.8
bpp
Figure MSSSIM-BPP curve on Kodak. Idempotent codecs are marked as idemp, near-idempotent codec are marked near id and non-idempotent codecs are marked as non id. First-time com- pression performance is plotted in dotted line, and re-compression performance (upto 50 times) is plotted in solid line. All models are optimized for minimizing MSE.
16

---

[idemp] proposed (34.77)
[idempl Helminger2021 (32.04)
[near id] proposed (35.79)
pann drop
Ca12022 (36.41)
[near Kim2020 (34. 761
[non id] Cheng2020 (36.62)
Balle2018 (34.53)
[non id] VTM444 (36.63)
Inon id] BPG444 (35.571
10
20
30
40
50
Iterations
Figure PSNR drop upto 50 re-compression on Kodak. Idempotent codecs are marked idemp, near-idempotent codec are marked as near id and non-idempotent codecs are marked as non id. First-time PSNR is annotated in (-).
drop
[idemp] proposed [17.8] (3.83)
[near id] proposed nearlddemp (18.52)
Inear id] Cal2022 (19.40)
id]
Inon id] Cheng2020 (19.58)
[non id] Balle2018 (18.01)
VTM444 (18.86)
[non id] BPG444 (17.96) 96)
10
20
30
40
50
iterations
Figure 1I: MS-SSIM drop upto 50 re-compression on Kodak. Idempotent codecs marked as idemp, near-idempotent codec are marked as near id and non-idempotent codecs are marked as non id. First-time MS-SSIN is annotated in (+). All models are optimized for minimizing MSE
17

---

Ground-truth
JPEG2000(50-th). BPP-0.798, PNSR-31.98
Balle2018(50-th), BPP=0.784, PN5R=18.25
Ours idempotent((0-th) BPP=0.953, PNSR-35.01
Figure 12: Qualitative comparison on reconstructed kodim06 image after 50 times re-compression.
Ground-truth
JPEG2000150-th) BPP-0.800 PN5R-32.86
Balle2018(50-th), BPP=0.590, PN5R=17.75
Ours idempotent(50-th) BPP=0.856, PNSR=35.12
Figure 13: Qualitative comparison on reconstructed kodim11 image after 50 times re-compression.
18

---

Ground-truth
JPEG2000(50+th). BPP-0.800, PN5R-26.12
Balle2018(50-th), BPP-1.949, PNSR=8.87
Ours idempotent(50-th) BPP-1.806, PNSR-32.91
Figure 14: Qualitative comparison on reconstructed kodim13 image after 50 times re-compression.
Ground-truth
JPEG200015-thh. 8PP-0.798, 30.0-
Balle2018(50-th). BPP=0.844, PNSR=17.40
Ours idempotent(S0-thh BPP=1.129, PNSR=34.11
Figure 15: Qualitative comparison on reconstructed kodim24 image after 50 times re-compression.
19


Reviews:
[{"review_id": "ICLLtxAqos", "reviewer": "Reviewer_FGoX", "summary": "In this work the authors address the problem of stability of codec re-compression (idempotence). In particular the paper points out the difficulty of achieving idempotence in learned image compression, and existing methods rely on invertible models such as normalizing flows which limits their performance. \nThe observation is that the only constraint is to have right-invertible transforms. Blocked convolutions are proposed, such that the right inverse matrix corresponding to the encoder convolution is used on the decoder side. \n\nBesides this main point, the paper also presents additional improvements to: 1) limit the effects of the block pattern in the receptive field, 2) extend the commonly used GDN layers, and 3) address the issue with mean-shift trick quantization that doesn’t guarantee idempotence. \n", "questions": "My questions are in the weaknesses (priority must be given to questions 3 and 7)", "limitations": "The authors discuss limitations in a sufficient manner.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In general the paper is well written and clearly motivated. There are several key contributions:\n+ Idea of using right inverse and its implementation with the blocked convolution and right matrix inverse.\n+ Addressing all remaining details in a sound way: GDN layer, issue with the mean-shift trick in the mean-scale entropy model\n\nIt is also important to mention that has:\n+ State of the art results for idempotent image compression\n+ An ablation study that shows the importance of each contribution\n+ Code provided along with the submission.\n", "weaknesses": "In general I think the paper is doing a great job in presenting the problem and the solution I would have minor points that authors should address in the rebuttal:\n\n1. I think the transition from function notation to matrix notation is not smooth, and in general the transition from idempotence to right inverse could be better explained for readers less familiar with the topic of learned image compression.\n\n2. The word “Rearrangement” together with the kernel size 5 example in line 94 brings a lot of confusion. It took me a while  to realize that the paper was proposing a new convolution and receptive fields are not overlapping which is needed to make everything work. \n\n3. Too much space is used for the Blocked convolution while the description is not detailed enough for the rest. For example what is f(Y) exactly (eq. 11 and 12). How is it learned? \n\n4. The extension to Near-Idempotence is a bit rushed and it’s not clear of considering the modification applied to other layers might be better?\n\n5. In the experiments, It should always be mentioned “idempotent” or “near-idempotent” to avoid any doubt. \n\n6. For reference, best performing non idempotent model should appear in Figure 3.a\n\n7. For sanity check, both the idempotent version and [Helminger2021] should appear in Figure 3.b\n\n\nOther details :\\\nl. 74: section title “Right-Invertibie” -> “Right-Invertible’\\\nl. 94: missing word in “if exists”?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# To reviewer FGoX\n\nThanks for your advice. We address your concerns as follows.\n\n**weakness-1**:Thanks for the kind advice. We will improve Sec.2 and Sec.3.1 in order to give a better presentation for these two points.\n\nSpecifically, to better explain the transition from idempotence to right inverse for readers less familiar with LIC, in Sec.2, we will first introduce the general form for LIC, that is $y = Q \\circ E(x)$ and $\\hat{x}=D(y)$ ($\\hat{x}$ is the reconstruction and other notations are accordingly explained). Then, we introduce the re-compression setting, which is formalized by Eq. 2. After that, we explain the idempotence requirement, which requires $E \\circ D$ to be canceled. From this requirement, we give the usual solution of inverse, and finally the proposed solution of right-inverse.\n\nTo make transition from function notation to matrix notation smoother, in Sec.3.1, we will first give higher level description for right-inverse of convolutions using function notation. Then, we explicitly give the shape of every variable in the function notation, for readers to get better understand of the calculation of right-inverse. Finally, we give the matrix notation, and re-emphasize the shapes so that the readers can better link matrix notation with function notation.\n\n**weakness-2**: Sorry for the unclearness. We will make this more clear by focusing on why overlapping receptive field is problematic and how do we overcome this.\n\n**weakness-3**: We will rebalance different parts and explain more on the null-space enhancement and near-idempotent setting.\n\nFor $f(Y)$: $f(Y)$ is the implementation of $F$, and $F$ is the arbitrarily chosen variable in eq. 10. We choose to implement $F$ in the form of $f(Y)$ so that it is adapted to each different $Y$. \n\nSpecifically, $f(\\cdot)$ is learned with a common residual block, and we will include this in the experiment section.\n\n**weakness-4**: We provide additional ablation study, as follows, that tests what happens if the modification to other layers is not applied.\n\nSpecifically, we test keeping the GDN layers unchanged (*w. gdn*) and keeping the convolution layers unchanged (*w. conv*). Keeping both the GDN layers and the convolution layers would reduce to baseline Balle2018. \n\nAs is shown in **[rebuttal fig.1]**, keeping more layers unchanged may slightly improve first-time compression performance, but is evidently harmful to re-compression performance. The proposed near-idempotent framework has the best re-compression performance among these settings.\n\nExtra ablation study on whether changing each layer is very interesting, we are waiting for more results due to limited computational resources.\n\n**weakness-5 & weakness-6**: Thanks for your kind advices. We will modify these two points.\n\n**weakness-7**: We add idempotent codecs in Fig.3(b) for sanity check, which is shown in **[rebuttal fig.2]**. Please note that idempotent codecs are straight lines and cover each other in the figure."}, {"review_id": "flvFB5AMau", "reviewer": "Reviewer_H19p", "summary": "This paper introduces a learned image codec with a right-inverse transform. The task is to ensure that an image can be re-compressed multiple times without significant quality degradation, while the compression is still lossy. This work is one of the few early attempts along this line of research. Its applications are rather niche.", "questions": "See my comments in the weakness section.", "limitations": "Please clarify whether the training would be complicated by the use of SVD.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The paper is easy to follow and the task is novel.", "weaknesses": "(1) The main idea of null space decomposition has been proposed in J. Schwab, S. Antholzer, and M. Haltmeier,  Deep null space learning for inverse problems: convergence analysis and rates. Inverse Problems, 35(2):025008, 2019. \n\n(2) The necessity and benefits of the blocked rearrangement convolution with coupling enhancement over the ordinary convolution are not clear. It seems to me that this part is not essential to null space decomposition. The authors argue that blocked rearrangement convolution can work more efficiently. However, there is no evidence or ablation study to support the argument. \n\n(3) The right inverse requires E o D to be an identity matrix. However, Eqs. (8) and (9) suggests D o E is an identify matrix. \n\n(4) Can the re-compression be done on different computation platforms while maintaining the right inverse property? \n\n(5) There is no ablation study on the near-idempotent idea. In Section 3.5, the authors mention that the near-idempotent codec has better first-time compression performance than the idempotent codec. Is there any insight into this? Also, how about the recompression performance as compared to the idempotent design? \n\n(6) The proposed method involves SVD. I wonder if this complicates the training process. \n\n(7) The authors should cite \"https://github.com/mahaichuan/Versatile-Image-Compression\" for invertible compression backbone design.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# To reviewer H19p\n\nThanks for your advices. We address your concerns as follows.\n\n**weakness-1**: Yes, and we have mentioned it at Line 43. We are the first to apply null-space decomposition to LIC task. More importantly, we propose several novel designs to enable efficient idempotent LIC as summarized in L39-47.\n\n**weakness-2**: Null-space decompostion is of use only when the right-inverse can be practically calculated. Ordinary convolutions have overlapping receptive fields, and this makes the calculation of its right-inverse forbidenly costy, as explained in line 104-109. The proposed blocked rearrangement convolution addresses this issue by making the receptive field non-overlapping.\n\nTo be more specific, consider a 2-dimension convolution with kernel size $K \\times K$, stride $S \\times S$, input spatial size $H \\times W$, input channel $C_i$ and output channel $C_o$. Assuming the in-place parallel matrix multiplication[1] is used. For serial method, we first substract the influence of the already-solved pixels, which takes $O(C_iK^2)$ time. Then we solve for the rest pixels, which takes $O(C_o)$ time. This substract-then-solve procedure needs to be done $HW/S^2$ times, so the overall complexity is $O(\\frac{HW}{S^2}(C_iK^2+C_o))$. For parallel method implemented with the proposed blocked rearrangement, we can solve for all pixels with $O(C_o)$ time complexity. We can see that, compared with the parallel method, time complexity of serial method is forbiddenly higher and not viable for practical usages.\n\nOn the other hand, non-overlapping receptive field causes visual artifact, which can be effectively removed by the proposed coupling enhancement, as is shown in Fig.4(b) and explained in line 267-274.\n\nTogether, blocked rearrangement convolution with coupling enhancement provides computable right-inverse without visual artifact.\n\n**weakness-3**: We beg to differ. On the one hand, Eq. (8-9) only describe how we compute the right inverse of convolution. But $E$ and $D$ are NOT just convolutions. On the other hand, even for convolutions, a right-invertible convolution only requires $K$ to be full rank in its column, and this does NOT necessarily make $KK^+$ an identity matrix. Eq. (8) follows the convention of GEMM and writes $K$ on the right of $X$, which does not affect the order of $E$ and $D$.\n\n**weakness-4**: The idempotence is theoretically assured by right-inverse, thus cross-platform compatibility can be achieved.\n\n**weakness-5**: The insight is that near-idempotent codec does not need the right-invertibility of the encoding transform, and thus has wider choices or better model capacity. \n\nWe provide the ablation study between proposed idempotent and near-idempotent frameworks, as is shown in **[rebuttal fig.3]**. It is clear that near-idempotent framework has much better first-time compression RD performance than idempotent framework. In terms of recompression RD performance, however, near-idempotent can only reach similar RD performance with much higher computation cost (8.40 GFLOPs v.s. 48.78 GFLOPs in Tab.1 and Tab.2 ).\n\n**weakness-6 & limitation**: Yes, it slows down the training speed for 2-3 times.\n\nBut please note that in practical usages only inference stage is used. And inference stage is not affected because we only need the matrix, and SVD is not needed when doing inference.\n\n**weakness-7**: Thanks for the kind advice, and we will include this in the reference.\n\n[1] Randall, Keith H. (1998). Cilk: Efficient Multithreaded Computing (PDF) (Ph.D.). Massachusetts Institute of Technology. pp. 54–57\n[2] M. Lezcano-Casado. Trivializations for gradient-based optimization on manifolds. NeurIPS, 2019"}, {"review_id": "OMKAyQyoD6", "reviewer": "Reviewer_4J8x", "summary": "The paper argues that invertibility is sufficient but not necessary for achieving idempotent codecs, and proposes a framework for achieving idempotent learned image compression (LIC) with right-inverse, which allows more flexible and expressive transforms. This paper details the expressive and right-reversible atomic transformations used in LIC, including convolution (using blocked rearrangement and null-space enhancement), normalization, and quantization. ", "questions": "1、Compared with the serial method, how much time complexity does the blocked rearrangement save, and will it have a huge impact on RD performance and re-compression performance?\n2、Can the convolution, GDN, quantization, and other modules designed in the paper with the Right-Invertibie properties be applied to existing learned image compression frameworks? In that case, will the performance of the initial compression be dropped excessively?\n3、The subjective encoding transform limits the expressiveness of the network, try other better mapping strategies?\n4、Could the paper discuss the potential impact of the assumption that the input image is preprocessed to have zero mean and unit variance on the performance of the framework?\n", "limitations": "1. The proposed framework considers compression on integer latent, which is different from the common LIC method. \n2. The assumption that the input image is preprocessed to have zero mean and unit variance may not hold for all images.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1、The paper first theoretically proves that idempotence can be relaxed to be right reversible and details the Right-Invertibie Codec.\n2、The proposed framework achieves state-of-the-art RD performance among idempotent codecs. Also, it can be easily relaxed into a near-idempotent codec, which also achieves state-of-the-art re-compression performance.\n3、The paper is well organized with detailed description of various parts of the whole right-reversible atomic transformations.\n", "weaknesses": "1、Lack of analysis of the computational complexity of the proposed framework: The paper does not provide a detailed analysis of the computational complexity of the proposed framework. While the paper mentions that the proposed framework is efficient and parallel-friendly, it does not provide a detailed analysis of the computational cost of the various components of the framework.\n2、The First-time compression RD performance of the proposed codec dramatically falls behind modern LIC. For most scenarios, the first compression is also important. It will be interesting for the author to provide an analysis on feasibility to further improve RD performance of the proposed framework. \n3、Limited discussion of the limitations of the proposed framework: While the paper briefly discusses the limitations of the proposed framework.  For example, the paper could discuss the potential impact of the assumption that the input image is preprocessed to have zero mean and unit variance on the performance of the framework.\n4、Lack of comparison with non-idempotent codecs: The paper only compares the proposed framework with other idempotent and near-idempotent codecs.\n5、Limited analysis of the impact of null-space enhancement: The paper only shows the impact of null-space enhancement on two lower-bpp points and two higher-bpp points, and does not provide a more comprehensive analysis of the impact of this technique on the performance of the framework.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# To reviewer 4J8x\n\nThanks for your advices. We address your concerns as follows.\n\n**weakness-1**: We provide the flops of various components of the proposed idempotent framework (for a $256 \\times 256 \\times 3$ input) as follows.\n\n| components | GFLOPs |\n| -------- | -------- |\n| blocked convolution     | 0.98     |\n| null-space enhancement  | 3.12     |\n| coupling enhancement    | 3.19     |\n| right-invertible GDN    | 0.24     |\n| hyperprior and others   | 0.87     |\n| *overall*               | 8.40     |\n\n\n**weakness-2**: To further improve the RD performance, we can first investigate the surjective mapping restriction. We currently concat multiple surjective mappings to form a big and complex encoding transform, in order to make this encoding transform right-invertible as a whole. However, this 'concat of surjective mappings' is sufficient but not necessary, and damages the expressiveness. It is possible to ensure the right-invertibility of encoding transform with other options, for example using multi-branch structures.\n\nAdditionally, the building blocks such as GDN can be improved, for example changed to residual blocks. We use GDN here only to conduct a fair comparison against baseline Balle2018. We test replacing GDN with the more recent residual blocks and see similar improvement as reported in prior works, as is shown in **[rebuttal fig.4]**.\n\n**weakness-3 & question-4 & limitation-2**: We do not make this assumption.\n\n**weakness-4**: in Fig.3, we compare with the non-idempotent traditional codecs {JPEG2000, BPG444, VTM444} as well as learned codecs {Balle2017, Balle2018, Cheng2020}. We will make this more clear. \n\n**weakness-5**: We provide the BD-rate and BD-PSNR of various components of the framework, including null-space enhancement, as follows. \n\n\n| setting | BD-rate ($\\downarrow$) | BD-PSNR ($\\uparrow$) |\n| -------- | -------- | -------- |\n| proposed    |  0   %     |  0        |\n| w. GDN      |  0.24%     | -0.01     |\n| w. int mean |  4.11%     | -0.20     |\n| w.o. c-en   | 16.48%     | -0.75     |\n| w.o. NE     | 19.68%     | -0.91     |\n| inv.        | 56.03%     | -2.31     |\n| w. conv1x1  | 60.65%     | -2.51     |\n\n\nIt is clear that these components are crucial to the proposed framework.\n\n**question-1**: To discuss this problem, consider a 2-dimension convolution with kernel size $K \\times K$, stride $S \\times S$, input spatial size $H \\times W$, input channel $C_i$ and output channel $C_o$. Assuming the in-place parallel matrix multiplication[1] is used. For serial method, as is described in Line 104-109, we first substract the influence of the already-solved pixels, which takes $O(C_iK^2)$ time. Then we solve for the rest pixels, which takes $O(C_o)$ time. This substract-then-solve procedure needs to be done $HW/S^2$ times, so the overall complexity is $O(\\frac{HW}{S^2}(C_iK^2+C_o))$. For parallel method implemented with the proposed blocked rearrangement, we can solve for all pixels with $O(C_o)$ time complexity. We can see that, compared with the parallel method, time complexity of serial method is forbiddenly higher and not viable for practical usages.\nIn terms of re-compression performance, both serial method and parallel method are right-inverse, so idempotence can be achieved for both.\nIn terms of RD performance, the serial method could be better because it does not suffer from block artifact. However, this issue has been addressed by the proposed coupling enhancement.\n\n**question-2**: The proposed idempotent frameworks is implemented based on the existing learned image compression framework Balle18[2], and the performance of the initial compression is not dropped excessively, as is shown in Fig.3 (a).\n\n**question-3**: To our best knowledge, surjective encoding transform is the only way to make encoding transform right-invertible, and this right-invertibility is the key to make the coding process idempotent. \n\nRelaxation of this surjection constraint while keeping right-invertibility would make a promising imporvement over this work.\n\n**limitation-1**: The latents can be made non-integer. For example, we can add {0.1, 0.2, ..., 0.9} as quantization level. In most LIC works the quantized latent is integer (e.g. Balle18[2]).\n\n[1] Randall, Keith H. (1998). Cilk: Efficient Multithreaded Computing (PDF) (Ph.D.). Massachusetts Institute of Technology. pp. 54–57\n[2] Ballé, Johannes, et al. \"Variational image compression with a scale hyperprior.\" International Conference on Learning Representations. 2018."}, {"review_id": "H0T7i8wYve", "reviewer": "Reviewer_fD4t", "summary": "The paper shows how to achieve a truly idempotent image compression method, where f(x) = f(f(x)). The paper shows that it's sufficient to have E(D(y)) == y. This only requires a surjective E.", "questions": "-", "limitations": "Only applied to old architectures from 2018 which contain 4 conv layers and GDN.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Interesting derivation of the required conditions for idempotence. Also nice to see this problem studied.", "weaknesses": "- Old baselines: I think GDN is barely used in SOTA image codecs, where it's all ReLU or Leaky ReLU. It would have been interesting to see this method applied to eg. ELIC from 2022 vs. Balle's 2018 method.\n- The linear algebra presentation was hard to follow (p4). Some more intuitive insights like in the introduction would have been useful.\n\n\nMinor: Typo in section 3 header (\"Invertibie\") ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# To reviewer fD4t\n\nThanks for your advices. We address your concerns as follows.\n\n**weakness-1 & limitation**: We test replacing GDN with residual blocks (as suggested by ELIC[1]), and report as follows (also shown in **[rebuttal fig.4]**):\n\n| framework | BD-rate (RB $\\times$ 1 v.s. GDN) | BD-rate (RB $\\times$ 3 v.s. GDN) |\n| -------- | -------- | -------- |\n| [idemp] proposed  | -2.61     | -9.28     |\n| Balle2018         | -2.35     | -10.32    |\n| Minnen2018        | -1.36     | -8.97     |\n\nThe results of Balle2018 and Minnen2018 are from Tab.4 in  [1], e.g. for Balle2018 RB  $\\times$ 1 v.s. GDN the BD-rate is $[(100 + 5.68) / (100 + 8.23) - 1] \\times 100  = -2.35$.\n\nIt is clear that, replacing GDN with the more recent residual blocks would also improve our framework to the same degree. Thus our propsed framework is compatible with the recent advances in LIC.\n\n**weakness-2**: Thanks for your kind advice. We will make these parts more clearly presented.\nSpecifically, we will first describe what does right-invertible linear operations look like, then we explain why null-space decomposition preserses the right-invertibility, and finally we introduce how we conduct null-space enhancement.\n\n[1] He, Dailan, et al. \"Elic: Efficient learned image compression with unevenly grouped space-channel contextual adaptive coding.\" CVPR, 2022."}]

Author rebuttal:
To all reviewers:

please kindly reach to the pdf file below for **[rebuttal fig.x]**.

Meta-review: This paper presents a novel method for idempotent image compression. It first shows that right-invertibility instead of invertibility is needed for idempotent compression. It then proposed a null space decomposition method to construct idempotent image compression network. The paper received four reviews, all of which are positive. 

The paper is well written. The idea is novel and the experimental results are also convincing. The rebuttal addressed almost all questions raised by the reviewers. Please incorporate the technical details, such as the comparison with non-idemoptent  compression methods, issues with floating-point computational accuracy, etc. into the final draft.  

Based on these points above, the AC made the decision to accept the paper.
Decision: Accept (poster)