The Earth Mover's Distance: Lower Bounds and Invariance Under Translation

作者: Scott Cohen , Leonidas Guibas

DOI: 10.21236/ADA358270

关键词:

摘要: The Earth Mover''s Distance (EMD) between two finite distributions of weight is proportional to the minimum amount work required transform one distribution into other. Current content-based retrieval in Stanford Vision Laboratory uses EMD as a common framework for measuring image similarity with respect color, texture, and shape content. In this report, we present some fast compute lower bounds on which may allow system avoid exact, more expensive computations during query processing. effectiveness tested color-based system. addition bound work, also show how under translation. problem, points are free translate, goal find translation that minimizes other distribution.

参考文章(11)
Marshall Bern, David Eppstein, Leonidas Guibas, John Hershberger, Subhash Suri, Jan Wolter, The Centroid of Points with Approximate Weights european symposium on algorithms. pp. 460- 472 ,(1995) , 10.1007/3-540-60313-1_163
Kenneth L. Clarkson, A bound on local minima of arrangements that implies the upper bound theorem Discrete & Computational Geometry. ,vol. 10, pp. 427- 433 ,(1993) , 10.1007/BF02573988
Zvi Drezner, A note on the Weber location problem Annals of Operations Research. ,vol. 40, pp. 153- 161 ,(1992) , 10.1007/BF02060474
Manabu Shirosaki, Another proof of the defect relation for moving targets Tohoku Mathematical Journal. ,vol. 43, pp. 355- 360 ,(1991) , 10.2748/TMJ/1178227459
R. Chandrasekaran, A. Tamir, Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem Mathematical Programming. ,vol. 44, pp. 293- 295 ,(1989) , 10.1007/BF01587094
I. Norman Katz, Local convergence in Fermat's problem Mathematical Programming. ,vol. 6, pp. 89- 104 ,(1974) , 10.1007/BF01580224
Harold W. Kuhn, A note on Fermat's problem Mathematical Programming. ,vol. 4, pp. 98- 107 ,(1973) , 10.1007/BF01584648
George O Wesolowsky, THE WEBER PROBLEM: HISTORY AND PERSPECTIVES. Computers & Operations Research. ,(1993)
Raimund Seidel, The upper bound theorem for polytopes: an easy proof of its asymptotic version Computational Geometry: Theory and Applications. ,vol. 5, pp. 115- 116 ,(1995) , 10.1016/0925-7721(95)00013-Y
Y. Rubner, C. Tomasi, L.J. Guibas, A metric for distributions with applications to image databases international conference on computer vision. pp. 59- 66 ,(1998) , 10.1109/ICCV.1998.710701