Computational Geometry Tools and Applications in Computer Vision

ECCV'16 tutorial on October 8 from 2pm to 5pm

Computational Geometry, which is a branch of computer science devoted to the study of geometric algorithms and data structures, has been used successfully in many fields including GIS, CAD, Geophysics and Computer Graphics. Mature C++ libraries such as the Computational Geometry Algorithms Library (CGAL) provide geometric data structures and algorithms that are reliable, efficient, easy to use and easy to integrate in existing software.

The tenet of our tutorial is that computational geometry tools are not yet fully exploited in Computer Vision while they have a high potential in this field. Such a potential is best illustrated by a state-of-the-art multi-view stereo reconstruction method [1] that relies upon an efficient 3D data structure from CGAL, and led to the creation of the successful company Acute3D.

The goal of this tutorial is to propose an introduction to Computational Geometry tools and to highlight their potential in Computer Vision. The tutorial is composed of three parts. The first part focuses on basic data structures in Computational Geometry. The second part offers an introduction to the CGAL library, and the recent advances on genericity and ease of integration. The third part presents concrete applications to core topics in Computer Vision, such as 3D reconstruction and image segmentation. The tutorial is based on courses given at SIGGRAPH by the organizers [2,3] and a series of works published in Computer Vision and Computer Graphics conferences [4-9].

Part A: Basics of Computational Geometry by Pierre Alliez [slides]
- Sample problems (10min)
- Voronoi Diagram and Delaunay triangulation (15min)
- Shape reconstruction (15min)
- Mesh generation (15min)

Part B: Introduction to the CGAL library by Andreas Fabri [slides]
- What is CGAL? (10min)
- Demo for point set processing (15min)
- Demo for polygon mesh processing (15min)
- Demo for mesh generation (15min)

Part C: Applications to Computer Vision problems by Florent Lafarge [slides]
- Image segmentation (20min)
- MVS reconstruction (20min)
- Urban 3D modeling (15min)

[1] Vu, Labatut, Pons, Keriven. High Accuracy and Visibility-Consistent Dense Multiview Stereo. In PAMI, vol 34(5), 2012
[2] Alliez, Fabri. Computational Geometry Algorithms Library. SIGGRAPH ASIA Courses, 2009
[3] Alliez, Fabri. Computational Geometry Algorithms Library. SIGGRAPH Courses, 2016
[4] Mandad, Cohen-Steiner, Alliez. Isotopic approximation within a tolerance volume. SIGGRAPH, 2015
[5] Lafarge, Alliez. Surface reconstruction through point set structuring. Eurographics conference, 2013
[6] Duan, Lafarge. Image Partitioning into Convex Polygons. CVPR, 2015
[7] Verdie, Lafarge, Alliez. LOD Generation for Urban Scenes. In Trans. on Graphics, vol 34(3), 2015
[8] Lafarge, Mallet. Building large urban environments from unstructured point data. ICCV, 2011
[9] Lafarge, Keriven, Bredif, Vu. A hybrid multi-view stereo algorithm for modeling urban scenes. In PAMI, vol 35(1), 2013