Gaetan Bahl

Mehdi Bahri
email: m.bahri@imperial.ac.uk

Florent Lafarge
email: florent.lafarge@inria.fr

Single-Shot End-to-end Road Graph Extraction

Automatic road graph extraction from aerial and satellite images is a long-standing challenge. Existing algorithms are either based on pixel-level segmentation followed by vectorization, or on iterative graph construction using next move prediction. Both of these strategies suffer from severe drawbacks, in particular high computing resources and incomplete outputs. By contrast, we propose a method that directly infers the final road graph in a single pass. The key idea consists in combining a Fully Convolutional Network in charge of locating points of interest such as intersections, dead ends and turns, and a Graph Neural Network which predicts links between these points. Such a strategy is more efficient than iterative methods and allows us to streamline the training process by removing the need for generation of starting locations while keeping the training end-to-end. We evaluate our method against existing works on the popular RoadTracer dataset and achieve competitive results. We also benchmark the speed of our method and show that it outperforms existing approaches. Our method opens the possibility of in-flight processing on embedded devices for applications such as real-time road network monitoring and alerts for disaster response.

Introduction

Vector-based maps are heavily used in Geographic Information Systems (GIS) such as online maps and navigation systems. The extraction of roads from overhead images has been, and mainly still is, performed by expert annotators. For a long time, handcrafted methods have been developed with the aim of reducing the burden of the annotators. However, they were not precise enough to replace them. Indeed, their outputs were imperfect and had a high dependence on user-adjustable parameters [START_REF] Lian | Road extraction methods in high-resolution remote sensing images: A comprehensive review[END_REF]. In recent years, the availability of large amounts of data [START_REF] Russakovsky | Imagenet large scale visual recognition challenge[END_REF], combined with the increase in compute capabilities, has led to a rise in the popularity of deep learning methods based on Convolutional Neural Networks [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]. Modern road extraction methods mostly fall into two kinds of approaches, each Figure 1. Result of our method on an image from the Road-Tracer [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF] test set. Our method regresses an entire graph without the need of pre or post-processing. This 8192x8192 pixel image was processed in 22 seconds on a single GPU, which is up to 91 times faster than previous approaches. The extracted graphs have a low complexity and retain good accuracy compared to existing works.

coming with its own drawbacks. The first kind [START_REF] Batra | Improved road connectivity by joint learning of orientation and segmentation[END_REF][START_REF] Mattyus | Deeproadmapper: Extracting road topology from aerial images[END_REF][START_REF] Zhang | Road extraction by deep residual u-net[END_REF][START_REF] Zhou | D-linknet: Linknet with pretrained encoder and dilated convolution for high resolution satellite imagery road extraction[END_REF] relies on a pixel-based segmentation which is then converted to a graph using compute-intensive handcrafted algorithms that require a lot of manual tuning and can often yield partial graphs. The production of raster road masks using neural networks is a computationally expensive task in itself because of the large number of layers required to retrieve a segmentation that has the same resolution as the input image. Iterative graph construction methods are the second kind of deep learning based methods for road extraction [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF][START_REF] Li | Topological map extraction from overhead images[END_REF]22,[START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF]. These approaches explore the map from an initial starting location using successive applications of a neural network on patches centered on the current point to predict the location of the next point (i.e. next move pre-diction). While having the advantage of directly inferring a graph, this is a very slow process. In addition, several starting locations may need be picked in order to cover the possible multiple connected components of the final graph.

Our approach aims to solve the aforementioned issues of current deep learning based methods by offering a fast and convenient way to extract roads from satellite or aerial images. Inspired by recent advances in neural networks for object detection [START_REF] Zhi Tian | Fcos: Fully convolutional one-stage object detection[END_REF], we design a fully convolutional detection head that learns to precisely locate multiple points of interest such as intersections, turns, and dead ends across the whole image in a single pass. Node features attached to these points are simultaneously regressed by this head, and fed to a Graph Neural Network (GNN) which predicts links between them to form the final graph without requiring any post-processing. Both networks are jointly trained end-to-end from ground truth road graphs, which are widely available from sources such as OpenStreetMap. We benchmark our method against state-of-the-art approaches on the RoadTracer [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF] dataset and find that it is orders of magnitude faster than recent competing methods while retaining competitive accuracy.

