Correspondences and Symmetry in 3D Scenes

Michael Wand

Correspondences and Symmetry in 3D Scenes

Correspondence problems and shape understanding

An important challenge in modern computer science is the understanding of structures in data. Humans have remarkable capabilities in understanding structures in the world from their sensory input. Obviously, computers are not able to perform tasks at even a vaguely comparable level of cognitive skill. Nevertheless, machine processing of data has significant advantages: Computers can work themselves through enormous quantities of data at minimal costs. Not only do they unburden the human of tedious tasks but could potentially detect patterns in data that are only visible in large data bases.

Our research area deals with the machine understanding of shapes. Our goal is to enable a computer algorithm to understand to a certain extent how geometric shapes are structured. In the last few years, we have mostly worked on an important low-level problem in the domain of shape understanding: establishing correspondences. The goal is to determine whether two shapes are essentially the same, and if so, which points are corresponding, i.e., matching equivalent geometry. We have addressed two aspects of this problem. The first is the primary problem of actually establishing correspondences. The second problem is the higher-level problem of using correspondences among data to analyze the structure of the shapes.

Figure 1: Decomposition of a 3D Model into elementary building blocks. The color indicates matching types.

Correspondence problems and symmetry

There are a large number of correspondence problems: The first aspect is how correspondences are established. The simplest option is to match geometry only under rigid motions, i.e., rotations, mirroring, and translations [Figure 1] . However, more complex models are possible; for example, shapes can undergo deformations [Figure 2] , or we might seek to establish correspondences according to semantic categories, learned from a small set of training examples provided by the user [Figure 3] using machine learning algorithms.

Figure 2: Correspondences between two 3D scans of a person in different poses (computed automatically).

Furthermore, not only is it possible to establish correspondences between pairs of separate shapes [Figure 2] , but we can also look for reoccurring building blocks within one and the same object [Figure 1] . This process is called partial symmetry detection.

Figure 3: Correspondence between semantically related parts of a building. The matching model is learned from a few user examples. Dataset: LKVK Saarland.

Applications

Correspondence information has a number of obvious applications; for example, we can fully automatically register multiple scans of a building (rigid matching) or of a scanned person (deformable matching), or automatically perform semantic tagging, for example, in large scale 3D scans of cities. However, interesting and non-obvious applications arise when we study the structure of the correspondences. By analyzing the structure of the partial symmetries of an object, we can find building blocks, out of which we can fully- or semi-automatically assemble variants of the shape [Figure 4] . An analysis can also reveal structural regularity such as arrangements of windows in regular grids [Figure 1] . This regularity can be used as an invariant for shape editing, thereby allowing a quick creation of plausible variations of the original shape. Such automated editing tools are useful, for example, for reducing the costs of content creation in computer games.

Figure 4: Building blocks (as in Figure 1) can be reassembled automatically to create plausible shape variations from a single example.