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.
VisualGeometryToolkitEstimation.ViewGraph — Method
ViewGraph(views, edges) -> ViewGraph
ViewGraph(edges) -> ViewGraphThe 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.
VisualGeometryToolkitEstimation.views — Function
views(vg::ViewGraph) -> VectorThe frame labels of vg, in the order it was built with.
VisualGeometryToolkitEstimation.adjacent_views — Function
adjacent_views(vg::ViewGraph, v) -> VectorThe views paired with v, sorted.
VisualGeometryToolkitEstimation.induced — Function
induced(vg::ViewGraph, keep) -> ViewGraphThe view graph on the views in keep and the edges between them, the views in vg's order.
ObservationGraph
VisualGeometryToolkitEstimation.ObservationGraph — Type
ObservationGraph{A, B, E}The bipartite graph of observations: observers labelled A (frames), observed things labelled B (targets, boards, tracks), one edge per observation (a, b) carrying data E. Build it with ObservationGraph(edges); read it with og[a, b], haskey(og, a, b), observers, observed, edgelist, observed_in and observers_of; its structure with components and articulation; its co-visibility with covisibility.
VisualGeometryToolkitEstimation.ObservationGraph — Method
ObservationGraph(edges) -> ObservationGraphThe 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.
VisualGeometryToolkitEstimation.observers — Function
observers(og::ObservationGraph) -> VectorThe observers (frames), sorted.
VisualGeometryToolkitEstimation.observed — Function
observed(og::ObservationGraph) -> VectorThe observed things (targets, boards, tracks), sorted.
VisualGeometryToolkitEstimation.observed_in — Function
observed_in(og::ObservationGraph, a) -> VectorThe things observer a observes, sorted.
VisualGeometryToolkitEstimation.observers_of — Function
observers_of(og::ObservationGraph, b) -> VectorThe observers that observe b, sorted.
VisualGeometryToolkitEstimation.covisibility — Function
covisibility(og::ObservationGraph; side = :observers) -> ViewGraphThe 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.
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.edgelist — Function
edgelist(g) -> Vector{Pair}The edges of a ViewGraph (its verified pairs) or an ObservationGraph (its observations) as (i, j) => data pairs, sorted by (i, j): the persistence form the graph is rebuilt from.
VisualGeometryToolkitEstimation.nedges — Function
nedges(g) -> IntThe number of edges of a ViewGraph (its verified pairs) or an ObservationGraph (its observations).
VisualGeometryToolkitEstimation.components — Function
components(g) -> VectorThe 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.
VisualGeometryToolkitEstimation.label_components — Function
label_components(vg::ViewGraph) -> DictEach view's component number, 1 the largest (GLOMAP's MarkConnectedComponents): the policy of one gauge per component.
label_components(og::ObservationGraph) -> @NamedTuple{observers::Dict, observed::Dict}Each observer's and each observed thing's component number, 1 the largest.
VisualGeometryToolkitEstimation.require_connected — Function
require_connected(g; what = "graph") -> gg (a ViewGraph or an ObservationGraph) when it is connected, otherwise an ArgumentError that names its components (an observation graph's by their observers): the policy of a method whose frames need one common gauge.
VisualGeometryToolkitEstimation.keep_largest_component — Function
keep_largest_component(vg::ViewGraph) -> ViewGraphThe largest connected component (Theia's GetLargestConnectedComponentIds, OpenCV's leaveBiggestComponent): the SfM policy.
VisualGeometryToolkitEstimation.articulation — Function
articulation(g)The cut vertices, whose removal splits their component: a ViewGraph's sorted views, or an ObservationGraph's (; observers, observed) (the fragile links of a session), each sorted.
VisualGeometryToolkitEstimation.bridges — Function
bridges(g) -> Vector{Tuple}The bridge edges, whose removal splits their component, as sorted label pairs: a ViewGraph's (i, j), i < j, an ObservationGraph's (a, b).
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.
VisualGeometryToolkitEstimation.chain — Function
chain(vg::ViewGraph, root; compose = *, inverse = inv, identity) -> DictAbsolute 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).
VisualGeometryToolkitEstimation.triangles — Function
triangles(vg::ViewGraph) -> Vector{NTuple{3}}The 3-cycles (i, j, k), i < j < k, every pair an edge, sorted.
VisualGeometryToolkitEstimation.filter_cycles — Function
filter_cycles(vg::ViewGraph; tol, residual = rotation_loop_angle, keep_untested = true) -> ViewGraphThe 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).
VisualGeometryToolkitEstimation.rotation_loop_angle — Function
rotation_loop_angle(ij, jk, ik) -> Float64The 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).
VisualGeometryToolkitEstimation.filter_by_orientation — Function
filter_by_orientation(vg::ViewGraph, world_from; tol) -> ViewGraphThe 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.
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).