Covisibility graph

Introduced prominently in ORB-SLAM, the covisibility graph is a weighted undirected graph over keyframes:

• Nodes: keyframes.
• Edges: connect two keyframes that observe common map points.
• Edge weight: the number of shared map point observations. In ORB-SLAM, an edge is kept when the weight exceeds a threshold $\theta$ (typically around 15 shared points).

The graph encodes what sees what, independent of when or where keyframes were created. Two keyframes taken minutes apart from the same viewpoint are strongly connected; two consecutive keyframes during a fast turn may barely be connected at all. This makes covisibility a far better notion of “neighbourhood” for a visual map than time or Euclidean distance.

SLAM systems query the covisibility graph constantly:

• Local bundle adjustment: when a new keyframe arrives, optimise it together with its covisibility neighbours and the map points they see — a well-defined local window that automatically includes exactly the relevant geometry.
• Tracking and map-point retrieval: project points seen by covisible keyframes into the current frame to find more matches.
• Loop closure: candidate places from the recognition database are verified against covisibility neighbourhoods, and detected loops correct not just one pose but the whole covisible group.
• Keyframe culling: a keyframe whose observations are largely covered by its covisibility neighbours is redundant and can be removed, keeping the map compact.

A closely related structure is the essential graph: a much sparser subgraph consisting of a spanning tree of the keyframes, augmented with high-weight covisibility edges and loop closure edges. ORB-SLAM runs pose-graph optimisation over the essential graph rather than the dense covisibility graph, getting most of the accuracy of full optimisation at a fraction of the cost.

Formal definition and maintenance

Let $\mathcal{P}_i$ be the set of map points observed by keyframe $K_i$. The covisibility weight between two keyframes is simply

$$w_{ij} = \left| \mathcal{P}_i \cap \mathcal{P}_j \right|,$$

and the graph keeps edge $(i, j)$ iff $w_{ij} \geq \theta$. Nothing about this requires poses — it is pure bookkeeping over observations — which is what makes it cheap and incremental:

• When a keyframe is inserted, count shared observations with the keyframes that see its matched points (found via each map point’s observation list), and add/update edges.
• When a map point gains or loses an observation (fusion, culling, tracking new matches), the affected weights are updated locally.
• When a keyframe is culled, its edges disappear, and the spanning tree reattaches its children to other neighbours.

In practice each keyframe stores its neighbours sorted by weight, so queries like “the $N$ best covisible keyframes” (used to define the local BA window and to expand loop candidates) are $O(1)$ lookups. Note the asymmetric thresholds in ORB-SLAM’s design: the covisibility graph keeps relatively weak edges ($\theta \approx 15$ shared points) because local mapping benefits from a generous neighbourhood, while the essential graph keeps only strong ones ($\theta = 100$) because pose-graph optimisation wants few, reliable constraints.

Why not time or distance?

It is worth internalising the failure modes of the alternatives. Temporal windows (the last $N$ frames) break whenever the camera revisits a place: the old keyframes observing the same scene are excluded from local BA, so the map duplicates and drifts locally. Metric neighbourhoods (keyframes within $r$ metres) break with orientation — a keyframe half a metre away but facing the opposite wall shares no observations and contributes nothing but cost — and depend on pose estimates that are themselves drifting. Covisibility sidesteps both by defining neighbourhood in observation space: exactly the keyframes whose measurements constrain the same geometry, which is exactly the set local BA needs for a well-conditioned problem.

Common pitfalls

• Threshold trade-offs: too low a $\theta$ and local BA windows balloon (every keyframe in a small room is connected to every other); too high and the graph fragments, starving BA of constraints. Small-room, texture-rich scenes are the stress test.
• Stale weights: if point culling/fusion does not update covisibility edges, the graph slowly diverges from reality and local windows include irrelevant keyframes.
• Confusing the two graphs: local mapping queries the (dense) covisibility graph; loop-closure pose-graph optimisation runs on the (sparse) essential graph. Running PGO on the full covisibility graph is dramatically slower for marginal accuracy gain — the exact point of the essential-graph design.
• Assuming covisibility implies matchability: two keyframes can share many points yet have extreme viewpoint difference; descriptor matching between them may still fail even though the graph says they are neighbours.

Why it matters for SLAM

The covisibility graph is the data structure that lets feature-based SLAM scale: it bounds the cost of local BA, focuses map-point search, and provides the sparse skeleton (the essential graph) for fast global correction after loop closure. Introduced in ORB-SLAM, it influenced map management in virtually every subsequent keyframe-based system, including ORB-SLAM2/3 and their many derivatives.

Related

• ORB-SLAM
• ORB-SLAM3
• Visual Place Recognition (VPR)
• Pose graph optimization