Long-term Visual Map Sparsification with Heterogeneous GNN

Many previous works have attempted to solve the long-term visual localization problem by finding robust feature descriptors against environmental changes [25] (such as day-night, lighting conditions, and seasonal changes). Concrete examples include R2D2 [19], SOSNet [24], PixLoc [21] and [1]. Some methods look into the dynamics of visual features (and the corresponding physical environment) such as persistency [8] and repeatability [6]. Besides learning robust features, some works also attempt to overcome the environmental challenges by finding common information in 2D and 3D, such as semantic information [26, 27] and predicting depth from query images [18]. In this work, instead of finding robust features, we focus on sparsifying the SfM map globally by taking the whole map graph structure into consideration. We use Kapture [11], a modern mapping and localization library using R2D2, to generate data and evaluate the proposed method.

For a map that contains redundant information of a world, the goal of map sparsification is to select the most valuable subset. In previous works, it is common to assume that the map contains all the possible camera positions, and formulate the map compression as a K-Cover problem, which encourages each possible camera position (the key frame location in the map) to observe enough 3D points for performing robust PnP during localization under a total point number budget. The K-Cover problem is then solved using various techniques: a probabilistic approach [5], Integer Linear Programming (ILP) [14, 7] and Integer Quadratic Programming (IQP) [17, 7, 15]. A hybrid map and hand-crafted heuristics were also used to determine the importance of map points [4, 13, 16]. These methods work well in a static world but suffer from performance degradation in vastly dynamic environments where many of the visibility edges in the map are outdated and invalidated.

Graph Neural Networks (GNNs) [10] have been applied to a variety of learning tasks with irregular data structures, such as citation graphs [29] and image visibility graphs [23]. An important advantage of Graph Neural Networks is the ability to handle heterogeneous data [31]. In this work, we represent the various information in SfM maps with heterogeneous graphs and extract features with a GNN. Recently, attention-based networks have shown strong performance in feature extraction from not only sequential data [28] but also graph structures such as 2D-3D matching [20]. Inspired by these works, we investigate the combination of heterogeneous GNN and attention, and demonstrated better final performance than the baselines.

A heterogeneous graph by definition is a graph structure that contains different types of nodes or edges. To represent an SfM map, three types of nodes are defined: 3D point nodes $\mathcal{V}_{p}$, 2D key point nodes $\mathcal{V}_{k}$, and image nodes $\mathcal{V}_{m}$. We also define three types of edges: visibility edges $\mathcal{E}_{v}$ connecting corresponding $\mathcal{V}_{p}$ and $\mathcal{V}_{k}$, kNN edges $\mathcal{E}_{n}$ connecting each $\mathcal{V}_{p}$ and its k nearest neighboring $\mathcal{V}_{p}$, and containing edges $\mathcal{E}_{c}$ connecting each $\mathcal{V}_{k}$ to the corresponding image $\mathcal{V}_{m}$. Each $\mathcal{V}_{p}$ might be connected to multiple $\mathcal{E}_{v}$s and $\mathcal{V}_{k}$s because it is observed by multiple map images. The SfM map is then represented with a heterogeneous graph $\mathcal{G}=\{\mathcal{V}_{p},\mathcal{V}_{k},\mathcal{V}_{m},\mathcal{E}_{v},\mathcal{E}_{n},\mathcal{E}_{c}\}$. An illustration of our map graph is shown in Fig. 3(a)(b).

The per-point importance score is predicted based on local appearance and spatial context. We design our map graph to provide the information: first, the local appearance data are stored in $\mathcal{V}_{k}$ by embedding the key point descriptors extracted at the map building stage. Second, the spatial context is captured in kNN edges $\mathcal{E}_{n}$, which are derived from the 3D point positions stored in $\mathcal{V}_{p}$. The image nodes $\mathcal{V}_{m}$ do not carry features, but are used to trace connected $\mathcal{V}_{k}$ and $\mathcal{V}_{p}$ for ensuring the GNN selects enough number of $\mathcal{V}_{p}$ in the field-of-view of each $\mathcal{V}_{m}$, as shown in Fig. 3(c).

