Nicolas Mellado Publications

MCGraph: Multi-criterion representation for scene understanding

The field of scene understanding endeavours to extract a broad range of information from 3D scenes. Current approaches exploit one or at most a few different criteria (e.g., spatial, semantic, functional information) simultaneously for analysis. We argue that to take scene understanding to the next level of performance, we need to take into account many different, and possibly previously unconsidered types of knowledge simultaneously. A unified representation for this type of processing is as of yet missing. In this work we propose MCGraph: a unified multi-criterion data representation for understanding and processing of large-scale 3D scenes. Scene abstraction and prior knowledge are kept separated, but highly connected. For this purpose, primitives (i.e., proxies) and their relationships (e.g., contact, support, hierarchical) are stored in an abstraction graph, while the different categories of prior knowledge necessary for processing are stored separately in a knowledge graph. These graphs complement each other bidirectionally, and are processed concurrently. We illustrate our approach by expressing previous techniques using our formulation, and present promising avenues of research opened up by using such a representation. We also distribute a set of MCGraph annotations for a small number of NYU2 scenes, to be used as ground truth multi-criterion abstractions.

Adaptive multi-scale analysis for point-based surface editing

This paper presents a tool that enables the direct editing of surface features in large point-clouds or meshes. This is made possible by a novel multi-scale analysis of unstructured point-clouds that automatically extracts the number of relevant features together with their respective scale all over the surface. Then, combining this ingredient with an adequate multi-scale decomposition allows us to directly enhance or reduce each feature in an independent manner. Our feature extraction is based on the analysis of the scale-variations of locally fitted surface primitives combined with unsupervised learning techniques. Our tool may be applied either globally or locally, and millions of points are handled in real-time. The resulting system enables users to accurately edit complex geometries with minimal interaction

Computational Design and Construction of Notch-free Reciprocal Frame Structures

A reciprocal frame (RF) is a self-standing 3D structure typically formed by a complex grillage created as an assembly of simple atomic RF-units, which are in turn made up of three or more sloping rods forming individual units. While RF-structures are attractive given their simplicity, beauty, and ease of deployment; creating such structures, however, is difficult and cumbersome. In this work, we present an interactive computational framework for designing and assembling RF-structures around a 3D reference surface. Targeting notch-free assemblies, wherein individual rods or sticks are simply tied together, we focus on simplifying both the process of exploring the space of aesthetic designs and also the actual assembly process. By providing computational support to simplify the design and assembly process, our tool enables novice users to interactivity explore a range of design variations, and assists them to construct the final RF-structure design. We use the proposed framework to design a range of RF-structures of varying complexity and also physically construct a selection of the models.

Super 4PCS: Fast Global Pointcloud Registration via Smart Indexing

Data acquisition in large-scale scenes regularly involves accumulating information across multiple scans. A common approach is to locally align scan pairs using Iterative Closest Point (ICP) algorithm (or its variants), but requires static scenes and small motion between scan pairs. This prevents accumulating data across multiple scan sessions and/or different acquisition modalities (e.g., stereo, depth scans). Alternatively, one can use a global registration algorithm allowing scans to be in arbitrary initial poses. The state-of-the-art global registration algorithm, 4PCS, however has a quadratic time complexity in the number of data points. This vastly limits its applicability to acquisition of large environments. We present Super 4PCS for global pointcloud registration that is optimal, i.e., runs in linear time (in the number of data points) and is also output sensitive in the complexity of the alignment problem based on the (unknown) overlap across scan pairs. Technically, we map the algorithm as an ‘instance problem’ and solve it efficiently using a smart indexing data organization. The algorithm is simple, memory-efficient, and fast. We demonstrate that Super 4PCS results in significant speedup over alternative approaches and allows unstructured efficient acquisition of scenes at scales previously not possible. Complete source code and datasets are available for research use at http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/.

The Revealing Flashlight: Interactive spatial augmented reality for detail exploration of cultural heritage artifacts

Cultural heritage artifacts often contain details that are difficult to distinguish due to aging effects such as erosion. We propose the revealing flashlight, a new interaction and visualization technique in spatial augmented reality that helps to reveal the detail of such artifacts. We locally and interactively augment a physical artifact by projecting an expressive 3D visualization that highlights its features, based on an analysis of its previously acquired geometry at multiple scales. Our novel interaction technique simulates and improves the behavior of a flashlight: according to 6-degree-of-freedom input, we adjust the numerous parameters involved in the expressive visualization - in addition to specifying the location to be augmented. This makes advanced 3D analysis accessible to the greater public with an everyday gesture, by naturally combining the inspection of the real object and the virtual object in a co-located interaction and visualization space.

The revealing flashlight can be used by archeologists, for example, to help decipher inscriptions in eroded stones, or by museums to let visitors interactively discover the geometric details and meta-information of cultural artifacts. We confirm its effectiveness, ease-of-use and ease-of-learning in an initial preliminary user study and by the feedbacks of two public exhibitions.

La Lampe torche magique : Une interface tangible pour l’inspection geometrique d’objets en realite augmentee spatiale

