Share Email Print
cover

Proceedings Paper

Guaranteed convergence of the Hough transform
Author(s): Menashe Soffer; Nahum Kiryati
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

The straight-line Hough Transform using normal parameterization with a continuous voting kernel is considered. It transforms the colinearity detection problem to a problem of finding the global maximum of a two dimensional function above a domain in the parameter space. The principle is similar to robust regression using fixed scale M-estimation. Unlike standard M-estimation procedures the Hough Transform does not rely on a good initial estimate of the line parameters: The global optimization problem is approached by exhaustive search on a grid that is usually as fine as computationally feasible. The global maximum of a general function above a bounded domain cannot be found by a finite number of function evaluations. Only if sufficient a-priori knowledge about the smoothness of the objective function is available, convergence to the global maximum can be guaranteed. The extraction of a-priori information and its efficient use are the main challenges in real global optimization problems. The global optimization problem in the Hough Transform is essentially how fine should the parameter space quantization be in order not to miss the true maximum. More than thirty years after Hough patented the basic algorithm, the problem is still essentially open. In this paper an attempt is made to identify a-priori information on the smoothness of the objective (Hough) function and to introduce sufficient conditions for the convergence of the Hough Transform to the global maximum. An image model with several application dependent parameters is defined. Edge point location errors as well as background noise are accounted for. Minimal parameter space quantization intervals that guarantee convergence are obtained. Focusing policies for multi-resolution Hough algorithms are developed. Theoretical support for bottom- up processing is provided. Due to the randomness of errors and noise, convergence guarantees are probabilistic.

Paper Details

Date Published: 4 January 1995
PDF: 11 pages
Proc. SPIE 2356, Vision Geometry III, (4 January 1995); doi: 10.1117/12.198599
Show Author Affiliations
Menashe Soffer, Technion--Israel Institute of Technology (Israel)
Nahum Kiryati, Technion--Israel Institute of Technology (Israel)


Published in SPIE Proceedings Vol. 2356:
Vision Geometry III
Robert A. Melter; Angela Y. Wu, Editor(s)

© SPIE. Terms of Use
Back to Top