Euclidean Distance-Based Skeletons: A Few Notes on Average Outward Flux and Ridgeness

Abstract

Among the various existing and mathematically equivalent definitions of the skeleton, we consider the set of critical points of the Euclidean distance transform of the shape. The problem of detecting these points and using them to generate a skeleton that is stable, thin and homotopic to the shape has been the focus of numerous papers. Skeleton branches correspond to ridges of the distance map, i.e., continuous lines of points that are local maxima of the distance in at least one direction. Extracting these ridges is a non-trivial task on a discrete grid. In this context, the average outward flux, used in the Hamilton–Jacobi skeleton (Siddiqi et al. in Int J Comput Vis 48(3):215–231, 2002), and the ridgeness measure (Leborgne et al. in J Vis Commun Image Represent 31:165–176, 2015) have been proposed as ridge detectors. We establish the mathematical relation between these detectors and, extending the work in Dimitrov et al. (Computer vision and pattern recognition, pp 835–841, 2003), we study various local shape configurations, on which closed-form expressions or approximations of the average outward flux and ridgeness can be derived. In addition, we conduct experiments to assess the accuracy of skeletons generated using these measures and study the influence of their respective parameters.

1 Introduction

• Question: What did the skeleton say while riding his Harley Davidson motorcycle?

• Answer: Bone to be wild!

Owing to its efficiency in representing shapes, and despite its intrinsic instability to contour deformations, the skeleton, or medial axis [11], is extensively used for shape matching, classification and indexing. Among several advantageous properties over the shape contour itself, it lends itself to the design of shape features with a certain degree of invariance to articulated deformations and reorganization of shape parts [6, 41]. In addition to thinness and homotopy to the shape, a desirable property of the skeleton in the context of shape recognition is stability. A number of recent methods focus on computing a skeleton that captures the main parts of the shape while being stable over global transformations or small local contour deformations [16, 23, 28, 34]. These advantageous features are exploited in shape recognition and matching methods [6, 33, 42, 48].

The choice of a skeletonization algorithm for a given shape depends on the available representation of the shape. When the data available is the border sampled in $\mathbb {R}^{n\in \{2,3\}}$ typically, a polygon when $n=2$ or a triangulated mesh when $n=3$—one would use Voronoi diagram-based algorithms [2, 13, 30, 37]. On the other hand, when the data available is a discrete shape, i.e., a subset of $\mathbb {Z}^{n\in \{2,3\}}$, it is preferable to choose from thinning procedures [4, 10, 26, 38], which iteratively remove border points with topological conditions, and/or distance-based methods [5, 20, 22, 25], which typically detect local maxima of the Euclidean distance transform. Furthermore, distance-based and thinning methods are not mutually exclusive, as some methods combine both aspects, e.g., [40, 43]. This is also the case of the methods studied in this paper.

Several equivalent definitions of the continuous skeleton exist. Among these, one definition is that it is the set of centers of maximally inscribed balls. Let ${\varOmega }\subset \mathbb {R}^{n\in \{2,3\}}$ be a shape in a n-dimensional image. The distance transform $D:{\varOmega }\rightarrow \mathbb {R}^+$ maps a point to the Euclidean distance to its nearest point on the shape border $\partial {\varOmega }$:

$$\begin{aligned} D({\varvec{x}}) = \min _{{\varvec{y}}\in \partial {\varOmega }} \left\| {{\varvec{x}}-{\varvec{y}}}\right\| \end{aligned}$$

The skeleton $\mathcal {S}$ is the subset of ${\varOmega }$ containing centers of maximal balls, or equivalently, balls having at least two distinct contact points on the shape border [23]. The radius of the maximal ball centered at a skeleton point $\varvec{s}$ being $D(\varvec{s})$, the skeleton is defined as

$$\begin{aligned} {\begin{array}{l} \mathcal {S}= \left\{ \varvec{s}\in {\varOmega }~|~\exists {\varvec{p}}, {\varvec{q}}\in \partial {\varOmega }, {\varvec{p}}\ne {\varvec{q}}, \right. \\ \qquad \left. \left\| {\varvec{s}-{\varvec{p}}}\right\| =\left\| {\varvec{s}-{\varvec{q}}}\right\| =D(\varvec{s}) \right\} \end{array}} \end{aligned}$$

Starting from the shape border, if one considers the evolution of a curve in the inward normal direction, the skeleton is the set of locations where fronts collide, namely shocks [44]. Equivalently, skeleton branches correspond to ridges, or crest lines, of the distance map. In other words, skeleton points are local maxima of $D$ in at least one direction, and $\nabla {D}$ is undefined at these points.

The extraction of ridges of the Euclidean distance map, which is the focus of this paper, dates as far back as [5]. The problem was initially addressed in a discrete ad hoc manner, in which a set of discrete kernels were designed to extract ridges. Later, it was formulated in a consistent, continuous framework in the Hamilton-Jacobi skeleton [43], where the Average Outward Flux (AOF), a measure of local divergence of the distance map, was used to distinguish skeleton points from non-skeleton points. The AOF measure was combined with an homotopy-preserving thinning process. Starting from the border, points are iteratively removed by ascending order of AOF, in absolute value. Points with strong AOF being located on local maxima of the distance map, the obtained skeleton is consistent in the Euclidean sense. Numerous works build upon the Hamilton-Jacobi skeleton, such as 3D centerline extraction [12], shock graphs for shape matching [42] and the curvature-density correction of [45]. Theoretical values of the AOF, known as flux invariants, were studied in [18], for a number of local configurations of planar shapes.

We recently introduced the ridgeness measure in [28]. In this method, candidate skeleton points are extracted by filtering the Euclidean distance map with a negative Laplacian of Gaussian (LoG) kernel. Local maxima of the distance map have thus strong ridgeness. In [28], we applied hard thresholding to remove points with insufficient ridgeness. This results in significantly lower complexity in comparison to iterative thinning, but to the detriment of connectivity, as hard thresholding may disconnect skeleton branches. In order to guarantee homotopy to the shape, a reconnection step was added, based on a criterion combining ridgeness and centers of maximal balls.

Both AOF and ridgeness are, roughly speaking, differential operators applied on the distance map. Among other ridge detectors of distance transforms is the skeleton strength map [19, 27, 31]. It is defined as a divergence-like measure of the diffused gradient field $\nabla {D}$, which is the solution of a partial differential equation. Unlike AOF or ridgeness, the skeleton strength map is the solution of a time-iterative process. Since we focus on ridge detectors for which analytical solutions can be derived for specific shape configurations, we do not include this measure in the current study.

To generate a skeleton relevant for recognition tasks, a common processing step is the pruning and/or hierarchization of skeleton branches  [7, 29, 48]. Meaningful branches, generated from significant shape parts, should typically be favored over branches arising from contour details. As regards distance-based skeletonization algorithms, the ridge detection step is crucial, as it affects the amount of branches to be pruned afterward. In their respective methods, the AOF and the ridgeness are thresholded at some stage. Points selected by this thresholding step are retained as candidate skeleton points. A loose thresholding will retain many points, resulting in a possibly high amount of undesirable branches, while an excessive thresholding might remove significant branches. Both measures have a parameter, related to their spatial extent, which impacts the detection. Thus, a principled way of determining the threshold, both according to the spatial parameter and the desired degree of branching, by means other than simple empirical study, would be of significant value.

We believe that studying the behavior of the skeleton measures can provide insights on how to choose their thresholds appropriately. We therefore conduct an analytical study of the measures on a set of local theoretical shape configurations (regular skeleton points, endpoints, etc.). We make multiple contributions. First, we establish the mathematical relation between the AOF and our ridgeness measure. Then, for the AOF, we provide mathematical derivations extending the flux invariants of Dimitrov et al. [18]. We express this particular contribution more explicitly in Sect. 2, once the AOF is defined. As regards the ridgeness, we provide completely new invariants.¹ Some configurations, like ligatures [24, 32, 39]—connections between skeleton branches—are often problematic in skeleton extraction and skeleton-based shape matching. Unlike other local shape configurations, the case of ligature was not studied in [18]. Therefore, we provide an analysis of AOF and ridgeness measures for this particular case. Finally, we report the experiments that we conducted on a shape dataset, in which we vary parameters and thresholds to corroborate our derivations and compared the performances of AOF-based and ridgeness-based skeletons.

2 Ridge Detection in Distance Maps

The AOF and the ridgeness are local detectors of ridges of $D$. As they imply first- and second-order differentiation, at a point ${\varvec{x}}$ where $D$ is twice differentiable, the Laplacian, divergence of gradient and Hessian matrix are linked as follows:

$$\begin{aligned} \mathrm {div}~{\nabla {D}({\varvec{x}})} = \varDelta {D}({\varvec{x}}) = \mathrm {tr}(\mathbf {H}_{D}({\varvec{x}})). \end{aligned}$$

2.1 Average Outward Flux

In a given region $B$, the outward flux of a vector field $\mathbf {v}$ is the amount by which vectors of $\mathbf {v}$ point toward the exterior of $B$. Naturally, the outward flux of $\nabla {D}$ is close to zero in regions located on linear slopes of $D$ (non-skeleton points), whereas it becomes highly negative on ridges of $D$ (skeleton points). Siddiqi et al. [43] defined the skeleton likeliness as the AOF of $\nabla {D}$, i.e., the outward flux in region $B({\varvec{x}})$ centered at ${\varvec{x}}$, normalized by the length of the boundary of $B({\varvec{x}})$:

$$\begin{aligned} \mathrm {aof}({\varvec{x}}) = \frac{\displaystyle {1}}{\displaystyle {\left| {\partial B({\varvec{x}})}\right| }} \int _{\partial B({\varvec{x}})} \nabla {D} \cdot \varvec{n}~\text {d}s \end{aligned}$$

(1)

where $\text {d}s$ is an element of the boundary $\partial B({\varvec{x}})$ of the region $B({\varvec{x}})$ and $\varvec{n}$ is the outward normal along this boundary. Via the divergence theorem,

$$\begin{aligned} \mathrm {aof}({\varvec{x}})= & {} \frac{\displaystyle {1}}{\displaystyle {\left| {\partial B({\varvec{x}})}\right| }} \int _{B({\varvec{x}})} \mathrm {div}~{\nabla {D({\varvec{y}})}}~\text {d}{\varvec{y}}\nonumber \\= & {} \frac{\displaystyle {1}}{\displaystyle {\left| {\partial B({\varvec{x}})}\right| }} \int _{B({\varvec{x}})} \varDelta {D({\varvec{y}})} ~\text {d}{\varvec{y}} \end{aligned}$$

(2)

In [43], region $B$ is chosen as a ball of constant radius $r$. In the 2D case, using Eqs. (1) and (2), the AOF is written as an integral over the circle of radius $r$, spanned by angle $\theta$:

$$\begin{aligned} \mathrm {aof}({\varvec{x}},r) = \frac{\displaystyle {1}}{\displaystyle {2\pi }} \int _0^{2\pi } \nabla {D}\left( {\varvec{x}}+ \left[ \begin{array}{c} \displaystyle r\cos \theta \\ r\sin \theta \end{array} \right] \right) \cdot \left[ \begin{array}{c} \displaystyle \cos \theta \\ \sin \theta \end{array} \right] \text {d}\theta \end{aligned}$$

(3)

The AOF is highly negative for skeleton points and close to zero for non-skeleton points. The skeletonization procedure, described in Algorithm 1, performs flux-ordered thinning, using a max-heap, relying on a criterion based on simple points [10], so that thinness and homotopy to the input shape are maintained. Endpoints such that $\mathrm {aof}({\varvec{x}},r)<{\mathrm {th}_\mathrm {aof}}$ are automatically kept as skeleton points. As soon as a point ${\varvec{p}}$ has been processed, propagation is performed on its 8-connected neighborhood, defined as

$$\begin{aligned} {\mathcal {N}}_8({\varvec{p}}) = \{ {\varvec{q}}\in \mathbb {Z}^2~|~\left\| {{\varvec{q}}-{\varvec{p}}}\right\| _\infty =1 \} \end{aligned}$$

This algorithm theoretically operates in $O(|{\varOmega }|\log |{\varOmega }|)$ iterations—due to the fact that thinning in ordered with respect to the AOF measure—but is close to $O(|{\varOmega }|)$ in practice. Skeletons generated with this procedure are studied in Sect. 4.

