4 January 1995 Guaranteed convergence of the Hough transform
Author Affiliations +
Proceedings Volume 2356, Vision Geometry III; (1995); doi: 10.1117/12.198599
Event: Photonics for Industrial Applications, 1994, Boston, MA, United States
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.
© (1995) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Menashe Soffer, Nahum Kiryati, "Guaranteed convergence of the Hough transform", Proc. SPIE 2356, Vision Geometry III, (4 January 1995); doi: 10.1117/12.198599; https://doi.org/10.1117/12.198599
PROCEEDINGS
11 PAGES


SHARE
KEYWORDS
Hough transforms

Vision geometry

Statistical modeling

Algorithm development

Quantization

Data modeling

Image analysis

Back to Top