• 2021 (Vol.35)

Fast binary linear clustering algorithm for small dimensional histograms

© 2017 E. I. Ershov

Institute for Information Transmission Problems RAS 127051 Moscow, Bolshoi Karetny per., 19

Received 10 Mar 2017

In this paper we propose linear separation algorithm for pairs of clusters in two- or three-dimensional space. Optimal separation criterion is the algorithm’s input parameter. The algorithm is based on combination of fast Hough transform, cumulative summation and criteria computation via additive statistics. Hence, the possibility of criterion expression in terms of additive statistics is a limitation of the algorithm. We show that computational complexity of the proposed algorithm is O(mn2 log n) for two-dimensional case and O(mn3 log n) for three-dimensional case, where n is a linear image size, while m is a number of the required additive statistics. In practice dimensionality of input histograms is restricted by the requirement of histogram dense representation in RAM.

Key words: fast Hough transform, image segmentation, linear clustering, Ótsu criterion, additive statistics

Cite: Ershov E. I. Algoritm bystroi binarnoi lineinoi klasterizatsii malomernykh gistogramm [Fast binary linear clustering algorithm for small dimensional histograms]. Sensornye sistemy [Sensory systems]. 2017. V. 31(3). P. 261-269 (in Russian).


  • Ankerst M., Breunig M.M., Kriegel H.-P., Sander J. OPTICS: Ordering points to identify the clustering structure // Proc. ACM SIGMOD Int. Conf on Management of data. 1999. P. 49–60.
  • Dempster A.P., Laird N.M., Rubin D. B. Maximum likelihood from incomplete data via the EM algorithm // J. Royal Statistical Society, Series B (Methodological). 1977. V. 39. No 1. P. 1–38.
  • Ershov E., Terekhin A., Karpenko S., Nikolaev D., Postnikov V. Fast 3D Hough Transform computation // Proc. 30th Europ. Conf. Model. Simul. 2016. P. 227–230.
  • Ershov E.I., Terekhin A.P., Postnikov V.V., Nikolaev D.P. Exact fast algorithm for optimal linear Separation of 2D distribution // Proc. 29th Europ. Conf. Model. Simul. 2015. P. 469–474.
  • Ester M., Kriegel H.-P., Sander J., Xu X. A density-based algorithm for discovering clusters in large spatial databases with noise // Proc. Second Int. Conf. Knowledge Discovery and Data Mining. 1996. P. 226–231.
  • Gong J., Li L., Chen W. Fast recursive algorithms for two-dimensional thresholding // Patt. Recogn. 1998. V. 31. No 3. P. 295–300.
  • Jianzhuang L., Wenqing L., Yupeng N. Automatic thresholding of gray-level pictures using two-dimension Otsu method // China Int. Conf. Circuits and Systems. 1991. P. 325–327.
  • Li L., Gong R., Chen W. Gray level image thresholding based on sher linear projection of two-dimensional histogram // Patt. Recogn. 1997. V. 30. No. 5. P. 743–749.
  • Nikolaev D.P., Karpenko S.M., Nikolaev I.P., Nikolaev P.P. Hough transform: underestimated tool in the computer vision eld // Proc. 22th Europ. Conf. Model. Simul. 2008. V. 238.
  • Ótsu N. A threshold selection method from gray-level histograms // IEEE transactions on systems, man, and cybernetics. 1979. V. 9. No 1. P. 62–66.
  • Rokach L., Maimon O. Clustering methods // Data mining and knowledge discovery handbook. Springer US. 2005. 321–352.
  • Steinhaus H. Sur la division des corps materiels en parties // Bull. Acad. Polon. Sci. 1956. V. 4 (C1.III). P. 801–804.
  • Ye Z., Hu Z., Lai X., Chen H. Image segmentation using thresholding and swarm intelligence // Jour. Soft. 2012. V. 7. No 5. P. 1074–1082.