Schnelle und robuste Earth Mover's Distances

Wir präsentieren einen neuen Algorithmus für eine robuste Familie von Earth Mover's Distances - EMDs mit gewichteten Bodendistanzen. Der Algorithmus transformiert das Flussnetzwerk des EMD, sodass die Anzahl der Kanten um eine Größenordnung reduziert wird. Infolgedessen berechnen wir den EMD um das Zehnfache schneller als der ursprüngliche Algorithmus, was es ermöglicht, den EMD auf großen Historgrammen und Datenbanken zu berechnen. Darüber hinaus zeigen wir, dass EMDs mit gewichteten Bodendistanzen viele wünschenswerte Eigenschaften haben. Erstens entsprechen sie der Art und Weise, wie Menschen Distanzen wahrnehmen. Zweitens sind sie robust gegenüber Ausreißerrauschen und Quantisierungswirkungen. Drittens sind sie metrisch. Schließlich zeigen experimentelle Ergebnisse zur Bildrückführung, dass die Gewichtung der Bodendistanz des EMD sowohl die Genauigkeit als auch die Geschwindigkeit verbessert.