Color is actually much more difficult than most people realize! Even CIE2000 color distance still has fundamental "perceptual distance" problems, especially comparing non-saturated with saturated colors (although that's a blog post in its own).
Here's our engine linking "real world" photos into the Macys catalogue (based on color, shape, texture): http://www.pcsso.com/demo/macys.htm
It is impossible to create a three dimensional color space in which Euclidean distance corresponds directly to perceived color difference. There are dozens of papers on this topic, for anyone who wants some fun evening reading.
Yes, absolutely, which (I'm assuming) is why CIE2K difference is not-quite-euclidean. My opinion is the we still need to find a better difference metric, rather than improving the color space.
On that front, it's amazing to see how much of an effect "switching color spaces" can have on many algorithms.
Yeah, totally agree on that. We noticed this as well when approaching it naively via simple clustering then going through different color spaces and methods until finally getting some decent results.
Here's our engine linking "real world" photos into the Macys catalogue (based on color, shape, texture): http://www.pcsso.com/demo/macys.htm