Analyzing Deviations of Dyadic Lines in Fast Hough Transform
This provides a statistical understanding of deviations for pattern recognition applications, but it is incremental as it builds on known worst-case bounds.
The paper tackles the problem of analyzing deviations of dyadic lines from ideal lines in the Fast Hough Transform, finding that the mean deviation is zero, variance grows as O(log(n)), and the distribution converges to a normal distribution as n increases.
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.