-
Notifications
You must be signed in to change notification settings - Fork 0
/
earth-movers-distance.html
217 lines (210 loc) · 11.5 KB
/
earth-movers-distance.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Visual Analysis of the Earth Mover's Distance — A Place for Asides</title>
<meta name="description" content="Title: Visual Analysis of the Earth Mover's Distance; Date: 2019-05-14; Author: Peter Mortimer">
<meta name="author" content="Peter">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<!-- Le HTML5 shim, for IE6-8 support of HTML elements -->
<!--[if lt IE 9]>
<script src="http://tonyromarock.github.io/theme/html5.js"></script>
<![endif]-->
<link href="http://tonyromarock.github.io/theme/css/ipython.css" rel="stylesheet">
<link href="http://tonyromarock.github.io/theme/css/jquery.tocify.css" rel="stylesheet">
<link href="//maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap.min.css" rel="stylesheet">
<link href="//maxcdn.bootstrapcdn.com/font-awesome/4.1.0/css/font-awesome.min.css" rel="stylesheet">
<!--
<link href="https://stackpath.bootstrapcdn.com/bootswatch/4.3.1/minty/bootstrap.min.css" rel="stylesheet">
-->
<link href="http://tonyromarock.github.io/theme/css/local.css" rel="stylesheet">
<link href="http://tonyromarock.github.io/theme/css/pygments.css" rel="stylesheet">
</head>
<body>
<div id="toc"></div><div class="container">
<div class="page-header">
<div class="row">
<div class="col-8 col-sm-8">
<h1><a href="http://tonyromarock.github.io/">A Place for Asides</a>
<br> </div>
<div class="col-4 col-sm-4 page-header-links">
<p><a href="/pages/about.html">About</a> | <a href="/pages/previous-projects.html">Previous Projects</a> | <a href="/">Blog</a> | <a href="/pages/books.html">Books I've read</a> </p>
</div>
</div>
</div>
<div class="row">
<div class="col-md-8 col-md-offset-2">
<div class="article" itemscope itemtype="http://schema.org/BlogPosting">
<div class="text-center article-header">
<h1 itemprop="name headline" class="article-title">Visual Analysis of the Earth Mover's Distance</h1>
<span itemprop="author" itemscope itemtype="http://schema.org/Person">
<h4 itemprop="name">Peter Mortimer</h4>
</span>
<time datetime="2019-05-14T10:30:00+02:00" itemprop="datePublished">May 14 2019</time>
</div>
<div itemprop="articleBody" class="article-body"><h1 style="visibility:hidden;">Visual Analysis of the Earth Mover's Distance</h1>
<p>Many recent research papers [<a href="#pcn">1</a>,<a href="#pointoutnet">2</a>] focused on neural networks for 3D point cloud data use one of the two distance metrics as loss function or evaluation metric: the Chamfer distance (<span class="math">\(D_{CD}\)</span>) and the Earth Mover's distance (<span class="math">\(D_{EMD}\)</span>). The calculation of the Chamfer distance is easy to grasp, while the Earth Mover's distance is less clearly defined. In this post I want to give an overview of the Earth Mover's distance and in particular how it is used for training point cloud data. The Earth Mover's distance is also known under the term 1-Wasserstein metric, but we will refer to it as the Earth Mover's distance in this post.</p>
<h3>Introduction</h3>
<p>Let's first look at the mathematical definition of the Earth Mover's distance:</p>
<div class="math">$$ D_{EMD}(S_{1},S_{2}) = \min_{\phi: S_{1} \to S_{2} } \frac{1}{|S_{1}|} \sum_{x \in S_{1}} \| x - \phi(x) \|_{2}$$</div>
<p>The function <span class="math">\(\phi\)</span> is a bijection (this also implies that <span class="math">\(D_{EMD}\)</span> is only defined for <span class="math">\(|S_{1}| = |S_{2}|\)</span>). This can be seen as a matching between points in <span class="math">\(S_{1}\)</span> to points in <span class="math">\(S_{2}\)</span>. The matching with the minimal euclidean distance therefore describes the Earth Mover's distance.
A common interpretation of the Earth Mover's distance describes the measure as the minimum amount of work needed to spread a mass of earth collected in piles to fill a set of holes in the same given space [<a href="#cvonline_emd">4</a>,<a href="#translocation">5</a>]. In this interpretation work is determined both by the weight of the earth moved and the distance that the earth had to be moved to fill the holes.</p>
<h3>References</h3>
<p><span id='pcn'>[1] Yuan, Khot, Held, Mertz, Herbert (3DV 2018) <a href="https://www.cs.cmu.edu/~wyuan1/pcn/">PCN: Point Completion Network</a></span></p>
<p><span id='pointoutnet'>[2] Fan, Su, Leonidas (CVPR 2017) <a href="https://arxiv.org/abs/1612.00603">A Point Set Generation Network for 3D Object Reconstruction from a Single Image</a></span></p>
<p><span id='swd'>[3] Lee, Batra, Baig, Ulbricht (CVPR 2019) <a href="https://arxiv.org/abs/1903.04064">Sliced Wasserstein Discrepancy for Unsupervised Domain Adaptation.</a></span></p>
<p><span id='cvonline_emd'>[4] CVOnline on the Earth Mover's Distance <a href="http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/RUBNER/emd.htm">The Earth Mover's Distance</a></span></p>
<p><span id='translocation'>[5] Kantorovitch, Lee (Management Science 1958) <a href="https://web.eecs.umich.edu/~pettie/matching/Kantorovitch-translocation-of-masses-1942.pdf">On the Translocation of Masses</a></span></p>
<script type="text/javascript">if (!document.getElementById('mathjaxscript_pelican_#%@#$@#')) {
var align = "center",
indent = "0em",
linebreak = "false";
if (false) {
align = (screen.width < 768) ? "left" : align;
indent = (screen.width < 768) ? "0em" : indent;
linebreak = (screen.width < 768) ? 'true' : linebreak;
}
var mathjaxscript = document.createElement('script');
mathjaxscript.id = 'mathjaxscript_pelican_#%@#$@#';
mathjaxscript.type = 'text/javascript';
mathjaxscript.src = 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML';
var configscript = document.createElement('script');
configscript.type = 'text/x-mathjax-config';
configscript[(window.opera ? "innerHTML" : "text")] =
"MathJax.Hub.Config({" +
" config: ['MMLorHTML.js']," +
" TeX: { extensions: ['AMSmath.js','AMSsymbols.js','noErrors.js','noUndefined.js'], equationNumbers: { autoNumber: 'none' } }," +
" jax: ['input/TeX','input/MathML','output/HTML-CSS']," +
" extensions: ['tex2jax.js','mml2jax.js','MathMenu.js','MathZoom.js']," +
" displayAlign: '"+ align +"'," +
" displayIndent: '"+ indent +"'," +
" showMathMenu: true," +
" messageStyle: 'normal'," +
" tex2jax: { " +
" inlineMath: [ ['\\\\(','\\\\)'] ], " +
" displayMath: [ ['$$','$$'] ]," +
" processEscapes: true," +
" preview: 'TeX'," +
" }, " +
" 'HTML-CSS': { " +
" fonts: [['STIX', 'TeX']]," +
" styles: { '.MathJax_Display, .MathJax .mo, .MathJax .mi, .MathJax .mn': {color: 'inherit ! important'} }," +
" linebreaks: { automatic: "+ linebreak +", width: '90% container' }," +
" }, " +
"}); " +
"if ('default' !== 'default') {" +
"MathJax.Hub.Register.StartupHook('HTML-CSS Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax['HTML-CSS'].FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"MathJax.Hub.Register.StartupHook('SVG Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax.SVG.FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"}";
(document.body || document.getElementsByTagName('head')[0]).appendChild(configscript);
(document.body || document.getElementsByTagName('head')[0]).appendChild(mathjaxscript);
}
</script></div>
<hr>
<div>
Category:
<span itemprop="articleSection">
<a href="http://tonyromarock.github.io/category/python.html" rel="category">Python</a>
</span>
</div>
<div>
Tags:
<span itemprop="keywords">
<a href="http://tonyromarock.github.io/tag/earth-movers-distance.html" rel="tag">Earth Mover's Distance</a>
</span>
<span itemprop="keywords">
<a href="http://tonyromarock.github.io/tag/point-clouds.html" rel="tag">Point Clouds</a>
</span>
<span itemprop="keywords">
<a href="http://tonyromarock.github.io/tag/3d-machine-learning.html" rel="tag">3D Machine Learning</a>
</span>
</div>
</div>
</div>
</div> <!-- <hr> -->
</div> <!-- /container -->
<footer class="aw-footer bg-danger">
<div class="container"> <!-- footer -->
<div class="row">
<div class="col-md-10 col-md-offset-1">
<div class="row">
<div class="col-md-3">
<h4>Navigation</h4>
<ul class="list-unstyled my-list-style">
<li><a href="http://tonyromarock.github.io">A Place for Asides</a></li>
<li><a href="http://tonyromarock.github.io/pages/about.html"><i class="fa fa-About "></i> About</a></li>
<li><a href="http://tonyromarock.github.io/pages/blogroll.html"><i class="fa fa-Blogroll "></i> Blogroll</a></li>
<li><a href="http://tonyromarock.github.io/pages/books.html"><i class="fa fa-Previous Projects "></i> Previous Projects</a></li>
<li><a href="http://tonyromarock.github.io/pages/previous-projects.html"><i class="fa fa-Previous Projects "></i> Previous Projects</a></li>
<li><a href="http://tonyromarock.github.io/feeds/all.atom.xml" type="application/atom+xml"><i class="fa fa-rss "></i> atom</a></li>
</ul>
</div>
<div class="col-md-3">
<h4>Author</h4>
<ul class="list-unstyled my-list-style">
<li><a href="https://github.com/tonyromarock">GitHub</a></li>
</ul>
</div>
<div class="col-md-3">
<h4>Categories</h4>
<ul class="list-unstyled my-list-style">
<li><a href="http://tonyromarock.github.io/category/linux.html">Linux (1)</a></li>
<li><a href="http://tonyromarock.github.io/category/nonfiction.html">Nonfiction (1)</a></li>
<li><a href="http://tonyromarock.github.io/category/python.html">Python (4)</a></li>
</ul>
</div>
</div>
</div>
</div>
</div>
</footer>
<div class="container">
<div class="row">
<div class="col-md-12 text-center center-block aw-bottom">
<p>© Peter 2020</p>
<p>Powered by Pelican</p>
</div>
</div>
</div>
<!-- JavaScript -->
<script src="https://code.jquery.com/jquery-2.1.1.min.js"></script>
<script src="http://tonyromarock.github.io/theme/js/jquery-ui-1.9.1.custom.min.js"></script>
<script src="http://tonyromarock.github.io/theme/js/jquery.tocify.min.js""></script>
<script src="//maxcdn.bootstrapcdn.com/bootstrap/3.2.0/js/bootstrap.min.js"></script>
<script type="text/javascript">
jQuery(document).ready(function($) {
$("div.collapseheader").click(function () {
$header = $(this).children("span").first();
$codearea = $(this).children(".input_area");
$codearea.slideToggle(500, function () {
$header.text(function () {
return $codearea.is(":visible") ? "Collapse Code" : "Expand Code";
});
});
});
});
$(function() {
var toc = $("#toc").tocify({
context:"div.article-body",
selectors:"h1,h3",
showAndHide:"false",
extendPage:"false",
history:"true",
scrollHistory:"true"
}).data("toc-tocify");
});
</script>
</body>
</html>