Efficient Co-Domain Quantisation for PDE-Based Image Compression
Main Article Content
Abstract
Finding optimal data for inpainting is a key problem for image compression with partial differential equations (PDEs). Not only the location of important pixels but also their values should optimise the compression quality. The position of such important data is usually encoded in a binary mask. The corresponding pixel values are real valued and yield prohibitively high storage costs in the context of data compression. Therefore, quantisation strategies for the pixel value domain are mandatory to obtain high compression ratios. While existing methods to quantise the data for PDE-based compression show good quality, unfortunately, they are too slow for many applications. We discuss several strategies, based on data clustering models from machine learning, to speed up the quantisation step.
Article Details
How to Cite
Hoeltgen, L., & Breuß, M.
(2016).
Efficient Co-Domain Quantisation for PDE-Based Image Compression.
Proceedings Of The Conference Algoritmy, , 194-203.
Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/algoritmy/article/view/408/325
Section
Articles
References
[1] C.C. Aggarwal and C. K. Reddy, editors. Data Clustering, Algorithms and Applications. CRC Press, 2014.
[2] D. Arthur and S. Vassilvitskii. K-means++: The advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1027–1035. SIAM, 2007.
[3] Z. Belhachmi, D. Bucur, B. Burgeth, and J. Weickert. How to choose interpolation data in images. SIAM Journal on Applied Mathematics, 70(1):333–352, 2009.
[4] A. Bourquard and M. Unser. Anisotropic interpolation of sparse generalized image samples. IEEE Transactions on Image Processing, 22(2):459–472, 2013.
[5] Y. Chen, R. Ranftl, and T. Pock. A bi-level view of inpainting based image compression. Computing Research Repository, 2014. Available from http://arxiv.org/abs/1401.4112v2.
[6] Carl de Boor. Good approximation by splines with variable knots II. In G. Watson, editor, Conference on the Numerical Solution of Differential Equations, volume 363 of Lecture Notes in Mathematics, pages 12–20. Springer, 1974.
[7] L. Demaret and A. Iske. Scattered data coding in digital image compression. In A. Cohen, J.-L. Merrien, and L. L. Schumaker, editors, Curve and Surface Fitting: Saint-Malo 2002, pages 107–117. Nashboro Press, 2003.
[8] L. Demaret and A. Iske. Advances in digital image compression by adaptive thinning. Annals of the MCFA, 3:105–109, 2004.
[9] L. Demaret, A. Iske, and W. Khachabi. Contextual image compression from adaptive sparse data representations. In Rémi Gribonval, editor, Proceedings of SPARS’09 (Signal Processing with Adaptive Sparse Structured Representations Workshop), 2009. Available online: https: //hal.inria.fr/inria-00369491.
[10] I. Galić, J. Weickert, M. Welk, A. Bruhn, A. Belyaev, and H.-P. Seidel. Towards PDE-based image compression. In Variational, Geometric and Level-Set Methods in Computer Vision, volume 3752 of LNCS, pages 37–48. Springer, 2005.
[11] G. Gan, C. Ma, and J. Wu. Clustering: Theory, Algorithms and Applications. SIAM, 2007.
[12] D. Gilbarg and N. Trudinger. Elliptic Partial Differential Equations of Second Order. Springer, 2001.
[13] A. Gordon. Hierarchical classification. In P. Arabie, L. Hubert, and G. Soete, editors, Clustering and Classification, pages 65–121. World Scientific, 1996.
[14] L. Guerra, V. Robles, C. Bielza, and P. Larranaga. A comparison of clustering quality indices using outliers and noise. Intelligent Data Analysis, 16:703–715, 2012.
[15] H. Hamideh. On the optimal knots of first degree splines. Kuwait Journal of Science and Engineering, 29(1):1–13, 2002.
[16] P. S. Heckbert. Color image quantization for frame buffer display. In ACM SIGGRAPH ’82 Proceedings, pages 297–307, 1982.
[17] L. Hoeltgen, S. Setzer, and J. Weickert. An optimal control approach to find sparse data for Laplace interpolation. In Energy Minimization Methods in Computer Vision and Pattern Recognition, volume 8081 of LNCS, pages 151–164. Springer, 2013.
[18] L. Hoeltgen and J. Weickert. Why does non-binary mask optimisation work for diffusion-based image compression? In Energy Minimization Methods in Computer Vision and Pattern Recognition, volume 8932 of LNCS, pages 85–98. Springer, 2015.
[19] D. Liu, X. Sun, F. Wu, S. Li, and Y.-Q. Zhang. Image compression with edge-based inpainting. IEEE Transactions on Circuits, Systems and Video Technology, 7(10):1273–1286, October 2007.
[20] S. P. Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 2(28):129–137, 1982.
[21] M. Mainberger, S. Hoffmann, J. Weickert, C. H. Tang, D. Johannsen, F. Neumann, and B. Doerr. Optimising spatial and tonal data for homogeneous diffusion inpainting. In A. M. Bruckstein, B. M. Haar ter Romeny, A. M. Bronstein, and M. M. Bronstein, editors, Scale Space and Variational Methods in Computer Vision, volume 6667 of LNCS, pages 26–37. Springer, 2012.
[22] J. B. McQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, pages 281–297. University of California Press, 1967.
[23] P. Ochs, Y. Chen, T. Brox, and T. Pock. iPiano: Inertial proximal algorithm for non-convex optimization. SIAM Journal on Imaging Sciences, 7(2):1388–1419, 2014.
[24] P. Peter, S. Hoffmann, F. Nedwed, L. Hoeltgen, and J. Weickert. From optimised inpainting with linear PDEs towards competitive image compression codecs. In T. Bräunl, B. McCane, M. Rivers, and X. Yu, editors, Advances in Image and Video Technology, LNCS. Springer, 2015. To appear.
[25] P. Peter, C. Schmaltz, N. Mach, M. Mainberger, and J. Weickert. Beyond pure quality: Progressive mode, region of interest coding and real time video decoding in PDE-based image compression. Journal of Visual Communication and Image Representation, 31:253– 265, 2015.
[26] P. J. Rousseeuw. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Computational and Applied Mathematics, 20:53–65, 1987.
[27] C. Schmaltz, J. Weickert, and A. Bruhn. Beating the quality of JPEG 2000 with anisotropic diffusion. In Pattern Recognition, volume 5748 of LNCS, pages 452–461. Springer, 2009.
[28] H. Steinhaus. Sur la division des corps matériels en parties. Bull. Acad. Polon. Sci., 12(4):801– 804, 1957.
[29] R. Sundberg. Maximum likelihood theory for incomplete data from an exponential family. Scandinavian Journal of Statistics, 1(2):49–58, 1974.
[30] R. Sundberg. An iterative method for solution of the likelihood equations for incomplete data from exponential families. Communications in Statistics – Simulation and Computation, 5(1):55–64, 1976.
[31] J. H. Ward. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58:236–244, 1963.
[32] A. P. Witkin. Scale-space filtering. In Proc. Eighth International Joint Conference on Artificial Intelligence, volume 2, pages 945–951, 1983.
[2] D. Arthur and S. Vassilvitskii. K-means++: The advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1027–1035. SIAM, 2007.
[3] Z. Belhachmi, D. Bucur, B. Burgeth, and J. Weickert. How to choose interpolation data in images. SIAM Journal on Applied Mathematics, 70(1):333–352, 2009.
[4] A. Bourquard and M. Unser. Anisotropic interpolation of sparse generalized image samples. IEEE Transactions on Image Processing, 22(2):459–472, 2013.
[5] Y. Chen, R. Ranftl, and T. Pock. A bi-level view of inpainting based image compression. Computing Research Repository, 2014. Available from http://arxiv.org/abs/1401.4112v2.
[6] Carl de Boor. Good approximation by splines with variable knots II. In G. Watson, editor, Conference on the Numerical Solution of Differential Equations, volume 363 of Lecture Notes in Mathematics, pages 12–20. Springer, 1974.
[7] L. Demaret and A. Iske. Scattered data coding in digital image compression. In A. Cohen, J.-L. Merrien, and L. L. Schumaker, editors, Curve and Surface Fitting: Saint-Malo 2002, pages 107–117. Nashboro Press, 2003.
[8] L. Demaret and A. Iske. Advances in digital image compression by adaptive thinning. Annals of the MCFA, 3:105–109, 2004.
[9] L. Demaret, A. Iske, and W. Khachabi. Contextual image compression from adaptive sparse data representations. In Rémi Gribonval, editor, Proceedings of SPARS’09 (Signal Processing with Adaptive Sparse Structured Representations Workshop), 2009. Available online: https: //hal.inria.fr/inria-00369491.
[10] I. Galić, J. Weickert, M. Welk, A. Bruhn, A. Belyaev, and H.-P. Seidel. Towards PDE-based image compression. In Variational, Geometric and Level-Set Methods in Computer Vision, volume 3752 of LNCS, pages 37–48. Springer, 2005.
[11] G. Gan, C. Ma, and J. Wu. Clustering: Theory, Algorithms and Applications. SIAM, 2007.
[12] D. Gilbarg and N. Trudinger. Elliptic Partial Differential Equations of Second Order. Springer, 2001.
[13] A. Gordon. Hierarchical classification. In P. Arabie, L. Hubert, and G. Soete, editors, Clustering and Classification, pages 65–121. World Scientific, 1996.
[14] L. Guerra, V. Robles, C. Bielza, and P. Larranaga. A comparison of clustering quality indices using outliers and noise. Intelligent Data Analysis, 16:703–715, 2012.
[15] H. Hamideh. On the optimal knots of first degree splines. Kuwait Journal of Science and Engineering, 29(1):1–13, 2002.
[16] P. S. Heckbert. Color image quantization for frame buffer display. In ACM SIGGRAPH ’82 Proceedings, pages 297–307, 1982.
[17] L. Hoeltgen, S. Setzer, and J. Weickert. An optimal control approach to find sparse data for Laplace interpolation. In Energy Minimization Methods in Computer Vision and Pattern Recognition, volume 8081 of LNCS, pages 151–164. Springer, 2013.
[18] L. Hoeltgen and J. Weickert. Why does non-binary mask optimisation work for diffusion-based image compression? In Energy Minimization Methods in Computer Vision and Pattern Recognition, volume 8932 of LNCS, pages 85–98. Springer, 2015.
[19] D. Liu, X. Sun, F. Wu, S. Li, and Y.-Q. Zhang. Image compression with edge-based inpainting. IEEE Transactions on Circuits, Systems and Video Technology, 7(10):1273–1286, October 2007.
[20] S. P. Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 2(28):129–137, 1982.
[21] M. Mainberger, S. Hoffmann, J. Weickert, C. H. Tang, D. Johannsen, F. Neumann, and B. Doerr. Optimising spatial and tonal data for homogeneous diffusion inpainting. In A. M. Bruckstein, B. M. Haar ter Romeny, A. M. Bronstein, and M. M. Bronstein, editors, Scale Space and Variational Methods in Computer Vision, volume 6667 of LNCS, pages 26–37. Springer, 2012.
[22] J. B. McQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, pages 281–297. University of California Press, 1967.
[23] P. Ochs, Y. Chen, T. Brox, and T. Pock. iPiano: Inertial proximal algorithm for non-convex optimization. SIAM Journal on Imaging Sciences, 7(2):1388–1419, 2014.
[24] P. Peter, S. Hoffmann, F. Nedwed, L. Hoeltgen, and J. Weickert. From optimised inpainting with linear PDEs towards competitive image compression codecs. In T. Bräunl, B. McCane, M. Rivers, and X. Yu, editors, Advances in Image and Video Technology, LNCS. Springer, 2015. To appear.
[25] P. Peter, C. Schmaltz, N. Mach, M. Mainberger, and J. Weickert. Beyond pure quality: Progressive mode, region of interest coding and real time video decoding in PDE-based image compression. Journal of Visual Communication and Image Representation, 31:253– 265, 2015.
[26] P. J. Rousseeuw. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Computational and Applied Mathematics, 20:53–65, 1987.
[27] C. Schmaltz, J. Weickert, and A. Bruhn. Beating the quality of JPEG 2000 with anisotropic diffusion. In Pattern Recognition, volume 5748 of LNCS, pages 452–461. Springer, 2009.
[28] H. Steinhaus. Sur la division des corps matériels en parties. Bull. Acad. Polon. Sci., 12(4):801– 804, 1957.
[29] R. Sundberg. Maximum likelihood theory for incomplete data from an exponential family. Scandinavian Journal of Statistics, 1(2):49–58, 1974.
[30] R. Sundberg. An iterative method for solution of the likelihood equations for incomplete data from exponential families. Communications in Statistics – Simulation and Computation, 5(1):55–64, 1976.
[31] J. H. Ward. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58:236–244, 1963.
[32] A. P. Witkin. Scale-space filtering. In Proc. Eighth International Joint Conference on Artificial Intelligence, volume 2, pages 945–951, 1983.