L. Dorst: Total Least Squares Fitting of k-Spheres in nD Euclidean Space Using an (n+2)D Isometric Representation


Leo Dorst (l.dorst_AT_uva.nl), Intelligent Systems Laboratory Amsterdam, University of Amsterdam, P.O. Box 94323, 1098 XH Amsterdam, The Netherlands.
Journal of Mathematical Imaging and Vision, Received: 14 February 2013Accepted: 8 January 2014. Published online: 18 January 2014. URL: http://link.springer.com/article/10.1007%2Fs10851-014-0495-2, DOI: 10.1007/s10851-014-0495-2

Abstract. We fit k-spheres optimally to n-D point data, in a geometrically total least squares sense. A specific practical instance is the optimal fitting of 2D-circles to a 3D point set.

Among the optimal fitting methods for 2D-circles based on 2D (!) point data compared in Al-Sharadqah and Chernov (Electron. J. Stat. 3:886–911, 2009), there is one with an algebraic form that permits its extension to optimally fitting k-spheres in n-D. We embed this ‘Pratt 2D circle fit’ into the framework of conformal geometric algebra (CGA), and doing so naturally enables the generalization. The procedure involves a representation of the points in n-D as vectors in an (n+2)-D space with attractive metric properties. The hypersphere fit then becomes an eigenproblem of a specific symmetric linear operator determined by the data. The eigenvectors of this operator form an orthonormal basis representing perpendicular hyperspheres. The intersection of these are the optimal k-spheres; in CGA the intersection is a straightforward outer product of vectors.

The resulting optimal fitting procedure can easily be implemented using a standard linear algebra package; we show this for the 3D case of fitting spheres, circles and point pairs. The fits are optimal (in the sense of achieving the KCR lower bound on the variance).

We use the framework to show how the hyperaccurate fit hypersphere of Al-Sharadqah and Chernov (Electron. J. Stat. 3:886–911, 2009) is a minor rescaling of the Pratt fit hypersphere.

Keywords. Sphere fitting, Hypersphere fitting, Circle fitting, Total least squares, Hyperaccuracy, Geometric algebra, Conformal geometric algebra, Minkowski metric, Horosphere
Source: Email from L. Dorst (l.dorst_AT_uva.nl), 20 Jan. 2014, http://link.springer.com/article/10.1007%2Fs10851-014-0495-2

Leave a comment

Filed under publications

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s