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 #undef LOCAL_DEBUG
  11
  12 #include "lib/lib.h"
  13 #include "lib/mempool.h"
  14 #include "lib/fastbuf.h"
  15 #include "images/images.h"
  16 #include "images/duplicates.h"
  17
  18 #include <fcntl.h>
  19
  20 static inline uns
  21 err (int a, int b)
  22 {
  23   a -= b;
  24   return a * a;
  25 }
  26
  27 static inline u64
  28 err_sum(byte *pos1, byte *pos2, uns count)
  29 {
  30   uns e64 = 0;
  31   while (count--)
  32     {
  33       uns e = err(*pos1++, *pos2++);
  34       e += err(*pos1++, *pos2++);
  35       e += err(*pos1++, *pos2++);
  36       e64 += e;
  37     }
  38   return e64;
  39 }
  40
  41 static inline u64
  42 err_sum_transformed(byte *pos1, byte *pos2, uns cols, uns rows, int row_step_1, int col_step_2, int row_step_2)
  43 {
  44   DBG("err_sum_transformed(pos1=%p pos2=%p cols=%u rows=%u row_step_1=%d col_step_2=%d row_step_2=%d)",
  45       pos1, pos2, cols, rows, row_step_1, col_step_2, row_step_2);
  46   u64 e64 = 0;
  47   for (uns j = rows; j--; )
  48     {
  49       byte *p1 = pos1;
  50       byte *p2 = pos2;
  51       uns e = 0;
  52       for (uns i = cols; i--; )
  53       {
  54         e += err(p1[0], p2[0]);
  55         e += err(p1[1], p2[1]);
  56         e += err(p1[2], p2[2]);
  57         p1 += 3;
  58         p2 += col_step_2;
  59       }
  60       pos1 += row_step_1;
  61       pos2 += row_step_2;
  62       e64 += e;
  63     }
  64   return e64;
  65 }
  66
  67 static inline int
  68 aspect_ratio_test(struct image_dup_context *ctx, uns cols1, uns rows1, uns cols2, uns rows2)
  69 {
  70   DBG("aspect_ratio_test(cols1=%u rows1=%u cols2=%u rows2=%u)", cols1, rows1, cols2, rows2);
  71   uns r1 = cols1 * rows2;
  72   uns r2 = rows1 * cols2;
  73   return
  74     r1 <= ((r2 * ctx->ratio_threshold) >> 7) &&
  75     r2 <= ((r1 * ctx->ratio_threshold) >> 7);
  76 }
  77
  78 static inline int
  79 average_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2)
  80 {
  81   byte *block1 = image_dup_block(dup1, 0, 0);
  82   byte *block2 = image_dup_block(dup2, 0, 0);
  83   uns e =
  84     err(block1[0], block2[0]) +
  85     err(block1[1], block2[1]) +
  86     err(block1[2], block2[2]);
  87   return e <= ctx->error_threshold;
  88 }
  89
  90 static int
  91 blocks_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns tab_row, uns trans)
  92 {
  93   DBG("blocks_compare(tab_col=%d tab_row=%d trans=%d)", tab_col, tab_row, trans);
  94   ctx->sum_pixels += 1 << (tab_col + tab_row);
  95   byte *block1 = image_dup_block(dup1, tab_col, tab_row);
  96   byte *block2;
  97   int col_step, row_step;
  98   if (trans < 4)
  99     block2 = image_dup_block(dup2, tab_col, tab_row);
 100   else
 101     block2 = image_dup_block(dup2, tab_row, tab_col);
 102   switch (trans)
 103     {
 104       case 0: ;
 105         uns err = (err_sum(block1, block2, 1 << (tab_col + tab_row)) >> (tab_col + tab_row));
 106         DBG("average error=%d", err);
 107         return err <= ctx->error_threshold;
 108       case 1:
 109         col_step = -3;
 110         row_step = (3 << tab_col);
 111         block2 += row_step - 3;
 112         break;
 113       case 2:
 114         col_step = 3;
 115         row_step = -(3 << tab_col);
 116         block2 += (3 << (tab_col + tab_row)) + row_step;
 117         break;
 118       case 3:
 119         col_step = -3;
 120         row_step = -(3 << tab_col);
 121         block2 += (3 << (tab_col + tab_row)) - 3;
 122         break;
 123       case 4:
 124         col_step = (3 << tab_row);
 125         row_step = 3;
 126         break;
 127       case 5:
 128         col_step = -(3 << tab_row);
 129         row_step = 3;
 130         block2 += (3 << (tab_col + tab_row)) + col_step;
 131         break;
 132       case 6:
 133         col_step = (3 << tab_row);
 134         row_step = -3;
 135         block2 += col_step - 3;
 136         break;
 137       case 7:
 138         col_step = -(3 << tab_row);
 139         row_step = -3;
 140         block2 += (3 << (tab_col + tab_row)) - 3;
 141         break;
 142       default:
 143         ASSERT(0);
 144     }
 145   uns err = (err_sum_transformed(block1, block2, (1 << tab_col), (1 << tab_row), (3 << tab_col), col_step, row_step) >> (tab_col + tab_row));
 146   DBG("average error=%d", err);
 147   return err <= ctx->error_threshold;
 148 }
 149
 150 static int
 151 same_size_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2, uns trans)
 152 {
 153   struct image *img1 = &dup1->image;
 154   struct image *img2 = &dup2->image;
 155   ctx->sum_pixels += img1->cols * img1->rows;
 156   byte *block1 = img1->pixels;
 157   byte *block2 = img2->pixels;
 158   int col_step, row_step;
 159   DBG("same_size_compare(trans=%d)",  trans);
 160   switch (trans)
 161     {
 162       case 0: ;
 163         col_step = 3;
 164         row_step = img2->row_size;
 165         break;
 166       case 1:
 167         col_step = -3;
 168         row_step = img2->row_size;
 169         block2 += 3 * (img2->cols - 1);
 170         break;
 171       case 2:
 172         col_step = 3;
 173         row_step = -img2->row_size;
 174         block2 += img2->row_size * (img2->rows - 1);
 175         break;
 176       case 3:
 177         col_step = -3;
 178         row_step = -img2->row_size;
 179         block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
 180         break;
 181       case 4:
 182         col_step = img2->row_size;
 183         row_step = 3;
 184         break;
 185       case 5:
 186         col_step = -img2->row_size;
 187         row_step = 3;
 188         block2 += img2->row_size * (img2->rows - 1);
 189         break;
 190       case 6:
 191         col_step = img2->row_size;
 192         row_step = -3;
 193         block2 += 3 * (img2->cols - 1);
 194         break;
 195       case 7:
 196         col_step = -img2->row_size;
 197         row_step = -3;
 198         block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
 199         break;
 200       default:
 201         ASSERT(0);
 202     }
 203   uns err = (err_sum_transformed(block1, block2, img1->cols, img1->rows, img1->row_size, col_step, row_step) / ((u64)img1->cols * img1->rows));
 204   DBG("average error=%d", err);
 205   return err <= ctx->error_threshold;
 206 }
 207
 208 uns
 209 image_dup_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2)
 210 {
 211   DBG("image_dup_compare()");
 212   if (!average_compare(ctx, dup1, dup2))
 213     return 0;
 214   struct image *img1 = &dup1->image;
 215   struct image *img2 = &dup2->image;
 216   uns flags = ctx->flags;
 217   if (flags & IMAGE_DUP_SCALE)
 218     {
 219       DBG("Scale support");
 220       if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->cols, img2->rows))
 221         flags &= ~0x0f;
 222       if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->rows, img2->cols))
 223         flags &= ~0xf0;
 224     }
 225   else
 226     {
 227       DBG("No scale support");
 228       if (!(img1->cols == img2->cols && img1->rows == img2->rows))
 229         flags &= ~0x0f;
 230       if (!(img1->cols == img2->rows && img1->rows == img2->cols))
 231         flags &= ~0xf0;
 232     }
 233   if (!(flags & 0xff))
 234     return 0;
 235   uns result = 0;
 236   if (flags & 0x0f)
 237     {
 238       uns cols = MIN(dup1->tab_cols, dup2->tab_cols);
 239       uns rows = MIN(dup1->tab_rows, dup2->tab_rows);
 240       for (uns t = 0; t < 4; t++)
 241         if (flags & (1 << t))
 242           {
 243             DBG("Testing trans %d", t);
 244             uns i = MAX(cols, rows), depth = 1;
 245             while (i--)
 246               {
 247                 depth++;
 248                 uns col = MAX(0, (int)(cols - i));
 249                 uns row = MAX(0, (int)(rows - i));
 250                 if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 251                   break;
 252                 if (!i &&
 253                     (img1->cols != img2->cols || img1->rows != img2->rows ||
 254                     same_size_compare(ctx, dup1, dup2, t)))
 255                   {
 256                     result |= 1 << t;
 257                     if (!(flags & IMAGE_DUP_WANT_ALL))
 258                       return result;
 259                     else
 260                       break;
 261                   }
 262               }
 263             ctx->sum_depth += depth;
 264           }
 265     }
 266   if (flags & 0xf0)
 267     {
 268       uns cols = MIN(dup1->tab_cols, dup2->tab_rows);
 269       uns rows = MIN(dup1->tab_rows, dup2->tab_cols);
 270       for (uns t = 4; t < 8; t++)
 271         if (flags & (1 << t))
 272           {
 273             DBG("Testing trans %d", t);
 274             uns i = MAX(cols, rows), depth = 1;
 275             while (i--)
 276               {
 277                 depth++;
 278                 uns col = MAX(0, (int)(cols - i));
 279                 uns row = MAX(0, (int)(rows - i));
 280                 if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 281                   break;
 282                 if (!i &&
 283                     (img1->cols != img2->rows || img1->rows != img2->cols ||
 284                     same_size_compare(ctx, dup1, dup2, t)) )
 285                   {
 286                     result |= 1 << t;
 287                     if (!(flags & IMAGE_DUP_WANT_ALL))
 288                       return result;
 289                     else
 290                       break;
 291                   }
 292               }
 293             ctx->sum_depth += depth;
 294           }
 295     }
 296   return result;
 297 }