1 Introduction

One of the goal of shape analysis is to describe objects with a minimal amount of information. Skeletonization answers this question. The skeleton or medial axis of a shape gives a thin topologically equivalent representation of the original shape. The importance of skeleton was discussed by Blum [4, 5] with motivation from visual perception. Nowadays skeletonization is frequently used in computer vision and pattern recognition. There exist several ways (more or less equivalent) to define the skeleton of a shape in the real plane (see for example [8] for a quick survey and references on the subject). The first one goes back to [4, 5] whose author has introduced the concept of prairie fire in which the shape is imagined to be filled with dry grass and the fire is started at the shape boundary. The boundary propagates with constant normal velocity and the skeleton is traced out by the singular points where the front intersects itself. Another approach is to consider the skeleton as the geometric location of centers of maximal discs contained in the shape [4, 6]. This definition is interesting since, in principle, if the radii of these discs are recorded at the corresponding points on the skeleton, the shape can be recovered as the envelope of all the discs centered on the skeleton with radii recorded. However, in practice, this approach is difficult to implement numerically. A third approach is to consider the skeleton as the set where the gradient of the distance function to the shape is discontinuous. If Ω denotes the shape, the signed distance to Ω is defined, for x∈ℝ2, by \(d(x)=d(x,\partial\varOmega) = \operatorname{inf}_{y \in \partial\varOmega} \|x-y\|\) where ∥x∥ is the Euclidean norm of x. It is well known that the gradient of the distance function satisfies the Eikonal equation ∥∇d(x)∥=1 except at points x where there exist at least two distinct points y and z ∈∂Ω such that d(x)=∥x−y∥=∥x−z∥. The set of such points x form the skeleton and at that points ∇d is discontinuous. We choose this last definition of the skeleton in the rest of the paper and we refer to it as the real or Euclidean skeleton.

