Abstract
To model association fields that underly perceptional organization (gestalt) in psychophysics we consider the problem P curve of minimizing \(\int _{0}^{\ell} \sqrt{\xi^{2} +\kappa^{2}(s)} {\rm d}s \) for a planar curve having fixed initial and final positions and directions. Here κ(s) is the curvature of the curve with free total length ℓ. This problem comes from a model of geometry of vision due to Petitot (in J. Physiol. Paris 97:265–309, 2003; Math. Inf. Sci. Humaines 145:5–101, 1999), and Citti & Sarti (in J. Math. Imaging Vis. 24(3):307–326, 2006). In previous work we proved that the range \(\mathcal{R} \subset\mathrm{SE}(2)\) of the exponential map of the underlying geometric problem formulated on SE(2) consists of precisely those end-conditions (x fin,y fin,θ fin) that can be connected by a globally minimizing geodesic starting at the origin (x in,y in,θ in)=(0,0,0). From the applied imaging point of view it is relevant to analyze the sub-Riemannian geodesics and \(\mathcal{R}\) in detail. In this article we
-
show that \(\mathcal{R}\) is contained in half space x≥0 and (0,y fin)≠(0,0) is reached with angle π,
-
show that the boundary \(\partial\mathcal{R}\) consists of endpoints of minimizers either starting or ending in a cusp,
-
analyze and plot the cones of reachable angles θ fin per spatial endpoint (x fin,y fin),
-
relate the endings of association fields to \(\partial\mathcal {R}\) and compute the length towards a cusp,
-
analyze the exponential map both with the common arc-length parametrization t in the sub-Riemannian manifold \((\mathrm{SE}(2),\mathrm{Ker}(-\sin\theta{\rm d}x +\cos\theta {\rm d}y), \mathcal{G}_{\xi}:=\xi^{2}(\cos\theta{\rm d}x+ \sin\theta {\rm d}y) \otimes(\cos\theta{\rm d}x+ \sin\theta{\rm d}y) + {\rm d}\theta \otimes{\rm d}\theta)\) and with spatial arc-length parametrization s in the plane \(\mathbb{R}^{2}\). Surprisingly, s-parametrization simplifies the exponential map, the curvature formulas, the cusp-surface, and the boundary value problem,
-
present a novel efficient algorithm solving the boundary value problem,
-
show that sub-Riemannian geodesics solve Petitot’s circle bundle model (cf. Petitot in J. Physiol. Paris 97:265–309, [2003]),
-
show a clear similarity with association field lines and sub-Riemannian geodesics.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Curve optimization plays a major role both in imaging and visual perception. In imaging there exist many works on snakes and active contour modeling, whereas in visual perception illusionary contours arise in various optical illusions [48, 52]. Mostly, these optimal curve models rely on Euler’s elastica curves [33] (minimizing \(\int(\kappa ^{2}+ \xi^{2}) {\rm d}s\)) to obtain extensions where typically external forces to the data are included, cf. [5, 18, 21, 60, 61].
The elastica problem suffers from the well-known fact that not every stationary curve is a global minimizer, e.g. many local minimizers exist, cf. Fig. 1. Stationarity of a curve can be reasonably checked by the visual system using local perturbations, whereas checking for (global) optimality [54, 66] is much more difficult. Some visual illusions (e.g. the Kanisza triangle) involve corners requiring abrupt resetting of initial and ending conditions, which are difficult to explain in the elastica model. Another problem with elastica is that it is very hard to solve the boundary value problem analytically [4, 6] (due to a highly non-linear ODE for curvature [48]) and this requires efficient numerical 3D shooting schemes.
On top of that elastica curves relate to modes of the direction process (for contour-completion [24]) where the direction of an oriented random walker is deterministic and its orientation is random. Such deterministic propagation only makes sense when the initial orientation is sharply defined. Instead Brownian motion with random behavior both in spatial propagation direction and in orientation direction [1, 22, 25], relates to hypo-elliptic diffusion on the planar roto-translation group. Such a Brownian motion models contour enhancement [25] rather than contour completion [24], see [28] for a short overview. The corresponding Brownian bridge measures [27, 67] (relating to so-called completion fields in imaging [4, 24, 63, 64]) tend to concentrate towards optimal sub-Riemannian geodesics [12, 15, 22, 26, 47, 56]. So both elastica curves and sub-Riemannian geodesics relate to two different fundamental left-invariant stochastic processes [28] on sub-Riemannian manifolds on the 2D-Euclidean motion group SE(2), (respectively to the direction process [24, 48] and to hypo-elliptic Brownian motion [1, 22, 25]).
In short, advantages of the sub-Riemannian geodesic model over the elastica model are:
-
Every cuspless sub-Riemannian geodesic (stationary curve) is a global minimizer [15, 16].
-
The Euler-Lagrange ODE for normalized curvature \(z=\kappa/\sqrt {\kappa^{2}+\xi^{2}}\) can be reduced to a linear one.
-
The boundary value problem can be tackled via effective analytic techniques.
-
The locations where global optimality is lost can be derived explicitly.
-
Sub-Riemannian geodesics are parametrization independent in the roto-translation group SE(2), which is encoded via a pinwheel structure of cortical columns in the primary visual cortex [50, 51].
However, the practical drawback of sub-Riemannian geodesics compared to elastica is that their spatial projections may exhibit cusps and it is hard to analyze when such a cusp occurs. See Fig. 2. Therefore, in this article we provide a complete analysis of such sub-Riemannian geodesics, their parametrization, solving the boundary value problem, and we show precisely when a cusp occurs. See Fig. 3.
A variant of the sub-Riemannian problem that ensures avoiding cusps is the following variational problem, here formulated on the plane:
- P :
-
Fix ξ>0 and boundary conditions \(g_{in}=(x_{in},y_{in},\theta _{in}), g_{fin}=(x_{fin},y_{fin},\theta_{fin})\in\mathbb{R}^{2}\times S^{1}\). On the space of (regular enough) planar curves, parameterized by planar arclength s>0, we aim to find the solutions of:
$$\begin{aligned} &\mathbf{x}(0)=(x_{in},y_{in}),\quad\quad\mathbf{x}(\ell )=(x_{fin},y_{fin}) , \\ &\dot{\mathbf{x}}(0)=(\cos(\theta_{in}), \sin(\theta_{in})) , \end{aligned}$$(1)$$\begin{aligned} &\dot{\mathbf{x}}(\ell)=(\cos(\theta_{fin}), \sin(\theta _{fin})), \\ & \int_0^\ell\sqrt{\xi^2+(\kappa (s))^2}~ds\to\min~~(\mbox{with $\ell$ free}). \end{aligned}$$(2)
Here \(\kappa(s)=\frac{\dot{x}(s) \ddot{y}(s)-\dot{y}(s)\ddot{x}(s)}{(|\dot{x}(s)|^{2}+|\dot{y}(s)|^{2})^{3/2}}\) is the geodesic curvature of the planar curve x(⋅)=(x(⋅),y(⋅))T.
This variational problem was studied as a possible model of the mechanism used by the visual cortex V1 to reconstruct curves which are partially hidden or corrupted. This model was initially due to Petitot (see [50, 51] and references therein). Subsequently, the sub-Riemannian structure was introduced in the problem by Petitot [52] for the contact geometry of the fiber bundle of the 1-jets of curves in the plane (the polarized Heisenberg group), whereas Citti and Sarti [22] introduced the sub-Riemannian structure in SE(2) in problem P. The group of planar rotations and translations SE(2) is the true symmetry group underlying problem P. Therefore, we build on the SE(2) sub-Riemannian viewpoint first proposed by Citti and Sarti [22], and we solve their cortical model for all appropriate end-conditions. The stationary curves of problem P were derived by the authors of this paper in [12, 26]. The problem was also studied by Hladky and Pauls in [40], and by Ben-Yosef and Ben-Shahar in [11].
In this article we will show that the model coincidesFootnote 1 with the circle bundle model by Petitot [52] and that its minimizers correspond to spatial projections of cuspless sub-Riemannian geodesics within \(\mathbb {R}^{2}\rtimes S^{1}\).
Remark 1.1
Problem P is well-posed if and only if,Footnote 2
where \(R_{\theta_{in}}\) denotes the counterclockwise rotation over θ in in the spatial plane and where \(\mathcal{R}\) is a particular subset \(\mathbb{R}^{2} \times S^{1}\) (equal to the range of the underlying exponential map of P curve which we will define and derive later in this article), cf. [15, 16].
We will see in the following that this set \(\mathcal{R}\) is the set of all endpoints in \(\mathbb{R}^{2} \times S^{1}\) that can be connected with a cuspless stationary curve of problem P, starting from (0,0,0).
Remark 1.2
The physical dimension of parameter ξ is [Length]−1. From a physical point of view it is crucial to make the energy integrand dimensionally consistent. However, the problem with (x(0),θ(0))=(0,0,0) and ξ>0 is equivalent up to a scaling to the problem with ξ=1: The minimizer x of P with ξ>0 and boundary conditions (0,0) and (x 1,θ 1) relates to the minimizer \(\overline{\mathbf{x}}\) of P with ξ=1 and boundary conditions (0,0) and (ξ x 1,θ 1), by spatial re-scaling: \(\mathbf{x}(s)=\xi^{-1} \overline{\mathbf{x}}(s)\). Therefore, in the remainder of this article we just consider the case ξ=1 for simplicity.
It is not straightforward to derive the exact Euler-Lagrange equations together with a necessary geometric study of the set of all possible solution curves. The exact solutions to the problem can be derived using 3 types of techniques:
-
1.
Direct derivation of the Euler-Lagrange equation. E.g. the approach by Mumford [48], yielding a direct approach to the ODE for the curvature, see Appendix A.
-
2.
The Pontryagin Maximum principle: A geometrical control theory approach based on Hamiltonians, cf. [3, 12, 47, 53] and Appendix D.
-
3.
The Bryant and Griffith’s approach (based on the works by Marsen-Weinstein on reduction in theoretical mechanics [44]) using a symplectic differential geometrical approach based on Lagrangians [26, App. A], cf. [19].
In this article we will apply all three techniques as they are complementary. Furthermore, we aim to provide a complete overview on the surprisingly tedious problem (many inaccurate and/or incomplete results on the stationary curves have appeared in the mathematical imaging literature). Finally, we want to connect remarkably different approaches in previous works [11, 14, 22, 26, 47, 58] on the topic.
The first approach very efficiently produces only the Euler-Lagrange equation for the curvature of stationary curves, but lacks integration of a single curve and lacks a geometric study of the continuum of all stationary curves that arise by varying the possible boundary conditions.
The second approach includes profound geometrical understanding from a Hamiltonian point of view and deals with local optimality [3] of stationary curves.
The third approachFootnote 3 takes a Lagrangian point of view and provides additional differential geometrical tools from theoretical mechanics that help integrating and structuring the canonical equations. These additional techniques will be of use in deriving semi-analytic solutions to the boundary value problem and in the modeling of association fields.
All three approaches provide, among other results, the following linear hyperbolic ODE
for normalized curvature
where s denotes spatial arc-length and κ(s) denotes curvature of the spatial part r↦x(r) of a geodesic \(\gamma=(\mathbf{x},\theta):[0,\ell] \to\mathbb{R}^{2}\rtimes S^{1}\), with \(\theta(s)=\operatorname{arg}(\dot{x}(s)+i\dot{y}(s))\). Such geodesics are globally minimizing, cf. [15, 16] and Theorem 1 below). Furthermore,
denotes sub-Riemannian arclength t as a function of s along a sub-Riemannian geodesic. Recall that spatial arclength s and sub-Riemannian arclength t are respectively determined by
As a particular case of Eq. (6), the total sub-Riemannian arc-length T of the lifted curve s↦γ=(x(s),θ(s)) with \(\theta(s)=\arg(\dot{x}(x)+i \, \dot {y}(s))\), relates to the total length ℓ of the spatial curve s↦x(s) via T=t(ℓ).
Firstly, application of Mumford’s approach for deriving the ODE for curvature of elastica, to problem P is relatively straightforward, see Appendix A, but does not explicitly involve geometrical control and the Frenet formula still needs to be integrated.
Secondly, in our previous work [16] we considered an extended mechanical problem P MEC related to P. This problem P MEC will soon be explained in detail in Sect. 1.1, and is completely solved by Sachkov et al. in [47, 55, 56]. Application of the Pontryagin maximum principle to this related problem P MEC (after squaring the Lagrangian and constraining the total time to a fixedFootnote 4 T) yields for ξ=1 the maximized HamiltonianFootnote 5
with momentum \(p=p_{1} {\rm d}\theta+p_{2}{\rm d}x +p_{3} {\rm d}y \) and the induced canonical equations
which via re-parametrization of cylinder \(H(p)=\frac{1}{2}\)
produces the mathematical pendulum ODE
For details on the involved computation see [16, 47].
Thirdly, application of the Bryant and Griffith’s (Lagrangian) approach to problem P will yield a canonical Pfaffian system on an extended manifold whose elements involve both position, orientation, control (curvature and length), spatial momentum and angular momentum. We will show that the essential part of this Pfaffian system is equivalent to \(\nabla_{\dot{\gamma}} p = 0\) where ∇ denotes a Cartan connection and p denotes momentum as a co-vector within \(T^{*}(\mathbb {R}^{2}\rtimes S^{1})\). This fundamental identity allows us to analytically solve the boundary value problem.
1.1 Lift problem \(\bf{P}\) to the roto-translation group
Problem \(\bf{P}\) relates to two different geometric control problems (P curve and P MEC):
-
- P curve::
-
Fix ξ>0 and boundary conditions \((x_{in},y_{in},\theta _{in}), (x_{fin},y_{fin},\theta_{fin})\in\mathbb{R}^{2}\times S^{1}\), with (x in ,y in )≠(x fin ,y fin ). In the space of integrable (possibly non-smooth) controls \(v(\cdot ):[0,\ell]\to\mathbb{R}\), we aim to solve:
$$\begin{aligned} &(x(0),y(0),\theta(0))=(x_{in},y_{in},\theta_{in}), \\ &(x(\ell ),y(\ell),\theta(\ell))=(x_{fin},y_{fin},\theta_{fin}), \\ & \left( \begin{array}{c} \frac{dx}{ds}(s)\\ \frac{dy}{ds}(s)\\ \frac{d\theta }{ds}(s) \end{array} \right)=\left( \begin{array}{c} \cos(\theta(s)) \\ \sin(\theta(s)) \\ 0 \end{array} \right)+v(s) \left( \begin{array}{c} 0\\ 0\\ 1 \end{array} \right), \\ & \int_0^\ell\sqrt{\xi^2 + \kappa(s)^2}~{\rm d}s= \int_0^\ell\sqrt{\xi^2 + v(s)^2}{\rm d}s\\ &\quad\to\min\quad (\mbox{here } \ell\geq0 \mbox{ is free}) \end{aligned}$$(11)
Since in this problem we are taking v(⋅)∈L 1([0,ℓ]), the curve \(\gamma=(x(\cdot),y(\cdot),\theta(\cdot)):[0,\ell]\to \mathbb{R} ^{2}\times S^{1}\) is absolutely continuous and curve \(\mathbf{x}=(x(\cdot ),y(\cdot)):[0,\ell]\to\mathbb{R}^{2}\) is in Sobolev space \(W^{2,1}([0,\ell],\mathbb{R}^{2})\).
-
- P MEC::
-
Fix ξ>0 and boundary conditions \((x_{in},y_{in},\theta _{in}), (x_{fin},y_{fin},\theta_{fin})\in\mathbb{R}^{2}\times S^{1}\). In the space of L ∞ controls \(\tilde{u}(\cdot),\tilde {v}(\cdot):[0,\ell]\to\mathbb{R}\), solve:
$$\begin{aligned} &(x(0),y(0),\theta(0))=(x_{in},y_{in},\theta_{in}), \\ &(x(T),y(T),\theta(T))=(x_{fin},y_{fin},\theta_{fin}) , \\ & \left( \begin{array}{c} \frac{dx}{dt}(t)\\ \frac{dy}{dt}(t)\\ \frac{d\theta }{dt}(t) \end{array} \right)=\tilde{u}(t) \left( \begin{array}{c} \cos(\theta(t)) \\ \sin(\theta(t)) \\ 0 \end{array} \right)+\tilde{v}(t) \left( \begin{array}{c} 0\\ 0\\ 1 \end{array} \right) \\ & \int_0^T\sqrt{\xi^2\tilde {u}(t)^2+\tilde{v}(t)^2}~{\rm d}t \\ &\quad \to\min\quad (\mbox{here } T\geq0 \mbox{ is free}) \end{aligned}$$(12)
Problem P MEC has a solution by Chow’s and Fillipov’s theorems [3] regardless the choice of end-condition and has been completely solved in a series of papers by one of the authors (see [47, 55, 56]). It gives rise to a sub-Riemannian distance on the sub-Riemannian manifold within SE(2) as we will explain next.
The space \(\mathbb{R}^{2}\times S^{1}\) can be equipped with a natural group product
where R θ denotes a counter-clockwise rotation over angle θ∈(−π,π] and with x=(x,y)T and x′=(x′,y′)T so that it becomes isomorphic to the 2D (special) Euclidean motion group consisting of rotations and translations in the plane, also known as roto-translation group, and commonly denoted by SE(2). As SE(2) acts transitive and free on the set of positions and orientations \(\mathbb{R}^{2}\times S^{1}\) we can identify point on orbits (x,y,θ) starting from the unity (0,0,0) with the corresponding group elements (x,y,R θ ). Therefore we write \(\mathbb{R}^{2}\rtimes S^{1} \equiv\mathrm{SE}(2)\) to stress that the set \(\mathbb{R}^{2}\times S^{1}\) is equipped with a (semi-direct) group product (13). Now both problems P curve and P MEC are invariant with respect to rotations and translations so we may as well set (x in ,y in ,θ in )=(0,0,0). Indeed, given a problem with general boundary conditions (x in ,y in ,θ in ) and (x fin ,y fin ,θ fin ), its minimizer γ opt (when it exists) is \((x_{in},y_{in},\theta_{in}) \cdot\tilde{\gamma}_{opt}\), where \(\tilde{\gamma}_{opt}\) is the minimizer from (0,0,0) to
Throughout this article we use the following notation for the moving frame \(\{\mathcal{A}_{1},\mathcal{A}_{2},\mathcal{A}_{3}\}\) of left-invariant vector fields
where on the right we consider vector fields as differential operators, for details on such identification see e.g. [3, 7]. The corresponding co-frame of left-invariant dual basis vectors will be denoted by
where frame and dual frame relate via
where in the righthand side we have the Kronecker symbols \(\delta ^{i}_{j}=1\) if i=j and 0 else. Problem P MEC can now be reformulated as the computation of
where d denotes the sub-Riemannian distanceFootnote 6 on the sub-Riemannian manifold
with sub-Riemannian metric tensor
Remark 1.3
The sub-Riemannian structure is 3D contact and analytic and therefore we have non-existence of abnormal extrema and all minimizers are analytic, where we note that distribution Δ is 2-generating cf.[3, Chap. 20.5.1].
Problem P MEC is to be considered as an auxiliary mechanical problem (of optimal path planning of a moving car carrying a steering wheel and the ability to drive both forwardly and backwardly) associated to P curve. To this end we stress that P MEC cannot be interpreted as a problem of reconstruction of planar curves, [14]. The problem is that the minimizing curve γ=(x,θ):[0,T]→SE(2) may have a vertical tangent vector (i.e. in θ-direction) in between the ending conditions, which causes a cusp in the corresponding projected curve t↦x(t) in the plane, see Fig. 2. Such a cusp corresponds to a point on an optimal path where the car is suddenly set in reverse gear.
Problem P MEC is invariant under monotonic re-parameterizations and at a cusp spatial arc-length parametrization breaks down. If \((x_{fin},y_{fin},\theta_{fin}) \in\mathcal{R}\) no such cusps arise and P MEC and P curve are equivalent [15, 16] and we can use arclength parametrization also in P MEC (in which case the first control-variable is set to 1, since \(\langle\omega^{2}\vert_{\gamma (s)},\dot{\gamma}(s)\rangle=1\)). In [16] we have proven the following Theorem.
Definition 1
Let \(\mathcal{R} \subset\mathrm{SE}(2)\) denote the set of end-points in SE(2) that can be reached from e with a stationary curve of problem P curve.
Theorem 1
In P curve we set initial condition (x in ,y in ,θ in )=e=(0,0,0) and consider \((x_{fin},y_{fin},\theta_{fin}) \in \mathbb{R} ^{2} \rtimes S^{1}\). Then
-
\((x_{fin},y_{fin},\theta_{fin}) \in\mathcal{R}\) if and only if P curve has a unique minimizing geodesic which exactly coincides with the unique minimizer of P MEC.
-
\((x_{fin},y_{fin},\theta_{fin}) \notin\mathcal{R}\) if and only if problem P curve is ill-defined (i.e. P curve does not have a minimizer).Footnote 7
As a result, for the case g in =(0,0,0), we say g fin ∈SE(2) is an admissible end-condition for P curve if \(g_{fin} \in\mathcal{R}\), as only for such end-conditions we have existence of a (smooth) global minimizer, see also [12]. See Fig. 4.
2 Structure of the Article
Firstly, in Sect. 3 we consider the origin of the problem of finding cuspless sub-Riemannian geodesics in \((\mathrm {SE}(2),\Delta , \mathcal{G}_{\beta})\), which includes cortical modeling of the primary visual cortex and association fields.
In Sect. 4 we provide a short road map on how to connect two natural parameterizations. The cuspless sub-Riemanian geodesics in the sub-Riemannian manifold \((\mathrm{SE}(2),\Delta,\mathcal{G}_{\beta})\) can be properly parameterized by the sub-Riemannian arclength parametrization (via t) or by spatial arclength parametrization (via s). Parametrization via t yields the central part of the mathematical pendulum phase portrait (recall Eq. (10)), whereas parametrization via s yields a central part of a hyperbolic phase portrait (recall Eq. (4)). The hyperbolic phase portrait does not coincide with a local linearization approximation (as in Hartman-Grobman’s theorem [38]). In fact, it is globally equivalent to the relevant part of the pendulum phase portrait (i.e. the part associated to cuspless sub-Riemannian geodesics). The involved coordinate transforms are global diffeomorphisms.
In Sect. 5 we define the exponential map [2, 47] for P curve and P MEC. Then we show that the set \(\mathcal{R} \subset\mathrm{SE}(2)\) (consisting of admissible end-conditions) equals the range of the exponential map of P curve. We will provide novel explicit formulas for the exponential map for P curve using spatial arc length parametrization s and moreover, for completeness and comparison, in Appendix B we will also provide explicit formulas for the exponential map of P MEC that were previously derived in previous work [47] by one of the authors.
We show that the exponential map of P curve follows by restriction of P MEC to the strip \((\nu,c) \in[0,2\pi] \times\mathbb{R}\), see Fig. 9. A quick comparison in Appendix B learns us that spatial arc-length parametrization (also suggested in [22]) simplifies the formulas of the (globally minimizing, cuspless) geodesics of P curve considerably.
As the set of admissible end-conditions \(\mathcal{R}\) equals the range of the exponential map of P curve, we analyze this important set \(\mathcal{R}\) carefully in Sect. 6. More precisely, we
-
1.
show that \(\mathcal{R}\) is contained in half space x≥0 and (0,y fin)≠(0,0) is reached with angle π,
-
2.
show in Theorem 6 that the boundary \(\partial \mathcal{R}\) consists of the union of endpoints of minimizers either starting or ending in a cusp and a vertical line \(\mathfrak{l}\) above (0,0,0), and we compute the total spatial arc-length towards a cusp,
-
3.
analyze and plot the cones of reachable angles θ fin per spatial endpoint (x fin,y fin),
-
4.
prove homeomorphic and diffeomorphic properties of the exponential map in Theorem 6,
-
5.
show in Lemma 8 that geodesics that end with a cusp at \(\theta_{fin}=\frac{\pi}{2}\) are precisely those with stationary curvature (\(\dot{\kappa}(0)=0\)) at the origin.
In Sect. 7 we solve the boundary value problem, where we derive a (semi)-analytic description of the inverse of the exponential map and present a novel efficient algorithm to solve the boundary value problem. This algorithm requires numerical shooting only in a small sub-interval of [−1,1], rather than a numerical shooting algorithm in \(\mathbb{R}^{2}\times S^{1}\).
In Sect. 8 we show a clear similarity of cuspless sub-Riemannian geodesics and the association field lines from psychophysics [34] and neuro-physiology [52]. This is not surprising as we will show that sub-Riemannian geodesics allowing x-parametrization, exactly solve the circle bundle model for association fields by Petitot, cf. [52]. It is remarkable that the endings of association fields are close to the cusp-surface \(\partial\mathcal{R}\), which we underpin with Lemma 8 and Remark 8.1.
For a concise overview of previous mathematical models for association fields and their direct relation to the cuspless sub-Riemannian geodesic model proposed in this article we refer to the final subsection in Appendix G.
3 Origin of Problem \(\bf{P}\): Cortical Modeling
In a simplified model (see [51, p. 79]), neurons of V1 are grouped into orientation columns, each of them being sensitive to visual stimuli at a given point of the retina and for a given direction on it. The retina is modeled by the real plane.
Orientation columns are connected between them in two different ways. The first kind is given by vertical connections, which connect orientation columns belonging to the same hypercolumn and sensible to similar directions. The second is given by the horizontal connections across the orientation columns which checks for alignment of local orientations. See Figs. 5 and 6.
The human visual system not only performs a score of local orientations (organized by a pinwheel structure in V1). It also checks (a priori) for alignment of local orientations in the enhancement and detection of elongated structures. In modeling both procedures it is crucial that one does not consider \(\mathbb{R}^{2}\times S^{1}\) as a flat Cartesian space. See Fig. 7.
The Euclidean motion group acts transitively and free on the space of positions and orientations, allowing us to identify the coupled space of positions and orientations \(\mathbb{R}^{2}\rtimes S^{1}\) with the roto-translation group \(\mathrm{SE}(2)=\mathbb{R}^{2} \rtimes SO(2)\). This imposes a natural Cartan connection [26, 52] on the tangent bundle \(T(\mathbb{R}^{2}\rtimes S^{1})\) induced by the push-forward of the left-multiplication of SE(2) onto itself.
Besides the non-commutative group structure on \(\mathbb{R}^{2}\rtimes S^{1}\equiv\mathrm{SE}(2)\), contact geometry plays a major role in the functional architecture of the primary visual cortex (V1) [41], and more precisely its pinwheel structure, cf. [52]. In his paper [52] Petitot shows that the horizontal cortico-cortical connections of V1 implement the contact structure of a continuous fibration π:R×P 1→P 1 with base space the space of the retina and P 1 the projective line of orientations in the plane. He applies his model to the Field’s, Hayes’ and Hess’ physical concept of an association field, to several models of visual hallucinations [32] and to a variational model of curved modal illusory contours [42, 48, 65]. Such association fields reflects the propagation of local orientations in the primary visual cortex. For further remarks on the concept of an association field and its mathematical models see Appendix G. Intuitively, the tangents to the field lines of the association field provide expected local orientations, given that a local orientation is observed at the center of the field in Fig. 8). These association fields have been confirmed by Jean Lorenceau et al. [43] via the method of apparent speed of fast sequences where the apparent velocity is overestimated when the successive elements are aligned in the direction of the motion path and underestimated when the motion is orthogonal to the orientation of the elements. They have also been confirmed by electrophysiological methods measuring the velocity of propagation of horizontal activation [37]. There exist several other interesting low-level vision models and psychophysical measurements that have produced similar fields of association and perceptual grouping [39, 49, 68], for an overview see [52, Chaps. 5.5, 5.6]. Remarkably, psychological physics experiments based on multiple Gabor patch-stimuli indicate a thresholding effect in contour recognition, if the slope variation in two subsequent elements (Gabor patches) is too large no alignment is perceived and if the orientations are no longer tangent but transverse to the curve no alignment is perceived, cf. [52].
In this article we will show that sub-Riemannian geodesics closely model the association fields from psychophysics and that the location of cusps seems to provide a reasonable grouping criterium to connect two local orientations (consistent with endings of the association field), see Fig. 8. Next we will show that it does not matter whether one lifts problem P (given by Eqs. (1) and (2)) to the projective line bundle or to the group of rotations and translations in the plane.
3.1 No Need for Projective Line Bundles in P curve
The P MEC problem on \((\mathrm{SE}(2)=\mathbb {R}^{2}\rtimes S^{1}, \Delta=\mathrm {Ker}(\omega^{3}), \mathcal{G}_{\xi})\) can as well be formulated on the projective line bundle P 1 [14, 52] where antipodal points on the sphere S 1 are identified. See also [13].
In the setting of P curve, we then can study the problem with initial condition in the set
and similarly for the final condition. Nevertheless, the structure of solutions does not change with respect to the solutions of the standard problem P curve. Indeed such flips are either not allowed or they do not produce new curves:
-
Flipping only one of the boundary conditions is not possible as in this article we shall show that if \((x_{fin},y_{fin}, \theta_{fin}) \in \mathcal{R} \Rightarrow(x_{fin},y_{fin}, \theta_{fin}+\pi) \in (\mathbb{R} ^{2}\times S^{1}) \setminus\mathcal{R}\), i.e. when (x fin ,y fin ,θ fin ) is an admissible ending condition then (x fin ,y fin ,θ fin +π) is not admissible.
-
If we both flip (i.e. θ↦θ+π) and switch both the initial and ending condition we get the same curve (in opposite direction).
So when insisting on cuspless solution curves in our central problem P, lifting problem P to the projective bundle \(\mathbb{R}^{2} \rtimes P^{1}\) is equivalent to lifting P to \(\mathrm{SE}(2)\equiv\mathbb {R}^{2}\rtimes S^{1}\). In fact, identification of antipodal points does not make any difference when considering cuspless sub-Riemannian geodesics in \((\mathrm{SE}(2), \Delta,\mathcal{G}_{\xi})\).
Therefore, in this article we will not identify antipodal points and we focus on problem P curve and its corresponding admissible boundary conditions (i.e. an explicit description of the set \(\mathcal {R}\subset\mathrm{SE}(2)\)).
4 Parametrization of Curves in P curve
The natural parametrization for sub-Riemannian geodesics in P MEC is the sub-Riemannian arclength parametrization. However, when considering only those sub-Riemannian geodesics in \((\mathrm{SE}(2),\Delta,\mathcal{G}_{\xi})\) without cusps (as in P curve), i.e. the cuspless sub-Riemannian geodesics, the problem is actually a planar curve problem (as in P) and there it is more naturalFootnote 8 to use spatial arclength parametrization.
Recall t denotes the sub-Riemannian arclength parameter of a (horizontal) curve γ(⋅)=(x(⋅),y(⋅),θ(⋅)) in \((\mathrm{SE}(2),\Delta,\mathcal{G}_{\xi})\) and s denotes the spatial arclength parameter of \((x(\cdot),y(\cdot ))=P_{\mathbb{R}^{2}} \gamma(\cdot)\), recall Eq. (7). Then along a horizontal curve \(\gamma\in(\mathrm{SE}(2),\Delta,\mathcal {G}_{\xi})\) we have \(\kappa(s)=\dot{\theta}(s)\) and \(\langle\omega^{2}\vert_{\gamma(s)}, \dot{\gamma}(s) \rangle= \|\dot{\mathbf{x}}(s)\|=1\) and thereby we have
As mentioned in Remark 1.2, we may as well set ξ=1. Furthermore, recall from Eq. (4) that the Euler-Lagrange equation for cuspless sub-Riemannian geodesics in P curve is \(\ddot{z}(s)=z(s)\), producing a hyperbolic phase portrait where we must restrict ourselves to \(z=\kappa/\sqrt{\kappa^{2}+1} \in(-1,1)\). On the other hand, we recall from Eq. (10) the Euler-Lagrange equation for sub-Riemannian geodesics in P MEC is given by \(\ddot{\nu}(t)=-\sin\nu(t)\) producing a mathematical pendulum phase portrait where we must restrict ν to the interior of \(\mathbb{R} /(4\pi\mathbb{Z})\) say the open interval (−π,3π), cf. [47]. The central part ν∈(0,2π) of the mathematical pendulum relates to the initial momentum components of cuspless sub-Riemannian geodesics. In fact, it is globally equivalent to the hyperbolic phase portrait as follows by the next lemma and Fig. 9.
Lemma 1
The central part (i.e. ν∈(0,2π)) of the mathematical pendulum phase portrait induced by \(\ddot{\nu}(t)=-\sin(\nu(t))\) is diffeomorphic to a hyperbolic phase portrait of the linear ODE \(\ddot {z}(s)=z(s)\) (with |z|<1). The direct coordinate transforms between (ν,c) and \((z,\dot{z})\) are given by
where
Proof
Directly follows by the chain-law:
Finally, we note that for |z(s)|<1 the mapping between s and t is a diffeomorphism. □
5 Cusps and the Exponential Map Associated to P curve and P MEC
In order to express the exponential map associated to P curve(for ξ=1) in spatial arclength parametrization we apply Bryant & Griffith’s approach [20], which was previously successfully applied to the elastica problem [19]. Here we will also include an additional viewpoint on this technical approach via the Cartan connection. In case the reader is not so much interested in the geometrical details and underpinnings, it is also possible to skip the following derivations and to continue reading starting from the formulas for the sub-Riemannian geodesics γ(s) in Theorem 3.
To avoid large and cumbersome computations we first need some preliminaries on moving frames of references and Cartan connections. Recall to this end our notations for left-invariant frame \(\{\mathcal {A}_{i}\}_{i=1}^{3}\) given by Eq. (14), and left-invariant co-frame \(\{\omega^{i}\}_{i=1}^{3}\) given by Eq. (15). The left-invariant vector fields generate a Lie algebra
where the non-zero structure constants are \(c^{3}_{12}=-c^{3}_{21}=-c_{13}^{2}=c_{31}^{2}=1\). This Lie-algebra serves as the moving frame of reference in \(\mathbb{R} ^{2}\rtimes S^{1} \equiv\mathrm{SE}(2)\). The Cartan connection ∇ on T(SE(2)) is given by
where we used the following definitions
As a result (for details see Eq. (93) and Theorem 12 in Appendix C) covariant differentiation of a momentum covector field
along a curve γ:[0,ℓ]→SE(2) yields
with \(\dot{\lambda}_{k}(s)= \langle{\rm d}\lambda_{k}, \dot{\gamma }(s)\rangle\).
Remark 5.1
The Christoffel symbols \(c^{j}_{ki}\) of the Cartan connection ∇ on the tangent bundle T(SE(2)) expressed in reference frame \(\{\mathcal{A}_{i}\}_{i=1}^{3}\) equal minus the structure constants on the Lie algebra. The Christoffel symbols of the corresponding Cartan connection on the co-tangent bundle T ∗(SE(2)) w.r.t. reference frame \(\{\omega^{i}\}_{i=1}^{3}\) have opposite sign and are thereby equal to the structure constants \(c^{j}_{ik}=-c^{j}_{ki}\).
Finally we mention the Cartan’s structural formula
so for example for k=2 we find \({\rm d}\omega^{2}= {\rm d}(\cos\theta{\rm d}x+\sin\theta{\rm d}y)=-\sin\theta{\rm d}\theta\wedge{\rm d}x + \cos\theta{\rm d}\theta\wedge{\rm d}y= {\rm d}\theta\wedge{\rm d}\omega^{3}\).
Now that the preliminaries are done let us apply Bryant and Griffith’s method to P curve in 4 steps.
Step 1: Extend the manifold SE(2) with geometric control variables Consider the extended manifold \(Q= \mathrm{SE}(2)\times\mathbb{R}^{+} \times\mathbb{R}\times \mathbb{R}\) with coordinates (x,y,e iθ,σ,κ,r), where σ=∥x′(r)∥ so that \({\rm d}s= \sigma{\rm d}r\), where r↦x(r) is some parametrization of the spatial part of the lifted curve r↦γ(r)=(x(r),θ(r)) in SE(2). In order to extend the sub-Riemannian manifold \((\mathrm{SE}(2),\mathrm{Ker}(\omega^{3}), \mathcal{G}_{\xi=1})\) such that the concept of horizontal curves is preserved we impose
These equations determine the horizontal part
of the dual tangent space T ∗(Q). We have extended the sub-Riemannian manifold \((\mathrm{SE}(2),\mathrm{Ker}(\omega ^{3}),\mathcal {G}_{\xi=1})\) naturally to I(Q).
Step 2: Include momentum Include the Lagrange multipliers as local momentum vectors in our target space. Therefore we extend Q to a larger space Z. We define Z as the affine sub-bundle
of T ∗(Q) determined by
which is isomorphic to Z≡Q×T ∗(SE(2)) via
Step 3: Minimization on extended space Z Consider a one parameter family {N r } of horizontal vector fields on SE(2) and compute the variation of the integrated Lagrangian-form ψ along such a N r :
where we used the Stokes Theorem \(\int_{N_{r}} {\rm d}(\frac{\partial }{\partial r} \rfloor\psi) = \oint_{\partial_{N_{r}}} \frac{\partial }{\partial r} \rfloor\psi=0\) and the formula for Lie derivatives of volume forms along vector fields \(\mathcal{L}_{X}A=X \rfloor{\rm d }A + {\rm d}(X \rfloor A)\) and where X⌋A:=A(X,⋅) denotes the insert operator. Consequently, we must solve the canonical ODE system
where Γ(r)≡(γ(r),κ(r),σ(r),r,p(r)). This boils down to
Now by means of the Cartan structural formula (22), and Eq. (27) we obtain the Pfaffian system
The first three equations represent the horizontality restriction. The two equations in the middle represent the Euler-Lagrange optimization of the energy and show that {λ 1,λ 2,λ 3} are components of momentum with respect to the dual frame (under identification (24)). It is readily deduced that
Theorem 2
Define \(L:= \sigma\sqrt{\kappa^{2}+1}\). The Pfaffian system (28) for
with γ a cuspless sub-Riemannian geodesic can be rewritten as
where ∇ denotes the Cartan connection on the co-tangent bundle T ∗(SE(2)).
Proof
The last 3 equations in (28) provide the momentum covector. They can be written as
which by Eq. (21) can be rewritten as
To this end we note that
Finally, with respect to the second part of Eq. (30):
from which the result follows. □
Remark 5.2
The first part ensures γ=(x,θ) is the horizontal lift from the planar curve x(s)=(x(s),y(s)), i.e. \(\theta(s)=\arg(\dot{x}(s)+i \dot{y}(s))\). The second part allows us to interpretate \(p=\sum_{i=1}^{3} \lambda_{i} \omega^{i}\) as a momentum covector.
Remark 5.3
In contrast to Levi-Civita connections on Riemannian manifolds, the Cartan connection ∇ has torsion and thereby auto-parallel curves do not coincide with geodesics. In fact, Theorem 12 in Appendix C shows that auto-parallel curves are (horizontal) exponential curves.
Step 4: Integrate the Pfaffian system To integrate \(\nabla_{\dot{\gamma}}p=0\) we resort to matrix-representation \(m:\mathrm{SE}(2) \to\mathbb{R}^{3\times3}\) given by
and express dual-vectors (covectors) as row vectors. Analogously to Bryant’s work on elastica [19] we express equation (32) in explicit coordinates
where we use short-notation for the row-vector
from which we deduce that
Before we will derive γ from Eq. (37) we will need the following lemma based on Noether’s theorem. Formally, one can avoid this general abstract lemma (as in [19]) by observing
Lemma 2
Cuspless sub-Riemannian geodesics are contained within the co-adjoint orbits
for all s∈[0,s max], with s max given by Eq. (41).
Proof
According to Noether’s theorem (i.e. conservation law on momentum) the moment map m:Z→T(SE(2))∗ given by \(\langle m(\mathfrak{q},p), \varXi\rangle= (\varXi\rfloor\psi )(\mathfrak{q},p)\) with \((\mathfrak{q},p) \in Z\equiv Q \times T^{*}(\mathrm {SE}(2))\), for all Ξ∈T(SE(2)) is constant along the characteristic curves \(\varXi=\dot{\gamma}\). The co-adjoint representation of SE(2) acting on the dual of its Lie-algebra (T(SE(2)))∗ is given by \(\langle(\mathrm{Ad}_{g^{-1}})^{*}p ,\varXi\rangle= \langle p, \mathrm {Ad}_{g} \varXi\rangle\), i.e.
We have \(m(\eta_{g}(\mathfrak{q},p))= (\mathrm{Ad}_{g^{-1}})^{*} m(\mathfrak {q},p)\), where the group action g↦η g is given by
As a result the co-adjoint orbits of SE(2) coincide with the cylinders in Eq. (38). □
Corollary 1
From Eq. (38) we deduce that
The minimizers of P curve are cuspless geodesics and their total length (towards a cusp) equals
The curvature of orbits with \(\mathfrak{c}<1\) and z 0>0 is strictly positive. The curvature of orbits with \(\mathfrak{c}<1\) and z 0<0 is strictly negative. The curvature of orbits with \(\mathfrak{c}>1\) switches sign once at
Proof
Follows directly from the hyperbolic phase portrait induced by \(\ddot{z}=z\) and Theorem 2, and solving for respectively |z(s)|=1 and z(s)=0. □
After these results on sub-Riemannian geodesics, we continue with solving for ∇p=0, Eq. (37). Problem P curve is left-invariant and in the next lemma we select a suitable point on each co-adoint orbit to simplify the computations considerably.
Lemma 3
Let \(\mathfrak{c}>0\). There exists a unique h 0∈SE(2) such that \(\hat{\lambda}(0) m(h_{0}^{-1}) = (\mathfrak{c},0,0)\). Consequently, we have for \(\tilde{\gamma}(s):=h_{0}\gamma(s)\) that
Proof
Equation (43) follows by Eq. (37) and the fact that m (Eq. (34)) is a group representation. □
Applying the above Lemma and Eq. (29) provides the next theorem, Theorem 3, where we provide explicit analytical formulae for the geodesics by integration of the Pfaffian system. To this end we first need a formal definition of the operator that integrates the Pfaffian system Eq. (28) and produces the corresponding geodesic of P curve in SE(2).
This operator needs initial momentum p 0 and total spatial length ℓ>0 as input and produces the corresponding geodesic of P curve as output. By Eqs. (29) and (32) initial momentum equals
with initial normalized curvature \(z_{0}=\kappa_{0}/\sqrt{\kappa_{0}^{2}+1}\). As a result, we have
The Hamiltonian at the unity element, evaluated at initial momentum is given by
Now let us use arclength parameterization (so set r=s and σ=1) in the canonical ODE system (26) on Z. Via identification Eq. (24) this gives rise to an equivalent ODE system on Q×T ∗(SE(2))
with unity element e=(0,0,0)∈SE(2).
Definition 2
Let γ(s)=e sF(γ(0)),s∈[0,ℓ] denote the unique solution of ODE (45). Now in view of Eq. (8) and Lemma 2 we define
and we define \(\widetilde{\mathrm{Exp}}_{e}: \mathcal{D} \to\mathrm {SE}(2)\) by
where π:Q×T ∗(SE(2))→SE(2) is the natural projection given by Π(g,1,κ,s,p)=g for all \(g \in\mathrm{SE}(2), \kappa ,s>0, p \in T^{*}_{g}(\mathrm{SE}(2))\).
Remark 5.4
For sober notation we omit index e and write \(\widetilde{\mathrm{Exp}}=\widetilde{\mathrm{Exp}}_{e}\) and H(p)=H(e,p) for exponential map and Hamiltonian. Furthermore, we include a tilde in this exponential map associated to the geometrical control problem of P curve to avoid confusion with the exponential map Exp:T e (SE(2))→SE(2) from Lie-algebra to Lie group.
Remark 5.5
The dual vectors \(p_{0}= \pm{\rm d}\theta\) are not part of the domain of the exponential map as in these cases one would have \((z_{0},\dot{z}_{0})=(\pm1,0)=(z(s),\dot{z}(s))\) for all s≥0 and the sub-Riemannian geodesics in SE(2) propagate only in vertical direction, not allowing spatial arc-length parameterization. See also [16, Remark 31].
Theorem 3
The exponential map (given by Eq. (47)) expressed in spatial arc-length parametrization is given by
with λ 1(0)=z 0, \(\lambda_{2}(0)=\sqrt{1-|z_{0}|^{2}}\), \(\lambda_{3}(0)=-\dot{z}_{0}\), and s∈[0,ℓ] with total spatial length ℓ≤s max less than the spatial cusp-length Eq. (41).
Here the cuspless geodesics are given by \(\gamma(s)= h_{0}^{-1} \tilde {\gamma}(s)\), i.e.
with \(h_{0}=(\overline{\mathbf{x}}_{0},\overline{R}_{0}) \in\mathrm {SE}(2)\), with \(\overline{\mathbf{x}}_{0}=(\frac{z_{0}}{\mathfrak{c}},0)^{T}\).
Here curve \(\tilde{\gamma}=(\tilde{x},\tilde{y},\tilde{\theta})\) is given by
where \(\mathfrak{c} \geq0\) is given by
Proof
Follows by Lemma 3 and Eq.’s (44), (29). □
Note that the cuspless geodesic γ follows from cuspless geodesic \(\tilde{\gamma}=h_{0} \gamma\) via the rigid body motion
Corollary 2
The end-point g fin of a cuspless sub-Riemannian geodesic is given by
Proof
From the previous Theorem 3 we deduce
and
from which the result follows. □
Corollary 3
The (x,y)-coordinates of the Exponential map involve one elliptic integral and the tangent vectors along geodesics do not involve any special functions. Furthermore, from \(-\dot{\tilde{y}}(s) \geq0\) it follows that the spatial part of the geodesics is monotonically increasing along the \((-\sin\overline {\theta}_{0}, -\cos\overline{\theta}_{0})=\frac{1}{\mathfrak{c}}(\sqrt {1-|z_{0}|^{2}},-\dot{z}_{0})\)-axis:
Geodesics with \(\mathfrak{c}=1\) admit simple formulas:
Corollary 4
In the critical case \(\mathfrak{c}=1\) and \(\dot{z}_{0}=-z_{0}\) we find s max=∞ and
For s→∞ solutions converge towards the \(-\tilde{y}\)-axis. Geodesic γ(s) now follows by Eq. (79).
Corollary 5
In the critical case \(\mathfrak{c}=1\) and \(\dot{z}_{0}=z_{0}\) we find s max=−log|z 0| and
Geodesic γ(s) now follows by Eq. (49).
For a plot of the critical surface see Fig. 10.
5.1 Relation Between the Exponential Mappings of P curve and P MEC
In Theorem 3 we have derived the exponential map of P curve in terms of spatial arc-length parametrization s, whereas in previous work [15] the exponential map of P MEC is expressed in sub-Riemannian arc-length t. For comparison see Appendix B.
On the one hand one observes that the exponential map of P curve is much simpler when expressed in s and it is easier to integrate in current active shape models in imaging where the same kind of parametrization is used. On the other hand for P MEC it is more natural to choose t-parametrization as this parametrization does not beak down at cusps. The following theorem relates the exponential mappings for P curve and P MEC.
Theorem 4
Let \(\widetilde{\mathrm{Exp}}\) denote Footnote 9 the exponential map of P curve. Let \(\widetilde{\mathrm{EXP}}\) denote the exponential map of P MEC. Then these exponential maps satisfy the following relation
for all \(p_{0}\in C \subset T^{*}_{e}(\mathrm{SE}(2))\), and all 0<ℓ≤s max , (so that \((p_{0},\ell) \in\mathcal{D}\), recall Eq. (46)), where t(ℓ,p 0) is given by Eq. (6).
Proof
We note that ℓ≤s max implies that the orbits do not hit the cusp lines in the pase portraits (i.e. |z|=1 and ν=0,2π) so that (ν(t),c(t)) stays within the central strip (i.e. ν(t)∈[0,2π]) indicated in Fig. 9. The rest follows by Lemma 1. □
6 The Set \(\mathcal{R}\) and the Cusp-Surface \(\partial \mathcal {R}\)
According to Theorem 1 the set of points in SE(2) that can be reached with a global minimizer from unity element g in =e=(0,0,0) is equal to \(\mathcal {R}\) given in Definition 1. Therefore, we first need to investigate this set in order to apply cuspless sub-Riemannian geodesics in vision applications. First of all we have the following characterization.
Theorem 5
Let s max (p 0) be given by Eq. (41). Let C be given by Eq. (46). The range of the exponential map given by
coincides with the set \(\mathcal{R}\), consisting of points in SE(2) that can be reached with (globally minimizing) geodesics of P curve departing from e.
Proof
Apply Theorems 1 and 3, where the analytic stationary solution curves of P curve break down iff ℓ=s max (p 0) in which case tangents to geodesics are vertical due to \(|z(\ell)|=\frac{d\theta}{dt}(T)=1\). □
The exponential map of P curve coincides with the exponential map of P MEC [2, 47] restricted to the strip ν(t(s))∈[0,2π] (in between the blue lines in Fig. 9), where we exclude the points (ν,c)=(0,0) and (ν,c)=(2π,0) from the strip (recall Remark 5.5) so that in the range we exclude the vertical line
The exponential map of P MEC restricted to this strip is a homeomorphism (as follows by the results in [56]) thereby the exponential map of P curve is a homeomorphism as well. As a result (for formal proof see Appendix F) we have
Theorem 6
Let \(\mathcal{D}, \mathcal{R}\) denote respectively the domain and range of the exponential map of P curve (recall Eqs. (46), (54)). Then
-
\(\widetilde{\mathrm{Exp}}: \mathcal{D} \to\mathcal{R}\) is a homeomorphism if we equip \(\mathcal{D}\) and \(\mathcal{R}\) with the subspace topology.Footnote 10
-
\(\widetilde{\mathrm{Exp}}: \mathring{\mathcal{D}} \to \mathring {\mathcal{R}}\) is a diffeomorphism.
Finally, the boundary \(\partial\mathcal{R}\) is given by
These results can be observed in Fig. 11, which shows a well-posed, smooth, bijective relation between smooth regions in the phase portrait (i.e. \(\mathcal{D}\)) and smooth regions in \(\mathcal {R}\subset\mathrm{SE}(2)\) and where the union of the blue and red surfaces form the cusp-surface adjacent to the line \(\mathfrak{l}\). Subsequently, we provide some theorems on \(\mathcal{R}\) and \(\partial \mathcal{R}\) to get a better grip on the existence set of P curve, recall Eqs. (3) and (11).
6.1 The Elliptic Integral in the Exponential Map
In this section we will first express the single elliptic integral arising in the exponential map in Theorem 3 in a standard elliptic integral and then we provide bounds for this integral from which one can deduce bounds on the set \(\mathcal{R}\).
Lemma 4
The elliptic integral in Theorem 3 can be rewritten as
with \(\delta= \sqrt{|c_{1}|^{2}-|c_{2}|^{2}}\leq1\) and \(\varphi=\frac {1}{4} \log\frac{c_{1}+c_{2}}{c_{1}-c_{2}}\), with \(c_{1}=\frac{|z_{0}|^{2} +|\dot{z}_{0}|^{2}}{1+\mathfrak{c}^{2}}\), \(c_{2}=\frac{2 z_{0} \dot{z}_{0}}{1+\mathfrak{c}^{2}}\) and where
denotes the elliptic integral of the second kind.
Proof
Using Eq. (77) and Eq. (38) we find \(1-|z(\tau)|^{2}= \frac{1+\mathfrak{c}^{2}}{2} (1- c_{1}\cosh(2\tau) - c_{2} \sinh(2\tau))\) from which the result follows via v=iτ. □
For explicit bounds for the elliptic integral for the cases \(\mathfrak {c}<1\), where the sub-Riemannian geodesics are U-shaped, see Appendix H.
6.2 Observations and Theorems on \(\mathcal{R}\)
In Theorem 3 we have derived the exponential map of P curve in explicit form. Before we derive some results on the range \(\mathcal{R}\) of the exponential map we refer to Fig. 11 where we have depicted the set \(\mathcal {R}\) using Theorem 3. In Fig. 11 we observe:
-
1.
The range \(\mathcal{R}\) of the exponential map is a connected, non-compact set and its piecewise smooth boundary coincides with the cusp-surface, Eq. (55).
-
2.
The range of the exponential map produces a reasonable criterium (namely condition (3)) to connect two local orientations. Consider the set of reachable cones depicted in Fig. 14.
-
3.
The range of the exponential map of P curve is contained in the half-space x fin ≥0 and |θ fin |=π can only be attained at x=0 and y≠0 where geodesics arrive at a cusp.
-
4.
The cone of reachable angles θ fin per position \((x_{fin}, y_{fin}) \in\mathbb{R}^{+} \times\mathbb{R}^{+}\), with \((x_{fin},y_{fin},\theta_{fin}) \in\mathcal{R}\) is either given by
$$ \begin{aligned} &[\theta_{\mathrm{begincusp}}(\mathbf{x}_{fin}), \theta _{\mathrm{endcusp}}(\mathbf{x}_{fin})]\quad \textrm{or by }\\ &[\theta_{\mathrm{endcusp}}^{1}(\mathbf{x}_{fin}), \theta _{\mathrm{endcusp}}^{2}(\mathbf{x}_{fin})], \end{aligned} $$(57)with x fin =(x fin ,y fin ) where θ endcusp(x fin ) denotes the final angle of the geodesic ending in (x fin ,⋅) with a cusp, and where θ begincusp(x fin ) denotes the final angle of a geodesic ending in (x fin ,⋅) starting with a cusp. In the second case there exist two geodesics ending in x fin with a cusp and we index these such that \(\theta_{\mathrm {endcusp}}^{1}<\theta_{\mathrm{endcusp}}^{2}\). Which of the two options applies depends on \(\mathbf{x}_{fin} \in \mathbb{R} ^{2}\). See Fig. 12.
-
5.
The boundary of the range of the exponential map (given by Eq. (55)) is smooth except for 3 intersections between the surface induced by end-points of geodesics starting from a cusp and the surface induced by end-points of geodesics ending at a cusp. These intersections are given by
$$\begin{aligned}& \theta_{fin}=-\pi\quad\textrm{and}\quad x_{fin}=0 \quad\textrm{and}\quad y_{fin} \leq 0, \\& \theta_{fin}=0 \quad\textrm{and }\\& |y_{fin}|= -x_{fin} i E \biggl(i \,\mathrm{arcsinh}\, \frac{x_{fin}}{\sqrt{4-x_{fin}^2}}, 1-\frac{4}{x_{fin}^2} \biggr), \\& \textrm{and}\quad 0\leq x_{fin}<2, \\& \theta_{fin}=\pi\quad\textrm{and}\quad x_{fin}=0\quad \textrm{and}\quad y_{fin} \geq0, \end{aligned}$$where E(z,m) is given by Eq. (56).
-
6.
The critical surface splits the range of the exponential map into four disjoint parts, cf. Fig. 11. These parts \(\mathcal{C}_{1}^{1}\), \(\mathcal{C}^{0}_{1}\), \(\mathcal{C}_{2}^{+}\) and \(\mathcal{C}_{2}^{-}\) directly relate to the splitting of the phase space, into the four parts \(C_{1}^{1}\), \(C^{0}_{1}\), \(C_{2}^{+}\) and \(C_{2}^{-}\).
-
7.
If \(g_{fin}=(x_{fin},y_{fin},\theta_{fin}) \in\mathcal{R}\) then \(g_{fin}=(x_{fin},y_{fin}, \theta_{fin}+\pi) \notin\mathcal{R}\).
Let’s underpin these observations with theorems.
Lemma 5
Let 0<a<b<1. Then \(\varPsi(a,b):=\frac{a}{\sqrt{1+b}} -\frac{1}{2} \log( \frac{b+a}{b-a} )<0\).
Proof
Ψ does not contain stationary points in the open region in \(\mathbb{R} ^{2}\) given by 0<a<b<1. At the boundary we have Ψ(0,b)=0 and lim b↓a Ψ(a,b)=−∞ and \(\varPsi(a,1)= \frac{a}{\sqrt{2}}-\frac{1}{2} \log( \frac {1+a}{1-a} )\) and \(\frac{\partial\varPsi(a,1)}{\partial a}<0\) so Ψ(a,b)<Ψ(0,1)=0 for 0<a<b<1. □
Theorem 7
The range \(\mathcal{R}\) of the Exponential map of P curve is contained within the half space x≥0. In particular, its boundary \(\partial\mathcal{R}\) (i.e. the cusp-surface) is contained within x≥0.
Proof
From Theorem 3 we deduce that
One has (see Fig. 9)
In the other cases in the phase portrait where
the result is obvious. Via symmetry considerations one only needs to consider the case
where z(s max )=1. Then we apply Lemma 5 (with \(a=-\dot{z}_{0}\) and b=z 0) from which we deduce that
In the remainder of this proof we will show that
which yields the result x fin ≥0. In order to show Eq. (60) we consider the integrand \(\psi(s):= \sqrt{1-|z(s)|^{2}}\) which is a continuous (concave) function with a single maximum at s ∗ with \(\dot{z}(s^{*})=0\) which yields (under the condition \(-z_{0}\leq\dot{z}_{0} \leq0\))
so that indeed by means of Eq. (59), see Fig. 18
from which the final result x(ℓ)=x fin ≥0 follows by Eq. (58) and Eq. (60). □
For analysis of \(\mathcal{R}\) and \(\partial\mathcal{R}\) and for (semi-)analytically solving of the boundary value problem the following identities (due to Theorem 3) come at hand.
Lemma 6
We have the following relation between the momentum at s=0
and the end-condition g fin =(x fin ,y fin ,θ fin ):
This yields a quadratic polynomial equation in \(\dot{z}_{0}\):
the discriminant D=b 2−4ac≥0 equals
and whose solutions are expressed in z 0 via
Theorem 8
In P curve the plane x fin =0 is only reached by a non-trivial geodesic that starts in a cusp and ends in a cusp with angle θ fin =π, i.e.
Proof
Suppose |θ fin |=π then on the one hand by Eq. (61) we have \(\dot{z}(\ell)=-\dot{z}_{0}\) whereas on the other hand by Eq. (52) we have \(\dot{z}_{\ell}\sqrt {1-|z_{0}|^{2}}-\dot{z}_{0}\sqrt{1-|z(\ell)|^{2}}=0\) from which we deduce |z(ℓ)|=|z 0|=1. Suppose |z 0|2=|z(ℓ)|2=1 and \(\dot{z}_{0}=-\dot{z}(\ell)\) then z(0)≠−z(ℓ) and we obtain x fin =0 and y fin ≠0 by Eq. (52). Finally, suppose x fin =0 and y fin ≠0 then D=ψ=R 2=0 and ρ=R 1=−α in Eq. (63) and thereby we obtain cos(2θ fin )=1 and the result follows □
See Fig. 13 for an illustration of such geodesics.
6.3 The Cones of Reachable Angles
We will provide a formal theorem that underpins our observations of the cone of reachable angles θ fin per end-position (x fin ,y fin ), recall (57). Recall that θ endcusp(x fin ,y fin ) denotes the final angle of the geodesic ending in (x fin ,y fin ,⋅) with a cusp and where θ begincusp(x fin ,y fin ) denotes the final angle of a geodesic ending in (x fin ,y fin ,⋅) starting with a cusp. In case there exist two geodesics ending with a cusp at (x fin ,y fin ) we order their end-angles by writing
Theorem 9
Let \((x_{fin},y_{fin},\theta_{fin}) \in\mathcal{R}\). If
then we have
otherwise (so in particular if x fin ≥2) we have
For a direct graphical validation of Theorem 9 see Fig. 11 (in particular the top view along θ), where we note that the bound in (65) relates to the spatial projection of the curve that arises by taking the intersection of the blue and red surface on \(\partial\mathcal{R}\) at θ=0 (the thick black line in Fig. 11 at θ=0). For more details on the proof see Appendix E.
As already mentioned in Sect. 3.1, it does not matter if one considers problem P curve on the projective line bundle \(\mathbb{R}^{2} \rtimes P^{1}\) or on \(\mathbb{R}^{2} \rtimes S^{1} \equiv\mathrm {SE}(2)\). This is due to the following theorem.
Theorem 10
If
then
Proof
From Theorem 3 we have \(-\dot {\tilde{y}}(s) \geq0\) from which we deduce condition \(\sin(\theta _{fin}-\overline{\theta}_{0}) \leq0\) implying the result. □
7 Solving the Boundary Value Problem
In order to explicitly solve the boundary-value problem for P curve for admissible boundary conditions (Eq. (3)) we can apply left-invariance (i.e. rotation and translation invariance) of the problem and consider the case g in =e=(0,0,0) and \(g_{fin} \in \mathcal{R}\).
Recall from Eq. (20) that initial momentum p 0 is determined by z 0 and \(\dot{z}_{0}\):
Now solving the boundary value problem boils down to expressing (p 0,ℓ) directly into
since when we achieve to do so we have
and the globally minimizing curve of P curve is given by
In fact, this means we must find the inverse of the exponential map \(\widetilde{\mathrm{Exp}}\). The inverse of this exponential map exists due to Theorems 6, 4 and 1.
We invert the boundary value problem for a very large part analytically, yielding a novel very fast and highly accurate algorithm to solve the boundary value problem. In comparison to previous work on this topic [45], we have less parameters to solve (and moreover, our proposed optimization algorithm involves less parameters).
First of all we directly deduce from Theorem 3, Lemma 6 and Eq. (40) that
where \(v,w,\mathfrak{c}\) are given by
Now we have already expressed two of the three unknowns in the end condition
The remaining unknown variable z 0∈[−1,1] can be found via a simple numerical algorithm to find the unique root of a function \(F:I \to\mathbb{R}^{+}\), where I⊂[−1,1] is a known and determined by g fin .
However, before we can formulate this formally there is a technical issue to be solved first, which is the choice of sign in Eq. (64).
Lemma 7
Let surface \(\mathcal{V} \subset\mathrm{SE}(2)\) be given by
(where \(\dot{z}_{0}=0\)). Given \(g_{fin} \in\mathcal{R}\) we have
with a=a(g fin ,z 0),b=b(g fin ,z 0) given by Eq. (62) and D=D(g fin ,z 0) given by Eq. (63) and with \({\rm sign}(g_{fin})\) given by
Proof
The \(\widetilde{\mathrm{Exp}}\) is a (global) homeomorphism and its orbits \(s \mapsto\widetilde{\mathrm{Exp}}(p_{0},s)\) are analytic for each \(p_{0} \in T^{*}_{e}(\mathrm{SE}(2))\). Thereby the sign cannot switch along orbits (unless D=0, which only occurs at θ fin =±π at \(\partial\mathcal{R}\)). Furthermore, since \(\widetilde{\mathrm{Exp}}\) is a homeomorphism sign switches (in Eq. (64)) between neighboring orbits are not possible unless it happens across an orbit \(s\mapsto(z(s),\dot {z}(s))\) with \(\dot{z}_{0}=0\). Now from the phase portrait it is clear that orbits in phase space \(s \mapsto(z(s), \dot{z}(s))\) with \(\dot{z}(s)>0\) and \(\mathfrak{c}>1\), i.e. orbits in \(C^{+}_{2}\) need a plus sign, whereas orbits in \(C^{-}_{2}\) need a minus sign in Eq. (64). The line \(\dot{z}_{0}=0\) splits the phase portrait in two parts, and by the results in Theorem 6 this means that the surface \(\mathcal{V}\) splits the set \(\mathcal{R}\) into two parts. Now \(\widetilde{\mathrm{Exp}}\) maps \(C^{+}_{2}\) onto \(\mathcal{C}^{+}_{2}\) and it maps \(C^{-}_{2}\) onto \(\mathcal{C}^{-}_{2}\), and \(\mathcal{C}^{-}_{2}\) lies beneath V and \(\mathcal{C}^{+}_{2}\) lies above V, from which the result follows. □
Remark 7.1
The surface \(\mathcal{V}\) is depicted in Fig. 15. Lemma 7 is depicted in Fig. 16, where we used Theorem 3 to compute for each point in \((z_{0},\dot{z}_{0}) \in[-1,1] \times[-2,2]\) in phase space the sign of \(2a \dot{z}_{0}+b\) at respectively \(s=0, \frac{1}{2}s_{max}(z_{0},0), \frac{3}{4}s_{max}(z_{0},0)\) and s=s max (z 0,0). We see that the black points (where the sign is positive) lies above the orbits family of orbits with z 0∈[−1,1] and \(\dot{z}_{0}=0\).
Remark 7.2
The explicit parametrization for plane \(\mathcal {V}\) is given by the union of the x-axis and the surface parameterized by
z 0∈(−1,1)∖{0}, 0≤ℓ≤arccosh(|z 0|−1).
The next theorem reduces the boundary value problem to finding the unique root of a single positive real-valued function.
Theorem 11
Let \(g_{fin} \in\mathcal{R}\). The inverse of the exponential map in Definition 2 is given by
with λ 1(0)=z 0, \(\lambda_{2}(0)=\sqrt{1-|z_{0}|^{2}}\), \(\lambda_{3}(0)=-\dot{z}_{0}\), where \(\dot{z}_{0}(z_{0},g_{fin})\) given in Lemma 7 and with discriminant D(z 0,g fin ) given by Eq. (63) and where z 0 denotes the unique zero F(z 0)=0 of function \(F:I \to \mathbb{R}^{+}\) defined on
given by
where ∥⋅∥ denotes the Euclidean norm on \(\mathbb{R}^{2}\times S^{1}\).
Proof
By Theorem 1 there is a unique stationary curve connecting e and \(g_{fin} \in\mathcal{R}\). The exponential map of P curve is a homeomorphism by Theorem 6 and thereby the continuous function F has a unique zero, since ℓ and \(\dot{z}_{0}\) are already determined by z 0 and g fin via Theorem 3 and Lemma 7. □
Remark 7.3
Theorem 11 allows fast and accurate computations of sub-Riemannian geodesics, see Fig. 12 where the computed geodesics are instantly computed with an accuracy of relative \(\mathbb{L}_{2}\)-errors in the order of 10−8. Finally, we note that Theorem 6 implies that (our approach to) solving the boundary-value problem is well-posed (i.e. the solutions are both unique and stable).
8 Modeling Association Fields with Solutions of P curve
Contact geometry plays a major role in the functional architecture of the primary visual cortex (V1) and more precisely in its pinwheel structure, cf. [52]. In his paper [52] Petitot shows that the horizontal cortico-cortical connections of V1 implement the contact structure of a continuous fibration π:R×P→P with base space the space of the retina and P the projective line of orientations in the plane. This model was refined by Citti and Sarti [22], who formulated the model as a contact structure within SE(2) producing problem P curve given by Eq. (11).
Petitot applied his model to the Field’s, Hayes’ and Hess’ physical concept of an association field, to several models of visual hallucinations [32] and to a variational model of curved modal illusory contours [42, 48, 65].
In their paper, Field, Hayes and Hess [34] present physiological speculations concerning the implementation of the association field via horizontal connections. They have been confirmed by Jean Lorenceau et al. [43] via the method of apparent speed of fast sequences where the apparent velocity is overestimated when the successive elements are aligned in the direction of the motion path and underestimated when the motion is orthogonal to the orientation of the elements. They have also been confirmed by electrophysiological methods measuring the velocity of propagation of horizontal activation [37].
There exist several other interesting low-level vision models and psychophysical measurements that have produced similar fields of association and perceptual grouping [39, 49, 68], for an overview see [52, Chaps. 5.5, 5.6].
8.1 Three Models and Their Relation
Subsequently, we discuss three models of the association fields: horizontal exponential curves, Legendrian geodesics, and cuspless sub-Riemannian geodesics (which for many boundary conditions coincide with Petitot’s circle bundle model, as we will explain below).
With respect to the first model we recall that horizontal exponential curves [26, 57] in the sub-Riemannian manifold \((\mathrm{SE}(2),\Delta,\mathcal {G}_{\xi})\), recall Eq. (17), are given by circular spirals
for c 1≠0, g 0=(x 0,y 0,θ 0)∈SE(2) and all r≥0. If c 1=0 they are straight lines:
Clearly, these horizontal exponential curves reflect the co-circularity model [46].
To model the association fields from psychophysics and neurophysiology Petitot [52] computes “Legendrian geodesics”, [52, Chap. 6.6.4, Eq. (49)] minimizing Lagrangian \(\sqrt{1+ |y'(x)|^{2}+ |\theta'(x)|^{2}}\) under the constraint θ(x)=y′(x). This is directly relatedFootnote 11 to the sub-Riemannian geodesics in
where (SE(2))0 is the well-known nilpotent Heisenberg approximation [25, Chap. 5.4]) of SE(2), which minimize Lagrangian \(\sqrt{1+ |\theta'(x)|^{2}}\) under constraint θ(x)=y′(x). The drawback of such curves is that they are coordinate dependent and not covariantFootnote 12 with rotations and translations. Similar problems arise with B-splines which minimize Lagrangian 1+|θ′(x)|2 under constraint θ(x)=y′(x) which are commonly used in vector graphics.
To this end Petitot [52] also proposed the “circle bundle model” which has the advantage that it is coordinate independent. Its energy integral
can be expressed as \(\int_{0}^{\ell} \sqrt{1+\kappa^{2}} {\rm d}s\), where s∈[0,ℓ] denotes spatial arclength-parametrization. As long as the curve can be well-parameterized by x↦(x,y(x),θ(x)) this model coincidesFootnote 13 with sub-Riemannian geodesics.
For the explicit connections between each of the 3 mathematical models we refer to Appendix G.
8.2 Sub-Riemannian Geodesics Versus Co-circularity
In Fig. 8 we have modeled the association field with sub-Riemannian geodesics (ξ=1) and horizontal exponential curves (Eq. (72) as proposed in [9, 57]). Horizontal exponential curves are circular spirals and thereby rely on “co-circularity”, a well-known basic principle to include orientation context in image analysis, cf. [35, 46].
On the one hand, a serious drawback arising in the co-circularity model for association fields is that the only the spatial part (x fin ,y fin ) of the end-condition can be prescribed (the angular part is imposed by co-circularity), whereas with geodesics one can prescribe (x fin ,y fin ,θ fin ) (as long as the ending condition is contained within \(\mathcal{R}\)). This drawback is clearly visible in Fig. 8, where the association field (see a) in Fig. 8) typically ends in points with almost vertical tangent vectors.
On the other hand, the sub-Riemannian geodesic model has more difficulty describing the association field by Field and co-workers in the almost circular connections to the side (where the co-circularity model is reasonable). To this end we note that circles are not sub-Riemannian geodesics as the ODE \(\ddot{z}=\xi z\) does not allow z to be constant.
This difficulty, however, can be tackled by variation of ξ in Problem P curve. Our algorithm explained in Sect. 5, combined with the scaling homothety described in Remark 1.2, is well-capable of reconstructing the almost circular field line cases as well. This can be observed in Fig. 17.
8.3 Variation of ξ and Association Field Modeling
See Fig. 17 to see the effect of ξ>0 on the modeling of association fields. The larger ξ the shorter the spatial part of the paths, and the more bending we see in the vicinity of the end-points. The smaller the ξ the more circular the shape becomes at the sides of the association field model. Here we note that for these smaller values of ξ, the end-points of the more straight association field lines become problematic. In Fig. 17 one can see that when choosing ξ too small the end-point of the most straight field line even lies outside the range \(\mathcal{R}\) of the exponential map. This effect is due to the fact that the boundary \(\partial\mathcal{R}\) of the range of the exponential map, depicted in Figs. 11 and 14, scales with ξ>0 in spatial direction.
Varying of ξ 2>0 also takes into account a well-known parameter in completion; namely the area of the completed figures (see e.g. [52]). This area equals A=(x fin −x in )(y fin −y in ). By Remark 1.1 we can as well set x in =y in =θ in =0 and then as explained in Remark 1.2 solving P curve with ξ>0 amounts to solving P curve with ξ=1 with scaled end-conditions (x fin ξ,y fin ξ). In fact, such rescaling of end-conditions rescales the area as follows A↦Aξ 2.
8.4 A Conjecture and Its Motivation
The shape of the association field lines is well captured by the sub-Riemannian geodesics with ξ=1, in comparison to e.g. the exponential curves as can be observed in part b) of Fig. 8. See also Fig. 17. On top of that, the field curves of the association field end with vertical tangent vectors, and these end-points are very close to cusp points in the sub-Riemannian geodesics modeling these field lines. This can be observed both in Fig. 4 and in Fig. 17, where the sub-Riemannian geodesics ending at the end-points of the association field is nearly vertical. We will underpin this observation also mathematically in Lemma 8 and Remark 8.1.
Apparently, both the shape of the association field lines and their ending is well-expressed by the sub-Riemannian geodesics model P curve, which was proposed by Citti and Sarti [22]. Therefore, following the general idea of Petitot’s work [50] (in particular, his circle bundle model) and the results in this article on the existence set \(\mathcal{R}\) this puts the following conjecture:
Conjecture 1
The criterium in our visual system to connect two local orientations, say g 0=(x 0,y 0,θ 0)=(0,0,0) and g fin =(x fin ,y fin ,θ fin )∈SE(2), could be modeled by checking whether g fin is within the range \(\mathcal{R}\) of the exponential map.
Here we recall that from the results in [16] (summarized in Theorem 1) it follows that the set \(\mathcal{R}\) consists precisely of those points in SE(2) that are connected to the origin by a unique global minimizer of P curve. This conjecture needs further investigation by psycho-physical and neuro-physiological experiments. In any case, within the model P curve (relating to Petitot’s circle bundle model [52] and the sub-Riemannian model by Citti and Sarti [22]) a curve is optimal if and only if it is stationary. Furthermore, the sub-Riemannian geodesics strongly deviate from horizontal exponential curves even if the end condition is chosen such that the co-circularity condition is satisfied (this can be observed in item c) of Fig. 8). This discrepancy between horizontal exponential curves and cusp-less sub-Riemannian geodesics in \((\mathrm{SE}(2), \Delta,\mathcal{G}_{\xi})\) is also intruiging from the differential geometrical viewpoint: see Theorem 12 in Appendix C.
In the remainder of this section we will mathematically underpin our observation that end-points of association fields are close to cusps.
Lemma 8
Let γ be the sub-Riemannian geodesic with γ(0)=(0,0,0) and γ(ℓ)=(x fin ,y fin ,θ fin )∈SE(2) induced by the exponential map associated to the trajectory \([0,\ell]\ni s \mapsto(z(s),\dot{z}(s))\) with
Then for \(\dot{z}_{0}<0\) small we have
Furthermore, under the conditions in Eq. (74), two of the following statements
-
1.
\(\dot{z}_{0}=0\).
-
2.
γ ends with a cusp in γ(ℓ)=(x(ℓ),y(ℓ),θ(ℓ)).
-
3.
\(|\theta(\ell)|=\frac{\pi}{2}\).
imply the remaining third one.
Proof
If \(\theta_{fin}=\theta(\ell)=\frac{\pi}{2}\) then by Eq. (61) we have that \(\dot{z}_{0}=-\sqrt{1-|z(\ell)|^{2}}\), so that
The rest follows by the fact that the second statement is equivalent to |z(ℓ)|=1 and the formula for θ fin in Eq. (52). □
Remark 8.1
The curves in the association field have \(\theta_{fin}=\frac{\pi }{2}\) and relatively small initial curvature so that \(|\dot{z}_{0}|\ll 1\) and therefore they end very close to cusps, i.e. ℓ≈s max.
9 Conclusion and Future Work
Under conditions (3) on the boundary conditions cuspless sub-Riemannian geodesics in
coincide with the lifts of global minimizers of P curve (i.e. curves optimizing \(\int_{0}^{\ell}\sqrt{\kappa^{2}+ \xi^{2}} {\rm d}s\) with free length ℓ and given boundary conditions).
As the derivation of these cuspless geodesics is much less trivial than it seems (many conflicting results have appeared in the imaging literature on this topic), we derived them via 3 different mathematical approaches producing the same results from different perspectives. There are two ways to reasonably parameterize such curves, via spatial arclength and sub-Riemannian arclength and in this article we explicitly relate these parameterizations. The phase portrait in momentum space induced by sub-Riemannian arclength parametrization corresponds to (a strip within) the phase portrait of the mathematical pendulum, whereas the phase portrait in momentum space induced by spatial arclength parametrization is a hyperbolic phase portrait associated to a linear ODE for normalized curvature \(z=\kappa /\sqrt{\kappa^{2}+\xi^{2}}\). Using the latter approach we have analyzed and computed the existence set \(\mathcal{R}\) for P curve (where every stationary curve is globally minimizing!). We have also solved the boundary value problem, where the numerics is reduced to finding the unique root of a continuous explicit real-valued function on a small subset of [−1,1].
As such cuspless sub-Riemannian geodesics provide a suitable alternative to (involved and not necessarily optimal) elastica curves in computer vision. Moreover, they seem to provide a very adequate model for association fields and they are the solutions to Petitot’s circle bundle model. They also relate to previous models for association fields based on horizontal exponential curves (i.e. “co-circularity”) via the Cartan connection: Along horizontal exponential curves tangent vectors are parallel transported, whereas along sub-Riemannian geodesics momentum is parallel transported.
Our solutions, analysis and geometric control for the sub-Riemannain geodesics presented in this article form the venture point for data-dependent active contour models in SE(2) (in combination with contour-enhancement [1, 14, 22, 26, 29, 35, 36] and contour completion PDE’s [4, 8, 30, 48]) we are currently developing and applying in various applied imaging problems. Applications include extraction of the vascular tree in 2D-retinal imaging [10] and fiber-tracking in diffusion weighted magnetic resonance imaging [23, 62] (where we use sub-Riemannian geodesics in SE(3) solving the 3D-version of P curve). In these applications one replaces the constant measure on SE(2) in P curve by a data-dependent measure \(\tilde{C}:\mathrm{SE}(2) \to[1,\infty)\) in P curve, producing external force terms in the Euler-Lagrange equations that pull the geodesics towards the data.
Finally, future work will include comparison of numerical algorithms for P MEC and P curve.
Notes
More precisely, the models coincide for cuspless sub-Riemannian geodesics that can be properly parameterized by their x-coordinate.
This fact has more or less been overlooked in the previous literature on this topic.
Although not considered here the third approach also includes local optimality via Jacobi operators appearing in 2nd order variations [20, Chap. 4.1, Prop. 4.4].
The choice of T>0 does not change the set of minimizers, but only their parametrization. For this reason, it can be useful to choose a T such that the minimizer is parametrized by sub-Riemannian arclength.
In this case the Lagrangian and Hamiltonian relate to each other by the Fenchel transform on the Lie algebra of horizontal left-invariant vector fields akin to the 3D-case [30].
Usually the minimization in Eq. (16) is made in the space of Lipschitz functions, to guarantee the existence of minimizers via PMP. However, a posteriori one verifies that these minimizers are indeed C ∞.
For end-condition \((x_{fin},y_{fin},\theta_{fin}) \notin\mathcal{R}\) problem P MEC has a minimizer with internal cusp (and thereby violating the natural settings of P curve). Such a minimizer of P MEC can be approximated by smooth curves satisfying the constraints of problem P curve. In these cases P curvedoes not allow local or global minimizers, nor does it allow a stationary curve [16].
This becomes even more apparent when considering the d-dimensional extension of P curve, see [31].
For the sake of simplicity we do not index \(\widetilde{\mathrm{Exp}}\) the exponential map with the initial condition g in , as throughout this article we set g in =e=(0,0,0).
As \(\mathcal{D}\) and \(\mathcal{R}\) are not open sets within the standard topologies on the embedding spaces \(T_{e}(\mathrm{SE}(2)) \times \mathbb{R}^{+}\) and \(\mathbb{R}^{2} \times S^{1}\). These subspace topologies do not coincide with the induced topology imposed by the embedding via the identity map, as such identity map is not continuous. However, with respect to the subspace topologies the set \(\mathcal{D}\), respectively \(\mathcal{R}\) are open sets and the homeomorphism \(\widetilde{\mathrm{Exp}}: \mathcal{D} \to\mathcal{R}\) is well-defined.
The dual basis in (SE(2))0 is equal to \(({\rm d}\theta, {\rm d}x,- \theta\, {\rm d}x+ {\rm d}y)\) and thereby the sub-Riemannian metric on (SE(2))0 does not include the |y′(x)|2 term.
The corresponding minimization problem (and induced sub-Riemannian distance) is left invariant in (SE(2))0 and not left-invariant in SE(2).
Within the association field model P curve scaling of the end-conditions amounts to scaling of ξ.
References
Agrachev, A., Boscain, U., Gauthier, J.-P., Rossi, F.: The intrinsic hypoelliptic Laplacian and its heat kernel on unimodular Lie groups. J. Funct. Anal. 256, 2621–2655 (2009)
Agrachev, A.: Exponential mappings for contact sub-Riemannian structures. J. Dyn. Control Syst. 2, 321–358 (1996)
Agrachev, A.A., Sachkov, Yu.L.: Control Theory from the Geometric Viewpoint. Encyclopedia of Mathematical Sciences, vol. 87. Springer, Berlin (2004)
van Almsick, M.: Context models of lines and contours. University of Technology, Department of Biomedical Engineering (2007). http://alexandria.tue.nl/extra2/200711652.pdf
Ambrosio, L., Masnou, S.: On an Variational Problem Arising in Image Reconstruction vol. 147. Birkhauser, Basel (2004)
Ardentov, A., Sachkov, Y.: Solution of Euler’s elastic problem. Avtom. Telemeh. 4, 78–88 (2009) (in Russian). English translation in Automation and Remote Control
Aubin, T.: A Course in Differential Geometry. Graduate Studies in Mathematics, vol. 27. AMS, Providance (2000)
August, J.: The curve indicator random field. PhD Thesis http://www.cs.cmu.edu/~jonas/
Barbieri, D., Citti, G., Sanguinetti, G., Sarti, A.: An uncertainty principle underlying the functional architecture of V1. J. Physiol. Paris. Accepted for publication. To appear in 2012
Bekkers, E., Duits, R., ter Haar Romeny, B.M., Beerenschot, T.: A new retinal vessel tracking method based on invertible orientation scores. Submitted. See arXiv
Ben-Yosef, G., Ben-Shahar, O.: A tangent bundle theory for visual curve completion. IEEE Trans. Pattern Anal. Mach. Intell. 34(7), 1263–1280 (2012). (3), 307–331 (1988)
Boscain, U., Charlot, G., Rossi, F.: Existence of planar curves minimizing length and curvature. Proc. Steklov Inst. Math. 270(1), 43–56 (2010)
Boscain, U., Rossi, F.: Projective Reeds-Shepp car on S 2 with quadratic cost. ESAIM Control Optim. Calc. Var. 16(2), 275–297 (2010)
Boscain, U., Duplaix, J., Gauthier, J.P., Rossi, F.: Anthropomorphic image reconstruction via hypoelliptic diffusion. SIAM J. Control Optim. 50, 1309–1336 (2012)
Boscain, U., Duits, R., Rossi, F., Sachkov, Y.: Optimal control for reconstruction of curves without cusps. In: IEEE Conference on Decision and Control (CDC), Maui, Hawaii, pp. 7679–7684 (2012)
Boscain, U., Duits, R., Rossi, F., Sachkov, Y.: Curve cuspless reconstruction via sub-Riemannian geometry. To appear in ESAIM Control Optim. Calc. Var. (2014). arXiv:1203.3089
Bosking, W.H., et al.: Orientation selectivity and the arrangement of horizontal connections in tree shrew striate cortex. J. Neurosci. 17(6), 2112–2127 (1997)
Bruckstein, A., Holt, R., Netravali, A.: Discrete elastica. Appl. Anal. 78, 453–485 (2001)
Bryant, R., Griffiths, P.: Reduction for constrained variational problems and \((1/2)\int \kappa^{2} {\rm ds}\). Am. J. Math. 108(3), 525–570 (1986)
Bryant, R., Griffiths, P., Grossman, D.: Exterior Differential Systems and Euler-Lagrange Partial Differential Equations. Chicago Lectures in Mathematics (2003)
Chan, T.F., Kang, S.-H., Shen, J.: Euler’s elastica and curvature based inpaintings. SIAM J. Appl. Math. 63, 564–594 (2002)
Citti, G., Sarti, A.: A cortical based model of perceptual completion in the roto-translation space. J. Math. Imaging Vis. 24, 307–326 (2006)
Dela Haije, T.C.J., Duits, R., Tax, C.M.W.: Sharpening fibers in diffusion weighted MRI via erosion. In: Visualization and Processing of Tensors and Higher Order Descriptors for Multi-Valued Data. Dagstuhl Seminar 11501. Accepted for publication www.bmia.bmt.tue.nl/people/RDuits/DDT.pdf
Duits, R., van Almsick, M.: The explicit solutions of linear left-invariant second order stochastic evolution equations on the 2D Euclidean motion group. Q. Appl. Math. 66, 27–67 (2008)
Duits, R., Franken, E.M.: Left-invariant parabolic evolutions on SE(2) and contour enhancement via invertible orientation scores, Part I: Linear left-invariant diffusion equations on SE(2). Q. Appl. Math. 68, 293–331 (2010)
Duits, R., Franken, E.M.: 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, 255–292 (2010)
Duits, R., Franken, E.M.: Left-invariant stochastic evolution equations on SE(2) and its applications to contour enhancement and contour completion via invertible orientation scores. arXiv:0711.0951v4. Also available as CASA report nr. 35 (2007) www.win.tue.nl/casa/research/casareports/2007.html
Duits, R., Franken, E.: Line enhancement and completion via left-invariant scale spaces on SE(2). In: Scale Space and Variational Methods in Computer Vision. Lecture Notes in Computer Science, vol. 5567, pp. 795–807. Springer, Berlin (2009)
Duits, R., Franken, E.M.: The explicit solutions of linear left-invariant second order stochastic evolution equations on the 2d-Euclidean motion group. Int. J. Comput. Vis. 92(3), 231–264 (2011). See http://www.springerlink.com/content/511j713042064t35/
Duits, R., Dela Haije, T.C.J., Creusen, E.J., Ghosh, A.: Morphological and linear scale spaces for fiber enhancement in DW-MRI. J. Math. Imaging Vis. To appear in 2013
Duits, R., Ghosh, A., Dela Haije, T.C.J., Sackov, Y.L.: Cuspless sub-Riemannian geodesics within the Euclidean motion group SE(d). In: Citti, G., Sarti, A. et al.(eds.) Neurogeometry. Springer, Berlin (2014). www.bmia.bmt.tue.nl/people/RDuits/Bookchapter.pdf
Ermentrout, G.B., Cowan, J.D.: A mathematical theory of visual hallucinations. Kybernetic 34(34), 137–150 (1979)
Euler, L.: Methodus inveniedi lineas curvas maximi minimive proprietate gaudentes, sive solutio problematis isoperimitrici latissimo sensu accepti. Lausanne, Geneva (1744)
Field, D.J., Hayes, A., Hess, R.F.: Contour integration by the human visual system: evidence for a local “association field”. Vis. Res. 33(2), 173–193 (1993)
Franken, E.M.: Enhancement of crossing elongated structures in images. Ph.D. thesis, Eindhoven University of Technology, Eindhoven (2008) http://www.bmi2.bmt.tue.nl/Image-Analysis/People/EFranken/PhDThesisErikFranken.pdf
Franken, E.M., Duits, R.: Crossing-preserving coherence-enhancing diffusion on invertible orienattion scores. Int. J. Comput. Vis. 85(3), 253–278 (2009)
Frégnac, Y., Shulz, D.: Activity-dependent regulation of receptive field properties of cat area 17 by supervised Hebbain learning. J. Neurobiol. 41(1), 69–82 (1999)
Grobman, D.M.: Homeomorphisms of systems of differential equations. Dokl. Akad. Nauk SSSR 128, 880–881 (1959)
Grossberg, S., Mingolla, E.: Neural dynamics of form perception: boundary completion, illusory figures and neon color spreading. Psychol. Rev. 92, 173–211 (1985)
Hladky, R.K., Pauls, S.D.: Minimal surfaces in the Roto-Translation group with applications to a neuro-biological image completion model. J. Math. Imaging Vis. 36, 1–27 (2010)
Hoffman, W.C.: The visual cortex is a contact bundle. Appl. Math. Comput. 32, 137–167 (1989)
Horn, B.K.P.: The curves of least energy. ACM Trans. Math. Softw. 9(4), 441–460 (1983)
Georges, S., Series, P., Fregnac, Y., Lorenceau, J.: Orientation-dependent modulation of apparent speed: psychophysical evidence. Vis. Res. 42, 2557–2572 (2002)
Marsden, J., Weinstein, A.: Reduction of symplectic manifolds with symmetry. Rep. Math. Phys. 5, 121–130 (1974)
Mashtakov, A.P., Ardentov, A.A., Sachkov, Y.L.: Parallel algorithm and software for image inpainting via sub-Riemannian minimizers on the group of rototranslations. Numer. Methods, Theory Appl. 6(1), 95–115 (2013)
Medioni, G., Lee, M.-S., Tang, C.-K.: A Computational Framework for Segmentation and Grouping. Elsevier Science, Amsterdam (2000)
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, 380–399 (2010)
Mumford, D.: Elastica and computer vision. In: Algebraic Geometry and Its Applications, pp. 491–506. Springer, Berlin (1994)
Parent, P., Zucker, S.W.: Trace interference, curvature consistency, and curve detection. IEEE Trans. Pattern Anal. Math. Intell. II 8, 823–939 (1989)
Petitot, J.: Vers une Neuro-géomètrie. Fibrations corticales, structures de contact et contours subjectifs modaux. Math. Inf. Sci. Humaines 145, 5–101 (1999)
Petitot, J.: Neurogéomètrie de la vision—Modèles mathématiques et physiques des architectures fonctionnelles. Les Éditions de l’École Polythecnique, Palaiseau (2008)
Petitot, J.: The neurogeometry of pinwheels as a sub-Riemannian contact structure. J. Physiol., Paris 97, 265–309 (2003)
Pontryagin, L.S., Boltyansij, V.G., Gamkrelidze, R.V., Mishchenko, E.F.: The Mathematical Theory of Optimal Processes. Pergamon Press, Oxford (1964)
Sachkov, Y.L.: Conjugate points in the Euler elastic problem. J. Dyn. Control Syst. 14(3), 409–439 (2008)
Sachkov, Y.L.: Conjugate and cut time in the sub-Riemannian problem on the group of motions of a plane. ESAIM Control Optim. Calc. Var. 16(4), 1018–1039 (2010)
Sachkov, Y.L.: Cut locus and optimal synthesis in the sub-Riemannian problem on the group of motions of a plane. ESAIM Control Optim. Calc. Var. 17 / Number 2, 293–321 (2011)
Sanguinetti, G., Citti, G., Sarti, A.: A model of natural image edge co-occurance in the rototranslation group. J. Vis. 10(14), 1–16 (2010)
Sarti, A., Citti, G.: A cortical based model of perceptual completion in the Roto-Translation space. In: Proceeding of the Workshop on Second Order Subelliptic Equations and Applications, Cortona (2003)
Spivak, M.: Differntial geometry, vol. II. Publish or Perish, (1975)
Tai, X.-C., Hahn, J., Chung, G.S.: A fast algorithm for Euler’s elastica model using augmented Lagrangian method. SIAM J. Imaging Sci. 4(1), 313–344 (2011)
Tai, X.-C., Hahn, J., Chung, G.S.: Fast algorithms for p-elastica energy with the application to image inpainting and curve reconstruction. In: Proc. of the Third international conference on Scale Space and Variational Methods in Computer Vision. LNCS, pp. 169–182 (2011)
Tax, C., Duits, R., Vilanova, A., Leemans, A., Ossenblok, P.: Improving and evaluating the reliability of white matter fiber pathways for presurgical planning: application to temporal lobe epilepsy. Submitted. See www.bmia.bmt.tue.nl/people/RDuits/TaxDuitsetal.pdf
Thornber, K.K., Williams, L.R.: Analytic solution of stochastic completion fields. Biol. Cybern. 75, 141–151 (1996)
Thornber, K.K., Williams, L.R.: Characterizing the distribution of completion shapes with corners using a mixture of random processes. Pattern Recognit. 33, 543–553 (2000)
Ullman, S.: Filling in the gaps: the shape of subjective contours and a model for their generation. Biol. Cybern. 25, 1–6 (1976)
Sachkov, Y.: Maxwell strata in the Euler elastic problem. J. Dyn. Control Syst. 14(2), 169–234 (2008)
Wittich, O.: An explicit local uniform bound on Brownian bridges. Stat. Probab. Lett. 73(1), 51–56 (2005)
Zucker, S.W., David, C., Dobbins, A., Iverson, L.: The organization of curve detection: coarse tangent fields and fine spline covering. In: Proc. of the 2nd Int. Conf. on Computer Vision. IEEE, New York (1988)
Acknowledgements
The authors wish to thank Tom Dela Haije and Arpan Ghosh, Eindhoven University of Technology, for fruitful discussion, fast numerical integration of the initial value problem and their assistance in creating Figs. 7, 11 and 14. The authors gratefully acknowledge European Research Council, ERC StG 2009 “GeCoMethods” contract number 239748, ERC StG 2013 “Lie Analysis” contract number 335555, the ANR “GCM” program “Blanc-CSD” project number NT09-504490, the DIGITEO project “CONGEO” and the Russian Foundation for Basic Research (project no. 12-01-00913-a), and the Ministry of Education and Science of Russia within the federal program “Scientific and Scientific-Pedagogical Personnel of Innovative Russia” (contract no. 8209), for financial support.
The research leading to the results of this article has received funding from the European Research Council under the European Community’s 7th Framework Programme (FP7/2007–2014)/ERC grant agreement Nos. 335555 and 239748.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix A: Basic Derivation of the ODE for Curvature Along Sub-Riemannian Geodesics
We derive normalized curvature \(z=\frac{\kappa}{\sqrt{\kappa^{2}+\xi^{2}}}\), recall Eq. (77), along stationary curves of the functional
with \(\mathbf{x}:[0,\ell] \to\mathbb{R}^{2}\) twice differentiable. Here we apply Mumford’s approach to elastica [48] to cuspless sub-Riemannian geodesics instead.
The energy after horizontal curve deformation
with h>0 and \(\mathbf{n}(s)=\ddot{\mathbf{x}}(s)\), \(\delta :[0,\ell] \to \mathbb{R}\) infinitely differentiable and vanishing at the boundary (i.e. \(\delta\in\mathcal{D}([0,\ell])\)), becomes
where we used \(\sqrt{1+x}=1 +\frac{1}{2} x + O(x^{2})\) and
Now \(\mathcal{D}([0,\ell])\) is dense within \(\mathbb{L}_{2}([0,\ell ])\) so for stationary curves one must have \(\ddot{z}(s)=\xi z(s) \Leftrightarrow\)
This gives us the preservation law
and curvature \(\kappa^{2}(s)= \frac{\xi^{2} (z(s))^{2}}{1-(z(s))^{2}}\) with
with \(z_{0}=\frac{\kappa_{0}}{\sqrt{\xi^{2} +\kappa_{0}^{2}}}\), \(\dot{z}_{0}=\frac{\xi^{2} \dot{\kappa}_{0}}{(\xi^{2} + \kappa _{0}^{2})^{\frac{3}{2}}}\). These expressions are only valid for \(s \in[0,s_{\mathrm{max}}(z_{0},\dot{z}_{0}))\) where
This last expression (78) denotes the spatial length towards a cusp (where E and the sub-Riemannian distance d, recall Eq. (16), remain finite despite the fact that curvature tends to ∞ when approaching a cusp).
Appendix B: Explicit Expression of Geodesics in Terms of Elliptic Functions
We will restrict ourselves to the case ξ=1 as we recall from the introduction (Remark 1.2) that the general case follows by spatial scaling.
2.1 B.1 The geodesics for P curve parameterized by spatial arclength
For P curve geodesics (x(s),θ(s)) are given by
with \(z(s)=z_{0} \cosh(s) + \dot{z}_{0} \sinh(s)\), z 0∈[−1,1], \(\dot{z}_{0} \in\mathbb{R}\) and \(\mathfrak{c}=\sqrt{1-|z_{0}|^{2}+|\dot{z}_{0}|^{2}}\). Geodesics are defined for s∈[0,s max ], with \(s_{max}=\log(\frac {1+\mathfrak{c}}{|z_{0}+ \dot{z}_{0}|} )\).
Remark
Lemma 4 expresses the integral for \(\tilde{y}\) in a singe elliptic function.
2.2 B.2 The Geodesics for P MEC (and P curve) Parameterized by Sub-Riemannian Arclength
Here we distinguish between different cases in the phase portrait of the mathematical pendulum, recall Fig. 9.
In the cases \(C_{1}=C_{1}^{1} \cup C_{1}^{0}\) (where \(\mathfrak{c}<1\)), \(C_{2}=C_{2}^{+} \cup C_{2}^{-}\) (where \(\mathfrak{c}>1\)), the geodesics of P MEC are expressed [47] in sub-Riemannian arc-length t are parameterized by Jacobian functions \(\mathrm{cn\,}\), \(\mathrm{sn\, }\), \(\mathrm{dn\,}\), \({\mathrm{E\,}}\) as follows.
Case C 1:
Case C 2:
In the critical case \(C_{3}= C_{3}^{1+}\cup C_{3}^{1-} \cup C_{3}^{0-} \cup C_{3}^{0+}\) (where \(\mathfrak{c}=1\)) geodesics are parameterized by hyperbolic functions:
Here (φ,k) are action-angle coordinates in the state space of the pendulum Eq. (10) that rectify its flow: \(\dot{\varphi}= 1\), \(\dot{k} = 0\). Set s 1=sign(cos(ν/2)), s 2=sign(c)∈{−1,1}. Using Jacobi’s functions \(\mathrm{sn\,}(\varphi,k), \mathrm{dn\, }(\varphi,k), \mathrm{cn\,} (\varphi,k)\) and elliptic integrals of the first kind K(k), the explicit dependence of (φ,k) on (ν,c), cf. [47], is given by
-
Case (ν,c)∈C 1:
$$ \begin{array}{l} k=\sqrt{\sin^{2}(\nu/2)+ c^2} \in(0,1), \\ \sin(\nu/2)= s_{1} k \mathrm{sn\,}(\varphi,k), \\ \cos(\nu/2)= s_{1} \mathrm{dn\,}(\varphi,k), \\ c/2 = k \mathrm{cn\,}(\varphi,k), \varphi\in[0,4K(k)]. \end{array} $$(80) -
Case (ν,c)∈C 2:
$$ \begin{array}{l} k=1/\sqrt{\sin^{2}(\nu/2)+ c^2} \in(0,1), \\ \sin(\nu/2)= s_{2} \mathrm{sn\,}(\varphi/k,k), \\ \cos(\nu/2)= s_{1} \mathrm{cn\,}(\varphi/k,k), \\ c/2 = (s_2/k) \mathrm{dn\,}(\varphi/k,k), \varphi\in[0,4K(k)]. \end{array} $$(81) -
Case (ν,c)∈C 3:
$$ \begin{array}{l} k=1, \\ \sin(\nu/2)= s_{1}s_{2} \tanh(\varphi), \\ \cos(\nu/2)= s_{1}/ \cosh(\varphi), \\ c/2 = s_{2}/\cosh(\varphi) , \varphi\in\mathbb{R}. \end{array} $$(82)
Remark 11.1
The geodesics of P MEC are defined for \(t \in \mathbb{R}\) and every pair of points in SE(2) can be connected by a smooth geodesic.
Appendix C: The Cartan Connection and Its Relation to Geodesics and Exponential Curves
In this section we show that last three equations of the Pfaffian system Eq. (28) can be summarized in a single simple formula \(\nabla_{\dot{\gamma}} p=0\), where ∇ denotes the Cartan connection on the co-tangent bundle T ∗(SE(2)) of SE(2).
In [26] we have shown that the principle fiber bundle P Y =(SE(2),SE(2)/Y,π,R) with projection π(g)=[g]=gY, g∈SE(2), base manifold SE(2)/Y and right-action R g (h)=hg and structure group \(Y=\{(0,y,0)\mid y \in\mathbb{R}\}\), coincides with the sub-Riemannian manifold \((\mathrm{SE}(2),\Delta, \mathcal{G}_{\xi})\). We equip P Y with Cartan-Maurer form ω=(L 0,−y,0)∗ (i.e. the push-forward of the left-multiplication of the structure group acting on SE(2)). In our moving frame of reference this Lie-algebra-valued 1-form reads as
for all left-invariant vector fields \(X \in\mathcal{L}(\mathrm {SE}(2))\). By definition the horizontal part of the tangent bundle on SE(2) is given by
which relates (P Y ,ω) to the sub-Riemannian manifold \((\mathrm{SE}(2),\mathrm{Ker}(\omega^{3}),\mathcal{G}_{\beta})\).
The Maurer connection form ω induces the following connection form on the associated vector bundle \(\mathrm{SE}(2) \times_{\widetilde{\mathrm{Ad}}} \mathcal {L}(\mathrm{SE}(2)) \)
with \(\widetilde{\mathrm{Ad}}={\rm d}\mathcal{R} \circ\mathrm{Ad} \circ\omega\) the adjoint action of SE(2) on the Lie algebra \(\mathcal{L}(\mathrm{SE}(2))\) of left-invariant vector fields, whose push-forward equals \(\widetilde{\mathrm {ad}}(A_{3})=[\cdot,A_{3}]= -\mathcal{A}_{2} \otimes\omega^{1}\), since \(c_{13}^{2}=-1\).
Connection form \(\tilde{\omega}\) induces the following matrix-valued 1-form
on the frame-bundle, cf. [59, pp. 353, 359], where the sections are moving frames.
Finally, the corresponding Cartan connection \(D=d+\overline{\omega}\) on the tangent bundle T(SE(2)) with \(\overline{\omega }(\sum_{k=1}^{3}a^{k} \mathcal{A}_{k})=a^{k} \sum_{j=1}^{3} \tilde {\omega }^{j}_{k}(\cdot) \mathcal{A}_{j}= a^{3} \omega^{1}(\cdot) \mathcal {A}_{2}\) and note that \(\tilde{\omega}\) vanishes when restricted to \(\mathcal{H}\) (as this implies a 3=0). Consequently, the only horizontal auto-parallel curves (i.e. \(D_{\dot{\gamma}} \dot{\gamma}=0\)) in T(SE(2)) passing through g 0∈SE(2) at t=0 are given by
with c 1 and c 2 constant.
The construction: Cartan-Maurer form on principal fiber bundle → connection form on associated vector bundle → connection form on frame bundle → connection form on tangent bundle, can also be applied to structure group SE(2) acting on SE(2) from the right. Then we find P=(SE(2),SE(2)/SE(2)≡{e},π,R), π(g)=e with Cartan-Maurer form \(\omega(X_{g})= \sum_{i=1}^{3} \langle\omega ^{i}\vert_{g}, X_{g}\rangle A_{i}\), and \(\tilde{\omega}= \mathcal{A}_{2} \otimes\omega^{3} \wedge\omega ^{1} + \mathcal{A}_{3} \otimes\omega^{1} \wedge\omega^{2} \) and we obtain (for details see [26, Thm. 3.8])
Definition 3
The Cartan connection ∇ on the tangent bundle (SE(2),T(SE(2))) is given by the covariant derivatives
with \(\dot{a}^{k}(t)= \dot{\gamma}^{i}(t) (\mathcal {A}_{i}\vert_{\gamma(t)} a^{k})\), for all tangent vectors \(X \vert_{\gamma(t)} = \dot{\gamma }^{i}(t) \mathcal{A}_{i}\vert_{\gamma(t)}\) along a curve t↦γ(t)∈SE(2) and all sections \(\mu(\gamma(t))=\sum_{k=1}^{3}a^{k}(\gamma(t)) \mathcal {A}_{k}(\gamma(t))\). The Christoffel symbols in (88) coincide with the structure constants of the Lie-algebra
Theorem 12
Exponential curves are auto-parallel with respect to the Cartan connection ∇. Horizontal exponential curves are auto-parallel with respect to Cartan connection D. In fact,
where Exp:T e (SE(2))→SE(2) denotes the exponential map from Lie algebra to Lie group. Along an exponential curve \(\gamma (t)=\mathrm{Exp} (t \sum_{i=1}^{3} c^{i} A_{i} ) \gamma(0)\), tangent vectors are covariantly constant. Along a geodesic one has covariantly constant momentum, i.e.
Proof
With respect to the first part of the theorem, we note that the left-invariant vector-fields on SE(2) are obtained by T e (SE(2)) by means of the infinitesimal generator of the right-regular representation acting on \(C^{1}(\mathrm{SE}(2),\mathbb {R})\) via
Via the identity \(e^{t {\rm d}\mathcal{R}(c^{i}A_{i})}=\mathcal{R}_{e^{\sum _{i=1}^{3}t(c^{i}A_{i})}}\) and application of the method of characteristics to linear, left-invariant convection systems on \(C^{1}(\mathrm{SE}(2),\mathbb{R})\)
with d∈{2,3}, we find its unique solutions \(W(g,t)=\mathcal{R}_{e^{-\sum_{i=1}^{d}t(c^{i}A_{i})}}(U)(g)= U(g e^{-t\sum_{i=1}^{d}c^{i}A_{i}})\). Thereby, for any C 1-curve \(\gamma:\mathbb{R}\to\mathrm{SE}(2)\) one has
Now, as the Christoffel symbols are anti-symmetric (see Eq. (89)) we have
which implies Eq. (90). With respect to Eq. (91) we note that by duality
with \(\mathcal{A}=\sum_{i=1}^{d}a^{i} \mathcal{A}_{i}\) and \(p=\sum _{i=1}^{d}\lambda_{i} \omega^{i}\), covariant derivatives in the tangent bundle (Definition 3) induce covariant derivatives in the cotangent bundle (by inversion of the Christoffel symbols \(c_{ji}^{k} \mapsto c_{ij}^{k}\)):
Now Eq. (94) and Eq. (31) imply Eq. (91). □
Appendix D: Canonical ODE’s via the Pontryagin Maximum Principle (PMP)
For details, proof and formal formulation of the Pontryagin maximum principle see [3]. Here we will apply the principle to our problems of interest (P MEC and P curve), without giving the general formulation. Furthermore, we will not rely on Hamiltonian vector fields on the co-tangent bundle. For details see [3, 47], [31, Thm. 1 & App. A].
4.1 D.1 Application of PMP to P MEC After Squaring the Lagrangian and Constraining to Fixed Length Using t-Parametrization
Via the Cauchy-Schwartz inequality it can be shown that P MEC is equivalent to the problem where one finds in the space of L ∞ controls \(u(\cdot),v(\cdot):[0,\ell]\to\mathbb{R}\), the solution of
where we constrain the total time T in such a way that the curve is parameterized by sub-Riemannian arclength: \(\xi^{2} \tilde{u}^{2}(t) +\tilde{v}^{2}(t)=1\).
The “control dependent Hamiltonian” equals
which provides (maximized) Hamiltonian
Here momentum is expressed in fixed coordinates
The vertical part of the canonical equations is now given by
which may be re-expressed in moving coordinates (again using sub-Riemannian arclength parametrization)
This ODE-system can be expressed in spatial arc-length parametrization (before cusp situations, i.e. for initial condition (x in ,y in ,θ in )=(0,0,0) and end condition \((x_{in},y_{in},\theta_{in}) \in\mathcal{R}\)) yielding
which coincides with the canonical equation for P curve.
The horizontal part of the PMP ODE is given right after Eq. (18) expressed in fixed coordinates, see also [16]. Expressed in our moving frame of reference, this horizontal part is given by \(\dot{\gamma}=\sum_{i=1}^{2}\lambda_{i}\mathcal{A}_{i}\vert_{\gamma}\), see [31].
4.2 D.2 Application of PMP to P curve with free Length Problem Using s-Parametrization
When we apply PMP directly to P curve and use spatial arc-length parametrization we obtain “control dependent Hamiltonian”
Optimization over all controls produces the (maximized) Hamiltonian
which vanishes since the total length is free [3, Thm. 12.8]. As a result we find
and thereby \(\ddot{z}(s)=\ddot{\lambda}_{1}(s)=\ddot {p}_{1}(s)=p_{1}(s)=\lambda_{1}(s)=z(s)\) which coincides with the result in Appendix A.
Appendix E: Proof of Theorem 9
First of all, see Fig. 11 (top view along θ) for a graphical validation of the statement. Without loss of generality we assume y fin <0. The surface of geodesics departing from a cusp and the surface of geodesics ending at a cusp intersect each other only at θ fin =0 (cases z(l)=−z(0)=±1 and \(\mathfrak{c}>1\)) or at |θ fin |=π (cases z(l)=z(0)=±1 and \(\mathfrak{c}>1\)). This directly follows by the formula for θ fin in Eq. (52). Next we show that if a geodesic starts with a cusp it will have x fin <2. This follows by the formula for x fin in Eq. (52) where the second term vanished if |z 0|=1 and where the first term is less than 2. For if z(ℓ)=−z(0)=±1 with \(|\dot{z}_{0}|>1\) we have |x fin |<|z(ℓ)−1|≤2, whereas if \(|\dot{z_{0}}|<1\) and z(ℓ)=z(0)=±1 we again have \(\frac{x_{fin}}{2} \leq\frac {x_{fin}^{2}+\sin^{2}(\theta_{fin})}{2 x_{fin}} < 1\). More precisely, a geodesic starting with a cusp will satisfy Eq. (65), since the maximum value for x fin under the condition |z 0|=1 is obtained at |z(ℓ)|=1=|z 0| and in these cases we find \(|\dot {z}_{0}|=\frac{x_{fin}}{2}\) and \(|y_{fin}|=-x_{fin} i E (i \, \mathrm{arcsinh}\, \frac{x_{fin}}{\sqrt{4-x_{fin}^{2}}}, 1-\frac {4}{x_{fin}^{2}} )\). Now assume Eq. (65) holds and consider a geodesic γ:[0,ℓ]→SE(2) and consider the corresponding trajectory in phase space and assume that the trajectory has \(\mathfrak{c}<1\) and \(\dot{z}_{0}<-z_{0}\), then \(\mathrm{sign}(z(s))=\mathrm{sign}(\kappa(s))=\mathrm {sign}(\dot{\theta}(s))=-1\) is for all s∈[0,ℓ] and minimum value for |θ(s)| is obtained s=ℓ. We can extend this geodesic to [s min ,s max ] with |z(s min )|=1 and s min ≤0. Then the extended geodesic starts and ends in a cusp and we have \(\theta_{fin} \in[ \theta_{\mathrm{endcusp}}(x_{fin},y_{fin}), \theta_{\mathrm {begincusp}}(x_{fin},y_{fin})] \subset\mathbb{R}^{-}\) due to the monotonic decrease of s↦θ(s). This can be observed in Fig. 11 where all extended orbits in \(\mathcal{C}_{1}^{0}\) go down in theta direction converging towards the θ-minimum at the blue surface at s↑s max .
For geodesics with \(\mathfrak{c}>1\) the curvature \(\kappa(s)=\dot {\theta}(s)\) can switch sign only once at s B where z(s B )=0. By the assumption y fin ≤0 we can restrict ourselves to the non-trivial case z 0<0, \(\dot{z}_{0}>0\) and \(\mathfrak{c}>1\), i.e. (\((z_{0},\dot{z}_{0}) \in C_{2}^{+}\)) where we assume z(ℓ)>0 in order to consider the non-straightforward case where the curvature switches sign. Again we extend the geodesic to [s min ,s max ] (starting from a cusp ending at a cusp). The extended geodesic’s angle initially decreases initially on [0,s B ], but then by reflection symmetry it will gain more than the initial decrease during s∈[s B ,s max ]. Thereby, if a geodesics is within \(\mathcal {C}_{2}^{+}\) its extension will stay in \(\mathcal{C}_{2}^{+}\), see Fig. 11 (as it cannot cross the critical surface) and converge (upwards in θ) towards the blue surface (where geodesics end with a cusp) and we have θ fin ∈[θ endcusp(x fin ,y fin ),θ begincusp(x fin ,y fin )]. Conclusion, if the bound (65) holds \((x_{fin},y_{fin}) \in \mathbb{R} ^{2}\) can be connected both with a geodesic starting with a cusp (at (0,0) and a geodesic ending in a cusp at (x fin ,y fin ), then the end-angles of these curves determine the cone of reachable orientations. In case Eq. (65) does not hold, there are no geodesics starting from a cusp that reach (x fin ,y fin ) and in these cases the cone of reachable orientations is just bounded by the end-angles of two geodesics ending in a cusp (the two blue surfaces in Fig. 11). □
Appendix F: Proof of Theorem 6
Within this proof we will rely on previous results by Sachkov in [47, 55, 56]. As these works rely on sub-Riemannian arclength parametrization and the pendulum phase portrait (Fig. 9), we will do the same in this proof. To this end (via Lemma 1) we re-express domain and range of the exponential map \(\widetilde {\mathrm{Exp}}\) of P curve in this parametrization
where \(t_{cusp}(p_{0})=t(s_{max}(z_{0},\dot{z}_{0}))\) denotes sub-Riemannian arclength until the first cusp-time formally defined by
The function p 0↦t cusp (p 0) is continuous on C and it is a uniform lower bound [55] for the continuous function p 0↦t cut (p 0) which assigns to each initial momentum the corresponding time where global optimality of P MEC is lost along the corresponding stationary curve.
Now that the preliminaries are done, let us start with the proof.
We will first show the mapping \(\widetilde{\mathrm{Exp}}: \mathring {\mathcal {D}} \to\mathring{\mathcal{R}}\) is a diffeomorphism. Consider to this end the set \(\check{N} = \{(p_{0},t) \in C \times\mathbb{R}^{+} \mid t < t_{cut}(p_{0})\}\). Since the function t cut :C→(0,∞] is continuous, the set \(\check{N}\) is open. Let \(\widetilde{\mathrm{EXP}}\) denote the exponential map of P MEC. It follows from Th. 3.1 [55] that the mapping \(\widetilde{\mathrm{EXP}}\vert_{\check{N}}\) is injective. Moreover, it was shown in Th. 2.5 [56] that this mapping is a local diffeomorphism. Thus the restriction \(\widetilde{\mathrm{EXP}}\vert_{\check{N}}\) is a global diffeomorphism. Now since t cusp (p 0)≤t cut (p 0), we have \(\mathring{\mathcal{D}} \subset\check{N}\). So \(\widetilde{\mathrm{Exp}}\vert_{\mathring{\mathcal{D}}}\equiv \widetilde{\mathrm{EXP}}\vert_{\mathring{\mathcal{D}}}\) is a global diffeomorphism as well.
Regarding the homeomorphic property we note that injectivity of \(\widetilde{\mathrm{EXP}}\vert_{\check{N}}\) implies injectivity of \(\widetilde{\mathrm{Exp}}\vert_{\check{N} \cap\mathcal{D}}\equiv\widetilde{\textrm{EXP}}\vert_{\check{N} \cap\mathcal{D}}\). Moreover, we have
where K=K(k) denotes the elliptic integral of the first kind (recall Appendix B). Now its was shown in [56] that the exponential map restricted to S k map S k , for k=1,2, diffeomorphically onto the corresponding ranges. Now as these ranges are disjoint, we have that \(\widetilde{\mathrm{Exp}}\vert_{\mathcal{D}}\) is bijective, with a continuous inverse.
Regarding the final remark: Consider a sequence \((g_{n})_{n \in\mathbb{N}}\) in \(\mathcal{R}\) that converges to some \(g \in\mathrm{SE}(2) \setminus\mathring{\mathcal{R}}\). We must show \(g=(x,y,\theta) \in\mathfrak{l}\) or g is the end-point of a geodesic starting with a cups or g is the end-point of a geodesic ending at a cusp.
By the homeomorphic and diffeomorphic properties of \(\widetilde {\mathrm{Exp}}\) this sequence relates to a sequence in the phase portrait converging to a point \((\nu,c,t) \in\partial\mathcal{D}\). Let us consider all possible cases:
-
If (ν,c)=(0,0) or (ν,c)=(2π,0) we have \(g \in\mathfrak{l}\).
-
If (ν,c)=(0,c) with c>0 or if (ν,c)=(2π,c) with c<0 (i.e. the cases corresponding to the red lines in the phase portrait in Fig. 11b), this means g is the end-point of a geodesic starting with a cusp.
-
If (ν,c)=(0,c) with c>0 or if (ν,c)=(2π,c) with c<0 (i.e. the cases corresponding to the blue lines in the phase portrait in Fig. 11b), this means g is the end-point of a geodesic ending with a cusp.
Appendix G: Definition of Cusps, Geodesics and Association Field (Models)
We use the following definition of a geodesic.
Definition 4
A geodesic of P curve (respectively P MEC) is a stationary curve γ of the corresponding geometric control problem formulated in Sect. 1.1. Geodesics of P curve are called cuspless sub-Riemannian geodesics.
Remark
It can be shown that such a geodesic γ has the property that for every sufficiently small interval I=(t 1,t 2) in the domain of such a curve the restriction γ| I is a minimizer between γ(t 1) and γ(t 2).
Smooth sub-Riemannian geodesics in P MEC may exhibit cusps when projected to the spatial plane, as we recall from Fig. 2. Roughly speaking, cusps are singular points in which spatial velocity changes its sign.
Definition 5
A curve trajectory \((\gamma(\cdot), \tilde{u}(\cdot), \tilde {v}(\cdot))\) has a cusp at t cusp ∈[0,T] if \(\tilde{u}(\cdot)\) changes its sign in a neighborhood of t cusp >0. More precisely, there exists an ϵ>0 such that \(\tilde{u}(a)\tilde{u}(b)<0\) for all a∈(t cusp −ϵ,t cusp ) and b∈(t cusp ,t cusp +ϵ), where \(\tilde{u}\) denotes the first control variable in P MEC. In such a case γ(t cusp ) is called the cusp-point and t cusp >0 is called the cusp-time.
Remark
Formally, in the minimizers of P curve, cusps do not occur, as the solutions break down at cusps. However, when |z(0)|=1, where z(s) denotes normalized curvature Eq. (5) we say that a geodesic in P curve departs from a cusp. If |z(ℓ)|=1, i.e. \(\ell=s_{max}(z_{0},\dot{z}_{0})\) given by Eq.(78), we say the geodesic of P curve ends in a cusp.
7.1 G.1 Association Field
The term association field comes from modeling contour integration in the human visual cortex by psycho-physical experiments [34, 52]. The general idea of an association field is to provide an a priori link between relative positions and orientations within the sensorium of cortical columns in the primary visual cortex, Fig. 5. Intuitively, the tangents to the field lines of the association field provide expected local orientations, given that an local orientation is observed at the center of the association field.
Field and his co-workers psychophysical measurements have resulted in the association field depicted in item a) of Fig. 8. They relied on the hypothesis that the visual system can solve the continuity problem separately at each scale.Footnote 14
7.2 G.2 Models of the Association Field
Within this article, we consider the cuspless sub-Riemannian geodesic model P curve, cf. [11, 22, 40], which is a natural extension of Petitot’s circle bundle model [52, Chap. 6.6.5]. Other models include Legendrian geodesics [52], and horizontal exponential curves in [57] given by Eq. (72).
These other models relate to the cuspless sub-Riemannian geodesics as follows:
-
The Legendrian geodesics follow from the cuspless sub-Riemannian geodesic model by contracting (e.g. [25]) the sub-Riemannian manifold on \((\mathrm {SE}(2),\Delta ,\mathcal{G}_{\xi})\), Eq. (17), towards its nilpotent approximation, cf. Eq. (73).
-
The horizontal exponential curves keeps the control variable in P curve constant and they can be considered as a rough local approximation of sub-Riemannian geodesics, see item (c) in Fig. 8. Finally, we recall Theorem 12.
Appendix H
We provide some estimates for the single elliptic integral appearing in the spatial arclength parametrization of cuspless sub-Riemannian geodesics, recall Theorem 3 and Lemma 4.
Lemma 9
We have the following lower and upper bound for the elliptic integral at s=s max , for the case \(z_{0}\dot{z}_{0}<1\) and \(\mathfrak{c}<1\):
with s B such that z(s B )=0 and |z(s max )|=1, given by Eq. (42) and Eq. (41). A sharper upper-bound is given by
where
Proof
The smooth integrand
is a concave function, since
Moreover, it is symmetric around the point s B and we have 2s B ≤s max . So the tangent lines at s=0 and s=2s B to the graph of
are contained in the epigraph. Their slope equals \(\frac{-z_{0} \dot{z}_{0}}{\sqrt{1-|z_{0}|^{2}}}\). The rest follows by Fig. 18.
□
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
About this article
Cite this article
Duits, R., Boscain, U., Rossi, F. et al. Association Fields via Cuspless Sub-Riemannian Geodesics in SE(2). J Math Imaging Vis 49, 384–417 (2014). https://doi.org/10.1007/s10851-013-0475-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-013-0475-y