用于计算地球移动器距离的Java代码/库

我正在查找计算两个直方图之间earth mover's distance (EMD)的java代码（或库）。这可能是直接或间接的（例如使用匈牙利算法）。我在c/C++中发现了几个这样的实现（例如"Fast and Robust Earth Mover's Distances"，但是我想知道是否有Java版本可用）用于计算地球移动器距离的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; 
}

来源

2012-01-15 Erik

最佳的运输成本明显具有线性约束的线性问题。任何线性优化库（内部点方法都能很好地工作）会做（顺便说一句，匈牙利算法在这里做什么？你不是在寻找整数解）。其他要搜索的关键字是“Monge-Kantorovich distance”，“Wasserstein distance”或“Optimal transportation”。还有一些基于凸优化的算法（您可以直接找到双Kantorovich问题的凸共轭对phi，phi^*;最适合连续空间）。 – 2012-03-30 12:23:38

这里的FastEMD算法的一个纯Java端口，我刚刚发布： https://github.com/telmomenezes/JFastEMD

来源

2012-03-30 12:16:20 telmomenezes

太棒了！而且正好及时，因为我只是准备分发给其他人来验证结果 – Erik 2012-04-15 17:25:30

一个简单的谷歌搜索匈牙利算法的java翻了几个环节，包括this link和this one。

来源

2012-01-15 21:11:49

我确实发现了这些，但是我不完全清楚匈牙利算法的输入应该是什么。很明显，NxN矩阵的行数和列数符合直方图中的桶数，但这不能解释单元格内容。如果这是桶之间的距离（即单元（1,3）应该包含| 1-3 | = 2）？ – Erik 2012-01-15 21:39:58

网站"Fast and Robust Earth Mover's Distances"有一个C/C++代码的Java包装器，它为Linux和Windows编译的二进制文件。

来源

2012-03-15 19:32:38 Maya

我知道（我自己添加了编译好的windows二进制文件），但我仍然希望有一个完整的java版本可用。这将使我能够将完整的实验代码转移给其他人，并给出一点解释。 – Erik 2012-03-16 22:36:01

https://github.com/wihoho/VideoRecognition

适应作者的C implementation用Python模块通过一个文件界面
的经修饰的C-码位于文件夹EarthMoverDistance SourceCode

我很确定你可以用Java做同样的事情。只需添加一个文件接口即可将EMD的C实现与Java代码连接起来。

来源

2013-12-10 09:30:38 wihoho

这是我使用的Java /斯卡拉：

import org.apache.commons.math3.ml.distance.EarthMoversDistance 
new EarthMoversDistance().compute(observed, expected)

来源

2016-08-30 14:04:23 isilpekel

用于计算地球移动器距离的Java代码/库

回答

相关问题