Abstract
The Earth Mover’s Distance (EMD) on weighted point sets is a distance measure with many applications. Since there are no known exact algorithms to compute the minimum EMD under transformations, it is useful to estimate the minimum EMD under various classes of transformations. For weighted point sets in the plane, we will show a 2-approximation algorithm for translations, a 4-approximation algorithm for rigid motions and an 8-approximation algorithm for similarity transformations. The runtime for translations is O(T EMD(n,m)), the runtime of the latter two algorithms is O(nmT EMD(n,m)), where T EMD(n,m) is the time to compute the EMD between two fixed weighted point sets with n and m points, respectively. All these algorithms are based on a more general structure, namely on reference points. This leads to elegant generalizations to higher dimensions. We give a comprehensive discussion of reference points for weighted point sets with respect to the EMD.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alt, H., Aichholzer, O., Rote, G.: Matching Shapes with a Reference Point. In: Proc. 10th Annual Symposium on Computational Geometry, pp. 85–92 (1994)
Alt, H., Behrends, B., Blömer, J.: Approximate Matching of Polygonal Shapes. In: Proc. 7th Ann. Symp. on Comp. Geometry, pp. 186–193 (1991)
Alt, H., Fuchs, U., Rote, G., Weber, G.: Matching Convex Shapes with Respect to the Symmetric Difference. In: Díaz, J. (ed.) ESA 1996. LNCS, vol. 1136, pp. 320–333. Springer, Heidelberg (1996)
Cabello, S., Giannopoulos, P., Knauer, C., Rote, G.: Matching Point Sets with respect to the Earth Mover’s Distance. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 520–531. Springer, Heidelberg (2005)
Cohen, S.: Finding Color and Shape Patterns in Images. PhD thesis, Stanford University, Department of Compute Science (1999)
Giannopoulos, P., Veltkamp, R.: A pseudo-metric for weighted point sets. In: Heyden, A., Sparr, G., Nielsen, M., Johansen, P. (eds.) ECCV 2002. LNCS, vol. 2352, pp. 715–730. Springer, Heidelberg (2002)
Graumann, K., Darell, T.: Fast contour matching using approximate Earth Mover’s Distance. In: ECCV 2002. LNCS, vol. 2352, pp. I: 220–227 (2004)
Klein, O., Veltkamp, R.C.: Approximation Algorithms for the Earth Mover’s Distance Under Transformations Using Reference Points. Technical Report UU-CS- 2005-003 (2005), http://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-2005/2005-003.pdf
Orlin, J.B.: A Faster Strongly Polynomial Minimum Cost Flow Algorithm. Operations Research 41(2), 338–350 (1993)
Rubner, Y., Tomasi, C., Guibas, L.J.: The Earth Mover’s Distance as a Metric for Image Retrieval. Int. J. of Comp. Vision 40(2), 99–121 (2000)
Typke, R., Giannopoulos, P., Veltkamp, R.C., Wierking, F., Oostrum, R.: Using transportation distances for measuring melodic similarity. In: Proc. of the 4th Int. Conf. Music Inf. Retrieval, pp. 107–114 (2003)
Weber, G.: The Centroid is a Reference Point for the Symmetric Difference in d Dimensions. Tech. Rep. UoA-SE-2004-1, The University of Auckland (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Klein, O., Veltkamp, R.C. (2005). Approximation Algorithms for Computing the Earth Mover’s Distance Under Transformations. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_101
Download citation
DOI: https://doi.org/10.1007/11602613_101
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30935-2
Online ISBN: 978-3-540-32426-3
eBook Packages: Computer ScienceComputer Science (R0)