{"ID":2876907,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.00231","arxiv_id":"2509.00231","title":"A High-Accuracy Fast Hough Transform with Linear-Log-Cubed Computational Complexity for Arbitrary-Shaped Images","abstract":"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 \\times h$, the $FHT2SP$ algorithm achieves near-optimal computational complexity $\\mathcal{O}(wh \\ln^3 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.","short_abstract":"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 d...","url_abs":"https://arxiv.org/abs/2509.00231","url_pdf":"https://arxiv.org/pdf/2509.00231v1","authors":"[\"Danil Kazimirov\",\"Dmitry Nikolaev\"]","published":"2025-08-29T20:49:51Z","proceeding":"cs.CV","tasks":"[\"cs.CV\"]","methods":"[]","has_code":false}