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