Error analysis of robust optical flow estimation by least median of squares methods for the varying illumination model

The apparent pixel motion in an image sequence, called optical flow, is a useful primitive for automatic scene analysis and various other applications of computer vision. In general, however, the optical flow estimation suffers from two significant problems: the problem of illumination that varies with time and the problem of motion discontinuities induced by objects moving with respect to either other objects or with respect to the background. Various integrated approaches for solving these two problems simultaneously have been proposed. Of these, those that are based on the LMedS (least median of squares) appear to be the most robust. The goal of this paper is to carry out an error analysis of two different LMedS-based approaches, one based on the standard LMedS regression and the other using a modification thereof as proposed by us recently. While it is to be expected that the estimation accuracy of any approach would decrease with increasing levels of noise, for LMedS-like methods, it is not always clear as to how much of that decrease in performance can be attributed to the fact that only a small number of randomly selected samples is used for forming temporary solutions. To answer this question, our study here includes a baseline implementation in which all of the image data is used for forming motion estimates. We then compare the estimation errors of the two LMedS-based methods with the baseline implementation. Our error analysis demonstrates that, for the case of Gaussian noise, our modified LMedS approach yields better estimates at moderate levels of noise, but is outperformed by the standard LMedS method as the level of noise increases. For the case of salt-and-pepper noise, the modified LMedS method consistently performs better than the standard LMedS method.     

Using symmetry in robust model fitting

The pattern recognition and computer vision communities often employ robust methods for model fitting. In particular, high breakdown-point methods such as least median of squares (LMedS) and least trimmed squares (LTS) have often been used in situations where the data are contaminated with outliers. However, though the breakdown point of these methods can be as high as 50% (they can be robust to up to 50% contamination), they can break down at unexpectedly lower percentages when the outliers are clustered. In this paper, we demonstrate the fragility of LMedS and LTS and analyze the reasons that cause the fragility of these methods in the situation when a large percentage of clustered outliers exist in the data. We adapt the concept of “symmetry distance” to formulate an improved regression method, called the least trimmed symmetry distance (LTSD). Experimental results are presented to show that the LTSD performs better than LMedS and LTS under a large percentage of clustered outliers and large standard variance of inliers.     

Robust adaptive-scale parametric model estimation for computer vision

Robust model fitting essentially requires the application of two estimators. The first is an estimator for the values of the model parameters. The second is an estimator for the scale of the noise in the (inlier) data. Indeed, we propose two novel robust techniques: the two-step scale estimator (TSSE) and the adaptive scale sample consensus (ASSC) estimator. TSSE applies nonparametric density estimation and density gradient estimation techniques, to robustly estimate the scale of the inliers. The ASSC estimator combines random sample consensus (RANSAC) and TSSE, using a modified objective function that depends upon both the number of inliers and the corresponding scale. ASSC is very robust to discontinuous signals and data with multiple structures, being able to tolerate more than 80 percent outliers. The main advantage of ASSC over RANSAC is that prior knowledge about the scale of inliers is not needed. ASSC can simultaneously estimate the parameters of a model and the scale of the inliers belonging to that model. Experiments on synthetic data show that ASSC has better robustness to heavily corrupted data than least median squares (LMedS), residual consensus (RESC), and adaptive least Kth order squares (ALKS). We also apply ASSC to two fundamental computer vision tasks: range image segmentation and robust fundamental matrix estimation. Experiments show very promising results.     

基于LQS的基本矩阵计算方法

基本矩阵作为分析两视图对极几何的有力工具,在视觉领域中占用重要的地位.分析了传统鲁棒方法在基本矩阵的求解问题中存在的不足,引入了稳健回归分析中的LQS方法,并结合Bucket分割技术,提出一种鲁棒估计基本矩阵的新方法,克服了RANSAC方法和LMedS方法的缺陷.模拟数据和真实图像实验结果表明,本文方法具有更高的鲁棒性和精确度.     

Robust Optical Flow Computation Based on Least-Median-of-Squares Regression

An optical flow estimation technique is presented which is based on the least-median-of-squares (LMedS) robust regression algorithm enabling more accurate flow estimates to be computed in the vicinity of motion discontinuities. The flow is computed in a blockwise fashion using an affine model. Through the use of overlapping blocks coupled with a block shifting strategy, redundancy is introduced into the computation of the flow. This eliminates blocking effects common in most other techniques based on blockwise processing and also allows flow to be accurately computed in regions containing three distinct motions.A multiresolution version of the technique is also presented, again based on LMedS regression, which enables image sequences containing large motions to be effectively handled.An extensive set of quantitative comparisons with a wide range of previously published methods are carried out using synthetic, realistic (computer generated images of natural scenes with known flow) and natural images. Both angular and absolute flow errors are calculated for those sequences with known optical flow. Displaced frame difference error, used extensively in video compression, is used for those natural scenes with unknown flow. In all of the sequences tested, a comparison with those methods that result in a dense flow field (greater than 80% spatial coverage), show that the LMedS technique produces the least error irrespective of the error measure used.     

