Fast convolution-based methods for computing the signed distance function and its derivatives

Details Fast convolution-based methods for computing the signed distance function and its derivatives Fast convolution-based methods for computing the signed distance function and its derivatives

2011-12-13

arxiv.org/abs/1112.3010v1

Computer Science

Computer Vision and Pattern Recognition

Scientific paper

We present a fast convolution-based technique for computing an approximate, signed Euclidean distance function at a set of 2D and 3D grid locations. Instead of solving the non-linear static Hamilton-Jacobi equation (|\nabla S|=1), our solution stems from solving for a scalar field \phi in a linear differential equation and then deriving the solution for S from its exponent. In other words, when S and \phi are related by \phi = \exp(-S/\tau) and \phi satisfies a specific linear differential equation corresponding to the extremum of a variational problem, we obtain the Euclidean distance function S = -\tau \log(\phi)in the limit as \tau-->0. This is in sharp contrast to solvers such as the fast marching and fast sweeping methods which directly solve the Hamilton-Jacobi equation by the Godunov upwind discretization scheme. Our linear formulation provides us with a closed-form solution to the approximate Euclidean distance function expressed as a discrete convolution, and hence efficiently computed by the Fast Fourier Transform (FFT). Moreover, the solution circumvents the need for spatial discretization of the derivative operator thereby providing highly accurate results. As \tau-->0, we show the convergence of our results to the true solution and also bound the error for a given value of \tau. The differentiability of our solution allows us to compute - using a set of convolutions - the first and second derivatives of the approximate distance function. In order to determine the sign of the distance function (defined to be positive inside a closed region and negative outside), we compute the winding number in 2D and the topological degree in 3D and again explicitly show that these computations can be performed via fast convolutions.

Affiliated with

Also associated with

No associations

Rating

Fast convolution-based methods for computing the signed distance function and its derivatives does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast convolution-based methods for computing the signed distance function and its derivatives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast convolution-based methods for computing the signed distance function and its derivatives will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-223596