# Leonidas J. Guibas - LJK

## Contact Details

NameLeonidas J. Guibas |
||

AffiliationLJK |
||

Location |
||

## Pubs By Year |
||

## External Links |
||

## Pub CategoriesComputer Science - Computer Vision and Pattern Recognition (16) Computer Science - Computational Geometry (7) Computer Science - Graphics (5) Computer Science - Learning (5) Statistics - Machine Learning (3) Computer Science - Artificial Intelligence (3) Mathematics - Information Theory (2) Computer Science - Information Theory (2) Mathematics - Optimization and Control (2) Physics - Physics and Society (1) Mathematics - Geometric Topology (1) Computer Science - Discrete Mathematics (1) Computer Science - Neural and Evolutionary Computing (1) Computer Science - Other (1) Computer Science - Data Structures and Algorithms (1) Computer Science - Robotics (1) Computer Science - Computers and Society (1) Computer Science - Software Engineering (1) Mathematics - Metric Geometry (1) |

## Publications Authored By Leonidas J. Guibas

We introduce a novel neural network architecture for encoding and synthesis of 3D shapes, particularly their structures. Our key insight is that 3D shapes are effectively characterized by their hierarchical organization of parts, which reflects fundamental intra-shape relationships such as adjacency and symmetry. We develop a recursive neural net (RvNN) based autoencoder to map a flat, unlabeled, arbitrary part layout to a compact code. Read More

We propose a method for converting geometric shapes into hierarchically segmented parts with part labels. Our key idea is to train category-specific models from the scene graphs and part names that accompany 3D shapes in public repositories. These freely-available annotations represent an enormous, untapped source of information on geometry. Read More

Important high-level vision tasks such as human-object interaction, image captioning and robotic manipulation require rich semantic descriptions of objects at part level. Based upon previous work on part localization, in this paper, we address the problem of inferring rich semantics imparted by an object part in still images. We propose to tokenize the semantic space as a discrete set of part states. Read More

Point cloud is an important type of geometric data structure. Due to its irregular format, most researchers transform such data to regular 3D voxel grids or collections of images. This, however, renders data unnecessarily voluminous and causes issues. Read More

Generation of 3D data by deep neural network has been attracting increasing attention in the research community. The majority of extant works resort to regular representations such as volumetric grids or collection of images; however, these representations obscure the natural invariance of 3D shapes under geometric transformations and also suffer from a number of other issues. In this paper we address the problem of 3D reconstruction from a single image, generating a straight-forward form of output -- point cloud coordinates. Read More

In this paper, we study the problem of semantic annotation on 3D models that are represented as shape graphs. A functional view is taken to represent localized information on graphs, so that annotations such as part segment or keypoint are nothing but 0-1 indicator vertex functions. Compared with images that are 2D grids, shape graphs are irregular and non-isomorphic data structures. Read More

We present a learning framework for abstracting complex shapes by learning to assemble objects using 3D volumetric primitives. In addition to generating simple and geometrically interpretable explanations of 3D objects, our framework also allows us to automatically discover and exploit consistent structure in the data. We demonstrate that using our method allows predicting shape representations which can be leveraged for obtaining a consistent parsing across the instances of a shape collection and constructing an interpretable shape similarity measure. Read More

In this paper we propose an optimization-based framework to multiple graph matching. The framework takes as input maps computed between pairs of graphs, and outputs maps that 1) are consistent among all pairs of graphs, and 2) preserve edge connectivity between pairs of graphs. We show how to formulate this as solving a piece-wise low-rank matrix recovery problem using a generalized message passing scheme. Read More

Interactions play a key role in understanding objects and scenes, for both virtual and real world agents. We introduce a new general representation for proximal interactions among physical objects that is agnostic to the type of objects or interaction involved. The representation is based on tracking particles on one of the participating objects and then observing them with sensors appropriately placed in the interaction volume or on the interaction surfaces. Read More

Building discriminative representations for 3D data has been an important task in computer graphics and computer vision research. Convolutional Neural Networks (CNNs) have shown to operate on 2D images with great success for a variety of tasks. Lifting convolution operators to 3D (3DCNNs) seems like a plausible and promising next step. Read More

3D shape models are becoming widely available and easier to capture, making available 3D information crucial for progress in object classification. Current state-of-the-art methods rely on CNNs to address this problem. Recently, we witness two types of CNNs being developed: CNNs based upon volumetric representations versus CNNs based upon multi-view representations. Read More

Optimal transportation distances are valuable for comparing and analyzing probability distributions, but larger-scale computational techniques for the theoretically favorable quadratic case are limited to smooth domains or regularized approximations. Motivated by fluid flow-based transportation on $\mathbb{R}^n$, however, this paper introduces an alternative definition of optimal transportation between distributions over graph vertices. This new distance still satisfies the triangle inequality but has better scaling and a connection to continuous theories of transportation. Read More

