On the decomposition and local degree of multiple saddles

Sara Derivière^{∗}, Tomasz Kaczynski^{†}, Pierre-Olivier Vallerand^{‡}

May 23, 2008

Abstract

Topological analysis of digital images motivates exploring the Euler– Maxwell formula in the absence of non-degeneracy and isolation conditions. We study the local degree of gradient fields at a k–fold saddle, and provide a generalization of the formula for degenerate critical points.

1 Introduction

This paper is the first step towards the answer to questions posed in [1, 2], concerning the Euler–Maxwell formula in the context of topological analysis of digital images. In those papers, the object of the study is a scalar function f : X → ℝ on a discrete multidimensional data set X. In the planar case studied in [1], f is geometrically interpreted as a height field. The features of interest are critical points of f, that is, peaks, pits, and saddles. Once the critical points are identified, various techniques are used to analyze relationships between them and to trace structures such as ridge and ravine lines, and isolines. In the case of data of higher dimensions studied in [2], the geometric interpretation of critical points is more complex but those points play equally important role in further study, such as the construction of the level sets given by f = c. A good understanding of the nature of saddles is especially important because these are points where level sets intersect. The smooth Morse theory [12] has inspired researchers in imaging science, however, in its rigorous applications such as [5], one spends a lot of effort on forcing, by local deformation of data, the main hypothesis of the Morse theory stating that critical points of f must be isolated and non-degenerate. This way one adjusts the finite input to the theory, with the aim at validating practical implementations. There is a discrete Morse index theory due to Forman [6], but it also deforms the data and, besides, its goals are different than those in the image analysis. In [1, 2], an effort is made to establish a discrete analogy of the Morse theory for a function f defined on pixels (mathematically speaking, elementary cubes) while keeping the original geometry, that is, without forcing the isolation and non-degeneracy of critical points. The main results obtained there are the algorithms detecting and classifying critical regions, and constructing the so-called Morse connections graph, whose nodes are critical components and edges display the existence of trajectories connecting them. A computer experimentation is done in [1] on planar images.

∗supported by the Tomlinson Visiting Scholarship of Bishop’s University

†supported by the NSERC individual Discovery Grant

‡supported by the NSERC USRA

Among questions addressed in [1, 2], one is related to extensions of the formula

♯ pits − ♯ passes + ♯ peaks = 2  (1)

for a height function defined on the surface of the globe, that is, the twodimensional sphere S^{2}. This formula is essentially due to Maxwell [13] but is often called Euler formula due to its similarity to the Euler characteristics of the sphere. In imaging science, it is used (often reinforced) as a criterion of correctness of programs extracting information on critical points from discrete data. A generalization of this formula to arbitrary dimensions and to Morse functions f : M → ℝ on compact smooth manifolds is the Morse formula

∑_{i=1}^{n}(−1)^{λ(p_{i})} = χ(M) ,  (2)

where p_{i} are the non-degenerate critical points of f, λ(p_{i}) is the Morse index of p_{i} defined as the sign of the Hessian of f at p_{i}, and χ(M) is the Euler-Poincaré characteristics of M. The terminology related to Morse functions is recalled in Section 2.

In applications to digital 2D image analysis, the functions are neither defined on manifolds, nor on the sphere S^{2}, but on some rectangular regions D ⊂ ℝ^{2}. One makes use of the formula (2) by assuming that D is “surrounded by a depression”, so that we may compactify the plane ℝ^{2} to the sphere S^{2} with a point at infinity where f assumes an absolute minimum. The same argument is used in an arbitrary dimension for a function on a bounded rectangular domain in D̄ ⊂ R^{d}. In mathematical terms, the assumption on a surrounding depression can be formulated by saying that f is decreasing through ∂D towards the exterior of D, or, that ∇f points inward on ∂D. For the d–dimensional sphere S^{d}, we have χ(S^{d}) = 1+(−1)^{d}. Thus by removing the added minimum point at infinity, we should obtain the formula

∑_{i=1}^{n}(−1)^{λ(p_{i})} = (−1)^{d}  (3)

for a function f : D̄ → ℝ whose gradient points inward on ∂D.

An observation which motivated the direction chosen in this paper is that the use of the passage through a theory of compact manifolds is somewhat artificial: the original function is defined on D̄ ⊂ R^{d} and we end up formulating the result for such functions. Thus we want a more elementary and direct proof confined within the framework of functions on bounded domains in ℝ^{d}.

There is such a theory at our disposal: it is the Brouwer degree, also called topological degree theory of vector fields which we may apply here to the gradient of f. Moreover, the degree theory remains valid for gradients of functions which have degenerate critical points, such as monkey saddles. More than that, it is valid for arbitrary continuous vector fields.

In the introductory Section 2, the basics of the degree theory are recalled to give an alternative proof of the formula (3) in the non-degenerate case.

In Section 3, we discuss a known model for the monkey saddle and use it to give a general definition of k–fold saddle using the terminology of stable and unstable manifolds from the theory of dynamical systems. We next give a combinatorial procedure for decomposing a k–fold saddle to k simple saddles.

Section 4 is concerned with any isolated but possibly degenerated critical points in ℝ^{2}. We first state a version of Wilson and Yorke isolating block, adapted to our context. We prove that any isolated critical point is either a minimum, maximum, or a k–fold saddle, whose local degree is 1 in the first two cases and −k in the last one. We next use the additivity property of degree to provide a generalization of (3) in the presence of k–fold saddles.

As we said, the topological degree is valid for any continuous vector field on a domain in ℝ^{d} and even more, any upper semi-continuous multivalued vector field with compact convex values (more generally, contractible or aspherical values) and it is additive with respect to unions of regions. Thus it should suit better the applications to discrete data and critical regions in the context of [1, 2]. This is the project for the future work discussed in Section 5.

2 Degree of a generic gradient field

The concept of topological degree goes back to Brouwer [3, 1912] but we will mainly use here a more recent analytic viewpoint on the degree due to Nagumo [14, 1951] which is a common choice in reference texts such as [10]. In applications to nonlinear analysis, one usually needs the Leray-Schauder degree which is the generalization of the Brouwer degree to infinite dimensional spaces.

