Interpreting Feature Tracking Through the Lens of Robustness

Abstract

A key challenge in the study of a time-varying vector fields is to resolve the correspondences between features in successive time steps and to analyze the dynamic behaviors of such features, so-called feature tracking. Commonly tracked features, such as volumes, areas, contours, boundaries, vortices, shock waves and critical points, represent interesting properties or structures of the data. Recently, the topological notion of robustness, a relative of persistent homology, has been introduced to quantify the stability of critical points. Intuitively, the robustness of a critical point is the minimum amount of perturbation necessary to cancel it. In this chapter, we offer a fresh interpretation of the notion of feature tracking, in particular, critical point tracking, through the lens of robustness. We infer correspondences between critical points based on their closeness in stability, measured by robustness, instead of just distance proximities within the domain. We prove formally that robustness helps us understand the sampling conditions under which we can resolve the correspondence problem based on region overlap techniques, and the uniqueness and uncertainty associated with such techniques. These conditions also give a theoretical basis for visualizing the piecewise linear realizations of critical point trajectories over time.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Introduction

A number of techniques have been proposed to define, extract and track features from vector field data [22, 26]. There are many different types of tracked features including volumes, contours, and vortices, which represent interesting properties or structures of the vector fields. In this chapter, we restrict ourselves to critical points [12, 13, 19, 26, 35–37] and sublevel sets. Feature tracking, which is initially inspired by object tracking in computer vision [42], has been intensively researched where most techniques could be classified into three categories [26]. The first approach does not rely on temporal interpolation but focuses on feature extractions at individual time slices and subsequently feature matching via region correspondences or attribute correspondences [22]. Correspondences could be found based on distance proximity [16, 28], attribute similarity [28], or spatial overlap of features [30–32], or alternatively, using prediction and verification [23–25, 29]. Level sets components volume overlap has been proposed in tracking contour tree evolution [34] and contour tree matching [20]. The second approach is based on temporal interpolation and considers time as an additional dimension of the space-time domain. Iso-surfaces are extracted and tracked in 4D space-time in scalar field [17, 40], and for vortex tracking in scale space [1]. Topological structures, such as Reeb graphs [8, 39], and Jacobi sets [7], could be employed in feature tracking (and specifically critical point tracking [8]). Temporal linear interpolation in combination with critical points tracking in 2D and 3D flow fields have been developed in [12, 37]. The third approach represents the dynamic behavior of features as streamlines of a higher-dimensional vector field, called feature flow fields [35, 41], with combinatorial extensions developed in [18, 26]. Critical points are tracked by computing streamlines using combinatorial feature flow fields [26], whose importance measure, referred to as integrated persistence, combines spatial persistence of a critical point along its temporal dimension.

Among these various feature tracking approaches, tracking the temporal evolution of critical points (and their corresponding sublevel sets) plays an important role in understanding the behavior of time-varying vector fields. Recently, the topological notion of robustness [5, 6, 11], a relative of persistent homology, has been introduced to quantify the stability of critical points [5, 38]. Intuitively, the robustness of a critical point is the minimum amount of perturbation necessary to cancel it. It has been shown to be useful for vector field analysis, visualization [38] and simplification [33]. The work in [27] also strongly advocated the need for importance measures for critical points and proposed such a measure closely related to persistence. Although robustness is also closely related to persistence, in the sense that the robustness of features in level and interlevel sets, quantified through well groups, can be read off the persistence diagram of the function [2]; however in more general settings the reduction from robustness to persistence is not known and the authors in [11] have conjectured that robustness may sit somewhere between the 1-parameter notion of persistence and its multi-parameter generalization [3].

In this chapter, we offer a fresh interpretation of the notion of feature tracking, in particular, critical point tracking, through the lens of robustness. We obtain our theoretical results by relating critical points tracking with their stability. That is, in a nutshell, stable critical points could be tracked more easily and more accurately. We prove formally that robustness can help us understand the sampling conditions under which we can resolve the correspondence problem based on commonly used region correspondence techniques. (e.g. [20, 30–32, 34]). It also gives a theoretical basis for visualizing the piecewise-linear (PL) realizations of critical point trajectories.

Background

We provide the relevant background for well groups [5, 6] and degree theory. In particular, we review the notion of static robustness and its properties explicitly stated in [38]. The main components for proving our results rely on these properties, as well as the Stability Theorem of Well Diagrams.

Degrees. In a 2D vector field, the degree of a critical point x, denoted as deg(x), equals its Poincaré index. Sources and sinks have a degree of +1 while saddles have a degree of −1. A path-connected component C in the domain that encloses a set of critical points {x _i } has a degree that sums the degrees of the individual critical points: $\mathrm{deg}(C) =\sum \nolimits_{i}\mathrm{deg}(x_{i})$. For the formal definition of the degree of a continuous mapping see [14] (page 134) and [6].

Merge tree. Given a continuous 2D vector field $f$, we define a scalar function $f_{0}: {\mathbb{R}}^{2} \rightarrow \mathbb{R}$ such that the value at each point $x \in {\mathbb{R}}^{2}$ is the Euclidean norm of the vector field at x, f ₀(x) =  | | f(x) | | ₂. Let $\mathbb{F}_{r} = f_{0}^{-1}(-\infty,r]$ be the sublevel set of f ₀ for some r ≥ 0. A value r > 0 is a regular value of f ₀ if $\mathbb{F}_{r}$ is a 2-manifold, and for all sufficiently small ε > 0, $f_{0}^{-1}[r-\epsilon,r+\epsilon ]$ deformation retracts to f ₀ ⁻¹(r); otherwise it is a critical value. We further assume f ₀ has a finite number of critical values and f has finite number of critical points (that is, the number of components in $\mathbb{F}_{0}$ is finite).

