The Perception-Distortion Tradeoff

Introduction

The last decades have seen continuous progress in image restoration algorithms (e.g. for denoising, deblurring, super-resolution) both in visual quality and in distortion measures like peak signal-to-noise ratio (PSNR) and structural similarity index (SSIM) . However, in recent years, it seems that the improvement in reconstruction accuracy is not always accompanied by an improvement in visual quality. In fact, and perhaps counter-intuitively, algorithms that are superior in terms of perceptual quality, are often inferior in terms of e.g. PSNR and SSIM . This phenomenon is commonly interpreted as a shortcoming of the existing distortion measures , which fuels a constant search for alternative “more perceptual” criteria.

In this paper, we offer a complementary explanation for the apparent tradeoff between perceptual quality and distortion measures. Specifically, we prove that there exists a region in the perception-distortion plane, which cannot be attained regardless of the algorithmic scheme (see Fig. 1). Furthermore, the boundary of this region is monotone. Therefore, in its proximity, it is only possible to improve either perceptual quality or distortion, one at the expense of the other. The perception-distortion tradeoff exists for all distortion measures, and is not only a problem of the mean-square error (MSE) or SSIM criteria.

Let us clarify the difference between distortion and perceptual quality. The goal in image restoration is to estimate an image $x$ from its degraded version $y$ (e.g. noisy, blurry, etc.). Distortion refers to the dissimilarity between the reconstructed image $\hat{x}$ and the original image $x$. Perceptual quality, on the other hand, refers only to the visual quality of $\hat{x}$, regardless of its similarity to $x$. Namely, it is the extent to which $\hat{x}$ looks like a valid natural image. An increasingly popular way of measuring perceptual quality is by using real-vs.-fake user studies, which examine the ability of human observers to tell whether $\hat{x}$ is real or the output of an algorithm (similarly to the idea underlying generative adversarial nets ). Therefore, perceptual quality can be defined as the best possible probability of success in such discrimination experiments, which as we show, is proportional to the distance between the distribution of reconstructed images and that of natural images.

Based on these definitions of perception and distortion, we follow the logic of rate-distortion theory . That is, we seek to characterize the behavior of the best attainable perceptual quality (minimal deviation from natural image statistics) as a function of the maximal allowable average distortion, for any estimator. This perception-distortion function (wide curve in Fig. 1) separates between the attainable and unattainable regions in the perception-distortion plane and thus describes the fundamental tradeoff between perception and distortion. Our analysis shows that algorithms cannot be simultaneously very accurate and produce images that fool observers to believe they are real, no matter what measure is used to quantify accuracy. This tradeoff implies that optimizing distortion measures can be not only ineffective, but also potentially damaging in terms of visual quality. This has been empirically observed e.g. in , but was never established theoretically.

From the standpoint of algorithm design, we show that generative adversarial nets (GANs) provide a principled way to approach the perception-distortion bound. This gives theoretical support to the growing empirical evidence of the advantages of GANs in image restoration .

The perception-distortion tradeoff has major implications on low-level vision. In certain applications, reconstruction accuracy is of key importance (e.g. medical imaging). In others, perceptual quality may be preferred. The impossibility of simultaneously achieving both goals calls for a new way for evaluating algorithms: By placing them on the perception-distortion plane. We use this new methodology to conduct an extensive comparison between recent super-resolution (SR) methods, revealing which SR methods lie closest to the perception-distortion bound.

Distortion and perceptual quality

Distortion and perceptual quality have been studied in many different contexts, and are sometimes referred to by different names. Let us briefly put past works in our context.

Given a distorted image $\hat{x}$ and a ground-truth reference image $x$, full-reference distortion measures quantify the quality of $\hat{x}$ by its discrepancy to $x$. These measures are often called full reference image quality criteria because of the reasoning that if $\hat{x}$ is similar to $x$ and $x$ is of high quality, then $\hat{x}$ is also of high quality. However, as we show in this paper, this logic is not always correct. We thus prefer to call these measures distortion or dissimilarity criteria.

2 Perceptual quality

The perceptual quality of an image $\hat{x}$ is the degree to which it looks like a natural image, and has nothing to do with its similarity to any reference image. In many image processing domains, perceptual quality has been associated with deviations from natural image statistics.

Perceptual quality is commonly evaluated empirically by the mean opinion score of human subjects . Recently, it has become increasingly popular to perform such studies through real vs. fake questionnaires . These test the ability of a human observer to distinguish whether an image is real or the output of some algorithm. The probability of success $p_{\text{success}}$ of the optimal decision rule in this hypothesis testing task is known to be (see Appendix A in the Supplementary Material)

where $d_{\text{TV}}(p_{X},p_{\hat{X}})$ is the total-variation (TV) distance between the distribution $p_{\hat{X}}$ of images produced by the algorithm in question, and the distribution $p_{X}$ of natural images . Note that $p_{\text{success}}$ decreases as the deviation between $p_{\hat{X}}$ and $p_{X}$ decreases, becoming $\tfrac{1}{2}$ (no better than a coin toss) when $p_{\hat{X}}=p_{X}$.

No-reference quality measures

