Seminar
Geometric Correspondence Problems – from Shape Matching to 3D Movie Making
Overview
Topics covered:
This seminar deals with geometric correspondence problems. The main question we are looking at is: How can we tell whether two geometric shapes are approximately the same? This is a basic operation in higher level shape recognition and shape understanding problems. We will look at rigid shape matching (the goal is to align two shapes by rotation and translation), deformable shape matching (alignment permitting some deformation), correspondences in 3D movies (multi-frame alignment) and symmetry detection (what are the building blocks a 3D shape is composed of?).
Goals:
The seminar has four main goals:
- Give an introduction into the important recent research area of shape correspondence.
- Gain experience in reading and understanding current research literature.
- Let the participant gain some practical experience by a small, guided implementation exercise.
- Practice presentation of scientific topics.
|
 |
Requirements
Each participant has to:
- Give a talk based on one or more recent research publications.
The focus should be on presenting the major concepts and ideas rather than enumerating details. Each talk should take about 30 minutes (+ 5min, see below).
- Prepare an implementation of a small “toy problem” related to the topic area (there is one and the same practical problem assignment for several talks of similar topics, as listed below, to allow for easy problems and thus reduce the implementation effort). The result of the practical experiment should be presented within the talk, in an additional 5 minutes short presentation.
- Write a summary of approximtely 10 pagers that presents the main ideas of the paper, discusses the outcomes of the practical experiments, and relates the experiments to the broader context. (10% of the summary write-up should concern the practical experiments, i.e. one page).
Follow-ups:
- Good starting point for a Bachelor / Master thesis.
|
 |
Schedule
Overview:
- Start of the summer semester: fixing time slots and topics
- Short introduction to shape modeling and variational techniques (3-4 weeks)
- September (in the break before the winter semester): Talks, all in one week
Rooms and Dates:
- Assignment of topics and introductiory lecture: Tuesdays, 16-18h, c.t., Room 021, Building E1 4 (MPI-Informatik)
First meeting: Tuesday, April 21st 2009, 16-18h, Room 021 (E1 4)
(+ up to three more meetings on the following Tuesdays)
- Presentations:
September 15th-17th 2009
Building E1 4 (MPI Inf), Room 019
11-13h and 14-16h (each day)
- Hand-in of writeups: end of September 2009.
|
|
Contact
Instructor:
Teaching Assistants:
Seminar Slides
Download the Slides:
Individual Presentations:
Software Framework
Optional Software Package for the Practical Experiments:
|
 |