We construct a merge tree (or a join tree [4]), which tracks the (connected) components of $\mathbb{F}_{r}$ as they appear and merge, as we increase r from 0 (or −∞). This corresponds to the 0-dimensional persistent homology [9] of the sublevel set filtration of f ₀. The leaves of the tree represent the creation of a component while the root represents the entire domain of f ₀. An internal node represents the merging of two or more components. We then assign an integer to each node in the tree that record the degree of the corresponding component in the sublevel set. The degree of any such component is determined by the sum of degrees of the critical points lying in it [5].

Well groups and well diagrams. To understand the concepts of well groups and well diagrams first introduced in [10], we need to introduce our particular notion of vector field perturbation. Let $f,h: {\mathbb{R}}^{2} \rightarrow {\mathbb{R}}^{2}$ be two continuous 2D vector fields. A continuous mapping h is an r-perturbation of f, if the distance between the two mappings $\mathrm{d}(f,h):=\sup _{x\in {\mathbb{R}}^{2}}\vert \vert f(x) - h(x)\vert \vert _{2} \leq r$.

As we track the connected components over a filtration (the sublevel set of f ₀) at each value of r, we are computing the 0-dimensional homology groups over a field. These groups are vector spaces whose ranks equal the number of components presented in the associated sublevel sets. Furthermore, if h is an r-perturbation of f, then $\mathbb{H}_{0} = {h}^{-1}(0)$ is a subspace of $\mathbb{F}_{r}$. The 0-dimensional homology groups are denoted as $\mathsf{H}(\mathbb{H}_{0})$ and $\mathsf{H}(\mathbb{F}_{r})$. The subspace relation induces a linear map $j_{h}: \mathsf{H}(\mathbb{H}_{0}) \rightarrow \mathsf{H}(\mathbb{F}_{r})$ between the two vector spaces. The well group, U(r), is the subgroup of $\mathsf{H}(\mathbb{F}_{r})$, whose elements belong to the image of each j _h , for all r-perturbation h of f [5]. That is, $\mathsf{U}(r) =\bigcap _{h}\mathrm{im\,}j_{h}.$ Intuitively, an element in U(r) is considered a stable element in $\mathsf{H}(\mathbb{F}_{r})$ if it does not disappear with respect to any perturbation. The rank of U(0) is the number of critical points of f. A point r ∈ (0, ∞) belongs to the well diagram of f ₀, Dgm(f ₀), with multiplicity k if the rank of the well group drops by k at r [5]. For reasons of stability, the point 0 is counted with infinite multiplicity. The point ∞ is counted with multiplicity k if for all sufficiently large values of r, the rank of U(r) is k. An algorithm to compute the well diagram is suggested by the Equivalence Theorem [5]. It states that, if r is a regular value of f ₀, then the rank of the well group U(r) is the number of components C of $\mathbb{F}_{r}$ such that deg(C) ≠ 0. We demonstrate by an example below that the constructed augmented merge tree is sufficient to derive its corresponding well diagram.

Stability of well diagrams. We now introduce the notion of stability for the well diagrams. Let $f,g: {\mathbb{R}}^{2} \rightarrow {\mathbb{R}}^{2}$ be two vector fields. Construct a bijection μ: Dgm(f ₀) → Dgm(g ₀) that maps the kth highest point in Dgm(f ₀) to the kth highest point in Dgm(g ₀). Since the point 0 in each well diagram has an arbitrary multiplicity, by choosing the appropriate multiplicities for 0, μ becomes a bijection. The bottleneck distance between Dgm(f ₀) and Dgm(g ₀) is $W_{\infty }(\mathrm{Dgm}(f_{0}),\mathrm{Dgm}(g_{0})) =\sup _{a\in \mathrm{Dgm}(f_{0})}\vert a -\mu (a)\vert.$ The Stability Theorem of Well Diagrams [11] states that the bottleneck distance between two well diagrams is bounded by the distance between the mappings, that is, $W_{\infty }(\mathrm{Dgm}(f_{0}),\mathrm{Dgm}(g_{0})) \leq \mathrm{ d}(f,g)$.

Static robustness and its properties. The static robustness of a critical point is the height of its lowest degree zero ancestor in the merge tree [5, 38]. The static robustness quantifies the stability of a critical point with respect to perturbations of the vector fields through the following lemmas first introduced in [38]. Both lemmas are illustrated in Fig. 1.

Fig. 1

Illustrations for (a) Lemma 1 and (b) Lemma 2

Lemma 1 (Critical Point Cancellation [38]).

Suppose a critical point x of f has static robustness r. Let C be the connected component of $\mathbb{F}_{r+\delta }$ containing x, for an arbitrarily small δ > 0. Then, there exists an (r + δ)-perturbation h of f, such that ${h}^{-1}(0) \cap C = \varnothing$ and h = f except possibly within the interior of C.

Lemma 2 (Degree and Critical Point Preservation [38]).

Suppose a critical point x of f has static robustness r. Let C be the connected component of $\mathbb{F}_{r-\delta }$ containing x, for some 0 < δ < r and r −δ being a regular value. Then for any ε-perturbation h of f where ε ≤ r −δ, the sum of the degrees of the critical points in h ⁻¹ (0) ∩ C is deg (C). Furthermore, if C contains only one critical point x, we have $\mathrm{deg}({h}^{-1}(0) \cap C) =\mathrm{ deg}(x)$ . In other words, there is no ε-perturbation (ε ≤ r −δ) that could cancel the critical point in C; that is, x is preserved.