La Réalité Augmentée Spatiale (RAS) permet d'enrichir des objets du monde réel par apposition d'informations numériques à l'aide de vidéo-projecteurs. Elle présente un fort potentiel pour introduire de nouvelles techniques d'interaction, car la co-localisation de l'espace de rendu et de l'espace d'interaction dans le monde réel permet de se baser sur nos habitudes spontanées, comme l'interaction directe avec les mains. Nous proposons la Lampe torche magique, une nouvelle interaction à six degrés de libertés destinée à améliorer l'analyse visuelle d'un objet réel grâce à l'apposition sélective d'informations numériques par le biais de la RAS. Cette interaction fait référence à une triple métaphore de lampe torche : la zone à inspecter déterminée par le spot lumineux, l'angle d'inspection caractérisé par la direction de la lampe torche, et l'intensité de la visualisation déterminée par la distance entre la lampe torche et l'objet "éclairé". Grâce à une numérisation 3D préalable de l'objet et une analyse géométrique multi-échelle de sa surface, nous augmentons l'objet réel avec une visualisation expressive qui met en évidence les détails de l'objet, tels que les courbures, à différentes échelles et selon différents angles. Une première étude utilisateur exploratoire montre que sur une stèle égyptienne comportant une inscription peu visible à l'oeil nu, notre technique permet d'améliorer la lisibilité sans perdre le lien entre l'objet réel et les informations abstraites.

Analysis of 3D objects at multiple scales: application to shape matching

Over the last decades, the evolution of acquisition techniques yields the generalization of detailed 3D objects, represented as huge point sets composed of millions of vertices. The complexity of the involved data often requires to analyze them for the extraction and characterization of pertinent structures, which are potentially defined at multiple scales. Among the wide variety of methods proposed to analyze digital signals, the scale-space analysis is today a standard for the study of 2D curves and images. However, its adaptation to 3D data leads to instabilities and requires connectivity information, which is not directly available when dealing with point sets.

In this thesis, we present a new multi-scale analysis framework that we call the Growing Least Squares (GLS). It consists of a robust local geometric descriptor that can be evaluated on point sets at multiple scales using an efficient second-order fitting procedure. We propose to analytically differentiate this descriptor to extract continuously the pertinent structures in scale-space. We show that this representation and the associated toolbox define an efficient way to analyze 3D objects represented as point sets at multiple scales. To this end, we demonstrate its relevance in various application scenarios.

A challenging application is the analysis of acquired 3D objects coming from the Cultural Heritage field. In this thesis, we study a real-world dataset composed of the fragments of the statues that were surrounding the legendary Alexandria Lighthouse. In particular, we focus on the problem of fractured object reassembly, consisting of few fragments (up to about ten), but with missing parts due to erosion or deterioration. We propose a semi-automatic formalism to combine both the archaeologist’s knowledge and the accuracy of geometric matching algorithms during the reassembly process. We use it to design two systems, and we show their efficiency in concrete cases.

Growing Least Squares for the Continuous Analysis of Manifolds in Scale-Space

We present a novel approach to the multi-scale analysis of point-sampled manifolds of co-dimension 1. It is based on a variant of Moving Least Squares, whereby the evolution of a geometric descriptor at increasing scales is used to locate pertinent locations in scale-space, hence the name “Growing Least Squares”. Compared to existing scale-space analysis methods, our approach is the first to provide a continuous solution in space and scale dimensions, without requiring any parametrization, connectivity or uniform sampling. An important implication is that we identify multiple pertinent scales for any point on a manifold, a property that had not yet been demonstrated in the literature. In practice, our approach exhibits an improved robustness to change of input, and is easily implemented in a parallel fashion on the GPU. We compare our method to state-of-the-art scale-space analysis techniques and illustrate its practical relevance in a few application scenarios

Semi-automatic geometry-driven reassembly of fractured archeological objects

3D laser scanning of broken cultural heritage content is becoming increasingly popular, resulting in large collections of detailed fractured archeological 3D objects that have to be reassembled virtually. In this paper, we present a new semi-automatic reassembly approach for pairwise matching of the fragments, that makes it possible to take into account both the archeologist's expertise, as well as the power of automatic geometry-driven matching algorithms. Our semi-automatic reassembly approach is based on a real-time interaction loop: an expert user steadily specifies approximate initial relative positions and orientations between two fragments by means of a bimanual tangible user interface. These initial poses are continuously corrected and validated in real-time by an algorithm based on the Iterative Closest Point (ICP): the potential contact surface of the two fragments is identified by efficiently pruning insignificant areas of a pair of two bounding sphere hierarchies, that is combined with a k-d tree for closest vertex queries. The locally optimal relative pose for the best match is robustly estimated by taking into account the distance of the closest vertices as well as their normals. We provide feedback to the user by a visual representation of the locally optimal best match and its associated error. Our first results on a concrete dataset show that our system is capable of assisting an expert user in real-time during the pairwise matching of downsampled 3D fragments.