Computational complexity lower bounds of certain discrete Radon transform approximations
This work addresses computational efficiency issues for researchers in image processing and computer vision, but it is incremental as it builds on existing complexity theory to derive specific lower bounds.
The paper tackled the problem of establishing computational complexity lower bounds for discrete Radon transform approximations, specifically for the fast Hough transform and a generic strip pattern class, and obtained an Ω(n² log n) lower bound on operations count for n×n images, implying the asymptotic optimality of the fast Hough transform algorithm.
For the computational model where only additions are allowed, the $Ω(n^2\log n)$ lower bound on operations count with respect to image size $n\times n$ is obtained for two types of the discrete Radon transform implementations: the fast Hough transform and a generic strip pattern class which includes the classical Hough transform, implying the fast Hough transform algorithm asymptotic optimality. The proofs are based on a specific result from the boolean circuits complexity theory and are generalized for the case of boolean $\vee$ binary operation.