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