View and Observation Graphs

Two graphs carry a multi-view problem's topology, as in Theia, GLOMAP and OpenSfM. A ViewGraph has one vertex per frame and one edge per verified pair (i, j), i < j; an ObservationGraph has frames on one side, the things they observe (targets, boards, tracks) on the other, and one edge per observation. The graph algorithms are Graphs.jl's; what is defined here is the label bookkeeping and the geometry they cannot know. Each graph's edge dictionary is its source of truth: edgelist returns it and the graph is rebuilt from it.

ViewGraph

VisualGeometryToolkitEstimation.ViewGraph — Type
ViewGraph{K, E}

The view graph of a set of frames: vertices labelled K (frame ids of any ordered type), one edge per verified pair (i, j) with i < j, carrying data E. An edge's data is its relative transform, or VisualGeometryToolkitCore's Attributed(transform, (; weight)) carrying a fixed non-negative weight (an inlier count; a bare transform weighs 1). The transform takes frame i's frame into frame j's — for a rotation R_ij, f_j = R_ij·f_i — as COLMAP's cam2_from_cam1.

Build it with ViewGraph(views, edges) or from the edges alone. Read it with vg[i, j], haskey(vg, i, j), views, edgelist and adjacent_views; its structure with components, articulation and bridges.

source
VisualGeometryToolkitEstimation.ViewGraph — Method
ViewGraph(views, edges) -> ViewGraph
ViewGraph(edges) -> ViewGraph

The view graph of views (frame labels, kept in the given order) with the edges, an AbstractDict keyed by pairs (i, j), i < j (a pair given the other way round is an ArgumentError: its data would have to be inverted, which only the caller knows how to do). A pair naming a frame not in views, or a frame paired with itself, is an ArgumentError. The one-argument form takes the views from the edges, sorted.

source

ObservationGraph

VisualGeometryToolkitEstimation.ObservationGraph — Method
ObservationGraph(edges) -> ObservationGraph

The observation graph of edges, an AbstractDict keyed by (observer, observed) pairs; the observers and the observed things are those the keys name, each side sorted.

source
VisualGeometryToolkitEstimation.covisibility — Function
covisibility(og::ObservationGraph; side = :observers) -> ViewGraph

The co-visibility of one side as a ViewGraph: two observers (side = :observers) are paired when they observe a common thing, two observed things (side = :observed) when a common observer observes both. Each edge is Attributed(shared, (; weight = length(shared))), shared the sorted labels of the other side they share and its weight their count (OpenSfM's pair connectivity), so spanning_tree keeps the best-connected pairs.

source

Structure and connectivity policies

A method picks its policy: one common gauge (require_connected), the largest part (keep_largest_component, the SfM default), or one gauge per component (label_components, what a calibration does).

VisualGeometryToolkitEstimation.components — Function
components(g) -> Vector

The connected components, largest first by vertex count, equal sizes by their smallest label (a ViewGraph's view, an ObservationGraph's observer). A ViewGraph's component is its sorted views; an ObservationGraph's is (; observers, observed), each sorted. Poses are comparable only within one component: a calibration gives each its own gauge.

source
VisualGeometryToolkitEstimation.label_components — Function
label_components(vg::ViewGraph) -> Dict

Each view's component number, 1 the largest (GLOMAP's MarkConnectedComponents): the policy of one gauge per component.

source
label_components(og::ObservationGraph) -> @NamedTuple{observers::Dict, observed::Dict}

Each observer's and each observed thing's component number, 1 the largest.

source

Spanning trees and edge filters

chain composes relative transforms along the maximum spanning_tree, the initialization Theia and OpenCV use; fit_rotation_averaging takes it as seed = :spanning_tree. filter_cycles drops edges no consistent loop supports before averaging, filter_by_orientation those that disagree with the averaged rotations after it. fit_filtered_rotation_averaging runs both around the averaging.

