用於計算地球移動器距離的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代碼/庫

回答

相關問題