Acceleration of Summation Over Segments Using the Fast Hough Transformation Pyramid

В работе предложен алгоритм быстрого приближенного вычисления на изображении сумм по произвольным отрезкам, задаваемым парой пикселей. Используя результаты промежуточных вычислений быстрого преобразования Хафа, предложенный алгоритм позволяет рассчитать сумму по произвольному отрезку линии с логарифмической сложностью, зависящей от линейного размера исходного изображения. Предподсчет реализован как модификация алгоритма Брейди быстрой суммации по диадическим аппроксимациям прямых. При таком подходе ключевым элементом алгоритма является поиск диадической прямой, проходящей через два данных пикселя. В работе предложен алгоритм решения этой задачи, не ухудшающий общую асимптотику, для него доказана корректность. Также в работе описывается обобщение этого подхода на трехмерный случай для отрезков и для сегментов плоскостей.

Ключевые слова

поиск отрезков; быстрое преобразование Хафа; дискретное преобразование Радона; алгоритм Брейди; быстрое дискретное преобразование Радона; диадический паттерн; бимлет-пирамида.

Литература

1. Donoho, D.L. Beamlets and Multiscale Image Analysis / D.L. Donoho, X. Huo. - Berlin: Springer, 2002.
2. Arias-Castro, E. Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods / E. Arias-Castro, D.L. Donoho, X. Huo // IEEE Transactions on Information Theory. - 2005. - Т. 51, № 7. - С. 2402-2425.
3. Brady, M.L. Fast Parallel Discrete Approximation Algorithms for The Radon Transform / M.L. Brady, W. Yong // Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures. - 1992 - C. 91-99.
4. 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, Cyprus. - 2008. - T. 238 - C. 246
5. Ershov, E.I Hough Transform and Approximation Properties of Dyadic Patterns / E.I. Ershov, S.M. Karpenko. - 2017. - URL: arxiv.1712.05615.
6. Khanipov, T.M. Computational Complexity Lower Bounds of Certain Discrete Radon Transform Approximations / T.M. Khanipov. - 2018. - URL: arxiv.801.01054.
7. 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.
8. 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. - T. 11041. - P. 1104119.
9. Ершов, Е.И. Обобщение быстрого преобразования Хафа для трехмерных изображений / Е.И. Ершов, А.П. Терехин, Д.П. Николаев // Информационные процессы. - 2017. - Т. 17, № 4. - С. 294-308.
10. Сошин, К.В. О быстром поиске сумм по сегментам за счет предподсчета Хаф-пирамид / К.В. Сошин, С.А. Гладилин, Е.И. Ершов // 43 междисциплинарная школа-конференция ИППИ РАН 'Информационные технологии и системы', Пермь. - 2019.
11. 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.
12. Арлазаров, В.Л. Об экономном построении транзитивного замыкания ориентированного графа / В.Л. Арлазаров, Е.А. Диниц, М.А. Кронрод, И.А. Фараджев // Доклады Академии Наук СССР. - 1970. - Т.194, № 3. - C. 487-488.