Sampson Error

Figure 4.1: Between a variety $\mathcal {V}$ and a point $\mathbf {p}$, it is possible to identify the point at minimum geometric distance $\hat {\mathbf {p}}$ and the point determined by the Sampson distance $\mathbf {x}$.

In many data-regression problems, it is necessary to have some metric for determining how far a $\mathbf {p}$ is from the actual model. For this purpose, it would be useful to have an $\hat {\mathbf {p}}$ estimate of the observation without the noise component, namely a datum that belongs exactly to the model. Neither of these quantities can normally be obtained directly without introducing unknown auxiliary variables. It is nevertheless possible to estimate these values by linearizing the model function in the neighborhood of the observation.

Let $\mathbf {p}$ be a noisy observation and let $f(\mathbf{x})=\mathbf{0}$ be a multidimensional manifold representing a particular model to which the observation must belong, namely $\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 provides no useful information in absolute terms: if the function is replaced by a nonzero multiple of itself, it obviously represents the same locus of points, but the value of the function changes accordingly. From the perspective of the maximum-likelihood estimator, the correct metric in the presence of additive white Gaussian noise in the observations is the geometric distance between the point $\mathbf {p}$ and the point $\hat {\mathbf {p}}$ belonging to the model, that is, estimating $\epsilon$.

We therefore consider the problem of computing 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}}$ lying on the variety and 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$$ (4.57)

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

The difference between minimizing an algebraic quantity linearly and a geometric quantity nonlinearly has motivated the search for a possible compromise. The Sampson method, initially developed for varieties such as conics, requires an assumption that can instead be applied to several problems: the derivatives of the cost function in the neighborhood of the minimum $\hat {\mathbf {p}}$ must be approximately linear and therefore 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}$$ (4.58)

with $\mathbf{J}_f$ the $n \times m$ matrix of the Jacobian 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 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).

The problem now becomes that of finding the point $\mathbf {x}$ closest to $\mathbf {p}$, that is, minimizing $\Vert\boldsymbol\delta_{\mathbf{x}}\Vert$ subject to the linear constraint

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

Since this is a constrained minimization problem, it is solved using Lagrange multipliers, yielding the notable result

$$\boldsymbol\delta_{\mathbf{x}} = - \mathbf{J}^{\top} \left( \mathbf{J} \mathbf{J}^{\top} \right)^{-1} f(\mathbf{p})$$ (4.60)

an interesting result when compared, for example, with the Gauss-Newton method, equation (4.50).

The value $\boldsymbol\delta_\mathbf{x}$ represents an estimate of the distance of the point $\mathbf {p}$ from the variety and can be used both to determine whether the point belongs to the variety (for example, within algorithms such as RANSAC to identify 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})$$ (4.61)

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}$$ (4.62)

Practical applications of the Sampson error include the distance between a point and a conic (see Section 4.6.7), the distance between a pair of points and a homography, and the distance between a pair of corresponding points with respect to the Fundamental matrix (Section 10.4.2).

The Sampson distance can be generalized to the case of multiple constraints using the Mahalanobis distance, that is, by minimizing

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

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

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