Example.

We illustrate the above concepts through an example shown Fig. 2 adapted from [38]. A 2D vector field f (on the left) contains four critical points, a sink x ₁ (red), a source x ₃ (green), and two saddles x ₂ and x ₄ (blue). Its corresponding mapping f ₀ has three critical values, denoted as r ₁, r ₂ and r ₃, respectively. The merge tree (on the right) tracks the components of the sublevel sets $\mathbb{F}_{r}$ as they appear and merge, as r increases from 0. We use α, β, γ etc. to represent components of certain sublevel sets at the critical values. At r = 0, four components α ₁ to α ₄ appear that correspond to the four critical points. At r = r ₁, components represented by α ₁ and α ₂ merge into a single component represented by β ₁, which has degree zero. The number of components with non-zero degree drops from four to two, this is reflected by two points in the well diagram Dgm(f ₀) with value r ₁. Then at r = r ₃ the number of components with non-zero degree drops from two to zero, this corresponds to two points in Dgm(f ₀) with value r ₃. By definition, the static robustness of the critical points x ₁, x ₂, x ₃, and x ₄ are r ₁, r ₁, r ₃, and r ₃, respectively.

Fig. 2

Top, vector field f (left) and relations among components of $\mathbb{F}_{r}$ (right). Bottom, augmented merge tree (left) and its well diagram (right) (Figure adapted from [38])

Critical Point and Sublevel Set Tracking Through the Lens of Robustness

In practice, we do not have access to a continuous time-varying 2D vector field, but rather a dataset consists of a discrete number of snapshots at different points in time. This means that to track vector fields features (i.e. critical points and sublevel sets) we must first resolve the correspondence problem. That is, determining the correspondences between the critical points and sublevel sets in successive time steps, that actually represent the same object at different times [22]. In this section, we prove formally that robustness helps us understand the sampling conditions under which we can resolve the correspondence problem based on region overlap techniques, and the uniqueness and uncertainty associated with such techniques.

The stability of well diagrams and the properties associated with (static) robustness allow us to give a theoretical underpinning to this approach by requiring that the vector field changes slowly enough and then treating adjacent time steps as small perturbations of each other. We assume that the underlying time-varying vector field is c-Lipschitz and that we have an ε-sampling in space and time. It follows that the vector fields at each time steps are cε-perturbations of each other. Formally, suppose $f: \mathbb{X} \subseteq {\mathbb{R}}^{2} \rightarrow {\mathbb{R}}^{2}$ is a c-Lipschitz function. That is, $\forall x,x^{\prime} \in \mathbb{X}$, $\vert \vert f(x) - f(x^{\prime})\vert \vert _{2} \leq c\vert \vert x - x^{\prime}\vert \vert _{2}$. Given a triangulation K of $\mathbb{X}$ and f valued at its vertices, we could linearly interpolate over its simplexes (that is, edges and triangles) resulting in a continuous function $\hat{f}: \vert K\vert \rightarrow {\mathbb{R}}^{2}$ [5]. If vertices P in K are ε-sampling of $\mathbb{X}$ (namely, $\forall x \in \mathbb{X}$, $d(x,P):=\inf _{y\in P}\vert \vert x - y\vert \vert _{2} \leq \epsilon$), then we have $\forall x \in \mathbb{X}$, $\vert \vert f(x) -\hat{ f}(x)\vert \vert _{2} \leq c\epsilon$. This observation allows us to move from continuous to the piecewise-linear (PL) setting by noting that for a c-Lipschitz function, a linear interpolation between samples results in an error of at most cε from the true underlying function. As a consequence of the Stability Theorem of Well Diagrams, we have,

Lemma 3 (Triangulation Lemma [5]).

The bottleneck distance between the well diagrams of f and the PL interpolation $\hat{f}$ is bounded by $W_{\infty }(\mathrm{Dgm}f,\mathrm{Dgm}\hat{f}) \leq c\epsilon.$

In the time varying setting, to accommodate the additional dimension of time we make a small change of notation by referring to $f: \mathbb{X} \times \mathbb{R} \rightarrow {\mathbb{R}}^{2}$ as a time-varying 2D vector field over domain $\mathbb{X} \subseteq {\mathbb{R}}^{2}$, where $f_{t}(x) = f(x,t): \mathbb{X} \rightarrow {\mathbb{R}}^{2}$ represents a 2D vector field at time $t \in \mathbb{R}$. For notational simplicity we assume we have an ε-sampling and that the Lipschitz constant is c in the time domain as well. That is, $\forall x \in \mathbb{X}$, $\vert \vert f_{t}(x) - f_{t+\epsilon }(x)\vert \vert _{2} \leq c\epsilon$.

We now give guarantees on the correspondence of critical points across time slices with respect to robustness. We assume that we have a PL-interpolation of the c-Lipschitz time-varying vector field built on certain ε-sample. The proofs do not depend on this interpolation but rather require a bound on the error from approximating the underlying function. Better interpolation methods will lead to better approximations and therefore better constants in the theoretical guarantees.

