Rethinking Lossy Compression: The Rate-Distortion-Perception Tradeoff

Introduction

Lossy compression techniques are ubiquitous in the modern-day digital world, and are regularly used for communicating and storing images, video and audio. In recent years, lossy compression is seeing a surge of research, due in part to the advancements in deep learning and their application in this domain (Toderici et al., 2016, 2017; Ballé et al., 2016, 2017, 2018; Agustsson et al., 2017, 2018; Rippel & Bourdev, 2017; Minnen et al., 2018; Li et al., 2018; Mentzer et al., 2018; Johnston et al., 2018; Galteri et al., 2017; Tschannen et al., 2018; Santurkar et al., 2018; Rott Shaham & Michaeli, 2018). The theoretical foundations of lossy compression are rooted in Shannon’s seminal work on rate-distortion theory (Shannon, 1959), which analyzes the fundamental tradeoff between the bit rate used for representing data, and the distortion incurred when reconstructing the data from its compressed representation (Cover & Thomas, 2012).

The premise in rate-distortion theory is that reduced distortion is a desired property. However, recent works demonstrate that minimizing distortion alone does not necessarily drive the decoded signals to have good perceptual quality. For example, incorporating generative adversarial type losses has been shown to lead to significantly better perceptual quality, but at the cost of increased distortion (Tschannen et al., 2018; Agustsson et al., 2018; Santurkar et al., 2018). This behavior has also been studied in the context of signal restoration (Blau & Michaeli, 2018), where it was shown that minimizing distortion causes the distribution of restored signals to deviate from that of the ground-truth signals (indicating worse perceptual quality). In light of this understanding, it is natural to seek for a generalized rate-distortion theory, which also accounts for perception. In particular, it is of key importance to understand how the best achievable rate depends not only on the distortion, but also on the perceptual quality of the algorithm. A preliminary attempt to incorporate perceptual quality into rate-distortion theory was briefly reported in (Matsumoto, 2018a, b). Yet, no theoretical characterization nor practical demonstration of its effect on the rate-distortion tradeoff was presented.

In this paper, we adopt the mathematical definition of perceptual quality used in (Blau & Michaeli, 2018), and prove that there is a triple tradeoff between rate, distortion and perception. Our key observation is that the rate-distortion function elevates as the perceptual quality is enforced to be higher (see Fig. 1). In other words, to obtain good perceptual quality, it is necessary to make a sacrifice in either the distortion or the rate of the algorithm.

Our analysis is based on the definition of a rate-distortion-perception function $R(D,P)$, which characterizes the minimal achievable rate $R$ for any given distortion $D$ and perception index $P$. We begin by deriving a closed form for this function in the classical case study of a Bernoulli source, a simple example which nonetheless nicely illustrates the typical behavior of the tradeoff. We then prove several general properties of $R(D,P)$, showing that it is monotone and convex for any full-reference distortion measure (under minor assumptions), and that there is a range of $P$ values for which it necessarily does not coincide with the traditional rate-distortion function. For the specific case of the squared-error distortion, we also provide an upper bound on the increase in distortion that has to be incurred in order to achieve perfect perceptual quality, at any given rate.

Our observations have important implications for the design and evaluation of practical compression methods. In particular, they suggest that comparing between algorithms only in terms of their rate-distortion curves can be misleading. We demonstrate this in the context of image compression using a toy MNIST example, by systematically exploring the visual effect of improvement in each of the three properties (rate, distortion, perception) on the expense of the others. We do this by training an encoder-decoder net utilizing a generative model, similarly to (Tschannen et al., 2018; Agustsson et al., 2018). As we show, the phenomena we discuss are dominant at low bit rates, where the classical approach of optimizing distortion alone leads to unacceptable perceptual quality. This is perhaps not surprising when using the MSE distortion, which is known to be inconsistent with human perception. But our theory shows that every distortion measure (excluding pathological cases) must have a tradeoff with perceptual quality. This includes e.g., the popular SSIM/MS-SSIM (Wang et al., 2003, 2004), the $L_{2}$ distance between deep features (Johnson et al., 2016), and any other full reference criterion. To illustrate this, we repeat our toy experiment with the distortion measure of (Johnson et al., 2016), which has been used as a means for enhancing perceptual quality in low-level vision tasks (Ledig et al., 2017). As we show, minimizing this distortion does not lead to good perceptual quality at low bit rates, just like our theory predicts. Moreover, when enforcing high perceptual quality, this distortion rather increases.

Background

Rate-distortion theory analyzes the fundamental tradeoff between the rate (bits per sample) used for representing samples from a data source $X\sim p_{X}$, and the expected distortion incurred in decoding those samples from their compressed representations. Formally, the relation between the input $X$ and output $\hat{X}$ of an encoder-decoder pair, is a (possibly stochastic) mapping defined by some conditional distribution $p_{\hat{X}|X}$, as visualized in Fig. 2. The expected distortion of the decoded signals is thus defined as

A key result in rate-distortion theory states that for an iid source $X$, if the expected distortion is bounded by $D$, then the lowest achievable rate $R$ is characterized by the (information) rate-distortion function

where $I$ denotes mutual information (Cover & Thomas, 2012). Closed form expressions for the rate-distortion function $R(D)$ are known for only a few source distributions and under quite simple distortion measures (e.g., squared error or Hamming distance). However several general properties of this function are known, including that it is always monotonically non-increasing and convex.

2 Perceptual Quality

The perceptual quality of an output sample $\hat{x}$ refers to the extent to which it is perceived by humans as a valid (natural) sample, regardless of its similarity to the input $x$. In various domains, perceptual quality has been associated with the deviation of the distribution $p_{\hat{X}}$ of output signals from the distribution $p_{X}$ of natural signals, which, as discussed in (Blau & Michaeli, 2018), is linked to the common practice of quantifying perceptual quality via real-vs.-fake user studies (Isola et al., 2017; Salimans et al., 2016; Zhang et al., 2016; Denton et al., 2015). In particular, deviation from natural scene statistics is the basis for many no-reference image quality measures (Mittal et al., 2013, 2012; Wang & Simoncelli, 2005), which have been shown to correlate well with human opinion scores. It is also the principle underlying GAN-based image restoration schemes, which achieve enhanced perceptual quality by directly minimizing some divergence $d(p_{X},p_{\hat{X}})$ (Ledig et al., 2017; Pathak et al., 2016; Isola et al., 2017; Wang et al., 2018). Based on these works, and following (Blau & Michaeli, 2018), we define the perceptual quality index (lower is better) of an algorithm as

where $d(\cdot,\cdot)$ is some divergence between distributionsWe assume that $d(p,q)\geq 0,d(p,q)=0\Leftrightarrow p=q$. (e.g., Kulback-Leibler, Wasserstein, etc.). Note that the divergence function $d(\cdot,\cdot)$ which best relates to human perception is a subject of ongoing research. Yet, our results below hold for (nearly) any divergence.

Obviously, perceptual quality, as defined above, is very different from distortion. In particular, minimizing the perceptual quality index does not necessarily lead to low distortion. For example, if the decoder disregards the input, and outputs random samples from the source distribution $p_{X}$, it will achieve perfect perceptual quality but very poor distortion. It turns out that this is true also in the other direction. That is, minimizing distortion does not necessarily lead to good perceptual quality. This observation has been studied in (Blau & Michaeli, 2018) in the specific context of signal restoration (e.g. denoising, super-resolution). In particular, perception and distortion are fundamentally at odds with each other (for non-invertible degradations), in the sense that optimizing one always comes on the expense of the other. This behavior, coined the perception-distortion tradeoff, was shown to hold true for any distortion measure.

The Rate-Distortion-Perception Tradeoff

Since both perceptual quality and distortion are typically important, here we extend the rate-distortion function (2) to take into account the perception indexSimilarly to (2), $R(D,P)$ in (1) lower bounds the best achievable rate for an iid source (see Supplementary Material). We do not prove achievability of $R(D,P)$ in general. However for the MSE distortion, we show an achievable upper bound (see Theorem 2). (3).

The (information) rate-distortion-perception function is defined as

Unfortunately, closed form solutions for (1) are even harder to obtain than for (2). Yet, one notable exception is the classical case study of a binary source, as we show next. While of limited applicability, this example illustrates the typical behavior of (1), which we analyze in Sec. 3.2.

Consider the problem of encoding a binary source $X\sim\text{Bern}(p)$, where the decoder’s output $\hat{X}$ is also constrained to be binary. Let us take the distortion measure $\Delta(\cdot,\cdot)$ to be the Hamming distance, and the perception indexThe term “perception” is somewhat inappropriate for a Bernoulli source, as it is not perceived by humans (contrary to images, audio). Yet, we keep this terminology here for consistency. to be the total-variation (TV) distance $d_{\text{TV}}(\cdot,\cdot)$. Without loss of generality, we assume that $p\leq\tfrac{1}{2}$. When perception is not constrained (i.e., $P=\infty$), the solution to (1) reduces to the rate-distortion function (2) of a binary source, which is known to be given by

where $H_{b}(\alpha)$ is the entropy of a Bernoulli random variable with probability $\alpha$ (Cover & Thomas, 2012).

In the Supplementary Material, we derive the solution for arbitrary $P$. It turns out that as long as the perceptual quality constraint is sufficiently loose, the solution remains the same. However, when $P\leq p$, the perception constraint in (1) becomes active whenever the distortion constraint is loose enough, from which point the function $R(\cdot,P)$ departs from $R(\cdot,\infty)$. Specifically, for $P\leq p$, we have

