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.
