\section{Introduction} \label{sec:introduction}

\input{sections/1_introduction}

\section{Related Work} \label{sec:related_work}

\input{sections/2_related_work}

\vspace{4mm}
\section{Taxonomy for Deterministic Uncertainty Quantification} \label{sec:taxonomy}

\input{sections/3_taxonomy}

\section{Evaluation of Deterministic Epistemic Uncertainty}\label{sec:experiments}

\input{sections/4_experiments}

\section{Conclusion} \label{sec:conclusion}

\input{sections/5_conclusion}
\vspace{-2mm}
\section{Broader Impact} \label{sec:broader_impact}

\input{sections/6_broader_impact}

\iffalse
\clearpage

\bibliographystyle{unsrt}

\subsection{Regularization of Hidden Representations} \label{ssec:taxonomy_strategy}
We group \acp{dum} according to how feature collapse is tackled, enabling \ac{ood} detection based on latent representations.
In particular, we identify two main paradigms - distance awareness and informative representations - which we discuss in \autoref{sssec:distance_awareness} and \autoref{sssec:informative_representations}.

\subsubsection{Distance Awareness} \label{sssec:distance_awareness}

The fundamental idea of distance-aware hidden representations is to avoid feature collapse by enforcing distances between latent representations to mirror distances in the input space.
This can be achieved by constraining the Lipschitz constant, as it enforces a lower and an upper bound to expansion and contraction performed by an underlying neural network.
A lower bound is associated with \textit{sensitivity}, since it enforces that different inputs are mapped to distinct latent representations and, thus, provides a solution to feature collapse.
Moreover, an upper bound enforces \textit{smoothness} of the hidden representations, \textit{i.e.}{} small changes in the input do not result in large changes in the latent space.
More formally, given any pair of inputs $x_1$ and $x_2$ the following lower and upper bounds must hold for the resulting activation of a feature extractor $f_\theta$ with parameters $\theta$: $c_1||x_1-x_2||_I \leq ||f_\theta(x_1)-f_\theta(x_2)||_F \leq c_2||x_1-x_2||_I$.
$c_1$ and $c_2$ denote respectively the lower and upper bound for the Lipschitz constant, and $||\cdot||_I$ and $||\cdot||_F$ are the chosen metrics in the input and feature space respectively.
While there exist other approaches, \textit{e.g.}{}~\cite{obukhov2021spectral}, recent proposals have primarily adopted two methods to impose the bi-Lipschitz constraint.

\textbf{Gradient Penalty.}
First introduced to regularize the Lipschitz constant in GAN training~\cite{gulrajani2017improved}, a two-sided gradient penalty is used as an additional loss term to enforce detectability in the feature space of changes in the input by DUQ~\cite{van2020uncertainty}.
The gradient penalty is formulated as an additional loss term that regularises the Frobenius norm $||J||_F$ of the Jacobian $J$ of a \ac{nn} to enforce a bi-Lipschitz
constraint. Therefore, the training loss of a \ac{nn} is typically enhanced with the absolute difference between $||J||_F$ and some chosen positive constant (see supplement or \cite{van2020uncertainty} for more details).

\textbf{Spectral Normalization.} The two-sided gradient penalty described above requires backpropagating through the Jacobian of a \ac{nn} and is, thus, computationally demanding. A more efficient technique is \ac{sn}~\cite{miyato2018spectral}. For each layer, \ac{sn} normalizes the weights $W$ of each layer using their spectral norm $sn(W)$ to constrain the bi-Lipschitz constant. Thus, weight matrices are normalized according to: $W_{sn}=\frac{W}{c\cdot sn(W)}$.
Note, that this soft constraint becomes hard for $c=1$. We refer to the supplement or \cite{liu2020simple} for further details.
Various \acp{dum} - SNGP~\cite{liu2020simple}, DUE~\cite{van2021improving} and DDU~\cite{mukhoti2021deterministic} - rely on \ac{sn} of the weight matrices to enforce distance-awareness of hidden representations.

Note that the Lipschitz constraint is defined with respect to a predefined distance measure, which can be difficult to choose for many high-dimensional data distributions of practical interest.
A popular choice, also adopted by~\cite{van2020uncertainty,liu2020simple,van2021improving}, is the $L_2$ distance.
Moreover, principled approaches to provide exact singular values in convolutional layers~\cite{sedghi2018singular} result in prohibitive computational complexity; the spectral normalization approximations typically adopted by the methods previously described have been found to be sub-optimal~\textit{et al.}~\cite{singla2019bounding}, and its interaction with losses, architecture and optimization is yet to be fully understood~\cite{rosca2020case}.
Consequently, Lipschitz regularization with respect to a potentially meaningless distance measure may result in overly sensitive models.
\autoref{ssec:classification_results} analyses the impact of regularization strength on \ac{ood} detection.

\subsubsection{Informative Representations} \label{sssec:informative_representations}
While methods enforcing distance-awareness achieve remarkable performance in OOD detection, they do not explicitly preserve sample-specific information.
Consequently, depending on the underlying distance metric they may discard useful information about the input or act overly sensitive.
An alternative line of work proposes to avoid feature collapse by learning informative representations~\cite{alemi2018uncertainty,wu2020simple,postels2020hidden,nalisnick2019hybrid,ardizzone2018analyzing,ardizzone2020training}, thus forcing discriminative models to preserve information beyond what required by its target task in its hidden representations independent of the choice of an underlying distance metric.
Notably, while representations that are aware of distances in the input space are arguably also informative, both categories remain fundamentally different in their approach to feature collapse.
While distance-awareness is based on the choice of a specific distance metric tying together input and latent space, informative representations incentivize the network to store more information about the input using an auxiliary task \cite{postels2020hidden, wu2020simple} or forbid information loss by construction \cite{ardizzone2018analyzing,nalisnick2019hybrid,ardizzone2020training}.
We identify three distinct families of approaches to enforce informative representations.

\textbf{Contrastive learning}~\cite{oord2018representation,wu2020simple} has emerged as an approach for learning representations that are both informative and discriminative.
This is utilized by Wu \textit{et al.}~\cite{wu2020simple}, who build on top of SimCLR~\cite{chen2020simple} to regularize hidden representations for a discriminative task by using an auxiliary contrastive loss to force representations to further discriminate between individual instances.

\textbf{Reconstruction regularization}~\cite{postels2020hidden} instead forces the intermediate activations to embody a complete representation of the input space.
This is achieved by adding a decoder branch fed with the activations of a given layer to reconstruct the input.
Since this method aims at producing Maximally Informative Representations, we term it MIR.

\textbf{\acp{inn}}~\cite{jacobsen2018revnet,ardizzone2018analyzing,nalisnick2019hybrid,ardizzone2020training}, built via a cascade of homeomorphic layers, cannot discard information except at the final classification stage.
Consequently, the mutual information between input and hidden representation is retained by construction.
Interestingly, Behrmann \textit{et al.}~\cite{behrmann2018invertible} showed that a ResNet is invertible if its Lipschitz constant is lower than $1$, meaning that invertible ResNets both possess highly-informative representations and satisfy distance-awareness. However, note that this is not a necessary condition for invertibility, and thus information preservation, in general.
\subsection{Uncertainty Estimation} \label{ssec:taxonomy_density_models}
We now describe the different approaches to quantifying uncertainty based on such regularized representations.
We distinguish two directions - generative and discriminative approaches.
While generative approaches use the likelihood produced by an explicit generative model of the distribution of hidden representations as a proxy for uncertainty, discriminative methods directly use the predictions based on regularized representations to quantify uncertainty.

\textbf{Generative approaches} estimate the distribution of hidden representations post-training and use the likelihood as uncertainty metric to detect \ac{ood} samples.
Wu \textit{et al.}~\cite{wu2020simple} propose a Deep Contrastive Uncertainty (DCU) method to train an additional deep network from the representation space to a distribution space, where the variance of the distribution is used as a confidence measure.
MIR~\cite{postels2020hidden} and DDU~\cite{mukhoti2021deterministic} fit a class-conditional GMM to their regularized hidden representations and use the log-likelihood as an epistemic uncertainty proxy.
A special instance of the generative approaches are \acp{inn} as they directly estimate the training data distribution. This allows using the likelihood of the input data as a proxy of uncertainty. While this idea is appealing, it can lead to training difficulties, imposes strong constraints on the underlying feature extractor and in some instances even remains susceptible to \ac{ood} data~\cite{nalisnick2018deep}.

