On a Fast Hough/Radon Transform as a Compact Summation Scheme over Digital Straight Line Segments

Dmitry Nikolaev (), Egor Ershov, Alexey Kroshnin, Elena Limonova (), Arseniy Mukovozov and Igor Faradzhev
Additional contact information
Dmitry Nikolaev: Institute for Information Transmission Problems RAS, 127051 Moscow, Russia
Egor Ershov: Institute for Information Transmission Problems RAS, 127051 Moscow, Russia
Alexey Kroshnin: Institute for Information Transmission Problems RAS, 127051 Moscow, Russia
Elena Limonova: Smart Engines Service LLC, 117312 Moscow, Russia
Arseniy Mukovozov: Smart Engines Service LLC, 117312 Moscow, Russia
Igor Faradzhev: Smart Engines Service LLC, 117312 Moscow, Russia

Mathematics, 2023, vol. 11, issue 15, 1-22

Abstract: The Hough transform, interpreted as the discretization of the Radon transform, is a widely used tool in image processing and machine vision. The primary way to speed it up is to employ the Brady–Yong algorithm. However, the accuracy of the straight line discretization utilized in this algorithm is limited. In this study, we propose a novel algorithm called A S D 2 that offers fast computation of the Hough transform for images of arbitrary sizes. Our approach adopts a computation scheme similar to the Brady–Yong algorithm but incorporates the best possible line discretization for improved accuracy. By employing the Method of Four Russians, we demonstrate that for an image of size n × n where n = 8 q and q ∈ N , the computational complexity of the A S D 2 algorithm is O ( n 8 / 3 ) when summing over O ( n 2 ) digital straight line segments.

Keywords: fast Hough transform; fast discrete Radon transform; digital straight lines (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/15/3336/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/15/3336/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:15:p:3336-:d:1206207

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().