The degree is a tool for investigating the equation F (x) = q, where F : D̄ → ℝ^{d} is a continuous map of the closure of a bounded open subset D of ℝ^{d} and q ∈ ℝ^{d}. If F is admissible, that is, if F (x) ≠ q for x ∈ ∂D, one can associate an integer deg(F, D, q) to the triple (F, D, q); this integer, called the topological degree of F on D with respect to q, has certain properties usually referred to as the additivity, homotopy and normalization axioms which determine the degree and sometimes aid in its computation.

From the viewpoint of solving F (x) = q, the most important fact is that deg(F, D, q) ≠ 0 implies the existence of x in D with F (x) = q. It is also useful to know that A1. (robustness) If G : \overline{D} → ℝ^{d} is a continuous map such that

sup_{x∈∂D} ||G(x) − F (x)|| < inf_{x∈∂D} ||F (x) − q||,

then deg(F, D, q) = deg(G, D, q);

A2. (additivity) If D = D_{1} ∪ D_{2} where D_{1} and D_{2} are open sets such that F (x) ∉ q for x ∈ ∂D_{1} ∪ ∂D_{2} ∪ \overline{D_{1} ∩ D_{2}}, then

deg(F, D, q) = deg(F, D_{1}, q) + deg(F, D_{2}, q).

The robustness property A1 leads to the following homotopy property

A3. (homotopy) Let H : \overline{D} × [0, 1] → ℝ^{d} be a continuous map such that

H(x, t) ≠ q for all x ∈ ∂D.

If F = H(·, 0) and G = H(·, 1), then deg(F, D, q) = deg(G, D, q). The map H is called admissible homotopy from F to G.

The analytic construction of the degree given e.g. in [10] goes in several steps of approximation. First, one assumes that F is generic, that is, it is of class C^{1} and the Jacobian of F at p, J_{F} (p) := det DF (p), is non-zero at any p such that F (p) = q. One proves that, in this case, the zeros of F are isolated so, since \overline{D} is compact, there are finitely many of them. Let F^{−1}(q) = {p_{1}, p_{2}, …, p_{n}}. Then the degree is defined by the formula

deg(F, D, q) = Σ_{i=1}^{n} sgnJ_{F} (p_{i}).  (4)

In particular, if D is a bounded neighborhood of the origin of coordinates and id is the identity map, then we instantly get

A0. (normalization) deg(id , D, 0) = 1.

One next proves that deg(F, D, q) is locally constant in the class of admissible generic C^{1} maps with respect to the supremum norm. Finally, one proves that any admissible continuous map F is approximated by an admissible generic map G satisfying the inequality of A1, so we may put deg(F, D, q) := deg(G, D, q).

Let now f : \overline{D} → ℝ be a function of class C^{2}. A point p ∈ \overline{D} is critical if the gradient F = ∇f vanishes at p and it is called regular otherwise. So, the critical points of f correspond to the zeros of F. The function f is called a Morse function if all of its critical points p are non degenerate, i.e. if the Hessian of f given by H_{f} := det D^{2}f does not vanish at p. Note that the Hessian of f is precisely the Jacobian of F = ∇f. Thus, f is a Morse function if and only if its gradient F is generic for degree computation at q = 0. From now on, we assume that q = 0 and denote the degree of F on D with respect to 0 by deg(F, D) instead of deg(F, D, 0).

Given a Morse function f, the index of any critical point p, denoted by λ(p), is the number of negative eigenvalues of D^{2}f(p). Thus sgn JF (p) = (−1)^{λ(p)}, hence the left-hand sides of the formulas (3) and (4) coincide. Here is a more visual, geometric way of introducing the Morse index. It is known that there exist local C^{2} coordinates originating at p such that, in those coordinates, f becomes a quadratic polynomial

f(x) = c + ∑_{i=1}^{d} λ_{i}x_{i}^{2},  (5)

where λ_{i} ∈ {−1, 1}. Then λ(p) is the number of indices i such that λ_{i} = −1. If λ(p) = 0, p is a local minimum and if λ(p) = d, it is a local maximum. The intermediate values of λ(p) classify different types of simple (non degenerate) saddles at p. In particular, in ℝ^{2}, the result formulates as follows.

Lemma 2.1 (The Morse lemma) Let p be a non degenerate critical point of a function f of two variables and let c = f(p). Then there exists a C^{2} change of coordinates in a neighborhood of p, taking p to 0, such that the function f expressed with respect to the new local coordinates (x, y) takes one of the following three standard forms

1. f(x, y) = c + x^{2} + y^{2} (minimum),

2. f(x, y) = c − x^{2} − y^{2} (maximum)

3. f(x, y) = c + x^{2} − y^{2} (simple saddle).

For those standard forms, we easily get the following.

Proposition 2.2 Let F = ∇f where f is the quadratic function in (5) and let D = B^{d} be the unit ball in ℝ^{d}. Then

deg(F, D) = λ_{1}λ_{2} ⋯ λ_{d} .

In particular, in ℝ^{2}, deg(F, D) = 1 when 0 is a local extremum (minimum or maximum), and deg(F, D) = −1 when 0 is a saddle.

Proof: F is a linear map whose matrix is diagonal with entries λ_{1}, λ_{2}, ⋯ λ_{d} ∈ {−1, 1}, so the degree formula for generic maps (4) applies.

We may also deduce the formula (3) from the properties of degree in the case when D = B^{d} is the open unit ball in ℝ^{d}. The condition that F = ∇f points inward on ∂D can be formulated in terms of the scalar product as F (x) · n(x) < 0 at all x ∈ ∂D, where n : ∂D → ℝ^{d} is the outward normal vector field. When D = B^{d}, ∂B^{d} = S^{d−1} is the unit sphere and n(x) = x and we get the condition F (x) · x < 0. Similarly, F points outward on ∂D if F (x)·n(x) > 0 at all x ∈ ∂D, so if D = B^{d}, we get the condition F (x)·x > 0. Thus, we want to prove the following result.

