For the successful completion of medical interventional procedures, several concepts, such as daily positioning compensation, dose accumulation or delineation propagation, rely on establishing a spatial coherence between planning images and images acquired at different time instants over the course of the therapy. To meet this need, image-based motion estimation and compensation relies on fast, automatic, accurate and precise registration algorithms. However, image registration quickly becomes a challenging and computationally intensive task, especially when multiple imaging modalities are involved. In the current study, a novel framework is introduced to reduce the computational overhead of variational registration methods. The proposed framework selects representative voxels of the registration process, based on a supervoxel algorithm. Costly calculations are hereby restrained to a subset of voxels, leading to a less expensive spatial regularized interpolation process. The novel framework is tested in conjunction with the recently proposed EVolution multi-modal registration method. This results in an algorithm requiring a low number of input parameters, is easily parallelizable and provides an elastic voxel-wise deformation with a subvoxel accuracy. The performance of the proposed accelerated registration method is evaluated on cross-contrast abdominal T1/T2 MR-scans undergoing a known deformation and annotated CT-images of the lung. We also analyze the ability of the method to capture slow physiological drifts during MR-guided high intensity focused ultrasound therapies and to perform multi-modal CT/MR registration in the abdomen. Results have shown that computation time can be reduced by 75% on the same hardware with no negative impact on the accuracy.