Global Minimum for a Finsler Elastica Minimal Path Approach

In this paper, we propose a novel curvature penalized minimal path model via an orientation-lifted Finsler metric and the Euler elastica curve. The original minimal path model computes the globally minimal geodesic by solving an Eikonal partial differential equation (PDE). Essentially, this first-order model is unable to penalize curvature which is related to the path rigidity property in the classical active contour models. To solve this problem, we present an Eikonal PDE-based Finsler elastica minimal path approach to address the curvature-penalized geodesic energy minimization problem. We were successful at adding the curvature penalization to the classical geodesic energy (Caselles et al. in Int J Comput Vis 22(1):61–79, 1997; Cohen and Kimmel in Int J Comput Vis 24(1):57–78, 1997). The basic idea of this work is to interpret the Euler elastica bending energy via a novel Finsler elastica metric that embeds a curvature penalty. This metric is non-Riemannian, anisotropic and asymmetric, and is defined over an orientation-lifted space by adding to the image domain the orientation as an extra space dimension. Based on this orientation lifting, the proposed minimal path model can benefit from both the curvature and orientation of the paths. Thanks to the fast marching method, the global minimum of the curvature-penalized geodesic energy can be computed efficiently. We introduce two anisotropic image data-driven speed functions that are computed by steerable filters. Based on these orientation-dependent speed functions, we can apply the proposed Finsler elastica minimal path model to the applications of closed contour detection, perceptual grouping and tubular structure extraction. Numerical experiments on both synthetic and real images show that these applications of the proposed model indeed obtain promising results.

1. For the IR metric and the AR metric, only the physical positions of these orientation-lifted vertices are used.

   

   Comparative closed contour detection results obtained by using different metrics. Column 1 Edge saliency map. Columns 2–5 The closed contour detection results from the IR metric, the AR metric, the IOLR metric and the Finsler elastica metric, respectively

   Full size image

2. Many thanks to Dr. Jiong Zhang to provide us these images.

3. We actually use a slight variant of the classical modulus of continuity because the latter one, obtained with the hard cutoff function \({\mathfrak {C}(t)} = 1\) if \(t\le 1\), 0 otherwise, lacks continuity in general.

The authors would like to thank all the anonymous reviewers for their detailed remarks that helped us improve the presentation of this paper. This work was partially supported by ANR Grant NS-LBR, ANR-13-JS01-0003-01.

Authors and Affiliations

1. University Paris Dauphine, PSL Research University, CNRS, UMR 7534, CEREMADE, 75016, Paris, France

   Da Chen & Laurent D. Cohen

2. Laboratoire de mathématiques d’Orsay, Université Paris-Sud, CNRS, Université Paris-Saclay, 91405, Orsay, France

   Jean-Marie Mirebeau

Corresponding author

Correspondence to Da Chen.

Communicated by Cordelia Schmid.

Appendix 1: Fast Marching Method

Basically, the fast marching method introduces a boolean map \(b:Z\rightarrow \{\text {Trial }, \text {Accepted }\}\) and tags each grid point \(\bar{\mathbf {x}}\in Z\) either Trial or Accepted. The Trial points are defined as grid points which have been updated at least once by Hopf-Lax operator (25) but not frozen. The Accepted points are these points that have been updated and frozen. This method can solve the fixed point system (24) in a single pass manner.

Appendix 2: Elements of Proof of Finsler Elastica Minimal Paths Convergence

Let \(X\subset \mathbb {R}^d\) be a compact domain and \(\mathfrak {I}\) be the collection of compact convex sets of \(\mathbb {R}^d\). We will later specialize to \(d=3\) for the application to the Euler elastica curves. The set \(\mathfrak {I}\) is metric space, equipped with the Haussdorff distance which is defined as follows.

Definition 1

The Euclidean distance map from a set \(A_1, A_2 \subseteq \mathbb {R}^d\) is

The Haussdorff distance between sets \(A_1\), \(A_2\subseteq \mathbb {R}^d\) is

Definition 2

Let \(\gamma \in C^0([0,1],X)\) be a path and \(\mathcal {B}\in C^0(X,\mathfrak {I})\) be a collection of controls on X. The path \(\gamma \) is said \(\mathcal {B}\)-admissible iff it is locally Lipschitz and \(\gamma ^\prime (t)\in \mathcal {B}(\gamma (t))\) for a.e. \(t\in [0,1]\).

Definition 3