Perceptual quality can also be measured by an algorithm. In particular, no-reference measures quantify the perceptual quality $Q(\hat{x})$ of an image $\hat{x}$ without depending on a reference image. These measures are commonly based on estimating deviations from natural image statistics. The works proposed perceptual quality indices based on the KL divergence between the distribution of the wavelet coefficients of $\hat{x}$ and that of natural scenes. This idea was further extended by the popular methods DIIVINE , BRISQUE , BLIINDS-II and NIQE , which quantify perceptual quality by various measures of deviation from natural image statistics in the spatial, wavelet and DCT domains.

GAN-based image restoration

Most recently, GAN-based methods have demonstrated unprecedented perceptual quality in super-resolution , inpainting , compression , deblurring and image-to-image translation . This was accomplished by utilizing an adversarial loss, which minimizes some distance $d(p_{X},p_{\hat{X}_{\text{GAN}}})$ between the distribution $p_{\hat{X}_{\text{GAN}}}$ of images produced by the generator and the distribution $p_{X}$ of images in the training dataset. A large variety of GAN schemes have been proposed, which minimize different distances between distributions. These include the Jensen-Shannon divergence , the Wasserstein distance , and any $f$-divergence .

Single image quality vs. image ensemble quality

Here $d_{\text{KL}}$ is the Kullback-Leibler divergence and $H$ denotes entropy. The second term in this decomposition discourages diversity. Choosing to drop it, results in the distributional-divergence based quality measures described above.

Problem formulation

In statistical terms, a natural image $x$ can be thought of as a realization from the distribution of natural images $p_{X}$. In image restoration, we observe a degraded version $y$ relating to $x$ via some conditional distribution $p_{Y|X}$. In this paper we focus on non-invertible settingsBy invertible we mean that the support of $p_{X|Y}(\cdot|y)$ is a singleton for almost all $y$’s (see Appendix C for a formal definition)., where $x$ cannot be estimated from $y$ with zero error. This is typically the case in denoising, deblurring, inpaitning, super-resolution, etc. Given $y$, an image restoration algorithm produces an estimate $\hat{x}$ according to some distribution $p_{\hat{X}|Y}$. Note that this description is quite general in that it does not restrict the estimator $\hat{x}$ to be a deterministic function of $y$. This problem setting is illustrated in Fig. 2.

Given a full-reference dissimilarity criterion $\Delta(x,\hat{x})$, the average distortion of an estimator $\hat{X}$ is given by

where the expectation is over the joint distribution $p_{X,\hat{X}}$. This definition aligns with the common practice of evaluating average performance over a database of degraded natural images. We assume that the dissimilarity criterion is such that $\Delta(x,\hat{x})\geq 0$ with equality when $\hat{x}=x$. Note that some distortion measures, e.g. SSIM, are actually similarity measures (higher is better), yet can always be inverted (and shifted) to become dissimilarity measures.

As discussed in Sec. 2.2, the perceptual quality of an estimator $\hat{X}$ (as quantified e.g. by real vs. fake human opinion studies) is directly related to the distance between the distribution of its reconstructed images, $p_{\hat{X}}$, and the distribution of natural images, $p_{X}$. We thus define the perceptual quality index (lower is better) of an estimator $\hat{X}$ as

where $d(p,q)$ is some divergence between distributions that satisfies $d(p,q)\geq 0$ with equality if $p=q$, e.g. the KL divergence, TV distance, Wasserstein distance, etc. It should be pointed out 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.

Notice that the best possible perceptual quality is obtained when the outputs of the algorithm follow the distribution of natural images (i.e. $p_{\hat{X}}=p_{X}$). In this situation, by looking at the reconstructed images, it is impossible to tell that they were generated by an algorithm. However, not every estimator with this property is necessarily accurate. Indeed, we could achieve perfect perceptual quality by randomly drawing natural images that have nothing to do with the original ground-truth images. In this case the distortion would be quite large.

Our goal is to characterize the tradeoff between (3) and (4). But let us first see why minimizing the average distortion (3), does not necessarily lead to a low perceptual quality index (4). We start by illustrating this with the square-error distortion $\Delta(x,\hat{x})=\|x-\hat{x}\|^{2}$ and the $0-1$ distortion $\Delta(x,\hat{x})=1-\delta_{x,\hat{x}}$ (where $\delta$ is Kronecker’s delta). We specifically illustrate that those measures are generally not distribution preserving in the following sense.

We say that a distortion measure $\Delta(\cdot,\cdot)$ is distribution preserving at $p_{X,Y}$ if the estimator $\hat{X}$ minimizing the mean distortion (3) satisfies $p_{\hat{X}}=p_{X}$.

More details about those examples are provided in Appendix B (Supplementary Material). We then proceed to discuss this phenomenon for arbitrary distortions in Sec. 3.3.

and $N\sim\mathcal{N}(0,1)$ is independent of $X$ (see Fig. 3). In this setting, the MMSE estimate is given by

