  Color descriptors are one of the important features used in content-based
image retrieval. The Dominant Color Descriptor (DCD) represents a few
perceptually dominant colors in an image through color quantization. For image
retrieval based on DCD, the earth mover's distance and the optimal color
composition distance are proposed to measure the dissimilarity between two
images. Although providing good retrieval results, both methods are too
time-consuming to be used in a large image database. To solve the problem, we
propose a new distance function that calculates an approximate earth mover's
distance in linear time. To calculate the dissimilarity in linear time, the
proposed approach employs the space-filling curve for multidimensional color
space. To improve the accuracy, the proposed approach uses multiple curves and
adjusts the color positions. As a result, our approach achieves
order-of-magnitude time improvement but incurs small errors. We have performed
extensive experiments to show the effectiveness and efficiency of the proposed
approach. The results reveal that our approach achieves almost the same results
with the EMD in linear time.
