Volume 31 #3

Contents

1. Development of functional impairments in the lateral geniculate nucleus of di erent hemispheres following early monocular deprivation
2. Eye optics and retinal topography in the Eurasian beaver Castor fiber L.
3. Recognition of projectively transformed planar figures. X. Methods for finding an octet of invariant points of an oval contour – the result of introducing a developed theory into the schemes of oval description
4. Mechanism of oxidative action of light on lipofuscin granules from the retinal pigment epithelium cells of the human eye: the role of superoxide radicals
5. Spatial and temporal integration in the chain of the transduction of olfactory signals
6. Adaptive image brightness stabilization for the industrial system of large moving object recognition
7. Fast binary linear clustering algorithm for small dimensional histograms

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

References:

• 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.