We introduce some additional notation. Recall $f: X \times \mathbb{R} \rightarrow {\mathbb{R}}^{2}$ is a time-varying 2D vector field over domain $\mathbb{X}$, and $f_{t}(x) = f(x,t): \mathbb{X} \rightarrow {\mathbb{R}}^{2}$ represents a 2D vector field at time t. A crucial concept is the sublevel set of the Euclidean norm of f _t , | | f _t (x) | | ₂. Let $C_{t}(\delta ) =\{ x \in \mathbb{X}\mid \vert \vert f_{t}(x)\vert \vert _{2} \leq \delta \}$ denote its sublevel set for any δ > 0 whose degree is non-zero, see Fig. 3a. If we consider a specific connected component of C _t (δ), we denoted it by C _t ⁱ(δ). Furthermore, let $z_{t} = C_{t}(0) =\{ x \in \mathbb{X}\mid \vert \vert f_{t}(x)\vert \vert _{2} = 0\}$ represent the set of critical points. When considering a single critical point in the set we will add an index to the notation (e.g. z _t ⁱ). We begin our discussion of correspondence by making the following observation: the critical points with high robustness in two adjacent time steps must be contained in the interior of the intersection of the corresponding sublevel sets. Formally,

Fig. 3

(a) Definition of C _t (δ): sublevel set with non-zero degree. (b) Illustration for Lemma 4

Lemma 4 (Critical Points Containment).

For two adjacent time steps of the vector field $f_{t},f_{t+\epsilon }: \mathbb{X} \rightarrow {\mathbb{R}}^{2}$ , the critical points in both time steps belong to $\mathrm{int\,}(C_{t}(\delta ) \cap C_{t+\epsilon }(\delta ))$ for all δ > cε.

Proof.

The lemma is illustrated in Fig. 3b. Consider C _t (δ), the sublevel set of f _t , where δ > 0. By the Lipschitz assumption, $\forall x \in \mathbb{X}$, $\vert \vert f_{t}(x) - f_{t+\epsilon }(x)\vert \vert _{2} \leq c\epsilon$. It follows that ∀δ > cε, the critical points in f _t , $z_{t} = C_{t}(0) \subseteq C_{t+\epsilon }(c\epsilon ) \subset C_{t+\epsilon }(\delta )$, and the critical point in f _t+ε , $z_{t+\epsilon } = C_{t+\epsilon }(0) \subseteq C_{t}(c\epsilon ) \subset C_{t}(\delta )$. On the other hand, $z_{t} = C_{t}(0) \subset C_{t}(\delta )$ and $z_{t+\epsilon } = C_{t+\epsilon }(0) \subset C_{t+\epsilon }(\delta )$. Hence, $z_{t},z_{t+\epsilon } \subseteq \mathrm{ int\,}(C_{t}(\delta ) \cap C_{t+\epsilon }(\delta ))$. □ 

Lemma 4 states that critical points are contained in intersections across time steps. While this is an important observation, it does not imply correspondence. The argument we would ultimately like to make is that we can find correspondences between two adjacent time slices represented by a (bounded)-homotopy. Recall a homotopy between two continuous functions that map between topological spaces, $f_{t},f_{t+\epsilon }: \mathbb{X} \rightarrow {\mathbb{R}}^{2}$, is defined to be a continuous function $H: \mathbb{X} \times [0,1] \rightarrow {\mathbb{R}}^{2}$, such that $\forall x \in \mathbb{X}$, H(x, 0) = f _t (x) and $H(x,1) = f_{t+\epsilon }(x)$. We then use $h_{s}(x) = H(x,s): \mathbb{X} \rightarrow {\mathbb{R}}^{2}$ (s ∈ [0, 1]) to represent intermediate time slices. Such a homotopy is δ-bounded (or has a maximum deformation of at most δ), if $\forall x \in \mathbb{X}$ and ∀s, s′ ∈ [0, 1], $\vert \vert h_{s}(x) - h_{s^{\prime}}(x)\vert \vert _{2} \leq \delta$. Figure 4a gives an illustration.

Fig. 4

Illustrations of (a) bounded-homotopy and (b) δ-tube

In order to obtain a correspondence, we will need to impose some further conditions. First we formally define a correspondence. A δ-correspondence between a pair of critical points is defined such that there exists a δ-bounded homotopy which maps the points to each other. Formally, there is a δ-correspondence between critical points p ∈ z _t and q ∈ z _t+ε if there exists a δ-bounded homotopy H between f _t and f _t+ε , such that H ⁻¹(0) contains a continuous path embedded in $\mathbb{X} \times [0,1] \subset {\mathbb{R}}^{3}$ that connects p with q. We refer to such a path as the critical path. A construction we will make use of is the straight-line homotopy. For two functions, $f_{t},f_{t+\epsilon }: \mathbb{X} \rightarrow {\mathbb{R}}^{2}$, we define their straight-line homotopy as

$$\displaystyle{ f_{t+s\epsilon }(x) = h_{s}(x) = (1 - s)f_{t}(x) + sf_{t+\epsilon }(x)\qquad 0 \leq s \leq 1,\quad \forall x \in \mathbb{X} }$$

(1)

First, we examine a simple situation, which we refer to as the unique intersection. We assume a component at time t intersects with only one component at time t +ε and vice versa. Formally we say that, for a single component C _t ⁱ(δ) in C _t (δ), there exists only a single component C _t+ε ^j(δ) in C _t+ε (δ) such that they intersect; and for C _t+ε ^j(δ), the only component it intersects in C _t (δ) is C _t ⁱ(δ).

Lemma 5 (Critical Points Correspondence Under Unique Intersection).

