summaryrefslogtreecommitdiff
path: root/match
diff options
context:
space:
mode:
Diffstat (limited to 'match')
-rw-r--r--match/match.c283
-rw-r--r--match/match.h6
-rw-r--r--match/test.c14
3 files changed, 174 insertions, 129 deletions
diff --git a/match/match.c b/match/match.c
index ebeadcd..dbb14ba 100644
--- a/match/match.c
+++ b/match/match.c
@@ -38,13 +38,13 @@
38typedef unsigned short col_t[1]; 38typedef unsigned short col_t[1];
39typedef unsigned short mat_t[DIM_FINGER]; 39typedef unsigned short mat_t[DIM_FINGER];
40 40
41#define GET1(m, x) ((m[0]>>(x))&1U) 41#define GET1(m, x) ((m[0] >> (x)) & 1U)
42#define SET1(m, x) (m[0]|=(1U<<(x))) 42#define SET1(m, x) (m[0] |= (1U << (x)))
43#define CLEAR1(m, x) (m[0]&=~(1U<<(x))) 43#define CLEAR1(m, x) (m[0] &= ~(1U << (x)))
44 44
45#define GET2(m, row, col) ((m[col]>>(row))&1U) 45#define GET2(m, row, col) ((m[col] >> (row)) & 1U)
46#define SET2(m, row, col) (m[col]|=(1U<<(row))) 46#define SET2(m, row, col) (m[col] |= (1U << (row)))
47#define CLEAR2(m, row, col) (m[col]&=~(1U<<(row))) 47#define CLEAR2(m, row, col) (m[col] &= ~(1U << (row)))
48 48
49/********************************************************/ 49/********************************************************/
50 50
@@ -64,11 +64,21 @@ static void buildixvector(int *ix, mat_t mstar, int nrows, int ncols)
64 64
65/********************************************************/ 65/********************************************************/
66 66
67static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin); 67static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
68static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin); 68 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
69static void step3(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin); 69 int dmin);
70static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin, int row, int col); 70static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
71static void step5(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin); 71 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
72 int dmin);
73static void step3(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
74 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
75 int dmin);
76static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
77 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
78 int dmin, int row, int col);
79static void step5(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
80 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
81 int dmin);
72 82
73static void ixoptimal(int *ix, float *mdist, int nrows, int ncols) 83static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
74{ 84{
@@ -84,162 +94,194 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
84 memset(nmstar, 0, sizeof(mat_t)); 94 memset(nmstar, 0, sizeof(mat_t));
85 95
86 /* initialization */ 96 /* initialization */
87 for(row=0; row<nrows; row++) 97 for (row = 0; row < nrows; row++)
88 ix[row] = -1; 98 ix[row] = -1;
89 99
90 mdistEnd = mdist + nrows * ncols; 100 mdistEnd = mdist + nrows * ncols;
91 101
92 /* preliminary steps */ 102 /* preliminary steps */
93 if(nrows <= ncols) { 103 if (nrows <= ncols) {
94 dmin = nrows; 104 dmin = nrows;
95 105
96 for(row=0; row<nrows; row++) { 106 for (row = 0; row < nrows; row++) {
97 /* find the smallest element in the row */ 107 /* find the smallest element in the row */
98 mdistTemp = mdist + row; 108 mdistTemp = mdist + row;
99 minValue = *mdistTemp; 109 minValue = *mdistTemp;
100 mdistTemp += nrows; 110 mdistTemp += nrows;
101 while(mdistTemp < mdistEnd) { 111 while (mdistTemp < mdistEnd) {
102 value = *mdistTemp; 112 value = *mdistTemp;
103 if(value < minValue) 113 if (value < minValue)
104 minValue = value; 114 minValue = value;
105 mdistTemp += nrows; 115 mdistTemp += nrows;
106 } 116 }
107 117
108 /* subtract the smallest element from each element of the row */ 118 /* subtract the smallest element from each element
119 of the row */
109 mdistTemp = mdist + row; 120 mdistTemp = mdist + row;
110 while(mdistTemp < mdistEnd) { 121 while (mdistTemp < mdistEnd) {
111 *mdistTemp -= minValue; 122 *mdistTemp -= minValue;
112 mdistTemp += nrows; 123 mdistTemp += nrows;
113 } 124 }
114 } 125 }
115 126
116 /* Steps 1 and 2a */ 127 /* Steps 1 and 2a */
117 for(row=0; row<nrows; row++) 128 for (row = 0; row < nrows; row++) {
118 for(col=0; col<ncols; col++) 129 for (col = 0; col < ncols; col++) {
119 if(mdist[row + nrows*col] == 0) 130 if (mdist[row + nrows * col] != 0)
120 if(!GET1(ccol, col)) { 131 continue;
121 SET2(mstar, row, col); 132 if (GET1(ccol, col))
122 SET1(ccol, col); 133 continue;
123 break; 134 SET2(mstar, row, col);
124 } 135 SET1(ccol, col);
136 break;
137 }
138 }
125 } else { 139 } else {
126 dmin = ncols; 140 dmin = ncols;
127 141
128 for(col=0; col<ncols; col++) { 142 for (col = 0; col < ncols; col++) {
129 /* find the smallest element in the column */ 143 /* find the smallest element in the column */
130 mdistTemp = mdist + nrows*col; 144 mdistTemp = mdist + nrows*col;
131 columnEnd = mdistTemp + nrows; 145 columnEnd = mdistTemp + nrows;
132 146
133 minValue = *mdistTemp++; 147 minValue = *mdistTemp++;
134 while(mdistTemp < columnEnd) { 148 while (mdistTemp < columnEnd) {
135 value = *mdistTemp++; 149 value = *mdistTemp++;
136 if(value < minValue) 150 if (value < minValue)
137 minValue = value; 151 minValue = value;
138 } 152 }
139 153
140 /* subtract the smallest element from each element of the column */ 154 /* subtract the smallest element from each element
155 of the column */
141 mdistTemp = mdist + nrows*col; 156 mdistTemp = mdist + nrows*col;
142 while(mdistTemp < columnEnd) 157 while (mdistTemp < columnEnd)
143 *mdistTemp++ -= minValue; 158 *mdistTemp++ -= minValue;
144 } 159 }
145 160
146 /* Steps 1 and 2a */ 161 /* Steps 1 and 2a */
147 for(col=0; col<ncols; col++) 162 for (col = 0; col < ncols; col++) {
148 for(row=0; row<nrows; row++) 163 for (row = 0; row < nrows; row++) {
149 if(mdist[row + nrows*col] == 0) 164 if (mdist[row + nrows * col] != 0)
150 if(!GET1(crow, row)) { 165 continue;
151 SET2(mstar, row, col); 166 if (GET1(crow, row))
152 SET1(ccol, col); 167 continue;
153 SET1(crow, row); 168 SET2(mstar, row, col);
154 break; 169 SET1(ccol, col);
155 } 170 SET1(crow, row);
171 break;
172 }
173 }
156 memset(crow, 0, sizeof(col_t)); 174 memset(crow, 0, sizeof(col_t));
157 } 175 }
158 176
159 /* move to step 2b */ 177 /* move to step 2b */
160 step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 178 step2b(ix, mdist, mstar, nmstar,
179 mprime, ccol, crow, nrows, ncols,
180 dmin);
161} 181}
162 182
163/********************************************************/ 183/********************************************************/
164static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin) 184static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
185 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
186 int dmin)
165{ 187{
166 int col, row; 188 int col, row;
167 189
168 /* cover every column containing a starred zero */ 190 /* cover every column containing a starred zero */
169 for(col = 0; col < ncols; col++) { 191 for (col = 0; col < ncols; col++) {
170 for(row = 0; row < nrows; row++) { 192 for (row = 0; row < nrows; row++) {
171 if(GET2(mstar, row, col)) { 193 if (!GET2(mstar, row, col))
172 SET1(ccol, col); 194 continue;
173 break; 195 SET1(ccol, col);
174 } 196 break;
175 } 197 }
176 } 198 }
177 199
178 /* move to step 3 */ 200 /* move to step 3 */
179 step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 201 step2b(ix, mdist, mstar, nmstar,
202 mprime, ccol, crow, nrows, ncols,
203 dmin);
180} 204}
181 205
182/********************************************************/ 206/********************************************************/
183static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin) 207static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
208 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
209 int dmin)
184{ 210{
185 int col, ncc; 211 int col, ncc;
186 212
187 /* count covered columns */ 213 /* count covered columns */
188 ncc = 0; 214 ncc = 0;
189 for(col=0; col<ncols; col++) 215 for (col = 0; col < ncols; col++)
190 if(GET1(ccol, col)) 216 if (GET1(ccol, col))
191 ncc++; 217 ncc++;
192 218
193 if(ncc == dmin) { 219 if (ncc == dmin) {
194 /* algorithm finished */ 220 /* algorithm finished */
195 buildixvector(ix, mstar, nrows, ncols); 221 buildixvector(ix, mstar, nrows, ncols);
196 } else { 222 } else {
197 /* move to step 3 */ 223 /* move to step 3 */
198 step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 224 step3(ix, mdist, mstar, nmstar,
225 mprime, ccol, crow, nrows, ncols,
226 dmin);
199 } 227 }
200 228
201} 229}
202 230
203/********************************************************/ 231/********************************************************/
204static void step3(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin) 232static void step3(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
233 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
234 int dmin)
205{ 235{
206 bool zerosFound; 236 int zerosFound;
207 int row, col, cstar; 237 int row, col, cstar;
208 238
209 zerosFound = 1; 239 zerosFound = 1;
210 while(zerosFound) { 240 while (zerosFound) {
211 zerosFound = 0; 241 zerosFound = 0;
212 for(col=0; col<ncols; col++) 242 for (col = 0; col < ncols; col++) {
213 if(!GET1(ccol,col)) 243 if (GET1(ccol, col))
214 for(row=0; row<nrows; row++) 244 continue;
215 if((!GET1(crow, row)) && (mdist[row + nrows*col] == 0)) { 245 for (row = 0; row < nrows; row++) {
216 /* prime zero */ 246 if (mdist[row + nrows * col] != 0)
217 SET2(mprime, row, col); 247 continue;
218 248 if (GET1(crow, row))
219 /* find starred zero in current row */ 249 continue;
220 for(cstar=0; cstar<ncols; cstar++) 250
221 if(GET2(mstar, row, cstar)) 251 /* prime zero */
222 break; 252 SET2(mprime, row, col);
223 253
224 if(cstar == ncols) { /* no starred zero found */ 254 /* find starred zero in current row */
225 /* move to step 4 */ 255 for (cstar = 0; cstar < ncols; cstar++)
226 step4(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin, row, col); 256 if (GET2(mstar, row, cstar))
227 return; 257 break;
228 } else { 258
229 SET1(crow, row); 259 if (cstar == ncols) { /* no starred zero */
230 CLEAR1(ccol, cstar); 260 /* move to step 4 */
231 zerosFound = 1; 261 step4(ix, mdist, mstar, nmstar,
232 break; 262 mprime, ccol, crow, nrows, ncols,
233 } 263 dmin, row, col);
234 } 264 return;
265 } else {
266 SET1(crow, row);
267 CLEAR1(ccol, cstar);
268 zerosFound = 1;
269 break;
270 }
271 }
272 }
235 } 273 }
236 274
237 /* move to step 5 */ 275 /* move to step 5 */
238 step5(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 276 step5(ix, mdist, mstar, nmstar,
277 mprime, ccol, crow, nrows, ncols,
278 dmin);
239} 279}
240 280
241/********************************************************/ 281/********************************************************/
242static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin, int row, int col) 282static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
283 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
284 int dmin, int row, int col)
243{ 285{
244 int n, rstar, cstar, primeRow, primeCol; 286 int n, rstar, cstar, primeRow, primeCol;
245 287
@@ -251,18 +293,18 @@ static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime
251 293
252 /* find starred zero in current column */ 294 /* find starred zero in current column */
253 cstar = col; 295 cstar = col;
254 for(rstar=0; rstar<nrows; rstar++) 296 for (rstar = 0; rstar < nrows; rstar++)
255 if(GET2(mstar, rstar, cstar)) 297 if (GET2(mstar, rstar, cstar))
256 break; 298 break;
257 299
258 while(rstar<nrows) { 300 while (rstar < nrows) {
259 /* unstar the starred zero */ 301 /* unstar the starred zero */
260 CLEAR2(nmstar, rstar, cstar); 302 CLEAR2(nmstar, rstar, cstar);
261 303
262 /* find primed zero in current row */ 304 /* find primed zero in current row */
263 primeRow = rstar; 305 primeRow = rstar;
264 for(primeCol=0; primeCol<ncols; primeCol++) 306 for (primeCol = 0; primeCol < ncols; primeCol++)
265 if(GET2(mprime, primeRow, primeCol)) 307 if (GET2(mprime, primeRow, primeCol))
266 break; 308 break;
267 309
268 /* star the primed zero */ 310 /* star the primed zero */
@@ -270,8 +312,8 @@ static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime
270 312
271 /* find starred zero in current column */ 313 /* find starred zero in current column */
272 cstar = primeCol; 314 cstar = primeCol;
273 for(rstar=0; rstar<nrows; rstar++) 315 for (rstar = 0; rstar < nrows; rstar++)
274 if(GET2(mstar, rstar, cstar)) 316 if (GET2(mstar, rstar, cstar))
275 break; 317 break;
276 } 318 }
277 319
@@ -282,49 +324,60 @@ static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime
282 memset(crow, 0, sizeof(col_t)); 324 memset(crow, 0, sizeof(col_t));
283 325
284 /* move to step 2a */ 326 /* move to step 2a */
285 step2a(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 327 step2a(ix, mdist, mstar, nmstar,
328 mprime, ccol, crow, nrows, ncols,
329 dmin);
286} 330}
287 331
288/********************************************************/ 332/********************************************************/
289static void step5(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin) 333static void step5(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
334 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
335 int dmin)
290{ 336{
291 float h = 0, value; 337 float h = 0, value;
292 int row, col, found = 0; 338 int row, col, found = 0;
293 339
294 /* find smallest uncovered element h */ 340 /* find smallest uncovered element h */
295 for(row=0; row<nrows; row++) 341 for (row = 0; row < nrows; row++) {
296 if(!GET1(crow, row)) 342 if (GET1(crow, row))
297 for(col=0; col<ncols; col++) 343 continue;
298 if(!GET1(ccol,col)) { 344 for (col = 0; col < ncols; col++) {
299 value = mdist[row + nrows*col]; 345 if (GET1(ccol, col))
300 if(!found || value < h) { 346 continue;
301 h = value; 347 value = mdist[row + nrows * col];
302 found = 1; 348 if (!found || value < h) {
303 } 349 h = value;
304 } 350 found = 1;
351 }
352 }
353 }
305 354
306 /* where to go if nothing uncovered? */ 355 /* where to go if nothing uncovered? */
307 if (!found) 356 if (!found)
308 return; 357 return;
309 358
310 /* add h to each covered row */ 359 /* add h to each covered row */
311 for(row=0; row<nrows; row++) 360 for (row = 0; row < nrows; row++) {
312 if(GET1(crow, row)) 361 if (!GET1(crow, row))
313 for(col=0; col<ncols; col++) 362 continue;
314 mdist[row + nrows*col] += h; 363 for (col = 0; col < ncols; col++)
364 mdist[row + nrows * col] += h;
365 }
315 366
316 /* subtract h from each uncovered column */ 367 /* subtract h from each uncovered column */
317 for(col=0; col<ncols; col++) 368 for (col = 0; col < ncols; col++) {
318 if(!GET1(ccol,col)) 369 if (GET1(ccol, col))
319 for(row=0; row<nrows; row++) 370 continue;
320 mdist[row + nrows*col] -= h; 371 for (row = 0; row < nrows; row++)
372 mdist[row + nrows * col] -= h;
373 }
321 374
322 /* move to step 3 */ 375 /* move to step 3 */
323 step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 376 step3(ix, mdist, mstar, nmstar,
377 mprime, ccol, crow, nrows, ncols,
378 dmin);
324} 379}
325 380
326////////////////////////////////////////////////////////
327
328void match_fingers(int ix[DIM_FINGER], float A[DIM2_FINGER], int nrow, int ncol) 381void match_fingers(int ix[DIM_FINGER], float A[DIM2_FINGER], int nrow, int ncol)
329{ 382{
330 int i; 383 int i;
@@ -337,5 +390,3 @@ void match_fingers(int ix[DIM_FINGER], float A[DIM2_FINGER], int nrow, int ncol)
337 ixoptimal(ix, A, nrow, ncol); 390 ixoptimal(ix, A, nrow, ncol);
338} 391}
339 392
340////////////////////////////////////////////////////////
341
diff --git a/match/match.h b/match/match.h
index 61ac72d..620d046 100644
--- a/match/match.h
+++ b/match/match.h
@@ -34,13 +34,7 @@
34#define MIN(a, b) ((a) < (b) ? (a) : (b)) 34#define MIN(a, b) ((a) < (b) ? (a) : (b))
35#define MAX(a, b) ((a) < (b) ? (b) : (a)) 35#define MAX(a, b) ((a) < (b) ? (b) : (a))
36 36
37typedef int bool;
38
39////////////////////////////////////////////////////////
40
41void match_fingers(int index[DIM_FINGER], float A[DIM2_FINGER], 37void match_fingers(int index[DIM_FINGER], float A[DIM2_FINGER],
42 int nrow, int ncol); 38 int nrow, int ncol);
43 39
44////////////////////////////////////////////////////////
45
46#endif 40#endif
diff --git a/match/test.c b/match/test.c
index e60e19a..192f969 100644
--- a/match/test.c
+++ b/match/test.c
@@ -53,7 +53,7 @@ static void test1()
53 53
54static void test2() 54static void test2()
55{ 55{
56 float A[]={ 56 float A[] = {
57 0.000000, 57 0.000000,
58 4534330.000000, 58 4534330.000000,
59 22653552.000000, 59 22653552.000000,
@@ -88,12 +88,12 @@ static void test2()
88 88
89static void speed1() 89static void speed1()
90{ 90{
91 // column-by-column matrix 91 /* column-by-column matrix */
92 float A[DIM2_FINGER]; 92 float A[DIM2_FINGER];
93 float x1[DIM_FINGER]={1,5,2,3,4,5,6,7,8}; 93 float x1[DIM_FINGER] = { 1, 5, 2, 3, 4, 5, 6, 7, 8 };
94 float y1[DIM_FINGER]={1,5,2,3,4,5.1,6,7,8}; 94 float y1[DIM_FINGER] = { 1, 5, 2, 3, 4, 5.1, 6, 7, 8 };
95 float x2[DIM_FINGER]={1.1,3,2,4,5,6,7,8}; 95 float x2[DIM_FINGER] = { 1.1, 3, 2, 4, 5, 6, 7, 8 };
96 float y2[DIM_FINGER]={1,3,2,4,5,6,7,8}; 96 float y2[DIM_FINGER] = { 1, 3, 2, 4, 5, 6, 7, 8 };
97 int index[DIM_FINGER]; 97 int index[DIM_FINGER];
98 int n1 = 4; 98 int n1 = 4;
99 int n2 = 7; 99 int n2 = 7;
@@ -121,7 +121,7 @@ static void speed1()
121 121
122} 122}
123 123
124int main(int argc,char* argv[]) 124int main(int argc, char *argv[])
125{ 125{
126 printf("test1\n"); 126 printf("test1\n");
127 test1(); 127 test1();
generated by cgit v1.2.3 (git 2.39.1) at 2026-09-20 22:58:40 +0000