2024, issue 3, p. 60-66
Received 04.09.2024; Revised 10.09.2024; Accepted 10.09.2024
Published 24.09.2024; First Online 30.09.2024
https://doi.org/10.34229/2707-451X.24.3.6
Lossy Image Compression with Stochastic Quantization
Anton Kozyriev 1 * 
, Vladimir Norkin 1, 2
1 National Technical University of Ukraine ''Igor Sikorsky Kyiv Polytechnic Institute'', Kyiv
2 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. Lossy image compression algorithms play a crucial role in various domains, including graphics, and image processing. As image information density increases, so do the resources required for processing and transmission. One of the most prominent approaches to address this challenge is color quantization, proposed by Orchard et al. (1991). This technique optimally maps each pixel of an image to a color from a limited palette, maintaining image resolution while significantly reducing information content. Color quantization can be interpreted as a clustering problem (Krishna et al. (1997), Wan (2019)), where image pixels are represented in a three-dimensional space, with each axis corresponding to the intensity of an RGB channel.
The purpose of the paper. Scaling of traditional algorithms like K-Means can be challenging for large data, such as modern images with millions of colors. This paper reframes color quantization as a three-dimensional stochastic transportation problem between the set of image pixels and an optimal color palette, where the number of colors is a predefined hyperparameter. We employ Stochastic Quantization (SQ) with a seeding technique proposed by Arthur et al. (2007) to enhance the scalability of color quantization. This method introduces a probabilistic element to the quantization process, potentially improving efficiency and adaptability to diverse image characteristics.
Results. To demonstrate the efficiency of our approach, we present experimental results using images from the ImageNet dataset. These experiments illustrate the performance of our Stochastic Quantization method in terms of compression quality, computational efficiency, and scalability compared to traditional color quantization techniques.
Conclusions. This study introduces a scalable algorithm for solving the color quantization problem without memory constraints, demonstrating its efficiency on a subset of images from the ImageNet dataset. The convergence speed of the algorithm can be further enhanced by modifying the update rule with alternative methods to Stochastic Gradient Descent (SGD) that incorporate adaptive learning rates. Moreover, the stochastic nature of the proposed solution enables the utilization of parallelization techniques to simultaneously update the positions of multiple quants, potentially leading to significant performance improvements. This aspect of parallelization and its impact on algorithm efficiency presents a topic for future research. The proposed method not only addresses the limitations of existing color quantization techniques but also opens up new possibilities for optimizing image compression algorithms in resource-constrained environments.
Keywords: non-convex optimization, stochastic optimization, stochastic quantization, color quantization, lossy compression.
Cite as: Kozyriev A., Norkin V. Lossy Image Compression with Stochastic Quantization. Cybernetics and Computer Technologies. 2024. 3. P. 60–66. https://doi.org/10.34229/2707-451X.24.3.6
References
1. Orchard M.T., Bouman C.A. Color quantization of images. IEEE Transactions on Signal Processing. 1991. 39 (12). P. 2677–2690. https://doi.org/10.1109/78.107417
2. Sharma G., Bala R. Digital color imaging handbook. CRC press, 2017.
3. Krishna K., Ramakrishnan K.R., Thathachar M.A.L. Vector quantization using genetic k-means algorithm for image compression. In Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Theme: Trends in Information Systems Engineering and Wireless Multimedia Communications. 1997. 3. P. 1585–1587. https://doi.org/10.1109/ICICS.1997.652261
4. Lloyd S. Least squares quantization in pcm. IEEE Transactions on Information Theory. 1982. 28 (2). P. 129–137. https://doi.org/10.1109/TIT.1982.1056489
5. Celebi M.E. Improving the performance of k-means for color quantization. Image and Vision Computing. 2011. 29 (4). P. 260–271. https://doi.org/10.1016/j.imavis.2010.10.002
6. Wan X. Application of k-means algorithm in image compression. IOP Conference Series: Materials Science and Engineering. 2019. 563 (5). 052042. https://doi.org/10.1088/1757-899X/563/5/052042
7. Kozyriev A., Norkin V. Robust clustering on high-dimensional data with stochastic quantization. https://arxiv.org/abs/2409.02066 (accessed: 08.09.2024)
8. Kuzmenko V., Uryasev S. Kantorovich–Rubinstein distance minimization: Application to location problems. Springer Optimization and Its Applications. 2019. 149. P. 59–68. https://doi.org/10.1007/978-3-030-22788-3
9. Lakshmanan R., Pichler A. Soft quantization using entropic regularization. Entropy. 2023. 25 (10). 1435. https://doi.org/10.3390/e25101435
10. Russakovsky O., Deng J., Su H. et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision (IJCV). 2015. 115 (3). P. 211–252. https://doi.org/10.1007/s11263-015-0816-y
11. Ermoliev Y.M. Methods of Stochastic Programming. M.: Nauka, 1976. (in Russian)
12. Ermol’ev Yu.M., Norkin V.I. Stochastic generalized gradient method for nonconvex nonsmooth stochastic optimization. Cybernetics and Systems Analysis. 1998. 34 (2). P. 196–215. https://doi.org/10.1007/BF02742069
13. Arthur D., Vassilvitskii S. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’07. Society for Industrial and Applied Mathematics, 2007. P. 1027–1035. ISBN 9780898716245.
14. Harris C.R., Millman K.J., van der Walt S.J. et al. Array programming with NumPy. Nature. 2020. 585 (7825). P. 357–362. https://doi.org/10.1038/s41586-020-2649-2
15. Kozyriev A. Lossy image compression with stochastic quantization, Aug 2024. https://github.com/kaydotdev/sqic (accessed: 08.09.2024)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)