For δ > cε, let C _t ⁱ (δ) and C _t+ε ^j (δ) be components of the δ-sublevel sets with a unique intersection. If there exists a unique δ-robust critical point in each component, denoted as x and y respectively, then they are in correspondence.

The lemma is illustrated in Fig. 5a. The main idea behind its proof is to construct a (δ + cε)-bounded homotopy that maps x to y by considering tubular neighborhood surrounding the parametrized curve connecting x and y as shown in Fig. 5b.

Fig. 5

(a) Illustration of Lemma 5 and (b) the main idea behind its proof

Proof.

Let $\mathcal{I} = C_{t}^{i}(\delta ) \cap C_{t+\epsilon }^{j}(\delta )$ and $\mathcal{U} = C_{t}^{i}(\delta ) \cup C_{t+\epsilon }^{j}(\delta )$. Suppose $\mathcal{I}\neq \varnothing$. Suppose both points x and y are δ-robust, that is, they have static robustness greater or equal to δ. First, based on the unique intersection condition, by Lemma 4, both x and $y$ are contained in $\mathcal{I}$. Second, we claim that $\mathcal{U}\setminus C_{t}^{i}(\delta )$ (and $\mathcal{U}\setminus C_{t+\epsilon }^{j}(\delta )$ symmetrically) contains no critical points. Suppose there is a critical point $x^{\prime} \in \mathcal{U}\setminus C_{t}^{i}(\delta )$, since x′∉C _t ⁱ(δ), then either (a) x′ ∈ C _t ^i′(δ) for some i′ ≠ i, or (b) | | f _t (x′) | | ₂ > δ. (a) is impossible as it violates the unique intersection condition. For (b), based on Lipschitz condition and the reverse triangle inequality, we have $\vert \vert f_{t+\epsilon }(x^{\prime})\vert \vert _{2} \geq \vert \vert f_{t}(x^{\prime})\vert \vert _{2} -\vert \vert f_{t}(x^{\prime}) - f_{t+\epsilon }(x^{\prime})\vert \vert _{2} >\delta -c\epsilon > 0$. Hence x′ cannot be a critical point.

For the rest of the proof, we need to show that x and y are in correspondence, by constructing the desired homotopy. We also claim that such a homotopy is (δ + cε)-bounded. First, we construct a critical path. Since both $x,y \in \mathcal{U}$, there exists a parametrized continuous curve γ in $\mathcal{U}$ that connects these two points. That is, $\gamma: [0,1] \rightarrow \mathbb{X}$ where γ(0) = x and γ(1) = y. Such a curve could be “lifted” to $\mathbb{X} \times [0,1]$ by defining a parametrized curve ${\gamma }^{{\ast}}: [0,1] \rightarrow \mathbb{X} \times [0,1]$ where γ ^∗(t) = γ(t) × t, for 0 ≤ t ≤ 1. This constitutes the desired critical path between x and y in ${H}^{-1}(0) \subset {\mathbb{R}}^{3}$. Our goal now is to define a continuous homotopy based on such a critical path. Such a process is shown in Fig. 6a.

Fig. 6

(a) Constructing the homotopy for correspondence $H: \mathbb{X} \times [0,1] \rightarrow {\mathbb{R}}^{2}$. Here we show two time slices at t and t +ε. $\mathcal{U}\subset \mathbb{X}$ is represented as a rectangle. The path between critical points x and y is $\gamma \subset \mathcal{U}$. It is “lifted” to a parametrized curve ${\gamma }^{{\ast}}\subset \mathbb{X} \times [0,1] \subset {\mathbb{R}}^{3}$, with N as its tubular neighborhood. (b) Spatial interpolation within N _s that linearly interpolate between its boundary and its center. λ is the scaling parameter used in the interpolation, where 0 ≤ λ ≤ 1

Second, we consider a tubular neighborhood $N \subset {\mathbb{R}}^{3}$ of γ ^∗. Such a neighborhood intersects each time slice $\mathbb{X} \times s$ at N _s , ∀s ∈ [0, 1], where $N_{s} \subset \mathbb{X}$ contains a zero center that is the intersection between γ ^∗ and the time slice. We introduce a spatial interpolation within each N _s that linearly interpolate between its boundary and the center. This is shown in Fig. 6b. Third, we are ready to construct the desired homotopy with guaranteed continuity. To do so, we rewrite the straight-line homotopy for a fixed $z \in \mathbb{X}$ as $\alpha _{z}(s): [0,1] \rightarrow {\mathbb{R}}^{2}$, where $\alpha _{z}(s) = (1 - s)f_{t}(z) + sf_{t+\epsilon }(z)$. We further define a curve β _z for a fixed $z \in \mathbb{X}$, such that, β _z : [0, 1] → z × [0, 1]. We define our homotopy $H: \mathbb{X} \times [0,1] \rightarrow {\mathbb{R}}^{2}$ as follows. $\forall z \in \mathbb{X}$: (a) If β _z does not intersect N or it only intersects N on its boundary point (non-transversal intersection), we use the straight-line homotopy, that is, H(z, s) = α _z (s) for 0 ≤ s ≤ 1; (b) If β _z intersects N transversally (by entering N at time s′ and existing N at time s″), then H(z, s) is defined to be α _z (s) for s ∈ [0, s′] ∪ [s″, 1], otherwise, it respects the spatial interpolation within the interior of N for s ∈ (s′, s″). In case (a) and (b), the maximum deformation at any point $z \in \mathbb{X}$ during the homotopy is at most cε and (δ + cε) respectively. Finally, since x and y are the only δ-robust critical points within their respective components, the uniqueness conditions imply that this is the only possible choice of correspondence. □ 

