A Linear Approximate Algorithm for Earth Mover's Distance with Thresholded Ground Distance
Joint Authors
Ma, Min
Wang, Xiaoping
Chen, Xiaoyun
Li, Longjie
Lei, Peng
Source
Mathematical Problems in Engineering
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-9, 9 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-03-09
Country of Publication
Egypt
No. of Pages
9
Main Subjects
Abstract EN
Effective and efficient image comparison plays a vital role in content-based image retrieval (CBIR).
The earth mover’s distance (EMD) is an enticing measure for image comparison, offering intuitive geometric interpretation and modelling the human perceptions of similarity.
Unfortunately, computing EMD, using the simplex method, has cubic complexity.
FastEMD, based on min-cost flow, reduces the complexity to (O(N2logN)).
Although both methods can obtain the optimal result, the high complexity prevents the application of EMD on large-scale image datasets.
Thresholding the ground distance can make EMD faster and more robust, since it can decrease the impact of noise and reduce the range of transportation.
In this paper, we present a new image distance metric, EMD+, which applies a threshold to the ground distance.
To compute EMD+, the FastEMD approach can be employed.
We also propose a novel linear approximation algorithm.
Our algorithm achieves ON complexity with the benefit of qualified bins.
Experimental results show that (1) our method is 2 to 3 orders of magnitude faster than EMD (computed by FastEMD) and 2 orders of magnitude faster than FastEMD and (2) the precision of our approximation algorithm is no less than the precision of FastEMD.
American Psychological Association (APA)
Li, Longjie& Ma, Min& Lei, Peng& Wang, Xiaoping& Chen, Xiaoyun. 2014. A Linear Approximate Algorithm for Earth Mover's Distance with Thresholded Ground Distance. Mathematical Problems in Engineering،Vol. 2014, no. 2014, pp.1-9.
https://search.emarefa.net/detail/BIM-469577
Modern Language Association (MLA)
Li, Longjie…[et al.]. A Linear Approximate Algorithm for Earth Mover's Distance with Thresholded Ground Distance. Mathematical Problems in Engineering No. 2014 (2014), pp.1-9.
https://search.emarefa.net/detail/BIM-469577
American Medical Association (AMA)
Li, Longjie& Ma, Min& Lei, Peng& Wang, Xiaoping& Chen, Xiaoyun. A Linear Approximate Algorithm for Earth Mover's Distance with Thresholded Ground Distance. Mathematical Problems in Engineering. 2014. Vol. 2014, no. 2014, pp.1-9.
https://search.emarefa.net/detail/BIM-469577
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-469577