Radiotekhnika
Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS


Тел.: +7 (495) 625-9241

 

Clustering of pixels for a hierarchically structured image

DOI 10.18127/j20700814-201905-05

Keywords:

M.V. Kharinov – Ph.D.(Eng.), Associate Professor, Senior Research Scientist,  St. Petersburg Institute for Informatics and Automation of RAS
E-mail: khar@iias.spb.su


The paper considers the problem of object detecting in the image. For adequate detection of objects, the problem of the total squared error (approximation error) minimizing for image approximations is treated. Effective minimization of the approximation error is achieved by the classical methods of cluster analysis, which are revised in the application to a hierarchically structured image. By hierarchical structuring is meant the separation of whole image pixel set into clusters of pixels packed in image approximations with a different number of colors. The hierarchical structuring of the image is also intended for detecting of the hierarchical sequence (hierarchy) of objects, which provides to take into account the ambiguity of the image and exclude the use of a priori data about objects at the stage of automatic preliminary image processing.
For the Ward's clustering, the necessary parameter is appointed, which is related to the number of visually observable target objects to which a specific detection algorithm is configured. The computational complexity is also estimated when applying the Ward's pixel clustering method to an image in parts. The possibility of high-speed implementation of the Ward method in parts with additional acceleration due to the replacement of the original image pixels with a reduced number of enlarged superpixels is shown.
The hierarchy of pixel clusters that are detected by the computer as possible variants of «objects of interest» is generated during the iterative clustering of pixels using the Ward's method. At the same time, both generation and storage, as well as optimization of the cluster hierarchy, are supported by a data structure in the form of an algebraic network that contains cyclic and acyclic graphs (trees). The network is called algebraic, as it is built using the merging operations of some elementary graphs. The hierarchy of image approximations is described by a convex sequence of approximation errors. This property ensures the correctness of minimizing the approximation error, and for detecting objects, it allows to introduce a measure of heterogeneity (complexity, saliency) for pixels clusters.
Methods to minimize approximation errors are justified analytically. It is shown that the commonly used K-means method, when applied to a hierarchically structured image, loses its effectiveness, as it relies on a coarsened estimate of the approximation error increment when reclassifying sets of pixels from one cluster to another. Therefore, it is useful to replace the K-means method with the more correct method of the approximation error minimizing.
The principles of high-speed computing in terms of an algebraic network, which is divided into cyclic and acyclic graphs (trees) and is formed by a reversible merging of elementary graphs, are discussed. The use of dynamic Sleator–Tarjan trees instead of traditional trees or dendrograms that are generated with the introduction of additional nodes without interconnecting to the pixel coordinates is justified in the paper.

