Fast Hough Transform and approximation properties of dyadic patterns
This work provides theoretical guarantees for a low-level computer vision algorithm, which is incremental but important for improving computational efficiency in image processing tasks.
The paper tackles the problem of approximating geometric lines in images using dyadic patterns within the Fast Hough Transform, deriving exact upper bounds on the approximation error, which is proven to be (1/6) log(n) for n x n images as previously conjectured.
Hough transform is a popular low-level computer vision algorithm. Its computationally effective modification, Fast Hough transform (FHT), makes use of special subsets of image matrix to approximate geometric lines on it. Because of their special structure, these subset are called dyadic patterns. In this paper various properties of dyadic patterns are investigated. Exact upper bounds on approximation error are derived. In a simplest case, this error proves to be equal to $\frac{1}{6} log(n)$ for $n \times n$ sized images, as was conjectured previously by Goetz et al.