2.2 Ridgeness

The n-dimensional Gaussian, with isotropic covariance matrix ${\Sigma } = \sigma ^2\mathbf {I}$, where $\mathbf {I}$ is the $n\times n$ identity matrix and $\sigma$ the standard deviation, is

$$\begin{aligned} G_\sigma ({\varvec{x}}) = \frac{\displaystyle {1}}{\displaystyle {\left( 2\pi \right) ^{n/2} \sigma ^n}}\exp \left( -\,\frac{\displaystyle {\left\| {{\varvec{x}}}\right\| ^2}}{\displaystyle {2\sigma ^2}} \right) \end{aligned}$$

The n-dimensional Laplacian of Gaussian (LoG) filter is

$$\begin{aligned} \varDelta {G_\sigma }({\varvec{x}}) = \frac{\displaystyle {1}}{\displaystyle {\left( 2\pi \right) ^{n/2} \sigma ^{n+2}}}\left( \frac{\displaystyle {\left\| {{\varvec{x}}}\right\| ^2}}{\displaystyle {\sigma ^2}}-n\right) \exp \left( -\,\frac{\displaystyle {\left\| {{\varvec{x}}}\right\| ^2}}{\displaystyle {2\sigma ^2}} \right) \end{aligned}$$

In [28], we defined the ridgeness, at a given scale $\sigma$, as the negative of the LoG-filtered distance transform:

$$\begin{aligned} \mathrm {rdg}({\varvec{x}},\sigma ) = -\,\left( D* \varDelta {G_\sigma } \right) ({\varvec{x}}) \end{aligned}$$

(4)

where $*$ is the convolution operator over $\mathbb {R}^n$. Assuming that the distance function is extended over the entire domain $\mathbb {R}^n$,

$$\begin{aligned} \mathrm {rdg}({\varvec{x}},\sigma ) = -\,\int _{\mathbb {R}^n} D({\varvec{y}}) \varDelta {G_\sigma }({\varvec{x}}-{\varvec{y}}) \text {d}{\varvec{y}} \end{aligned}$$

(5)

or, if $D$ is twice differentiable,

$$\begin{aligned} \mathrm {rdg}({\varvec{x}},\sigma ) = -\,\int _{\mathbb {R}^n} \varDelta {D}({\varvec{y}}) G_\sigma ({\varvec{x}}-{\varvec{y}}) \text {d}{\varvec{y}} \end{aligned}$$

(6)

In our initial method [28], the skeleton construction uses two thresholds on the ridgeness map, namely ${\mathrm {th}_{\mathrm {rdg}-\mathrm {low}}}$ and ${\mathrm {th}_{\mathrm {rdg}-\mathrm {high}}}$. Hard thresholding is performed with respect to ${\mathrm {th}_{\mathrm {rdg}-\mathrm {low}}}$, chosen slightly above 0, in order to remove all points that are unlikely to be skeleton points, in linear time. The initial purpose was to avoid the log-linear complexity of the ordered thinning as in Algorithm 1. However, small branches connected by weak ligatures, as described in Sect. 2.3, can be lost, as skeleton ligature points can have very weak ridgeness. This impediment drastically reduces the range of ${\mathrm {th}_{\mathrm {rdg}-\mathrm {low}}}$ for which an accurate skeleton can be obtained. After thresholding, a thinning pass is performed. Finally, the thin skeleton is pruned with a criterion using, among others, the second threshold ${\mathrm {th}_{\mathrm {rdg}-\mathrm {high}}}$. We now believe that the ridgeness-based skeleton can be generated more simply, in the same way as the AOF-based one. Indeed, a similar homotopy-preserving iterative thinning can be applied, with a single threshold ${\mathrm {th}_\mathrm {rdg}}$. The adaptation of Algorithm 1 to the ridgeness measure will be described in Sect. 4.1.

Fig. 1

Shortcomings of ridges on ligatures and branch extremities. (Left) distance map and (right) ridgeness map. Ligatures create undesirably weak ridges (dashed green ellipse) whereas branch extremities create undesirably strong ridges (dashed red ellipses) (Color figure online)

2.3 Shortcomings and Contributions

We now introduce our contributions on the backdrop of the limitations of existing work. In [43], Siddiqi et al do not report a value for ${\mathrm {th}_\mathrm {aof}}$, which is used for marking skeleton endpoints in Algorithm 1. In [12, p. 220], ${\mathrm {th}_\mathrm {aof}}$ is selected using an empirical approach only, such that 25–40% of the AOF map has values below it. They report a value of − 5.0 for all experiments. In [18, p. 840], a threshold value is given with respect to the minimum object angle² allowed for skeleton endpoints, but no explicit formula, involving the AOF parameter $r$, is given. Similarly, in [28], we only provided an empirical approach to determine threshold(s) on ridgeness. Our position in the current paper, however, is that the thresholds can be chosen by taking into account theoretical values on specific shape configurations and can be expressed with respect to their respective parameters $r$ and $\sigma$.

Theoretical values of the AOF were calculated in [18, 45] for an infinitesimal $r$, i.e., as a limit when $r$ tends to 0. They were not calculated for a general $r$. Moreover, they were calculated for skeleton points only, but not at locations neighboring skeleton points. We extend the work in [18] by providing invariants for any $r$. For some particular types of skeleton points, we perform further extension by generalizing the measure to points near skeleton points. Doing so, we formalize the variation of AOF as the considered points get farther from the skeleton. Since we establish the relation between AOF and ridgeness, we are able to provide equivalent results for the ridgeness.

In addition, we provide a model for ligature skeleton points, induced by connections between branches, which was not studied in [18]. In general, skeleton points are located on significant ridges of $D$. However, there exist non-skeleton points with undesirably high—in absolute value—AOF or ridgeness (typically, points in branch extremities) and, conversely, skeleton with undesirably low AOF or ridgeness (typically, ligature points). This phenomenon is depicted in Fig. 1. Note that the presence of undesirably strong ridges near branch extremities is amplified by discretization artifacts. Ligature points are problematic [24, 32, 39], as they are weak ridges of $D$, that should nevertheless be kept as part of the skeleton.

3 Theoretical Values for AOF and Ridgeness

We use a novel approach to study the various skeleton points, inspired by the classifications in [18, 21, 39]. We consider the following types:

• regular skeleton points

• peak points

• end points

• ligature points

• junction points

We calculate theoretical values of the AOF in Eq. (3) and ridgeness in Eqs. (5) for local shape configurations corresponding to these types of skeleton points. For some configurations, integrals can be calculated explicitly, while other configurations require approximations of $D$ so that closed-form expressions can be obtained. A useful property, that will be used subsequently, is the rotation-invariance of the AOF and ridgeness. To be more precise, $\mathrm {aof}({\varvec{x}},r)$ and $\mathrm {rdg}({\varvec{x}},\sigma )$ do not change if the shape is rotated with center ${\varvec{x}}$. The following derivations are valid for any orientation of the skeleton branch under study. As will be derived, the AOF and ridgeness have the advantageous property of being independent of the local thickness of the shape, i.e., of the absolute value of $D({\varvec{x}})$. They rather depend on the local geometry of the shape borders.

As the ridgeness measure implies convolution of $D$ with an infinite support kernel, the distance map is extended outside the object, so that it is defined everywhere. We thus consider the signed distance transform

$$\begin{aligned} D({\varvec{x}}) = \left\{ {\begin{array}{rl} \min _{{\varvec{y}}\in \partial {\varOmega }} \left\| {{\varvec{y}}-{\varvec{x}}}\right\| &{}\quad \text { if } {\varvec{x}}\in {\varOmega }\\ -\min _{{\varvec{y}}\in \partial {\varOmega }} \left\| {{\varvec{y}}-{\varvec{x}}}\right\| &{}\quad \text { if } {\varvec{x}}\notin {\varOmega }\end{array}} \right. \end{aligned}$$

(7)

To begin with, we establish the link between the two measures.

Proposition 1

The AOF and ridgeness at point ${\varvec{x}}$ are related as follows:

$$\begin{aligned} \mathrm {rdg}({\varvec{x}},\sigma ) = -\frac{\displaystyle {1}}{\displaystyle {\sigma ^4}} \int _0^\infty \rho ^2\exp \left( -\frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}}\right) \mathrm {aof}({\varvec{x}},\rho )~\text {d}\rho \end{aligned}$$

(8)

Proof

The proof is given in Appendix A.1 $\square$

In what follows, we omit the second parameter for AOF and ridgeness. Thus it is assumed that

$$\begin{aligned} \mathrm {aof}({\varvec{x}})= & {} \mathrm {aof}({\varvec{x}},r) \\ \mathrm {rdg}({\varvec{x}})= & {} \mathrm {rdg}({\varvec{x}},\sigma ) \end{aligned}$$

Fig. 2

Regular skeleton point

3.1 Regular Skeleton Point

Let $\varvec{\gamma }:[0,1] \rightarrow \mathbb {R}^2$ be a parametrization of the shape contour $\partial {\varOmega }$. The parameterization is continuously differentiable and positively oriented, so that $\frac{\displaystyle {\varvec{\gamma }'(u)}}{\displaystyle {\left\| {\varvec{\gamma }'(u)}\right\| }}$ and $\frac{\displaystyle {\varvec{\gamma }'(u)^\perp }}{\displaystyle {\left\| {\varvec{\gamma }'(u)}\right\| }}$ are the unit tangent and inward normal vectors, respectively, at position u. Consider a skeleton point $\varvec{s}$, as the center of a maximal disk tangent to the contour at two points $\varvec{\gamma }_1$ and $\varvec{\gamma }_2$. We denote by ${\varvec{n}_1}$ and ${\varvec{n}_2}$ the unit normal vectors at $\varvec{\gamma }_1$ and $\varvec{\gamma }_2$, respectively. This regular skeleton point configuration is illustrated in Fig. 2.

The distance between a point ${\varvec{x}}$ and a line with origin ${\varvec{p}}$ and unit direction vector $\varvec{v}$ is $({\varvec{x}}-{\varvec{p}})\cdot \varvec{v}^\perp$. Thus, if we locally approximate parts of the contour around $\varvec{\gamma }_1$ and $\varvec{\gamma }_2$ with straight lines, distance $D$ in the neighborhood of $\varvec{s}$ is

$$\begin{aligned} D({\varvec{x}}) = D(\varvec{s}) + \min (({\varvec{x}}-\varvec{s})\cdot {\varvec{n}_1}, ({\varvec{x}}-\varvec{s})\cdot {\varvec{n}_2}) \end{aligned}$$

(9)

The unit direction of the skeleton branch is

$$\begin{aligned} \varvec{t}= \frac{\displaystyle {{\varvec{n}_1}^\perp -{\varvec{n}_2}^\perp }}{\displaystyle {\left\| {{\varvec{n}_1}-{\varvec{n}_2}}\right\| }} \end{aligned}$$

Let $\alpha$ be the object angle, as introduced in [18], which is half the angle formed by the two inward unit normal vectors. Note that ${\varvec{n}_1}\cdot {\varvec{n}_2}=\cos (2\alpha )$ and $\left\| {{\varvec{n}_1}-{\varvec{n}_2}}\right\| =2\sin \alpha$. When the two contour parts are parallel, the object angle is $\frac{\displaystyle {\pi }}{\displaystyle {2}}$. For every point ${\varvec{x}}$ located on the skeleton, i.e., $\exists ~k~\text {s.t.}~{\varvec{x}}=\varvec{s}+k\varvec{t}$, $D$ is not differentiable. However, we can still derive the expressions of the gradient and Laplacian of $D$, using identity $\min (x,y)=\frac{\displaystyle {x+y-\left| x-y \right| }}{\displaystyle {2}}$

$$\begin{aligned} {\begin{array}{l} \nabla {D}({\varvec{x}}) = \frac{\displaystyle {1}}{\displaystyle {2}}\left( {\varvec{n}_1}+ {\varvec{n}_2}-\mathrm {sgn}(({\varvec{x}}-\varvec{s}) \cdot ({\varvec{n}_1}- {\varvec{n}_2}))({\varvec{n}_1}-{\varvec{n}_2}) \right) \\ \varDelta {D}({\varvec{x}}) = -\delta (({\varvec{x}}-\varvec{s})\cdot ({\varvec{n}_1}-{\varvec{n}_2})) \left\| {{\varvec{n}_1}-{\varvec{n}_2}}\right\| ^2 \end{array}} \end{aligned}$$