Robust estimation of BRDF model parameters

The effect of the Bidirectional Reflectance Distribution Function (BRDF) is one of the most important factors in correcting the reflectance obtained from remotely sensed data. Estimation of BRDF model parameters can be deteriorated by various factors; contamination of the observations by undetected subresolution clouds or snow patches, inconsistent atmospheric correction in multiangular time series due to uncertainties in the atmospheric parameters, slight variations of the surface condition during a period of observation, for example due to soil moisture changes, diurnal effects on vegetation structure, and geolocation errors [Lucht and Roujean, 2000]. In the present paper, parameter estimation robustness is examined using Bidirectional Reflectance Factor (BRF) data measured for paddy fields in Japan. We compare both the M-estimator and the least median of squares (LMedS) methods for robust parameter estimation to the ordinary least squares method (LSM). In experiments, simulated data that were produced by adding noises to the data measured on the ground surface were used. Experimental results demonstrate that if a robust estimation is sought, the LMedS method can be adopted for the robust estimation of a BRDF model parameter.     

Robust pose estimation

Standard least-squares (LS) methods for pose estimation of objects are sensitive to outliers which can occur due to mismatches. Even a single mismatch can severely distort the estimated pose. This paper describes a least-median of squares (LMedS) approach to estimating pose using point matches. It is both robust (resistant to up to 50% outliers) and efficient (linear in the number of points). The basic algorithm is then extended to improve performance in the presence of two types of noise: 1) type I which perturbs all data values by small amounts (e.g., Gaussian) and 2) type II which can corrupt a few data values by large amounts     

LSMAT Least Squares Medial Axis Transform

The medial axis transform has applications in numerous fields including visualization, computer graphics, and computer vision. Unfortunately, traditional medial axis transformations are usually brittle in the presence of outliers, perturbations and/or noise along the boundary of objects. To overcome this limitation, we introduce a new formulation of the medial axis transform which is naturally robust in the presence of these artefacts. Unlike previous work which has approached the medial axis from a computational geometry angle, we consider it from a numerical optimization perspective. In this work, we follow the definition of the medial axis transform as ‘the set of maximally inscribed spheres’. We show how this definition can be formulated as a least squares relaxation where the transform is obtained by minimizing a continuous optimization problem. The proposed approach is inherently parallelizable by performing independent optimization of each sphere using Gauss–Newton, and its least‐squares form allows it to be significantly more robust compared to traditional computational geometry approaches. Extensive experiments on 2D and 3D objects demonstrate that our method provides superior results to the state of the art on both synthetic and real‐data.     

Computer vision-based framework for extracting tectonic lineaments from optical remote sensing data

ABSTRACT

The extraction of tectonic lineaments from digital satellite data is a fundamental application in remote sensing. The location of tectonic lineaments such as faults and dykes are of interest for a range of applications, particularly because of their association with hydrothermal mineralization. Although a wide range of applications have utilized computer vision techniques, a standard workflow for application of these techniques to tectonic lineament extraction is lacking. We present a framework for extracting tectonic lineaments using computer vision techniques. The proposed framework is a combination of edge detection and line extraction algorithms for extracting tectonic lineaments using optical remote sensing data. It features ancillary computer vision techniques for reducing data dimensionality, removing noise and enhancing the expression of lineaments. The efficiency of two convolutional filters are compared in terms of enhancing the lineaments. We test the proposed framework on Landsat 8 data of a mineral-rich portion of the Gascoyne Province in Western Australia. To validate the results, the extracted lineaments are compared to geologically mapped structures by the Geological Survey of Western Australia (GSWA). The results show that the best correlation between our extracted tectonic lineaments and the GSWA tectonic lineament map is achieved by applying a minimum noise fraction transformation and a Laplacian filter. Application of a directional filter shows a strong correlation with known sites of hydrothermal mineralization. Hence, our method using either filter can be used for mineral prospectivity mapping in other regions where faults are exposed and observable in optical remote sensing data.     

Efficient and robust model fitting with unknown noise scale

