6.3Spatial Structure Construction

Given a visual scene (a 2D image, a video, a point cloud, or an RGB-D stream) and two target object instances specified by tags, boxes, or masks, SRE outputs their spatial relationship either as a triplet $(s,p,o)$ with $p$ drawn from a spatial predicate vocabulary, or as a natural-language sentence describing the relation and its context. Three subtasks differ in output granularity. Visual Spatial Classification (VSC) [785, 786] predicts the predicate from a closed label set (“on”, “in”, “next to”). Visual Spatial Description (VSD) [787, 788] generates a free-form sentence that can carry attributes and context beyond the bare predicate. Quantitative spatial understanding [789, 229] replaces qualitative predicates with metric quantities (distances, absolute sizes, 3D orientations), which navigation and manipulation require. The field has moved through these three in order, from closed-set classification to generation to metric quantification.

Figure 6.13 summarizes the task and the three method families surveyed below.

Table 6.17 lists the benchmarks. They differ mainly in how relations were collected: manual labeling of robot-captured lab scenes in SpatialAwareRobot [795]; adversarial crowdsourcing in SpatialSense [785], where annotators propose relations that fool a baseline and only those count, which makes the dataset deliberately hard; the merge of SpatialSense and Visual Genome [796] into VSRC [787], whose 143K free-form descriptions make it the standard VSD benchmark; the 34-preposition, English–French annotations of SpatialVOC2K [797]; and the automatically generated, depth-aware SpaceSGG [776], released as 10K scene descriptions, 20K question–answer pairs, and 20K multi-turn conversations over 20K scenes.

Each subtask has its own evaluation regime, and the metrics are not comparable across them. VSC is scored as classification: predicate accuracy and per-relation precision/recall on SpatialSense [785] and VSRC [787], with the driving-scene systems Roadscene2Vec [779] and HKT-SG [790] reporting per-relation F1 or accuracy on their own data; results on SpatialSense’s adversarial split lag well behind those on conventional crowdsourced data, which is the contextual-relation difficulty taken up under Challenges. VSD is scored as generation: VSDNet [787] and 3DVSD [788] report BLEU-4, METEOR, and CIDEr on VSRC, and LLaVA-SpaceSGG [776] reports QA accuracy on SpaceSGG. Quantitative understanding is the newest regime: SpatialVLM [229] and SpatialRGPT [789] report distance- and size-estimation accuracy against depth-aligned ground truth on auto-generated test sets (SpatialVLM-Bench, SpatialRGPT-Bench), SpatialLLM [794] reports combined qualitative and quantitative VQA accuracy, and SpatialBot [793] adds robotic grasp success as an embodied proxy. MLLM-based models dominate the qualitative leaderboards but still fall short on metric-scale reasoning, which motivates the unified representations discussed next.

Spatial relations are not purely geometric. “A cup on a table” is plausible and “a cup on a wall” is not, yet the two differ only in object identity, so rule-based and purely geometric methods cannot capture functional or commonsense constraints; a model needs to know what objects are for and where they tend to be, not just their boxes or point coordinates. Metric grounding is the second gap. MLLMs handle contextual and functional predicates well but judge distances, sizes, and angles poorly; injecting geometry and depth during pre- or post-training, or exposing dedicated spatial tools, is the current route, and the longer-term goal is a representation that holds discrete predicates (“near”) and continuous quantities (“2 meters away”) together, since navigation and manipulation need both. Generalization is the third. SpatialSense [785] and VSRC [787] cover a small slice of real scenes, and models trained on them degrade under new object appearances, scene complexity, lighting, and occlusion; SpatialVLM [229] and its successors generalize better, but unseen and dynamic environments remain largely untested.

Given a visual scene, SGG produces a graph

where each entity in $\mathcal{O}$ is an object instance with a localization (a bounding box, or a mask in the panoptic setting) and a class label, and $p_{i}$ is a predicate from a relation vocabulary $\mathcal{P}$ describing how $s_{i}$ and $o_{i}$ interact.

