Acceleration of Summation Over Segments Using the Fast Hough Transformation Pyramid

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; discrete Radon transformation; Brady algorithm; fast discrete Radon transformation; dyadic pattern; beamlet pyramid.

References

1. Donoho D.L., Huo X. Beamlets and Multiscale Image Analysis. Berlin, Springer, 2002.
2. Arias-Castro E. Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods. IEEE Transactions on Information Theory, 2005, vol. 51, no. 7, pp. 2402-2425
3. Brady M.L., Yong W. Fast Parallel Discrete Approximation Algorithms for the Radon Transform. Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, 1992, pp. 91-99.
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, Cyprus, 2008, vol. 238, pp. 246. DOI:10.7148/2008-0238
5. Ershov E.I., Karpenko S.M. Transform and Approximation Properties of Dyadic Patterns. Available at: arxiv.1712.05615.
6. Khanipov T.M. Computational Complexity Lower Bounds of Certain Discrete Radon Transform Approximations. 2018, Available at: 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, Austria, vol. 10696, pp. 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, The Netherlands, 2019, vol. 11041, pp. 1104119. DOI: 10.1117/12.2522803
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, 2018, vol. 63, no. 6, pp. 626-636
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 Mezhdistsiplinarnaya shkola-konferentsiya IPPI RAN 'Informatsionnye tekhnologii i sistemy' [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. International Society for Optics and Photonics, 2018, vol. 10696. pp. 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]. Reports of the Academy of Sciences of the USSR, 1970, vol. 194, no. 3, pp. 487-488. (in Russian)