Notice that $\hat{x}_{\text{MMSE}}$ can take any value in the range $(-1,1)$, whereas $x$ can only take the discrete values $\{-1,0,1\}$. Thus, clearly, $p_{\hat{X}_{\text{MMSE}}}$ is very different from $p_{X}$, as illustrated in Fig. 3. This demonstrates that minimizing the MSE distortion does not generally lead to $p_{\hat{X}}\approx p_{X}$.

The same intuition holds for images. The MMSE estimate is an average over all possible explanations to the measured data, weighted by their likelihoods. However the average of valid images is not necessarily a valid image, so that the MMSE estimate frequently “falls off” the natural image manifold . This leads to unnatural blurry reconstructions, as illustrated in Fig. 4. In this experiment, $x$ is a $280\times 280$ image comprising $100$ smaller $28\times 28$ digit images. Each digit is chosen uniformly at random from a dataset comprising $54$K images from the MNIST dataset and an additional $5.4$K blank images. The degraded image $y$ is a noisy version of $x$. As can be seen, the MMSE estimator produces blurry reconstructions, which do not follow the statistics of the (binary) images in the dataset.

2 The 0−1010-1 distortion

The discussion above may give the impression that unnatural estimates are mainly a problem of the square-error distortion, which causes averaging. One way to avoid averaging, is to minimize the binary $0-1$ loss, which restricts the estimator to choose $\hat{x}$ only from the set of values that $x$ can take. In fact, the minimum mean $0-1$ distortion is attained by the maximum-a-posteriori (MAP) rule, which is very popular in image restoration. However, as we exemplify next, the distribution of the MAP estimator also deviates from $p_{X}$. This behavior has also been studied in .

Consider again the setting of (5). In this case, the MAP estimate is given by

where $p(X=n|y)$ is as in (7). Now, it can be easily verified that when $\log(p_{1}/p_{0})>1/2$, we have $\hat{x}_{\text{MAP}}(y)=\text{sign}(y)$. Namely, the MAP estimator never predicts the value . Therefore, in this case, the distribution of the estimate is

which is obviously different from $p_{X}$ of (5) (see Fig. 3).

This effect can also be seen in the experiment of Fig. 4. Here, the MAP estimates become increasingly dominated by blank images as the noise level rises, and thus clearly deviates from the underlying prior distribution.

3 Arbitrary distortion measures

We saw that neither the square-error nor the $0-1$ loss are distribution preserving. That is, their minimization does not generally lead to $p_{\hat{X}}=p_{X}$ (i.e. perfect perceptual quality). However these two examples do not yet preclude the existence of a distribution preserving distortion measure. Does there exist a measure whose minimization is guaranteed to lead to $p_{\hat{X}}=p_{X}$? If we limit ourselves to one single setting, then the answer may be positive. For example, in the setting of Fig. 3, if $p_{0}$ of (5) equals , then the $0-1$ loss is distribution preserving as its minimization leads to an estimate satisfying $p_{\hat{X}}=p_{X}$. This illustrates that a distortion measure may be distribution preserving for certain underlying distributions $p_{X,Y}$ but not for others.

However, from a practical standpoint, we typically want our distortion measure to be adequate in more than one single setting. For example, if our goal is to train a neural network to perform denoising, then it is reasonable to expect that the same distortion measure be equally adequate as a loss function for different noise levels. In fact, we may also want to use the same distortion measure across different tasks (e.g. super-resolution, deblurring, inpainting). The interesting question is, therefore, whether there exists a stably distribution preserving distortion measure.

As we show next, if the degradation is non-invertible, then no distortion metric can be stably distribution preserving (see proof in Appendix C).

If $p_{X,Y}$ defines a non-invertible degradation, then $\Delta(\cdot,\cdot)$ is not a stably distribution preserving distortion at $p_{X,Y}$.

The perception-distortion tradeoff

We saw that for any distortion measure, a low distortion does not generally imply good perceptual-quality. An interesting question, then, is: What is the best perceptual quality that can be attained by an estimator with a prescribed distortion level?

The perception-distortion function of a signal restoration task is given by

where $\Delta(\cdot,\cdot)$ is a distortion measure and $d(\cdot,\cdot)$ is a divergence between distributions.

In words, $P(D)$ is the minimal deviation between the distributions $p_{X}$ and $p_{\hat{X}}$ that can be attained by an estimator with distortion $D$. To gain intuition into the typical behavior of this function, consider the following example.

Suppose that $Y=X+N$, where $X\sim\mathcal{N}(0,1)$ and $N\sim\mathcal{N}(0,\sigma_{N}^{2})$ are independent. Take $\Delta(\cdot,\cdot)$ to be the square-error distortion and $d(\cdot,\cdot)$ to be the KL divergence. For simplicity, let us focus on estimators of the form $\hat{X}=aY$. In this case, we can derive a closed form solution to Eq. (10) (see Appendix D), which is plotted for several noise levels $\sigma_{N}$ in Fig. 5. As can be seen, the minimal attainable $d_{\text{KL}}(p_{X},p_{\hat{X}})$ drops as the maximal allowable distortion (MSE) increases. Furthermore, the tradeoff is convex and becomes more severe at higher noise levels $\sigma_{N}$.

