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) heteroscedastic noise (different noise covariance matrices for different data points), and (4) outliers (achieving robustness by using finite support influence functions). The starting point for the analysis is the assumption of additive, zero mean, Gaussian measurement noise with point-dependent covariance matrix with crossterms. A maximum-likelihood approach is taken. The handling of outliers is inspired by robust M-estimation. Line fitting is viewed as a global optimization problem. It is shown that even in the rather general setup considered here, the objective function has a special structure in the normal parameters space, that allows efficient systematic computation. The suggested algorithm can be extended to deal with "repulsive" data points (from which the line should keep a distance) and with simultaneous fitting of several lines to the same data set. (C) 2000 Academic Press.