Generalizing the Brady-Yong Algorithm: Efficient Fast Hough Transform for Arbitrary Image Sizes
The Hough (discrete Radon) transform (HT/DRT) is a digital image processing tool that has become indispensable in many application areas, ranging from general image processing to neural networks and X-ray computed tomography. The utilization of the HT in applied problems demands its computational ef...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10854475/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832575564987236352 |
|---|---|
| author | Danil D. Kazimirov Ekaterina O. Rybakova Vitalii V. Gulevskii Arseniy P. Terekhin Elena E. Limonova Dmitry P. Nikolaev |
| author_facet | Danil D. Kazimirov Ekaterina O. Rybakova Vitalii V. Gulevskii Arseniy P. Terekhin Elena E. Limonova Dmitry P. Nikolaev |
| author_sort | Danil D. Kazimirov |
| collection | DOAJ |
| description | The Hough (discrete Radon) transform (HT/DRT) is a digital image processing tool that has become indispensable in many application areas, ranging from general image processing to neural networks and X-ray computed tomography. The utilization of the HT in applied problems demands its computational efficiency and increased accuracy. The de facto standard algorithm for the fast HT is the Brady-Yong algorithm. However, it is applicable only to images of a power-of-two width. The algorithm that generalizes the Brady-Yong algorithm for non-power-of-two image width with the same asymptotic complexity is known, but it has not been studied neither in terms of the constant in the asymptotics nor in accuracy. Thus, supported both by theory and experiments, generalization of the Brady-Yong algorithm for images of arbitrary size while maintaining asymptotic computational complexity and acceptable accuracy remains of paramount necessity. In this paper, we proposed 5 novel algorithms that incorporate the core idea of the Brady-Yong algorithm and are suitable for computing the fast HT for images of arbitrary size. We investigated the properties of 5 new algorithms, along with one previously proposed algorithm from the literature, through both theoretical analysis and experimental validation. As one of our major contributions, among the proposed algorithms, we singled out a <inline-formula> <tex-math notation="LaTeX">$FHT2DT$ </tex-math></inline-formula> algorithm and proved that it provides a substantial compromise between accuracy and computational complexity. The <inline-formula> <tex-math notation="LaTeX">$FHT2DT$ </tex-math></inline-formula> algorithm is significantly more accurate than the algorithm previously suggested in the literature and, hence, <inline-formula> <tex-math notation="LaTeX">$FHT2DT$ </tex-math></inline-formula> can substitute it in practical applications. During the analysis of the properties of the proposed algorithms, we created a map that characterizes the algorithms based on their accuracy and speed parameters. Users can select the method that best suits their needs — whether prioritizing computational complexity or accuracy — by referring to our map. |
| format | Article |
| id | doaj-art-0983b21a96694b2c9ff3b64b02ea8006 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-0983b21a96694b2c9ff3b64b02ea80062025-01-31T23:04:49ZengIEEEIEEE Access2169-35362025-01-0113201012013210.1109/ACCESS.2025.353440510854475Generalizing the Brady-Yong Algorithm: Efficient Fast Hough Transform for Arbitrary Image SizesDanil D. Kazimirov0https://orcid.org/0009-0004-9469-8389Ekaterina O. Rybakova1Vitalii V. Gulevskii2https://orcid.org/0009-0000-0498-0702Arseniy P. Terekhin3Elena E. Limonova4https://orcid.org/0000-0001-7673-9109Dmitry P. Nikolaev5https://orcid.org/0000-0001-5560-7668Smart Engines Service LLC, Moscow, RussiaSmart Engines Service LLC, Moscow, RussiaFaculty of Mathematics, National Research University Higher School of Economics, Moscow, RussiaInstitute for Information Transmission Problems, Russian Academy of Sciences, Moscow, RussiaSmart Engines Service LLC, Moscow, RussiaSmart Engines Service LLC, Moscow, RussiaThe Hough (discrete Radon) transform (HT/DRT) is a digital image processing tool that has become indispensable in many application areas, ranging from general image processing to neural networks and X-ray computed tomography. The utilization of the HT in applied problems demands its computational efficiency and increased accuracy. The de facto standard algorithm for the fast HT is the Brady-Yong algorithm. However, it is applicable only to images of a power-of-two width. The algorithm that generalizes the Brady-Yong algorithm for non-power-of-two image width with the same asymptotic complexity is known, but it has not been studied neither in terms of the constant in the asymptotics nor in accuracy. Thus, supported both by theory and experiments, generalization of the Brady-Yong algorithm for images of arbitrary size while maintaining asymptotic computational complexity and acceptable accuracy remains of paramount necessity. In this paper, we proposed 5 novel algorithms that incorporate the core idea of the Brady-Yong algorithm and are suitable for computing the fast HT for images of arbitrary size. We investigated the properties of 5 new algorithms, along with one previously proposed algorithm from the literature, through both theoretical analysis and experimental validation. As one of our major contributions, among the proposed algorithms, we singled out a <inline-formula> <tex-math notation="LaTeX">$FHT2DT$ </tex-math></inline-formula> algorithm and proved that it provides a substantial compromise between accuracy and computational complexity. The <inline-formula> <tex-math notation="LaTeX">$FHT2DT$ </tex-math></inline-formula> algorithm is significantly more accurate than the algorithm previously suggested in the literature and, hence, <inline-formula> <tex-math notation="LaTeX">$FHT2DT$ </tex-math></inline-formula> can substitute it in practical applications. During the analysis of the properties of the proposed algorithms, we created a map that characterizes the algorithms based on their accuracy and speed parameters. Users can select the method that best suits their needs — whether prioritizing computational complexity or accuracy — by referring to our map.https://ieeexplore.ieee.org/document/10854475/Brady-Yong algorithmdyadic patternsfast discrete Radon transformfast Hough transform |
| spellingShingle | Danil D. Kazimirov Ekaterina O. Rybakova Vitalii V. Gulevskii Arseniy P. Terekhin Elena E. Limonova Dmitry P. Nikolaev Generalizing the Brady-Yong Algorithm: Efficient Fast Hough Transform for Arbitrary Image Sizes IEEE Access Brady-Yong algorithm dyadic patterns fast discrete Radon transform fast Hough transform |
| title | Generalizing the Brady-Yong Algorithm: Efficient Fast Hough Transform for Arbitrary Image Sizes |
| title_full | Generalizing the Brady-Yong Algorithm: Efficient Fast Hough Transform for Arbitrary Image Sizes |
| title_fullStr | Generalizing the Brady-Yong Algorithm: Efficient Fast Hough Transform for Arbitrary Image Sizes |
| title_full_unstemmed | Generalizing the Brady-Yong Algorithm: Efficient Fast Hough Transform for Arbitrary Image Sizes |
| title_short | Generalizing the Brady-Yong Algorithm: Efficient Fast Hough Transform for Arbitrary Image Sizes |
| title_sort | generalizing the brady yong algorithm efficient fast hough transform for arbitrary image sizes |
| topic | Brady-Yong algorithm dyadic patterns fast discrete Radon transform fast Hough transform |
| url | https://ieeexplore.ieee.org/document/10854475/ |
| work_keys_str_mv | AT danildkazimirov generalizingthebradyyongalgorithmefficientfasthoughtransformforarbitraryimagesizes AT ekaterinaorybakova generalizingthebradyyongalgorithmefficientfasthoughtransformforarbitraryimagesizes AT vitaliivgulevskii generalizingthebradyyongalgorithmefficientfasthoughtransformforarbitraryimagesizes AT arseniypterekhin generalizingthebradyyongalgorithmefficientfasthoughtransformforarbitraryimagesizes AT elenaelimonova generalizingthebradyyongalgorithmefficientfasthoughtransformforarbitraryimagesizes AT dmitrypnikolaev generalizingthebradyyongalgorithmefficientfasthoughtransformforarbitraryimagesizes |