Skip to content

NoPA: Non-Parametric Online 3D Scene Graph Generation

Conference: ECCV 2026
Paper: ECCV Official
Area: 3D Vision
Keywords: 3D Scene Graph, Online Generation, Non-Parametric Distribution, Kernel Density Estimation, Maximum Mean Discrepancy

TL;DR

Addressing geometric detail loss and severe under-merging caused by single-Gaussian parametric assumptions in online 3D scene graph generation, NoPA introduces a fixed-size non-parametric particle representation with a two-stage "Hellinger pre-filter + MMD refinement" online merging strategy and affinity-based relationship propagation, doubling relationship recall while preserving real-time frame rates.

Background & Motivation

Online 3D semantic scene graph (3D SSG) generation from sequential RGB-D streams provides a structured spatial abstraction of objects, geometry, and functional relationships, serving as a fundamental perceptual backbone for embodied AI, robot navigation, and spatial manipulation. However, conventional offline frameworks and dense SLAM-based online systems incur prohibitive computational burdens, requiring full-scene point cloud reconstruction and iterative graph optimization that cannot meet the low-latency and bounded-memory constraints of real-time robotic deployment. Recently, SLAM-free online approaches such as FROSS achieved real-time frame rates by lifting 2D scene graphs into 3D and parameterizing each object as a single 3D Gaussian ellipsoid, but this rigid assumption introduces severe geometric and structural bottlenecks.

A single 3D Gaussian enforces an unimodal ellipsoidal geometric prior defined strictly by its centroid and covariance matrix. For thin, planar structures such as windows, pictures, and walls, depth back-projections often produce near-singular covariance matrices; for complex concave or multi-part objects like sinks, chairs, or counters, an ellipsoid cannot capture multi-modal spatial support. Under varying camera viewpoints and partial visibility during sequential exploration, local object observations yield inconsistent covariances and spatial offsets. When applying covariance-based metrics like Hellinger or Bhattacharyya distance, data association between local candidates and global objects frequently fails, causing pervasive under-merging. Single object instances are consequently fragmented into multiple disjoint small Gaussians that are discarded by post-processing filters, precipitating a cascading loss of relationship edges in the final graph.

The fundamental trade-off lies in retaining expressive 3D geometric fidelity without collapsing back into unbounded point clouds or sacrificing real-time inference efficiency. The core idea is to represent each 3D object as a non-parametric particle set with kernel density estimation, employ Maximum Mean Discrepancy (MMD) within a Hellinger margin band for distribution-level data association, and preserve constant memory via MCMC-perturbed resampling while recovering missed relationship edges through affinity-guided propagation.

Method

Overall Architecture

NoPA ingests streaming RGB-D frames alongside real-time camera poses. At each timestep, a lightweight pretrained 2D detector (RT-DETR-EGTR) infers 2D bounding boxes and pairwise predicate hypotheses. For each detected object box, pixels are sampled uniformly and back-projected via depth into the world frame to establish a local 3D particle set. These candidates are then fused into the existing global 3D scene graph via a fast two-stage association rule: an inexpensive Hellinger distance pre-filter resolves clear matches and clear spawns, while ambiguous pairs within an uncertainty margin are verified through Maximum Mean Discrepancy (MMD) on their kernel density estimates. Following a merge, a constant particle count is enforced via KDE-based proposal resampling. Finally, the cached MMD affinity matrix is reused to cluster high-affinity candidates and propagate relationship predictions, recovering edges missed by single-view 2D predictions.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Streaming RGB-D Input & Camera Pose"] --> B["2D Scene Graph Detection & Particle Sampling"]
    B --> C["Two-Stage Association & Distribution Merging<br/>Hellinger Pre-filter + MMD Margin Test"]
    C --> D["Constant-Memory Particle KDE Resampling<br/>MCMC Proposal Perturbation on Union Support"]
    D --> E["Affinity Cluster Relation Propagation<br/>Reusing MMD Scores to Recover Dropped Edges"]
    E --> F["Global 3D Semantic Scene Graph Output"]

Key Designs

1. Non-parametric particle representation: Eliminating rigid ellipsoidal priors while preserving multi-modal support Single-Gaussian modeling forces objects into unimodal, symmetric ellipsoids, discarding fine surface geometry and failing on non-convex or thin structures. NoPA models each 3D object \(o\) as a discrete particle set \(\mathcal{X}(o) = \{\mathbf{x}_k\}_{k=1}^n \subset \mathbb{R}^3\) of \(n\) points, which defines a continuous probability occupancy distribution through kernel density estimation (KDE): $\(\hat{f}(\mathbf{x}\mid o) = \frac{1}{n} \sum_{k=1}^n \kappa(\mathbf{x}, \mathbf{x}_k), \quad \kappa(\mathbf{x}, \mathbf{y}) = \exp\left(-\frac{\|\mathbf{x}-\mathbf{y}\|_2^2}{2\sigma^2}\right)\)$ This non-parametric formulation naturally accommodates arbitrary geometries, multi-part shapes, and planar instances without maintaining full dense point clouds, eliminating the root cause of covariance-induced under-merging under viewpoint variations.

