Heteroscedastic Hough transform (HtHT): An efficient method for robust line fitting in the 'errors in the variables' problem

A versatile, systematic, and efficient line-fitting algorithm is presented, accommodating (1) errors in both coordinates ('errors in the variables'), (2) correlation between the noise in the two coordinates (i.e., equal noise density ellipses that are not aligned with the coordinate axes), (3) heter oscedastic noise (different noise covariance matrices for different data po ints), and (4) outliers (achieving robustness by using finite support influ ence functions). The starting point for the analysis is the assumption of a dditive, zero mean, Gaussian measurement noise with point-dependent covaria nce matrix with crossterms. A maximum-likelihood approach is taken. The han dling of outliers is inspired by robust M-estimation. Line fitting is viewe d as a global optimization problem. It is shown that even in the rather gen eral setup considered here, the objective function has a special structure in the normal parameters space, that allows efficient systematic computatio n. The suggested algorithm can be extended to deal with "repulsive" data po ints (from which the line should keep a distance) and with simultaneous fit ting of several lines to the same data set. (C) 2000 Academic Press.