Theorem 2.3 Let f : \overline{B}^{d} → ℝ be a Morse function satisfying the condition

x · ∇f(x) < 0 for all x ∈ S^{d−1}.  (6)

Let {p_{1}, p_{2}, …, p_{n}} be the set of all critical points of f in B^{d}. Then the Euler–Maxwell–Morse formula (3) holds in ℝ^{d}.

Proof: We calculate the degree of F = ∇f on D with respect to q = 0. By (6), F (x) ≠ 0 for x ∈ S^{d−1}, hence F is admissible. Since f is a Morse function, F is generic, so deg(F, D) is given by (4). On the other hand, the degree of the linear map −id given by −id(x) = −x on B^{d} is (−1)^{d}. Hence, it remains to prove that

deg(F, D) = deg(−id , D).

For this, we will use the homotopy property A3. Define H : \overline{B^{d}} ×[0, 1] → ℝ^{d} by

H(x, t) = (1 − t)F (x) − tx.

Then H(x, 0) = F (x) and H(x, 1) = −x. It remains to show that H is admissible. Suppose that on the contrary, there exists t ∈ [0, 1] and x ∈ S^{d} such that H(x, t) = 0. Since F and −id are admissible, this is impossible for t = 0, 1 and we may assume that 0 < t < 1. By (6), we get

0 = x · H(x, t) = (1 − t)x · F (x) − tx · x < 0,

a contradiction.

We wish to know if Proposition 2.2 remains true in original coordinates and if Theorem 2.3 can be extended to domains diffeomorphic to B^{d}. The Morse lemma suggests that this is true but we need the following property of invariance of degree of ∇f under the change of coordinates in the domain of f.

Its proof relies on lengthy but elementary vector calculus arguments. By a diffeomorphism between closed bounded regions of ℝ^{d} we mean a homeomorphism extending to a diffeomorphism of their neighborhoods.

Lemma 2.4 Let D be a bounded domain in ℝ^{d} with a C^{2} boundary ∂D and let f : \overline{D} → ℝ be a C^{1} function. Suppose that there exists a C^{2} diffeomorphism Φ : \overline{B}^{d} → \overline{D} and put g = f ∘ Φ. Then

(a) F := ∇f is admissible in D if and only if G := ∇g is admissible in B^{d};

(b) If F is admissible, then deg(F, D) = deg(G, B^{d});

(c) Moreover, F is inward (respectively outward) at Φ(x) ∈ ∂D if and only if G is inward (respectively outward) at x ∈ S^{d−1}.

Theorem 2.3 and Lemma 2.4 instantly imply the following.

Corollary 2.5 Let \overline{D} be a region C^{2}–diffeomorphic to a unit ball and f : \overline{D} → ℝ a Morse function whose gradient is inward on ∂D. Let \{p_{1}, p_{2}, …, p_{n}\} be the set of all critical points of f in B^{d}. Then the formula (3) holds in ℝ^{d}.

The classical result of the Morse theory can now be deduced as an easy consequence of the previous statements. The Euler-Poincaré characteristic [11] of a compact manifold M (more generally, of any compact space homeomorphic to a compact polyhedron) is given by

χ(M) = ∑_{i=0}^{m}(−1)^{i}β_{i}(X),

where β_{i}(X), the Betti numbers of X, are the ranks of the homology groups H_{i}(X).

Corollary 2.6 Let f : S^{d} → ℝ be a Morse function and let {p_{0}, p_{1}, p_{2}, …, p_{n}} be the set of all its critical points. Then the Euler–Maxwell–Morse formula

∑_{i=0}^{n}(−1)^{λ(p_{i})} = χ(S^{d}) = 1 + (−1)^{d} ,  (7)

holds on S^{d}.

Proof: Since S^{d} is compact, f assumes its minimum at some point, let it be p_{0}. Let U be an open ball in S^{d} centered at p_{0}, isolating it from other critical points, to which the Morse lemma applies. The stereographic projection is a diffeomorphism of S^{d} \ {p_{0}} onto ℝ^{d} which takes S^{d} \ U to some closed ball \overline{D} ⊂ ℝ^{d} centered at the origin. Since the Morse index of a minimum point is 1, it is enough to show that

∑_{i=1}^{n}(−1)^{λ(p_{i})} = (−1)^{d} ,

This can be deduced from Corollary 2.5 applied for the composition of the inverse stereographic projection with the restriction of f to S^{d} \ {p_{0}}.

3 Local degree at a k–fold saddle

In this section we study functions f in the plane ℝ^{2} whose critical points are isolated but possibly degenerate.

3.1 A model of a k–fold saddle

The most commonly seen case of an isolated degenerate critical point is a monkey saddle. First, if

f_{1}(x, y) = x^{2} − y^{2},

the origin of coordinates is a simple saddle of f: The vectors (1, 0) and (−1, 0) define two ascending directions or, in terms of the topography of the surface h = f(x, y) two ridge lines emanating from the origin. Similarly, the vectors (0, 1) and (0, −1) define two descending directions or two ravine lines. The monkey saddle is, roughly speaking a critical point which is the origin of three ridge lines separated by three ravine lines. By the Morse Figure 1: Left: Level lines and gradient filed for the monkey saddle. Right: Trajectories, ridge and ravine lines. The displayed vector field permits tracing the winding of F as q moves on counterclockwise on a circle described in Remark 3.2.

Lemma, this is of course impossible if H_{f}(0, 0) ≠ 0. A simple model for the monkey saddle, illustrated by Figure 1 is given by

f_{2}(x, y) = x^{3} − 3xy^{2}.

More generally, a k–fold saddle is a critical point originating (k + 1) ridge lines separated by (k + 1) ravine lines. A simple saddle is a 1–fold saddle and a monkey saddle is a 2–fold saddle.

The most transparent formula for a function giving rise to a k–fold saddle is in terms of complex numbers. We identify ℝ^{2} with the complex plane ℂ and use the variable z = x + iy = (x, y)^{T}. Then, z^{2} = (x^{2} − y^{2}) + 2ixy and z^{3} = (x^{3} − 3xy^{2}) + i (3x^{2}y − y^{3}), that is f_{1} = ℜe (z^{2}) and f_{2} = ℜe (z^{3}). Consider the function

