# Scan Matching by Cross-Correlation and Differential Evolution
## 3 Background
### Scan Matching  
Scan matching is a high-level self-localization strategy based on the assumption that two spatio-temporally collocated laser range scans of an environment are alike and can be (to a large extent) aligned [48]. Scan matching methods seek transformations that align two laser range scans taken by a robot in the same environment but at different locations and from a different angle. The first laser range scan, taken at the first location, is usually called the reference scan and the second laser range scan, taken at the second location, is called the current scan. The transformation that aligns the scans is defined by parameters that describe the relative position and rotation of the scan (see Figure 2). Figure 2a shows two laser range scans before the transformation (alignment) and Figure 2b shows the same scans after a successful alignment. Scan matching is most often based on 2 or 3-dimensional point clouds captured by LiDAR laser rangefinders. The LiDAR periodically measures the distance to the nearest object in the direction of a laser beam it emits [48]. In a 2-dimensional LiDAR, the measuring laser beam is rotated on the horizontal plane and creates a laser range scan that corresponds to the surrounding of the scanner [49]. 3-dimensional LiDARs also tilt the measuring sensor in the vertical direction and obtain 3-dimensional point clouds [50]. A typical 2-dimensional LiDAR laser range finder, also used in this study, is Sick LMS 100 by SICK AG. This type of range scanner produces counterclockwise oriented vectors of distances to the nearest obstacle. The output of the scanner is a range vector,  
\[\vec{a}=\langle|a_{1}|,\,|a_{2}|,\,\ldots,\,|a_{s_{\max}}|\rangle, \tag{1}\] \begin{table}
\begin{tabular}{l l c c c c} \hline \hline  & **ARM Cortex-M Version** & **M0+** & **M3** & **M4** & **M7** \\ \hline \multirow{2}{*}{Architecture} & CPU architecture & Von Neumann & Harvard & Harvard & Harvard \\  & Pipeline stages & 2 & 3 & 3 & 6 \\ \hline \multirow{3}{*}{Integer operations} & MULT 32 bit & Fast/Slow & Fast & Fast & Fast \\  & DIV 32 bit & No & Yes & Yes & Yes \\ \cline{1-1}  & DSP & No & No & Yes & Yes \\ \hline \multirow{2}{*}{Floating-point operations} & FPU single precision & No & No & Optional & Optional \\  & FPU double precision & No & No & No & Optional \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Overview of various ARM Cortex-M features useful for computational localization. composed of a sequence of distances to the nearest objects, \(|a_{1}|\), \(|a_{2}|\),..., \(|a_{s_{\max}}|\) and \(s_{\max}\) is the number of measurement steps within the aperture range of the scanner. Each measured distance, \(|a_{\phi_{i}}|\), corresponds to a particular angle, \(\phi_{i}\) and each range vector, \(\vec{a}\), corresponds to a vector of angles,  
\[\vec{\phi}=\langle\phi_{1},\,\phi_{2},\,\ldots,\,\phi_{s_{\max}}\rangle, \tag{2}\]  
where the index of the angle corresponds to the orientation of the laser beam. The range vector, \(\vec{a}\), together with the angle vector, \(\vec{\phi}\), describe the surrounding of the scanner in the polar coordinate system. The laser range scan, \((\vec{a},\vec{\phi})\), can be transformed to the Cartesian coordinates by  
\[\mathbf{A}=\left( \begin{array}{c}\langle|a_{1}|\cdot\cos(\phi_{1}),\,|a_{2} |\cdot\cos(\phi_{2}),\,\ldots,\,|a_{s_{\max}}|\cdot\cos(\phi_{s_{\max}})\rangle \\ \langle|a_{1}|\cdot\sin(\phi_{1}),\,|a_{2}|\cdot\sin(\phi_{2}),\,\ldots,\,|a_ {s_{\max}}|\cdot\sin(\phi_{s_{\max}})\rangle\end{array} \right), \tag{3}\]  
where \(\mathbf{A}\in\mathbb{R}^{2\times s_{\max}}\) is a real matrix with the first row representing the \(x\) coordinates and the second row to the \(y\) coordinates of the points in the scan expressed in Cartesian coordinates. Each column of \(\mathbf{A}\), \(\vec{a}_{s}\in\mathbf{A}\), corresponds to a single point of the scan in Cartesian coordinates:  
\[\vec{a}_{s}=\left( \begin{array}{c}a_{x}\\ a_{y}\end{array} \right)=\left( \begin{array}{c}|a_{s}|\cdot\cos(\phi_{s})\\ |a_{s}|\cdot\sin(\phi_{s})\end{array}