Grouping-Based Low-Rank Trajectory Completion and 3D Reconstruction

Katerina Fragkiadaki, Marta Salas, Pablo Andrés Arbeláez, Jitendra Malik

Introduction

Extracting the 3D shape of a deforming object from a single 2D video—a task known as Non-Rigid Structure-from-Motion (NRSfM)—is a classic ill-posed problem in computer vision. Because many different 3D shapes can result in the same 2D projection, researchers traditionally rely on heavy constraints. Historically, NRSfM has only succeeded under strict "lab conditions": synthetic datasets where every point is tracked perfectly for the entire video, and the object is already perfectly separated from the background.

Real-world videos, such as those from YouTube or Hollywood movies, break these assumptions due to occlusions (parts of an object disappearing), segmentation challenges (separating the object from the background), and tracking noise (optical flow drifting or bleeding across boundaries). This paper bridges the gap between theoretical NRSfM and "in-the-wild" monocular video by combining dense optical flow, multiscale trajectory clustering, and low-rank matrix completion.

Proposed Method

The authors propose a robust three-stage pipeline to handle the messy realities of unconstrained video:

  1. Video Segmentation: The system uses multiscale trajectory clustering to group pixels that move similarly. To handle "bleeding"—where the background appears to move with the object due to tracking errors—morphological operations (erosion and dilation) are applied to clean the object masks.
  2. Trajectory Completion: Because many trajectories are incomplete due to occlusions or objects leaving the frame, the authors treat the 2D trajectory matrix as a low-rank completion problem. They solve this using Augmented Lagrange Multipliers to accurately fill in missing $(x, y)$ coordinates.
  3. 3D Reconstruction:
  4. Camera Pose: The authors make a surprising observation: for dense trajectories, a simple rank-3 truncation (normally used for rigid objects) is sufficient to recover camera rotation. With enough dense points, the "rigid" signal of the object dominates.
  5. Shape Recovery: With camera poses fixed, the system minimizes the reprojection error while penalizing the "nuclear norm" (a proxy for rank) of the 3D shape. This encourages the model to find a 3D shape that is as low-dimensional as possible while still matching the 2D video.
The proposed pipeline: from raw video sequences and trajectory clustering to handling missing entries and recovering 3D shape and depth via NRSfM.

Key Insights

  • Rank-3 is Enough for Rotation: Even for non-rigid objects, complex models are not strictly necessary to find the camera's rotation. The rigid component of dense point clouds allows for a simpler, more stable Euclidean upgrade step.
  • Completion via Reconstruction: Trajectory completion is not merely a preprocessing step; it acts as a byproduct of the reconstruction itself. By projecting the recovered 3D shape back into 2D, the system accurately "guesses" where occluded points should be.
  • Agnosticism: Unlike many previous methods, this approach requires no object-specific priors. It does not need to know whether it is looking at a face, a hand, or a torso to reconstruct it.

Datasets and Results

The method was evaluated across several datasets, including the NRSfM Benchmark (Garg et al.) for synthetic and real sequences, VSB100 (YouTube videos) for video segmentation, and Moseg (Hollywood movie clips) for motion-based segmentation.

  • Benchmark Performance: On the Garg et al. benchmark, the method achieved competitive results (mean RMS error around 3-5%) while using a fixed set of parameters across all sequences. This is a major improvement over previous methods that required manual tuning for different types of motion.
  • Robustness to Occlusion: In experiments where 13-31% of the data was artificially hidden to simulate occlusions, the error increase was minimal, proving the effectiveness of the low-rank completion strategy.
  • Qualitative Success: The paper showcases the first dense 3D reconstructions of objects from unconstrained sources, handling complex deformations and camera movements that would typically crash traditional NRSfM algorithms.

Limitations and Future Work

While highly effective for many deformations, the core assumption of the method is that the 3D shape is "low-rank" (describable by a few basis shapes). This holds well for a deforming face or a bending back but struggles with highly articulated bodies (like a person running or performing complex dances), which violate the low-rank assumption.

Furthermore, the quality of the 3D reconstruction remains heavily dependent on the quality of the initial 2D optical flow. If tracking fails completely due to motion blur or extreme low resolution, the reconstruction will fail as well. The authors suggest that extending these techniques to robustly handle highly articulated bodies is the next major frontier for "in-the-wild" 3D reconstruction.

Summary updated

Abstract

Extracting 3D shape of deforming objects in monocular videos, a task known as non-rigid structure-from-motion (NRSfM), has so far been studied only on synthetic datasets and controlled environments. Typically, the objects to reconstruct are pre-segmented, they exhibit limited rotations and occlusions, or full-length trajectories are assumed. In order to integrate NRSfM into current video analysis pipelines, one needs to consider as input realistic -thus incomplete- tracking, and perform spatio-temporal grouping to segment the objects from their surroundings. Furthermore, NRSfM needs to be robust to noise in both segmentation and tracking, e.g., drifting, segmentation <code>leaking'', optical flow</code>bleeding'' etc. In this paper, we make a first attempt towards this goal, and propose a method that combines dense optical flow tracking, motion trajectory clustering and NRSfM for 3D reconstruction of objects in videos. For each trajectory cluster, we compute multiple reconstructions by minimizing the reprojection error and the rank of the 3D shape under different rank bounds of the trajectory matrix. We show that dense 3D shape is extracted and trajectories are completed across occlusions and low textured regions, even under mild relative motion between the object and the camera. We achieve competitive results on a public NRSfM benchmark while using fixed parameters across all sequences and handling incomplete trajectories, in contrast to existing approaches. We further test our approach on popular video segmentation datasets. To the best of our knowledge, our method is the first to extract dense object models from realistic videos, such as those found in Youtube or Hollywood movies, without object-specific priors.
BibTeX
@inproceedings{fragkiadaki2014grouping,
  author = {Katerina Fragkiadaki and Marta Salas and Pablo Andrés Arbeláez and Jitendra Malik},
  title = {{Grouping-Based Low-Rank Trajectory Completion and 3D Reconstruction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure