MFAS - GTSAM Docs

Created by Codex.

Find a one-dimensional ordering and outlier weights using the Minimum Feedback Arc Set (MFAS) heuristic from one-dimensional structure from motion (1DSfM).

Authors: Frank Dellaert, et al. (see THANKS for the full author list)

See LICENSE for the license information

Mathematical idea¶

MFAS means Minimum Feedback Arc Set. For an ordering $\pi$ of graph vertices, an edge $(i,j)$ is backward when $\pi(i)>\pi(j)$ ; the weighted objective is

\min_{\pi}\sum_{(i,j):\,\pi(i)>\pi(j)} w_{ij}.

(1)

The one-dimensional structure-from-motion (1DSfM) procedure projects translation directions onto a line, uses this ordering problem to expose inconsistent edges, and repeats over projection directions for robust outlier evidence.

try:
    import google.colab
    %pip install --quiet gtsam-develop
except ImportError:
    pass

import gtsam
import numpy as np

from gtsam import symbol_shorthand

C = symbol_shorthand.C
K = symbol_shorthand.K
P = symbol_shorthand.P
S = symbol_shorthand.S
X = symbol_shorthand.X

Translation-averaging use¶

MFAS projects world-frame translation directions onto a chosen Unit3. It flips negative projected edges, computes a node ordering, and marks edges that disagree with that ordering. computeOutlierWeights() returns zero for inliers and projected magnitude for detected outliers.

KeyPairDoubleMap is the C++ map type returned through the wrappers; Python receives a normal dictionary.

noise = gtsam.noiseModel.Isotropic.Sigma(2, 0.01)
edges = [
    gtsam.BinaryMeasurementUnit3(X(0), X(1), gtsam.Unit3(np.array([1.0, 0.1, 0.0])), noise),
    gtsam.BinaryMeasurementUnit3(X(1), X(2), gtsam.Unit3(np.array([1.0, 0.0, 0.0])), noise),
    gtsam.BinaryMeasurementUnit3(X(2), X(0), gtsam.Unit3(np.array([1.0, 0.0, 0.0])), noise),
]

mfas = gtsam.MFAS(edges, gtsam.Unit3(np.array([1.0, 0.0, 0.0])))
print("1D ordering:", mfas.computeOrdering())
print("outlier weights:", mfas.computeOutlierWeights())

1D ordering: [8646911284551352321, 8646911284551352322, 8646911284551352320]
outlier weights: {(8646911284551352320, 8646911284551352321): 0.9950371902099893, (8646911284551352321, 8646911284551352322): 0.0, (8646911284551352322, 8646911284551352320): 0.0}

Practical notes¶

One projection direction can miss outliers nearly orthogonal to it. A robust 1DSfM pipeline repeats the test over multiple directions and combines evidence before removing translation edges.

Source¶

MFAS.h