In practice, we store two sets of $\mathcal{V}_{k}$, $\mathcal{V}_{m}$, $\mathcal{E}_{v}$, and $\mathcal{E}_{c}$ in the map graph: one set is from the map and the other set is from localizing the query set on the map before sparsification. The first set is fed to the proposed GNN to provide information for score prediction. The second set is only available in the training area, and was only used to generate the point selection labels $L_{gt}$ stored in $\mathcal{V}_{p}$ (Sec. 3.4).

Note that all the graph edges described above are directional. To be specific, $\mathcal{E}^{ji}_{n}$ represents a kNN edge from a neighbor $\mathcal{V}_{p}^{j}$ to the $\mathcal{V}_{p}^{i}$, and $\mathcal{E}^{wi}_{v}$ shows a visibility edge from key point $\mathcal{V}_{k}^{w}$ to map point $\mathcal{V}_{p}^{i}$, where $i,j,w$ are node indices. The directionality of edges is useful in retrieving local subgraphs during network training (Sec. 3.3).

To extract the spatial context from the map, we propose to aggregate the features from locally connected 3D point nodes with a Graph Attention Network (GATConv) [30, 29]. For a 3D point node $\mathcal{V}_{p}^{i}$, a GATConv layer is applied to fuse the input node features and predict an output node feature. Formally, the GATConv operation is:

where $\mathbf{h}_{j}\in\mathbb{R}^{F}$ is an input feature from $\mathcal{V}_{p}^{j}$ to node $\mathcal{V}_{p}^{i}$ with feature dimension $F$. The input features are from the $\mathcal{V}_{p}^{i}$ itself and the kNN nodes, where $j\in\{1,2,\dots,k,i\}$ and $k$ is the number of kNN nodes. The $\mathbf{W}^{h}\in\mathbb{R}^{F^{+}\times F}$ is a shared weight matrix, $\alpha^{h}_{ij}$ is the normalized attention coefficient, $H$ is the number of attention heads, $a(.):\mathbb{R}^{F^{+}}\times\mathbb{R}^{F^{+}}\rightarrow\mathbb{R}$ computes the attention coefficients. We aggregate the multi-head GATConv outputs by simple summation. The output $\mathbf{h}_{i}^{+}\in\mathbb{R}^{F^{+}}$ is the output feature with dimension $F^{+}$ stored on $\mathcal{V}_{p}^{i}$. Empirically, we found this GATConv outperformed GraphConv[12] and SAGEConv [10] for our application.

We design a heterogeneous GNN to extract features and perform score prediction from the aforementioned map graph. The motivation is that the key point descriptors, although not raw pixel values, still contain valuable appearance information, enabling us to infer the 3D point scores from the connected 2D key point descriptors. The heterogeneity here enables us to define different operations according to the node and edge types.

Our GNN comprises three stages: 1) a descriptor gathering layer $g_{1}$, 2) a local feature extraction layer $g_{2}$, and 3) a final Multilayer Perceptron (MLP) layer $g_{3}$. In $g_{1}$, we trace the connected $\mathcal{E}_{v}$ for each $\mathcal{V}_{p}$ to collect the connected key point descriptors stored in $\mathcal{V}_{k}$. The collected descriptors are sent to a Graph Convolutional layer (GraphConv) [12] with LeakyReLU activation and summation aggregation functions. The output of $g_{1}$ is an aggregated point feature $\mathbf{f}_{desc}$ carrying the local appearance information. In $g_{2}$, we use the GATConv layer (Sec. 3.2) to gather the nearby point features from the kNN $\mathcal{V}_{p}$, generating a local feature $\mathbf{f}_{knn}$ that captures spatial context. Finally, a 3-layer MLP $g_{3}$ is used to convert the point feature dimension to 1 and a sigmoid layer is used to constrain the predicted score value $s$ to $[0,1]$. The network structure is shown in Fig. 3(d).

