We propose a method to estimate localizability as a covariance matrix using local map correlation by SAD. Figure

12 shows the localizability estimation algorithm of the proposed method. First, we trim the template image and the local map from the occupancy grid maps Next, the template image is slided over the local map and the distribution of correlation is calculated by SAD. There are several ways to express localization error in terms of probability distributions, typical methods is to use the Gaussian distribution. Therefore, in this paper we use local map correlation to estimate localizability as a covariance matrix of the Gaussian distribution. As in the correlation distribution in Fig.

12, if the correlation values in the grid have values corresponding to the weights, the expression of the covariance matrix of the Gaussian distribution is as in Eq. (

8).

$$\begin{aligned} \Sigma _{S_\text {SAD}}=k \left[ \begin{array}{ccc} \frac{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}(x_{i}-\mu _{x})^{2}}{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}} &{} \frac{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k} (x_{i}-\mu _{x})(y_{j}-\mu _{y})}{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}} &{} \frac{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k} (x_{i}-\mu _{x})(\theta _{k}-\mu _{\theta })}{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}} \\ \frac{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}(y_{j}-\mu _{y})(x_{i}-\mu _{x})}{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}} &{} \frac{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}(y_{j}-\mu _{y})^{2}}{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}} &{} \frac{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k} (y_{j}-\mu _{y})(\theta _{k}-\mu _{\theta })}{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}} \\ \frac{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k} (\theta _{k}-\mu _{\theta })(x_{i}-\mu _{x})}{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}} &{} \frac{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k} (\theta _{k}-\mu _{\theta })(y_{j}-\mu _{y})}{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}} &{} \frac{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}(\theta _{k}-\mu _{\theta })^{2}}{\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}} \\ \end{array}\right] \end{aligned}$$

(8)

Here,

\(w_{i, j, k}\) in Eq. (

8) is weights. We have conducted basic experiment on several patterns of how the correlation values obtained by SAD are converted into weights. The higher the similarity between the template image and the local map, the lower the correlation value for SAD, so the weights were determined as in Eq. (

9).

$$\begin{aligned} w_{i, j, k} := \frac{1}{S_\text {SAD}\left( x_{i}, y_{j}, \theta _{k}\right) ^2} \end{aligned}$$

(9)

In Eq. (

8),

\(x_{i}\),

\(y_{j}\) and

\(\theta _{k}\) are the positions of the weights in the distribution of correlation in Fig.

12, and

\(\mu _{x}\),

\(\mu _{y}\) and

\(\mu _{\theta }\) are the average positions of the weights. The denominator

\(\sum _{i=0}^{x \prime } \sum _{j=0}^{y \prime } \sum _{k=0}^{\theta \prime } w_{i, j, k}\) means normalisation. The

k in Eq. (

8) is a parameter that determines covariance magnitude, called the noise level [

25]. We determined the

k so that the magnitude of the covariance was appropriate as a localization error. The

k is a scalar value. It is also possible to express localizability in terms of scalar values by using the determinant of the covariance matrix as in Eq. (

10).

$$\begin{aligned} e := \sqrt{ \text {det}(\Sigma _{S_\text {SAD}}) } = \sqrt{ \lambda _1 \lambda _2 \lambda _3} \end{aligned}$$

(10)

The localizability uncertainty value

e represents the estimated magnitude of the localization error. The

\(\lambda _1\) and the

\(\lambda _2\) and the

\(\lambda _3\) in Eq. (

10) show the first and second and third eigenvalues of Eq. (

8). We can visualize the localizability in terms of scalar values by calculating the localizability uncertainty value

e. The covariance matrix is calculated for each cell on occupancy grid map to estimate the localizability of the whole map area. In this way, we can estimate the magnitude of the localization error and the characteristics of the error of the occupancy grid maps.