where $q=1-p$ and $H_{t}(\alpha,\beta)$ denotes the entropy of a ternary random variable with probabilities $\alpha$, $\beta$, $1-\alpha-\beta$. Here, $\mathcal{S}_{1}=[0,D_{1})$, $\mathcal{S}_{2}=[D_{1},D_{2})$, and $\mathcal{S}_{3}=[D_{2},\infty)$, where $D_{1}=\tfrac{P}{1-2(p-P)}$ and $D_{2}=2pq-(q-p)P$.

Figure 3 plots $R(D,P)$ as a function of $D$ for several values of $P$. As can be seen, at $D=0$, all the curves merge. This is because at this point $\hat{X}=X$ (lossless compression), so that $p_{\hat{X}}=p_{X}$, and thus the perceptual quality is perfect. Yet, as the allowed distortion $D$ grows larger, the curves depart. This illustrates that achieving the classical rate-distortion curve (black dashed line) does not generally lead to good perceptual quality. The more stringent our prescribed perceptual quality constraint (lower $P$), the more the rate-distortion curve elevates (colored curves). In particular, the tradeoff becomes severe at the low bit rate regime, where good perceptual quality comes at the cost of a significantly higher distortion and/or bit rate. Notice that it is possible to achieve perfect perceptual quality at every rate (blue curve) by compromising the distortion to some extent. In Sec. 3.2 we provide an upper-bound on the increase in distortion required for obtaining perfect perceptual quality.

While Fig. 3 displays cross-sections of $R(D,P)$ along rate-distortion planes, in Fig. 4 we plot $R(D,P)$ as a surface in 3 dimensions, as well as its cross-sections along the other planes. The equi-rate level sets shown on the surface in Fig. 4, provide another visualization for the phenomenon described above. That is, at high bit-rates, it is possible to achieve good perceptual quality (low $P$) without a significant sacrifice in the distortion $D$. However, as the bit-rate becomes lower, the equi-rate level sets substantially curve towards the low $P$ values, illuminating the exacerbation in the tradeoff between distortion and perception in this regime. Figure 4 provides an additional viewpoint, by showing perception-distortion curves for different bit rates. Notice again that the tradeoff between distortion and perceptual quality becomes stronger at low bit-rates. Finally, Fig. 4 shows the somewhat counter-intuitive tradeoff between rate and perceptual quality as a function of distortion. Specifically, we see that at every constant distortion level, the perceptual quality can be improved by increasing the rate.

2 Theoretical Properties

For general source distributions, it is usually impossible to solve (1) analytically. However, it turns out that the behavior we saw for a Bernoulli source is quite typical. We next prove several general properties of the function (1), which hold under rather mild assumptions. Specifically, we assume:

A1 The divergence $d(\cdot,\cdot)$ in (1) is convex in its second argument. That is, for any $\lambda\in$ and for any three distributions $p_{0},q_{1},q_{2}$,

Assumption A1 is not very limiting. For instance, any $f$-divergence (e.g. KL, TV, Hellinger, $\mathcal{X}^{2}$) as well as the Renyi divergence, satisfies this assumption (Csiszár et al., 2004; Van Erven & Harremos, 2014). Assumption A2 holds in any setting where the mean distance between a “valid” signal $z$ and all other “valid” signals is not constantA valid signal is any $x:p_{X}(x)>0$. Also, we use “distance” here for clarity, although $\Delta(\cdot,\cdot)$ is not necessarily a metric.. In particular, it holds for any distortion function $\Delta(\cdot,\cdot)$ with a unique minimizer, such as the squared-error distortion and the SSIM index (under some assumptions) (Brunet, 2012). Using these assumptions, we are able to qualitatively characterize the general shape of the function $R(D,P)$.

The rate-distortion-perception function (1):

is monotonically non-increasing in $D$ and $P$;

satisfies $R(\cdot,0)\neq R(\cdot,\infty)$ if A2 holds.

The proof of Theorem 1 can be found in the Supplementary Material. Note that when assumption A2 holds, properties 1 and 3 indicate that there exists some $D_{0}$ for which $R(D_{0},0)>R(D_{0},\infty)$, showing that the rate-distortion curve necessarily elevates when constraining for perfect perceptual quality. In any case, assumption A2 is a sufficient condition for property 3, so that even if it does not hold, this does not necessarily imply that $R(\cdot,0)=R(\cdot,\infty)$.

How much does the rate-distortion curve elevate when constraining for perfect perceptual quality? The next theorem upper-bounds this elevation for the MSE distortion (see proof in the Supplementary Material).

When using the squared-error distortion, the function $R(\cdot,0)$ (rate-distortion at perfect perceptual quality) is bounded by