In general settings, it is impossible to solve (10) analytically. However, it turns out that the behavior seen in Fig. 5 is typical, as we show next (see proof in Appendix E).

Assume the problem setting of Section 3. If $d(p,q)$ of (4) is convex in its second argumentThat is, $d(p,\lambda q_{1}+(1-\lambda)q_{2})\leq\lambda d(p,q_{1})+(1-\lambda)d(p,q_{2})$ for any three distributions $p,q_{1},q_{2}$ and any $\lambda\in$., then the perception-distortion function $P(D)$ of (10) is

Note that Theorem 2 requires no assumptions on the distortion measure $\Delta(\cdot,\cdot)$. This implies that a tradeoff between perceptual quality and distortion exists for any distortion measure, including e.g. MSE, SSIM, square error between VGG features , etc. Yet, this does not imply that all distortion measures have the same perception-distortion function. Indeed, as we demonstrate in Sec. 6, the tradeoff tends to be less severe for distortion measures that capture semantic similarities between images.

The convexity of $P(D)$ implies that the tradeoff is more severe at the low-distortion and at the high-perceptual-quality extremes. This is particularly important when considering the TV divergence which is associated with the ability to distinguish between real vs. fake images (see Sec. 2.2). Since $P(D)$ is steeper at the low-distortion regime, any small improvement in distortion for an algorithm whose distortion is already low, must be accompanied by a large degradation in the ability to fool a discriminator. Similarly, any small improvement in the perceptual quality of an algorithm whose perceptual index is already low, must be accompanied by a large increase in distortion. Let us comment that the assumption that $d(p,q)$ is convex, is not very limiting. For instance, any $f$-divergence (e.g. KL, TV, Hellinger, $\mathcal{X}^{2}$) as well as the Renyi divergence, satisfy this assumption . In any case, the function $P(D)$ is monotonically non-increasing even without this assumption.

Several past works attempted to answer the question: What is the minimal attainable distortion $D_{\min}$ in various restoration tasks? . This corresponds to the value

which is the horizontal coordinate of the leftmost point on the perception-distortion function. However, as the minimum distortion estimator is generally not distribution preserving (Sec. 3.3), an important complementary question is: What is the minimal distortion that can be attained by an estimator having perfect perceptual quality? This corresponds to the value

which is the horizontal coordinate of the point where the perception-distortion function first touches the horizontal axis (see Fig. 6).

Observe that perfect perceptual quality ($p_{\hat{X}}=p_{X}$) is always attainable, for example by drawing $\hat{x}$ from $p_{X}$ independently of the input $y$. This method, however, ignores the input and is thus not good in terms of distortion. It turns out that perfect perceptual quality can generally be achieved with a significantly lower MSE distortion, as we show next (see proof in Appendix F).

For the square error distortion $\Delta(x,\hat{x})=\|\hat{x}-x\|^{2}$,

where $D_{\min}$ and $D_{\max}$ are defined by (11) and (12), respectively. This bound is attained by the estimator $\hat{X}$ defined through

which achieves $p_{\hat{X}}=p_{X}$ and has an MSE of $2D_{\min}$.

In simple words, Theorem 3 states that one would never need to sacrifice more than $3$dB in PSNR to obtain perfect perceptual quality. This can be achieved by drawing $\hat{x}$ from the posterior distribution $p_{X|Y}$. Interestingly, such a degradation was indeed incurred by all super-resolution methods that achieved state-of-the-art perceptual quality to date. This can be seen in Fig. 9, where the RMSE of the algorithms with the lowest perceptual index is nearly a factor of $\sqrt{2}$ larger than the RMSE of the methods with the lowest RMSE (see also ). However, note that this bound is generally not tight. For example, in the scalar Gaussian toy example of Fig. 5, $D_{\max}$ can be quite smaller than $2D_{\min}$, depending on the noise level.

2 Connection to rate-distortion theory

The perception-distortion tradeoff is closely related to the well-established rate-distortion theory . This theory characterizes the tradeoff between the bit-rate required to communicate a signal, and the distortion incurred in the signal’s reconstruction at the receiver. More formally, the rate-distortion function of a signal $X$ is defined by

where $I(\!X;\hat{X}\!)$ is the mutual information between $X$ and $\hat{X}$.

There are, however, several key differences between the two tradeoffs. First, in rate-distortion the optimization is over all conditional distributions $p_{\hat{X}|X}$, i.e. given the original signal. In the perception-distortion case, the estimator has access only to the degraded signal $Y$, so that the optimization is over the conditional distributions $p_{\hat{X}|Y}$, which is more restrictive. In other words, the perception-distortion tradeoff depends on the degradation $p_{Y|X}$, and not only on the signal’s distribution $p_{X}$ (see Example 1). Second, in rate-distortion the rate is quantified by the mutual information $I(X;\hat{X})$, which depends on the joint distribution $p_{X,\hat{X}}$. In our case, perception is quantified by the similarity between $p_{X}$ and $p_{\hat{X}}$, which does not depend on their joint distribution. Lastly, mutual information is inherently convex, while the convexity of the perception-distortion curve is guaranteed only when $d(\cdot,\cdot)$ is convex.