\textbf{Discriminative approaches} use the predictions based on regularized representations to directly assess confidence.
Mandelbaum \textit{et al.}~\cite{mandelbaum2017distance} propose to use a Distance-based Confidence Score (DCS) to estimate local density at a point as the Euclidean distance in the embedded space between the point and its k nearest neighbors in the training set.
Similarly, DUQ~\cite{van2020uncertainty} builds on Radial Basis Function (RBF) networks~\cite{lecun1998gradient} and propose a novel centroid updating scheme.
Uncertainty is estimated as the distance between the model output and the closest centroid.
DUMs adopting \ac{sn}~\cite{liu2020simple,van2021improving}, and thus preserving $L_2$ distances, typically fit \acp{gp} with RBF kernels on top of the learned feature space, extending distance awareness to the output layer.
In particular, SNGP~\cite{liu2020simple} relies on a Laplace approximation of the \ac{gp} based on the random Fourier feature (RFF) expansion of the \ac{gp} posterior~\cite{rasmussen2003gaussian}.
DUE~\cite{van2021improving} leverages instead the inducing point approximation~\cite{titsias2009variational,hensman2015scalable}, allowing to pick an arbitrarily large number of inducing points without overfitting~\cite{burt2019rates}.
The uncertainty is then derived respectively as the Dempster-Shafer metric~\cite{liu2020simple} or the softmax entropy~\cite{van2021improving}.

\subsubsection{Results} \label{ssec:classification_results}

\textbf{Calibration under continuous distributional shift.} \autoref{tab:classification_cal} shows accuracy on the test set and calibration performance in terms of \ac{raulc}. With the exception of DUQ, which we find to be prone to training instabilities, all \acp{dum} achieve similar predictive performance as \ac{mc} dropout, deep ensembles and standard softmax models. In terms of uncertainty calibration, we observe that in particular DUE, SNGP and MIR compete with established uncertainty estimation methods (\textit{e.g.}{} \ac{mc} dropout) across most datasets and both types of distributional shifts. Consequently, these approaches do not only fare well at detecting \ac{ood} data but also deliver well calibrated uncertainties under synthetic distributional shifts.
However, this is not sufficient to justify their use for real-world safety-critical applications.
Refer to \autoref{ssec:segmentation_results} for an analysis of calibration under realistic distributional shift.

\begin{figure*}[t]
\begin{tabular}{ccc}

\multicolumn{3}{c}{\input{figures/image_classification/acc_aulc_auroc_vs_perturbation/custom_legend}}
\\

\input{figures/image_classification/acc_aulc_auroc_vs_perturbation/mnist_ACC_vs_perturbation} &
\input{figures/image_classification/acc_aulc_auroc_vs_perturbation/mnist_AUROC_vs_perturbation} &
\input{figures/image_classification/acc_aulc_auroc_vs_perturbation/mnist_AULC_vs_perturbation}
\\

\input{figures/image_classification/acc_aulc_auroc_vs_perturbation/svhn_ACC_vs_perturbation} &
\input{figures/image_classification/acc_aulc_auroc_vs_perturbation/svhn_AUROC_vs_perturbation} &
\input{figures/image_classification/acc_aulc_auroc_vs_perturbation/svhn_AULC_vs_perturbation}

\end{tabular}
\vspace{-1em}
\caption{We compare \acp{dum} and the baselines (\ac{mc} dropout (MCD), ensembles (Ens)) under continuous distributional shifts. Therefore, we plot accuracy (LEFT), \ac{auroc} (CENTER) and \ac{raulc} (RIGHT) against the perturbation magnitude for a MLP trained on MNIST (TOP) and a ResNet-18 on SVHN (BOTTOM). We perturbe MNIST using rotations and SVHN using additive Gaussian noise. The \ac{auroc} is computed against unperturbed test data. Most \acp{dum} demonstrate similar behaviour as the baselines, except DDU. While MIR shows strong performance on MNIST, its performance drops on CIFAR10.}\label{fig:acc_aulc_auroc_vs_perturbation}
\end{figure*}

\begin{table}[t]
\small
    \centering
    \setlength{\tabcolsep}{2.8pt}
    \input{tables/classification_cal}
    \caption{We evaluate the in-domain test accuracy (Acc, \%) and calibration performance (\ac{raulc}, \%) on MNIST, FashionMNIST, CIFAR10 and SVHN datasets. The backbones for all methods are MLP for MNIST/FashionMNIST and ResNet-18 for CIFAR10/SVHN. We observe that - in particular - DUE, SNGP and MIR are well calibrated across several scenarios.}
    \label{tab:classification_cal}
\end{table}

\begin{table}[t]
\small
    \centering
    \setlength{\tabcolsep}{3pt}
    \input{tables/classification_ood}
    \caption{Experiments for OOD detection (AUROC and AUPR, \%). The baseline method and all \acp{dum} use a MLP trained on MNIST/FashionMNIST and predict on another dataset. MIR demonstrates strong performance. (F-MNIST $=$ FashionMNIST).}
    \label{tab:classification_ood1}
\end{table}

\textbf{\ac{ood} Detection.} \autoref{tab:classification_ood1} shows quantitative results on detecting \ac{ood} data for \acp{dum}, \ac{mc} dropout, softmax entropy and deep ensembles trained on MNIST/FashionMNIST (similarly in the supplement for ResNet-18 trained on CIFAR10/SVHN). Among \acp{dum}, SNGP and MIR demonstrate the best performance across a variety of scenarios. While \acp{dum} confirm to be naturally suited for \ac{ood} detection, other established approaches (\textit{e.g.}{} \ac{mc} dropout) remain competitive. We note a particular drop in performance for \acp{dum} estimating uncertainty based on the distribution of hidden representations (\textit{i.e.} MIR and DDU) in the case of CIFAR10 vs. SVHN (see supplement). We hypothesize that this results from difficulties of generative models at distinguishing CIFAR10 and SVHN \cite{nalisnick2018deep}.

\textbf{Sensitivity to Regularization Strength.} The hyperparameter associated with each \ac{dum} constitutes an important element in each method. It is important to know whether their performance in terms of \ac{ood} detection and calibration is sensitive to its choice. Intuitively, we expect the regularization technique to be positively correlated with \ac{ood} detection performance, since this is what most \acp{dum} were designed for. For each regularization paradigm - distance-awareness (SNGP) and informative representations (MIR) -, \autoref{fig:sensitivity_to_regularization_strength} visualizes the calibration (\ac{raulc}) and \ac{ood} detection (\ac{auroc}) performance depending on the strength of the regularization (similarly for other datasets and methods in the supplement). Most interestingly, we find that \acp{dum} regularizing the Lipschitz constant of the underlying feature extractor do not show evidence for a correlation between the regularization strength and the performance on \ac{ood} detection. One possible reason for this result is that Lipschitz-regularization is defined in the context of a particular predefined norm (\textit{e.g.}{} $L_2$) (see \autoref{sec:taxonomy}). However, this norm does not necessarily represent meaningful distances on a particular dataset (\textit{e.g.}{} images). On the contrary, in the case of enforcing informative representations using reconstruction regularization (MIR), we find evidence for a correlation between regularization strength and performance in terms of both \ac{ood} detection and calibration.

\begin{figure}[t]
\begin{tabular}{ccc}
\vspace{-4mm}
\input{figures/image_classification/regularization_strength_error_bars/mir_mnist_AULC_vs_ACC} &
\input{figures/image_classification/regularization_strength_error_bars/mir_mnist_fashion_mnist_AUROC_vs_ACC} &
\input{figures/image_classification/regularization_strength_error_bars/mir_mnist_omniglot_AUROC_vs_ACC}
\\ \vspace{-1mm}
\input{figures/image_classification/regularization_strength_error_bars/sngp_mnist_AULC_vs_ACC} &
\input{figures/image_classification/regularization_strength_error_bars/sngp_mnist_fashion_mnist_AUROC_vs_ACC} & \hspace{-3mm}
\input{figures/image_classification/regularization_strength_error_bars/sngp_mnist_omniglot_AUROC_vs_ACC}
\end{tabular}
\vspace{-0.5em}
\caption{Trained on MNIST. Vertical axis: Test accuracy. Horizontal axis: \ac{raulc} (left), \ac{auroc} against FashionMNIST (center) and Omniglot (right) for MIR (top) and SNGP (bottom) using different regularization strength. For SNGP a larger hyperparameter corresponds to less regularization. For MIR we observe a correlation between regularization strength and performance.}\label{fig:sensitivity_to_regularization_strength}
\vspace{-1em}
\end{figure}
\subsubsection{Dataset} \label{ssec:segmentation_dataset}
To benchmark our model in a realistically and continuously changing environment, we collect a synthetic dataset for semantic segmentation.
We use the CARLA Simulator~\cite{Dosovitskiy17} for rendering the images and segmentation masks. The classes definition is aligned with the CityScape dataset~\cite{Cordts2016Cityscapes}.

\textbf{Training data.} Data is collected from four towns in CARLA. We produce 32 sequences from each town. Vehicles and pedestrians are randomly generated for each sequence. Every sequence has 500 frames with a sampling rate of $10$ FPS. We uniformly sample a validation set.

