Imaging techniques and applications often require heavy computations for finding the k-nearest-neighbour of a given pattern. Texture synthesis, image colourisation and super-resolution are all affected by this issue. Advanced clustering-based indexing schemas over metric spaces speed-up efficiently both k-nearest-neighbour and range searches. By using them, we are able to save CPU time without losing quality which would be lost using approximate approaches. Moreover, with the proposed technique we are able to convert a batch process task into a real-time task and, more importantly, it might be run on a typical user-end PC desktop rather than powerful mainframes. It has been shown how the application of recently reported well-known indexing schemas improves the speed performance of the above problems.