Sovann En

Alexis Lechervy

Frédéric Jurie

COMBINING MODALITY SPECIFIC AND COMMON FEATURES FOR MULTIMODAL PATCH MATCHING

Keywords: Multimodal Patch Matching, Siamese network, Deep Metric Learning

published or not. The documents may come

INTRODUCTION AND RELATED WORK

Patch matching, the task consisting in determining the correspondences between image patches, is essential for many computer vision problems, i.e., multi-view reconstruction, structure from motion, object-instance recognition, etc. In this work, we aim to study the problem of matching patches in a multimodal setting where input patches come from different sources, i.e. RGB images vs hand-drawn sketches or RGB vs near-infrared images.

Broadly speaking, there are two main ways to design local patch matching systems, either by employing handcrafted features or through machine learning techniques. Pioneer works in patch matching [START_REF] David G Lowe | Object recognition from local scaleinvariant features[END_REF] are based on handcrafted features such as the SIFT descriptor/detector or some variants, e.g. [START_REF] Bay | Surf: Speeded up robust features[END_REF], DAISY, [START_REF] Tola | Daisy: An efficient dense descriptor applied to wide-baseline stereo[END_REF], etc. Such approaches usually use conventional distance to measure patch similarity, e.g. the Euclidean distance, which usually does not provide an optimal solution for matching purposes. This family of approaches relies heavily on human expertise.

In contrast with feature engineering, another approach to patch matching consists in using supervised algorithms to find † Codes and resources available at http://github.com/ensv/ TS-Net adapted features or adapted similarity functions, for given datasets. Machine learning allows to find optimal projections minimizing (or maximizing) the distances between positive patches (negative patches respectively) [START_REF] Heinly | Comparative evaluation of binary features[END_REF][START_REF] Jain | Metric and kernel learning using a linear transformation[END_REF][START_REF] Brown | Discriminative learning of local image descriptors[END_REF].

Recent breakthroughs in deep learning have strongly contributed to this field. One of the first works in deep metric learning is the one of Jahrer et al. [START_REF] Jahrer | Learned local descriptors for recognition and matching[END_REF] introducing a Siamese networks inspired by the LeNet5 networks, and comparing the so-obtained features with the Euclidean distance. Since then, Siamese networks have been very popular in the literature. Several variants have been proposed, differing by their weight-sharing strategy [START_REF] Zagoruyko | Learning to compare image patches via convolutional neural networks[END_REF] (Siamese vs Pseudo Siamese), combinations of the inputs [START_REF] Zagoruyko | Learning to compare image patches via convolutional neural networks[END_REF][START_REF] Fan | L2-net: Deep learning of discriminative patch descriptor in euclidean space[END_REF] (two channels input images vs multi-scale images), similarity functions (conventional distance [START_REF] Zagoruyko | Learning to compare image patches via convolutional neural networks[END_REF][START_REF] Zbontar | Stereo matching by training a convolutional neural network to compare image patches[END_REF][START_REF] Fan | L2-net: Deep learning of discriminative patch descriptor in euclidean space[END_REF][START_REF] Altwaijry | Learning to match aerial images with deep attentive architectures[END_REF] or using metric layers [START_REF] Han | Matchnet: Unifying feature and metric learning for patch-based matching[END_REF]).

Another important aspect when training deep networks for patch matching is the objective function. It can be (a) the cross entropy (binary classification loss) [START_REF] Han | Matchnet: Unifying feature and metric learning for patch-based matching[END_REF] (b) the hinge loss [START_REF] Zagoruyko | Learning to compare image patches via convolutional neural networks[END_REF] (c) the triplet loss [START_REF] Balntas | Pn-net: conjoined triple deep network for learning local image descriptors[END_REF][START_REF] Bg Kumar | Learning local image descriptors with deep siamese and triplet convolutional networks by minimising global loss functions[END_REF] to incorporate the notion of relative distance, relative distance [START_REF] Fan | L2-net: Deep learning of discriminative patch descriptor in euclidean space[END_REF] (d) the global loss which models the loss as two distributions (positive and negative) to be pushed away from each other [START_REF] Bg Kumar | Learning local image descriptors with deep siamese and triplet convolutional networks by minimising global loss functions[END_REF].

More specifically, the question of multimodal patch matching has been investigated recently by several authors. [START_REF] Cristhian | Learning cross-spectral similarity measures with deep convolutional neural networks[END_REF][START_REF] Suárez | Cross-spectral image patch similarity using convolutional neural network[END_REF] suggested to concatenate the different modalities as different channels of the input data. [START_REF] Merkle | Exploiting deep matching and sar data for the geo-localization accuracy improvement of optical satellite images[END_REF] experimented the use of Siamese networks for the matching of visible/SAR patches. [START_REF] Cristhian | Cross-spectral local descriptors via quadruplet network[END_REF] studied the quadratic network, a variant of the Siamese network that takes 4 patches as input. In the context of cross-spectral face recognition [START_REF] Lezama | Not afraid of the dark: Nir-vis face recognition via crossspectral hallucination and low-rank embedding[END_REF] proposed two components (one before and another one after the feature extraction network) to allow the system to transform the NIR images into the VIS spectrum. As we write, Siamese networks are still seen as a reference for multimodal patch matching.

One important aspect of Siamese architectures is that the weights of feature extraction towers are shared between the inputs. This is to say that the network is trained to extract characteristics present in both modalities. In case of the Pseudo-Siamese architectures, the feature towers are not shared: contrarily to the Siamese networks, the motivation is to extract modality specific information in order to better discriminate the pair of inputs. Our motivation in this paper is to take advantage of these two complementary aspects and propose a novel architecture, dubbed as TS-Net. It consists of two sub-networks, one Siamese and one Pseudo-Siamese networks. Their outputs are combined with a fully connected layer, acting as a weighting scheme between the modality specific information and the common information present in the input patches. The overall architecture is given Figure 1.

Our second contribution is to show that adding a constraint on the feature embedding, by means of a contrastive loss in the feature extraction tower, helps to boost the performance further. The idea is to encourage the network to bring projections of positive pairs closer in the Euclidean space. In the extreme case, this is equivalent to make two clusters of input pairs at the metric layers, allowing to easily separate them with an hyperplane instead of having to learn an arbitrarily complex boundary.

The rest of the paper is organized as follows: Section 2 introduces the network architecture and the training methodology. Section 3 discusses the datasets and presents the experimental validation of the approach. Finally, Section 4 concludes the paper.

THE PROPOSED THREE-STREAM NETWORK

As explained before, the proposed architecture for multimodal patch matching, denoted as the TS-Net architecture, is intended to combine the advantages of both Siamese and Pseudo-Siamese networks. The overall architecture of TS-Net is given Fig. 1(c). Each sub-network has 2 main parts: two feature extraction towers and a metric learning module. In the case of the Siamese network, the parameters of the feature extraction towers are shared, while for Pseudo-Siamese networks they are distinct. TS-Net takes a pair of patches as input, one from each modality, and predicts independently in each sub-network whether they are similar or not. Finally, the outputs of each sub-network are combined by an additional fully connected (FC) layer to produce the final prediction. In the next paragraphs, the different components of TS-Net are described and commented.

