Accurate approximation of the earth mover's distance in linear time

Min Hee Jang, Sang Wook Kim, Christos Faloutsos, Sunju Park

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)142-154
Number of pages13
JournalJournal of Computer Science and Technology
Issue number1
Publication statusPublished - 2014 Jan

Bibliographical note

Funding Information:
Regular Paper 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. ∗Corresponding Author ©2014 Springer Science + Business Media, LLC & Science Press, China

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Accurate approximation of the earth mover's distance in linear time'. Together they form a unique fingerprint.

Cite this