We study completeness properties of the Sobolev diffeomorphism groups Ds(M) endowed with strong right-invariant Riemannian metrics when the underlying manifold M is Rd or compact without boundary. The main result is that for s>dimM/2+1, the group Ds(M) is geodesically and metrically complete with a surjective exponential map. We then present the connection between the Sobolev diffeomorphism group and the large deformation matching framework in order to apply our results to diffeomorphic image matching.