2. Two-stage online association and merging: Balancing millisecond latency with distribution-level precision Evaluating full distribution metrics across all local-global candidate pairs would destroy real-time performance, whereas relying purely on covariance matching leads to association errors on ambiguous cases. NoPA resolves this with a two-stage decision pipeline: for local candidate \(\hat{o}\) and global object \(o\), first- and second-order moments \((\mu, \Sigma)\) and \((\hat{\mu}, \hat{\Sigma})\) are fitted to calculate the closed-form Hellinger distance \(d_H\). Pairs with \(d_H < \delta_H - \epsilon\) are immediately merged, while those with \(d_H > \delta_H + \epsilon\) spawn new nodes. For borderline candidates falling within the margin band \([\delta_H - \epsilon, \delta_H + \epsilon]\), the system triggers a Maximum Mean Discrepancy (MMD) test in reproducing kernel Hilbert space: $\(d_{\mathrm{MMD}}^2(o, \hat{o}) = \mathbb{E}_{\mathbf{x},\mathbf{x}'\sim\mathcal{X}(o)}[\kappa(\mathbf{x}, \mathbf{x}')] + \mathbb{E}_{\mathbf{y},\mathbf{y}'\sim\mathcal{X}(\hat{o})}[\kappa(\mathbf{y}, \mathbf{y}')] - 2\mathbb{E}_{\mathbf{x}\sim\mathcal{X}(o),\mathbf{y}\sim\mathcal{X}(\hat{o})}[\kappa(\mathbf{x}, \mathbf{y})]\)$ Merging occurs if \(d_{\mathrm{MMD}} \le \delta_{\mathrm{MMD}}\), otherwise spawning a new object. Because MMD compares full continuous distributions without requiring explicit point-to-point correspondence or surface meshing, it reliably intercepts false associations between objects sharing similar spatial centroids but possessing distinct geometric supports.

3. Constant-memory KDE resampling: Preventing particle explosion and stabilizing long-horizon fusion Naively concatenating particle sets across streaming frames causes particle counts to grow linearly, resulting in unbounded memory expansion and exponential computational slowdowns. NoPA introduces a continuous KDE resampling scheme that updates the merged object support while resetting the particle count to a constant \(n\): $\(\mathcal{X}_j(o) \leftarrow \mathcal{X}_{I_j}(o) + \varepsilon_j, \quad I_j \sim \mathrm{Uniform}\{1, \dots, 2n\}, \quad \varepsilon_j \sim \mathcal{N}(0, h^2 \Sigma)\)$ In implementation, this proposal step of MCMC sampling is vectorized via Cholesky decomposition \(LL^\top = h^2 \Sigma\) as \(\mathcal{X}(o) \leftarrow \mathcal{X}_{:,\mathbf{I}}(o) + L \mathbf{Z}\), where \(\mathbf{Z} \in \mathbb{R}^{3\times n}\) is standard Gaussian noise. This resampling guarantees that every object maintains exactly \(n=256\) particles, bounding runtime and GPU memory to constant footprints while effectively smoothing multi-view observation boundaries and preserving multi-modal geometric modes.

4. Affinity cluster relationship propagation: Compensating for single-view predicate dropouts Pretrained 2D scene graph detectors suffer from frequent predicate dropouts caused by transient occlusions, lighting shifts, and threshold cutoffs; in an incremental 3D graph, missed edges often remain permanently lost. NoPA reuses the pairwise MMD distances computed during association to construct a bounded affinity matrix without additional compute: $\(\mathbf{A}_{i,j} = \left[\max\left(0, 1 - \frac{d_{\mathrm{MMD}}(\mathcal{X}_i(o), \mathcal{X}_j(o))}{2\delta_{\mathrm{MMD}}}\right)\right]\)$ Pairs with affinity below threshold \(\tau\) are filtered to prevent oversized clusters. For newly merged or spawned nodes, candidate relations are propagated across their affinity cluster, and final predicate types are determined through majority voting over accumulated evidence. This aggregation suppresses false-positive detections while recovering dropped relations across consistent geometric neighbors.

Key Experimental Results

Main Results

Evaluated on the 3DSSG benchmark (20 object classes, 7 predicate classes) and the ReplicaSSG benchmark (34 object classes, 9 predicate classes) under top-1 recall and mean recall (mRecall) metrics, alongside per-frame latency and VRAM consumption on an NVIDIA RTX 3090 GPU.

Dataset Method Rel. Recall (%) Obj. Recall (%) Pred. Recall (%) Obj. mRecall (%) Pred. mRecall (%) Latency (ms) VRAM (MB)
3DSSG JointSSG [34] 25.5 58.1 27.3 43.0 33.3 191 -
3DSSG Kim et al. [14] 9.1 59.0 7.1 51.0 8.0 310 -
3DSSG FROSS [11] 27.9 62.4 33.0 63.8 18.0 7 -
3DSSG FROSS (reproduced) 25.7 60.6 30.7 62.4 17.7 22 1204
3DSSG NoPA (n=128) 49.9 68.5 58.5 65.7 30.2 26 1206
3DSSG NoPA (n=256) 53.2 69.0 61.4 66.4 29.4 27 1206
ReplicaSSG FROSS [11] 22.3 26.1 27.8 28.8 20.4 7 -
ReplicaSSG FROSS (reproduced) 22.3 25.3 27.5 27.6 12.6 17 1206
ReplicaSSG NoPA (n=128) 32.4 28.0 34.6 29.6 16.5 22 1230
ReplicaSSG NoPA (n=256) 36.9 28.6 39.5 29.8 18.6 23 1230

