Classical transform-coding theory predicts that the mean-square distortion decays exponentially in the bit rate, D∝2−2RˉD \propto 2^{-2\bar{R}}, but this rests on the high-resolution quantization hypothesis, which fails for the practical image-coding regime below roughly one bit per pixel. Mallat and Falzon (1998) showed that at such low rates the distortion is governed instead by the nonlinear approximation error D0(M)D_0(M) obtained by keeping only the MM largest transform coefficients, with MM proportional to the bit budget and proportionality and overhead constants (r0,r1r_0, r_1 for direct coders, r0e,r1er_0^e, r_1^e for embedded coders) fixed by the significance-map and entropy coding. Their derivation, however, treats each image as a deterministic vector with an interpolated coefficient histogram, imposes unquantified regularity hypotheses on the decay of sorted coefficients, leaves the choice of an optimal orthonormal basis for a given image class at a qualitative level, and calibrates the coding overheads empirically. The open problem is to complete that theory: constructing a stochastic ensemble model of natural images that provably yields the low-bit-rate asymptotic formulas, quantifying where the regularity hypotheses fail, giving a constructive basis-optimization principle, and deriving tight analytic bounds on significance-map and entropy-coding overheads for actual run-length, zero-tree, and set-partitioning algorithms. Stylized models (sparse, Gaussian-mixture, self-similar, and piecewise-regular sources) have been analyzed rigorously, but no prior work derives the Mallat–Falzon asymptotics from a realistic natural-image ensemble, closes the overhead bounds, or solves the basis-optimization problem for natural image classes.

Background

Transform coding is the architecture underlying JPEG and JPEG2000: the image is decomposed in an orthonormal basis (a block discrete cosine basis for JPEG; a wavelet basis, i.e. a basis of dilated and translated local oscillating waveforms, for JPEG2000), each transform coefficient is scalar-quantized, and the quantized values are losslessly entropy-coded. Classical rate-distortion theory for this scheme, developed for Gaussian stationary sources under the high-resolution quantization hypothesis (quantization bins much smaller than the spread of the data), predicts that the mean-square distortion decays exponentially, D(Rˉ)∝2−2RˉD(\bar{R}) \propto 2^{-2\bar{R}}, with the bits per pixel Rˉ\bar{R}, and that the Karhunen–Loève basis (the eigenbasis of the signal covariance, which optimizes linear energy compaction) is the best orthonormal basis. Real image coders operate below about one bit per pixel, where both conclusions break down: the quantization bins are coarse, most coefficients fall in a wide zero bin, and the coder must spend bits storing a binary significance map indicating which coefficients are nonzero. Embedded (progressive) coders such as Shapiro's embedded zero-tree coder (EZW), which exploits the tendency of wavelet coefficients to decay across scales by coding significance information on quad-trees, and Said and Pearlman's set-partitioning coder (SPIHT), refine this further. Mallat and Falzon (1998) analyzed this regime. They observed that wavelet and block-cosine coefficient histograms of natural images are sharply peaked at zero with heavy, approximately generalized-Gaussian (exponentially decaying, non-Gaussian) tails, and that the decay of the sorted coefficient amplitudes can be summarized by a slowly varying exponent. Under four regularity hypotheses on the interpolated coefficient density p(x)p(x) and on the sorted-coefficient decay — a bound on the second derivative (slow variation of the local decay exponent γ\gamma), derivative conditions, concavity, and symmetry of pp (equations (19)–(22) of the paper) — they proved that at low rates the distortion is, up to constants, the nonlinear approximation error D0(M)D_0(M) (the error of reconstructing the image from its MM largest coefficients alone) evaluated at a number of significant coefficients proportional to the total bit budget, with the proportionality and coding-overhead summarized by constants r0,r1r_0, r_1 for a direct transform coder and r0e,r1er_0^e, r_1^e for an embedded zero-tree coder. For typical natural images the resulting distortion decays like a power of the bit rate whose exponent involves the decay exponent of the sorted coefficients, which the authors found to be of order one (about 3 dB of signal-to-noise improvement per additional bit per pixel for such images, as stated in the paper for Lena). The analysis explained, in a unified way, the observed low-rate behavior of JPEG and wavelet coders and why basis quality should be judged by nonlinear (few-term) approximation rather than by linear energy compaction. The framework, however, was explicitly built on three acknowledged shortcuts. First, the signals are treated as deterministic vectors with parameterized coefficient decay: the paper states that no stochastic model then existed that "incorporates the full diversity of image structures, such as nonstationary textures and edges", so the distortion rate is computed per signal rather than as an ensemble average. Second, the regularity hypotheses (19)–(22) are verified only qualitatively on a handful of test images, the concavity being described as a technical condition used to control corrective O(ϵ)O(\epsilon) terms in the calculations, and the range of images and parameter values for which they hold — and the size of the neglected corrective terms — is not quantified. Third, the basis is optimized only qualitatively (the paper notes that finding the basis minimizing D0D_0 over realizations of an image class "is difficult because the basis vectors are selected depending on each realization"), and the significance-map and entropy-coding overheads of run-length, zero-tree, and set-partitioning coders enter only through constants partly estimated numerically rather than bounded analytically. Later work clarified the neighboring mathematics: nonlinear (best MM-term) approximation theory (DeVore 1998; Cohen–Daubechies–Guleryuz–Orchard 2002, which shows in Besov-type smoothness classes — spaces characterized by wavelet-coefficient decay — when nonlinear approximation gains do and do not translate into rate-distortion gains) and stochastic sparse-source rate-distortion theory (Weidmann–Vetterli) supply rigorous counterparts of pieces of the framework, but for stylized source and function classes rather than for natural images.

