Analyzing Deviations of Dyadic Lines in Fast Hough Transform
Gleb Smirnov Simon Karpenko
Fast Hough transform is a widely used algorithm in pattern recognition. The
algorithm relies on approximating lines using a specific discrete line model
called dyadic lines. The worst-case deviation of a dyadic line from the ideal
line it used to construct grows as $O(log(n))$, where $n$ is the linear size of
the image. But few lines actually reach the worst-case bound. The present paper
addresses a statistical analysis of the deviation of a dyadic line from its
ideal counterpart. Specifically, our findings show that the mean deviation is
zero, and the variance grows as $O(log(n))$. As $n$ increases, the distribution
of these (suitably normalized) deviations converges towards a normal
distribution with zero mean and a small variance. This limiting result makes an
essential use of ergodic theory.