(10)

where $\delta$ is the Dirac distribution, implying that the gradient and Laplacian should be understood in the sense of distributions (weak derivatives).

As will be derived, the AOF and ridgeness at skeleton point $\varvec{s}$ depend on object angle $\alpha$. In what follows, we calculate the AOF and ridgeness measures for any point ${\varvec{x}}$ in the vicinity of $\varvec{s}$. As we will see, in absolute value, both are decreasing functions of $\left| ({\varvec{x}}-\varvec{s})\cdot \varvec{t}^\perp \right|$, the distance between ${\varvec{x}}$ and the nearest point on the skeleton.

3.1.1 Average Outward Flux

Proposition 2

The AOF at a point ${\varvec{x}}$ in the neighborhood of a regular skeleton point $\varvec{s}$, with object angle $\alpha$, is

$$\begin{aligned} \mathrm {aof}_\mathrm {regular}({\varvec{x}}) = \left\{ {\begin{array}{l} -\frac{\displaystyle {2\sin \alpha }}{\displaystyle {\pi r}}\sqrt{r^2-(({\varvec{x}}-\varvec{s})\cdot \varvec{t}^\perp )^2} \\ \quad \qquad \text {if } \left| ({\varvec{x}}-\varvec{s})\cdot \varvec{t}^\perp \right| <r\\ 0 ~~~\hbox {otherwise} \end{array}} \right. \end{aligned}$$

(11)

Proof

The proof is given in Appendix A.2 $\square$

As a geometric interpretation, notice that $2\sqrt{r^2-(({\varvec{x}}-\varvec{s})\cdot \varvec{t}^\perp )^2}$ is the length of the line segment resulting from the intersection of the disk and the skeleton branch. As a particular case, when the point is the skeleton point $\varvec{s}$,

$$\begin{aligned} \mathrm {aof}_\mathrm {regular}(\varvec{s}) = -\,\frac{\displaystyle {2}}{\displaystyle {\pi }}\sin \alpha \end{aligned}$$

(12)

as found in [18]. A notable property is that the AOF at regular skeleton point is independent of $r$. The most salient regular skeleton point is obtained when the two contour parts are parallel, i.e., $\alpha =\frac{\displaystyle {\pi }}{\displaystyle {2}}$, which gives $\mathrm {aof}_\mathrm {regular}(\varvec{s})= -\,\frac{\displaystyle {2}}{\displaystyle {\pi }}$.

3.1.2 Ridgeness

Proposition 3

The ridgeness at a point ${\varvec{x}}$ in the neighborhood of a regular skeleton point $\varvec{s}$, with object angle $\alpha$, is

$$\begin{aligned} \mathrm {rdg}_\mathrm {regular}({\varvec{x}}) = \frac{\displaystyle {\sqrt{2\pi }\sin \alpha }}{\displaystyle {\pi \sigma }} \exp \left( -\,\frac{\displaystyle {(({\varvec{x}}-\varvec{s})\cdot \varvec{t}^\perp )^2}}{\displaystyle {2\sigma ^2}} \right) \end{aligned}$$

(13)

Proof

The proof is given in Appendix A.3. $\square$

It is easy to see from Eq. (13) that the ridgeness decreases with a Gaussian profile as ${\varvec{x}}$ gets farther from the skeleton branch. As a particular case, when the point is the skeleton point $\varvec{s}$,

$$\begin{aligned} \mathrm {rdg}_\mathrm {regular}(\varvec{s}) = \frac{\displaystyle {\sqrt{2\pi }}}{\displaystyle {\pi \sigma }}\sin \alpha \end{aligned}$$

(14)

Again, the highest ridgeness value appears when the two contour parts are parallel, which leads to $\mathrm {rdg}_\mathrm {regular}(\varvec{s})=\frac{\displaystyle {\sqrt{2\pi }}}{\displaystyle {\pi \sigma }}.$

3.2 Peak Point

Fig. 3

Peak point. a Distance. b Average outward flux with $r=2$. c Ridgeness with  $\sigma =2$

If ${\varOmega }$ is a disk, there exist only one skeleton point $\varvec{s}$ at its center, which is a local maximum of $D$. The distance function is then

$$\begin{aligned} D({\varvec{x}}) = D(\varvec{s})-\left\| {\varvec{s}-{\varvec{x}}}\right\| \end{aligned}$$

(15)

which is non-differentiable at $\varvec{s}$. Otherwise, for any ${\varvec{x}}\ne \varvec{s}$,

$$\begin{aligned} \nabla {D}({\varvec{x}})= & {} \frac{\displaystyle {\varvec{s}-{\varvec{x}}}}{\displaystyle {\left\| {\varvec{s}-{\varvec{x}}}\right\| }} \nonumber \\ \varDelta {D}({\varvec{x}})= & {} -\frac{\displaystyle {1}}{\displaystyle {\left\| {\varvec{s}-{\varvec{x}}}\right\| }} \end{aligned}$$

(16)

This case is depicted in Fig. 3a. It is of little practical use in itself, as the shape to be skeletonized is rarely a disk. However, in Sect. 3.3, we derive the more general endpoint case from the current case. For calculating both AOF and ridgeness at ${\varvec{x}}$, we switch to a polar coordinate system, centered at ${\varvec{x}}$ s.t. $\varvec{s}={\varvec{x}}+[\mathcal {R}\cos \beta , \mathcal {R}\sin \beta ]^\mathrm {T}$, and show that $\mathrm {aof}$ and $\mathrm {rdg}$ are decreasing functions (in absolute value) of distance $\mathcal {R}=\left\| {{\varvec{x}}-\varvec{s}}\right\|$.

3.2.1 Preliminary Notes on Elliptic Integrals

We define special functions that arise when deriving the AOF and ridgeness of points in the neighborhood of a peak point. Given an argument $\psi \in \left[ 0,\frac{\displaystyle {\pi }}{\displaystyle {2}}\right]$ and a modulus $k\in [0,1]$, $\mathrm {F}(\psi ,k)$ and $\mathrm {E}(\psi ,k)$ are Legendre’s incomplete elliptic integrals of the first and second kind [15, p. 486], respectively, defined as

$$\begin{aligned} \mathrm {F}(\psi ,k)= & {} \int _0^\psi \frac{\displaystyle {1}}{\displaystyle {\sqrt{1-k^2\sin ^2 \theta }}} \text {d}\theta \nonumber \\ \mathrm {E}(\psi ,k)= & {} \int _0^\psi \sqrt{1-k^2\sin ^2 \theta } \text {d}\theta \end{aligned}$$

(17)

A particular case arises when $\psi =\frac{\displaystyle {\pi }}{\displaystyle {2}}$, which leads to the so-called complete elliptic integrals of the first and second kind, respectively:

$$\begin{aligned} \mathrm {K}(k)= \mathrm {F}\left( \frac{\displaystyle {\pi }}{\displaystyle {2}},k\right) \quad \mathrm {E}(k)= \mathrm {E}\left( \frac{\displaystyle {\pi }}{\displaystyle {2}},k\right) \end{aligned}$$

(18)

These integrals have no closed-form expressions. They can be numerically evaluated using Landen’s transformation, related to the arithmetic-geometric mean [15, p. 493]. Moreover, closed-form approximations and bounds for them have been extensively studied [1, 3, 14, 36]. These bounds should be understood in the pointwise sense, i.e., w.r.t k. Let $A$ be the generalized mean of two real numbers a and b, also known as the power mean,

$$\begin{aligned} A_p(a,b) = \left\{ {\begin{array}{ll} \left( \frac{\displaystyle {a^p+b^p}}{\displaystyle {2}} \right) ^\frac{1}{p} &{} \text { if } p\ne 0 \\ \sqrt{ab} &{} \text { if } p=0 \end{array}} \right. \end{aligned}$$

Special cases include the geometric mean ($p=0$) and the arithmetic mean ($p=1$). We also define the logarithmic mean:

$$\begin{aligned} L(a,b) = \left\{ {\begin{array}{ll} 0 &{}\quad \text{ if } a=0 \text{ or } b=0 \\ a &{}\quad \text{ if } a=b \\ \frac{\displaystyle {a-b}}{\displaystyle {\log a -\log b}} &{}\quad \text { otherwise} \end{array}} \right. \end{aligned}$$

According to [14, 46], the following inequality holds:

$$\begin{aligned} A_0(a,b)<L(a,b)<A_1(a,b)<A_p(a,b) \text { with } p>1 \end{aligned}$$

(19)

Introducing the complementary modulus $k'=\sqrt{1-k^2}$, bounds for the complete elliptic integral of the first kind are [1, 14, 36]:

$$\begin{aligned} \frac{\displaystyle {\pi }}{\displaystyle {2A_p(1,k')}}< \mathrm {K}(k) < \frac{\displaystyle {\pi }}{\displaystyle {2A_0(1,k')}} \text { with } p\ge \frac{\displaystyle {1}}{\displaystyle {2}} \end{aligned}$$

Note that a sharper upper bound can be found in [14]:

$$\begin{aligned} \mathrm {K}(k) < \frac{\displaystyle {\pi }}{\displaystyle {2L(1,k')}} \end{aligned}$$

The following bounds for $\mathrm {E}$ are due to [8, 9, 47]:

$$\begin{aligned} \frac{\displaystyle {\pi }}{\displaystyle {2}}A_p(1,k')< \mathrm {E}(k) < \frac{\displaystyle {\pi }}{\displaystyle {2}}A_2(1,k') \text { with } p\le \frac{\displaystyle {3}}{\displaystyle {2}} \end{aligned}$$

We denote the following lower and upper bounds for $\mathrm {K}$ and $\mathrm {E}$ involving generalized and logarithmic means:

$$\begin{aligned} \mathcal {L}_\mathrm {K}^p(k)= & {} \frac{\displaystyle {\pi }}{\displaystyle {2A_p(1,k')}} \text { with }~p\ge \frac{\displaystyle {1}}{\displaystyle {2}} \\ \mathcal {U}_\mathrm {K}^0(k)= & {} \frac{\displaystyle {\pi }}{\displaystyle {2A_0(1,k')}} \\ \mathcal {U}_\mathrm {K}^\mathrm {L}(k)= & {} \frac{\displaystyle {\pi }}{\displaystyle {2L(1,k')}} \\ \mathcal {L}_\mathrm {E}^p(k)= & {} \frac{\displaystyle {\pi }}{\displaystyle {2}}A_p(1,k') \text { with }~p\le \frac{\displaystyle {3}}{\displaystyle {2}} \\ \mathcal {U}_\mathrm {E}(k)= & {} \frac{\displaystyle {\pi }}{\displaystyle {2}}A_2(1,k') \end{aligned}$$

The sharper lower bound $\mathcal {L}_\mathrm {K}^p(k)$ is obtained with $p=1/2$, while the sharper lower bound $\mathcal {L}_\mathrm {E}^p(k)$ is obtained with $p=3/2$.

3.2.2 Average Outward Flux

Using polar coordinates centered at ${\varvec{x}}$ and Eqs. (3) and  (16), we obtain the following result:

Proposition 4

The AOF at a point ${\varvec{x}}$, at distance $\mathcal {R}=\left\| {{\varvec{x}}-\varvec{s}}\right\|$ from a peak skeleton point $\varvec{s}$ is

$$\begin{aligned} \mathrm {aof}_\mathrm {peak}({\varvec{x}}) = \frac{\displaystyle {1}}{\displaystyle {\pi }} \int _0^\pi \frac{\displaystyle {-\,r+ \mathcal {R}\cos \theta }}{\displaystyle {\sqrt{r^2+\mathcal {R}^2 -2r\mathcal {R}\cos \theta }}}\hbox {d}\theta \end{aligned}$$

(20)

Proposition 5

The AOF at a point ${\varvec{x}}$, at distance $\mathcal {R}=\left\| {{\varvec{x}}-\varvec{s}}\right\|$ from a peak skeleton point $\varvec{s}$ can be expressed using complete elliptic integrals as

$$\begin{aligned} \mathrm {aof}_\mathrm {peak}({\varvec{x}}) = \frac{\displaystyle {1}}{\displaystyle {\pi r}} \left( (\mathcal {R}-r)\mathrm {K}(k) - (\mathcal {R}+r)\mathrm {E}(k) \right) \end{aligned}$$

(21)

with $k=\frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+r}}$.

Proof

The proofs for the two previous propositions are given in Appendix A.5. $\square$

Note that k is the ratio between the geometric and arithmetic means of $r$ and $\mathcal {R}$, which verifies, according to Eq. (19),

$$\begin{aligned} \frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+r}} \le 1 \end{aligned}$$

Let us compute bounds with $k=\frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+ r}}$. In our case, the complementary modulus is

$$\begin{aligned} k'= \sqrt{1-k^2} = \frac{\displaystyle {\left| \mathcal {R}-r\right| }}{\displaystyle {\mathcal {R}+r}} \end{aligned}$$

Using identities $a+b+\left| a-b\right| =2\max (a,b)$ and $a+b-\left| a-b\right| =2\min (a,b)$, we obtain

$$\begin{aligned} \mathcal {L}_\mathrm {K}^{1/2} \left( \frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+ r}} \right)= & {} \frac{\displaystyle {\pi (\mathcal {R}+r)}}{\displaystyle {\max (\mathcal {R},r) + \sqrt{\left| \mathcal {R}^2-r^2 \right| }}} \\ \mathcal {L}_\mathrm {K}^1 \left( \frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+ r}} \right)= & {} \frac{\displaystyle {\pi (\mathcal {R}+r)}}{\displaystyle {2\max (\mathcal {R},r)}} \\ \mathcal {U}_\mathrm {K}^0\left( \frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+ r}} \right)= & {} \frac{\displaystyle {\pi (\mathcal {R}+r)}}{\displaystyle {2\sqrt{\left| \mathcal {R}^2-r^2 \right| }}} \\ \mathcal {U}_\mathrm {K}^\mathrm {L}\left( \frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+ r}} \right)= & {} \frac{\displaystyle {\pi (\mathcal {R}+r)}}{\displaystyle {4\min (\mathcal {R},r)}}\log \left( \frac{\displaystyle {\mathcal {R}+r}}{\displaystyle {\left| \mathcal {R}-r\right| }}\right) \\ \mathcal {L}_\mathrm {E}^{3/2}\left( \frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+ r}} \right)= & {} \frac{\displaystyle {\pi }}{\displaystyle {2^{5/3}}}\frac{\displaystyle {\left( \sqrt{(\mathcal {R}+r)^3} + \sqrt{|\mathcal {R}-r|^3}\right) ^{2/3}}}{\displaystyle {\mathcal {R}+r}} \\ \mathcal {L}_\mathrm {E}^1\left( \frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+ r}} \right)= & {} \frac{\displaystyle {\pi \max (\mathcal {R},r)}}{\displaystyle {2(\mathcal {R}+r)}} \\ \mathcal {U}_\mathrm {E}\left( \frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+ r}} \right)= & {} \frac{\displaystyle {\pi \sqrt{\mathcal {R}^2+r^2}}}{\displaystyle {2(\mathcal {R}+r)}} \end{aligned}$$

