Class emd_hat

java.lang.Object
  extended by emd_hat

public class emd_hat
extends java.lang.Object

A class that provides efficient emd_hat functions. emd_hat was described in the paper:
A Linear Time Histogram Metric for Improved SIFT Matching
Ofir Pele, Michael Werman
ECCV 2008
The efficient algorithm is described in the paper:
Fast and Robust Earth Mover's Distances
Ofir Pele, Michael Werman
ICCV 2009


Constructor Summary
emd_hat()
           
 
Method Summary
static double dist_gd_metric(double[] P, double[] Q, double[][] C, double extra_mass_penalty, double[][] F)
          Fastest version of EMD.
static double dist(double[] P, double[] Q, double[][] C, double extra_mass_penalty, double[][] F)
          Same as dist_gd_metric, but does not assume metric property for the ground distance (C).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

emd_hat

public emd_hat()
Method Detail

dist_gd_metric

public static double dist_gd_metric(double[] P,
                                    double[] Q,
                                    double[][] C,
                                    double extra_mass_penalty,
                                    double[][] F)
Fastest version of EMD. Also, in my experience metric ground distance yields better performance.

Parameters:
P - a histogram of size N
Q - a histogram of size N
C - The NxN matrix of the ground distance between bins of P and Q. Must be a metric. I recommend it to be a thresholded metric (which is also a metric, see ICCV paper).
extra_mass_penalty - The penalty for extra mass - If you want the resulting distance to be a metric, it should be at least half the diameter of the space (maximum possible distance between any two points). If you want partial matching you can set it to zero (but then the resulting distance is not guaranteed to be a metric). Default value is -1 which means 1*max_element_in_C
F - if not null, F is filled with the flows between all bins, except the flow to the extra mass bin. Note that EMD and EMD-HAT does not necessarily have a unique flow solution.
Returns:
the distance
See Also:
"demo_FastEMD.java ../emd_hat.hpp ../demo_FastEMD#.m"

dist

public static double dist(double[] P,
                          double[] Q,
                          double[][] C,
                          double extra_mass_penalty,
                          double[][] F)
Same as dist_gd_metric, but does not assume metric property for the ground distance (C). Note that C should still be symmetric and non-negative!

See Also:
dist_gd_metric(double[], double[], double[][], double, double[][])