f(z) = ℜe (z^{k+1})  (8)

Note that f is positively homogeneous in the sense that f(tx, ty) = t^{k+1}(x, y) for all t > 0, so the ascending and descending directions are determined by the values of f on the circle S^{1} given by |z| = 1. The maximum of f is 1 assumed at the roots of z^{k+1} = 1 and the minimum is −1 assumed at the roots of z^{k+1} = −1. In polar coordinates, the ridge lines are the rays emanating from the origin at the angles θ_{j} = \frac{2πj}{k+1} and the ravine lines are rays at the angles θ_{j} + \frac{π}{k+1}.

Theorem 3.1 Let F = ∇f, where f is given by (8). Then

deg(F, B^{2}) = −k.

Proof:

Consider the function g : ℂ → ℂ, given by g(z) = z^{k+1}. Let u(x, y) and v(x, y) be the real and imaginary parts of g respectively, so that f(z) = u(x, y). Then ∇f = (u_{x}, u_{y})^{T} where u_{x} and u_{y} denote the partial derivatives of u with respect to x and y respectively. Using the Cauchy-Riemann equations, we get

g′(z) = u_{x}(z) + iv_{x}(z) = u_{x}(z) − iu_{y}(z) ≅ (u_{x}, −u_{y})^{T}

On the other hand, g′(z) = (k + 1)z^{k}, so \overline{∇f} = (k + 1)z^{k}, where \overline{z} stands for the complex conjugate of z. It is known that the topological degree of a holomorphic function h : \overline{B}^{2} → ℂ which has no roots on S^{1} is the number of roots of h in B^{2} counting their multiplicity (see [10, Sec. 1.4]). In our case, h = g′ and this number is k.

For the sake of visibility, we mention that this number can be computed from the residue formula (see for example [8, p. 353])

\begin{aligned}deg(h, B^{2}) & = \frac{1}{2πi} ∫_{S^{1}} \frac{h′(z)}{h(z)}dz = \frac{1}{2πi} ∫_{S^{1}} \frac{k(k + 1)z^{k−1}}{(k + 1)z^{k}} dz \\ & = \frac{k}{2πi} ∫_{S^{1}} \frac{dz}{z} = k, \end{aligned}

where S^{1} is positively oriented. Thus,

deg(\overline{F} , B^{2}) = deg(h, B^{2}) = k.

Next, consider G : ℝ^{2} → ℝ^{2}, G(z) = (x, −y) = \overline{z}. Then, \overline{F} = G∘F. Since G is a linear isomorphism taking B^{2} to itself, the multiplication theorem [10, Sec. 2.3] implies that

deg(\overline{F} , B^{2}) = deg(G ∘ F, B^{2}, 0) = deg(G, B^{2}, 0) deg(F, B^{2}, 0).

By definition,

deg(G, B^{2}, 0) = sgn det ∇G = −1,

so

k = deg(\overline{F} , B^{2}) = −deg(F, B^{2}, 0).

Remark 3.2 Here is a geometric interpretation of the analytic proof provided above, based on the interpretation of degree as the winding number, and of ∇f as the vector pointing the direction of the steepest ascend of f, interpreted as the height function. We refer to Figure 1. We register the angle traced by the vector F = ∇f(q) attached to the origin 0, as the point q = (x, y) moves counterclockwise on the unit circle. When q = (1, 0) is on the first ridge line at θ_{0} = 0, F points in the same direction as 0q. When q moves counterclockwise towards the isoline at the angle \frac{π}{2(k+1)}, f decreases, so F rotates clockwise towards the left ridge line. When q reaches the first ravine line at the angle \frac{π}{k+1}, F points in the opposite direction of the angle \frac{π}{k+1} − π, and when the point is at the next ridge line θ_{1} = \frac{2π}{k+1}, F points again the same direction as 0q. Thus, the angle traced by F between the first two ridge lines is α = \frac{2π}{k+1} −2π. The same scenario repeats between any two consecutive ridge lines, so when q is back at θ = 2π, the angle traced by F is (k + 1) α = −2kπ. Thus the winding number of F around 0 is −k.

3.2 Stable and unstable manifolds

In order to generalize Theorem 3.1, we need to give a more precise definition of a k–fold saddle of some function f̃. One possible way is to define it in similar terms as the Corollary 2.5, by requiring that there exists a diffeomorphism φ : \overline{B^{2}} → \overline{D} with φ(0) = p and f̃∘ φ = f, where f is the model function given in (8). Then Lemma 2.4 can be used to conclude that the degree of f̃ is −k. However, such a condition is hard to verify in practice.

In order to define the k–fold saddle for any C^{2} function, we should first state what is meant by ridge and ravine lines in the discussion opening Section 3.1. This can be done in terms of the flow φ(t, z) generated by the differential equation ż = F (z), where F = ∇f. Since F (z) shows the direction of the fastest ascent, the ridge lines are formed by trajectories of φ “climbing up” from p as time increases, that is, converging to p as t → −∞. The points on those trajectories belong to the unstable manifold of p defined by

W^{u}(p) = {z ∈ M | lim_{t→−∞} φ(t, z) = p} .

The ravine lines are formed by trajectories of φ “sliding down” from p or, more precisely, converging to p as t → ∞. The points on those trajectories belong to the stable manifold of p defined by

W^{s}(p) = {z ∈ M | lim_{t→∞} φ(t, z) = p} .

It is easy to check for the function in (8) that its unstable and stable manifolds are indeed the described rays θ_{j} and, respectively, θ_{j} + \frac{π}{k+1}.

Note that the terminology “manifold” for W^{u}(p) and W^{s}(p) is only justified if f is a Morse function. In this case the dimensions of those manifolds are equal to the numbers of positive and, respectively, negative eigenvalues of the Hessian of f at p. Thus dim W^{s}(p) = λ(p) is the Morse index^{1} of p. In a degenerate case, one may encounter for example W^{u} containing a cone of ridge lines ascending from p not separated by ravine lines. In order to handle such cases we introduce the following sets. Let N be an isolating neighborhood of p, that is, one of its closed neighborhood which does not contain other critical points. We put