Theorem 2 shows that it is possible to attain perfect perceptual quality without increasing the rate, by sacrificing no more than a $2$-fold increase in the mean squared-error (MSE). More specifically, attaining perfect perceptual quality at distortion $D$ does not require a higher bit rate than that necessary for compression at distortion $\frac{1}{2}D$ with no perceptual quality constraint. This is illustrated in Fig. 5, where the perfect-quality curve $R(\cdot,0)$ shown in blue is bounded by the scaled version of Shannon’s unconstrained quality curve $R(\cdot,\infty)$ shown as a black dashed line. In image restoration scenarios, such a $2$-fold increase in the MSE ($3$dB decrease in PSNR) has been shown to enable a substantial improvement in perceptual quality by practical algorithms (Blau et al., 2018; Ledig et al., 2017). Note that this bound is generally not tight. Thus, in some settings, perfect perceptual quality can be obtained with an even smaller increase in distortion.

Experimental Illustration

We now turn to demonstrate the visual implications of the rate-distortion-perception tradeoff in lossy image compression on a toy MNIST example. We make no attempt to propose a new state-of-the-art compression method. Our sole goal is to systematically explore the effect of the balance between rate, distortion, and perception. To this end, we utilize a net-based encoder-decoder pair trained in an end-to-end fashion, similarly to recent works. By tuning the influence of each of the different terms of the loss, we can easily control the balance between these three quantities.

More concretely, we use an encoder $f$ and a decoder $g$, both parametrized by deep neural nets (DNNs). The encoder maps the input $x$ into a latent feature vector $f(x)$, whose entries are then uniformly quantized to $L$ levels to obtain the representation $\hat{f}(x)$. The decoder outputs a reconstruction $\hat{x}=g(\hat{f}(x))$. To enable back-propagation through the quantizer, we use the differentiable relaxation of (Mentzer et al., 2018). Note that this relaxation affects only the gradient computation through the quantizer during back-propagation, but not the forward-pass “hard” quantization.

As in recent perceptual-quality driven lossy compression schemes (Tschannen et al., 2018; Agustsson et al., 2018), the rate is controlled by the dimension $dim$ of the encoder’s output $f(x)$, and the number of levels $L$ used for quantizing each of its entries, such that $R\leq dim\times\log_{2}(L)$. Note that this only upper-bounds the best achievable rate, as lossless compression of $\hat{f}(x)$ would potentially further reduce the representation’s size. However, it significantly simplifies the scheme, and was found to be only slightly sub-optimal (Agustsson et al., 2018).

For any fixed rate, we train the encoder-decoder to minimize a loss comprising a weighted combination of the expected distortion and the perception index,

where in our specific case of a Wasserstein GAN (Arjovsky et al., 2017), $\mathcal{F}$ denotes the class of bounded $1$-Lipschitz functions. As usual, all expectations are replaced by sample means, the constraint $h\in\mathcal{F}$ is replaced by a gradient penalty (Gulrajani et al., 2017), and the loss is minimized by alternating between minimization w.r.t. $f,g$ while holding $h$ fixed and maximization w.r.t. $h$ while holding $f,g$ fixed.

To achieve good perceptual quality, especially at low rates, it is essential that the decoder be stochastic (Tschannen et al., 2018). This is commonly carried out by an additional random noise input. Yet, deep generative models in the conditional setting tend to ignore this type of stochasticity (Zhu et al., 2017a, b; Mathieu et al., 2016). Tschannen et al. (2018) remedy this by applying a two-stage training scheme, which indeed promotes the use of stochasticity within the decoder, but can lead to sub-optimal results. Here, instead of concatenating a noise vector $n$ to the encoder’s output $\hat{f}(x)$, we add it, so that the decoder in fact operators on the noisy representation $\hat{f}(x)+n$. This does not lead to loss of information, as the noise $n$ is drawn from a uniform distribution $U(-\tfrac{\alpha}{2},\tfrac{\alpha}{2})$, with $\alpha$ smaller than the quantization bin size. Thus, different coded representations $\hat{f}(x)$ do not “mix-up”, and can always be distinguished from one another. This scheme urges the decoder to utilize the stochastic input, while allowing end-to-end training in a one-step manner.

We begin by experimenting with the squared-error distortion $\Delta(x,\hat{x})=\|x-\hat{x}\|^{2}$. We train 98 encoder-decoder pairs on the MNIST handwritten digit dataset (LeCun et al., 1998), while varying the encoder’s output dimension $dim$ and number of quantization levels $L$ to control the rate $R$, and the tuning coefficient $\lambda$ to achieve different balances between distortion and perceptual quality. A list of all combinations of $(dim,L,\lambda)$ used, along with all other training details can be found in the Supplementary Material.

