2730:
2903:
the number of entities in that cluster. To compare two such signatures with the EMD, one must define a distance between features, which is interpreted as the cost of turning a unit mass of one feature into a unit mass of the other. The EMD between two signatures is then the minimum cost of turning
2505:
The EMD can be extended naturally to the case where more than two distributions are compared. In this case, the "distance" between the many distributions is defined as the optimal value of a linear program. This generalized EMD may be computed exactly using a greedy algorithm, and the resulting
2308:
2028:
1822:
2562:
548:
306:
1383:
2748:
applications. However, the computational cost of EMD is super-cubic to the number of the "bins" given an arbitrary "D". Efficient and scalable EMD computation techniques for large scale data have been investigated using
2147:
2408:
An alternative approach is to allow for mass to be created or destroyed, on a global or local level, as an alternative to transportation, but with a cost penalty. In that case one must specify a real parameter
1006:
863:
1650:
1557:
1464:
54:, the EMD captures the minimum cost of building the smaller pile using dirt taken from the larger, where cost is defined as the amount of dirt moved multiplied by the distance over which it is moved.
2429:, the ratio between the cost of creating or destroying one unit of "dirt", and the cost of transporting it by a unit distance. This is equivalent to minimizing the sum of the earth moving cost plus
1853:
1658:
606:
2567:
2725:{\displaystyle {\begin{aligned}{\text{EMD}}_{0}&=0\\{\text{EMD}}_{i+1}&=P_{i}+{\text{EMD}}_{i}-Q_{i}\\{\text{Total Distance}}&=\sum _{i=0}^{n}|{\text{EMD}}_{i}|\end{aligned}}}
2495:
407:
2824:
181:
2353:
2931:. The use of the EMD as a distance measure for monochromatic images was described in 1989 by S. Peleg, M. Werman and H. Rom. The name "earth mover's distance" was proposed by
344:
2447:
2427:
2399:
2376:
85:
2552:, the EMD can be efficiently computed by scanning the array and keeping track of how much dirt needs to be transported between consecutive bins. Here the bins are
1223:
2119:
2072:
1277:
1250:
1105:
1078:
720:
693:
392:
372:
1190:
1051:
2139:
2092:
1845:
1145:
1125:
662:
634:
169:
149:
2777:, blurring, or local deformations. In this case, the region is the image's domain, and the total amount of light (or ink) is the "dirt" to be rearranged.
2047:, where dirt from the more massive distribution is rearranged to make the less massive, and any leftover "dirt" is discarded at no cost. Formally, let
1285:
2303:{\displaystyle {\text{EMD}}(P,Q)={\tfrac {1}{\min(w_{P},w_{Q})}}\inf \limits _{\gamma \in \Pi _{\geq }(P,Q)}\int d(x,y)\,\mathrm {d} \gamma (x,y)}
2541:
is the set {0, 1}. If the domain is integral, it can be translated for the same algorithm by representing integral bins as multiple binary bins.
3213:
Jia Xu; Bin Lei; Yu Gu; Winslett, M.; Ge Yu; Zhenjie Zhang (2015). "Efficient
Similarity Join Based on Earth Mover's Distance Using MapReduce".
3198:
Jin Huang; Rui Zhang; Rajkumar Buyya; Jian Chen (2014). "MELODY-Join: Efficient Earth Mover's
Distance Similarity Joins Using MapReduce".
868:
725:
3228:
Jin Huang; Rui Zhang; Rajkumar Buyya; Jian Chen, M.; Yongwei Wu (2015). "Heads-Join: Efficient Earth Mover's
Distance Join on Hadoop".
1847:
is found by solving this linear optimization problem. The earth mover's distance is defined as the work normalized by the total flow:
1565:
1472:
120:
119:
transportation problem; when the measures are uniform over a set of discrete elements, the same optimization problem is known as
2023:{\displaystyle {\text{EMD}}(P,Q)={\frac {\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}d_{i,j}}{\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}}}}
1817:{\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}=\min \left\{\ \sum _{i=1}^{m}w_{pi},\quad \sum _{j=1}^{n}w_{qj}\ \right\}}
1394:
3103:
3062:
3424:
C++ and Matlab and Java wrappers code for the Earth Mover's
Distance, especially efficient for thresholded ground distances
560:
2928:
2043:
Some applications may require the comparison of distributions with different total masses. One approach is to allow for
3429:
Java implementation of a generic generator for evaluating large-scale Earth Mover's
Distance based similarity analysis
3407:
2996:
2741:
543:{\displaystyle {\text{EMD}}(P,Q)=\sup \limits _{\|f\|_{L}\leq 1}\,\mathbb {E} _{x\sim P}-\mathbb {E} _{y\sim Q}\,}
2456:
398:
347:
3448:
3434:
Demonstration of
Minkowski additivity, convex monotonicity, and other properties of the Earth Movers distance
2912:
2781:
2758:
301:{\displaystyle {\text{EMD}}(P,Q)=\inf \limits _{\gamma \in \Pi (P,Q)}\mathbb {E} _{(x,y)\sim \gamma }\left\,}
3246:
S. Peleg; M. Werman; H. Rom (1989). "A unified approach to the change of resolution: Space and gray-level".
3423:
3283:"Earth Mover's Distance (EMD): A True Metric for Comparing Biomarker Expression Levels in Cell Populations"
32:
2948:
3183:
Kristen
Grauman; Trevor Darrel (2004). "Fast contour matching using approximate earth mover's distance".
2796:, and each image pixel is a parcel of "dirt". The same technique can be used for any other quantitative
3344:
Histoire de l'Académie Royale des
Science, Année 1781, avec les Mémoires de Mathématique et de Physique
2316:
665:
3168:
Mark A. Ruzon; Carlo Tomasi (2001). "Edge, Junction, and Corner
Detection Using Color Distributions".
2754:
2527:
2523:
100:
3082:. Lecture Notes in Computer Science. Vol. 5304. Springer Berlin Heidelberg. pp. 495–508.
3078:
Pele, Ofir; Werman, Michael (2008). "A Linear Time
Histogram Metric for Improved SIFT Matching".
3359:
2915:, with potential applications to other technologies that report distributions of measurements.
2519:
314:
112:
96:
28:
2432:
2412:
351:
36:
2381:
2358:
3296:
2402:
554:
172:
63:
8:
2820:
2745:
2534:
1195:
92:
3428:
3413:
3300:
2453:
distance between the rearranged pile and the second distribution. The resulting measure
3382:
3319:
3282:
3281:
Orlova, DY; Zimmerman, N; Meehan, C; Meehan, S; Waters, J; Ghosn, EEB (23 March 2016).
3263:
3150:
3091:
3002:
2936:
2507:
2097:
2050:
1255:
1228:
1083:
1056:
698:
671:
377:
357:
108:
88:
58:
46:. Informally, if the distributions are interpreted as two different ways of piling up
3324:
3154:
3109:
3099:
3058:
2992:
116:
3386:
3267:
3006:
1150:
1011:
3374:
3314:
3304:
3255:
3140:
3083:
3033:
2984:
2891:
2124:
2077:
1830:
1130:
1110:
647:
619:
154:
134:
3403:
3309:
3087:
2793:
2785:
2740:
EMD-based similarity analysis (EMDSA) is an important and effective tool in many
57:
Over probability distributions, the earth mover's distance is also known as the
2805:
1378:{\displaystyle \min \limits _{F}{\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}d_{i,j}}}
3378:
3145:
3128:
3038:
3021:
2976:
2877:
is "mass" (how many times that feature occurs in the record). Alternatively,
2868:
is a certain "feature" (e.g., color in an image, letter in a text, etc.), and
3442:
3227:
3113:
3095:
2988:
2924:
2789:
104:
3328:
2932:
2809:
2553:
40:
2981:
Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271)
3197:
2813:
3418:
2908:
2769:
An early application of the EMD in computer science was to compare two
2405:
between distributions, as it does not satisfy the triangle inequality.
3419:
Python2 wrapper for the C implementation of the Earth Mover's Distance
3259:
3356:
J. Stolfi, personal communication to L. J. Guibas, 1994, as cited by
2801:
2774:
2770:
2750:
3433:
2907:
EMD analysis has been used for quantitating multivariate changes in
3287:
2935:
in 1994, and was used in print in 1998 by Y. Rubner, C. Tomasi and
2887:
1001:{\textstyle Q=\{(q_{1},w_{q1}),(q_{2},w_{q2}),...,(q_{n},w_{qn})\}}
858:{\textstyle P=\{(p_{1},w_{p1}),(p_{2},w_{p2}),...,(p_{m},w_{pm})\}}
616:
In some applications, it is convenient to represent a distribution
2823:
to compare generic summaries or surrogates of data records called
2977:"A metric for distributions with applications to image databases"
1645:{\displaystyle \sum _{i=1}^{m}{f_{i,j}}\leq w_{qj},1\leq j\leq n}
1552:{\displaystyle \sum _{j=1}^{n}{f_{i,j}}\leq w_{pi},1\leq i\leq m}
3200:
Proceedings of IEEE International Conference on Data Engineering
3248:
IEEE Transactions on Pattern Analysis and Machine Intelligence
3212:
3170:
IEEE Transactions on Pattern Analysis and Machine Intelligence
2797:
3360:"The earth mover's distance as a metric for image retrieval"
3182:
3280:
47:
3358:
Rubner, Yossi; Tomasi, Carlo; Guibas, Leonidas J. (2000).
3167:
1459:{\displaystyle f_{i,j}\geq 0,1\leq i\leq m,1\leq j\leq n}
3245:
3129:"Properties of the d-dimensional earth mover's problem"
3342:"Mémoire sur la théorie des déblais et des remblais".
2175:
2127:
2100:
2080:
2053:
1833:
1258:
1231:
1198:
1153:
1133:
1113:
1086:
1059:
1014:
871:
728:
701:
674:
650:
622:
157:
137:
3230:
IEEE Transactions on Parallel and Distributed Systems
2565:
2459:
2435:
2415:
2384:
2361:
2319:
2150:
1856:
1661:
1568:
1475:
1397:
1288:
563:
410:
380:
360:
317:
184:
66:
3057:(4th ed.). John Wiley & Sons. p. 221.
601:{\displaystyle \|\nabla f(x)\|\leq 1\quad \forall x}
3215:
IEEE Transactions on Knowledge and Data Engineering
2827:. A typical signature consists of list of pairs ((
3357:
2974:
2724:
2518:The EMD can be computed by solving an instance of
2489:
2441:
2421:
2393:
2370:
2347:
2302:
2133:
2113:
2086:
2066:
2022:
1839:
1816:
1644:
1551:
1458:
1377:
1271:
1244:
1217:
1184:
1139:
1119:
1099:
1072:
1045:
1000:
857:
714:
687:
656:
628:
600:
542:
386:
366:
338:
300:
163:
143:
79:
2355:is the set of all measures whose projections are
3440:
3052:
2735:
2401:. Note that this generalization of EMD is not a
2181:
1723:
2548:is a one-dimensional array of "bins" of length
2537:can be used to get the solution if the domain
2500:
3071:
3055:Engineering Optimization: Theory and Practice
3019:
2975:Rubner, Y.; Tomasi, C.; Guibas, L.J. (1998).
995:
878:
852:
735:
722:. In this formulation, consider signatures
582:
564:
446:
439:
27:) is a measure of dissimilarity between two
3274:
2983:. Narosa Publishing House. pp. 59–66.
2038:
3077:
2490:{\displaystyle {\widehat {EMD}}_{\alpha }}
2033:
131:The EMD between probability distributions
16:Distance between probability distributions
3318:
3308:
3144:
3046:
3037:
2276:
611:
539:
505:
466:
463:
297:
241:
3367:International Journal of Computer Vision
3241:
3239:
3206:
1053:be the ground distance between clusters
2970:
2968:
2966:
2964:
99:'s distance. It is the solution of the
3441:
3221:
3176:
3022:"A note on asymptotic joint normality"
3414:Python implementation with references
3404:C code for the Earth Mover's Distance
3236:
3191:
3126:
553:where the supremum is taken over all
126:
103:, which in turn is also known as the
2961:
2923:The concept was first introduced by
2513:
3161:
2819:More generally, the EMD is used in
2792:. In this case, the region is the
1279:, that minimizes the overall cost.
13:
2321:
2278:
2229:
592:
567:
318:
219:
14:
3460:
3397:
3026:Annals of Mathematical Statistics
2784:to compute distances between the
2348:{\displaystyle \Pi _{\geq }(P,Q)}
401:, this can also be expressed as:
121:minimum weight bipartite matching
2742:multimedia information retrieval
2506:functional has been shown to be
3350:
3335:
2764:
1771:
591:
3120:
3013:
2773:images that may differ due to
2714:
2697:
2342:
2330:
2297:
2285:
2273:
2261:
2250:
2238:
2210:
2184:
2168:
2156:
1874:
1862:
1179:
1160:
1040:
1021:
992:
963:
945:
916:
910:
881:
849:
820:
802:
773:
767:
738:
579:
573:
536:
533:
527:
521:
497:
494:
488:
482:
428:
416:
399:Kantorovich-Rubinstein duality
333:
321:
289:
277:
258:
246:
234:
222:
202:
190:
1:
2954:
2782:content-based image retrieval
2759:resilient distributed dataset
2736:EMD-based similarity analysis
2497:is a true distance function.
1147:is given by the optimal flow
3310:10.1371/journal.pone.0151859
3133:Discrete Applied Mathematics
3088:10.1007/978-3-540-88690-7_37
2904:one of them into the other.
1388:subject to the constraints:
7:
3080:Computer Vision – ECCV 2008
2942:
2927:in 1781, in the context of
2501:More than two distributions
2218:
1290:
435:
209:
10:
3465:
2918:
2780:The EMD is widely used in
2522:, using any algorithm for
175:over joint probabilities:
111:problem, or sometimes the
3146:10.1016/j.dam.2019.02.042
3053:Singiresu S. Rao (2009).
2755:bulk synchronous parallel
2528:network simplex algorithm
2524:minimum-cost flow problem
664:-th cluster represents a
339:{\displaystyle \Pi (P,Q)}
101:optimal transport problem
19:In computer science, the
3185:Proceedings of CVPR 2004
2989:10.1109/iccv.1998.710701
2039:Unequal probability mass
3379:10.1023/A:1026543900054
3127:Kline, Jeffery (2019).
3039:10.1214/aoms/1177692631
2442:{\displaystyle \alpha }
2422:{\displaystyle \alpha }
2121:be the total weight of
2074:be the total weight of
2034:Variants and extensions
1107:. Then the EMD between
29:frequency distributions
3020:C. L. Mallows (1972).
2726:
2695:
2544:As a special case, if
2520:transportation problem
2491:
2443:
2423:
2395:
2394:{\displaystyle \geq Q}
2372:
2371:{\displaystyle \geq P}
2349:
2304:
2135:
2115:
2088:
2068:
2024:
2000:
1979:
1924:
1903:
1841:
1818:
1792:
1754:
1703:
1682:
1646:
1589:
1553:
1496:
1460:
1379:
1341:
1320:
1273:
1246:
1219:
1186:
1141:
1121:
1101:
1074:
1047:
1002:
859:
716:
689:
658:
630:
612:EMD between signatures
602:
555:1-Lipschitz continuous
544:
388:
368:
340:
302:
165:
145:
81:
21:earth mover's distance
2949:Monge–Ampère equation
2929:transportation theory
2727:
2675:
2510:and convex monotone.
2492:
2444:
2424:
2396:
2373:
2350:
2305:
2136:
2116:
2089:
2069:
2025:
1980:
1959:
1904:
1883:
1842:
1819:
1772:
1734:
1683:
1662:
1647:
1569:
1554:
1476:
1461:
1380:
1321:
1300:
1274:
1247:
1220:
1187:
1142:
1122:
1102:
1075:
1048:
1003:
860:
717:
690:
659:
640:, or a collection of
631:
603:
545:
389:
369:
341:
303:
171:can be defined as an
166:
146:
82:
80:{\displaystyle W_{1}}
3449:Statistical distance
2563:
2457:
2433:
2413:
2382:
2359:
2317:
2148:
2125:
2098:
2078:
2051:
1854:
1831:
1659:
1566:
1473:
1395:
1286:
1256:
1229:
1218:{\textstyle f_{i,j}}
1196:
1151:
1131:
1111:
1084:
1057:
1012:
869:
726:
699:
672:
648:
620:
561:
408:
378:
358:
315:
182:
155:
135:
64:
3301:2016PLoSO..1151859O
2821:pattern recognition
2800:attribute, such as
2746:pattern recognition
2535:Hungarian algorithm
348:joint distributions
2722:
2720:
2508:Minkowski additive
2487:
2439:
2419:
2391:
2368:
2345:
2300:
2254:
2215:
2131:
2114:{\textstyle w_{Q}}
2111:
2084:
2067:{\textstyle w_{P}}
2064:
2020:
1837:
1814:
1642:
1549:
1456:
1375:
1298:
1272:{\textstyle q_{j}}
1269:
1245:{\textstyle p_{i}}
1242:
1215:
1182:
1137:
1117:
1100:{\textstyle q_{j}}
1097:
1073:{\textstyle p_{i}}
1070:
1043:
998:
855:
715:{\textstyle p_{i}}
712:
688:{\textstyle w_{i}}
685:
654:
626:
598:
540:
462:
384:
364:
346:is the set of all
336:
298:
238:
161:
141:
127:Formal definitions
77:
59:Wasserstein metric
3260:10.1109/34.192468
3105:978-3-540-88689-1
3064:978-0-470-18352-6
2705:
2666:
2638:
2600:
2574:
2514:Computing the EMD
2478:
2217:
2214:
2154:
2018:
1860:
1827:The optimal flow
1808:
1733:
1289:
1225:the flow between
434:
414:
387:{\displaystyle Q}
367:{\displaystyle P}
208:
188:
3456:
3391:
3390:
3364:
3354:
3348:
3347:
3339:
3333:
3332:
3322:
3312:
3278:
3272:
3271:
3243:
3234:
3233:
3225:
3219:
3218:
3210:
3204:
3203:
3195:
3189:
3188:
3180:
3174:
3173:
3165:
3159:
3158:
3148:
3124:
3118:
3117:
3075:
3069:
3068:
3050:
3044:
3043:
3041:
3017:
3011:
3010:
2972:
2786:color histograms
2731:
2729:
2728:
2723:
2721:
2717:
2712:
2711:
2706:
2703:
2700:
2694:
2689:
2667:
2664:
2658:
2657:
2645:
2644:
2639:
2636:
2630:
2629:
2613:
2612:
2601:
2598:
2581:
2580:
2575:
2572:
2496:
2494:
2493:
2488:
2486:
2485:
2480:
2479:
2474:
2463:
2448:
2446:
2445:
2440:
2428:
2426:
2425:
2420:
2400:
2398:
2397:
2392:
2377:
2375:
2374:
2369:
2354:
2352:
2351:
2346:
2329:
2328:
2309:
2307:
2306:
2301:
2281:
2253:
2237:
2236:
2216:
2213:
2209:
2208:
2196:
2195:
2176:
2155:
2152:
2140:
2138:
2137:
2132:
2120:
2118:
2117:
2112:
2110:
2109:
2093:
2091:
2090:
2085:
2073:
2071:
2070:
2065:
2063:
2062:
2045:partial matching
2029:
2027:
2026:
2021:
2019:
2017:
2016:
2015:
1999:
1994:
1978:
1973:
1957:
1956:
1955:
1940:
1939:
1923:
1918:
1902:
1897:
1881:
1861:
1858:
1846:
1844:
1843:
1838:
1823:
1821:
1820:
1815:
1813:
1809:
1806:
1805:
1804:
1791:
1786:
1767:
1766:
1753:
1748:
1731:
1719:
1718:
1702:
1697:
1681:
1676:
1651:
1649:
1648:
1643:
1623:
1622:
1607:
1606:
1605:
1588:
1583:
1558:
1556:
1555:
1550:
1530:
1529:
1514:
1513:
1512:
1495:
1490:
1465:
1463:
1462:
1457:
1413:
1412:
1384:
1382:
1381:
1376:
1374:
1373:
1372:
1357:
1356:
1340:
1335:
1319:
1314:
1297:
1278:
1276:
1275:
1270:
1268:
1267:
1251:
1249:
1248:
1243:
1241:
1240:
1224:
1222:
1221:
1216:
1214:
1213:
1191:
1189:
1188:
1183:
1178:
1177:
1146:
1144:
1143:
1138:
1126:
1124:
1123:
1118:
1106:
1104:
1103:
1098:
1096:
1095:
1079:
1077:
1076:
1071:
1069:
1068:
1052:
1050:
1049:
1044:
1039:
1038:
1007:
1005:
1004:
999:
991:
990:
975:
974:
944:
943:
928:
927:
909:
908:
893:
892:
864:
862:
861:
856:
848:
847:
832:
831:
801:
800:
785:
784:
766:
765:
750:
749:
721:
719:
718:
713:
711:
710:
694:
692:
691:
686:
684:
683:
663:
661:
660:
655:
635:
633:
632:
627:
607:
605:
604:
599:
557:functions, i.e.
549:
547:
546:
541:
520:
519:
508:
481:
480:
469:
461:
454:
453:
415:
412:
393:
391:
390:
385:
373:
371:
370:
365:
345:
343:
342:
337:
307:
305:
304:
299:
296:
292:
268:
267:
244:
237:
189:
186:
170:
168:
167:
162:
150:
148:
147:
142:
86:
84:
83:
78:
76:
75:
3464:
3463:
3459:
3458:
3457:
3455:
3454:
3453:
3439:
3438:
3400:
3395:
3394:
3362:
3355:
3351:
3341:
3340:
3336:
3295:(3): e0151859.
3279:
3275:
3244:
3237:
3226:
3222:
3211:
3207:
3196:
3192:
3181:
3177:
3166:
3162:
3125:
3121:
3106:
3076:
3072:
3065:
3051:
3047:
3018:
3014:
2999:
2973:
2962:
2957:
2945:
2921:
2902:
2885:
2876:
2867:
2859:)), where each
2858:
2849:
2840:
2833:
2810:apparent motion
2767:
2738:
2719:
2718:
2713:
2707:
2702:
2701:
2696:
2690:
2679:
2668:
2663:
2660:
2659:
2653:
2649:
2640:
2635:
2634:
2625:
2621:
2614:
2602:
2597:
2596:
2593:
2592:
2582:
2576:
2571:
2570:
2566:
2564:
2561:
2560:
2516:
2503:
2481:
2464:
2462:
2461:
2460:
2458:
2455:
2454:
2434:
2431:
2430:
2414:
2411:
2410:
2383:
2380:
2379:
2360:
2357:
2356:
2324:
2320:
2318:
2315:
2314:
2277:
2232:
2228:
2221:
2204:
2200:
2191:
2187:
2180:
2174:
2151:
2149:
2146:
2145:
2126:
2123:
2122:
2105:
2101:
2099:
2096:
2095:
2079:
2076:
2075:
2058:
2054:
2052:
2049:
2048:
2041:
2036:
2005:
2001:
1995:
1984:
1974:
1963:
1958:
1945:
1941:
1929:
1925:
1919:
1908:
1898:
1887:
1882:
1880:
1857:
1855:
1852:
1851:
1832:
1829:
1828:
1797:
1793:
1787:
1776:
1759:
1755:
1749:
1738:
1730:
1726:
1708:
1704:
1698:
1687:
1677:
1666:
1660:
1657:
1656:
1615:
1611:
1595:
1591:
1590:
1584:
1573:
1567:
1564:
1563:
1522:
1518:
1502:
1498:
1497:
1491:
1480:
1474:
1471:
1470:
1402:
1398:
1396:
1393:
1392:
1362:
1358:
1346:
1342:
1336:
1325:
1315:
1304:
1299:
1293:
1287:
1284:
1283:
1263:
1259:
1257:
1254:
1253:
1236:
1232:
1230:
1227:
1226:
1203:
1199:
1197:
1194:
1193:
1185:{\textstyle F=}
1167:
1163:
1152:
1149:
1148:
1132:
1129:
1128:
1112:
1109:
1108:
1091:
1087:
1085:
1082:
1081:
1064:
1060:
1058:
1055:
1054:
1046:{\textstyle D=}
1028:
1024:
1013:
1010:
1009:
983:
979:
970:
966:
936:
932:
923:
919:
901:
897:
888:
884:
870:
867:
866:
840:
836:
827:
823:
793:
789:
780:
776:
758:
754:
745:
741:
727:
724:
723:
706:
702:
700:
697:
696:
679:
675:
673:
670:
669:
649:
646:
645:
621:
618:
617:
614:
562:
559:
558:
509:
504:
503:
470:
465:
464:
449:
445:
438:
411:
409:
406:
405:
379:
376:
375:
359:
356:
355:
316:
313:
312:
273:
269:
245:
240:
239:
212:
185:
183:
180:
179:
156:
153:
152:
136:
133:
132:
129:
71:
67:
65:
62:
61:
17:
12:
11:
5:
3462:
3452:
3451:
3437:
3436:
3431:
3426:
3421:
3416:
3411:
3399:
3398:External links
3396:
3393:
3392:
3349:
3334:
3273:
3254:(7): 739–742.
3235:
3220:
3205:
3190:
3175:
3160:
3119:
3104:
3070:
3063:
3045:
3032:(2): 508–515.
3012:
2997:
2959:
2958:
2956:
2953:
2952:
2951:
2944:
2941:
2920:
2917:
2913:flow cytometry
2898:
2881:
2872:
2863:
2854:
2845:
2838:
2831:
2794:RGB color cube
2790:digital images
2766:
2763:
2737:
2734:
2733:
2732:
2716:
2710:
2699:
2693:
2688:
2685:
2682:
2678:
2674:
2671:
2669:
2665:Total Distance
2662:
2661:
2656:
2652:
2648:
2643:
2633:
2628:
2624:
2620:
2617:
2615:
2611:
2608:
2605:
2595:
2594:
2591:
2588:
2585:
2583:
2579:
2569:
2568:
2515:
2512:
2502:
2499:
2484:
2477:
2473:
2470:
2467:
2438:
2418:
2390:
2387:
2367:
2364:
2344:
2341:
2338:
2335:
2332:
2327:
2323:
2311:
2310:
2299:
2296:
2293:
2290:
2287:
2284:
2280:
2275:
2272:
2269:
2266:
2263:
2260:
2257:
2252:
2249:
2246:
2243:
2240:
2235:
2231:
2227:
2224:
2220:
2212:
2207:
2203:
2199:
2194:
2190:
2186:
2183:
2179:
2173:
2170:
2167:
2164:
2161:
2158:
2134:{\textstyle Q}
2130:
2108:
2104:
2087:{\textstyle P}
2083:
2061:
2057:
2040:
2037:
2035:
2032:
2031:
2030:
2014:
2011:
2008:
2004:
1998:
1993:
1990:
1987:
1983:
1977:
1972:
1969:
1966:
1962:
1954:
1951:
1948:
1944:
1938:
1935:
1932:
1928:
1922:
1917:
1914:
1911:
1907:
1901:
1896:
1893:
1890:
1886:
1879:
1876:
1873:
1870:
1867:
1864:
1840:{\textstyle F}
1836:
1825:
1824:
1812:
1803:
1800:
1796:
1790:
1785:
1782:
1779:
1775:
1770:
1765:
1762:
1758:
1752:
1747:
1744:
1741:
1737:
1729:
1725:
1722:
1717:
1714:
1711:
1707:
1701:
1696:
1693:
1690:
1686:
1680:
1675:
1672:
1669:
1665:
1653:
1652:
1641:
1638:
1635:
1632:
1629:
1626:
1621:
1618:
1614:
1610:
1604:
1601:
1598:
1594:
1587:
1582:
1579:
1576:
1572:
1560:
1559:
1548:
1545:
1542:
1539:
1536:
1533:
1528:
1525:
1521:
1517:
1511:
1508:
1505:
1501:
1494:
1489:
1486:
1483:
1479:
1467:
1466:
1455:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1411:
1408:
1405:
1401:
1386:
1385:
1371:
1368:
1365:
1361:
1355:
1352:
1349:
1345:
1339:
1334:
1331:
1328:
1324:
1318:
1313:
1310:
1307:
1303:
1296:
1292:
1266:
1262:
1239:
1235:
1212:
1209:
1206:
1202:
1181:
1176:
1173:
1170:
1166:
1162:
1159:
1156:
1140:{\textstyle Q}
1136:
1120:{\textstyle P}
1116:
1094:
1090:
1067:
1063:
1042:
1037:
1034:
1031:
1027:
1023:
1020:
1017:
997:
994:
989:
986:
982:
978:
973:
969:
965:
962:
959:
956:
953:
950:
947:
942:
939:
935:
931:
926:
922:
918:
915:
912:
907:
904:
900:
896:
891:
887:
883:
880:
877:
874:
854:
851:
846:
843:
839:
835:
830:
826:
822:
819:
816:
813:
810:
807:
804:
799:
796:
792:
788:
783:
779:
775:
772:
769:
764:
761:
757:
753:
748:
744:
740:
737:
734:
731:
709:
705:
682:
678:
657:{\textstyle i}
653:
629:{\textstyle P}
625:
613:
610:
597:
594:
590:
587:
584:
581:
578:
575:
572:
569:
566:
551:
550:
538:
535:
532:
529:
526:
523:
518:
515:
512:
507:
502:
499:
496:
493:
490:
487:
484:
479:
476:
473:
468:
460:
457:
452:
448:
444:
441:
437:
433:
430:
427:
424:
421:
418:
383:
363:
335:
332:
329:
326:
323:
320:
309:
308:
295:
291:
288:
285:
282:
279:
276:
272:
266:
263:
260:
257:
254:
251:
248:
243:
236:
233:
230:
227:
224:
221:
218:
215:
211:
207:
204:
201:
198:
195:
192:
164:{\textstyle Q}
160:
144:{\textstyle P}
140:
128:
125:
74:
70:
15:
9:
6:
4:
3:
2:
3461:
3450:
3447:
3446:
3444:
3435:
3432:
3430:
3427:
3425:
3422:
3420:
3417:
3415:
3412:
3409:
3405:
3402:
3401:
3388:
3384:
3380:
3376:
3373:(2): 99–121.
3372:
3368:
3361:
3353:
3345:
3338:
3330:
3326:
3321:
3316:
3311:
3306:
3302:
3298:
3294:
3290:
3289:
3284:
3277:
3269:
3265:
3261:
3257:
3253:
3249:
3242:
3240:
3231:
3224:
3216:
3209:
3201:
3194:
3186:
3179:
3171:
3164:
3156:
3152:
3147:
3142:
3138:
3134:
3130:
3123:
3115:
3111:
3107:
3101:
3097:
3093:
3089:
3085:
3081:
3074:
3066:
3060:
3056:
3049:
3040:
3035:
3031:
3027:
3023:
3016:
3008:
3004:
3000:
2998:81-7319-221-9
2994:
2990:
2986:
2982:
2978:
2971:
2969:
2967:
2965:
2960:
2950:
2947:
2946:
2940:
2938:
2934:
2930:
2926:
2925:Gaspard Monge
2916:
2914:
2910:
2905:
2901:
2897:
2893:
2889:
2884:
2880:
2875:
2871:
2866:
2862:
2857:
2853:
2848:
2844:
2837:
2830:
2826:
2822:
2817:
2815:
2811:
2807:
2803:
2799:
2795:
2791:
2787:
2783:
2778:
2776:
2772:
2762:
2760:
2756:
2753:, as well as
2752:
2747:
2743:
2708:
2691:
2686:
2683:
2680:
2676:
2672:
2670:
2654:
2650:
2646:
2641:
2631:
2626:
2622:
2618:
2616:
2609:
2606:
2603:
2589:
2586:
2584:
2577:
2559:
2558:
2557:
2555:
2551:
2547:
2542:
2540:
2536:
2531:
2529:
2525:
2521:
2511:
2509:
2498:
2482:
2475:
2471:
2468:
2465:
2452:
2436:
2416:
2406:
2404:
2403:true distance
2388:
2385:
2365:
2362:
2339:
2336:
2333:
2325:
2294:
2291:
2288:
2282:
2270:
2267:
2264:
2258:
2255:
2247:
2244:
2241:
2233:
2225:
2222:
2205:
2201:
2197:
2192:
2188:
2177:
2171:
2165:
2162:
2159:
2144:
2143:
2142:
2128:
2106:
2102:
2081:
2059:
2055:
2046:
2012:
2009:
2006:
2002:
1996:
1991:
1988:
1985:
1981:
1975:
1970:
1967:
1964:
1960:
1952:
1949:
1946:
1942:
1936:
1933:
1930:
1926:
1920:
1915:
1912:
1909:
1905:
1899:
1894:
1891:
1888:
1884:
1877:
1871:
1868:
1865:
1850:
1849:
1848:
1834:
1810:
1801:
1798:
1794:
1788:
1783:
1780:
1777:
1773:
1768:
1763:
1760:
1756:
1750:
1745:
1742:
1739:
1735:
1727:
1720:
1715:
1712:
1709:
1705:
1699:
1694:
1691:
1688:
1684:
1678:
1673:
1670:
1667:
1663:
1655:
1654:
1639:
1636:
1633:
1630:
1627:
1624:
1619:
1616:
1612:
1608:
1602:
1599:
1596:
1592:
1585:
1580:
1577:
1574:
1570:
1562:
1561:
1546:
1543:
1540:
1537:
1534:
1531:
1526:
1523:
1519:
1515:
1509:
1506:
1503:
1499:
1492:
1487:
1484:
1481:
1477:
1469:
1468:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1417:
1414:
1409:
1406:
1403:
1399:
1391:
1390:
1389:
1369:
1366:
1363:
1359:
1353:
1350:
1347:
1343:
1337:
1332:
1329:
1326:
1322:
1316:
1311:
1308:
1305:
1301:
1294:
1282:
1281:
1280:
1264:
1260:
1237:
1233:
1210:
1207:
1204:
1200:
1174:
1171:
1168:
1164:
1157:
1154:
1134:
1114:
1092:
1088:
1065:
1061:
1035:
1032:
1029:
1025:
1018:
1015:
987:
984:
980:
976:
971:
967:
960:
957:
954:
951:
948:
940:
937:
933:
929:
924:
920:
913:
905:
902:
898:
894:
889:
885:
875:
872:
844:
841:
837:
833:
828:
824:
817:
814:
811:
808:
805:
797:
794:
790:
786:
781:
777:
770:
762:
759:
755:
751:
746:
742:
732:
729:
707:
703:
680:
676:
667:
651:
643:
639:
623:
609:
595:
588:
585:
576:
570:
556:
530:
524:
516:
513:
510:
500:
491:
485:
477:
474:
471:
458:
455:
450:
442:
431:
425:
422:
419:
404:
403:
402:
400:
395:
381:
361:
353:
349:
330:
327:
324:
293:
286:
283:
280:
274:
270:
264:
261:
255:
252:
249:
231:
228:
225:
216:
213:
205:
199:
196:
193:
178:
177:
176:
174:
158:
138:
124:
122:
118:
114:
110:
106:
102:
98:
94:
90:
72:
68:
60:
55:
53:
49:
45:
42:
38:
34:
30:
26:
22:
3370:
3366:
3352:
3343:
3337:
3292:
3286:
3276:
3251:
3247:
3229:
3223:
3214:
3208:
3199:
3193:
3184:
3178:
3169:
3163:
3136:
3132:
3122:
3079:
3073:
3054:
3048:
3029:
3025:
3015:
2980:
2937:L. G. Guibas
2922:
2911:measured by
2906:
2899:
2895:
2892:data cluster
2882:
2878:
2873:
2869:
2864:
2860:
2855:
2851:
2846:
2842:
2835:
2828:
2818:
2779:
2768:
2765:Applications
2739:
2554:zero-indexed
2549:
2545:
2543:
2538:
2532:
2517:
2504:
2450:
2407:
2312:
2044:
2042:
1826:
1387:
695:centered at
644:, where the
641:
637:
615:
552:
396:
310:
130:
56:
51:
50:(dirt) over
43:
41:metric space
24:
20:
18:
3139:: 128–141.
2886:may be the
2814:video frame
2526:, e.g. the
2141:. We have:
109:Kantorovich
95:metric, or
89:Kantorovich
3406:(archived
2955:References
2909:biomarkers
2825:signatures
2449:times the
93:Rubinstein
3155:127962240
3114:0302-9743
3096:1611-3349
2933:J. Stolfi
2802:luminance
2775:dithering
2771:grayscale
2751:MapReduce
2677:∑
2647:−
2483:α
2476:^
2437:α
2417:α
2386:≥
2363:≥
2326:≥
2322:Π
2283:γ
2256:∫
2234:≥
2230:Π
2226:∈
2223:γ
1982:∑
1961:∑
1906:∑
1885:∑
1774:∑
1736:∑
1685:∑
1664:∑
1637:≤
1631:≤
1609:≤
1571:∑
1544:≤
1538:≤
1516:≤
1478:∑
1451:≤
1445:≤
1433:≤
1427:≤
1415:≥
1323:∑
1302:∑
638:signature
593:∀
586:≤
583:‖
568:∇
565:‖
514:∼
501:−
475:∼
456:≤
447:‖
440:‖
352:marginals
319:Π
265:γ
262:∼
220:Π
217:∈
214:γ
113:Hitchcock
39:, over a
33:densities
3443:Category
3387:14106275
3329:27008164
3288:PLOS One
3268:18415340
3007:18648233
2943:See also
2888:centroid
2841:), ... (
2816:, etc..
2806:gradient
668:of mass
642:clusters
117:Koopmans
37:measures
3346:. 1781.
3320:4805242
3297:Bibcode
2919:History
2788:of two
1192:, with
666:feature
173:infimum
97:Mallows
3385:
3327:
3317:
3266:
3153:
3112:
3102:
3094:
3061:
3005:
2995:
2894:, and
2313:where
2094:, and
1807:
1732:
1008:. Let
350:whose
311:where
3383:S2CID
3363:(PDF)
3264:S2CID
3151:S2CID
3092:eISSN
3003:S2CID
2890:of a
2812:in a
2798:pixel
636:as a
105:Monge
48:earth
35:, or
3408:here
3325:PMID
3110:ISSN
3100:ISBN
3059:ISBN
2993:ISBN
2757:and
2744:and
2533:The
2378:and
1252:and
1127:and
1080:and
865:and
374:and
354:are
151:and
3375:doi
3315:PMC
3305:doi
3256:doi
3141:doi
3137:265
3084:doi
3034:doi
2985:doi
2704:EMD
2637:EMD
2599:EMD
2573:EMD
2219:inf
2182:min
2153:EMD
1859:EMD
1724:min
1291:min
436:sup
413:EMD
397:By
210:inf
187:EMD
25:EMD
3445::
3381:.
3371:40
3369:.
3365:.
3323:.
3313:.
3303:.
3293:11
3291:.
3285:.
3262:.
3252:11
3250:.
3238:^
3149:.
3135:.
3131:.
3108:.
3098:.
3090:.
3030:43
3028:.
3024:.
3001:.
2991:.
2979:.
2963:^
2939:.
2808:,
2804:,
2761:.
2556::
2530:.
608:.
394:.
123:.
87:,
31:,
3410:)
3389:.
3377::
3331:.
3307::
3299::
3270:.
3258::
3232:.
3217:.
3202:.
3187:.
3172:.
3157:.
3143::
3116:.
3086::
3067:.
3042:.
3036::
3009:.
2987::
2900:i
2896:m
2883:i
2879:x
2874:i
2870:m
2865:i
2861:x
2856:n
2852:m
2850:,
2847:n
2843:x
2839:1
2836:m
2834:,
2832:1
2829:x
2715:|
2709:i
2698:|
2692:n
2687:0
2684:=
2681:i
2673:=
2655:i
2651:Q
2642:i
2632:+
2627:i
2623:P
2619:=
2610:1
2607:+
2604:i
2590:0
2587:=
2578:0
2550:n
2546:D
2539:D
2472:D
2469:M
2466:E
2451:L
2389:Q
2366:P
2343:)
2340:Q
2337:,
2334:P
2331:(
2298:)
2295:y
2292:,
2289:x
2286:(
2279:d
2274:)
2271:y
2268:,
2265:x
2262:(
2259:d
2251:)
2248:Q
2245:,
2242:P
2239:(
2211:)
2206:Q
2202:w
2198:,
2193:P
2189:w
2185:(
2178:1
2172:=
2169:)
2166:Q
2163:,
2160:P
2157:(
2129:Q
2107:Q
2103:w
2082:P
2060:P
2056:w
2013:j
2010:,
2007:i
2003:f
1997:n
1992:1
1989:=
1986:j
1976:m
1971:1
1968:=
1965:i
1953:j
1950:,
1947:i
1943:d
1937:j
1934:,
1931:i
1927:f
1921:n
1916:1
1913:=
1910:j
1900:m
1895:1
1892:=
1889:i
1878:=
1875:)
1872:Q
1869:,
1866:P
1863:(
1835:F
1811:}
1802:j
1799:q
1795:w
1789:n
1784:1
1781:=
1778:j
1769:,
1764:i
1761:p
1757:w
1751:m
1746:1
1743:=
1740:i
1728:{
1721:=
1716:j
1713:,
1710:i
1706:f
1700:n
1695:1
1692:=
1689:j
1679:m
1674:1
1671:=
1668:i
1640:n
1634:j
1628:1
1625:,
1620:j
1617:q
1613:w
1603:j
1600:,
1597:i
1593:f
1586:m
1581:1
1578:=
1575:i
1547:m
1541:i
1535:1
1532:,
1527:i
1524:p
1520:w
1510:j
1507:,
1504:i
1500:f
1493:n
1488:1
1485:=
1482:j
1454:n
1448:j
1442:1
1439:,
1436:m
1430:i
1424:1
1421:,
1418:0
1410:j
1407:,
1404:i
1400:f
1370:j
1367:,
1364:i
1360:d
1354:j
1351:,
1348:i
1344:f
1338:n
1333:1
1330:=
1327:j
1317:m
1312:1
1309:=
1306:i
1295:F
1265:j
1261:q
1238:i
1234:p
1211:j
1208:,
1205:i
1201:f
1180:]
1175:j
1172:,
1169:i
1165:f
1161:[
1158:=
1155:F
1135:Q
1115:P
1093:j
1089:q
1066:i
1062:p
1041:]
1036:j
1033:,
1030:i
1026:d
1022:[
1019:=
1016:D
996:}
993:)
988:n
985:q
981:w
977:,
972:n
968:q
964:(
961:,
958:.
955:.
952:.
949:,
946:)
941:2
938:q
934:w
930:,
925:2
921:q
917:(
914:,
911:)
906:1
903:q
899:w
895:,
890:1
886:q
882:(
879:{
876:=
873:Q
853:}
850:)
845:m
842:p
838:w
834:,
829:m
825:p
821:(
818:,
815:.
812:.
809:.
806:,
803:)
798:2
795:p
791:w
787:,
782:2
778:p
774:(
771:,
768:)
763:1
760:p
756:w
752:,
747:1
743:p
739:(
736:{
733:=
730:P
708:i
704:p
681:i
677:w
652:i
624:P
596:x
589:1
580:)
577:x
574:(
571:f
537:]
534:)
531:y
528:(
525:f
522:[
517:Q
511:y
506:E
498:]
495:)
492:x
489:(
486:f
483:[
478:P
472:x
467:E
459:1
451:L
443:f
432:=
429:)
426:Q
423:,
420:P
417:(
382:Q
362:P
334:)
331:Q
328:,
325:P
322:(
294:]
290:)
287:y
284:,
281:x
278:(
275:d
271:[
259:)
256:y
253:,
250:x
247:(
242:E
235:)
232:Q
229:,
226:P
223:(
206:=
203:)
200:Q
197:,
194:P
191:(
159:Q
139:P
115:–
107:-
91:–
73:1
69:W
52:D
44:D
23:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.