Publications

Average Interpolating Wavelets on Point Clouds and Graphs arXiv preprint, arXiv:1110.2227v1 [math.FA] We introduce a new wavelet transform suitable for analyzing functions on point clouds and graphs. Our construction is based on a generalization of the average interpolating refinement scheme of Donoho. The most important ingredient of the original scheme that needs to be altered is the choice of the interpolant. Here, we define the interpolant as the minimizer of a smoothness functional, namely a generalization of the Laplacian energy, subject to the averaging constraints. In the continuous setting, we derive a formula for the optimal solution in terms of the poly-harmonic Green's function. The form of this solution is used to motivate our construction in the setting of graphs and point clouds. We highlight the empirical convergence of our refinement scheme and the potential applications of the resulting wavelet transform through experiments on a number of data stets.
Multiscale Biharmonic Kernels SGP Best Paper Award, 3rd place Computer Graphics Forum (Symposium on Geometry Processing), Volume 30, Number 5 (July 2011). This paper introduces a general principle for constructing multiscale kernels on surface meshes, and presents a construction of the multiscale pre-biharmonic and multiscale biharmonic kernels. Our construction is based on an optimization problem that seeks to minimize a smoothness criterion, the Laplacian energy, subject to a sparsity inducing constraint. Namely, we use the lasso constraint, which sets an upper bound on the L1-norm of the solution, to obtain a family of solutions parametrized by this upper-bound parameter. The interplay between sparsity and smoothness results in smooth kernels that vanish away from the diagonal. We prove that the resulting kernels have gradually changing supports, consistent behavior over partial and complete meshes, and interesting limiting behaviors (e.g. in the limit of large scales, the multiscale biharmonic kernel converges to the Green's function of the biharmonic equation); in addition, these kernels are based on intrinsic quantities and so are insensitive to isometric deformations. We show empirically that our kernels are shape-aware, are robust to noise, tessellation, and partial object, and are fast to compute. Finally, we demonstrate that the new kernels can be useful for function interpolation and shape correspondence. Paper
Interpolated Eigenfunctions for Volumetric Shape Processing To appear in The Visual Computer Abstract This paper introduces a set of volumetric functions suitable for geometric processing of volumes. We start with Laplace-Beltrami eigenfunctions on the bounding surface and interpolate them into the interior using barycentric coordinates. The interpolated eigenfunctions: 1) can be computed efficiently by using the boundary mesh only; 2) can be seen as a shape-aware generalization of barycentric coordinates; 3) can be used for efficiently representing volumetric functions; 4) can be naturally plugged into existing spectral embedding constructions such as the diffusion embedding to provide their volumetric counterparts. Using the interior diffusion embedding we define the interior Heat Kernel Signature (iHKS) and examine its performance for the task of volumetric point correspondence. We show that the three main qualities of the surface Heat Kernel Signature -- being informative, multiscale, and insensitive to pose -- are inherited by this volumetric construction. Finally, we construct a bag of features based shape descriptor that aggregates the iHKS signatures over the volume of a shape, and evaluate its performance on a public shape retrieval benchmark. We find that while, theoretically, strict isometry invariance requires concentrating on the intrinsic surface properties alone, yet, practically, pose insensitive shape retrieval can be achieved using volumetric information. Paper
A Versatile Framework for Shape Description The Visual Computer, Volume 26, Number 10, 1245-1256 We present a shape description framework that generates a multitude of shape descriptors through a variety of design and continuum of parameter choices. Our parameter is a surface mesh, referred to as template, which is supplied at run time, and allows generating different shape descriptors for the same model. Our framework extracts a numerical shape descriptor by computing a selected function on the model mesh, mapping (transferring) it to the template, expanding the mapped function in terms of a basis on the template, and collecting the expansion coefficients into a vector. We investigate possible design choices for the steps in the framework, and introduce novel approaches that provide further freedom in generating a multitude of previously unknown descriptors. We show that our approach is a generalization of the way some of the existing numerical descriptors are defined, and that for appropriate template choices one is able to reproduce some of the well-known descriptors. Finally, we show empirically that design and parameter choices have non-trivial effects on the descriptor's performance, and that better retrieval results can be obtained by combining descriptors obtained via different templates. Paper
Barycentric Coordinates on Surfaces Computer Graphics Forum (Symposium on Geometry Processing), Volume 29, Number 5 (July 2010). This paper introduces a method for defining and efficiently computing barycentric coordinates with respect to polygons on general surfaces. Our construction is geared towards injective polygons (polygons that can be enclosed in a metric ball of an appropriate size) and is based on replacing the linear precision property of planar coordinates by a requirement in terms of center of mass, and generalizing this requirement to the surface setting. We show that the resulting surface barycentric coordinates can be computed using planar barycentric coordinates with respect to a polygon in the tangent plane. We prove theoretically that the surface coordinates properly generalize the planar coordinates and carry some of their useful properties such as unique reconstruction of a point given its coordinates, uniqueness for triangles, edge linearity, similarity invariance, and smoothness; in addition, these coordinates are insensitive to isometric deformations and can be used to reconstruct isometries. We show empirically that surface coordinates are shape-aware with consistent gross behavior across different surfaces, are well-behaved for different polygon types/locations on variety of surface forms, and that they are fast to compute. Finally, we demonstrate effectiveness of surface coordinates for interpolation, decal mapping, and correspondence refinement. Paper Presentation (PPTX)	Barycentric coordinate with respect to the vertex v1 of a surface triangle.
Biharmonic Distance Yaron Lipman, Raif Rustamov, and Thomas Funkhouser *equal contribution ACM Transactions on Graphics, Volume 29, Issue 3 (June 2010). Measuring distances between pairs of points on a 3D surface is a fundamental problem in computer graphics and geometric processing. For most applications, the important properties of a distance are that it is a metric, smooth, locally isotropic, globally "shape-aware", isometry invariant, insensitive to noise and small topology changes, parameter-free, and practical to compute on a discrete mesh. However, the basic methods currently popular in computer graphics (e.g., geodesic and diffusion distances) do not have these basic properties. In this paper, we propose a new distance measure based on the biharmonic differential operator that has all the desired properties. This new surface distance is related to the diffusion and commute-time distances, but applies different (inverse squared) weighting to the eigenvalues of the Laplace-Beltrami operator, which provides a nice trade-off between nearly geodesic distances for small distances and global shape-awareness for large distances. The paper provides theoretical and empirical analysis for a large number of meshes. Paper Code
Robust Volumetric Shape Descriptor Eurographics 3DOR 2010 This paper introduces a volume-based shape descriptor that is robust with respect to changes in pose and topology. We use modified shape distributions in conjunction with the interior distances and barycentroid potential that are based on barycentric coordinates. In our approach, shape distributions are aggregated throughout the entire volume contained within the shape thus capturing information conveyed by the volumes of shapes. Since interior distances and barycentroid potential are practically insensitive to various poses/deformations and to non-pervasive topological changes (addition of small handles), our shape descriptor inherits such insensitivity as well. In addition, if any other modes of information (e.g. electrostatic potential within the protein volume) are available, they can be easily incorporated into the descriptor as additional dimensions in the histograms. Our descriptor has a connection to an existing surface based shape descriptor, the Global Point Signatures (GPS). We use this connection to fairly examine the value of volumetric information for shape retrieval. We find that while, theoretically, strict isometry invariance requires concentrating on the intrinsic surface properties alone, yet, practically, pose insensitive shape retrieval still can be achieved/enhanced using volumetric information. Paper
Interior Distance Using Barycentric Coordinates Raif Rustamov, Yaron Lipman, and Thomas Funkhouser Computer Graphics Forum (Symposium on Geometry Processing), 2009. This paper introduces a framework for deﬁning a shape-aware distance measure between any two points in the interior of a surface mesh. Our framework is based on embedding the surface mesh into a high-dimensional space in a way that best preserves boundary distances between vertices of the mesh, performing a mapping of the mesh volume into this high-dimensional space using barycentric coordinates, and deﬁning the interior distance between any two points simply as their Euclidean distance in the embedding space.We investigate the theoretical properties of the interior distance in relation to properties of the chosen boundary distances and barycentric coordinates, and we investigate empirical properties of the interior distance using diffusion distance as the prescribed boundary distance and mean value coordinates.We prove theoretically that the interior distance is a metric, smooth, interpolating the boundary distances, and reproducing Euclidean distances, and we show empirically that it is insensitive to boundary noise and deformation and quick to compute. In case the barycentric coordinates are non-negative we also show a maximum principle exists. Finally, we use it to deﬁne a new geometric property, barycentroid of shape, and show that it captures the notion of semantic center of the shape. Paper Presentation (PPTX) Code
On Mesh Editing, Manifold Learning, and Diffusion Wavelets IMA Conference on the Mathematics of Surfaces, 2009 We spell out a formal equivalence between the naive Laplacian editing and semi-supervised learning by bi-Laplacian Regularized Least Squares. This allows us to write the solution to Laplacian mesh editing in a “closed” form, based on which we introduce the Generalized Linear Editing (GLE). GLE has both naive Laplacian editing and gradient based editing as special cases. GLE allows using diffusion wavelets for mesh editing. We present preliminary experiments, and shortly discuss connections to segmentation. Paper
Template Based Shape Descriptor Eurographics Workshop on 3D Object Retrieval 2009 We introduce a new 3D shape descriptor which maps the surface features onto an arbitrary template surface using mean-value interpolation. A compact numerical shape descriptor is extracted using manifold harmonics on the template. We show that mean-value interpolation is a strong alternative to the often used projection. The utility of using different templates is established by showing that concatenating descriptors coming from different templates improves retrieval quality. Paper Presentation
Rapid comparison of properties on protein surface Sael L, La D, Li B, Rustamov R, Kihara D. Proteins. Volume 73, Number 1 / October, 2008 The mapping of physicochemical characteristics onto the surface of a protein provides crucial insights into its function and evolution. This information can be further used in the characterization and identification of similarities within protein surface regions. We propose a novel method which quantitatively compares global and local properties on the protein surface. We have tested the method on comparison of electrostatic potentials and hydrophobicity. The method is based on 3D Zernike descriptors, which provides a compact representation of a given property defined on a protein surface. Compactness and rotational invariance of this descriptor enable fast comparison suitable for database searches. The usefulness of this method is exemplified by studying several protein families including globins, thermophilic and mesophilic proteins, and active sites of TIM beta/alpha barrel proteins. In all the cases studied, the descriptor is able to cluster proteins into functionally relevant groups. The proposed approach can also be easily extended to other surface properties. This protein surface-based approach will add a new way of viewing and comparing proteins to conventional methods, which compare proteins in terms of their primary sequence or tertiary structure. Paper
Fast protein tertiary structure retrieval based on global surface shape similarity Sael L, Li B, La D, Fang Y, Ramani K, Rustamov R, Kihara D. Proteins. Volume 72, Number 4 / September, 2008 Characterization and identification of similar tertiary structure of proteins provides rich information for investigating function and evolution. The importance of structure similarity searches is increasing as structure databases continue to expand, partly due to the structural genomics projects. A crucial drawback of conventional protein structure comparison methods, which compare structures by their main-chain orientation or the spatial arrangement of secondary structure, is that a database search is too slow to be done in real-time. Here we introduce a global surface shape representation by three-dimensional (3D) Zernike descriptors, which represent a protein structure compactly as a series expansion of 3D functions. With this simplified representation, the search speed against a few thousand structures takes less than a minute. To investigate the agreement between surface representation defined by 3D Zernike descriptor and conventional main-chain based representation, a benchmark was performed against a protein classification generated by the combinatorial extension algorithm. Despite the different representation, 3D Zernike descriptor retrieved proteins of the same conformation defined by combinatorial extension in 89.6% of the cases within the top five closest structures. The real-time protein structure search by 3D Zernike descriptor will open up new possibility of large-scale global and local protein surface shape comparison. Paper 3D Surfer: Protein search engine
On Manifold Learning and Mesh Editing Poster at SGP 2008 We notice a formal connection between two fields -- manifold learning and mesh editing, and exploit this connection to introduce a generalization of the naive Laplacian mesh editing.
Augmented Planar Reflective Symmetry Transforms The Visual Computer, Volume 24, Number 6/June, 2008 Symmetry has been playing an increasing role in 3D shape processing. Recently introduced planar reflective symmetry transform (PRST) has been found useful for canonical coordinate frame determination, shape matching, retrieval, and segmentation. Guided by the intuition that every imperfect symmetry is imperfect in its own way, we investigate the possibility of incorporating more information into symmetry transforms like PRST. As a step in this direction, the concept of augmented symmetry transform is introduced; we obtain a family of symmetry transforms indexed by a parameter. While the original PRST measures how much the symmetry is broken, the augmented PRST also gives some information about how it is broken. Several approaches to calculating the augmented transform are described. We demonstrate that the augmented transform is beneficial for shape retrieval. Paper
Boundary Element Formulation of Harmonic Coordinates Technical Report, November, 2007 We explain how Boundary Element Methods (BEM) can be used to speed up the computation and reduce the storage associated with Harmonic Coordinates. In addition, BEM formulation allows extending the harmonic coordinates to the exterior and makes possible to compare the transfinite harmonic coordinates with transfinite Shepard interpolation and Mean Value Coordinates. This comparison reveals that there are unifying formulas, yet harmonic coordinates belong to a fundamentally different end of the spectrum. This observation allows us to generalize harmonic coordinates by introducing a novel class of interpolates which we call weakly singular interpolates. Technical Report
Laplace-Beltrami Eigenfunctions for Deformation Invariant Shape Representation SGP 2007 A deformation invariant representation of surfaces, the GPS embedding, is introduced using the eigenvalues and eigenfunctions of the Laplace-Beltrami differential operator. Notably, since the definition of the GPS embedding completely avoids the use of geodesic distances, and is based on objects of global character, the obtained representation is robust to local topology changes. The GPS embedding captures enough information to handle various shape processing tasks as shape classification, segmentation, and correspondence. To demonstrate the practical relevance of the GPS embedding, we introduce a deformation invariant shape descriptor called G2-distributions, and demonstrate their discriminative power, invariance under natural deformations, and robustness. Paper Presentation (PPT)
Augmented Symmetry Transforms SMI 2007 Symmetry has been playing an increasing role in 3D shape processing. Recently introduced Planar Reflective Symmetry Transform(PRST) has been found useful for canonical coordinate frame determination, shape matching, retrieval, and segmentation. Guided by the intuition that every imperfect symmetry is imperfect in its own way, we investigate the possibility of incorporating more information into symmetry transforms like PRST. As a step in this direction, the concept of Augmented Symmetry Transform is introduced; we obtain a family of symmetry transforms indexed by a parameter. While the original PRST measures how much the symmetry is broken, the Augmented PRST also gives some information about how it is broken. Several approaches to calculating the augmented transform are described. We demonstrate that the augmented transform is useful for shape retrieval. Paper Presentation (PPT)
Work in Topology My PhD work concentrated on low-dimensional topology, specifically, Heegaard Floer homology and its interplay with singularity theory and symplectic geometry. The Renormalized Euler Characteristic and L-space Surgeries. On Plumbed L-spaces. Surgery formula for the renormalized Euler characteristic of Heegaard Floer homology. On Heegaard Floer homology of plumbed three-manifolds with b1 = 1. Calculation of Heegaard Floer homology for a class of Brieskorn spheres.