A collection of controls on X is a map \(\mathcal {B}\in C^0(X,\mathfrak {I})\). Its diameter \(diam(\mathcal {B})\) and modulus^{Footnote 3} of continuity \(\varXi (\mathcal {B},\epsilon )\), are defined by \(\varXi (\mathcal {B},0)=0\) and for \(\epsilon >0\)

where \({\mathfrak {C}}\) is the continuous cutoff function defined by

Clearly \(\mathcal {B}\mapsto diam(\mathcal {B})\) and \((\mathcal {B},\epsilon )\mapsto \varXi (\mathcal {B},\epsilon )\) are continuous functions of \(\mathcal {B}\in C^0(X,\mathfrak {I})\) and \(\epsilon \in \mathbb {R}^+\). In addition \(\varXi (\mathcal {B},\epsilon )\) is increasing w.r.t. \(\epsilon \). Here and below, if \(A_1\), \(A_2\) are metric spaces, and \(A_1\) is compact, then \(C^0(A_1,A_2)\) is equipped with the topology of uniform convergence. This applies in particular to the space of paths \(C^0([0,1],X)\) and of controls \(C^0(X,\mathfrak {I})\).

Lemma 1

If \(\gamma \) is \(\mathcal {B}\)-admissible, then its Lipschitz constant is at most \(diam(\mathcal {B})\). A necessary and sufficient condition for \(\gamma \) to be \(\mathcal {B}\)-admissible is: for all \(0\le p\le q\le 1\),

Proof

Assume that \(\gamma \) is \(\mathcal {B}\)-admissible. Then for any \(0\le p\le q\le 1\) one has

hence \(\gamma \) is \(diam(\mathcal {B})\)-Lipschitz as announced. Denoting \(w_\varrho = p+(q-p)\varrho \), for all \(\varrho \in [0,1]\), one obtains

Hence by Jensen’s inequality and the convexity of \(d(\mathcal {B}(\gamma (p)),\cdot )\), which follows the convexity of \(\mathcal {B}(\gamma (p))\), we obtain

which establishes half of the announced characterization. The inequality (78) follows from the admissibility property \(\gamma ^\prime (w_\varrho )\in \mathcal {B}(\gamma (w_\varrho ))\) and the definition of the Haussdorff distance (71). The inequality (79) follows from the above established Lipschitz regularity of \(\gamma \) and the definition of the modulus of continuity (73).

Conversely, assume that \(\gamma \) and \(\mathcal {B}\) obey (74). Then

for any \(0\le p\le q\le 1\). Thus \(\gamma \) is a Lipschitz path as announced, and therefore it is almost everywhere differentiable. If \(p\in [0,1]\) is a point of differentiability, then letting \(q\rightarrow p\) we obtain

which is the announced admissibility property \(\gamma ^\prime (p)\in \mathcal {B}(\gamma (p))\). \(\square \)

The characterization (74) is written in terms of continuous functions of the path \(\gamma \) and control set \(\mathcal {B}\), hence it is a closed condition, which implies the following two corollaries. We denote

Corollary 1

The set

is closed.

Corollary 2

Let \(\mathbf {x}_n\), \(\mathbf {y}_n\), \(\mathcal {B}_n\) and \(T_n\) be converging sequences in X, X, \(C^0(X,\mathfrak {I})\) and \(\mathbb {R}^+\), with limits \(\mathbf {x}_\infty \), \(\mathbf {y}_\infty \), \(\mathcal {B}_\infty \), and \(T_\infty \) respectively. Let \(\gamma _n\in C^0([0,1],X)\) be a \((T_n+1/n)\mathcal {B}_n\)-admissible path with endpoints \(\mathbf {x}_n\) and \(\mathbf {y}_n\). Then the sequence of paths \((\gamma _n)\) is equip-continuous, and the limit \(\gamma _\infty \) of any converging subsequence  is a \(T_\infty \mathcal {B}_\infty \)-admissible path \(\gamma \in C^0([0,1],X)\) with endpoints \(\mathbf {x}_\infty \) and \(\mathbf {y}_\infty \).

Proof

Note that the map \((T,\mathcal {B})\mapsto T\mathcal {B}\) is continuous on  \(\mathbb {R}^+\times C^0(X,\mathfrak {I})\), hence the controls \(\tilde{\mathcal {B}}_n:=(T_n+1/n)\mathcal {B}_n\) converge to \(\tilde{\mathcal {B}}_\infty :=T_\infty \mathcal {B}_\infty \). Defining \(E:=\sup \{diam(\tilde{\mathcal {B}}_n);n>0\}\) which is finite by continuity of \(diam(\cdot )\) (72) and convergence of \(\tilde{\mathcal {B}}_n\), we find that the paths \((\gamma _n)_{n>0}\) are simultaneously E-Lipschitz, hence that a subsequence uniformly converges to some path \(\gamma _\infty \). The \(\tilde{\mathcal {B}}_\infty \)-admissibility of \(\gamma _\infty \) then follows from Corollary 1. \(\square \)

