Accurate Approximation of the Earth Mover's Distance in Linear Time

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 (EMD) and the optimal color composition distance were 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.This research was supported by the MSIP (Ministry of Science, ICT, and Future Planning), Korea, under the IT-CRSP (IT Convergence Research Support Program) with No. NIPA-2013-H0401-13-1001 supervised by the NIPA (National IT Industry Promotion Agency) and by the NRF (National Research Foundation) of Korea Grant funded by the Korean Government with No. NRF-2011-330-B00076. This research was also supported by the Basic Science Research Program through the NRF funded by the Ministry of Education, Science and Technology of Korea under Grant Nos. 2012R1A1A2007817 and 2013R1A6A3A03027153