计算推土机距离的Java代码/库

Question

我正在寻找计算 earth mover's distance (EMD) 的 Java 代码(或库)在两个直方图之间。这可以是直接的或间接的(例如使用匈牙利算法)。我在 c/c++ 中找到了这个的几个实现(例如 "Fast and Robust Earth Mover's Distances" ，但我想知道是否有现成的 Java 版本。

我将使用 EMD 计算来评估 this paper 给出的方法在我正在进行的科学项目的背景下。

更新

使用各种资源，我估计下面的代码应该可以解决问题。 determineMinCostAssignment 是由匈牙利算法确定的最佳分配的计算。为此，我将使用 http://konstantinosnedas.com/dev/soft/munkres.htm 中的代码我主要关心的是计算出的流量:我不确定这是否正确。有没有人可以验证这是正确的还是错误的？

    /**
 * Determines the Earth Mover's Distance between two histogram assuming an equal distance between two buckets of a histogram. The distance between
 * two buckets is equal to the differences in the indexes of the buckets.
 * 
 * @param threshold
 *          The maximum distance to use between two buckets.
 */
public static double determineEarthMoversDistance(double[] histogram1, double[] histogram2, int threshold) {
    if (histogram1.length != histogram2.length)
        throw new InvalidParameterException("Each histogram must have the same number of elements");

    double[][] groundDistances = new double[histogram1.length][histogram2.length];
    for (int i = 0; i < histogram1.length; ++i) {
        for (int j = 0; j < histogram2.length; ++j) {
            int abs_diff = Math.abs(i - j);
            groundDistances[i][j] = Math.min(abs_diff, threshold);
        }
    }

    int[][] assignment = determineMinCostAssignment(groundDistances);
    double costSum = 0, flowSum = 0;
    for (int i = 0; i < assignment.length; i++) {
        double cost = groundDistances[assignment[i][0]][assignment[i][1]];
        double flow = histogram2[assignment[i][1]];
        costSum += cost * flow;
        flowSum += flow;
    }
    return costSum / flowSum;
}

Answer 1

这是我刚刚发布的 FastEMD 算法的纯 Java 端口: https://github.com/telmomenezes/JFastEMD