# A High-Accuracy Fast Hough Transform with Linear-Log-Cubed Computational Complexity for Arbitrary-Shaped Images

arXiv: https://arxiv.org/abs/2509.00231 · HTML: https://mlsanity.com/paper/2509.00231/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 21 references that are in the map.
- First posted on arXiv 29 Aug 2025.

## Builds on (most cited first, 6 of 6)

- [Computational complexity lower bounds of certain discrete Radon transform approximations](https://mlsanity.com/paper/1801.01054/) (2018)
- [On the use of FHT, its modification for practical applications and the structure of Hough image](https://mlsanity.com/paper/1811.06378/) (2018)
- [Ensemble computation approach to the Hough transform](https://mlsanity.com/paper/1802.06619/) (2018)
- [Vanishing Point Detection with Direct and Transposed Fast Hough Transform inside the neural network](https://mlsanity.com/paper/2002.01176/) (2020)
- [Analyzing Deviations of Dyadic Lines in Fast Hough Transform](https://mlsanity.com/paper/2311.10064/) (2023)
- [Generalization of Brady-Yong Algorithm for Fast Hough Transform to Arbitrary Image Size](https://mlsanity.com/paper/2411.07351/) (2024)

## Abstract (arXiv)

The Hough transform (HT) is a fundamental tool across various domains, from classical image analysis to neural networks and tomography. Two key aspects of the algorithms for computing the HT are their computational complexity and accuracy - the latter often defined as the error of approximation of continuous lines by discrete ones within the image region. The fast HT (FHT) algorithms with optimal linearithmic complexity - such as the Brady-Yong algorithm for power-of-two-sized images - are well established. Generalizations like FHT2DT extend this efficiency to arbitrary image sizes, but with reduced accuracy that worsens with scale. Conversely, accurate HT algorithms achieve constant-bounded error but require near-cubic computational cost. This paper introduces FHT2SP algorithm - a fast and highly accurate HT algorithm. It builds on our development of Brady's superpixel concept, extending it to arbitrary shapes beyond the original power-of-two square constraint, and integrates it into the FHT2DT algorithm. With an appropriate choice of the superpixel's size, for an image of shape w × h, the FHT2SP algorithm achieves near-optimal computational complexity O(wh ln3 w), while keeping the approximation error bounded by a constant independent of image size, and controllable via a meta-parameter. We provide theoretical and experimental analyses of the algorithm's complexity and accuracy.