Visual data mining based on differential topology: a survey <s> Analyzing samples of a function R n → R <s> Researchers in the fields of computer graphics and geographical information systems GISs have extensively studied the methods of extracting terrain features such as peaks, pits, passes, ridges, and ravines from discrete elevation data. The existing techniques, however, do not guarantee the topological integrity of the extracted features because of their heuristic operations, which results in spurious features. Furthermore, there have been no algorithms for constructing topological graphs such as the surface network and the Reeb graph from the extracted peaks, pits, and passes. This paper presents new algorithms for extracting features and constructing the topological graphs using the features. Our algorithms enable us to extract correct terrain features; i.e., our method extracts the critical points that satisfy the Euler formula, which represents the topological invariant of smooth surfaces. This paper also provides an algorithm that converts the surface network to the Reeb graph for representing contour changes with respect to the height. The discrete elevation data used in this paper is a set of sample points on a terrain surface. Examples are presented to show that the algorithms also appeal to our visual cognition. <s> BIB001 </s> Visual data mining based on differential topology: a survey <s> Analyzing samples of a function R n → R <s> Topological volume skeletons represent level-set graphs of 3D scalar fields, and have recently become crucial to visualizing the global isosurface transitions in the volume. However, it is still a time-consuming task to extract them, especially when input volumes are large-scale data and/or prone to small-amplitude noise. The paper presents an efficient method for accelerating the computation of such skeletons using adaptive tetrahedralization. The tetrahedralization is a top-down approach to linear interpolation of the scalar fields in that it selects tetrahedra to be subdivided adaptively using several criteria. As the criteria, the method employs a topological criterion as well as a geometric one in order to pursue all the topological isosurface transitions that may contribute to the global skeleton of the volume. The tetrahedralization also allows us to avoid unnecessary tracking of minor degenerate features that hide the global skeleton. Experimental results are included to demonstrate that the present method smoothes out the original scalar fields effectively without missing any significant topological features. <s> BIB002 </s> Visual data mining based on differential topology: a survey <s> Analyzing samples of a function R n → R <s> Scientific visualization and illustration tools are designed to help people understand the structure and complexity of scientific data with images that are as informative and intuitive as possible. In this context the use of metaphors plays an important role since they make complex information easily accessible by using commonly known concepts. In this paper we propose a new metaphor, called "topological landscapes," which facilitates understanding the topological structure of scalar functions. The basic idea is to construct a terrain with the same topology as a given dataset and to display the terrain as an easily understood representation of the actual input data. In this projection from an n-dimensional scalar function to a two-dimensional (2D) model we preserve function values of critical points, the persistence (function span) of topological features, and one possible additional metric property (in our examples volume). By displaying this topologically equivalent landscape together with the original data we harness the natural human proficiency in understanding terrain topography and make complex topological information easily accessible. <s> BIB003 </s> Visual data mining based on differential topology: a survey <s> Analyzing samples of a function R n → R <s> A contour tree is a powerful tool for delineating the topological evolution of isosurfaces of a single-valued function, and thus has been frequently used as a means of extracting features from volumes and their time-varying behaviors. Several sophisticated algorithms have been proposed for constructing contour trees while they often complicate the software implementation especially for higher-dimensional cases such as time-varying volumes. This paper presents a simple yet effective approach to plotting in 3D space, approximate contour trees from a set of scattered samples embedded in the high-dimensional space. Our main idea is to take advantage of manifold learning so that we can elongate the distribution of high-dimensional data samples to embed it into a low-dimensional space while respecting its local proximity of sample points. The contribution of this paper lies in the introduction of new distance metrics to manifold learning, which allows us to reformulate existing algorithms as a variant of currently available dimensionality reduction scheme. Efficient reduction of data sizes together with segmentation capability is also developed to equip our approach with a coarse-to-fine analysis even for large-scale datasets. Examples are provided to demonstrate that our proposed scheme can successfully traverse the features of volumes and their temporal behaviors through the constructed contour trees. <s> BIB004 </s> Visual data mining based on differential topology: a survey <s> Analyzing samples of a function R n → R <s> We present a novel method to visualize multidimensional point clouds. While conventional visualization techniques, like scatterplot matrices or parallel coordinates, have issues with either overplotting of entities or handling many dimensions, we abstract the data using topological methods before presenting it. We assume the input points to be samples of a random variable with a high-dimensional probability distribution which we approximate using kernel density estimates on a suitably reconstructed mesh. From the resulting scalar field we extract the join tree and present it as a topological landscape, a visualization metaphor that utilizes the human capability of understanding natural terrains. In this landscape, dense clusters of points show up as hills. The nesting of hills indicates the nesting of clusters. We augment the landscape with the data points to allow selection and inspection of single points and point sets. We also present optimizations to make our algorithm applicable to large data sets and to allow interactive adaption of our visualization to the kernel window width used in the density estimation. <s> BIB005
The aforementioned algorithm is quite effective for discrete samples of 2D/3D scalar fields, since we can linearly interpolate the function value in the data domain easily by decomposing it into triangles/tetrahedra. Nonetheless, implementing the algorithm incurs other problems due to the complexity for partitioning the data domain especially when its dimension is equal to 4 or more. This problem has recently been tackled by approaches to projecting the high-dimensional data samples onto screen space using dimensionality reduction techniques BIB004 , which have been available in the community of machine learning. The basic idea behind this approach Figure 4 Examples of contour trees extracted from discrete samples on functions R 2 → R and R 3 → R. (a) A digital elevation model around Hakone area, which contains a crater lake (Lake Ashi) surrounded by mountains BIB001 . (b) Voxel samples at a 3D grid in a volume data, which is obtained through a simulation of the probability distribution of a nucleon in the atomic nucleus BIB004 O BIB002 . http://www.pacific-mathforindustry.com/content/6/1/4 is to introduce different metrics among the discrete data samples so that we can effectively locate each sample point on the contour tree to be constructed. This has been accomplished by constructing a proximity graph over the data samples to infer its manifold connectivity and then projecting the samples onto the screen space to stipple the contour tree. In practice, we first construct the proximity graph by searching for the nearest k-neighbors of each sample using the new metric based on their spatial relationship and function values, and then projecting the samples onto the contour tree by approximating the distance between every pair of sample points. As shown in Figure 5 , the dimensionality reduction process effectively permits us to construct the contour tree from a set of discrete samples embedded in the high-dimensional data domain. Figure 6 shows another example where the features of differential topology are extracted from time-varying volume data. We can also use the proximity graphs to directly define the partial orders among data samples in terms of the scalar function value. Nonetheless, it is still hard to select appropriate types of graphs for constructing the manifold connectivity, since we have to keep the graph as sparse as possible to minimize the associated computational cost. In practice, we can refer to BIB005 for several possible types of vertex connectivities. The work also successfully constructed a visual metaphor called topological landscape BIB003 , which is a variant of a contour tree for a terrain surface and is currently often employed for the visual analysis of high dimensional data.