Affine Invariant Distance Using Multiscale Analysis

Abstract

In this paper we introduce an affine invariant distance definition from a $2D$ point to the boundary of a bounded shape using morphological multiscale analysis. We study the mathematical behavior of this distance by examining separately the cases of convex and non-convex shapes. We prove that the proposed distance is bounded in the convex hull of the shape and infinite otherwise. A numerical scheme is given as well as experiments illustrating the behavior of the affine invariant distance.

1 Introduction

In this paper we address the problem of defining an affine invariant distance to a shape, in the realm of morphological multiscale analysis. The search for affine invariants in image analysis is motivated by the necessity of obtaining local image descriptors invariant to perspective changes, which causes local affine distortion of objects. The most celebrated such affine invariant descriptor is MSER, proposed in [16]. It extracts the well-contrasted connected components of level sets of the image and applies to them a global normalization. Nevertheless this method is not combined with a multiscale analysis in the sense that no previous smoothing is involved. It is a semi-global method, as it is based on whole connected components. Scale space theory has led to several similarity invariant shape and image local descriptors. The SIFT method [15] has been acclaimed for its efficiency. It has some practical partial affine invariance, but is theoretically only similarity invariant [21]. The ASIFT method [26] is theoretically proved to be fully affine invariant [20], but it is a brute force method simulating not less than three affine parameters to reach affine invariance. Since affine invariance requires invariance to six parameters, the royal way to achieve local descriptor would be affine normalization, but the only attempt to do is the Hessian affine descriptor [17] which has never been justified mathematically. Thus the question of extracting directly local and reliable affine invariant information from an image or from a shape is still a valid challenge. Here our goal is to involve the existence of affine invariant PDEs to define an affine invariant topography for a shape (understood as a bounded 2D set). We shall not focus on the potential applications, which are left to future work. We focus here on the theory and justification for the existence of affine local distances to shapes, obtained by a PDE. In [4], the authors showed that under some minimal architectural assumptions, all the contrast and similarity invariant image multiscale analyses are generated by the partial differential equation

$$\begin{aligned} \frac{\partial u}{\partial t}=\beta (t\cdot \mathrm{curv}(u))\left\| \nabla u\right\| , \end{aligned}$$

(1)

where $\beta (.)$ is a nondecreasing function and $\mathrm{curv}(u)(x,y)$ is the curvature of the level line passing by the point $(x,y),$ namely $\mathrm{curv}(u):= \mathrm{div}\left( \frac{\nabla u}{\left\| \nabla u\right\| }\right) .$ Conversely, given a continuous nondecreasing function $\beta$, and provided the viscosity solution theory for this particular function $\beta$ holds, the Eq. (1) defines a unique multiscale analysis endowed with the above-mentioned invariance properties and is applicable to any uniformly continuous function on the plane. The existence of viscosity solutions has been proved for the classic case of power functions $\beta (s)=s^\alpha$. We refer to [18] for detailed references on the subject and for a numerical analysis of the equation understood as a curve evolution. The particular case $\alpha =1/3$ was studied in detail in [5] and its numerical analysis is detailed in [8]. In the case $\alpha =1$ a proof was given in [7] that the curve evolution of the level lines of an image by curvature shortening is strictly equivalent to moving the image by curvature motion (1). This proof is extendable to other powers provided a classic solution exists for the curvature shortening equation, which is granted for $\alpha >1/3$. Numerical schemes for arbitrary powers of curvature are also considered in [14, 25], including the case $\alpha =\frac{1}{3}$.

Let $f$ be an initial data function. Under the above-mentioned condition of existence of a viscosity solution theory for the equation, the nonlinear partial differential equation (1) generates a multiscale analysis $T_{t}^{\beta }(f)$ given by

$$\begin{aligned} u(t,x,y)=T_{t}^{\beta }(f)(x,y). \end{aligned}$$

According to the morphological principle and provided the existence and uniqueness of solutions are granted for the choice of $\beta$, each level value $l\in R,$ $T_{t}^{\beta }(f)$ generates an intrinsic curve evolution given by the collection of level set curves:

$$\begin{aligned} C(t)=\partial S(t), \end{aligned}$$

where

$$\begin{aligned} S(t)=\{(x,y):\ T_{t}^{\beta }(f)(x,y)\le l\}. \end{aligned}$$

In what follows we will fix that the curves we are interested in correspond to $l=0$. Due to the morphological invariance (also called level set principle [22]), the evolution of $C(t)$ only depends on the geometry of $C_{0}\equiv C(0)=\partial \{(x,y):\ f(x,y)\le 0\}$ and it is independent of the particular surface $f(x,y)$ where $C_{0}$ is embedded.

It is well known (see for instance [13]) that if we choose $\beta (s)\equiv 1$ in (1) then the Euclidean distance $d_{E}((x,y),C_{0})$ of a point $(x,y)\in S_0$ to $C_{0}$ can be computed as

$$\begin{aligned} d_{E}((x,y),C_{0})=\sup \left\{ t\ge 0:T_{t}^{\beta }(f)(x,y)\le 0\right\} . \end{aligned}$$