The task is instantiated by input modality. Image SGG (ISG) [796, 809] on static 2D images is the original and most studied setting and anchors most benchmarks. Video SGG (VSG) [810, 811] adds time, so relations become dynamic and temporally extended, and temporal context disambiguates interactions a single frame leaves open. Textual SGG (TSG) [812, 813] parses a sentence (“A person is riding a horse in a field”) into a graph, treating SGG as structured language parsing. 3D SGG (3DSG) [342, 343] operates on point clouds or meshes and models relations in metric 3D space, free of the perspective ambiguity of images. Universal SGG (USG) [778] aims at one graph from several simultaneous modalities (image, video, 3D, text). Two further variants change the level of detail rather than the modality. Human–Object Interaction detection (HOI) [814, 815] restricts the subject to humans and has become a field of its own because of pose variability and the subtlety of intent. Panoptic SGG (PSG) [816, 817] grounds nodes on panoptic segmentation masks instead of boxes, so relations can involve “stuff” (sky, road) and are localized without the imprecision of boxes.

Figure 6.14 illustrates the five modality settings and the two specializations with a representative input and output each.

Table 6.18¹ lists the benchmarks by modality. The image benchmarks run from the small precursors Visual Phrase [838], Scene Graph [598], and VRD [829], which first exposed the long-tailed predicate distribution, to Visual Genome [796], Open Images [442], and GQA [839], with VrR-VG [840] and UnRel [841] carved out to test visually relevant and zero-shot relations respectively. Visual Genome is the primary benchmark but its raw release (33,877 object and 40,480 relationship synsets) is noisy and heavily long-tailed, so the community works with cleaned subsets: the broad cleaning in Table 6.18 keeps roughly 6K object and 1K predicate classes, and the de-facto SGG benchmark VG150 restricts these to the 150 most frequent object and 50 most frequent predicate classes. Spatial-only relations are covered by SpatialSense and SpatialVOC2K (see the preceding subsection), panoptic grounding by OpenSG [816], and non-standard viewpoints by the overhead AUG [842], the satellite STAR [843], ReCon1M [844], and instruction-based SkySenseGPT [845], and the traffic-scene graphs of [804]. Video benchmarks began with ImageNet-VidVRD [846] and the trajectory-annotated VidOR [847], then specialized to human activity (Action Genome [848]), drone footage (AeroEye [849]), panoptic video (PVSG [817]), fine topological interlacements (ASPIRe [850]), egocentric capture (Ego-EASG [851]), and imminent traffic events (IESG [805]). 3DSSG [342] is the standard 3D benchmark; PSG4D [852] adds time, and the operating-room sets 4D-OR [853], MM-OR [854], and EgoExOR [855] bring multimodal (RGB-D, audio, robot logs) and egocentric surgical scenes. On the text side, TSG Bench [856] evaluates LLMs on graph generation from narratives, while FACTUAL [812] and DiscoSG-DS [857] pair images with text for factually consistent, cross-modal graphs.

Evaluation separates what is given from what is predicted. In Predicate Classification (PredCls) boxes and object labels are given and only predicates are predicted; in Scene Graph Classification (SGCls) boxes are given and both object labels and predicates are predicted; in Scene Graph Generation (SGGen, also SGDet) everything is predicted, and a triplet counts only if both boxes overlap their ground truth at IoU $\geq 0.5$, with Phrase Detection relaxing this to the union box and SGGen+ also crediting correctly detected singleton nodes. Panoptic SGG replaces box IoU with mask IoU. The standard metric is recall of ground-truth triplets among the top-$K$ predictions,

under a graph constraint (one predicate per pair) or without it. Because $R@K$ is dominated by frequent predicates, mean Recall@K ($mR@K$) averages recall per predicate class and has become the long-tail metric of record; the gap between $R@K$ and $mR@K$ drove much of the debiasing literature [819, 818, 821]. Weighted triplet recall, micro- versus macro-averaging over images, the stricter $mAP_{rel}$ / $mAP_{phr}$ of the Open Images challenge, and retrieval-based R-Precision are reported in specific settings.

Each modality has its own benchmark and protocol, so leaderboards are not comparable across types: video SGG uses ImageNet-VidVRD, VidOR, and Action Genome with the same triad plus temporal-IoU thresholds; textual SGG uses set F1 over triples on FACTUAL and LLM-judged action coverage on TSG Bench; 3D SGG uses object-, predicate-, and triplet-level recall on 3DSSG; panoptic SGG uses mask-IoU $R@K$ on OpenSG and PVSG. Table 6.19 therefore reports only the image setting, where VG150 SGDet is shared.

