Sampson Error

Figure 3.1: Between a variety $\mathcal {V}$ and a point $\mathbf {p}$, one can identify the point at minimum geometric distance $\hat {\mathbf {p}}$ and the point determined by the Sampson distance $\mathbf {x}$.

In many regression problems, it is necessary to have some metric to understand how far a $\mathbf {p}$ is from the true model. To achieve this, it would be useful to have an estimate $\hat {\mathbf {p}}$ of the observation without the noise component, that is, a data point that exactly belongs to the model. Both of these quantities are typically not directly obtainable without introducing unknown auxiliary variables. However, it is possible to obtain an estimate of these values by linearizing the model function around the observation.

Let $\mathbf {p}$ be an observation affected by noise, and let $f(\mathbf{x})=\mathbf{0}$ be a multidimensional variety manifold representing a specific model to which the observation must belong, that is, $\mathbf{p} = \hat{\mathbf{p}} + \epsilon$.

The residual $f(\mathbf{p})$ is an algebraic measure of the proximity between the point and the model and does not provide any useful information in absolute terms: if the function is replaced by a non-zero multiple of itself, it will obviously represent the same locus of points, but the function's output will change accordingly. The correct metric from the perspective of the maximum likelihood estimator in the case of additive white Gaussian noise on the observations is the geometric distance between the point $\mathbf {p}$ and the point $\hat {\mathbf {p}}$ belonging to the model, that is, to estimate $\epsilon$.

We therefore examine the problem of calculating an approximate distance between the point $\mathbf{p} \in \mathbb{R}^m$ and a geometric variety $f(\mathbf{x})=\mathbf{0}$ where $f: \mathbb{R}^{m} \mapsto \mathbb{R}^{n}$ is a differentiable function in a neighborhood of $\mathbf {p}$.

The point $\hat {\mathbf {p}}$ that lies on the manifold closest to the point $\mathbf {p}$ is, by definition, the point that minimizes the geometric error

$$\hat{\mathbf{p}} = \argmin_\mathbf{x} \Vert \mathbf{p} - \mathbf{x} \Vert$$ (3.50)

under the constraint $f(\mathbf{x})=0$ (or $\min \vert\vert \epsilon \vert\vert^2$ under the constraint $f(\mathbf{p} + \epsilon)=\mathbf{0}$).

The difference between minimizing an algebraic quantity in a linear manner and a geometric quantity in a non-linear manner has prompted the search for a potential compromise. The Sampson method, initially developed for varieties such as conics, requires a hypothesis that can instead be applied to various problems: the derivatives of the cost function in the vicinity of the minimum $\hat {\mathbf {p}}$ must be nearly linear and thus approximable through a series expansion. The variety $f(\mathbf{p})=0$ can be approximated using Taylor expansion such that

$$\tilde{f}(\mathbf{x}) \approx f(\mathbf{p}) + \mathbf{J}_f \boldsymbol\delta_{\mathbf{x}} = \mathbf{0}$$ (3.51)

with $\mathbf{J}_f$ being the $n \times m$ Jacobian matrix of the function $f$ evaluated at $\mathbf {p}$ and $\boldsymbol\delta_{\mathbf{x}} = \mathbf{x}-\mathbf{p}$.

This is the equation of a hyperplane in $\mathbf {x}$ and the distance between the point $\mathbf {p}$ and the plane $\tilde{f}(\mathbf{x})=0$ is known as the Sampson distance or the approximate maximum likelihood (AML). The Sampson error represents the geometric distance between the point and the approximated version of the function (geometric distance to first order approximation function).

At this point, the problem becomes finding the point $\mathbf {x}$ that is closest to $\mathbf {p}$, which means minimizing $\Vert\boldsymbol\delta_{\mathbf{x}}\Vert$, while satisfying the linear constraint

$$\mathbf{J}_f \boldsymbol\delta_{\mathbf{x}} = -f(\mathbf{p})$$ (3.52)

.

As it is a minimization problem with constraints, it is solved using Lagrange multipliers, from which a remarkable result is obtained. An interesting result when compared to the Gauss-Newton method, for instance, equation (3.44).

The value $\boldsymbol\delta_\mathbf{x}$ represents an estimate of the distance from the point $\mathbf {p}$ to the variety and can be used both to determine whether the point belongs to the variety (for example, within algorithms like RANSAC to discern outliers) and potentially as an alternative cost function to the Euclidean norm. $\boldsymbol\delta_\mathbf{x}$ is the Sampson error, and its norm, given by

$$\Vert \boldsymbol\delta_x \Vert^2 = \boldsymbol\delta_x^{\t... ...\left( \mathbf{J} \mathbf{J}^{\top} \right)^{-1} f(\mathbf{p})$$ (3.53)

, indicates the squared distance between the point and (the first-order approximation of) a point on the variety.

In the notable case $n=1$, the Sampson distance reduces to

$$\Vert \boldsymbol\delta_x \Vert^2 = \dfrac{\left( f(\mathbf{p}) \right)^{2}}{\left\Vert \nabla f(\mathbf{p}) \right\Vert^2}$$ (3.54)

Practical applications of the use of the Sampson error include, for example, the distance from a point to a conic (see section 3.6.7), the distance of a pair of points from a homography, or the distance of a pair of corresponding points with respect to the Fundamental matrix (section 9.4.2).

The Sampson distance can be generalized in the case of multiple constraints using the Mahalanobis distance, specifically by minimizing

$$\min_\epsilon \sum \vert\vert \epsilon \vert\vert^2_\Sigma ... ...epsilon \sum \epsilon^{\top} \boldsymbol \Sigma^{-1} \epsilon$$ (3.55)

subject to the constraint $f(\mathbf{p}+\epsilon)=0$. Thus, the above equation generalizes to

$$\Vert \boldsymbol\delta_x \Vert^2 = \boldsymbol\delta_x^{\t... ...boldsymbol \Sigma \mathbf{J}^{\top} \right)^{-1} f(\mathbf{p})$$ (3.56)

.