images/sig-cmp-gen.h

   1 #ifdef CONFIG_UCW_CLEAN_ABI
   2 #define image_signatures_dist ucw_image_signatures_dist
   3 #define image_signatures_dist_explain ucw_image_signatures_dist_explain
   4 #endif
   5
   6 #ifdef EXPLAIN
   7 #  define MSG(x...) do{ line += sprintf(line, x); }while(0)
   8 #  define LINE do{ line = buf; msg(line, param); }while(0)
   9
  10 static void explain_signature(struct image_signature *sig, void (*msg)(byte *text, void *param), void *param)
  11 {
  12   byte buf[1024], *line = buf;
  13   MSG("signature: flags=0x%x df=%u dh=%u f=(%u", sig->flags, sig->df, sig->dh, sig->vec.f[0]);
  14   for (uint i = 1; i < IMAGE_VEC_F; i++)
  15     MSG(" %u", sig->vec.f[i]);
  16   MSG(")");
  17   LINE;
  18   for (uint j = 0; j < sig->len; j++)
  19     {
  20       struct image_region *reg = sig->reg + j;
  21       MSG("region %u: wa=%u wb=%u f=(%u", j, reg->wa, reg->wb, reg->f[0]);
  22       for (uint i = 1; i < IMAGE_VEC_F; i++)
  23         MSG(" %u", reg->f[i]);
  24       MSG(") h=(%u", reg->h[0]);
  25       for (uint i = 1; i < IMAGE_REG_H; i++)
  26         MSG(" %u", reg->h[i]);
  27       MSG(")");
  28       LINE;
  29     }
  30 }
  31
  32 #else
  33 #  define MSG(x...) do{}while(0)
  34 #  define LINE do{}while(0)
  35 #endif
  36
  37 #define MSGL(x...) do{ MSG(x); LINE; }while(0)
  38
  39 #ifndef EXPLAIN
  40 static uint image_signatures_dist_integrated(struct image_signature *sig1, struct image_signature *sig2)
  41 #else
  42 static uint image_signatures_dist_integrated_explain(struct image_signature *sig1, struct image_signature *sig2, void (*msg)(byte *text, void *param), void *param)
  43 #endif
  44 {
  45   uint dist[IMAGE_REG_MAX * IMAGE_REG_MAX], p[IMAGE_REG_MAX], q[IMAGE_REG_MAX];
  46   uint n, i, j, k, l, s, d;
  47   struct image_region *reg1, *reg2;
  48 #ifdef EXPLAIN
  49   byte buf[1024], *line = buf;
  50   MSGL("Integrated matching");
  51   explain_signature(sig1, msg, param);
  52   explain_signature(sig2, msg, param);
  53 #endif
  54
  55   /* FIXME: do not mux textured and non-textured images (should be split in clusters tree) */
  56   if ((sig1->flags ^ sig2->flags) & IMAGE_SIG_TEXTURED)
  57     {
  58       MSGL("Textured vs non-textured");
  59       return ~0U;
  60     }
  61
  62   /* Compute distance matrix */
  63   n = 0;
  64   MSGL("Distance matrix:");
  65   /* ... for non-textured images */
  66   if (!((sig1->flags | sig2->flags) & IMAGE_SIG_TEXTURED))
  67     for (j = 0, reg2 = sig2->reg; j < sig2->len; j++, reg2++)
  68       for (i = 0, reg1 = sig1->reg; i < sig1->len; i++, reg1++)
  69         {
  70           uint dt = 0, ds = 0, dp = 0, d;
  71           for (uint i = 0; i < IMAGE_VEC_F; i++)
  72             dt += image_sig_cmp_features_weights[i] * isqr((int)reg1->f[i] - (int)reg2->f[i]);
  73           for (uint i = 0; i < 3; i++)
  74             ds += image_sig_cmp_features_weights[IMAGE_VEC_F + i] * isqr((int)reg1->h[i] - (int)reg2->h[i]);
  75           for (uint i = 3; i < 5; i++)
  76             dp += image_sig_cmp_features_weights[IMAGE_VEC_F + i] * isqr((int)reg1->h[i] - (int)reg2->h[i]);
  77 #if 0
  78           int x1, y1, x2, y2;
  79           if (sig1->cols > sig1->rows)
  80             {
  81               x1 = reg1->h[3];
  82               y1 = ((int)reg1->h[4] - 64) * (int)sig1->rows / (int)sig1->cols + 64;
  83             }
  84           else
  85             {
  86               y1 = reg1->h[4];
  87               x1 = ((int)reg1->h[3] - 64) * (int)sig1->cols / (int)sig1->rows + 64;
  88             }
  89           if (sig2->cols > sig2->rows)
  90             {
  91               x2 = reg2->h[3];
  92               y2 = ((int)reg2->h[4] - 64) * (int)sig2->rows / (int)sig2->cols + 64;
  93             }
  94           else
  95             {
  96               y2 = reg2->h[4];
  97               x2 = ((int)reg2->h[3] - 64) * (int)sig2->cols / (int)sig2->rows + 64;
  98             }
  99           MSGL("%d %d %d %d", x1, y1, x2, y2);
 100           dp = image_sig_cmp_features_weights[IMAGE_VEC_F + 3] * isqr(x1 - x2) +
 101                image_sig_cmp_features_weights[IMAGE_VEC_F + 4] * isqr(y1 - y2);
 102 #endif
 103 #if 0
 104           d = dt * (4 + MIN(8, (ds >> 12))) * (4 + MIN(8, (dp >> 10))) + (ds >> 11) + (dp >> 10);
 105           MSG("[%u, %u] d=%u=(%u * %u * %u + %u + %u) dt=%u ds=%u dp=%u df=(%d", i, j, d,
 106               dt, 4 + MIN(8, (ds >> 12)), 4 + MIN(8, dp >> 10), ds >> 11, dp >> 10, dt, ds, dp, (int)reg1->f[0] - (int)reg2->f[0]);
 107 #endif
 108 #if 1
 109           d = dt;
 110           if (ds < 1000)
 111             d = d * 4;
 112           else if (ds < 4000)
 113             d = d * 6 + 8;
 114           else if (ds < 10000)
 115             d = d * 8 + 20;
 116           else if (ds < 50000)
 117             d = d * 10 + 50;
 118           else
 119             d = d * 12 + 100;
 120           if (dp < 1000)
 121             d = d * 2;
 122           else if (dp < 4000)
 123             d = d * 3 + 100;
 124           else if (dp < 10000)
 125             d = d * 4 + 800;
 126           else
 127             d = d * 5 + 3000;
 128 #endif
 129           dist[n++] = (d << 8) + i + (j << 4);
 130           MSG("[%u, %u] d=%u dt=%u ds=%u dp=%u df=(%d", i, j, d, dt, ds, dp, (int)reg1->f[0] - (int)reg2->f[0]);
 131 #ifdef EXPLAIN
 132           for (uint i = 1; i < IMAGE_VEC_F; i++)
 133             MSG(" %d", (int)reg1->f[i] - (int)reg2->f[i]);
 134           MSG(") dh=(%d", (int)reg1->h[0] - (int)reg2->h[0]);
 135           for (uint i = 1; i < IMAGE_REG_H; i++)
 136             MSG(" %d", (int)reg1->h[i] - (int)reg2->h[i]);
 137           MSGL(")");
 138 #endif
 139         }
 140   /* ... for textured images (ignore shape properties) */
 141   else
 142     for (j = 0, reg2 = sig2->reg; j < sig2->len; j++, reg2++)
 143       for (i = 0, reg1 = sig1->reg; i < sig1->len; i++, reg1++)
 144         {
 145           uint dt = 0;
 146           for (uint i = 0; i < IMAGE_VEC_F; i++)
 147             dt += image_sig_cmp_features_weights[i] * isqr((int)reg1->f[i] - (int)reg2->f[i]);
 148           dist[n++] = (dt << 12) + i + (j << 4);
 149 #ifdef EXPLAIN
 150           MSG("[%u, %u] dt=%u df=(%d", i, j, dt, (int)reg1->f[0] - (int)reg2->f[0]);
 151           for (uint i = 1; i < IMAGE_VEC_F; i++)
 152             MSG(" %d", (int)reg1->f[i] - (int)reg2->f[i]);
 153           MSGL(")");
 154 #endif
 155         }
 156
 157   /* One or both signatures have no regions */
 158   if (!n)
 159     return ~0U;
 160
 161   /* Get percentages */
 162   for (i = 0, reg1 = sig1->reg; i < sig1->len; i++, reg1++)
 163     p[i] = reg1->wb;
 164   for (i = 0, reg2 = sig2->reg; i < sig2->len; i++, reg2++)
 165     q[i] = reg2->wb;
 166
 167   /* Sort entries in distance matrix */
 168   image_signatures_dist_integrated_sort(dist, n);
 169
 170   /* Compute significance matrix and resulting distance */
 171   uint sum = 0;
 172   MSGL("Significance matrix:");
 173   for (k = 0, l = 128; l; k++)
 174     {
 175       i = dist[k] & 15;
 176       j = (dist[k] >> 4) & 15;
 177       d = dist[k] >> 8;
 178       if (p[i] <= q[j])
 179         {
 180           s = p[i];
 181           q[j] -= p[i];
 182           p[i] = 0;
 183         }
 184       else
 185         {
 186           s = q[j];
 187           p[i] -= q[j];
 188           q[j] = 0;
 189         }
 190       l -= s;
 191       sum += s * d;
 192 #ifdef EXPLAIN
 193       reg1 = sig1->reg + i;
 194       reg2 = sig2->reg + j;
 195       MSG("[%u, %u] s=%u d=%u df=(%d", i, j, s, d, (int)reg1->f[0] - (int)reg2->f[0]);
 196       for (uint i = 1; i < IMAGE_VEC_F; i++)
 197         MSG(" %d", (int)reg1->f[i] - (int)reg2->f[i]);
 198       if (!((sig1->flags | sig2->flags) & IMAGE_SIG_TEXTURED))
 199         {
 200           MSG(") dh=(%d", (int)reg1->h[0] - (int)reg2->h[0]);
 201           for (uint i = 1; i < IMAGE_REG_H; i++)
 202             MSG(" %d", (int)reg1->h[i] - (int)reg2->h[i]);
 203         }
 204       MSGL(")");
 205 #endif
 206     }
 207
 208   d = sum / 32;
 209
 210   uint a = sig1->cols * sig2->rows;
 211   uint b = sig1->rows * sig2->cols;
 212   if (a < 2 * b && b < 2 * a)
 213     d = d * 2;
 214   else if (a < 4 * b && b < 4 * a)
 215     d = d * 3;
 216   else
 217     d = d * 5;
 218
 219   a = sig1->cols * sig1->rows;
 220   b = sig2->cols * sig2->rows;
 221
 222   if ((a < 1000 && b > 5000) || (b < 1000 && a > 5000))
 223     d = d * 2;
 224   else if ((a < 5000 && b > 20000) || (b < 5000 && a > 20000))
 225     d = d * 3 / 2;
 226
 227   return d;
 228 }
 229
 230 #ifndef EXPLAIN
 231 static uint image_signatures_dist_fuzzy(struct image_signature *sig1, struct image_signature *sig2)
 232 #else
 233 static uint image_signatures_dist_fuzzy_explain(struct image_signature *sig1, struct image_signature *sig2, void (*msg)(byte *text, void *param), void *param)
 234 #endif
 235 {
 236 #ifdef EXPLAIN
 237   byte buf[1024], *line = buf;
 238   MSGL("Fuzzy matching");
 239   explain_signature(sig1, msg, param);
 240   explain_signature(sig2, msg, param);
 241 #endif
 242
 243   /* FIXME: do not mux textured and non-textured images (should be split in clusters tree) */
 244   if ((sig1->flags ^ sig2->flags) & IMAGE_SIG_TEXTURED)
 245     {
 246       MSGL("Textured vs non-textured");
 247       return ~0U;
 248     }
 249
 250   uint cnt1 = sig1->len;
 251   uint cnt2 = sig2->len;
 252   struct image_region *reg1 = sig1->reg;
 253   struct image_region *reg2 = sig2->reg;
 254   uint mf[IMAGE_REG_MAX][IMAGE_REG_MAX], mh[IMAGE_REG_MAX][IMAGE_REG_MAX];
 255   uint lf[IMAGE_REG_MAX * 2], lh[IMAGE_REG_MAX * 2];
 256   uint df = sig1->df + sig2->df, dh = sig1->dh + sig2->dh;
 257
 258   /* Compute distance matrix */
 259   for (uint i = 0; i < cnt1; i++)
 260     for (uint j = 0; j < cnt2; j++)
 261       {
 262         uint d = 0;
 263         for (uint k = 0; k < IMAGE_VEC_F; k++)
 264           {
 265             int dif = reg1[i].f[k] - reg2[j].f[k];
 266             d += image_sig_cmp_features_weights[k] * dif * dif;
 267           }
 268         mf[i][j] = d;
 269         d = 0;
 270         for (uint k = 0; k < IMAGE_REG_H; k++)
 271           {
 272             int dif = reg1[i].h[k] - reg2[j].h[k];
 273             d += image_sig_cmp_features_weights[k + IMAGE_VEC_F] * dif * dif;
 274           }
 275         mh[i][j] = d;
 276       }
 277
 278   uint lfs = 0, lhs = 0;
 279   for (uint i = 0; i < cnt1; i++)
 280     {
 281       uint f = mf[i][0], h = mh[i][0];
 282       for (uint j = 1; j < cnt2; j++)
 283         {
 284           f = MIN(f, mf[i][j]);
 285           h = MIN(h, mh[i][j]);
 286         }
 287       lf[i] = (df * 0x10000) / (df + fast_sqrt_u32(f));
 288       lh[i] = (dh * 0x10000) / (dh + fast_sqrt_u32(h));
 289       lfs += lf[i] * (6 * reg1[i].wa + 2 * reg1[i].wb);
 290       lhs += lh[i] * reg1[i].wa;
 291     }
 292   for (uint i = 0; i < cnt2; i++)
 293     {
 294       uint f = mf[0][i], h = mh[0][i];
 295       for (uint j = 1; j < cnt1; j++)
 296         {
 297           f = MIN(f, mf[j][i]);
 298           h = MIN(h, mh[j][i]);
 299         }
 300       lf[i + cnt1] = (df * 0x10000) / (df + fast_sqrt_u32(f));
 301       lh[i + cnt1] = (dh * 0x10000) / (dh + fast_sqrt_u32(h));
 302       lfs += lf[i] * (6 * reg2[i].wa + 2 * reg2[i].wb);
 303       lhs += lh[i] * reg2[i].wa;
 304     }
 305
 306   uint measure = lfs * 6 + lhs * 2 * 8;
 307
 308 #ifdef EXPLAIN
 309   /* Display similarity vectors */
 310   MSG("Lf=(");
 311   for (uint i = 0; i < cnt1 + cnt2; i++)
 312     {
 313       if (i)
 314         MSG(" ");
 315       if (i == cnt1)
 316         MSG("~ ");
 317       MSG("%.4f", (double)lf[i] / 0x10000);
 318     }
 319   MSGL(")");
 320   MSG("Lh=(");
 321   for (uint i = 0; i < cnt1 + cnt2; i++)
 322     {
 323       if (i)
 324         MSG(" ");
 325       if (i == cnt1)
 326         MSG("~ ");
 327       MSG("%.4f", (double)lh[i] / 0x10000);
 328     }
 329   MSGL(")");
 330   MSGL("Lfm=%.4f", lfs / (double)(1 << (3 + 8 + 16)));
 331   MSGL("Lhm=%.4f", lhs / (double)(1 << (8 + 16)));
 332   MSGL("measure=%.4f", measure / (double)(1 << (3 + 3 + 8 + 16)));
 333 #endif
 334
 335   return (1 << (3 + 3 + 8 + 16)) - measure;
 336 }
 337
 338 #ifndef EXPLAIN
 339 static uint image_signatures_dist_average(struct image_signature *sig1, struct image_signature *sig2)
 340 #else
 341 static uint image_signatures_dist_average_explain(struct image_signature *sig1, struct image_signature *sig2, void (*msg)(byte *text, void *param), void *param)
 342 #endif
 343 {
 344 #ifdef EXPLAIN
 345   byte buf[1024], *line = buf;
 346   MSGL("Average matching");
 347 #endif
 348
 349   uint dist = 0;
 350   for (uint i = 0; i < IMAGE_VEC_F; i++)
 351     {
 352       uint d = image_sig_cmp_features_weights[0] * isqr((int)sig1->vec.f[i] - (int)sig2->vec.f[i]);
 353       MSGL("feature %u: d=%u (%u %u)", i, d, sig1->vec.f[i], sig2->vec.f[i]);
 354       dist += d;
 355     }
 356
 357   MSGL("dist=%u", dist);
 358   return dist;
 359 }
 360
 361 #ifndef EXPLAIN
 362 #define CALL(x) image_signatures_dist_##x(sig1, sig2)
 363 uint image_signatures_dist(struct image_signature *sig1, struct image_signature *sig2)
 364 #else
 365 #define CALL(x) image_signatures_dist_##x##_explain(sig1, sig2, msg, param)
 366 uint image_signatures_dist_explain(struct image_signature *sig1, struct image_signature *sig2, void (*msg)(byte *text, void *param), void *param)
 367 #endif
 368 {
 369   if (!sig1->len)
 370     return CALL(average);
 371   else
 372     switch (image_sig_compare_method)
 373       {
 374         case 0:
 375           return CALL(integrated);
 376         case 1:
 377           return CALL(fuzzy);
 378         case 2:
 379           return CALL(average);
 380         default:
 381           ASSERT(0);
 382       }
 383 }
 384 #undef CALL
 385
 386 #undef EXPLAIN
 387 #undef MSG
 388 #undef LINE
 389 #undef MSGL