A mechanism is provided in a data processing system comprising a processor and a memory, the memory comprising instructions executed by the processor to specifically configure the processor to implement a multi-atlas segmentation engine. An offline registration component performs registration of a plurality of atlases with a set of image templates to thereby generate and store, in a first registration storage device, a plurality of offline registrations. The atlases are annotated training medical images and the image templates are non-annotated medical images. The multi-atlas segmentation engine receives a target image. An image selection component selects a subset of image templates in the set of image templates based on the target image. An online registration component performs registration of the subset of image templates with the target image to generate a plurality of online registrations. The multi-atlas segmentation engine retrieves offline registrations corresponding to the subset of image templates from the first registration storage device. The multi-atlas segmentation engine performs segmentation of the target image based on the retrieved offline registrations corresponding to the subset of image templates and the plurality of online registrations. The segmentation applies labels to anatomical structures present in the target image based on the retrieved offline registrations and the plurality of online registrations to thereby output a modified target image.