N_{p} = {z ∈ N | f(z) > f(p)};
N_{n} = {z ∈ N | f(z) < f(p)};

and

N_{z} = {z ∈ N \ {p} | f(z) = f(p)}.

In the case of an isolated minimum, N_{p} = N \ {p} and N_{n} = ∅. For an isolated maximum, it is the reverse. From the isolation condition and the hypothesis that f is of class C^{2}, it follows that N_{z} ∪ \{p\} = \overline{N}_{p} ∩ \overline{N}_{n} and that it consists of isolines. For our model (8) of a k–saddle, the connected components of N_{p} are cones given by |θ − θ_{j}| < \frac{π}{2(k+1)} and those of N_{n} are given by |θ − θ_{j} − \frac{π}{k+1}| < \frac{π}{2(k+1)}. The set N_{z} is given by z^{k+1} = ±i and consists of rays at the angles θ_{j} ± \frac{π}{2(k+1)}.

1In the literature, one often considers the reverse flow of the equation ẋ = −∇f, so to make the potential of the gravitation field increasing along the trajectories as t increases.

In this case, the role of stable and unstable manifolds is reversed.

Definition 3.3 A k–fold saddle of a C^{2} function f is a critical point p of f whose unstable and stable manifolds contain (k+1) ridge lines S_{1}, S_{2}, …, S_{k+1} and (k + 1) ravine lines V_{1}, V_{2}, …, V_{k+1} which satisfy the following conditions.

(a) The sets S = {S_{1}, S_{2}, …, S_{k+1}} and V = {V_{1}, V_{2}, …, V_{k+1}} are interlaced in the following sense: The set N \ ({p} ∪ S ∪ V) has 2(k + 1) connected components called wedges. Each wedge is bounded in N\{p} by one ridge line and one ravine line.

(b) Each connected component of N_{p} contains one ridge line from S and each connected component of N_{n} contains one ravine line from V.

This definition permits ordering ridge and ravine lines as

(S_{1}, V_{1}, S_{2}, V_{2}, …, S_{k+1}, V_{k+1})  (9)

in a circle around {p}, so that the two consecutive elements in this sequence (where S_{1} follows V_{k+1}) bound a wedge.

3.3 Decomposition of a k–fold saddle

The degree theory assures that a degenerate critical point p can be replaced by a number of non-degenerate ones by a small perturbation of the vector field, which does not change the global degree. More precisely, the vector field F is replaced by a shifted vector field F (x) − q in a small region D around p. The measure theoretical arguments imply that there exist arbitrarily small values of q for which the zeros of the perturbed field are non-degenerated. This is illustrated on Figure 2. It is however not always easy to explicitly determine q and analytically calculate the local degrees at the new critical points. The goal of this section is to establish a combinatorial graph-theoretical procedure for the decomposition of k–fold saddles into k–simple saddles, without relaying on the smoothness and transversality assumptions. The main idea comes from Edelsbrunner et al., see [5]. We show that the decomposition preserves the degree on D. The described procedure is useful for understanding and construction of the Morse connections graph described below.

We introduce first some terminology from [1] related to Morse connections graph. This is a graph whose nodes are critical points of the flow (minimum, maximum, k–fold saddle). Each node is connected to other nodes using oriented edges of the graph. To a pair of critical points (p, q), we associate an edge called an ascending direction if there is a trajectory converging to p as t → −∞ and to q as t → ∞, equivalently, if W^{s}(p) ∩ W^{u}(q) ≠ ∅, Figure 2: Above: The 3–fold saddle and its unfolding to two simple saddles by a shift of F in the x-direction. Below: Two different decompositions of the monkey saddle. In the phase portrait on the left, a shift of F along the x-axis is applied. The ridge line of one saddle and the ravine line of another produce a connecting trajectory between the two, as described in Algorithm 3.5. On the right, a small shift in the y-direction makes those two lines separate and escape outside of the picture.

Figure 3: V_{3} = {V 1, V 2, V 3} and S_{4} = {S1, S2, S3, S4} are interlaced.

and they are called descending direction, if there is a reverse trajectory. For example, if p is a minimum, all the edges attached to p are ascending directions; similarly, if p is a maximum, all the edges attached to p are descending directions . But if p is a k–fold saddle, there are (k + 1) ascending directions which correspond to ridge lines and (k + 1) descending directions which correspond to ravine lines.

In practical applications to imaging, one works not in a compact manifold but in a bounded rectangular region of a plane, so ridge and ravine lines may escape the boundary picture. That way we assume that f is decreasing towards the boundary, so that the escaping lines can be regarded as lines connecting a given critical point to the point compactifying the plane to the sphere, where f assumes the global minimum.

We consider a k–fold saddle p, an isolating neighborhood N of p, and a portion of the Morse connections graph corresponding to ridge and ravine lines which leave or enter N. Thus this part of the graph consists of exactly (k + 1) ascending directions or ridge lines S = {S_{1}, S_{2}, …, S_{k+1}}, and (k + 1) descending directions or ravine lines V = {V_{1}, V_{2}, …, V_{k+1}}. We order ascending and descending directions in the abstract graph such as (S_{1}, V_{1}, S_{2}, V_{2}, …, S_{k+1}, V_{k+1}) is the ordered set (9).

Definition 3.4 Let V_{i} be a set of i descending directions and S_{j} be a set of j ascending directions. V_{i} and S_{j} are said to be interlaced, see Fig. 3, if we can alternate the elements of V_{i} with those of S_{j} such that the obtained sequence is a subsequence of (9) consisting of i + j consecutive elements, where S_{1} is considered as consecutive to V_{k+1}. Note that, necessarily, |i − j| ≤ 1.

We are now ready to present the procedure for the decomposition of a k–fold saddle p, see Fig. 3, into k simple saddles.