The left side of Fig. 6 plots the 98 trained encoder-decoder pairs on the rate-distortion plane, with the perceptual quality indicated by color coding and rate measured in bits per digit. The perceptual quality is quantified by the final discriminator loss$\mathcal{L}_{\text{dis}}=\tfrac{2}{N}\left(\sum_{i=1}^{N/2}h(x_{i})-\sum_{i=N/2+1}^{N}h(g(\hat{f}(x_{i})))\right)$, where $\{x_{i}\}_{i=1}^{N}$ are the test samples., which approximates the Wasserstein distance $d_{\text{W}}(p_{X},p_{\hat{X}})$. We plot an approximation of Shannon’s rate-distortion function (obtained with $\lambda=0$), and two additional rate-distortion curves with (approximately) constant perceptual qualityWe plot a smoothing spline calculated over the set of points which satisfy the constraint $d_{\text{W}}(p_{X},p_{\hat{X}})\leq P$ and have the minimal distortion among all points with the same rate.. As can be seen, the rate-distortion curve elevates when constraining the perceptual quality to be good. This demonstrates once again that we can improve the perceptual quality w.r.t. that obtained on Shannon’s rate-distortion curve, yet this must come at the cost of a higher rate and/or distortion. Notice that the perception index is not constant along Shannon’s function; it increases (worse quality) towards lower bit-rates.

On the right side of Fig. 6, we depict the outputs of encoder-decoder pairs along Shannon’s rate-distortion function, and along the two equi-perception curves shown on the left. It can be seen that as the rate decreases, the perceptual quality of the reconstructions along Shannon’s function degrades. However, this is avoided when constraining the perceptual quality, which results in visually pleasing reconstructions even at extremely low bit-rates. Notice that this increased perceptual quality does not imply increased accuracy, as at low bit rates (e.g., $2$ bits), most reconstructions fail to preserve even the identity of the digit. Yet, while the encoder-decoder pairs on Shannon’s rate-distortion curve are more accurate on average, no doubt that the perceptually-constrained encoder-decoder pairs are favorable in terms of perceptual quality. Also, notice that at a rate of $2$ bits, the outputs of the perceptually-constrained encoder-decoder pairs are all distinct, even though there are only $4$ code words (as can be seen for Shannon’s encoder-decoder). This shows that the decoder effectively utilizes the noise.

Figure 7 depicts the function $R(D,P)$ in 3-dimensions, as well as its cross sections along the other axis aligned planes. In Fig. 7, the curved equi-rate lines show the tradeoff between distortion and perceptual quality. This is also apparent in Fig. 7, which shows cross sections along perception-distortion planes at different rates. As can be seen, the tradeoff becomes stronger at low bit-rates. Figure 7 shows the counter-intuitive tradeoff between rate and perception. That is, at constant distortion, the perceptual quality can be improved by increasing the rate.

2 Advanced Distortion Measures

The peak-signal-to-noise ratio (PSNR), which is a rescaling of the MSE, is still the most common quality measure in image compression. Yet, it is well-known to be inadequate for quantifying distortion as perceived by humans (Wang & Bovik, 2009). Over the past decades, there has been a constant search for better distortion criteria, ranging from the simple SSIM/MS-SSIM (Wang et al., 2003, 2004) to the recently popular deep-feature based distortion (Johnson et al., 2016; Zhang et al., 2018). Interestingly, the perceptual quality along Shannon’s classical rate-distortion function is not perfect for nearly any distortion measure (see property 3 in Theorem 1). This implies that perfect perceptual quality cannot be achieved by merely switching to more advanced distortion criteria, but rather requires directly optimizing the perception index (e.g. using GAN-based schemes). This is not to say that the function $R(D,P)$ is the same for all distortion measures. The strength of the tradeoff can certainly decrease for distortion criteria which capture more semantic similarities (Blau & Michaeli, 2018).

We demonstrate this by repeating the experiment of Sec. 4.1, while replacing the squared-error distortion by the deep-feature based distortion of (Ledig et al., 2017), i.e.,

where $\Psi(x)$ is the output of an intermediate DNN layer for input $x$. Here we take the second conv-layer output of a $4$-layer DNN, which we pre-trained to achieve over $99\%$ classification accuracy on the MNIST test set. All training details appear in the Supplementary Material.

Figure 8 plots 98 encoder-decoder pairs on the rate-distortion plane, trained exactly as in Fig. 6, but this time with the loss (11) instead of MSE. As can be seen, here too the rate-distortion curves elevate when constraining the perceptual quality, demonstrating that the use of advanced distortion measures does not eliminate the tradeoff. From the decoded outputs, however, it is evident that the tradeoff here is somewhat weaker, as minimizing distortion alone (Shannon’s) appears a bit more visually pleasing compared to Fig. 6 (though still with reduced variability and more blur than the perception constrained reconstruction).

3 Related Work

