  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 $\Theta(n^2\log n)$ FHT asymptotics
which might suggest that the actual classical Hough transform circuits could
smaller size than $\Theta(n^3/ \log n)$.

Computational Complexity;Computer Vision and Pattern Recognition