images/dup-cmp.c

   1 /*
   2  *      Image Library -- Duplicates Comparison
   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  *      FIXME:
  11  *      - many possible optimization
  12  *      - compare normalized pictures (brightness, ...)
  13  *      - better image scale... now it can completely miss some rows/cols of pixels
  14  *      - maybe better/slower last step
  15  *      - different thresholds for various transformations
  16  *      - do not test all transformations for symetric pictures
  17  *      - ... secret ideas :-)
  18  */
  19
  20 #undef LOCAL_DEBUG
  21
  22 #include "sherlock/sherlock.h"
  23 #include "lib/mempool.h"
  24 #include "images/images.h"
  25 #include "images/dup-cmp.h"
  26
  27 static uns image_dup_scale_min_size = 16;
  28 static uns image_dup_ratio_threshold = 140;
  29 static uns image_dup_error_threshold = 50;
  30
  31 static inline byte *
  32 image_dup_block(struct image_dup *dup, uns col, uns row)
  33 {
  34   ASSERT(col <= dup->cols && row <= dup->rows);
  35   return dup->buf + (dup->line << row) + (3 << (row + col));
  36 }
  37
  38 static inline void
  39 pixels_average(byte *dest, byte *src1, byte *src2)
  40 {
  41   dest[0] = ((uns)src1[0] + (uns)src2[0]) >> 1;
  42   dest[1] = ((uns)src1[1] + (uns)src2[1]) >> 1;
  43   dest[2] = ((uns)src1[2] + (uns)src2[2]) >> 1;
  44 }
  45
  46 void
  47 image_dup_init(struct image_dup *dup, struct image *image, struct mempool *pool)
  48 {
  49   ASSERT(image->width && image->height);
  50
  51   dup->image = image;
  52   dup->width = image->width;
  53   dup->height = image->height;
  54   for (dup->cols = 0; (uns)(2 << dup->cols) < image->width; dup->cols++);
  55   for (dup->rows = 0; (uns)(2 << dup->rows) < image->height; dup->rows++);
  56   dup->buf = mp_alloc(pool, dup->buf_size = (12 << (dup->cols + dup->rows)));
  57   dup->line = 6 << dup->cols;
  58   dup->flags = 0;
  59   if (image->width >= image_dup_scale_min_size && image->height >= image_dup_scale_min_size)
  60     dup->flags |= IMAGE_DUP_FLAG_SCALE;
  61
  62   /* Scale original image to right bottom block */
  63   {
  64     byte *d = image_dup_block(dup, dup->cols, dup->rows);
  65     uns width = 1 << dup->cols;
  66     uns height = 1 << dup->rows;
  67     uns line_size = 3 * image->width;
  68     uns src_y = 0;
  69     for (uns y = 0; y < height; y++)
  70       {
  71         byte *line = image->pixels + line_size * (src_y >> dup->rows);
  72         uns src_x = 0;
  73         for (uns x = 0; x < width; x++)
  74           {
  75             byte *s = line + 3 * (src_x >> dup->cols);
  76             d[0] = s[0];
  77             d[1] = s[1];
  78             d[2] = s[2];
  79             d += 3;
  80             src_x += image->width;
  81           }
  82         src_y += image->height;
  83       }
  84   }
  85
  86   /* Complete bottom row */
  87   for (uns i = dup->cols; i--; )
  88     {
  89       byte *d = image_dup_block(dup, i, dup->rows);
  90       byte *s = image_dup_block(dup, i + 1, dup->rows);
  91       for (uns y = 0; y < (uns)(1 << dup->rows); y++)
  92         for (uns x = 0; x < (uns)(1 << i); x++)
  93           {
  94             pixels_average(d, s, s + 3);
  95             d += 3;
  96             s += 6;
  97           }
  98     }
  99
 100   /* Complete remaining blocks */
 101   for (uns i = 0; i <= dup->cols; i++)
 102     {
 103       uns line_size = (3 << i);
 104       for (uns j = dup->rows; j--; )
 105         {
 106           byte *d = image_dup_block(dup, i, j);
 107           byte *s = image_dup_block(dup, i, j + 1);
 108           for (uns y = 0; y < (uns)(1 << j); y++)
 109             {
 110               for (uns x = 0; x < (uns)(1 << i); x++)
 111                 {
 112                   pixels_average(d, s, s + line_size);
 113                   d += 3;
 114                   s += 3;
 115                 }
 116               s += line_size;
 117             }
 118         }
 119     }
 120 }
 121
 122 static inline uns
 123 err (int a, int b)
 124 {
 125   a -= b;
 126   return a * a;
 127 }
 128
 129 static inline uns
 130 err_sum(byte *pos1, byte *end1, byte *pos2)
 131 {
 132   uns e = 0;
 133   while (pos1 != end1)
 134     e += err(*pos1++, *pos2++);
 135   return e;
 136 }
 137
 138 static inline uns
 139 err_sum_transformed(byte *pos1, byte *end1, byte *pos2, uns width, int add1, int add2)
 140 {
 141   DBG("err_sum_transformed(): %p %p %p %d %d %d", pos1, end1, pos2, width, add1, add2);
 142   uns e = 0;
 143   while (pos1 != end1)
 144     {
 145       for (uns i = 0; i < width; i++, pos2 += add1)
 146       {
 147         e += err(pos1[0], pos2[0]);
 148         e += err(pos1[1], pos2[1]);
 149         e += err(pos1[2], pos2[2]);
 150         pos1 += 3;
 151       }
 152       pos2 += add2;
 153     }
 154   return e;
 155 }
 156
 157 static inline int
 158 aspect_ratio_test(uns width1, uns height1, uns width2, uns height2)
 159 {
 160   uns r1 = width1 * height2;
 161   uns r2 = height1 * width2;
 162   return
 163     r1 <= ((r2 * image_dup_ratio_threshold) >> 5) &&
 164     r2 <= ((r1 * image_dup_ratio_threshold) >> 5);
 165 }
 166
 167 static inline int
 168 average_compare(struct image_dup *dup1, struct image_dup *dup2)
 169 {
 170   byte *block1 = image_dup_block(dup1, 0, 0);
 171   byte *block2 = image_dup_block(dup2, 0, 0);
 172   uns e =
 173     err(block1[0], block2[0]) +
 174     err(block1[1], block2[1]) +
 175     err(block1[2], block2[2]);
 176   return e <= image_dup_error_threshold;
 177 }
 178
 179 static int
 180 blocks_compare(struct image_dup *dup1, struct image_dup *dup2, uns col, uns row, uns trans)
 181 {
 182   DBG("blocks_compare(): col=%d row=%d trans=%d", col, row, trans);
 183   byte *block1 = image_dup_block(dup1, col, row);
 184   byte *block2 = (trans < 4) ? image_dup_block(dup2, col, row) : image_dup_block(dup2, row, col);
 185   int add1, add2;
 186   switch (trans)
 187     {
 188       case 0: ;
 189         uns err = (err_sum(block1, block1 + (3 << (col + row)), block2) >> (col + row));
 190         DBG("average error=%d", err);
 191         return err <= image_dup_error_threshold;
 192       case 1:
 193         add1 = -3;
 194         add2 = 6 << col;
 195         block2 += (3 << col) - 3;
 196         break;
 197       case 2:
 198         add1 = 1;
 199         add2 = -(6 << col);
 200         block2 += (3 << (col + row)) - (3 << col);
 201         break;
 202       case 3:
 203         add1 = -3;
 204         add2 = 0;
 205         block2 += (3 << (col + row)) - 3;
 206         break;
 207       case 4:
 208         add1 = (3 << col);
 209         add2 = -(3 << (col + row)) + 3;
 210         break;
 211       case 5:
 212         add1 = -(3 << col);
 213         add2 = (3 << (col + row)) + 3;
 214         block2 += (3 << (col + row)) - (3 << col);
 215         break;
 216       case 6:
 217         add1 = (3 << col);
 218         add2 = -(3 << (col + row)) - 3;
 219         block2 += (3 << col) - 3;
 220         break;
 221       case 7:
 222         add1 = -(3 << col);
 223         add2 = (3 << (col + row)) - 3;
 224         block2 += (3 << (col + row)) - 3;
 225         break;
 226       default:
 227         ASSERT(0);
 228     }
 229   uns err = (err_sum_transformed(block1, block1 + (3 << (col + row)), block2, (1 << col), add1, add2) >> (col + row));
 230   DBG("average error=%d", err);
 231   return err <= image_dup_error_threshold;
 232 }
 233
 234 static int
 235 same_size_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans)
 236 {
 237   byte *block1 = dup1->image->pixels;
 238   byte *block2 = dup2->image->pixels;
 239   DBG("same_size_compare(): trans=%d",  trans);
 240   int add1, add2;
 241   switch (trans)
 242     {
 243       case 0: ;
 244         uns err = (err_sum(block1, block1 + 3 * dup1->width * dup1->height, block2) / (dup1->width * dup1->height));
 245         DBG("average error=%d", err);
 246         return err <= image_dup_error_threshold;
 247       case 1:
 248         add1 = -3;
 249         add2 = 6 * dup1->width;
 250         block2 += 3 * (dup1->width - 1);
 251         break;
 252       case 2:
 253         add1 = 1;
 254         add2 = -6 * dup1->width;
 255         block2 += 3 * dup1->width * (dup1->height - 1);
 256         break;
 257       case 3:
 258         add1 = -3;
 259         add2 = 0;
 260         block2 += 3 * (dup1->width * dup1->height - 1);
 261         break;
 262       case 4:
 263         add1 = 3 * dup1->width;
 264         add2 = -3 * (dup1->width * dup1->height - 1);
 265         break;
 266       case 5:
 267         add1 = -3 * dup1->width;
 268         add2 = 3 * (dup1->width * dup1->height + 1);
 269         block2 += 3 * dup1->width * (dup1->height - 1);
 270         break;
 271       case 6:
 272         add1 = 3 * dup1->width;
 273         add2 = -3 * (dup1->width * dup1->height + 1);
 274         block2 += 3 * (dup1->width - 1);
 275         break;
 276       case 7:
 277         add1 = -3 * dup1->width;
 278         add2 = 3 * (dup1->width * dup1->height - 1);
 279         block2 += 3 * (dup1->width * dup1->height - 1);
 280         break;
 281       default:
 282         ASSERT(0);
 283     }
 284   uns err = (err_sum_transformed(block1, block1 + 3 * dup1->width * dup1->height, block2, dup1->width, add1, add2) / (dup1->width * dup1->height));
 285   DBG("average error=%d", err);
 286   return err <= image_dup_error_threshold;
 287 }
 288
 289 int
 290 image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans)
 291 {
 292   if (!average_compare(dup1, dup2))
 293     return 0;
 294   if ((dup1->flags & dup2->flags) & IMAGE_DUP_FLAG_SCALE)
 295     {
 296       DBG("Scale support");
 297       if (!aspect_ratio_test(dup1->width, dup1->height, dup2->width, dup2->height))
 298         trans &= 0xf0;
 299       if (!aspect_ratio_test(dup1->width, dup1->height, dup2->height, dup2->width))
 300         trans &= 0x0f;
 301     }
 302   else
 303     {
 304       DBG("No scale support");
 305       if (!(dup1->width == dup2->width && dup1->height == dup2->height))
 306         trans &= 0xf0;
 307       if (!(dup1->width == dup2->height && dup1->height == dup2->width))
 308         trans &= 0x0f;
 309     }
 310   if (!trans)
 311     return 0;
 312   if (trans & 0x0f)
 313     {
 314       uns cols = MIN(dup1->cols, dup2->cols);
 315       uns rows = MIN(dup1->rows, dup2->rows);
 316       for (uns t = 0; t < 4; t++)
 317         if (trans & (1 << t))
 318           {
 319             DBG("Testing trans %d", t);
 320             for (uns i = MAX(cols, rows); i--; )
 321               {
 322                 uns col = MAX(0, (int)(cols - i));
 323                 uns row = MAX(0, (int)(rows - i));
 324                 if (!blocks_compare(dup1, dup2, col, row, t))
 325                   break;
 326                 if (!i &&
 327                     (dup1->width != dup2->width || dup1->height != dup2->height ||
 328                     same_size_compare(dup1, dup2, t)))
 329                   return 1;
 330               }
 331           }
 332     }
 333   if (trans & 0xf0)
 334     {
 335       uns cols = MIN(dup1->cols, dup2->rows);
 336       uns rows = MIN(dup1->rows, dup2->cols);
 337       for (uns t = 4; t < 8; t++)
 338         if (trans & (1 << t))
 339           {
 340             DBG("Testing trans %d", t);
 341             for (uns i = MAX(cols, rows); i--; )
 342               {
 343                 uns col = MAX(0, (int)(cols - i));
 344                 uns row = MAX(0, (int)(rows - i));
 345                 if (!blocks_compare(dup1, dup2, col, row, t))
 346                   break;
 347                 if (!i &&
 348                     (dup1->width != dup2->height || dup1->height != dup2->width ||
 349                     same_size_compare(dup1, dup2, t)) )
 350                   return 1;
 351               }
 352           }
 353     }
 354   return 0;
 355 }