1 | #ifndef _EMD_H |
---|

2 | #define _EMD_H |
---|

3 | /* |
---|

4 | emd.h |
---|

5 | |
---|

6 | Last update: 3/24/98 (but see below for newer changes) |
---|

7 | |
---|

8 | An implementation of the Earth Movers Distance. |
---|

9 | Based of the solution for the Transportation problem as described in |
---|

10 | "Introduction to Mathematical Programming" by F. S. Hillier and |
---|

11 | G. J. Lieberman, McGraw-Hill, 1990. |
---|

12 | |
---|

13 | Copyright (C) 1998 Yossi Rubner |
---|

14 | Computer Science Department, Stanford University |
---|

15 | E-Mail: rubner@cs.stanford.edu URL: http://robotics.stanford.edu/~rubner/emd/default.htm |
---|

16 | */ |
---|

17 | |
---|

18 | // List of changes since 2020, compared to the original implementation: |
---|

19 | // r1050: Renamed variables that caused problems with g++ 7.3.0 |
---|

20 | // r1062: Global static arrays moved to a function and now allocated dynamically; removed #defined limit of MAX_SIG_SIZE=1000 |
---|

21 | // r1172: Introduced EMD_LIMIT_WARNING_MESSAGES to limit the number of warning messages printed to stderr: "emd: Maximum number of iterations has been reached" |
---|

22 | |
---|

23 | |
---|

24 | /* DEFINITIONS */ |
---|

25 | #define MAX_ITERATIONS 500 |
---|

26 | //#define INFINITY 1e20 |
---|

27 | #define EPSILON 1e-6 |
---|

28 | |
---|

29 | /*****************************************************************************/ |
---|

30 | /* feature_t SHOULD BE MODIFIED BY THE USER TO REFLECT THE FEATURE TYPE */ |
---|

31 | //typedef struct { |
---|

32 | // double X,Y,Z; |
---|

33 | //} |
---|

34 | typedef double feature_t; |
---|

35 | /*****************************************************************************/ |
---|

36 | |
---|

37 | |
---|

38 | typedef struct |
---|

39 | { |
---|

40 | int n; /* Number of features in the signature */ |
---|

41 | feature_t *Features; /* Pointer to the features vector */ |
---|

42 | float *Weights; /* Pointer to the weights of the features */ |
---|

43 | } signature_t; |
---|

44 | |
---|

45 | |
---|

46 | typedef struct |
---|

47 | { |
---|

48 | int from; /* Feature number in signature 1 */ |
---|

49 | int to; /* Feature number in signature 2 */ |
---|

50 | float amount; /* Amount of flow from "from" to "to" */ |
---|

51 | } flow_t; |
---|

52 | |
---|

53 | |
---|

54 | |
---|

55 | float emd(signature_t *Signature1, signature_t *Signature2, |
---|

56 | float (*func)(feature_t *, feature_t *), |
---|

57 | flow_t *Flow, int *FlowSize); |
---|

58 | |
---|

59 | #endif |
---|