Spherical Distance Transforms
Authors:
- Takashi MichikawaTMTakashi Michikawa
- Hiromasa SuzukiHSHiromasa Suzuki
- 1 June 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 405-412
Abstract
We present three algorithms for computing correct distance fields on a unit sphere. These algorithms enhance conventional distance transform techniques with several extensions. The first algorithm is a wavefront scheme using quaternions. As a unit quaternion represents a single rotation corresponding to the distance on a sphere, correct distances can be evaluated. Second, we propose a Euclidean vector-based algorithm whose computation is much simpler than that of the first. In addition, we also propose sequential versions of these algorithms that take in linear time. This paper demonstrates several examples computed by these algorithms, and shows that correct distance fields can be obtained by all the methods, with the sequential algorithm being the fastest.Keywords
This publication has 12 references indexed in Scilit:
- 3D distance fields: a survey of techniques and applicationsIEEE Transactions on Visualization and Computer Graphics, 2006
- Variational shape approximation2004
- Spherical parametrization and remeshing2003
- Vector-City Vector Distance TransformComputer Vision and Image Understanding, 2001
- Adaptively sampled distance fields2000
- Optimum design of chamfer distance transformsIEEE Transactions on Image Processing, 1998
- On Digital Distance Transforms in Three DimensionsComputer Vision and Image Understanding, 1996
- Discrete euclidean metricsPattern Recognition Letters, 1992
- Euclidean distance mappingComputer Graphics and Image Processing, 1980
- Sequential Operations in Digital Picture ProcessingJournal of the ACM, 1966