The Hamliton-Jacobi Skeleton
Kaleem Siddiqi, Sylvain Bouix, Allen Tannenbaum, Steven W. Zucker
International Conference on Computer Vision
Pages 828-834, 1999
The eikonal equation is a partial differential equation that arises in
many areas of computer vision, including mathematical morphology, Blum's
grassfire transform, new dynamic theories of shape representation, image
processing and analysis, shape-from-shading, and stereo. The numerical
simulation of the eikonal equation is a nontrivial problem.
The authors wish to apply classical approaches from Hamiltonian physics to the
problem of numerically simulating the eikonal equation and apply the results
to computer vision problems in which the eikonal equation must be simulated.
The authors present a new algorithm for simulating the eikonal equation. Then
they present a very efficient algorithm for shock detection. Shocks are
singularities that the evolving front of the eikonal equation simulation
develops as it propagates. The authors apply these algorithms to computer
vision problems such as computing skeletons of complex 2D and 3D shapes.
Existing popular work is based on level set representation of the evolving
front of eikonal equation solution.
This paper uses more classical methods from Hamiltonian physics instead, which
have not been considered in computer vision literature as far as the authors
know.
The Hamlitonian physics-based algorithm for simulating the eikonal equation
introduced in this paper has computational advantages when it comes to shock
tracking. The algorithm for shock detection presented in this paper is very
efficient and robust.
Note that while Voronoi-based techniques (such as medial axis) yield a
topologically organized skeleton, their complexity increases with the number
of points on the boundary of a shape. Also, heuristic measures of
significance are then used for pruning to obtain reasonable results. Instead,
this paper uses divergence which is a natural measure of significance. Also
since the algorithm for computing skeletons in this paper is purely local,
its complexity is linear in the number of input pixels or voxels. The authors
claim that the methods in this paper can be extended to have the same topology
as the original shape as well, and leave this as future work.
ctj