Table 6.19 shows the trade-off that still shapes image SGG. The two-stage Motifs baseline keeps the highest overall recall, but its mean recall is the lowest, which is the frequent-predicate bias in numbers; BGNN’s debiasing doubles mean recall at a small cost in $R@K$. The one-stage DETR-style models start several recall points lower, since they must detect and relate in one pass with a weaker backbone, yet SGTR and RelTR reach the best mean recall of the group, and EGTR closes most of the overall-recall gap to two-stage methods while running end to end.

Given an image $\mathbf{I}\in\mathbb{R}^{H\times W\times 3}$ (a perspective view, a $360^{\circ}$ panorama, or a multi-view or video capture), layout estimation recovers the dominant surfaces that bound the navigable volume of a room as a room layout $\mathcal{L}=\{P_{k}\}_{k=1}^{K}$, where each $P_{k}$ is a planar polygon in 3D; equivalently the output may be plane parameters $(\mathbf{n}_{k},d_{k})$ or a per-pixel structural-surface label map. Under a vertical-wall model, the layout compresses to a floor-plan polygon with floor and ceiling heights $y_{f},y_{c}$. Outdoor road-layout methods instead predict road regions and vehicle occupancy in bird’s-eye view. Room parsing adds per-object instance masks $\{m_{i}\}$ or boxes with class labels, drawn from a fixed ontology or, in the open-vocabulary setting, from free-form language.

Table 6.20 summarizes the benchmarks. Perspective-image evaluation grew from Hedau [859] (308 web and LabelMe images with box layouts and surface labels) through its augmented successor Hedau+ and the more cluttered SUNbox drawn from SUN2012 [607], both built by Mallya and Lazebnik [861] to train FCN edge predictors, to LSUN Room Layout [870], the standard perspective benchmark with corner positions and cuboid topologies on over 5K images. Corridor and video data serve navigation: Yang [871] labels ground versus wall in corridor images, FreeYourCamera [872] records six-degree-of-freedom smartphone walks that frequently violate box and Manhattan assumptions, and MichiganIndoorCorridor [873] provides non-Manhattan corridors with glass and reflections. Panoramic and 3D evaluation rests on PanoContext [874] (cuboid layouts and furniture for about 500 SUN360 panoramas, the standard testbed for LayoutNet, HorizonNet, and LED2-Net), Stanford 2D-3D-S [875] (about 70K RGB-D panoramas with depth, normals, semantics, and meshes over 270 rooms, enabling joint layout-depth-semantics evaluation), and Matterport3D-Layout [869], derived from Matterport3D [340] with RANSAC-fitted plane ground truth for cuboid and non-cuboid rooms.

Metrics follow the output representation. Perspective benchmarks (Hedau, LSUN) report pixel error, the fraction of pixels whose predicted surface label differs from the ground truth, and corner error, the mean distance between predicted and true corners normalized by image size; the edge-map methods additionally report the contour-detection F-scores at the optimal dataset scale (ODS, one threshold for the whole set) and optimal image scale (OIS, the best threshold per image). Panoramic and 3D benchmarks (PanoContext, Stanford 2D-3D-S, Matterport3D-Layout) report 3D and 2D room IoU between the predicted and ground-truth layout volumes or floor plans, with frequency-weighted IoU and pixel accuracy as segmentation-style complements. A method trained for one input type rarely transfers to the other without re-training, so perspective and panoramic results are not compared directly, and the outdoor road-layout protocol [858] is separate again.

Table 6.21 compares the panorama methods under one protocol. The 1D column representation of HorizonNet gained about eight IoU points over LayoutNet’s 2D maps on PanoContext, and the geometric supervision of LED2-Net adds a further point or two on every benchmark; the beyond-cuboid methods pay for their generality on cuboid-heavy PanoContext (DuLa-Net, AtlantaNet below HorizonNet) and recoup it on Matterport3D-Layout, whose non-cuboid rooms are exactly what they were designed for.

