img2014 multiscale symmetry detection in scalar fields by clustering contours

1、IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, VOL. 20, NO. 12, DECEMBER 20142427Multiscale Symmetry Detection in Scalar Fields by Clustering ContoursDilip Mathew Thomas and Vijay Natarajan, Member, IEEEFig. 1. Clustering based analysis detects symmetry at different scales in a 3D cryo-el

2、ectron microscopy image of AMP-activated kinase (EMDB-1897). (left) The three-fold rotational symmetry is apparent from the volume rendering. (center) Contours are repre- sented as points in a high-dimensional shape descriptor space (illustrated in 2D). Symmetric contours form a cluster in the descr

3、iptor space and can be easily identied. 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.AbstractThe complexity in visualizing volumetric data often limits the scope of direct explor

4、ation of scalar elds. Isocontour extrac- tion is a popular method for exploring scalar elds because of its simplicity in presenting features in the data. In this paper, we present a novel representation of contours with the aim of studying the similarity relationship between the contours. The repres

5、entation maps contours to points in a high-dimensional transformation-invariant descriptor space. We leverage the power of this representation to design a clustering based algorithm for detecting symmetric regions in a scalar eld. Symmetry detection is a challenging problem because it demands both s

6、egmentation of the data and identication of transformation invariant segments. While the former task can be addressed using topological analysis of scalar elds, the latter requires geometry based solutions. Our approach combines the two by utilizing the contour tree for segmenting the data and the d

7、escriptor space for determining transformation invariance. We discuss two applications, query driven exploration and asymmetry visualization, that demonstrate the effectiveness of the approach.Index TermsScalar eld visualization, symmetry detection, contour tree, data exploration1 INTRODUCTIONMany s

8、cientic experiments and simulations generate scalar eld data that contain symmetric or repeating patterns. In many disciplines, symmetry plays an important role in studying the underlying scien- tic phenomenon. For example, in crystallography, symmetry infor- mation is used to determine the structur

9、e of a crystal 7. In product design, symmetry is important to ensure functional efciency and op- timal manufacturing cost 3. Symmetry is a useful cue in biology for determining growth and development of organs 35. Since the study of symmetric features is of great interest in scientic data analysis,

10、the problem of detecting symmetry in scalar elds has received consider-able attention among researchers in the recent past 10, 13, 19, 38, 39.Automatic detection of symmetry in scalar elds is a challenging problem and the quest for a widely applicable, efcient, and robust method for symmetry detecti

11、on is ongoing. Though symmetry identi- cation in scalar elds is a relatively new area of research, the problem of detecting symmetry in shapes has been well studied in the geome- try processing community. These studies have established that clus- tering based analysis result in superior performance

12、and robust iden- tication of symmetry. Some of these methods have been extended to scalar elds and they operate by determining symmetry transfor- mations through aggregation of local symmetry of sample points of the domain. Symmetry in shapes is associated with a group struc- ture on geometric objec

13、ts that are invariant under transformations. In scalar elds, it is more meaningful to relax this constraint and iden- tify all repeating occurrences since this is more useful for data ex- ploration. Scalar eld datasets are typically represented using scalar values assigned to a discrete set of sampl

14、e points that represent the domain under consideration. However, the domain and the scalar val- ues are assumed to be continuous by interpolating the values at the sample points. Therefore, the sample points in a scalar eld capture the lowest level of information. In practice, scientists are more in

15、ter- ested in higher level features, extracted through methods like segmen- tation and isosurface extraction, for studying the underlying physical Dilip Mathew Thomas is with Department of Computer Scienceand Automation, Indian Institute of Science, Bangalore, India. E-mail: dilipcsa.iisc.ernet.in.

16、Vijay Natarajan is with Department of Computer Science and Automation, and Supercomputer Education Research Centre, Indian Institute of Science, Bangalore, India. E-mail: vijayncsa.iisc.ernet.in.Manuscript received 31 Mar. 2014; accepted 1 Aug. 2014. Date ofpublication 11 Aug. 2014; date of current

17、version 9 Nov. 2014. For information on obtaining reprints of this article, please send e-mail to: .Digital Object Identier 10.1109/TVCG.2014.23463321077-2626 2014 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See /public

18、ations_standards/publications/rights/index.html for more information.2428IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, VOL. 20, NO. 12, DECEMBER 2014phenomenon. Hence, symmetry identication methods that are based on local information available at the sample points encounter consid- erabl

19、e difculty in representing and extracting meaningful symmetric regions. Moreover, these methods are computationally expensive since the number of sample points in scalar eld datasets is typically orders of magnitude higher than that in geometric shape datasets.Though it is clear from methods propose

20、d in the geometry pro- cessing community that a clustering based analysis offers signicant advantages in recognizing symmetry, we believe that unlike shapes, low-level information available at the sample points of the domain is not suited for symmetry identication in scalar elds. In this work, we pr