\textbf{Continuous Distributional Shifts.} We use the time-of-the-day (weather conditions in the supplement) as the parameter for continuously changing the distribution. Visual examples and details on data collection are in the appendix. The time-of-the-day is parametrized by the Sun's altitude angle, where $90^\circ$ means the mid-day (training data) and the $0^\circ$ means the dust/dawn. We produce samples with altitude angles from $90^\circ$ to $15^\circ$ by steps of $5^\circ$, and $15^\circ$ to $-5^\circ$, where the environment changes sharply, in $1^\circ$ steps.
\subsubsection{Method Details} \label{ssec:segmentation_method_details}
\textbf{Backbone.}
We adopt \ac{drn}~\cite{Yu2016, Yu2017} as semantic segmentation backbone.
\ac{drn} introduces dilated convolutions to ResNet, effectively increasing the receptive field without increasing the number of layers or parameters. This improves the spatial accuracy of \ac{drn}, achieving satisfactory results on CityScapes~\cite{Cordts2016Cityscapes}.
We adopt the variant DRN-A-50.
All experiments were run $3$ times.

\textbf{SNGP.}
\ac{drn} uses $1 \times 1$ convolutions at the last layer to map the latest feature map to the predicted segmentation mask.
This works under the assumption that all pixels in the output mask are i.i.d. random variables.
Following this intuition, we extend SNGP to semantic segmentation by fitting a $GP: \mathbb{R}^Z \rightarrow \mathbb{R}^C$  at pixel level that maps from the deep feature dimension $z$ to the number of classes $c$. By keeping the \ac{gp} kernel parameters shared across all pixels, we simulate a  $1 \times 1$ convolutional \acp{gp}, \textit{i.e.}{} $\sigma: (H_l \times W_l \times Z) \rightarrow (H_l \times W_l \times C)$, where $\sigma$ convolves the \ac{gp}, $H_l$ and $W_l$ are respectively feature map height and width at layer $l$, $Z$ is the number of latent features and $C$ is the number of output classes. For details about the \ac{gp} we refer to \cite{liu2020simple} or the supplement.

\textbf{MIR.} To estimate image-level uncertainty MIR requires fitting the distribution of hidden representations. We fit a \ac{gmm} with $20$ components (\textit{i.e.}{} number of classes) to each spatial location of the hidden representations using features extracted from the training data independently. This assumes that the distribution is translation invariant and factorizes along the spatial dimensions of the latent space which is similar to the procedure used in \cite{blum2019fishyscapes}. We refer to the supplement for more details and computation of pixel-level uncertainties in this framework.

\subsubsection{Results} \label{ssec:segmentation_results}
\textbf{Continuous Distribution Shift.}
We compare \acp{dum} with \ac{mc} dropout and the softmax baseline.
in terms of their calibration under realistic distributional shifts.
\autoref{table:calibration_segmentation} shows quantitative results. Encouragingly, all methods yield similar performance in terms of \ac{miou} and pixel accuracy. However, we observe that while \acp{dum} yield a considerable improvement over the softmax entropy - both in \ac{ood} detection and calibration - using a similar computational budget, these methods still fall short of established approaches, such as \ac{mc} dropout, in terms of calibration under challenging realistic distributional shifts.
This finding is further supported by the results of \autoref{fig:miou_auroc_lc}, which shows
that \acp{dum} behave poorly in terms of calibration (see Lift curves) under realistic distributional shift.
We believe that these shortcomings must be addressed before practical deployment.

\begin{table}[t]
    \centering
    \scalebox{0.9}{
    \input{tables/segmentation}
    }
    \caption{We compare predictive performance on unperturbed test data - pixel accuracy (Acc.) and \ac{miou} - and calibration (rAULC) on realistic continuous distributional shifts of softmax, \ac{mc} dropout (MCD), SNGP and MIR on semantic segmentation. While SNGP and MIR perform better than the simple softmax baseline, they remain outclassed by \ac{mc} dropout in terms of calibration.}
    \label{table:calibration_segmentation}
    \vspace{-1em}
\end{table}

\begin{figure}

\begin{tabular}{ccc}

\multicolumn{3}{c}{\input{figures/semantic_segmentation/custom_legend}}
\\

\input{figures/semantic_segmentation/segmentation_mIoU_vs_perturbation} &
\input{figures/semantic_segmentation/segmentation_AUROC_vs_perturbation} &
\input{figures/semantic_segmentation/segmentation_LC_summary}

\end{tabular}
\caption{We compare the \ac{miou} (left), \ac{auroc} (center) and \ac{raulc} (right) of softmax (SM), \ac{mc} dropout (MCD), SNGP and MIR under realistic continuous distributional shifts. The \ac{auroc} is computed against unperturbed test data. While the softmax entropy as a measure of uncertainty clearly fails in this scenario, \acp{dum} (SNGP/MIR) yield reasonable uncertainty using a similar computational budget at identical predictive performance (\ac{miou}). However, \ac{mc} dropout, with its larger computational footprint, provides better calibrated uncertainty estimates (Lift).}\label{fig:miou_auroc_lc}
\vspace{-4mm}
\end{figure}

\subsection{Image Classification}\label{ssec:classification}
\input{sections/4_1_image_classification}

\subsection{Semantic Segmentation}\label{ssec:segmentation}
\input{sections/4_2_large_scale_visual_task}