Algorithm 3.5 (Decomposition Procedure) Let p be a k–fold saddle and N an isolating neighborhood of p.

(a) Choose arbitrarily a set S_{i+1} of i + 1 ascending directions and a set V_{i} of i descending directions originating at p such that V_{i} and S_{i+1} are interlaced. At this end of this step, we have the critical point p, S_{i+1} and V_{i}, See Fig. 4(Left).

(b) As there are i + 1 ridge lines and i ravine lines originating at p, there exists two ridge lines bounding the same wedge. Modify the flow in Int N by creating a ravine line inside this wedge, merging from p and ending at a new critical point p_{j} ∈ Int N. This new ravine line for p is a ridge line for p_{j}, see Fig. 4(Middle).

(c) Attach at p_{j} the remaining k − i = j ascending directions and the k − i + 1 = j + 1 descending directions with the same ordering, see Fig. 4(Right). At the end of this step, p is a i–fold saddle and p_{j} a j–fold saddle.

(d) Repeat the step (a) for p_{i} and p_{j}, re-initializing k to, respectively, i and j.

At the end of this process, a k–fold saddle p is decomposed to k simple saddles.

Figure 4: Left: isolating i + 1 = 2 ascending directions and i descending directions originated at p; Middle: Creating a ridge line from p to p_{j}; Right: Completing the graph: p is a 1–fold saddle (a simple saddle) and p_{j} is a 3–fold saddle.

The choices of edges to decompose in Algorithm 3.5 are not unique but they all lead to the same result on the sum of the local degrees:

Theorem 3.6 Let p_{1}, p_{2}, …, p_{k} be k simple saddles in N produced from a k–fold saddle p by Algorithm 3.5. Let N_{i} ⊂ N, i = 1, …, k, be isolating neighborhoods for p_{1}, p_{2}, …, p_{k} respectively, for the modified flow G. Then

deg(F′, N) = ∑_{i=1}^{k} deg(F′, N_{i}).

Proof: By standard analytical arguments on smooth extensions of functions, it is possible to modify the surface u = f(x, y) inside N, so that the flow lines are modified as described in the algorithm, without modifying it on ∂N. By the axiom A1,

deg(F, N) = deg(G, N)

There are no new critical points created in N other than p_{1}, p_{2}, …, p_{k}. Thus the conclusion follows from the axiom A2.

We would like to use Proposition 2.2 and Theorem 3.6 to conclude that

deg(F, N) = ∑_{i=1}^{k} deg(G, N_{i}) = (−1) + (−1) + ⋯ + (−1) = −k. (10)

Unfortunately, a simple saddle may possibly have null Hessian, so we are not ready yet to make use of Proposition 2.2. The conclusion on (10) could only be derived after the classification of degenerate critical points which is the main goal of the next section.

Remark 3.7 The decomposition produced by Algorithm 3.5 creates an edge in the Morse connections graph corresponding to a connection between two new saddles. Those connections are not desirable in the construction of Morse-Smale complexes [5]. The two phase portraits in the bottom of Figure 2 show a possibility of modifying the algorithm so to split that connection.

4 Classification of isolated degenerate critical points

4.1 Isolating blocks

We recall here a definition of an isolating block from [17] adapted to the context of our paper. The general Wilson and Yorke definition is given for an isolated invariant set of a flow in ℝ^{n} but we restrict it to an isolated critical point p of a C^{2} function f in ℝ^{2}. The hypothesis that f is C^{2} could be relaxed by assuming that it is C^{1} and its gradient is locally Lipschitz, so the associated flow φ is well defined.

A manifold with corners in ℝ^{2} is a closed bounded region N whose boundary is either smooth (i.e. of class C^{2}) or it consists of a finite number of smooth arcs connected at endpoints, called corners, where the smoothness fail.

If A is an open smooth arc on the boundary of N, then n : A → ℝ^{2} denotes the normal vector field on A pointing outward of N. We say that a C^{1} vector field F is strongly inward, respectively strongly outward on A, if F ≠ 0 on A and there is a constant δ > 0 such that F/||F || · n < δ < 0, respectively, F/||F || · n > δ > 0.

Definition 4.1 Let p be an isolated zero of a vector field F. An isolating neighborhood N of p is called an isolating block, if it is a manifold with corners homeomorphic to a closed unit disc in ℝ^{2}, satisfying the following conditions.

(a) If A is a smooth arc of ∂N, then F is either strongly inward or strongly outward on A.

(b) If x ∈ ∂N is a corner point, the orbit of the flow φ of F bounces off at x in the following sense:

φ(ℝ, x) ∩ N = {x}.

The closed union of the arcs at which F is outward, is called the exit set of N and denoted by N^{−}

The purpose of using manifolds with corners rather than smooth manifolds for isolating blocks, is that they are stable, in the sense that their inward and outward arcs are stable under small perturbations of the vector field F. Here is a standard example from the Conley index theory:

Example 4.2 Consider the function given in Lemma 2.1(3). Its gradient field is given by F (x, y) = ∇f(x, y) = 2(x, −y) and the flow trajectories are branches of hyperbolas xy = c. The square N = [−1, 1]^{2} is an isolating block of F. The vector field is inward on the upper and lower open edge and outward on the closed left and right edge. The absolute value of the angle between F and each edge is greatest at each vertex where it is equal to π/4. Since ||F || ≥ 2 on ∂N, for a sufficiently small perturbation G of F and any q ∈ ∂N, the angle between G(x, y) and F (x, y) is less than π/4 for all (x, y) ∈ ∂N. Hence the conditions (a) and (b) in Definition 4.1 remain valid for G.

Example 4.3 Consider the function given by (8) providing the model for a k–fold saddle. Let P be a closed convex equilateral polygone with 2(k + 1) sides centered at the origin, whose vertices are on the rays θ = \frac{π}{2(k+1)} + \frac{πj}{k+1}, j = 0, …, 2k + 1. Then P is an isolating block of the origin.

As the above examples suggest, it is useful to state the following polyhedral version of Lemma 2.4. Its proof is analogous.