While the two tradeoffs are different, it is important to note that perceptual quality does play a role in lossy compression, as evident from the success of recent GAN based compression schemes . Theoretically, its effect can be studied through the rate-distortion-perception function , which is an extension of the rate-distortion function (15) and the perception-distortion function (10), characterizing the triple tradeoff between rate, distortion, and perceptual quality.

Traversing the tradeoff with a GAN

There exists a systematic way to design estimators that approach the perception-distortion curve: Using GANs. Specifically, motivated by , restoration problems can be approached by modifying the loss of the generator of a GAN to be

Besides the MMSE estimator, Figure 7 also includes the MAP estimator, the random draw estimator $\hat{x}\sim p_{X}$ (which ignores the noisy image $y$), and the conditional draw estimator of (14). The perceptual quality of these estimators is evaluated, as above, by the final loss of the WGAN discriminator , trained (without a generator) to distinguish between the estimators’ outputs and images from the dataset. Note that the denoising WGAN estimator (D) achieves the same distortion as the MAP estimator, but with far better perceptual quality. Furthermore, it achieves nearly the same perceptual quality as the random draw estimator, but with a significantly lower distortion.

Practical method for evaluating algorithms

Certain applications may require low-distortion (e.g. in medical imaging), while others may prefer superior perceptual quality. How should image restoration algorithms be evaluated, then?

We say that Algorithm A dominates Algorithm B if it has better perceptual quality and less distortion.

Note that if Algorithm A is better than B in only one of the two criteria, then neither $A$ dominates $B$ nor $B$ dominates $A$. Therefore, among a group of algorithms, there may be a large subset which can be considered equally good.

We say that an algorithm is admissible among a group of algorithms, if it is not dominated by any other algorithm in the group.

As shown in Figure 8, these definitions have very simple interpretations when plotting algorithms on the perception-distortion plane. In particular, the admissible algorithms in the group, are those which lie closest to the perception-distortion bound.

As discussed in Sec. 2, distortion is measured by full-reference (FR) metrics, e.g. . The choice of the FR metric, depends on the type of similarities we want to measure (per-pixel, semantic, etc.). Perceptual quality, on the other hand, is ideally quantified by collecting human opinion scores, which is time consuming and costly . Instead, the divergence $d(p_{X},p_{\hat{X}})$ can be computed, for instance by training a discriminator net (see Sec. 5). However, this requires many training images and is thus also time consuming. A practical alternative is to utilize no-reference (NR) metrics, e.g. , which quantify the perceptual quality of an image without a corresponding original image. In scenarios where NR metrics are highly correlated with human mean-opinion-scores (e.g. $4\times$ super-resolution ), they can be used as a fast and simple method for approximating the perceptual quality of an algorithmIn scenarios where NR metrics are inaccurate (e.g. blind deblurring with large blurs ), the perceptual metric should be human-opinion-scores or the loss of a discriminator trained to distinguish the algorithms’ outputs from natural images..

We use this approach to evaluate $16$ SR algorithms in a $4\times$ magnification task, by plotting them on the perception-distortion plane (Fig. 9). We measure perceptual quality using the NR metric NIQE , which was shown to correlate well with human opinion scores in a recent SR challenge (see Appendix H for experiments with the NR metrics BRISQUE , BLIINDS-II and the recent NR metric by Ma et al. ). We measure distortion by the five common FR metrics RMSE, SSIM , MS-SSIM , IFC and VIF , and additionally by the recent $\text{VGG}_{2,2}$ metric (the distance in the feature space of a VGG net) . To conform to previous evaluations, we compute all metrics on the y-channel after discarding a 4-pixel border (except for VGG2,2, which is computed on RGB images). Comparisons on color images can be found in Appendix H. The algorithms are evaluated on the BSD100 dataset . The evaluated algorithms include: A+ , SRCNN , SelfEx , VDSR , Johnson et al. , LapSRN , Bae et al. (“primary” variant), EDSR , SRResNet variants which optimize MSE and $\text{VGG}_{2,2}$ , SRGAN variants which optimize MSE, $\text{VGG}_{2,2}$, and $\text{VGG}_{5,4}$, in addition to an adversarial loss , ENet (“PAT” variant), Deng ($\gamma=0.55$), and Mechrez et al. .

Interestingly, the same pattern is observed in all plots: (i) The lower left corner is blank, revealing an unattainable region in the perception-distortion plane. (ii) In proximity of this blank region, NR and FR metrics are anti-correlated, indicating a tradeoff between perception and distortion. Notice that the tradeoff exists even for the IFC, VIF and VGG2,2 measures, which are considered to capture visual quality better than MSE and SSIM.

Figure 10 depicts the outputs of several algorithms lying closest to the perception-distortion bound in the IFC graph in Fig. 9. While the images are ordered from low to high distortion (according to IFC), their perceptual quality clearly improves from left to right.