\subsection{Official Implementation} \label{ssec:code}
An official implementation of this work can be found, completely anonymized, at the following link:
\url{https://1drv.ms/u/s!AmvoAvndzeKvarxW2fCTi_4W9-o?e=KjaQNE}

\subsection{Additional Results} \label{ssec:suppl_additional_results}
\subsubsection{Image Classification} \label{sssec:suppl_classification_results}
\textbf{OOD Detection.}
\autoref{table:classification_ood2} show quantitative results on detecting \ac{ood} data for \acp{dum}, \ac{mc} dropout, softmax entropy and deep ensembles trained on CIFAR/SVHN.
Similarly to the results shown in \autoref{ssec:classification_results}, among \acp{dum} SNGP and MIR demonstrate strong performance across a variety of scenarios. Note that in this case DUE also shows good performance. While \acp{dum} confirm to be naturally suited for \ac{ood} detection, other established approaches (\textit{e.g.}{} \ac{mc} dropout) remain competitive.

\begin{table}[htbp]
\small
    \centering
    \setlength{\tabcolsep}{3pt}
    \input{tables/classification_ood_2}
    \caption{Experiments for OOD detection performance (AUROC and AUPR, \%). The baselines and all \acp{dum} use a ResNet-18 trained on CIFAR10/SVHN. In particular, SNGP, MIR and DUE demonstrate strong performance. However, computationally more expensive baselines remain competitive.} \label{table:classification_ood2}
\end{table}

\textbf{Sensitivity to regularization strength.}
\input{figures/image_classification/supplementary_regularization_strength/mnist_regularization_strength}
\input{figures/image_classification/supplementary_regularization_strength/fashion_mnist_regularization_strength}
\input{figures/image_classification/supplementary_regularization_strength/cifar10_regularization_strength}
\input{figures/image_classification/supplementary_regularization_strength/svhn_regularization_strength}
We provide additional ablation studies on the sensitivity to regularization strength for different methods on datasets, \textit{i.e.}{} MNIST (\autoref{fig:suppl_mnist_sensitivity_to_regularization_strength}), FashionMNIST (\autoref{fig:suppl_fashion_mnist_sensitivity_to_regularization_strength}), CIFAR10 (\autoref{fig:suppl_cifar_sensitivity_to_regularization_strength}), and SVHN (\autoref{fig:suppl_svhn_sensitivity_to_regularization_strength}).
These results confirm the findings of the main manuscript, \textit{i.e.}{} that only MIR and Dropout are sensible to regularization strength, while \acp{dum} based on Lipschitz regularization are not influenced by the regularization strength. Note that for MIR we observe that regularization strength and calibration/ood detection are anti-correlated. We hypothesize that this originates from generative models inability to distinguish these datasets \cite{nalisnick2018deep}. Thus, storing more information in the latent representations about the input leads to worse \ac{ood} detection performance.

\subsubsection{Semantic Segmentation}  \label{sssec:suppl_segmentation_results}
\textbf{Weather conditions.} Additionally, we evaluate the calibration performance of DUMs under changing weather conditions. Fig.~\ref{fig:carla_weather} of Sec.~\ref{ssec:suppl_segmentation_dataset} demonstrates examples of this distributional shift. The quantitative evaluation results are summarized in Table~\ref{table:calibration_segmentation_weather}. Similar to the trend in the Table~\ref{table:calibration_segmentation}, all methods yield decent performance on pixel accuracy and mIoU, and the DUMs obtain significant improvements over the Softmax baseline. However, we again observe that \ac{mc} dropout outperforms \acp{dum} on continuous distributional shifts.
\begin{table}[!h]
    \centering
    \scalebox{0.9}{
    \input{tables/segmentation2}
    }
    \caption{Calibration results on semantic segmentation for weather conditions.}
    \label{table:calibration_segmentation_weather}
\end{table}

\textbf{Examples of segmentation and uncertainty masks.}
\input{figures/supplementary_segmentation_uncertainty/minimal_shift_uncertainty}
\input{figures/supplementary_segmentation_uncertainty/maximal_shift_uncertainty}
We show qualitative examples of predicted masks, error masks and uncertainty masks for Softmax, \ac{mc} dropout, SNGP and MIR on semantic segmentation.
\autoref{fig:suppl_segmentation_minimal} illustrates examples under \textit{minimal} distributional shift (\textit{i.e.}{} Azimuth angle of the sun $=85\degree$ and \autoref{fig:suppl_segmentation_maximal} under \textit{maximal} distributional shift (\textit{i.e.}{} Azimuth angle of the sun $=-5\degree$.
We show the input image (Input), the segmentation ground truth (GT), the predicted segmentation mask (Prediction), the error mask (Error) and the uncertainty mask (Uncertainty).
The error mask is computed as a boolean mask with True values when a pixel is predicted wrongly (yellow) and False (blue) when the prediction is instead correct.
The uncertainty mask is preprocessed to facilitate visualization. In particular, we first compute mean $\mu$ and standard deviation $\sigma$ of per-pixel uncertainties over each uncertainty mask. Then, the uncertainty mask is clipped between $[\mu-2\sigma, \mu+2\sigma]$. Finally, the uncertainty mask is normalized between $0$ and $1$ before being visualized.

While the softmax entropy provides decent uncertainty estimates under minimal distributional shift, it tends to be overconfident under severe distributional shift.
In particular, Softmax models are only uncertain close to object borders, but they are confident about large portions of the image that are instead predicted wrongly.
This can be observed in \autoref{fig:suppl_segmentation_maximal}, where all models tend to predict the entire sky wrongly (assigned to `building' class), but the Softmax model is the most confident about its predictions of the sky being correct.
\acp{dum} and \ac{mc} dropout do a better job at recognizing wrong predictions under sever domain shift by outputting higher uncertainty values.

\subsection{Lipschitz Regularization} \label{ssec:suppl_regularization}

\textbf{Gradient Penalty.}
Given a model $g$ and an input $x$, regularising the Frobenius norm $||J||_F$ of its Jacobian $J$ constraints its Lipschitz constant.
Therefore, the following two-sided gradient penalty is used:
$\lambda \left[ ||\nabla_x g(x)||_F-1\right]^2$,
where $\lambda$ is the regularization strength, $||\cdot||_2$ is the $L_2$ norm, the target bi-Lipschitz constant is 1.

\textbf{Spectral Normalization.} A more efficient technique to constrain the Lipschitz constant is \ac{sn}~\cite{miyato2018spectral}. For each layer $g: \mathbf{h}_{in} \rightarrow \mathbf{h}_{out}$, \ac{sn} effectively constrain its Lipschitz norm $||g||_{Lip}=sup_{\mathbf{h}}sn(\nabla g(\mathbf{h}))$, where $sn(A)$ is the spectral norm - the $L_2$ matrix norm - of the matrix A, equivalent to its largest singular value.
When applied, \ac{sn} normalizes the spectral norm of the weights $W$ of each layer to satisfy the soft-Lipschitz constraint $sn(W)=c$ (hard- if the Lipschitz constant $c=1$): $W_{sn}=W/sn(W)$.
A number of \acp{dum} - SNGP~\cite{liu2020simple}, DUE~\cite{van2021improving} and DDU~\cite{mukhoti2021deterministic} - rely on \ac{sn} of the weight matrices to make the feature extractor distance preserving.

\subsection{Training Details}
\label{ssec:suppl_training_details}
We provide training and optimization details for all evaluated methods.
All methods using spectral normalization use $1$ power iteration.
Hyperparameters were chosen to minimize the validation loss.

\subsubsection{Image Classification - MNIST/FashionMNIST}
All methods trained on MNIST/FashionMNIST used a MLP as backbone with $3$ hidden layers of $100$ dimensions each and ReLU activation functions.
We used a batch size of $128$ samples and trained for $200$ epochs.
No data augmentation is performed.

\textbf{Softmax and Deep ensembles.}
We used for the single softmax model the Adam optimizer with learning rate $0.003$, and $L_2$ weight regularization $0.0001$. When using ensembles, $10$ models are trained from different random initializations.

\textbf{\ac{mc} dropout.}
We used for all baselines the Adam optimizer with learning rate $0.003$, dropout rate $0.4$ and $L_2$ weight regularization $0.0001$.

\textbf{DUE}
We trained DUE with the SGD optimizer with learning rate $0.01$, $L_2$ weight regularization $0.0005$, and a multi-step learning rate decay policy with decay rate $0.2$ and decay steps at the epochs $60$, $120$, $160$.
We found the optimal \ac{sn} coefficient to be $7$, with the GP approximation using $10$ (number of classes) inducing points initialized using k-means over $10000$ samples.

\textbf{DUQ}
We trained DUQ with the SGD optimizer with learning rate $0.01$, $L_2$ weight regularization $0.0001$, and a multi-step learning rate decay policy with decay rate $0.3$ and decay steps at the epochs $10$, $20$.
Lengthscale for the RBF kernel is $0.1$ and optimal gradient penalty loss weight is $0$.

\textbf{DDU.}
We trained DDU with the Adam optimizer with learning rate $0.001$, $L_2$ weight regularization $0.0001$, and a multi-step learning rate decay policy with decay rate $0.2$ and decay steps at the epochs $100$, $200$, $300$.
We found the optimal \ac{sn} coefficient to be $6$. The GMM fit on top of the pretrained feature extractor is trained for $100$ epochs and is fit with $64$ batches.

\textbf{SNGP.}
We trained SNGP with the SGD optimizer with learning rate $0.05$, $L_2$ weight regularization $0.0003$, and a multi-step learning rate decay policy with decay rate $0.2$ and decay steps at the epochs $60$, $120$, $160$.
We found the optimal \ac{sn} coefficient to be $6$, with the GP approximation using $10$ hidden dimensions, lengthscale $2$ and mean field factor $30$.

\textbf{MIR.}
We trained MIR with the Adam optimizer with learning rate $0.001$, and $L_2$ weight regularization $0.0001$.
We found the optimal reconstruction loss weight to be $1$.

\subsubsection{Image Classification - CIFAR10/SVHN}
When training on CIFAR-10/SVHN, we use a ResNet-18~\cite{he2016deep} as backbone.
The dimensionality of the last feature space encoded with the ResNet backbone is $100$ for all methods.
We used a batch size of $128$ samples and trained for $400$ epochs.
The training set is augmented with common data augmentation techniques. We apply random horizontal flips, random brightness augmentation with maximum delta $0.2$ and random contrast adjustment with multiplier lower bound $0.8$ and upper bound $1.2$.

\textbf{Softmax and Deep ensembles.}
We used for the single softmax model the Adam optimizer with learning rate $0.003$, $L_2$ weight regularization $0.0001$, and a multi-step learning rate decay policy with decay rate $0.2$ and decay steps at the epochs $250$, $300$, $400$. When using ensembles, $10$ models are trained from different random initializations.

\textbf{\ac{mc} dropout.}
We used for all baselines the Adam optimizer with learning rate $0.003$, dropout rate $0.3$, $L_2$ weight regularization $0.0001$, and a multi-step learning rate decay policy with decay rate $0.2$ and decay steps at the epochs $250$, $300$, $400$.

\textbf{DUE}
We trained DUE with the SGD optimizer with learning rate $0.01$, $L_2$ weight regularization $0.0005$, dropout rate $0.1$, and a multi-step learning rate decay policy with decay rate $0.2$ and decay steps at the epochs $100$, $200$, $300$.
We found the optimal \ac{sn} coefficient to be $7$ for SVHN and $9$ for CIFAR-10, with the GP approximation using $10$ (number of classes) inducing points initialized using k-means over $10000$ samples.

\textbf{DUQ}
We trained DUE with the SGD optimizer with learning rate $0.01$, $L_2$ weight regularization $0.0001$, dropout rate $0.1$, and a multi-step learning rate decay policy with decay rate $0.3$ and decay steps at the epochs $200$, $250$. $300$.
Lengthscale for the RBF kernel is $0.1$ and optimal gradient penalty loss weight is $0$

\textbf{DDU.}
We trained DDU with the Adam optimizer with learning rate $0.001$, $L_2$ weight regularization $0.0001$, dropout rate $0.3$, and a multi-step learning rate decay policy with decay rate $0.2$ and decay steps at the epochs $80$, $120$, $180$.
We found the optimal \ac{sn} coefficient to be $7$. The GMM fit on top of the pretrained feature extractor is trained for $100$ epochs and is fit with $64$ batches.

\textbf{SNGP.}
We trained SNGP with the SGD optimizer with learning rate $0.05$, $L_2$ weight regularization $0.0004$, dropout rate $0.1$, and a multi-step learning rate decay policy with decay rate $0.2$ and decay steps at the epochs $100$, $200$, $300$.
We found the optimal \ac{sn} coefficient to be $7$, with the GP approximation using $10$ hidden dimensions, lengthscale $2$ and mean field factor $30$.

\textbf{MIR.}
We trained MIR with the Adam optimizer with learning rate $0.003$, $L_2$ weight regularization $0.0001$, dropout rate $0.1$, and a multi-step learning rate decay policy with decay rate $0.2$ and decay steps at the epochs $150$, $200$, $250$, $300$.
We found the optimal reconstruction loss weight to be $1$.

\subsubsection{Semantic Segmentation.}
When training on semantic segmentation, we use a \ac{drn}~\cite{Yu2016, Yu2017} (DRN-A-50) as backbone.
We used a batch size of $8$ samples and trained for $200$ epochs.
Images are rescaled to size $200 \times 320$
The training set is augmented with common data augmentation techniques.
All training samples are augmented with random cropping with factor $0.8$. We apply random horizontal flips, random brightness augmentation with maximum delta $0.2$ and random contrast adjustment with multiplier lower bound $0.8$ and upper bound $1.2$.

\textbf{Softmax.}
We used for the single softmax model the Adam optimizer with learning rate $0.0004$, $L_2$ weight regularization $0.0001$, and a multi-step learning rate decay policy with decay rate $0.3$ and decay steps at the epochs $30$, $60$, $90$, $120$.

\textbf{\ac{mc} dropout.}
We used for all baselines the Adam optimizer with learning rate $0.0004$, dropout rate $0.4$, $L_2$ weight regularization $0.0001$, and a multi-step learning rate decay policy with decay rate $0.3$ and decay steps at the epochs $30$, $60$, $90$, $120$.

\textbf{SNGP.}
We trained SNGP with the SGD optimizer with learning rate $0.0002$, $L_2$ weight regularization $0.0003$, dropout rate $0.1$, and a multi-step learning rate decay policy with decay rate $0.2$ and decay steps at the epochs $20$, $40$, $60$, $80$, $100$.
We found the optimal \ac{sn} coefficient to be $6$, with the GP approximation using $128$ hidden dimensions, lengthscale $2$ and mean field factor $25$.

\textbf{MIR.}
We trained MIR with the Adam optimizer with learning rate $0.0002$, $L_2$ weight regularization $0.0001$, dropout rate $0.1$, and a multi-step learning rate decay policy with decay rate $0.3$ and decay steps at the epochs $30$, $60$, $90$, $120$.
We found the optimal reconstruction loss weight to be $1$.

\subsection{Implementation Details.} \label{ssec:suppl_implementation_details}
All methods were re-implemented in Tensorflow 2.0.
We payed attention to all the details reported in each paper and we run all experiments for each method multiple times to account for stochasticity, \textit{i.e.}{} $5$ times for classification and $3$ times for segmentation.
When an implementation was publicly available, we relied on it.
This is the case for DUQ (\url{https://github.com/y0ast/deterministic-uncertainty-quantification}), SNGP (\url{https://github.com/google/uncertainty-baselines/blob/master/baselines/imagenet/sngp.py}) and DUE (\url{https://github.com/y0ast/DUE}).

\textbf{SNGP.} We follow the publicly available implementation of SNGP, which, compared to the implementation described in the original paper, proposes to further reduce the computational overhead of the GP approximation by replacing the Monte-Carlo averaging with the mean-field approximation~\cite{daunizeau2017semi}.
This is especially relevant in large-scale tasks like semantic segmentation, were it is important to reduce the computational overload.

\subsubsection{Image Classification}
\textbf{DUE.} Note that only DUE uses a \ac{sn} approximation also for the batch normalization layer.
All other methods only restrict the Lipschitz constant of convolutional and fully connected layers.

\textbf{MIR} only differs from regular softmax models in its decoder module used for the reconstruction regularization loss \cite{postels2020hidden}. When training MLP architectures the decoder is comprised of two fully-connected layer. The first has a ReLU activation function and 200 output neruons. The second has a linear activation function and its output dimensionality equals that of the models' input data. When training convolutional neural networks the decoder is comprised of four blocks of transpose convolutions, batch normalization layers and ReLU activation functions that gradually upscale the hidden representations to the dimensionality of the input data. These four blocks are followed by a 1x1 convolution with linear activation function.

\subsubsection{Semantic Segmentation}

\textbf{MIR.} Similar to image classification, MIR only differs from regular segmentation models in its decoder module used for the reconstruction regularization loss \cite{postels2020hidden}. The decoder module is comprised of a single point-wise feed forward layer that maps the hidden representations $\textbf{z}\in \mathbb{R}^{W_z\times H_z \times C_z}$ to $\textbf{z}\in \mathbb{R}^{W_z\times H_z \times 3}$. Subsequently, the result is bilinearly upsampled to the image resolution on which we compute the reconstruction loss.

\subsubsection{Uncertainty Derivation.} \label{ssec:suppl_uncertainty_derivation_classification}
We provide details on the estimation of uncertainty for the baseline methods.
For details on the uncertainty derivation in DUMs, please refer to \autoref{sec:taxonomy} of the main paper or to the original paper of each amalysed method.

\textbf{Softmax.} In case of the softmax baseline we estimate uncertainty using the entropy of the predictive distribution parameterized by the neural network. Given an input $\textbf{x}$ the entropy $H$ is given by $H(\textbf{y}|\textbf{x}) = \sum -p(\textbf{y}|\textbf{x}) \log (p(\textbf{y}|\textbf{x}))$ where $p(\textbf{y}|\textbf{x})$ are the softmax probabilities.

\textbf{\ac{mc} dropout and deep ensembles.} We following \cite{gal2017deep} and compute epistemic uncertainty as the conditional mutual information between the weights $\textbf{w}$ and the predictions $\hat{y}$ given the input $\textbf{x}$. Given an input $\textbf{x}$ and a set of weights $\textbf{w}$ we observe the predictive distribution $p(\hat{y}|x, w)$. Then epistemic uncertainty $u_{ep}$ is calculated by approximating the mutual information conditioned on the input $\textbf{x}$:
\begin{align*}
    u_{ep} &= I\left( \hat{y}, w | x \right) \\
    &= H(\hat{y}| x) -  H(\hat{y}| w, x) \\
    &= E_{y\sim p(\hat{y}|x)} \left[ -\log(p(\hat{y}|x)) \right] - u_{al}
\end{align*}
where $u_{al}$ denotes the aleatoric uncertainty. Here, $p(\hat{y}|x) = \int \mathrm{d}w p(w) p(\hat{y}|x, w)$ is evaluated using a finite set of samples/ensemble members.

\subsubsection{Uncertainty Derivation for Semantic Segmentation.} \label{ssec:suppl_uncertainty_derivation_segmentation}
We derive uncertainty estimates for each method for semantic segmentation.
We average pixel-level uncertainties under the assumption that all pixels are represented by i.i.d. variables.

\textbf{Uncertainty Averaging.}
In our experiments on continuous distributional shifts we want to estimate a global uncertainty for the output map and are not interested in pixel-level confidence. Therefore, we propose to approximate the uncertainty of the predicted segmentation masks as the average of all pixel-level uncertainties, i.e.,
\begin{equation}
\begin{aligned}
    H(\mathbf{y} \mid \mathbf{x}) & = \mathbb{E}_{\mathbf{x}} \left[ -\int_{\mathbf{y}} p(\mathbf{y} \mid \mathbf{x}) \log p(\mathbf{y} \mid \mathbf{x}) \mathrm{d} \mathbf{y} \right] \\
    & = \mathbb{E}_{\mathbf{x}} \left[ -\int_{\mathbf{y}} p(\mathbf{y} \mid \mathbf{x}) \log p(y_1 \mid \mathbf{x}) \mathrm{d} \mathbf{y} \right] + \cdots + \mathbb{E}_{\mathbf{x}} \left[ -\int_{\mathbf{y}} p(\mathbf{y} \mid \mathbf{x}) \log p(y_n \mid \mathbf{x}) \mathrm{d} \mathbf{y} \right] \\
    & \approx \frac{1}{n} \sum_{i=1}^n H(y_i \mid \mathbf{x})
\end{aligned}
\end{equation}

\textbf{MIR} estimates epistemic uncertainty using the likelihood of hidden representations $\textbf{z}\in \mathbb{R}^{W_z\times H_z \times C_z}$. Since $\textbf{z}$ is high-dimensional in our experiments, we assume that it factorizes along $W_z$ and $H_z$ and is translation invariant. Formally, $p(\textbf{z}) = \prod_i^{W_z}\prod_{j}^{H_z}p_{\theta}(\textbf{z}_{ij})$ where $\textbf{z}_{ij} \in \mathbb{R}^{W_z\times H_z}$ and $\theta$ is shared across $W_z$ and $H_z$.

We parameterize $p_{\theta}$ with a GMM with $n=10$ components where each component has a full covariance matrix. We fit the GMM on $100000$ hidden representations ($\textbf{z}_{ij} \in \mathbb{R}^{C_z}$) randomly picked from the training dataset post-training. Since $C_z = 1024$ is still high-dimensional, we first apply PCA to reduce its dimensionality to $32$.

In the dilated resnet architecture used for semantic segmentation the latent representation $\textbf{z}$ is passed through a point-wise feedforward layer $f: \mathbb{R}^{W_z\times H_z \times C_z} \mapsto \mathbb{R}^{W_z\times H_z \times 3}$ and, subsequently, bilinearly upsampled to image resolution ($\mathbb{R}^{W\times H \times K}$) where K is the number of classes. We could estimate the global, \textit{i.e.} image-level, uncertainty of an input, by providing the negative log-likelihood of the factorizing distribution. However, in order to also obtain pixel-wise uncertainties using MIR, we first compute the negative log-likelihood (\textit{i.e.} epistemic uncertainty) associated with each latent representation $\textbf{z}_{ij}$. Then, we bilinearly upsample the negative log-likelihoods and use the result as proxy for pixel-wise epistemic uncertainty. To obtain a global, \textit{i.e.} image-level, uncertainty we apply the same averaging scheme used for SNGP, softmax and \ac{mc} dropout.

\subsection{Dataset} \label{ssec:suppl_segmentation_dataset}
To benchmark our model on data with realistically and continuously changing environment, we collect a synthetic dataset for semantic segmentation.
We use the CARLA Simulator~\cite{Dosovitskiy17} for rendering the images and segmentation masks. The classes definition is aligned with the CityScape dataset~\cite{Cordts2016Cityscapes}. In order to obtain a fair comparison, all the OOD data are sampled with the same trajectory and the environmental objects, except for the time-of-the-day or weather parameters.

\paragraph{In-domain data} The data is collected from 4 towns in CARLA. We produce 32 sequences from each town. The distribution of the vehicles and pedestrians are randomly generated for each sequence. Every sequence has has 500 frames with a sampling rate of $10$ FPS. From them we randomly sample the training and validation set.

\paragraph{Out-of-domain data} Here, we consider the time-of-the-day and the rain strength as the  parameters for the continuous changing environment. In practice, these two parameters have major influence for autonomous driving tasks.

 The change of the time-of-the-day is illustrated in Fig.~\ref{fig:carla_time}. The time-of-the-day is parametrized by the Sun's altitude angle, where $90^\circ$ means the mid-day and the $0^\circ$ means the dust or dawn. Here, we produce samples with the altitude angle changes from $90^\circ$ to $15^\circ$ by step of $5^\circ$, and $15^\circ$ to $-5^\circ$ by step of $1^\circ$ where the environment changes shapely. From these examples, we can confirm that the change of time-of-the-day leads to the major change in the lightness, color and visibility of the sky, roads and the buildings nearby.
The effect of rain strength is demonstrated in Fig.~\ref{fig:carla_weather}. Here the cloudiness and, ground wetness and ground reflection are the main changing parameters.
\begin{figure}[htbp]
    \def3.4cm{3.4cm}
    \centering
    \subfloat[Mid-day ($90^\circ$)]{\includegraphics[width=3.4cm]{figures/continue/90.resize.png}} \ %
    \subfloat[Afternoon ($45^\circ$)]{\includegraphics[width=3.4cm]{figures/continue/45.resize.png}} \ %
    \subfloat[Afternoon ($15^\circ$)]{\includegraphics[width=3.4cm]{figures/continue/15.resize.png}} \ %
    \subfloat[Evening ($10^\circ$)]{\includegraphics[width=3.4cm]{figures/continue/10.resize.png}} \\%
    \subfloat[Dust ($2^\circ$)]{\includegraphics[width=3.4cm]{figures/continue/3.resize.png}} \ %
    \subfloat[Sunset ($0^\circ$)]{\includegraphics[width=3.4cm]{figures/continue/0.resize.png}} \ %
    \subfloat[Sunset ($-2^\circ$)]{\includegraphics[width=3.4cm]{figures/continue/_2.resize.png}} \ %
    \subfloat[Night ($\leq -5 ^\circ$)]{\includegraphics[width=3.4cm]{figures/continue/_5.resize.png}}%
    \caption{Changing of the time-of-the-day}
    \label{fig:carla_time}
\end{figure}
\begin{figure}[htbp]
    \def3.4cm{3.4cm}
    \centering
    \subfloat[Clear]{\includegraphics[width=3.4cm]{figures/weather/clear.resize.png}} \ %
    \subfloat[Cloudy]{\includegraphics[width=3.4cm]{figures/weather/cloudy.resize.png}} \ %
    \subfloat[Small rain]{\includegraphics[width=3.4cm]{figures/weather/small_rain.resize.png}} \ %
    \subfloat[Heavy rain]{\includegraphics[width=3.4cm]{figures/weather/heavy_rain.resize.png}}
    \caption{Changing of the weather}
    \label{fig:carla_weather}
\end{figure}


\section{Introduction}
\IEEEPARstart{M}{}ost unmanned aircraft rely on the global navigation satellite system (GNSS) to ascertain their position and velocity during flight. The GNSS is usually used to recalibrate the inertial navigation system (INS) periodically as the INS estimates a vehicle’s current position and velocity by integrating acceleration data over time. However, especially in military applications, various factors like jamming, interference, and unintentional interference due to terrain geometry can cause the GNSS device to work in an erroneous mode or shut down. Many researchers have been working in alternative/supplementary systems to cope with GNSS-devoid environments. These systems are required to control error accumulation of the INS and provide the absolute position in
terms of latitude and longitude.

One alternative is terrain-aided navigation (TAN) or terrain-referenced navigation (TRN) where the positioning data is provided by comparing the radar altimeter measurements of terrain elevation under an aircraft with an onboard digital elevation model (DEM). TAN has been considered as a solid alternative since it is all-weather capable in a sufficiently low flight altitude above terrain by utilizing a radar altimeter. However, the TAN system can be used in limited applications where an expensive, heavy altimetry sensor is available, e.g., cruise missiles or large aircraft. Moreover, it is well known that the TAN system mainly suffer from terrain ambiguity \cite{kim2017utilizing} and slant range measurements \cite{spiegel2016slant} due to the nature of one-dimensional, wide-lobe radar altimeter measurements.

Another alternative is vision-based navigation where images taken by a camera on an aircraft are used to estimate the position of the aircraft. There are two features that make this approach attractive; first, cameras are passive sensors, so it is hard to detect or interfere with them. Second, because most unmanned aircraft are already equipped with cameras, they don’t have to mount additional payload for utilizing vision data to navigate. Earlier works on vision-based navigation addressed positioning by obtaining elevation data from aerial images and then matching it to a DEM \cite{sim2002integrated, rodriguez1990matching}. These approaches can be viewed as a two-dimensional extension of TAN. A recently proposed work uses a stereo analysis of the image sequence to obtain heights of the feature points and compare them with the DEM to estimate the vehicle state \cite{kim2018vision}. However, the so-called vision-based TAN approach is limited because the performance depends on the resolution and accuracy of the DEM. Furthermore, in practice the visual terrain surface elevation can differ from the DEM that is usually obtained by a synthetic aperture radar (SAR). Hence, careful construction of the digital surface model (DSM) as in \cite{el2014digital} is required to acquire an elevation model of the visual terrain surface.

Map-based navigation approaches have been attracting attention since recently public map databases that render 2D locations on aerial/satellite imagery have become available, including Google Maps, Airbus Defence and Space, and OpenStreetMap. Thus, once established, the map-based navigation technology will require no map-building process and can be scaled to various types of aircraft systems and map databases. Several approaches have been attempted to match images taken by an aircraft-mounted camera to the public map: image registration by adopting a correlation filter \cite{shan2015google} and feature point detection and matching between two scenes \cite{zhuo2017automatic}. Mountain drainage patterns \cite{wang2016characterization} and road intersection \cite{volkova2018more} have also been used to characterize scenes. However, relevant works have reported that variations in scale, orientation, and illumination pose challenges to these vision-based approaches. Moreover, because the imagery in a public map database is not regularly or consistently updated, the aerial images recorded in flight may differ due to seasonal changes. A more robust technique for scene matching is required for realizing a reliable map-based navigation system. The huge amount of storage required for the image database is another problem that threatens practicality of the map-based navigation.

To tackle the problems above, this paper proposes the novel use of deep learning technologies as a tool for extracting high-level features, called ``labels'', from aerial images and a map database. The deep learning is supposed to do what it does well as a part of an image processing system, rather than more complex tasks like image matching and navigation. For example, once ground objects such as road intersections, buildings, and highways are distinguished, not necessarily identified, the configuration of the objects can be used to find corresponding location in the map database. In other words, the aerial localization is done by pattern matching of labelled objects, not image-to-image matching. Semantic segmentation is known to provide accurate object position in the image. However, other methods like object detection can be also employed compromising accuracy for speed. In this way, the aerial images are converted to a set of dense information that is robust to imagery variations and noises, requiring significantly less storage and computational power. To show the feasibility of such an approach, this paper proposes and verifies a pattern matching algorithm for estimating the camera's position assuming the image processing is done.

The rest of this paper is organized as follows. It starts with addressing the proposed map-based navigation system in Section \ref{sec:system}. The method to utilize the labelled objects for pattern matching is discussed in detail. The feasibility the proposed approach with simulated images is discussed in Section \ref{sec:simulation}. Finally, Section \ref{sec:conclusion} gives summary and conclusion.

\begin{figure}[t!]
	\centering
	\includegraphics[clip,width=1.0\linewidth]{fig01.png}%
	\caption{Block diagram of the proposed map-based navigation system.}
	\label{fig:diagram}
\end{figure}

\section{Proposed Map-Based Navigation System}\label{sec:system}
The block diagram of the proposed map-based navigation system is presented in Fig. 1. The overall system consists of image processing, probabilistic data fusion, and attitude and heading reference system (AHRS) blocks. Output of this system is the primary aircraft states: position, velocity, and attitude. The key idea of the proposed approach is depicted in Fig. 2, which consists of image processing and pattern matching. These are discussed in detail below in Section \ref{sec:semantic} and \ref{sec:pattern}, followed by brief remarks on velocity estimation and probabilistic data fusion.

\begin{figure}[t!]
	\centering
	\includegraphics[clip,width=0.95\linewidth]{fig02.png}%
	\caption{The configuration of labelled ground objects is used to match the aerial scene with the meta image of the database. The red rectangles denote the result of semantic segmentation on an aerial image. The black dots denote the labelled objects. The red cross denotes the center of the image.}
	\label{fig:pattern}
\end{figure}

\subsection{Image Processing}\label{sec:semantic}
The navigation is started by the image processing block that classifies and localizes (within an image) various ground objects. Deep learning systems have been proven to very effective in separating the objects from the background and classify them. State-of-the-art approaches of deep learning can be used as a tool for object labelling. For example, Mask R-CNN \cite{he2017mask} has shown superior performance on segmentation and classification. Successful semantic segmentations on aerial images have also been reported \cite{marmanis2016semantic, mallberg2018map, niu2021hybrid}. Besides, the oriented object detection methods on aerial images \cite{xie2021orcnn, yang2021kl} are emerging as attractive candidates. The recent progress of oriented object detection is reporting evolving accuracy, featuring its inherent efficiency.

Each ground object can be designated a label such as building, stadium, park or green area, road intersection, lake or river, agricultural field, and mountain. These ground objects are very robust about preserving their shape. The objects in the image can be represented as dots by averaging the pixels occupying each object. Constructing such an on-board meta-image map should also be done where the objects in the map are classified in the same way for the aerial scene.

Note that the term ``localization'' in image processing or deep learning means obtaining objects' positions in the image, e.g., in pixels. On the other hand, the purpose of the overall navigation is to obtain position of the camera in the reference frame the map database is based on, e.g., in meters.

\subsection{Pattern Matching and Localization}\label{sec:pattern}
The configuration of the objects in the image is compared to the configuration of those in the map database. This is called pattern matching here, not landmark matching, because the random ground objects in a scene are used to match the scene against the map. In other words, it is not required to identify each ground object. In this way, the proposed approach lowers the burden of image processing and therefore it is expected to increase robustness of the vision-based navigation system. Since the objects are represented as dots, the pattern matching problem involves scale-invariant and rotation-invariant features.

\begin{algorithm*}[tb!]
	\caption{Proposed Pattern Matching Algorithm}
	\begin{algorithmic}[1]
		\State $N_{best} = 0$
		\State $E_{best} = \inf$
		\State $c_{best}^D = \textnormal{None}$
		\For {$(o_i^I,o_j^I) \in C(O^I)$}
		\State \textit{Calculate polar coordinates from the center of the image:} $(r_i, \theta_i), (r_j, \theta_j)$
		\State $\Delta \theta_j = \theta_i - \theta_j$
		\For {$(o_i^D,o_j^D) \in P(O^D)$ \textbf{if} $label(o_i^D) = label(o_i^I)$ \textbf{and} $label(o_j^D) = label(o_j^I)$}

		\State \textit{Find the origin of the polar coordinates on database,} $c_{ij}^D$\textit{, satisfying} \newline
		$~~~~~~~~~~~~\Delta \Theta_j = \Theta_i - \Theta_j = \Delta \theta_j$ \textit{and} $R_i : R_j = r_i : r_j$ \newline
		$~~~~~~~~~~~~$\textit{where} $(R_i, \Theta_i), (R_j, \Theta_j)$ \textit{are polar coordinates of} $o_i^D,o_j^D$ \textit{with origin} $c_{ij}^D$
		\State $N_{matched} \leftarrow 2$
		\For {$o_k^I \in O^I - \{o_i^I,o_j^I\}$}
		\State \textit{Calculate} $r_k, \theta_k$ \textit{and therefore} $r_k / r_i, \Delta \theta_k$
		\For {$o_k^D \in O^D - \{o_i^D,o_j^D\}$ \textbf{if} $label(o_k^D) = label(o_k^I)$}
		\State \textit{Calculate} $R_k, \Theta_k$ \textit{and therefore} $R_k / R_i, \Delta \Theta_k$
		\If {$|r_k / r_i - R_k / R_i| < \delta_r $ \textbf{and} $|\Delta \theta_k - \Delta \Theta_k|< \delta_{\theta}$}
		\State $e_k = |r_k / r_i - R_k / R_i| + |\Delta \theta_k - \Delta \Theta_k|$
		\State $N_{matched} \leftarrow N_{matched} + 1$

		\EndIf
		\EndFor
		\EndFor

		\If {$N_{matched} >= N_{min}$}
		\State $E_{ij} = std(\{e_k\})$
		\If {$N_{matched} >= N_{best}$ \textbf{and} $E_{ij} < E_{best}$}
		\State $N_{best} \leftarrow N_{matched}$
		\State $E_{best} \leftarrow E_{ij}$
		\State $c_{best}^D \leftarrow c_{ij}^D$

		\EndIf

		\EndIf

		\EndFor
		\EndFor

		\State \textit{Return} $c_{best}^D$
	\end{algorithmic}
\end{algorithm*}

Here a random sample consensus (RANSAC) \cite{fischler1981random} based method is proposed in Algorithm 1. The consensus algorithm will iteratively test hypotheses of matching between the labels in an image and those in the database to provide one or multiple matching candidates where each label in the image has the same relative angle and distance to the equivalent label in the database. Suppose objects in the image and the database are denoted as $o^I$ and $o^D$, respectively. Each object pertains to its label and 2-dimensional position in its own coordinate system. It is assumed the image is taken by a downward-looking camera. If the attitude of the camera is not zero, the attitude information can be incorporated to project the image objects onto the plane parallel to the ground before executing the algorithm. The set of objects in the image is denoted as $O_I$, and that in the database as $O^D$. For every 2-combination of the objects on the image, $(o_i^I,o_j^I) \in C(O^I)$ where $C(O^I)$ means all the 2-combinations of the image objects, the polar coordinates of the two objects are calculated. Taking the polar coordinates of the first object $o_i^I$ as the reference, the relative radius and angle, $r_j / r_i$ and $\theta_i - \theta_j$, are compared as depicted in Fig. 3. All the angle differences here are represented in $(-\pi,\pi]$. For every 2-permutation of objects in the database, $(o_i^D,o_j^D) \in P(O^D)$, find the origin of the polar coordinates that makes the same configuration that $(o_i^I,o_j^I)$ does to the image center. This can be done by finding the intersection of two circles with radius $R_i$ and $R_i \times r_j/r_i$, centered at $o_i^D$ and $o_j^D$, respectively. The intersection with the same sign of the relative angle is chosen out of at most two intersections. Every time the match between the image object and the database object with the same relative radius and angle with tolerances $\delta_r$ and $\delta_{\theta}$ is found, increment the number of matched points $N_{matched}$ and store the matching error $e_k$. The matching candidate with the lowest standard deviation of matching error is chosen as the best match and the pattern matching outputs the corresponding horizontal position. Note that the proposed algorithm doesn't require a camera model or altitude information to get the horizontal position. The coordinates and labels of the objects in the image and the database are the only input.

\begin{figure}[b!]
	\centering
	\includegraphics[clip,width=0.8\linewidth]{fig03.png}%
	\caption{The polar coordinates of the image objects with respect to the image center.}
	\label{fig:matching}
\end{figure}

Several variants of the algorithm are available. Algorithm 1 attempts to match the objects in the image to those in the whole database. In practice, one can guess a region the objects are probably within by using the results of the probabilistic data fusion technique, which is discussed in Section \ref{sec:filter}. Searching for objects in a smaller region will reduce the computation time and the number of false positives. Plus, whereas Algorithm 1 tests if the objects have the same label, classifying the objects into a smaller set of labels, or only one label, is possible to get more robust matches compromising uniqueness. If ambiguity arises and it is hard to determine the best match, it is able to output multiple candidates and let the probabilistic filter deal with them. Moreover, if the camera model is known, the height above ground can be induced from the projection of the matched data objects into the image. Users can exploit any variant design to meet their needs.

\subsection{Velocity Estimation}
The image processing block should provide both velocity and position as an alternative to GNSS for unmanned aircraft navigation. Although the observability in velocity is required to correct the INS drift, many existing studies haven’t addressed velocity estimation for vision-based navigation. It is well known that the velocity can be measured using optical flow techniques. Or one can borrow the insights from a recent work \cite{bloesch2017iterated} for visual-inertial odometry technique.

\subsection{Probabilistic Data Fusion}\label{sec:filter}
Designing a probabilistic filter requires analysis on the measurement and error models of the localization and velocity estimation blocks. It is obvious that an altimeter is required for the altitude information because the pattern matching and localization block provides horizontal position. This 3-dimensional position and the 3-dimensional velocity from the velocity estimation block will construct the measurement. If it turns out the measurement errors can be modelled as additive Gaussian noise, as in GNSS, borrowing a simple INS/GNSS filter \cite{kim2019introduction} will be desirable. If the pattern matching and localization block is designed to provide multiple candidates of aircraft position from a scene, possibly a particle filter dealing with a multimodal distribution will be suitable.

In cases where the navigation performance depends on aircraft states, information theory can be exploited to quantify and control the information gathered by the sensors. Background in information theory \cite{kim2019real} would be helpful in this problem. For example, desirable or undesirable trajectory can be analyzed to meet the criteria of the navigation performance.

The probabilistic filter provides the estimated state and its covariance as an output. The covariance is the measure of uncertainty of the estimate. The uncertainty information can be used to restrain the region of interest on the database to reduce false matchings computational burden in pattern matching.

\section{Feasibility Verification}\label{sec:simulation}
The feasibility of the proposed approach described above is verified by a simulation. Suppose it is able to get labelled objects of aerial images and a map database. It is tested if the proposed pattern matching and localization, Algorithm 1, works with the simulated image objects under various conditions.

\begin{figure}[t!]
	\centering
	\includegraphics[clip,width=0.95\linewidth]{fig04.png}%
	\caption{The graph at the top represents positions of objects in the database used in the simulation. The red rectangle denotes an area the camera takes an aerial image for an instance. The resulting image is simulated as the graph at the bottom.}
	\label{fig:simulation}
\end{figure}

\subsection{Method}
Suppose a database meta image contains labelled objects and their absolute horizontal positions in meters. A unmanned aircraft with a downward-looking camera takes aerial images. The simulated images are generated by using the true absolute horizontal position and the true height above ground, the camera's field of view (FOV), the image size in pixels, and errors in camera attitude and image processing. For example, the squared region in Fig. 4 is projected onto the image on the right. The database represents objects with the same label in a region of 250$\times$150 meters. The image size is 640$\times$480 pixels.

\begin{table*}[t]
	\captionsetup{justification=centering}
	\caption{Control variables and result of the simulation.}
	\centering
	\label{tab:result}
	\renewcommand{\arraystretch}{1.5}
	\begin{tabular}{|c|l|M{2.0cm}|M{2.0cm}|M{2.0cm}|M{2.0cm}|M{2.0cm}|}
		\hline
		\multicolumn{1}{|l|}{}      &                          & Case 1      & Case 2         & Case 3           & Case 4         & Case 5        \\ \hline
		\multirow{3}{*}{Variables} & Attitude error std (deg) & 0           & 0.05           & 0.05             & 0.15           & 0.15          \\ \cline{2-7}
		& Pixel error std (pixel)  & 0           & 1              & 3                & 3              & 3             \\ \cline{2-7}
		& Field of view (deg)      & 35          & 35             & 35               & 35             & 45            \\ \hline
		\multirow{3}{*}{Result}     & Error std (m)            & 0.01        & 0.53           & 1.97             & 1.74           & 3.29          \\ \cline{2-7}
		& \# of rejected images       & 0/500 (0\%) & 22/500 (4.4\%) & 107/500 (21.4\%) & 95/500 (19\%)  & 0/500 (0\%)   \\ \cline{2-7}
		& \# of false positives       & 0/500 (0\%) & 2/478 (0.4\%)  & 30/393 (7.6\%)   & 36/405 (8.9\%) & 9/500 (1.8\%) \\ \hline
	\end{tabular}%
	\renewcommand{\arraystretch}{1}
\end{table*}

The attitude error and image processing error are also reflected. The attitude error is contributed by the gimbal control error. The pattern matching algorithm assumes the camera is looking straight down, but actually the camera is misaligned by the attitude error in the simulated image. Note that the algorithm is not affected by yaw angle (horizontal rotation) or its error. The database and the image in the simulation are aligned in yaw axis, for better presentation without loss of generality, and the errors in pitch and roll are used. And the imperfect image processing causes the pixel error on x, y coordinates of each object in the image. All the errors are sampled from normal distributions of given standard deviations.

Using the database meta image in Fig. 4, 500 random true positions from uniform distributions in x, y axes are sampled. The set of objects in each image and the set of objects in the map database are fed into Algorithm 1. The result of Algorithm 1 on the simulated images is compared to the true positions. The images are taken at $100 m$ above the ground, and the FOV and error statistics are controlled to see the effect of the number of objects in the image and the type of errors. The attitude error of $0.05^{\circ}$, slightly larger than that of an industry level AHRS, and the pixel error of $1$, as the discretization error, are taken as the reference error statistics. By increasing each threefold, the effect of each error is observed. FOVs of $35^{\circ}$ and $45^{\circ}$ are tested to see the effect of the number of objects in the images. All the cases are run with the same parameters: $N_{min} = 6$, $\delta_{\theta} = 0.2$, $\delta_{r} = 0.2$. Larger threshold values tends to accept more false positives and smaller threshold values tends to reject more matches.

\subsection{Result}
Table 1 shows the result of the simulation on 5 different cases. The standard deviation of the horizontal distance error are presented with the number of rejected matching instances and the number of false positive matchings. Cases 1-4 are with the FOV of $35^{\circ}$ where the average number of objects taken in the images is about 17. Case 1 is the result with no attitude error and no pixel error. It shows an almost perfect matching and the nonzero position estimation error comes from the generous thresholds in the matching algorithm. Case 2 is the result with the attitude error of $0.05^{\circ}$ and the pixel error of $1$. One can observe the pattern matching algorithm is able to estimate the absolute position with reasonable estimation errors. $4.4 \%$ of matchings are rejected in this case. This happens when the position estimate is not provided because the number of matched points are less than $N_{min}$. The false positive is the case when the algorithm finds a wrong matching. The large number of false positives is observed when the pixel error is increased to 3 as in Case 3. This can be mitigated by using a prior knowledge of the region the camera might be taking to reject unreasonable outputs. The attitude error is increased in Case 4. It doesn't necessarily affect the matching itself because the relative configuration of the image objects is not changed by the attitude error. The estimation error as well shows no noticeable difference from Case 3. The effect of the attitude error might be relatively smaller than the pixel error where $0.15^{\circ}$ of angle error corresponds to $0.26 m$ on the ground. The FOV is increased to $45^{\circ} $ in Case 5 where the average number of objects in the images is about 34. In this case, no matching is rejected and only $1.8 \%$ of the matchings are false positives despite the large pixel error. Capturing more objects helps finding the match, but the decreased resolution might cause larger position estimation error.

\section{Conclusion}\label{sec:conclusion}

The proposed method aims for realizing a robust map-based navigation system for unmanned aircraft. In summary, the pattern matching and localization block compares the aerial images with a map database in a robust, efficient way to provide the horizontal position. The key idea is to let the map matching algorithm deal with the high-abstraction information of the image, rather than the image itself. The map-based navigation system is expected to continuously provide the position and velocity by probabilistic data fusion of the position information from the pattern matching with the velocity from visual-inertial odometry.

The feasibility analysis with simulated meta images shows that the proposed pattern matching algorithm can provide position estimates by using labelled objects on the images and the database. The proposed approach to map-based navigation would be an attractive choice for image-based navigation if the image processing block is able to provide labelled objects and their positions in the image.

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

\bibliographystyle{IEEEtran}