Changeset 1062 for cpp/frams


Ignore:
Timestamp:
01/26/21 17:41:01 (4 years ago)
Author:
oriona
Message:

Global arrays moved to emd function.

Location:
cpp/frams/model/similarity
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • cpp/frams/model/similarity/EMD/emd.c

    r1061 r1062  
    3030*/
    3131
    32 
    33 #define MAX_SIG_SIZE1  (MAX_SIG_SIZE+1)  /* FOR THE POSIBLE DUMMY FEATURE */
    34 
    3532/* NEW TYPES DEFINITION */
    3633
    … …  
    5350
    5451/* GLOBAL VARIABLE DECLARATION */
    55 static int _n1, _n2;                          /* SIGNATURES SIZES */
    56 static float _CM[MAX_SIG_SIZE1][MAX_SIG_SIZE1];/* THE COST MATRIX */
    57 static node2_t _XV[MAX_SIG_SIZE1*2];            /* THE BASIC VARIABLES VECTOR */
     52
    5853/* VARIABLES TO HANDLE _X EFFICIENTLY */
    5954static node2_t *_EndX, *_EnterX;
    60 static char _IsX[MAX_SIG_SIZE1][MAX_SIG_SIZE1];
    61 static node2_t *_RowsX[MAX_SIG_SIZE1], *_ColsX[MAX_SIG_SIZE1];
    6255static double _maxW;
    6356static float _maxC;
    … …  
    6558/* DECLARATION OF FUNCTIONS */
    6659static float init(signature_t *Signature1, signature_t *Signature2,
    67                   float (*Dist)(feature_t *, feature_t *));
    68 static void findBasicVariables(node1_t *U, node1_t *V);
    69 static int isOptimal(node1_t *U, node1_t *V);
    70 static int findLoop(node2_t **Loop);
    71 static void newSol();
    72 static void russel(double *S, double *D);
     60                  float (*Dist)(feature_t *, feature_t *), int _n1, int _n2,
     61        float **_CM, node2_t *_XV, char **_IsX, node2_t **_RowsX, node2_t **_ColsX);
     62static void findBasicVariables(node1_t *U, node1_t *V, int _n1, int _n2, float **_CM, char **_IsX);
     63static int isOptimal(node1_t *U, node1_t *V, int _n1, int _n2, float **_CM, char **_IsX);
     64static int findLoop(node2_t **Loop, int _n1, int _n2, node2_t *_XV, node2_t **_RowsX, node2_t **_ColsX);
     65static void newSol(int _n1, int _n2, node2_t *_XV, char **_IsX, node2_t **_RowsX, node2_t **_ColsX);
     66static void russel(double *S, double *D, int _n1, int _n2, float **_CM, char **_IsX, node2_t **_RowsX, node2_t **_ColsX);
    7367static void addBasicVariable(int minI, int minJ, double *S, double *D,
    7468                             node1_t *PrevUMinI, node1_t *PrevVMinJ,
    75                              node1_t *UHead);
     69                             node1_t *UHead, char **_IsX, node2_t **_RowsX, node2_t **_ColsX);
    7670#if DEBUG_LEVEL > 0
    7771static void printSolution();
    … …  
    10195float emd(signature_t *Signature1, signature_t *Signature2,
    10296          float (*Dist)(feature_t *, feature_t *),
    103           flow_t *Flow, int *FlowSize)
     97          flow_t *Flow, int *FlowSize, int _n1, int _n2)
    10498{
    10599  int itr;
     100  int max_n = (_n1 > _n2) ? _n1 : _n2;
    106101  double totalCost;
    107102  float w;
    108103  node2_t *XP;
    109104  flow_t *FlowP;
    110   node1_t U[MAX_SIG_SIZE1], V[MAX_SIG_SIZE1];
    111 
    112   w = init(Signature1, Signature2, Dist);
     105  node1_t U[max_n], V[max_n];
     106  /* THE COST MATRIX */
     107  float** _CM = new float*[_n1];
     108  char** _IsX = new char*[_n1];
     109  for(int k = 0; k < _n1; ++k)
     110  {
     111    _CM[k] = new float[_n2];
     112    _IsX[k] = new char[_n2];
     113  }
     114  /* THE BASIC VARIABLES VECTOR */ 
     115  node2_t *_XV = new node2_t[max_n*2];
     116  node2_t **_RowsX = new node2_t*[max_n*2];
     117  node2_t **_ColsX = new node2_t*[max_n*2];
     118 
     119  w = init(Signature1, Signature2, Dist, _n1, _n2, _CM, _XV, _IsX, _RowsX, _ColsX);
    113120
    114121#if DEBUG_LEVEL > 1
    … …  
    122129        {
    123130          /* FIND BASIC VARIABLES */
    124           findBasicVariables(U, V);
     131          findBasicVariables(U, V, _n1, _n2, _CM, _IsX);
    125132         
    126133          /* CHECK FOR OPTIMALITY */
    127           if (isOptimal(U, V))
     134          if (isOptimal(U, V, _n1, _n2, _CM, _IsX))
    128135            break;
    129136         
    130137          /* IMPROVE SOLUTION */
    131           newSol();
     138          newSol(_n1, _n2, _XV, _IsX, _RowsX, _ColsX);
    132139         
    133140#if DEBUG_LEVEL > 1
    … …  
    172179#endif
    173180
    174   /* RETURN THE NORMALIZED COST == EMD */
     181  for(int k = 0; k < _n1; ++k)
     182  {
     183    delete[] _CM[k];
     184    delete[] _IsX[k];
     185  }
     186  delete[] _CM;
     187  delete[] _IsX;
     188  delete[] _XV;
     189  delete[] _RowsX;
     190  delete[] _ColsX; 
     191 
     192  /* RETURN THE NORMALIZED COST == EMD */   
    175193  return (float)(totalCost / w);
    176194}
    … …  
    184202**********************/
    185203static float init(signature_t *Signature1, signature_t *Signature2,
    186                   float (*Dist)(feature_t *, feature_t *))
     204                  float (*Dist)(feature_t *, feature_t *), int _n1, int _n2,
     205        float **_CM, node2_t *_XV, char **_IsX, node2_t **_RowsX, node2_t **_ColsX)
    187206{
    188207  int i, j;
     208  int max_n = (_n1 > _n2) ? _n1 : _n2;
    189209  double sSum, dSum, diff;
    190210  feature_t *P1, *P2;
    191   double S[MAX_SIG_SIZE1], D[MAX_SIG_SIZE1];
    192  
    193   _n1 = Signature1->n;
    194   _n2 = Signature2->n;
    195 
    196   if (_n1 > MAX_SIG_SIZE || _n2 > MAX_SIG_SIZE)
    197     {
    198       fprintf(stderr, "emd: Signature size is limited to %d\n", MAX_SIG_SIZE);
    199       exit(1);
    200     }
     211  double S[max_n], D[max_n];
     212
    201213 
    202214  /* COMPUTE THE DISTANCE MATRIX */
    … …  
    257269
    258270  /* FIND INITIAL SOLUTION */
    259   russel(S, D);
     271  russel(S, D, _n1, _n2, _CM, _IsX, _RowsX, _ColsX);
    260272
    261273  _EnterX = _EndX++;  /* AN EMPTY SLOT (ONLY _n1+_n2-1 BASIC VARIABLES) */
    … …  
    268280    findBasicVariables
    269281 **********************/
    270 static void findBasicVariables(node1_t *U, node1_t *V)
     282static void findBasicVariables(node1_t *U, node1_t *V, int _n1, int _n2, float **_CM, char **_IsX)
    271283{
    272284  int i, j, found;
    … …  
    406418    isOptimal
    407419 **********************/
    408 static int isOptimal(node1_t *U, node1_t *V)
     420static int isOptimal(node1_t *U, node1_t *V, int _n1, int _n2, float **_CM, char **_IsX)
    409421{   
    410422  double delta, deltaMin;
    … …  
    451463    newSol
    452464**********************/
    453 static void newSol()
     465static void newSol(int _n1, int _n2, node2_t * _XV, char **_IsX, node2_t **_RowsX, node2_t **_ColsX)
    454466{
    455     int i, j, k;
     467    int i, j, k, max_n = (_n1 > _n2) ? _n1 : _n2;
    456468    double xMin;
    457469    int steps;
    458     node2_t *Loop[2*MAX_SIG_SIZE1], *CurX, *LeaveX;
     470    node2_t *Loop[2*max_n], *CurX, *LeaveX;
    459471 
    460472#if DEBUG_LEVEL > 3
    … …  
    473485
    474486    /* FIND A CHAIN REACTION */
    475     steps = findLoop(Loop);
     487    steps = findLoop(Loop, _n1, _n2, _XV, _RowsX, _ColsX);
    476488
    477489    /* FIND THE LARGEST VALUE IN THE LOOP */
    … …  
    529541    findLoop
    530542**********************/
    531 static int findLoop(node2_t **Loop)
     543static int findLoop(node2_t **Loop, int _n1, int _n2, node2_t *_XV, node2_t **_RowsX, node2_t **_ColsX)
    532544{
    533   int i, steps;
     545  int i, steps, max_n = (_n1 > _n2) ? _n1 : _n2;
    534546  node2_t **CurX, *NewX;
    535   char IsUsed[2*MAX_SIG_SIZE1];
     547  char IsUsed[2*max_n];
    536548 
    537549  for (i=0; i < _n1+_n2; i++)
    … …  
    623635    russel
    624636**********************/
    625 static void russel(double *S, double *D)
     637static void russel(double *S, double *D, int _n1, int _n2, float **_CM, char **_IsX, node2_t **_RowsX, node2_t **_ColsX)
    626638{
    627   int i, j, found, minI, minJ;
     639  int i, j, found, minI, minJ, max_n = (_n1 > _n2) ? _n1 : _n2;
    628640  double deltaMin, oldVal, diff;
    629641  double** Delta = new double*[_n1];
    630642  for(int k = 0; k < _n1; ++k)
    631643    Delta[k] = new double[_n2];
    632   node1_t Ur[MAX_SIG_SIZE1], Vr[MAX_SIG_SIZE1];
     644  node1_t Ur[max_n], Vr[max_n];
    633645  node1_t uHead, *CurU, *PrevU;
    634646  node1_t vHead, *CurV, *PrevV;
    … …  
    720732      /* ADD X[minI][minJ] TO THE BASIS, AND ADJUST SUPPLIES AND COST */
    721733      Remember = PrevUMinI->Next;
    722       addBasicVariable(minI, minJ, S, D, PrevUMinI, PrevVMinJ, &uHead);
     734      addBasicVariable(minI, minJ, S, D, PrevUMinI, PrevVMinJ, &uHead, _IsX, _RowsX, _ColsX);
    723735
    724736      /* UPDATE THE NECESSARY Delta[][] */
    … …  
    779791    } while (uHead.Next != NULL || vHead.Next != NULL);
    780792    for(int k = 0; k < _n1; ++k)
    781       delete [] Delta[k];
    782     delete [] Delta;
     793      delete[] Delta[k];
     794    delete[] Delta;
    783795}
    784796
    … …  
    791803static void addBasicVariable(int minI, int minJ, double *S, double *D,
    792804                             node1_t *PrevUMinI, node1_t *PrevVMinJ,
    793                              node1_t *UHead)
     805                             node1_t *UHead, char **_IsX, node2_t **_RowsX, node2_t **_ColsX)
    794806{
    795807  double T;

  • cpp/frams/model/similarity/EMD/emd.h

    r1044 r1062  
    1717
    1818/* DEFINITIONS */
    19 #define MAX_SIG_SIZE   1000
    2019#define MAX_ITERATIONS 500
    2120//#define INFINITY       1e20

  • cpp/frams/model/similarity/measure-distribution.cpp

    r1054 r1062  
    287287        sig2 = {bin_num, points[1], weights[1]};
    288288
    289         float e = emd(&sig1, &sig2, dist, 0, 0);
     289        float e = emd(&sig1, &sig2, dist, 0, 0, bin_num, bin_num);
    290290       
    291291        for (int i = 0; i < 2; i++)
Note: See TracChangeset for help on using the changeset viewer.