Abstract Already for reasonable sized 3D images, image registration becomes a computationally intensive task. Here, we introduce and explore the concept of OcTree’s for registration which drastically reduces the number of processed data and thus the computational costs. We show how to map the registration problem onto an OcTree and present a suitable optimization technique. Furthermore, we demonstrate the performance of the new approach by academic as well as real life examples. These examples indicate that the computational time can be reduced by a factor of 10 compared with standard approaches.