Feature extraction network. Each tower is based on convolutional and pooling layers to hierarchically extract high-level information from the input patches. We use max-pooling layers to reduce the dimensions of the feature maps by a factor of 2. At the end of the tower, we use a bottleneck (fully connected) layer to produce a compact output vector with 128 dimensions. Inspired from [START_REF] Han | Matchnet: Unifying feature and metric learning for patch-based matching[END_REF], we use Relu activation as a non-linear activation function.

Tower Fusion. We observed in our experiments that subtracting the layers produced better performance than concatenating them, as in the original MatchNet. So the output of the feature extraction tower are element-wise subtracted before they are fed to the metric network.

Metric network. The metric learning part of the network consists of three fully connected layers. It takes a vector of 128 dimensions and produces a vector of dimension two, suitable for binary classification.

Losses. We treat patch matching as a binary classification problem, as we observed it performs better (also observed by [START_REF] Fan | L2-net: Deep learning of discriminative patch descriptor in euclidean space[END_REF]) than learning a similarity function. Therefore, Siamese and Pseudo-Siamese parts of TS-Net are trained with binary cross-entropy loss functions.

One contribution of this paper is to introduce additional constraints, at the feature level, by means of a contrastive loss [START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF] enforcing the features coming from the two feature towers to be close to each other if the pair is positive. This will enable the features of positive pairs to be in the hypersphere and the features of the negative pairs to be outside the hypersphere.

The fusion of Siamese and Pseudo-Siamese networks is done by introducing an additional cross-entropy loss on the top of the two.

More formally, let (x 1 , x 2 ) be the input pair of patches and y the class label. y = 1 means the pair is positive (similar patches), y = 0 means the pair is negative (different patches). We denote by L en and L con the cross-entropy and the contrastive loss, with: (a) L en = y log(ŷ) + (1 -y) log(1 -ŷ) where ŷ is output of the Softmax layer, and (b)

L con = y 2 Q D 2 + (1 -y)2Qe -2.77
Q D where D is the Euclidean distance between features. Q is the margin to be optimized. The overall loss function is then given by: L = L tsneten + L siamen + L pseudoen + λL siamcon + βL pseudocon , with λ and β two cross-validated parameters in [0, 1].

In multimodal settings, it is not always guaranteed that the two modalities can be projected into the same subspace. In practice, we observed that optimal performance is obtained for λ and β set to 10 -2 (values obtained by cross validating the parameters on the validation set).

Implementation details. We initialize the weights of each convolutional layer using the Xavier initialization and all the FC layers with a truncated normal distribution (stddev = 0.005 and mean = 0, bias = 0.1). While the original Match-Net is trained with plain stochastic gradient descent, we found that training with 0.95 momentum produce equal or better performance. We train the network with lr = 10 -3 with L2 regularization of 10 -3 with neither dropout nor batchnorm. Q is optimized experimentally on VeDAI validation set and set to be 50 for the other two datasets. During training, we observe that the λ and β parameters should be carefully set and the best performance we obtain is for λ = 10 -2 , β = 10 -4 or β = 10 -2 on CUHK and NIR Scene (cross validation experiments). We use batch size of 32 and train with at least 150 epochs. All the experimentations are done using Tensorflow 1.4 with NVIDIA P100 or K80 GPU. Patches are normalized to have zero mean and unit standard deviation for each modality.

EXPERIMENTATIONS

Our aim in this section is to provide insights about TS-Net, its behavior and, more importantly, to draw a comparison with Siamese and Pseudo-Siamese networks, which are considered as a reference to this task. First, we run a series of experiments on the VeDAI dataset to validate TS-Net. It consists in evaluating different ways to fuse information either in the metric or after the feature extraction network. Next, we show that the gain in performance is not due to an increase of the number of parameters. Finally, we run experiments on three public datasets to experimentally validate our network and compare it to Siamese and Pseudo-Siamese networks. To report the performance, we employ the standard evaluation protocol defined in [START_REF] Brown | Discriminative learning of local image descriptors[END_REF], namely the 95% error rate criteria, abbreviated 95%ErrRate, which is the percentage of false matches present when 95% of all correct matches are detected. For each experimentation, we report the average performance with its standard deviation on at least 3 runs (Table 2) and 8 runs (Table 3).

Datasets The proposed approach is experimentally validated on three different datasets: VeDAI * , RGB-NIR Scene † and * https://downloads.greyc.fr/vedai/ † https://ivrl.epfl.ch/supplementary_material/ CUHK ‡ . These 3 datasets contain images from two different modalities. It is worth mentioning that these 3 datasets have been created for different tasks. Therefore, it will provide an opportunity to test and compare performance on a variety of fields. For instance, VeDAI is generally used for Vehicle Detection in Aerial Imagery while CUHK for face sketch synthesis/recognition. VeDAI, CUHK and RGB-NIR Scene contain respectively a total of 1246, 188 and 477 pairs of images.

Pairs of Patch Generation. For each dataset, the images are given as sets of aligned pairs (one image from each modality). To extract patches and form pairs, we uniformly sample each image using grid-like layout where each cell has a width and height of 64 × 64 pixels. This gives us a collection of corresponding positive patches. We randomly choose patches coming from different images to form negative pairs. To make our patch matching experiments more realistic and challenging, we artificially augment our datasets by introducing some random affine transformations between the images of the same pair. For each pair, we generate three additional pairs using a random combination of: (i) Rotation (-12 to 12 degrees), (ii) Translation (-5 to 5 pixels on both axes) and (iii) Scale (0.8 to 0.99). For the validation and test set, we keep only one pair among the four, chosen randomly. Combining Siamese and Pseudo-Siamese networks. Our motivation is to find an efficient way to combine the information coming from the two sub-networks. We consider four options depending on whether this fusion (element-wise subtraction) is done (a) after the feature extraction tower (b) after the first (c) second or (d) third layer of the metric network.

In the case of early fusion, all the following layers are kept as in MatchNet. Table 2 shows the performance given by each alternative. It also compares the performance obtained when 1 unique entropy loss (tsnet en ) is used, on the top of the network, with the performance obtained when each subnetwork has, in addition, its own loss (L tsneten + L siamen + L pseudoen ). Based on these results, it is clear that the additional losses are important. The two additional losses help to guarantee the Siamese and the Pseudo-Siamese network learn complementary representation of the modalities. Consequently, this is the reason why having a late fusion (after FC3) is more beneficial. In addition, to guarantee that the gain in performance of TS-Net is not due to a larger number of parameters, we also provide the performance of MatchNet (noted as S* in Table 2) when we increase the number of parameters in the feature tower by a factor of 1.45 and the bottleneck by 2 to have exactly the same number of parameters as in TS-Net. Experimental results suggest that this is roughly equivalent to the performance of TS-Net without additional losses with fusion at the FC1 layer.

Influence of the contrastive loss. Table 3 presents the experimental results given by the three architectures: Siamese, Pseudo-Siamese and TS-Net network with/without the additional contrastive loss. In general, we observed that the error During training, we found that the margin Q and the weighting value λ and β are crucial and need to be carefully cross-validated. We also consider replacing it by the classical contrastive loss. However it turned out to be very sensitive to gradient explosion. In addition, to make these parameters less sensitive during training, we tried to normalize the features before feeding into the loss function in order to maintain a fixed range of distances. Unfortunately, we observed some (marginal) drop in performance.

