标题： 一种针对任意形状图像的高精度快速霍夫变换，具有线性对数立方计算复杂度 显示英文标题

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

摘要： 霍夫变换（HT）是多个领域中的基本工具，从经典的图像分析到神经网络和断层扫描。 计算HT的算法的两个关键方面是其计算复杂性和准确性——后者通常定义为在图像区域内由离散线近似连续线的误差。 具有最优线性对数复杂度的快速HT（FHT）算法，如针对大小为2的幂次的图像的Brady-Yong算法，已经得到广泛认可。 像$FHT2DT$这样的推广将这种效率扩展到任意图像尺寸，但准确性会降低，并且随着尺度增大而恶化。 相反，准确的HT算法可以实现常数有界误差，但需要接近立方的计算成本。 本文介绍了$FHT2SP$算法——一种快速且高度准确的HT算法。 它基于我们对Brady的超像素概念的发展，将其扩展到原始的2的幂次平方约束之外的任意形状，并将其集成到$FHT2DT$算法中。 选择适当的超像素大小，对于形状为$w \times h$的图像，$FHT2SP$算法实现了接近最优的计算复杂度$\mathcal{O}(wh \ln^3 w)$，同时保持近似误差由与图像大小无关的常数限制，并可通过一个元参数进行控制。 我们提供了该算法的复杂性和准确性的理论和实验分析。 显示英文摘要

摘要： 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.