We have previously presented a new scan-matching algorithm based on the IDC (iterative dual correspondence) algorithm, which showed a good localization performance even in environments with severe changes. The problem of the IDC algorithm is that there is no good way to estimate a covariance matrix of the position estimate, which prohibits an effective fusion with other position estimates of other sensors. This paper presents two new ways to estimate the covariance matrix. The first estimates the covariance matrix from the Hessian matrix of the error function minimized by the scan-matching algorithm. The second one, which is an off-line method, estimates the covariance matrix of a specific scan, from a specific position by simulating and matching scans around the position. Simulation results show that the covariance matrix provided by the off-line method fully corresponds with the real one. Some preliminary tests on real data indicate that the off-line method gives a good quality value of a specific scan position, which is of great value in map building.