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   if (!img1->pixels || !img2->pixels)
 156     return 1;
 157   ctx->sum_pixels += img1->cols * img1->rows;
 158   byte *block1 = img1->pixels;
 159   byte *block2 = img2->pixels;
 160   int col_step, row_step;
 161   DBG("same_size_compare(trans=%d)",  trans);
 162   switch (trans)
 163     {
 164       case 0: ;
 165         col_step = 3;
 166         row_step = img2->row_size;
 167         break;
 168       case 1:
 169         col_step = -3;
 170         row_step = img2->row_size;
 171         block2 += 3 * (img2->cols - 1);
 172         break;
 173       case 2:
 174         col_step = 3;
 175         row_step = -img2->row_size;
 176         block2 += img2->row_size * (img2->rows - 1);
 177         break;
 178       case 3:
 179         col_step = -3;
 180         row_step = -img2->row_size;
 181         block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
 182         break;
 183       case 4:
 184         col_step = img2->row_size;
 185         row_step = 3;
 186         break;
 187       case 5:
 188         col_step = -img2->row_size;
 189         row_step = 3;
 190         block2 += img2->row_size * (img2->rows - 1);
 191         break;
 192       case 6:
 193         col_step = img2->row_size;
 194         row_step = -3;
 195         block2 += 3 * (img2->cols - 1);
 196         break;
 197       case 7:
 198         col_step = -img2->row_size;
 199         row_step = -3;
 200         block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
 201         break;
 202       default:
 203         ASSERT(0);
 204     }
 205   uns err = (err_sum_transformed(block1, block2, img1->cols, img1->rows, img1->row_size, col_step, row_step) / ((u64)img1->cols * img1->rows));
 206   DBG("average error=%d", err);
 207   return err <= ctx->error_threshold;
 208 }
 209
 210 uns
 211 image_dup_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2)
 212 {
 213   DBG("image_dup_compare()");
 214   if (!average_compare(ctx, dup1, dup2))
 215     return 0;
 216   struct image *img1 = &dup1->image;
 217   struct image *img2 = &dup2->image;
 218   uns flags = ctx->flags;
 219   if (flags & IMAGE_DUP_SCALE)
 220     {
 221       DBG("Scale support");
 222       if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->cols, img2->rows))
 223         flags &= ~0x0f;
 224       if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->rows, img2->cols))
 225         flags &= ~0xf0;
 226     }
 227   else
 228     {
 229       DBG("No scale support");
 230       if (!(img1->cols == img2->cols && img1->rows == img2->rows))
 231         flags &= ~0x0f;
 232       if (!(img1->cols == img2->rows && img1->rows == img2->cols))
 233         flags &= ~0xf0;
 234     }
 235   if (!(flags & 0xff))
 236     return 0;
 237   uns result = 0;
 238   if (flags & 0x0f)
 239     {
 240       uns cols = MIN(dup1->tab_cols, dup2->tab_cols);
 241       uns rows = MIN(dup1->tab_rows, dup2->tab_rows);
 242       for (uns t = 0; t < 4; t++)
 243         if (flags & (1 << t))
 244           {
 245             DBG("Testing trans %d", t);
 246             uns i = MAX(cols, rows), depth = 1;
 247             while (i--)
 248               {
 249                 depth++;
 250                 uns col = MAX(0, (int)(cols - i));
 251                 uns row = MAX(0, (int)(rows - i));
 252                 if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 253                   break;
 254                 if (!i &&
 255                     (img1->cols != img2->cols || img1->rows != img2->rows ||
 256                     same_size_compare(ctx, dup1, dup2, t)))
 257                   {
 258                     result |= 1 << t;
 259                     if (!(flags & IMAGE_DUP_WANT_ALL))
 260                       return result;
 261                     else
 262                       break;
 263                   }
 264               }
 265             ctx->sum_depth += depth;
 266           }
 267     }
 268   if (flags & 0xf0)
 269     {
 270       uns cols = MIN(dup1->tab_cols, dup2->tab_rows);
 271       uns rows = MIN(dup1->tab_rows, dup2->tab_cols);
 272       for (uns t = 4; t < 8; t++)
 273         if (flags & (1 << t))
 274           {
 275             DBG("Testing trans %d", t);
 276             uns i = MAX(cols, rows), depth = 1;
 277             while (i--)
 278               {
 279                 depth++;
 280                 uns col = MAX(0, (int)(cols - i));
 281                 uns row = MAX(0, (int)(rows - i));
 282                 if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 283                   break;
 284                 if (!i &&
 285                     (img1->cols != img2->rows || img1->rows != img2->cols ||
 286                     same_size_compare(ctx, dup1, dup2, t)) )
 287                   {
 288                     result |= 1 << t;
 289                     if (!(flags & IMAGE_DUP_WANT_ALL))
 290                       return result;
 291                     else
 292                       break;
 293                   }
 294               }
 295             ctx->sum_depth += depth;
 296           }
 297     }
 298   return result;
 299 }