With the increasing interest in deep learning inference on embedded hardware, such as satellites or drones [START_REF] Bahl | Low-power neural networks for semantic segmentation of satellite images[END_REF], our method, combined with recent advances in CNN and GNN quantization [2,[START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF], opens the possibility of on board inflight road extraction, which could reduce ground computation and bandwidth needs by transmitting graphs instead of images. Real-time road network monitoring is also a future possibility which would greatly benefit applications such as disaster response, by rapidly obtaining and transmitting updated maps to facilitate evacuation (e.g. in the event of a flood or earthquake).

The main contribution of our work is threefold. First, we propose a fast fully convolutional method for precise localisation of points of interest. Second, we design a Graph Neural Network for road link prediction. Third, we propose a performance-oriented architecture highly competitive against state-of-the art approaches.

Related Works

Detection Neural Networks

In recent works, Convolutional Neural Networks (CNN) such as VGG [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] or ResNet [START_REF] He | Deep residual learning for image recognition[END_REF] which were originally used for image classification, are stripped of their final classifier and repurposed as fully convolutional feature extractors (often called backbones) for other computer vision tasks, such as semantic segmentation [START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF]. Object detection methods such as YOLO [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF] or FCOS [START_REF] Zhi Tian | Fcos: Fully convolutional one-stage object detection[END_REF] have taken advantage of the fully convolutional nature of these backbones to design very fast single stage object detection neural networks, which infer bounding boxes and classes in a single forward pass and can be trained end-to-end, as opposed to two-stage approaches that perform these tasks separately. Single-stage architectures often follow a similar structure composed of a backbone which extracts features, a neck outputting feature representations at different scales [START_REF] Lin | Feature pyramid networks for object detection[END_REF], and several detection heads performing the final task.

Road Extraction

A large number of unsupervised methods have been developed for road graphs extraction. We refer the reader to recent extensive surveys on the subject for more information [22]. In this section, we focus on recent road extraction methods based on deep learning. Early deep learning based methods for road extraction were patch-based applications of fully connected neural networks [START_REF] Mnih | Learning to detect roads in high-resolution aerial images[END_REF]. However, most recent neural network-based methods proceed differently and can be sorted into two groups.

The first group of methods is based on pixel-level segmentation. Inspired by the success of FCN [START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF] and U-Net [START_REF] Ronneberger | Unet: Convolutional networks for biomedical image segmentation[END_REF], these methods use a backbone as an encoder and learned upscaling as a decoder to retrieve a classification of individual pixels of an input image. In [START_REF] Zhang | Road extraction by deep residual u-net[END_REF], residual connections are added to a U-Net to improve road predictions. D-LinkNet [START_REF] Zhou | D-linknet: Linknet with pretrained encoder and dilated convolution for high resolution satellite imagery road extraction[END_REF] adapts the LinkNet architecture to form a U-Net-like network and achieve better connectivity. DeepRoadMapper [START_REF] Mattyus | Deeproadmapper: Extracting road topology from aerial images[END_REF] uses a ResNet-based [START_REF] He | Deep residual learning for image recognition[END_REF] FCN to produce a segmentation which is then converted to a graph using thinning and an additional connection classifier. In [START_REF] Batra | Improved road connectivity by joint learning of orientation and segmentation[END_REF], the authors improve the connectivity of extracted networks by jointly learning the segmentation and orientation of roads. All segmentation-based approaches have the drawback of relying on post-processing techniques such as morphological thinning to convert the predicted road pixels to a road graph. Thus, these methods are slow and the final graphs can lack connectivity.

The second kind of approaches iteratively construct a graph from an initial starting point by successively applying a neural network that predicts the location of next point of the graph on a patch around the current point. These methods are inspired by the way human annotators iteratively create road graphs. In [START_REF] Ventura | Iterative deep learning for road topology extraction[END_REF], a network predicts which points from the border of the output patch are linked to the center point. RoadTracer [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF] uses a CNN to predict the direction of the next move with a fixed step size. PolyMapper [START_REF] Li | Topological map extraction from overhead images[END_REF] uses a Recurrent Neural Network (RNN) guided by segmentation cues to predict the road topology and building polygons. VecRoad [START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF] implements a variable step size for next move prediction in order to achieve better alignment of intersections. DeepWindow [22] estimates the road direction along a center line regressed by a CNN using a Fourier spectrum analysis algorithm. While these methods have the advantage of outputting a road graph directly, they cannot guarantee the exploration of the whole map from a single starting location. The choice of initial starting locations is a hard problem in itself. Moreover, the repeated application of CNNs makes these approaches very slow.

Relational Inference and GNNs

Graph Neural Networks (GNNs) [33] are effective models for encoding interactions, and have recently been applied to link prediction [START_REF] Zhang | Link Prediction Based on Graph Neural Networks[END_REF], relational structure discovery, such as to model the dynamics of complex systems [START_REF] Kipf | Neural relational inference for interacting systems[END_REF], and to the modeling of relational knowledge [START_REF] Schlichtkrull | Modeling relational data with graph convolutional networks[END_REF]. Kipf and Welling [START_REF] Thomas | Variational graph autoencoders[END_REF] proposed a graph autoencoder using a Graph Convolutional Network (GCN) encoder [17] and a simple dot-product decoder to model undirected networks and applied it to the link prediction task. Follow-up work [START_REF] Schlichtkrull | Modeling relational data with graph convolutional networks[END_REF] models different edge types in relational data using a graph neural network encoder and a decoder based on the DistMul [START_REF] Yang | Embedding entities and relations for learning and inference in knowledge bases[END_REF] factorization. In [START_REF] Kipf | Neural relational inference for interacting systems[END_REF] the authors propose a messagepassing [START_REF] Gilmer | Neural message passing for quantum chemistry[END_REF] encoder that alternates between the computation of node and edge features that can later be leveraged to predict the evolution of the system of interest several time steps in advance. The aforementioned models assume the ground-truth graph is partially known, or operate on the complete graph as an uninformative prior [START_REF] Kipf | Neural relational inference for interacting systems[END_REF]. A parallel line of work is that of learning the unknown graph explicitly. The Dynamic Graph CNN model [START_REF] Wang | Dynamic Graph CNN for Learning on Point Clouds[END_REF] proposes to dynamically build a graph by k-NN search in the feature space after each application of the EdgeConv operator also introduced in [START_REF] Wang | Dynamic Graph CNN for Learning on Point Clouds[END_REF]. The approach has been extended in [START_REF] Kazi | Differentiable graph module (dgm) for graph convolutional networks[END_REF], where the authors address the question of the differentiable construction of a discrete graph using the recently proposed Gumbel Top-k trick [START_REF] Kool | Stochastic beams and where to find them: The gumbel-top-k trick for sampling sequences without replacement[END_REF] -a stochastic and differentiable relaxation of k-NN search -and decouple the construction of the graph and the learning of graph features amenable for downstream tasks. With the introduction of deeper architectures [START_REF] Gong | Geometrically principled connections in graph neural networks[END_REF][START_REF] Li | DeepGCNs: Can GCNs go as deep as CNNs?[END_REF] came increased interest for efficient implementations of GNNs, an issue relevant to our work as on-board processing of satellite images, such as for road graph extraction, is a pressing issue. [START_REF] Wang | Bi-GCN: Binary Graph Convolutional Network[END_REF] applied bucketbased quantization of matrix-matrix products to accelerate the GCN [17] operator. [2] proposed a general framework for binarizing graph neural networks and introduced efficient binarized versions of the Dynamic EdgeConv operator [START_REF] Wang | Dynamic Graph CNN for Learning on Point Clouds[END_REF] with real-world speed-ups on a low-power device.

Method

In this section, we present our method based on a fully convolutional head for regression of points of interest and a Graph Neural Network (GNN) for link prediction. An overview of our method is available in Figure 2.

General architecture

Our neural network architecture follows the trend of using a pre-trained CNN as a feature extractor (backbone). We choose to work at a single level of detail and thus feed the output feature maps of the feature extractor directly to a single head. Using a single head allows us to save computation time and to make the training process more streamlined. Indeed, we remove all ground truth assignment complications that arise when using multiple heads.

Each branch of our head is composed of three convolutional layers working on N feat feature maps. The first two branches are the junction-ness and offset branch, which form the point-of-interest detection model. The third branch is a node feature branch, which computes features that will be used to predict links between points detected by the "point-of-interest" branch.

Let H I , W I be the dimensions of the input RGB image I ∈ R H I ×W I ×3 . We call "detection cells" the pixels of the final output feature maps of the point-of-interest detection network. With the ResNet-50 [START_REF] He | Deep residual learning for image recognition[END_REF] backbone used in our experiments, the height and width H, W of the input feature maps F in ∈ R H×W ×Nin are 32 times smaller than the ones of I. This means that the final layers of our head have H × W output cells. In the case of an input image size of 512 × 512 pixels, for example, we thus obtain 16x16=256 output cells, which can each regress the position of one point.

Point detection branch

Our point of interest detection branch, shown in Figure 2 is inspired by recent developments in single shot detection neural networks [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF][START_REF] Zhi Tian | Fcos: Fully convolutional one-stage object detection[END_REF], which regress a bounding box for each output "cell" of a detection head, even if they do not necessarily contain an object. This allows object detection to be performed using very fast Fully Convolutional Networks. These methods represent bounding boxes as offsets relative to the center of the cell regressed by a first output and filter the detected objects using a second separate output. We adapt this design to the regression of points of interest by outputting a "junction-ness" score J j for each output cell j (middle of Figure 2), as well as a two-dimensional vector o j = [u j , v j ] ∈ [-0.5; 0.5] 2 representing the offset of the regressed point with respect to the center of its cell (top of Figure 2). A point p j is detected in an output cell j if J j > J thr , where J thr is the junction-ness detection threshold. We can retrieve the coordinates (x j , y j ) of p j in the original input image:

x j = u j + X j + 0.5 W • W I , y j = v j + Y j + 0.5 H • H I (1)
where (X j , Y j ) are the coordinates of the cell j in the output feature map F out . The "junction-ness" and offset ground truths are generated on the fly during data loading by reversing Equation 1 using the sub-graph covered by each input patch.

Edge prediction

Once junctions have been extracted from the image, our task is to predict links between connected points of interest. This is a relational inference -or a latent graph learningproblem which we solve with a graph neural network. Starting with an initial prior connectivity estimation -i.e. a set of edges -E 0 , we aim at both inferring missing edges and discarding irrelevant ones to learn the true road graph.

Formally, let j be one of the detected junctions. We denote by X j = F out j the corresponding features in the output feature map of the backbone, and p j = (x j , y j ) the 2D Cartesian coordinates of the junction in the input image, computed from the offset vectors.

Our method computes initial node embeddings

x j = f (X j , p j ).
(2)

We choose the function f to be either a 2D Convolutional Neural Network defining an additional node features branch responsible for dimensionality reduction and transformation of the raw image features, or the identity. In the latter case the task of transforming the raw image features is left to the GNN. We then perform several (e.g. three) message-passing iterations using the EdgeConv operator [START_REF] Wang | Dynamic Graph CNN for Learning on Point Clouds[END_REF]:

e (l) ij = ReLU θ (l) (x (l-1) j -x (l-1) i ) + ϕ (l) x (l-1) i (3) = ReLU Θ (l) X(l-1) (4)
x

(l) i = max j∈N (i) e (l) ij (5)
followed by Batch Normalization, where X(l-1) = x

(l-1) i || x (l-1) j -x (l-1) i
, θ and ϕ are trainable weights, and Θ their concatenation. The resulting increase in receptive field allows for connectivity patterns to be learned based on both local image and graph properties, and shared context across junctions.

Finally, each possible edge is scored using a simple scoring function g applied on the final node features of the graph. Edge features must be computed explicitly for all possible edge, we therefore choose node features to prevent combinatorial explosion. We note

p ij = σ(g(x i , x j )) (6)
the inferred probability that the edge e ij exists, where σ is the sigmoid function. In practice, we choose g to be either a single bilinear layer, i.e. or a multi-layer MLP classifier (please refer to the supplementary material for more details and comparison with other decoders such as the dot product).

g(x i , x j ) = x T i W g x j (7)
Connectivity estimation Our choice of operator is motivated by the fact that the connectivity is unknown, and therefore we may initialize the graph learning process with the complete graph (i.e. considering all possible connections between junctions), or introduce a sparse prior by building the graph dynamically by k-NN search in feature space. We also considered the case where the initial graph is complete, while subsequent iterations of message passing are done on dynamically inferred connectivity. We choose k = 4 motivated by the observations that junctions with more than four incident roads are rare. To verify this intuition, we trained a model using a three-layer (2D convolutions followed by Batch Normalization and ReLU activations) node features head and an MLP classifier for each possible edge. The model was trained to convergence, and the four nearest neighbours graph was built on the output of the node features branch. The resulting graph is shown in Figure 3, and demonstrates that a high quality sparse initialization of the connectivity can be obtained in this manner.

Loss function

To train our neural network our loss function is defined as a sum of three terms:

L = L jun + L off + L edge ( 8
)
where L jun and L edge are the binary cross-entropy loss which we use to train our junction-ness branch and our edge prediction Graph Neural Network. L off is a Mean Squared Error offset loss masked with the positive junction predictions, which we use to train our offset regression branch. We define it as:

L off = 1
1 Ji,j >J thr i,j 1 Ji,j >J thr (v i,j -V i,j ) 2 (9)

Where V is the ground truth offset vector field. The mask is used so that the predictions of the offset branch are not conditionned to the presence of nodes.

Experiments

In this section, we compare our method against other road extraction approaches on the widely-used RoadTracer dataset [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF], which is composed of 35 training cities (180 images of 4096x4096 pixels) and 15 test cities of 8192x8192 pixels. The low number of training images, low ground sampling distance, high resolution and high annotation density of this dataset make it quite challenging. For iterative methods [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF][START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF], we used the starting locations hard-coded into the provided code.

Implementation details

We implement our method in the Pytorch 1.9.1 [START_REF] Paszke | Pytorch: An imperative style, high-performance deep learning library[END_REF] framework based on CUDA 11. We choose a ResNet-50 backbone (thus N in = 2048) and N feat = 256. We perform edge classification on the complete graph (other cases included in the supplementary material) using a three-layer GNN and a 2-layer MLP scoring function. J thr is set to 0.5 for the main results. We use basic data augmentation techniques such as random flips, and train our network on 512x512 pixel random crops for 2350 epochs, which took 24 hours on our system with a single Nvidia RTX 3090 GPU with 24GB of VRAM, an AMD Ryzen 9 3900X CPU and 64GB of RAM. We use the Adam [14] optimizer with a learning rate of 1e -3 . We did not use any loss balancing.

We also run performance benchmarks. All numbers were obtained on a computer with two Intel Cascade Lake 6248 20-core CPUs, 192GB of RAM, and four Nvidia Tesla V100 GPU with 16GB of VRAM. 10 CPU cores, a single GPU, and a quarter of the available memory were assigned to each run.

Choice of input resolution

By design, our method is only able to find a single point of interest by output cell and is directly trained on ground truth annotations. However, depending on the dataset, and especially in very dense neighborhoods, several ground truth points may fall into the same cell. We chose that these points would effectively be merged into their centroid, while keeping incoming edges from outside of that cell linked to that new point. However, this situation should be avoided as much as possible, since it can shift intersections, Ours RoadTracer [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF] DeepRoadMapper [26] Figure 4. Comparison of our method against an iterative method [3] and a segmentation based method [START_REF] Mattyus | Deeproadmapper: Extracting road topology from aerial images[END_REF] on a challenging area of the RoadTracer dataset. The first line is the full image. The second line shows crops of the regions in red squares. Our method is able to find more roads, even in sections that are completely missed by other methods.

and link close points that should not be linked (e.g. parallel roads). Images are often resized when being forwarded through a neural network, as a compromise between speed, memory and accuracy. In our case, the resizing ratio has to be chosen carefully according to the ground sampling distance (GSD) of the dataset and the density of ground truth annotations. To estimate the correct ratio for each dataset, we evaluate the average number of points in each positive cell over the whole dataset, at a wide range of ratios. This average should be as close to one as possible, in order to limit the effects of point merging. Figure 5 shows this average for the popular RoadTracer [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF], SpaceNet3 [START_REF] Van Etten | Spacenet: A remote sensing dataset and challenge series[END_REF] and Massachussetts roads [START_REF] Mnih | Machine learning for aerial image labeling[END_REF] datasets.

Qualitative results

Figure 4 shows qualitative results against an iterative method and a segmentation-based method. Our method is able to find a noticeably larger number of roads than Road-Tracer [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF] and DeepRoadMapper [START_REF] Mattyus | Deeproadmapper: Extracting road topology from aerial images[END_REF] in this challenging image. We can also notice that there are a few areas with low connectivity compared to RoadTracer. Indeed, since their network "walks" through the entire regressed graph, it is inherently made of a single connected component. However, the result of RoadTracer is missing entire portions of the city (e.g. top left) because they are separated from the starting position by a highway that the network was not able to cross during its exploration. Our method does not suffer from such limitations. More qualitative results are available in Figure 1 and in supplementary material.

Quantitative evaluation

We follow the literature and use the three metrics defined in [START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF] to evaluate the accuracy of our network. P-F1 is a pixel-based F1 score obtained by comparing the rasterized output graph and ground truth. J-F1 is a junction-based F1 score based on local connectivity. APLS is the Average Path Length Similarity defined in the SpaceNet challenge [START_REF] Van Etten | Spacenet: A remote sensing dataset and challenge series[END_REF] and is based on the comparison of shortest paths in the predicted graph and the ground truth.

The results of our testing are shown in Table 1. Our method achieves results which are competitive with Deep-RoadMapper [START_REF] Mattyus | Deeproadmapper: Extracting road topology from aerial images[END_REF] and RoadTracer [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF]. It is however outperformed by VecRoad [START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF]. Our intuition is that VecRoad "brute-forces" these metrics by regressing a lot more points and edges than our method, as shown in Section 4.6 and Table 3. Iterative methods inherently yield a better connectivity as their output is always a single connected component. This is reflected in the scores.

Method

P-F1 J-F1 APLS DeepRoadMapper [START_REF] Mattyus | Deeproadmapper: Extracting road topology from aerial images[END_REF] 56

Performance benchmarks

Run-time is seldom mentioned in the road extraction literature, but it is a very important metric, especially as we move towards inference edges devices. Thus, we benchmark the performance of our method against other recent approaches with open source code. We remove data loading and output times from all methods because different libraries and formats were used and thus only account for pre-processing, inference and post-processing steps of each algorithm. We provide average performance numbers for a single 8192x8192 test image from the RoadTracer [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF] dataset, as well as numbers for the whole dataset (15 images), since some methods such as VecRoad [START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF] have optimizations for multiple-image inference. Our method can run on the whole dataset at once by performing the sliding window in batches, which is a bit faster. The results of this experiment are shown in Table 2 and Figure 6. We observe that iterative methods are much slower because of the repeated forward passes required for next move estimation. Segmentation methods are not particularly fast as well, as the upscaling computation performed by a learned decoder is very compute intensive, and the extra post-processing steps required for graph conver-sion are slow. Our method is the fastest one by a large margin and offers a very good compromise between accuracy and speed. Indeed, it achieves similar APLS scores as RoadTracer [START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF] while running 27 times faster. Our approach also beats the APLS scores of DeepRoadMapper [START_REF] Mattyus | Deeproadmapper: Extracting road topology from aerial images[END_REF] by a large margin while running 65 times faster. It has lower accuracy scores than VecRoad [START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF], however it is 91 times faster. Our method could be made even faster by using a smaller and more efficient backbone, such as ResNet-18 [START_REF] He | Deep residual learning for image recognition[END_REF] or DarkNet-53 [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF]. . APLS metric with respect to inference time for our method, compared to state-of-the art approaches. Our method is the fastest and offers a very good compromise between accuracy and speed.

Graph complexity

Another interesting metric which is seldom mentioned in the road extraction literature is the notion of graph complexity. Graphs are a sparse representation and are meant to use a lot less storage space than masks. Most algorithms commonly used on graphs (e.g. shortest path algorithms) have a complexity which depends on the number of nodes and edges of the graph. Thus, offering accurate graphs with a low number of unnecessary nodes and edges is also beneficial in terms of run-time of subsequent applications. To evaluate the complexity of the graphs regressed by our method and compare it to other approaches, we propose a complexity score (lower is better) which is simply the total number of graph elements (nodes and edges) divided by the APLS score. We use the APLS because it seems to be the most popular metric. This score represents the compromise between the accuracy and compactness of graphs.

The results of this experiment are shown in Table 3. We observe that our method obtains the lower complexity compared to VecRoad [START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF] and DeepRoadMapper [START_REF] Mattyus | Deeproadmapper: Extracting road topology from aerial images[END_REF]. This is mainly due to our sparse approach to the regression of junctions, as shown by the average number of nodes. In Figure 7, we show the way our method finds an optimal representation of a neighborhood compared to the very high number of nodes and edges found by VecRoad [START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF]. Our method achieves the lowest complexity compared to other approaches, which make it a good between accuracy and compactness of graphs.

Figure 7. Exemple of the low complexity of the graphs inferred by our method (left) compared to VecRoad [START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF] (right). Our method finds an optimal 4-node representation of this simple neighborhood, whereas iterative methods tend to find overly complex representations. Having graphs with a low number of elements will save storage and speed up the computation of algorithms performed on these graphs, such as shortest path algorithms.

Limitations

Our method comes with some limitations. The first one, as said in previous sections, is the difficulty to work in very dense areas with lots of intersections. Since multiple intersections might fall into the same detection cell, our network will only be able to detect one of them, which can lead to shifted junctions. Nevertheless, our method still works well on dense areas of Tokyo shown in Figure 4. The second limitation is the inability to be trained on mask-based datasets such as DeepGlobe [START_REF] Demir | Deepglobe 2018: A challenge to parse the earth through satellite images[END_REF] without converting the masks to graphs first. Finally, some long sections of road such as highways or bridges might lack points of interest since they do not have any junctions. Our network can miss these sections of road in the final graph as shown in Figure 8 and in some parts of Figure 1. This issue could be addressed by working at different scales using multiple heads or by adding virtual points-of-interest on long stretches of road.

Conclusion

We proposed a novel architecture for single-shot extraction of road graphs from satellite images. Our method first predicts sparse interest points using an image CNN feature extractor as well as a junction detection head, and an offset regression head, trained jointly to identify candidate road intersections in a lower-resolution image and predict their position in the high-resolution image. We then combine the extracted image features and regressed point coordinates with a graph neural network to combine local and global information and infer the unknown graph structure. Our method combines aspects of graph learning and link prediction to score candidate connections between road junctions and infer the road graph. We demonstrate competitive performance with state of the art methods on three reference metrics while achieving significantly lower graph complexity and inference times (up to 91x faster than iterative models) compared to iterative and segmentation-based methods.

Even though the experimental validation of our approach was focused on road networks, our single-shot graph extraction framework can be applied to other types of problems. An example would be the extraction of blood vessels in medical images [START_REF] Moazam Fraz | Blood vessel segmentation methodologies in retinal images-a survey[END_REF]. An interesting follow-up to road extraction could be to not only decide if edges exist or not in the final graph, but also infer edge attributes like road types, amount of traffic, or speed limits, as done in [9]. We also believe that our method could be adapted to tackle map update problems that have been presented in newly released datasets [START_REF] Bastani | Beyond road extraction: A for map update using aerial images[END_REF]. In addition, our method can further be combined with existing model compression techniques, both from the Euclidean [START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF] and Geometric [2] deep learning literature, to pave the way for on board single-shot extraction of road graphs on edge devices.

Figure 2 .

 2 Figure2. Our single-shot road graph extraction neural network. Features computed using a ResNet[START_REF] He | Deep residual learning for image recognition[END_REF] backbone are fed to three branches. The junction prediction branch identifies cells which contain points of interest and is trained with binary cross-entropy. The offset prediction branch regresses the precise location of these points inside of the cells by outputting a two-dimensional vector field and is trained with a Mean Squared Error loss. Points selected by the junction and offset branch are paired with node features from a third branch and fed to a Graph Neural Network which predicts the presence of edges between pairs of points to create the final output.

Figure 3 .

 3 Figure 3. k = 4-NN graph constructed in feature space on features learned by an additional node features head combined with an MLP edge classifier.

Figure 5 .

 5 Figure 5. Average ground truth points per positive output cell at a range of image resizing ratios for 3 popular road extraction datasets. The ideal average is one, to prevent the collapse of neighboring nodes as much as possible.

Figure 6

 6 Figure 6. APLS metric with respect to inference time for our method, compared to state-of-the art approaches. Our method is the fastest and offers a very good compromise between accuracy and speed.

Figure 8 .

 8 Figure 8. Examples of long sections of road without points of interest, which are occasionally missed by our method.

Table 1 .

 1 Accuracy metrics on the RoadTracer Dataset, evaluated using open source code from[START_REF] Tan | Vecroad: Point-based iterative graph exploration for road graphs extraction[END_REF] and[START_REF] Bastani | Roadtracer: Automatic extraction of road networks from aerial images[END_REF].

		.85	29.05	21.27
	RoadTracer [3]	55.81	49.57	45.09
	RoadCNN [3]	71.76	32.22	53.18
	VecRoad [36]	72.56	63.13	64.59
	Ours	57.2	39.23	46.93

Table 2 .

 2 Run-time in seconds on the RoadTracer Dataset. The single image score is averaged over the whole test set. Our method is the fastest by a large margin. *RoadTracer failed on some images, thus this number is extrapolated from the average.

	Method	Type Single image Whole dataset
	VecRoad [36]	Iterative	1902.5	8873.4
	RoadTracer [3]	Iterative	579.4	8690.5*
	DeepRoadMapper [26] Seg.	1361.6	20423.4
	RoadCNN [3]	Seg.	278.2	4172.4
	Ours	Graph	20.9	295.0

Table 3 .

 3 Comparison of average graph complexity scores (Total elements divided by APLS. Lower is better). Nodes (resp. Edges) is the average number of nodes (resp. edges) in the output graphs over the whole RoadTracer test set. DRM = DeepRoadMapper.

	Method	Nodes Edges Total APLS Complexity
	VecRoad [36] 29620 61042 90662 64.59	1404
	DRM [26]	6071 11963 18034 21.27	848
	RoadTracer [3] 8263 17044 25306 45.09	561
	Ours	4343 17273 21615 46.93	461

Acknowledgements G.B. is funded by the CIAR project at IRT Saint Exupéry. M. B. was supported by a Department of Computing scholarship from Imperial College London, and a Qualcomm Innovation Fellowship. The authors are grateful to the OPAL infrastructure from Université Côte d'Azur for providing resources and support. This work was granted access to the HPC resources of IDRIS under the allocation 2020-AD011011311R2 made by GENCI.