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.

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.

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.

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 07

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  Project Page  GPS Based Search Engine

Augmented Symmetry Transforms

SMI 07

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

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.