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