 |
Jian Sun
|
|
About Me
I am a PostDoc scholar in Department of Computer Science at Stanford University. I work with Prof. Leonidas J. Guibas and I am a member of his Geometric Computation Group. I earned my Ph.D in Computer Science from Department of Computer Science and Engineering at the Ohio State University under the supervision of Prof. Tamal K. Dey. Before that, I spent seven years in Tsinghua University and got my M.S. in computer science and B.E. in mechanical engineering. |
|
Research Interests
My research interest is in developing geometric and topological methods for shape and data analysis. |
Publications
|
A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion written with Leonidas Guibas and Maks Ovsjanikov SGP 2009, to appear We propose a novel point signature based on the properties of the heat diffusion process on a shape. Our signature, called the Heat Kernel Signature (or HKS), is obtained by restricting the well-known heat kernel to the temporal domain. Remarkably we show that under certain mild assumptions, HKS captures all of the information contained in the heat kernel, and characterizes the shape up to isometry. This means that the restriction to the temporal domain, on the one hand, makes HKS much more concise and easily commensurable, while on the other hand, it preserves all of the information about the intrinsic geometry of the shape. In addition, HKS inherits many useful properties from the heat kernel, which means, in particular, that it is stable under perturbations of the shape. Our signature also provides a natural and efficiently computable multi-scale way to capture information about neighborhoods of a given point, which can be extremely useful in many applications. To demonstrate the practical relevance of our signature, we present several methods for non-rigid multi-scale matching based on the HKS and use it to detect repeated structure within the same shape and across a collection of shapes. |
|
Integral Estimation from Point Cloud in $\real^d$: a Geometric View written with Chuanjiang Luo and Yusu Wang SoCG 2009, to appear Integration over a domain, such as a Euclidean space or a Riemannian manifold, is a fundamental problem across scientific fields. Many times, the underlying domain is only accessible through a discrete approximation, such as a set of points sampled from it, and it is crucial to be able to estimate integral in such discrete settings. In this paper, we study the problem of estimating the integral of a function over a k-submanifold embedding in $\reals^d$, from its function values over a set of sample points. Previously, such estimation is usually obtained in a statistical setting, where input data is usually assumed to be drawn from certain probabilistic distribution. Our paper is the first to consider this important problem for arbitrary point clouds data (PCD), and provide theoretical guarantees. We approaches the problem from a geometric point of view. Specifically, we model the integral as a weighted sum, and propose two weighting schemes: the Voronoi and the Principle Eigenvector weighting schemes. The running time of both methods depend mostly on the intrinsic dimension of the underlying manifold, instead of on the ambient dimensions. We show that the estimation based on the Voronoi scheme converges to the true integral (explicit error bound is given). This is the first result of this sort for estimating integral from general PCDs. For the Principle Eigenvector scheme, we present its connection to the Heat diffusion operator, and illustrate several justifications behind its construction. Experiments show that both new methods consistently out-perform common statistical methods under various sampling conditions. |
|
Topological Methods for Exploring Low-density States in Biomolecular Folding Pathways Yuan Yao, Jian Sun, Xuhui Huang, Gregory R. Bowman, Gurjeet Singh, Michael Lesnick, Leonidas J. Guibas, Vijay S. Pande, Gunnar Carlsson. Journal of Chemical Physics, accepted Characterization of transient intermediate or transition states is crucial for the description of biomolecular folding pathways, which is however difficult in both experiments and computer simulations. Such transient states are typically of low population in simulation samples. Even for simple systems such as RNA hairpins, recently there are mounting debates over the existence of multiple intermediate states. In this paper, we develop a computational approach to explore the relatively low populated transition or intermediate states in biomolecular folding pathways, based on a topological data analysis tool, Mapper, with simulation data from large-scale distributed computing. The method is inspired by the classical Morse theory in mathematics which characterizes the topology of high dimensional shapes via some functional level sets. In this paper we exploit a conditional density filter which enables us to focus on the structures on pathways, followed by clustering analysis on its level sets, which helps separate low populated intermediates from high populated uninterested structures. A successful application of this method is given on a motivating example, a RNA hairpin with GCAA tetraloop, where we are able to provide structural evidence from computer simulations on the multiple intermediate states and exhibit different pictures about unfolding and refolding pathways. The method is effective in dealing with high degree of heterogeneity in distribution, capturing structural features in multiple pathways, and being less sensitive to the distance metric than nonlinear dimensionality reduction or geometric embedding methods. The methodology described in this paper admits various implementations or extensions to incorporate more information and adapt to different settings, which thus provides a systematic tool to explore the low density intermediate states in complex biomolecular folding systems. |
|
Constructing Laplace Operator from Point Clouds in R^d written with Mikhail Belkin and Yusu Wang. SODA 2009, to appear We present an algorithm for approximating the Laplace-Beltrami operator from an arbitrary point cloud obtained from a k-dimensional submanifold embedded in the $d$-dimensional space. We show that this PCD Laplace (Point-Cloud Data Laplace) operator converges to the Laplace-Beltrami operator on the underlying manifold as the point cloud becomes denser. Unlike the previous work, we do not assume that the data samples are independent identically distributed from a probability distribution and do not require a global mesh. The resulting algorithm is easy to implement. We present experimental results indicating that even for point sets sampled from a uniform distribution, PCD Laplace converges faster than the weighted graph Laplacian. We also show that certain geometric invariants, such as manifold area, can be estimated directly from the point cloud using our PCD Laplacian with reasonable accuracy. We make the software publically available at the authors' webpages. |
|
Structural Insight into RNA Hairpin Folding Intermediates Gregory R. Bowman, Xuhui Huang, Yuan Yao, Jian Sun, Gunnar Carlsson, Leonidas J. Guibas, and Vijay S. Pande; J. Am. Chem. Soc., ja8032857, ASAP article, (2008) Hairpins are a ubiquitous secondary structure motif in RNA molecules. Despite their simple structure, there is some debate over whether they fold in a two-state or multi-state manner. We have studied the folding of a small tetraloop hairpin using a serial version of replica exchange molecular dynamics on a distributed computing environment. On the basis of these simulations, we have identified a number of intermediates that are consistent with experimental results. We also find that folding is not simply the reverse of high-temperature unfolding and suggest that this may be a general feature of biomolecular folding. |
|
Global Intrinsic Symmetries of Shapes written with Leonidas J. Guibas and Maks Ovsjanikov. SGP 2008, Best Student Paper Although considerable attention in recent years has been given to the problem of symmetry detection in general shapes, few methods have been developed that aim to detect and quantify the intrinsic symmetry of a shape rather than its extrinsic, or pose-dependent symmetry. In this paper, we present a novel approach for efficiently computing symmetries of a shape which are invariant up to isometry preserving transformations. We show that the intrinsic symmetries of a shape are transformed into the Euclidean symmetries in the signature space defined by the eigenfunctions of the Laplace-Beltrami operator. Based on this observation, we devise an algorithm which detects and computes the isometric mappings from the shape onto itself. We show that our approach is both computationally efficient and robust with respect to small non-isometric deformations, even if they include topological changes. |
|
Computing Geometry-aware Handle and Tunnel Loops in 3D Models written with David Cohen-Steiner, Tamal K. Dey and Kuiyu Li. SIGGRAPH 2008, to appear Many applications such as topology repair, model editing, surface parameterization, and feature recognition benefit from computing loops on surfaces that wrap around their `handles' and `tunnels'. Computing such loops while optimizing their geometric lengths is diffiult. On the other hand, computing such loops without considering geometry is easy but may not be very useful. In this paper we strike a balance by computing topologically correct loops that are also geometrically relevant. Our algorithm is a novel application of the concepts from topological persistence introduced recently in computational topology. The usability of the computed loops is demonstrated with some examples in feature identification and topology simplification. |
|
Discrete Laplace Operator on Meshed Surfaces written with Mikhail Belkin and Yusu Wang. SoCG 2008 In recent years a considerable amount of work in graphics and geometric optimization used tools based on the Laplace-Beltrami operator on a surface. The applications of the Laplacian include mesh editing, surface smoothing, and shape interpolations among others. In this paper we propose the first algorithm for approximating the Laplace operator of a surface from a mesh with theoretical guarantees, applying to arbitrary meshed surfaces. We show that for a sufficiently fine mesh over an arbitrary surface, our mesh Laplacian is close to the Laplace-Beltrami operator on the surface. The error guarantee is based on a new result on approximating integrals over surfaces, which is of independent interest. Experiments show that our algorithm compares favorably with other methods and is able to provide accurate approximation of the Laplace operator for several types of meshes on several different surfaces. |
|
Reconstructing and Analyzing Surfaces in 3-Space Thesis, The Ohio State University, July 2007 Adviser: T. K. Dey. One often analyzes surfaces through their induced structures such as the convex hull or the homology group. It is important to derive appropriate induced structures. If they are too complicated, it becomes hard to extract the information about the original surface from them. If they are too simple, little or nothing about the surface can be inferred from them. To analyze surfaces computationally, it is important that the induced structures can be computed efficiently. In this work, we address two induced structures for surfaces: curve-skeletons and handle and tunnel loops. We give formal definitions for both structures and propose algorithms to compute them. One can also reverse the direction, namely, given an induced structure, how to recover the original surface. It is hard, sometimes impossible, to recover the surface exactly. We often seek to obtain an approximation with bounded error. The problem of reconstructing surfaces from their sample points is such an example. This problem has been studied for almost three decades though there are still many open gaps. In this work, we focus on how to handle sample points when they are contaminated with noise. We define a smooth surface out of the noisy sample points by using a technique called moving least squares. We prove that under a non-uniform sampling condition, this smooth surface approximates the sampled surface correctly in terms of topology and geometry. The effectiveness of the proposed algorithms is demonstrated through numerous examples and experimental results. |
|
On Computing Handle and Tunnel Loops written with T. K. Dey and Kuiyu Li. OSU-CISRC-6/07-TR48 Many applications seek to identify features like `handles' and `tunnels' in a shape bordered by a surface embedded in three dimensions. To this end we define handle and tunnel loops on surfaces which can help identifying these features. We show that a closed surface of genus $g$ always has $g$ handle and $g$ tunnel loops induced by the embedding. For a class of shapes that retract to graphs, we characterize these loops by a linking condition with these graphs. These characterizations lead to algorithms for detection and generation of these loops. We provide an implementation with applications to feature detection and topology simplification to show the effectiveness of the method. |
|
Defining and Computing Curve-skeletons with Medial Geodesic Function written with T. K. Dey. Symposium on Geometry Processing 2006. Many applications in geometric modeling, computer graphics, visualization and computer vision benefit from a reduced representation called curve-skeletons of a shape. These are curves possibly with branches which compactly represent the shape geometry and topology. The lack of a proper mathematical definition has been a bottleneck in developing and applying the the curve-skeletons. A set of desirable properties of these skeletons has been identified and the existing algorithms try to satisfy these properties mainly through a procedural definition. We define a function called medial geodesic on the medial axis which leads to a methematical definition and an approximation algorithm for curve-skeletons. Empirical study shows that the algorithm is robust against noise, operates well with a single user parameter, and produces curve-skeletons with the desirable properties. Moreover, the curve-skeletons can be associated with additional attributes that follow naturally from the definition. These attributes capture shape eccentricity, a local measure of how far a shape is away from a tubular one. |
|
Normal and Feature Estimations from Noisy Point Clouds written with T. K. Dey. The 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2006 We consider the problem of normal and feature size approximations of a surface from its point cloud data that may be noisy. These problems are central to many applications dealing with point cloud data. Although solutions to these problems for noise-free case are known, the case with noise is not fully understood. We provide new analysis that brings new insights and design new algorithms based on these analyses. |
|
An Adaptive MLS Surface for Reconstruction with Guarantees. written with T. K. Dey. Symposium on Geometry Processing 2005. Recent work have shown that moving least squares (MLS) surfaces can be used effectively to reconstruct surfaces from possibly noisy point cloud data. Several variants of MLS surfaces have been suggested, some of which have been analyzed theoretically for guarantees. These analyses, so far, have assumed uniform sampling density. We propose a new variant of the MLS surface that, for the first time, incorporates local feature sizes in its formulation, and we analyze it for reconstruction guarantees using a non-uniform sampling density. The proposed variant of the MLS surface has several computational advantages over existing MLS methods. For those interested in the proofs, please see the extended version Technical Report OSU-CISRC-4-05-TR26, April, 2005. |
|
Normal Estimation for Point Clouds: A Comparison Study for a Voronoi Based Method written with T. K. Dey and Gang Li. Symposium on Point-Based Graphics 2005. Many applications that process a point cloud data benefit from a reliable normal estimation step. Given a point cloud presumably sampled from an unknown surface, the problem is to estimate the normals of the surface at the data points. Two approaches, one based on numerical optimizations and another based on Voronoi diagrams are known for the problem. Variations of numerical approaches work well even when point clouds are contaminated with noise. Recently a variation of the Voronoi based method is proposed for noisy point clouds. The centrality of the normal estimation step in point cloud processing begs a thorough study of the two approaches so that one knows which approach is appropriate for what circumstances. This paper presents such results. |
|
Extremal Surface Based Projections Converge and Reconstruct with Isotopy written with T. K. Dey and S. Goswami. Technical Report OSU-CISRC-05-TR25, April, 2005 Many real world applications need to model a smooth surface from a noisy point sample. In order to eliminate unnecessary undulations on the output surface, it is necessary to project the points on a nearby smooth surface and then approximate the smooth surface with a surface reconstruction algorithm. Moving Least Square (MLS) surfaces in the family of extremal surfaces have been shown to be useful as projection targets. However, it is unknown if the extremal surface based projection procedure converges and if the target extremal surface is isotopic to the original sampled surface. We prove these two facts. The success the entire projection method depends on the quality of the estimated normals at the sample points. We suggest an algorithm to estimate the normals from the noisy samples which can be of independent interest for other applications. We also present some experimental results. |
Submitted and preprints
|
A Fast Geometric Clustering Method on Conformation Space of Biomolecules Jian Sun, Yuan Yao, Xuhui Huang, Vijay Pande, Gunnar Carlsson and Leonidas J. Guibas preprint |
|
A faster algorithm for matching planar maps under the weak Fr\'{e}chet distance written with Daniel Chen, Leonidas J. Guibas and Qixing Huang preprint We consider the problem of matching a polygonal curve of complexity $p$ with an arbitrary curve on an embedded planar graph of complexity $q$. With the large amount of GPS and location trace data that have become available in recent years, algorithms for such problems have become increasingly important. Direct applications include matching a GPS trace to a given roadmap and indirect applications including building and querying databases of polygonal curves. As problem sizes increase, improvements in asymptotic runtime may prove to be useful and we present an algorithm which solves the problem with respect to the weak Fr\'{e}chet distance in $O(pq)$ time, which is an asymptotic improvement. In the process of doing so, we also provide a more intuitive and practical approach for the recursive division procedure used in Henzinger et al.'s shortest path algorithm for planar graphs. Unlike previous approaches to minimize the asymptotic complexity of calculating the Fr\'{e}chet distance, our method does not involve parametric search, and hence is also more practical to implement. |