Our theoretical analysis and experimental validation help explain some of the observations reported in the recent literature. Specifically, a lot of research efforts have been devoted to optimizing the rate-distortion function (2) using deep nets (Toderici et al., 2016, 2017; Agustsson et al., 2017; Ballé et al., 2017; Minnen et al., 2018; Li et al., 2018). Some papers explicitly targeted high perceptual quality. One line of works did so by choosing the distortion criterion to be some advanced full-reference measure, like SSIM/MS-SSIM (Ballé et al., 2018; Mentzer et al., 2018; Johnston et al., 2018), normalized Laplacian pyramid (Ballé et al., 2016) and deformation-aware sum of squared differences (DASSD) (Rott Shaham & Michaeli, 2018). While beneficial, these methods could not demonstrate high perceptual quality at very low bit rates, which aligns with our theory. Another line of works incorporated generative models, which explicitly encourage the distribution of outputs to be similar to that of natural images (decreasing the divergence in (3)). This was done on an image patch level (Rippel & Bourdev, 2017), on reduced-size (thumbnail) images (Tschannen et al., 2018; Santurkar et al., 2018), on a full-image scale (Agustsson et al., 2018), and as a post-processing step (Galteri et al., 2017). In particular, Tschannen et al. (2018) propose a practical method for distribution-preserving compression ($P=0$ in our terminology). These methods managed to obtain impressive perceptual quality at very low bit rates, but not without a substantial sacrifice in distortion, as predicted by our theory. Finally, we note that rate-distortion analysis (with a specific distortion) has also been used in the context of generative models (Alemi et al., 2018), which target $p_{\hat{X}}=p_{X}$ (i.e., $P=0$). Our results hold for arbitrary distortions and arbitrary $P$.

Conclusion

We proved that in lossy compression, perceptual quality is at odds with rate and distortion. Specifically, any attempt to keep the statistics of decoded signals similar to that of source signals, will result in a higher distortion or rate. We characterized the triple tradeoff between rate, distortion and perception, and empirically illustrated its manifestation in image compression. Our observations suggest that comparing methods based on their rate-distortion curves alone may be misleading. A more informative evaluation must also include some (no-reference) perceptual quality measure.

Acknowledgements

This research was supported in part by the Israel Science Foundation (grant no. 852/17) and by the Ollendorf Foundation.

References

Appendix A Proof of Theorem 1

The proof of this theorem follows closely that of its rate-distortion analogue (Cover & Thomas (2012), 2nd ed., p. 316).

The value $R(P,D)$ is the minimal mutual information $I(X,\hat{X})$ over a constraint set whose size increases with $D$ and $P$. This implies that the function $R(D,P)$ is non-increasing in $D$ and $P$.

Convexity

Here, we assume that A1 holds. That is, the divergence $d(p,q)$ in (1) is convex in its second argument, so that for any $\lambda\in$,

To prove the convexity of $R(D,P)$, we will show that

for all $\lambda\in$. First, by definition, the left hand side of (13) can be written as

where $\hat{X}_{1}$ and $\hat{X}_{2}$ are defined by

Since $I(X,\hat{X})$ is convex in $p_{\hat{X}|X}$ for a fixed $p_{X}$ (Cover & Thomas (2012), 2nd ed., p. 33),

because $\hat{X}_{\lambda}$ is in the constraint set. The divergence $d(p,q)$ is assumed to be convex in the second argument, thus

where (a) and (c) are according to the law of total expectation, and (b) is by (18). Therefore, since $R(D,P)$ is non-increasing in $D$ and $P$, we have from (A) and (A) that

Combining (14), (17), (19) and (22) proves (13), thus proving that $R(D,P)$ is convex.

Dependence on the perceptual quality

Notice that since $I(X,\hat{X})=0$ in this case, $X$ and $\hat{X}$ are independent, so that $p_{\hat{X}|X}=p_{\hat{X}}$. Therefore

Clearly, the $p_{\hat{X}}$ which minimizes (A) cannot assign positive probability outside the set where $k(z)$ attains its minimal value. Namely, the support of $p_{\hat{X}}$ must be contained in the set $S$ defined by

But since our encoder-decoder pair achieves perfect perceptual quality, i.e. $p_{\hat{X}}=p_{X}$, this implies that $\text{support}\{p_{X}\}\subset S$, contradicting Assumption A2.

Appendix B Proof of Theorem 2

Appendix C Perception aware lossy compression of a memoryless stationary source

We now prove that when compressing a memoryless stationary source with average distortion $D$ and average perception index $P$, the rate is lower bounded by $R(D,P)$. This proof follows closely that of its rate-distortion analogue (Cover & Thomas (2012), 2nd ed., p. 316).

Assume a memoryless stationary source. Given a source sequence $X^{n}$ comprising i.i.d. variables $X_{1},\ldots,X_{n}$ with distribution $p_{X}$, the encoder $f_{n}$ constructs an encoded representation with rate $R$ as $f_{n}:\mathcal{X}^{n}\rightarrow\{1,2,\ldots,2^{nR}\}$. The decoder $g_{n}$ outputs an estimate $\hat{X}^{n}$ of $X^{n}$ as $g_{n}:\{1,2,\ldots,2^{nR}\}\rightarrow\hat{\mathcal{X}}^{n}$. We are interested in the the average distortion of the reconstructions, $\frac{1}{n}\sum_{i=1}^{n}\Delta(X_{i},\hat{X}_{i})$, and in their average perceptual quality, $\frac{1}{n}\sum_{i=1}^{n}d(p_{X_{i}},p_{\hat{X}_{i}})$. Assume that