We next introduce the minimum-time optimal control problems. The minimum of (80) is attained by Corollary 2, which also immediately implies the Corollary 3.

Definition 4

For all \(\mathbf {x}\), \(\mathbf {y}\in X\), and \(\mathcal {B}\in C^0(X,\mathfrak {I})\), we let

Corollary 3

The map \((\mathbf {x},\mathbf {y},\mathcal {B})\mapsto \mathcal {T}_\mathcal {B}(\mathbf {x},\mathbf {y})\) is lower semi-continuous on \(X\times X\times \mathcal {C}^0(X,\mathfrak {I})\). In other words, whenever \((\mathbf {x}_n,\mathbf {y}_n,\mathcal {B}_n)\rightarrow (\mathbf {x}_\infty ,\mathbf {y}_\infty ,\mathcal {B}_\infty )\) as \(n\rightarrow \infty \) one has

Proof

For each \(n>0\) let \(T_n = \mathcal {T}_{\mathcal {B}_n}(\mathbf {x}_n,\mathbf {y}_n)\) and let \(T_\infty = \lim \inf T_n\) as \(n\rightarrow \infty \). Up to extracting a subsequence, we can assume that \(T_\infty = \lim T_n\) as \(n\rightarrow \infty \). Denoting by \(\gamma _n\) a path as in Corollary 2 for all \(n \ge 0\), we find that there is a converging subsequence which limit \(\gamma _\infty \) is \(T_\infty \mathcal {B}_\infty \) admissible and obeys \(\gamma _\infty (0)=\mathbf {x}_\infty \) and \(\gamma _\infty (1)=\mathbf {y}_\infty \). Thus \(T_\infty \ge \mathcal {T}_{\mathcal {B}_\infty }(\mathbf {x}_\infty ,\mathbf {y}_\infty )\) as announced. \(\square \)

Definition 5

Let \(\mathcal {B}_1\), \(\mathcal {B}_2\in C^0(X,\mathfrak {I})\). These collections of controls are said included \(\mathcal {B}_1\subseteq \mathcal {B}_2\) iff \(\mathcal {B}_1(\mathbf {x})\subseteq \mathcal {B}_2(\mathbf {x})\) for all \(\mathbf {x}\in X\).

The property \(\mathcal {B}_1\subseteq \mathcal {B}_2\) clearly implies, for all \(\mathbf {x}\), \(\mathbf {y}\in X\)

Corollary 4

Assume that one has a converging sequence of controls \(\mathcal {B}_n\rightarrow \mathcal {B}_\infty \) obeying the inclusions \(\mathcal {B}_n\supseteq \mathcal {B}_\infty \) for all \(n\ge 0\). Then

for all \(\mathbf {x},\mathbf {y}\in X\). Let \(T_n := \mathcal {T}_{\mathcal {B}_n}(\mathbf {x},\mathbf {y})\) for all \(n\in {\mathbb N} \cup \{\infty \}\), and let \(\gamma _n\) be an arbitrary \((T_n+1/n)\mathcal {B}_n\)-admissible path from \(\mathbf {x}\) to \(\mathbf {y}\). If there exists a unique \(T_\infty \mathcal {B}_\infty \)-admissible path \(\gamma _\infty \) from \(\mathbf {x}\) to \(\mathbf {y}\), then \(\gamma _n \rightarrow \gamma _\infty \) as \(n \rightarrow \infty \).

Proof

The identity (83) follows from inequalities (81) and (82). By Corollary 2 the sequence of paths \(\gamma _n\) is equi-continuous, and any converging subsequence tends to a \(T_* \mathcal {B}_\infty \) admissible path \(\gamma _*\) from \(\mathbf {x}\) to \(\mathbf {y}\), with \(T_* := \lim T_n\). Since \(T_*=T_\infty \) and by uniqueness we have \(\gamma _*=\gamma _\infty \), hence \(\gamma _n \rightarrow \gamma _\infty \) as announced. \(\square \)

Application to Finsler Elastica Geodesics Convergence Problem