Topics & Literature
Rigid shape matching (local):
- Local rigid registration and the ICP Algorithm (1-2 Talks)
- Topic 1:
(taken)
- Besl, P. J., Mckay, N.: A Method for Registration of 3-D Shapes. In: IEEE Transactions on Pattern Analysis and Machine Intelligence, 14, 239-256, IEEE Computer Society, 1992.
- Chen, Y., Medioni, G.: Object modeling by registration of multiple range images. In: Image Vision Comput., 10, 145-155, Butterworth-Heinemann, 1992.
- Topic 2: (taken)
- Rusinkiewicz, S., Levoy, M.: Efficient Variants of the ICP Algorithm. In: Proceedings of the Third Intl. Conf. on 3D Digital Imaging and Modeling, 145-152, 2001.
- Real-time registration (1-2 Talks)
- Topic 3: (taken)
- Rusinkiewicz, S., Hall-Holt, O., Levoy, M.: Real-Time 3D Model Acquisition. In: ACM Transactions on Graphics 21(3) (Proc. Siggraph 2002), 438 – 446, 2002.
- Biber, P., Straßer, W.: The Normal Distributions Transform: A New Approach to Laser Scan Matching. In: IEEE/RJS International Conference on Intelligent Robots and Systems, 2003.
- Software project: registration of 2D point clouds
Given two 2D shapes (e.g. painted with the mouse), align the two shapes optimally using an ICP or NDT technique.
Compare the performance of different implementation variants.
Examine the convergence properties.
Rigid shape matching (global):
- Global rigid registration: (3-4 Talks)
- Topic 4: (taken)
- Gelfand, N., Mitra, N. J., Guibas, L. J., Pottmann, H.: Robust Global Registration. In: Symposium on Geometry Processing, 197-206, 2005.
- Topic 5: (taken)
- Huang, Q.-X., Flöry, S., Gelfand, N., Hofer, M., Pottmann, H.: Reassembling Fractured Objects by Geometric Matching. In: ACM Transactions on Graphics 25(3), 569–578, 2006.
- Topic 6: (taken)
- Li, X. & Guskov, I.: Multiscale Features for Approximate Alignment of Point-based Surfaces. In: Symposium on Geometry Processing, 217-226, 2005.
- Topic 7: (taken)
- Leordeanu, M. & Hebert, M.: A Spectral Technique for Correspondence Problems using Pairwise Constraints. In: International Conference of Computer Vision (ICCV), 1482-1489, 2005.
- Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Pang, H., Davis, J.: The Correlated Correspondence Algorithm for Unsupervised Registration of Nonrigid Surfaces. In: Proc. Neural Information Processing Systems (NIPS), 2004.
- Software project: global registration of 2D point clouds
Given two 2D shapes (e.g. painted with the mouse), find a coarse rigid alignment of the two shapes from an arbitrary initial pose.
Algorithms: Spectral matching, or RANSAC.
- Symmetry Detection (rigid, global):
(2 Talks)
- Topic 8: (taken)
- Mitra, N. J., Guibas, L. J., Pauly, M: Partial and approximate symmetry detection for 3D geometry. In: ACM Transactions on Graphics 25(3) (Siggraph 2006), 560–568, 2006.
- Topic 9: (taken)
- Bokeloh, M.; Berner, A.; Wand, M.; Seidel, H.-P. & Schilling, A.: Symmetry Detection Using Line Features. In: Computer Graphics Forum (Eurographics 2009), to appear (online version available), 2009.
- Software project: 2D symmetry detection
Given two 2D images, find translational symmetries (tiles) using 2D transformation voting as described by Mitra et al. 2006 (see above).
Deformable shape matching (local):
- Deformation Modeling:
(2 Talks)
- Topic 10: (taken)
- Terzopoulos, D.; Platt, J.; Barr, A. & Fleischer, K.: Elastically deformable models. In: Siggraph 87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, 205-214, ACM, 1987.
- Topic 11: (availabe)
- Botsch, M., Sorkine, O.: On Linear Variational Surface Deformation Methods. In: IEEE Transactions on Visualization and Computer Graphics, 14(1), 213–230, 2008.
- Deformable Registration: (4 Talks)
- Topic 12: (available)
- Häehnel, D., Thrun, S., Burgard, W.: An Extension of the ICP Algorithm for Modeling Nonrigid Objects with Mobile Robots. In: Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), 2003.
- Topic 13: (available)
- Allen, B., Curless, B., Popović, Z.: The space of human body shapes: reconstruction and parameterization from range scans. In: ACM Transactions on Graphics 22(3) (Proc. Siggraph 2003), 587–594, 2003.
- Topic 14: (taken)
- Brown, B., Rusinkiewicz, S.: Global Non-Rigid Alignment of 3-D Scans. In: ACM Transactions on Graphics 26(3) (Proc. Siggraph 2007), 2007.
- Topic 15: (available)
- Bronstein, A. M., Bronstein, M. M., Kimmel, R.: Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. In: Proc. National Academy of Sciences (PNAS), 103, 1168–1172, 2006.
- 3D Movie making (1 Talk)
- Topic 16: (available)
- Wand, M., Jenke, P., Huang, Q., Bokeloh, M., Guibas, L., Schilling, A.: Reconstruction of Deforming Geometry from Time-Varying Point Clouds. In: Symposium on Geometry Processing, 49-58, 2007.
- Global deformable shape matching: (1 Talks)
- Topic 17: (taken)
- Huang, Q.-X., Adams, B., Wicke, M., Guibas, L. J.: Non-Rigid Registration under Isometric Deformations. In: Computer Graphics Forum 27 (Proc. SGP 2008), 2008.
- Software project: 2D image deformation
Given a 2D image, compute a deformed image according to given constraints. Compute a morphing animation between two images (e.g. different faces).
Extension: Half-automatic image registration
Algorithm: Thin-plate splines.
