Fast Hough Transform with Linear-Log-Cubed Computational Complexity for High-Accuracy Processing of Arbitrary-Shaped Images
D. D. Kazimirov, D.P. Nikolaev · Problems of Information Transmission · 2025
The Hough transform (HT) is a cornerstone technique applied in fields ranging from classical image processing to cutting-edge neural networks. Its algorithmic implementations are primarily evaluated along two directions: computational complexity and accuracy, where the latter is typically defined as the error of approximation of continuous lines by discrete ones implicitly constructed during the HT algorithm execution. Fast HT (FHT) algorithms with optimal linearithmic complexity are well established—for instance, the Brady–Yong algorithm for images with power-of-two sizes. Extensions such as FHT2DT generalize this efficiency to images of arbitrary shape, but at the expense of accuracy, which deteriorates with increasing image size. On the other hand, HT algorithms that maintain a bounded approximation error achieve higher accuracy but approach near-cubic complexity, making them impractical for large inputs. In this work, we introduce the FHT2SP algorithm, which combines near-optimal speed with high accuracy. Within the FHT2SP algorithm formulation, we extend Brady’s original superpixel definition—applicable solely to square images with power-of-two side lengths—so that it becomes applicable to rectangular images of arbitrary dimensions. Unlike Brady’s definition, which restricted superpixels to square shapes with power-of-two linear size, our superpixel definition permits them to take any rectangular form. The FHT2SP algorithm further incorporates our extended superpixel definition into the $FHT2DT$ algorithm. By carefully selecting the superpixel size, the FHT2SP achieves nearly optimal linear-log-cubed complexity $\Theta(wh\log^3 w)$ for an image of shape $w\times h$ , while guaranteeing a constant approximation error bound $\lambda+1/2$ independent of image size, tunable via the FHT2SP meta-parameter $\lambda\in(0,1]$ . The auxiliary space complexity is shown to be $\Theta(wh\log^2 w)$ . We provide a summary table of experimental results, which can serve as practical guidance for selecting the value of the meta-parameter $\lambda$ to balance accuracy, computational cost, and memory usage.