source: cpp/frams/model/similarity/EMD/emd.h @ 1302

#ifndef _EMD_H
#define _EMD_H
/*
    emd.h

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

    An implementation of the Earth Movers Distance.
    Based of the solution for the Transportation problem as described in
    "Introduction to Mathematical Programming" by F. S. Hillier and 
    G. J. Lieberman, McGraw-Hill, 1990.

    Copyright (C) 1998 Yossi Rubner
    Computer Science Department, Stanford University
    E-Mail: rubner@cs.stanford.edu   URL: http://robotics.stanford.edu/~rubner/emd/default.htm
*/

// List of changes since 2020, compared to the original implementation:
// r1050: Renamed variables that caused problems with g++ 7.3.0
// r1062: Global static arrays moved to a function and now allocated dynamically; removed #defined limit of MAX_SIG_SIZE=1000
// r1172: Introduced EMD_LIMIT_WARNING_MESSAGES to limit the number of warning messages printed to stderr: "emd: Maximum number of iterations has been reached"


/* DEFINITIONS */
#define MAX_ITERATIONS 500
//#define INFINITY       1e20
#define EPSILON        1e-6

/*****************************************************************************/
/* feature_t SHOULD BE MODIFIED BY THE USER TO REFLECT THE FEATURE TYPE      */
//typedef struct {
//   double X,Y,Z;
//}
typedef double feature_t;
/*****************************************************************************/


typedef struct
{
  int n;                /* Number of features in the signature */
  feature_t *Features;  /* Pointer to the features vector */
  float *Weights;       /* Pointer to the weights of the features */
} signature_t;


typedef struct
{
  int from;             /* Feature number in signature 1 */
  int to;               /* Feature number in signature 2 */
  float amount;         /* Amount of flow from "from" to "to" */
} flow_t;



float emd(signature_t *Signature1, signature_t *Signature2,
          float (*func)(feature_t *, feature_t *),
          flow_t *Flow, int *FlowSize);

#endif