Robust Statistical methods (such as LMedS and LTS) were first introduced in computer vision to improve the performance of feature extraction algorithms. One attractive feature of traditional robust statistical methods is that they can tolerate up to half of the data points that do not obey the assumed model (i.e., they can be robust to up to 50% contamination). However, they can break down at unexpectedly lower percentages when the outliers are clustered; also, they cannot tolerate more than 50% outliers. This is because that these methods measure only one single statistic: for example, the least median of residuals (for LMedS) or the least sum of trimmed squared of residuals (for LTS), omitting other characteristics of the data. We realised that there are two possible ways to improve the robustness of the methods: (i) to take advantage of special information in the data (e.g., symmetry); (ii) to take advantage of information in the residuals (i.e., the probability density function (pdf) of the residuals). In terms of these aspects, the thesis makes the following contributions:

• To leverage possible symmetry in the data, we adapt the concept of Symmetry Distance to formulate an improved regression method, called the Least Trimmed Symmetry Distance (LTSD).

• To exploit the structure in the pdf of residuals, we develop a family of very robust estimators: Maximum Density Power Estimator (MDPE), Quick-MDPE (QMDPE), and variable-bandwidth QMDPE (vbQMDPE) by applying nonparametric density estimation and density gradient estimation techniques in parametric estimation. In these methods, we consider the density distribution of data points in residual space and the size of the residual corresponding to the local maximum of the density distribution in their objective functions. An important tool in our methods is the mean shift method.

• The pdf of the residuals is important for scale estimation (more specifically, the "shape/spread"). By considering distribution of the residuals, and by employing the mean shift method and our proposed mean shift valley method, we develop the Two Step Scale Estimator (TSSE). Furthermore, based on TSSE, we propose a family of novel robust estimators: Adaptive Scale Sample Consensus (ASSC) and Adaptive Scale Residual Consensus (ASRC), which consider both the residuals of inliers and the scale of inliers in the objective functions.

The traditional robust methods generally assume that the data of interests (inliers) occupy a majority of the whole data. In image analysis, however, the data is often complex and several instances of a model are simultaneously present, each accounting for a relatively small percentage of the data points. To deal with data including multiple structures and a high percentage of outliers (>50%) remains a challenging task. In this thesis, we assume that the inliers occupy a relative majority of the data, by which it is possible that a robust estimator can tolerate more than 50% outliers. A significant contribution of this thesis is that we present a series of novel and highly robust estimators—MDPE, QMDPE and vbQMDPE, which can tolerate more than 80% outliers and is very robust to data with multiple structures, by applying the mean shift algorithm in the space of the pdf of residuals.

When data include multiple structures, two major steps should be taken in the process of robust model fitting: i) robustly estimate the parameters of a model, and ii) differentiate inliers from outliers. Experiments in this thesis show that to correctly estimate the parameters of a model (only) is not enough; to differentiate inliers from outliers, both the estimated parameters of a model and the corresponding scale estimate should be correct.

Having a correct scale of inliers is crucial to the robust behaviour of an estimator. The success of many robust estimators is based on having a correct initial scale estimate or the correct setting of a particular parameter that is related to scale (e.g., RANSAC, Hough Transform, M-estimators etc.). Although there are a lot of papers that propose highly robust estimators, robust scale estimation is relatively neglected in the computer vision community. One major contribution of this thesis is that we investigate the behaviour of several state-of-the-art robust scale estimators for data with multiple structures, and propose a novel robust scale estimator: TSSE. TSSE is very robust to outliers and can resist heavily contaminated data with multiple structures. TSSE is a very general method and can be used to give an initial scale estimate for robust estimators such as M-estimators. TSSE can also be used to provide an auxiliary estimate of scale (after the parameters of a model to fit have been found) as a component of almost any robust fitting method such as Hough Transform, MDPE, etc.

Another important contribution of this thesis is that we propose, based on TSSE and RANSAC, another novel and highly robust estimator: ASSC (and a variant of ASSC: ASRC). The ASSC estimator is an important improvement over RANSAC because no priori knowledge concerning the scale of inliers is necessary (the scale estimation is data driven). ASSC can tolerate more than 80% outliers and multiple structures. ASSC is also an improvement over MDPE and its family (QMDPE/vbQMDPE). MDPE and its family only estimate the parameters of a model. In contrast, ASSC can produce the parameters of a model and the corresponding scale as its results.

