Finding lines under bounded error

A new algorithm for finding straight lines in images under a bounded error model is described. The algorithm is based on a hierarchical and adaptive subdivision of the space of line parameters. It measures errors in image space and thereby guarantees that no solution satisfying the given error bounds will be lost. The algorithm can find interpretations of all the lines in the image that satisfy the constraint that each image feature supports at most one line hypothesis. It can be extended to compute efficiently the maxima of the probabilistic Hough transform and the generalized Hough transform under a variety of statistical error models.