Geodesic
Acceleration of summation over segments using the fast Hough transformation pyramid
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 13 (2020) no. 1, pp. 129-140 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper, we propose an algorithm for fast approximate calculation of the sums over arbitrary segments given by a pair of pixels in the image. Using the results of intermediate calculations of the fast Hough transform, the proposed algorithm allows to calculate the sum over arbitrary line segment with a logarithmic complexity depending on the linear size of the original image (also called fast discrete Radon transform or Brady transform). In this approach, the key element of the algorithm is the search for the dyadic straight line passing through two given pixels. We propose an algorithm for solving this problem that does not degrade the general asymptotics. We prove the correctness of the algorithm and describe a generalization of this approach to the three-dimensional case for segments of straight lines and of planes.
Keywords: search for segments, fast Hough transformation, Brady algorithm, dyadic pattern, beamlet pyramid.
Mots-clés : discrete Radon transformation, fast discrete Radon transformation 
@article{VYURU_2020_13_1_a9,
     author = {K. V. Soshin and D. P. Nikolaev and S. A. Gladilin and E. I. Ershov},
     title = {Acceleration of summation over segments using the fast {Hough} transformation pyramid},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {129--140},
     year = {2020},
     volume = {13},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2020_13_1_a9/}
}
TY  - JOUR
AU  - K. V. Soshin
AU  - D. P. Nikolaev
AU  - S. A. Gladilin
AU  - E. I. Ershov
TI  - Acceleration of summation over segments using the fast Hough transformation pyramid
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2020
SP  - 129
EP  - 140
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VYURU_2020_13_1_a9/
LA  - en
ID  - VYURU_2020_13_1_a9
ER  - 
%0 Journal Article
%A K. V. Soshin
%A D. P. Nikolaev
%A S. A. Gladilin
%A E. I. Ershov
%T Acceleration of summation over segments using the fast Hough transformation pyramid
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2020
%P 129-140
%V 13
%N 1
%U http://geodesic.mathdoc.fr/item/VYURU_2020_13_1_a9/
%G en
%F VYURU_2020_13_1_a9
K. V. Soshin; D. P. Nikolaev; S. A. Gladilin; E. I. Ershov. Acceleration of summation over segments using the fast Hough transformation pyramid. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 13 (2020) no. 1, pp. 129-140. http://geodesic.mathdoc.fr/item/VYURU_2020_13_1_a9/

[1] Donoho D. L., Xiaoming Huo, Beamlets and Multiscale Image Analysis, Springer, Berlin, 2002 | MR | Zbl

[2] Arias-Castro E., Donoho D. L., Xiaoming Huo, “Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods”, IEEE Transactions on Information Theory, 51:7 (2005), 2402–2425 | DOI | MR | Zbl

[3] Brady M. L., Whanki Yong, “Fast Parallel Discrete Approximation Algorithms for the Radon Transform”, Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, 1992, 91–99 | DOI

[4] Nikolaev D. P., Karpenko S. M., Nikolaev T. P., Nikolaev P. P., “Hough Transform: Underestimated Tool in the Computer Vision Field”, Proceedings of the 22th European Conference on Modelling and Simulation (3–6 June, Nicosia, 2008), 238–243 | DOI

[5] Ershov E. I., Karpenko S. M., Transform and Approximation Properties of Dyadic Patterns, 2017, arXiv: 1712.05615

[6] Khanipov T. M., Computational Complexity Lower Bounds of Certain Discrete Radon Transform Approximations, 2018, arXiv: 1801.01054

[7] Skoryukina N., Shemyakina J., Arlazarov V. L., Faradzhev I., “Document Localization Algorithms Based on Feature Points and Straight Lines”, The Tenth International Conference on Machine Vision (13–16 April, Vienna, 2018), Proc. SPIE, 10696, 106961H

[8] Aliev M., Ershov E. I., Nikolaev D. P., “On the Use of FHT, Its Modification for Practical Applications and the Structure of Hough Image”, Eleventh International Conference on Machine Vision (16–18 November, Amsterdam, 2019), Proc. SPIE, 11041, 1104119 | DOI

[9] Ershov E. I., Terekhin A. P., Nikolaev D. P., “Generalization of the Fast Hough Transform for Three-Dimensional Images”, Journal of Communications Technology and Electronics, 63:6 (2018), 626–636 | DOI

[10] Soshin K. V., Gladilin S. A., Ershov E. I., “About Fast Search Sums Through Segments on the Image With Pre-Calculated Hough-Pyramid”, 43-rd Interdisciplinary School-Conference IITP RAS “Information Technolgies and Systems” (Perm, 2019) (in Russian)

[11] Sheshkus A., Ingacheva A., Nikolaev D., “Vanishing Points Detection Using Combination of Fast Hough Transform and Deep Learning”, Proc. SPIE, 10696, 2018, 106960

[12] Arlazarov V. L., Dinits E. A., Kronrod M. A., Faradzhev I. A., “On Economical Construction of The Transitive Closure of a Directed Graph”, Doklady Academii Nauk, 194:3 (1970), 487–488 (in Russian) | MR | Zbl