The geometric priors that make layout estimation tractable also bound it. Cuboid models cannot express alcoves or L-shaped plans; Manhattan models keep orthogonal walls even when the footprint is free-form; the Atlanta-world model of AtlantaNet [868] frees wall orientation but not wall tilt; and plane-based methods such as GeoLayout [869] approximate curved geometry only with many planes. Slanted enclosures, split levels, and the outdoor bird’s-eye-view target of [858], which is a different output space altogether, all sit outside the standard formulations. Clutter and occlusion are the second obstacle: furniture hides the corners, boundaries, and vanishing lines that both classical and learned methods read, so estimators must hallucinate hidden structure from layout priors, and confidently wrong boundaries without uncertainty are the typical failure. Generalization follows from the data: benchmarks are indoor, mostly rooms and corridors, and models trained on one set degrade on another’s appearance, architecture, and lighting, while sparse, unposed multi-view capture breaks the pose assumptions of classical pipelines; the feed-forward geometry models of §6.2.4 are the natural starting point for layout from such input.

Given an untrimmed video (or a continuous multi-sensor stream), AD outputs a set of tuples $(t_{s},t_{e},c)$ with start time, end time, and category for every action instance. Three settings differ in what is assumed about the input. Action classification (AC) takes a trimmed clip and predicts one category, with no localization. Temporal action localization (TAL) predicts start and end times in untrimmed video, usually assuming one dominant action per video. Temporal action detection (TAD) is the general case: multiple instances per video, possibly overlapping or concurrent, across temporal scales, each to be localized and classified.

Figure 6.18 organizes the methods by the three settings; each builds on the previous one’s representations.

Table 6.22 lists the benchmarks by role. UCF101 [902] and HMDB51 [903] are trimmed-clip classification sets; AVA [904] adds spatio-temporal boxes on movie footage. THUMOS’14 [905], whose 20 classes carry dense temporal boundaries, and ActivityNet [906], with 200 classes over 20K untrimmed videos, are the standard TAL and TAD benchmarks, extended in scale and granularity by HACS Segment [907] and FineAction [908]. MultiTHUMOS [909], Charades [910], and TVSeries [911] supply dense, multi-label, overlapping actions in sports, homes, and television; Breakfast [912], 50Salads [913], MPII Cooking 2 [914], and COIN [915] cover procedural cooking and instructional activity for segmentation and step detection; and MEVA [916] (thousands of hours of surveillance) and MoVi [917] (motion-captured actors) sit at the large-scale and controlled extremes.

Each setting has its own metric. Action classification reports Top-1 accuracy, $\mathrm{Acc}_{\mathrm{Top}\text{-}1}=\frac{1}{N}\sum_{i=1}^{N}\mathbb{I}(\hat{y}_{i}=y_{i})$, with Top-$k$ on large label sets; temporal boundaries are given, so localization is not assessed. Localization quality is measured by the temporal intersection over union of predicted and ground-truth intervals,

a prediction counting as correct above a threshold $\tau$; TAL reports average precision at one or several thresholds. TAD scores detections $(I_{p},\hat{y},c)$ with confidence $c$ by mean average precision over classes and thresholds,

which penalizes misclassification, loose boundaries, and duplicates together; THUMOS’14 uses $\tau\in\{0.3,\dots,0.7\}$ and ActivityNet $\{0.5,\dots,0.95\}$, and proposal methods also report average recall at a fixed proposal budget. Weakly supervised methods are often evaluated on ActivityNet-1.2 rather than 1.3, so their numbers are not interchangeable with fully supervised ones.

Table 6.23 shows how far the two settings have diverged. Trimmed-clip classification on UCF101 was effectively solved once Kinetics-pretrained 3D networks arrived, with I3D and R(2+1)D within a point of each other near 98%. Detection on THUMOS’14 tells a different story: mAP@0.5 moved from 19.0 (S-CNN) to 36.9 (BSN) over the anchor-to-boundary transition, jumped to 55.5 with anchor-free salient-boundary features (AFSD), and reached 70.4 with query-based decoding (DualDETR), while the best weakly supervised method (CoLA, 32.2) matches fully supervised accuracy of only a few years earlier, which quantifies what video-level labels still cost.