Both FR and NR measures are commonly validated by calculating their correlation with human opinion scores, based on the assumption that both should be correlated with perceptual quality. However, as Fig. 11 shows, while FR measures can be well-correlated with perceptual quality when distant from the unattainable region, this is clearly not the case when approaching the perception-distortion bound. In particular, all tested FR methods are inconsistent with human opinion scores which found the SRGAN to be superb in terms of perceptual quality , while NR methods successfully determine this. We conclude that image restoration algorithms should always be evaluated by a pair of NR and FR metrics, constituting a reliable, reproducible and simple method for comparison, which accounts for both perceptual quality and distortion. This evaluation method was demonstrated and validated by a human opinion study in the 2018 PIRM super-resolution challenge .

Up until 2016, SR algorithms occupied only the upper-left section of the perception-distortion plane. Nowadays, emerging techniques are exploring new regions in this plane. The SRGAN, ENet, Deng, Johnson et al. and Mechrez et al. methods are the first (to our knowledge) to populate the high perceptual quality region. In the near future we will most likely witness continued efforts to approach the perception-distortion bound, not only in the low-distortion region, but throughout the entire plane.

Conclusion

We proved and demonstrated the counter-intuitive phenomenon that distortion and perceptual quality are at odds with each other. Namely, the lower the distortion of an algorithm, the more its distribution must deviate from the statistics of natural scenes. We showed empirically that this tradeoff exists for many popular distortion measures, including those considered to be well-correlated with human perception. Therefore, any distortion measure alone, is unsuitable for assessing image restoration methods. Our novel methodology utilizes a pair of NR and FR metrics to place each algorithm on the perception-distortion plane, facilitating a more informative comparison of image restoration methods.

Acknowledgements This research was supported by the Israel Science Foundation (grant no. 852/17), and by the Technion Ollendorff Minerva Center.

References

Appendix A Real-vs.-fake user studies and hypothesis testing

We assume the setting where an observer is shown a real image (a draw from $p_{X}$) or an algorithm output (a draw from $p_{\hat{X}}$), with a prior probability of $0.5$ each. The task is to identify which distribution the image was drawn from ($p_{X}$ or $p_{\hat{X}}$) with maximal probability of success. This is the setting of the Bayesian hypothesis testing problem, for which the maximum a-posteriori (MAP) decision rule minimizes the probability of error (see Section 1 in ). When there are two possible hypotheses with equal probabilities (as in our setting), the relation between the probability of error and the total-variation distance between $p_{X}$ and $p_{\hat{X}}$ in (1) can be easily derived (see Section 2 in ).

Appendix B The MMSE and MAP examples of Sec. 3

Sections 3.1 and 3.2 exemplify that the MSE and the $0-1$ loss are not distribution preserving in the setting of estimating a discrete random variable (vector) $X$ from its noisy version $Y=X+N$, where $N\sim\mathcal{N}(0,\sigma^{2}I)$ is independent of $X$. Since the conditional distribution of $Y$ given $X=x$ is $\mathcal{N}(x,\sigma^{2}I)$, the MMSE estimator is given by

In the example of Fig. 4, $x$ is a $280\times 280$ binary image comprising $28\times 28$ blocks chosen uniformly at random from a finite database. Since the noise $N$ is i.i.d., each $28\times 28$ block of $y$ can be denoised separately, both in the case of the MSE criterion and in the case of MAP. For each block, we have $p(x)=1/59400$ for the non-blank images and $p(x)=1/11$ for the blank image.

In the trinary example (5), we calculate the distribution of the MMSE estimate (Fig. 3) by

where the inverse of $\hat{x}_{\text{MMSE}}(y)$ (see (6)) and its derivative are calculated numerically, and $p_{Y}(y)=\sum_{x}p(y|x)p(x)$ with $p(y|x)\sim\mathcal{N}(x,1)$ and $p(x)$ of (5).

Appendix C Proof of Theorem 1

We will show that a stably distribution preserving optimal estimator is necessarily unique. At the same time, we will show that a non-invertible degradation implies that this optimal estimator is non-unique. Specifically, we use the following definitions.

We say that the optimal estimator is not unique if there exist two estimators, $p_{\hat{X}_{1}|Y}$ and $p_{\hat{X}_{2}|Y}$ that minimize the mean distortion (3) and differ from one another in the sense that

The outline of the proof of Theorem 1 will be as follows:

In Lemma 1 we will show that if the distortion measure is stably distribution preserving, then the optimal estimator $\hat{X}^{*}$ is uniquely defined by $p_{\hat{X}^{*}|Y}=p_{X|Y}$.

In Lemma 2 we will show that if the estimator $\hat{X}^{*}$ defined by $p_{\hat{X}^{*}|Y}=p_{X|Y}$ is an optimal estimator and the degradation is non-invertible, then the optimal estimator is non-unique.

This leads to a contradiction, proving that there does not exist a stably distribution preserving distortion metric if the degradation in non-invertible.

If the distortion measure $\Delta(\cdot,\cdot)$ is stably distribution preserving at $p_{X,Y}$, then the optimal estimator $\hat{X}^{*}$ that minimizes the mean distortion (3) is uniquely defined by $p_{\hat{X}^{*}|Y}=p_{X|Y}$.

We start by noting that the optimal estimator $p_{\hat{X}|Y}$ depends only on $p_{X|Y}$ and not on $p_{Y}$. Indeed, since $X$ and $\hat{X}$ are independent given $Y$, the mean distortion can be written as