21、opose a novel symmetry detection method based on the idea of clustering contours. Isosurfaces are extensively used in studying scalar eld datasets and contours, which are connected components of isosurfaces, capture information about a scalar eld at a macroscale. Therefore, contours are more suitabl

22、e for a clustering based analysis as opposed to sample points of the domain. Contours belonging to regions with symmetric scalar eld distribution are also symmetric. Using an appropriate shape descriptor, our method maps contours to points in a descriptor space such that the distance between points

23、in the descriptor space is a measure of similarity between the contours. As a result, points in the descriptor space representing symmetric contours lie in close proximity to each other and form clusters in the descriptor space. The region of the domain corresponding to each such contour can be extr

24、acted and these regions are reported as symmetric. Note that the choice of the shape descriptor is not xed and depending on the noise characteristics and the denition of similarity relevant to the application of interest, an appropriate descriptor may be used. Fig. 1 illustrates our approach on a 3D

25、 cryo-EM image of AMP-activated ki- nase (EMDB-1897) with three-fold rotational symmetry. Our method identies symmetric regions of different scales. The large-scale fea- tures shown in gold and the small-scale features shown in blue and pink highlight the multiscale aspect of our approach.The main c

26、ontributions of this paper are the following:tra et al. 21. Some of these methods 2, 12, 22 have been applied to scalar elds 10,13,19. However, they struggle to address the chal- lenges in extending geometric methods to scalar elds. Scalar eld datasets are signicantly larger in size and hence symmet

27、ry detection is computationally costly. Geometric methods typically consider ge- ometric information derived from a small region around each sample point of the domain for symmetry recognition. A direct extension of this approach to scalar elds suffers from the difculty of capturing important featur

28、es and leads to poor performance in extracting higher level features and handling of noise in the data. Moreover, the scalar eld is considered to be continuous over the domain by interpolating the values at the sample points. Inspecting only the sample points introduces additional challenges due to

29、discretization errors since the symmetric counterpart for a given point may be aninterpolated point. Hong and Shen 10 propose a method to detect global reective symmetry by identifying planes of reection that minimize the differ- ence between the scalar value at a point and its reection. This method

30、 is computationally inefcient and cannot be easily extended to iden- tify other types of symmetry. Kerber et al. 13 build a graph network of crease line features and detect symmetry by computing transfor- mations that match subgraphs within the crease line network. Since only a small subset of featu

31、res in scalar elds contain crease lines, this method is not very useful in practice. Masood et al. 19 detect symmetry by identifying symmetry transformations as clusters in the space of all transformations. The clusters are generated by aggregating local symmetry transformations of pairs of points i

32、n the domain. This method relies on local signatures of sample points for determining transformations and as a result several parameters need to be tweaked at various stages of the symmetry detection pipeline to limit the ad- verse effects of variations in the local signatures and discretization err

33、ors. Moreover, the transformation space often contains additional transformations that introduces artifacts. The abovemethods compute transformations between candidate pairs for identifying symmetry and are computationally costly. Moreover, they are driven by purely lo- cal geometric measures and do

34、 not incorporate any criterion to either recognize important features or discard pairs corresponding to noise. Our method, on the other hand, uses topological information derived from the contour tree to infer importance of a feature and this allowsthe design of a feature-aware algorithm for symmetr

35、y identication. Bruckner et al. propose an information theoretic approach for iso- surface similarity detection 4, 8. They use mutual information be- tween distance transforms to quantify the information common to two isosurfaces and build a similarity map between all pairs of isosurfaces. Clusters

36、with high mutual information correspond to similar isosur- faces both within and across datasets. While this method is related since it is also based on isosurface similarity, the goal here is to select a subset of representative and possibly important isovalues. The dis- tance transform is used to

37、identify redundant isovalues corresponding to families of isosurfaces that form an onion-peel like layered arrange- ment. The goal of our method, on the other hand, is to locate regions that are similar and hence we compute similarity between contours and not isosurfaces. While the isosurface simila

38、rity map based method is limited to analyzing similarity between pairs of datasets, the descriptor space can be used to analyze multiple datasets simultaneously. Sim- ilarity between different scalar elds has also been studied by mea- suring the extent of overlap between contours 31, 32. The distanc

39、e transform descriptor and the overlap measure are affected by changes in orientation. Our method is not restricted to a particular choice of descriptor. Based on the requirements of the application under con- sideration, our method can be adapted to be sensitive or insensitive toorientation.A formu

40、lation of the problem of symmetry detection in scalar elds as a clustering problem in a shape descriptor space. This model provides a lot of exibility in analyzing similarity of scalar elds as well as handling noise since it allows the shape repre- sentation and the descriptor space to be varied.A n

