Ekaterina O. Rybakova

The Hough transform (HT) is widely used in computer vision, tomography, and neural networks. Numerous algorithms for HT computation have been proposed, making their systematic comparison essential. However, existing comparative methodologies are either non-universal and limited to certain HT formulations or task-oriented, relying on application-specific criteria that do not fully capture algorithmic properties. This paper introduces a novel unified methodology for the systematic comparison of HT algorithms. It evaluates key characteristics, including computational complexity, accuracy, and auxiliary space complexity, while explicitly accounting for the property of self-adjointness. The methodology integrates both implementation-level and theoretical considerations related to the interpretation of HT as a discrete approximation of the Radon transform. A set of mathematically justified evaluation functions, not previously described in the literature, is proposed to support our methodology. Importantly, the methodology is universal, applicable across diverse HT paradigms, encompasses pattern-based and Fourier-based fast HT (FHT) algorithms, and offers a comprehensive alternative to existing task-specific methodologies. Its application to several state-of-the-art FHT algorithms ($FHT2DT$, $FHT2SP$, $ASD2$, $KHM$, and Fast Slant Stack) yields new experimentally confirmed theoretical insights, identifies $ASD2$ as the most balanced algorithm, and provides practical guidelines for algorithm selection. In particular, the methodology reveals that for image sizes up to 3000, the maximum normalized computational complexity increases as follows: $FHT2DT$ (1.1), $ASD2$ (15.3), and $KHM$ (30.6), while the remaining algorithms exhibit at least 1.1 times higher values. The maximum orthotropic approximation error equals 0.5 for $ASD2$, $KHM$, and Fast Slant Stack; lies between 0.5 and 1.5 for $FHT2SP$; and reaches 2.1 for $FHT2DT$. In terms of worst-case normalized auxiliary space complexity, the lowest values are achieved by $FHT2DT$ (2.0), Fast Slant Stack (4.0, lower bound), and $ASD2$ (6.8), with all other algorithms requiring at least 8.2 times more memory.

Nowadays, the Hough transform (HT) is a tool extensively used in image processing and computer vision. It finds applications ranging from line detection in images to tomographic reconstruction. Due to their numerous industrial applications, which comprise execution not only on remote servers but also on less powerful embedded devices and within the Internet of Things (IoT) paradigm, fast algorithms for computing the HT (fast HT, or FHT) that efficiently utilize computational memory are in high demand. In-place algorithms, which use memory allocated for the input data array and may employ a small amount of additional memory for intermediate calculations, are recognized to have such characteristics. For images with widths that are powers of two, such an algorithm is known; it is the in-place version of the de facto standard Brady–Yong algorithm. However, in practice, it is often needed to compute the FHT for images with arbitrary widths, to which the Brady–Yong algorithm is not applicable. In this paper, we propose an in-place \(\mathit{FHT}2\mathit{IDS}\) algorithm. It is a modification of the \(\mathit{FHT}2\mathit{DS}\) out-of-place algorithm for computing the FHT for images of arbitrary width previously presented in the literature. We justify correctness of the \(\mathit{FHT}2\mathit{IDS}\) algorithm and show that the result of processing an image of an arbitrary width matches the output of the \(\mathit{FHT}2\mathit{DS}\) algorithm. We demonstrate that the \(\mathit{FHT}2\mathit{IDS}\) algorithm allocates a significantly smaller data array at each recursion step compared to the \(\mathit{FHT}2\mathit{DS}\) algorithm: at each recursion step, it requires an array of size no greater than \(w+h\), rather than \(wh\), assuming that the input image has a \(w\times h\) shape. We also develop a nonrecursive version of the \(\mathit{FHT}2\mathit{IDS}\) algorithm, which is called the \(\mathit{FHT}2\mathit{IDS}\)-\(\mathit{NonRecursive}\) algorithm. The auxiliary space complexity of the \(\mathit{FHT}2\mathit{IDS}\)-\(\mathit{NonRecursive}\) algorithm is proved to be \(\mathcal{O}(w+h)\), while the \(\mathit{FHT}2\mathit{DS}\)-\(\mathit{NonRecursive}\) algorithm, a nonrecursive version of the \(\mathit{FHT}2\mathit{DS}\) algorithm, demonstrates the auxiliary space complexity of \(\mathcal{O}(wh)\), where \(w\) and \(h\) denote the dimensions of the input image. Experimental results show that the \(\mathit{FHT}2\mathit{IDS}\)-\(\mathit{NonRecursive}\) algorithm implemented in C/C\(\texttt{++}\) is 45% faster than its out-of-place counterpart, \(\mathit{FHT}2\mathit{DS}\)-\(\mathit{NonRecursive}\). The \(\mathit{FHT}2\mathit{IDS}\) and \(\mathit{FHT}2\mathit{IDS}\)-\(\mathit{NonRecursive}\) algorithms are also implemented in Python within an open-access adrt library, which the readers may find useful in their research.

Gaussian filtering, being a convolution with a Gaussian kernel, is a widespread technique in image analysis and computer vision applications. It is the traditional approach for noise reduction. In some cases, performing the exact convolution can be computationally expensive and time-consuming. To address this problem, approximations of the convolution are often used to achieve a balance between accuracy and computational efficiency, such as with running sums, Bell blur, Deriche approximation, etc. At the same time, modern computing devices support data parallelism (vectorization) via Single Instruction Multiple Data (SIMD) and can process integer numbers faster than floating-point approaches. In this paper, we describe several methods for approximating a Gaussian filter, implement the SIMD and quantized versions, and compare them in terms of speed and accuracy. The experiments were performed on central processing units with a x86_64 architecture using a family of SSE SIMD extensions and an ARMv8 architecture using the NEON SIMD extension. All the optimized approximations demonstrated 10–20× speedup while maintaining the accuracy in the range of 1 × ${10}^{-5}$ or higher. The fastest method is a trivial Stack blur with a relatively high error, so we recommend using the second-order Vliet–Young–Verbeek filter and quantized Bell blur and running sums as more accurate and still computationally efficient alternatives.