Therefore, the optimal $p_{\hat{X}|Y}$ is that which minimizes $\int f(\hat{x},y)p_{\hat{X}|Y}(\hat{x}|y)d\hat{x}$ for each $y$. Since $f(\hat{x},y)$ depends only on $p_{X|Y}$, the optimal estimator depends only on $p_{X|Y}$.

where we used the assumption that $p_{\hat{X}^{*}}=p_{X}$. Similarly, the distribution of $X$ has changed to

This equality can hold for every perturbation $q$ only if $p_{\hat{X}^{*}|Y}=p_{X|Y}$, completing the proof.

Notice that this also proves that the optimal estimator is unique (under the stably distribution preserving assumption), as we demonstrated that only $p_{\hat{X}^{*}|Y}=p_{X|Y}$ minimizes the mean distortion. ∎

If the degradation is non-invertible, and the estimator $\hat{X}^{*}$ defined by $p_{\hat{X}^{*}|Y}=p_{X|Y}$ is an optimal estimator, then the optimal estimator is non-unique.

Now, since $\hat{X}^{*}$ is an optimal estimator, $p_{\hat{X}^{*}|Y}$ must minimize $\int f(\hat{x},y)p_{\hat{X}|Y}(\hat{x}|y)d\hat{x}$ for each $y$ (see proof of Lemma 1). This means that for any $y$, the conditional $p_{\hat{X}^{*}|Y}(\hat{x}|y)$ must assign positive probability only to $\hat{x}$ in the set of minima $\mathcal{S}_{\min}(y)=\operatorname{\arg\min}_{\hat{x}}f(\hat{x},y)$. We conclude that $\mathcal{S}_{x}\subseteq\mathcal{S}_{\min}(y)$ for every $y\in\mathcal{S}_{y}$. This implies that any other estimator that assigns zero probability to $\hat{x}\notin\mathcal{S}_{x}$ for every $y\in\mathcal{S}_{y}$, is also optimal.

Let $\mathcal{S}_{x}^{1},\mathcal{S}_{x}^{2}$ be non-empty disjoint sets such that $\mathcal{S}_{x}^{1}\cup\mathcal{S}_{x}^{2}=\mathcal{S}_{x}$. Now, define two estimators, such that $p_{\hat{X}_{1}|Y}(\hat{x}|y)>0$ only for $\hat{x}\in\mathcal{S}_{x}^{1}$, and $p_{\hat{X}_{2}|Y}(\hat{x}|y)>0$ only for $\hat{x}\in\mathcal{S}_{x}^{2}$, for every $y\in\mathcal{S}_{y}$. Both are optimal estimators (as they only assign positive probability to $\hat{x}\in\mathcal{S}_{x}$). Yet, these two estimators have conditional distributions with disjoint supports for every $y$, and thus $d_{\text{TV}}(p_{\hat{X}_{1}|Y}(\cdot|y),p_{\hat{X}_{2}|Y}(\cdot|y))>0\quad\forall y\in\mathcal{S}_{y}$. Therefore, by Definition 7, the optimal estimator is non-unique. ∎

Now, let us assume to the contrary that $p_{X,Y}$ defines a non-invertible degradation, and that the distortion function $\Delta(\cdot,\cdot)$ is stably distribution preserving at $p_{X,Y}$. By Lemma 1, the optimal estimator $\hat{X}^{*}$ is uniquely defined by $p_{\hat{X}^{*}|Y}=p_{X|Y}$. But now according to Lemma 2, since the degradation is non-invertible, the optimal estimator is non-unique, leading to a contradiction.

Appendix D Derivation of Example 1

Since $\hat{X}=aY=a(X+N)$, it is a zero-mean Gaussian random variable. Now, the Kullback-Leibler distance between two zero-mean normal distributions is given by

and the MSE between $X$ and $\hat{X}$ is given by

Substituting $\hat{X}=aY$ and $\sigma_{X}^{2}=1$, we obtain that $\sigma_{\hat{X}}=|a|\sqrt{1+\sigma_{N}^{2}}$ and $\sigma_{X\hat{X}}=a$, so that

Notice that $d_{\text{KL}}$ is symmetric, and $\text{MSE}(|a|)\leq\text{MSE}(a)$ (see Fig. 12). Thus, for any negative $a$, there always exists a positive $a$ with which $d_{\text{KL}}$ is the same and the MSE is not larger. Therefore, without loss of generality, we focus on the range $a\geq 0$.

For $D<D_{\min}=\frac{\sigma_{N}^{2}}{1+\sigma_{N}^{2}}$ the constraint set of $\text{MSE}(a)<D$ is empty, and there is no solution to (33). For $D\geq D_{\min}$, the constraint is satisfied for $a_{-}\leq a\leq a_{+}$, where

For $D=D_{\min}$, the optimal (and only possible) $a$ is

