Back to Search
Start Over
METRIC-PRESERVING REDUCTION OF EARTH MOVER'S DISTANCE.
- Source :
- Asia-Pacific Journal of Operational Research; Feb2010, Vol. 27 Issue 1, p39-54, 16p
- Publication Year :
- 2010
-
Abstract
- Earth mover's distance (EMD for short) is a perceptually meaningful dissimilarity measure between histograms. The computation of EMD reduces to a network flow optimization problem; however, it lays a heavy computational burden when the number of locations of histograms is large. In this paper, we address an efficient formulation for computing the exact EMD value. We prove that the EMD problem reduces to a problem with half the number of constraints regardless of the ground distance. We then propose a further reduced formula in which the number of variables is reduced from O(m<superscript>2</superscript>) to O(m) for histograms with m locations when the ground distance is derived from a graph with a homogeneous neighborhood structure. Specifically, EMD problems with L<subscript>1</subscript>, L<subscript>∞</subscript>and D-norm ground distances can be reduced in this manner. Some experiments show that the reduction helps compute the EMD efficiently. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02175959
- Volume :
- 27
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Asia-Pacific Journal of Operational Research
- Publication Type :
- Academic Journal
- Accession number :
- 50463114
- Full Text :
- https://doi.org/10.1142/S0217595910002545