VisualGeometryToolkitEstimation.spanning_tree — Function
spanning_tree(vg::ViewGraph) -> Vector{Tuple}

The maximum spanning forest by the edges' weights (Graphs.jl's kruskal_mst, maximizing): the strongest edges that tie every component together, as sorted pairs. Theia and OpenCV seed absolute orientations from it, weighted by inlier counts. An edge of non-positive weight is an ArgumentError.

source
VisualGeometryToolkitEstimation.chain — Function
chain(vg::ViewGraph, root; compose = *, inverse = inv, identity) -> Dict

Absolute transforms from relative ones by walking the maximum spanning tree (spanning_tree) out of root: each view k of root's component gets world_from_k, root the identity, an edge's transform j_from_i taking view i's frame into view j's. Going from i to j along the tree, world_from_j = world_from_i ∘ inverse(j_from_i); from j to i, world_from_i = world_from_j ∘ j_from_i. Views outside root's component get no entry. With rotations (identity = one(RotMatrix{3, Float64})) this is the spanning-tree seed of rotation averaging (d = R_k·f_k).

source
VisualGeometryToolkitEstimation.filter_cycles — Function
filter_cycles(vg::ViewGraph; tol, residual = rotation_loop_angle, keep_untested = true) -> ViewGraph

The view graph without the edges no consistent loop supports (Theia's FilterViewGraphCyclesByRotation): over the triangles(i, j, k), residual(vg[i, j], vg[j, k], vg[i, k]) measures how far the loop is from closing, and an edge stays when at least one of its triangles has residual <= tol. An edge in no triangle stays when keep_untested (a sequence's chain edges have none) and goes otherwise. The default residual is rotation_loop_angle, for rotation edges.

A triangle cannot say which of its edges is wrong, so a correct edge whose every triangle runs through a wrong one goes too, and wrong edges clustered on a sequence's backbone can disconnect the graph; a removal that worst-first re-checks does no better there (the edges' loops all run through the cluster).

source
VisualGeometryToolkitEstimation.rotation_loop_angle — Function
rotation_loop_angle(ij, jk, ik) -> Float64

The angle (radians) by which the rotations of a triangle's edges fail to close: f_k = R_jk·R_ij·f_i should equal R_ik·f_i, so the angle of R_ikᵀ·R_jk·R_ij. The residual of filter_cycles for rotation edges (each edge a rotation, an Uncertain one, or an Attributed one of either; a covariance plays no part).

source
VisualGeometryToolkitEstimation.filter_by_orientation — Function
filter_by_orientation(vg::ViewGraph, world_from; tol) -> ViewGraph

The view graph without the rotation edges that disagree with the absolute rotations world_from (a Dict view => R_k, d = R_k·f_k, as fit_rotation_averaging returns): an edge (i, j) goes when the angle of R_j·R_ij·R_iᵀ exceeds tol radians (Theia's FilterViewPairsFromOrientation). An edge with a view missing from world_from stays. Each edge is a rotation, an Uncertain one, or an Attributed one of either (as fit_rotation_averaging takes them; a covariance plays no part), and so may each R_k.

source
VisualGeometryToolkitEstimation.fit_filtered_rotation_averaging — Function
fit_filtered_rotation_averaging(vg::ViewGraph; cycle_tol = nothing, orientation_tol = nothing, kwargs...)
    -> (; fit, graph)

Rotation averaging behind the two view-graph filters, as Theia's global pipeline runs them: filter_cycles at cycle_tol before the averaging, then filter_by_orientation at orientation_tol against the averaged rotations and, when it dropped an edge, the averaging again on what is left. Both tolerances are radians; nothing skips that filter. kwargs go to every fit_rotation_averaging (its optimization_strategy and its scale or width among them). Returns the fit and the view graph it was fitted on (graph: a caller drops whatever it keyed by a removed edge, a sequence's tracks). A graph a filter disconnects is an ArgumentError naming that filter (require_connected).

source