For $D>D_{\min}$, $a_{+}$ monotonically increases with $D$, broadening the constraint set. The objective $d_{\text{KL}}(a)$ monotonically decreases with $a$ in the range $a\in(0,1/\sqrt{(1+\sigma_{N}^{2})})$ (see Fig. 12 and the mathematical justification below). Thus, for $D_{\min}<D\leq D_{0}$, the optimal $a$ is always the largest possible $a$, which is $a=a_{+}(D)$, where $D_{0}$ is defined by $a_{+}(D_{0})=1/\sqrt{(1+\sigma_{N}^{2})}$ (see Fig. 12). For $D>D_{0}$, the optimal $a$ is $a=1/\sqrt{(1+\sigma_{N}^{2})}$, which achieves the global minimum $d_{\text{KL}}(a)=0$. The closed form solution is therefore given by

To justify the monotonicity of $d_{\text{KL}}(a)$ in the range $a\in(0,1/\sqrt{(1+\sigma_{N}^{2})})$, notice that for $a>0$,

which is negative for $a\in(0,1/\sqrt{(1+\sigma_{N}^{2})})$.

Appendix E Proof of Theorem 2

The proof of Theorem 2 follows closely that of the rate-distortion theorem from information theory . The value $P(D)$ is the minimal distance $d(p_{X},p_{\hat{X}})$ over a constraint set whose size does not decrease with $D$. This implies that the function $P(D)$ is non-increasing in $D$. Now, to prove the convexity of $P(D)$, we will show that

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

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

Since $d(\cdot,\cdot)$ is convex in its second argument,

because $\hat{X}_{\lambda}$ is in the constraint set. Below, we show that

Therefore, since $P(D)$ is non-increasing in $D$, we have that

Combining (39), (42), (E) and (46) proves (38), thus demonstrating that $P(D)$ is convex.

where the second and fourth transitions are according to the law of total expectation and the third transition is justified by

Here we used (43) and the fact that $X$ and $\hat{X}_{\lambda}$ are independent given $Y$, and similarly for the pairs $(X,\hat{X}_{1})$ and $(X,\hat{X}_{2})$.

Appendix F Proof of Theorem 3

The estimator $\hat{X}$ of (14) attains perfect perceptual quality since

where we used the law of total expectation and the fact that given $Y$, $X$ and $\hat{X}$ are independent and identically distributed. The MSE of $\hat{X}$ is therefore

where the second equality is due to (F) and (51), and the third equality is due to the orthogonality principle. We thus established that $\hat{X}$ is a distribution preserving estimator whose MSE is precisely twice the MSE of the MMSE estimator. This implies that

Appendix G WGAN architecture and training details (Sec. 5)

Appendix H Super-resolution evaluation details (Sec. 6) and additional comparisons

The no-reference (NR) and full-reference (FR) methods BRISQUE, BLIINDS-II, NIQE, SSIM, MS-SSIM, IFC and VIF were obtained from the LIVE laboratory websitehttp://live.ece.utexas.edu/research/Quality/index.htm, the NR method of Ma et al. was obtained from the project webpagehttps://github.com/chaoma99/sr-metric, and the pretrained VGG-19 network was obtained through the PyTorch torchvision packagehttp://pytorch.org/docs/master/torchvision/index.html. The low-resolution images were obtained by factor 4 downsampling with a bicubic kernel. The super-resolution results on the BSD100 dataset of the SRGAN and SRResNet variants were obtained onlinehttps://twitter.box.com/s/lcue6vlrd01ljkdtdkhmfvk7vtjhetog, and the results of EDSR, Deng, Johnson et al. and Mechrez et al. were kindly provided by the authors. The algorithms for testing the other SR methods were obtained online: A+http://www.vision.ee.ethz.ch/~timofter/ACCV2014_ID820_SUPPLEMENTARY/, SRCNNhttp://mmlab.ie.cuhk.edu.hk/projects/SRCNN.html, SelfExhttps://github.com/jbhuang0604/SelfExSR, VDSRhttp://cv.snu.ac.kr/research/VDSR/, LapSRNhttps://github.com/phoenix104104/LapSRN, Bae et al. https://github.com/iorism/CNN and ENethttps://webdav.tue.mpg.de/pixel/enhancenet/. All NR and FR metrics and all SR algorithms were used with the default parameters and models. In the paper, we reported comparisons on the y-channel (except for the $\text{VGG}_{2,2}$ measure). In the supplementary material, we report results with additional NR metrics on the y-channel, as well as results on color images. When comparing color images, for SR algorithms which treat the y-channel alone, the Cb and Cr channels are upsampled by bicubic interpolation.

The general pattern appearing in Fig. 9 will appear for any NR method which accurately predicts the perceptual quality of images. We show here three additional popular NR methods: BRISQUE , BLIINDS-II and the recent measure by Ma et al. in Figs. 14, 15, 16, where the same conclusions as for NIQE (see Sec. 6) are apparent. The same pattern appears for RGB images as well, as shown in Figs. 17, 18. Note that the perceptual quality of Johnson et al. and SRResNet-VGG2,2 is inconsistent between NR metrics, likely due to varying sensitivity to the cross-hatch pattern artifacts which are present in these method’s outputs. For this reason, Johnson et al. does not appear in the NIQE plots, as its NIQE score is $13.55$ (far off the plots).