Earth Mover's Distance in Java
Java
Switch branches/tags
Nothing to show
Latest commit 752a364 Mar 30, 2012 @telmomenezes telmomenezes working on README.md
Permalink
Failed to load latest commit information.
src/com/telmomenezes/jfastemd making code pretier Mar 30, 2012
.classpath adding eclipse project Mar 30, 2012
.project adding eclipse project Mar 30, 2012
LICENSE.txt updating license Mar 30, 2012
README.md working on README.md Mar 30, 2012

README.md

JFastEMD

This is a pure Java implementation of the Fast Earth Mover's Algorithm by Ofir Pele and Michael Werman. In fact, it's a partial port of the C++ implementation that can be found here:

http://www.cs.huji.ac.il/~ofirpele/FastEMD/code/

Please cite these papers if you use this code:

A Linear Time Histogram Metric for Improved SIFT Matching
Ofir Pele, Michael Werman
ECCV 2008
bibTex:
@INPROCEEDINGS{Pele-eccv2008,
author = {Ofir Pele and Michael Werman},
title = {A Linear Time Histogram Metric for Improved SIFT Matching},
booktitle = {ECCV},
year = {2008}
}
Fast and Robust Earth Mover's Distances
Ofir Pele, Michael Werman
ICCV 2009
@INPROCEEDINGS{Pele-iccv2009,
author = {Ofir Pele and Michael Werman},
title = {Fast and Robust Earth Mover's Distances},
booktitle = {ICCV},
year = {2009}
}

Install

JFastEMD is meant to be easily incorporated into your project by copying the following files:

  • JFastEMD.java
  • Signature.java
  • Feature.java
  • Aux.java

How to use

The main entry point is the static method JFastEMD.distance with the following signature:

double distance(Signature signature1, Signature signature2, double extraMassPenalty)
  • signature1 and signature2: the sparse matrices being compared - more details ahead
  • extraMassPenalty: penalty for extra mass. 0 for no penalty, -1 for the default, other positive values to specify the penalty

An extraMassPenalty of -1 means that the extra mass penalty is the maximum distance found between two features.

Signatures can be used to represent sparse n-dimensional matrices. They are a collection of features and their respective weights. Feature is an interface that you must implement for your specific application.

Test.java and Feature2D.java provide a usage example, where we compute EMD distances between two-dimensional matrices using Cartesian distances.

public class Feature2D implements Feature {
	private double x;
	private double y;

	public Feature2D(double x, double y) {
		this.x = x;
		this.y = y;
	}

	public double groundDist(Feature f) {
		Feature2D f2d = (Feature2D)f;
		double deltaX = x - f2d.x;
		double deltaY = y - f2d.y;
		return Math.sqrt((deltaX * deltaX) + (deltaY * deltaY));
	}
}

The two-dimensional matrices can be converted to signature like so:

static Signature getSignature(double[] map, int bins) {

	// find number of entries in the sparse matrix
	int n = 0;
	for (int x = 0; x < bins; x++) {
		for (int y = 0; y < bins; y++) {
			if (getValue(map, x, y, bins) > 0) {
				n++;
			}
		}
	}
	
	// compute features and weights
	Feature2D[] features = new Feature2D[n];
	double[] weights = new double[n];
	int i = 0;
	for (int x = 0; x < bins; x++) {
		for (int y = 0; y < bins; y++) {
			double val = getValue(map, x, y, bins);
			if (val > 0) {
				Feature2D f = new Feature2D(x, y);
				features[i] = f;
				weights[i] = val;
				i++;
			}
		}
	}

	Signature signature = new Signature();
	signature.setNumberOfFeatures(n);
	signature.setFeatures(features);
	signature.setWeights(weights);

	return signature;
}

License

This code is released under the BSD license.