Proposition 6

The AOF at a point ${\varvec{x}}$, at distance $\mathcal {R}=\left\| {{\varvec{x}}-\varvec{s}}\right\|$ from a peak skeleton point $\varvec{s}$ is bounded as

$$\begin{aligned} \mathcal {L}_{\mathrm {aof}_\mathrm {peak}}< \mathrm {aof}_\mathrm {peak}({\varvec{x}}) < \mathcal {U}_{\mathrm {aof}_\mathrm {peak}}\end{aligned}$$

with

$$\begin{aligned} {\begin{array}{l} \mathcal {L}_{\mathrm {aof}_\mathrm {peak}}\\ \quad = \left\{ {\begin{array}{l} \frac{\displaystyle {1}}{\displaystyle {\pi r}} \left( (\mathcal {R}-r)\mathcal {U}_\mathrm {K}(k)-(\mathcal {R}+r)\mathcal {U}_\mathrm {E}(k)\right) \,\mathrm{if }\, \mathcal {R}\le r\\ \frac{\displaystyle {1}}{\displaystyle {\pi r}} \left( (\mathcal {R}-r)\mathcal {L}_\mathrm {K}^p(k)-(\mathcal {R}+r)\mathcal {U}_\mathrm {E}(k)\right) \, \mathrm{if }\, \mathcal {R}>r\end{array}} \right. \end{array}} \end{aligned}$$

(22)

$$\begin{aligned} {\begin{array}{l} \mathcal {U}_{\mathrm {aof}_\mathrm {peak}}\\ \quad = \left\{ {\begin{array}{l} \frac{\displaystyle {1}}{\displaystyle {\pi r}} \left( (\mathcal {R}-r)\mathcal {L}_\mathrm {K}^p(k)-(\mathcal {R}+r)\mathcal {L}_\mathrm {E}^p(k)\right) \,\mathrm{if }\, \mathcal {R}\le r\\ \frac{\displaystyle {1}}{\displaystyle {\pi r}} \left( (\mathcal {R}-r)\mathcal {U}_\mathrm {K}(k)-(\mathcal {R}+r)\mathcal {L}_\mathrm {E}^p(k)\right) \, \mathrm{if }\, \mathcal {R}>r\end{array}} \right. \end{array}} \end{aligned}$$

(23)

where $\mathcal {U}_\mathrm {K}$ is either $\mathcal {U}_\mathrm {K}^0$ or $\mathcal {U}_\mathrm {K}^\mathrm {L}$.

If one chooses $\mathcal {U}_\mathrm {K}^0$ and $p=1$ for both $\mathcal {L}_\mathrm {K}^p$ and $\mathcal {L}_\mathrm {E}^p$, one obtains the bounds with the simplest expressions:

$$\begin{aligned} \mathcal {L}_{\mathrm {aof}_\mathrm {peak}}^1= \left\{ {\begin{array}{ll} -\frac{\displaystyle {1}}{\displaystyle {2r}}\left( \sqrt{r^2-\mathcal {R}^2}+\sqrt{r^2+\mathcal {R}^2} \right) &{} \text { if } \mathcal {R}\le r\\ \frac{\displaystyle {1}}{\displaystyle {2r}}\left( \frac{\displaystyle {\mathcal {R}^2-r^2}}{\displaystyle {\mathcal {R}}}-\sqrt{\mathcal {R}^2+r^2}\right) &{} \text { if } \mathcal {R}>r\end{array}} \right. \end{aligned}$$

$$\begin{aligned} \mathcal {U}_{\mathrm {aof}_\mathrm {peak}}^1= \left\{ {\begin{array}{ll} \frac{\displaystyle {\mathcal {R}^2}}{\displaystyle {2r^2}}-1 &{} \text { if } \mathcal {R}\le r\\ \frac{\displaystyle {1}}{\displaystyle {2r}}\left( \sqrt{\mathcal {R}^2-r^2} -\mathcal {R}\right) &{} \text { if } \mathcal {R}>r\end{array}} \right. \end{aligned}$$

The previous lower and upper bounds are rather loose. Choosing $\mathcal {U}_\mathrm {K}^\mathrm {L}$, $\mathcal {L}_\mathrm {K}^{1/2}$ and $\mathcal {L}_\mathrm {E}^{3/2}$, much sharper bounds are obtained, which we denote by $\mathcal {L}_{\mathrm {aof}_\mathrm {peak}}^2$ and $\mathcal {U}_{\mathrm {aof}_\mathrm {peak}}^2$. Their expressions, which are tedious, can be easily derived from Eqs. (22) and (23). The bounds are plotted versus $\mathcal {R}$, with $r$ fixed, in Fig. 4.

The analytical expressions of the bounds are intricate. It appears that the second-order Taylor expansion of $D$ gives a suitable approximation to $\mathrm {aof}_\mathrm {peak}$ as soon as $\mathcal {R}$ is large enough. Let $\widetilde{D}$ be the second-order Taylor approximation of $D$ in the neighborhood of ${\varvec{x}}$:

$$\begin{aligned} \widetilde{D}({\varvec{y}})= & {} D({\varvec{x}}) + ({\varvec{y}}-{\varvec{x}})^\mathrm {T}\nabla {D}({\varvec{x}}) \nonumber \\&+ \frac{\displaystyle {1}}{\displaystyle {2}} ({\varvec{y}}-{\varvec{x}})^\mathrm {T} \mathbf {H}_{D}({\varvec{x}})({\varvec{y}}-{\varvec{x}}) \nonumber \\ D({\varvec{y}})= & {} \widetilde{D}({\varvec{y}}) + \mathcal {O}(\left\| {{\varvec{y}}-{\varvec{x}}}\right\| ^3) \end{aligned}$$

(24)

The approximate AOF is

$$\begin{aligned} {\begin{array}{l} \widetilde{\mathrm {aof}}({\varvec{x}})\\ \quad = \frac{\displaystyle {1}}{\displaystyle {2\pi }}\int _0^{2\pi }\nabla {\widetilde{D}} \left( {\varvec{x}}+\left[ \begin{array}{c} \displaystyle r\cos \theta \\ r\sin \theta \end{array} \right] \right) \cdot \left[ \begin{array}{c} \displaystyle \cos \theta \\ \sin \theta \end{array} \right] ~\text {d}\theta \end{array}} \end{aligned}$$

(25)

Proposition 7

The second-order approximation of the AOF at a point ${\varvec{x}}$, at distance $\mathcal {R}=\left\| {{\varvec{x}}-\varvec{s}}\right\|$ from a peak skeleton point $\varvec{s}$ is

$$\begin{aligned} \widetilde{\mathrm {aof}}_\mathrm {peak}({\varvec{x}}) = -\frac{\displaystyle {r}}{\displaystyle {2\mathcal {R}}} \end{aligned}$$

Proposition 8

The AOF at ${\varvec{x}}$ is asymptotically equivalent to its second-order approximation

$$\begin{aligned} \mathrm {aof}_\mathrm {peak}({\varvec{x}}) \sim \widetilde{\mathrm {aof}}_\mathrm {peak}({\varvec{x}}) \text { (as }\left\| {{\varvec{x}}-\varvec{s}}\right\| \rightarrow +\,\infty \text {)} \end{aligned}$$

Proof

The proofs for the two previous propositions are given in Appendix A.6 $\square$

We observe from Fig. 4 that this approximation is accurate as soon as $\mathcal {R}>>r$.

Fig. 4

Average outward flux and corresponding bounds at distance $\mathcal {R}$ from a peak skeleton point, versus $\mathcal {R}$ (with $r=2$)

3.2.3 Ridgeness

We rewrite Eq. (6) in the polar coordinate system centered at ${\varvec{x}}$,

$$\begin{aligned} {\begin{array}{l} \mathrm {rdg}({\varvec{x}}) = \\ \quad -\int _0^\infty \int _0^{2\pi } \rho G_\sigma (\rho ) \varDelta {D}\left( {\varvec{x}}+\left[ \begin{array}{c} \displaystyle \rho \cos \theta \\ \rho \sin \theta \end{array} \right] \right) \text {d}\theta \text {d}\rho , \end{array}} \end{aligned}$$

(26)

where $G_\sigma (\rho )$ is a shorthand notation for

$$\begin{aligned} G_\sigma (\rho \cos \theta ,~\rho \sin \theta ) = \frac{\displaystyle {1}}{\displaystyle {2\pi \sigma ^2}}\exp \left( -\frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}} \right) \end{aligned}$$

Combining Eqs. (26) and (16), we obtain the following result:

Proposition 9

The ridgeness at a point ${\varvec{x}}$, at distance $\mathcal {R}=\left\| {{\varvec{x}}-\varvec{s}}\right\|$ from a peak skeleton point $\varvec{s}$ is

$$\begin{aligned} {\begin{array}{l} \mathrm {rdg}_\mathrm {peak}({\varvec{x}}) \\ \quad =2\int _0^\infty \rho G_\sigma (\rho ) \int _0^{\pi } \frac{\displaystyle {1}}{\displaystyle {\sqrt{\rho ^2+\mathcal {R}^2-2\rho \mathcal {R}\cos \theta }}}\text {d}\theta \text {d}\rho \end{array}} \end{aligned}$$

(27)

Proposition 10

The ridgeness at a point ${\varvec{x}}$, at distance $\mathcal {R}=\left\| {{\varvec{x}}-\varvec{s}}\right\|$ from a peak skeleton point $\varvec{s}$ can be expressed using the complete elliptic integral of the first kind as

$$\begin{aligned} {\begin{array}{l} \mathrm {rdg}_\mathrm {peak}({\varvec{x}}) \\ \quad =\frac{\displaystyle {2}}{\displaystyle {\pi \sigma ^2}} \int _0^\infty \frac{\displaystyle {\rho }}{\displaystyle {\mathcal {R}+\rho }}\mathrm {K}\left( \frac{\displaystyle {2\sqrt{\rho \mathcal {R}}}}{\displaystyle {\mathcal {R}+\rho }} \right) \exp \left( -\frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}}\right) \text {d}\rho \end{array}} \end{aligned}$$

