key: cord-0058273-2v0js27d
authors: Hofstetter, Isabell; Springer, Malte; Ries, Florian; Haueis, Martin
title: Constellation Codebooks for Reliable Vehicle Localization
date: 2021-03-17
journal: Pattern Recognition
DOI: 10.1007/978-3-030-71278-5_22
sha: 548f4efd4609d81b007f295a969e1425422cc703
doc_id: 58273
cord_uid: 2v0js27d

Safe feature-based vehicle localization requires correct and reliable association between detected and mapped localization landmarks. Incorrect feature associations result in faulty position estimates and risk integrity of vehicle localization. Depending on the number and kind of available localization landmarks, there is only a limited guarantee for correct data association due to various ambiguities. In this work, a new data association approach is introduced for feature-based vehicle localization which relies on the extraction and use of unique geometric patterns of localization features. In a preprocessing step, the map is searched for unique patterns that are formed by localization landmarks. These are stored in a so called codebook, which is then used online for data association. By predetermining constellations that are unique in a given map section, an online guarantee for reliable data association can be given under certain assumptions on sensor faults. The approach is demonstrated on a map containing cylindrical objects which were extracted from LiDAR data. The evaluation of a localization drive of about 10 min using various codebooks both demonstrates the feasibility as well as limitations of the approach.

High definition (HD) maps are essential to enable safe highly automated driving. Consequently, reliable and accurate vehicle localization in such maps is inevitable. In the past years, various feature-based localization approaches have been introduced. These methods utilize a separate map layer containing localization features, also called landmarks, which they aim to associate with detected features in the vehicle's surrounding. The resulting association constraints pose an optimization problem, which is solved for an accurate pose estimate.

State-of-the-art methods differ mainly in the kind of localization features that are used. Whereas some approaches rely on dense point clouds such as visual point features [17] or RADAR point clouds [16] , other methods make use of landmarks such as road markings [11, 15] , or geometric primitives [4, 7] . However, all these methods imply some kind of feature association. Especially in those cases where localization features are sparse and do not have an expressive descriptor, data association represents one of the main challenges for reliable vehicle localization. To satisfy integrity requirements, a guarantee for correct data association is desirable.

This contribution focuses on the extraction and use of unique landmark patterns, hereafter referred to as constellation codebooks, for reliable data association. Landmarks used for localization often appear in periodic orders, so that many ambiguities arise in the data association step. This contribution suggests to identify that specific geometric information which breaks the symmetry and to cluster landmarks such that the resulting feature patterns reflect the uniqueness of the environment. This enables reliable feature association even in sparse feature maps.

The proposed approach consists of a two-step process: In a first step, a given map of localization features is searched for such unique geometric patterns of landmarks. In this work, these constellations are referred to as codewords. All extracted codewords are stored in a codebook, which can then be used online for vehicle localization. For easy and fast search and access, this work suggests to store the codebook in a hash table format.

During the localization drive, the geometric patterns of detected localization features are compared to the codebook content. As soon as one of the codewords is detected online, incorrect associations can be excluded and a certain guarantee can be given that the resulting associations are correct. Hereby, the suggested data association approach, which is based on Geometric Hashing [19] , does not make any assumptions on prior vehicle poses. It allows for feature association based only on the geometric information provided by the extracted features, while ambiguities are eliminated due to the preprocessing step.

The method is derived and tested on a dataset representing an urban loop of 3.8 km in Sindelfingen, Germany, where pole-like features are used as localization landmarks. The method, however, is not limited to this specific kind of features and can easily be adapted to arbitrary localization features. Experimental results verify the potential of the proposed approach.

In order to provide reliable localization that meets high integrity requirements, most approaches rely on outlier detection and exclusion [1, 21] or pattern matching techniques [2, 7] to avoid incorrect associations between map and sensor data. By accumulating sensor features and matching a group of landmarks with the map, these approaches try to reduce or even eliminate the number of ambiguities in data association and exclude associations that are found to be outliers. A major drawback of most approaches is the assumption that a certain number of correct associations is found and only a small percentage of outliers needs to be eliminated. Also, a guarantee that all outliers are excluded or that the correct alignment with the map is found cannot be given. [4, 14] for vehicle localization. By deriving a descriptor for cylindrical localization features based on other features in the near surrounding, they notice that such patterns can be ambiguous as well and not every accumulated pattern of localization landmarks provides enough unique information for a reliable alignment with the map. The existence of ambiguities in data association is also discussed in [6] , where a method based on Geometric Hashing [8] for the extraction of such patterns is suggested. Applying the same Geometric Hashing algorithm for the actual feature association step has been introduced in [5] and a similar technique is used in this work. The main contribution of this work, however, focuses on the generation and use of constellation codebooks, i.e. unique geometric patterns of localization features.

Extracting unique information from the environment for localization has been considered in works like [9] . Here, a method is proposed for creating unique identifiers, called fingerprint sequences, for visually distinct locations using panoramic color images. Also, object recognition methods like Bag of Words approaches as utilized in [10, 20] are well known and provide a similar kind of vocabulary, however, without satisfying any uniqueness requirements. Furthermore, these methods have only been applied in the field of image data processing. To the authors' knowledge, the concept of identifying unique patterns in feature maps and the use of codebooks for localization has not been studied before.

In the following, a codebook is defined as a set of feature patterns, hereafter referred to as codewords. The codebook is computed for a given map or map section and used for feature-based vehicle localization. The proposed feature constellations, which are contained in a codebook must satisfy certain constraints in order to enable reliable vehicle localization. The main requirement is the uniqueness of the extracted constellations in a given map section. If a feature pattern is known to be unique in a map even under various sensor or map faults, this information can be used for reliable data association.

In the following subsections, the codebook generation is described in detail. This involves the derivation of various requirements for the constellations of interest, as well as a search algorithm for the identification of such feature patterns.

Feature patterns of interest are desired to be unique in a sense that they are uniquely associable in a given map section. This must still be true, even if the measurements of the landmarks are affected by noise. In other words: For a unique feature constellation, there exists no other approximative matching in the map section of interest than the correct one.

To describe these assumptions in a mathematical way, the distance d between single landmarks p = (x, y) ∈ R 2 and sets of landmarks

which is the distance of p to its nearest neighbor in G. Thus, the mean pointto-point distance between two sets of landmarks G 1 and G 2 with cardinality |G 1 | = |G 2 | can be defined as

Let T be the set of all euclidean transformations, i.e. all combinations of rotation and translation. Then, a pattern of landmarks C is unique in a map section M if

for F = C and a minimum distance . This means that considering any arbitrary transformation T eucl ∈ T , no subset F ⊂ M with |F | = |C| exists, whose mean distance to T eucl (C) is smaller than . Therefore, there exists only one transformation, which allows an approximative matching [3] of the constellation with the map, which is the identity transformation.

In the following, is also called uniqueness threshold, because the choice of is decisive for the classification of feature patterns in unique or ambiguous patterns. For large , less patterns will be identified as unique. On the other hand, for small , patterns that differ only slightly in their geometrical characteristics will be classified as unique, which results in less ambiguous patterns.

In practice, it is not feasible to find unique feature patterns in large maps of entire cities or even countries. However, a reasonable assumption is that an initial, very rough position estimate within a map is given. Therefore, the patterns of interest do not need to be unique within an entire map, but rather in a map section of limited size. In the following, the uniqueness requirement (3) will be limited to certain map tiles T of size R. Thus, R = ∞ refers to the entire map.

Also, to facilitate the detection of codewords C during the localization drive, the spatial expansion of codewords, i.e. the diameter of the smallest enclosing circle containing a codeword, should be limited. This can be described as

with a given maximum diameter L. (3) and (4) can be identified in a map M . The method is summarized in Algorithm 1.

In steps 1) and 2), the map is divided into map tiles of a given radius R. This parameter should be chosen in a way that the current map tile can always be found reliably, for example using a low-cost GPS module. Then, each tile is regarded separately.

First, all possible feature combinations of the desired cardinality s cw and expansion L are constructed. These are the candidate patterns which need to be classified into unique or ambiguous patterns.

Regarding a tile T i containing N f features, there are a total of N f scw constellations of s cw features. As an example, for N f = 50 and s cw = 3, there exist 50 3 = 19.600 constellations in total. For larger patterns of cardinality s cw = 6, there are almost 16 million different patterns. However, by limiting the constellation expansion to L as suggested by Eq. (4), this number of candidate patterns can be reduced noticeably.

All candidate patterns found in step 3) are then compared to each other and uniqueness requirement (3) is checked for a given uniqueness threshold . Here, scan matching methods like the well-known Iterative Closest Point (ICP) algorithm [13] can be used. If the constellation proves to fulfill the uniqueness requirement, it is added to the codebook. If it is not unique according to (3), the pattern is discarded. Finally, steps 3) -5) are repeated for each previously constructed map tile T i . 

The offline generated constellation codebook can now be used for the purpose of data association for vehicle localization. In order to allow an easy and fast recognition of codewords and a quick search for associations, in this work, a Geometric Hashing based method is proposed for the representation of codebooks as well as the actual data association step. Geometric Hashing was initially introduced in [8] for object recognition purposes. It is a popular technique for the association of geometric features that have undergone transformations. The method consists of a training phase as well as the recognition phase. During the training phase, features of interest are represented in a variety of coordinate systems that are defined by the features themselves and stored in a quickly searchable, tabular format. Online, a given input sample S can be searched for the objects of interest with the help of the previously generated hash table.

The following subsections will discuss a modified hashing algorithm which is suggested in combination with constellation codebooks as they were derived in Sect. 3. For further details on Geometric Hashing, the authors refer to [8, 19] or [12] .

For the generation of the hash table, which is used for codeword recognition during localization, each codeword is hashed separately. Details on the hashing procedure as well as the noise model will be discussed briefly. Noise Model. If the measured features are affected by noise, the positional error in the hash locations has to be described by a valid noise model. Obviously, the positional noise on the feature locations in the hash frame depends heavily on the chosen basis pair as well as the position of the features within the geometric basis. A small distance between basis pair features will enhance the noise in angular direction, while the noise in radial direction stays constant. Therefore, the authors suggest to estimate the resulting noise distribution in polar coordinates. For the underlying sensor noise, a Gaussian distribution with standard deviation σ is assumed, which is centered at the "true" location of the feature. A Monte Carlo Simulation is performed to generate noisy measurements, which are then transformed into the basis frame. For each geometric basis and each feature within that basis, the standard deviation in angular σ θ and radial σ r component are estimated using these simulated measurements and stored in the hash table for the online use. 

Given a sample of detected features D and the previously generated hash table H, feature associations can now be determined by searching the hash table. For more detail on data association for vehicle localization based on Geometric

Hashing the authors refer to [5] . In the following, the method will be briefly recapitulated.

First, two arbitrary detections p 1 , p 2 ∈ D are chosen, which define a geometric basis O (p1,p2) just as described before. All feature detections D are then transformed into this basis by a rigid transformation, quantized, and hashed accordingly. For each computed hash value, appropriate bins in the hash table H are accessed and a vote is given to each basis found there. In this step, not only the exact bin is accessed but also its direct neighborhood to ensure that noisy measurements that fell into neighboring bins can be associated as well.

Then, the set of bases B is determined that received as many votes as the number of features belonging to the codeword, namely s cw . These bases represent those codewords that could potentially be matched. Finally, the resulting candidate associations are validated based on the Mahalanobis distance between feature measurement in the hash frame and noise distribution, which is stored in the hash table.

If valid associations were found, the matching codeword is returned. Otherwise, the previously described steps can be repeated for each available basis pair k = (p i , p j ) with p i , p j ∈ D, i = j. In practice, not every generated basis will necessarily have a matching basis in the hash table. If a basis pair was chosen, which is not part of a codeword, the resulting basis cannot be matched with the hash table. Therefore, multiple bases have to be generated in order to find one that is part of a codeword.

The vehicle BerthaONE [18] was used for the acquisition of the dataset utilized to demonstrate and evaluate the proposed approach. A loop of about 3.8 km in an urban area in Sindelfingen, Germany, which results in about 10 min of driving time, was used for the evaluation. The corresponding localization map layer contains 593 cylinders such as traffic signs, tree trunks, and traffic lights as localization features, which were extracted from LiDAR data as described in [7] . Each cylinder is described by its center point (x, y) ∈ R 2 on the ground plane. The feature locations in map coordinates were shown in Fig. 1 . A reference solution for validation is provided by [17] .

The localization framework used to demonstrate the approach is visualized in Fig. 3 . A State-of-the-Art localization framework consisting of map, feature detectors, feature association, and optimizer is adapted and extended by a codebook generator and hashing functionalities. The main contribution of this work, namely the codebook generation and feature association, is highlighted in green. The hashing functionalities are highlighted in gray. Additional sensors, such as a GNSS receiver and an odometry unit, are added to the framework in dashed lines. These are optional components that are not needed for the data association step itself. However, the GNSS input can be used to determine the current map tile and odometry measurements could be utilized to improve the continuity of the localization solution whenever the suggested method is unavailable.

However, one of the biggest advantages of the proposed approach lies in the fact that no prior pose propagation is needed to find correct associations. Therefore, such information is completely neglected in this work.

To evaluate the described approach, a variety of codebooks is generated for the before mentioned map and used for localization. Parameters for the codebook generation that were examined in this work are the tile size R, the uniqueness threshold as well as the number of resulting codewords. All generated codebooks contain feature constellations of size s cw ∈ {3, 4} with a maximum constellation expansion of L = 35 m, which corresponds to the sensor range. Constellations of size s cw > 4 could also be extracted using the same method. However, this is something that was not evaluated, since no enhancement of the system availability is expected. Also, it is desirable to extract the minimal number of landmarks required to provide a reliable localization solution.

Depending on the chosen tile radius R and the uniqueness threshold , a different number of feature patterns was identified as unique patterns in the map ranging in between 0 up to 550.000 codewords. The numbers can be taken from Fig. 4 . Here, codebooks were generated for tiles of radius R ∈ {∞, 300m, 200m} and uniqueness threshold ∈ {0.25m, 0.5m, 0.75m, 1.0m, 1.25m}. For large uniqueness thresholds, the number of unique feature patterns decreases as expected. While there are more than 400.000 codewords using a tile size of R = 300 m and = 0.25 m, only 129 codewords are available for = 1.25 m and the same tile size. In the case of R = ∞, no codewords were found at all for > 0.75 m. Also, for decreasing tile sizes, the number of codewords increases. Looking at = 0.5 m, there are 17.802 codewords if the uniqueness is required in the whole map. For R = 300 m, this number increases to 62.939, and for R = 200 m to 104.491. As an example, a codebook for R = ∞ and = 0.5 m containing 17.802 codewords of 3 or 4 features is visualized in Fig. 5 . Each color represents the features that are part of a different codeword. It should also be noted that there are some parts in the map where the codeword density is relatively low. This is due to the low feature density in those regions. Features that belong to one codeword are connected by lines.

The potential of the proposed approach is mainly assessed by the availability of the system and the percentage of correct associations. The association availability obviously depends very strongly on the codebook used and especially on the number of codewords contained in the codebook. This correlation can be observed in Fig. 6 . The use of codebooks that contain a few hundred codewords results in a low availability of less than 5 %. For larger codebooks with more than 500.000 codewords, an association availability of about 48 % is reached. This is due to the fact that map features often are occluded or not yet in sensor range. Only if all features of one codeword are detected, the association is possible and the system is available. Therefore, the system availability increases with the number of codewords that are contained in the codebook used. The percentage of correct associations is visualized in Fig. 7 . Here, the uniqueness threshold , which was chosen to extract the codewords, plays an important role.

For a relatively small choice of = 0.25 m, codewords were correctly associated in up to 97 % of the time, depending on the tile size R. By increasing the uniqueness threshold up to 1 m, 100 % correct associations are found independent of the tile size R ∈ {200m, 300m}. For R = ∞ and > 0.75 m no codewords are available, therefore the system is not available.

Overall, there exists a trade-off between system availability and reliability. In order to reach a high availability, it is desirable to extract many codewords. This can be achieved using small tiles and small uniqueness thresholds. On the other hand, for reliable associations, a high uniqueness threshold should be chosen which results in fewer codewords, but 100% correct associations. In practice, it is conceivable to use multiple codebooks with different uniqueness thresholds to boost availability, where no high integrity solution is available.

In this work, a new approach for reliable data association for feature-based vehicle localization was proposed. The method suggests to preprocess a given map in order to identify and extract unique geometric landmark patterns, called codewords, which are suitable for reliable feature association. These unique feature constellations are hashed and stored in a hash table format, the constellation codebook, for quick and easy search and access during localization.

The exclusive use of unique landmark patterns for data association enables, under certain assumptions on sensor faults, a guarantee for correct feature association and, therefore, provides reliable vehicle localization.

Experimental results were discussed for a feature map of about 3.8 km of roads containing about 600 cylindrical localization landmarks. A variety of codebooks with different parameter choices was constructed for this map. The evaluation of a localization drive of about 10 min in the before mentioned map using these previously generated codebooks demonstrates a trade-off between system availability and reliability.

Future work will focus on the use of multiple constellation codebooks that satisfy different uniqueness requirements for a continuous and accurate localization solution.

Failure detection for laser-based SLAM in urban and peri-urban environments

Feature group matching for appearance-based localization

A simple algorithm for approximate partial point set pattern matching under rigid motion

Global localization of vehicles using local pole patterns

Reliable data association for feature-based vehicle localization using geometric hashing methods

On ambiguities in feature-based vehicle localization and their a priori detection in maps

Accurate and efficient self-localization on roads using basic geometric primitives

Geometric hashing: A general and efficient model-based recognition scheme

Deriving and matching image fingerprint sequences for mobile robot localization

Combination of bag-of-words descriptors for robust partial shape retrieval

Precise localization in high-definition road maps for urban regions

Massively Parallel Bayesian Object Recognition

Efficient variants of the icp algorithm

Localization using automotive laser scanners and local pattern matching

Laneloc: Lane marking based localization using highly accurate maps

Landmark based radar SLAM using graph optimization

Mapping and localization using surround view

Making bertha cooperate-team annieways entry to the 2016 grand cooperative driving challenge

Geometric hashing: An overview

Discovery of collocation patterns: from visual words to visual phrases

Sequential FDIA for autonomous integrity monitoring of navigation maps on board vehicles