The challenge is how to compute the skeleton or an approximation of it. There exist in the literature many different approaches on this issue. Let us only quote some of them: the morphological approach [20, 21, 23, 26], the wavelet approach [32] and those which are embedded in a partial differential equation (PDE) or variational framework [9, 17, 27–29, 31]. In the four first papers the authors highlight the connection between monotonically evolving fronts and the Eikonal equation and they propose various algorithms for tracking shocks. It is well-known that hyperbolic PDEs (as the Eikonal equation) are not easy to solve numerically and very fine algorithms must be used. A different but related point of view is given in [29] where the authors construct a function v whose level curves mimic the curve evolution with a speed consisting of a constant component and a component proportional to curvature. The function v is defined as the minimizer of a Modica-Mortola type functional [22] which approximates the perimeter of the boundary of the shape. More precisely v is the unique solution of the Poisson equation \(\Delta v (x) = \frac{v}{\sigma^{2}}\) in Ω and v=1 on ∂Ω. The smoothed skeleton is then defined as the locus of points where the gradient of v is minimum along the level curves i.e. the points where \(\frac{d\Arrowvert\nabla v \Arrowvert}{ds}=0\). Notice that this framework has been extended to non-local functionals in [30], and its relationship with the notion of scale has been investigated in [3]. See also [13] for a recent overview on skeleton extraction by variational methods. Our model is significantly simpler than those based on the Eikonal equation [17] since it relies on the resolution of the well-known Poisson Δu(x)=−1 with Dirichlet boundary conditions. Our contribution is in the same spirit as [27, 29]: we also solve a Poisson equation (without any parameter) but our algorithm for extracting the skeleton is different from the one proposed in [27, 29]. More precisely if Ω denotes the shape we want to analyze, our algorithm is as follows:

  1. 1.

    We solve the Poisson equation Δu(x)=−1 in Ω, u=0 on ∂Ω.

  2. 2.

    We determine the set

    (1)
  3. 3.

    For each \(x \in\mathcal{A} \), we solve the dynamical system

    $$ \left \{ \begin{array}{l} \xi'(s) = \nabla u(\xi(s)) \\[3pt] \xi(0)=x \end{array} \right . $$
    (2)

    We denote by \(\mathcal{S}_{1}\) the set of trajectories of these flows.

  4. 4.

    Let us define the sets W, E, and F:

    (3)
    (4)
    (5)

    where λ 1 and λ 2 are the eigenvalues of ∇2 u (λ i is real since ∇2 u is symmetric real). W is the set of critical points of u in Ω. E is the set of extremal points of u in Ω (which in fact are maximal points since Δu=−1) and F is the set of saddle points of u in Ω. We set \(\mathcal{S}_{2}\) the trajectories from F to E (see Sect. 5 for more details).

  5. 5.

    The skeleton of Ω is defined by

    $$ \mathcal{S}= \mathcal{S}_1 \cup\mathcal{S}_2 \cup W $$
    (6)

Let us explain briefly why this algorithm furnishes an approximation of the real skeleton. The justification comes from four facts which will be proved in the next sections.

  1. 1.

    Actually the solution of the Poisson equation Δu(x)=−1 in Ω, u=0 on ∂Ω, can be viewed as a regularization of the distance function d.

  2. 2.

    As shown in [17, 18] the real skeleton tends to terminate at the boundary at points of maximal curvature.

  3. 3.

    If d is the distance function and if locally we parametrize the real skeleton by a curve ξ(s) then necessarily ξ(s) satisfies the dynamical system

    $$ \xi'(s) = \nabla d\bigl(\xi(s)\bigr) $$
    (7)

    where here the gradient ∇d of d has to be understood in a generalized sense. Actually d is a function of bounded variations and a meaning can be given to system (7) (see [2]).

  4. 4.

    The trajectories defined in (2) converge asymptotically as s→±∞ to points in the critical set W which is finite.

Let us point out that Poisson equation has also been used in [12] for shape representation. In [12] the authors utilize the gradient and the curvature of the level sets of the solution of Poisson equation for segmenting silhouette, identifying corners and deriving some structures of the skeleton of a shape. In that paper no real mathematical justification is given. Let us also note that Poisson equation is related to the Brownian motion of a set of particles placed inside the shape. Indeed the solution u of Poisson equation measures the mean time required for a particle to hit the boundary [15].

The paper is organized as follows. In Sect. 2 we first recall classical properties of Poisson equation. Then in Sect. 3 we give some reasons why u the solution of Poisson equation can be viewed as a regularization of the distance function. In Sect. 4 we study the dynamical system (2) and in particular its asymptotic behaviour as s→±∞. Then in Sect. 5 we write the detailed algorithm. Finally we illustrate the capability of our algorithm in Sect. 6 by showing several computational examples.

2 Some Results About Poisson Equation

2.1 Classical Results

In this section we recall some well-known properties of the solution u of Poisson equation:

$$ \Delta u (x) = -1 \quad\mbox{if $x$ is in $ \varOmega$, $u=0$ on $\partial \varOmega$.} $$
(8)

Proposition 1

  • Existence and uniqueness: If ∂Ω is Lipschitz then (8) admits a unique solution u in the Sobolev space \(W_{0}^{1,p}(\varOmega), \forall p\in[2, \infty[\).

  • Regularity: If ∂Ω is of class C 2, then u is in \(C^{2}(\bar {\varOmega})\).

  • Maximum principle: There exists C>0 such that 0≤u≤C on \(\bar{\varOmega}\). Moreover, we have 0<u on Ω.

Proof

See [10, 11]. □

As a consequence of Proposition 1, we can then extend u as a C 2 function on ℝ2. This is what we do until the end of the paper (so we suppose that ∂Ω is of class C 2).

2.2 More Refined Properties

We set λ 1≤λ 2 the eigenvalues of ∇2 u (notice that λ i is real since ∇2 u is symmetric real). In Ω, we have Δu=−1=λ 1+λ 2. Hence λ 1<0.

Let us consider the set W, E, and F defined by (3), (4) and (5). W is the set of critical points of u in Ω. E is the set of extremal points of u in Ω (which in fact are maximal points since Δu=−1) and F is the set of saddle points of u in Ω. We give below a nontrivial result due to Alessandrini et al [1] concerning the number of critical points of u. This result is fundamental for our algorithm.

Theorem 1

Let us assume that Ω is a simply connected open set in ℝ2. W is a non empty set, and W contains at most a finite number of points (which are isolated). Moreover, we have #E−#F=1.

Remarks

  1. 1.

    If Ω is convex, then W is reduced to a single point which is the maximizer of u on Ω [19].

    For example [16], if Ω is symmetric and convex in two orthogonal directions, then all the level sets of u are symmetric and convex in those directions. Under those assumptions, the gradient of u vanishes only in a single point, the center of symmetry.

  2. 2.

    If Ω is not simply connected then W can be a curve. For example if Ω is the annulus Ω={(x,y);1≤x 2+y 2≤4}. It is easy to see that \(u(x,y)=\frac{3}{8 \log2} \log(x^{2} + y^{2} ) - \frac{1}{4} (x^{2} + y^{2} + \frac{1}{4})\) is the solution of (8) and

    (9)
    (10)

    Moreover, we have: ∇u(x,y)=(0,0) if and only if \(x^{2} + y^{2} = \frac{3}{2 \log2} \approx2.16\) (notice that (0,0) does not belong to Ω). Hence the set of critical points is a circle of radius \(\sqrt{2.16} \approx1.47\). It is close to 1.5, but not equal to it.

Corollary 1

If x is in W and Ω simply connected, then x is a non degenerate point, i.e. λ 1≠0 and λ 2≠0.

Proof

If one of the eigenvalues is zero, then there exist non isolated critical points (see [14, p. 326]), which contradicts Theorem 1. □

Remark

As a consequence, F (defined by (5)) is in fact:

$$ F= \bigl\{ x \in\varOmega, \ \nabla u (x)=0, \lambda_1 < 0 < \lambda_2 \bigr\} $$
(11)

Proposition 2

There exists α>0 such that ∇u.N≥α on ∂Ω, with N the inner normal to ∂Ω.

Proof

This is a consequence of the Hopf lemma [10], and of the fact that ∂Ω is C 2 and Ω bounded. □

Corollary 2

Let β in (0,α) (with α given by Proposition 2). Then there exists r>0 such that ∇u.N r ≥β on ∂Ω r , with N r the inner normal to ∂Ω r , and

$$ \varOmega_r = \bigl\{ x \in\varOmega, \ d(x,\varOmega) \geq r \bigr \} $$
(12)

Proof

This is a consequence of the fact that u is in C 2(ℝ2) and of Proposition 2. □

3 Relating the Poisson Equation with the Distance Function

In this section we give some heuristic reason showing the connection between the solution of the Poisson equation and the distance function. In all this section we denote by

u(x) the unique solution of Poisson equation:

$$ \Delta u (x) = -1 \quad\mbox{if $x$ is in $\varOmega$, $u(x)=0$ on $\partial \varOmega$.} $$
(13)

First of all, we think there exists no direct relation between u(x) and the Euclidean distance function d(x) i.e. we cannot express u as a function of d. What we can say is as follows:

  • From the potential theory (see [7, 25]) we know there exist two positive constants A and B such that if x is in Ω then

    (14)

  • As pointed out in [27, 29] and illustrated here on Fig. 1 the level curves of u ressemble to those of d and they can be viewed as a regularized version of the level curves of d. In fact u attains its minimum at the shape boundary and (at least for convex domains) increases monotonically from the boundary to the center of the shape.

    Fig. 1
    figure 1

    Level curves of u and d, u being the solution of Δu=−1 inside the shape, and d being the distance function to the boundary of the shape. As pointed out in [27, 29], the level curves of u ressemble to those of d and they can be viewed as a regularized version of the level curves of d

    Full size image

  • A third heuristic argument is: let us consider for ϵ>0 the following PDE:

    $$ \left \{ \begin{array}{l} \epsilon\frac{\partial z }{\partial t}(x,t)=\Delta z (x,t) +1 \quad \mbox{in} \ \varOmega\times(0, \infty) \\[3pt] z(x,t)= 0\quad \mbox{on} \ \partial\varOmega\times(0, \infty) \\[3pt] z(x,0)=d(x) \end{array} \right . $$
    (15)

    where the initial condition d(x) is the Euclidean distance function.

    From [10], Eq. (15) admits a unique regular solution z ϵ (x,t). Thanks to (13), (15) can be written into

    $$ \left \{ \begin{array}{l} \epsilon\frac{\partial z }{\partial t}(x,t)=\Delta z (x,t) - \Delta u (x) \quad \mbox{in} \ \varOmega\times(0, \infty) \\[3pt] z(x,t)= 0 \quad \mbox{on} \ \partial\varOmega\times(0, \infty) \\[3pt] z(x,0)=d(x) \end{array} \right . $$
    (16)

    Setting w ϵ (x,t)=z ϵ (x,t)−u(x) then w ϵ (x,t) is a solution of the following heat equation:

    $$ \left \{ \begin{array}{l} \epsilon\frac{\partial w_\epsilon}{\partial t}(x,t)=\Delta w_\epsilon(x,t) \quad \mbox{in} \ \varOmega\times(0, \infty) \\[3pt] w_\epsilon(x,t)= 0 \quad \mbox{on} \ \partial\varOmega\times(0, \infty) \\[3pt] w_\epsilon(x,0)=d(x) - u(x) \end{array} \right . $$
    (17)

    From classical estimations [10] for the heat equation we get the following estimate:

    $$ \big\|w_\epsilon(.,t)\big\|_{L^2(\varOmega)} \leq\|d-u\|_{L^2(\varOmega)} e^{-(\mu_1 t/\epsilon)} $$
    (18)

    where μ 1 is the first eigenvalue of the Laplacian. From (18) we deduce when ϵ→0+ that for all t>0 then z ϵ (.,t)→u(.). Therefore this convergence shows that z ϵ (x,t) is close to u(x) for ϵ small and for all t>0. But for small t>0, z ϵ (x,t) can be viewed as a smoothed version of the distance function d(x). This argument shows some proximity in the L 2 sense between u and d. Of course this argument does not imply that u is a distance function. More arguments will be given later in Sect. 5.

4 Study of the Dynamical System

In this section we first study the gradient flow (2) associated to u and then we justify why its trajectories can be used as an approximation of the skeleton. From now on, we assume that the shape Ω is a simply connected open set (thus the points in W are isolated thanks to Theorem 1).

4.1 Definitions and Basic Results

We consider the following problem. Let x 0 in \(\bar{\varOmega}\), and:

$$ \left \{ \begin{array}{l} \xi'(s) = \nabla u(\xi(s)) \\[3pt] \xi(0)=x_0 \end{array} \right . $$
(19)

where u is the unique solution of (8).

Remark

Notice that if x 0∈W, then ξ(s)=x 0 for all s in ℝ.

Proposition 3

There exists a unique C 1 function ξ solution of (19). This solution is defined on ℝ.

Proof

The uniqueness of ξ is given by Cauchy-Lipschitz theorem for ODE. The existence on ℝ is standard, since ∇u remains bounded on ℝ2. □

From Theorem 1, we know that the set of critical points of ∇u are isolated points. Moreover, we saw that W={x∈Ω,∇u(x)=0}=E∪F, with E the set of maximal points of u in Ω, and F the set of saddle points of u in Ω.

Let us now state some basic results about the qualitative property of (19) in a neighbourhood of a point in E.

Proposition 4

If x is in E, then x is an attractive point. There exists r>0 such that if x 0 belongs to B(x,r) (the ball of radius r centered in x), then ξ(s)→x as s→+∞.

Proof

See Theorem 8.4, p. 366 of [14]. □

Proposition 5

If x is in F, then x is a saddle point, and we have the following properties:

  1. 1.

    There exists exactly two trajectories ξ i , i=1,2, such that ξ i (s)→x as s→+∞.

  2. 2.

    There exists exactly two trajectories ξ i , i=1,2, such that ξ i (s)→x as s→−∞.

Proof

See Theorem 8.5, p. 371 of [14]. □

Corollary 3

Let us consider ξ the unique solution of (19).

  1. 1.

    Let us assume that there exists an increasing sequence s n such that s n →+∞, and ξ(s n ) converges to some element w of W. Then ξ(s)→w as s→+∞.

  2. 2.

    Let us assume that there exists an decreasing sequence s n such that s n →−∞, and ξ(s n ) converges to some element w of W. Then ξ(s)→w as s→−∞.

Proof

We first remark that the points of W are isolated thanks to Theorem 1. The rest of the proof is a straightforward consequence of Propositions 4 and 5. □

4.2 Qualitative Results

The next theorem states the following fact: given a point x 0 in \(\bar{\varOmega} \backslash W\), there exists a trajectory of the flow (19) such that when s→+∞, ξ(s)→y ∞ with y ∞ in W. Moreover, there exits s 0 in \(\mathbb{R}_{-}^{*}\) such that ξ(s 0)∈∂Ω or ξ(s)→z −∞∈F as s→−∞.

Theorem 2

Let x 0 in \(\bar{\varOmega} \backslash W\). The unique solution ξ of (19) satisfies the two following properties.

  1. 1.

    ξ(s) belongs to Ω for all s>0. Moreover, there exists y ∞ in W (given by (3)) such that: ξ(s)→y ∞ as s→+∞.

  2. 2.

    One of the two following properties hold:

    1. (a)

      There exists s 0 in \(\mathbb{R}_{-}^{*}\) such that ξ(s 0) belongs to ∂Ω, and \(\xi(s) \in\mathbb{R}^{2} \backslash\bar{\varOmega}\) if s<s 0.

    2. (b)

      ξ(s) remains in Ω for all s in ℝ, and there exists z −∞ in F such that: ξ(s)→z −∞ as s→−∞. Moreover, the set of elements x 0, which satisfies this last property, is embedded into a finite number of curves.

Proof

1. We begin by showing the first point of the proposition. The fact that ξ(s) belongs to Ω for all s>0 is a straightforward consequence of Proposition 2.

Let us consider y 0 in Ω such that \(u(y_{0})= \max_{x \in \bar{\varOmega}} u(x)\) and let F be the function:

$$ F(x)= \big\|u(x) - u(y_0) \big\|^2 $$
(20)

F is a Lyapunov function for problem (19). Indeed, F has a minimum in y 0, and if x is in Ω, \(x \in\bar{\varOmega} \backslash W\), then:

$$ \bigl\langle\nabla F (x) , \nabla u(x) \bigr\rangle = 2 \big\|\nabla u (x) \big\|^2 \bigl(u(x)-u(y_0) \bigr)<0 $$
(21)

(using the fact that y 0 is a maximum of u). Assertion 1. is then a standard result on ODE (see [14], p. 363, Theorem 8.2 and Remark, p. 364). For the convenience of the reader we detail the proof below.

We have:

$$ \frac{d}{ds} \bigl(F\bigl(\xi(s)\bigr)\bigr) = \bigl\langle \xi'(s),\nabla F \bigl(\xi(s)\bigr) \bigr\rangle= \bigl\langle\nabla u\bigl(\xi(s)\bigr),\nabla F \bigl(\xi(s)\bigr) \bigr\rangle $$
(22)

Hence:

$$ \frac{d}{ds} \bigl(F\bigl(\xi(s)\bigr)\bigr) = 2\bigl(u \bigl(\xi(s)\bigr)-u(y_0)\bigr) \big\| \nabla u \bigl(\xi(s)\bigr) \big\|^2 < 0 $$
(23)

for all s≥0 since ξ(0)=x 0 is not in W, so s↦F(ξ(s)) is a strictly decreasing non negative function.

ξ(s) belongs to \(\bar{\varOmega}\) for all s≥0, and Ω is bounded. Let us consider an increasing sequence s n which goes to +∞ as n→+∞. Let us denote ξ(s n ) by ξ n . (ξ n ) is a bounded sequence in \(\bar{\varOmega}\). Up to a subsequence, it is thus a convergent sequence.

F(ξ n ) is a strictly decreasing non negative sequence. It is therefore a convergent sequence. In particular, we have F(ξ n )−F(ξ n+1)→0.

But we know that there exists t n in (s n ,s n+1) such that:

$$ \frac{d}{ds}F\bigl(\xi(t_n)\bigr)=F(\xi_{n+1})-F( \xi_n) $$
(24)

ξ(t n ) is a bounded sequence. Hence, up to a subsequence, it is a converging sequence. Let us denote by y ∞ its limit. We have

$$ \frac{d}{ds}F(y_\infty)=0 $$
(25)

This implies with (23) that ∇u(y ∞)=0 and so y ∞ belongs to W. We therefore have shown that any cluster point of ξ n belongs to W. We conclude thanks to Corollary 3 that ξ(s) converges to y ∞.

Remark If W is a singleton then y ∞=y 0 (this is in particular the case when Ω is convex).

2. To show the second point, we first see that if there exists s 0 in \(\mathbb{R}_{-}^{*}\) such that ξ(s 0) belongs to ∂Ω, then \(\xi(s) \in\mathbb{R}^{2} \backslash\bar{\varOmega}\) if s<s 0 (as a straightforward consequence of Proposition 2).

Let β in (0,α) as in Corollary 2. Then if there exists s 1 in ℝ such that ξ(s 1) belongs to ℝ2∖Ω r , there exits s 0 in \(\mathbb{R}_{-}^{*}\) such that ξ(s 0) belongs to ∂Ω (as a consequence of Corollary 2).

Now let us assume that ξ(s) remains in Ω r for all s in ℝ, and let us consider the function:

$$ G(x)= \big\|u(x)\big\|^2 $$
(26)

G is a Lyapunov function for problem (19) with reversed time. The rest of the proof is the same as before. □

We have thus completely determined the behaviour of the trajectories of the flow (19). This is the basis of the algorithm we introduce in the next section.

5 Detailed Algorithm

5.1 Our Approach

In this section we describe our algorithm for constructing the Poisson skeleton of a shape Ω and we show more connection between that skeleton and the real skeleton constructed from the distance function.

We first define the set:

(27)

Then let u be the solution of Poisson equation (8) and the sets W, E and F defined respectively in (3), (4) and (5). For constructing the Poisson skeleton of Ω we consider the following flow starting from x in \(\mathcal{A}\):

$$ \left \{ \begin{array}{l} \xi'(s) = \nabla u(\xi(s)) \\[3pt] \xi(0)=x \end{array} \right . $$
(28)

We denote by \(\mathcal{S}_{1}\) the set of trajectories of these flows. Thanks to Theorem 2, we know that these trajectories converge to points in W. Of course, since the flow starts from x on ∂Ω, we need to remove the beginning of these trajectories. Since x is in \(\mathcal{A}\), it is easy to see that the length of the trajectory to be removed is equal to 1/ρ, where ρ is the curvature of ∂Ω in x [17]. To compute flow (28), we use a dynamical programming approach. Given a point x on the flow, we compute the next point y on the flow, in the neighbourhood of x (8-neighbourhood of x in practice), as the point y for which u(y) is maximum.

We set \(\mathcal{S}_{2}\) the trajectories from F to E. If x is in F, then it is an unstable fixed point of the flow considered here. Thus, from a numerical point of view, one just need to select points in the neighbourhood of x (in 4 or 8 connectivity), and to compute the trajectories from these points with the flow (28).

So the question remains on how to compute the location of the points in F. This could be done by computing the zeros of the function x↦∥∇u(x)∥2 in Ω. But we have found it to be more accurate to see the points in F as the points where the sign of the curvature changes as explained later [27].

Definition

The Poisson skeleton is defined as

$$ \mathcal{S}= \mathcal{S}_1 \cup\mathcal{S}_2 \cup W $$
(29)

Let us explain why the Poisson skeleton can be regarded as an approximation of the real skeleton. The fact that the skeleton tends to terminate at points on the boundary of maximal curvature is well established in the computer vision community (see [17, 18]).

But why using Eq. (28)? Let us suppose that the real skeleton is given by a parametrized curve X(t) and let X 0=X(t 0) be a point on the skeleton. By definition there exist two points A and B on the boundary ∂Ω such that \(d(x_{0},\partial\varOmega)=\lVert X_{0}A \rVert=\lVert X_{0} B \rVert\). It can also be shown that the tangent X′(t 0) is the bissector of the angle (X 0 A,X 0 B) and that the segment AB is orthogonal to \(X'_{0}=X'(t_{0})\) (see Fig. 2).

Fig. 2
figure 2

Local parametrization of the skeleton of an arbitrary shape. X is on the skeleton, and points A and B realize the distance of X to the boundary of the shape. The tangent vector X′ is the bissector of the angle (XA,XB), and the segment AB is orthogonal to X′

Full size image

Let us now define ∇+ d(X 0) (respectively ∇− d(X 0)) as the gradient of the distance function in the direction AX 0 ((respectively BX 0)). It is easily seen that these vectors do exist and that the vector (∇+ d(X 0)+∇− d(X 0)) is parallel to X′(t 0). Let us denote \(\nabla^{\bullet} d(X(t))=\frac {1}{2}(\nabla^{+} d(X(t))+\nabla^{-} d(X(t)))\). From the above considerations the vector ∇• d(X(t)) is parallel to X′(t) and this can be formally expressed as

$$ \nabla^{\bullet} d\bigl(X(t) \bigr)=X'(t) $$
(30)

So we have just shown that if the skeleton is represented by a curve X(t) then necessarily X(t) satisfies (30) which is the flow (28) where u is replaced by d. We think that this observation fully justifies the construction of the Poisson skeleton.

Remarks

  1. 1.

    From a mathematical point of view the writing of (30) can be justified. Actually the distance function belongs to the space: \(\mathit{BV}^{2}(\varOmega)=\{f \in W^{1,1}(\varOmega) ; \frac {\partial f}{\partial x_{i}} \in BV(\varOmega) \ \mbox{for} \ i=1,\ldots,n \}\) and ∇• d is called the preciserepresentation of ∇d. In this setting it can be shown that (30) admits a solution in a generalized meaning (see [2, 24]).

  2. 2.

    Our construction of the Poisson skeleton shares some similarities with the one of Shah et al [27, 29]. In that paper the authors define an approximation of the skeleton as the locus of points where the norm of the gradient of a smoothed distance function v(x) is minimum along the level curves i.e. they solve \(\frac{d\Arrowvert \nabla v \Arrowvert}{ds}=0\) where s is the arc-length along the level curves of v. The smoothed distance v is constructed as the minimum of a Modica-Mortola functional which is characterized by the Poisson equation \(\Delta v (x) = \frac{v}{\sigma^{2}}\) in Ω and v=1 on ∂Ω. Notice that v depends on the parameter σ. Then a direct computation shows that the equation \(\frac {d\Arrowvert\nabla v \Arrowvert}{ds}=0\) is equivalent to

    $$ \frac{v_{xy} (v_{x}^2-v_{y}^2) - v_x v_y (v_{xx}-v_{yy}) }{|\nabla v|^{3}}=0 $$
    (31)

    But this expression is exactly the curvature of the trajectories defined in (28). Indeed, we have: ξ′(s)=∇u(ξ(s)), and thus ξ″(s)=∇u(ξ(s))ξ′(s). We remind the reader that the curvature of a parametrized s↦ξ(s) is:

    $$ \kappa(s)=\frac{\xi{'}_1 \xi{''}_2 -\xi{'}_2 \xi{''}_1 }{((\xi{'}_1)^2+(\xi{'}_1)^2)^{3/2}} $$
    (32)

    So here ξ′1=u x , ξ′2=u y , ξ″1=u xx u x +u yx u y , ξ″2=u xy u x +u yy u y . Hence:

    $$ \kappa(s)=\frac{u_x (u_y u_{yy}+ u_x u_{xy}) - u_y (u_x u_{xx}+ u_y u_{yx}) }{|\nabla u|^{3}} $$
    (33)

    i.e.:

    $$ \kappa(s)=\frac{u_{xy} (u_{x}^2-u_{y}^2) - u_x u_y (u_{xx}-u_{yy}) }{|\nabla u|^{3}} $$
    (34)

    which is precisely the expression (31) where v is replaced by u.

As will be seen in the next section on Figs. 3 to 8, the sign of the curvature gives some indication on where the skeleton is (see [27, 29] for further details). However, as pointed in [27, 29], such an approach gives an approximation of both the skeleton and the anti skeleton: a pruning step is needed afterwards.

Fig. 3
figure 3

Skeleton computation of a moon-like shape. The change of sign of the curvature gives the location of the maximum of the curvature on the boundary of the shape

Full size image

5.2 Basic Examples for Ω

Here we detail basic examples of Ω where we can actually show that the skeleton computed with our algorithm is the true skeleton.

Circle

In such a simple case, it is easy to see that our algorithm give the center of the circle as the unique element of the inner skeleton of the circle.

Ellipse

Again it is easy to show that the center of the ellipse is the unique critical point of u and that \(\frac{\partial u }{\partial y}(x,0)=0\). Moreover, Ω has only two points with maximal curvature: the summits corresponding to the largest radius of the ellipse.

Without any restriction, let us assume that the horizontal axis is the largest radius of the ellipse. Then, since \(\frac{\partial u }{\partial y}(x,0)=0\), it implies that the trajectories starting from these two summits go straight to the center of the ellipse.

We conclude that in this particular case, our algorithm give the exact solution.

Square

Since the diagonal are symmetry axes for Ω, and since the two diagonals are non parallel (in fact they are even orthogonal), we conclude with the same arguments as above that our algorithm provide the user with the exact solution.

Rectangle

Unfortunately, even in such a simple example, it remains an open question to prove that the skeleton given by our algorithm is indeed an approximation of the genuine skeleton. Nevertheless, as will be shown on Fig. 5, our algorithm provide numerically a perfect result.

6 Numerical Examples

In this section, we show some numerical examples to illustrate that indeed our algorithm gives a good approximation of the skeleton. As a comparison, we give the sign of the curvature given by Eq. (34), which is the first step of the approach of [27]. We also show the result provided by the matlab function bwmorph (with option skel) which calculates a medial axis skeleton.

Figures 3 to 8 present results on different simply connected shapes. Our algorithm gives interesting approximation in all cases. The reader should notice the difference between the skeleton provided by our method, and the information given by the sign of the curvature. One should also notice that the intersection of the boundary with the change of sign of the curvature gives a robust and accurate approximation of the location of the local maximum of the curvature along the boundary.

Eventually, the reader should compare the skeleton computed with our approach to the one obtained with the matlab function bwmorph. In the case of the rectangle shape for instance (Fig. 5), both results are almost identical, whereas in the case of the hand with the wise palm (Fig. 8), the results are quite different. This comes from the fact the Poisson skeleton is a good approximation of the Euclidean skeleton in tubular like shapes (like the fingers of the hand in Fig. 8 for instance), but the approximation is not so good with large blobs. The same conclusion can be done with the sign of the curvature given by Eq. (34) (which is the first step of the approach of [27]).

In Fig. 3, we show the obtained result on a moon-like shape. There are already differences between the Poisson skeleton and the Euclidean skeleton.

In Fig. 4, we show the obtained result on a star-like shape. This example is a perfect match for our algorithm.

Fig. 4
figure 4

Skeleton computation of a star-like shape. This kind of shape is perfect for the framework developed in this paper

Full size image

In Fig. 5, we show the obtained result on a rectangle. Notice that the method works although the rectangle boundary is not C 2. As explained above, the Poisson skeleton and the Euclidean skeleton are almost identical in that case.

Fig. 5
figure 5

Skeleton computation of a rectangle shape. Although the boundary is not C 2, our algorithm performs well

Full size image

In Fig. 6, we show the obtained result on a complicated shape. One should notice that the approximate location of the stationary points of the flow are given by the location of the change of signs of the curvature. This is the first example for which E is non void (it is reduced to one point here). In this example, the boundary of the shape are noisy. Notice that our algorithm is still capable of computing a good approximation of the result. Notice also that it seems to have less spurious artifacts than the one computed with bwmorph.

Fig. 6
figure 6

Skeleton computation of a complicated shape with a noisy boundary. Our algorithm works even in the case when the set of saddle points F (5) is non empty (in this case F is reduced to one point). Moreover, the skeleton we compute is not polluted by some spurious artifacts

Full size image

Figure 7 shows another example for which E is non void (it is composed of two points here). Our algorithm handles correctly this case too.

Fig. 7
figure 7

Skeleton computation of a complicated shape. Our algorithm works even in the case when the set of saddle points F (5) is non empty (in this case F is composed of two points)

Full size image

In Fig. 8, we display an example of skeleton computation in the case of a hand with a wide palm. As explained above, the approximation given by the Poisson skeleton is not good within the wide palm, and much better inside the fingers. This illustrates the limitation of the methods: for the Poisson skeleton to give a good approximation of the Euclidean skeleton, the shape should not contain large blobs (the same problem can be noticed in Fig. 3), and it should essentially be made of tubular components (such as the fingers in Fig. 8, or the branches of the star in Fig. 4).

Fig. 8
figure 8

Skeleton computation of a hand with a wide palm. Our algorithm shows its limitations within the wide palm of the hand

Full size image

7 Conclusion

In this paper, we have proposed a novel algorithm to compute an approximation of the skeleton. Based on a mathematical analysis, we gave some insight on why such an approach is well-founded. The Poisson equation has already been used to compute approximation of the skeleton in the computer vision community [12, 27, 29]. We gave here new mathematical arguments to justify such an approach, and we have proposed a new algorithm that seems to perform well, as demonstrated in our numerical examples.