Invisible Map Generation

Overview

The backend is the halfway point between Invisible Map Creator and Invisible Map. It will pull the unprocessed maps from Firebase, optimize it, identify any new connections to be made, then give it back to firebase with the new data. It is written primarily in Python, with some supporting C code that should be abstracted away for the most part. The whole thing is run on a server that Paul has access to, which will run a script (process_graphs) whenever it detects a new map from Firebase. The pipeline is as follows:

1. FirebaseManager is notified of an update to Firebase, and downloads the map before handing it off to GraphManager
2. as_graph converts the raw JSON to a Graph object
3. This Graph can then convert itself to a SparseOptimizer, directly from the g2o library
4. GraphManager handles the optimization through the SparseOptimizer, pulling the new odometry and tag poses from the optimizer
5. graph_utils detects any intersections, giving the new list of neighbors to GraphManager
6. GraphManager compiles the new poses and neighbors into a dict
7. That dict is given to FirebaseManager to reupload so InvisibleMap can see it

Additionally, there are a few extra scripts for us to run manually:

1. graph_manager_user: manually download and process maps
2. correlate_metrics: determines the correlation between different metrics of ranking weights
3. optimize_weights: either runs a genetic algorithm or a sweep to determine the best set of weights to use
4. visualize_chi2: helps to see where error from chi2s are coming from

Graph

Graph is the main data structure the backend uses to contain any and all information about the map the user made. For the most part, it contains a list of type Vertex and a list of type Edge, along with a ton of functions for optimization, converting to a SparseOptimizer, and some utility functions to aid certain metrics.

Vertex

Vertex is a very basic wrapper class to represent a single vertex of a Graph. It has four attributes:

• mode: the type of Vertex this is, represented as a VertexType enum. Either:
• Odometry: representing a phone position
• Tag: representing the center of a tag
• Tag Point: representing the corner of a tag (for SBA)
• Dummy: representing a dummy node (see the As Graph section)
• Waypoint: representing a user-saved location
• estimate: a 7x1 ndarray, the estimated pose of this vertex with respect to the origin of Invisible Map Creator’s AR Session. This will update as the optimization runs, and as such can represent either the optimized or unoptimized estimate.
• fixed: a boolean, whether the estimate of this Vertex is allowed to be changed during optimization
• meta_data: a dict containing any other data this Vertex needs. Will contain
• For Tags and Tag Points, the id of the tag
• For Waypoints, the name of the saved location

In Graph, the vertices are stored in a dict of int to Vertex. Each key is a uid for the Vertex. While typically assigned in order (i.e. the dict is essentially a list), this is not necessarily the case, so make sure to watch out for this! Also note that these need to be converted to G2O’s own Vertex type before optimization; typically a VertexSE3Expmap ¹.

Edge

Edge is another wrapper class for Graph, containing the basic information needed to represent a connection between two vertices. Its attributes are:

• startuid: the UID of the first Vertex this edge connects
• enduid: the UID of the last Vertex this edge connects
• measurement: a 7x1 ndarray, the pose of the end Vertex relative to the start Vertex
• information: The omega matrix for G2O - typically a diagonal matrix of the weights
• (Optional) information_prescaling: Values to create a prescaling matrix for information, defaults to 6x1 of ones
• (Optional) corner_ids: For SBA, the uids of the corners of the tag
• (Optional) camera_intrinsics: For SBA, the matrix needed to convert pixels to position in space

Like Vertex, Edges are stored as a dict of int to Edge. In general, we refer to edges as “odometry edges”, “tag edges”, etc. This refers to the type of node it connects. Because of the way our mapping is set up, all edges are connected to at least one odometry node. This will always be the start node. Therefore, “odometry edge” is shorthand for “odometry-to-odometry edge” and “tag edge” is short for “odometry-to-tag edge”, etc. Note also that these are only our own edge types; when converting to G2O, these need to be converted to their own edge types. Most of the time, this will be EdgeSE3Expmap ².

Other Attributes

There are a few other items Graph will store. These include:

• _weights: a dict of weights to give to the optimizer. The dict between 4 and 5 elements:
• odometry: 6x1 ndarray, the weights for odometry edges
• tag: 6x1 ndarray, the weights for tag edges without SBA
• Does not have to be included for SBA optimization
• tag_sba: 2x1 ndarray, the weights for tag edges with SBA
• Does not have to be included for non-SBA optimization
• dummy: 6x1 array, the weights for dummy edges
• odom_tag_ratio: Specifies the ratio between the magnitude of the odometry weights and the tag weights. Currently unused in Graph, but see graph_utils.weight_dict_from_array and graph_utils.normalize_weights.
• original_vertices: a dict of uid to Vertex, containing the vertices as they were before optimization
• is_sparse_bundle_adjustment: a boolean, whether to perform SBA during optimization
• _verts_to_edges: a mapping of Vertex UIDs to a Set of Edge UIDs
• gravity_axis: which axis is up/down. Defaulted to ‘y’
• Anything with huber and damping: relating to Huber matrixes, unimportant for now
• errors, observations, and anything with maximization: relating to automatically tuning weights, unimportant for now
• unoptimized_graph: a g2opy.SparseOptimizer, the graph to optimize with G2O
• optimized_graph: a g2opy.SparseOptimizer, the resulting graph from G2O

Methods

Update Graph

• set_weights: sets the weights, scaling by the amount of edges each type has, if specified
• update_edges: updates each edge with the current set of weights
• update_vertices: updates the estimates of each Vertex to match the ones in optimized_graph
• delete_tag_vertex: deletes a tag vertex from all attributes, except the SparseOptimizer(s)
• remove_edge: removes an edge from all attributes, except the SparseOptimizer(s)

Chi Squared and Evaluation

• check_optimized_edges (static): calculates the total chi2 from a SparseOptimizer
• get_chi2_of_edge (static): calculates the chi2 from a specific g2opy edge
• get_chi2_of_edge_type: returns a dict containing the chi2 values for each type of edge
• map_odom_to_adj_chi2: given an odometry vertex, returns the chi2 from that vertex and the number of tag vertices connecting to that tag
• get_subgraph: returns a subgraph containing the vertices with UIDs between the given values. Used to partition a graph for Duncan's evaluation metric

Optimization

• generate_unoptimized_graph: sets unoptimized_graph to the result of graph_to_optimizer
• graph_to_optimizer: converts this Graph to a SparseOptimizer. Essentially, it pulls the data from vertices and edges, then creates g2opy objects from that information.
  • To actually optimize the Graph, see GraphManager.get_optimizer

While there are many other methods in Graph, the rest do not need to be rigorously explained. They are either utility methods, not typically called outside of Graph, or relate to weight tuning ("expectation maximization"), which is not important for now.

As Graph

as_graph essentially contains just one function: converting the raw JSON uploaded from Invisible Map Creator into a Graph object. While the code is long and looks complicated, most of it is simply setup for the final part: creating data structures for more efficient lookup of information. After pulling all of the edge and vertex information into these various structures, it loops through the odometry information, creating nodes for each point and the non-odometry nodes that connect to it, along with edges to connect for them.

The only odd portion of As Graph is the creation of dummy nodes. These were implemented as a solution to a problem involving bending of the graph. What would often happen was odometry orientation would be slightly off in successive measurements, causing the path to tilt up or down. When the G2O optimization was run on the graph, it would decide to change the orientation of the odometry nodes rather than the position to correct this tilt (think creating a U or V shape rather than moving points up or down to correct the tilt), resulting in a warped path rather than a straight one. This is because the error function only pays attention to te error between two adjacent nodes and the transformation between them, so warping the path appeared to the optimizer to be the best solution to minimize error, although this solution is obviously incorrect to the human eye.

Dummy nodes attempted to fix this by adding more nodes directly below the odometry nodes and giving them a very strong weight for orientation. This gave the optimizer incentive to leave the orientation the same and opt to move the position instead. Note that this solution was implemented before our more feasible weight sweeping methods, so it is possible that this issue is fixed by having better weights, though this is worth checking out (see To Do)

Graph Manager

GraphManager is the main class to handle anything to do with Graph, from optimization and evaluation to weight correlation. As such, there are many functions to cover.

Weight Evaluation and Comparison

As of 8/6/2021, there are three methods to evaluate a set of weights: ground truth, chi2, and Duncan's metric. Ground truth is based on physical measurements of tag locations relative to each other. Chi2 is the resulting chi2 from the graph optimization. While this is based on the weights, theoretically the weights should not matter so long as they are normalized properly. Duncan's metric is similar to chi2, thought it was originally created to try to subvert the issue with different magnitude weights. Below is a quick outline of the pros and cons of each:

The methods to calculate these are:

• compare_weights: runs Dunan's chi2 comparison metric on the weights specified in GraphManager.iter_weights, displaying and printing the results
• optimize_weights: runs a genetic machine learning model to attempt to find the best weights. As of 8/6/2021, it uses a ground truth metric based solely on tag positions, but this is easily alterable by changing the lambda expression given to the genetic algorithm.
• sweep_weights: sets up weight sweeping, running it through _sweep_weights (a recursive function). Can be based on any metric based on the input given to _sweep_weights
• get_chi2_from_subgraphs: runs Duncan's metric on a given Graph or a tuple of two Graphs without altering the Graph.
• get_chi2_by_edge_from_subgraphs: calculates Duncan's metric on a Graph as above, but instead returning the chi2 split by edge type
• create_graphs_for_chi2_comparison: splits a Graph into two sub-Graphs for Duncan's metric
• get_ground_truth_from_graph: given a Graph, a set of weights, and the ground truth positions of the tags, calculates the average difference between the tag positions in the optimized graph and the ground turht tag positions.
• _weights_to_dict: returns a set of weights through all the ways we have to represent weights. These are:
  • int: an index into GraphManager.ordered_weights_dict_keys
  • string: a key for GraphManager._weights_dict
  • float: a ratio between odometry magnitude and tag magnitude. Each weight within odometry magnitude and tag ratio will be the same
  • ndarray: see graphutils.weight_dict_from_array
  • dict: an already compiled weight dictionary
• plot_adj_chi2 (static): plots the chi2 across odometry edges (analogous to over time). Also plots the points in which at least one tag was visible.
• get_ground_truth_metric (static):: given the poses of the optimized tag locations and actual tag locations, calculates the avreage translational difference between them.

Optimize Graph

• process_maps: main function run to manually process graphs. Will optimize and optionally upload any maps whose file path matches the given pattern
• get_optimized_graph_info: calculates chi2 and the positions of the nodes for the optimized graph witout actually altering the Graph object
• get_optimizer: pulls the SparseOptimizer from the given Graph and optimizes it
• get_json_from_map_info: generates the JSON to give to InvisibleMap given the file path and name of the unoptimized map (stored in MapInfo)
• _map_info_from_path: generates a MapInfo object given the path of an unoptimized map
• _optimize_graph: optimizes a Graph, "committing" the changes to the Graph object. Optionally can run optimization multiple times, removing edges with chi2 values that are too high. By default, this will run the filter once if the original chi2 is greater than 1.
• plot_optimization_result: plots the original node locations, final node locations, and tag poses for an optimized Graph
• make_processed_map_JSON: given the poses of all the nodes, dumps the information into a dict to put in a JSON for Invisible Map

Any other functions in GraphManager are just helpers and do not require rigorous explanation.

Scripts

While only one script is run on the sever, we have many that we use for testing purposes. Only a brief overview of what each does will be given here; to actually find how to run them, see the code itself and the README. If any command line arguments are given, they will be created in the corresponding file in a function called make_parser.

Process Graphs

process_graphs.py is the script that the server runs. The script itself is fairly basic: it first sets up a FirebaseManager and a GraphManager. It creates a function that will be called whenever Firebase updates, which will pull the map info, optimize the map, create a json, and upload it. Finally, it the FirebaseManager tells Firebase to run that function whenever it is updated.

Graph Manager User

graph_manager_user.py is essentially the manual version of process_graphs. It does, however, have a few more options, such as the ability to set the weights and the prescaling option (these are defaulted in process_graphs). It also has th eability to display a visualization of the optimized graphs(s).

Optimize Weights

optimize_weights.py is a script that attempts to find the best set of weights. It has two options to accomplish this. The first (and default) is a genetic machine learning model. As of 8/6/2021, it can tune al 12 parameters, but it is likely worth it to have it only tune 3 (as specified by graph_utils.weight_dict_from_array). The second method is a parameter sweep, where the script will try every combination of values in a certain range and determine the best one. If the sweep is 2-D, it will also display a visualization of the surface the resulting metric creates.

Correlate Metrics

This script was created to try to measure how good each metric was, especially when compared to ground truth. It visualizes the metrics and calculates the Spearman Correlation between each. The Spearman Correlation is essentially a measure of correlation that does not rely on linearity - i.e. any monotonically increasing function will have a Spearman Correlation of 1, even if it is nonlinear. This also has the option of instead loading the correlations from a saved file so as to not have to recalculate.

Visualize Chi2s

This is a script used when chi2s are suspiciously high, especially when trying to find weights. It will optimize the graphs with several different weight values, and display the resulting chi2 from each edge type.