  This paper considers the problem of estimating the covariance of
roto-translations computed by the Iterative Closest Point (ICP) algorithm. The
problem is relevant for localization of mobile robots and vehicles equipped
with depth-sensing cameras (e.g., Kinect) or Lidar (e.g., Velodyne). The
closed-form formulas for covariance proposed in previous literature generally
build upon the fact that the solution to ICP is obtained by minimizing a linear
least-squares problem. In this paper, we show this approach needs caution
because the rematching step of the algorithm is not explicitly accounted for,
and applying it to the point-to-point version of ICP leads to completely
erroneous covariances. We then provide a formal mathematical proof why the
approach is valid in the point-to-plane version of ICP, which validates the
intuition and experimental results of practitioners.
