›› 2014, Vol. 29 ›› Issue (1): 142-154.doi: 10.1007/s11390-013-1417-2

Special Issue: Computer Graphics and Multimedia

• Computer Graphics and Multimedia • Previous Articles     Next Articles

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

Min-Hee Jang1, Sang-Wook Kim2, Member, ACM, IEEE, Christos Faloutsos1, Fellow, ACM, Member, IEEE and Sunju Park3   

  1. 1 Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, U.S.A.;
    2 Department of Electronics and Computer Engineering, Hanyang University, Seoul 133-071, Korea;
    3 School of Business, Yonsei University, Seoul 120-749, Korea
  • Received:2013-01-16 Revised:2013-10-28 Online:2014-01-05 Published:2014-01-05
  • Supported by:

    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.

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.

[1] Lang H, Wang B, Jones G et al. Query performance prediction for information retrieval based on covering topic score. Journal of Computer Science and Technology, 2008, 23(4): 590-601.

[2] Liu Y, Zhang D, Lu G et al. A survey of content-based image retrieval with high-level semantics. Pattern Recognition, 2007, 40(1): 262-282.

[3] Yan R, Hsu W. Recent developments in content-based and concept-based image/video retrieval. In Proc. ACM Int. Conf. Multimedia, Oct. 2008, pp.1155-1156.

[4] Schwartz W, Kembhavi A, Harwood D et al. Human detection using partial least squares analysis. In Proc. the 12th IEEE Int. Conf. Computer Vision, Sept. 29-Oct. 2, 2009, pp.24-31.

[5] Thang N, Rasheed T, Lee Y et al. Content-based facial image retrieval using constrained independent component analysis. Information Sciences, 2011, 181(15): 3162-3174.

[6] Ajorloo H, Lakdashti A. HBIR: Hypercube-based image retrieval. Journal of Computer Science and Technology, 2012, 27(1): 147-162.

[7] van de Weijer J, Schmid C. Coloring local feature extraction. In Proc. the 9th European Conference on Computer Vision, May 2006, pp.334-348.

[8] Rubner Y, Tomasi C, Guibas L. The earth mover's distance as a metric for image retrieval. International Journal of Computer Vision, 2000, 40(2): 99-121.

[9] Mojsilovic A, Hu J, Soljanin E. Extraction of perceptually important colors and similarity measurement for image matching, retrieval, and analysis. IEEE Transactions on Image Processing, 2002, 11(11): 1238-1248.

[10] Ciaccia P, Patella M, Zezula P. M-tree: An efficient access method for similarity search in metric spaces. In Proc. the 23rd Int. Conf. Very Large Data Bases, Aug. 1997, pp.426435.

[11] Moon B, Jagadish H, Faloutsos C et al. Analysis of the clustering properties of the Hilbert space-filling curve. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1): 124-141.

[12] Jagadish H. Analysis of the Hilbert curve for representing two-dimensional space. Information Processing Letters, 1997, 62(1): 17-22.

[13] Lawler E. Combinatorial Optimization: Networks and Matroids. New York: Courier Dover Publications, 1976.

[14] Rachev S. The Monge-Kantorovich mass transference problem and its stochastic applications. Theory of Probability and Its Applications, 1984, 29(4): 647-676.

[15] Ling H, Okada K. An efficient earth mover's distance algorithm for robust histogram comparison. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 29(5): 840-853.

[16] Shirdhonkar S, Jacobs D. Approximate earth mover's distance in linear time. In Proc. IEEE Int. Conf. Computer Vision and Pattern Recognition, June 2008.

[17] Ling H, Okada K. Diffusion distance for histogram comparison. In Proc. the IEEE Conf. Computer Vision and Pattern Recognition, June 2006, pp.246-253.

[18] Pele O, Werman M. Fast and robust earth mover's distances. In Proc. the 12th IEEE Conf. Computer Vision, Sept. 29Oct. 2, 2009, pp.460-467.

[19] Werman M, Peleg S, Melter R et al. Bipartite graph matching for points on a line or a circle. Journal of Algorithms, 1986, 7(2): 277-284.

[20] Werman M, Peleg S, Rosenfeld A. A distance metric for multidimensional histograms. Computer Vision, Graphics, and Image Processing, 1985, 32(3): 328-336.

[21] Wang J, Li J, Wiederholdy G. SIMPLIcity: Semanticssensitive integrated matching for picture libraries. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(9): 947-963.

[22] AutoDesk Maya Press. Learning Autodesk Maya 2009: The Special Effects Handbook. Wiley, 2008.

[23] Martnez J. MPEG-7 overview. http://mpeg.chiariglione.org/ standards/mpeg-7, Nov. 2013.

[24] Shepperd M, Schofield C. Estimating software project effort using analogies. IEEE Transactions on Software Engineering, 1997, 23(11): 736-743.

[25] Assent I, Wenning A, Seidl T. Approximation techniques for indexing the earth mover's distance in multimedia databases. In Proc. IEEE Int. Conf. Data Engineering, Apr. 2006.

[26] Wichterich M, Assent I, Kranen P et al. Efficient EMD-based similarity search in multimedia databases via 癳xible dimensionality reduction. In Proc. ACM SIGMOD Int. Conf. Management of Data, June 2008, pp.199-211.

[27] Xu J, Zhang Z, Tung A et al. Efficient and effective similarity search over probabilistic data based on earth mover's distance. Proc. of the VLDB Endowment, 2010, 3(1/2): 758-769.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved