I've had good results from converting to Lab space and geospatial indexing the ab components.

http://en.m.wikipedia.org/wiki/Lab_color_space