An ADMM-based scheme for distance function approximation
- PDF / 2,207,769 Bytes
- 14 Pages / 439.642 x 666.49 pts Page_size
- 53 Downloads / 217 Views
An ADMM-based scheme for distance function approximation Alexander Belyaev1
· Pierre-Alain Fayolle2
Received: 6 March 2019 / Accepted: 24 July 2019 / © The Author(s) 2019
Abstract A novel variational problem for approximating the distance function (to a domain boundary) is proposed. It is shown that this problem can be efficiently solved by ADMM. A review of several other variational and PDE-based methods for distance function estimation is presented. Advantages of the proposed distance function estimation method are demonstrated by numerical experiments. Applications of the method to the problems of surface curvature estimation and computing the skeleton of a binary image are shown. Keywords Distance function · Variational methods · Distance transform · Skeleton · Curvature
1 Introduction Fast and accurate estimation of the distance to a surface (the distance to a curve in 2D) is important for a number of applications including redistancing or reinitialization for level-set methods [17], wall distance models in turbulence modeling [23, 29], heterogeneous material modeling in computational mechanics [6], medial axis transform and meshing [31], FEM extensions [2, 16], robot navigation and mapping [9], and
Alexander Belyaev
[email protected] Pierre-Alain Fayolle [email protected] 1
School of Engineering & Physical Sciences, Heriot-Watt University, Edinburgh, UK
2
Computer Graphics Laboratory, University of Aizu, Aizu-Wakamatsu, Japan
Numerical Algorithms
various computer graphics studies [10, 34, 35]. In particular, variational and PDEbased methods for distance function estimation are currently a subject of intensive research [3, 4, 11, 22, 24]. In this paper, we propose a variational method for accurate distance function estimation. The core of our approach consists of formulating a new variational problem, whose solution is the distance function and solving this variational problem numerically by ADMM [19]. We review several other variational and PDE-based methods for distance function estimation, such as the recent geodesics-in-heat method [11, 12]. We show how to discretize the variational problem by the finite element method, and by using finite difference. In particular, we present the Matlab code for implementing our method (as well as the other variational methods) for computing the distance transform of a 2D binary image. We compare the results obtained by our approach with those of the other methods, and also show how our method can be used for estimating surface curvatures and approximating the skeleton of a 2D binary image.
2 Distance function computation 2.1 Distance function properties Consider a domain ⊂ Rm bounded by ∂ oriented by itsinner normal n. Denoted
2 . Let d(x) by |q|, the magnitude of vector q = (q1 , . . . , qm )T , |q| = q12 + · · · + qm be the signed distance function from ∂. The distance function satisfies the eikonal equation
|∇d| = 1 in
(1)
and boundary conditions d = 0,
∂d/∂n = 1,
and ∂ kd/∂nk = 0,
k = 2, 3, . . .
on ∂.
(2)
Typically, (1) is used
Data Loading...
