19082019  Original Paper  Issue 3/2020 Open Access
An ADMMbased scheme for distance function approximation
 Journal:
 Numerical Algorithms > Issue 3/2020
Important notes
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
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 levelset 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 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 PDEbased methods for distance function estimation, such as the recent geodesicsinheat 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.
Advertisement
2 Distance function computation
2.1 Distance function properties
Consider a domain
\({\Omega }\subset \mathbb {R}^{m}\) bounded by
∂Ω oriented by its inner normal
n. Denoted by 
q, the magnitude of vector
\({\boldsymbol {q}}=(q_{1},\dots ,q_{m})^{T}\),
\({\boldsymbol {q}}=\sqrt {{q_{1}^{2}}+\dots +{q_{m}^{2}}}\). Let
d(
x) be the signed distance function from
∂Ω. The distance function satisfies the eikonal equation
and boundary conditions
Typically, (
1) is used with the first (Dirichlet) boundary condition in (
2).
$$ \nabla d=1\quad\text{in}\quad{\Omega} $$
(1)
$$ \begin{array}{@{}rcl@{}} d=0,\qquad\partial d/\partial{\boldsymbol{n}}=1,\quad\text{and}\quad \partial^{ k}\!d/\partial{\boldsymbol{n}}^{k}=0, \quad k=2,3,\dots\quad\text{on}\quad\partial{\Omega}. \end{array} $$
(2)
2.2 Screened Poisson distance function approximations
A simple PDEbased approach to estimate
d(
x) consists of considering a Dirichlet boundary value problem for a screened Poisson equation
where
t is a small positive parameter. As shown in [
30, Theorem 2.3],
Thus,
\(\sqrt {t}\ln [1/w({\boldsymbol {x}})]\) approximates
d(
x) and the parameter
t controls the approximation accuracy. This approximation of the distance function was used in [
28] for detecting skeletal structures in grayscale images.
$$ w({\boldsymbol{x}})t{\Delta} w({\boldsymbol{x}})=0\quad\text{in}\quad{\Omega}, \qquad w=1\quad\text{on}\quad\partial{\Omega}, $$
(3)
$$ \lim\limits_{t\to0}\sqrt{t}\ln[1/w({\boldsymbol{x}})] = d({\boldsymbol{x}}). $$
(4)
A simple heuristic behind (
4) can be found, for example, in [
20] and uses the HopfCole transformation [
13]. It is easy to check that substituting
\(w({\boldsymbol {x}})=\exp \left \{v({\boldsymbol {x}})/\sqrt {t}\right \}\) in (
3) yields
\(\nabla v^{2}=1+\sqrt {t}{\Delta } v\), which for small
t can be considered as a regularized version of eikonal (
1).
The geodesicsinheat method [
11,
12], a highly popular distance function approximation, is a close relative of the above approach extended to nonflat geometry. The method is based on the observation that
w(
x) and
v(
x) have the same level sets and construct a distance function approximation
u(
x) as the solution of the following minimization problem
where
m = ∇
w/∇
w and
w(
x) is the solution to (
3).
$$ {\int}_{\Omega}\nabla u {\boldsymbol{m}}^{2}d{\boldsymbol{x}}\rightarrow\min, \qquad u=0\text{ on }\partial{\Omega}, $$
(5)
Advertisement
Practical implementation of the geodesicsinheat method includes numerical solutions to the screened Poisson (
3) and the Poisson equation corresponding to the variational problem (
5).
It is also interesting that (
3) combined with either (
4) or (
5) can serve as a warm start to iterative methods for computing the distance function.
Although both the methods, (
4) and (
5), are based on screened Poisson (
3), to distinguish them we refer to the former as the
screened Poisson method and to the latter as the
heat method. In Section
4, we deal with approximate distance transforms for 2D binary images and provide the reader with simple
matlabbased implementations of both methods.
2.3 Proposed distance function approximation
We now turn to the description of our approach. A key observation is given by the following proposition.
Proposition 1
The distance function
d(
x) delivers the solution to the following energy minimization problem
$$ {\int}_{\Omega}\phi d{\boldsymbol{x}}\longrightarrow\max,\quad\text{where}\quad \max\limits_{\Omega}\nabla\phi\leq1\quad\text{and}\quad\phi=0 \quad\text{on}\quad\partial{\Omega}. $$
(6)
Proof
Indeed, in order to maximize
\({\int }_{\Omega }\phi d{\boldsymbol {x}}\), the function
ϕ(
x) has to grow as fast as possible and its gradient magnitude ∇
ϕ achieves at each point
x its maximal allowed value. Thus, the solution to (
6) satisfies
and, therefore, is the distance function
d(
x). □
$$ \nabla\phi=1\text{ in }{\Omega}\quad\text{and}\quad\phi=0 \text{ on }\partial{\Omega} $$
The constrained energy minimization problem (
6) can be reformulated as the following unconstrained minimization problem
where
$$ F(\phi)+G(\nabla\phi)\rightarrow\min, $$
(7)
$$ F(\phi)={\int}_{\Omega}\phi d{\boldsymbol{x}}, \quad \phi=0\text{ on }\partial{\Omega}, \quad G({\boldsymbol{q}})=\left\{ \begin{array}{ll} 0 & \text{if }\{\boldsymbol{q}}\_{L^{\infty}}\leq1 \\ +\infty & \text{otherwise} \end{array} \right. $$
We solve (
7) numerically by ADMM. The corresponding augmented Lagrangian has the form
where
σ is the vector of Lagrange multipliers and
r > 0 is a regularization parameter. Now ADMM for (
8) yields the following iterative process:
$$ L(\phi,{\boldsymbol{q}},\sigma)={\int}_{\Omega}\left( \phi+G({\boldsymbol{q}})+\sigma\cdot(\nabla\phi{\boldsymbol{q}}) +\frac{r}{2}\nabla\phi{\boldsymbol{q}}^{2}\right) d{\boldsymbol{x}}, $$
(8)
×
The iterative approach presented here shares a lot of similarities with the numerical method proposed in [
15], where ADMM is used to numerically compute the solution to a
pPoisson problem −Δ
_{p}
u = 1. The limit as
\(p \rightarrow \infty \) of the solution to this
pPoisson problem, with vanishing Dirichlet boundary condition, is
d(
x), the distance to the boundary function [
5]. The main difference with the approach proposed here lies in the second step of minimizing (
8) by ADMM, where a simple projection can now be used instead of numerically computing the root of a polynomial.
3 Numerical experiments: distance to a polygonal mesh using FEM and application to curvature computation
We consider first the problem of computing the distance function to
∂Ω, a surface (curve in 2D), represented by a triangle mesh (a polygonal chain in 2D).
As described in Section
2, we use ADMM to minimize (
7). This gives an iterative process, where the first step involves solving a Poisson problem of the form: −Δ
ϕ =
f. This Poisson problem is discretized and solved by the finite elements method. The computational domain bounded by
∂Ω is represented by a triangle mesh in 2
D or a tetrahedral mesh in 3D. Linear basis functions are used at each node of the triangulation. The solution to the Poisson problem is obtained from numerically solving a linear system
AΦ =
b, where the sparse matrix
A, corresponding to a discretization of the Laplacian, is the same for each iteration of ADMM and can thus be prefactored (for example with the Cholesky decomposition).
3.1 Distance computation
Figure
1 illustrates the result obtained by our approach on a 2D polygonal domain with complex geometry. The left image visualizes the exact distance obtained by computing the minimum distance to any boundary segment. The middle image presents the distance computed by solving (
7). The right image demonstrates how the relative residual error
decreases with each iteration when solving (
7) by ADMM. One can observe that (
7) solved numerically by ADMM demonstrates a good convergence and is capable to deliver an accurate approximation of the distance function.
$$ \\phi_{k+1}\phi_{k}\_{2} / \\phi_{k}\_{2} $$
×
As seen in Fig.
2, a similar performance of (
7) with ADMM is achieved for 3D models. In this figure, we visually compare on a planar slice of Ω the function obtained by numerically solving (
7) and the exact distance, which is obtained by computing at a given node of the tetrahedral mesh the minimal distance to the set of triangles corresponding to the input surface
∂Ω.
×
3.2 Comparison to other approaches
In Figs.
3 and
4, we compare the distance function estimation results achieved by solving (
7) with those obtained by using the heat method (
3) and (
5). The results are shown on a planar slice of the domains.
×
×
As seen in Fig.
3, the distance function approximation obtained from minimizing (
7) delivers the best result. This is also confirmed by Fig.
4, where the pointwise relative error w.r.t. the exact distance
is visualized on a planar slice of the domain. Here
u(
x) is the distance function approximation obtained by either (
7) with ADMM, or the heat method (
3) and (
5).
$$ u({\boldsymbol{x}})  d({\boldsymbol{x}}) / d({\boldsymbol{x}}) $$
One can notice that (
7) delivers the best approximation. Some small regions with relatively high errors are likely due to the numerical solution of the ADMM subproblems by the finite element method. Mesh refinement and mesh moving techniques can be used to improve the results.
3.3 Application to surface curvature estimation
We can further use the computed distance to approximate the curvature of the boundary surface
∂Ω. Surface curvature estimation is important for many computer graphics and geometric modeling applications [
8] and remains a subject of intensive research [
21,
27] (see also references therein). It turns out that the distance function from a surface contains full information about the surface curvatures. Namely, the eigenvalues of the Hessian
H of the distance function
d at a boundary point
y are {
κ
_{1},
κ
_{2},0} and the corresponding eigenvectors are {
t
_{1},
t
_{2},
n}, where
t
_{1},
t
_{2} are the principal curvature directions at
y and
n the outward normal to the surface at
y. See, for example, [
18, Section 14.6].
Given an approximation of the distance, computed by numerically solving (
7), and sampled on a tetrahedral mesh, we first approximate the gradient of the distance function ∇
d at each node of the tetrahedral mesh as the normalized weighted average of the gradients in each incident tetrahedron (the volume of the tetrahedron is used as the weight). By repeating this procedure for each component of ∇
d, we obtain an expression of the Hessian of the distance function at each node of the tetrahedral mesh. We then compute the non zero eigenvalues of the Hessian at each boundary node (nodes of the tetrahedral mesh that are on the surface boundary).
Figure
5 illustrates results obtained by this approach for computing the mean curvature,
H = (
κ
_{1} +
κ
_{2})/2 of some surfaces.
×
4 Approximate distance transforms for 2D binary images and skeleton computation
4.1 Approximate distance transforms for 2D binary images
Constructing exact and approximate distances from boundaries of objects is also important for a number of image processing applications [
14], where it is usually called the distance transform. In particular, shape skeletonization, which itself has numerous applications in image processing and computer graphics [
26], can be used as a quality indicator for distance function approximations.
In this section, we focus on computing approximate distance functions for the boundaries of objects represented by 2D binary images. Since the most popular way to encode 2D images consists of representing them using grids of numbers (pixels), we deal with finite difference approximations. We present
matlabbased implementations of the screened Poisson method (
3) and (
4), heat method (
5) of Crane, Weischedel, and Wardetzky [
11,
12], and our method (
7). We demonstrate that typically our method produces a more accurate approximation of the distance function. Finally, we present a simple way to extract skeletons of binary shapes.
matlab allows for a very simple implementation of the screened Poisson based and heat distance function approximations discussed in Section
2.2. Since in this section we use them in our numerical experiments and comparison, we present their implementations below. First, our
matlab implementation of (
3) and (
4) for approximating the distance to the shape of a binary image looks as follows:
×
Next, our
matlab implementation of the heat method [
11,
12] solving (
3) and minimizing (
5) reads as follows:
×
Finally, a simple implementation of the ADMMbased minimization of (
7) in
matlab, relying on its builtin functions, is shown below
×
In the numerical experiments presented below, we compare these three methods (the screened Poisson (
3) and (
4), the heat method (
3) and (
5), and the proposed approach (
7)) for computing the distance to the boundary of binary shapes. We set
t = 0.6 for both the screened Poisson and heat methods, as choosing a smaller value may lead to instabilities. We set
r = 10 and use 50 iterations for our method.
In our experiments, we use two simple geometric shapes (mushroom and keyhole) and four more complex shapes from the Kimia99 dataset [
25]. Figure
6 illustrates the results obtained by these methods on the test shapes. The bottom three rows show the pointwise absolute error of the screened Poisson, the heat method, and our approach, respectively, compared with the exact distance. Quantitative results are provided in Table
1, where the RMS and maximum error for each of the test shapes is provided.
Table 1
RMS and maximum errors for the images in Fig.
6
RMS error

Maximum error



Varadhan

Heat

Ours

Varadhan

Heat

Ours


Mushroom

0.35

0.26

0.16

1.72

1.84

0.79

Keyhole

0.26

0.22

0.14

1.63

1.25

0.69

Hand

0.25

0.26

0.16

1.67

1.86

0.96

Cat

0.17

0.19

0.14

1.21

1.77

1.37

Donkey

0.17

0.18

0.12

1.50

1.63

0.99

Fish

0.10

0.12

0.07

1.02

1.40

1.01

×
The heat method (
5) demonstrates a better stability than the screened Poisson one (
3) and (
4). In particular, the latter collapses for some images tested above if we set
t = 0.5, while the heat method demonstrates slightly better performance. On the other hand, our method (
7) can also benefit from a more accurate selection of the regularization parameter
r. For example, setting
r = 7 makes our method the absolute RMS and maximum error winner for all the images considered above.
4.2 2D binary image skeletonization
The proposed approach for distance estimation can be used to compute skeletons of binary images. The skeleton, or medial axis, is an important shape descriptor, which was introduced more than fifty years ago [
7] and which remain a topic of active research, see, for example, [
1,
26,
32,
33]. The skeleton of a 2D shape can be defined as the locus of centers of inner bitangent circles. Alternatively, given the distance function to the boundary of a shape, the skeleton can be defined as the set of inner distance function singularities. In this study, we use a smooth distance function for constructing an approximate skeleton of a binary image.
Since the magnitude of the gradient of the distance function is equal to one everywhere except at the distance function singularities, it is natural to expect that the points where the gradient of a smooth distance function is small form a thick/fuzzy version of the skeleton. Once such a thick/fuzzy skeleton is extracted, one can get a onepixelwide skeleton by applying
matlab’s
bwmorph function to the thick/fuzzy skeleton.
In Fig.
7, we demonstrate how this gradientofsmoothdistancefunction approach works and compare it with the standard thinningbased binary image skeletonization procedure consisting of applying
bwmorph to the whole binary image. Given a binary image, we start from using (
7) for computing a smooth distance function
u(
x). Then, the fuzzyskeleton function and its normalized version
are evaluated. Here, the factor
\(\sqrt {u({\boldsymbol {x}})}\) is used to suppress image skeletal structures appearing due to small perturbations of the image boundary. As demonstrated by the top row images of Fig.
7,
S
_{n}(
x) delivers a good detection of skeletal structures of the binary images. Applying simple thresholding and thinning by
bwmorph yields onepixelwide skeletons (the middle row of Fig.
7), which are of higher quality than those generated by thinning the original binary images with
bwmorph (the bottom row).
$$ S({\boldsymbol{x}})=\sqrt{u({\boldsymbol{x}})(1\nabla u({\boldsymbol{x}})^{2})} \quad\text{and}\quad S_{n}({\boldsymbol{x}})=S({\boldsymbol{x}})/\max\limits_{{\boldsymbol{x}}}[S({\boldsymbol{x}})] $$
(9)
×
5 Conclusion
In this paper, we have proposed a new variational problem for the distancefromsurface function (
7) and showed how it can be efficiently solved using ADMM. We have presented the results of our numerical experiments when the problem is discretized by FEM or finite differences. We have demonstrated advantages of (
7) over the heat method [
11] and shown that our approach can be used for surface curvature estimation and skeletonization of 2D binary images.
Acknowledgments
The Armadillo and the Bunny mesh models are courtesy of the Stanford Graphics Laboratory. The Fertility mesh model is courtesy of AIM@SHAPE. The Kimia99 binary shape dataset [
25] was downloaded from
https://github.com/mmssouza/kimia99.
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.