(28)

Proof

The proofs for the two previous propositions are given in Appendix A.7. $\square$

Since the term $G_\sigma (\rho )\frac{\displaystyle {\rho }}{\displaystyle {\mathcal {R}+\rho }}$ is positive in $[0,+\infty )$,

Proposition 11

The ridgeness at a point ${\varvec{x}}$, at distance $\mathcal {R}=\left\| {{\varvec{x}}-\varvec{s}}\right\|$ from a peak skeleton point $\varvec{s}$ is bounded as

$$\begin{aligned} \mathcal {L}_{\mathrm {rdg}_\mathrm {peak}}< \mathrm {rdg}_\mathrm {peak}({\varvec{x}}) < \mathcal {U}_{\mathrm {rdg}_\mathrm {peak}}\end{aligned}$$

with

$$\begin{aligned}&{\begin{array}{l} \mathcal {L}_{\mathrm {rdg}_\mathrm {peak}}\\ \quad = \frac{\displaystyle {2}}{\displaystyle {\pi \sigma ^2}} \int _0^\infty \frac{\displaystyle {\rho }}{\displaystyle {\mathcal {R}+\rho }}\mathcal {L}_\mathrm {K}^p\left( \frac{\displaystyle {2\sqrt{\rho \mathcal {R}}}}{\displaystyle {\mathcal {R}+\rho }} \right) \exp \left( -\frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}}\right) \text {d}\rho \end{array}} \nonumber \\ \end{aligned}$$

(29)

$$\begin{aligned}&{\begin{array}{l} \mathcal {U}_{\mathrm {rdg}_\mathrm {peak}}\\ \quad = \frac{\displaystyle {2}}{\displaystyle {\pi \sigma ^2}} \int _0^\infty \frac{\displaystyle {\rho }}{\displaystyle {\mathcal {R}+\rho }}\mathcal {U}_\mathrm {K}\left( \frac{\displaystyle {2\sqrt{\rho \mathcal {R}}}}{\displaystyle {\mathcal {R}+\rho }} \right) \exp \left( -\frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}}\right) \text {d}\rho \end{array}}\nonumber \\ \end{aligned}$$

(30)

where $\mathcal {U}_\mathrm {K}$ is either $\mathcal {U}_\mathrm {K}^0$ or $\mathcal {U}_\mathrm {K}^\mathrm {L}$.

No closed-form expression can be found for Eq. (28), for either its lower or upper bounds. In Fig. 5, numerical integration was performed to plot $\mathrm {rdg}_\mathrm {peak}$ and its bounds versus $\mathcal {R}$. Loose lower and upper bounds $\mathcal {L}_{\mathrm {rdg}_\mathrm {peak}}^1$ and $\mathcal {U}_{\mathrm {rdg}_\mathrm {peak}}^1$ were obtained with $\mathcal {L}_\mathrm {K}^1$ and $\mathcal {U}_\mathrm {K}^0$, respectively. Sharp lower and upper bounds $\mathcal {L}_{\mathrm {rdg}_\mathrm {peak}}^2$ and $\mathcal {U}_{\mathrm {rdg}_\mathrm {peak}}^2$ were obtained with $\mathcal {L}_\mathrm {K}^{1/2}$ and $\mathcal {U}_\mathrm {K}^\mathrm {L}$, respectively.

As for the AOF, the second-order Taylor expansion of $\widetilde{D}$ gives a suitable approximation to $\mathrm {rdg}_\mathrm {peak}$ as soon as $\mathcal {R}$ is large enough. The approximate ridgeness is obtained using Eqs. (24) and the polar transformation of Eq. (5):

$$\begin{aligned} {\begin{array}{l} \widetilde{\mathrm {rdg}}({\varvec{x}})=\\ \quad -\int _0^\infty \int _0^{2\pi } \rho \varDelta {G}_\sigma (\rho ) \widetilde{D}\left( {\varvec{x}}+\left[ \begin{array}{c} \displaystyle \rho \cos \theta \\ \rho \sin \theta \end{array} \right] \right) \text {d}\theta \text {d}\rho , \end{array}} \end{aligned}$$

(31)

where $\varDelta {G}_\sigma (\rho )$ is a shorthand notation for

$$\begin{aligned} \varDelta {G}_\sigma (\rho \cos \theta ,~\rho \sin \theta ) = \frac{\displaystyle {1}}{\displaystyle {\pi \sigma ^4}}\left( \frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}}-1\right) \exp \left( -\frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}} \right) , \end{aligned}$$

Proposition 12

The second-order approximation of the ridgeness at a point ${\varvec{x}}$, at distance $\mathcal {R}=\left\| {{\varvec{x}}-\varvec{s}}\right\|$ from a peak skeleton point $\varvec{s}$ is

$$\begin{aligned} \widetilde{\mathrm {rdg}}_\mathrm {peak}({\varvec{x}}) = \frac{\displaystyle {1}}{\displaystyle {\mathcal {R}}} \end{aligned}$$

Proposition 13

The ridgeness at ${\varvec{x}}$ is asymptotically equivalent to its second-order approximation

$$\begin{aligned} \mathrm {rdg}_\mathrm {peak}({\varvec{x}}) \sim \widetilde{\mathrm {rdg}}_\mathrm {peak}({\varvec{x}}) \text { (as }\left\| {{\varvec{x}}-\varvec{s}}\right\| \rightarrow +\infty \text {)} \end{aligned}$$

Proof

The proofs for the two previous propositions are given in Appendix A.8 $\square$

As for the AOF, we observe from Fig. 5 that this approximation is accurate as soon as $\mathcal {R}>>\sigma$.

Fig. 5

Ridgeness and corresponding bounds at distance $\mathcal {R}$ from a peak skeleton point, versus $\mathcal {R}$ (with $\sigma =2$)

3.3 Endpoint

Fig. 6

Endpoint. a Distance. b Average outward flux with $r=2$. c Ridgeness with  $\sigma =2$

The endpoint configuration, illustrated in Fig. 6a, is described as a mix of properties of the regular skeleton point in Sect. 3.1 and the peak point in Sect. 3.2. As in the case of the regular skeleton point, the skeleton branch forms an object angle $\alpha$, which is half the angle formed by the two inward unit normal vectors ${\varvec{n}_1}$ and ${\varvec{n}_2}$. The skeleton branch has unit tangent vector

$$\begin{aligned} \varvec{t}= \frac{\displaystyle {{\varvec{n}_1}^\perp -{\varvec{n}_2}^\perp }}{\displaystyle {\left\| {{\varvec{n}_1}-{\varvec{n}_2}}\right\| }}. \end{aligned}$$

We assume that the branch extremity forms an arc of angle $2\alpha$ with center $\varvec{s}$. In what follows, we focus on deriving the AOF and ridgeness at $\varvec{s}$, as functions of $\alpha$. The shape branch is split into 3 open subregions. ${\varOmega }_1$ is the region bounded by line segments $\varvec{s}\varvec{\gamma }_1$, $\varvec{s}\varvec{\gamma }_2$ and the arc from $\varvec{\gamma }_1$ to $\varvec{\gamma }_2$. ${\varOmega }_2$ is the region above the skeleton branch and on the left of line $\varvec{s}\varvec{\gamma }_1$, whereas ${\varOmega }_3$ is the region below the skeleton branch and on the left of the line $\varvec{s}\varvec{\gamma }_2$. In the current case, we consider a piecewise definition of the distance,