(2)

In the same way if $(x,y)\notin S_{0}$ and $\beta (s)\equiv -1$ then

$$\begin{aligned} d_{E}((x,y),C_{0})=\sup \left\{ t\ge 0:T_{t}^{\beta }(f)(x,y)\ge 0\right\} . \end{aligned}$$

(3)

The main goal of this paper is to study the generalization of the above expressions to define an affine invariant distance using the affine invariant multiscale analysis. In [4] the authors showed that all affine invariant morphological multiscale analyses are given by the following choice for $\beta (s)$

$$\begin{aligned} \beta (s)=\left\{ \begin{array}{lll} \beta _{1}s^{\frac{1}{3}} &{} \quad \mathrm{if} &{} s\ge 0\\ -\beta _{-1}(-s)^{\frac{1}{3}} &{} \quad \mathrm{if} &{} s<0, \end{array} \right. \end{aligned}$$

(4)

where $\beta _{1},\beta _{-1}\ge 0$. These particular cases are well studied and grant the existence and uniqueness of a viscosity solution for the PDE (see [4, 9]). Affine invariant multiscale analyses in terms of curve evolution have been introduced in [23] and [24]. The existence theory of a classic affine curve evolution was completed in [5]. The level set formulation in the sense of Osher and Sethian [22] for the affine invariant multiscale analysis was developed in [2–4]. In [19], the author introduced an affine invariant area distance yielding approximation scheme of affine invariant curve evolution using a polygonal approximation.

Affine invariance means that for any affine transformation $H(x,y)=A\cdot (x,y)^{T}+(c_{x},c_{y})^T$ where $A$ is a $2\times 2$ matrix with $|A|\ne 0$, the multiscale analysis satisfies:

$$\begin{aligned} T_{t^{\prime }(H,t)}^{\beta }(f)(H(x,y))=T_{t}^{\beta }(H(f))(x,y). \end{aligned}$$

(5)

In addition, it is proved in [4] that if $\beta (s)$ is given by (4) then

$$\begin{aligned} t^{\prime }(H,t)=t\sqrt{\left| A\right| } . \end{aligned}$$

(6)

In this paper we are going to use two particular affine multiscale analyses which correspond to adequate combinations of the parameters $\beta _1$ and $\beta _{-1}$. The first one, that we will use to define the affine distance inside the shape, is given by

$$\begin{aligned} \beta _+(s)=(s_+)^{\frac{1}{3}}, \end{aligned}$$

(7)

where $s_+= \mathrm{max}\{s,0\}$. The second affine multiscale analysis that we will use to define the affine distance outside the shape is given by

$$\begin{aligned} \beta _-(s)=-(-s_-)^{\frac{1}{3}}, \end{aligned}$$

(8)

where $s_-= \mathrm{min}\{s,0\}$. Using these affine multiscale analyses, we define the affine distance from a point $(x,y)$ to the boundary $C_{0}$ of a shape $S_0$ by

$$\begin{aligned} \begin{array}{l} d_{A}((x,y),C_{0})=\\ \left\{ \begin{array}{ccc} \sup \left\{ t\ge 0:T_{t}^{\beta _+}(f_{S_{0}})(x,y)\le 0\right\} &{} \quad \mathrm{if} &{} (x,y) \in S_0\\ \sup \left\{ t\ge 0:T_{t}^{\beta _-}(f_{S_{0}})(x,y)\ge 0\right\} &{} \quad \mathrm{if} &{} (x,y) \notin S_0. \end{array} \right. \end{array} \end{aligned}$$

(9)

Here $f_{S_0}(x,y)$ is any function such that $S_0\!=\!\{(x,y)$:$f_{S_0}(x,y) \le 0\}$. First we shall prove that, formally, $d_{A}((x,y),C_{0})$ is an affine invariant (modulus a constant factor).

Theorem 1

Let $H(x,y)=A\cdot (x,y)^{T}+(c_{x},c_{y})^{T}$ be an affine transformation, $C_{0}$ the boundary of a shape $S_0$ and $d_{A}((x,y),C_{0})$ defined by (9) then if $H(S_{0}^{\prime })=S_{0}$ and $C^{\prime }_0=\partial S^{\prime }_{0}$ we have, that for any point $(x,y)$,

$$\begin{aligned} d_{A}(H(x,y),C_{0})=\sqrt{\left| A\right| }d_{A}((x,y),C_{0}^{\prime }). \end{aligned}$$

Proof

First we consider the case $H(x,y)\in S_{0}$. Using (9) and (5), (6), we obtain

$$\begin{aligned} T_{t\sqrt{|A|}}^{\beta _+}(f_{S_{0}})(H(x,y))=T_{t}^{\beta _+}\big (f_{S_{0}^{\prime }}\big )(x,y) \end{aligned}$$

and therefore

$$\begin{aligned}&d_{A}((x,y),C_{0}^{\prime })=\sup \left\{ t\ge 0:T_{t}^{\beta _+}(f_{C_{0}^{\prime }})((x,y))\le 0\right\} \\&\quad =\sup \left\{ t\ge 0:T^{\beta _+}_{t\sqrt{|A|}}(f_{C_{0}})(H(x,y))\le 0\right\} \\&\quad =\frac{1}{\sqrt{|A|}}\sup _{t>0}\left\{ t\ge 0:T_{t}^{\beta _+}(f_{C_{0}} )(H(x,y))\le 0\right\} \\&\quad =\frac{d_{A}(H(x,y),C_{0})}{\sqrt{\left| A\right| }}. \end{aligned}$$

In the case $H(x,y)\notin S_{0}$ we get the same conclusion using the definition of $d_{A}(H(x,y),C_{0})$ when $H(x,y)$ is outside $S_{0}$. $\square$

In order to study the mathematical properties of $d_{A}((x,y), C_{0})$ we are first going to study the case of convex shapes. We will then extend the study to the general case of non-convex shapes.

The organization of the paper is as follows: In Sect.  2, we study the mathematical properties of the proposed affine invariant distance in the case of convex shapes. In Sect. 3, we study the case of general non-convex shapes. In Sect. 4, we present the discretization of the affine multiscale analysis we use to compute numerically the affine distance and some experiments to illustrate the behavior of the proposed distance function and finally in Sect.  5 we present some conclusions.

2 Affine Invariant Distance for Convex Shapes

There are several ways to define an affine distance from a point to the boundary of a shape. A simple way is to perform shape normalization as explained in [11] and [6] where the authors prove the validity of a classic affine invariant shape normalization based on shape regular moments invented by Hu in 1962 [12]. Once the shape is normalized, one can define an affine invariant distance by taking the usual Euclidean distance in the normalized space. The main limitation of this definition is that it depends globally on the geometry of the shape. In [10], in the case of convex shapes, the authors used an affine invariant distance definition based on the affine arc-length parametrization of the shape contour boundary.

First of all we need to justify the surprising fact that the distance of a point to a single convex set must be infinite.

Lemma 1

Let $d$ be an affine invariant distance of a point to set satisfying the (obvious) prerequisites:

$$\begin{aligned}&A\subset B\Rightarrow d((x,y), A)\ge d((x,y), B); \end{aligned}$$

(10)

$$\begin{aligned}&\hbox {For every } \lambda >0, \; d(\lambda (x,y), \lambda A)=\lambda d((x,y), A) \end{aligned}$$

(11)

$$\begin{aligned}&d((1,0),\{(x,y)\mid x<0\}) >0. \end{aligned}$$

(12)

Then for any point $(x,y)$ and any convex set $C$ such that $(x,y)\notin C$, we have $d((x,y), C)=+\infty$.

Proof

Since we can always replace the convex set $C$ by a half plane containing it and excluding the point, it is enough to develop our argument in that particular case. Consider for example the point $(1,0)$ in the Euclidean plane and the half plane $C:=\{(x,y)\mid x<0\}$. Applying to the whole figure an affine map $A=\left( \begin{array}{cc} a &{} 0 \\ 0 &{} a^{-1} \\ \end{array} \right)$, with determinant 1, we notice that the half plane is invariant by $A$, while the point $(1,0)$ is changed into $(a, 0)$. It follows that we can let $a\rightarrow +\infty$, while by the affine invariance the distance of the point to the plane should not change. By the scale covariance assumption we deduce that the distance of all points $(x,y)$ with $x>0$ to the half plane $x<0$ must be a (positive) constant invariant by the multiplication by any $\lambda >0$. Thus it is equal to $+\infty$. $\square$

Properties of the Interior Distance to a Convex Set Let $S_{0}$ be a bounded convex set. We embed $S_{0}$ in a surface $f_{S_{0}}(x,y)$ such that $f_{S_{0}}(x,y)<0$ is inside $S_{0}$ and $f_{S_{0} }(x,y)>0$ is outside. Then we consider the curve evolution $S(t)$ generated by the affine multiscale analysis associated to (7). In [24] it was proved that if $C(t)=\partial S(t)$ is the curve evolution associated to this affine invariant multiscale analysis then $C(t)$ satisfies the following properties:

• 1. $C(t)$ remains convex for all $t>0,$

• 2. The curvature $k$ satisfies that $k\ge 0$ for any point of $C_{0}$ and for any $t>0$, $k>0$ for any point of $C(t).$

• 3. $C(t)$ vanishes in a finite time. That is $C(t)$ is the empty set if $t$ is big enough.

• 4. For any $t^{\prime }>t,$ $S(t^{\prime })\subseteq S(t).$

Since $C(t)$ vanishes in finite time, for any point $(x,y)\in S_{0}$ we have $d_{A}((x,y),C_{0})<\infty .$ Next, to obtain estimations of the curve motion velocity (specially in points where $k=0)$. We are going to use a particular collection of solutions of the affine invariant multiscale analysis: we consider $C_{0}^{\alpha }$ the curve associated to a corner contour with angle $\alpha$ given by

$$\begin{aligned} C_{0}^{\alpha }=\Bigg \{(x,y)\in R^{2}:y=\frac{1}{\tan \left( \frac{\alpha }{2}\right) }|x|\Bigg \}, \end{aligned}$$

in [1], authors showed that the evolution of $C_{0}^{\alpha }$ under the action of the affine multiscale analysis associated to (7) is given by the hyperbola branch:

$$\begin{aligned} C^{\alpha }(t)= \left\{ (x,y)\in R^{2} :y= \sqrt{\frac{t^{2}}{\tan \left( \frac{\alpha }{2}\right) } + \frac{x^{2}}{\tan ^{2}\left( \frac{\alpha }{2}\right) }}\right\} . \end{aligned}$$

(13)

Figure 1 illustrates the curves $C_{0}^{\alpha }$ and $C^{\alpha }(t).$ We denote by $S_{0}^{\alpha }$ the inside region of the corner.

Fig. 1

Illustration of a corner contour $C_0^{\alpha }$ and its evolution $C^{\alpha }(t)$ under the action of the affine multiscale analysis

Let $S_0$ be a convex-bounded shape, $C_{0}=\partial S_0$, and by an Euclidean transformation $E:R^{2}\rightarrow R^{2}$ we say that $E(C_{0}^{\alpha })$ is a tangent corner to $C_{0}$ if $C_{0}\subseteq E(S_{0}^{\alpha })$ and $C_{0}$ intersects both corner bounding lines.

Lemma 2

Let $S_{0}$ be a convex-bounded set, $C_0=\partial S_0$, $C(t)$ the curve evolution generated by the affine multiscale analysis associated with $\beta _+(s)$ defined in (7), $E(C_{0}^{\alpha })$ a tangent corner to $C_{0}$, $(x_{0},y_{0})\in$ $E(C_{0}^{\alpha })\cap C_{0},$ and $(x_{0} (t),y_{0}(t))$ the nearest intersection point of $C(t)$ with the normal line to $C_{0}$ passing by $(x_{0},y_{0}).$ Then, if $t>0$ is small enough

$$\begin{aligned}&\left\| (x_{0}(t),y_{0}(t))-(x_{0},y_{0})\right\| \\&\ge \left\{ \begin{array}{lll} \left| \frac{d\lambda -\sqrt{d^{2}\lambda ^{2}+t^{2}\lambda (1-\lambda ^{2})} }{(1-\lambda ^{2})}\right| &{} \quad \mathrm{{if}} &{} \lambda \ne 1\\ \frac{t^{2}}{2d} &{} \quad \mathrm{{if}} &{} \lambda =1, \end{array} \right. \end{aligned}$$

where $\lambda =\frac{1}{\tan \left( \frac{\alpha }{2}\right) }$ and $d$ is the distance from $(x_{0},y_{0})$ to the corner vertex (Fig. 2 illustrates the Lemma’s notation and result).

Proof

We shall use the shape comparison principle (which follows from the maximum principle) for all curvature motions. It simply states that curvature motion is shape inclusion preserving, namely $C_{0}\subseteq E(S_{0}^{\alpha })\Rightarrow C(t)\subseteq E(S^{\alpha }(t)).$ Using (13) we can compute the intersection $(x_{0}^{\alpha }(t),y_{0}^{\alpha }(t))$ of the normal line to $C_{0}$ passing by $(x_{0},y_{0})$ with $C^{\alpha }(t)$ and a straightforward computation yields

$$\begin{aligned}&\left\| (x_{0}(t),y_{0}(t))-(x_{0},y_{0})\right\| \ge \left\| (x_{0}^{\alpha }(t),y_{0}^{\alpha }(t))-(x_{0},y_{0})\right\| \\&\quad =\left\{ \begin{array} [c]{ccc} \left| \frac{d\lambda -\sqrt{d^{2}\lambda ^{2}+t^{2}\lambda (1-\lambda ^{2})}}{(1-\lambda ^{2})}\right| &{} \quad \mathrm{{if}} &{} \lambda \ne 1\\ \frac{t^{2}}{2d} &{} \quad \mathrm{{if}} &{} \lambda =1. \end{array} \right. \end{aligned}$$

Notice that if $t>0$ is small enough the normal line intersects $C_{0}^{\alpha }$. $\square$

Fig. 2

Illustration of the notation and result of Lemma 2

Next, we are going to show that the distance of a point to the curve is equal to zero if the point belongs to the curve.

Lemma 3

Let $S_0$ be a convex-bounded shape, $C_{0}=\partial S_0$ and $C(t)$ the curve evolution generated by the affine multiscale analysis associated with $\beta _+(s)$ defined in (7), then for any point $(x,y)\in S_{0}$ :

$$\begin{aligned} d_{A}((x,y),C_{0})=0\Leftrightarrow (x,y)\in C_{0}. \end{aligned}$$

Proof

Since $C_{0}$ is a convex Jordan curve, for any point $(x,y)\in C_{0}$ there exists a tangent corner $E(C_{0}^{\alpha })$ such that $(x,y)\in$ $E(C_{0}^{\alpha })\cap C_{0}$. Then, using the previous Lemma we obtain that for any $t>0$ $S(t)$ $\cap$ $C_{0}=\phi$ which concludes the proof. $\square$

3 Affine Invariant Distance for Non-Convex Shapes

To define the affine invariant distance of a point to the boundary of a bounded non-convex shape $S_{0}$ we will consider separately the case of points inside or outside $S_{0}.$

3.1 Affine Invariant Distance for Points Inside the Non-Convex Shape

Defining the affine distance, $d_A((x,y),C_0)$, for a point $(x,y)$ inside a non-convex shape $S_0$ involves the affine multiscale analysis associated with $\beta _+(s)$ defined in (7). Note that in the concave part of the shape where the curvature $k$ is negative, $\beta _+(k)=0$ and therefore the curve could not initially move in these concave parts. The expected behavior in this case is that initially only the convex parts of the curve move and the concave parts of the initial shape become convex under the action of the motion of the convex parts. Next we show some mathematical properties of $d_A((x,y),C_0)$ when we deal with points inside a non-convex shape.

Lemma 4

If $C_{0}$ is the boundary contour of a bounded shape $S_0$, and $(x,y)\in S_{0}$ then $d_{A}((x,y),C_{0})<\infty$.

Proof

Since $S_{0}$ is bounded, there exists an ellipse $C_{0}^{e}$ such that $S_{0}\subseteq S_{0}^{e}$. Then we obtain by the shape inclusion principle that $S(t)\subseteq S^{e}(t)$. The statement of the Lemma follows, because $S^{e}(t)$ is a collection of ellipses that vanishes in finite time [5]. $\square$

One can also observe that $\beta _+(s)\ge 0$ for all $s$, and therefore for any $t^{\prime }>t\ge 0$ $S(t^{\prime })\subseteq S(t)$. However the condition

$$\begin{aligned} d_{A}((x,y),C_{0})=0\Leftrightarrow (x,y)\in C_{0} \end{aligned}$$

is in general not true due to the fact that initially, in points where the curvature is negative, the curve does not move.

3.2 Affine Invariant Distance for Points Outside the Non-Convex Shape

The affine distance outside a non-convex shape uses the affine multiscale analysis associated with $\beta _-(s)$ defined in (8). We shall explore the properties of $d_A((x,y),C_0)$ in that case.

Lemma 5

Let $S_{0}$ be a bounded shape, the collection of sets $S(t)$ generated by the affine multiscale analysis associated with $\beta _-(s)$ defined in (8) satisfies

$$\begin{aligned} S(t)\subseteq S(t^{\prime })\subseteq \mathrm{Hull}(S_{0}) \end{aligned}$$

for any $t^{\prime }>t\ge 0$, where $\mathrm{Hull}(S_{0})$ is the convex hull of $S_{0}$.

Proof

Since $\beta _-(s)\le 0$ then for any $t^{\prime } >t\ge 0$ we get $S(t)\subseteq S(t^{\prime }).$ On the other hand the boundary of Hull$(S_{0})$, is a convex curve with non-negative curvature $k\ge 0$, and therefore, since $\beta _{-}(k) =0$, for $k\ge 0$ such curve does not move under the action of the multiscale analysis and by the shape inclusion principle we get $S(t)$ $\subseteq \mathrm{Hull}(C_{0})$ for any $t\ge 0.$ $\square$

Lemma 6

Let $S_{0}$ be a bounded connected shape, and $S(t)$ the evolution of the shape under the action of the affine multiscale analysis associated with $\beta _-(s)$ is defined in (8). Then $S(t)$ converges towards $\mathrm{Hull}(S_0)$. Furthermore, if $(x,y)$ is an interior point of $\mathrm{Hull}(S_{0})-S_{0}$, then $d_{A}((x,y),C_{0})<\infty$.

Proof

The collection of sets $\{S(t)\}_{t>0}$ satisfies $S(t)$ $\subseteq \mathrm{Hull}(S_{0})$ for any $t\ge 0$ and for any $t^{\prime }>t\ge 0$ $S(t)\subseteq S(t^{\prime }).$ Thus $S(t)$ increases and converges to a limit set $S_{\infty }.$ On the other hand we have $S_{\infty }\subseteq \mathrm{Hull}(S_{0})$ and $S_{\infty }$ should be convex because otherwise there would be some point on the boundary of $S_{\infty }$ where the curvature could be negative, and the multiscale analysis would move such a point, in contradiction with the fact that $S_{\infty }$ is the limit of $S(t)$. Therefore $S_{\infty }$ is convex and since $S_0$ is a connected set, then $S_{\infty }=\mathrm{Hull}(S_{0})$ and therefore for any interior point $(x,y)$ of $\mathrm{Hull}(S_{0})-S_{0}$ there exists $t>0$ such that $(x,y)\in S(t)$ and therefore $d_{A}((x,y),C_{0})\le t.$ $\square$

According to the previous Lemma, if a point $(x,y)$ is outside $\mathrm{Hull}(S_{0}),$ then $d_{A}((x,y),C_{0})=\infty$ (as it was shown in Lemma 1). On the other hand the condition

$$\begin{aligned} d_{A}((x,y),C_{0})=0\Leftrightarrow (x,y)\in C_{0} \end{aligned}$$

is in general not true. For instance, $d_{A}((x,y),C_{0})=\infty .$ for any point $(x,y)\in C_{0}\cap \mathrm{Hull}(S_{0})$

4 Numerical Affine Distance Computation and Experimental Results

To compute numerically the proposed affine distance given by (9) first consider the case of points inside the shape $S_0$. Observe that using $\beta _+(s)$ given by (7), the partial differential equation (1) becomes

$$\begin{aligned} u_{t}= \left( t \cdot \left( \left( u_{y}\right) ^{2}u_{xx}-2u_{x} u_{y}u_{xy}\!+\!\left( u_{x}\right) ^{2}u_{yy}\right) _{+}\right) ^{\frac{1}{3}}. \end{aligned}$$

(14)

In order to remove the $t$ factor in the differential operator we can apply the following change of variables

$$\begin{aligned} \tilde{t}=\frac{3}{4}t^{\frac{4}{3}} \end{aligned}$$

and the Eq. (14) becomes

$$\begin{aligned} u_{\tilde{t}}=\left( \left( \left( u_{y}\right) ^{2}u_{xx}-2u_{x} u_{y}u_{xy}+\left( u_{x}\right) ^{2}u_{yy}\right) _{+}\right) ^{\frac{1}{3}}. \end{aligned}$$

(15)

To compute the affine distance (9) the above partial differential equation can be discretized by the following standard explicit finite difference schemes

$$\begin{aligned} \frac{u^{n+1}-u^{n}}{\delta \tilde{t}} =\left( \left( \left( u_{y}^{n}\right) ^{2}u_{xx}^{n} - 2u_{x}^{n}u_{y}^{n}u_{xy}^{n} \!+\! \left( u_{x}^{n}\right) ^{2}u_{yy}^{n}\right) _{+}\right) ^{\frac{1}{3}}, \end{aligned}$$

here standard $3\times 3$ masks are being used to approximate the spatial derivatives of the function. We shall denote by $u^n_{i,j}$ the solution of the above iterative scheme in the position $(i,j)$, where we consider that the spatial discretization step $h$ is equal to 1. We point out that in the case $h\ne 0$ we can normalize $h$ using the spatial transformation $(x,y)\rightarrow (x/h,y/h)$ and then the above numerical scheme becomes

$$\begin{aligned}&\frac{u^{n+1}-u^{n}}{\delta \tilde{t}} \\&\quad = \left( \frac{ \left( \left( u_{y}^{n}\right) ^{2}u_{xx}^{n} - 2u_{x}^{n}u_{y}^{n}u_{xy}^{n} + \left( u_{x}^{n}\right) ^{2}u_{yy}^{n}\right) _{+}}{h^4}\right) ^{\frac{1}{3}}. \end{aligned}$$

Observe that the above expression introduces a natural coupling between time and space discretization steps given by

$$\begin{aligned} \delta \tilde{t}=C\cdot h^{\frac{4}{3}}, \end{aligned}$$

(16)

where $C>0$ is a constant.

To improve the numerical stability of the scheme, at each iteration the solution $u^n_{i,j}$ is forced to satisfy a local comparison principle in the following way : denoted by $\mathbf{N}_{i,j}$ the usual $8$-point neighborhood of the pixel $(i,j)$, at each iteration, $u^{n+1}_{i,j}$ is updated in the following way:

$$\begin{aligned} \begin{array}{c c c} if \ u^{n+1}_{i,j} > \underset{{(k,l)\in \mathbf{N}_{i,j} }}{\max } u^{n}_{k,l}&{} \ \ \mathrm{then} \ \ &{} u^{n+1}_{i,j} = \underset{{(k,l)\in \mathbf{N}_{i,j} }}{\max } u^{n}_{k,l} \\ if \ u^{n+1}_{i,j} < \underset{{(k,l)\in \mathbf{N}_{i,j} }}{\min } u^{n}_{k,l}&{} \ \ \mathrm{then} \ \ &{} u^{n+1}_{i,j} = \underset{{(k,l)\in \mathbf{N}_{i,j} }}{\min } u^{n}_{k,l}. \end{array} \end{aligned}$$

(17)

Figure 3 shows the solution of the above iterative scheme for an initial shape given by the characteristic function of an ellipse. This illustrates the influence of the updating step given by (17): without this updating step the solution using (15) shows a number of artifacts (visible as bright spots). On the other hand, using the above explicit scheme, the computation of the affine distance inside the shape is straightforward: after initializing $d_A(i,j)\equiv 0$ for any pixel position $(i,j)$, $u^0_{i,j}$ is defined by

$$\begin{aligned} u^{0}_{i,j}=\left\{ \begin{array} [c]{ccc} -1 &{} \quad \mathrm{if} &{} (i,j)\in S_{0}\\ 1 &{} \quad \mathrm{if} &{} (i,j)\notin S_{0}. \end{array} \right. \end{aligned}$$

Then $u^n_{i,j}$ is computed iteratively and at each iteration $d_A(i,j)$ is updated by

$$\begin{aligned} if\big (u^n_{i,j}<T\big ) \ \ \mathrm{then} \ \ d_A(i,j)=d_A(i,j)+\delta \tilde{t}, \end{aligned}$$

where iterations stop when $\{(i,j): u^n_{i,j}< T\}=\emptyset$. Observe that, theoretically, due to the morphological principle, the solution should be independent of the value of the threshold $T$ (for $T\in (-1,1)$). However, as illustrated in Fig. 3, the numerical discretization introduces an artificial smoothing effect around the shape boundary and therefore, in practice, as will appear below, the choice of the threshold $T$ can modify the estimation of the affine distance $d_A(i,j)$.

Fig. 3

From left to right i an initial shape given by an ellipse, ii illustration of the discrete solution of (15) without updating $u^{n+1}_{i,j}$ using (17), and iii illustration of the discrete solution of (15) updating $u^{n+1}_{i,j}$ using (17)

In order to check the accuracy of the proposed discretization scheme and the influence of the threshold $T$ choice and the updating step (17) we are going to use the explicit closed form of solution of Eq. (14) in case the initial shape is an ellipse. It is known that if $S_0$ is an ellipse of major and minor semi-axes given by $a_0,b_0>0$, then the evolution of the ellipse under the action of the affine multiscale analysis given by (7) is an ellipse with the same eccentricity and semi-axes given by

$$\begin{aligned} a(t)= & {} \sqrt{\frac{a_{0}}{b_{0}}}\left( \left( \sqrt{a_{0}b_{0}}\right) ^{\frac{4}{3}}-t^{\frac{4}{3}}\right) ^{\frac{3}{4}};\\ b(t)= & {} \sqrt{\frac{b_{0}}{a_{0}}}\left( \left( \sqrt{a_{0}b_{0}}\right) ^{\frac{4}{3}}-t^{\frac{4}{3}}\right) ^{\frac{3}{4}}. \end{aligned}$$

A straightforward computation yields the following expression of the affine distance through the direction of the ellipse major semi-axis:

$$\begin{aligned} d_{A}((x,y),C_{0})=\left( \left( \sqrt{a_{0}b_{0}}\right) ^{\frac{4}{3} }-\left( s(x,y)\sqrt{\frac{b_{0}}{a_{0}}}\right) ^{\frac{4}{3}}\right) ^{\frac{3}{4}}, \end{aligned}$$

where $s(x,y)$ is the Euclidean distance from the ellipse center to $(x,y)$. In the same way if $(x,y)$ belongs to the line passing by the ellipse center and oriented in the direction of minor semi-axis then

$$\begin{aligned} d_{A}((x,y),C_{0})=\left( \left( \sqrt{a_{0}b_{0}}\right) ^{\frac{4}{3} }-\left( s(x,y)\sqrt{\frac{a_{0}}{b_{0}}}\right) ^{\frac{4}{3}}\right) ^{\frac{3}{4}}. \end{aligned}$$

To show quantitative comparison results between the actual and the approximate solutions when the initial shape is an ellipse, one can use as error measure the average squared distance between the actual and the approximated solution through the ellipse semi-axis. In the experiments presented in this paper we used an ellipse of semi-axis given by $a_0=56$ and $b_0=28$. First we measured the influence of the threshold $T$ choice. Figure 4 shows the evolution of the average error across ellipse semi-axis when we modify $T$ using the discretization scheme including the updating step (17). Observe that the optimum threshold value is around $T=0.07$.

Fig. 4

Evolution of the average error across the ellipse semi-axis when the threshold $T$ is modified using the discretization scheme including the updating step (17)

To measure the influence of the discretization step $\delta \tilde{t}$ and the iteration updating step (17), Table 1 shows the average error for several values of the time discretization steps $\delta \tilde{t}$. When $\delta \tilde{t}$ is small there is a significant improvement in the error measure with the updating procedure (17). On the other hand, the error tends to stabilize around $\delta \tilde{t}=0.01$. Figure 5 shows the expected theoretical value of $d_A(x,y)$ and the solutions obtained by the discretization scheme with and without using the updating step (17). There is no significant visual difference between the actual solution and the discrete solution using the updating step (17). In the case where such updating step is not used, some spurious oscillations appear near the ellipse center.

Table 1 The square average error through the ellipse main axis for several time discretization steps $\delta \tilde{t}$ using threshold $T=0.07$

Next, we study the influence of the scheme’s spatial step $h$, using the expression (16) to define a coupling between the time and space steps. Table 2 gives the results using different values of the spatial discretization $h$. Observe that for high values of $h$ the ellipse boundary is approximated less accurately, and therefore the error measure increases. For $h<1$ the error increases with respect to $h=1$. There are a number of issues that can explain this behavior: first we use a smaller time step. Thus, even if at each step we can expect a better approximation of the solution, more iterations of the scheme are needed to get the solution. Thus, due to the strong nonlinear behavior of the equation it is not clear if the global solution approximation improves when $h\rightarrow 0^+$. Second, as the ellipse is discretized, there are a number of interpolation problems that could appear when $h\rightarrow 0^+$. Third, we use a discrete characteristic function as level set approximation of the initial ellipse. Even if theoretically the solution of the equation should remain a characteristic function, it is well known that a finite difference scheme introduces an artificial diffusion. This diffusion effect is higher when the number of iterations, which is the case when $h\rightarrow 0^+$.

Fig. 5

Illustrating the values of the affine distance $d_A(x,y)$ through the major and minor semi-axis of an ellipse. We present the expected theoretical value (in red), the solution obtained by the discretization scheme with the updating step (17) (in green) and without the updating step (in blue). The oscillations which appear in the middle correspond to some artifacts introduced by the discrete scheme without the updating step (17) (Color figure online)

Table 2 The square average error through the ellipse main axis for several discretization space $h$ and time steps $\delta \tilde{t}$ using the coupling (16) and the threshold $T=0$

An interesting advantage of this simple discretization scheme is that it can be easily implemented using GPU programming techniques which provide an efficient algorithm : in a $512 \times 768$ image an iteration of this explicit numerical scheme takes just $5.7995$ ms.

To compute the affine distance outside $S_0$ we used the multiscale analysis generated by the partial differential equation:

$$\begin{aligned} u_{\tilde{t}} = -\left( - \left( \left( u_{y}\right) ^{2}u_{xx} - 2u_{x} u_{y}u_{xy} + \left( u_{x}\right) ^{2}u_{yy}\right) _{-}\right) ^{\frac{1}{3}}, \end{aligned}$$

(18)

The equation was discretized exactly in the same way as in the previous case. Again the initialization was $d_A(i,j)\equiv 0$. At each iteration $d_A(i,j)$ was updated by

$$\begin{aligned} if(u^n_{i,j}>0) \ \ \mathrm{then} \ \ d_A(i,j)=d_A(i,j)+\delta \tilde{t}. \end{aligned}$$

Notice that if $(i,j)$ is outside the convex hull of $S_0$ then $u^n_{i,j}>0$ for all $n$. To stop iterations in that case, we point out that using Lemma 6, we obtain that $S(t)$ is an increasing collection of shapes which converges towards the convex hull of $S_0$ and therefore we can stop iterations looking at the size variation of the set $S_n=\{(i,j): u^n_{i,j}\le 0\}$.

To illustrate the behavior of the affine distance $d_A(x,y)$ for non-convex shapes we use the shapes presented in Fig. 6. In this case, one shape was obtained from the other one by applying an affine transformation satisfying $|A|=1$. In Figs. 7 and 8 we show the affine distance estimation for both shapes for points inside the shapes as well as some level contours of the affine distance function. In Figs. 9 and 10 we show the affine distance and level contours for points outside the shapes. For comparison purposes, Figs. 11 and 12 display the Euclidean distance inside and outside the shapes. The Euclidean distance is of course not affine invariant. In particular, inside the swan head one can observe a significant difference between both shapes.

Fig. 6

Shapes used to illustrate the behavior of $d_A(x,y)$ for non-convex shapes. One shape is obtained from the other one by applying an affine transformation satisfying $|A|=1$

Fig. 7

Illustration of the affine distance, $d_A(x,y)$, inside the shapes shown in Fig. 6

Fig. 8

Illustration of some level contours for the affine distance, $d_A(x,y)$, inside the shapes shown in Fig. 6

Fig. 9

Illustration of the affine distance, $d_A(x,y)$, outside the shapes shown in Fig. 6

Fig. 10

Illustration of some level contours of the affine distance, $d_A(x,y)$, outside the shapes shown in Fig. 10

Fig. 11

Illustration of the Euclidean distance, $d_E(x,y)$, inside the shapes shown in Fig. 6

Fig. 12

Illustration of the Euclidean distance, $d_E(x,y)$, outside the shapes shown in Fig. 6

We intend to study in detail the potential applications of the proposed affine invariant distance in future works. Among other possibilities, the affine distance could be used to detect features such as corners, which correspond to locations where the distance function varies linearly (with respect to the corner angle) and could be detected using watershed techniques. Another potential application is to define affine invariant shape signatures for shape comparison. For example, given a shape contour $C_0$, the function

$$\begin{aligned} Area(d)=\big |\{(x,y):d_A((x,y),C_0)>d\}\big | \end{aligned}$$

is a signature of the shape that could be used for affine invariant shape comparison.

5 Conclusion

In this paper we used the affine invariant multiscale analysis to define the affine invariant distance from a point to the boundary of a shape. This affine invariant distance definition is based on a generalization of the Euclidean distance definition estimated using the level set formulation of the solution of the eikonal equation. The basic mathematical properties of this affine invariant distance definition were explored and a simple finite difference numerical scheme was proposed, based on a GPU implementation, to estimate this distance. We forced the associated discrete solution to satisfy a discrete local comparison principle. The experiments presented show the accuracy and robustness of the numerical scheme using the actual solution of an ellipse and we also illustrated the behavior of the proposed affine distance for general non-convex shapes.