Changeset 1062
- Timestamp:
- 01/26/21 17:41:01 (4 years ago)
- Location:
- cpp/frams/model/similarity
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
cpp/frams/model/similarity/EMD/emd.c
r1061 r1062 30 30 */ 31 31 32 33 #define MAX_SIG_SIZE1 (MAX_SIG_SIZE+1) /* FOR THE POSIBLE DUMMY FEATURE */34 35 32 /* NEW TYPES DEFINITION */ 36 33 … … 53 50 54 51 /* 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 58 53 /* VARIABLES TO HANDLE _X EFFICIENTLY */ 59 54 static 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];62 55 static double _maxW; 63 56 static float _maxC; … … 65 58 /* DECLARATION OF FUNCTIONS */ 66 59 static 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); 62 static void findBasicVariables(node1_t *U, node1_t *V, int _n1, int _n2, float **_CM, char **_IsX); 63 static int isOptimal(node1_t *U, node1_t *V, int _n1, int _n2, float **_CM, char **_IsX); 64 static int findLoop(node2_t **Loop, int _n1, int _n2, node2_t *_XV, node2_t **_RowsX, node2_t **_ColsX); 65 static void newSol(int _n1, int _n2, node2_t *_XV, char **_IsX, node2_t **_RowsX, node2_t **_ColsX); 66 static void russel(double *S, double *D, int _n1, int _n2, float **_CM, char **_IsX, node2_t **_RowsX, node2_t **_ColsX); 73 67 static void addBasicVariable(int minI, int minJ, double *S, double *D, 74 68 node1_t *PrevUMinI, node1_t *PrevVMinJ, 75 node1_t *UHead );69 node1_t *UHead, char **_IsX, node2_t **_RowsX, node2_t **_ColsX); 76 70 #if DEBUG_LEVEL > 0 77 71 static void printSolution(); … … 101 95 float emd(signature_t *Signature1, signature_t *Signature2, 102 96 float (*Dist)(feature_t *, feature_t *), 103 flow_t *Flow, int *FlowSize )97 flow_t *Flow, int *FlowSize, int _n1, int _n2) 104 98 { 105 99 int itr; 100 int max_n = (_n1 > _n2) ? _n1 : _n2; 106 101 double totalCost; 107 102 float w; 108 103 node2_t *XP; 109 104 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); 113 120 114 121 #if DEBUG_LEVEL > 1 … … 122 129 { 123 130 /* FIND BASIC VARIABLES */ 124 findBasicVariables(U, V );131 findBasicVariables(U, V, _n1, _n2, _CM, _IsX); 125 132 126 133 /* CHECK FOR OPTIMALITY */ 127 if (isOptimal(U, V ))134 if (isOptimal(U, V, _n1, _n2, _CM, _IsX)) 128 135 break; 129 136 130 137 /* IMPROVE SOLUTION */ 131 newSol( );138 newSol(_n1, _n2, _XV, _IsX, _RowsX, _ColsX); 132 139 133 140 #if DEBUG_LEVEL > 1 … … 172 179 #endif 173 180 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 */ 175 193 return (float)(totalCost / w); 176 194 } … … 184 202 **********************/ 185 203 static 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) 187 206 { 188 207 int i, j; 208 int max_n = (_n1 > _n2) ? _n1 : _n2; 189 209 double sSum, dSum, diff; 190 210 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 201 213 202 214 /* COMPUTE THE DISTANCE MATRIX */ … … 257 269 258 270 /* FIND INITIAL SOLUTION */ 259 russel(S, D );271 russel(S, D, _n1, _n2, _CM, _IsX, _RowsX, _ColsX); 260 272 261 273 _EnterX = _EndX++; /* AN EMPTY SLOT (ONLY _n1+_n2-1 BASIC VARIABLES) */ … … 268 280 findBasicVariables 269 281 **********************/ 270 static void findBasicVariables(node1_t *U, node1_t *V )282 static void findBasicVariables(node1_t *U, node1_t *V, int _n1, int _n2, float **_CM, char **_IsX) 271 283 { 272 284 int i, j, found; … … 406 418 isOptimal 407 419 **********************/ 408 static int isOptimal(node1_t *U, node1_t *V )420 static int isOptimal(node1_t *U, node1_t *V, int _n1, int _n2, float **_CM, char **_IsX) 409 421 { 410 422 double delta, deltaMin; … … 451 463 newSol 452 464 **********************/ 453 static void newSol( )465 static void newSol(int _n1, int _n2, node2_t * _XV, char **_IsX, node2_t **_RowsX, node2_t **_ColsX) 454 466 { 455 int i, j, k ;467 int i, j, k, max_n = (_n1 > _n2) ? _n1 : _n2; 456 468 double xMin; 457 469 int steps; 458 node2_t *Loop[2* MAX_SIG_SIZE1], *CurX, *LeaveX;470 node2_t *Loop[2*max_n], *CurX, *LeaveX; 459 471 460 472 #if DEBUG_LEVEL > 3 … … 473 485 474 486 /* FIND A CHAIN REACTION */ 475 steps = findLoop(Loop );487 steps = findLoop(Loop, _n1, _n2, _XV, _RowsX, _ColsX); 476 488 477 489 /* FIND THE LARGEST VALUE IN THE LOOP */ … … 529 541 findLoop 530 542 **********************/ 531 static int findLoop(node2_t **Loop )543 static int findLoop(node2_t **Loop, int _n1, int _n2, node2_t *_XV, node2_t **_RowsX, node2_t **_ColsX) 532 544 { 533 int i, steps ;545 int i, steps, max_n = (_n1 > _n2) ? _n1 : _n2; 534 546 node2_t **CurX, *NewX; 535 char IsUsed[2* MAX_SIG_SIZE1];547 char IsUsed[2*max_n]; 536 548 537 549 for (i=0; i < _n1+_n2; i++) … … 623 635 russel 624 636 **********************/ 625 static void russel(double *S, double *D )637 static void russel(double *S, double *D, int _n1, int _n2, float **_CM, char **_IsX, node2_t **_RowsX, node2_t **_ColsX) 626 638 { 627 int i, j, found, minI, minJ ;639 int i, j, found, minI, minJ, max_n = (_n1 > _n2) ? _n1 : _n2; 628 640 double deltaMin, oldVal, diff; 629 641 double** Delta = new double*[_n1]; 630 642 for(int k = 0; k < _n1; ++k) 631 643 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]; 633 645 node1_t uHead, *CurU, *PrevU; 634 646 node1_t vHead, *CurV, *PrevV; … … 720 732 /* ADD X[minI][minJ] TO THE BASIS, AND ADJUST SUPPLIES AND COST */ 721 733 Remember = PrevUMinI->Next; 722 addBasicVariable(minI, minJ, S, D, PrevUMinI, PrevVMinJ, &uHead );734 addBasicVariable(minI, minJ, S, D, PrevUMinI, PrevVMinJ, &uHead, _IsX, _RowsX, _ColsX); 723 735 724 736 /* UPDATE THE NECESSARY Delta[][] */ … … 779 791 } while (uHead.Next != NULL || vHead.Next != NULL); 780 792 for(int k = 0; k < _n1; ++k) 781 delete 782 delete 793 delete[] Delta[k]; 794 delete[] Delta; 783 795 } 784 796 … … 791 803 static void addBasicVariable(int minI, int minJ, double *S, double *D, 792 804 node1_t *PrevUMinI, node1_t *PrevVMinJ, 793 node1_t *UHead )805 node1_t *UHead, char **_IsX, node2_t **_RowsX, node2_t **_ColsX) 794 806 { 795 807 double T; -
cpp/frams/model/similarity/EMD/emd.h
r1044 r1062 17 17 18 18 /* DEFINITIONS */ 19 #define MAX_SIG_SIZE 100020 19 #define MAX_ITERATIONS 500 21 20 //#define INFINITY 1e20 -
cpp/frams/model/similarity/measure-distribution.cpp
r1054 r1062 287 287 sig2 = {bin_num, points[1], weights[1]}; 288 288 289 float e = emd(&sig1, &sig2, dist, 0, 0 );289 float e = emd(&sig1, &sig2, dist, 0, 0, bin_num, bin_num); 290 290 291 291 for (int i = 0; i < 2; i++)
Note: See TracChangeset
for help on using the changeset viewer.