Most automated MRI tissue-segmentation techniques require whole-brain atlases, which are extremely time-consuming to manually delineate. This inhibits utilisation of complementary structural sequences during segmentation as matching atlases rarely exist. We demonstrate a means of reducing the computational complexity of patch-based segmentation using self-organising maps. This overcomes the need for local-only searching of matching patches and, in turn, the need for complete atlases. We demonstrate this technique’s ability to perform registration-free tissue-segmentation of target images using an atlas that is less than 2% complete. The technique may be used as-is, or for rapidly generating novel whole-brain atlases for other techniques.