Empirical Convergence

We now evaluate how the above probabilistic idea performs compared to the steepest descent strategy. LetΩ= [−2,2]²andα∈R⁺. The function f: Ω→Ris given as

f(x,y) =−e^−α

√

x²+y²−12

−0.3(x+y). (6.6)

(x, f

y) Steepestdescent Probabilisticdescent

(a)α=20(b)α=21(c)α=22(d)α=23(e)α=24(f) Figure6.4:Theanalyticexamplef(6.6).Thefirstrowshowsthesampledfunctionfcolor-codedfordifferentchoicesofα.Red functionvalue,whilebluedenotesalowvalue.Blacklinesdepictintegrallinesofthegradient∇f.Thesecondandthirdrowshowthe basedonAlgorithm5usingthesteepestdescentandourprobabilisticlinkselectionstrategy,respectively.Minima,saddlesandmaxima blue,yellowandredspheres,whereasthe0-and1-separatricesareshownasblueandredlines,respectively.

10⁴ 10⁵ 10⁶ 10⁷ 10⁸ 10⁹

(b) Statistical characteristics of probabilistic error (this paper)

Figure 6.5: The analytic example f (6.6). (a) and (b) show the Hausdorff distance of the approximated center circle to the reference circle for different choices ofα and increasing resolution. (a) shows the evolution of the error using the steepest descent approach. (b) shows two statistical characteristics of the error of the probabilistic ap-proach.

The function f describes a circle engraved on a tilted plane. The sharpness of this circle is defined by the parameterα. Forα→∞, the circle becomes arbitrary sharp.

Forα→0, f gets flattened. Varyingα allows us to simulate smooth as well as sharp features appearing in many applications. An illustration of f sampled on a 2048²grid for different choices ofα is given in the first row of Figure 6.4. Integral lines of the continuous gradient∇f are depicted by black lines using the dual streamline seeding technique by Rosanwo et al. [RPP⁺09]. Converging integral lines indicate thereby the existence of a separatrix. In the following paragraphs, we choose the engraved circle as a reference feature. For illustration, it is shown as a white circle line in the first row of Figure 6.4.

We applied Algorithm 5 using the steepest descent version as well as the proba-bilistic version to construct a combinatorial gradient of f for different choices ofα. The resulting Morse-Smale complexes of the steepest descent version are shown in the second row of Figure 6.4. Our reference feature – the white circle – is visually well recovered for large values ofα, which confirms also the extraction results in Sec-tion 5.3 and of recently proposed methods [CCL03, KRHH11]. In many applicaSec-tions, the desired features are sufficiently sharp.

However, deviations from the reference circle become visible if the feature gets smooth, i.e., for small choices ofα. The steepest descent version of Algorithm 5 is not able to recover the circle forα =2⁰andα =2¹. The probabilistic approach, in contrast, is able to recover the circle for all choices ofα. The resulting Morse-Smale complexes are shown in the third row of Figure 6.4.

To quantify the approximation error, we measured the Hausdorff distance [Hau14]

of the reference circle to the approximated circle. Figure 6.5a shows the approximation error for Algorithm 5 using the steepest descent strategy in a log-log plot. Although the extraction result looked visually reasonable for largeα-values, there is no convergence for anyα. The Hausdorff distance to the reference circle is not decreasing if a finer grid is employed.

For the probabilistic approach, we did 200 runs of Algorithm 5. Figure 6.5b shows the mean value of the Hausdorff distance and its standard deviation. Both quantities are converging to zero. Hence, the sampling as well as the quantization error are reduced when a finer grid is employed. However, it needs to be noted that the approximation error for very sharp features (α=2⁵) is slightly larger compared to the steepest descent

0 0.025 0.05 0.075 0.1 0.125 0.15 0

10 20 30

Hausdorff Distance

ProbabilityD

Figure 6.6: Distribution of Hausdorff distance error. The blue, black and red curves show the estimated probability density function of the Hausdorff distance between the center circle and the reference circle (as shown in Figure 6.4) for different resolutions.

strategy when coarse grids are used. It is also worth mentioning that the convergence speed is not optimal since we employed uniform refinements. Increasing the efficiency may be achieved by developing an adaptive grid refinement approach. This may be particularly effective since a high resolution is only needed in the vicinity of the sepa-ratrices.

In Figure 6.6, we plotted a kernel density estimate [BGK10] of the probability den-sity of the Hausdorff distance error for different resolutions. We applied Algorithm 5 using the probabilistic approach 1000 times to obtain a sufficient number of samples for the density estimate. The overall shape of the densities suggests a sequence of binomial error distributions that converge to a normal distribution.

To demonstrate that the probabilistic approach is convergent for general smooth functions, we considered a set of smooth functions generated by the expression

2 m,n=1

∑

X_m,n⁽¹⁾sin(mx) +X_m,n⁽²⁾cos(mx) X_m,n⁽³⁾sin(ny) +X_m,n⁽⁴⁾cos(ny)

, (6.7)

where theX_m,n^(j)’s are random variables uniformly distributed in[−1,1]. This ex-pression is now evaluated on the domain[−π,π]²discretized using two different grid resolutions. We selected four representatives of this set of functions and applied the steepest descent and our probabilistic version of Algorithm 5. The resulting separatri-ces are shown in Figure 6.7.

It is apparent that the steepest descent approach does not yield separatrices with a correct embedding. The proposed probabilistic link selection strategy, however, visu-ally converges to the correct solution. We applied this idea to a much larger number of such functions, and always observed the above behavior.

We can conclude that a probabilistic extension of Algorithm 5 yields combinato-rial gradients whose separatrices converge to their continuous counterpart when the grid resolution is increased. We can therefore benefit from the simplicity and robust-ness of discrete Morse theory, and still obtain topological structures that converge to

Testfunction1

512×512

Steepest descent Probabilistic

4096×4096

Steepest descent Probabilistic

Testfunction2Testfunction3Testfunction4

Figure 6.7: Comparison of the steepest descent and the probabilistic approach using generic functions. The four rows show four different functions randomly generated using expression (6.7). Red denotes a high function value, while blue denotes a low value. Black lines depict integral lines of their gradient. The left two columns show the extracted Morse-Smale complexes for each function sampled on a 512²grid using the steepest descent and our probabilistic link selection strategy, respectively. The right two columns show the result on a 4096²grid. Minima, saddles and maxima are shown as blue, yellow and red spheres, whereas the 0- and 1-separatrices are shown as blue and red lines, respectively. Since separatrices are integral lines of the gradient, the blue and red lines should follow the black lines. White arrows indicate regions where the difference of the two approaches is visually apparent.

torial 1-streamlines can merge and split in three dimensions due to the fundamentally different structure of the cell graph (Section 3.2.4). It turns out that this property results in space-filling combinatorial separation surfaces if the links are chosen in the above probabilistic way. A more adapted link selection strategy is necessary.