Comparison to Siamese and Pseudo-Siamese network. Intuitively, the Pseudo-Siamese network has more parameters and degree of freedom to project the two modalities onto the new subspace. Hence, it should produce better results compared to the Siamese network (See Table 3). However, in practice, we observed the opposite. We perform a grid search on the different parameters, regularization techniques (dropout, L2/L1), different losses (entropy/contrastive loss) with different strategy of combining the two towers (concatenation/subtraction). In all the experimentations, the Siamese network always outperform the Pseudo-Siamese network. This behavior has also been observed by [START_REF] Zagoruyko | Learning to compare image patches via convolutional neural networks[END_REF][START_REF] Cristhian | Learning cross-spectral similarity measures with deep convolutional neural networks[END_REF][START_REF] Merkle | Exploiting deep matching and sar data for the geo-localization accuracy improvement of optical satellite images[END_REF]. When combining the Siamese and Pseudo-Siamese network, we notice significant improvement over the 3 datasets. On VeDAI and CUHK, the error is reduced by almost 50% not counting the additional loss at the feature level. On the three datasets, our approach outperforms the Siamese and Pseudo-Siamese networks. This fully justifies the competitiveness of our approach.

CONCLUSIONS

We proposed a novel architecture, called TS-Net, for multimodal patch matching. TS-Net consists of two sub-networks: a Siamese and Pseudo-Siamese network. Each of them is responsible for learning different types of complementary characteristics from both modalities. In addition, we showed that an additional loss, at the intermediate feature level, is beneficial at the price of only a small additional computational costs. Experimental results demonstrate the superiority of our approach over Siamese and Pseudo-Siamese networks.

Fig. 1 .

 1 Fig. 1. The detailed architectures of (a) standard Siamese networks (b) Siamese networks with the proposed additional loss on the feature towers (c) the proposed TS-Net network with additional losses on the feature extraction tower and on the metric network. The numbers on each rectangle indicate the output size of this layer.

Table 1

 1 summarizes the number of train, test and validation

cvpr11/

‡ http://mmlab.ie.cuhk.edu.hk/archive/facesketch. html

Table 1 .

 1 Number of pairs of patches in the train, test and validation set, for each dataset. Each set contains 50% of positive pairs and 50% of negative ones.

	Dataset	Train (70%) Test (20%) Validation (10%)
	VeDAI	448k	128k	64k
	CUHK	113k	32k	16k
	NIR Scene 427k	122k	61k
	Table 2. 95%ErrRate on VeDAI validation set using TS-Net.
	Rows: tower fusion after the feature extraction network (bot-
	tleneck layer), FC1, FC2 or FC3 of the metric layer. '1 En-
	tropy' means there is only one classification loss at the top
	of the network. '3 Entropy': each sub-network also has his
	own classification loss. S*: Matchnet Network with the same
	number of parameters as TS-Net.
		3 Entropy losses 1 Entropy loss
	FC3 (TS-Net) 0.52 ± 0.07	0.93 ± 0.05
	FC2	0.62 ± 0.13	0.92 ± 0.05
	FC1	0.74 ± 0.07	1.03 ± 0.06
	Feature tower n/a		1.05 ± 0.07
	S*	n/a		1.01 ± 0.11

pairs of patches. Half are positive, half are negative.

Table 3 .

 3 95%ErrRate on the 3 datasets, for Siamese network alone (S), Pseudo-Siamese network alone (PS), TS-NET, without/with the additional contrastive loss (C).

	Dataset	Vedai	CUHK	NIR Scene
	S	1.16 ± 0.07 5.07 ± 0.46 14.35 ± 0.20
	PS	1.50 ± 0.08 5.56 ± 0.36 16.05 ± 0.30
	TS-Net	0.52 ± 0.07 3.58 ± 0.14 12.40 ± 0.34
	S+C	0.84 ± 0.05 3.38 ± 0.20 13.17 ± 0.86
	PS+C	1.37 ± 0.08 3.70 ± 0.14 15.60 ± 0.28
	TS-Net+C 0.45 ± 0.05 2.77 ± 0.07 11.86 ± 0.27
	can be reduced by up to 30 % by adding this loss, for any
	architecture and dataset. More importantly, this gain can be
	obtained with negligible computing costs and with little ef-
	fort.

Acknowledgements. This work was partly funded by the French-UK MCM ITP program and by the ANR-16-CE23-0006 program. The authors thank Shivang Agarwal for proofreading the manuscript.


Clélia Lopez
email: clelia.lopez@entpe.fr

Panchamy Krishnakumari
email: p.k.krishnakumari@tudelft.nl

Ludovic Leclercq
email: ludovic.leclercq@entpe.fr

Nicolas Chiabaut
email: nicolas.chiabaut@entpe.fr

Hans Van

Corresponding Author

Hans Van Lint

Lopez

Krishnakumari

Leclercq

Chiabaut

Van Lint

Spatio-temporal partitioning of transportation network using travel time data

Keywords: Graph-partitioning, coarse network, GIS, missing data, homogeneous spatio-temporal regions

come

INTRODUCTION

