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   byte *block1 = image_dup_block(dup1, tab_col, tab_row);
  95   byte *block2;
  96   int col_step, row_step;
  97   if (trans < 4)
  98     block2 = image_dup_block(dup2, tab_col, tab_row);
  99   else
 100     block2 = image_dup_block(dup2, tab_row, tab_col);
 101   switch (trans)
 102     {
 103       case 0: ;
 104         uns err = (err_sum(block1, block2, 1 << (tab_col + tab_row)) >> (tab_col + tab_row));
 105         DBG("average error=%d", err);
 106         return err <= ctx->error_threshold;
 107       case 1:
 108         col_step = -3;
 109         row_step = (3 << tab_col);
 110         block2 += row_step - 3;
 111         break;
 112       case 2:
 113         col_step = 3;
 114         row_step = -(3 << tab_col);
 115         block2 += (3 << (tab_col + tab_row)) + row_step;
 116         break;
 117       case 3:
 118         col_step = -3;
 119         row_step = -(3 << tab_col);
 120         block2 += (3 << (tab_col + tab_row)) - 3;
 121         break;
 122       case 4:
 123         col_step = (3 << tab_row);
 124         row_step = 3;
 125         break;
 126       case 5:
 127         col_step = -(3 << tab_row);
 128         row_step = 3;
 129         block2 += (3 << (tab_col + tab_row)) + col_step;
 130         break;
 131       case 6:
 132         col_step = (3 << tab_row);
 133         row_step = -3;
 134         block2 += col_step - 3;
 135         break;
 136       case 7:
 137         col_step = -(3 << tab_row);
 138         row_step = -3;
 139         block2 += (3 << (tab_col + tab_row)) - 3;
 140         break;
 141       default:
 142         ASSERT(0);
 143     }
 144   uns err = (err_sum_transformed(block1, block2, (1 << tab_col), (1 << tab_row), (3 << tab_col), col_step, row_step) >> (tab_col + tab_row));
 145   DBG("average error=%d", err);
 146   return err <= ctx->error_threshold;
 147 }
 148
 149 static int
 150 same_size_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2, uns trans)
 151 {
 152   struct image *img1 = &dup1->image;
 153   struct image *img2 = &dup2->image;
 154   byte *block1 = img1->pixels;
 155   byte *block2 = img2->pixels;
 156   int col_step, row_step;
 157   DBG("same_size_compare(trans=%d)",  trans);
 158   switch (trans)
 159     {
 160       case 0: ;
 161         col_step = 3;
 162         row_step = img2->row_size;
 163         break;
 164       case 1:
 165         col_step = -3;
 166         row_step = img2->row_size;
 167         block2 += 3 * (img2->cols - 1);
 168         break;
 169       case 2:
 170         col_step = 3;
 171         row_step = -img2->row_size;
 172         block2 += img2->row_size * (img2->rows - 1);
 173         break;
 174       case 3:
 175         col_step = -3;
 176         row_step = -img2->row_size;
 177         block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
 178         break;
 179       case 4:
 180         col_step = img2->row_size;
 181         row_step = 3;
 182         break;
 183       case 5:
 184         col_step = -img2->row_size;
 185         row_step = 3;
 186         block2 += img2->row_size * (img2->rows - 1);
 187         break;
 188       case 6:
 189         col_step = img2->row_size;
 190         row_step = -3;
 191         block2 += 3 * (img2->cols - 1);
 192         break;
 193       case 7:
 194         col_step = -img2->row_size;
 195         row_step = -3;
 196         block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
 197         break;
 198       default:
 199         ASSERT(0);
 200     }
 201   uns err = (err_sum_transformed(block1, block2, img1->cols, img1->rows, img1->row_size, col_step, row_step) / ((u64)img1->cols * img1->rows));
 202   DBG("average error=%d", err);
 203   return err <= ctx->error_threshold;
 204 }
 205
 206 uns
 207 image_dup_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2)
 208 {
 209   DBG("image_dup_compare()");
 210   if (!average_compare(ctx, dup1, dup2))
 211     return 0;
 212   struct image *img1 = &dup1->image;
 213   struct image *img2 = &dup2->image;
 214   uns flags = ctx->flags;
 215   if (flags & IMAGE_DUP_SCALE)
 216     {
 217       DBG("Scale support");
 218       if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->cols, img2->rows))
 219         flags &= ~0x0f;
 220       if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->rows, img2->cols))
 221         flags &= ~0xf0;
 222     }
 223   else
 224     {
 225       DBG("No scale support");
 226       if (!(img1->cols == img2->cols && img1->rows == img2->rows))
 227         flags &= ~0x0f;
 228       if (!(img1->cols == img2->rows && img1->rows == img2->cols))
 229         flags &= ~0xf0;
 230     }
 231   if (!(flags & 0xff))
 232     return 0;
 233   uns result = 0;
 234   if (flags & 0x0f)
 235     {
 236       uns cols = MIN(dup1->tab_cols, dup2->tab_cols);
 237       uns rows = MIN(dup1->tab_rows, dup2->tab_rows);
 238       for (uns t = 0; t < 4; t++)
 239         if (flags & (1 << t))
 240           {
 241             DBG("Testing trans %d", t);
 242             for (uns i = MAX(cols, rows); i--; )
 243               {
 244                 uns col = MAX(0, (int)(cols - i));
 245                 uns row = MAX(0, (int)(rows - i));
 246                 if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 247                   break;
 248                 if (!i &&
 249                     (img1->cols != img2->cols || img1->rows != img2->rows ||
 250                     same_size_compare(ctx, dup1, dup2, t)))
 251                   {
 252                     result |= 1 << t;
 253                     if (!(flags & IMAGE_DUP_WANT_ALL))
 254                       return result;
 255                     else
 256                       break;
 257                   }
 258               }
 259           }
 260     }
 261   if (flags & 0xf0)
 262     {
 263       uns cols = MIN(dup1->tab_cols, dup2->tab_rows);
 264       uns rows = MIN(dup1->tab_rows, dup2->tab_cols);
 265       for (uns t = 4; t < 8; t++)
 266         if (flags & (1 << t))
 267           {
 268             DBG("Testing trans %d", t);
 269             for (uns i = MAX(cols, rows); i--; )
 270               {
 271                 uns col = MAX(0, (int)(cols - i));
 272                 uns row = MAX(0, (int)(rows - i));
 273                 if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 274                   break;
 275                 if (!i &&
 276                     (img1->cols != img2->rows || img1->rows != img2->cols ||
 277                     same_size_compare(ctx, dup1, dup2, t)) )
 278                   {
 279                     result |= 1 << t;
 280                     if (!(flags & IMAGE_DUP_WANT_ALL))
 281                       return result;
 282                     else
 283                       break;
 284                   }
 285               }
 286           }
 287     }
 288   return result;
 289 }