This paper addresses the general problem of robust parametric model estimation from data that has both an unknown (and possibly majority) fraction of outliers as well as an unknown scale of measurement noise. We focus on computer vision applications from image correspondences, such as camera resectioning, estimation of the fundamental matrix or relative pose for 3D reconstruction, and estimation of 2D homographies for image registration and motion segmentation, although there are many other applications. In practice, these methods typically rely on a predefined inlier thresholds because automatic scale detection is usually too unreliable or too slow. We propose a new method for robust estimation with automatic scale detection that is faster, more precise and more robust than previous alternatives, and show that it can be practically applied to these problems.     

一种新的高精度的L-M基本矩阵估计算法

分析了基于随机抽样检测思想的现有鲁棒算法在基本矩阵估计中存在的不足,结合LMedS和M估计法各自的优点,提出一种新的高精度的L-M基本矩阵估计算法。利用LMedS思想方法获得内点集,此时内点集通常情况下不包含误匹配,但仍存在位置误差,用Torr-M估计法计算基本矩阵,因为当匹配点只存在位置误差时,用M估计法得到的基本矩阵非常精确。大量的模拟实验和真实图像实验数据表明,在高斯噪声和误匹配存在的情况下,该算法具有更高的鲁棒性和精确度。     

Estimation of nonlinear errors-in-variables models for computer vision applications

In an errors-in-variables (EIV) model, all the measurements are corrupted by noise. The class of EIV models with constraints separable into the product of two nonlinear functions, one solely in the variables and one solely in the parameters, is general enough to represent most computer vision problems. We show that the estimation of such nonlinear EIV models can be reduced to iteratively estimating a linear model having point dependent, i.e., heteroscedastic, noise process. Particular cases of the proposed heteroscedastic errors-in-variables (HEIV) estimator are related to other techniques described in the vision literature: the Sampson method, renormalization, and the fundamental numerical scheme. In a wide variety of tasks, the HEIV estimator exhibits the same, or superior, performance as these techniques and has a weaker dependence on the quality of the initial solution than the Levenberg-Marquardt method, the standard approach toward estimating nonlinear models.     

Robust edge detection

Edge detection is an important issue in computer vision and image understanding systems. Most conventional techniques have assumed Gaussian noise, and their performance could decrease with the departure of noise distribution from normality. In this paper, we present an edge detection approach using robust statistics. The edge structure is first detected by a robust one-way design model, and then localized by a robust contrast test. Finally, hysteresis thresholding is applied to yield the output edge map. To evaluate its performance, experiments were carried out on synthetic and real images corrupted with both Gaussian noise and a mixture of Gaussian and impulsive noise. The results show that the performance of the proposed edge detector is stable and reliable under severe impulsive noise conditions.     

Localising discontinuities using weak continuity constraints

Many processes in computer vision can be formulated concisely as optimisation problems. In particular the localisation of discontinuities can be regarded as optimisation under weak continuity constraints. A weak constraint is a constraint which can be broken — but at a cost.In this paper we illustrate the use of weak constraints by considering a simple example — edge detection in 1D. Finite elements are used to discretise the problem. The cost function is minimised using a ‘graduated non-convexity’ algorithm. This gives a local relaxation scheme which could be implemented in parallel.Results are given for a serial computer implementation of the method. They show that the algorithm does perform as theoretically predicted, and that it is robust in the presence of noise. Results are also given for a 2D version of the method, applied to real images.     

A Framework for Robust Subspace Learning

Many computer vision, signal processing and statistical problems can be posed as problems of learning low dimensional linear or multi-linear models. These models have been widely used for the representation of shape, appearance, motion, etc., in computer vision applications. Methods for learning linear models can be seen as a special case of subspace fitting. One draw-back of previous learning methods is that they are based on least squares estimation techniques and hence fail to account for outliers which are common in realistic training sets. We review previous approaches for making linear learning methods robust to outliers and present a new method that uses an intra-sample outlier process to account for pixel outliers. We develop the theory of Robust Subspace Learning (RSL) for linear models within a continuous optimization framework based on robust M-estimation. The framework applies to a variety of linear learning problems in computer vision including eigen-analysis and structure from motion. Several synthetic and natural examples are used to develop and illustrate the theory and applications of robust subspace learning in computer vision.     

基于运动放大的振动结构的模态识别

快速准确地获取结构的振动信息是确定结构模态参数的关键。随着计算机视觉和高速相机技术的发展,视觉测量振动逐渐受到人们的重视。对一种可检测结构微小运动的计算机视觉技术进行了研究,并将最新的实时运动放大算法用于振动结构的模态识别。此算法可在不提取位移的情况下直接展示振动结构的模态特征。为了验证提出方法的可行性,以悬臂梁为例搭建了加速度计和高速相机的模态识别实验系统,并依据理论模态对其实验数据进行模态置信准则(MAC)检验。分析实验结果表明：提出的方法可以识别振动结构的模态参数。     

