Robust detection of lines using the progressive probabilistic Hough transform

In the paper we present the progressive probabilistic Hough transform (PPHT ). Unlike the probabilistic HT, where the standard HT is performed on a pre selected fraction of input points, the PPHT minimizes the amount of computa tion needed to detect lines by exploiting the difference in the fraction of votes needed to reliably detect lines with different numbers of supporting points. The fraction of points used for voting need not be specified ad ho c or using a priori knowledge, as in the probabilistic HT; it is a function of the inherent complexity of data. The algorithm is ideally suited for re al-time applications with a fixed amount of available processing time, sinc e voting and line detection are interleaved. The most salient features are likely to be detected first. While retaining its robustness, experiments sh ow that the PPHT has, in many circumstances, advantages over the standard H T. (C) 2000 Academic Press.