# Scan Matching by Cross-Correlation and Differential Evolution
###### Abstract  
Scan matching is an important task, solved in the context of many high-level problems including pose estimation, indoor localization, simultaneous localization and mapping and others. Methods that are accurate and adaptive and at the same time computationally efficient are required to enable location-based services in autonomous mobile devices. Such devices usually have a wide range of high-resolution sensors but only a limited processing power and constrained energy supply. This work introduces a novel high-level scan matching strategy that uses a combination of two advanced algorithms recently used in this field: cross-correlation and differential evolution. The cross-correlation between two laser range scans is used as an efficient measure of scan alignment and the differential evolution algorithm is used to search for the parameters of a transformation that aligns the scans. The proposed method was experimentally validated and showed good ability to match laser range scans taken shortly after each other and an excellent ability to match laser range scans taken with longer time intervals between them.  
Keywords:scan matching; indoor localization; differential evolution; cross-correlation; robotics +
Footnote †: journal:  
finders, sonar systems [7; 12], radio-frequency identification (RFID), wireless network technologies such as Wi-Fi, Bluetooth [10; 11] and Zigbee [2], ultra-wideband (UWB), magnetic sensors and acoustic signal analysis [2; 10]. Indoor self-localization by light detection and ranging (LiDAR) relies on analysis of a sequence of laser range scans. The scans capture the surroundings of the robot as a series of points representing the intersections of the laser beam with nearby objects [7]. They generate sequences of 2- or 3-dimensional point clouds that are mutually compared (matched) to approximate the trajectory of the robot in the environment. In general, scan matching algorithms can be split into two major groups. Point-based approaches process the entire point clouds, while feature-based techniques focus on features extracted from the point clouds by various feature extraction algorithms. The features are seen as landmarks and the changes in their (relative) locations are used to estimate the moves of the robot [7].  
Advanced methods that utilize artificial intelligence, machine learning and soft computing can be used for different types of self-localization applications. For example, artificial neural networks and support vector machines have been used to build indoor localization models based on the received signal strength indicator (RSSI) [2]. In this work, a novel scan matching algorithm based on differential evolution and modified cross-correlation is introduced. Cross-correlation is used to evaluate the alignment of laser range scans, while differential evolution serves as an optimization method for the approximation of the scan matching parameters.  
The contributions of this work are twofold: (1) It shows that the differential evolution can be used as an optimization mechanism in a point-based scan matching strategy; and (2) It demonstrates that cross-correlation is a computationally efficient and at the same time robust point cloud alignment measure. The extensive experimental evaluation of these novel concepts also demonstrates that the scan matching procedure based on differential evolution and cross-correlation can be used for accurate indoor localization of autonomous mobile devices.  
The remainder of this article is structured in the following way. The problem of localization is summarized and related work is reviewed in Section 2. The algorithms used in this work (scan matching, cross-correlation and differential evolution) are described in Section 3. The proposed approach is detailed in Section 4 and experimentally evaluated in Section 5. The results of conducted experiments are discussed in Section 6 and the article is concluded in Section 7 which also outlines future research directions.