Ordering and parameterizing scattered 3D data for B-spline surfaceapproximation

Surface representation is intrinsic to many applications in medical imaging, computer vision, and computer graphics. We present a method that is based on surface modeling by B-spline. The B-spline constructs a smooth surface that best fits a set of scattered unordered 3D range data points obtained from either a structured light system (a range finder), or from point coordinates on the external contours of a set of surface sections, as for example in histological coronal brain sections. B-spline stands as of one the most efficient surface representations. It possesses many properties such as boundedness, continuity, local shape controllability, and invariance to affine transformations that makes it very suitable and attractive for surface representation. Despite its attractive properties, however, B-spline has not been widely applied for representing a 3D scattered nonordered data set. This may be due to the problem in finding an ordering and a choice for the topological parameters of the B-spline that lead to a physically meaningful surface parameterization based on the scattered data set. The parameters needed for the B-spline surface construction, as well as finding the ordering of the data points, are calculated based on the geodesics of the surface extended Gaussian map. The set of control points is analytically calculated by solving a minimum mean square error problem for best surface fitting. For a noise immune modeling, we elect to use an approximating rather than an interpolating B-spline. We also examine ways of making the B-spline fitting technique robust to local deformation and noise     

Mining Adaptive Ratio Rules from Distributed Data Sources

Different from traditional association-rule mining, a new paradigm called Ratio Rule (RR) was proposed recently. Ratio rules are aimed at capturing the quantitative association knowledge, We extend this framework to mining ratio rules from distributed and dynamic data sources. This is a novel and challenging problem. The traditional techniques used for ratio rule mining is an eigen-system analysis which can often fall victim to noise. This has limited the application of ratio rule mining greatly. The distributed data sources impose additional constraints for the mining procedure to be robust in the presence of noise, because it is difficult to clean all the data sources in real time in real-world tasks. In addition, the traditional batch methods for ratio rule mining cannot cope with dynamic data. In this paper, we propose an integrated method to mining ratio rules from distributed and changing data sources, by first mining the ratio rules from each data source separately through a novel robust and adaptive one-pass algorithm (which is called Robust and Adaptive Ratio Rule (RARR)), and then integrating the rules of each data source in a simple probabilistic model. In this way, we can acquire the global rules from all the local information sources adaptively. We show that the RARR technique can converge to a fixed point and is robust as well. Moreover, the integration of rules is efficient and effective. Both theoretical analysis and experiments illustrate that the performance of RARR and the proposed information integration procedure is satisfactory for the purpose of discovering latent associations in distributed dynamic data source.     

Robust reweighted MAP motion estimation

This paper proposes a motion estimation algorithm that is robust to motion discontinuity and noise. The proposed algorithm is constructed by embedding the least median squares (LMedS) of robust statistics into the maximum a posteriori (MAP) estimator. Difficulties in accurate estimation of the motion field arise from the smoothness constraint and the sensitivity to noise. To cope robustly with these problems, a median operator and the concept of reweighted least squares (RLS) are applied to the MAP motion estimator, resulting in the reweighted robust MAP (RRMAP). The proposed RRMAP motion estimation algorithm is also generalized for multiple image frame cases. Computer simulation with various synthetic image sequences shows that the proposed algorithm reduces errors, compared to three existing robust motion estimation algorithms that are based on M-estimation, total least squares (TLS), and Hough transform. It is also observed that the proposed algorithm is statistically efficient and robust to additive Gaussian noise and impulse noise. Furthermore, the proposed algorithm yields reasonable performance for real image sequences     

Optic flow field segmentation and motion estimation using a robustgenetic partitioning algorithm

Optic flow motion analysis represents an important family of visual information processing techniques in computer vision. Segmenting an optic flow field into coherent motion groups and estimating each underlying motion is a very challenging task when the optic flow field is projected from a scene of several independently moving objects. The problem is further complicated if the optic flow data are noisy and partially incorrect. In this paper, the authors present a novel framework for determining such optic flow fields by combining the conventional robust estimation with a modified genetic algorithm. The baseline model used in the development is a linear optic flow motion algorithm due to its computational simplicity. The statistical properties of the generalized linear regression (GLR) model are thoroughly explored and the sensitivity of the motion estimates toward data noise is quantitatively established. Conventional robust estimators are then incorporated into the linear regression model to suppress a small percentage of gross data errors or outliers. However, segmenting an optic flow field consisting of a large portion of incorrect data or multiple motion groups requires a very high robustness that is unattainable by the conventional robust estimators. To solve this problem, the authors propose a genetic partitioning algorithm that elegantly combines the robust estimation with the genetic algorithm by a bridging genetic operator called self-adaptation