Combination of Piecewise-Geodesic Paths for Interactive Segmentation

Abstract

Minimum cost paths have been extensively studied theoretical tools for interactive image segmentation. The existing geodesically linked active contour (GLAC) model, which basically consists of a set of vertices connected by paths of minimal cost, blends the benefits of minimal paths and region-based active contours. This results in a closed piecewise-smooth curve, over which an edge or region energy functional can be formulated. As an important shortcoming, the GLAC in its initial formulation does not guarantee the curve to be simple, consistent with respect to the purpose of segmentation. In this paper, we draw our inspiration from the GLAC and other boundary-based interactive segmentation algorithms, in the sense that we aim to extract a contour given a set of user-provided points, by connecting these points using paths. The key idea is to select a combination among a set of possible paths, such that the resulting structure represents a relevant closed curve. Instead of considering minimal paths only, we switch to a more general formulation, which we refer to as admissible paths. These basically correspond to the roads travelling along the bottom of distinct valleys between given endpoints. We introduce a novel term to favor the simplicity of the generated contour, as well as a local search method to choose the best combination among possible paths.

Appendix: Mathematical Derivations of Overlap and Exteriority Terms

1.1 Overlap Term

Let $\mathcal {C}$ be a regular curve parameterized over $[0,L]$. Let $\phi$ be a $C^1$ function defined over $[0,L]^2$ representing the distance between two positions on the curve:

$$\begin{aligned} \phi (u,v) = \left\| \mathcal {C}(u)-\mathcal {C}(v) \right\| ^p \end{aligned}$$

where $p>1$ is a real exponent. The length of the zero level set of $\phi _\mathcal {C}$,

$$\begin{aligned} \left| \mathcal {Z}_\mathcal {C}\right| = \int _0^L \int _0^L \delta (\phi (u,v))\left\| \nabla \phi (u,v) \right\| {\text {d}}u {\text {d}}v, \end{aligned}$$

(19)

quantifies the self-overlap of $\mathcal {C}$.

Proposition

If $\mathcal {C}$ is simple, i.e. without self-intersection and self-tangency, then $\left| \mathcal {Z}_\mathcal {C}\right| = L\sqrt{2}$.

Proof

As a preliminary calculation, let us express the gradient of $\phi$ (partial derivatives are written using the indexed notation):

$$\begin{aligned} \nabla \phi (u,v)&= \left[ \phi _u(u,v)~~\phi _v(u,v) \right] ^T \nonumber \\&= p \left\| \mathcal {C}(u)-\mathcal {C}(v) \right\| ^{p-2} \left[ \begin{aligned} \mathcal {C}'(u) \cdot (\mathcal {C}(u)-\mathcal {C}(v)) \\ -\mathcal {C}'(v) \cdot (\mathcal {C}(u)-\mathcal {C}(v)) \end{aligned} \right] \end{aligned}$$

$\square$

If $\mathcal {C}$ is regular and simple, varying with respect to $u$ in range $[0,L], \phi (u,v)$ is nowhere zero except when $u=v$. Hence, for a fixed $v$, we have:

$$\begin{aligned} \delta (\phi (u,v)) = \frac{\delta (u-v)}{\left| \phi _u(v,v) \right| } \end{aligned}$$

(20)

Integrating (20) into (19) and applying the definition of measure $\delta$:

$$\begin{aligned} \left| \mathcal {Z}_\mathcal {C}\right|&= \int _0^L \int _0^L \delta (\phi (u,v))\left\| \nabla \phi (u,v) \right\| {\text {d}}u {\text {d}}v \\&= \int _0^L \int _0^L \frac{\delta (u-v)}{\left| \phi _u(v,v) \right| } \left\| \nabla \phi (u,v) \right\| {\text {d}}u {\text {d}}v \\&= \int _0^L \frac{\left\| \nabla \phi (v,v) \right\| }{\left| \phi _u(v,v) \right| } {\text {d}}v \end{aligned}$$

Expanding the gradient gives:

$$\begin{aligned} \left| \mathcal {Z}_\mathcal {C}\right|&= \int _0^L \left\{ \right. \frac{p \left\| \mathcal {C}(v)-\mathcal {C}(v) \right\| ^{p-2}}{p \left\| \mathcal {C}(v)-\mathcal {C}(v) \right\| ^{p-2}} \\&\frac{ \sqrt{2(\mathcal {C}'(v)\cdot (\mathcal {C}(v)-\mathcal {C}(v)))^2}}{ \left| \mathcal {C}'(v)\cdot (\mathcal {C}(v)-\mathcal {C}(v))\right| } \left. \right\} {\text {d}}v \\&= \int _0^L \sqrt{2}~{\text {d}}v \\&= L\sqrt{2} \end{aligned}$$

1.2 Exteriority Term

Let $\mathcal {C}$ be a piecewise-smooth regular curve parameterized over $[0,1]$. If it is simple and positively oriented such that normal vector ${\mathcal {C}}'^\perp$ points inward, its inner area may be expressed using Green’s theorem:

$$\begin{aligned} \left| {\Omega _{\text {in}}}(\mathcal {C}) \right|&= \frac{1}{2} \int _0^1 \mathcal {C}^\perp (u) \cdot {\mathcal {C}}'(u)~{\text {d}}u \\&= \frac{1}{2} \int _0^1 x(u){y}'(u) - {x}'(u)y(u)~{\text {d}}u \end{aligned}$$

When one calculates the previous expression on a non-simple closed curve, one gets the signed area, in which positively and negatively oriented connected components have positive and negative contributions, respectively.

Proposition

The signed area formed by an open curve $\mathcal {C}$ over $[0,1]$ and the line segment from $\mathcal {C}(1)$ returning to $\mathcal {C}(0)$ (see Fig. 15), which we use to as the exteriority measure in Sect. 5.2, may be expressed as:

$$\begin{aligned} \mathcal {X}[\mathcal {C}] = \frac{1}{2} \int _0^1 \mathcal {C}^\perp \cdot {\mathcal {C}}'{\text {d}}u + \frac{1}{2}\mathcal {C}^\perp (1) \cdot \mathcal {C}(0) \end{aligned}$$

Fig. 15

The exteriority of an open curve is measured as the signed area of the multiple connected region that it forms with the line segment joining its two endpoints

Proof

Let $S$ be the parametrization of the line segment joining $\mathcal {C}(1)$ and $\mathcal {C}(0)$, over $[0,1]$:

$$\begin{aligned} S(u) = (1-u)\mathcal {C}(1)+u\mathcal {C}(0) \end{aligned}$$

The signed area is then obtained by applying Green’s theorem on a piecewise basis:

$$\begin{aligned} \mathcal {X}[\mathcal {C}]&= \frac{1}{2} \int _0^1 \mathcal {C}^\perp \cdot {\mathcal {C}}' {\text {d}}u + \frac{1}{2} \int _0^1 S^\perp (u)\cdot {S}'(u) {\text {d}}u \\&= \frac{1}{2} \int _0^1 \mathcal {C}^\perp \cdot {\mathcal {C}}' {\text {d}}u \\&\quad + \frac{1}{2} \int _0^1 ((1-u)\mathcal {C}^\perp (1)+u\mathcal {C}^\perp (0))\cdot (\mathcal {C}(0)-\mathcal {C}(1)) {\text {d}}u \\&= \frac{1}{2} \int _0^1 \mathcal {C}^\perp \cdot {\mathcal {C}}' {\text {d}}u \\&\quad + \frac{1}{2} \int _0^1 (1-u)\mathcal {C}^\perp (1) \cdot \mathcal {C}(0) +u\mathcal {C}^\perp (1)\cdot \mathcal {C}(0) {\text {d}}u \\&= \frac{1}{2} \int _0^1 \mathcal {C}^\perp \cdot {\mathcal {C}}' {\text {d}}u + \frac{1}{2} \int _0^1 \mathcal {C}^\perp (1) \cdot \mathcal {C}(0) {\text {d}}u \\&= \frac{1}{2} \int _0^1 \mathcal {C}^\perp \cdot {\mathcal {C}}' {\text {d}}u + \frac{1}{2} \mathcal {C}^\perp (1) \cdot \mathcal {C}(0) \end{aligned}$$

$\square$