AN OPTIMIZING LINE FINDER USING A HAUGH TRANSFORM ALGORITHM

In this paper we present an optimization algorithm for locating peaks in the accumulator of the Hough algorithm with robust voting kernel. W e present a detailed discussion of the accuracy that can be achieved b y locating these peaks in the accumulator, and show that the error bou nds on the estimates of line parameters are always within those based upon least squares. This arises from the robust nature of the voting k ernel. We describe the optimization algorithm in some detail since the shape of the peaks in the standard parameter space for straight lines are sinusoidal ridges. Standard approaches therefore fail, but the me thod described is shown to be robust from the experimental results pre sented. Some discussion of postprocessing is also made, in which the s hortcomings of standard Hough techniques, splitting long lines across parameter bins, can be remedied. We also discuss the use of a confiden ce measure in the line parameters based upon the value of the accumula tor, and show that this is related to the mean squared distance from t he line of the edge pixels associated with it. Finally, we present res ults produced by this optimizing Hough technique on a disparate set of images, with various application areas in mind, to demonstrate the ve rsatility of the method and the accuracy that can be achieved at littl e computational overhead. (C) 1997 Academic Press.