3D Point Cloud Processing

A point cloud is a 3D data representation obtained through numerical acquisition. Depth sensors, such as LiDAR, or computer vision algorithms, like Multi-View Stereo, typically generate a discrete set of 3D coordinates that sample a real-world scene. Processing point clouds poses several challenges, including acquisition noise, missing data due to occlusions, large data volumes often reaching billions of points equivalent to hundreds of gigabytes, and the lack of a regular structure. Common processing techniques include denoising, registration, meshing, compression, segmentation, and classification. Many fields, such as robotics, aerospace, virtual/augmented reality, cultural heritage, Computer-Aided Design (CAD), and urban planning, now extensively use 3D scanning technologies and point clouds.

Curvature estimation

Curvatures of curves and surfaces are local properties that are fundamental in geometry processing. They correspond to local features that characterize small neighborhoods of points on a surface. Their applications in computer vision are numerous, including keypoint extraction, sharp feature detection, shape matching, smoothing, and segmentation. The differential properties of smooth surfaces have been well understood in theory since Gauss's work in 1827. The current challenge is to estimate these quantities on point-sampled surfaces using accurate and precise estimators. Algorithms must be efficient in terms of time and memory and adapted to GPU implementations. Theoretical proofs of convergence under asymptotic settings should certify that these estimators tend toward the correct differential invariants and that they remain robust in the presence of noise.

Segmentation and classification

Segmentation aims to divide a 3D point cloud into distinct regions. Geometric criteria are usually used to define these regions. Planes and feature curves are examples of geometric patterns that can be extracted using a segmentation algorithm. Classification adds another level of abstraction, where semantics play an essential role. Specific objects, such as furniture in a building, pedestrians on the street, and electric poles in a landscape, can be detected in a 3D scan. Classification is increasingly addressed by deep learning methods, as a large amount of scanned data is now available. However, labeling 3D points is costly, and real scanned data exhibit a wide variety of shapes that cannot be well captured by mid-size neural networks. Finally, there is a strong need for machine learning approaches that do not require hundreds of hours of training on expensive hardware.

SAT Solvers on GPU

SAT problems are fundamental in computer science, and many solvers exist today. However, due to the ever-growing size of SAT formulas, efficient solvers are still actively being researched in various directions: sequential algorithms, parallel algorithms on multi-core processors, and parallel algorithms in cloud computing environments. Another type of hardware that has not yet been widely utilized in this domain is massively parallel architectures, such as GPUs. The challenge is to design a new kind of solver that leverages the computational power of GPUs to accelerate SAT problem solving.