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