Bridging Parameter and Data Spaces for Fast Robust Estimation in Computer Vision

All high breakdown robust estimators, at their core, include an isolated search in either the data or the parameter space. In this paper, we devise a high breakdown robust estimation technique, called fast least k-th order statistics (FLkOS) that employs the derivatives of order statistics of squared residuals to implement Newton's optimization method for its search. It is mathematically shown that Newton's optimization of the order statistics leads to a very simple and substantially fast search algorithm that bridges the data and parameter spaces. The proposed search involves replacing a p-tuple with another p-tuple in the data space, while moving towards the minimum point of the estimator's cost function in the parameter space. An important practical implication of this strategy is that we can limit the required search in the parameter space to the specific manifold spanned by data. FLkOS is shown to be an effective tool to perform multi-structured data fitting and segmentation via a number of experiments including range image segmentation experiments involving both synthetic and real images and fundamental matrix estimation involving real image pairs. The results show that FLkOS is remarkably efficient and substantially faster than state-of-the-art high breakdown estimators.