Graph partitioning is a common challenge in different fields, such as transportation (1; 2) and image segmentation [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. Partitioning a heterogeneous network, such as an urban network, into homogeneous zones can be extremely useful for many applications. We distinguished, at least, three applications that can be improved by using 3D homogeneous regions: (i) traffic control, (ii) macroscopic traffic modeling and (iii) route guidance. (i) For traffic control purpose, different traffic management schemes can be identified for regions of a heterogeneous network (4; 5). Traffic signal control is computationally expensive for a large network [START_REF] Ma | Urban traffic signal control network automatic partitioning using laplacian eigenvectors[END_REF], especially if the scheme is required to be generated in real-time [START_REF] Peeta | Foundations of Dynamic Traffic Assignment: The Past, the Present and the Future[END_REF]. Developing a scheme at the region scale is a computationally plausible approach than at a links scale. A time adaptive scheme can be considered from the 3D regions. (ii) The Macroscopic Fundamental Diagram (MFD) is more likely to be well-defined in a homogeneous network (8; 9; 10; 11; 12). Refine the equilibrium analysis by zone is a promising approach to investigate the effect of route choice behavior [START_REF] Yildirimoglu | Equilibrium analysis and route guidance in large-scale networks with MFD dynamics[END_REF]. Partitioning methods make it possible to define sub-regions within a network which is essential for a multi-reservoir modeling approach such as the MFD modelling framework (10; 14). This macroscopic scale model facilitates the development of traffic management strategies. (iii) Tour planning, trip advisors and dynamic route guidance can be refined by network partitioning results. The routing models can calculate the least cost routes including the day-today 3D regions, i.e. the travel time objective function 𝑓(𝑡, 𝑥) is refined by the space time properties of the 3D regions. An investigation can be done to identify the best time to start a journey by minimizing the total route time through spatio-temporal network.

To this end, [START_REF] Ji | On the spatial partitioning of urban transportation networks[END_REF] investigates the performance of 𝑘-means in partitioning urban networks by considering spatial locations of the road as new features in the data. [START_REF] Saeedmanesh | Clustering of heterogeneous networks with directional flows based on "Snake" similarities[END_REF] elaborates a second method based on the definition of a similarity matrix between observations and the application of the Ncut algorithm [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. Such regions are defined in 2D, i.e. only measurements of a single time period are considered to identify homogeneous areas. The question of traffic dynamics is only addressed by iterating the algorithms for each time step without direct connections between the 2D clusters (quasi-stationary approximation). It should be noted that the inter-cluster dissimilarity is a central property in these studies because the main targeted application is traffic control.

To perform network partitioning, both the network topology and the link speeds for all time periods are needed. However, real data is often flawed and incomplete, especially for data collected by classic urban measurements. Therefore, data preparation is needed to create a validated dataset for partitioning. The aim of the data preparation is (1) travel time outlier removal, (2) coarsening the large scale network to improve the computation time, and (3) speed estimation including an extension for missing data. In this paper, we introduce methodologies that address these issues. We use real data gathered from Amsterdam urban area. The network topology is derived from both cameras and Geographic Information System (GIS) data from Open Street Maps. In the Amsterdam case, not all speeds for every time period are available. This necessitates the development of algorithms to impute these missing data. We discuss the estimation of missing data and how to minimize the problem of missing data in section 2. Based on a complete (albeit partially imputed) record of all data, we can now use the Amsterdam network to assess the performance of different partitioning techniques.

In this paper, we investigate two classes of clustering techniquesan extension of Ncut based on a new expression of the similarity matrix, called snakes (1; 2) and classical methods such as DBSCAN and Growing Neural Gas (GNG) from the data-mining field. These clustering techniques are used to construct 3D clusters of road links based on their average speed. We want to ensure that all clusters contains a single connected component (CC) in order all links be reached within the same clusters. This requirement is central for application like travel time estimation or macroscopic traffic modeling. Clustering consists of finding the optimal decomposition of the graph into connected clusters with lowest internal variance of the speed while it retains a reasonable inter-cluster dissimilarity. However, the classical methods that are used in this paper -DBSCAN and GNG produce unconnected clusters. Hence, a new post-treatment method is introduced in this work to generate connected clusters from unconnected clusters in 2D and 3D.

In section 2, we describe the methodology for building both a validated network and speed dataset for partitioning. The construction of the 3D connected clusters using the three clustering techniques along with the posttreatment and cross evaluation criteria are described in section 3. Section 4 provides the results of this preliminary evaluation and section 5 concludes the paper with the major findings of the paper and future recommendations.

DATA PREPARATION

Network Reconstruction

In our study, raw data are the individual travel times from the city of Amsterdam. The data includes the ID and location of the start camera and end camera, recorded individual passing times and travel times for 41 days. There are a total of 314 unique pairs of start and end camera observations in the data for all the days. The first step to build a network from this dataset is to create a route table. For this purpose, we need to locate the camera on the Amsterdam GIS network obtained from OpenStreetMaps which consists of 147059 links/edges as shown in FIGURE 1(a). The mapping of the camera coordinates to the GIS network is required since these coordinates may not be located in the road, hence location correction is needed. This snapping is done by finding the point-tosegment distance to find the nearest location in the network. Once the coordinates have been snapped to the network graph, we find the path between the start and end camera location. There are various path finding algorithms available in the literature. For this work, the shortest path was found using the algorithm employed in OSRM (OpenStreet Maps Routing Machine) which is based on contraction rules [START_REF] Daganzo | Urban gridlock: Macroscopic modeling and mitigation approaches[END_REF]. This algorithm is fast and robust for real time applications as well. There were 314 pairs of start and end cameras leading to 314 shortest paths. Mapping these to the GIS Amsterdam network provides a network with 7512 links as shown in FIGURE 1(b).

FIGURE 1 Camera data to validated network 2.2 Network Coarsening

After mapping the shortest path to the Amsterdam GIS network, there are still 7512 links, which is quite large. Hence, we employ network coarsening techniques to remove nodes that satisfy certain criteria. The idea behind coarsening is that a multiscale graph 𝐺 𝑖+1 can be constructed from the previous fine scale graphs 𝐺 𝑖 by collapsing together the nodes that have similar matching criteria. The matching criteria can differ according to the application. In this paper, the matching criterion relates to the differences in edge weights. In our case, these weights represents the speed of each link/edge. If the edges have the same weight, the node that connects the edges will be collapsed/removed. The network coarsening in this paper is based on a constrained version of contraction hierarchies [START_REF] Daganzo | Urban gridlock: Macroscopic modeling and mitigation approaches[END_REF].

The construction of the coarsened graph in this work is based on three steps: (a) the nodes are prioritized or ranked for contraction, i.e. a node with a lower rank will be removed before a node with a higher rank, (b) the contraction rules are determined based on the edge difference, and (c) the new weights of the link for the coarse graph are calculated. In this work, the contraction rules are governed by the edge weights and the connectivity of the network. The weights for each link/edge is the estimated speed of each link. The weight 𝑤 𝑢𝑣 of link (𝑢, 𝑣) is the speed of the link 𝑠 𝑢𝑣 . As we only require speed for one time slice for assigning the weights, a peak period time slice (16:00) was chosen. This is because the network will exhibit the most variance during peak period with most links having different speeds at this time. If we chose a non-peak period, these variances will be smoothed out. A more detailed description of node ranking and the contraction rules are given below.

Node Ranking

The order in which the nodes are removed is important for graph coarsening. There are different node ranking or ordering techniques as introduced in relation to contraction hierarchies [START_REF] Daganzo | Urban gridlock: Macroscopic modeling and mitigation approaches[END_REF]. In this work, the nodes are ordered based on their densities. The more number of neighbors the node has, the higher the rank is, and the lower the chance that the node will be removed. A dense node might connect a lot of edges and might be important for transportation purpose application. Given a graph 𝐺 = (𝑉, 𝐸) with node set 𝑉 and an edge set 𝐸 . Suppose, (𝑢, 𝑣) ϵ 𝐸 where 𝑢, 𝑣 ϵ 𝑉 then the rank of the nodes 𝑢 and 𝑣 will satisfy the following condition:

𝒓(𝒖) > 𝒓(𝒗) , 𝒊𝒇 𝒏(𝒖) > 𝒏(𝒗) ( 1
) where 𝑛(𝑢) and 𝑛(𝑣) are the number of neighbors of node 𝑢 and 𝑣 respectively. Thus, based on the contraction rule, 𝑣 will be contracted before 𝑢. The neighbors of the node are found by determining all the incoming and outgoing links from the node. A link (𝑢, 𝑣) is said to be incoming w.r.t node 𝑣 if 𝑣 is the target node of the link and outgoing if 𝑣 is the source node. Once the neighbors are found for all the nodes, the nodes are sorted based on their ranks in ascending order with the lowest rank first.

Contraction Rules

Once the nodes are sorted according to the rank, the contraction rules are used to remove them. First, a criterion has been set to decide if the given node is eligible for contraction to decrease the complexity. The criteria are that if the node removal results in the same or more number of links than before removal, then the node is not removed. TABLE 1 presents an overview of different cases of node contraction. The link color represents weights; different color implies different weights. For example, in case (5) of TABLE 1, removing the nodes results in 4 new links which is the same number of links as that before node contraction. Hence, this node will not be considered for removal. It was also observed that contracting nodes with more than four neighbors, in the majority of the case, leads to 5 or more links. Therefore, an initial constraint has been imposed on the node contraction only to contract nodes with neighbors less than or equal to 4 links as given below:

𝒄 𝟏 (𝒗) = { 𝟏, 𝒏(𝒗) ≤ 𝟒 𝟎, 𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆 ( 2 )
A given node 𝑣 will be contracted only if 𝑐 1 (𝑣) is equal to 1; where 𝑐 1 (𝑣) is the criterion. When the initial criterion has been satisfied for a given node 𝑣, edge difference is then used as the next rule for inclusion or exclusion of that node for contraction.

𝒄 𝟐 (𝒖, 𝒗, 𝒘) = { 𝟏, 𝒘 𝒖𝒗 -𝒘 𝒗𝒘 ≤ 𝒕𝒉𝒓𝒆𝒔𝒉𝒐𝒍𝒅 𝟎, 𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆 ( 3 )
Here, 𝑊 𝑢𝑣 and 𝑊 𝑣𝑤 are the weights of the links (𝑢, 𝑣) and (𝑣, 𝑤) respectively. In this work, the weight is the estimated speed for each link. In our work, we set the threshold to 0, so that only if the links have the same speed, nodes can be contracted.

Based on these two criteria, we will now discuss the rulesets for node contraction. Given the nodes that have been ranked, the steps for coarsening are as follows:

1. Set the node with the lowest rank as 𝑣.

2. Check if 𝑐 1 (𝑣) is satisfied.

3. If it is satisfied, we find all the incoming and outgoing links of node v. If 𝑐 1 (𝑣) returns 0, go to step 9.

4. Pair up all the incoming and outgoing links while considering the direction. For example, in case (6) of TABLE 1, if (𝑢, 𝑣), (𝑥, 𝑣) and (𝑦, 𝑣) are the incoming links and (𝑣, 𝑤) the outgoing link, the pairs are (𝑢, 𝑣, 𝑤), (𝑥, 𝑣, 𝑤) and (𝑦, 𝑣, 𝑤). 5. U-turn is not considered in this work, thus (𝑢, 𝑣, 𝑢) is not considered as a valid pairing as shown in case [START_REF] Saeedmanesh | Clustering of heterogeneous networks with directional flows based on "Snake" similarities[END_REF] of TABLE 1. 6. Check if 𝑐 2 criteria is satisfied for all the valid incoming-outgoing pairs. 7. If one of the pairings does not satisfy the condition, assign the next node in the rank list as 𝑣 and repeat from step 2. 8. If 𝑐 2 is satisfied for all pairs, then we remove the node from the node list and update the node ranking as new links are formed. Repeat from 1. 9. Stop the iteration.

In the case (4) of TABLE 1, the node cannot be contracted as the edge difference did not satisfy the threshold criteria. The node coarsening is applied to the mapped Amsterdam network with 7512 links. As explained before, the peak period was estimated to be around 4pm and hence the speed at this time slice is used for the network coarsening. The new coarsened network contains 411 links as shown in FIGURE 1(c).

TABLE 1 Examples of contraction rules

Speed Estimation

This section described the methodology to estimate the link speed based on individual travel times recorded by the cameras. First, a cleansing process will remove outliers. Second, the speed will be estimated for each time period. The moving average process has been used to remove travel time outliers. There are usually alternative paths for a given Origin-Destination (OD). It can be 𝑘-shortest paths, representing the common route choices. We defined travel times significantly higher than the distribution as outliers. To remove these outliers, we propose two approaches: (1) treat the travel times higher than the third quantile as outliers. In order to keep the dynamics, distributions can be split by periods. The disadvantage of this approach is that distribution is sensitive to the number of observations. Thus, outliers can be smoothed into time periods with few travel times. [START_REF] Saeedmanesh | Clustering of heterogeneous networks with directional flows based on "Snake" similarities[END_REF] The approach that we used for removing the outliers is based on the moving average process. We define the moving average 𝜏̅ as

𝝉 ̅ 𝒏 = 𝟏 𝒌 ∑ 𝝉 𝒏-𝒊 𝒌-𝟏 𝒊=𝟎 ( 4 )
where 𝜏 𝑛 is the 𝑛 th realized travel time. Outliers are defined by 𝜏̅ 𝑛 + Δ𝜏, where Δ𝜏 is the travel time window. In our study, we set Δ𝜏 to the standard deviation of the peak demand. Δ𝜏 has be tuned by a graphical inspection of the effects of Δ𝜏 on the number of outliers. We considered only the upstream window to remove travel time outliers as the downstream window is not relevant for our study, i.e. we do not consider that fast travel times could be outliers. The travel time window is refined after two iterations. FIGURE 2 gives an example with the 𝑥 axis being the observed time and 𝑦 axis the travel time. The red curve is the moving average and the black curve represents the upstream travel time window.

Individual travel times have been aggregated by period. We consider the mean of individual travel times for a given OD at a given period. . It can happen that a given link 𝑙 𝑘 belongs to different OD's paths, i.e. 𝑙 𝑘 ∈ (𝑜𝑑 1 , 𝑜𝑑 2 , … , 𝑜𝑑 𝑚 ). For this case, its speed is defined as the mean of the corresponding speeds of the paths.

When no data is available to measure 𝑡𝑡 (𝑖,𝑡) , we distinguished three approaches to estimate the speed: (1) set links without data to the limited speed, which does not consider traffic lights. We assume that setting limited speed at links without data will increase the variance of the zones. (2) Compute new speed value through the speeds of a specific neighborhood. We assumed that the average speed of a given specific neighborhood will smooth the speed. Thus, congestion pockets can be less homogeneous and location zones can be less identifiable in space and time. The phenomenon is more common with link belonging to the boundaries of the zones, i.e. the link without data is being connected with links from different zones. (3) Duplicate speed from an identified link. We assumed that the duplication of speed minimize the speed variance of zones. We use the third approach by using a cost function. Let 𝐺 = (𝑉, 𝐸) be the weighted graph where 𝑁 𝑣 and 𝑁 𝑒 are the numbers of vertices and edges respectively, 𝐴 is the directed adjacency matrix of the network, 𝐶 is the directed weight matrix and 𝐷 is the cost paths matrix. 𝐴 represents relationship of the finite graph 𝐺. In our study, 𝐺 is the graph of the 3D network, i.e. a repetition of the same network at 𝑁 𝑡 time slices. Through the time, a vertex 𝑣 𝑖 is connected to itself at time steps 𝑡 + 1 and 𝑡 -1 where 𝑡 ∈ (1 , 𝑁 𝑡 ). Its edge weight is set to the period duration. Through the space, we denote the edge weight by 𝑐 𝑖𝑗 ,where 𝑖 and 𝑗 are connected links. Directions are considered to set the edge weight. , where 𝑤 is the backward wave speed and it is set to 5 m/s in this study. If no data is available for 𝑣 𝑗 which is downstream to 𝑣 𝑖 , then 𝑠 𝑗 = max(𝑠) + max(𝑠) 2 . Dijkstra's algorithm ( 16) is used to estimate the shortest path between two vertices 𝑖 and 𝑗 in 𝐺. The cost of the shortest path is denoted by 𝐷 𝑖𝑗 . Thus, the link without data will be assigned the speed of the most relevant link. The most relevant link is identified as the link that minimizes the cost function. For computation efficiency, the process is performed strictly for links without data and a time window is used to constrain the search for the relevant link.

Experimental setup

The data preparation process -the coarsening methodology and the speed estimation of the link -considers a weighted directed network. The partitioning methods used in this paper requires strongly connected graph, i.e. a directed path exists for every pair of vertices. A real network is strongly connected when a vehicle can reach any link from any starting point. For both fine and coarse resolutions networks, this constraint is not true. Thus, direction is not a convenient attribute to partition the Amsterdam network.

Our study application focuses on only one-day data. This given day is a common weekday. The analyzed period is from 7am to 5pm. It is a time window of 8 hours, one third of a day representing the morning peak demand. After analyzing the travel time data, it was found that not all of the ODs are used on all days. Only used ODs have been considered for reconstructing the network based on the shortest path finding in the network with 411 links. They are mapped to create a new coarsened network as explained in Section 2.1. From the used ODs, around 16% of data are missing.

SPATIO-TEMPORAL PARTITIONING TECHNIQUES

Normalized Cut based on snakes similarities

One of the contributions of this paper is to adapt the existing methodology of snakes for a spatio-temporal network, i.e. a repetition of the same network at numerous time slices. A snake ( 2) is composed of a sequence of links, which iteratively grows by adding adjacent link that are similar to itself. The connectivity is ensured by a link addition constraint which considers links strictly belonging to the neighborhood of the snake. Let 𝑆 𝑖 be the snake initialized by the link 𝑙 𝑖 where 𝑆 𝑖𝑘 ∈ 𝑆 𝑖 is the subset containing the first 𝑘 elements. For a fixed time, the neighborhood of 𝑆 𝑖𝑘 of a given snake is defined as the links spatially connected to it. We consider this neighborhood both in space and time. The link 𝑙 𝑖 at time 𝑡 is denoted by 𝑙 (𝑖,𝑡) . We make duplicates of link 𝑙 (𝑖,𝑡) at instants 𝑡 -1 and 𝑡 + 1, denoted by 𝑙 (𝑖,𝑡+1) and 𝑙 (𝑖,𝑡-1) , respectively. The snake similarities are defined as follows [START_REF] Saeedmanesh | Clustering of heterogeneous networks with directional flows based on "Snake" similarities[END_REF] 𝒘 𝒊𝒋 = ∑ 𝒑 𝒌 𝒊𝒏𝒕𝒆𝒓𝒔𝒆𝒄𝒕(𝑺 𝒊𝒌 , 𝑺 𝒋𝒌 )

𝑵 𝒌=𝟏

( 5 ) where the weight coefficient 𝑝 is fixed to 𝑝 ≤ 1. Let 𝑊 be the snakes similarities matrix with 𝑊(𝑖, 𝑗) = 𝑤 𝑖𝑗 . NCut (3) is a measure of dissociation based on this 𝑊. The complexity of NCut is NP-complete.

One of the main inconveniences of snake is its heavy computational cost. The complexity to run a snake is 𝑂(𝑛) for the best case and 𝑂(𝑛²) for the worst case, where 𝑛 = 𝑁 𝑙 and 𝑛 = 𝑁 𝑙 * 𝑁 𝑡 for a spatial snake and a spatiotemporal snake respectively. The complexity of running 𝑛 snakes is 𝑂(𝑛²) for the best case and 𝑂(𝑛 3 ) for the worst case. The growing snake algorithm search its neighbors iteratively. The neighborhood size depends on the growing snake pattern and the network topology. In particular, the neighborhood of a snake growing in a corridor is equal to 2 (the upstream and the downstream neighbors of the current snake). It is much smaller than the neighborhood of a snake growing in a strongly connected network, i.e. a network where every nodes have a link with every other nodes. These both examples correspond to the best and the worst cases. Their associated complexity are respectively 𝑂(𝑛²) and 𝑂(𝑛 3 ). Any realistic situation is between these boundaries. For example, we numerically investigated the complexity of the algorithm in our case study. We show that it is 𝑂(𝑛 2.2 ), where 2.2 was obtained by a regression of the complexity. It can be seen that the similarities decrease exponentially with the weight coefficient 𝑝. A sensitivity analysis was done to investigate the performance of snakes for different lengths. Results show that the quality of NCut partitioning is independent of the snake length. Nevertheless, the snake length -𝑘 -has to be set at a minimal threshold to keep the connectivity. Thus, a too short snake cannot discover the entire topology of the network in both space and time. The short snake length may also provide clusters results where a cluster contains links that are not all connected with each other. Therefore, we set the snake length to 38% of the spatio-temporal size of the network. In addition, the weight coefficient is set to 𝑝 = 0.8 in our study.

Partitioning based on Data Points Clustering

The two other classic clustering methods that are considered for this study are: (i) GNG ( 17) and (ii) DBSCAN [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF]. We represented the 3D network into a data set containing four variables, link coordinates with their corresponding speed and time measurement (x, y, t, s). The four quantitative variables have been normalized. After normalization, we multiply the speed column by a fixed coefficient equal to 3 to be sure that speed is the predominant variable over spatial and temporal coordinates during clustering.

(i) DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a density-based method. DBSCAN has two user-specified parameters. The radius parameter ε > 0 specifies the radius neighborhood and the MinPts parameter specifies the density threshold of dense regions. For our study, parameters have been set to ε = 0.01 and MinPts = 50.

(ii) GNG is an Artificial Neural Network variant of Neural Gas [START_REF] Martinetz | A "neural gas" network learns topologies[END_REF]. GNG begins with two neurons and the network grows during the execution of the algorithm. GNG has been adapted for clustering through a two-step process: running GNG and reconstructing data point clusters based on GNG centroids. The user-specified parameters are the number of centroids 𝑁, the maximum number of iteration 𝑚, 𝐿, the adaptation threshold 𝜀 𝑏 , 𝜀 𝑛 , the neighborhood size α, δ, the time 𝑇, which have been set as 𝑁 = 10, 𝑚 = 20, 𝐿 = 50, 𝜀 𝑏 = 0.2, 𝜀 𝑛 = 0.005, 𝛼 = 0.5, 𝛿 = 0.995, 𝑇 = 50.

Post-treatment

The clustering results provide clusters which are not connected as shown in FIGURE 3(a). The homogeneous zone partition needs to be a single connected cluster. Therefore, post-treatment is needed on the clusters that is obtained from DBSCAN and GNG to obtained connected clusters with minimum inter-cluster speed variance. There are three steps for the post-treatment algorithm and these are:

 Identifying the CCs in each of the cluster  Assigning the biggest CCs as the initial clusters  Assigning all the other CCs to the initial clusters Given that there are 𝑁 number of clusters from the data point clustering methods, there might be more than one CC for each cluster as shown in FIGURE 3(a). Ideally each cluster should contain a single CC. In order to achieve this, all CCs within each cluster are identified. Then, these CCs are sorted according to the CC size. Given that the target cluster size is 𝑀, the biggest 𝑀 CCs from different clusters are chosen as the initial cluster. This process is illustrated with a simple example in FIGURE 3. In FIGURE 3(a), there are 2 CCs in blue cluster, 1 CC in red, 1 CC in green and so on. It can be clearly seen that there are 2 CCs for the blue cluster.

Assuming that there are a total of 𝑋 CCs from all the clusters, there are (𝑋 -𝑀) clusters that still need to be assigned to one of the initial cluster. The rest of the (𝑋 -𝑀) CCs are merged with the 𝑀 initial cluster and the following two parameters are found for each pair.

𝒄(𝒙, 𝒎) = {

𝟏, 𝒙 ∩ 𝒎 𝒊𝒔 𝒄𝒐𝒏𝒏𝒆𝒄𝒕𝒆𝒅 𝟎, 𝒙 ∩ 𝒎 𝒊𝒔 𝒏𝒐𝒕 𝒄𝒐𝒏𝒏𝒆𝒄𝒕𝒆𝒅

𝒗(𝒙, 𝒎) = { 𝒗𝒂𝒓𝒊𝒂𝒏𝒄𝒆(𝒔 𝒙 , 𝒔 𝒎 ), 𝒙 ∩ 𝒎 𝒊𝒔 𝒄𝒐𝒏𝒏𝒆𝒄𝒕𝒆𝒅 ∞, 𝒙 ∩ 𝒎 𝒊𝒔 𝒏𝒐𝒕 𝒄𝒐𝒏𝒏𝒆𝒄𝒕𝒆𝒅 ( 7 ) where 𝑥 ∈ (𝑋 -𝑀) CCs, 𝑚 ∈ 𝑀 initial CCs, 𝑠 𝑥 and 𝑠 𝑚 are the speed of each cluster. Once the 𝑐(𝑥, 𝑚) and 𝑣(𝑥, 𝑚) have been calculated for all the CC pairs, the (𝑋 -𝑀) CCs are sorted in decreasing order according to the ∑ 𝑐(𝑥, 𝑚) for all 𝑚 ∈ 𝑀 CCs. The 𝑥 CCs with the largest ∑ 𝑐(𝑥, 𝑚) is selected and it is merged with the initial cluster 𝑚 that has 𝑐(𝑥, 𝑚) = 1 and have the smallest variance 𝑣(𝑥, 𝑚) among all the 𝑚 ∈ 𝑀. Once merged, this cluster is removed from the (𝑋 -𝑀) CCs and 𝑐(𝑥, 𝑚) and 𝑣(𝑥, 𝑚) is updated for all (𝑋 -𝑀) CCs as the initial clusters are updated. This process is repeated until all the (𝑋 -𝑀) CCs are assigned to the 𝑀 initial clusters. FIGURE 3 shows an example of post-treatment results in 2D and 3D. FIGURE 3(a) shows the cluster before post-treatment and FIGURE 3(b) shows post-treatment with the same number of clusters as the input for a single time slice. FIGURE 3(d) shows the result of post-treatment in 3D with same number of clusters as the input which is shown in FIGURE 3(c). There is no difference in post-treatment methodology between 2D and 3D. The only difference is in calculating the 3D adjacency matrix for finding the 3D CCs and the connectivity. The 3D adjacency matrix is defined by creating bi-directional links between the time slices. ( 8 ) This indicator is based on the assumption that a given cluster is composed of links characterized by similar speeds. The speed variance is highlighted. (ii) The second metric used is the CCD. The criterion is the dissimilarity between a given cluster and its neighboring cluster, i.e. clusters touching the given cluster. CDD is defined as follows:

CCD = ∑ ∑ 𝜹 𝒊𝒌 𝒏 𝒌=𝟏+𝒊 𝒏 𝒊=𝟏 |𝒙 ̅ 𝒊 -𝒙 ̅ 𝒌 | ∑ ∑ 𝜹 𝒊𝒌 𝒏 𝒌=𝟏+𝒊 𝒏 𝒊=𝟏 ( 9 ) 𝜹 𝒊𝒌 { 𝟏 𝒊𝒇 𝒌 𝒂𝒏𝒅 𝒊 𝒂𝒓𝒆 𝒄𝒐𝒏𝒏𝒆𝒄𝒕𝒆𝒅 𝒄𝒍𝒖𝒔𝒕𝒆𝒓𝒔 𝟎 𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆 (
10 ) (iii) The time computation indicator evaluates the computational cost of the algorithms. The complexity has to be considered for another size of network and number of time slices. Two different field of partitioning methods have been compared: (1) NCut from the graph theory based on the snakes similarities and (2) DBSCAN and GNG from data point clustering. The basic data point clustering methods are faster but a post-treatment process is required. The computational cost of the post-treatment is heavy because it checks the connectivity of the previous results and iteratively updates the clusters. The time computation evaluation includes both field partitioning methods and all the internal processes.

RESULTS AND DISCUSSION

In this section, results from the three methods are analyzed and compared -NCut based on snakes similarities, DBSCAN with post-treatment and GNG with post-treatment. The comparison focuses on two conceptually different fields to partition a transportation network. FIGURE 4 illustrates the partitioning results from three methods under a fixed number of clustersset to 2. Both the data point clustering methods do not produce the same spatio-temporal zones by the post-treatment algorithm. The zones shapes present a reasonable 3D covers, i.e. a given zone is roughly compacting by space and time. We use three indicators to evaluate the three methods. TVn and CCD measure the quality of clusters representing the homogeneous zones and the inter-cluster dissimilarity respectively. The time computation quantifies the computational cost applied to our case study. FIGURE 4(d,e) shows the TVn and CCD for a systematic number of clusters from 2 to 9. It can be observed that GNG is the best method that minimizes the TVn. NCut is the best method that maximizes the CCD. However, the time computation for GNG is found to be the fastest. 5(b,d,f) are histogram plots of links speed for each cluster. Note that the maximal speed is around 40 m/s, corresponding to highway. The validated Amsterdam network used in this work contains both provincial roads and highways. The histogram validates that each cluster has speed variance as low as possible. For example, in FIGURE 5(d), most of the links in the blue cluster have speed of 5 to 10m/s. Only a few of the links in the blue cluster have 0 to 5m/s compared to the orange cluster. This observation remains valid for all the three cases shown here proving the hypothesis that the cluster results from post-treatment provides clusters that are connected and that minimizes the speed variance.

CONCLUSION AND FUTURE WORK

This research describes a generic methodology to prepare data for transportation application. We reconstructed the network from GIS based on the coordinates of cameras and their corresponding recorded travel times. We also introduced coarsening techniques to reduce computational complexity. The speed has been estimated from incomplete and flawed individual travel times. The validated network along with the estimated speed has been used for partitioning. Two different concepts of spatio-temporal partitioning of a transportation network has been compared in this work. We implemented methods belonging to different fields: (i) unsupervised learning and (ii) graph theory. (i) Clustering approach considers links under a network as data points. This hypothesis allows us to implement simple and efficient clustering algorithms but it requires post-processing for contiguity, i.e. all clusters should be composed of a unique CC. (ii) We considered transportation network at numerous time slices as a graph. In this case, connectivity is considered through graph topology.

This paper has presented three methodologies to partition a network both in space and time, which is demonstrated in a coarsened Amsterdam city network. The partition criterion is the speed. The comparison between the three techniques has been evaluated by two metrics: TVn and CCD. Preliminary results show that none of the partitioning method is better w.r.t both metrics. TVn measures the homogeneous zones which can be spread throughout the 3D network keeping the connectivity. CCD indicator focuses on the inter-cluster dissimilarity but can forsake the homogeneity. The choice of a spatio-temporal partitioning method is a compromise among both criterions.

There are various future directions that can be pursued. The methodology can be improved to be more generic and computationally efficient. A more extended comparison study needs to be implemented. Also, we have only looked at one day in this work and the methodology can be iterated for several days. Another application that is promising for creating these spatio-temporal speed regions is that it can be used to derive future travel times. These claims still need to be researched and validated.

FIGURE 2

 2 FIGURE 2 Travel times exceeding the travel time window (black curve) are considered as travel time outliers An OD denoted by 𝑜𝑑 𝑖 is characterized by a succession of links 𝐿 𝑖 = (𝑙 1 , 𝑙 2 , … , 𝑙 𝑛 ), i.e., represents a path. The first shortest path has been used to keep speed estimation zones compact. During a given period 𝑡, the travel time of 𝑜𝑑 𝑖 is 𝑡𝑡 (𝑖,𝑡) . Then, it is easy to estimate the speed of the path 𝑖 by 𝑠 𝑖 = 𝑑𝑖𝑠𝑡(𝐿 𝑖 ) 𝑡𝑡 𝑖,𝑡

  For a given edge, if vertex 𝑗 named 𝑣 𝑗 is downstream to 𝑣 𝑖 then the edge weight 𝑐 𝑖𝑗 = 𝑙𝑒𝑛𝑔𝑡ℎ(𝑙 𝑗 ) 𝑠 𝑗 , else if vertex 𝑣 𝑗 is upstream to 𝑣 𝑖 then the weight cost 𝑐 𝑖𝑗 = 𝑙𝑒𝑛𝑔𝑡ℎ(𝑙 𝑗 ) 𝑤

FIGURE 3

 3 FIGURE 3 Post-treatment results for data point clustering methods3.3 Evaluation MetricsThe three clustering techniques have been compared using three indicators in this study: (i) Total Variance normalized (TNn), (ii) Connected Clusters Dissimilarity (CCD), and (iii) time computation. (i) TV is the original indicator of the snake similarities partitioning and is defined as 𝑇𝑉 = ∑ 𝑁 𝐴 * 𝑉𝑎𝑟(𝐴) 𝐴∈𝐶[START_REF] Ji | On the spatial partitioning of urban transportation networks[END_REF]. TV has been normalized using the following equation: 𝑻𝑽𝒏 = 𝟏 𝑵

FIGURE 4

 4 FIGURE 4 Amsterdam network (7am to 5pm) where 3D clusters (𝒏 = 𝟐) obtained with (a) NCut based on snakes similarities, (b) DBSCAN with post-treatment, (c) GNG with post-treatment; and a comparison of the three partitioning methods by (d) TVn, (e) CCD and (f) the computation time FIGURE 5(a,c,e) illustrates the GNG partitioning with different number of clusters ranging from two to four. FIGURE5(b,d,f) are histogram plots of links speed for each cluster. Note that the maximal speed is around 40 m/s, corresponding to highway. The validated Amsterdam network used in this work contains both provincial roads and highways. The histogram validates that each cluster has speed variance as low as possible. For example, in FIGURE5(d), most of the links in the blue cluster have speed of 5 to 10m/s. Only a few of the links in the blue cluster have 0 to 5m/s compared to the orange cluster. This observation remains valid for all the three cases shown here proving the hypothesis that the cluster results from post-treatment provides clusters that are connected and that minimizes the speed variance.

  FIGURE 5 (a,c,e) 3D network visualization of the GNG partitioning into two to four spatio-temporal zones and (b,d,f) its corresponding histograms

ACKNOWLEDGMENTS

The authors would like to thank Sjoerd Linders and AMS for providing the data for this study. This research is supported by the region Auvergne-Rhône-Alpes (ARC7 Research Program), by the réseau franco/néerlandais -Bourse Eole and partly by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 646592 -MAGnUM project). We also acknowledge the support of the SETA project funded from the European Union's Horizon 2020 research and innovation programme under grant agreement No 688082. The authors would like to thank Zhengui Xue for proof reading this paper.


est destinée au dépôt

Vessel Segmentation on Computed Tomography Angiography

The partner in Paris has a long experience of vessel segmentation and improved, in the framework of this project, an approach based on minimal paths and front propagation for 3D vascular tree segmentation and on tubular anisotropy. The key is to represent the trajectory of the vessel not as a 3D curve but to go up a dimension and represent the entire vessel as a 4D curve, where each point represents a 3D sphere (three coordinates for the center point and one for the radius). The 3D vessel structure is then obtained as the envelope of the family of spheres traversed along this 4D curve. Since this 3D surface is defined simply from a 4D curve, we are able to fully exploit minimal path techniques to obtain globally minimizing trajectories between two or more user supplied points in order to reconstruct vessels from noisy or low contrasted 3D data. This approach has the advantage of not being sensitive to local minima inherent in most active surface techniques. This 4D curve yields a natural notion of a vessel's centerline and its envelope which corresponds to the boundary of the vessel. An important aspect of our approach consists in building a multi-resolution metric that guides the propagation in this 4D space. This means we extract the local geometry (orientation and scale) of the image using the so called optimally oriented flux.

With partners in Lyon (CREATIS team), we developed an interactive tool for minimal interaction vessel segmentation based on their black box toolkit (BBTK). This tool is useful for the physician in order to obtain a segmentation of a vascular tree and centerline paths that enable to make efficient visualization and to allow the clinician to perform a quantitative assessment of the vessel morphology.

The Israeli partners focused on the creation of a rough shape prior model for segmentation invariant under non-rigid transformations. With cardiac CTA usage on the rise, there appeared a growing population of patients who underwent more than one CTA study. Our initial proposal was to use the segmentation from the first study to automate the segmentation of the subsequent studies. We have adopted a representation similar to that described above for minimal paths, where a vessel is described by the centerline and the radius at each point. We developed an algorithm which, given an existing segmentation, register it with another study, thus providing an automatic segmentation. The algorithm progresses from the proximal end of the vessel distally, predicting the next point based in the existing segmentation and then correcting it based on the image data.

In conclusion, we have proposed minimally interactive methods for vessels and vascular tree segmentation (tubular branching structures), where the user provides only one initial point. These are used for shape prior segmentation allowing non rigid deformation of the surface. Publications can be found on the website http://www.ceremade.dauphine.fr/~cohen/recentpub2.html

  Laurent D. Cohen, Fethallah Benmansour, Philippe Charles Douek, Maciej Orkisz, M. A. A. Zuluaga, Eduardo Davila, Ron Kimmel, Alexander Brook, Nir Sochen To cite this version: Laurent D. Cohen, Fethallah Benmansour, Philippe Charles Douek, Maciej Orkisz, M. A. A. Zuluaga, et al.. Vessel Segmentation on Computed Tomography Angiography. Daguesh Science, 2010, 71, pp.25. hal-00701410 French Partners: Laurent D. Cohen and Fethallah Benmansour, CEREMADE, Université Paris Dauphine; Philippe Douek, Maciej Orkisz, Maria Alejandra Zuluaga and Eduardo Davila, Creatis Lyon. Israeli Partners : Ron Kimmel and Alexander Brook, Technion; Nir Sochen, Tel Aviv University. This short paper describes our contribution in the research aimed at model based vessel segmentation on CTA. Although each partner was involved in a main subject among what follows, the contribution is a joint effort of all the partners, as a result of regular visits in France and Israel, as well as between partners in each country. The French Hospital Partner in Lyon provided a large set of CTA studies, including sets with two studies performed on each patient and about 20 studies suitable for work on other aspects of cardiac vessel segmentation.