python emd算法

python emd算法 Earth Mover's Distance

/*
    emd.c

    Last update: 3/14/98

    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://vision.stanford.edu/~rubner
*/

#include 
#include 
#include 

#include “emd.h“

#define DEBUG_LEVEL 0
/*
 DEBUG_LEVEL:
   0 = NO MESSAGES
   1 = PRINT THE NUMBER OF ITERATIONS AND THE FINAL RESULT
   2 = PRINT THE RESULT AFTER EVERY ITERATION
   3 = PRINT ALSO THE FLOW AFTER EVERY ITERATION
   4 = PRINT A LOT OF INFORMATION （PROBABLY USEFUL ONLY FOR THE AUTHOR）
*/


#define MAX_SIG_SIZE1  （MAX_SIG_SIZE+1）  /* FOR THE POSIBLE DUMMY FEATURE */

/* NEW TYPES DEFINITION */

/* node1_t IS USED FOR SINGLE-linkED LISTS */
typedef struct node1_t {
  int i;
  double val;
  struct node1_t *Next;
} node1_t;

/* node1_t IS USED FOR DOUBLE-linkED LISTS */
typedef struct node2_t {
  int i j;
  double val;
  struct node2_t *NextC;               /* NEXT COLUMN */
  struct node2_t *NextR;               /* NEXT ROW */
} node2_t;



/* GLOBAL VARIABLE DECLARATION */
static int _n1 _n2;                          /* SIGNATURES SIZES */
static float _C[MAX_SIG_SIZE1][MAX_SIG_SIZE1];/* THE COST MATRIX */
static node2_t _X[MAX_SIG_SIZE1*2];            /* THE BASIC VARIABLES VECTOR */
/* VARIABLES TO HANDLE _X EFFICIENTLY */
static node2_t *_EndX *_EnterX;
static char _IsX[MAX_SIG_SIZE1][MAX_SIG_SIZE1];
static node2_t *_RowsX[MAX_SIG_SIZE1] *_ColsX[MAX_SIG_SIZE1];
static double _maxW;
static float _maxC;

/* DECLARATION OF FUNCTIONS */
static float init（signature_t *Signature1 signature_t *Signature2
		  float （*Dist）（feature_t * feature_t *））;
static void findBasicVariables（node1_t *U node1_t *V）;
static int isOptimal（node1_t *U node1_t *V）;
static int findLoop（node2_t **Loop）;
static void newSol（）;
static void russel（double *S double *D）;
static void addBasicVariable（int minI int minJ double *S double *D 
			     node1_t *PrevUMinI node1_t *PrevVMinJ
			     node1_t *UHead）;
#if DEBUG_LEVEL > 0
static void printSolution（）;
#endif


/******************************************************************************
float emd（signature_t *Signature1 signature_t *Signature2
	  float （*Dist）（feature_t * feature_t *） flow_t *Flow int *FlowSize）
  
where

   Signature1 Signature2  Pointers to signatures that their distance we want
              to compute.
   Dist       Pointer to the ground distance. i.e. the function that computes
              the distance between two features.
   Flow       （Optional） Pointer to a vector of flow_t （defined in emd.h） 
              where the resulting flow will be stored. Flow must have n1+n2-1
              elements where n1 and n2 are the sizes of the two signatures
              respec

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-02-25 09:28  python-emd-master\
     文件        1826  2015-08-17 21:12  python-emd-master\Makefile
     文件        5018  2015-05-24 22:28  python-emd-master\README.md
     目录           0  2015-11-30 23:14  python-emd-master\SolutionConverter_demo\
     文件       17920  2010-05-07 15:24  python-emd-master\SolutionConverter_demo\SolutionConverter.exe
     文件       13824  2010-05-07 15:24  python-emd-master\SolutionConverter_demo\SolutionConverterLib.dll
     文件        5120  2010-04-17 17:41  python-emd-master\SolutionConverter_demo\StringValueAttribute.dll
     目录           0  2015-11-30 23:14  python-emd-master\_emd\
     目录           0  2015-11-30 23:14  python-emd-master\_emd\_emd\
     目录           0  2015-11-30 23:14  python-emd-master\_emd\_emd\Debug\
     文件        1281  2015-08-21 19:53  python-emd-master\_emd\_emd\Debug\_emd.log
     目录           0  2015-11-30 23:14  python-emd-master\_emd\_emd\Debug\_emd.tlog\
     文件        1452  2015-08-21 19:53  python-emd-master\_emd\_emd\Debug\_emd.tlog\CL.read.1.tlog
     文件         762  2015-08-21 19:53  python-emd-master\_emd\_emd\Debug\_emd.tlog\CL.write.1.tlog
     文件         167  2015-08-21 19:53  python-emd-master\_emd\_emd\Debug\_emd.tlog\_emd.lastbuildstate
     文件        1318  2015-08-21 19:53  python-emd-master\_emd\_emd\Debug\_emd.tlog\cl.command.1.tlog
     文件           0  2015-08-21 19:53  python-emd-master\_emd\_emd\Debug\_emd.tlog\unsuccessfulbuild
     文件       19456  2015-08-21 19:53  python-emd-master\_emd\_emd\Debug\vc120.idb
     文件       53248  2015-08-21 19:53  python-emd-master\_emd\_emd\Debug\vc120.pdb
     目录           0  2015-11-30 23:14  python-emd-master\_emd\_emd\Release\
     文件        5680  2015-08-21 19:58  python-emd-master\_emd\_emd\Release\_emd.log
     目录           0  2015-11-30 23:14  python-emd-master\_emd\_emd\Release\_emd.tlog\
     文件         169  2015-08-21 19:58  python-emd-master\_emd\_emd\Release\_emd.tlog\_emd.lastbuildstate
     文件        1526  2015-08-21 19:56  python-emd-master\_emd\_emd\Release\_emd.tlog\cl.command.1.tlog
     文件       20736  2015-08-21 19:56  python-emd-master\_emd\_emd\Release\_emd.tlog\cl.read.1.tlog
     文件         936  2015-08-21 19:56  python-emd-master\_emd\_emd\Release\_emd.tlog\cl.write.1.tlog
     文件           2  2015-08-21 19:58  python-emd-master\_emd\_emd\Release\_emd.tlog\link.command.1.tlog
     文件           2  2015-08-21 19:58  python-emd-master\_emd\_emd\Release\_emd.tlog\link.read.1.tlog
     文件           2  2015-08-21 19:58  python-emd-master\_emd\_emd\Release\_emd.tlog\link.write.1.tlog
     文件           0  2015-08-21 19:58  python-emd-master\_emd\_emd\Release\_emd.tlog\unsuccessfulbuild
     文件       54809  2015-08-21 19:56  python-emd-master\_emd\_emd\Release\emd.obj
............此处省略5782个文件信息