Completing Missing Regions using Symmetries

Thiago Pereira e Renato Paes Leme

{tpereira, paesleme}@impa.br

Introduction

Symmetries are a very important aspect of many natural and human-made objects. They are common in many fields like arts, architecture, mathematics and design. A shape is symmetric if there is a transformation that maps the shape onto itself. In this work, we restrict our attention to reflective symmetries. Most symmetries that are found are not perfect. Also, some symmetries only hold in a subset of the object. These are called partial symmetries. This motivates research for algorithms that identify partial and approximate symmetries. We have implemented a symmetry detection scheme largely based on the work of Mitra et al. [1]. We develop an application of symmetry detection: completion of missing regions in objects.

Overview

A partial symmetry is a relation between two subsets S1, S2 of an object, such that an axis reflection exists that maps S1 onto S2 . This reflection defines a correspondence between points in both sets. This can also be seen in the inverse direction, a correspondence between a pair of points defines a reflection axis. For each pair of points, we build the transformation that maps one in the other. Not all points can be matched though, differential properties of the shape must also be invariant under the reflection. This means, for example, that one points normal must me mapped onto the other point's normal. This also holds for curvature. These local properties are calculated for each point in a pre-processing step and used to prune the search for point pairs.


[ Mitra et al. 2006 ]


All the identified symmetries only hold in a local neighbourhood. For a symmetry to hold for a large region (patch) of the object, many point pairs must agree on that reflection. This process can be regarded as if pairs are voting for a certain symmetry. How do we count this votes then? In a way similar to the Hough Transform, every candidate symmetry axis is represented in a parameter space. We map symmetry lines on this dual space (d, phi). In this representation d is the distance between the symmetry line and the origin, while phi is the angle that the line's normal makes with the horizontal axis. After an appropriate distance function is defined in these parameter space, we must cluster similar transformations.


[ Comaniciu and Meer 2002 ]
Clustering is a very important step because many point pairs which are invariant under a certain axis will not map exactly onto the same dual point in parameter space. We follow the approach of [1] and use Mean-Shift Clustering [4]. The method derives a continous density distribution from the transformation points. It then used a gradient ascent method to find local maxima of this distribution.

After detecting the relevant symmetry axes, we must determine the set of points where that transformation holds. This set might not be contiguous. For this reason an incremental approach is taken which starts at a few selected seeds and proceeds to near neighbours where the same symmetry is present. This process associates pairs of patches that are invariant under a reflection by an axis.

We start object completion by quering for points in the neighbourhood of the hole. Next we identify a symmetry axis S associated with a patch that contains this neighbourhood points. The hole is completed with the points of this patch that are reflected in the hole.

Results

     
On the left we can see the symmetry used to complete the missing hand of the lizard. On the right we can see a partial symmetry detected in the bunny.This example shows that the algorithms is robust to noisy data. [ view larger images ]

Future work

Some interesting problems for future work are:

Bibliography

1. MITRA, N. J., GUIBAS, L. J., AND PAULY, M. . Partial and approximate symmetry detection for 3d geometry. ACM Trans. Graph. 2006

2. MITRA, N. J., GUIBAS, L. J., AND PAULY, M. . Symmetrization. ACM Trans. Graph. 2007

3. THRUN, S., AND WEGBREIT, B. 2005. Shape from symmetry. In Int. Conference on Computer Vision

4. COMANICIU, D. , MEER, P., Mean Shift: A Robust Approach Toward Feature Space Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.5, p.603-619, May 2002