41、ovel representation of contours as points in a contour descrip- tor space. Similarity between contours is naturally dened as the distance between points in this space. This is a generic represen- tation of independent interest and we show its benet in similar- ity analysis of scalar elds.A robust al

42、gorithm to detect symmetric regions at multiple scales. Though geometry based symmetry detection methods are typically computationally costly, we design an efcient algo- rithm that employs elegant optimizations by incorporating topo- logical information about the contours using the contour tree.Appl

43、ications to query driven exploration and asymmetry visual- ization.Symmetry information in scalar elds has been used for transfer function design, exploration of isosurfaces, selection of cross-section planes and view directions, linked selection and editing, query driven exploration, and visualizat

44、ion of features through dual rendering 10, 19,38,39. We believe that as better techniques for symmetry detection are developed, many more applications will emerge.2 RELATED WORKExisting symmetry identication methods in scalar elds can be broadly classied into two categories, namely, geometry based m

45、eth- ods and topology based methods. We briey review these methods in this section.2.1 Geometry based approachesSeveral methods have been proposed in the literature for detect- ing symmetry in shapes as described in the survey paper by Mi-2.2 Topology based methodsThomas and Natarajan propose topolo

46、gy based methods for symmetry identication and these methods are computationally efcient because they operate on graph representations of the scalar eld like the con- tour tree 38 and the extremum graph 39. The contour tree based method assumes that the subtrees of the contour tree corresponding to

47、symmetric regions are structurally similar. They detect symmetryTHOMAS AND NATARAJAN: MULTISCALE SYMMETRY DETECTION IN SCALAR FIELDS BY CLUSTERING CONTOURS2429by evaluating structural similarity between the subtrees using a sim- ilarity score that measures the overlap between the branches of the tre

48、es. This method can nd symmetry at multiple scales but cannot handle noise that destroy the repeating structure of the subtrees. The extremum graph based method selects a set of extrema called seed set and estimates distances robustly through a graph traversal procedure. A carefully chosen distance

49、threshold is used to disconnect the graph and classify the seeds into different groups called super-seeds. A re- gion growing procedure is then used to identify the symmetric region corresponding to each super-seed. This procedure makes a strong as- sumption that the symmetric regions can be identie

50、d purely from the proximity relationship between the seeds. Hence, it relies heavily on a meaningful selection of seed set which involves signicant effort and understanding about the symmetry of the domain. In addition, this method requires several thresholds to be set.The above methods, being topol

51、ogical in nature, do not ensure that the regions reported by them are indeed geometrically symmetric while our method, being geometric in nature, ensures that the regions extracted are symmetric. Moreover, current methods compare can- didate regions pairwise and rely on a similarity threshold to cla

52、ssify them into symmetric groups. Determining the similarity threshold is a challenge when using datasets with varying characteristics. Clustering based analysis avoids the need for pairwise comparisons. Instead, the symmetric regions are directly obtained as clusters in the descriptor space. Simila

53、rity between scalar elds have been studied in the con- text of shape matching applications by using graph matching methods on discrete approximations of the contour tree 9, 43. The contour tree provides metadata information about the contours and allows in- tegration of topological information in ge

54、ometric processing. Thus, by utilizing the descriptor space to capture geometric information about contours together with the power of the contour tree as a topological abstraction of contours, our method offers signicant advantages over existing symmetry identication methods.which is a costly opera

55、tion. Therefore, we use an alternate denition of symmetry. Let C be the set of all contours. Consider a functiong : C Rn such that g(c)= g(T (c) where T is a transformation. In other words, g is a function that maps each contour to a point in ahigh-dimensional space such that a contour and its copie

56、s are mapped to the same point. The point to which a contour is mapped is called a descriptor and the high-dimensional space is called the descriptor space, see Fig. 3. For illustration, the descriptor space is shown in 2D but the actual dimension of the space depends on the choice of the descriptor

57、. The distance between contours in the descriptor space is a measure of their similarity. In practice, scalar elds do not exhibit per- fect symmetry and therefore it is important to detect symmetry in an approximate sense. Ideally, deviation from perfect symmetry should be measured in the space of s

58、hapes but it is more convenient to mea- sure deviations in the descriptor space. If contours c1 and c2 are not perfectly symmetric, then c1 and c2 will not be mapped to the same point in the descriptor space. The distance between the contours in thedescriptor space, g(c1) g(c2) , will be indicative

59、of the deviationfrom perfect symmetry.Denition (Symmetric Contours). Contours c1 and c2 are perfectlysymmetric if g(c1) g(c2) = 0, where is a norm in the descriptorspace. They are -symmetric if g(c1) g(c2) , for 0.Shape descriptors have been extensively used in the geometry pro- cessing community for shape matching and there is