Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag

Mathematics-Online lexicon:

Affine Approximation of Point Clouds


A B C D E F G H I J K L M N O P Q R S T U V W X Y Z overview

A best Euclidean approximation of points

$\displaystyle p_i = (p_{i,1},\,\ldots,\,p_{i,n}),\quad
i=1,\ldots,m,
$

with a $ k$-dimensional affine subspace

$\displaystyle H:\ a + \mathrm{span}(v_1,\ldots,v_k)
$

can be determined by minimizing the sum of the squared distances,

$\displaystyle e(P,H) =
\sum_i \mathrm{dist}(p_i,H)^2.
$

\includegraphics[width=0.7\linewidth]{Bild_approx_point_clouds}

The optimal affine subspace $ H$ is characterized as follows. The point $ a$ is the center of the points $ p_i$,

$\displaystyle a = \frac{1}{m} \sum_i p_i,
$

and, if

$\displaystyle \left(\begin{array}{c}
p_1 - a \\
\vdots \\
p_m - a
\end{array}\right)
=
U\,\mathrm{diag}(s_1,\,s_2,\,\ldots)\,V^t
$

is the singular value decomposition of the centered point set, then the basis vectors $ v_j$ are the first $ k$ columns of $ V$.

The error can be expressed in terms of the singular values:

$\displaystyle e(P,H) = \sum_{i>k} s_i^2.
$

(Authors: Höllig/Pfeil/Walter)

Annotation:


[Examples] [Links]

  automatically generated 7/ 2/2007