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