Lemma 4.4 Let N be a manifold with corners in ℝ^{2} and let f : N → ℝ be a C^{1} function. Suppose that there exists a C^{2} diffeomorphism Φ : P → N, where P is a convex polyhedron and put g = f ∘ Φ. Then

(a) F := ∇f is admissible in Int N if and only if G := ∇g is admissible in Int P;

(b) If F is admissible, then deg(F, Int N) = deg(G, Int P);

(c) Moreover, F is strongly inward (respectively strongly outward) at on smooth arcs of ∂D if and only if G is strongly inward (respectively strongly outward) on the corresponding edges of P.

Lemma 4.5 Suppose that two C^{1} fields F and G share an isolating block N and the same inward and outward arcs of ∂N. Then deg(F, Int N) = deg(G, Int N).

Proof: One instantly verifies that the homotopy

H(x, t) = (1 − t) F (x) + t G(x)

satisfies the same strong inward and outward conditions as F and G. This implies that H(x, t) ≠ 0 for all t ∈ [0, 1] and all x ∈ ∂N.

Lemma 4.6 Let N ⊂ ℝ^{2} be an isolating block for p and F = ∇f. If its exit set N^{−} is empty or is the whole ∂N, deg(F, Int N) = 1. Otherwise, N^{−} is disconnected. Let k + 1 be the number of its connected components. Then deg(F, Int N) = −k.

Proof: Since an isolating block of a critical point is homeomorphic to the disc \overline{B}, then it must be either diffeomorphic to \overline{B} or to a closed convex polyhedron P. When either N^{−} = ∅ or N^{−} = ∂N, we get N which is diffeomorphic to \overline{B}.

In the first case, F inward on ∂N. By Lemma 2.4, Lemma 4.5, and Proposition 2.2,

deg(F, Int N) = deg(−id, B) = 1.

By the same arguments, if N^{−} = ∂N, F outward on ∂N and we get

deg(F, Int N) = deg(id, B) = 1.

If N^{−} is disconnected, the condition (b) in Definition 4.1 and the continuity of the flow imply that if two smooth arcs of ∂N meet at a corner point, then F is strongly inward on one of them and strongly outward on the other. Therefore the inward arcs are interlaced with outward arcs as the ridge lines and ravine lines in Definition 3.3. Since the arcs complete a circle, the number of inward arcs is the same as the number of outward arcs, equal to (k + 1). In particular, the convex polyhedron P to which N is homeomorphic has 2(k + 1) edges. By Lemma 4.4, Lemma 4.5, Theorem 3.1 and Example 4.3,

deg(F, Int N) = deg(\overline{z}^{k}, P) = −k.

We note that Lemma 4.5 provides a link between the local degree at p and the Conley index [4] of the singleton {p}, which is the pointed homotopy type of the pair (N, N^{−}). In the case when N^{−} is disconnected with (k + 1) connected components, (N, N^{−}) has the homotopy type of the wedge of k circles.

4.2 Extension of the Euler–Maxwell formula

We are now ready to prove the main results of this section.

Theorem 4.7 (Classification of isolated critical points) Let p be an isolated critical point of a C^{2} function f : \overline{D} → ℝ. Then (i) Any isolating neighborhood of p contains an isolating block N of p;

(ii) p is either a maximum point, a minimum point or a k–fold saddle;

(iii) deg(∇f, Int N) is 1 in the first two cases and −k in the last one.

Proof: Since a gradient field has no periodic orbits, the singleton {p} is an isolated invariant set in the sense of [17, Definition 1.1]. By [17, Theorem 2.5], any isolating neighborhood of p contains an isolating block in the sense of [17, Definition 1.2]. It follows from the proof of [17, Theorem 2.5], and from [16, Corollary 3.5] that one can construct a Wilson and Yorke isolating block N which is deformable to {p}. It is known that a manifold homotopic to a disc is also homeomorphic to \overline{B}, hence it is an isolating block in the sense of Definition 4.1. One can also derive this conclusion from [7, Remark 3.1]. This proves (i). Then (iii) follows from Lemma 4.6.

We now prove (ii). If N^{−} is empty, ∇f is inward on ∂N, so f must assume a maximum in N. Since there are no other critical points, that maximum is assumed at p. If N^{−} = ∂N, ∇f is outward on ∂N so, by the same argument, f has minimum on N at p.

Consider the remaining case when N^{−} is disconnected with (k + 1) connected components. We already showed in the proof of Lemma 4.6, that the inward arcs are interlaced with outward arcs and their numbers are both equal to (k + 1). Moreover, it follows again from [17, Theorem 2.5], and from [16, Corollary 3.5] that any outward arc deforms to its intersection with W^{u}(p) and any inward arc deforms to its intersection with W^{s}(p). In particular, those intersections are non-empty. This means that each outward arc contains at least one ridge line and each outward arcs contains at least one ravine line. This conclusion can also be derived from cohomological description of isolating blocks in [7]. Thus we proved that p is exactly the k–fold saddle accordingly to the Definition 3.3.

Remark 4.8 In spaces of higher dimensions, namely in ℝ^{4} and ℝ^{5}, the proof of the fact that a Wilson and Yorke isolating block of an isolated critical point is homeomorphic to the unit ball, relies on the famous Poincaré conjecture, proved just several years ago.

Theorem 4.9 (Maxwell formula for degenerate critical points) Let \overline{D} be a region in ℝ^{2}, C^{2}–diffeomorphic to the closed unit ball or to a closed convex polyhedron, and f : \overline{D} → ℝ a C^{2} function whose gradient ∇f is inward on ∂D. Suppose that all critical points of f are isolated. Then there are finitely many of them, they are local minima, maxima or extended k–fold saddles. Moreover we have the formula

♯ min − ∑_{k} k · ♯ k-saddles +♯ max = 1.

Proof: By the same arguments as those in the proof of Theorem 2.3 and Corollary 2.5,

deg(∇f, D) = deg(−id , B^{2}) = (−1)^{2} = 1.

