Algebraic Distance

Bob Fisher

A linear distance metric commonly used in computer vision applications because of its simple form and standard matrix based least mean square estimation operations.

If a curve or surface is defined implicitly by $f(\vec{x},\vec{a})=0$ (e.g. $\vec{x}^\top \vec{a}=0$ for a hyperplane) the algebraic distance of a point $\vec{x}_i$ to the surface is simply $f(\vec{x}_i,\vec{a})$.

If $f()$ can be factored as $f(\vec{x},\vec{a})= \vec{a}^\top \vec{g}(\vec{x})$ (e.g. $\vec{g}(\vec{x}) = \vec{x}$ for a hyperplane and $\vec{g}((x,y)^\top) = (x^2,y^2,-1)^\top$ for a circle) then the least square estimation of the parameters $\vec{a}$ is as follows. (This factoring is straightforward if the components of $\vec{g}$ are polynomials in the components of $\vec{x}$.) Let $\vec{g}_i = \vec{g}(\vec{x}_i)$. Then we wish to estimate the $\vec{a}$ that minimizes

$$\epsilon = \Sigma_i f(\vec{x}_i,\vec{a})^2 = \Sigma_i (\vec{a}^\top \vec{g}(\vec{x}_i))^2$$

Form the matrix $\mathbf{G} = [\vec{g}(\vec{x}_1), \vec{g}(\vec{x}_2), \dots, \vec{g}(\vec{x}_n) ]$. Then the above equation can be reformulated as

$$\epsilon = \vec{a}^\top \mathbf{G} \mathbf{G}^\top \vec{a}$$

The eigenvector corresponding to the smallest eigenvalue of $\mathbf{G} \mathbf{G}^\top$ is the parameter vector $\vec{a}$ that minimizes the algebraic distance.

The algebraic distance is the same as the Euclidean distance for hyperplanes, but can have significant error for curved surfaces. As a consequence, Taubin produced a variant to the algebraic distance that may give parameter estimates with lower Euclidean distance. This approach is a first order approximation to the Euclidean distance and minimizes:

$$\frac{\mid f(\vec{x},\vec{a}) \mid}{\mid \mid \nabla f(\vec{x},\vec{a}) \mid\mid }$$

$\vec{a}$ is found using a generalized eigenvalue method. For more details on this distance and how to minimize it in closed form, see:

G. Taubin, F. Cukierman, S. Sullivan, J. Ponce, D.J. Kriegman. Parameterized families of polynomials for bounded algebraic curve and surface fitting. IEEE. Trans. Pat. Anal. and Mach. Intel., March 1994 (Vol. 16, No. 3) p.287-303.