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 CONFIG_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 CONFIG_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       MSGL("[%u, %u] s=%u d=%u", i, j, s, d);
 153     }
 154
 155   return sum;
 156 }
 157
 158 #ifndef EXPLAIN
 159 static uns
 160 image_signatures_dist_fuzzy(struct image_signature *sig1, struct image_signature *sig2)
 161 #else
 162 static uns
 163 image_signatures_dist_fuzzy_explain(struct image_signature *sig1, struct image_signature *sig2, void (*msg)(byte *text, void *param), void *param)
 164 #endif
 165 {
 166 #ifdef EXPLAIN
 167   byte buf[1024], *line = buf;
 168   MSGL("Fuzzy matching");
 169   explain_signature(sig1, msg, param);
 170   explain_signature(sig2, msg, param);
 171 #endif
 172
 173   /* FIXME: do not mux textured and non-textured images (should be split in clusters tree) */
 174   if ((sig1->flags ^ sig2->flags) & IMAGE_SIG_TEXTURED)
 175     {
 176       MSGL("Textured vs non-textured");
 177       return ~0U;
 178     }
 179
 180   uns cnt1 = sig1->len;
 181   uns cnt2 = sig2->len;
 182   struct image_region *reg1 = sig1->reg;
 183   struct image_region *reg2 = sig2->reg;
 184   uns mf[IMAGE_REG_MAX][IMAGE_REG_MAX], mh[IMAGE_REG_MAX][IMAGE_REG_MAX];
 185   uns lf[IMAGE_REG_MAX * 2], lh[IMAGE_REG_MAX * 2];
 186   uns df = sig1->df + sig2->df, dh = sig1->dh + sig2->dh;
 187
 188   /* Compute distance matrix */
 189   for (uns i = 0; i < cnt1; i++)
 190     for (uns j = 0; j < cnt2; j++)
 191       {
 192         uns d = 0;
 193         for (uns k = 0; k < IMAGE_REG_F; k++)
 194           {
 195             int dif = reg1[i].f[k] - reg2[j].f[k];
 196             d += dif * dif;
 197           }
 198         mf[i][j] = d;
 199         d = 0;
 200         for (uns k = 0; k < IMAGE_REG_H; k++)
 201           {
 202             int dif = reg1[i].h[k] - reg2[j].h[k];
 203             d += dif * dif;
 204           }
 205         mh[i][j] = d;
 206       }
 207
 208   uns lfs = 0, lhs = 0;
 209   for (uns i = 0; i < cnt1; i++)
 210     {
 211       uns f = mf[i][0], h = mh[i][0];
 212       for (uns j = 1; j < cnt2; j++)
 213         {
 214           f = MIN(f, mf[i][j]);
 215           h = MIN(h, mh[i][j]);
 216         }
 217       lf[i] = (df * 0x10000) / (df + fast_sqrt_u32(f));
 218       lh[i] = (dh * 0x10000) / (dh + fast_sqrt_u32(h));
 219       lfs += lf[i] * (6 * reg1[i].wa + 2 * reg1[i].wb);
 220       lhs += lh[i] * reg1[i].wa;
 221     }
 222   for (uns i = 0; i < cnt2; i++)
 223     {
 224       uns f = mf[0][i], h = mh[0][i];
 225       for (uns j = 1; j < cnt1; j++)
 226         {
 227           f = MIN(f, mf[j][i]);
 228           h = MIN(h, mh[j][i]);
 229         }
 230       lf[i + cnt1] = (df * 0x10000) / (df + fast_sqrt_u32(f));
 231       lh[i + cnt1] = (dh * 0x10000) / (dh + fast_sqrt_u32(h));
 232       lfs += lf[i] * (6 * reg2[i].wa + 2 * reg2[i].wb);
 233       lhs += lh[i] * reg2[i].wa;
 234     }
 235
 236   uns measure = lfs * 6 + lhs * 2 * 8;
 237
 238 #ifdef CONFIG_EXPLAIN
 239   /* Display similarity vectors */
 240   MSG("Lf=(");
 241   for (uns i = 0; i < cnt1 + cnt2; i++)
 242     {
 243       if (i)
 244         MSG(" ");
 245       if (i == cnt1)
 246         MSG("~ ");
 247       MSG("%.4f", (double)lf[i] / 0x10000);
 248     }
 249   MSGL(")");
 250   for (uns i = 0; i < cnt1 + cnt2; i++)
 251     {
 252       if (i)
 253         MSG(" ");
 254       if (i == cnt1)
 255         MSG("~ ");
 256       MSG("%.4f", (double)lh[i] / 0x10000);
 257     }
 258   MSGL(")");
 259   MSGL("Lfm=%.4f", lfs / (double)(1 << (3 + 8 + 16)));
 260   MSGL("Lhm=%.4f", lhs / (double)(1 << (8 + 16)));
 261   MSGL("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
 270 #undef MSGL