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 #define LOCAL_DEBUG
  11
  12 #include "lib/lib.h"
  13 #include "lib/math.h"
  14 #include "images/math.h"
  15 #include "images/images.h"
  16 #include "images/signature.h"
  17 #include <stdio.h>
  18
  19 uns
  20 image_signatures_dist(struct image_signature *sig1, struct image_signature *sig2)
  21 {
  22   DBG("image_signatures_dist()");
  23
  24   uns cnt1 = sig1->len;
  25   uns cnt2 = sig2->len;
  26   struct image_region *reg1 = sig1->reg;
  27   struct image_region *reg2 = sig2->reg;
  28   uns mf[IMAGE_REG_MAX][IMAGE_REG_MAX], mh[IMAGE_REG_MAX][IMAGE_REG_MAX];
  29   uns lf[IMAGE_REG_MAX * 2], lh[IMAGE_REG_MAX * 2];
  30   uns df = sig1->df + sig2->df, dh = sig1->dh + sig2->dh;
  31
  32   /* Compute distance matrix */
  33   for (uns i = 0; i < cnt1; i++)
  34     for (uns j = 0; j < cnt2; j++)
  35       {
  36         uns d = 0;
  37         for (uns k = 0; k < IMAGE_REG_F; k++)
  38           {
  39             int dif = reg1[i].f[k] - reg2[j].f[k];
  40             d += dif * dif;
  41           }
  42         mf[i][j] = d;
  43         d = 0;
  44         for (uns k = 0; k < IMAGE_REG_H; k++)
  45           {
  46             int dif = reg1[i].h[k] - reg2[j].h[k];
  47             d += dif * dif;
  48           }
  49         mh[i][j] = d;
  50       }
  51
  52   uns lfs = 0, lhs = 0;
  53   for (uns i = 0; i < cnt1; i++)
  54     {
  55       uns f = mf[i][0], h = mh[i][0];
  56       for (uns j = 1; j < cnt2; j++)
  57         {
  58           f = MIN(f, mf[i][j]);
  59           h = MIN(h, mh[i][j]);
  60         }
  61       lf[i] = (df * 0x10000) / (df + fast_sqrt_u32(f));
  62       lh[i] = (dh * 0x10000) / (dh + fast_sqrt_u32(h));
  63       lfs += lf[i] * (6 * reg1[i].wa + 2 * reg1[i].wb);
  64       lhs += lh[i] * reg1[i].wa;
  65     }
  66   for (uns i = 0; i < cnt2; i++)
  67     {
  68       uns f = mf[0][i], h = mh[0][i];
  69       for (uns j = 1; j < cnt1; j++)
  70         {
  71           f = MIN(f, mf[j][i]);
  72           h = MIN(h, mh[j][i]);
  73         }
  74       lf[i + cnt1] = (df * 0x10000) / (df + fast_sqrt_u32(f));
  75       lh[i + cnt1] = (dh * 0x10000) / (dh + fast_sqrt_u32(h));
  76       lfs += lf[i] * (6 * reg2[i].wa + 2 * reg2[i].wb);
  77       lhs += lh[i] * reg2[i].wa;
  78     }
  79
  80   uns measure = lfs * 6 + lhs * 2 * 8;
  81
  82 #ifdef LOCAL_DEBUG
  83   /* Display similarity vectors */
  84   byte buf[2 * IMAGE_REG_MAX * 16 + 3], *b = buf;
  85   for (uns i = 0; i < cnt1 + cnt2; i++)
  86     {
  87       if (i)
  88         *b++ = ' ';
  89       if (i == cnt1)
  90         *b++ = '~', *b++ = ' ';
  91       b += sprintf(b, "%.4f", (double)lf[i] / 0x10000);
  92     }
  93   *b = 0;
  94   DBG("Lf=(%s)", buf);
  95   b = buf;
  96   for (uns i = 0; i < cnt1 + cnt2; i++)
  97     {
  98       if (i)
  99         *b++ = ' ';
 100       if (i == cnt1)
 101         *b++ = '~', *b++ = ' ';
 102       b += sprintf(b, "%.4f", (double)lh[i] / 0x10000);
 103     }
 104   *b = 0;
 105   DBG("Lh=(%s)", buf);
 106   DBG("Lfm=%.4f", lfs / (double)(1 << (3 + 8 + 16)));
 107   DBG("Lhm=%.4f", lhs / (double)(1 << (8 + 16)));
 108   DBG("measure=%.4f", measure / (double)(1 << (3 + 3 + 8 + 16)));
 109 #endif
 110
 111   return (1 << (3 + 3 + 8 + 16)) - measure;
 112 }