Human beings have special cognitive abilities that make it easy to recognize symmetric patterns but it is a tough task for a machine to do so. Automatic detection of symmetry is a challenging problem because both the segmentation of the domain into potential symmetric segments and the correspondence between segments that are symmetric need to be determined. Moreover, real life data sets never exhibit perfect symmetry. This introduces additional challenges in determining symmetry in an approximate sense as well as handling noise and missing parts within symmetric regions in the data. Since the search space for locating symmetric segments is quite large, it is also important to design an algorithm that is computationally efficient. Domain experts are interested in studying important features that provide insights about the underlying scientific phenomena that is being analyzed. Therefore, it is pertinent for a scalar field symmetry detection algorithm to report symmetric segments in a feature-aware manner.

We propose four methods to detect symmetry in scalar fields. The first method models symmetry detection as a subtree matching problem in the contour tree, which is a topological graph abstraction of the scalar field. The contour tree induces a hierarchical segmentation of features at different scales and hence this method can detect symmetry at different scales. The second method identifies symmetry by comparing dis- tances between extrema from each symmetric region. The distance is computed robustly using a topological abstraction called the extremum graph. Hence, this method can de- tect symmetry even in the presence of significant noise. The above methods compare pairs of regions to identify symmetry instead of grouping the entire set of symmetric regions as a cluster. This motivates the third and fourth methods which uses a clustering analysis for symmetry detection. In the third method, the contours of a scalar field are mapped to points in a high-dimensional shape descriptor space such that points corresponding to similar contours lie in close proximity to each other. Symmetry is identified by clustering the points in the descriptor space. In the fourth method, pairs of points which are locally symmetric vote for geometric transformations and symmetry transformation is identified as clusters in the space of all transformations.

The first method [1] models symmetry detection as a subtree matching problem in the contour tree, which is a topological graph abstraction of the scalar field. We propose a comparison measure for identifying similar subtrees of a contour tree based on a topological measure called persistence. This leads to an algorithm that detects symmetry by classifying subtrees of the contour tree into different groups. Regions of the domain corresponding to subtrees that belong to a common group are extracted and reported to be symmetric. Since the contour tree induces a hierarchical segmentation of features at different scales, this method can detect symmetry at different scales. Figure 2 shows an illustration of this method. A volume rendering of a cryo-electron microscopy image of RuBisCO molecule in complex with RuBisCO large subunit methyltransferase (EMDB 1734) highlights the symmetric or repeating patterns in the scalar field. Our algorithm classifies subtrees of the contour tree into different groups based on similarity. Subtrees that belong to the same group are shown with the same color. We extract regions of the domain corresponding to subtrees that belong to the same group and report them to be symmetric. Four different groups of symmetric regions identified by our algorithm are shown in cyan, magenta, brown, and violet.


Figure 2. Symmetric patterns identified using the contour tree in a cryo-electron microscopy image of RuBisCO molecule in complex with RuBisCO large subunit methyltransferase (EMDB 1734). (left) Volume rendering of the molecule highlight repeating structures in the scalar field. (center) The contour tree for the data set. Subtrees of the contour tree are classified into different groups based on similarity. Subtrees belonging to a common group are shown with the same color. (right) Four different types of regions, indicative of the different subunits in the molecule, identified by the symmetry detection algorithm shown in cyan, magenta, brown, and violet. Regions with the same color are symmetric.

The second method we propose identifies symmetry by comparing distances between extrema from each symmetric region [2]. We propose a data structure called the augmented extremum graph and use it to design an algorithm for robust estimation of distances. The augmented extremum graph captures both topological and geometric information of the scalar field and enables robust and computationally efficient detection of symmetry. We show through experiments on different cryo-electron microscopy datasets that the algorithm is capable of detecting symmetry even in the presence of significant noise. Figure 3 shows 4-fold rotational symmetry in the cryo-electron microscopy (cryo-EM) data of Rubisco RbcL8-RbcX2-8 complex (EMDB 1654). We perform Morse decomposition of the data and select a set of Morse cells as seed cells. The augmented extremum graph is traversed to compute distances from the seed cells to the remaining Morse cells and merge the seed cells into super-seeds. Eight seeds cells are selected for this data set and they merge to form four super-seeds as shown in the center. The four super-seeds provide an initial estimate of the 4-fold symmetry in the data which is then expanded in a region growing stage. The 4-fold symmetry in the data thus identified is shown on the right.


