images/sig-cmp-gen.h

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