Let $i,j\in\{1,2,\dots,N_{p}\}$ denote the map point indices and $w\in\{1,2,\dots,N_{k}\}$ be a key point index, where $N_{p}$ and $N_{k}$ are the total number of map points and key points. Let $\mathcal{G}$ denote the map graph, the score prediction steps are:

where $\mathbf{h}_{i}=\mathbf{f}_{desc}^{i}$ and $\mathbf{h}_{i}^{+}=\mathbf{f}_{knn}^{i}$ in Eq. 1.

To facilitate GNN training on large-scale graphs, we sample a $\mathcal{V}_{m}$ to extract a local subgraph for each training batch and only run our GNN on the local subgraph. Given a $\mathcal{V}_{m}$, we first extract the connected $\mathcal{V}_{k}$ by tracing $\mathcal{E}_{c}$. Afterwards we trace $\mathcal{E}_{v}$ and $\mathcal{E}_{n}$ to extract the corresponding $\mathcal{V}_{p}^{i}$ and its neighbors. Finally, we trace the $\mathcal{E}_{v}$ connecting to the neighboring $\mathcal{V}_{p}^{j}$ for computing the neighboring $\mathbf{f}^{j}_{desc}$.

Our losses promote high scores on points with two properties: first, the descriptor distribution of the selected points should align with the descriptors that are useful for training query localization. Second, the selected points should cover all the possible viewing poses, so that all the queries would observe a sufficient amount of points within the field-of-view. We propose a training loss with two terms:

For the maps we evaluated with, we found the computation of ILP formulation is tractable to process the whole map. It is also possible to use IQP [17] for label generation, but in practice IQP is computationally intractable to run on large-scale maps without additional graph partition steps. The potential effect of graph partition on localization performance is beyond the focus of this paper.

By adding both terms, we propose the final loss as:

The data split and usage is summarized in Tab. 1. Note that the training and testing queries are spatially non-overlapping and the pre-built map covers both the train and test areas. The role of the training queries is to provide up-to-date appearance information that cannot be obtained from the outdated map data, as we focus on the temporal appearance difference. In this case, the training and testing data should not overlap spatially but can overlap temporally.

For each map sparsification method, we first obtained its point selection result, and reconstructed the multi-session map in Kapture format with only the the key points and descriptors that correspond to the selected points. We used the number of point descriptors remaining in the map (#kpts) as map size proxy, since these high-dimension descriptors (e.g., 128 for R2D2) occupied most of the map storage space. Three baselines were compared:

• •

  Random : randomly select a subset of map points up to the allowed budget.

• •

  ILP (map) : the conventional ILP [14], which assembles the K-Cover problem with 1) the visibility edges stored in the map, and 2) the per-point weight based on number of observations in the map.

• •

  ILP (query) : the ideal ILP [14] that has access to test queries. The K-Cover problem is constructed using visibility edges from localizing the test queries on the map before sparsification, and points are weighted according to the number of observations during the test query localization. This approach indicates the ideal performance of ILP approach without environmental changes and cannot be achieved in the real world.

We obtained data points by sweeping the desired total point number $n_{desired}$[14]. For our method, we randomly selected points with predicted scores larger than 0.1. If there were not enough points with scores larger than 0.1 to satisfy $n_{desired}$, we randomly selected from the rest of the points. We observed that predicted score distribution is close to binary (due to the $L_{1}$ norm sparsity loss) and the point selection result is not sensitive to the score threshold.

Overall, our proposed approach outperformed the ILP (map) baseline in all the testing slices by achieving higher localization recall (success rate) under the same map sizes, as shown in Tab. 2 and Fig. 6. Qualitatively, we observed that compared with the ILP (map) baseline, the proposed method selects map points on static structures that are more useful for query set localization, as in Fig. 7 and Fig. 8.