Ablation Study

Ablation on the test split of the 3DSSG dataset dissecting the non-parametric particle representation (NP.), MMD-based association (Merge.), and affinity-based relationship propagation (Prop.).

Config NP. Merge. Prop. Rel. Recall (%) Obj. Recall (%) Pred. Recall (%) Obj. mRecall (%) Pred. mRecall (%) Note
Baseline (FROSS) \(\times\) \(\times\) \(\times\) 25.7 60.6 30.7 62.4 17.7 Standard parametric Gaussian baseline
+ Particle representation \(\checkmark\) \(\times\) \(\times\) 17.6 66.1 20.8 64.8 11.1 Naive Gaussian merging fails on particle distributions
+ MMD merging strategy \(\checkmark\) \(\checkmark\) \(\times\) 26.3 69.0 31.0 66.4 17.1 Distribution-level MMD unlocks particle representation
Full NoPA \(\checkmark\) \(\checkmark\) \(\checkmark\) 53.2 69.0 61.4 66.4 29.4 Relation propagation surges triplet recall to 53.2%

Key Findings

  • Non-parametric representations require tailored distribution criteria: Replacing Gaussians with particles while retaining parametric covariance merging causes relationship recall to plummet to 17.6%, confirming that Gaussian assumptions are fundamentally incompatible with multi-modal particle sets; coupling particles with MMD resolves this and establishes immediate gains.
  • Relationship propagation critically restores topological completeness: Without altering object spatial extents, relationship propagation doubles predicate recall (31.0% \(\rightarrow\) 61.4%) and surges relationship recall from 26.3% to 53.2% (+26.9% absolute increase), proving that transient 2D predicate dropout is the primary bottleneck in online 3D SSG construction.
  • Favorable latency-accuracy operating point: With \(n=128\) particles, NoPA already reaches 49.9% relationship recall at 26ms per frame (~38.5 FPS); scaling to \(n=256\) increases runtime by only 1ms (27ms, ~37 FPS) with a steady 1.2GB VRAM footprint, validating its readiness for real-time onboard robotics.

Highlights & Insights

  • Continuous KDE resampling solves the particle explosion dilemma: Applying MCMC perturbation over unified candidate supports maintains a strictly bounded memory footprint while avoiding voxel-grid discretization artifacts and preserving multi-modal shape modes.
  • Two-stage association as a compute-optimal filter: Rather than blindly computing full MMD kernel matrices across all candidates, the method uses moment-level Hellinger distance as a fast gate, invoking MMD only within an ambiguous boundary band to achieve maximum precision at minimal compute cost.
  • Zero-overhead topological healing via metric reuse: Directly repurposing intermediate MMD scores from the merging stage into graph affinity weights enables robust multi-view relation voting without introducing auxiliary neural networks.

Limitations & Future Work

  • Bottlenecked by 2D front-end detections: As a 2D-to-3D lifting pipeline, severe misclassifications or false negatives from the 2D RT-DETR-EGTR detector (e.g., confusing kitchen counters with cabinets) cannot be easily recovered by 3D spatial priors alone.
  • Sensitivity under dynamic objects and extreme occlusions: The current formulation assumes predominantly static indoor environments; dynamic object motion or prolonged severe occlusions could induce alignment drift during incremental particle fusion.
  • Future directions: Integrating open-vocabulary foundation models (VLMs) to provide semantic grounding alongside non-parametric geometric representations represents a promising path for open-world online scene understanding.
  • vs JointSSG / MonoSSG: Rely on heavyweight RGB-D SLAM and multi-view bundle adjustments, suffering high latency (191–310 ms, 3–5 FPS); NoPA bypasses SLAM mapping and runs at ~27 ms (~37 FPS) while achieving far higher recall.
  • vs FROSS: FROSS is fast but approximates objects as coarse Gaussian ellipsoids, causing severe under-merging on thin or multi-modal objects; NoPA retains rich geometry via non-parametric particle distributions and doubles relationship recall (53.2% vs 25.7%) with negligible latency overhead.

Rating

  • Novelty: ⭐⭐⭐⭐☆ Introduces non-parametric KDE and MMD association into SLAM-free online 3D SSG generation with clear theoretical elegance.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Rigorous validation across 3DSSG and ReplicaSSG with clear ablations and direct reproductions of competitive baselines.
  • Writing Quality: ⭐⭐⭐⭐⭐ Well-structured, mathematically rigorous, and articulates technical pain points clearly.
  • Value: ⭐⭐⭐⭐⭐ Provides an outstanding practical foundation for real-time robotic 3D spatial reasoning and embodied navigation.