where (a) is since the size of the range of $f_{n}$ is $2^{nR}$, (b) is since $H(f_{n}(X^{n})|X^{n})>0$, (c) is from the data-processing inequality, (d) is since $X_{i}$ are independent, (e) is from the chain rule of entropy, (f) is since conditioning reduces entropy, (g) is from the definition of $R(D,P)$ in (1), (h) is from the convexity of $R(D,P)$ (see Theorem 1) and Jensen’s inequality, and (i) is from (31) and the fact that $R(D,P)$ is non-increasing in $D,P$ (see Theorem 1). This proves that the rate of any encoder-decoder pair having average distortion $\frac{1}{n}\sum_{i=1}^{n}\Delta(X_{i},\hat{X}_{i})=D$ and average perceptual quality $\frac{1}{n}\sum_{i=1}^{n}d(p_{X_{i}},p_{\hat{X}_{i}})=P$, is lower-bounded by $R(D,P)$, the rate-distortion-perception function evaluated at $D,P$.

To prove that the rate-distortion-perception function describes the optimal rate at distortion level $D$ and perceptual quality $P$, we would also have to prove that $R(D,P)$ is achievable, which we leave for future work. Yet, the proof that $R(D,P)$ lower-bounds the rate is sufficient for concluding that a tradeoff between rate, distortion and perception necessarily exists. Specifically, in Theorem 1 we prove that (subject to assumptions) the rate-distortion curve elevates when constraining for perceptual quality, i.e. $R(\cdot,0)>R(\cdot,\infty)$. Now, Shannon’s rate-distortion curve $R(\cdot,\infty)$ is known to be achievable (Cover & Thomas (2012), 2nd ed., p. 318) and thus describes the optimal rate $R_{S}$ when not constraining the perceptual quality. As shown above, $R(\cdot,0)$ lower-bounds the rate $R_{P}$ when constraining for perfect perceptual quality. Combining these, we get that $R_{P}>R_{S}$, indicating that constraining for perceptual quality necessarily leads to an increase in rate (for constant distortion level), thus illustrating the rate-distortion-perception tradeoff.

Appendix D Derivation of the rate-distortion-perception function R​(D,P)𝑅𝐷𝑃R(D,P) of a Bernoulli source

Assume that $X\sim\text{Bern}(p)$ with $p\leq\tfrac{1}{2}$. We seek a conditional distribution $p_{\hat{X}|X}$, which we parameterize by $a,b$ as

that solves the rate-distortion-perception problem

Here we concentrate on the case where $\Delta(\cdot,\cdot)$ is the Hamming distance, and $d(\cdot,\cdot)$ is the total-variation (TV) divergence. The mutual information term $I(X,\hat{X})$ is given by

The function $R(D,\infty)$ for Shannon’s classic rate-distortion problem is given by (see (Cover & Thomas, 2012), 2nd ed., p. 308)

where $H_{b}$ denotes the binary entropy $H_{b}(z)=-z\log(z)-(1-z)\log(1-z)$. This optimal solution is obtained by setting the parameters $a,b$ to

Solution for finite P𝑃P and I​(X,X^)>0𝐼𝑋^𝑋0I(X,\hat{X})>0

Therefore, the constraint $d_{\text{TV}}(p_{X},p_{\hat{X}})\leq P$ is satisfied when

Below, we show that the lower constraint of (43) is never active (see J1). The upper constraint is obviously active only when $a_{S}(D)$ of (40) does not satisfy the upper bound in (43), which happens when

Therefore, when $D\leq D_{1}$ the solution is independent of $P$ and is given by (39). When $D>D_{1}$, the constraint $d_{\text{TV}}(p_{X},p_{\hat{X}})\leq P$ is active, the upper constraint of (43) is active, and thus

and by substituting into (41) we also get

Note that in (44) we assumed $D\leq\tfrac{1}{2}$, below we will justify that this is always the case in this region (see J2).

Now, substituting $a,b$ from (45), (46) back into (36) we get

where $q=1-p,\,\alpha=\tfrac{D-P}{2}$ and $\beta=\tfrac{D+P}{2}$. This can be further simplified to obtain

where $H_{t}(p_{1},p_{2})$ is the entropy of a ternary random variable (taking values in a three element alphabet) with probabilities $p_{1},p_{2},1-p_{1}-p_{2}$.

Solution for finite P𝑃P and I​(X,X^)=0𝐼𝑋^𝑋0I(X,\hat{X})=0

The function $R(D,P)$ is non-increasing in $D$ (see Theorem 1), and will reach $R(D,P)=0$ for $a=b$ since in this case $\hat{X}$ and $X$ are independent. From (45) and (46), this happens when