Problem Statement

Establish a complete, rigorous, and predictive distortion-rate theory for transform coding of natural images at low bit rates (below roughly one bit per pixel), completing the program opened by Mallat and Falzon (1998). The theory should jointly deliver: (1) a stochastic ensemble model of natural images — capturing the sharply peaked, heavy-tailed, scale-dependent statistics of their wavelet and block-cosine coefficients — from which the low-bit-rate asymptotic formulas of that paper, in which the distortion at rate Rˉ\bar{R} equals a constant multiple of the nonlinear approximation error D0D_0 evaluated at a number of significant coefficients proportional to Rˉ\bar{R}, can be derived rigorously rather than for deterministic signals via an interpolated coefficient histogram; (2) a quantification of the range of images and coding parameters for which the regularity hypotheses (19)–(22) on the coefficient density and the sorted-coefficient decay hold, and of the parameter regimes where the neglected corrective O(ϵ)O(\epsilon) terms become significant; (3) a constructive principle (not merely the qualitative advice of using more vanishing moments and smaller wavelet support) for choosing or optimizing the orthonormal basis for a given class of images, in the sense of minimizing the low-rate distortion or equivalently the nonlinear approximation error D0D_0; and (4) tight, general analytic bounds — rather than empirically calibrated constants — on the rate overhead of the significance map and the entropy coding, for the specific algorithms used in practice (run-length coding as in JPEG, zero-tree coding as in EZW, and set-partitioning as in SPIHT), covering both direct and embedded coders. These four components are parts of one objective — making the low-bit-rate theory rigorous and predictive for real image ensembles — and the theory should make explicit which components hold for which image models or classes, and how the constants depend on the model.