$$\begin{aligned} D({\varvec{x}}) = \left\{ {\begin{array}{ll} D(\varvec{s})-\left\| {{\varvec{x}}-\varvec{s}}\right\| &{} \text { if }{\varvec{x}}\in {\varOmega }_1 \\ D(\varvec{s}) + ({\varvec{x}}-\varvec{s})\cdot {\varvec{n}_1}&{} \text { if }{\varvec{x}}\in {\varOmega }_2 \\ D(\varvec{s}) + ({\varvec{x}}-\varvec{s})\cdot {\varvec{n}_2}&{} \text { if }{\varvec{x}}\in {\varOmega }_3, \end{array}} \right. \end{aligned}$$

(32)

and its resulting gradient, which is undefined on the common boundaries of ${\varOmega }_1$, ${\varOmega }_2$ and ${\varOmega }_3$,

$$\begin{aligned} \nabla {D}({\varvec{x}}) = \left\{ {\begin{array}{ll} \frac{\displaystyle {\varvec{s}-{\varvec{x}}}}{\displaystyle {\left\| {\varvec{s}-{\varvec{x}}}\right\| }} &{} \text { if }{\varvec{x}}\in {\varOmega }_1 \\ {\varvec{n}_1}&{} \text { if }{\varvec{x}}\in {\varOmega }_2 \\ {\varvec{n}_2}&{} \text { if }{\varvec{x}}\in {\varOmega }_3. \end{array}} \right. \end{aligned}$$

(33)

3.3.1 Average Outward Flux

Proposition 14

The AOF at the endpoint $\varvec{s}$ of a skeleton branch, with object angle $\alpha$, is³

$$\begin{aligned} \mathrm {aof}_\mathrm {end}(\varvec{s}) = -\frac{\displaystyle {1}}{\displaystyle {\pi }}(\alpha + \sin \alpha ) \end{aligned}$$

(34)

Proof

The proof is given in Appendix A.9. $\square$

For any point ${\varvec{x}}\in {\varOmega }_1$ s.t. the disk of radius $r$ and center ${\varvec{x}}$ is fully included within ${\varOmega }_1$, $\mathrm {aof}_\mathrm {end}({\varvec{x}})=\mathrm {aof}_\mathrm {peak}({\varvec{x}})$. It can be observed from Fig. 6b that the AOF in ${\varOmega }_1$ has a behavior similar to the one obtained for the peak point case. Its absolute value decreases in $\mathcal {O}(1/\left\| {{\varvec{x}}-\varvec{s}}\right\| )$.

3.3.2 Ridgeness

Proposition 15

The ridgeness at the endpoint $\varvec{s}$ of a skeleton branch, with object angle $\alpha$, is

$$\begin{aligned} \mathrm {rdg}_\mathrm {end}(\varvec{s}) = \frac{\displaystyle {\sqrt{2\pi }}}{\displaystyle {2\pi \sigma }}(\alpha + \sin \alpha ) \end{aligned}$$

(35)

Proof

The proof is given in Appendix A.10. $\square$

Again, it can be observed from Fig. 6c that the ridgeness in ${\varOmega }_1$ has a behavior similar to the one obtained for the peak point case.

3.4 Ligature Point

Fig. 7

Ligature point. a Distance. b Average outward flux with $r=2$. c Ridgeness with $\sigma =2$ (color scales for the AOF and ridgeness are similar to the ones in Fig. 6) (Color figure online)

In Fig. 7a, a thin branch connects to a thick branch, which creates a ligature. As partially described in Sect. 2.3, a ligature is a skeleton branch created by the junction of two shape branches. Unlike a regular skeleton branch, it does not arise from a shape branch itself. The junction creates two corners ${\varvec{p}}$ and ${\varvec{q}}$. Let $\ell$ be the line passing through ${\varvec{p}}$ and ${\varvec{q}}$. Let us denote the two branches by ${\varOmega }_1$ and ${\varOmega }_2$, on the right and left of $\ell$, respectively. The ligature is included into ${\varOmega }_2$ and is located on the bisector of ${\varvec{p}}$ and ${\varvec{q}}$, regardless of the orientation of branch ${\varOmega }_1$. Its unit tangent vector is

$$\begin{aligned} \varvec{t}= \frac{\displaystyle {({\varvec{p}}-{\varvec{q}})^\perp }}{\displaystyle {\left\| {{\varvec{p}}-{\varvec{q}}}\right\| }}. \end{aligned}$$

Assuming that $\varvec{t}$ is directed toward ${\varOmega }_2$, any ligature point verifies

$$\begin{aligned} \varvec{s}= \frac{\displaystyle {{\varvec{p}}+{\varvec{q}}}}{\displaystyle {2}} + \mathcal {A}\varvec{t}\end{aligned}$$

with $\mathcal {A}\ge 0$. Midpoint $({\varvec{p}}+{\varvec{q}})/2$ is referred to as the ligature junction. Let $\mathcal {B}$ be the half-thickness of branch ${\varOmega }_1$ at the junction,

$$\begin{aligned} \mathcal {B}= \frac{\displaystyle {\left\| {{\varvec{p}}-{\varvec{q}}}\right\| }}{\displaystyle {2}}. \end{aligned}$$

Let us assume that the thickness of ${\varOmega }_2$ is much greater than $\mathcal {B}$. For any point in the neighborhood of a ligature point $\varvec{s}$,

$$\begin{aligned} D({\varvec{x}}) = \min (\left\| {{\varvec{x}}-{\varvec{p}}}\right\| ,\left\| {{\varvec{x}}-{\varvec{q}}}\right\| ), \end{aligned}$$

(36)

and, for the ligature point itself,

$$\begin{aligned} D(\varvec{s}) = \left\| {\varvec{s}-{\varvec{p}}}\right\| = \left\| {\varvec{s}-{\varvec{q}}}\right\| = \sqrt{\mathcal {A}^2+\mathcal {B}^2}. \end{aligned}$$

We calculate the AOF and ridgeness of a ligature point $\varvec{s}$, assuming that distance $\mathcal {A}$ is reasonably small compared to the thickness of ${\varOmega }_2$. In other words, $\varvec{s}$ is far enough from the opposite border of ${\varOmega }_2$, so that ${\varvec{p}}$ and ${\varvec{q}}$ are considered as the only local borders. As will be derived, AOF and ridgeness are decreasing functions, in absolute value, of distance $\mathcal {A}$. Hence, in what follows, the distance to borders $\mathcal {R}$, and angle $\beta$ both depend on $\mathcal {A}$:

$$\begin{aligned} \mathcal {R}(\mathcal {A})= & {} \sqrt{\mathcal {A}^2+\mathcal {B}^2} \nonumber \\ \beta (\mathcal {A})= & {} \tan ^{-1} \frac{\displaystyle {\mathcal {B}}}{\displaystyle {\mathcal {A}}} \end{aligned}$$

(37)

3.4.1 Average Outward Flux

As an additional requirement, the following AOF is valid only if $\mathcal {A}\ge r$ and $\mathcal {B}\ge r$.

Proposition 16

The AOF at ligature point $\varvec{s}$, at a distance $\mathcal {A}$ from the ligature junction, is

$$\begin{aligned} {\begin{array}{l} \mathrm {aof}_\mathrm {ligature}(\varvec{s}) \\ \quad =\frac{\displaystyle {1}}{\displaystyle {\pi }} \int _0^\pi \frac{\displaystyle {r-\mathcal {A}\cos \theta -\mathcal {B}\sin \theta }}{\displaystyle {\sqrt{r^2+\mathcal {A}^2+\mathcal {B}^2-2r(\mathcal {A}\cos \theta +\mathcal {B}\sin \theta )}}}~\text {d}\theta \end{array}} \end{aligned}$$

(38)

Proposition 17

The AOF at ligature point $\varvec{s}$, at a distance $\mathcal {A}$ from the ligature junction, can be expressed with complete and incomplete elliptic integrals as

$$\begin{aligned} {\begin{array}{l} \mathrm {aof}_\mathrm {ligature}(\varvec{s}) = \frac{\displaystyle {1}}{\displaystyle {\pi r}} \\ \left[ (\mathcal {R}+r)\left( 2\mathrm {E}(k)-\mathrm {E}\left( \frac{\displaystyle {\beta }}{\displaystyle {2}},k\right) -\mathrm {E}\left( \frac{\displaystyle {\pi }}{\displaystyle {2}}-\frac{\displaystyle {\beta }}{\displaystyle {2}},k\right) \right) \right. \\ \left. -(\mathcal {R}-r)\left( 2\mathrm {K}(k) -\mathrm {F}\left( \frac{\displaystyle {\beta }}{\displaystyle {2}},k\right) -\mathrm {F}\left( \frac{\displaystyle {\pi }}{\displaystyle {2}}-\frac{\displaystyle {\beta }}{\displaystyle {2}},k\right) \right) \right] \end{array}} \end{aligned}$$

with $k=\frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+r}}$, and $\mathcal {R}=\mathcal {R}(\mathcal {A})$ and $\beta =\beta (\mathcal {A})$.

Using the Taylor expansion $\widetilde{D}$ of Eq. (24), we can calculate an approximate AOF.

Proposition 18

The second-order approximation of the AOF at ligature point $\varvec{s}$, at a distance $\mathcal {A}$ from the ligature junction is

$$\begin{aligned} \widetilde{\mathrm {aof}}_\mathrm {ligature}(\varvec{s}) = \frac{\displaystyle {1}}{\displaystyle {\sqrt{\mathcal {A}^2+\mathcal {B}^2}}} \left( \frac{\displaystyle {r}}{\displaystyle {2}}-\frac{\displaystyle {2\mathcal {B}}}{\displaystyle {\pi }} \right) \end{aligned}$$

Proposition 19

The AOF at ligature point $\varvec{s}$ is asymptotically equivalent to its second-order approximation

$$\begin{aligned} \mathrm {aof}_\mathrm {ligature}(\varvec{s}) \sim \widetilde{\mathrm {aof}}_\mathrm {ligature}(\varvec{s}) \text { (as }\mathcal {A}\rightarrow +\infty \text {)} \end{aligned}$$

Proof

The proofs for the two previous propositions are given in Appendix A.12 $\square$

3.4.2 Ridgeness

Since the ridgeness is calculated on an infinite domain, it should be assumed that the following expressions are accurate if $\mathcal {A}$ and the thickness of ${\varOmega }_2$ are large enough, so that $\mathcal {A}>n\sigma$ (usually, $n=3$). Using a transformation of definition (5) in the polar coordinate system centered at ${\varvec{x}}$,

$$\begin{aligned} {\begin{array}{l} \mathrm {rdg}({\varvec{x}}) = \\ -\int _0^\infty \int _0^{2\pi } \rho \varDelta {G}_\sigma (\rho ) D\left( {\varvec{x}}+\left[ \begin{array}{c} \displaystyle \rho \cos \theta \\ \rho \sin \theta \end{array} \right] \right) \text {d}\theta \text {d}\rho , \end{array}} \end{aligned}$$

(39)

we obtain the following result:

Proposition 20

The ridgeness at ligature point $\varvec{s}$, at a distance $\mathcal {A}$ from the ligature junction, is

$$\begin{aligned} {\begin{array}{l} \mathrm {rdg}_\mathrm {ligature}(\varvec{s}) = -2 \int _0^\infty \rho \varDelta {G}_\sigma (\rho ) \\ \int _0^\pi \sqrt{\rho ^2+\mathcal {A}^2+\mathcal {B}^2-2\rho (\mathcal {A}\cos \theta +\mathcal {B}\sin \theta )}~\text {d}\theta \text {d}\rho \end{array}} \end{aligned}$$

(40)

Proposition 21

The ridgeness at ligature point $\varvec{s}$, at a distance $\mathcal {A}$ from the ligature junction can be expressed using complete and incomplete elliptic integrals of the second kind as

$$\begin{aligned} {\begin{array}{l} \mathrm {rdg}_\mathrm {ligature}(\varvec{s}) = \frac{\displaystyle {4}}{\displaystyle {\pi \sigma ^4}} \int _0^\infty \left( 1-\frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}}\right) \exp \left( -\frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}}\right) \\ (\mathcal {R}+\rho )\left( 2\mathrm {E}(k)-\mathrm {E}\left( \frac{\displaystyle {\beta }}{\displaystyle {2}},k\right) -\mathrm {E}\left( \frac{\displaystyle {\pi }}{\displaystyle {2}}-\frac{\displaystyle {\beta }}{\displaystyle {2}},k\right) \right) \text {d}\rho \end{array}} \end{aligned}$$

(41)

with $k=\frac{\displaystyle {2\sqrt{\rho \mathcal {R}}}}{\displaystyle {\mathcal {R}+\rho }}$ and $\mathcal {R}=\mathcal {R}(\mathcal {A})$ and $\beta =\beta (\mathcal {A})$, as defined in Eq. (37).

Proof

The proofs for the two previous propositions are given in Appendix A.13. $\square$

Using the Taylor expansion $\widetilde{D}$ of Eq. (24), we can calculate an approximate ridgeness.

Proposition 22

The second-order approximation of the ridgeness at ligature point $\varvec{s}$, at a distance $\mathcal {A}$ from the ligature junction is

$$\begin{aligned} \widetilde{\mathrm {rdg}}_\mathrm {ligature}(\varvec{s}) = \frac{\displaystyle {1}}{\displaystyle {\sqrt{\mathcal {A}^2+\mathcal {B}^2}}}\left( \mathcal {B}\frac{\displaystyle {\sqrt{2\pi }}}{\displaystyle {\sigma \pi }}-1\right) \end{aligned}$$

Proposition 23

The ridgeness at ligature point $\varvec{s}$ is asymptotically equivalent to its second-order approximation

$$\begin{aligned} \mathrm {rdg}_\mathrm {ligature}(\varvec{s}) \sim \widetilde{\mathrm {rdg}}_\mathrm {ligature}(\varvec{s}) \text { (as }\mathcal {A}\rightarrow +\infty \text {)} \end{aligned}$$

Proof

The proofs for the two previous propositions are given in Appendix A.14 $\square$

The AOF and ridgeness are illustrated in Fig. 7b , c, respectively. Note that their color scales are the same as for Fig. 6b, c. In accordance with Propositions 18 and 22, it can be observed that the AOF and ridgeness become weaker as the considered ligature point gets farther from the ligature junction.

3.5 Junction Point

Fig. 8

Junction point

We consider a simplified model of a junction of n branches, such that the n corners $\{ {\varvec{p}}_i \}_{i=1...n}$ formed by the branches are all equidistant to the junction skeleton point $\varvec{s}$, as depicted in Fig. 8. We focus on the AOF and ridgeness at junction point $\varvec{s}$. Note that any point located on a line segment between $\varvec{s}$ and the midpoint of two successive corners,  $({\varvec{p}}_i+{\varvec{p}}_{i+1})/2$, is a ligature point. The distance from $\varvec{s}$ to any corner is denoted by $\mathcal {R}$. In the neighborhood of $\varvec{s}$, the distance is:

$$\begin{aligned} D({\varvec{x}})= & {} \min _{i=1...n} D_i({\varvec{x}}) \nonumber \\ D_i({\varvec{x}})= & {} \left\| {{\varvec{x}}-{\varvec{p}}_i}\right\| \end{aligned}$$

(42)

Switching to polar coordinates, corners are defined as

$$\begin{aligned} {\varvec{p}}_i = \varvec{s}+ [\mathcal {R}\cos \beta _i, \mathcal {R}\sin \beta _i]^\mathrm {T} \end{aligned}$$

(43)

where $\beta _i$ is the absolute angle formed by the line from $\varvec{s}$ to ${\varvec{p}}_i$ and the horizontal axis. We denote by $\alpha _i$ the relative angle formed by $\varvec{s}$ and the two successive corners ${\varvec{p}}_i$ and ${\varvec{p}}_{i+1}$, thus

$$\begin{aligned} \alpha _i = \beta _{i+1}-\beta _i. \end{aligned}$$

In the subsequent parts of this section, we show that the AOF and ridgeness only depend on the spatial layout of the corners and distance $\mathcal {R}$—which is linked to the thicknesses of the branches—but does not depend on the geometry of the branch borders.

