Ensemble computation approach to the Hough transform
This work addresses a theoretical bottleneck in image processing algorithms, offering incremental improvements to known methods like the fast Hough transform.
The paper tackles the computational complexity of the classical Hough transform for digital straight lines, proving an additive complexity upper bound of O(n^3 / log n) on an n×n image using an ensemble computation approach.
It is demonstrated that the classical Hough transform with shift-elevation parametrization of digital straight lines has additive complexity of at most $\mathcal{O}(n^3 / \log n)$ on a $n\times n$ image. The proof is constructive and uses ensemble computation approach to build summation circuits. The proposed method has similarities with the fast Hough transform (FHT) and may be considered a form of the "divide and conquer" technique. It is based on the fact that lines with close slopes can be decomposed into common components, allowing generalization for other pattern families. When applied to FHT patterns, the algorithm yields exactly the $Θ(n^2\log n)$ FHT asymptotics which might suggest that the actual classical Hough transform circuits could smaller size than $Θ(n^3/ \log n)$.