Remark 1.

Much of the complication in constructing the above homotopy is dealing with the tubular neighborhoods to ensure the mapping is continuous. and therefore a homotopy. It is important to note that although the maximum deformation of such a homotopy is bounded, its Lipschitz constant is not. Controlling the Lipschitz constant of such a homotopy is a far more difficult problem. We merely impose a Lipschitz constant on the time-varying vector field to ensure validity of the approximation, whereas here we demonstrate the existence of a possible correspondence.

Now we extend the above lemma to cases without the uniqueness intersection assumptions. We make the following claim regarding many-to-many correspondences among critical points with large robustness. We consider the following statement a major contribution in rethinking and treating correspondence problem under the robustness framework. The key point is that we relax the uniqueness condition on the intersections. With this we lose the guarantee on uniqueness of the map, but we show that for any choice among possible correspondences, there exists a homotopy.

Lemma 6 (Robust Critical Points Correspondence).

There exists a (δ + cε)-bounded homotopy between δ-robust critical points between time slices, from which a correspondence could be obtained.

The idea is the behind the proof is illustrated in Fig. 7. Here, we consider case (a) where the sublevel sets have unique intersection, however there may be multiple δ-robust critical points in each component; and case (b) where the sublevel sets do not have unique intersection. In case (a), we choose the desired correspondence by constructing the critical paths which are no longer unique. In case (b), we require that a path exists between critical points. There are many choices of correspondences (under the restriction that the corresponding points are distinct), our proposed homotopy construction works for any of them.

Fig. 7

Illustration of the main proof idea behind Lemma 6

Proof.

In case (a), suppose we still have unique intersection condition, however there exist multiple δ-robust critical points in each component. All the arguments from Lemma 5 hold except now we must first choose the desired correspondences by constructing critical paths (which are no longer unique). We also need to add some discussions, since for a fixed choice of correspondences, we have multiple critical paths and their corresponding tubular neighborhoods. In generic situations, we suppose all such critical paths with arbitrarily small tubular neighborhoods do not intersect during the construction of the homotopy. Therefore although the constructed homotopy might be more complicated (where β _z for a fixed z may intersect multiple neighborhoods), it remains continuous and bounded.

In case (b), suppose the unique intersection condition no longer holds. In the construction of the above homotopy, we require only that a path γ exists (in the union of components, i.e. $\mathcal{U}$) between critical points. Without the uniqueness assumption, we have many choices of correspondences, and the homotopy construction works for any of them (under the restriction that the corresponding points are distinct). To complete the proof, we need only to check that a path γ exists, such that, ∀x ∈ γ, | | f _t (x) | | ₂ ≤ (δ + cε) and $\vert \vert f_{t+\epsilon }(x)\vert \vert _{2} \leq (\delta +c\epsilon )$. This follows from the Lipschitz assumptions. □ 

Robustness also provides guarantees on the critical paths, that is, trajectories of critical points trace over time. To make a precise statements, we define the notion of δ-tube and its PL counterpart. A δ-tube is a (connected) component in the collection of δ-sublevel sets between two adjacent discrete time steps based on straight-line homotopy. Let C _s (δ) be connected components of the δ-sublevel set at time s. Suppose f _t and f _t+ε are two adjacent time steps. A δ-tube is defined as a component in $\bigcup _{s\in [t,t+\epsilon ]}C_{s}(\delta )$. This is illustrated in Fig. 4b. Given the i-th δ-tube between times t and t +δ, without loss of generality, we denote each of its time slice as C _s ⁱ(δ). Note that splitting and merging is possible with a given δ-tube.

A PL δ-tube is similarly defined but is based on the straightline homotopy of PL interpolations at each time step. Correspondingly, each of its time slice is denoted as $\hat{C}_{s}^{i}(\delta )$, for t ≤ s ≤ t +ε. The following lemma states conditions under which a δ-tube contains a critical path.

Lemma 7 (Critical Paths Containment).

For a c-Lipschitz time-varying vector field and any δ > cε, if a critical path between two δ-robust critical points exists, it will be completely contained within a δ-tube between the two time slices f _t and f _t+ε .

Proof.

The lemma is illustrated the same way as in Fig. 5b. Suppose a critical path γ leaves the i-th δ-tube at some time s (t ≤ s ≤ t +ε). This implies that there exists a critical point p ∈ z _s that continuously moves outside of the δ-tube at time s. This means p∉C _s ⁱ(δ), therefore f _s (p) ≥δ. There are two cases: (a) the critical point re-enters the i-th δ-tube at time s′ and stays inside the tube until time t +ε; and (b) the critical point enters a different δ-tube (i.e. the j-th δ-tube) at time s′ and never returns back to the i-th δ-tube, where s < s′ < t +ε.

In case (a), we consider the particular scenario where (s′ − s) approaches zero, by the Lipschitz assumption, p ∈ C _t ⁱ(c(s − t)) and $p \in C_{t+\epsilon }^{i}(c(t +\epsilon -s))$. Based on Lemma 4, $p \in C_{t}^{i}(c(s - t)) \cap C_{t+\epsilon }^{i}(c(t +\epsilon -s))$. The Lipschitz condition also implies that the function value at p based on straight-line homotopy at time s is, $f_{s}(p) \leq \min \{ 2c(s - t),2c(t +\epsilon -s)\}$. The above upper bound achieves its maximum when $s = t +\epsilon /2$, where f _s (p) ≤ cε. Since δ > cε, this contradicts the assumption that f _s (p) ≥δ. So case (a) is not possible.

