danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-8323-2021-65-3-269-274dan-971Research ArticleИНФОРМАТИКАINFORMATICSМногоуровневый алгоритм цветовой кластеризации изображенийMultilevel algorithm for color clustering of imagesЗалесскийБ. А.ZaleskyB. A.

Залесский Борис Андреевич – д-р физ.-мат. наук, заведующий лабораторией

ул. Сурганова, 6, 220012, Минск, Республика Беларусь

Zalesky Boris A. – D. Sc. (Physics and Mathematics), Head of the Laboratory

6, Surganov Str., 220012, Minsk, Republic of Belarus

zalesky@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук БеларусиUnited Institute of Informatics Problems of the National Academy of Sciences of Belarus202115072021653269274Copyright © Залесский Б.А., 20212021Залесский Б.А.Zalesky B.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/971

Представлен многоуровневый алгоритм цветовой кластеризации MACC (Multilevel Algorithm for Color Clustering), предназначенный для быстрой кластеризации изображений. В настоящее время для цветовой кластеризации изображений активно используется несколько хорошо известных алгоритмов, в том числе k-средних (который является одним из наиболее часто используемых при обработке данных) и его нечеткие версии, водораздела, наращивания областей и целая серия новых более сложных нейросетевых и других алгоритмов. Однако их невозможно применять для кластеризации больших цветных изображений в режиме реального времени. Быстрая кластеризации бывает необходима, например, при обработке кадров видеопотока, создаваемого различными видеокамерами или при работе с большими базами данных изображений. Разработанный алгоритм MACC позволяет выполнить на персональном компьютере кластеризацию больших изображений, например размера FullHD, по цвету со средним отклонением от исходных значений цвета около пяти единиц менее, чем за 20 мс, в то время как параллельная версия классического алгоритма k-средних выполняет кластеризацию этих же изображений со средней ошибкой более 12 единиц за время, превышающее 2 с. Предложенный алгоритм многоуровневой кластеризации изображений по цвету достаточно прост в реализации. Он был протестирован на большом количестве цветных изображений.

The fast multilevel algorithm to cluster color images (MACC – Multilevel Algorithm for Color Clustering) is presented. Currently, several well-known algorithms of image clustering, including the k‑means algorithm (which is one of the most commonly used in data mining) and its fuzzy versions, watershed, region growing ones, as well as a number of new more complex neural network and other algorithms are actively used for image processing. However, they cannot be applied for clustering large color images in real time. Fast clustering is required, for example, to process frames of video streams shot by various video cameras or when working with large image databases. The developed algorithm MACC allows the clustering of large images, for example, FullHD size, on a personal computer with an average deviation from the original color values of about five units in less than 20 milliseconds, while a parallel version of the classical k‑means algorithm performs the clustering of the same images with an average error of more than 12 units for a time exceeding 2 seconds. The proposed algorithm of multilevel color clustering of images is quite simple to implement. It has been extensively tested on a large number of color images.

кластеризацияцветные изображениямногоуровневый алгоритмReferencesSteinhaus, H. Sur la division des corps materiels en parties / H. Steinhaus // Bull. Acad. Polon. – 1956. – Vol. 4, N 12. – P. 801–804.Steinhaus H. Sur la division des corps materiels en parties. Bulletin L’Académie Polonaise des Science, 1956, vol. 4, no. 12, pp. 801–804.Lloyd, S. Least squares quantization in PCM / S. Lloyd // IEEE Transactions on Information Theory. – 1982. – Vol. 28, N 2. – P. 129–137. https://doi.org/10.1109/tit.1982.1056489Lloyd S. Least squares quantization in PCM. IEEE Transactions on Information Theory, 1982, vol. 28, no. 2, pp. 129–137. https://doi.org/10.1109/tit.1982.1056489Bezdek, J. C. Pattern Recognition with Fuzzy Objective Function Algoritms / J. C. Bezdek. – MA, USA, 1981. – 256 p. https://doi.org/10.1007/978-1-4757-0450-1Bezdek J. C. Pattern Recognition with Fuzzy Objective Function Algoritms. MA, USA, 1981. 256 p. https://doi.org/10.1007/978-1-4757-0450-1Towards K-means-friendly spaces: simultaneous deep learning and clustering / Bo Yang [et al.] // ICML’17: Proc. of the 34th International Conference on Machine Learning. – 2017. – Vol. 70. – P. 3861–3870.Bo Yang, Xiao Fu, Sidiropoulos N. D., Mingyi Hong. Towards K-means-friendly spaces: simultaneous deep learning and clustering. ICML’17: Proceedings of the 34th International Conference on Machine Learning, 2017, vol. 70, pp. 3861–3870.Fully convolution neural network combined with K-means clustering algorithm for image segmentation / Bing He [et al.] // Tenth International Conference on Digital Image Processing (ICDIP 2018). – 2018. – Vol. 10806. https://doi.org/10.1117/12.2502814Bing He, FengXiang Qiao, Weijun Chen, Ying Wen. Fully convolution neural network combined with K-means clustering algorithm for image segmentation. Tenth International Conference on Digital Image Processing (ICDIP 2018), 2018, vol. 10806. https://doi.org/10.1117/12.2502814Deep k-Means: Re-Training and Parameter Sharing with Harder Cluster Assignments for Compressing Deep Convolutions / Junru Wu [et al.] // Proc. of the 35th International Conference on Machine Learning, PMLR. – 2018. – Vol. 80. – P. 5363–5372.Junru Wu, Yue Wang, Zhenyu Wu, Zhangyang Wang, Ashok Veeraraghavan, Yingyan Lin. Deep k-Means: Re- Training and Parameter Sharing with Harder Cluster Assignments for Compressing Deep Convolutions. Proceedings of the 35th International Conference on Machine Learning, PMLR, 2018, vol. 80, pp. 5363–5372.Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. – М., 2005. – 1075 с.Gonzales R. C., Woods R. E. Digital Image Processing. Forth Edition. Pearson/Prentice-Hall, 2018. 1192 p.Залесский, Б. А. Метод нечеткой кластеризации k-средних со сглаживающей штрафной функцией / Б. А. Залесский // Информатика. – 2014. – № 3. – С. 14–20.Zalesky B. A. Method fuzzy clustering k-means with smoothing penalty function. Informatika = Informatics, 2014, no. 3, pp. 14–20 (in Russian).Image Clustering. 2018 [Electronic resource]. – Mode of access: https://paperswithcode.com/task/image-clustering. – Date of access: 12.04.21.Image Clustering. 2018. Available at: https://paperswithcode.com/task/image-clustering (accessed 12 April 2021).Залесский, Б. А. Алгоритм отслеживания объектов движущейся видеокамерой / Б. А. Залесский // Докл. Нац. акад. наук Беларуси. – 2020. – Т. 64, № 2. – С. 144–149. https://doi.org/10.29235/1561-8323-2020-64-2-144-149Zalesky B. A. Object tracking algorithm by moving camera. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2020, vol. 64, no. 2, pp. 144–149 (in Russian). https://doi.org/10.29235/1561-8323-2020-64-2-144-149

The authors declare that there are no conflicts of interest present.