IROS2019国际学术会议论文集 1148

Lane Marking Learning based on Crowdsourced Data David Pannen1 Martin Liebner1and Wolfram Burgard2 Abstract In this paper we propose a new algorithm that de rives lane marking maps from crowdsourced data We process the data in four steps i We make use of a point landmark map and if available an existent lane marking map for trajectory optimization and alignment ii use a custom DBSCAN variant to cluster observations that belong to the same lane marking iii apply a novel graph fi tting approach to extract lane marking dashes lines and even complex structures such as splits and merges and iv optimize the graph geometry with domain knowledge The process of point landmark and lane marking based trajectory alignment and the lane marking derivation is repeated iteratively to improve the results Evaluation is carried out on a 9km highway section by comparison with high accuracy aerial photographs and manually labeled ground truth lane markings I INTRODUCTION Automated Driving is promising a safer more comfortable and more effi cient future of transportation To achieve this goal high defi nition digital maps HD maps enable the car to augment its sensor readings with prior beliefs detect sensor outliers and extend the foresight of the vehicle In the event of sensor outages and challenging environmental conditions the baseline knowledge of drivable lanes and lane connectivity contained in HD maps offers a fallback for safe trajectory planning and decision making The HD map must be updated frequently to incorporate inevitable changes in the environment With current state of the art mapping vehicles these updates can only be created in large time intervals as mapping vehicles with high accuracy sensor equipment are expensive The mapping company HERE for example had a worldwide fl eet of just over 200 mapping vehicles in 2015 1 which limits the achievable frequency of visits and makes it impossible to achieve an acceptable update rate As an outdated map could lead to uncomfortable maneu vers or even accidents when used by autonomous driving functions car manufacturers like BMW have recently started to collect anonymized fl oating car data FCD from their fl eets 2 5 Due to cost and bandwidth limitations in these vehicles sensors must be cheaper and the data transmission rate has to be lower compared to dedicated mapping vehicles Thus the collected data is sparser noisier and compressed The image processing is carried out on board the vehicle and instead of video streams or point clouds only abstracted high level features such as lane marking observations or traffi c sign positions are transmitted 1D Pannen and M Liebner are with BMW Group 80788 Munich Germany firstname lastname bmw de 2W Burgard is with the Department of Computer Science University of Freiburg Georges K ohler Allee 080 79110 Freiburg i Br Germany burgard informatik uni freiburg de In our previous work we introduced a method to detect outdated regions based on these features 6 However the same data can not only be used for change detection but also to generate map patches Lane markings are of partic ular interest as they represent a frequently available visual landmark for localization purposes and allow to infer the drivable lanes of a higher level road model A Related Work For the extraction of individual lane markings different strategies have been proposed Pink et al used high accuracy aerial images to extract lane markings on a pixel basis with a Support Vector Machine classifi er 7 For each lane marking their chosen representation is a centroid with an associated length and orientation for visualization purposes Another approach based on similar input data was proposed by Azimi et al 8 They developed a pixel wise semantic segmenta tion solution based on fully convolutional neural networks with discrete wavelet transforms Another proposed strategy similar to our problem suggests using data from multiple drives with vehicles equipped with lower quality sensors Naumann et al for example extract a map representation consisting of a global map with a reference line and a number of local maps storing lane marking information in a grid Their approach requires the vehicle to observe the reference line in every situation which is a strict requirement in multi lane highway scenarios Schreiber et al generate a globally referenced lane marking map with graph based simultaneous localization and mapping SLAM in rural road scenarios 9 They use the lane marking signature describing the relationship between individual lane marking dashes to solve the association problem between multiple drives The applicability of their approach to highway scenarios remains unclear as highway environments are often highly symmetric and repetitive which makes solving the association problem much harder The use of crowdsourced vehicle data necessitates the fi tting of lane marking candidates to a large number of individual lane marking point observations In the robotics community similar problems arise in abstracting and com pressing sensor data Laser scanners for example generate large point clouds that often need to be transformed into an effi cient representation for storage and comparison Thus different techniques for feature extraction have been devel oped Veeck et al show an approach for fi tting polylines to two dimensional point clouds 10 Latecki et al use an expectation maximization algorithm to represent point clouds with a set of line segments 11 2019 IEEE RSJ International Conference on Intelligent Robots and Systems IROS Macau China November 4 8 2019 978 1 7281 4003 2 19 31 00 2019 IEEE7040 B Problem addressed In this work we propose a new method for extracting lane marking maps based on crowdsourced vehicle data As lane markings can form complicated structures such as splits and merges traditional polyline based approaches 10 do not offer a suffi cient representation Pixel or grid based approaches 7 8 on the other hand have the downside of requiring a lot of storage and bandwidth respectively when being transmitted as part of a map update to the vehicle fl eet We therefore propose a graph based approach that can represent complicated lane marking structures in a compact fashion The main contribution of this paper is a new graph fi tting algorithm for lane marking structures We further employ the well known density based spatial clustering of applications with noise DBSCAN algorithm 12 with distance functions tailored specifi cally to the characteristics of sparse and noisy lane marking observations Finally we describe the integration of our approach into a more general pipeline and evaluate its results for highway sections around Munich II APPROACH This section describes our approach for learning individual lane markings based on crowdsourced vehicle data The data is obtained from measurement campaigns with close to series production test vehicles It is sparser and noisier than the high accuracy sensors used in state of the art mapping vehicles due to the cost of the sensors and bandwidth limitations In the preprocessing steps of our approach global navigation satellite system GNSS and odometry measurements are used alongside point landmark observations such as traffi c signs or refl ector poles to provide the best possible estimate of each vehicle trajectory This procedure is described in Sec II A whereas Sec II B II C II D and II E explain the subsequent observation extraction observation clustering graph fi tting and graph optimization steps that are necessary to obtain the lane marking map An overview of these steps and the data fl ow is given in Fig 1 A Trajectory Optimization and Alignment For each crowdsourced trajectory an optimization and alignment step are conducted In the optimization step available GNSS measurements are combined with odometry measurements in a graph SLAM approach and solved with the open source graph optimization framework g2o 13 In the alignment step the optimized trajectories are aligned with the help of point landmark observations such as traffi c signs refl ector poles or traffi c lights and a point landmark map that for the purpose of this paper is assumed to be provided When learning in an iterative fashion the learned lane markings and road edges from a previous iteration can also be used for alignment B Observation Extraction From the aligned trajectories we can extract the desired lane marking observations Each trajectory data set contains a list of grouped lane marking observations These groups Fig 1 Processing steps for lane marking derivation consist of a time sorted list of observations that belong to the same lane boundary e g the boundary to the left of the vehicle These observation groups can extend over long distances and include lane dashes as well as the gaps between them However observations are always reported on actual lane markings and never in the gaps The sorted list of observations allows us to estimate an orientation for each individual observation by evaluating the direction to the successive observation For the defi nition of orientation in 3D space we use that of a Cartesian east north up ENU coordinate system However the vector connection between two points in 3D space only partly defi nes the orientation of the local coordinate system as the rotation angle around the vector axis is not defi ned Therefore we need to introduce the additional assumption that the angle between the up axis of the lane marking orientation and the up axis of the vehicle orientation should be minimized With both constraints the problem of estimating the orientation is solvable and we are able to augment the position information of the observations with an orientation estimate Examples of the deducted orientations can be found in the visualization of the clustering result in Fig 2 C Observation Clustering In this step we try to fi nd clusters in the observations that belong to the same individual lane marking There are a number of challenges associated with the characteristics of the problem The number of individual lane markings and therefore the number of clusters to be found is unknown The cluster shape can vary signifi cantly depending on the kind of lane marking to be observed For example during splits and merges on the highway Y shaped lane markings are common Solid lines can extend over signifi cant lengths while individual dashes can be quite short 7041 Fig 2 Clustering result of DBSCAN Different clusters are shown with different colors The orientation of each cluster pose is indicated by a small right handed coordinate system with the red axis pointing forward the green axis pointing left and the blue axis pointing upwards The dataset contains outliers resulting from sensor noise and wrong landmark associations in the preprocessing pipeline see Sec II A Due to the characteristics of the problem at hand a density based clustering approach namely the DBSCAN algorithm is chosen The output of the algorithm is a set of clusters containing lane marking observations that belong to the same individual lane marking structure as shown in Fig 2 1 DBSCAN The DBSCAN used in our approach is a slightly modifi ed version of the standard DBSCAN algorithm 12 that uses the two distance functions described in Sec II C 2 To improve the computational speed of the clustering a k dimensional k d orthogonal range search tree is employed to preselect potentially close poses before the actual distance calculation This improves the computational complexity from O n2 to O nlogn 2 Distance Functions Our implementation of the DB SCAN uses two distance functions in order to determine if two candidates are close If both distances are below defi ned thresholds the poses are determined close This is equivalent to a combination of both distance functions with appropriate step functions into a single distance function that could be used in the standard DBSCAN However our approach only needs to compute the second distance function in case the fi rst distance is below its threshold because we use short circuit evaluation in the logical AND conjunction The distance functions must be able to model the density of observations that belong to the same lane marking The position of each observation depends on many factors First the observations are not conducted continuously but at a defi ned sampling rate Depending on the velocity of the vehicle points observed on the same line will be distributed along the line with a comparably large distance between individual points Second each observation and the cor responding vehicle pose is subject to a comparably small deviation due to errors and noise Our density based cluster ing algorithm should therefore assign a different weight to distances in longitudinal direction which can be quite large due to the sampling characteristic of our sensor compared to the distances in lateral or vertical direction that are purely due to measurement errors This is achieved by the mean orientation weighted Euclidean distance To guarantee that the mean orientation that defi nes the longitudinal direction is an accurate approximation we limit the accepted differ ence in orientation between any two observations with the second distance function This has the pleasant side effect of rejecting outliers and of separating crossing lane markings into different clusters As the DBSCAN has an undefi ned and potentially random traversal of the dataset we require the two distance functions to obey symmetry a Weighted Euclidean distance This function mea sures the weighted Euclidean distance between two obser vations in a local coordinate system Due to the symmetry requirement of the DBSCAN we choose the mean orienta tion of both observations as the local coordinate system Thus the fi rst step is calculating the mean orientation from the two observations According to Markley et al 14 the mean orientation quaternion q is the eigenvector corresponding to the maximum eigenvalue of matrix M where M is defi ned as M n X i 1 wiqiqT i 1 This general case is applicable to averaging n orientations represented as quaternions qiand individually weighed with wi In our case n 2 and wi 1 as we have only two orientations and they should be equally important Having determined the mean orientation we now transform both observation coordinates x1and x2from the global reference system into the mean orientation local coordinate system This is achieved with the standard quaternion rotation for mula representing the global observation coordinates as pure quaternions p with vector part x p0 qp q 1 2 The vector parts of the resulting quaternions p01and p02 represent the observation coordinates u1and u2 defi ned in 7042 the local coordinate system The last step is to calculate the weighted Euclidean distance between u1and u2 d u1 u2 v u u t 3 X i 1 t2 i u1 i u2 i 2 3 Here the weight is specifi ed as 1 t2 i with the variable ti describing the scaling factor for dimension i The resulting distance d is unitless as the parameters ti are specifi ed in meters In our case we have three dimensions and therefore three parameters For the longitudinal clustering threshold t1 two requirements are important First successive points along the same lane marking should belong to the same cluster Second in the case of dashed lane markings the gaps between them should brake the clusters apart Therefore a compromise must be found that allows the clustering algo rithm to fulfi ll both requirements For the highway situations at hand with high speeds and comparably large gaps a longi tudinal threshold of 2 5m was chosen A lateral threshold t2 of 0 9m proved to be able to separate observations between lanes but also account for small deviations due to noise and inevitable inaccuracies during the preprocessing of the data In the vertical direction a threshold t3of 2 5m was chosen to separate observations from different streets like overpasses but account for larger deviations in vertical direction due to GNSS noise and preprocessing errors Finally the two observations are considered close if the unitless distance value is below 1 0 which is equivalent to the scaled distance vector endpoint lying inside a unit sphere around the vector start point This corresponds to an ellipsoid for the unscaled distance vector with principal semi axes t1 t2and t3 b Angular orientation distance The previous section described the calculation of a weighted Euclidean distance based on the mean orientation of two poses However this approximation is only valid as long as the two orientations are comparably similar Therefore we introduce a second distance metric to limit the difference in orientation We use a metric based on the inner or dot product of quaternions q1and q2as suggested by Huynh 15 arccos q1 q2 4 As the angle between orientations is twice the angle between unit quaternions we compute the angular ori entation distance as 2 2arccos q1 q2 5 is given in radians and lies in the range of 0 For our problem we found an angular orientation distance threshold of 5 approximately 0 087rad to give a suffi cient compromise between tracing lane markings around corners and discarding outliers D Graph Fitting After separating observations into clusters in the previous section we now fi t an initial lane marking structure to each cluster independently Due to the diversity of lane markings a Center point extraction and shell assignment b Clustering within each shell c Initial Graph Fitting d Graph Optimization Fig 3 Graph Fitting and Optimization steps 7043 on the road the algorithm must be able to handle curves splits and merges This poses the problem that existing approaches from literature for fi tting polylines such as 10 cannot be applied Therefore a graph structure containing polylines and nodes was chosen as a generic lane marking model and a new Shell Graph Fitting algorithm was devel oped It consists of the following steps 1 Shell assignment 2 Shell clustering 3 Initial g