PI: Justin Solomon, Department of Electrical Engineering & Computer Science, MIT
Abstract
Computer graphics and vision software relies on algorithms for shape analysis to create links between objects observed using sensing equipment and preprocessed databases of annotated 3D objects. While we typically can only observe the outer surface of an object in front of a camera, in reality that surface bounds a volume whose structure determines the purpose and affordances of the object. This project will develop tools for efficient volume-based shape analysis. To overcome inefficiencies of existing tools, our algorithms will leverage a mathematical technique known as the boundary element method (BEM) to derive conclusions about the volume bounded by a surface without an expensive process of filling it with tetrahedra or other volumetric elements. This project will be carried out by Prof. Justin Solomon with a student and a postdoctoral researcher at MIT as well as with potential collaborators at Skoltech.
Report
- Project Title: Boundary Element Methods for Shape Analysis
- Principal Investigator: Justin Solomon, MIT Department of Electrical Engineering and Computer Science, MIT Geometric Data Processing Group
- Grant Period: February 2017 – January 2018
This project for the MIT-Skoltech Seed Fund Program involves the development of mathematical models and algorithms for volumetric shape analysis. Most three-dimensional shapes are stored computationally using boundary representations, that is, as thin shell surfaces that bound a volume of interest. While this representation is efficient storage-wise since it stores two- rather than three-dimensional data, it captures a different type of shape: A thin sheet surrounding an object of interest rather than the object itself. Hence, algorithms in computer vision and graphics that analyze these representations often miss key extrinsic features relevant to a shape analysis task.
To address this gap between computation and physical reality, we propose using the boundary element method (BEM). BEM is a numerical algorithm for solving partial differential equations (PDEs) in a volume using calculations only on its boundary. The basic premise of our research is that the operators involved in BEM not only define an effective means of solving PDEs but also themselves encode information about the volume enclosed by a surface.
To explore this idea, we focused on a basic operator appearing in the BEM literature, the Dirichlet-to-Neumann operator for the Laplace equation. After interfacing with state-of-the-art BEM tools for approximating this operator, we carried out a theoretical and experimental study of this operator, validating its usefulness in 3D computer vision applications as well as its stability to typical sources of error present in this context. We additionally implemented some full application-oriented computational pipelines for shape analysis to demonstrate real-world usefulness of the resulting algorithms.
Our research project was extremely successful and has led to published papers, interest among the broader scientific community, and a broader collaboration with Skoltech. We outline some of the main outcomes of the project below.
Research Products
The generous support of the Skoltech seed grant is acknowledged in several publications that resulted from the one-year study:
Wang, Yu, Mirela Ben-Chen, Iosif Polterovich, and Justin Solomon. “Steklov Geometry Processing: An Extrinsic Approach to Spectral Shape Analysis.” ACM Transactions on Graphics, accepted pending revision.
This paper is a direct product of the proposed research in which we demonstrate the value of the Dirichlet-to-Neumann (Steklov) operator for key shape analysis tasks in computer graphics and vision.Supported by a collaboration with mathematician Iosif Polterovich, we were able to prove theoretically that BEM operators address drawbacks of operators applied in previous geometry processing techniques based on spectral computation, namely that it can distinguish between different isometric embeddings of the same shape.Beyond theoretical progress, the paper reports state-of-the-art performance for problems including shape retrieval and statistical analysis.At the end of the day, the paper shows that the Dirichlet-to-Neumann operator can serve as a drop-in replacement for the Laplace operator in countless geometry processing pipelines.
Claici, Sebastian, Mikhail Bessmeltsev, Scott Schaefer, and Justin Solomon. “Isometry-Aware Preconditioning for Mesh Parameterization.” Symposium on Geometry Processing 2017, London.
This paper proposes an algorithm for large-scale optimization of nonconvex objectives typically appearing in geometry processing applications.In particular, we view the set of deformations of a fixed-topology triangulated surface or tetrahedralized volume as itself a high-dimensional manifold.By defining a rigid-invariant Riemannian metric on this space, we show that simple gradient descent algorithms can be accelerated by several orders of magnitude, bypassing the need for complex optimization procedures.This technique currently applies state-of-the-art performance on challenging surface parameterization tasks.
Ezuz, Danielle, Justin Solomon, Vladimir Kim, and Mirela Ben-Chen. “GWCNN: A Metric Alignment Layer for Deep Shape Analysis.” Symposium on Geometry Processing 2017, London.
This paper provides a technique for machine learning on meshed geometry, building on algorithms for surface-to-surface correspondence proposed by Prof. Solomon in previous work.The idea is to learn a mapping from 3D geometry into a two-dimensional grid on which deep learning algorithms can carry out analysis for problems like classification and segmentation.The proposed technique is among the first end-to-end trainable machine learning pipelines for triangle meshes and related data.
Bessmeltsev, Mikhail and Justin Solomon. “Vectorization of Line Drawings via PolyVector Fields.” ACM Transactions on Graphics, submitted.
This paper explores an application of geometry processing ideas to a key problem in image processing:vectorization of line drawings.The algorithm proposed in this paper takes as input a sketched, hand-drawn image in bitmapped format and outputs a set of vectorized curves suitable for use in software like Adobe Illustrator.Behind the scenes, vectorization is guided by polyvector fields, a new representation of frames recently proposed in the geometry processing literature for quadrilateral meshing.Although this algorithm is not currently guided by machine learning techniques, we have begun a research project supported by the Skoltech Next Generation grant jointly with Prof. Evgeny Burnaev exploring how learning techniques can enhance algorithms in this class.
Educational and Career Development Outcomes
Most of the research supported by this seed grant has been carried out by MIT students and postdoctoral researchers. As members of the newly-formed Geometric Data Processing Group, these researchers’ work has formed the basis for future directions in the research group and is a significant portion of their portfolios for the PhD and academic job search.
As a few examples involving staff funded using this grant:
- PhD student Sebastian Claici has completed his RQE exam by presenting his SGP 2017 paper mentioned above; this is his final PhD requirement beyond thesis research.
- PhD student Yu Wang currently is wrapping up his MSc degree by presenting his research on Steklov geometry processing using boundary element operators.
- Postdoctoral research associate Dr. Mikhail Bessmeltsev is currently on the market for full-time academic positions and has received interviews at top-tier research institutions and universities.
Collaboration with Skoltech
A key secondary goal of the research in this proposal is to establish a research connection between the MIT Geometric Data Processing Group and colleagues at Skoltech. We are pleased to report the foundation of a longer-term collaboration between these two groups that will last beyond the term of the seed grant.
Approximately midway through the period of MIT-Skoltech Seed Grant support, postdoc Mikhail Bessmeltsev visited Skoltech in person and presented his research at MIT as well as his prior work as a PhD student at the University of British Columbia. The group also hosted a visit from Skoltech faculty member Evgeny Burnaev at MIT.
Based on discussions during these visits as well as at intermediate points over teleconference and inspired by the research on boundary element methods, the two parties proposed a longer-term collaboration studying machine learning techniques applied to curve network data and other expressions of three-dimensional shape. We are pleased to have received the Skoltech Next Generation grant to support his research. Geometric Data Processing Group members are currently completing preliminary stages of this new project, guided by feedback from both Prof. Solomon and Prof. Burnaev; already one submission for publication on machine learning for point cloud data has resulted from these discussions. The group plans to share an implementation of the proposed technique in a Skoltech-hosted repository in the coming weeks.