Consider an orientation-lifted Finsler metric \(\mathcal {F}:X\times \mathbb {R}^3\rightarrow \mathbb {R}^+\) where \(X:=\bar{\varOmega } \subset \mathbb {R}^3\). For any \(\bar{\mathbf {x}}\in X\), let \(\mathcal {B}(\bar{\mathbf {x}}):=\{\bar{\mathbf {u}}\in \mathbb {R}^3; \mathcal {F}(\bar{\mathbf {x}},\bar{\mathbf {u}})\le 1\}\) be the unit ball of \(\mathcal {F}\). \(\mathcal {B}(\bar{\mathbf {x}})\) is compact and convex, due to the positivity, continuity and convexity of the metric \(\mathcal {F}\) and the map \(\mathcal {B}:X\rightarrow \mathfrak {I}\) is continuous. Furthermore, using the homogeneity of the metric, one obtains for all \(\bar{\mathbf {x}}\), \(\bar{\mathbf {y}}\in X\):

where \(\mathcal {L}^*(\bar{\mathbf {x}},\bar{\mathbf {y}})\) is the minimal curve length between \(\bar{\mathbf {x}}\) and \(\bar{\mathbf {y}}\) with respect to metric \(\mathcal {F}\).

In the case of Finsler elastica problem, one has \(\mathcal {B}_\infty (\bar{\mathbf {x}}):=B^\infty _{\bar{\mathbf {x}}} \) and \(\mathcal {B}_\lambda (\bar{\mathbf {x}}):=B_{\bar{\mathbf {x}}}^\lambda \), \(\forall \bar{\mathbf {x}}\in X\), where \(B^\infty _{\bar{\mathbf {x}}} \) and \(B_{\bar{\mathbf {x}}}^\lambda \) are defined in Eqs. (42) and (43) respectively. The Finsler elastica metrics \(\mathcal {F}^\lambda \) on X pointwisely tend to the metric \(\mathcal {F}^\infty \) as \(\lambda \rightarrow \infty \). Fortunately, the associated control sets \(\mathcal {B}_\lambda (\bar{\mathbf {x}}) \rightarrow \mathcal {B}_\infty (\bar{\mathbf {x}})\) uniformly in \(C^0(\varOmega ,\mathfrak {I})\), as can be seen from (46). Hence one has

as \(\lambda \rightarrow \infty \) for all \(\bar{\mathbf {x}},\bar{\mathbf {y}}\in X\). To show that equality holds, it suffices to prove that sequence \(\mathcal {B}_\lambda \) obeys \(\mathcal {B}^{\lambda }\supseteq \mathcal {B}^\infty \), equivalently to prove that \(\mathcal {F}^{\lambda }(\bar{\mathbf {x}},\bar{\mathbf {u}})\le \mathcal {F}^\infty (\bar{\mathbf {x}},\bar{\mathbf {u}})\) for all \(\bar{\mathbf {x}}\in X\) and any vector \(\bar{\mathbf {u}}\in \mathbb {R}^3\). Indeed, let \(\bar{\mathbf {x}}=(\mathbf {x},\theta )\in X\), and \(\bar{\mathbf {u}}=(\mathbf {u},\nu )\in \mathbb {R}^2\times \mathbb {R}\):

The last inequality holds because the denominator \(1+\sqrt{1+\frac{2|\nu |^2}{\lambda \Vert \mathbf {u}\Vert ^2}}\) in (84) is greater than 2, and \(\Vert \mathbf {u}\Vert \ge \langle \mathbf {u},\mathbf {v}_\theta \rangle \) for any vector \(\mathbf {u}\) and any orientation \(\theta \).

By Corollary 2, minimal paths \(\mathcal {C}^\lambda \) with endpoints \(\bar{\mathbf {x}}\) and \(\bar{\mathbf {y}}\) for geodesic distance \(\mathcal {L}^*_{\mathcal {F}^\lambda }(\bar{\mathbf {x}},\bar{\mathbf {y}}) \) converge as \(\lambda \rightarrow \infty \) to a minimal path \(\mathcal {C}^\infty \) for \(\mathcal {L}^*_{\mathcal {F}^\infty }(\bar{\mathbf {x}},\bar{\mathbf {y}}) \). We finally point out that \(\mathcal {L}^*_{\mathcal {F}^\infty }(\bar{\mathbf {x}},\bar{\mathbf {y}})<\infty \) for all \(\bar{\mathbf {x}}\), \(\bar{\mathbf {y}}\) in the interior of X, provided this interior is connected, due a classical controllability result for the Euler elastica problem.

Reprints and permissions