References:
  1. Pattern Recognition and Information Processing. Proc. of the 14th International Conference. Minsk: «Bestprint». 21−23 May 2019. P. 445.
  2. Kurylovich A., Bohush R., Ablameyko S. Video-based Content Detection and Recognition of Bank Cards in iOS Mobile Devices. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 116−119.
  3. Assanovich B., Veretilo Y., Bich N., Pushkina A., Khilmanovich V. Recognition of Genuine Smile as a Factor of Happiness and its Application to Measure the quality of Customer Retail Services. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 84−89.
  4. Lutkovski V., Zheludkovich D., Popleteev A. Multimodal Biometric System for Human Emotion Monitoring. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 90−92.
  5. Zhuk A., Ablameyko S. Automatic detection of discrete object in satellite images using U-NET neural network. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 129−133.
  6. Kachurka A., Ablameyko S. Roads recognition on the Earth surface using artificial neural networks. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 213−216.
  7. Ganchenko V., Doudkin A., Thai Quang Vinh Convolutional Neural Networks for Pattern Recognition on Agriculture Aerial Images. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 224−227.
  8. Stantchik H., Nedzved A., Belotserkovsky A. Shadow description for machine learning algorithms. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 204−210.
  9. Thang Dang N.H., Thanh Li Thi, Dvoenko S., Prasath V.B. Surya, San Nguen Quang Adaptive Thresholding Segmentation Method for Skin Lesion with Normalized Color Channels of NTSC and YCbCr. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 147−151.
  10. Lukashevich M., Starovoitov V. Cell nuclei counting and segmentation for histological image analysis. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 164−168.
  11. Nedzved O., Jin L., Lin W., Ablameyko S., Xu Y. Particle tracking in super resolution cell video. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 134−138.
  12. Spasic S., Subotic S., Visnjic-Jeftic Z., Lenhardt M. Determination of the Development Stage of Erythrocytes In the Common Nase (Chodrostoma nasus) Using Different Classification Methods. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 414−419.
  13. PPAML (Probabilistic Programming for Advanced Machine Learning), DARPA project. 2013−2017. URL = https://galois.com/ project/probabilistic-programming-for-advanced-machine-learning/ (data obrashcheniya 18.05.2019).
  14. Gurevich I., Yashina V. On the interpretability of operations of descriptive image algebras. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 159−163.
  15. Liauchuk V., Kovalev V. Detection of Lung Pathologies Using Deep Convolutional Neural Networks. 14th International Conference Pattern Recognition and Information Processing (PRIP’2019). Minsk: «Bestprint». 21−23 May 2019. P. 275−277.
  16. Ward Jr J.H. Hierarchical grouping to optimize an objective function. Journal of the American statistical association. 1963. V. 58. № 301. P. 236−244.
  17. Mandel I.D. Klasternyi analiz. M.: Finansy i statistika. 1988. 176 s. (In Russian).
  18. Aivazyan S.A., Bukhshtaber V.M., Enyukov I.S., Meshalkin L.D. Prikladnaya statistika: Klassifikatsiya i snizhenie razmernosti. M.: Finansy i statistika. 1989. 607 s. (In Russian).
  19. Malashin R.O. Metody strukturnogo analiza izobrazhenii trekhmernykh stsen. SPb. 2014. 22 s. (In Russian).
  20. Favorskaya M.N., Proskurin A.V. Kategorizatsiya stsen na osnove rasshirennykh tsvetovykh deskriptorov. Trudy SPIIRAN. 2015. T. 3. № 40. S. 203−220. (In Russian).
  21. Achanta R., Shaji A., Smith K., Lucchi A., Fua P., Susstrunk S. SLIC superpixels compared to state-of-the-art superpixel methods. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2012. V. 34. № 11. P. 2274−2282.
  22. Achanta R., Hemami S., Estrada F., Susstrunk S. Frequency-tuned salient region detection. IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2009. P. 1597−1604.
  23. Cheng M.M., Mitra N.J., Huang X., Torr P.H., Hu S.M. Global contrast based salient region detection. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2015. V. 37. № 3. P. 569−582.
  24. Chochia P.A. Teoriya i metody obrabotki videoinformatsii na osnove dvukhmasshtabnoi modeli izobrazheniya. M.: IPPI RAN. 2016. 302 s. (In Russian).
  25. Dvoenko S.D. Meanless k-means as k-meanless clustering with the bi-partial approach. 12th International Conference Pattern Recognition and Information Processing (PRIP’20114). Minsk. 2014. P. 50−54.
  26. Kharinov M.V. Model of the quasi-optimal hierarchical segmentation of a color image. Journal of Optical Technology. 2015. V. 82. № 7. P. 425−429.
  27. Kharinov M.V. Pixel Clustering for Color Image Segmentation. Programming and Computer Software. 2015. V. 41. № 5. P. 258−266.
  28. Sleator D.D., Tarjan R.E. Self-Adjusting Binary Search Trees. Journal of the ACM. 1985. V. 32. № 3. P. 652−686.
  29. Rylov S.A. Metody i algoritmy segmentatsii multispektralnykh sputnikovykh izobrazhenii vysokogo prostranstvennogo razresheniya. Novosibirsk: Sibirskii gos. un-t geosistem i tekhnologii. 2016. 135 s. (In Russian).
  30. Gashnikov m.v., Glumov N.I., Ilyasova N.Yu., Myasnikov V.V., Popov S.B., Sergeev V.V., Soifer V.A., KHramov A.G., Chernov A.V., Chernov V.M., Chicheva M.A., Fursov V.A. Metody kompyuternoi obrabotki izobrazhenii. M.: Fizmatlit. 2001. 784 s. (In Russian).
June 24, 2020
May 29, 2020

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio