# Scan Matching by Cross-Correlation and Differential Evolution
## 3 Background
### Cross-Correlation  
Cross-correlation is a concept known in the area of signal processing. It is a measure that evaluates the similarity between two signals, \(x\) and \(y\), shifted in time by a specific value, \(\tau\)[54]. The cross-correlation of two arbitrary signals, expressed by \(N\) discrete samples,  
\[R_{xy}(\tau)=\sum_{i=0}^{N-1}x_{i}(t)\cdot y_{i}(t-\tau), \tag{7}\]  
reaches maximum for a value of \(\tau\) for which are the signals most similar. In this study, the cross-corelation principle is used to match two laser range scans for indoor robot localization. Cross-corelation of a laser range scan, \(\mathbf{A}\), with a translated and rotated version of another scan, \(\mathbf{B}\), is maximized when the parameters of the transformation that correspond to the cumulative transition and rotation of the robot (scanner) between the scans were taken are found [42]. The evaluation of the cross-correlation between two 2-dimensional laser range scans under affine transformation \(\mathcal{T}\) with parameter vector \(\vec{t}=(t_{x},t_{y},\Phi)\) can be expressed by  
\[R_{\mathbf{A}\mathbf{B}}(t_{x},t_{y},\Phi)=\mathbf{A}\odot(\mathcal{T}( \mathbf{B},t_{x},t_{y},\Phi)), \tag{8}\]  
where \(\odot\) is an operator that compares two 2-dimensional laser range scans and quantifies the degree of their alignment (i.e., an implementation of Equation (7) suitable for the comparison of 2-dimensional signals). The definition of \(\odot\) is essential for the properties of the process. A simple measure such as the root mean square error (RMSE) can provide a reasonable estimate of the degree of scan alignment and it can be used as a part of an optimization-based scan matching procedure [44]. However, its computational complexity is too high for practical use. In this work, an efficient numerical algorithm,implementing the cross-correlation principle for 2-dimensional signals, is used instead of RMSE to evaluate the level of alignment of two laser range scans in the scan matching procedure.  
In the proposed approach, the laser range scan is converted to Cartesian coordinates in the same manner as in [44]. Next, a _grid map_ simplifying the scene is created from the point cloud data. The grid map can be build using an arbitrary computationally feasible procedure. Figure 3 illustrates two methods for grid map creation. The approach, shown in Figure 3a, is based on area comparison. It assumes that the best scan match is achieved when the total volume of the overlapping regions is maximized. For each cell in the grid, the algorithm decides whether it is inside of the first or the second scan and then computes the number of overlapping cells. The second method, shown in Figure 3b, is based on boundary line analysis. It assumes that the best scan match is obtained when the intersection of the boundary lines is maximized. This approach does not require any operations over empty grid cells and laser scans can be represented by lists of non-empty grid cells that contain the points of the scans.  
During the grid map creation, more than one point can be located in a single grid cell. This fact can be used by the scan matching procedure. For example, each cell can have a weight corresponding to the number of points it contains [42]. The cell weight can then affect the remainder of the scan matching procedure. However, initial experiments carried out in the scope of this study showed that the use of cell weights leads to the premature convergence of the optimization process and, in many cases, it prevents the algorithm from reaching the global optima. The scan matching algorithm is more robust when the cell weights are not taken into account and the grid cells are simply marked as occupied or empty. The number of occupied cells is usually not greater than 10% of all grid cells and the creation of grid maps as well as their comparison is fast.