Fully supervised TAD depends on densely annotated boundaries, which scale poorly to long, loosely structured real-world video; weakly and semi-supervised methods relax this with video-level labels or sparse temporal cues [918, 919], at the accuracy cost the table above makes visible. Actions are also still detected in isolation. Coupling TAD with structured temporal representations such as scene graphs or event schemas [778, 803] would let a system infer boundaries, temporal relations, and higher-level activity structure jointly, which matters most in instructional video, driving, and human–robot interaction. Finally, benchmarks and detectors remain visual and closed-set, whereas real action understanding draws on audio, language, gaze, and context and must handle actions outside a fixed vocabulary [920, 921, 922]; multimodal temporal detection, where audio or language sharpens boundaries and disambiguates semantics, and open-vocabulary formulations that loosen the classification-centric setup are the directions large multimodal video corpora now make feasible.

The input is a stream of exteroceptive observations (camera images, RGB-D frames, LiDAR, or radar), optionally fused with proprioceptive readings (IMU, wheel odometry, velocity and steering commands) and priors such as a coarse map, an initial pose, or GPS. The output is a map plus the estimated trajectory. Maps lie on an abstraction–detail spectrum: a topological map is a graph of distinctive places and their traversable connections, with no metric layout; a sparse metric map stores registered keypoints or landmarks and the camera-pose graph that observes them, enough for accurate localization but not for geometry; and a dense metric map reconstructs a complete surface or volume (point cloud, mesh, TSDF, or occupancy grid) for obstacle avoidance and 3D reconstruction. Two dense representations have become prominent in the past three years: neural implicit maps that store geometry and appearance in network weights (an MLP in iMAP [923], a voxel-grid encoder in NICE-SLAM [924]) and 3D Gaussian Splatting (3DGS) maps that represent the scene as explicit, differentiable 3D Gaussians [925, 926, 927].

SLAM systems are classified by the exteroceptive sensor and by the density of the map they build. LiDAR SLAM measures range directly with a stable error model; KISS-ICP [928] and KISS-SLAM [929] show that a minimal pipeline delivers robust real-time 3D LiDAR odometry and mapping at city scale. Visual SLAM uses monocular, stereo, or RGB-D cameras, exploiting texture for place recognition, with PTAM [88] and the ORB-SLAM family [91, 736] as the foundational systems. Multi-sensor SLAM tightly fuses cameras with IMUs and/or LiDAR (VINS-Mono, OKVIS, FAST-LIO2), and event-camera SLAM uses asynchronous per-pixel brightness changes for high-speed and high-dynamic-range operation [930]. By map density, sparse keypoint-and-pose-graph systems (ORB-SLAM) sit next to semi-dense direct methods that track image gradients (LSD-SLAM [718], DSO [719]), dense geometric systems that fuse point clouds, meshes, or TSDFs (KinectFusion, ElasticFusion), neural implicit systems (iMAP [923], NICE-SLAM [924], Co-SLAM, NICER-SLAM), and 3DGS systems that render and optimize Gaussians jointly with poses (SplaTAM [925], MonoGS [927], SplatSLAM, MASt3R-SLAM [931]). Read historically, the field moved from feature-based geometry (PTAM, ORB-SLAM) to direct methods (LSD-SLAM, DSO), to tightly coupled multi-sensor systems (OKVIS, VINS-Mono, ORB-SLAM3), to learning-augmented pipelines (DROID-SLAM [95], SuperPoint and SuperGlue matching [539, 541]), to neural implicit and then 3DGS maps, and most recently to 3D geometry foundation models (DUSt3R [122], MASt3R [728], MASt3R-SLAM).

