Statistics of the PPHT
- The 3rd step of the PPHT algorithm checks if a bin count exceeds expected noise.
- The count in a bin has a Binomial distribution
- Too computationally intensive to calculate (n choose i)
- We assume the count is distributed as Gaussian with Mean = N*p and standard dev =
- N is the number of input pixels which have voted so far
- p is the probability of choosing a random bin with a particular radius
- Probability of a bin having a given bin count is integral of Gaussian pdf from -infinity to the count
- Generally we would calculate this with standard error function
- Erf is very computationally expensive: We approximate with Stratified Monte Carlo Algorithm
- Consider (2): If the integral from (Mean-2*sigma) exceeds some threshold, a circle is found
- Threshold is a user-specified probability
- We integrate from (Mean-2*sigma) because extending integral to -infinity is the same as choosing a different threshold
Figure #2: Gaussian curve that might be generated during running of PPHT algorithm.
If integral of pdf to the bin count exceeds user-specified value, a circle is found