We used the mean shift algorithm extensively in the robust methods described above. We also directly apply the mean shift method to image segmentation based on image intensity or on image color. One property of the mean shift is that it is sensitive to local peaks (including false peaks). We found in our experiments that it is possible that there are many false peaks if the feature space (such as the intensity/color space or the residual space) is quantized. The occurrence of false peaks may have a negative influence on the performance of methods employing the mean shift. In this thesis, we establish a quantitative relationship between the appearance of false peaks and the value of the bandwidth h. We provide a complete unsupervised peak-valley sliding algorithm for graylevel image segmentation. The general mean shift algorithm considers only the global information (features) of the image, while neglecting the local homogeneity information. We modify the mean shift algorithm so that both local homogeneity and global information are considered.

In order to validate our proposed methods, we have (successfully) applied these methods to a considerable number of important and fundamental computer vision tasks including:

• Model fitting (geometric primitive fitting): (a) line fitting; (b) circle fitting; (c) ellipse fitting; (d) plane fitting, etc.;
• Range image segmentation;
• Robust optical flow calculation;
• Fundamental matrix estimation;
• Grey image segmentation and color image segmentation.

Related Publications
 

H. Wang and D. Suter, "Robust Adaptive-Scale Parametric Model Estimation for Computer Vision", IEEE Trans.    Pattern Analysis and Machine Intelligence (PAMI), 2004.

H. Wang and D. Suter, "Robust Fitting by Adaptive-Scale Residual Consensus", in 8th European Conference on Computer Vision (ECCV04), Prague, pages 107-118, May 11-14, 2004.

H. Wang and D. Suter, "MDPE: A Very Robust Estimator for Model Fitting and Range Image Segmentation", International Journal of Computer Vision (IJCV), 59(2), pages 139-166, 2004.

D. Suter and H. Wang, "Robust Fitting Using Mean Shift: Applications in Computer Vision", in M. Hubert, G. Pison, A. Struyf, and S. Van Aelst, editors, Theory and Applications of Recent Robust Methods, Statistics for Industry and Technology. Birkhauser, Basel, pages 307-318, 2004.

H. Wang and D. Suter, "Using Symmetry in Robust Model Fitting", Pattern Recognition Letters, 24(16), pages 2953-2966, 2003.

H. Wang and D. Suter, "False-Peaks-Avoiding Mean Shift Method for Unsupervised Peak-Valley Sliding Image Segmentation", in 7th International Conference on Digital Image Computing: Techniques and Applications (DICTA'03), Sydney, pages 581-590, 10-12 Dec. 2003.

H. Wang and D. Suter, "Color Image Segmentation Using Global Information and Local Homogeneity", in 7th International Conference on Digital Image Computing: Techniques and Applications (DICTA'03), Sydney, pages 89-98, 10-12 Dec. 2003.

H. Wang and D.Suter, "Variable Bandwidth QMDPE and Its Application in Robust Optic Flow Estimation", in 9th IEEE International Conference on Computer Vision (ICCV03), Nice, France, pages 178-183, Oct. 2003.

H. Wang and D. Suter, "A Model-Based Range Image Segmentation Algorithm Using a Novel Robust Estimator", in 3rd International Workshop on Statistical and Computational Theories of Vision - SCTV03 (in conjunction with ICCV03), Nice, France, Oct. 2003.

D. Suter, P. Chen, and H. Wang, "Extracting Motion from Images: Robust Optic Flow and Structure from Motion", in Proceedings Australia-Japan Advanced Workshop on Computer Vision, Adelaide, Australia, pages 64-69, 9-11 Sept. 2003.

H. Wang and D. Suter, "A Novel Robust Method for Large Numbers of Gross Errors", in 7th Int. Conf. on Automation, Robotics and Computer Vision (ICARCV02), Singapore, pages 326-331, December 3-6, 2002.

H. Wang and D. Suter, "LTSD: A Highly Efficient Symmetry-based Robust Estimator", in 7th Int. Conf. on Automation, Robotics and Computer Vision (ICARCV02), Singapore, pages 332-337, December 3-6, 2002.