Figure 3. Symmetry identification algorithm based on augmented extremum graph detects symmetry even in the presence of significant noise in the electron microscopy data of the Rubisco RbcL8-RbcX2-8 complex (EMDB 1654). (left) Volume rendering shows symmetry and noise in the data. (center) A set of seed cells is chosen as source vertices for traversing the augmented extremum graph of the data. During the traversal, the seed cells merge together to form four symmetric super-seeds. Seed cells that belong to a common super-seed are shown with the same color. (right) The initial estimate of symmetry is expanded in a region growing stage to identify the symmetric regions. A symmetry-aware transfer function highlights the 4-fold rotational symmetry detected in the Rubisco complex.

The study of symmetry detection in shapes have established that clustering based analysis result in superior performance and robust identification of symmetry. Such an analysis avoids the need for comparing pairs of regions to identify symmetry and can instead group a set of symmetric regions as a cluster. This motivates the third method which uses a clustering analysis for symmetry detection [3]. In this method, we present a novel representation of contours with the aim of studying the similarity relationship between the contours. The representation maps contours to points in a high-dimensional transformation-invariant shape descriptor space. We leverage the power of this representation to design a clustering based algorithm for detecting symmetric regions in a scalar field. By selecting a contour from each arc of the contour tree, we are able to detect symmetry at different scales similar to the contour tree based approach. Noise in the data is seamlessly handled by the clustering framework through the choice of a robust shape descriptor. Thus, our approach combines the advantages of the earlier methods based on the contour tree and extremum graph. Figure 4 illustrates our approach on a 3D cryo-EM image of AMP-activated kinase (EMDB-1897) with three-fold rotational symmetry. The large-scale features shown in gold and the small-scale features shown in blue and pink highlight the multiscale aspect of our approach.


Figure 4. Clustering based analysis detects symmetry at different scales in a 3D cryo-electron microscopy image of AMP-activated kinase (EMDB-1897). (left) The three-fold rotational symmetry is apparent from the volume rendering. (center) Contours are represented as points in a high-dimensional shape descriptor space (illustrated in 2D). Symmetric contours form a cluster in the descriptor space and can be easily identified. Three such clusters are shown in gold, blue, and pink. (right) Three symmetric regions of different sizes, highlighted in gold, blue, and pink, detected by the method.

In this method [4], points are sampled from the domain and for each sample point a descriptor that captures the scalar field locally is computed. The descriptor consists of an invariant component and an alignment component. The invariant component of a point consists of properties of the field like scalar value, gradient magnitude, and curvature of the level set passing through the point. The alignment component of a point consists of vectors like the gradient vector and the principal curvature directions of the level set passing through the point. These vectors are used to define a local coordinate frame at each point. Sample points with similar invariant components are paired together and the transformation that maps the points in the pair is computed using their local coordinate frame. Since the scalar field is locally similar for the points in a pair, they are considered to be locally symmetric. Each pair then votes for the symmetry transformation that maps the points in the pair in the space of all transformations. Symmetry detection problem is then reduced to finding clusters in the high-dimensional transformation space. Each cluster corresponds to aggregation of votes for a particular symmetry transformation. These clusters are identified using a clustering technique. Finally, the symmetry transformation is spatially verified and the symmetric regions are extracted and reported. An illustration of this technique on a synthetic 2D scalar field data set is shown in Figure 5.


Figure 5. Illustration of symmetry detection by clustering point pairs on a synthetic data set. (left) The input scalar field. (left-centre) Points sampled from the domain shown in green. (centre) The sample points corresponding to the endpoints of each line segment are locally similar and hence paired together. For each pair, the transformation that maps the points in the pair is represented as a point in a transformation space. (right-centre) The clusters in the transformation space are identified. (right) For each cluster, the corresponding symmetry transformation is spatially verified and the symmetric regions, shown in red and blue, are extracted.

Visualizing symmetric or repeating patterns in the data often help the domain scientists in understanding and characterizing the features in the data. We design novel applications that use symmetry information to facilitate visualization and exploration of scalar field data. Some of the applications we propose like symmetry-aware transfer function design, symmetry-aware isosurface extraction, and symmetry-aware editing and rendering enhance traditional visualization methods. In addition, we also propose applications like query driven exploration, asymmetry visualization, and proximity-aware visualization that can significantly aid users in the analysis and exploration of scalar fields. We believe that the methods we propose for symmetry detection will open new frontiers in analyzing structural similarity of scalar fields and more applications of symmetry detection will emerge.