Earth Mover’s Distance (EMD)

2024-01-01 09:32
文章标签 distance emd earth mover

本文主要是介绍Earth Mover’s Distance (EMD)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文将讨论Earth Mover’s Distance (EMD)，和欧式距离一样，它们都是一种距离度量的定义、可以用来测量某两个分布之间的距离。EMD主要应用在图像处理和语音信号处理领域，在自然语言处理上很少有听说。
EMD 问题如下图所示
<ignore_js_op> id="iframe_0.7310089599341154" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/data/attachment/forum/201306/19/195258w27y3a7wwa74wwa3.jpg?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.7310089599341154',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0"> 

<ignore_js_op> id="iframe_0.07185405353084207" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/data/attachment/forum/201306/19/195819u0cnpy0ei353nkzr.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.07185405353084207',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0"> 
不同情况下EMD使用方式也不一样，但还是有一些共通之处。比如权重都是指特征量的重要程度。例如，一个直方图对应一个签名的情况下，直方图中的每一根柱(bar)代表一个特征量，柱的高度就对应其权重。在之前的相似图像检索 (2009/10/3）一文中，我使用到了图像颜色分布直方图相交距离(Histogram Intersection )，也可以用在EMD中当作ground distance使用。最早提出EMD概念的论文中有提到，EMD最初就是用来做相似图片检索的。
运输问题概述
<ignore_js_op> id="iframe_0.7222093800082803" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/data/attachment/forum/201306/19/200025r8s77o2wums9dzdm.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.7222093800082803',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0"> 
<ignore_js_op> id="iframe_0.2584721043240279" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/data/attachment/forum/201306/19/200038aquylykggduk6g1y.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.2584721043240279',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0"> 
很自然可以想到，给定两个签名，把一个变成另一个所需要的最小工作量，就是EMD对距离的定义，这里的「工作量」要基于用户对ground distance的定义，即特征量之间的距离的定义。然而，当特征量非常多的时候，由于要做一一匹配，其计算量是非常大的。因此，有人提出了一种将多个特征量组合起来做向量量化编码(Vector Quantization)后再组成签名的方法。
EMD的一些优点可见这里
举个栗子 <ignore_js_op> id="iframe_0.388046451844275" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/data/attachment/forum/201306/19/200447wrrpr990ru5jw552.jpg?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.388046451844275',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0"> 

<ignore_js_op> id="iframe_0.5452677409630269" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/data/attachment/forum/201306/19/200226ekt2c53t00j6mr0c.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.5452677409630269',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0"> 
Rubner的C语言实现首先我们尝试使用Rubner桑公开的C语言代码(example1.c)，编译依赖emd.c和emd.h。其中特征量类型feature_t在emd.h中定义如下：
typedef struct { int X,Y,Z; } feature_t;具体实现代码见emd.c。对于上述例子的解答如下：

普通浏览复制代码
  1. id="iframe_0.10071098245680332" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.10071098245680332',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0"># include <stdio.h>
  2. id="iframe_0.9153952854685485" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.9153952854685485',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0"># include <math.h>
  3. id="iframe_0.5096627038437873" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.5096627038437873',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0"># include "emd.h"
  4. id="iframe_0.40024990937672555" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.40024990937672555',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">
  5. id="iframe_0.432026332244277" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.432026332244277',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">/* 欧几里得距离 */
  6. id="iframe_0.46847684402018785" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_shrink.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.46847684402018785',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">float dist(feature_t *F1, feature_t *F2) {
  7. id="iframe_0.7292746563907713" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.7292746563907713',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    int dX = F1->X - F2->X;
  8. id="iframe_0.7462860192172229" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.7462860192172229',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    int dY = F1->Y - F2->Y;
  9. id="iframe_0.5723320455290377" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.5723320455290377',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    int dZ = F1->Z - F2->Z;
  10. id="iframe_0.25498996023088694" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.25498996023088694',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    return sqrt(dXdX + dY*dY + dZ*dZ);
  11. id="iframe_0.6203882237896323" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.6203882237896323',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">}
  12. id="iframe_0.46001951629295945" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.46001951629295945',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">
  13. id="iframe_0.09172290447168052" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_shrink.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.09172290447168052',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">int main() {
  14. id="iframe_0.8486427136231214" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.8486427136231214',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">
  15. id="iframe_0.8748402525670826" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.8748402525670826',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    /* 分布P的特征矢量 */
  16. id="iframe_0.45718725910410285" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.45718725910410285',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    feature_t f1[4] = { {100,40,22}, {211,20,2}, {32,190,150}, {2,100,100} };
  17. id="iframe_0.2652773552108556" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.2652773552108556',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    /*分布Q的特征矢量 */
  18. id="iframe_0.016863980796188116" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.016863980796188116',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    feature_t f2[3] = { {0,0,0}, {50,100,80}, {255,255,255} };
  19. id="iframe_0.07613023440353572" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.07613023440353572',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    /*分布P的权重 */
  20. id="iframe_0.5582009658683091" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.5582009658683091',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    float w1[5] = { 0.4, 0.3, 0.2, 0.1 };
  21. id="iframe_0.31324169621802866" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.31324169621802866',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    /*分布Q的权重 */
  22. id="iframe_0.7341312814969569" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.7341312814969569',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    float w2[3] = { 0.5, 0.3, 0.2 };
  23. id="iframe_0.46556183020584285" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.46556183020584285',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    /*分布P的签名 */
  24. id="iframe_0.26522848615422845" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.26522848615422845',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    signature_t s1 = { 4, f1, w1 };
  25. id="iframe_0.1938192155212164" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.1938192155212164',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    /*分布Q的签名 */
  26. id="iframe_0.5959899798035622" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.5959899798035622',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    signature_t s2 = { 3, f2, w2};
  27. id="iframe_0.5327454374637455" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.5327454374637455',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    /* 计算EMD */ 
  28. id="iframe_0.5628343552816659" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.5628343552816659',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    float e; 
  29. id="iframe_0.7989976138342172" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.7989976138342172',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    e = emd(&s1, &s2, dist, 0, 0); 
  30. id="iframe_0.05220225919038057" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.05220225919038057',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">    printf("emd = %f\n", e); return 0; 
  31. id="iframe_0.3915507940109819" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.3915507940109819',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">
  32. id="iframe_0.4900689253117889" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/source/plugin/imc_colorcode/images/jssc_none.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.4900689253117889',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0">}



<ignore_js_op> id="iframe_0.007229788461700082" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://www.sigvc.org/bbs/data/attachment/forum/201306/19/200349a45arnt5ktcmg7rn.gif?_=3314667%22%20style=%22border:none;max-width:796px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.007229788461700082',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" scrolling="no" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 796px;" frameborder="0"> 
结束语本文对与EMD的讨论力求准确，但是错误难免，敬请批评指正，同时请参考其他文献。
参考文献

  • Earth mover’s distance - Wikipedia link
  • Y. Rubner, C. Tomasi and L. J. Guibas: The earth mover’s distance as a metric for image retrieval (PDF), International Journal of Computer Vision, 40(2), pp.99-121, 2000 - EMDの原論文。EMDを類似画像検索に適用しています。
  • Code for the Earth Movers Distance (EMD) - Rubnerさんが公開されているC言語実装 link
  • Fast Earth Mover’s Distance (EMD) Code - EMDを高速計算する実装 link
  • 柳本, 大松: Earth Mover’s Distanceを用いたテキスト分類、人工知能学会全国大会, 2007. - EMDの説明がわかりやすい。画像や音声の手法がテキストにも使えるんですね。
  • lpSolve - R言語のlpSolveのマニュアル。lp.transform()の詳しい仕様はここで。
  • Formal definition of EMD

this article is mainly based on the original text written by sylvan5 on aidiary.some additional contents are added by mckelvin.
本文主要基于sylvan5发表在aidiary的原文，在此基础上增加了一些内容。

这篇关于Earth Mover’s Distance (EMD)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/558834。

相关文章

Google Earth Engine——高程数据入门和山体阴影和坡度的使用

Google Earth Engine——高程数据入门和山体阴影和坡度的使用

目录 山体阴影和坡度 对图像应用计算 应用空间减速器 高程数据 通过从“重置”按钮下拉菜单中选择“清除脚本”来清除脚本。搜索“elevation”并单击 SRTM Digital Elevation Data 30m 结果以显示数据集描述。单击导入，将变量移动到脚本顶部的导入部分。将默认变量名称“image”重命名为“srtm”。使用脚本将图像对象添加到地图： Map
阅读更多...
[LeetCode] 863. All Nodes Distance K in Binary Tree

[LeetCode] 863. All Nodes Distance K in Binary Tree

题：https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/ 题目大意 求给树中，距给定 结点 指定长度的 所有结点的val 思路 tree -> graph 、 bfs 先遍历树，并用map记录每个结点的父结点 ，将树变为图，然后 bfs。 /*** Definition for a binary tree
阅读更多...
Google Earth Engine——导入无云 Sentinel-2 图像和NDVI计算

Google Earth Engine——导入无云 Sentinel-2 图像和NDVI计算

目录 搜索和导入无云 Sentinel-2 图像 Sentinel-2 的背景 打开 GEE 界面 定义您感兴趣的领域 查询 Sentinel-2 图像的存档 过滤图像集合 将图像添加到地图视图 定义真彩色可视化参数 探索影像 定义假色可视化参数 从波段组合中导出指数 NDVI 锻炼 本实验的目的是介绍 Google Earth Engine 处理环境。在本练习
阅读更多...
【HDU】5102 The K-th Distance bfs

【HDU】5102 The K-th Distance bfs

传送门：【HDU】5102 The K-th Distance 题目分析：思路秒出，5101写完不到20分钟这题就AC了。。将所有点扔进队列中，记录前驱，步数，每次扩展的时候不走前驱，这样就相当于n棵树同时在扩展。注意到一条路径会被重复走两次，所以k*2，ans/2。注意姿势不对就会MLE。 代码如下： #include <map>#include <vector>
阅读更多...
【codechef】 Prime Distance On Tree【求树上路经长度为i的路径条数】【点分治+FFT】

【codechef】 Prime Distance On Tree【求树上路经长度为i的路径条数】【点分治+FFT】

传送门：【codechef】 Prime Distance On Tree 点分治+FFT水题……竟然n*n爆int没发现…… 而且NTT TLE，FFT跑的超级快…… my  code: my~~code: #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) m
阅读更多...
Shortest Distance to a Character

Shortest Distance to a Character

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string. Example 1: Input: S = "loveleetcode", C = 'e'Output: [3, 2, 1,
阅读更多...
Goolge earth studio 高阶4——缓动与其他技术结合使用

Goolge earth studio 高阶4——缓动与其他技术结合使用

缓动只是 Goolge Earth Studio 中众多工具之一。将缓动与其他技术（如相机路径、关键帧插值和多相机角度）结合使用，可以创造出真正动态和吸引人的动画。 1、下面的动画中，我们设置关键帧，仅仅对关键帧处的相机位置属性进行更改，在一开始，相机的位置升高一点，移动到最后一帧，视角降低一点，预览一下动画； Animations_clip_12 2、如果还想调整一下动画，可以点击
阅读更多...
QT+OSG+osg-earth显示一个球

QT+OSG+osg-earth显示一个球

目录 1、环境配置 2、在QT  Creator导入相关的库 3、代码部分 4、运行过程中的问题 5、相关参考 重要衔接：QT+OSG显示一个三维模型-CSDN博客 1、环境配置  系统：windows10系统 QT:版本5.15.2        编译器：MSVC2019_64bit        编辑器：QT  Creator OSG版本：3.7.0   64位
阅读更多...
Opencv中的直方图(5)计算EMD距离的函数EMD()的使用

Opencv中的直方图(5)计算EMD距离的函数EMD()的使用

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C++11 算法描述 计算两个加权点配置之间的“最小工作量”距离。 该函数计算地球搬运工距离（Earth Mover’s Distance）和/或两个加权点配置之间距离的下界。其中一个应用如文献 225和 226中所述，是在图像检索中进行多维直方图比较。EMD 是
阅读更多...
Goolge earth studio 高阶2——缓动简单应用

Goolge earth studio 高阶2——缓动简单应用

应用缓动，需要打开图形编辑器。图形编辑器通过调整关键帧的曲线，让我们控制动画的速度。 1、选择关键帧，单击，将出现一个包含速度更改选项的列表，包括“Auto Ease自动缓变”、“Ease in缓入”，“Ease out缓出”、“Linear线性”、“step分布”，其中线性为默认选项，“Ease in缓入”一般在进入某一关键帧时使用，“Ease out缓出”一般在离开某关键帧时使用；“Auto
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2