Abstract
We introduce a data-driven version of the plus Cartan connection on the homogeneous space \({\mathbb {M}}_2\) of 2D positions and orientations. We formulate a theorem that describes all shortest and straight curves (parallel velocity and parallel momentum, respectively) with respect to this new data-driven connection and corresponding Riemannian manifold. Then we use these shortest curves for geodesic tracking of complex vasculature in multi-orientation image representations defined on \({\mathbb {M}}_{2}\). The data-driven Cartan connection characterizes the Hamiltonian flow of all geodesics. It also allows for improved adaptation to curvature and misalignment of the (lifted) vessel structure that we track via globally optimal geodesics. We compute these geodesics numerically via steepest descent on distance maps on \({\mathbb {M}}_2\) that we compute by a new modified anisotropic fast-marching method.Our experiments range from tracking single blood vessels with fixed endpoints to tracking complete vascular trees in retinal images. Single vessel tracking is performed in a single run in the multi-orientation image representation, where we project the resulting geodesics back onto the underlying image. The complete vascular tree tracking requires only two runs and avoids prior segmentation, placement of extra anchor points, and dynamic switching between geodesic models. Altogether we provide a geodesic tracking method using a single, flexible, transparent, data-driven geodesic model providing globally optimal curves which correctly follow highly complex vascular structures in retinal images. All experiments in this article can be reproduced via documented Mathematica notebooks available at van den Berg (Data-driven left-invariant tracking in Mathematica, 2022).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Retinal images are often used to examine the vascular system with optical scanning devices that image the vasculature in the retina noninvasively. The vasculature in the eye is known to be typically representative of the vasculature throughout the body. This allows doctors to monitor the circulatory system and aids in the diagnosis of different kinds of diseases like diabetes, hypertension [1,2,3] and Alzheimer’s disease [4]. Typically, high levels of tortuosity in the vasculature are a biomarker for such diseases [5,6,7,8]. Successful automatic vessel tracking detects complex vasculature and aids the effective diagnosis of such diseases. Here, geometric models come into play via geodesic tracking methods where geodesics are the shortest paths that follow the biological blood vessels. They help in tracking and subsequent analysis of the vascular tree in the retina originating from the optic nerve [9,10,11,12].
Geodesic tracking has been extensively studied where many prevalent approaches perform the tracking in the standard 2D image domain [13,14,15,16,17,18]. For many methods in this category, calculating the geodesics in \({\mathbb {R}}^2\) leads to certain difficulties in accurately following the blood vessel. For example, one common difficulty is the inaccurate tracking of crossing structures and bifurcations. This has motivated methods that aim to lift the image function to higher dimensional spaces. For example, the space of positions and orientations [19, 20] or radius-lifted spaces [21] where the lifting yields the benefit of disentangling seemingly complex crossing structures in the retinal images.
In this article, we focus on the methods [12, 21,22,23] that perform the geodesic tracking in the 3D-space of positions and orientations \({\mathbb {M}}_{2}\). This is based on lifted images, or so-called orientation scores. The well-known benefit of this lifted approach is that lines involved in crossings are manifestly disentangled in \({\mathbb {M}}_{2}\). As visualized in Fig. 1, the crossing circles in the image become disjoint spirals (cf. Figure 1b) in the homogeneous space of positions and orientations.
However, practical considerations of working in (the domain \({\mathbb {M}}_2\) of) orientation scores, like memory reduction and enabling low computation times, result in some undesirable effects. For example, using a limited number of orientations leads to imperfections in the computation of the orientation scores. Hence, some vessels can be assigned a near angular coordinate that may not reflect their true orientation, and therefore does not align with the vessel data correctly. We denote this problem as ‘misalignment’ (also referred to as deviation from horizontality [24]). Moreover, considering a limited number of orientations results in a sampling bias on orientations, and thereby the possibility of missing high curvature regions yielding poor curvature adaptation (cf. Fig. 2).
In this article, we provide a novel, data-driven tracking model that improves upon existing geodesic tracking methods. Our model demonstrates an improved curvature adaptation, reduces misalignment, and exhibits a high degree of geometric interpretability.
We will aim for a single geometric Finslerian model to deal with complex vasculature without requiring heavy pre-processing (e.g., placement of anchor points, pre-skeletonization) and associated extra parameters, and without suffering from the ‘cusp problems’ reported in [12, 25, 26].
The cusp problem is tackled by creating an asymmetric Finslerian modelFootnote 1\(({\mathbb {M}}_2,{\mathcal {F}}^U)\) extension of the data-driven Riemannian manifold similar to the much less data-driven techniques in [28]. For a quick impression of such a ‘cusp’ in a spatially projected sub-Riemannian geodesic, see Fig. 19a in Appendix D. Clearly, cusps are undesirable for vascular tracking, and an asymmetric Finslerian version of the Riemannian manifold tackles this problem. Intuitively, cusps in spatial projections of sub-Riemannian geodesics arise sometimes as optimal paths of a ‘Reed-Shepp’ car (imagine a car driving along the geodesic track) [28, 29] where the car was required to use its reverse gear to follow the optimal path. In the asymmetric Finslerian model we turn off the reverse gear of the car, while allowing for ‘in-place rotations’ see Fig. 19b.
Pre-processing techniques for geodesic tracking such as pre-skeletonization and iterative placement of anchor/key points are typically used in conjunction with Bézier curves [30] or splines on Lie-groups [30, 31], but often require additional parameters and fine-tuning. Specifically, extensive use of anchor points implies that anchors get relatively close to each other, and then the choice of geometric model in between becomes increasingly less relevant (even non-data-driven sub-Riemannian distance approximations suffice as shown in the work by Bekkers et al. [31]). As a result, this reduces the geometric interpretability of the overall model. In this work, we therefore aim for a single geometrical model. Therefore, we will not use pre-processing, pre-skeletonization [21], multiple anchor points [32], and connectivity by perceptional grouping [15, 31, 33], even though these techniques are theoretically interesting and applicable.
In tracking an entire vascular tree, we limit the number of anchor points to at most one (which is computed without explicit manual supervision) and only use the boundary conditions for each vessel (see Fig. 3). Thanks to our new modified version of the anisotropic fast-marching algorithm [34], we can now better adapt to curvature and spatial misalignment efficiently (see Fig. 4). We also address common pitfalls at complex overlapping structures, where one must impose additional constraints to avoid taking wrong exits in the tracking. The implementation of such constraints is easily accounted for in our model, as we will see.
Similarly to the plus-control variant of previous geometric curve optimization models [28] we replace symmetric, anisotropic, (sub-)Riemannian geodesic tracking by asymmetric, anisotropic Finslerian models that avoid cusps and allow for automatic placement of in-place rotations (recall Fig. 19 and see [28, 35]). As a result, our model automatically accounts for bifurcations, thereby reducing the number of anchor points.
In summary, the main contributions of this article are:
-
1.
We introduce a new geodesic tracking model that uses a crossing-preserving approach for tracking complex vasculatures in \({\mathbb {M}}_2\). Our model uses a new anisotropic fast-marching algorithm to compute cusp-free data-driven geodesics. The induced geometric vessel tracking better adapts for vessel curvature and orientation sampling biases, compared to the previous model in [28].
-
2.
We mathematically analyze these solutions (the family of all geodesics) via our data-driven version of the plus Cartan connection (Sect. 3) that underlies the Hamiltonian flow as we will show in Theorem 1.
-
3.
Finally, we demonstrate our method on highly challenging examples of retinal images with complex vasculature where adequate tracking results are obtained with only two runs of the proposed anisotropic fast-marching algorithm.
1.1 Structure of the Article
In Sect. 2, we provide background of the geometrical tools underlying our method. We explain the space of positions and orientations \({\mathbb {M}}_2\), and why it is beneficial to apply tracking in this 3D space rather than in 2D position space.
In Sects. 3 and 4, we describe our model. We begin in Sect. 3 by introducing a new data-driven Cartan connection \(\nabla ^U\) associated with a data-driven left-invariant metric tensor field \({\mathcal {G}}^U\). These geometric tools allow for curvature adaptation and correction of misalignments in existing geodesic tracking algorithms in \({\mathbb {M}}_2\).
In Sect. 4 we use the data-driven Cartan connections and data-driven left-invariant metric tensor fields. We present our main theoretical result in Theorem 1 where we
-
characterize ‘straight curves’ and ‘shortest curves’ in data-driven left-invariant Riemannian manifolds on a finite-dimensional Lie group G,
-
analyze the Hamiltonian flow of all geodesics together,
-
provide the geodesic backtracking formula of the new geodesic tracking model,
-
address the symmetries of the geodesics and connections of the new model.
Then in Sect. 5 we employ the geometrical models and tools and present a numerical algorithm to compute the distance map for the special case where the Lie group equals the roto-translation group \(G=\text {SE}(2)\). Additionally, we explain how to compute the backtracking of geodesics from end to source point. We present a new version of the anisotropic fast-marching algorithm [36] that applies to our new data-driven model.
In Sect. 6, we report an extensive experimental evaluation of geodesic tracking in retinal images from the annotated STAR dataset [37, 38], and show that our new model allows for adequate geometric tracking of highly complex vasculatures.
Finally, in Sect. 7, we end with a brief discussion of future work and conclude.
2 Background
2.1 Lifted Space of Positions and Orientations \({\mathbb {M}}_2\)
We begin by introducing the lifted space of positions and orientations \({\mathbb {M}}_2\). As motivated earlier, working in this space allows for convenient ways to separate difficult crossing structures in \({\mathbb {R}}^2\). In this article, we specifically focus on the challenging problem of vessel tracking in retinal images having complex vasculature.
Definition 1
The space of two-dimensional positions and orientations \({\mathbb {M}}_2\) is defined as a smooth manifold
where \(S^1\equiv {\mathbb {R}}/(2\pi {\mathbb {Z}})\) using the identification
Elements in the homogeneous space are denoted by ordered pairs \(({{\textbf {x}}},\theta ) \in {\mathbb {R}}^{2} \times S^{1}\) but to stress the semidirect product structure of the roto-translation group \(\text {SE}(2):={\mathbb {R}}^{2} \rtimes \text {SO}(2)\) acting on \({\mathbb {M}}_{2}\) we write \({\mathbb {M}}_{2}={\mathbb {R}}^{2} \rtimes S^{1}\).
The space \({\mathbb {M}}_{2}\) is a homogeneous space under the transitive action of roto-translations given by the following mapping:
Definition 2
(Lie group action on domain) For each roto-translation \({{\textbf {g}}}=({{\textbf {y}}},R_{\alpha }) \in \text {SE}(2)\) the mapping of \(L_{{\textbf {g}}}:{\mathbb {M}}_2\rightarrow {\mathbb {M}}_2\) is given by
where \(R_\alpha \in \text {SO}(2)\) is the matrix associated with a counter-clockwise rotation with rotation angle \(\alpha \in S^1\).
Clearly, the concatenation of two rigid body motions is again a rigid body motion and indeed one has
for all \({{\textbf {g}}}_1,{{\textbf {g}}}_2\in \text {SE}(2)\), i.e., L is a group representation.
After setting a reference point \({{\textbf {p}}}_0=({{\textbf {0}}},0) \in {\mathbb {M}}_{2}\) we have a 1-to-1 relation between the roto-translation \(({{\textbf {x}}},R_{\theta })\) mapping \({{\textbf {p}}}_0\) to \({{\textbf {p}}}=({{\textbf {x}}},\theta )\) and the point in the homogeneous space \({{\textbf {p}}}=({{\textbf {x}}},\theta )\in {\mathbb {M}}_2\). In particular, \({{\textbf {p}}}_0\) is then identified with the unity element \({{\textbf {e}}}:=({{\textbf {0}}},I)\).Footnote 2 In short, we identify
Under this identification, the product of two elements, say \(({{\textbf {x}}}_1,\theta _1),({{\textbf {x}}}_2,\theta _2)\in {\mathbb {M}}_2\), in the space of positions (\({{\textbf {x}}}_1,{{\textbf {x}}}_2\in {\mathbb {R}}^2\)) and orientations (\(\theta _1,\theta _2\in S^1\)) is given by
where henceforth \(R_{\!\theta _2}\in \text {SO}(2)\) denotes the counter-clockwise rotation matrix with rotation angle \(\theta _2 \in {\mathbb {R}}/(2\pi {\mathbb {Z}})\).
Definition 3
Let X be a Banach space, then B(X) denotes the space of bounded linear operators on X.
As mentioned we lift the image from \({\mathbb {R}}^2\) to \(\text {SE}(2)\) to separate crossing structures in the corresponding orientation score (Fig. 1). Next we explain how this is precisely done.
Definition 4
(Orientation Scores) The orientation score transform \(W_\psi :{\mathbb {L}}_2({\mathbb {R}}^2)\rightarrow {\mathbb {L}}_2(\text {SE}(2))\) using anisotropic wavelet \(\psi \) maps an image f to an orientation score \(U=W_{\psi }f\). The orientation score is given by
where the rotated and translated mother wavelets are obtained by the Lie group action \({\mathcal {U}}:\text {SE}(2)\rightarrow B({\mathbb {L}}_{2}({\mathbb {R}}^2))\) given by
for all \( {\textbf {g}}=({\textbf {x}},R_{\theta }) \in \text {SE}(2)\) and all \({\textbf {y}}\in {\mathbb {R}}^2\).
Definition 4 inputs an image \(f\in {\mathbb {R}}^2\) and yields a function \(U\in \text {SE}(2)\). This is achieved by taking a convolution with a rotated wavelet filter, where the canonical/mother wavelet function \(\psi \) is rotated counter-clockwise with the angle \(\theta \), as we can see in (3). By varying \(\theta \) over all orientations \({\mathbb {R}}/(2\pi {\mathbb {Z}})\), the image is lifted from \({\mathbb {R}}^2\) to \({\mathbb {M}}_2\). We use the real part of the cake wavelets [23, 39] depicted in Fig. 1c as then the space of orientation scores is naturally embedded in \({\mathbb {L}}_2(\text {SE}(2))\) [39], and gives practically informative orientation scores [1]. More information on the orientation score transform, its range, its invertibility, and the choice of wavelets \(\psi \) can be found in previous works [1, 39,40,41].
We can rotate and translate images via \(f \mapsto {\mathcal {U}}_{{\textbf {g}}}f\). This corresponds to a left action on the orientation score:
for all \({{\textbf {g}}}\in \text {SE}(2)\). Left actions are defined as follows:
Definition 5
(Lie group action on orientation scores) The left regular representation \({\mathcal {L}}_{{\textbf {g}}}:\text {SE}(2)\rightarrow B({\mathbb {L}}_2(\text {SE}(2)))\) is given by
for all \({{\textbf {g}}},{{\textbf {h}}}\in \text {SE}(2), U\in {\mathbb {L}}_2(\text {SE}(2))\).
As shown in [39, Thm. 21], by construction of (3), orientation score processing must be left-invariant (i.e., equivariant with respect to left actions \({\mathcal {L}}_{{\textbf {g}}}\)) and not right-invariant. The key reason for this is the fundamental relation (4). This left-invariance will also be crucial in our geometric tracking which needs to be left-invariant (and not right-invariant). Indeed rotating and translating the image should yield to an equally rotated and translated (lifted) tracking output curve.
2.2 Metric Tensor Fields and Finsler Functions
To calculate shortest paths in orientation scores, we need to establish local costs on tangents (velocities). We do so by assigning a metric tensor \({\mathcal {G}}_{{\textbf {p}}}(\cdot ,\cdot )\) to every point \({{\textbf {p}}}=({{\textbf {x}}},\theta )\) in the lifted space of positions and orientations. It is beneficial to design this metric tensor depending on the specific application. Typically, this choice of the metric tensor field establishes the geometric model. Additionally, diagonalizing this tensor at every point \({{\textbf {p}}}\) provides a local frame of reference.
First, we introduce the static frame denoted by \(\{\partial _x,\partial _y,\partial _\theta \}\), induced by the coordinates \(x,y,\theta \) for all points in \({\mathbb {M}}_2\). Its dual frame, for the cotangent bundle \(T^*({\mathbb {M}}_2)\), is denoted by \(\{\text {d}x,\text {d}y,\text {d}\theta \}\), and can be used to express the metric tensor field \({\mathcal {G}}\).
It is advantageous to use left-invariant vector fields for our application, since it guarantees that tracking results are equivariant to the group of roto-translations. More specifically, tracking is independent of the roto-translation of the image, meaning that tracking on a roto-translated image is identical to tracking on the original and roto-translating the result.
Definition 6
(Frame of Left-Invariant Vector Fields) The frame of left-invariant vector fields (left-invariant frame) is obtained by a pushforward of the static frame at the origin \({{\textbf {p}}}_0\). We define the pushforward \((L_{{\textbf {g}}})_*:T_{{\textbf {h}}}(G)\rightarrow T_{{{\textbf {g}}}{{\textbf {h}}}}(G)\) by
for all smooth functions \(U:{\mathbb {M}}_2\rightarrow {\mathbb {C}}\). Then, the left-invariant frame \(\{{\mathcal {A}}_1,{\mathcal {A}}_2,{\mathcal {A}}_3\}\) is defined by
After computations, we obtain the left-invariant vector fields
The corresponding dual frame is given by \(\{\omega ^i\}_{i=1}^3\) where \(\omega ^i\!\left( {\mathcal {A}}_j\right) =\delta _j^i\). A brief computation gives
In addition to that, we define the left-invariant metric tensor field:
Definition 7
Metric tensor field \({\mathcal {G}}\) on \({\mathbb {M}}_{2}\) is left-invariant iff
for all \({{\textbf {p}}}\in {\mathbb {M}}_{2}\), all \({\dot{{{\textbf {p}}}}} \in T_{{{\textbf {p}}}}({\mathbb {M}}_{2})\) and all \({{\textbf {g}}}\in \text {SE}(2)\).
Remark 1
(Left-invariant Metric Tensor Field) Let \({\mathcal {G}}\) denote a left-invariant metric tensor field on G. Then there exists a unique constant matrix \([g_{ij}]_{ij}\in {\mathbb {R}}^{3\times 3}\) such that
where \(\otimes \) denotes the usual tensor product.
In the standard left-invariant model we restrict ourselves to the case \(g_{ij}= g_{ii}\delta _{ij}\), and then \({\mathcal {G}}\) is diagonal with respect to the co-frame \(\{\omega ^i\}_i\), i.e., \({\mathcal {G}}=\sum \limits _{i=1}^3g_{ii}\;\omega ^i\otimes \omega ^i\).
Often we do not want to work with symmetric Riemannian metric tensor fields (for instance to avoid cusps, and to ensure that fronts only move forward, see Fig. 5), and then we resort to the general Finsler geometry as done in [28, 34]. Essentially, this means that we replace the symmetric norm \(\sqrt{\left. {\mathcal {G}} \right| _{\gamma (t)}({\dot{\gamma }}(t),{\dot{\gamma }}(t))}\) in the Riemannian distance/metric:
by an asymmetric Finsler norm \({\mathcal {F}}(\gamma (t),{\dot{\gamma }}(t))\), given by
where the relaxation parameter \(0<\varepsilon \ll 1\) punishes spatial backward motions. For convergence results of geodesics and distances if \(\varepsilon \downarrow 0\), see [28, 42].
Later in Sect. 2.4 we will explain all parameter settings including the choice of \(g_{11},g_{22},g_{33}>0\) in \({\mathcal {F}}\).
Next, we define some relevant geometrical tools associated to (7) and (8).
Remark 2
(The Space of Curves over which we optimize) To adhere to standard conventions in Riemannian geometry we optimize over the space of piecewise continuously differentiable curves in \({\mathbb {M}}_2\) (indexed by \(T>0\)):
In (7) we set \(T=1\), as there the choice of T is irrelevant by parameterization independence of the functional.
Remark 3
(Control Sets) The control set in the tangent bundle \(T({\mathbb {M}}_2)\) is defined as
with \({{\textbf {p}}}\in {\mathbb {M}}_2\) and \({\mathcal {G}}\) the underlying Riemannian metric tensor field.
The corresponding asymmetric control set in the tangent bundle \(T({\mathbb {M}}_2)\) is defined as
with \({{\textbf {p}}}=({{\textbf {x}}},{{\textbf {n}}})\in {\mathbb {M}}_2\) and \({\mathcal {F}}\) the underlying Finslerian metric tensor field. In the limiting case where backward motions become prohibited as \(\varepsilon \downarrow 0\) (i.e., the sub-Finslerian setting) we only get half of the Riemannian control sets
2.3 Cartan Connections
The theory of Cartan connections was developed by Élie Cartan. His viewpoint on differential geometry relies on moving frames of reference (repère mobile). The idea is to connect tangent spaces by group actions on homogeneous spaces. This geometric tool allows us to understand the geodesic flow associated to (7) and its data-driven extensions.
The homogeneous space that we will use for crossing-preserving 2D image processing is the homogeneous space of positions and orientations \({\mathbb {M}}_2\). Here, the pushforward \((L_{{\textbf {g}}})_*\) of the left-multiplication connects \(T_{{\textbf {e}}}({\mathbb {M}}_2)\) to \(T_{{\textbf {g}}}({\mathbb {M}}_2)\) as it maps \(T_{{\textbf {e}}}({\mathbb {M}}_2)\) (isometricallyFootnote 3) onto \(T_{{\textbf {g}}}({\mathbb {M}}_2)\) and \((L_{{\textbf {g}}}^{-1})_*\), known as the Cartan-Ehresmann form, maps \(T_{{\textbf {g}}}(G)\) back to \(T_{{\textbf {e}}}(G)\).
First, we introduce the general definition of Cartan connections, after which we also introduce the Cartan plus connection [43]. In this article, we will introduce a data-driven version of the Cartan plus connection, leading to a generalization of the existing theory on shortest and straight curves in \({\mathbb {M}}_2\).
Definition 8
(Cartan Connection [43])A Cartan connection on a Lie group G is a tangent bundle connection with the following additional properties
-
1.
left invariance: if X, Y are left-invariant vector field then \(\nabla _X Y\) is a left-invariant vector field,
-
2.
for any \(A\in T_{{\textbf {e}}}(G)\) the exponential curve is auto-parallel, i.e., \(\nabla _{{\dot{\gamma }}(t)}{\dot{\gamma }}(t)=0\) where \(\gamma (t)=\gamma (0)\, \exp (tA)\).
We use the following special case of a Cartan connection to define shortest and straight curves. Note that this Cartan connection is easily expressed in the left-invariant frame [21, 43,44,45,46,47].
Definition 9
(Cartan Plus Connection [43])Consider a Lie group G of finite dimension n, with Lie brackets \([\cdot ,\cdot ]\) and structure constants \(c_{ij}^k\in {\mathbb {R}}\) s.t.
Then the Cartan plus connection is given by
Remark 4
Note that the \(\circ \) symbol denotes the composition of functions such that for example
For explicit coordinate expressions, see [43]. Next, we explain how to read and compute (12). The covariant derivative \(\nabla _X Y\) of a vector field Y with respect to a vector field X is again a vector field. Indeed the above formula gives
so that it becomes clear where X and Y typically enter in the open slots of the expression (12). Note that vector field \({\mathcal {A}}_i\) in (13) is a differential operator applied to the smooth function \(G\ni {{\textbf {g}}}\mapsto \omega ^k_{{\textbf {g}}}(Y_{{\textbf {g}}})\in {\mathbb {R}}\).
Remark 5
The connection \(\nabla ^{[+]}\) is called ‘Cartan plus connection’ as we add the two sums between the two large round brackets. In differential geometry one also has Cartan connections with a realvalued scalar factor in front of the second term, but this does not serve our applications [48].
Now that we explained Cartan connections, let us return to the core purpose of designing a geometric model such that projected geodesics follow the blood vessels.
2.4 Geodesic Tracking in the Space of Positions and Orientations \({\mathbb {M}}_2\)
Geodesic tracking methods aim to find the shortest paths following the underlying biological blood vessels in the retinal image. Such shortest paths are obtained by finding minimizing geodesics, which are defined as curves with the shortest length functionals. Typically, such length functionals are driven by a cost function that is small at locations of the blood vessels and high at all other places. Many different approaches to determine the minimizing geodesics have been proposed over the years, ranging from classical geodesic tracking in the image domain [14] to tracking in higher-dimensional homogeneous spaces [1, 12, 22, 28].
As already explained, we lift the input image f from \({\mathbb {R}}^2\) to \({\mathbb {M}}_2\) using orientation scores in homogeneous spaces [40, 41] (see Fig. 1). The tracking process involves computing a geodesic distance map in \({\mathbb {M}}_2\) and then using steepest descent to find the shortest curve in the lifted space. Finally, we project the curve back onto the input image in \({\mathbb {R}}^2\) to get the final tracking result, see the examples in Fig. 4.
Over time, different models have been introduced that describe how the geodesics should behave. Imagine a car moving along such geodesics. Then the Reeds–Shepp car model [29] which describes the problem of shortest paths for cars between an initial and final point, and the Reeds–Shepp forward model [28] turns off the reverse gear of the car. In both cases the spatially projected geodesics (optimal paths) tend to follow blood vessels in medical images well.
2.4.1 Symmetric Reeds–Shepp Car Model
The left-invariant metric tensor field of the symmetric Reeds–Shepp car model, \({\mathcal {G}}\), is given by the symmetric tensor field
for all \({\textbf {p}}=({\textbf {x}},{\textbf {n}}),\dot{{\textbf {p}}}=(\dot{{\textbf {x}}},\dot{{\textbf {n}}})\) with \( \Vert {\dot{{{\textbf {x}}}}}\wedge {{\textbf {n}}}\Vert ^2:=\Vert {\dot{{{\textbf {x}}}}}\Vert ^2-|{\dot{{{\textbf {x}}}}}\cdot {{\textbf {n}}}|^2. \) The anisotropy parameter \(\zeta \) penalizes vectors with large sideways components. Note that the classical sub-Riemannian model corresponds to the limit \(\zeta \downarrow 0\). For formal convergence results of the Riemannian model to the sub-Riemannian model see [28, Thm. 2]. In practice, choosing \(\zeta =0.1\) usually provides a good enough approximation of the sub-Riemannian model for our purposes. The last parameter \(\xi \), a weighting parameter, influences the flexibility of the tracking. It either stimulates or discourages angular movement over spatial movement [28].
The cost function \(C:{\mathbb {M}}_2\rightarrow [\delta ,1]\), with \(\delta >0\), discourages movement at specific locations, e.g., outside vessel structures. In this article, the smooth costfunction \((x,y,\theta )\mapsto C(x,y,\theta )\) is typically a version of the multiscale crossing-preserving vesselness map [49] explained in Appendix D. For an impression of what such a map C looks like see the 3D visualization in Fig. 18. As we consider rather complex vasculatures it is often more intuitive to display their minimum projections over \(\theta \), see for example Fig. 13.
2.4.2 Asymmetric Reeds–Shepp Car Model
Besides the symmetric version of the left-invariant metric tensor field of the Reeds–Shepp car model, an asymmetric version has been introduced in [28]. The forward gear left-invariant metric tensor field of this model is given by the asymmetric Finsler norm/function
for all \({\textbf {p}}=({\textbf {x}},{\textbf {n}}),\dot{{\textbf {p}}}=(\dot{{\textbf {x}}},\dot{{\textbf {n}}})\), with \(a_-:=\min \{0,a\}\). Equation (15) coincides with (8) with \(g_{11}=\xi ^2\), \(g_{22}= \xi ^2/\zeta ^2\), \(g_{33}=1\).
The parameters \(\zeta \) and \(\xi \) and the cost function C have the same meaning as in the symmetric model. However, we consider an extra variable \(\varepsilon \in (0,1]\) in the asymmetric Reeds–Shepp car model. This parameter determines how strongly the model needs to adhere to the forward gear. Note that when \(\varepsilon =1\), we find the symmetric Reeds–Shepp car model, and when \(\varepsilon \rightarrow 0\), backward movement becomes prohibited. In that case, we move from cusps to change orientation to in-place rotations visualized (cf. Figure 19 in Appendix D). These asymmetric Finslerian models are also highly beneficial in image segmentation as shown by Chen and Cohen [50].
2.5 Anisotropic Fast Marching
We provide here a brief overview of the partial differential equation (PDE) framework associated with geodesic distance maps, and of their numerical computation, see Sect. 5 for further details. We already mentioned that it is common to calculate minimizing geodesics in two steps; first calculating the geodesic distance map, then calculating the shortest curve using steepest descent. To get a first impression of how this looks like in practice, see Fig. 5. The geodesic distance map is characterized, in the PDE framework, as the viscosity solution of a static first-order Hamilton–Jacobi–Bellman equation, known as the Eikonal Equation. For numerically solving the Eikonal equation, it is discretized using for instance finite differences [12], leading to a coupled nonlinear system of equations, which is typically solved using a front propagation method such as the fast-marching algorithm (FMM). Classical references on the FMM include [17, 51], anisotropic variants are presented in [34, 36, 52], and the details related to our new model will follow in Sect. 5.1.
The fast-marching algorithm is a numerical method for solving the coupled system of equations discretizing the eikonal PDE. The algorithm proceeds in only one pass over the domain hence providing significant efficiency gains, but also requiring that the numerical scheme satisfies two conditions (monotonicity and causality), see [34, 36, Def. 2.1]. The proposed variant of this method uses Selling’s algorithm [53] to calculate in a preliminary step a decomposition of the quadratic forms defining the dual metric. This dual metric suitably only involves positive weights and vectors with integer coordinates, see Proposition 2. These ingredients are used to devise an adaptive finite differences scheme, discretizing the anisotropic Eikonal PDE and obeying the required conditions, see Sect. 5.2. The eikonal PDE is solved via an anisotropic fast-marching algorithm, and its solution provides the desired distance map. Finally, the minimizing geodesic is calculated by solving an ordinary differential equation defined in terms of the distance map [34, 36].
In previous studies of the Reeds–Shepp model and variants [28, 34], the geodesic metric tensor matrix featured a block diagonal structure, which was exploited in the discretization. However, while working with data-driven metric tensor fields, this block format does not apply! Therefore we adapt the anisotropic fast-marching algorithm to cope with the general setting. In this article, we will briefly discuss the changes that were necessary to solve data-driven metric tensor fields. Such data-driven geometric models (that we explain in the next section) give better tracking results than the previous model, as one can see in Fig. 5. In addition to that, using the anisotropic fast-marching algorithm to calculate the geodesics, only a limited number of runs (one for a single vessel, Fig. 5, and only two for a full vasculature, Fig. 3) are needed to correctly track the vascular structures.
2.6 Flowchart and Overview of the Methodology
Before we dive into the details of our method, we provide a sequential flowchart of our methodology, and more information on where more details of each part will be addressed.
-
1.
Create an orientation score of input image f (Eq. (3));
-
2.
Calculate the Hessian (App. C);
-
3.
Extract the Data-Driven frame from the Hessian (Eq. (17));
-
4.
Determine the local cost function for tracking: Vesselness Map (App. D);
-
5.
Identify the Finsler Function (with +-control in App. E) with the special Riemannian case (Eq. (8) with \(\varepsilon =1\)) in Theorem 1;
-
6.
Identify the Dual Finsler Function (with +-control in Lemma 2 and App. E);
-
7.
Analyze the Hamiltonian Flow of all geodesics (Theorem 1);
-
8.
Determine the Eikonal PDE distance map (symmetric case: Eq. (38), with +-control: Eq. (53));
-
9.
Numerically solve the Eikonal PDE using anisotropic fast marching:
-
3.
Apply steepest descent on the distance map (Sect. 5.4);
-
4.
Project the geodesic spatially by
$$\begin{aligned} \Pi (x(t),y(t),\theta (t))=(x(t),y(t)). \end{aligned}$$
3 Data-Driven Metric and Data-Driven Cartan Connection
In multi-orientation image processing, it is beneficial (for vessel segmentation [37]) to rely on locally adaptive frames [54, 55]. However, the locally adaptive frames in \({\mathbb {M}}_2\) typically require a stable selection of the principal eigenvector (eigenvector corresponding to the largest eigenvalue) of a symmetrized Hessian of the function \(U:\text {SE}(2)\rightarrow {\mathbb {R}}\). Recall that a Hessian is defined by a (dual) connection. Even if one uses the left Cartan connection, selecting the principal eigenvector can be locally unstable [55] and the largest eigenvalue may not be unique. For instance, if line structures are not locally present at all. Therefore, in this article, we take a slightly different approach by creating an unconditionally stable data-driven left-invariant metric tensor field.
Definition 10
(Data-Driven Left-Invariant Metric) Let G be a Lie group. Then the metric tensor field \({\mathcal {G}}^U\) is data-driven left invariant when it satisfies for all \(({{\textbf {g}}},{\dot{{{\textbf {g}}}}})\in T(G)\) and all \({{\textbf {q}}}\in G\):
Recall that in our case of interest where \(G=\text {SE}(2)\) and where \(U={\mathcal {W}}_{\psi }f\) is an orientation score of the image f, the equivariance relation (4) holds, so roto-translation of an image \(f \mapsto {\mathcal {U}}_{{\textbf {g}}}f\) is equivalent to roto-translation \(U \mapsto {\mathcal {L}}_{{\textbf {g}}}U\) of the score.
Consequently (as will follow in Theorem 1) if a metric tensor field is data-driven left invariant then a roto-translation \({\mathcal {U}}_{{\textbf {g}}}f\) of the input image f yields a new geodesic \(\gamma _{new}\) that is rotated and translated accordingly: \(\gamma _{new}(\cdot )={{\textbf {g}}}\gamma (\cdot )\).
Thus, Definition 10 is a valid constraint in our application as we want the vessel tracking along geodesics to be equivariant with respect to roto-translations.
By creating such a data-driven metric tensor field \({\mathcal {G}}^U\) on our Lie group of interest \(G=\text {SE}(2)\equiv {\mathbb {M}}_{2}\), data-driven corrections are made for spatial and angular misalignment in existing models relying on the standard left-invariant frame [24, 55, 56]. We will see that a better fitted metric tensor field \({\mathcal {G}}^U\) has a significant impact on the tracking results for very tortuous vessels, as shown in Fig. 5. For our case of interest \({\mathbb {M}}_2\), a reasonable choice that satisfies the constraint, and that we use in our experiments, is given by:
with \({\textbf {p}}=({\textbf {x}},{\textbf {n}}) \in {\mathbb {M}}_{2}\) and \(\dot{{\textbf {p}}}=(\dot{{\textbf {x}}},\dot{{\textbf {n}}}) \in T_{{\textbf {p}}}({\mathbb {M}}_{2})\). Here the Hessian field HU is defined in Lemma 4 in Appendix C, and \(\Vert \cdot \Vert _*\) the dual norm corresponding to the primal norm given by \(\sqrt{{\mathcal {G}}_{{\textbf {p}}}({\dot{{{\textbf {p}}}}},{\dot{{{\textbf {p}}}}})}\) with \(\zeta =1\) in (14).
Parameter \(\lambda >0\) regulates inclusion of data-driven 2nd order line-adaptation to the orientation score data U, cf. Fig. 1.
Finally, the data-driven left-invariant metric tensor field relies on the usual Reeds–Shepp car models \({\mathcal {G}}\), respectively, \({\mathcal {F}}\) with external smooth cost \(C({\textbf {p}})\) satisfying:
computed from the orientation score U, as explained in Appendix D. There we combine ideas on crossing-preserving vesselness maps from [28, 37, 49].
Remark 6
Within \({\mathcal {G}}\) and \({\mathcal {F}}\) in (17) we set \(\zeta ^2=0.01=g_{11}/g_{22}\) as relative costs for sideward motion, recall (14). Ideally we want this to be high, but as we will prove in the numerics section (Sect. 5.2), a spatial anisotropy of \(\zeta ^2=0.01\) still guarantees numerical accuracy. We follow [12, 28] and set bending stiffness \(\xi ^2=g_{11}=0.01\) and \(g_{33}=1\).
Proposition 1
Metric tensor field \({\mathcal {G}}^U\) given by Eq. (17) is indeed data-driven left-invariant (i.e., satisfying (16)).
Proof
See Lemma 6 in Appendix C. \(\square \)
Next, we list a few remarks that underpin and explain our specific choice of metric tensor field.
Remark 7
In geometric image analysis [57], eigenvectors of the Hessian typically provide a local coordinate frame along lines. In orientation scores, this is not different [24]. In \({\mathbb {M}}_2\), Hessians \(HU=\nabla ^{[+],*}\text {d}U\) are not symmetric and we rely on a singular value decomposition via the dual norm in (17) which only relies on the symmetric product, see Remark 9.
Remark 8
Formally speaking, the (old) metric tensor fields \({\mathcal {G}}\) and asymmetric version \({\mathcal {F}}\) are also data-driven if it comes to scalar-adaptation via cost function C, but as they do not adapt for any kind of directional data-adaptation (as illustrated in Fig. 6) we do not refer to them as ‘the data-driven model’.
Remark 9
Via the identification (1) we write \({\textbf {p}}=(x,y,\theta )\) for short. Then in fixed coordinates on \({\mathbb {R}}^2 \times {\mathbb {R}}/(2\pi {\mathbb {Z}})\) one may write \({\dot{{{\textbf {p}}}}}=({\dot{x}},{\dot{y}},{\dot{\theta }})^\top \). The dual norm expression \(\left\| \left. HU\right| _{{\textbf {p}}}({\dot{{{\textbf {p}}}}},\cdot )\right\| _*^2\) in (17) then boils down to a straightforward Euclidean norm:
where \(M_\xi =\text {diag}\,(\xi ^{-1},\xi ^{-1},1) \in {\mathbb {R}}^{3\times 3}\).
For details of Hessians of functions on manifolds with a connection, see Appendix C. For now let us focus on the notion of data-driven left-invariant frames, where we improve upon the ‘Locally Adaptive Derivatives (LADs)’ in [37, 55].
Definition 11
(Data-Driven Left-Invariant Frame) Any data-driven metric tensor field \({\mathcal {G}}^U\) can be diagonalized:
and this defines the positively oriented data-driven left-invariant co-frame \(\left\{ \omega _U^i\right\} _{i=1}^3\), dual to the primal frame \(\left\{ {\mathcal {A}}_j^U\right\} _{j=1}^3\) related by \(\langle \omega _U^i,{\mathcal {A}}_j^U\rangle =\delta _j^i\).
Remark 10
(Advantages of our data-driven metric and frame) The local frame of reference \(\{{\mathcal {A}}_{i}^U\}\) depends on the image data, cf. Fig. 6. In fact, Eq. (20) is used to define the dual of the data-driven left-invariant frame via diagonalization. This deviates from LADs in previous work [37, 43]. We now have the advantage of coercivity
recall (18), independent of the orientation score data U, which makes the tracking algorithms unconditionally stable. Furthermore, we now have another advantageous property over LADs, namely that \({\mathcal {A}}_i^U={\mathcal {A}}_i\) for U constant.
In order to calculate distances using the new data-driven metric tensor field, we need to introduce the data-driven Riemannian distance.
Definition 12
(Data-Driven Riemannian Distance) The data-driven Riemannian distance \(d_{{\mathcal {G}}^U}\) from a point \({{\textbf {p}}}\in {\mathbb {M}}_2\) to a point \({{\textbf {q}}}\in {\mathbb {M}}_2\) is given by
where \(\Gamma _1\) was defined in (9), and \({\dot{\gamma }}(t):=\frac{\text {d}}{\text {d}t}\gamma (t)\).
Remark 11
If image U is constant, then \({\mathcal {G}}^U={\mathcal {G}}\), \(d_{{\mathcal {G}}^U}=d_{{\mathcal {G}}}\).
Remark 12
Note that this distance can always be transformed to a quasi-distance when we are working in with the forward gear version of the model:
Using the new data-driven metric frame, recall Definition 11, we introduce the data-driven Cartan plus connection, which will be used to express ‘short’ and ‘straight’ curves in Sect. 4.
Definition 13
(Data-Driven Cartan Plus Connection) The data-driven Cartan plus connection is given by
Explicit coordinate expressions will follow in Lemma 1.
In Table 1, an overview of the notation used for the new concepts introduced in this work and concepts introduced in earlier work is given.
In Fig. 7, the exponential curves and the control sets for both discussed Cartan connections, \(\nabla ^{[+]}\) and \(\nabla ^U\) are visualized. In addition to that, the tracking results relying on different models are plotted. One sees that the data-driven Cartan connection better adapts for curvature leading to more accurate tracking results.
4 The New Geometric Tracking Model: Asymmetric Finsler Functions Steered by Locally Adaptive Frames
We discuss a new data-driven version of the Cartan connection. This result applies to all Lie-groups G of finite dimension \(\text {dim}(G)=n\). Note that \(\text {SE}(2)\equiv {\mathbb {M}}_2\), but the result does not apply to all homogeneous spaces (like \({\mathbb {M}}_d\) for \(d>2\)). The notation used in this section is summarized in Table 2.
We consider a locally adaptive frame \(\left\{ {\mathcal {A}}_{i}^U\right\} _{i=1}^n\) with dual frame \(\left\{ \omega _U^i\right\} _{i=1}^n\). This can be any well-defined frame that depends on the underlying data. The (data-driven) metric tensor field that is considered, is given by (20). The data-driven terms can adapt for curvature and deviation from horizontality where the direction of the left-invariant frame deviates from the underlying line structure.
4.1 Combine Optimally Straight and Short: A New Data-Driven Version \(\nabla ^{U}\) of the Cartan Connection
In previous works, the Cartan plus connection, which relies on the left-invariant frame, has been used to describe straight and shortest curves in Lie groups [48]. However, this frame is not always adequate in multi-orientation image processing as it does not always align perfectly with the underlying line structures in the orientation scores (see Fig. 6). To improve the tracking results, we, therefore, switch to using a data-driven Cartan connection associated with the data-driven metric tensor field \({\mathcal {G}}^U\) given by (17). Let us first define what we mean by a ‘data-driven Cartan connection’.
Definition 14
The data-driven Cartan connection and its corresponding dual are given by
where \(\left( \nabla ^U\right) _X^*\lambda :=\left( \nabla ^U\right) ^*(X,\lambda )\) and \(\nabla _X^U Y:=\nabla ^U(X,Y)\).
Remark 13
The relation between \(\nabla \) and its dual \(\nabla ^*\) is
for all vector fields X, Y and all covector fields \(\lambda \) on G, which may be interpreted as a product rule for the pairing between the vectors and co-vectors. In particular for \(X\!=\!{\mathcal {A}}^U_i\), \(Y\!=\!{\mathcal {A}}_j^U\) and \(\lambda =\omega _U^k\) we get
In the next lemma, we will express the data-driven Cartan connection and its corresponding dual explicitly in coordinates, which will provide us an expression on which we will build in the proof of our main theorem, Theorem 1.
Lemma 1
When expressing Eqs. (28) and (29) more explicitly in data-driven left-invariant frame components (gauge frame components for short), one finds
and for the dual connection
where \(X=\sum \limits _{i=1}^n{\tilde{x}}^i{\mathcal {A}}_{i}^U|_\gamma \), \(Y=\sum \limits _{i=1}^n {\tilde{y}}^i{\mathcal {A}}_{i}^U|_\gamma \) and \(\lambda =\sum \limits _{i=1}^n{\tilde{\lambda }}_i\omega _U^i\), and where derivations of the components of Y and \(\lambda \) equal
along a flow-lineFootnote 4\(\gamma :[0,1]\rightarrow {\mathbb {M}}_2\) of smooth vector field X.
Proof
See Appendix A. \(\square \)
4.2 Main Theorems
Our goal is to analyze and structure the Hamiltonian flow belonging to the new data-driven geometric model determined by a data-driven metric tensor field \({\mathcal {G}}^U\). For convenience, we restrict ourselves in our main theorem to the case where the homogeneous space equals a full finite-dimensional Lie group G as the base manifold. We are mainly interested in the case \(G=\text {SE}(2) \equiv {\mathbb {M}}_{2}\) with \(n=3\) and with data-driven metric tensor field \({\mathcal {G}}^U\) given by (17).
In geometric control curve optimization problems, the Hamiltonian flow is a powerful mechanism [58,59,60,61,62]. It typically allows us to analyze the behavior of all geodesics (and their momentum) together, see e.g., [62]. In the left-invariant (non-data-driven) setting, the Hamiltonian flows were characterized [43, Thm. 1 &2] via the plus Cartan connection, where shortest curves (geodesics) have parallel momentum. It has led to exact formulas [26, 63] for specific settings (uniform cost case in the left-invariant model \({\mathcal {G}}\) given in (14), \(C=1\) which was introduced on \({\mathbb {M}}_2\equiv \text {SE}(2)\) by Citti and Sarti [64] and deeply analyzed by Sachkov [65]). Remarkably, the Cartan plus connection \(\nabla ^{[+]}\) has torsion resulting in different ‘straight curves’ (parallel velocity) and ‘shortest curves’ (parallel momentum), and it underlies many multi-orientation image analysis applications [43].
Before stating the main theoretical result, that generalizes [43, Thm. 1 &2] to data-driven metric tensor fields \({\mathcal {G}}^U\), we introduce the concepts of parallel momentum and parallel velocity. They are now determined by the data-driven Cartan connection \(\nabla ^U\) and its dual \(\left( \nabla ^U\right) ^*\).
Definition 15
(Parallel momentum) Let \(\gamma :[0,1]\rightarrow G\) be a smooth curve. Then, the curve \(\gamma (\cdot )\) has \(\nabla ^{U}\) parallel momentum \(\lambda (\cdot )\)
Definition 16
(Parallel velocity) Let \(\gamma :[0,1]\rightarrow G\) be a smooth curve. Then, the curve \(\gamma (\cdot )\) has parallel velocity \({\dot{\gamma }}(\cdot )\) w.r.t. connection \(\nabla ^{U}\)
Remark 14
Using the antisymmetry of the structure functions (26) and (31) in Lemma 1 we can rewrite Eq. (34) to
Next, we formulate the main theoretical results where we generalize the main results [43, Thm. 1 &2] from the left-invariant setting \((G,{\mathcal {G}})\) with connection \(\nabla ^{[+]}\), to the new data-driven geometric models \((G,{\mathcal {G}}^U)\) with connection \(\nabla ^U\). In more detail, the next theorem shows
-
1.
how to compute globally optimal distance minimizers in a geometry that relies on data-driven left-invariant frames: These geodesics have parallel momentum w.r.t. connection \(\nabla ^{U}\) (Definition 15).
-
2.
that the locally optimal straight curves are the straight curves w.r.t. connection \(\nabla ^{U}\): These curves have parallel velocity (i.e., are auto-parallel) w.r.t. \(\nabla ^{U}\) (Definition 16).
Note that the equation for geodesics of the new data-driven model \(({\mathbb {M}}_{2},{\mathcal {G}}^U)\) gives a wild expression in the left-invariant frame. In the fixed frame it is even worse. However, our new tool of the connection \(\nabla ^U\) expressed in the locally adaptive frame \(\omega _{i}^U\) allows us to describe these geodesic equations (and the Hamiltonian flow) concisely and intuitively by the next theorem, using the tools listed in Table 2.
Theorem 1
(Straight and shortest curves: parallel velocity and momentum w.r.t. connection \(\nabla ^{U}\)) In a Riemannian manifold \((G, {\mathcal {G}}^U)\) with data-driven left-invariant metric tensor field \({\mathcal {G}}^U\) satisfying (16), and with induced Riemannian metric \(d_{{\mathcal {G}}^U}\) (22), we have:
-
\(\gamma \) is a straight curve with respect to \(\nabla ^U\) \(\overset{\text {def.}}{\Leftrightarrow }\) \(\nabla _{{\dot{\gamma }}}^{U}{\dot{\gamma }}=0\)
$$\begin{aligned} \Leftrightarrow \exists \ (c^1,\ldots ,c^n) \in {\mathbb {R}}^n \text { constant s.t. }{\dot{\gamma }}=\sum _{i=1}^n c^i {\mathcal {A}}_{i}^U|_\gamma . \end{aligned}$$ -
\(\gamma \) is a shortest curve with respect to \(\nabla ^U\) \(\Rightarrow \) the curve-momentum pair \(\nu =(\gamma , \lambda ): [0,1] \rightarrow T^*(G)\) satisfies the Hamiltonian flow
$$\begin{aligned} {\dot{\nu }}=\overrightarrow{{\mathfrak {h}}}(\nu ) \Leftrightarrow {\left\{ \begin{array}{ll} (\nabla ^{U})_{{\dot{\gamma }}}^*\lambda =0\\ {\mathcal {G}}^U {\dot{\gamma }}=\lambda , \end{array}\right. } \end{aligned}$$(35)where one has the following pullback symmetryFootnote 5 of the data-driven Cartan connection
$$\begin{aligned} (L_{{{\textbf {q}}}})^* (\nabla ^{{\mathcal {L}}_{{{\textbf {q}}}} U})^* =(\nabla ^U)^* \text { for all }{{\textbf {q}}}\in G, \end{aligned}$$(36)with left actions L and \({\mathcal {L}}\) given by (2) and (5), respectively.
The shortest curve \(\gamma :[0,1] \rightarrow G\) with \(\gamma (0)={{\textbf {g}}}\) and \(\gamma (1)={{\textbf {g}}}_0\) may be computed by steepest descent backtracking on the distance map \(W({{\textbf {g}}})=d_{{\mathcal {G}}^U}({{\textbf {g}}},{{\textbf {g}}}_0)\)
where Exp integrates the following vector field on G: \(v(W)\!:=\!-W({{\textbf {g}}}) ({{\mathcal {G}}^U})^{-1}\text {d}W\!=\!-W({{\textbf {g}}}) \!\sum \limits _{k=1}^n |\alpha _k|^{-1} {\mathcal {A}}_k^U(W) {\mathcal {A}}_{k}^U\)and where W is the viscosity solution of the eikonal PDE system
where we assume \({{\textbf {g}}}\) is neither a 1st Maxwell-point nor a conjugate point. As v(W) is data-driven left-invariant, the geodesics carry the symmetry
Proof
See Appendix B. \(\square \)
Remark 15
(Assumptions on point \({{\textbf {g}}}\) in backtracking (37)) For the geodesic backtracking formulated above, we need a differentiable distance map along the path and a well-posed Hamiltonian flow (i.e., the mapping from \(\nu (0)\) to \(\nu (t)\) arising from (35) must have a non-vanishing Jacobian) along the path. If \({{\textbf {g}}}\) would be a first Maxwell-point (i.e., two distinct geodesics meet for the first time at \({{\textbf {g}}}\)) the distance map is not differentiable at \({{\textbf {g}}}\). If \({{\textbf {g}}}\) would be a conjugate point (often limits of first Maxwell points [12]) then the Hamiltonian flow breaks down. In the latter case, local optimality is lost. In the first case, global optimality is lost. Fortunately the viscosity property of the viscosity solution [66] of (38) kills non-optimal fronts [12] and one may resort to multi-valued backtracking via sub-gradient backtracking.
The next 3 remarks show how incredibly simple the Hamiltonian flow, the eikonal PDE, and the backtracking of geodesics become when expressed in the data-driven left-invariant frame.
Remark 16
Equation (33) is in gauge frame components simply:
Remark 17
Equation (38) is in gauge frame components simply:
Remark 18
Equation (37) is in gauge frame components simply:
This explains the definition of v(W) below (37). A more explicit integration formula for (37) can be obtained in a similar way as in [26, 63] (where exact solutions are derived for \(C=U=1\)) via momentum preservation laws.
4.3 Asymmetric Finsler Extension to Automatically Deal with Bifurcations
One can always decide to include a positive control variant, to avoid cusps in the spatial projection of geodesics in \(G=\text {SE}(2)\). This is done by considering the geodesics in the asymmetric Finslerian manifold \(({\mathbb {M}}_{2},{\mathcal {F}}^U)\), recall (17), rather than the geodesics in the Riemannian manifold \(({\mathbb {M}}_{2},{\mathcal {G}}^U)\).
It is not too hard in practice: a slight adaptation of the eikonal PDE (taking the positive part of one momentum component) will guarantee that all optimal geodesic wavefronts propagate in the preferred forward direction around the source point, as can be observed in Fig. 5 where the fronts initially move ‘down-left’ (and not ‘up-right’).
The asymmetric Finslerian model \(({\mathbb {M}}_{2},{\mathcal {F}}^U)\) is still well-posed (controllable and piecewise regular geodesics) even if \(\zeta \downarrow 0\). In fact, such asymmetric Finslerian geodesics are by construction piecewise concatenations of Riemannian geodesics and in-place rotations. These observations follow by a straightforward generalization of [28, Thm. 1, 2, 4] to the data-driven setting, where the control set formulation of the geodesic distances, still applies:
where \(\Gamma _T\) was defined in (9). Moreover, the field of control sets given by \( {{\textbf {p}}} \mapsto {\mathcal {B}}_{{\mathcal {F}}^U}({{\textbf {p}}}) \) recall (10) remains continuous when using \({\mathcal {F}}^U\) or \({\mathcal {G}}^U\) (instead of \({\mathcal {F}}\) or \({\mathcal {G}}\)), which directly follows by [28, Lemma 6] in conjunction with the important coercivity property (21).
The nice thing in practice is that in-place rotations are automatically placed at optimal locations by the eikonal PDE system (solved by the anisotropic fast-marching algorithm that we discuss in the next section). It is not surprising that, when using a reasonable cost function C (see Figs. 12 and 13), these in-place rotations are automatically placed at bifurcations in complex vascular trees as can be observed in the upcoming Fig. 16.
5 Numerical Solutions to the Eikonal PDE System: Extension of the Anisotropic Fast-Marching Algorithm that Allows for All Left-Invariant Data-Driven Metrics
In this section we describe the computation of globally minimizing geodesics for the new models \({\mathcal {F}}^U\) considered in this paper, whose fundamental ingredient is the numerical solution to an anisotropic eikonal PDE. The Reeds–Shepp forward optimal control model \({\mathcal {F}}\), of which a variant \({\mathcal {F}}^U\) is considered in this paper, has already been addressed numerically using a Semi-Lagrangian [28] and Eulerian [34] discretization of the corresponding eikonal PDE. Both works however take advantage of the fact that the original geodesic model \({\mathcal {F}}\) regards the tangent spaces to the physical \({{\mathbb {R}}}^2\) and the angular \(S^1\) domains as orthogonal to each other. However, in our case of interest (with model \({\mathcal {F}}^U\) given by (17)), we cannot expect such a block-matrix structure in the fixed coordinate system \((x,y,\theta )\).
To overcome this problem, we describe below the extension of [34] to the adaptive frame setting considered here, where this orthogonality relation is lost; in contrast, [28] could not be generalized in an efficient manner.
Remark 19
(Convenience notations for the numerical section) Throughout this section, we label the dependence w.r.t. the relaxation parameter \(\varepsilon \in (0,1]\), so as to analyze it more easily, and to investigate the limit \(\varepsilon \rightarrow 0\). In contrast, we often drop the dependence w.r.t. the data U, which is regarded as fixed.
We also take advantage of the fact that the manifold \({{\mathbb {M}}}_2:= {{\mathbb {R}}}^2 \rtimes S^1 \equiv {{\mathbb {R}}}^2 \times {{\mathbb {R}}}/(2\pi {{\mathbb {Z}}})\) has a trivial tangent bundle: \(T_{{{\textbf {p}}}}({\mathbb {M}}_{2}) \equiv {{\mathbb {R}}}^2 \times {{\mathbb {R}}}\equiv {{\mathbb {R}}}^3\) canonically for any \({{\textbf {p}}}\in {{\mathbb {M}}}_2\), and likewise \(T^*_{{\textbf {p}}}({\mathbb {M}}_{2}) \equiv {{\mathbb {R}}}^3\). As a result, by identifying co-vectors and vectors by their components in \({\mathbb {R}}^3\), the functional brackets \(\langle \cdot , \cdot \rangle \) below boil down to the ordinary dot product on \({\mathbb {R}}^3\). Similarly, the tensor product \(\omega \otimes \omega \) boils down to \(\omega \omega ^\top \).
5.1 Asymmetric Quadratic Eikonal PDE
The Reeds–Shepp forward model, is defined through a sub-Finslerian quasi-metric,Footnote 6 relaxed by a small parameter \(\varepsilon >0\), recall \({\mathcal {F}}\) was given by Eq. (8) and its data-driven version \({\mathcal {F}}^U\) was given by (17). Throughout this section, and in our vessel tracking experiments, we are concerned with the case where sideward motions and backward motions become very expensive: we set spatial anisotropy parameter \(\zeta =\varepsilon \) with \(0<\varepsilon \ll 1\) in the Finsler norm \({\mathcal {F}}^U\) given by (17).
The generic form of the data-driven Finsler metric function considered in this paper (17) reads:
for any point \({{\textbf {p}}}\in {{\overline{\Omega }}}\), within a given bounded connected domain \(\Omega \subset {{\mathbb {M}}}_2\), and any tangent vector \({{\dot{{{\textbf {p}}}}}} \in T_{{{\textbf {p}}}}({\mathbb {M}}_{2}) \equiv {{\mathbb {R}}}^3\), and where the two small parameters \(\epsilon ,\varepsilon \) relate via
In the following analysis, we only use the property that the tensor field \(M^0\) is pointwise positive definite, that the differential forms \(\omega ^1\) and \(\omega ^2\) are pointwise linearly independent, and that \(M^0: {{\overline{\Omega }}} \rightarrow S_3^{++}\), and \(\omega ^1, \omega ^2: {{\overline{\Omega }}} \rightarrow {{\mathbb {R}}}^3\) (following the conventions of Remark 19) have Lipschitz regularity. Here \(S_{3}^{++}\) denotes the space of \(3\times 3\) symmetric positive definite real-valued matrices.
Remark 20
In the normal left-invariant setting \({\mathcal {F}}^{U=1}={\mathcal {F}}\) the asymmetric metric expressed in the fixed frame \(({\dot{x}},{\dot{y}},{\dot{\theta }})\), of the tangent space at any coordinates \((x,y,\theta )\), has a block diagonal structure. In contrast the data-driven metrics \({\mathcal {G}}^U\), \({\mathcal {F}}^U\), in general, does not have a block-matrix structure, as the independent elements \(\{\omega ^i_U\}_{i=1}^3\) may point anywhere due to their data-driven nature, as can be seen in Fig. 6, keeping in mind the duality (23). Therefore, we must introduce a new modification of the anisotropic fast-marching algorithm.
The purpose of the second term in (42) is to increase the cost of sideways motions, whereas the final term prevents motions in reverse gear; both are excluded in the genuine Reeds–Shepp forward car model obtained in the limit (akin to [28, Thm. 2]) as \(\varepsilon \rightarrow 0\), which is non-holonomic.
The distance map \(W: {{\overline{\Omega }}} \rightarrow {{\mathbb {R}}}\) from a given point \({{\textbf {p}}}_0 \in \Omega \) and w.r.t. the Finsler function \({{\mathcal {F}}}_\varepsilon \), is the unique viscosity solution to the following anisotropic eikonal system
where the dual Finsler function equals by definition
with \({\hat{{{\textbf {p}}}}}\in T_{{\textbf {p}}}^*({\mathbb {M}}_2)\).
The structure of the metric (44), referred to as asymmetric quadratic, allows to compute a closed form expression of the dual metric \({{\mathcal {F}}}_\epsilon ^*\), and thereby the eikonal PDE (44), as we will see below.
Lemma 2
Let \(M \in S_3^{++}\) and \(\omega \in {{\mathbb {R}}}^3\), and define
Then \({{\mathcal {F}}}\) is a quasi-norm (i.e., an asymmetric norm), whose dual quasi-norm reads for all \(\hat{{\textbf {p}}}\in {{\mathbb {R}}}^3\)
with \(D:= (M +\omega \, \omega ^\top )^{-1}\) and \(\eta := M^{-1} \omega /\sqrt{1+\omega ^{\top } M^{-1}\omega }\).
Proof
See [28, Lemma 4]. \(\square \)
For concreteness, we apply Lemma 2 to our Finsler function \({{\mathcal {F}}}_\epsilon \) of interest (44), defined pointwise by the parameters
This then results in the following dual Finsler functions:
Lemma 3
(Dual Finsler Functions) With our choice (42) of Finsler function \({\mathcal {F}}_{\varepsilon }\) used in (44), the dual Finsler function \({\mathcal {F}}_{\varepsilon }^*\) is given for all \(\hat{{\textbf {p}}}\in T_{{{\textbf {p}}}}^*({\mathbb {M}}_2) \equiv {{\mathbb {R}}}^3\) by
where we used the shorthand notation \(M^{-1}:= (M^0)^{-1}\), the cross-product \({\omega }:= \omega _U^1 \times \omega _U^2\), and the orthogonalization coefficient \(\alpha :=(\omega _U^2)^\top M^{-1} \omega _U^1 / (\omega _U^2)^\top M^{-1} \omega _U^2\).
Proof
Follows by Lemma 2 and Taylor expansion, for details, see Appendix F. \(\square \)
Note that by (43), \({\mathcal {O}}(\epsilon ^2)={\mathcal {O}}(\varepsilon ^2)\) for small values of \(\varepsilon \).
Lemma 3 shows that one can define an ideal sub-Finsler function \({{\mathcal {F}}}_0^*\) that arises in the limiting case \(\epsilon \downarrow 0\), and that
Our goal, achieved in Sects. 5.1 and 5.2, is to design a numerical scheme that is consistent with the sub-Finslerian eikonal PDE \({{\mathcal {F}}}_0^*({{\textbf {p}}}, \text {d} W({{\textbf {p}}}))=1\), and which satisfies the conditions that make the fast-marching algorithm applicable.
5.2 Discretization and Consistency
We discretize the eikonal PDE (44), which has an asymmetric quadratic structure (45), using adaptive finite differences on the Cartesian grid \(\Omega _h:= \Omega \cap h {{\mathbb {Z}}}^3\) of the domain \(\Omega \), where \(h>0\) denotes the grid scale. Note that \(2\pi /h\) must be an integer, for consistency with the periodic boundary conditions in the angular coordinate. The numerical scheme construction relies on Selling’s decomposition of positive definite matrices [53] and on a corollary related to the approximation of the squared positive part of a linear form. The versions of these results presented in [34, Corollary 4.12, Corollary 4.13] are gathered in the following proposition.
We denote \(\mu (D):= \sqrt{\Vert D\Vert \Vert D^{-1}\Vert }\), for any \(D \in S_3^{++}\), and \(a_+:= \max \{0,a\}\), for any \(a \in {{\mathbb {R}}}\).
Proposition 2
(Selling matrix decomposition, see [34]) For any \(D \in S_3^{++}\), there exists \(\dot{{\textbf {e}}}_1,\cdots ,\dot{{\textbf {e}}}_I \in {{\mathbb {Z}}}^3\) and \(\lambda _1,\cdots ,\lambda _I \ge 0\), such that for all \(\hat{{\textbf {p}}}\in {{\mathbb {R}}}^3\)
For any \(\eta \in {{\mathbb {R}}}^3\), \(\epsilon >0\), there exists \(\dot{{\textbf {f}}}_1,\cdots ,\dot{{\textbf {f}}}_I \in {{\mathbb {Z}}}^3\) and \(\mu _1,\cdots ,\mu _I \ge 0\), such that for all \(\hat{{\textbf {p}}}\in {{\mathbb {R}}}^3\)
In addition \(\Vert \dot{{\textbf {e}}}_i\Vert ,\cdots ,\Vert \dot{{\textbf {e}}}_I\Vert \le C \mu (D)\) and \(\Vert \dot{{\textbf {f}}}_i\Vert ,\cdots ,\Vert \dot{{\textbf {f}}}_I\Vert \le C\varepsilon ^{-1}\). The above holds with the constants \(I:= 6\), \(C:= 4\sqrt{3}\).
Remark 21
A key aspect of Proposition 2 is that the vectors \((\dot{{\textbf {e}}}_i)\) and \((\dot{{\textbf {f}}}_j)\) have integer coordinates, hence we avoid (off-grid) interpolations in our discretization.
Proposition 2 suggests the following discretization of \({{\mathcal {F}}}^*(\text {d}W({{\textbf {p}}}))\), as in (45), for arbitrary \(D \in S_3^{++}\), \(\eta \in {{\mathbb {R}}}^3\), \(\varepsilon >0\):
with suitable boundary conditions. This numerical scheme falls within the Hamiltonian fast-marching framework [36], and thus can be efficiently solved numerically, see Sect. 5.3. Before that, we discuss its consistency with the eikonal equation: inserting a first order Taylor expansion in (51), we obtain (using Proposition 2):
where \(R:= \max \{\mu (D),\epsilon ^{-1}\}>0\) denotes the stencil radius.
We next analyze the approximation error toward the ideal model as \(\epsilon \rightarrow 0\) and \(h\rightarrow 0\) suitably. To this end we denote by \({{\mathfrak {F}}}^h_\epsilon \) the finite differences scheme on \(\Omega _h\) associated with the parameters \(D_\epsilon \) and \(\eta _\epsilon \) of our application (47). Note that the stencil radius is \(R_\epsilon =\max \{\mu (D_{\epsilon }),\epsilon ^{-1}\} = {{\mathcal {O}}}(\epsilon ^{-1})\), since \(\mu (D_\epsilon ) = \mu (M_\epsilon ) = {{\mathcal {O}}}(\epsilon ^{-1})\) in view of (46). Now combining (50) with (52), we obtain the overall consistency error
The optimal order of the consistency error \({{\mathcal {O}}}(h^\frac{2}{3})\) is achieved with the scaling \(\epsilon = h^{\frac{1}{3}}\). In our practical experiments however, we rather use the small fixed value \(\zeta =\varepsilon =0.1\) which by (53) indeed yields a sufficiently accurate scheme [34]!
5.3 Anisotropic Fast-Marching for Computing Distance Maps of Data-Driven Left-Invariant Finsler Models
In fast-marching methods (FMM), one divides the grid points into 3 categories: Far, Trial, and Accepted. In each step of the FMM, one selects the trial point \({{\textbf {p}}}\) whose function value \(W({{\textbf {p}}})\) is minimal. The point \({{\textbf {p}}}\) is moved into the accepted set, and \(W({{\textbf {p}}})\) is frozen. In contrast, all the trial or far points whose stencil contains \({{\textbf {p}}}\) see their function value updated, and they are moved into the trial set. This procedure generalizes and abstracts the classical FMM [51], for details see [21]. When all points have moved to the accepted category, the FMM terminates, and a geodesic can be easily calculated by steepest descent as described in Sect. 5.4.
The update of a single function value \(W({{\textbf {p}}})\) is defined as follows: isolate \(W({{\textbf {p}}})\) in the numerical scheme expression (51), and express it by the values of its neighbors so as to obey \(\mathfrak {F}W({\textbf {p}})=1\). The latter equation admits by construction a unique solution, which is obtained as the largest root of a quadratic equation.
There are two crucial properties of the discretization \({{\mathfrak {F}}}\):
-
Discrete Degenerate ellipticity: \({{\mathfrak {F}}}W({{\textbf {p}}})\) is a non-decreasing function of the finite differences in (51).
-
Causality: \({{\mathfrak {F}}}W({{\textbf {p}}})\) only depends on the positive part of all finite differences in (51).
These are the two keyFootnote 7 assumptions of [52, Theorem 2.3], implying that the discretized PDE (53) admits a unique solution \(W_h^\epsilon \), which is computable in a single pass over the discretization domain \(\Omega _h\), using anisotropic fast-marching.
Following the steps of the proof [34] associated with the standard Reeds–Shepp forward model, and with straightforward adaptations, we obtain that \(W_h^\epsilon \) converges uniformly as \(\epsilon \rightarrow 0\) and \(h/\epsilon \rightarrow 0\) to the solution W of the sub-Finslerian Eikonal PDE \({{\mathcal {F}}}_0^*({{\textbf {p}}}, \text {d} W({{\textbf {p}}}))=1\).
5.4 Steepest Descent for the Finslerian Geodesics
In previous work [28, Thm. 4], standard Riemannian steepest descent tracking on the distance map W, recall (37) in Theorem 1, is generalized from the symmetric Riemannian setting to the (possibly asymmetric) Finsler model setting. That idea also transfers to the new data-driven left-invariant model as the Finslerian backtracking [28, App. B] still applies. Steepest descent tracking (37) from \({{\textbf {p}}}\) to source point \({{\textbf {p}}}_0\) again becomes (using the embedding of \({\mathbb {M}}_2\subset {\mathbb {R}}^3\))
with \(0<\epsilon \ll 1\) and where the derivative is taken with respect to the second entry of the dual Finsler function, and where W is the viscosity solution of the eikonal PDE system (44).
In the practical implementations we use a second order Runge–Kutta method for time integration approximations and at time \(t=1\) we arrive at the source-point \({{\textbf {p}}}_0\).
This geodesic backtracking in \(({\mathbb {M}}_{2},{\mathcal {F}}^U)\) again boils down to piecewise concatenations of
-
1.
labelit:1 symmetric Riemannian geodesics in \({\mathbb {M}}_{2}\) with metric tensor field \({\mathcal {G}}^U_{{{\textbf {p}}}}({\dot{{{\textbf {p}}}}},{\dot{{{\textbf {p}}}}})\) recall (17), and
-
2.
symmetric Riemannian geodesics in \({\mathbb {M}}_2\) with metric tensor field \({\mathcal {G}}^U_{{{\textbf {p}}}}({\dot{{{\textbf {p}}}}},{\dot{{{\textbf {p}}}}})+(\epsilon ^{-2}-1)|\omega ^{1}_U({\dot{{{\textbf {p}}}}})|^2\) that are in-place rotations, at locations where \({\mathcal {A}}_1^U \approx {\mathcal {A}}_{1}\) if \(0<\varepsilon \ll 1\).
Remark 22
Taking the negative part of the final term in (42) means that we switch between two Riemannian manifolds (one with the final term active and with the final term non-active). At locations where \(\omega ^{3}_U \approx \omega ^3\), for instance at locations where \({\mathcal {A}}_1^U\approx {\mathcal {A}}_1\) this means that one switches between anisotropic geodesics and spherical geodesics (in-place rotations). In the vessel tracking applications we want such in-place rotations to appear above bifurcations in the vasculature.
A closely related situation is discussed in [28, Thm. 4], but now it is applied to the new data-driven model \({\mathcal {F}}^U\) (17) with dual \(({\mathcal {F}}^U)^*=\lim \limits _{\epsilon \downarrow 0} {\mathcal {F}}_{\epsilon }^*\).
By Theorem 1 the Riemannian geodesics have parallel momentum and their transitions toward spherical geodesics is like C continuously differentiable. The surface \({\mathcal {S}}\) where Finslerian geodesics of \({\mathcal {F}}^U\) in \({\mathbb {M}}_{2}\) switch from one Riemannian manifold to the other is given by
Interestingly, in the mixed-model \({\mathcal {F}}^M\) that we will explain later in Sect. 6, the condition in Remark 22 is satisfied at bifurcations. Then in-place rotations are indeed automatically placed at the bifurcations in the tracking of blood vessels, as can be seen in Fig. 16.
6 Experiments
We choose the data-driven left-invariant metric tensor field with forward gear \({\mathcal {F}}^U\) as given in Eq. (17). An elaboration on the calculation of the cost function can be found in Appendix D. We will discuss the new model’s ability to adapt for curvature. Additionally, we show and discuss some full vascular tree tracking results.
6.1 Curvature Adaptation
The data-driven left-invariant metric tensor field \({\mathcal {G}}^U\) and its asymmetric variant \({\mathcal {F}}^U\) both consists of a “standard” left-invariant metric tensor field to which a data-driven term is added, as introduced in (17). The idea of the second data-driven term in this equation is that it pushes the main direction of the model into the direction of the underlying vessel, as illustrated in Fig. 8, where no data-dependent cost function \(C=1\) was used to generate the tracking result. We see that the data-driven left-invariant metric tensor field takes the image data into account and steers the tracking in the direction of the underlying vascular structure, even when the cost function does not contain information about vessel locations and curvature.
The data-driven term also leads to better tracking results of very tortuous vascular structures as we see in Fig. 9. In Fig. 9a, the tracking results relying on (solely) the left-invariant metric tensor field \({\mathcal {F}}\) fail to follow the underlying vessel correctly, contrary to the new data-driven left-invariant model \({\mathcal {F}}^{U}\) (17) which follows the vascular structure correctly. In addition, one sees that when using the left-invariant model, the wave fronts (indicated in orange) suffer from the discretization. In the data-driven left-invariant model, these discretization artifacts are gone, and the wavefronts follow the underlying vascular structure correctly. When only considering 8 orientations, as in Fig. 9b, the data-driven left-invariant frame is still able to follow the vascular structure correctly. Although the discretization is clearly visible in the tracking results, the data-driven left-invariant metric tensor field is still able to follow the vessel correctly. It is important to note that both models use the same cost function. The differences in the tracking results are due to the data-driven left-invariant metric tensor fields’ ability to better adapt for:
-
1.
gradual curvature change of blood vessels. The same applies to other applications such as the detecting of cracks, see Fig. 10,
-
2.
orientation biases by orientation score data- alignment as depicted in Fig. 6.
6.2 Complete Vascular Tree Tracking
In the previous section, we discussed the curvature adaption feature of the new (asymmetric) data-driven left-invariant metric tensor field \({\mathcal {F}}^U\). This model also can automatically place ‘in-place’ rotations in globally optimal geodesics which are typically placed at bifurcations.
However, these valuable abilities of the model may also lead to extremely complex structures to some undesirable behavior. In full vascular tree tracking, we see that the data-driven term may steer the tracking away from the actual vessel at crossings in extreme cases, as can be seen in Fig. 11.
To overcome this problem (see item c in Fig. 11), and to still take advantage of improved data-adaptation (like in Figs. 5, 8 and 9) we introduce a (new) mixed model that prevents this undesirable behavior at (extreme) complex structures, where it locally relies on the old model. Then in between (extreme) complex structures we still benefit from the directional data adaptation in the orientation score.
The mixed metric tensor field \({\mathcal {G}}^M\) (and its asymmetric version \({\mathcal {F}}^M\)) is given by the data-driven left-invariant metric tensor field away from the crossing structures, and by the left-invariant metric tensor field otherwise:
for all \({{\textbf {p}}}=({{\textbf {x}}},{{\textbf {n}}}) \in {\mathbb {M}}_2\), and all \(\hat{{{\textbf {p}}}}=({\dot{{{\textbf {x}}}}},{\dot{{{\textbf {n}}}}}) \in T_{{{\textbf {p}}}}({\mathbb {M}}_2)\), and where \(\kappa ({{\textbf {x}}})= \mathbb {1}_A * G_{\sigma }({{\textbf {x}}})\) with \(A=\cup _{i=1}^N[{{\textbf {x}}}_i-a,{{\textbf {x}}}_i+a]\), where \({{\textbf {x}}}_i\) representing \(N \in {\mathbb {N}}\) crossing locations in the image.
The results are typically not sensitive to the choice of a and \(\sigma \) in our application as long as \(a>2\). Therefore we always set \(a=5\) and \(\sigma = 1\) pixel-size in our experiments.
This construction of the metric tensor field ensures that the metric tensor field is not tempted to move in the wrong direction in extreme cases where vessels cross each other. The tracking result relying on the mixed metric tensor field is visualized in Fig. 11c, and does not show the earlier mentioned undesirable behavior, as shown in Fig. 11b. Therefore, this new model will be used in all full vascular tree tracking results. All results presented in this section are calculated using parameters \(g_{11}=0.01, g_{22}=g_{33}=1\). For the curve optimization this is the same as setting \(\varepsilon =\zeta =0.1\) in (15) used in (17). Even for such extreme anisotropy settings, our numerical algorithm is appropriate as motivated in Sect. 5. We always observed that tracking is stable with respect to small variations in these parameters, so there was no point in fine-tuning them.
6.2.1 Asymmetric Double Step
The tracking results were computed in two steps; first tips are connected to the nearest bifurcation/seed (cost function visualized in Fig. 12), after which those points are connected to the nearest seed (cost function visualized in Fig. 13). The used cost functions (from tip to nearest bifurcation and from bifurcation to seed) support movement along the thin and thick vessels, respectively. The tracking results that correspond to these cost functions are depicted in Fig. 14. The calculated geodesics are all correct, except for 2 difficulties when:
-
1.
crossings and bifurcations are very close to each other,
-
2.
vascular structures are kissing.
Next, we compare the results of the new mixed model \({\mathcal {F}}^M\) and the left-invariant model \({\mathcal {F}}\) in Fig. 15. There are some visible differences between both tracking methods, marked in pink and blue. First, we see that the tracking results relying on the mixed method ensure that the centerline is better followed, and multiple geodesics are at approximately the same place (in blue). Second, we see the ability of the mixed method to adapt to the direction of the vascular structure (in pink). Instead of moving toward a bifurcation point away from the seed in the left-invariant metric tensor field, the curvature adaptation ensures that the tracking results immediately move toward the seed it is connected to.
6.2.2 Asymmetric Single Step with Prior Classification of Seeds and Tips
Common practical setups in vascular tracking of retinal images include the prior knowledge of the locations of tips and seeds of vessel structures. We implemented our data-driven model using a prior classification of the connected tips and seeds. More specifically, in every run of the fast-marching algorithm, one of the seeds is considered together with its corresponding tips, and the connecting vessel structures are tracked. Figure 16 shows our result in this setup and demonstrates that our approach can determine the geodesics that accurately follow the vascular structure in the retinal image.
6.3 Accuracy of the Model
We now present some quantitative evaluations to measure the accuracy of our data-driven metrics for geodesic tracking. We measure the mistake ratio E for the images in the STAR dataset. For these images, the ground truth of the vessels is known, which allows us to calculate the percentage of the vessel that is not on the correct vascular structure, where
We have calculated this accuracy for images of the STAR dataset where we connect the tips to their nearest bifurcation, since one should use the new model away from crossing structures. The results are presented in Fig. 17. We see that for most tracks, the performance improves when switching to the new data-driven model, and in the cases where there is no improvement, the results do not get significantly worse. On average, we find an improvement of 10.7% of the calculated tracks for the considered images.
7 Conclusion and Future Work
In this article, we introduced the concept of a data-driven left-invariant metric tensor field \({\mathcal {G}}^U\) and its asymmetric variant \({\mathcal {F}}^U\). The metric tensor field is defined by the underlying image, where movement along line structures is encouraged by its design in (17). In addition, a data-driven version \(\nabla ^U\) of the plus Cartan connection, relying on \({\mathcal {G}}^U\), was introduced.
We used these geometrical tools to formulate a challenging data-driven version of [43, Thm. 1], which was stated and proved in Theorem 1. In this theorem, ‘straight’ and ‘short’ curves are described with respect to the data-driven Cartan connection. In particular, it describes the entire Hamiltonian flow of the new Riemannian manifold model \(({\mathbb {M}}_{2},{\mathcal {G}}^U)\) in terms of the new data-driven Cartan connection \(\nabla ^U\), and explains the backtracking procedure for backtracking data-driven left-invariant geodesics in \(({\mathbb {M}}_{2},{\mathcal {G}}^U)\). As subsequently explained this can be extended to the asymmetric Finsler model \(({\mathbb {M}}_{2},{\mathcal {F}}^U)\) that often yields the same geodesics, but also automatically places in-place rotations. The latter is beneficial at bifurcations in complex vasculature when using crossing-preserving vesselness costs for the cost function C.
The diagonalization of the new data-driven left-invariant models \({\mathcal {G}}^U\) and \({\mathcal {F}}^U\) provides locally adaptive frames that are beneficial over previous approaches to locally adaptive frames in \({\mathbb {M}}_2\) [37, 55, 67] in the sense that:
-
1.
they coincide with the usual left-invariant frame if the data is locally constant,
-
2.
they are more stable as they are constructed by coercive metric tensor fields, recall (21).
To calculate the minimizing geodesics efficiently, an adaptation to the efficient anisotropic fast-marching algorithm was required and presented in Sect. 5. The metric tensor component matrix was no longer of block form in the fixed coordinate system, and the necessary changes to overcome this have been discussed and analyzed in Sect. 5. We also provide an asymptotic error analysis of our numerical scheme.
To show the performance of the data-driven metric tensor field and the mixed metric tensor field, we have tested them on 2D images of the retina. All experiments confirm that the new model is better able to adapt for curvature. In addition to that, for the tracking of a single vessel, a low number of orientations is sufficient to find the correct minimizing geodesic, as can be seen in Fig. 9. Full vascular tree tracking needs to be handled with care at difficult crossings structures, which is done in the mixed model \({\mathcal {F}}^M\) introduced in (55).
In general, the tracking results perform very well in the discussed two-step approach (see e.g., Figure 15), where tips are first connected to the nearest bifurcation, after which the geodesics connecting these bifurcations to the corresponding seeds are calculated. After prior classification of seeds and tips belonging to the same vascular tree, the tracking results follow the vessels perfectly, recall Fig. 16.
Despite some very appealing theoretical and practical advantages of our model, we still require considerable computation and runtime (tripling the overall processing time) to make the data-driven metric-tensor field and distance maps. Therefore, the exact usage of the proposed data-driven metric depends on the specific context of the tracking requirements.
For future work, it would be interesting to look into the possibilities to train the cost function C using PDE-G-CNNs [68], which is now geometrically computed as explained in Appendix D. In the past, this method had promising results for vessel segmentation. Besides using PDE-G-CNNs to construct the cost function, it would be worth looking into the possibilities to use neural networks to calculate the distance function as was done in [69].Footnote 8
Notes
Since \(\text {Stab}_{\text {SE}(2)}({{\textbf {p}}}_0)=\{{{\textbf {e}}}\}\).
W.r.t. norm induced by the metric tensor field \({\mathcal {G}}\) in Definition 6.
A curve \(\gamma \) satisfying \({\dot{\gamma }}(t)=X_{\gamma (t)}\).
i.e., the cost associated with a velocity at a point is non-Riemannian, non-symmetric, and possibly infinite.
There are two other minor assumptions, the existence of a sub- and super-solution to the scheme, and a perturbation property, which can be established analogously to the Riemannian case in [52, Proposition 2.5].
See A.J. Wemmenhove’s master thesis: https://pure.tue.nl/ws/portalfiles/portal/173216892/Wemmenhove_Jelle.pdf.
References
Bekkers, E.: Retinal Image Analysis Using Sub-Riemannian Geometry in SE(2). PhD thesis, TU Eindhoven (2017)
Weiler, D.L., Engelke, C.B., Moore, A.L., Harrison, W.W.: Arteriole tortuosity associated with diabetic retinopathy and cholesterol. Optom. Vis. Sci. 92(3), 384–391 (2015)
Sasongko, M.B., Wong, T.Y., Nguyen, T.T., Cheung, C.Y., Shaw, J.E., Kawasaki, R., Lamoureux, E.L., Wang, J.J.: Retinal vessel tortuosity and its relation to traditional and novel vascular risk markers in persons with diabetes. Curr. Eye Res. 41(4), 551–557 (2016)
Colligris, P., Perez de Lara, M.J., Colligris, B., Pintor, J.: Ocular manifestations of Alzheimer’s and other neurodegenerative diseases: the prospect of the eye as a tool for the early diagnosis of Alzheimer’s disease. J. Ophthalmol. (2018)
Bekkers, E.J., Zhang, J., Duits, R., ter Haar Romeny, B.M.: Curvature based biomarkers for diabetic retinopathy via exponential curve fits in SE(2). In: Proceedings of the Ophthalmic Medical Image Analysis Second International Workshop, OMIA, pp. 113–120 (2015)
Kalitzeos, A.A., Lip, G.Y.H., Heitmar, R.: Retinal vessel tortuosity measures and their applications. Exp. Eye Res. 106, 40–46 (2013)
Cheung, C., Lamoureux, E., Ikram, M., Sasongko, M., Ding, J., Zheng, Y., Mitchell, P., Wang, J., Wong, T.: Retinal vascular geometry in Asian persons with diabetes and retinopathy. J. Diabetes Sci. Technol. 6(3), 595–605 (2012)
Sasongko, M., Wong, T., Nguyen, T., Cheung, C., Shaw, J., Wang, J.: Retinal vascular tortuosity in persons with diabetes and diabetic retinopathy. Diabetologia 54(9), 2409–2416 (2011)
Chen, D., Cohen, L.D.: A new dynamic minimal path model for tubular structure centerline delineation. In: 2018 24th International Conference on Pattern Recognition (ICPR), pp. 3001–3006 (2018)
Liu, L., Chen, D., Shu, M., Shu, H., Cohen, L.D.: A new tubular structure tracking algorithm based on curvature-penalized perceptual grouping. In: ICASSP 2021–2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2195–2199 (2021)
Liu, L., Chen, D., Cohen, L.D., Shu, H., Pâques, M.: Vessel extraction using crossing-adaptive minimal path model with anisotropic enhancement and curvature constraint. In: 2019 IEEE 16th International Symposium on Biomedical Imaging (ISBI 2019), pp. 20–23 (2019)
Bekkers, E.J., Duits, R., Mashtakov, A., Sanguinetti, G.R.: A PDE approach to data-driven sub-Riemannian geodesics in SE(2). SIAM J. Imag. Sci. 8(4), 2740–2770 (2015)
Cootes, T.F., Taylor, C.J., Cooper, D.H., Graham, J.: Active shape models-their training and application. Comput. Vis. Image Underst. 61(1), 38–59 (1995)
Caselles, V., Kimmel, R., Sapiro, G.: Geodesic active contours. Int. J. Comput. Vision 22, 61–79 (1997)
Cohen, L.D.: Multiple contour finding and perceptual grouping using minimal paths. J. Math. Imaging Vis. 14(3), 225–236 (2001)
Sapiro, G.: Geometric Partial Differential Equations and Image Analysis. Cambridge University Press, Cambridge (2006)
Peyré, G., Péchaud, M., Keriven, R., Cohen, L.D., et al.: Geodesic methods in computer vision and graphics. Found. Trends Comput. Graph. Vis. 5(3–4), 197–397 (2010)
Chen, D., Spencer, J., Mirebeau, J.M., Chen, K., Shu, M., Cohen, L.D.: A generalized asymmetric dual-front model for active contours and image segmentation. IEEE Trans. Image Process. 30, 5056–5071 (2021)
Péchaud, M., Descoteaux, M., Keriven, R.: Brain connectivity using geodesics in HARDI. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 482–489. Springer, Berlin (2009)
Portegies, J., Meesters, S., Ossenblok, P., Fuster, A., Florack, L., Duits, R.: Brain connectivity measures via direct sub-Finslerian front propagation on the 5D sphere bundle of positions and directions. In: Bonet-Carne, E., Grussu, F., Ning, L., Sepehrband, F., Tax, C.M.W. (eds.) Computational Diffusion MRI, pp. 309–321. Springer, Cham (2019)
Chen, D.: New Minimal Paths Models for Tubular Structure Extraction and Image Segmentation. Ph.D. thesis, University Paris-Dauphine (2016)
Benmansour, F., Cohen, L.D.: Tubular structure segmentation based on minimal path method and anisotropic enhancement. Int. J. Comput. Vis. 92(2), 192–210 (2011)
Bekkers, E., Duits, R., Berendschot, T., ter Haar Romeny, B.: A multi-orientation analysis approach to retinal vessel tracking. J. Math. Imaging Vis. 49(3), 583–610 (2014)
Franken, E., Duits, R.: Crossing–preserving coherence-enhancing diffusion on invertible orientation scores. Int. J. Comput. Vis. 85(3), 253 (2009)
Boscain, Ugo, Charlot, Grégoire., Rossi, Francesco: Existence of planar curves minimizing length and curvature. Proc. Steklov Inst. Math. 270, 43–56 (2010)
Duits, R., Boscain, U., Rossi, F., Sachkov, Y.: Association fields via cuspless sub-Riemannian geodesics in SE(2). J. Math. imaging Vis. 49(2), 384–417 (2014)
Bao, D., Chern, S.S., Shen, Z.: An Introduction to Riemann–Finsler Geometry. Springer, New York (2000)
Duits, R., Meesters, S.P., Mirebeau, J.M., Portegies, J.M.: Optimal paths for variants of the 2D and 3D Reeds–Shepp car with applications in image analysis. J. Math. Imaging Vis. 60, 816–848 (2018)
Reeds, J., Shepp, L.: Optimal paths for a car that goes both forwards and backwards. Pac. J. Math. 145(2), 367–393 (1990)
Absil, P.A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2009)
Bekkers, E.J., Chen, D., Portegies, J.M.: Nilpotent approximations of sub-Riemannian distances for fast perceptual grouping of blood vessels in 2D and 3D. J. Math. Imaging Vis. 60, 1–18 (2018)
Chen, D., Mirebeau, J.M., Cohen, L.D.: Vessel tree extraction using radius-lifted keypoints searching scheme and anisotropic fast marching method. J. Algorithms Comput. Technol. 10(4), 224–234 (2016)
Abbasi-Sureshjani, S., Zhang, J., Duits, R., ter Haar Romeny, B.: Retrieving challenging vessel connections in retinal images by line co-occurrence statistics. Biol. Cybern. 111(3), 237–247 (2017)
Mirebeau, J.M.: Fast-marching methods for curvature penalized shortest paths. J. Math. Imaging Vis. 60(6), 784–815 (2018)
Mashtakov, A.: Extremal controls for the duits car. In: Nielsen, F., Barbaresco, F. (eds.) Geometric Science of Information, pp. 73–81. Springer, Cham (2021)
Mirebeau, J.M., Portegies, J.: Hamiltonian fast marching: a numerical solver for anisotropic and non-holonomic Eikonal PDEs. Image Process. Line 9, 47–93 (2019)
Zhang, J., Dashtbozorg, B., Bekkers, E.J., Pluim, J.P., Duits, R., HaarRomeny, BMt.: Robust retinal vessel segmentation via locally adaptive derivative frames in orientation scores. IEEE Trans. Med. Imaging 35(12), 2631–2644 (2016)
Abbasi-Sureshjani, S., Smit-Ockeloen, I., Zhang, J., Ter Haar Romeny, B.: Biologically-inspired supervised vasculature segmentation in SLO retinal fundus images. In: Kamel, M., Campilho, A. (eds.) Image Analysis and Recognition, pp. 325–334. Springer, Cham (2015)
Duits, R.: Perceptual Organization in Image Analysis: A Mathematical Approach Based on Scale, Orientation and Curvature. Ph.D. thesis, Eindhoven University of Technology (2005)
Duits, R., Duits, M., van Almsick, M., ter Haar Romeny, B.: Invertible orientation scores as an application of generalized wavelet theory. Pattern Recognit Image Anal. 17(1), 42–75 (2007)
Duits, R., Franken, E.M.: Left invariant parabolic evolution equations on \({SE}(2)\) and contour enhancement via invertible orientation scores, part I: Linear left-invariant diffusion equations on \({SE}(2)\). Quart. Appl. Math. AMS 68, 255–292 (2010)
Franceschiello, B., Mashtakov, A., Citti, G., Sarti, A.: Geometrical optical illusion via sub-Riemannian geodesics in the roto-translation group. Differ. Geom. Appl. 65, 55–77 (2019)
Duits, R., Smets, B., Wemmenhove, J., Portegies, J., Bekkers, E.: Springer Handbook of Mathematical Imaging 2021, chap. Recent Geometric Flows in Multi-Orientation Image Processing via a Cartan Connection, pp. 1–60. Springer, Berlin (2021)
Kobayashi, S., Nomizu, K.: Foundations of Differential Geometry, vol. 45. Wiley, New York (1963)
Cogliati, A., Mastrolia, P.: Cartan, Schouten and the search for connection. Hist. Math. 45, 39–74 (2017)
Piuze, E., Sporring, J., Siddiqi, K.: Maurer–Cartan forms for fields on surfaces: application to heart fiber geometry. IEEE Trans. Pattern Anal. Mach. Intell. 37(12), 2492–2504 (2015)
Momayyez, P., Siddiqi, K.: 3D stochastic completion fields for fiber tractography. In: 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, pp. 178–185 (2009)
Duits, R., Smets, B.M.N., Wemmenhove, A.J., Portegies, J.W., Bekkers, E.J.: Recent geometric flows in multi-orientation image processing via a Cartan connection. In: Handbook of Mathematical Models and Algorithms in Computer Vision and Imaging: Mathematical Imaging and Vision pp. 1–60 (2021)
Hannink, J., Duits, R., Bekkers, E.: Crossing-preserving multi-scale vesselness. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 603–610. Springer, Berlin (2014)
Chen, D., Cohen, L.D.: Fast asymmetric fronts propagation for image segmentation. J. Math. Imaging Vis. 60(6), 766–783 (2018)
Sethian, J.A.: Fast marching methods. SIAM Rev. 41(2), 199–235 (1999)
Mirebeau, J.M.: Riemannian fast-marching on Cartesian grids, using Voronoi’s first reduction of quadratic forms. SIAM J. Numer. Anal. 57(6), 2608–2655 (2019)
Selling, E.: Ueber die binären und ternären quadratischen formen. Journal für die reine und angewandte Mathematik 77, 143–229 (1874)
Savadjiev, P., Strijkers, G., Bakermans, A., Piuze, E., Zucker, S., Siddiqi, K.: Heart wall myofibers are arranged in minimal surfaces to optimize organ function. PNAS 109(24), 9248–9253 (2012)
Duits, R., Janssen, M.H., Hannink, J., Sanguinetti, G.R.: Locally adaptive frames in the roto-translation group and their applications in medical imaging. J. Math. Imaging Vis. 56(3), 367–402 (2016)
Duits, R., Franken, E.: Left-invariant parabolic evolutions on SE(2) and contour enhancement via invertible orientation scores part II: Nonlinear left-invariant diffusions on invertible orientation scores. Q. Appl. Math. 68(2), 293–331 (2010)
Haar Romeny, B.M.: Front-End Vision and Multi-Scale Image Analysis. Springer, Berlin (2003)
Marsden, J.E., Ratiu, T.S.: Introduction to Mechanics and Symmetry: A Basic Exposition of Classical Mechanical Systems, vol. 17. Springer, Berlin (2013)
Montgomery, R.: A Tour of Subriemannian Geometries, Their Geodesics and Applications, vol. 91. American Mathematical Society, Providence (2002)
Agrachev, A.A., Sachkov, Y.L.: Control Theory from the Geometrical Viewpoint, vol. 87. Springer, Berlin (2004)
Agrachev, A., Barilari, D., Boscain, U.: A Comprehensive Introduction to Sub-Riemannian Geometry. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (2019)
Moiseev, I., Sachkov, Y.L.: Maxwell strata in sub-Riemannian problem on the group of motions of a plane. ESAIM: Control Optim. Calc. Var. 16(2), 380–399 (2010)
Duits, R., Ghosh, A., Dela Haije, T., Mashtakov, A.: On sub-Riemannian geodesics in SE(3) whose spatial projections do not have cusps. J. Dyn. Control Syst. 22(4), 771–805 (2016)
Citti, G., Sarti, A.: A cortical based model of perceptional completion in the roto-translation space. J. Math. Imaging Vis. 24(3), 307–326 (2006)
Sachkov, Y.: Cut locus and optimal synthesis in the sub-Riemannian problem on the group of motions of a plane. ESAIM: Control Optim Calc. Var. 17, 293–321 (2011)
Evans, L.C.: Partial Differential Quations. AMS, Providence (1998)
Smets, B.M., Portegies, J., St-Onge, E., Duits, R.: Total variation and mean curvature PDEs on the homogeneous space of positions and orientations. J. Math. Imaging Vis. 63(2), 237–262 (2021)
Smets, B.M.N., Portegies, J., Bekkers, E.J., Duits , R.: PDE-based group equivariant convolutional neural networks. J. Math. Imaging Vis. 65, 209–239 (2023). https://doi.org/10.1007/s10851-022-01114-x
Lichtenstein, M., Pai, G., Kimmel, R.: Deep eikonal solvers. In: Lellmann, J., Burger, M., Modersitzki, J. (eds.) Scale Space and Variational Methods in Computer Vision, pp. 38–50. Springer, Cham (2019)
Berg, N.J.v.d.: Data-driven left-invariant tracking in Mathematica. https://github.com/NickyvdBerg/DataDrivenTracking (2022)
Frangi, R., Niessen, W., Vincken, K., Viergever, M.: Multiscale vessel enhancement filtering. Med. Image Comput. Comput. Assist. Interv. 1496, 130–137 (2000)
Acknowledgements
We gratefully acknowledge former TU/e master student A.J. Wemmenhove (supervised by R. Duits and B.M.N. Smets) for preliminary investigations in support of Appendix B.
Funding
We gratefully acknowledge the Dutch Foundation of Science NWO for its financial support by Talent Programme VICI 2020 Exact Sciences (Duits, Geometric learning for Image Analysis, VI.C. 202-031).
Author information
Authors and Affiliations
Contributions
NJvdB developed the used model, wrote the first draft of the manuscript, did all the experiments, wrote the code for the experimental section supported by BMNS, J-MM and RD (available via GitHub [70]), and created all figures. She also contributed to important parts of the proof of Theorem 1 (App. B). BMNS proposed the data-driven metric tensor model (beneficial over previous choices of locally adaptive frames in the context of image enhancement [48]) on which the paper is built. He developed Lemma 5, and contributed to Lemma 1. GP acted as co-supervisor of the project, providing relevant input and suggestions to experiments, helped with careful exposition of the results, and structuring of the manuscript. J-MM developed the new anisotropic fast-marching algorithm and theoretical analysis (Lemma 3 and asymptotic expansion in (53)), which is explained in Sect. 5, and provided relevant input on Theorem 1. RD is the supervisor of the project, proposed and build up the underlying theory (Sects. 3 and 4, Theorem 1 & Lemma 6), and polished the manuscript on mathematical details. All authors collaborated closely, wrote parts of the manuscript and reviewed the manuscript. Author contributions per section (in order of appearance): Sect. 1—NJvdB and GP; Sect. 2—NJvdB and RD; Sect. 3—NJvdB, BMNS and RD; Sect. 4—NJvdB and RD; Sect. 5—J-MM and RD; Sect. 6—NJvdB and GP; App. A—NJvdB and RD; App. B—NJvdB and RD; App. C—NJvdB, BMNS and RD; App. D—NJvdB and RD; App. F—NJvdB and J-MM
Corresponding author
Ethics declarations
Competing Interests
R. Duits is a member of the editorial board of JMIV.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A: Proof of Lemma 1
Writing out the definition (28) gives
where the last equality holds since
Similarly, we have for (29)
where the last equality holds since
\(\square \)
Appendix B: Proof of Theorem 1
Firstly, we address the characterization of straight curves. \(\left( \nabla ^{U}\right) _{{\dot{\gamma }}}{\dot{\gamma }}=0 \Leftrightarrow \) \(\ddot{{\tilde{\gamma }}}^k+\sum _{i,j=1}^{n} {c}_{ij}^k(\gamma (t))\dot{{\tilde{\gamma }}}^i\dot{{\tilde{\gamma }}}^j=0\) for \(k=1,\ldots ,n\).
Since \([{\mathcal {A}}_{i}^U,{\mathcal {A}}_j^U]=-[{\mathcal {A}}_j^U,{\mathcal {A}}_i^U]\) due to (25) and (26), we have \({\tilde{c}}_{ij}^k=-{\tilde{c}}_{ji}^k\) and \({\tilde{c}}_{ii}^k=0\).
Consequently, we are left with \(\ddot{{\tilde{\gamma }}}^k=0\Rightarrow \ \dot{{\tilde{\gamma }}}^k-c^k=0\). Summarizing we have
Secondly, we address the characterization of shortest curves. The Pontryagin Maximum Principle is given by (Hamiltonian flow on co-tangent bundle \(T^*(G)\))
For details see [60].
Remark 23
(Liouvilles Theorem) By the chain law, for any smooth function \(f:T^*(G)\rightarrow {\mathbb {R}}\), one has
where \({\mathfrak {h}}\) denotes the Hamiltonian flow, and where \(\nabla _{\gamma }\) and \(\nabla _{\lambda }\) denote the gradient with respect to \(\gamma \) and \(\lambda \), respectively.
The result of Eq. (56) can be expressed in coordinates
The horizontal part is given by
This follows from the computation of the Hamiltonian via the Fenchel transform.
The vertical part is given by
In the above derivation, we have used that
Additionally, it is important to note that
since \({\mathcal {A}}_k^U{\tilde{\lambda }}_i=0\). Consequently, we find
since the Hamiltonian is constant. So in total we have
This is equivalent to
Remark 24
(Justification of Eq. (58)) We have Lagrangian
From this expression, we can determine the Hamiltonian \({\mathfrak {h}}\):
The maximum is calculated by taking the derivative w.r.t. v:
where
Consequently, we find \({\tilde{\lambda }}^i=v_{\max }^i\) for \(i=1,\ldots ,n\), and the Hamiltonian is given by
Hence, we also have found that \({\tilde{\lambda }}_i=\dot{{\tilde{\gamma }}}_i\) and \({\tilde{\lambda }}^i=\dot{{\tilde{\gamma }}}^i\), which we aimed to show. Note that reformulation in a coordinate-free matter yields
for all \(t \in [0,W({{\textbf {g}}})]\).
Remark 25
In Theorem 1 we give a backtracking formulation (where geodesics go ‘down-hill’ to the origin via steepest descent) where we rescaled time back to the interval \(t \in [0,1]\) (as this is more practical). Similar to [28, Thm. 4, Eq. 28] this is done as follows: in the ODE backtracking for geodesics (37) we included an extra negative scaling factor \(-W({{\textbf {g}}})\) in comparison with all the canonical ODEs above.
Thirdly, we address the symmetry (36) of the data-driven Cartan connection.
By construction of (17) and (28), we have the correct symmetry (36). Indeed from (17), it follows that
and via (28) we get \((L_{{{\textbf {g}}}})^* \left( \nabla ^{{\mathcal {L}}_{{{\textbf {g}}}}U}\right) ^*= (\nabla ^U)^*\), where we use the fact that \({\mathcal {G}}^U\) is diagonal w.r.t. basis \(\{{\mathcal {A}}_i^U\}\) and where we, respectively, applied the pushforward of a vector field, the pullback of a covector field, and the pullback of a dual connection.
Remark 26
In general the pullback \(\Phi ^* \nabla ^*\) of a dual connection \(\nabla ^*\) on manifold G under a smooth mapping \(\Phi : G \rightarrow G\) is given by \((\Phi ^* \nabla ^*_X)(\Phi ^* \lambda )=\Phi ^*(\nabla ^*_{\Phi _* X}\; \lambda )\) with \(\lambda \in T^*(G)\) and \(X \in T(G)\).
Finally, we address the integration of geodesics and their symmetry. Eq. (37) follows by (35). Here \(\lambda =\text {d}W\) implies we must indeed set the following momentum components:
Furthermore in (35) we invert the data-driven left-invariant metric tensor field \({\mathcal {G}}^U\) (recall Eq. (20)) and express the velocities as \(\dot{{\tilde{\gamma }}}^{k}= g_{kk}^{-1} \lambda _k = g^{kk} \lambda _k\). Then via Remark 18 we obtain that the geodesics indeed follow by integration of the vector field v(W) on G. Clearly, this vector field is data-driven left-invariant (as all the vector fields \({\mathcal {A}}_{i}^U\) are) and thereby one has:
for all \({{\textbf {q}}},{{\textbf {g}}},{{\textbf {g}}}_0 \in G\), \(t \in [0,1]\), from which the symmetry (39) follows by integration. \(\square \)
Appendix C: The Used Metric Tensor Field is Indeed a Data-Driven Left-Invariant Metric Tensor Field
We first rely on a convenient standard formula of the Hessian of smooth function on a manifold relative to a connection on that manifold in Lemma 4. Then we provide an alternative formulation of such a Hessian in Lemma 5 (via the notion of parallel transport).
Finally, we prove that \(\mathcal {G}^U\), that heavily relies (17) on a Hessian HU of a sufficiently smooth orientation score \(U:\text {SE}(2)\rightarrow {\mathbb {R}}\), is indeed a data-driven left-invariant vector field in Lemma 6.
Lemma 4
The Hessian \(HU=\nabla ^* \textrm{d}U\) of a smooth function \(U: M \rightarrow {\mathbb {R}}\) relative to connection \(\nabla \) on manifold M satisfies
Proof
One can easily see that
\(\square \)
Remark 27
(Alternative Formulation Hessian) Let M be a smooth manifold with connection \(\nabla \). Let \({{\textbf {p}}}\in M\) and \(X_{{\textbf {p}}},Y_{{\textbf {p}}}\in T_{{\textbf {p}}}(M)\), i.e., two tangent vectors not necessarily associated to a vector field. Let \(f\in C^\infty (M,{\mathbb {R}})\).
Let \(\mathcal {X}:[-\delta ,\delta ]\rightarrow M\), with \(\delta >0\), such that
i.e., \(\mathcal {X}\) is the unique auto-parallel curve through \({{\textbf {p}}}\) with tangent vector \(X_{{\textbf {p}}}\). For all \(s,t\in [-\delta ,\delta ]\) let \(P_{s,t}^\mathcal {X}: T_{\mathcal {X}(s)}M\rightarrow T_{\mathcal {X}(t)}M\) be the parallel transport operator along the curve \(\mathcal {X}\), which is uniquely defined by the following properties
-
1.
\(P_{t,t}^\mathcal {X}=id\quad \forall t\in [-\delta ,\delta ]\),
-
2.
\(P_{t_2,t_3}^\mathcal {X}\circ P_{t_1,t_2}^\mathcal {X}=P_{t_1,t_3}^\mathcal {X}, \quad \forall t_1,t_2,t_3\in [-\delta ,\delta ]\),
-
3.
smooth with respect to \(\mathcal {X}\), t and s.
Then \(t\mapsto P_{0,t}^\mathcal {X} Y_{{\textbf {p}}}\in T_{\gamma (t)}M\) gives a smooth vector field along the curve \(\mathcal {X}\) that is unique parallel transport of \(Y_{{\textbf {p}}}\) along that curve, i.e., with the property \(\nabla _{\dot{\mathcal {X}}(t)}\left( P_{0,\cdot }^\mathcal {X} Y_{{\textbf {p}}}\right) =0\).
Lemma 5
We can now define the Hessian of a (sufficiently) smooth function \(f:M \rightarrow {\mathbb {R}}\) also as follows
Proof
If X and Y are smooth vector fields then
Note that \(\lim _{t\rightarrow 0} P_{t,0}^\mathcal {X}=id\), so
Now, we have
which is the same as Eq. (60). \(\square \)
Lemma 6
The metric tensor field \(\mathcal {G}^U\) introduced in Eq. (17) is a data-driven left-invariant metric tensor field.
Proof
We recall that the dual norm used in the definition of the data-driven metric tensor field \(\mathcal {G}^U\) is given by
In order to prove that \(\mathcal {G}^U\) is a data-driven left invariant metric tensor field, we need the following identities:
where (63) is the definition of the pushforward, and (64) is the equivariance of the Cartan connection \(\nabla =\nabla ^{U=1}\). In addition, it is important that
so \(\Vert Y\Vert =\Vert \tilde{Y}\Vert \), where \(Y\in T_{{\textbf {p}}}(\mathbb {M}_2)\) and \(\tilde{Y}\in T_{{{\textbf {g}}}{{\textbf {p}}}}(\mathbb {M}_2)\).
We check the data-driven left invariance for the separate terms of the metric tensor field, starting with \(\mathcal {G}_{{\textbf {p}}}(\dot{{{\textbf {p}}}},\dot{{{\textbf {p}}}})\):
Then, we study the data-driven left invariance of the term
which is satisfied since (set \(\tilde{Y}=(L_{{\textbf {g}}})_* Y\))
Note that since \(\Vert HU|_{{\textbf {p}}}(\dot{{{\textbf {p}}}},\cdot )\Vert _*^2\) satisfies the data-driven left-invariant property, we also have
Thereby, \(\mathcal {G}^U\) is data-driven left-invariant:
\(\square \)
Appendix D: Cost Function C: A Multi-scale Crossing-Preserving Vesselness Filter Variant
The differentiable cost function \(C:\mathbb {M}_2\rightarrow [\delta ,1]\) is an important tool used to encode where vascular structures are located. Costs are high (“1”) outside the blood vessels, and low (\(\delta \) given in experiments) at the center of the blood vessels, stimulating the geodesic to move along the vascular structure. Many approaches to automatically calculate the vessel locations have been proposed over the years [12, 37, 49]. In the calculation of the tracking results, we use a cost function inspired by [49]. The precise relation between the cost and the vesselness filter follows later in (67). The vesselness expression \(\mathcal {V}^{\text {SE}(2)}(U_f^a):\text {SE}(2)\rightarrow \mathbb {R}^+\) is, as in [49, 71]
where \(U_f^a({{\textbf {x}}},\theta )\), \(a>0\) fixed, is a single layer of a multilayer wavelet transform. In all experiments, we set \(\sigma _1=0.5\) and \(\sigma _2=0.5\left\| \mathcal {S}\right\| _\infty \). In (66), the anisotropy measure \(\mathcal {R}\), structure measure \(\mathcal {S}\) and convexity criterion \(\mathcal {Q}\) are given by
where \(\mathcal {A}_{i}^2 U_f^a:=\mathcal {A}_i\mathcal {A}_i U_f^a\), and where the superscripts \(^{s,\beta }\) denote Gaussian derivatives at spatial scale \(s=0.5\sigma _s^2\) and angular scale \(0.5\beta ^2\), where \(\beta =0.75\), and where the superscripts \(^{\sigma _{s,Ext},\sigma _{a,Ext}}\) denote external regularization with spatial scale \(\sigma _{s,Ext}=\sigma _s=a\) and angular scale \(\sigma _{a,Ext}\).
Here, we implement the dual norm \(\Vert HU|_{{\textbf {p}}}(\dot{{{\textbf {p}}}},\cdot )\Vert _*^2\) is computed by (19) using Gaussian derivatives with scales \(\sigma _{s,Ext}\) and \(\sigma _{a,Ext}\).
Last, we apply erosion with scale \(s_e\) on \(\mathcal {V}^{\text {SE}(2)}\), denoting the result by \(\mathcal {V}_{s_e}^{\text {SE}(2)}\). Then, the cost function \(C:\text {SE}(2)\rightarrow \mathbb {R}^+\) is defined as (similar to [12])
where \(N_s\) denotes the number of scales, and \(a_l\) denotes the different scales that are considered. The scaling parameter \(\mu _\infty \) is defined as \(\mu _\infty :=\left\| \sum _{l=1}^{N_s}\mathcal {V}_{s_2}^{\text {SE}(2)}\left( U_f^{a_l}\right) \right\| _\infty \). In all experiments, the values of parameters \(\sigma _{a,Ext}\), \(\lambda \ge 0\) and \(p>0\) are chosen to be 0, 1000 and 2, respectively. In Fig. 18, a cost function constructed by the above formulation is visualized. Here, the vertical structures at bifurcations allow for in-place rotations, as depicted in Fig. 19.
Appendix E: Adaptation to Asymmetric Data-Driven Finsler Functions
A generalization of [28, Thm. 1, 2, 4] to go from the symmetric model \((\mathbb {M}_2,\mathcal {G}^U)\) to the asymmetric model \((\mathbb {M}_2,\mathcal {F}^U)\), means in practice that we have to adapt the Eikonal equation (38) to
where \((x)_+=\max \{x,0\}\), and backtracking (40) to
This adapted model does work reasonably well in practice. However, cusps may still occur in projected geodesics of this adopted model since the required (‘no reverse gear’) condition
differs from the actually applied condition \(\dot{\tilde{\gamma }}^1\ge 0\). If the angle between \(\left. \mathcal {A}_1^U\right| _{\tilde{\gamma }}\) and \(\left. \mathcal {A}_1\right| _{\tilde{\gamma }}\) is not too large (which is often the case when geodesics pass locations with low cost), projected geodesics usually do not exhibit cusps.
A much less obvious and more precise solution—that does exclude cusps altogether—in spatially projected data-driven geodesics, is given in Lemma 3 in the Numerical Section with computational scheme (52) and backtracking (54).
Essentially, in this approach (used in our experiments!) one takes the positive part of \(\langle M^{-1}(\omega _U^1-\alpha \omega _U^2)|_{\tilde{\gamma }},\dot{\tilde{\gamma }}\rangle \) to ensure (68), rather than taking the positive part of \(\dot{\tilde{\gamma }}^1=\langle \omega _U^1|_{\tilde{\gamma }},\dot{\tilde{\gamma }}\rangle \).
If U is constant, then \(\alpha =0\), \(\omega ^{1}_U=\omega ^1\) and then we have \(\dot{\tilde{\gamma }}^1=\dot{\gamma }^1\ge 0\), thereby if U is constant we indeed end up in the standard Reeds–Shepp car model without reverse gear [28].
Appendix F: Proof of Lemma 3
Only in this proof we briefly write \(\omega ^i:=\omega ^i_U\) for \(i=1,2,3\).
Let P be a \(3\times k\) matrix of rank k (\(1\le k\le 3\)). Then, by the Woodbury formula, one has
which is up to \({{\mathcal {O}}}(\epsilon ^2)\) error equal to the orthogonal projection \(\text {Id}_3-P(P^TP)P^T\) onto \({{\,\textrm{Span}\,}}(P)^\perp \). Calculating the expression for \(D_\epsilon \) by Woodbury formula and Taylor expansion gives:
where \(P:=(M^0)^{-1/2}{\tilde{P}}\) and \({\tilde{P}}=\begin{bmatrix}\omega ^1&\omega ^2\end{bmatrix}\). Noticing \(\text {Span}\{P\}^\perp =\text {Span}\{{\tilde{\omega }}\}\), with \({\tilde{\omega }}:=(\sqrt{M^0}^{-1}\omega ^1)\times (\sqrt{M^0}^{-1}\omega ^2)\), one has
Simplification yields \(D=\frac{\omega \omega ^\top }{\omega ^\top M^0\omega }+{{\mathcal {O}}}(\epsilon ^2),\) with \(\omega :=\omega ^1\times \omega ^2\) as stated in (48).
Likewise, via Lemma 2, the Woodbury formula, and applying a Taylor expansion, we obtain that
where \({\tilde{\omega }}^2:=(M^0)^{-1/2}\omega ^2\) and
is up to \({{\mathcal {O}}}(\epsilon ^2)\) error the orthogonal projection onto \({{\,\textrm{Span}\,}}\{(M^0)^{-1/2}\omega ^2\}^\perp \). The further simplification of
boils down to (49). \(\square \)
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
van den Berg, N.J., Smets, B.M.N., Pai, G. et al. Geodesic Tracking via New Data-Driven Connections of Cartan Type for Vascular Tree Tracking. J Math Imaging Vis 66, 198–230 (2024). https://doi.org/10.1007/s10851-023-01170-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-023-01170-x