In case (b), suppose the critical point leaves C _s ⁱ(δ) and enters C _s′ ^j(δ), where s < s′. Lemma 4 implies the critical point belongs to $C_{s}^{i}(\delta ) \cap C_{s^{\prime}}^{j}(\delta )$, and in addition, it belongs to any $C_{s}^{i}(\delta ) \cap C_{s^{\prime}}^{j}(\delta )$ as (s′ − s) approaches zero. This contradicts the fact that C _s ⁱ(δ) and C _s′ ^j(δ) originate from non-intersecting δ-tubes. Therefore case (b) does not hold either. □ 

Corollary 1 (PL Critical Paths Containment).

For a c-Lipschitz time-varying vector field and any δ > cε, if a critical path between two δ-robust critical points exists, it will be completely contained within a PL (δ + cε)-tube between the two time slices f _t and f _t+ε .

Proof.

This follows directly from Lemma 7, since $C_{s}^{i}(\delta ) \subseteq \hat{ C}_{s}^{i}(\delta +c\epsilon )$ for all s and i. Therefore since the critical path is included in the δ-tube, it follows that it is included in the PL (δ + cε)-tube.

To prove the above inclusion, this property holds at the end points (s = t and $s = t+\epsilon$) of the straight-line homotopy based on the c-Lipschitz assumption and ε-sampling. Because the straight-line homotopy is a convex combination of the end points, it holds at any point in between as well. □ 

Remark 2.

The above lemmas prove that regardless of the (possibly unknown) underlying changes of the vector field, the critical paths of the vector fields for robust critical points are contained inside some δ-tubes, which implies that the straight-line homotopy roughly captures the behavior of the critical paths.

Now we have addressed critical points correspondences and critical paths containments, we would like to address the problem of sublevel set correspondence, as shown in the following lemma and illustrated in Fig. 8a, b where critical point x in f _t corresponds to y in f _t+ε .

Lemma 8 (Sublevel Set Unique Correspondence).

For δ > cε, suppose C _t ⁱ (δ) and C _t+ε ^j (δ) are two components of C _t (δ) and C _t+ε (δ) respectively such that their intersection contains critical points. If there are no merge events in $[\delta -c\epsilon,\delta +c\epsilon ]$ (within the merge trees) between times t and t + ε, the map induced between these pairs of components is unique. In other words, the correspondences between connected components in C _t (δ) and C _t+ε (δ) whose intersections contain critical points are unique.

Fig. 8

(a) and (b): Illustration of Lemma 8. (c) Diagram in its proof

Proof.

Since there are no merge events in $[\delta -c\epsilon,\delta +c\epsilon ]$ between times t and t +ε, components can neither merge nor split apart. First we show that each connected component C _t ⁱ(δ) has intersection with at least one connected component C _t+ε ^j(δ). For every i, there exists a j such that we can obtain the diagram in Fig. 8c, where all the maps are inclusions. Three of these inclusions are obvious. We prove the inclusion exists for $C_{t}^{i}(\delta -c\epsilon ) \rightarrow C_{t+\epsilon }^{j}(\delta )$. Suppose there exists a point p ∈ C _t ⁱ(δ − cε) but p∉C _t+ε ^j(δ). This implies that f _t+ε (p) > δ and f _t (p) ≤ δ − cε. This violates the Lipschitz assumption at p. The above diagram implies that for every i, there exists a j such that $C_{t}^{i}(\delta ) \cap C_{t+\epsilon }^{j}(\delta )\neq \varnothing$, and their intersection contains critical points (referred to as non-zero intersections). Thus there is a possible correspondence between these two components. To show such a correspondence is unique, we claim that if there were additional intersections, i.e., with a connected component C _t+ε ^k(δ), this would imply a merge/splitting event in the required interval (between C _t+ε ^j(δ) and C _t+ε ^k(δ)). Assume that both C _t+ε ^j(δ) and C _t+ε ^k(δ) have a non-zero intersection with C _t ⁱ(δ), it follows by Lipschitz assumptions that there exists a path γ ⊂ C _t ⁱ(δ) connecting C _t+ε ^j(δ) and C _t+ε ^k(δ), such that ∀x ∈ γ, $\vert \vert f_{t+\epsilon }(x)\vert \vert _{2} \leq \delta +c\epsilon$. However this implies that the two components merge in the interval $[\delta -c\epsilon,\delta +c\epsilon ]$ which contradicts our assumption. Therefore, we conclude there cannot be two components C _t+ε ^j(δ) and C _t+ε ^k(δ) with a non-zero intersection with C _t ⁱ(δ), making the map unique. □ 

Experiments

We demonstrate robustness-based critical point tracking on three real world datasets, which are extracted from consecutive time slices of 2D time-varying vector fields. The first two datasets, OceanA and OceanB, come from top layers of the 3D simulation of global oceanic eddies [21] for 350 days in the year 2002. We extracted tiles from this simulation data, representing the flow in the central Atlantic Ocean for OceanA (resolution 60 × 60), south Atlantic Ocean for OceanB (resolution 100 × 100), and construct standard triangulations on the point samples. We use time slices #21310 and #21311 for OceanA, and #20710 and #20711 for OceanB. Our third dataset CombustionC is taken from the simulation of homogeneous charge compression ignition (HCCI) engine combustion [15]. The domain has periodic boundary and is represented as a 640 × 640 regular grid. The 2D time-varying vector field consists of 299 time-steps with a time interval of 10⁻⁵ s. We selected time slices #173 and #174 from this data.

