{'fraction_non_alphanumeric': 0.038428656920577925, 'fraction_numerical': 0.008036248610754894, 'mean_word_length': 4.623798076923077, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DA-LMR: A Robust Lane Markings Representation for Data Association Methods

While complete localization approaches are widely studied in the literature, their data association and data representation subprocesses usually go unnoticed. However, both are a key part of the final pose estimation. In this work, we present DA-LMR (Delta-Angle Lane Markings Representation), a robust data representation in the context of localization approaches. We propose a representation of lane markings that encodes how a curve changes in each point and includes this information in an additional dimension, thus providing a more detailed geometric structure description of the data. We also propose DC-SAC (Distance-Compatible Sample Consensus), a data association method. This is a heuristic version of RANSAC that dramatically reduces the hypothesis space by distance compatibility restrictions. We compare the presented methods with some state-of-theart data representation and data association approaches in different noisy scenarios. The DA-LMR and DC-SAC produce the most promising combination among those compared, reaching 98.1% in precision and 99.7% in recall for noisy data with 0.5m of standard deviation.


I. INTRODUCTION
Localization is an essential part of autonomous driving. For past years, there has been a wide variety of works in different approaches like Simultaneous Localization and Mapping (SLAM) [1], localization in previously built HD maps [2], and geo-referencing using aerial imagery [3]. A data association process becomes necessary for all these approaches to find one-to-one correspondences between landmarks in maps and detections from the onboard sensors. The typical models used in localization, such as factorgraphs or Bayesian filters, need these correspondences for the inference. Then, the final result of these associations is crucial for the agent pose estimation.
The landmarks and detections used in the process usually depend on applications and the localization approaches used. In SLAM or localization in HD maps, in roads and cityscapes, lane markings, poles, traffic signs, and traffic lights are usually used in the last years. While these maps usually provide high local accuracy, they also suffer drifts that produce inaccurate global consistency due to accumulated errors. To avoid this effect, another approach in localization is geo-referencing, where local detections from sensors are aligned with landmarks from aerial imagery. Fig. 1. An overview of a complete localization system, where the data representation and data association play a key role. Our research focuses on evaluating these modules (inside red dashes) by comparing the presented DA-LMR and the DC-SAC with state-of-the-art approaches.
Hence, from aerial imagery, traffic signs and lights are unobservable, and poles are hard to detect. Here, lane markings are the potentially best observable marks for geo-referencing approaches. These lane markings are usually represented in maps as polylines and dashes.
The question that arises at this point is how to represent polylines and dashes for the data association process. In most works in the literature, there is no evaluation on how polylines and dashes representation can affect the data association, and therefore, the final result of localization. This matter usually goes unnoticed. For this reason, in this paper, we focus our research on evaluating different data association methods using different data representation (yellow and green modules in Fig. 1). For this, we propose the Delta-Angle Lane Markings Representation (DA-LMR), which represents polylines and dashes as points where an additional dimension represents a proportional value of the differential angle concerning the adjacent line segments. In addition, for data association, we propose a heuristic version of RANSAC, called Distance-Compatible Sample Consensus (DC-SAC), that limits possible samples to distance compatible ones.
To summarize, the main contributions are the following: representation and data association common state-ofthe-art approaches, including those proposed in this paper. One of the possible applications of the data representation and data association proposed in this work is the georeferencing localization using aerial imagery. For this reason, we present this work assuming a 2D world representation.

II. RELATED WORK
In this section, we give a brief review of existing data association methods and the different data representations for lane markings.

A. Data Association
We review the data association approaches distinguishing into two different categories: pose estimation and graphtheoretic.
In pose estimation, one of the most widely used approaches for data association in localization is Iterative Closest Point (ICP). SLAM approaches such as Hector SLAM [5], among others [6], [7], rely on the ICP for LiDAR scan matching. Currently, state-of-the-art Lidar Odometry And Mapping (LOAM) approaches also implement ICP for the data association process [8], [9]. Nevertheless, this is a local approach; hence, it requires a fine initialization to converge in a global minimum. Further, it is more sensitive to suffer drifts in high outlier scenarios. Therefore, we do not consider ICP a potential solution for data association in the context of geo-referencing using aerial imagery. In that case, the initialization is not usually fine because it depends on GNSS sensors, producing high noise and, in some cases, multipath problems. The random Sample Consensus (RANSAC) method [10] is a global data association approach common in the literature. RANSAC follows a strategy that samples hypothesis in SE(2) transformations depending on the data structure. Different authors use RANSAC for localization [11], [12] (include aerial imagery-based [3], [13]), mapping [14], and loop closure [15].
The graph-theoretic approach is based on searching a maximum number of associations being distance compatible (DC). This problem is also known in the literature as the maximum clique (MC) problem [16]. In the past decades, this approach has been used in localization [17], including loop closures [18], [19]. This is also a global data association approach, and we consider it potentially suitable for localization in aerial imagery. In past years, there have been researches focused on a weighed version of the MC problem [20], [21]. An interesting variant is CLIPPER [22], where the authors implement a weighed MC problem using a continuous relaxation for the optimization process.
It is worth noting that there are other data association approaches that we don't include in this work because we consider strongly coupled to the SLAM problem. That is the case of the Hungarian method [23], Nearest Neighbor (NN) [24], Joint Compatibility Branch and Bound (JCBB) [25], [26], probabilistic data association based on Mixture Models [27], [28], and Multi-Hypothesis based data association [29], [30].

B. Data Representation
The most common approach presented in the literature to represent data in the data association process is 2D points for 3-DOF localization [31], [32]. To represent lane markings as 2D points, a previous sampling of polylines becomes necessary. When this process is computed for both landmarks and detections, it is called Point-to-Point (P2P) association. Another strategy is the Point-to-Line association (P2L) [33], [34]. In this case, the authors project point detections in the landmarks polylines in each pose estimation iteration. However, after projection, the polylines (landmarks) are sampled and converted into 2D points, and roughly speaking, the representation comes to the P2P strategy. Hence, we consider both strategies, P2P and P2L, as unique 2D pointsbased representations. In other works [3], [35], the authors represent the data as lines, also with a previous sampling. In these cases, the authors use a distance metric for line segments, such as Hausdorff distance [36], [37].

III. DELTA ANGLE LANE MARKINGS REPRESENTATION (DA-LMR)
As discussed in Section II-B, the most common representation of lane markings in the process of data association is point-based representation. Nevertheless, transforming lines and polylines into isolated points entails a loss of data structure information. In a polyline, how the angle of each point changes in a curve provides additional information about the geometric structure of that curve. Following this assumption, we present the Delta-Angle Lane Markins Representation (DA-LMR). In the following subsections, we explain how to derive this representation for both polylines and dashes.

A. DA-LMR for polylines
We can describe a polyline as a set of 2D points given this connection, we can describe the polyline as a Vectorial representation provides information about the orientation of each i-th point in a polyline. However, representing the orientation in the reference frame can lead to problems due to the Euler angle limitations. To obtain a compact and invariant angle representation, we use the differential angle between adjacent vectors v i−1 and v i . Then, for each i-th point in a polyline, we can obtain the delta-angle as follows: It is worth noting, that the points i = 0 and i = N does not have adjacent information, and therefore we assign them a default value of ∆α 0 = ∆α N = 0. The delta-angle calculation defined in (1) is a non-oriented angle calculation. This entails that the representation is also invariant to the direction in the polyline, i.e., we can sort the polyline from 0 to N or from N to 0, obtaining the same result. In Fig. 2, we show an example of this direction invariance.
As the final step of DA-LMR, we use delta-angle information as an extra dimension in the 2D point representation to obtain a compact description suitable for data association methods. Now, the polyline is converted in a set of 3D points Here w is a weight that tunes how strongly the deltaangle describes the data structuring. Note that when w − → 0, the representation tends to traditional 2D representation. In Fig. 3, we show an example of the DA-LMR in contrast to line segments representation and 2D points representation. In the case of DA-LMR, we represent the Z-axis value as the proportional size of the circles. In terms of information theory, we consider this representation richer than the other commonly used in the literature. Depiction of two dashes intersecting in its centroid. If we compute the distance measurement (3) for 2D points representation, the result is d pt ij = 0. However, this doesn't represent a good measure because they are misaligned. If we compute (3) for DA-LMR, the result is d dalmr ij = ∆α ij w, which encodes more realistic information about the distance between these dashes.

B. DA-LMR for dashes
For dashed lines, it is not trivial to determine adjacent lines. Hence, for that case, we move the representation formulation to the distance measurement step in the data association process. This distance could be used for the error measurement in pose estimation data association, or otherwise, for distance compatibility measurement in graphtheoretic data association.
We can describe dashes as vectors where v = (x 2 − x 1 , y 2 −y 1 ), and where subscripts 1 and 2 denotes start point and end point, respectively. Then, given a pair of dashes v i and v j , we can formulate the distance measurement for DA-LMR as follows: Where (x i , y i ) and (x j , y j ) are the centroid of each dash respectively. And where: In Fig. 4, we show an example of two dashes intersecting in its centroid but misaligned. In this case, if we use 2D points representation, we obtain a distance measurement d pt ij = 0 (expression (3)), which doesn't describe the misalignment. Nevertheless, using DA-LMR, we obtain a distance measurement d dalmr ij = ∆α ij w that provides more realistic information.

IV. DC-SAC DATA ASSOCIATION
Distance-Compatible Sample Consensus (DC-SAC) could be seen as a heuristic version of the RANSAC method. This is a formalization of a previously used in [4] for camera-LiDAR calibration approach. In [38], the authors propose a similar approach but focus on dense point clouds and geometric descriptors. This is a pose estimation method that samples the possible transformations. How to sample the data for a ∆ T ∈ SE(2) transformation candidate is the key difference between RANSAC and DC-SAC.
Given a set of landmarks L and a set of detections D, RANSAC chooses a pair of points randomly from each set. Thereafter, it estimates ∆ T ∈ SE(2) by minimizing: Superscripts l and d means landmarks and detections, respectively. Then, all the points in D are transformed using the estimated ∆ * T , obtaining a new set D * . Thereafter, an error is computed by the sum of the distance measurement between each detection in D * and the nearest neighbor in L. RANSAC iterates this process obtaining a new in each iteration until the error satisfies the condition < ξ, where ξ is a configurable threshold. The threshold limits the accuracy of the method. For example, a high value for ξ can miss potentially optimal hypotheses producing inaccurate results. In contrast, a low-value configuration of ξ can dramatically increase time-consuming in the process that could make the method unusable.
In the case of DC-SAC, we sample a pair of points in D. However, in contrast with RANSAC, we randomly choose a pair of points in L that are distance compatible, i.e., that satisfies: Where γ is a configurable value. The constraint proposed in (6) could be applied in a general way for data association. Additionally, as we present this work in localization, we can propose other constraints in the hypothesis space H depending on the uncertainty of the prior. Given the distribution of localization, we can get the standard deviation values for each dimension (σ x , σ y , σ θ ). Then, by taking σ x and σ y values, we can limit the area of sampling points in L. By using σ θ and given v l = (p l 1 − p l 2 ) and v d = (p d 1 − p d 2 ), we can define an orientation constraint between pairs of samples as follows: Where θ t is a configurable value that depend on σ θ . The above-presented heuristic constraints reduce the size of H dramatically. In this way, we can search the full space H for the minimum value of instead of iterating until < ξ. This is the best scenario for converging to a potentially optimal solution. In the next section, we demonstrate experimentally how DC-SAC produces more accurate results than RANSAC by configuring a value of ξ where both methods run with a similar time consumption.

V. EVALUATION
The evaluation step aims to compare the presented DA-LMR with other data representations as well as the presented DC-SAC with other data association methods. Nevertheless, it is difficult to perform a quantitative comparison using maps and real onboard sensor data due to the hard ground truth obtention. Hence, in Section V-A, we generate syntheticdetections D s by cropping, transforming, and adding noise Comparison in F1 score (solid), precision (dotted) and recall (dashed) metrics between LSR, PR, and DA-LMR for CLIPPER [22] data association method. Comparison in F1 score (solid), precision (dotted) and recall (dashed) metrics between LSR, PR, and DA-LMR for Max Clique [39] data association method. from the original landmarks L that comes from a real map. In Section V-B, we show qualitative results using the previously used L and real detections D r from stereo cameras in a real autonomous vehicle.

A. Quantitative results
For quantitative evaluation, we use a map that contains continuous and dashed lane markings. This map was labeled by hand from aerial imagery from the city of Karlsruhe, Germany. We define the set of landmarks L by sampling the map polylines with steps of 1 m, and we use this labeled data as ground truth. Then, using a pre-recorded trajectory in the mapped area as a reference, we apply a sliding window to L. In each iteration, we crop a set of data that forms a new D s i , where the subscript i indicates the iteration of the sliding window, and the superscript s denotes synthetic. Thereafter, we apply a random 3-DOF rigid body transformation t = (t x , t y ) and R = f (r θ ) to each D s i . Where t x and t y are uniformly distributed random variables Comparison in F1 score (solid), precision (dotted) and recall (dashed) metrics between LSR, PR, and DA-LMR for the proposed DC-SAC data association method. with range (−5 m, 5 m), and where r θ is also uniformly distributed random variable with range (−5°, 5°). Also, for each experiment, we produce additive Gaussian noise with a range of σ between 0.1 m and 0.5 m with steps of 0.1 m. Finally, we include outliers, where the number of outliers is 10 % of the samples in D s i . It is worth noting that it is not recommendable to execute the data association process in the complete set L. Hence, assuming we have a prior localization, we generate a set L i bigger than D s i in each ith iteration of the sliding window that covers an area around it.
At this point, given L i and D s i , we run a data association process for each data representation and each σ value of the range mentioned above. We use the representations shown Fig. 3, i.e., line segments representation (LSR), 2D points representation (PR), and the proposed DA-LMR with w = 5 m rad . For metrics, we use euclidean distance for PR and DA-LMR and Hausdorff distance for LSR. Finally, we repeat the process for the different data association methods: CLIPPER [22], Max Clique [39], RANSAC [3], and the proposed DC-SAC.
In Fig. 5, we show a comparison in F1 score, precision and recall metrics between the representation approaches proposed for the CLIPPER [22] data association method. The statistics are accumulated for all i values, i.e., for the complete pre-recorded trajectory. For this experiment, we configure the distance compatibility (6) parameter as γ = 3σ. As we can see in Fig. 5, DA-LMR improves the results of PR for both precision and recall. LSR shows the best results in precision. However, it generates the worst results in recall. In other words, LSR can associate less data than the other, but with better precision.
In the case of Max Clique [39], for this experiment, we also configure the distance compatibility (6) parameter as γ = 3σ. We can see in Fig. 6 that the behavior of the different representations is similar to the previous. But in this case, LSR seems more sensitive against the noise in recall statistics than PR and DA-LMR.
For RANSAC [3], we configure ξ with a value that produces a computational time similar to the DC-SAC method. The results for RANSAC are strongly correlated with the threshold ξ. For this reason, the results are stable against the noise. We can see this behavior in Fig. 7 for PR and DA-LMR, where DA-LMR improves the results of PR. However, LSR shows different behavior and presents less stability against noise again.
In Fig. 8, we compare the data representation approaches proposed using the presented DC-SAC data association method and configure γ = 3σ. In this case, we can see the best results in precision with DA-LMR. While in recall, LSR shows the best results, but the difference is relatively small.
In general, LSR shows good results in low-noise scenarios, but it is more sensitive to noise disturbances. The PR and DA-LMR show more robustness against noise, and DA-LMR improves the results of PR in all cases.
Comparing the data association methods, we found the graph-theoretic ones (CLIPPER and Max Clique) more sensitive against noise. Especially the CLIPPER method. Max Clique shows good results for low-noise, but for high noise, the precision is similar to RANSAC and the recall much worst. In contrast, we found the pose estimation methods more robust against the noise. RANSAC shows reasonably good results. In precision are similar to the worst case of Max Clique, but in recall shows more stability. DC-SAC shows, in general, the highest percentages in precision and recall and, like RANSAC, high robustness against noise disturbances.
Finally, in Table I, we show the evaluation of the computational time for each data association and each data representation depending on the samples number |L i |+|D s i |. The experiments were performed on an i7-7700HQ CPU with 16 GB of RAM in a C++ compiled code. We can see that RANSAC and DC-SAC show similar results for the configuration described in this section and are reasonable. In the case of the Max Clique, it improves the time consumption for low sample scenarios, but for > 200 samples, it is slower than SAC-based methods. The CLIPPER method results slowest of all. Even for 400 samples, the CPU cannot run a complete process. Comparing data representation, LSR shows slower behavior than PR and DA-LMR for SAC-based methods. However, in graph-theoretic-based, the behavior is different. In that case, LSR is faster than the others representations. In all cases, DA-LMR is faster than PR. As we obtain the highest values on precision and recall, we consider that the combination of the presented data representation DA-LMR, and the presented data association DC-SAC, are the potentially best combination among evaluated for a localization application and in special for geo-referencing using aerial imagery.

B. Qualitative results
In Section V-A, we compared different data association methods with different data representations, and we concluded that DA-LMR and DC-SAC are our preferred combination. In this section, we show some qualitative results with the choose combination. For the evaluation, we use the same map as in the previous section and the same prerecorded trajectory. Then, we have the same L i as a set of landmarks for each sliding window iteration. However, in this case, we use real data for detections (D r i ) obtained during the pre-recorded trajectory applied for the sliding window. This process of detection was performed using stereo cameras from our experimental vehicle BerthaOne [40]. Then, given L i and D r i , we run the process of DA-LMR and DC-SAC for the complete trajectory.
In Fig. 9, we show some examples of data association results. In red, we show the L i , while in blue, we show D r i . Green lines indicate the association between landmarks and detections. The size of circles is proportional to the Z-axis value. The results look very reasonable for its implementation in a complete localization approach.

VI. CONCLUSIONS
We proposed DA-LMR, a robust data representation for lane markings in data association processes for localization approaches. As we demonstrate experimentally, this representation provides richer information of geometrical data structure than others, such as line segments and points representations. Furthermore, we proposed DC-SAC, a data association method that can achieve an optimal solution by reducing the hypothesis space using distance compatibility constraints. We also demonstrate experimentally how the presented method improves the results of other state-of-theart ones, such as RANSAC, Max Clique, and CLIPPER.
In future work, we will apply the combination of DA-LMR and DC-SAC for a geo-referencing localization using aerial imagery. Although we have emphasized this kind of localization in this work, we also plan to apply the presented method to localization in HD maps.