From this point onward, the solution is fixed, as mutual information $I(X,\hat{X})$ is non-negative and we cannot further decrease the objective of (35).

Overall solution

Putting all the pieces together, the overall solution for $P<p$ is

where $D_{1}$ and $D_{2}$ are defined in (44) and (49), respectively. For $P\geq p$, the solution is independent of $P$ and is given by the solution to Shannon’s classic rate-distortion curve for a Bernoulli source in (39) (see justification in J3 below).

Additional justifications

The solution $a_{S}(D)$ in (40) does not satisfy this lower constraint of (43) when

When $P<\frac{1-2p}{2}$ this happens for $D<\frac{P}{2p+2P-1}<0$, which never occurs as $D\in$. When $P\geq\frac{1-2p}{2}$ this happens for $D>\frac{P}{2p+2P-1}$. However, since $\frac{P}{2p+2P-1}>D_{1}=\frac{P}{1+2P-2p}$ for all $p\leq\frac{1}{2}$ (which is our assumption), the upper constraint of (43) will always become active before the lower constraint.

J2

Taking the derivative of $D_{2}=2p(1-p)+(2p-1)P$ with respect to $p$ we obtain

which is non-negative since $p\leq\tfrac{1}{2}$. Thus, $D_{2}$ is increasing in $p$ for all $P>0$, and its largest value in the range $p\in[0,\tfrac{1}{2}]$, which is $D_{2}=\tfrac{1}{2}$, is obtained at $p=\tfrac{1}{2}$. Thus, in the region where $D_{1}<D\leq D_{2}$, it is ensured that $D\leq\tfrac{1}{2}$.

J3

Taking the derivative of $D_{1}=\frac{P}{1+2P-2p}$ with respect to $P$ we obtain

which is non-negative for $p\leq\tfrac{1}{2}$, thus $D_{1}$ is non-decreasing in $P$. It is easy to see from (49) that $D_{2}$ in non-increasing in $P$ (for $p\leq\tfrac{1}{2}$). Thus, $D_{1}(P)=D_{2}(P)$ for a single $P$, which is $P=p$. For any $P\geq p$, there are no $D$ satisfying $D_{1}<D\leq D_{2}$.

Appendix E Architecture and training parameters for the experiments in Sec. 4

The architecture of the encoder, decoder and discriminator nets used for compressing (and decompressing) the MNIST images in Sec. 4 is detailed in Table 1. The optimization objective is given in (10), where $\Delta(x,\hat{x})$ is the squared-error distortion in Sec. 4.1, and a combination of the squared-error and the “perceptual loss” of Johnson et al. (2016) in Sec. 4.2. The encoder output dimension $dim$, the number of quantization levels $L$, and values of the tradeoff coefficient $\lambda$ in (10) used for training the $98$ encoder-decoder pairs appear in Table 2. The distortion term in (10) was also multiplied by a constant factor of $10^{-3}$ for the MSE term (in Sec. 4.1 and Sec. 4.2) and factor of $5\times 10^{-5}$ for the perceptual loss (in Sec. 4.2). For each $dim$ and $L$, an encodoer-decoder with $\lambda=0$ (only distortion, no adversarial loss) was trained for 25 epochs. The other encoder-decoder pairs with $\lambda>0$ continued training from this point for another 25 epochs. The ADAM optimizer was used with $\beta_{1}=0.5,\beta_{2}=0.9$. Batch size was $64$. Initial learning rates were $10^{-2}/2\times 10^{-4}$ for the encoder-decoder/discriminator updates in Sec. 4.1, and $5\times 10^{-3}/2\times 10^{-4}$ for the encoder-decoder/discriminator updates in Sec. 4.2. These learning rates decreased by $\tfrac{1}{5}$ after 20 epochs. The convolutional/transposed-convolutional layers filter size (in the decoder and discriminator) was always $5$, except for the last convolutional layer in the decoder where the filter size was $4$. No padding was used in the decoder, and a padding of $2$ was used in each convolutional layer of the discriminator.

The quantization layer (last encoder layer) follows Mentzer et al. (2018). Here, the bin centers $\mathcal{C}=\{c_{1},\ldots,c_{L}\}$ are fixed and evenly spaced in the interval $$. Denoting by$z_{i}$the output of the encoder unit$i$before quantization (after the Tanh activation), the encoder output$\hat{z}_{i}$in the forward pass is given by nearest-neighbor assignment, i.e.$\hat{z}_{i}=\arg\min_{c_{j}}\|z_{i}-c_{j}\|$. To compute the gradients in the backward pass, we use a differential “soft” assignment

where we use $\sigma=2/L$. Uniformly distributed noise $\mathcal{U}(-\tfrac{a}{2},\tfrac{a}{2})$ is added to the encoder output before it is passed on to the decoder, with $a=2/(L-1)$.

Appendix F The perceptual loss in the experiment in Sec. 4.2