  We present a novel computational approach to fast and memory-efficient
deformable image registration. In the variational registration model, the
computation of the objective function derivatives is the computationally most
expensive operation, both in terms of runtime and memory requirements. In order
to target this bottleneck, we analyze the matrix structure of gradient and
Hessian computations for the case of the normalized gradient fields distance
measure and curvature regularization. Based on this analysis, we derive
equivalent matrix-free closed-form expressions for derivative computations,
eliminating the need for storing intermediate results and the costs of sparse
matrix arithmetic. This has further benefits: (1) matrix computations can be
fully parallelized, (2) memory complexity for derivative computation is reduced
from linear to constant, and (3) overall computation times are substantially
reduced.
  In comparison with an optimized matrix-based reference implementation, the
CPU implementation achieves speedup factors between 3.1 and 9.7, and we are
able to handle substantially higher resolutions. Using a GPU implementation, we
achieve an additional speedup factor of up to 9.2.
  Furthermore, we evaluated the approach on real-world medical datasets. On ten
publicly available lung CT images from the DIR-Lab 4DCT dataset, we achieve the
best mean landmark error of 0.93 mm compared to other submissions on the
DIR-Lab website, with an average runtime of only 9.23 s. Complete non-rigid
registration of full-size 3D thorax-abdomen CT volumes from oncological
follow-up is achieved in 12.6 s. The experimental results show that the
proposed matrix-free algorithm enables the use of variational registration
models also in applications which were previously impractical due to memory or
runtime restrictions.
