Fast and Robust Earth Mover's Distances

被引：542

作者：

Pele, Ofir ^{[1
]}

Werman, Michael ^{[1
]}

机构：

[1] Hebrew Univ Jerusalem, IL-91905 Jerusalem, Israel

来源：

2009 IEEE 12TH INTERNATIONAL CONFERENCE ON COMPUTER VISION (ICCV) | 2009年

关键词：

D O I：

10.1109/ICCV.2009.5459199

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a new algorithm for a robust family of Earth Mover's Distances - EMDs with thresholded ground distances. The algorithm transforms the flow-network of the EMD so that the number of edges is reduced by an order of magnitude. As a result, we compute the EMD by an order of magnitude faster than the original algorithm, which makes it possible to compute the EMD on large histograms and databases. In addition, we show that EMDs with thresholded ground distances have many desirable properties. First, they correspond to the way humans perceive distances. Second, they are robust to outlier noise and quantization effects. Third, they are metrics. Finally, experimental results on image retrieval show that thresholding the ground distance of the EMD improves both accuracy and speed.

引用

页码：460 / 467

页数：8