Optimal predictors and quantizers
Optional · supplementary note 2 of 3 for IP 08 · Image Compression and Watermarking. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.
Navigate: this page and this track: Navigate: this page and this track
The optimal linear predictor chooses to minimize the mean-square prediction error . Setting the derivatives to zero gives the normal equations
where is the autocorrelation matrix with entries and is the vector with entries . (The analysis usually ignores the quantizer inside the loop, which is accurate when quantization is fine.)
The optimal quantizer for a given number of levels minimizes the mean-square quantization error for the error distribution. Two conditions characterize it: each decision boundary lies halfway between its two neighboring reconstruction levels, and each reconstruction level is the centroid (conditional mean) of the probability mass in its interval. Because prediction errors are peaked at zero, the optimal levels are dense near zero and sparse in the tails. In practice, a uniform quantizer followed by a variable-length code is nearly as good and much simpler.
References
- R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 8. publisher page
- Joint Photographic Experts Group, “JPEG 1 (ISO/IEC 10918-1 | ITU-T Rec. T.81): Digital compression and coding of continuous-tone still images,” JPEG overview page. jpeg.org
- Joint Photographic Experts Group, “JPEG 2000 (ISO/IEC 15444),” JPEG overview page. jpeg.org
- W3C, “Portable Network Graphics (PNG) Specification (Third Edition),” W3C Recommendation, 2025. w3.org
- Joint Photographic Experts Group, “JPEG XL (ISO/IEC 18181),” JPEG overview page. jpeg.org
- Alliance for Open Media, “AV1 Image File Format (AVIF),” v1.2.0, 2025. aomediacodec.github.io
- Nokia Technologies, “High Efficiency Image File Format (HEIF), ISO/IEC 23008-12: technical information.” nokiatech.github.io
- D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,” Proceedings of the IRE, vol. 40, pp. 1098–1101, 1952. doi
- S. W. Golomb, “Run-length encodings,” IEEE Transactions on Information Theory, vol. 12, pp. 399–401, 1966. doi
- M. J. Weinberger, G. Seroussi and G. Sapiro, “The LOCO-I lossless image compression algorithm: principles and standardization into JPEG-LS,” IEEE Transactions on Image Processing, vol. 9, pp. 1309–1324, 2000. doi
- I. H. Witten, R. M. Neal and J. G. Cleary, “Arithmetic coding for data compression,” Communications of the ACM, vol. 30, pp. 520–540, 1987. doi
- T. A. Welch, “A Technique for High-Performance Data Compression,” Computer, vol. 17, pp. 8–19, 1984. doi
- G. K. Wallace, “The JPEG still picture compression standard,” IEEE Transactions on Consumer Electronics, vol. 38, no. 1, pp. xviii–xxxiv, 1992. doi
- A. Skodras, C. Christopoulos and T. Ebrahimi, “The JPEG 2000 still image compression standard,” IEEE Signal Processing Magazine, vol. 18, pp. 36–58, 2001. doi
- J. Ballé, D. Minnen, S. Singh, S. J. Hwang and N. Johnston, “Variational image compression with a scale hyperprior,” ICLR, 2018. arXiv
- Y. Hu, W. Yang, Z. Ma and J. Liu, “Learning End-to-End Lossy Image Compression: A Benchmark,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021. arXiv
- Y. Yang, S. Mandt and L. Theis, “An Introduction to Neural Data Compression,” Foundations and Trends in Computer Graphics and Vision, vol. 15, no. 2, 2023. arXiv
- X. Zhong, A. Das, F. Alrasheedi and A. Tanvir, “A Brief Yet In-Depth Survey of Deep Learning-Based Image Watermarking,” Applied Sciences, 2023. arXiv
- J. Zhu, R. Kaplan, J. Johnson and L. Fei-Fei, “HiDDeN: Hiding Data With Deep Networks,” arXiv:1807.09937, 2018. arXiv
- P. Fernandez, G. Couairon, H. Jégou, M. Douze and T. Furon, “The Stable Signature: Rooting Watermarks in Latent Diffusion Models,” ICCV, 2023. arXiv