Image registration is a demanding task that is required in many different areas of application, in particular in medical imaging. Due to the ill-posedness of image registration problems, regularization is unavoidable. This paper focuses on a family of so-called vector-field (VF) regularizers which consist of second-order energies based on a convex combination of gradients of divergence and rotation. Following a discretize-then-optimize approach, this paper proposes a staggered-grid discretization of the VF regularizers and applies a quasi-Newton type minimization to the image registration problem. Here the most costly part is solving linear systems, which can be regarded as a discretization of a linearization of a partial differential equation of fourth order. This paper proposes a highly efficient multigrid (MG) solver. In particular, the paper presents a local Fourier analysis to show that the suggested discretization is well suited for MG. More specifically, the paper provides an explicit number for the h-ellipticity measure and the local smoothing factor for a collective \(\omega \) -relaxed Jacobi-type iteration. Our numerical results, including 3D image registration tasks, underline that the MG solver has in fact a complexity of \(\mathcal {O}(n)\) , where n is the number of unknowns.