References

  1. S. Mallat, F. Falzon, 'Analysis of low bit rate image transform coding', IEEE Transactions on Signal Processing 46(4):1027–1042, 1998. DOI: 10.1109/78.668554, https://doi.org/10.1109/78.668554
  2. F. Falzon, S. Mallat, 'Low bit rate image coding over bases', Proceedings of the 14th International Conference on Pattern Recognition (ICPR 1998), vol. 2, pp. 1260–1263. DOI: 10.1109/ICPR.1998.711930, https://doi.org/10.1109/ICPR.1998.711930
  3. D. L. Donoho, M. Vetterli, R. DeVore, I. Daubechies, 'Data compression and harmonic analysis', IEEE Transactions on Information Theory 44(6):2435–2476, 1998. DOI: 10.1109/18.720544, https://doi.org/10.1109/18.720544
  4. R. DeVore, 'Nonlinear approximation', Acta Numerica 7:51–150, 1998. DOI: 10.1017/S0962492900002816, https://doi.org/10.1017/S0962492900002816
  5. A. Cohen, I. Daubechies, O. G. Guleryuz, M. T. Orchard, 'On the importance of combining wavelet-based nonlinear approximation with coding strategies', IEEE Transactions on Information Theory 48(7):1895–1921, 2002. DOI: 10.1109/TIT.2002.1013132, https://doi.org/10.1109/TIT.2002.1013132
  6. A. Cohen, W. Dahmen, I. Daubechies, R. DeVore, 'Tree approximation and optimal encoding', Applied and Computational Harmonic Analysis 11(2):192–226, 2001. DOI: 10.1006/ACHA.2001.0336, https://doi.org/10.1006/ACHA.2001.0336
  7. C. Weidmann, M. Vetterli, 'Rate distortion behavior of threshold-based nonlinear approximations', Data Compression Conference (DCC 2000), pp. 333–342. DOI: 10.1109/DCC.2000.838173, https://doi.org/10.1109/DCC.2000.838173
  8. C. Weidmann, M. Vetterli, 'Rate distortion behavior of sparse sources', IEEE Transactions on Information Theory 58(8):4969–4992, 2012. DOI: 10.1109/TIT.2012.2201335, https://doi.org/10.1109/TIT.2012.2201335
  9. N. Sarshar, X. Wu, 'On rate-distortion models for natural images and wavelet coding performance', IEEE Transactions on Image Processing 16(5):1383–1394, 2007. DOI: 10.1109/TIP.2007.894224, https://doi.org/10.1109/TIP.2007.894224
  10. E. Le Pennec, S. Mallat, 'Sparse geometric image representations with bandelets', IEEE Transactions on Image Processing 14(4):423–438, 2005. DOI: 10.1109/TIP.2005.843753, https://doi.org/10.1109/TIP.2005.843753
  11. M. D. Gaubatz, S. S. Hemami, 'Efficient entropy estimation based on doubly stochastic models for quantized wavelet image data', IEEE Transactions on Image Processing 16(4):967–981, 2007. DOI: 10.1109/TIP.2007.891784, https://doi.org/10.1109/TIP.2007.891784
  12. P. Prandoni, M. Vetterli, 'Approximation and compression of piecewise smooth functions', Philosophical Transactions of the Royal Society A 357(1760):2573–2591, 1999. DOI: 10.1098/rsta.1999.0449, https://doi.org/10.1098/rsta.1999.0449
  13. A. Fraysse, B. Pesquet-Popescu, J.-C. Pesquet, 'On the uniform quantization of a class of sparse sources', IEEE Transactions on Information Theory 55(7):3243–3263, 2009. DOI: 10.1109/TIT.2009.2021329, https://doi.org/10.1109/TIT.2009.2021329
  14. S. S. Pradhan, D. L. Neuhoff, 'Transform coding of densely sampled Gaussian data', IEEE International Symposium on Information Theory (ISIT 2007), pp. 1111–1114. DOI: 10.1109/ISIT.2007.4557372, https://doi.org/10.1109/ISIT.2007.4557372
  15. M. S. Crouse, R. D. Nowak, R. G. Baraniuk, 'Wavelet-based statistical signal processing using hidden Markov models', IEEE Transactions on Signal Processing 46(4):886–902, 1998. DOI: 10.1109/78.668544, https://doi.org/10.1109/78.668544
  16. J. M. Shapiro, 'Embedded image coding using zerotrees of wavelet coefficients', IEEE Transactions on Signal Processing 41(12):3445–3462, 1993. DOI: 10.1109/78.258085, https://doi.org/10.1109/78.258085
  17. A. Said, W. A. Pearlman, 'A new, fast, and efficient image codec based on set partitioning in hierarchical trees', IEEE Transactions on Circuits and Systems for Video Technology 6(3):243–250, 1996. DOI: 10.1109/76.499834, https://doi.org/10.1109/76.499834