3.5.1 Average Outward Flux

Hereafter, we assume that $\mathcal {R}>r$.

Proposition 24

The AOF at junction point $\varvec{s}$ at distance $\mathcal {R}$ from n corners forming angles $(\alpha _i)_{i=1...n}$ is

$$\begin{aligned} {\begin{array}{l} \mathrm {aof}_\mathrm {junction}(\varvec{s}) \\ \quad = \frac{\displaystyle {1}}{\displaystyle {\pi }} \sum _{i=1}^n \int _0^{\frac{\alpha _i}{2}} \frac{\displaystyle {r-\mathcal {R}\cos \theta }}{\displaystyle {\sqrt{r^2+\mathcal {R}^2-2r\mathcal {R}\cos \theta }}} \text {d}\theta \end{array}} \end{aligned}$$

(44)

Proposition 25

The AOF at junction point $\varvec{s}$ at distance $\mathcal {R}$ from n corners forming angles $(\alpha _i)_{i=1...n}$ can be expressed with complete and incomplete elliptic integrals as

$$\begin{aligned} {\begin{array}{l} \mathrm {aof}_\mathrm {junction}(\varvec{s}) \\ \quad =\frac{\displaystyle {1}}{\displaystyle {\pi r}} \sum _{i=1}^n \left[ (\mathcal {R}+r)\left( \mathrm {E}(k)-\mathrm {E}\left( \frac{\displaystyle {\pi }}{\displaystyle {2}}-\frac{\displaystyle {\alpha _i}}{\displaystyle {4}},k\right) \right) \right. \\ \qquad \left. -(\mathcal {R}-r)\left( \mathrm {K}(k)-\mathrm {F}\left( \frac{\displaystyle {\pi }}{\displaystyle {2}}-\frac{\displaystyle {\alpha _i}}{\displaystyle {4}},k\right) \right) \right] \end{array}} \end{aligned}$$

(45)

with $k=\frac{\displaystyle {2\sqrt{r\mathcal {R}}}}{\displaystyle {\mathcal {R}+r}}$.

Proof

The proofs for the two previous propositions are given in Appendix A.15 $\square$

Using the Taylor expansion $\widetilde{D}$ of Eq. (24), we can calculate an approximate AOF.

Proposition 26

The second-order approximation of the AOF at junction point $\varvec{s}$, at distance $\mathcal {R}$ from n corners forming angles $(\alpha _i)_{i=1...n}$, is

$$\begin{aligned} \widetilde{\mathrm {aof}}_\mathrm {junction}(\varvec{s}) = -\frac{\displaystyle {1}}{\displaystyle {\pi }}{s}_2 + \frac{\displaystyle {r}}{\displaystyle {2\mathcal {R}}}\left( 1-\frac{\displaystyle {1}}{\displaystyle {2\pi }}{s}_1\right) \end{aligned}$$

where ${s}_1$ and ${s}_2$ are the sums of angles $\alpha _i$ and their halves, respectively:

$$\begin{aligned} {s}_1= & {} \sum _{i=1}^n \sin \alpha _i \nonumber \\ {s}_2= & {} \sum _{i=1}^n \sin \left( \frac{\displaystyle {\alpha _i}}{\displaystyle {2}}\right) \end{aligned}$$

(46)

This result should be put in perspective with the invariant obtained in [18] for junction points. Indeed, the term $-\frac{\displaystyle {1}}{\displaystyle {\pi }}{s}_2$ was also found by them. We extend their result with an additional term taking r into account.

Proposition 27

The AOF at junction point $\varvec{s}$ is asymptotically equivalent to its second-order approximation

$$\begin{aligned} \mathrm {aof}_\mathrm {junction}(\varvec{s}) \sim \widetilde{\mathrm {aof}}_\mathrm {junction}(\varvec{s}) \text { (as }\mathcal {R}\rightarrow +\infty \text {)} \end{aligned}$$

Proof

The proofs for the two previous propositions are given in Appendix A.16 $\square$

Fig. 9

AOF-based skeleton for shape with irregular border. Left: final skeleton, center: AOF, right: thresholded AOF. Top row: $r=1$, bottom row: $r=4$

Fig. 10

Ridgeness-based skeleton for shape with irregular border. Left: final skeleton, Center: ridgeness, Right: thresholded ridgeness. Top row: $\sigma =1$, bottom row: $\sigma =4$

Fig. 11

Overview of the synthetic shape dataset

Fig. 12

Synthetic shape $\hbox {n}^{\circ }{5}$ at different noise levels $\eta$ with AOF-based skeletons (ridgeness-based skeletons are visually equivalent and are not depicted)

3.5.2 Ridgeness

Again, it should be assumed that the following expressions are accurate if the thickness of the junction is large enough, i.e.,$\mathcal {R}>n\sigma$ (usually, $n=3$). Starting from the polar LoG-based expression of the ridgeness of Eq. (39), it follows that:

Proposition 28

The ridgeness at junction point $\varvec{s}$ at distance $\mathcal {R}$ from n corners forming angles $(\alpha _i)_{i=1...n}$ is

$$\begin{aligned} {\begin{array}{l} \mathrm {rdg}_\mathrm {junction}(\varvec{s}) = -\,2\int _0^\infty \rho \varDelta {G_\sigma }(\rho ) \\ \quad \sum _{i=1}^n \int _0^{\frac{\alpha _i}{2}} \sqrt{r^2+\mathcal {R}^2-2r\mathcal {R}\cos \theta }~\text {d}\theta ~\text {d}\rho \end{array}} \end{aligned}$$

(47)

Proposition 29

The ridgeness at junction point $\varvec{s}$ at distance $\mathcal {R}$ from n corners forming angles $(\alpha _i)_{i=1,\ldots ,n}$ can be expressed using complete and incomplete elliptic integrals of the second kind as

$$\begin{aligned} {\begin{array}{l} \mathrm {rdg}_\mathrm {junction}(\varvec{s}) = \frac{\displaystyle {4}}{\displaystyle {\pi \sigma ^4}} \int _0^\infty \left( 1-\frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}}\right) \exp \left( -\frac{\displaystyle {\rho ^2}}{\displaystyle {2\sigma ^2}}\right) \\ \sum _{i=1}^n (\mathcal {R}+\rho )\left( \mathrm {E}(k)-\mathrm {E}\left( \frac{\displaystyle {\pi }}{\displaystyle {2}}-\frac{\displaystyle {\alpha _i}}{\displaystyle {4}},k\right) \right) \text {d}\rho \end{array}} \end{aligned}$$

(48)

with $k=\frac{\displaystyle {2\sqrt{\rho \mathcal {R}}}}{\displaystyle {\mathcal {R}+\rho }}$.

Proof

The proofs for the two previous propositions are given in Appendix A.17. $\square$

Proposition 30

The second-order approximation of the ridgeness at junction point $\varvec{s}$, at distance $\mathcal {R}$ from n corners forming angles $(\alpha _i)_{i=1...n}$, is

$$\begin{aligned} \widetilde{\mathrm {rdg}}_\mathrm {junction}(\varvec{s}) = \frac{\displaystyle {1}}{\displaystyle {\sigma \sqrt{2\pi }}}{s}_2 -\frac{\displaystyle {1}}{\displaystyle {\mathcal {R}}}\left( 1-\frac{\displaystyle {1}}{\displaystyle {2\pi }}{s}_1\right) \end{aligned}$$

with ${s}_1$ and ${s}_2$ as defined in Eq. (46).

Proposition 31

The ridgeness at junction point $\varvec{s}$ is asymptotically equivalent to its second-order approximation

$$\begin{aligned} \mathrm {rdg}_\mathrm {junction}(\varvec{s}) \sim \widetilde{\mathrm {rdg}}_\mathrm {junction}(\varvec{s}) \text { (as }\mathcal {R}\rightarrow +\infty \text {)} \end{aligned}$$

Proof

The proofs for the two previous propositions are given in Appendix A.18 $\square$

4 Experiments

4.1 Implementation Details

Given a binary input image containing the shape ${\varOmega }$, the Euclidean distance map $D$ is computed thanks to the steerable algorithm of  [17, 35] which operates in $O(|{\varOmega }|)$. Then, for every ${\varvec{p}}$ in the outer 8-connected border, i.e., the set of background pixels with at least one 8-connected neighbor in ${\varOmega }$, $D$ is set to 0. Eventually, $D$ is extended below 0 in the background, according to Eq. (7), within a radius of $r+1$ for the AOF-based skeleton, and $3\sigma +1$ for the ridgeness-based skeleton. We thus obtain a truncated signed distance function, which is smooth on the object contour, avoiding border artifacts on the AOF and ridgeness maps.

In Algorithm 1, line 4, boundary $\partial {\varOmega }$ is discretized as the 8-connected inner border, i.e., the subset of pixels in ${\varOmega }$ having at least one 8-connected neighbor in the background. For the ridgeness-based skeleton, we use the same procedure, up to minor modifications. Specifically, in the ridgeness-ordered thinning procedure, ${\mathcal {H}}$ is a min-heap sorted w.r.t to ridgeness, and the condition in line 10 should be replaced by

$$\begin{aligned} \mathrm {isEndpoint}({\varvec{p}})~\mathrm {and}~\mathrm {rdg}({\varvec{p}},\sigma )\ge {\mathrm {th}_\mathrm {rdg}}\end{aligned}$$

4.2 Influence of Scale Parameters: Analysis on Regular Skeleton Points

We performed several numerical experiments to corroborate our derivations and to assess the applicability of the theoretical AOF and ridgeness values. We first give a short overview of the influence of parameters $r$ and $\sigma$, and their respective thresholds, on the final skeleton. The choice of thresholds ${\mathrm {th}_\mathrm {aof}}$ and ${\mathrm {th}_\mathrm {rdg}}$ in the AOF-based and ridgeness-based thinning procedure is crucial, as they control the amount of pixels that will be retained as skeleton endpoints, i.e., starting points for branches, according to lines 10 and 11 in Algorithm 1. Thresholds should be chosen as far as possible in the light of the previously derived analytical expressions.

In [18, p. 840], it was suggested that ${\mathrm {th}_\mathrm {aof}}$ be chosen with respect to a minimal object angle. However, no explicit formula was provided nor was a relation established with respect to a particular theoretical shape configuration. Following their suggestion, it seems natural to derive a threshold according to a minimal object angle with respect to the regular skeleton point configuration described in Sect. 3.1, as it is the type of skeleton point most commonly encountered. Object protrusions generating branches with an object angle below this minimal angle should be considered as insignificant. Choosing the threshold according to the minimal object angle gives a clear geometrical interpretation of what a significant object part is. Hence, Eqs. (12) and (14) were used as a basis:

$$\begin{aligned} {\mathrm {th}_\mathrm {aof}}= & {} -\,\frac{\displaystyle {2}}{\displaystyle {\pi }}\sin \alpha _0 \\ {\mathrm {th}_\mathrm {rdg}}= & {} \frac{\displaystyle {\sqrt{2\pi }}}{\displaystyle {\pi \sigma }}\sin \alpha _0 \end{aligned}$$

where $\alpha _0$ is the minimal object angle that a shape part should form in order to generate a skeleton branch. Following [18, p. 840], we used $\alpha _0=\frac{\pi }{6}=30^{\circ }$ in the current experiment. AOF and ridgeness-based skeletons were computed on a shape with moderate noise, such that, at a fine scale, protrusions and indentations on the shape border are expected to generate branches. Results are depicted in Figs. 9 and 10. The left, center and right columns contain skeletons, AOF/ridgeness and thresholded AOF/ridgeness maps, respectively. For each measure, two scales $r,\sigma \in \{1,4\}$ are tested and thresholds are set accordingly. Note that ${\mathrm {th}_\mathrm {aof}}$ only depends on $\alpha _0$ and is thus left unchanged when $r$ varies. Conversely, ${\mathrm {th}_\mathrm {rdg}}$ is set according to $\alpha _0$ and $\sigma$. Note that the color scale of the AOF map, in the center column of Fig. 9, is inverted so that it can be easily interpreted and compared to the ridgeness map.

