提出一种高精度快速霍夫变换算法，支持任意形状图像。
A High-Accuracy Fast Hough Transform with Linear-Log-Cubed Computational Complexity for Arbitrary-Shaped Images
- 基于超像素思想扩展至任意形状图像，融合高效算法框架
- 计算复杂度近似 O(wh ln³w)，误差恒定且可控
- 适合对精度和速度都有要求的图像分析任务
霍夫变换（HT）是图像分析、神经网络和断层成像等多个领域的基础工具。计算HT的算法需兼顾计算复杂度与精度——后者常定义为连续直线在离散图像区域中的近似误差。现有快速霍夫变换（FHT）算法如Brady-Yong适用于2的幂次尺寸图像，具有最优线性对数复杂度；而扩展至任意尺寸的FHT2DT虽保持效率但精度随尺度下降。相反，高精度算法虽能保证误差有界，但计算成本接近立方级。本文提出FHT2SP算法：基于我们发展的Brady超像素概念，将其推广至非2的幂次任意形状图像，并融入FHT2DT框架。对于大小为w×h的图像，该算法实现近似最优复杂度O(wh ln³w)，同时将近似误差控制在与图像尺寸无关的常数范围内，且可通过元参数调节。本文提供了算法复杂度与精度的理论与实验分析。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。