The critical points correspondences based on robustness are shown in Fig. 9. Suppose we use PL interpolation between time slices. Our theoretical results rely on the quantity cε, which depends on our prior knowledge of the datasets, or some form of estimation.

Fig. 9

Tracking critical points correspondences based on robustness for OceanA (top), OceanB (middle) and CombustionC (bottom). In each pair of pictures between time slices (e.g. (a) vs (b), (c) vs (d), (e) vs (f)), the corresponding points are shown by the same color

First, suppose cε is equal to the magnitude of the maximum observed difference in the vector fields of the two adjacent time slices t ₁ and t ₂, $\delta =\sup _{x}\vert \vert f_{t_{1}}(x) - f_{t_{2}}(x)\vert \vert _{2}$. That is, let cε = δ. For OceanA (a) and (b), we illustrate the components of the sublevel set at cε that contains critical points. Since cε is relatively large, based on Lemma 5, the components (pointed by white solid arrows) in (a) and (b) have unique intersection and each contains a single critical point, therefore these critical points correspond to one another. On the other hand, the blue points in t ₁ and t ₂ could all potentially map to one another, creating a many-to-many correspondence scenario. It appears that the single yellow point in t ₁ could potentially map to any of the three points in t ₂ based on region overlap (or distance proximity, if all three yellow points are moved even closer in distance). However, this is not true as we investigate further in OceanA(c) and (d) by showing the components of the sublevel set at the robustness values of each critical point. It is interesting to point out that the points (pointed by white arrows) end up matching to each other uniquely based on Lemma 5 since their robustness values are higher than cε, while the two unmatched points (in the black components) are considered newly appeared. A similar situation occurs in OceanB(a) and (b). High robustness points have unique correspondences (pointed by solid white arrows) and many low robustness points are matched under many-to-many (usually pair-to-pair) scenarios. Newly appeared critical points (pointed by a hollow white arrow) at t ₂ are not matched and are shown in black. In CombustionC(a) and (b), cε is quite small, therefore almost all points have unique matches except for two low robustness pairs which are matched as pairs (pointed by the hollow white arrows). Second, we can also measure the difference in vector fields between t ₁ and t ₂ in local regions. We compute ${\delta }^{{\ast}} =\sup _{x\in \varOmega }\vert \vert f_{t_{1}}(x) - f_{t_{2}}(x)\vert \vert _{2}$ for some Ω in the local neighborhoods of some critical points. Suppose the critical points in the local regions Ω has robustness values higher than cε, then we could further differentiate some of the many-to-many correspondence scenarios, and create unique correspondences. Such conditions are met by OceanA and OceanB, as shown in Fig. 9 OceanA (c) and (d) and OceanB (c) and (d). For example, in the local regions pointed to by the hollow white arrows, the critical points across t ₁ and t ₂ obtain unique correspondences since their robustness values are higher than the amount of vector field perturbation in their local neighborhoods. These correspondences are shown without sublevel sets in OceanA (e) and (f) and OceanB (e) and (f) (black marks points which are not matched). Finally, it is interesting to note that when critical points leave the boundary or appear near fold bifurcations, they typically do not find correspondences in the adjacent time slices (e.g. the black points shown in Fig. 9).

Discussion

Feature tracking, especially critical point tracking, is crucial for understanding the temporal behavior of time-varying vector fields. The theory of well groups allows us to make rigorous statements under mild assumptions about the correspondences: both when they are unique and when possible ambiguities exist. We infer correspondences between critical points based on their closeness in stability, measured by robustness, instead of just distance proximities within the domain. The correlations among critical points with high robustness values inherently capture some core structures of the time-varying vector field that is otherwise hidden due to the noise associated with region correspondence techniques.

The stability of well diagrams and the bijection between the critical points and the generators of the well groups serve as the motivation for viewing correspondence through well group theory. First, the well diagrams of a vector field and its PL interpolation are close, making it possible to translate the language of well groups from smooth to the PL setting in practice. Second, the bottleneck matching between two well diagrams constructed from two temporally adjacent vector fields gives a bijective mapping between generators of the well groups (which are also the generators of the 0-homology groups).

We show that robust generators are in some sense spatially stable, (namely, the generators must lie in the intersection of the connected components at the two time slices), and therefore there exist correspondences which respect the underlying geometry. The correspondences are not always unique since there may be several possible mappings between the generators of the robust well groups and the robust critical points. Static robustness captures this ambiguity making it possible to give sufficient conditions on the uniqueness of correspondences. On the other hand, we constructively show that whenever ambiguity exists, any of the possible correspondences are valid choices. This brings up many interesting questions. For example, does other criteria exist to choose the best correspondence from the set of possible correspondences? This may depend on the distance between the critical points, preservation of the topological skeletons, etc.

One future research direction is the constructions of different homotopy. The current construction, while bounded, is not guaranteed to be Lipschitz. It remains an open question how to construct a homotopy with a controlled Lipschitz constant. A second direction is the application of these methods to three dimensional and higher dimensional vector field data. The theorems and proofs are general and generalize to higher dimensions with minimal modification. Finally, the robustness framework gives correspondences a natural sense of scale: if we allow larger perturbations, more correspondences are possible. A natural question which arises is how to best visualize possible correspondences in a clear and intuitive way.