In the right columns of Figs. 9 and 10, black pixels correspond to all ${\varvec{p}}$ for which $\mathrm {aof}({\varvec{p}},\mathcal {R})\le {\mathrm {th}_\mathrm {aof}}$ or $\mathrm {rdg}({\varvec{p}},\sigma )\ge {\mathrm {th}_\mathrm {rdg}}$. Note that this thresholding does not correspond to the final skeleton, as it has gaps and is not thin. A visual inspection shows that a skeleton branch emanates from each connected component of these selected pixels. For both AOF and ridgeness, the amount of connected components of thresholded pixels diminishes as the scale is increased. Simultaneously, the thickness of the central connected components, arising from the most significant shape parts, increases. This corroborates the expressions of AOF and ridgeness of points near regular skeleton branches, in Eqs. (11) and (13). Let ${\varvec{p}}$ be a point in the vicinity of the skeleton branch and $d$ its distance to the nearest regular skeleton point. We derive the conditions according to which ${\varvec{p}}$ is selected as a candidate skeleton point, i.e., $\mathrm {aof}({\varvec{p}},\mathcal {R})\le {\mathrm {th}_\mathrm {aof}}$ or $\mathrm {rdg}({\varvec{p}},\sigma )\ge {\mathrm {th}_\mathrm {rdg}}$, with respect to $d$ and a given $\alpha$, the object angle of the considered branch. We assume that $\alpha \in \left[ \alpha _0, \frac{\pi }{2}\right]$. Regarding the AOF, according to Eq. (11), ${\varvec{p}}$ satisfies $\mathrm {aof}({\varvec{p}},\mathcal {R})\le {\mathrm {th}_\mathrm {aof}}$ if

$$\begin{aligned} -\,\frac{\displaystyle {2}}{\displaystyle {\pi r}}\sin \alpha \sqrt{r^2-d^2} \le -\,\frac{\displaystyle {2}}{\displaystyle {\pi }}\sin \alpha _0, \end{aligned}$$

which implies

$$\begin{aligned} d\le r\sqrt{1-\frac{\displaystyle {\sin ^2\alpha _0}}{\displaystyle {\sin ^2\alpha }}}. \end{aligned}$$

(49)

Similarly, regarding the ridgeness, plugging the inequality $\mathrm {rdg}({\varvec{p}},\sigma )\ge {\mathrm {th}_\mathrm {rdg}}$ into Eq. (13) leads to

$$\begin{aligned} \frac{\displaystyle {\sqrt{2\pi }}}{\displaystyle {\pi \sigma }}\sin \alpha \exp \left( -\,\frac{\displaystyle {d^2}}{\displaystyle {2\sigma ^2}} \right) \ge \frac{\displaystyle {\sqrt{2\pi }}}{\displaystyle {\pi \sigma }}\sin \alpha _0 \end{aligned}$$

which implies

$$\begin{aligned} d\le \sigma \sqrt{-2\log \left( \frac{\displaystyle {\sin \alpha _0}}{\displaystyle {\sin \alpha }}\right) }. \end{aligned}$$

(50)

According to Eqs. (49) and (50), at a fixed object angle $\alpha$, the distance $d$ below which pixels will be thresholded as candidate skeleton points increases as $r$ or $\sigma$ gets larger, in agreement with our observation.

4.3 Quantitative Study of Accuracy

Fig. 13

Accuracy of AOF-based skeleton for synthetic shape $\hbox {n}^{\circ }{5}$ at noise level $\eta =3$. In the zoomed part, blue pixels belong to the computed skeleton, whereas red pixels belong to the ground-truth skeleton (Color figure online)

Fig. 14

Modified Hausdorff distance between ground-truth skeleton and computed skeleton, for the individual 20 synthetic shapes, at 4 different noise levels

We study and compare quantitatively the accuracy of skeletons generated using the AOF-based and ridgeness-based thinning procedures, under variations of parameters and thresholds. Quantifying the accuracy of the skeletonization algorithms requires images where the expected structures of skeletons are known. For this purpose, we created a dataset of 20 synthetic shapes. Various curved centerlines were first manually generated. These centerlines were then dilated by using circular masks with smoothly varying radii along their entire length. This allows expected skeleton branches to be known beforehand. The expected skeleton branches correspond to the initial centerlines, except in junction areas, which thus need to be corrected. For each shape, the ground-truth reference skeleton was generated by correcting these junction areas using those of the AOF-based skeleton with $r=2$ and ${\mathrm {th}_\mathrm {aof}}$ value selected as in Sect. 4.2. An overview of this dataset is shown in Fig. 11.

In order to study the influence of contour noise on the choice of parameters $r$ and $\sigma$, and their respective thresholds, the shapes were corrupted with additive white Gaussian noise at different intensities. We achieved this by moving contour points along their unit normal vector, with an offset randomly drawn from a zero-mean Gaussian with standard deviation $\eta$. A particular shape of the dataset at noise levels $\eta \in \{0,1,2,3\}$ is depicted in Fig. 12. Note that $\eta =0$ corresponds to the initial uncorrupted shapes, from which the ground-truth skeletons are extracted.

Accuracy is measured based on the similarity between the extracted skeleton and the ground-truth skeleton. We use the Modified Hausdorff distance (MHD) in the Euclidean sense:

$$\begin{aligned} {\begin{array}{l} \mathrm {MHD}(P,Q) \\ \quad = \max \left\{ \frac{\displaystyle {1}}{\displaystyle {|P|}} \sum _{{\varvec{p}}\in P} \min _{{\varvec{q}}\in Q} \left\| {{\varvec{p}}-{\varvec{q}}}\right\| , \frac{\displaystyle {1}}{\displaystyle {|Q|}} \sum _{{\varvec{q}}\in Q} \min _{{\varvec{p}}\in P} \left\| {{\varvec{q}}-{\varvec{p}}}\right\| \right\} \end{array}} \end{aligned}$$

where P and Q are non-empty subsets of $\mathbb {Z}^{2}$ (the extracted skeleton and the ground-truth skeleton). The discrepancy between the extracted and ground-truth skeleton is illustrated in Fig. 13.

In addition to the AOF-based and ridgeness-based skeletons, we report results obtained with corrected AOF of Torsello and Hancock [45], as well as the Integer Medial Axis by Hesselink and Roerdink [22]. On the one hand, the AOF arises from the divergence of $\nabla D$, or equivalently, the curvature of the front propagating along $\nabla D$ [43]. According to [45], the error in calculating the AOF is related to the pixel resolution but is also proportional to the curvature. Hence, they developed a method that alleviates the contribution of the curvature to the error, by taking into account variations of curvature density. This led to the correction of curvature density effects on the AOF, that is subsequently referred to as CC-AOF. On the other hand, the Integer Medial Axis (IMA) algorithm is based on a discrete modeling of the shape. In addition to $D$, it uses the feature transform, which maps each shape point to the set of closest boundary points:

$$\begin{aligned} \mathrm {FT}({\varvec{x}}) = \{ {\varvec{y}}\in \partial {\varOmega }~|~\left\| {{\varvec{x}}-{\varvec{y}}}\right\| =D({\varvec{x}}) \} \end{aligned}$$

The AOF and ridgeness-based skeletonization methods include pruning natively. The pruning level is controlled by ${\mathrm {th}_\mathrm {aof}}$ and ${\mathrm {th}_\mathrm {rdg}}$, respectively. Similarly, the IMA integrates pruning in the criterion used to select skeleton points. This criterion implies the distance between feature transform points of neighboring shape points. Three pruning modes are proposed, depending on the form of the function of this distance: constant pruning, linear pruning and square-root pruning. Constant and linear pruning criteria depend on a parameter $\gamma$, which is varied in the experiments.⁴

Radius $r$ and scale $\sigma$ were both varied from 1 to 5 with a step of 0.1. Threshold ${\mathrm {th}_\mathrm {aof}}$ was varied from $-\,1$ to 0 with a step of 0.02, whereas threshold ${\mathrm {th}_\mathrm {rdg}}$ was varied from 0 to 1 with a step of 0.02. For the IMA, the best results were obtained with the constant pruning mode, with parameter $\gamma$ varying from 10 to 50. For each couple $(r,{\mathrm {th}_\mathrm {aof}})$ (and correspondingly, $(\sigma ,{\mathrm {th}_\mathrm {rdg}})$ and $\gamma$), the AOF, CC-AOF, ridgeness and IMA skeletons were generated from the 20 shapes at the 4 different noise levels.

Table 1 Modified Hausdorff distance between ground-truth skeleton and computed skeleton, averaged over the 20 synthetic shapes, at 4 different noise levels

Fig. 15

Modified Hausdorff distance between ground-truth skeleton and computed skeleton, averaged over all shapes, versus parameter and threshold, at 4 different noise levels. Top row: AOF, middle row: CC-AOF, bottom row: ridgeness

In Fig. 14, the MHD is graphically represented on a per-shape basis. For each shape at each noise level, we retained the configurations of  $(r,{\mathrm {th}_\mathrm {aof}})$, $(\sigma ,{\mathrm {th}_\mathrm {rdg}})$ and $\gamma$ that resulted in the most accurate skeleton. It is not straightforwad to bring out a clear trend from Fig. 14, except that the IMA skeleton gives lower accuracy than the three other ones at noise level $\eta =0$. CC-AOF seems to give the best results at noise level $\eta =0$, whereas the ridgeness-based skeleton seems to deal better with noisy shapes. Note that the y-scale in Fig. 14 is different across noise levels. To get an overall view of the performances, results listed in Fig. 14 are averaged in Table 1. On noisy shapes, it is observed that the ridgeness-based skeleton outperform AOF-based ones. It is slightly more accurate at noise level $\eta =2$ and significantly better at noise level $\eta =3$. This is expected from the LoG filtering embedded in the ridgeness measure, which integrates regularization of the distance map into the ridge detection process.

The previous experiments considers the skeletonization algorithms with their most favorable parameter tuning, but does not report their behavior with respect to the parameters. In Fig. 15, the MHD is averaged over the 20 shapes, for each couple $(r,{\mathrm {th}_\mathrm {aof}})$ of the AOF (top row) and CC-AOF (middle row) and each couple $(\sigma ,{\mathrm {th}_\mathrm {rdg}})$ of the ridgeness (bottom row), at different noise levels. The IMA having only one parameter, equivalent plots could not be obtained; hence, we did not include it into this study. Notice that, in the top and middle rows, values of ${\mathrm {th}_\mathrm {aof}}$ increase downwards. First, it can be seen from the general appearance of the MHD surfaces that accuracy smoothly evolves with respect to parameters and thresholds. For the AOF and ridgeness, large Regions of Accurate Skeletons (RAS), with characteristic shapes, are observed. Unsurprisingly, as a general trend, accuracy falls as the noise level increases. In each plot, the area above the RAS corresponds to over-pruned skeletons, generated with AOF and ridgeness maps that were thresholded too hard. In this case, the skeleton is almost empty, all candidate skeleton points being filtered out. Conversely, the area below the RAS is related to under-pruned noisy skeletons with undesirable branches, due to loose thresholding. For the ridgeness, hyperbola-shaped RAS are observed, indicating that the optimal threshold is an inverse function of scale $\sigma$, which supports, among others, our derivations that led to Eqs. (14) and (35). As claimed in [45], the correction of curvature density effects, as a postprocessing step in the CC-AOF, makes the AOF significantly less sensitive to parameter tuning. The interpretation is that it filters out noisy branches while reinforcing the AOF on desired branches. No area of empty skeletons can be observed, unlike in the AOF.

5 Conclusion

The AOF and ridgeness measures depend on the local geometry of the shape borders. Closed-form exact expressions could be obtained for regular skeleton points and their neighboring points, as well as for skeleton endpoints. As regards peak points, ligatures and junction points, exact expressions using elliptic integrals and simpler closed-form approximations based on the Taylor expansion of the distance function were derived. We established a strong relationship between the spatial parameter ($r$ or $\sigma$) and the corresponding ideal threshold, based on an analysis of regular skeleton points and their neighboring points. This was validated by experiments on a shape dataset with known ground-truth skeletons. As a possible extension to this work, AOF and ridgeness measures could be studied for theoretical configurations of 3D shapes. Further investigation could be conducted on the corrected AOF. In that case, approximate analytical solutions to the transport Eq. (6) in [45] would be necessary.