images/sig-cmp.c

   1 /*
   2  *      Image Library -- Comparitions of image signatures
   3  *
   4  *      (c) 2006 Pavel Charvat <pchar@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #undef LOCAL_DEBUG
  11
  12 #include "lib/lib.h"
  13 #include "lib/math.h"
  14 #include "lib/fastbuf.h"
  15 #include "images/math.h"
  16 #include "images/images.h"
  17 #include "images/signature.h"
  18
  19 #include <stdio.h>
  20
  21 static uns
  22 image_signatures_dist_1(struct image_signature *sig1, struct image_signature *sig2)
  23 {
  24   DBG("image_signatures_dist_1()");
  25
  26   uns cnt1 = sig1->len;
  27   uns cnt2 = sig2->len;
  28   struct image_region *reg1 = sig1->reg;
  29   struct image_region *reg2 = sig2->reg;
  30   uns mf[IMAGE_REG_MAX][IMAGE_REG_MAX], mh[IMAGE_REG_MAX][IMAGE_REG_MAX];
  31   uns lf[IMAGE_REG_MAX * 2], lh[IMAGE_REG_MAX * 2];
  32   uns df = sig1->df + sig2->df, dh = sig1->dh + sig2->dh;
  33
  34   /* Compute distance matrix */
  35   for (uns i = 0; i < cnt1; i++)
  36     for (uns j = 0; j < cnt2; j++)
  37       {
  38         uns d = 0;
  39         for (uns k = 0; k < IMAGE_REG_F; k++)
  40           {
  41             int dif = reg1[i].f[k] - reg2[j].f[k];
  42             d += dif * dif;
  43           }
  44         mf[i][j] = d;
  45         d = 0;
  46         for (uns k = 0; k < IMAGE_REG_H; k++)
  47           {
  48             int dif = reg1[i].h[k] - reg2[j].h[k];
  49             d += dif * dif;
  50           }
  51         mh[i][j] = d;
  52       }
  53
  54   uns lfs = 0, lhs = 0;
  55   for (uns i = 0; i < cnt1; i++)
  56     {
  57       uns f = mf[i][0], h = mh[i][0];
  58       for (uns j = 1; j < cnt2; j++)
  59         {
  60           f = MIN(f, mf[i][j]);
  61           h = MIN(h, mh[i][j]);
  62         }
  63       lf[i] = (df * 0x10000) / (df + fast_sqrt_u32(f));
  64       lh[i] = (dh * 0x10000) / (dh + fast_sqrt_u32(h));
  65       lfs += lf[i] * (6 * reg1[i].wa + 2 * reg1[i].wb);
  66       lhs += lh[i] * reg1[i].wa;
  67     }
  68   for (uns i = 0; i < cnt2; i++)
  69     {
  70       uns f = mf[0][i], h = mh[0][i];
  71       for (uns j = 1; j < cnt1; j++)
  72         {
  73           f = MIN(f, mf[j][i]);
  74           h = MIN(h, mh[j][i]);
  75         }
  76       lf[i + cnt1] = (df * 0x10000) / (df + fast_sqrt_u32(f));
  77       lh[i + cnt1] = (dh * 0x10000) / (dh + fast_sqrt_u32(h));
  78       lfs += lf[i] * (6 * reg2[i].wa + 2 * reg2[i].wb);
  79       lhs += lh[i] * reg2[i].wa;
  80     }
  81
  82   uns measure = lfs * 6 + lhs * 2 * 8;
  83
  84 #ifdef LOCAL_DEBUG
  85   /* Display similarity vectors */
  86   byte buf[2 * IMAGE_REG_MAX * 16 + 3], *b = buf;
  87   for (uns i = 0; i < cnt1 + cnt2; i++)
  88     {
  89       if (i)
  90         *b++ = ' ';
  91       if (i == cnt1)
  92         *b++ = '~', *b++ = ' ';
  93       b += sprintf(b, "%.4f", (double)lf[i] / 0x10000);
  94     }
  95   *b = 0;
  96   DBG("Lf=(%s)", buf);
  97   b = buf;
  98   for (uns i = 0; i < cnt1 + cnt2; i++)
  99     {
 100       if (i)
 101         *b++ = ' ';
 102       if (i == cnt1)
 103         *b++ = '~', *b++ = ' ';
 104       b += sprintf(b, "%.4f", (double)lh[i] / 0x10000);
 105     }
 106   *b = 0;
 107   DBG("Lh=(%s)", buf);
 108   DBG("Lfm=%.4f", lfs / (double)(1 << (3 + 8 + 16)));
 109   DBG("Lhm=%.4f", lhs / (double)(1 << (8 + 16)));
 110   DBG("measure=%.4f", measure / (double)(1 << (3 + 3 + 8 + 16)));
 111 #endif
 112
 113   return (1 << (3 + 3 + 8 + 16)) - measure;
 114 }
 115
 116 #define ASORT_PREFIX(x) image_signatures_dist_2_##x
 117 #define ASORT_KEY_TYPE uns
 118 #define ASORT_ELT(i) items[i]
 119 #define ASORT_EXTRA_ARGS , uns *items
 120 #include "lib/arraysort.h"
 121
 122 #define SIG_EXPLAIN
 123 #include "images/sig-cmp-gen.h"
 124 #include "images/sig-cmp-gen.h"
 125
 126 uns
 127 image_signatures_dist(struct image_signature *sig1, struct image_signature *sig2)
 128 {
 129   switch (image_sig_compare_method)
 130     {
 131       case 1:
 132         return image_signatures_dist_1(sig1, sig2);
 133       case 2:
 134         return image_signatures_dist_2(sig1, sig2);
 135       default:
 136         die("Invalid image signatures compare method.");
 137     }
 138 }
 139
 140 uns
 141 image_signatures_dist_explain(struct image_signature *sig1, struct image_signature *sig2, struct fastbuf *fb)
 142 {
 143   if (image_sig_compare_method == 2)
 144     return image_signatures_dist_2_explain(sig1, sig2, fb);
 145   return image_signatures_dist(sig1, sig2);
 146 }
 147