Massively Parallel Multiview Stereopsis by Surface Normal Diffusion

Silvano Galliani, Katrin Lasinger, Konrad SchindlerICCV 2015 · DOI

Abstract

Turning a collection of 2D images into a dense 3D point cloud—a process known as Multiview Stereopsis (MVS)—is a computationally intensive task. Historically, researchers faced a trade-off between slow, high-accuracy global methods and fast, less precise local methods. This paper introduces Gipuma, a massively parallel MVS algorithm that reformulates Patchmatch in 3D scene space. By utilizing a novel "red-black" diffusion scheme for plane propagation, Gipuma achieves top-tier accuracy and completeness on major benchmarks while running orders of magnitude faster than competing methods.

Introduction

The core challenge in MVS is finding correspondences across multiple images. Standard algorithms often struggle with scalability as image resolutions increase, fronto-parallel bias on slanted surfaces, and the sequential nature of traditional Patchmatch, which hinders GPU parallelization. Gipuma addresses these issues by operating directly in 3D Euclidean space and employing a diffusion-based propagation strategy.

Methods

The authors introduce three major innovations to overcome traditional MVS hurdles:

Patchmatch in Scene Space

Instead of searching for pixel-shift "disparity," Gipuma operates in 3D Euclidean space. Each pixel is assigned a 3D plane defined by a depth and a surface normal. This allows the algorithm to aggregate similarity scores across multiple views simultaneously without complex epipolar rectification for every image pair.

Red-Black Diffusion Scheme

To break the sequential bottleneck of Patchmatch, the authors propose a diffusion-like propagation. They partition pixels into a checkerboard pattern (red and black). In one step, all "red" pixels are updated in parallel using information from their "black" neighbors, and vice versa.

The Red-Black diffusion scheme allows for massive parallelization by updating checkerboard patterns in alternating steps.

By using a larger neighborhood (up to 20 neighbors), information "diffuses" across the image rapidly, enabling the algorithm to fully utilize the thousands of cores available on modern GPUs.

Slanted Support Windows

By explicitly estimating surface normals, Gipuma uses "slanted" windows for matching. This removes the fronto-parallel bias, allowing the algorithm to accurately reconstruct slanted surfaces, such as roofs or hillsides, without "stair-casing" artifacts.

Key Results

Gipuma was evaluated on the DTU Robot Image Dataset, the Middlebury Multiview Benchmark, and large-scale oblique aerial images.

Convergence of median accuracy and completeness over iterations, alongside qualitative reconstruction results.
  • Speed: Gipuma can match ten 1.9-megapixel images in just 3 seconds on a consumer-grade GPU. A full reconstruction of a DTU object takes approximately 7 minutes.
  • Accuracy: At the time of publication, it reached the #1 rank in accuracy on the DTU benchmark with a 0.273mm mean error.
  • Efficiency: The algorithm only needs to store four values per pixel (depth and a 3D normal), making it highly memory-efficient for high-resolution mapping.

Conclusion

Gipuma demonstrates that local matching methods can achieve results comparable to global energy minimization methods when combined with powerful regularization through plane diffusion. While it still faces challenges in textureless regions, its speed and accuracy make it a high-performance tool for real-time SLAM systems and large-scale photogrammetry.

Summary updated

BibTeX
@inproceedings{galliani2015massively,
  author = {Silvano Galliani and Katrin Lasinger and Konrad Schindler},
  title = {{Massively Parallel Multiview Stereopsis by Surface Normal Diffusion}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2015},
  doi = {10.1109/iccv.2015.106},
}
Figure