Материал: [2.1] 3D Imaging, Analysis and Applications-Springer-Verlag London (2012)

73.Shilane, P., Funkhauser, T.: Selecting distinctive 3D shape descriptors for similarity retrieval. In: Proc. Shape Modelling and Applications (2006)

74.Sipiran, I., Bustos, B.: A robust 3D interest points detector based on Harris operator. In: Proc. 3DOR, pp. 7–14. Eurographics (2010)

75.Sivic, J., Zisserman, A.: Video Google: A text retrieval approach to object matching in videos. In: Proc. CVPR (2003)

76.Skraba, P., Ovsjanikov, M., Chazal, F., Guibas, L.: Persistence-based segmentation of deformable shapes. In: Proc. NORDIA, pp. 45–52 (2010)

77.Sochen, N., Kimmel, R., Malladi, R.: A general framework for low level vision. IEEE Trans. Image Process. 7(3), 310–318 (1998)

78.Starck, J., Hilton, A.: Correspondence labelling for widetimeframe free-form surface matching. In: Proc. ICCV (2007)

79.Strecha, C., Bronstein, A.M., Bronstein, M.M., Fua, P.: LDAHash: improved matching with smaller descriptors. Technical Report, EPFL (2010)

80.Sumner, R.W., Popovic,´ J.: Deformation transfer for triangle meshes. In: Proc. Conf. Computer Graphics and Interactive Techniques, pp. 399–405 (2004)

81.Sun, J., Ovsjanikov, M., Guibas, L.: A concise and provably informative multi-scale signature based on heat diffusion. Comput. Graph. Forum 28(5), 1383–1392 (2009)

82.Thorstensen, N., Keriven, R.: Non-rigid shape matching using geometry and photometry. In: Proc. CVPR (2009)

83.Toldo, R., Castellani, U., Fusiello, A.: Visual vocabulary signature for 3D object retrieval and partial matching. In: Proc. 3DOR (2009)

84.Torresani, L., Kolmogorov, V., Rother, C.: Feature correspondence via graph matching: models and global optimization. In: Proc. ECCV, pp. 596–609 (2008)

85.Wang, C., Bronstein, M.M., Bronstein, A.M., Paragios, N.: Discrete minimum distortion correspondence problems for non-rigid shape matching. In: Proc. Conf. on Scale Space and Variational Methods in Computer Vision (SSVM) (2011)

86.Wardetzky, M., Mathur, S., Kälberer, F., Grinspun, E.: Discrete Laplace operators: no free lunch. In: Conf. Computer Graphics and Interactive Techniques (2008)

87.Zaharescu, A., Boyer, E., Varanasi, K., Horaud, R.: Surface feature detection and description with applications to mesh matching. In: Proc. CVPR (2009)

Chapter 6

3D Shape Registration

Umberto Castellani and Adrien Bartoli

Abstract Registration is the problem of bringing together two or more 3D shapes, either of the same object or of two different but similar objects. This chapter first introduces the classical Iterative Closest Point (ICP) algorithm, which represents the gold standard registration method. Current limitations of ICP are addressed and the most popular variants are described to improve the basic implementation in several ways. Challenging registration scenarios are analyzed and a taxonomy of recent and promising alternative registration techniques is introduced. Three case studies are then described with an increasing level of problem difficulty. The first case study describes a simple but effective technique to detect outliers. The second case study uses the Levenberg-Marquardt optimization procedure to solve standard pairwise registration. The third case study focuses on the challenging problem of deformable object registration. Finally, open issues and directions for future work are discussed and conclusions are drawn.

6.1 Introduction

Registration is a critical issue for various problems in computer vision and computer graphics. The overall aim is to find the best alignment between two objects or between several instances of the same object, in order to bring the shape data into the same reference system. The main high level problems that use registration techniques are:

1.Model reconstruction. The goal in model reconstruction is to create a complete object model from partial 3D views obtained by a 3D scanner. Indeed, it is rare that a single 3D view captures the whole object structure, mainly due to self occlusions. Registration allows one to obtain the alignment between the partial

detailed description of registration techniques and experimental comparisons, we refer the reader to recent surveys [48, 57, 76, 78, 79]. It is worth mentioning that most of the existing computational solutions are based on the seminal Iterative Closest Point (ICP) [7] algorithm that we will describe shortly.

Chapter Outline This chapter is organized as follows. We first present the twoview registration problem and the current algorithmic solutions. We then describe some advanced registration techniques. We give a comprehensive derivation of algorithms for registration by proposing three case studies. We give an overview of open challenges with future directions and conclusions. Finally, suggestions for further reading, questions and exercises are proposed.

6.2 Registration of Two Views

Firstly we give a mathematical formulation of the two-view registration problem and then derive the basic ICP algorithm and discuss its main variants.

6.2.1 Problem Statement

Given a pair of views D and M representing two scans (partial 3D views) of the same object, registration is the problem of finding the parameters a of the transformation function T (a, D) which best aligns D to M. Typically, D and M are either simple point clouds or triangulated meshes [15]. The moving view D is called the data-view, while the fixed view M is called the model-view. The registration problem is solved by estimating the parameters a of the transformation T that satisfy:

where E is called the error function and measures the registration error. Figure 6.2 illustrates the two-view registration process. The data-view and the model-view show different portions of Bunny. The transformation function T (a, D) is applied and the registered views are shown.

Most of the registration methods are based on the paradigm defined directly above and differ in the following aspects:

The transformation function. The transformation function T usually implements a rigid transformation of the 3D space. It uses a translation vector t and a rotation matrix R whose values are encoded or parametrized in the parameter vector a. The transformation function may also handle deformations; this requires a more complex formulation.

Fig. 6.2 Pairwise registration. The data-view and the model-view (left) are to be registered. The transformation function

T (a, D) allows one to move the data-view to the model-view’s coordinate frame (right) to align the two views

The error function. The error function E measures the registration error or dissimilarity between D and M after alignment. When the transformation function T is rigid, E is a measure of congruence between the two views. In general E takes the form of an L2 approximation of the Hausdorff distance, which further involves the so-called point-to-point distance [7] or the point-to-plane distance [23].

The optimization method. This is the method or algorithm used to find the minimizer a in Eq. (6.1). The gold standard is the iterative approach used in the ICP algorithm [7], which was specifically designed for the problem at hand. General purpose optimization methods such as Levenberg-Marquardt [32] have also been used for this problem.

6.2.2 The Iterative Closest Points (ICP) Algorithm

In the classical ICP algorithm [7] the overall aim is to estimate a rigid transformation with parameters a = (R, t). Both views are treated as point clouds D = {d1, . . . , dNd } and M = {m1, . . . , mNm }. The error function is chosen as:

k{1,...,Nm}

1Note that the pair (di , mj ) is initially a tentative correspondence, which becomes a true correspondence when convergence to a global minimum is attained.