1
Introduction
1.1 Motivation
Shape analysis is an old topic that has been studied, for many centuries, by scientists from different boards, including philosophers, psychologists, mathematicians, biologists, and artists. However, in the past two decades, we have seen a renewed interest in the field motivated by the recent advances in 3D acquisition, modeling, and visualization technologies, and the substantial increase in the computation and storage power. Nowadays, 3D scanning devices are accessible not only to domain-specific experts but also to the general public. Users can scan the real world at high resolution, using devices that are as cheap as video cameras, edit the 3D data using 3D modeling software, share them across the web, and host them in online repositories that are growing in size and in number. Such repositories can include millions of every day objects, cultural heritage artifacts, buildings, as well as medical, scientific, and engineering models.
The increase in the availability of 3D data comes with new challenges in terms of storage, classification, and retrieval of such data. It also brings unprecedented opportunities for solving long-standing problems; First, the rich variability of 3D content in existing shape repositories makes it possible to directly reuse existing 3D models, in whole or in part, to construct new 3D models with rich variations. In many situations, 3D designers and content creators will no more need to scan or model a 3D object or scene from scratch. They can query existing repositories, retrieve the desired models, and fine-tune their geometry and appearance to suit their needs. This concept of context reuse is not specific to 3D models but has been naturally borrowed from other types of media. For instance, one can translate sentences to different languages by performing cross-language search. Similarly, one can create an image composite or a visual art piece by querying images, copying parts of them and pasting them into their own work.
Second, these large amounts of 3D data can be used to learn computational models that effectively reason about properties and relationships of shapes without relying on hard-coded rules or explicitly programmed instructions. For instance, they can be used to learn 3D shape variation in medical data in order to model physiological abnormalities in anatomical organs, model their natural growth, and learn how shape is affected by disease progression. They can be also used to model 3D shape variability using statistical models, which, in turn, can be used to facilitate 3D model creation with minimum user interaction.
Finally, data-driven methods facilitate high-level shape understanding by discovering geometric and structural patterns among collections of shapes. These patterns can serve as strong priors not only in various geometry processing applications but also in solving long-standing computer vision problems, ranging from low-level 3D reconstruction to high-level scene understanding.
These technological developments and the opportunities they bring have motivated researchers to take a fresh look at the 3D shape analysis problem. Although most of the recent developments are application-driven, many of them aim to answer fundamental, sometimes philosophical, questions such as: What is shape? Can we mathematically formulate the concept of shape? How to compare the shape of objects? How to quantify and localize shape similarities and differences? This book synthesizes the critical mass of 3D shape analysis research that has accumulated over the past 15 years. This rapidly developing field is both profound and broad, with a wide range of applications and many open research questions that are yet to be answered.
1.2 The 3D Shape Analysis Problem
Shape is the external form, outline or surface, of someone or something as opposed to other properties such as color, texture, or material composition.
Source: Wikipedia and Oxford dictionaries.
Humans can easily abstract the form of an object, describe it with a few geometrical attributes or even with words, relate it to the form of another object, and group together, in multiple ways and using various criteria, different objects to form clusters that share some common shape properties. Shape analysis is the general term used to refer to the process of automating these tasks, which are trivial to humans but very challenging to computers. It has been investigated under the umbrella of many applications and has multiple facets. Below, we briefly summarize a few of them.
- 3D shape retrieval, clustering, and classification. Similar to other types of multimedia information, e.g. text documents, images, and videos, the demand for efficient clustering and classification tools that can organize, automatically or semi-automatically, the continuously expanding collections of 3D models is growing. Likewise, users, whether they are experts, e.g. graphics designers who are increasingly relying on the reuse of existing 3D contents, or novice, will benefit from a search engine that will enable them to search for 3D data of interest in the same way they search for text documents or images.
- Correspondence and registration. This problem, which can be summarized as the ability to say which part of an object matches which part on another object, and the ability to align one object onto another, arises in many domains of computer vision, computer graphics, and medical imaging. Probably, one of the most popular examples is the 3D reconstruction problem where usually a 3D object is scanned by multiple sensors positioned at different locations around the object. To build the complete 3D model of the object, one needs to merge the partial scans produced by each sensor. This operation requires a correct alignment, i.e. registration, step that brings all the acquired 3D data into a common coordinate frame. Note also that, in many cases, 3D objects move and deform, in a nonrigid way, during the scanning process. This makes the alignment process even more complex. Another example is in computer graphics where a 3D designer creates a triangulated 3D mesh model, hereinafter referred to as the reference, and assigns to each of its triangular faces some attributes, e.g. color and material properties. The designer then can create additional models with the same attributes but instead of manually setting them, they can be automatically transferred from the reference model if there is a mechanism which finds for each point on the reference model its corresponding points on the other models.
- Detection and recognition. This includes the detection of low level features such as corners or regions of high curvatures, as well as the localization and recognition of parts in 3D objects, or objects in 3D scenes. The latter became very popular in the past few years with the availability of cheap 3D scanning devices. In fact, instead of trying to localize and recognize objects in a scene from 2D images, one can develop algorithms that operate on the 3D scans of the scene, eventually acquired using commodity devices. This has the advantage that 3D data are less affected than 2D images by the occlusions and ambiguities, which are inherent to the loss of dimensionality when projecting the 3D world onto 2D images. 3D face and 3D action recognition are, among others, examples of applications that have benefited from the recent advances in 3D technologies.
- Measurement and characterization of the geometrical and topological properties of objects on one hand and of the spatial relations between objects on the other hand. This includes the identification of similar regions and finding recurrent patterns within and across 3D objects.
- Summarization and exploration of collections of 3D models. Given a set of objects, one would like to compute a representative 3D model, e.g. the average or median shape, as well as other summary statistics such as covariances and modes of variation of their shapes. One would like also to characterize the collection using probability distributions and sample from these distributions new instances of shapes to enrich the collection. In other words, one needs to manipulate 3D models in the same way one manipulates numbers.
Implementing these representative analysis tasks requires solving a set of challenges, and each has been the subject of important research and contributions. The first challenge is the mathematical representation of the shape of objects. 3D models, acquired with laser scanners or created using some modeling software, can be represented with point clouds, polygonal soup models, or as volumetric images. Such representations are suitable for storage and visualization but not for high-level analysis tasks. For instance, scanning the same object from two different viewpoints or using different devices will often result in two different point clouds but the shape remains the same. The challenge is in designing mathematical representations that capture the essence of shape. A good representation should be independent of (or invariant to) the pose of the 3D object, the way it is scanned or modeled, and the way it is stored. It is also important to ensure that two different shapes cannot have the same representation.
Figure 1.1Complexity of the shape similarity problem. (a) Nonrigid deformations. (b) Partial similarity. (c) Semantic similarity.
Second, almost every shape analysis task requires a measure that quantifies shape similarities and differences....