Whatever the sensor or map, a SLAM system runs the four modules of Figure 6.20 in a loop. The front end is visual (or LiDAR) odometry, the incremental motion estimate between consecutive readings treated as a stand-alone task in §6.2.4; because each pose is estimated relative to the last, its errors accumulate as drift. Back-end optimization corrects that drift globally. Modern back ends pose the problem as factor-graph optimization: robot poses and landmarks are nodes, and measurements between them (visual reprojection, IMU pre-integration, GPS, loop-closure relative poses) are factors; solving for all nodes at once yields a consistent trajectory and map, factor graphs absorb heterogeneous sensors naturally, and incremental solvers such as iSAM2 update the estimate in real time, with GTSAM, g²o, and OKVIS as representative libraries. Loop closing supplies the back end with its strongest constraints by recognizing that the agent has returned to a previously visited place, comparing current observations against the history and, on a match, adding a constraint between two temporally distant poses that pulls the accumulated drift of the intervening trajectory back into alignment. Mapping finally places the sensor data in the global frame using the optimized trajectory, in whatever representation the application needs; for neural implicit and 3DGS maps it also minimizes a rendering loss (photometric or perceptual such as LPIPS) between observed images and views rendered from the current map, optimizing geometry, appearance, and poses jointly [925, 931].

Table 6.24 groups the benchmarks by what they stress. The classical trajectory sets are TUM RGB-D [652] (handheld indoor RGB-D with motion-capture ground truth), KITTI [173] (stereo and LiDAR driving), and the synthetic ICL-NUIM [933] with exact ground truth, while COLD [932] targets topological localization under changing conditions. Visual-inertial systems are tested on EuRoC [733] (micro-aerial vehicle), TUM VI [935], and OpenLORIS-Scene [938], the last built for lifelong SLAM in changing indoor scenes, and Bonn RGB-D [936] isolates dynamic objects. Large synthetic corpora (SceneNet [934], InteriorNet [937], Replica [339], TartanAir [666]) supply photorealistic training and controlled evaluation, with Replica the standard testbed for neural implicit and 3DGS SLAM; ScanNet++ [939] and ETH3D SLAM [940] add laser-scanned geometry for dense reconstruction quality; and DSEC [941], CU-Multi [942], and AirSwarm [943] open the event-camera and multi-agent settings.

Evaluation covers trajectory, map, rendering, and system cost. Trajectory accuracy uses the absolute trajectory error and relative pose error defined in §6.2.4, after aligning the estimated trajectory to the ground truth by a rigid or, for monocular systems, similarity transform; RMSE is the usual summary, with mean, median, and standard deviation also reported. Dense maps are scored by accuracy (mean distance from reconstructed points to the nearest ground-truth point) and completeness (the reverse), summarized by an F-score at a distance threshold, with Chamfer distance common for neural and 3DGS maps. Neural implicit and 3DGS maps add novel-view-synthesis metrics (PSNR, SSIM, LPIPS) on held-out views of the same trajectory. Memory footprint, tracking and mapping frame rates, and end-to-end latency decide embedded deployment [929]. Mature evaluation tools such as EVO² and the RPG Trajectory Evaluation toolbox³ implement these protocols.

Deployment exposes SLAM to conditions its assumptions exclude: static scenes, stable illumination, abundant texture, and ample computation. Dynamic objects induce correspondences that drift with their own motion; illumination change, reflective and transparent surfaces, and repetitive texture create perceptual aliasing that confuses data association and place recognition alike; and resource-constrained platforms must run ever heavier front and back ends. Current work answers each directly. Moving features are detected and excluded through semantic segmentation, motion-consistency checks, or learned masks; learned matchers (SuperPoint [539], SuperGlue [541], LoFTR [542]) replace hand-crafted descriptors and tolerate larger viewpoint and illumination changes; neural implicit and 3DGS maps are optimized jointly with poses and yield photorealistic reconstructions usable for inspection, telepresence, and policy learning; and the two-view geometry priors of DUSt3R [122] and MASt3R [728] remove the fragile hand-engineered front end, already enabling real-time dense monocular SLAM at the robustness of MASt3R-SLAM [931].

Two broader shifts follow. Lifelong SLAM aims at months of continuous operation by combining relocalization, map update, and place re-identification against changing environments, and is now an evaluation track of its own; collaborative multi-agent SLAM fuses observations across robots for faster coverage and graceful degradation, increasingly together with event cameras and heterogeneous sensors for high-speed, low-light, and high-dynamic-range conditions. What remains open is concrete: 3DGS maps still do not scale to city-level memory and rendering budgets, learned components carry a sim-to-real gap, and verifying loop closures under strong perceptual aliasing is still the failure that breaks every back end.