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.

Еще

Search for segments, fast hough transformation, discrete radon transformation, brady algorithm, fast discrete radon transformation, dyadic pattern, beamlet pyramid

Короткий адрес: https://sciup.org/147232979

IDR: 147232979   |   DOI: 10.14529/mmp200110

Список литературы Acceleration of summation over segments using the fast Hough transformation pyramid

  • Donoho, D.L. Beamlets and Multiscale Image Analysis / D.L. Donoho, Xiaoming Huo. - Berlin: Springer, 2002.
  • Arias-Castro, E. Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods / E. Arias-Castro, D.L. Donoho, Xiaoming Huo // IEEE Transactions on Information Theory. - 2005. - Т. 51, № 7. - С. 2402-2425.
  • Brady, M.L. Fast Parallel Discrete Approximation Algorithms for the Radon Transform / M.L. Brady, Whanki Yong // Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures. - 1992. - C. 91-99.
  • Nikolaev, D.P. Hough Transformation: Underestimated Tool in the Computer Vision Field / D.P. Nikolaev, S.M. Karpenko, I.P. Nikolaev, P.P. Nikolaev // Proceedings of the 22th European Conference on Modelling and Simulation, 3-6 June. - Nicosia, 2008. - T. 238. - C. 246
  • Ershov, E.I Hough Transform and Approximation Properties of Dyadic Patterns / E.I. Ershov, S.M. Karpenko. - 2017. - URL: https://arxiv.1712.05615
  • Khanipov, T.M. Computational Complexity Lower Bounds of Certain Discrete Radon Transform Approximations / T.M. Khanipov. - 2018. - URL: https://arxiv.801.01054
  • Skoryukina, N. Document Localization Algorithms Based on Feature Points and Straight Lines / N. Skoryukina, J. Shemyakina, V.L. Arlazarov, I. Faradzhev // The Tenth International Conference on Machine Vision. - 2018. - V. 10696. - P. 106961H.
  • Aliev, M. On the Use of FHT, Its Modification for Practical Applications and the Structure of Hough Image / M. Aliev, E.I. Ershov, D.P. Nikolaev // International Society for Optics and Photonics. - 2019. - V. 11041. - P. 1104119.
  • Ершов, Е.И. Обобщение быстрого преобразования Хафа для трехмерных изображений / Е.И. Ершов, А.П. Терехин, Д.П. Николаев // Информационные процессы. - 2017. - Т. 17, № 4. - С. 294-308.
  • Сошин, К.В. О быстром поиске сумм по сегментам за счет предподсчета Хаф-пирамид / К.В. Сошин, С.А. Гладилин, Е.И. Ершов // 43 Междисциплинарная школа-конференция ИППИ РАН технологии и системы. - Пермь, 2019.
  • Sheshkus, A. Vanishing Points Detection Using Combination of Fast Hough Transform and Deep Learning / A. Sheshkus, A. Ingacheva, D. Nikolaev // International Society for Optics and Photonics. - 2018. - V. 10696. - C. 106960.
  • Арлазаров, В.Л. Об экономном построении транзитивного замыкания ориентированного графа / В.Л. Арлазаров, Е.А. Диниц, М.А. Кронрод, И.А. Фараджев // Доклады Академии наук СССР. - 1970. - Т. 194, № 3. - C. 487-488.
Еще
Статья научная