Simulation modeling of the clustering problem solution using the Mean Shift method

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

The article describes the implementation of the Mean Shift data clustering algorithm based on the data flow computing system, which provides maximum parallelization of calculations. The description of an algorithm adapted for execution on a dataflow computing system, an algorithm for generating a computational grid, is given. the architecture of the computer system, the implementation of its simulation model, the results of simulation modeling, evaluation of the main parameters of the computer system.

About the authors

S. M. Salibekyan

National Research University Higher School of Economics

Author for correspondence.
Email: ssalibekyan@hse.ru

Cand. Sc., Assistant Professor

Russian Federation, Moscow, 101000

References

  1. Milutinovic V., Salom J., Veljovic D., Korolija N., Markovic D., Petrovic L. DataFlow Supercomputing Essentials, Research, Development and Education, Springer, 2017, 150 p.
  2. Milutinovic V., Trifunovic N., Salom J., Giorgi R. The guide to dataflow supercomputing, USA, Springer, 2015, available at: https://proxylibrary.hse.ru:2084/content/pdf/10.1007%2F978-3-319-16229-4.pdf.
  3. Salibekyan S. M., Panfilov P. B. Issues in automata network modeling of dataflow computing systems, Informacionnye tekhnologii i vychislitel’nye sistemy, 2015, no. 1, pp. 3—9 (in Russian).
  4. Panfilov P. B., Salibekyan S. M. A New Approach for Distributed Computing in Embedded Systems, Procedia Engineering , 2015, vol. 100, pp. 977—986. available at: http://www.scien-cedirect.com/science/article/pii/S187770581500484.
  5. Panfilov P. B., Salibekyan S. M. Modeling of a supercomputer computing system of object-attribute architecture with data flow control, Informacionnye tekhnologii i vychislitel’nye sistemy, 2013, no. 1, pp. 3—10 (in Russian).
  6. Tyurin A. G., Zuyev I. O. Cluster analysis, methods and algorithms of the clustering, Vestnik MGTU MIREA, 2014, no. 2, pp. 86—97 (in Russian).
  7. Comaniciu D., Meer P. Mean Shift: A Robust Approach Toward Feature Space Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, pp. 603—619.
  8. Kim E., Wang W., Li H., Huang X. A parallel annealing methods for automatic color cervigram image segmentation, available at: http://edwardkim.net/publications/edkim_miccaigpu2009.pdf.
  9. Klaus A., Sormann M., Karner K. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure, ICPR 2006, available at: http://old.vrvis.at/2d3d/technology/stereomatching/images/segment-based-stereomatching.pdf.
  10. Wang Z., Zheng Z. A region based stereo matching algorithm using cooperative optimization, CVPR, 2008, available at: http://vision.middlebury.edu/stereo/eval/papers/CORegion.pdf.
  11. Medvedev M. Y., Lazarev V. S. A path planning method for a moving object group using clustering in a two-dimensional environment, Nauchnyj vestnik Novosibirskogo gosudarstvennogo tekhnicheskogo universiteta, 2019, no. 4(77). pp. 45—54, doi: 10.17212/1814-1196-2019-4-45-54, EDN FVNLJV (in Russian).
  12. Skvorcov A. V. Delaunay triangulation and its application, Tomsk, Publishing house of Tomsk university, 2002, 128 p. (in Russian).
  13. Levin B. A., Rosenberg I. N., Tsvetkov V. Y. Modeling of the basic relief based on Delaunay triangulation, Railway Science and Technology, 2018, vol. 2, no. 1 (5), pp. 3—15.
  14. Zheleznyakova A. L., Surzhikov S. T. A Molecular dynamics-based triangulation of multiple nurbs-surfaces for complex products of the aviation and space-rocket industry, Fiziko-himicheskaya kinetika v gazovoj dinamike, 2014, vol. 15, no 1, pp. 6, EDN UAHFHZ (in Russian).
  15. Rebay S. Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm, Journal of Computational Physics, May 1993, vol. 106, iss. 1, p. 127.
  16. Skvorcov A. V., Mirza N. S. Algorithms for constructing and analyzing triangulation, Tomsk, Publishing house of Tomsk university, 2006, 168 p., EDN SBVWBL (in Russian).
  17. Batenkov A. A., Man’yakov Yu. A., Gasilov A. V., Yakovlev O. A. Mathematical model of optimal triangulation, Informatika i ee primeneniya, 2018, vol. 12, no. 2, pp. 69—74, doi: 10.14357/19922264180210, EDN USPXIK (in Russian).
  18. Salibekyan S. M., Panfilov P. B. Object-attribute architecture is a new approach to object systems developing, Informacionnye Tehnologii, 2012, no. 2, pp. 8—14 (in Russian).
  19. Salibekyan S. M., Vishnekov A., Ivanova E. Methodology of Mean Shift Clustering Algorithm Implementation Based on Dataflow Computer, Proceedings of 2019 XVI International Symposium "Problems of Redundancy in Information and Control Systems" (REDUNDANCY)б IEEE, 2019б pp. 177—180, doi: 10.1109/REDUNDANCY48165.2019.9003312.
  20. Salibekyan S. M. High-level Language Translation Controlled by Dataflow, Informacionnye Tehnologii, 2024, vol. 30, no. 4, pp. 261—268 (in Russian).
  21. Cormen T., Leiserson Ch., Rivest R., Klifford Sh. Introduction to Algorithms, Moscow, Sankt-Peterburg, Dialektika, 2019, 1323 p. (in Russian).

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Informacionnye Tehnologii


СМИ зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор).
Регистрационный номер и дата принятия решения о регистрации СМИ: серия ПИ № 77 - 15565 от 02 июня 2003 г.