Fast Hough Transform with Linear-Log-Cubed Computational Complexity for High-Accuracy Processing of Arbitrary-Shaped Images
摘要
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