We present ShapeNet: a richly-annotated, large-scale repository of shapes represented by 3D CAD models of objects. ShapeNet contains 3D models from a multitude of semantic categories and organizes them under the WordNet taxonomy. It is a collection of datasets providing many semantic annotations for each 3D model such as consistent rigid alignments, parts and bilateral symmetry planes, physical sizes, keywords, as well as other planned annotations. Read More

Knowledge tracing---where a machine models the knowledge of a student as they interact with coursework---is a well established problem in computer supported education. Though effectively modeling student knowledge would have high educational impact, the task has many inherent challenges. In this paper we explore the utility of using Recurrent Neural Networks (RNNs) to model student learning. Read More

Providing feedback, both assessing final work and giving hints to stuck students, is difficult for open-ended assignments in massive online classes which can range from thousands to millions of students. We introduce a neural network method to encode programs as a linear mapping from an embedded precondition space to an embedded postcondition space and propose an algorithm for feedback at scale using these linear maps as features. We apply our algorithm to assessments from the Code. Read More

Object viewpoint estimation from 2D images is an essential task in computer vision. However, two issues hinder its progress: scarcity of training data with viewpoint annotations, and a lack of powerful features. Inspired by the growing availability of 3D models, we propose a framework to address both issues by combining render-based image synthesis and CNNs. Read More

Let $P$ be a set of $n$ points in $\mathrm{R}^2$, and let $\mathrm{DT}(P)$ denote its Euclidean Delaunay triangulation. We introduce the notion of an edge of $\mathrm{DT}(P)$ being {\it stable}. Defined in terms of a parameter $\alpha>0$, a Delaunay edge $pq$ is called $\alpha$-stable, if the (equal) angles at which $p$ and $q$ see the corresponding Voronoi edge $e_{pq}$ are at least $\alpha$. Read More

Comparing two images in a view-invariant way has been a challenging problem in computer vision for a long time, as visual features are not stable under large view point changes. In this paper, given a single input image of an object, we synthesize new features for other views of the same object. To accomplish this, we introduce an aligned set of 3D models in the same class as the input object image. Read More

Maximum a posteriori (MAP) inference over discrete Markov random fields is a fundamental task spanning a wide spectrum of real-world applications, which is known to be NP-hard for general graphs. In this paper, we propose a novel semidefinite relaxation formulation (referred to as SDR) to estimate the MAP assignment. Algorithmically, we develop an accelerated variant of the alternating direction method of multipliers (referred to as SDPAD-LR) that can effectively exploit the special structure of the new relaxation. Read More

Joint matching over a collection of objects aims at aggregating information from a large collection of similar instances (e.g. images, graphs, shapes) to improve maps between pairs of them. Read More

In this paper, we consider the weighted graph matching problem. Recently, approaches to this problem based on spectral methods have gained significant attention. We propose two graph spectral descriptors based on the graph Laplacian, namely a Laplacian family signature (LFS) on nodes, and a pairwise heat kernel distance on edges. Read More

Modern data acquisition routinely produces massive amounts of network data. Though many methods and models have been proposed to analyze such data, the research of network data is largely disconnected with the classical theory of statistical learning and signal processing. In this paper, we present a new framework for modeling network data, which connects two seemingly different areas: network data analysis and compressed sensing. Read More

We consider the problem of maintaining the Euclidean Delaunay triangulation $\DT$ of a set $P$ of $n$ moving points in the plane, along algebraic trajectories of constant description complexity. Since the best known upper bound on the number of topological changes in the full $\DT$ is nearly cubic, we seek to maintain a suitable portion of it that is less volatile yet retains many useful properties. We introduce the notion of a stable Delaunay graph, which is a dynamic subgraph of the Delaunay triangulation. Read More

**Affiliations:**

^{1}LJK,

^{2}LJK,

^{3}LBNL

Distance function to a compact set plays a central role in several areas of computational geometry. Methods that rely on it are robust to the perturbations of the data by the Hausdorff noise, but fail in the presence of outliers. The recently introduced distance to a measure offers a solution by extending the distance function framework to reasoning about the geometry of probability measures, while maintaining theoretical guarantees about the quality of the inferred information. Read More

**Authors:**Marshall Bern, David Eppstein, Pankaj K. Agarwal, Nina Amenta, Paul Chew, Tamal Dey, David P. Dobkin, Herbert Edelsbrunner, Cindy Grimm, Leonidas J. Guibas, John Harer, Joel Hass, Andrew Hicks, Carroll K. Johnson, Gilad Lerman, David Letscher, Paul Plassmann, Eric Sedgwick, Jack Snoeyink, Jeff Weeks, Chee Yap, Denis Zorin

Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both computation and topology. Read More

We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during their motion. For two convex polygons in the plane, let $D$ be the maximum diameter of the polygons, and let $s$ be the minimum distance between them during their motion. Our separation certificate changes $O(\log(D/s))$ times when the relative motion of the two polygons is a translation along a straight line or convex curve, $O(\sqrt{D/s})$ for translation along an algebraic trajectory, and $O(D/s)$ for algebraic rigid motion (translation and rotation). Read More