Since \overline{D} is compact and the critical points of f are isolated, there are finitely many of them. Let {p_{i}}_{i=1,2,...n} be their set. By Theorem 4.7(i), each point p_{i} admits an isolating block N_{i}. By the axiom A2,

1 = deg(F, D) = ∑_{i=1}^{n} deg(F, Int N_{i}).

The conclusion follows from Theorem 4.7(ii,iii).

By the same arguments as in the proof of Corollary 2.6, we get the following

Corollary 4.10 Let f : S^{d} → ℝ be a C^{2} function. Suppose that all critical points are isolated. Then there are finitely many of them, they are local minima, maxima or extended k–fold saddles. Moreover we have the formula

♯ min − ∑_{k} k · ♯ k-saddles +♯ max = 2.

5 Conclusion

As we mentioned in the introduction, the main motivation for this paper is improving existing models for analysis of digital images, where functions are not defined on points in ℝ^{2} but pixels in a finite lattice. Our first numerical experiments showed that we need to relax the hypothesis that critical points are isolated. Note that a typical example from mathematical analysis is a critical point p which is a limit of a sequence of other critical points p_{i}. Such cases are not really of concern in the digital image analysis, because the sets of pixels are finite. However, flat critical regions are common in digital images. In analysis of a height function in topography, for example, one cares about flat regions such as bottoms of lakes, flat mountain tops, or volcano craters, which are extremum regions; and about long sand bars at a sea shore, which are saddle regions. An algorithm detecting and classifying critical regions is produced in [1] but it requires improvements, especially with regard to the concept of topological boundary in the digital setting, and of identification of k-saddle regions. Understanding saddle regions is crucial for construction of isolines, because these are places where smooth continuation techniques fail. Also the model of discrete multivalued dynamical system used of the Morse Connections Graph Algorithm needs to be rethought in terms of the degree theory for multivalued maps.

Another obvious direction of the future study is to provide an analogous analysis of critical points and regions for dimensions 3 and higher. An initial work on this topic is [2]. The analysis of saddle pixels and saddle regions is more difficult in high dimensions because the numbers of connected components of inward and outward portions of an isolating block is not sufficient to distinguish between a saddle and an extremum or between two different types of saddles. Thus one has to search for more advanced topological tools.

We finish this paper with a little disclaimer. The study of dynamical systems in arbitrary dimensions is very extensive, and many statements presented in this paper can be derived from more general and abstract theorems formulated often in the language of algebraic topology. In particular:

1. The most general and concise formulations of the local degree of a map are in terms of the homomorphism induced in homology or cohomology groups of spheres.

2. The differential equation ż = (k + 1)\overline{z}^{k} related to the model (8) of k–fold saddle is well known, and it is a special case of DE’s studied in [15].

3. As we previously mentioned, some conclusions in the proof of Theorem 4.7, can be derived from cohomological statements in [7].

However the generality of a theory is often an obstruction to geometric visualization and accessibility to the applied mathematics, computer science, and engineering communities. We wish to emphasize that our goal is not to achieve the greatest possible generality but to give a presentation of the issue as elementary, self confined, and as visual as possible within the framework of a mathematical paper. We hope that the understanding of geometric aspects of both analytical and homological tools will be helpful in designing adequate models for digital imaging.

References

[1] M. Allili, D. Corriveau, S. Derivière, T. Kaczynski, A. Trahan: Discrete dynamical system framework for construction of connections between critical regions in lattice height data. Journal of Math. Imaging and Vision 28 2 (2007) 99–111.

[2] M. Allili, D. Corriveau, S. Derivière, T. Kaczynski: Detecting Critical Regions in Multidimensional Data Sets via the Conley Index Approach. Rapport de Rech. Univ. Sherbrooke No. 52, Sept. 2007.

[3] L.E.J. Brouwer: Über Abbildungen von Manningfaltigkeiten. Math. Ann. 71 (1912) 97–115.

[4] C.C. Conley: Isolated invariant sets and the Morse index. CBMS Vol. 38, Amer. Math. Soc. Providence, RI 1978.

[5] H. Edelsbrunner, J. Harer, A. Zomorodian: Hierarchical Morse-Smale complexes for Piecewise Linear 2-Manifolds. 17th ACM Symposium on Computational Geometry, Medford, MA, 2001

[6] R. Forman: Morse theory for cell complexes. Advances in Math. 134 (1998), 90-145.

[7] A. Gierzkiewicz and K. Wójcik: On periodic solutions of planar polynomial differential equations with periodic coefficients. Top. Meth. in Nonlin. Anal. to appear.

[8] F.P. Greenleaf: Complex Variables. Saunders Company, 1972.

[9] J. Leray and J. Schauder: Topologie et équations fonctionnelles. Ann. Sci. Ecole Norm. Sup. (3) 51, 45-78, 1934.

[10] N. G. Lloyd: Degree theory. Cambridge Tracts in Math., vol. 73, Cambridge Univ. Press, Cambridge, Great Britain, 1978.

[11] W.S. Massey: A basic course un algebraic topology. GTM 127, Springer-Verlag, 1991.

[12] Y. Matsumoto: An Introduction to Morse Theory. Mathematical Monographs 208, Amer. Math. Soc. (2002).

[13] J. C. Maxwell: On hills and dales. The London, Edinburg and Dublin Philosophical Magazine and Journal of Science, (1870) 40:421-425.

[14] M. Nagumo: A theory of degree of mappings based on infinitesimal analysis. Amer. J. Math. 73 (1951) 485–496.

[15] R. Srzednicki: On periodic solutions of planar polynomial differential equations with periodic coefficients. J. Diff. Equ. 114 (1994) 77–100.

[16] F.W. Wilson: The structure of the level surfaces of a Lyapunov function. J. Diff. Eq. 3 (1967) 323–329.

[17] F.W. Wilson and J.A. Yorke: On the cohomology of an isolating block and its invariant part. J. Diff. Eq. 13 (1973) 106–123.

Département de mathématiques Université de Sherbrooke, Sherbrooke (Québec), Canada J1K 2R1 {sara.deriviere, tomasz.kaczynski, pierre-olivier.vallerand.beaudry}@usherbrooke.ca