This Is AuburnElectronic Theses and Dissertations

The Utilization of Geometric Hashing Techniques for Feature Association during Ground Vehicle Localization




Sprunk, Michael

Type of Degree

Master's Thesis


Mechanical Engineering


This thesis presents a new approach to laser-based robot localization using the concept of geometric hashing. The technique operates on an a priori feature map representing the navigation environment by recording all possible feature combinations as transformation-invariant sets. Each combination can be defined by an implementation-specific geometric basis, and then hashed in order to promote rapid parallelizable search conditions and easily encode large quantities of information. The primary focus of this work is centered on the individual component of map data association within the much larger localization pipeline. At this step, the navigation system is generally required to provide a correct association between features extracted in real-time from the environment and their corresponding a priori mapped counterparts. In addition to the main concerns of accuracy and reliability, this thesis addresses several other relevant challenges present in feature-based localization such as time complexity, sensitivity to noise, and the detection of map symmetries. The concept of using geometric hashing for laser-based localization consists of three phases: the training phase, screening phase, and recognition phase. Within this work, each phase is thoroughly defined and analyzed. Particular attention is given toward the utilization of cylindrical-like features found predominantly in urban environments for use during localization. A simulation was developed to test and verify geometric hashing localization in both unique and ambiguous environments. The results validated that geometric hashing localization can provide sub-meter level accuracy even in the presence of ambiguous geometries so long as sufficient information is present. To test the approach on time-critical scenarios, an implementation of the data association algorithm written C++ was integrated into an existing localization framework deployed on a vehicle. Results showed that the positioning solution is capable of providing sub-meter accuracy at 20 Hz update rates driving through urban environments.