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 <ucw/lib.h>
  13 #include <ucw/mempool.h>
  14 #include <ucw/fastbuf.h>
  15 #include <images/images.h>
  16 #include <images/duplicates.h>
  17
  18 #include <fcntl.h>
  19
  20 static inline uint
  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, uint count)
  29 {
  30   uint e64 = 0;
  31   while (count--)
  32     {
  33       uint 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, uint cols, uint 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 (uint j = rows; j--; )
  48     {
  49       byte *p1 = pos1;
  50       byte *p2 = pos2;
  51       uint e = 0;
  52       for (uint 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, uint cols1, uint rows1, uint cols2, uint rows2)
  69 {
  70   DBG("aspect_ratio_test(cols1=%u rows1=%u cols2=%u rows2=%u)", cols1, rows1, cols2, rows2);
  71   uint r1 = cols1 * rows2;
  72   uint 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   uint 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, uint tab_col, uint tab_row, uint 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         uint err = (err_sum(block1, block2, 1 << (tab_col + tab_row)) >> (tab_col + tab_row));
 106         DBG("average error=%d", err);
 107         ctx->error = err;
 108         return err <= ctx->error_threshold;
 109       case 1:
 110         col_step = -3;
 111         row_step = (3 << tab_col);
 112         block2 += row_step - 3;
 113         break;
 114       case 2:
 115         col_step = 3;
 116         row_step = -(3 << tab_col);
 117         block2 += (3 << (tab_col + tab_row)) + row_step;
 118         break;
 119       case 3:
 120         col_step = -3;
 121         row_step = -(3 << tab_col);
 122         block2 += (3 << (tab_col + tab_row)) - 3;
 123         break;
 124       case 4:
 125         col_step = (3 << tab_row);
 126         row_step = 3;
 127         break;
 128       case 5:
 129         col_step = -(3 << tab_row);
 130         row_step = 3;
 131         block2 += (3 << (tab_col + tab_row)) + col_step;
 132         break;
 133       case 6:
 134         col_step = (3 << tab_row);
 135         row_step = -3;
 136         block2 += col_step - 3;
 137         break;
 138       case 7:
 139         col_step = -(3 << tab_row);
 140         row_step = -3;
 141         block2 += (3 << (tab_col + tab_row)) - 3;
 142         break;
 143       default:
 144         ASSERT(0);
 145     }
 146   uint err = (err_sum_transformed(block1, block2, (1 << tab_col), (1 << tab_row), (3 << tab_col), col_step, row_step) >> (tab_col + tab_row));
 147   DBG("average error=%d", err);
 148   ctx->error = err;
 149   return err <= ctx->error_threshold;
 150 }
 151
 152 static int
 153 same_size_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2, uint trans)
 154 {
 155   struct image *img1 = &dup1->image;
 156   struct image *img2 = &dup2->image;
 157   if (!img1->pixels || !img2->pixels)
 158     return 1;
 159   ctx->sum_pixels += img1->cols * img1->rows;
 160   byte *block1 = img1->pixels;
 161   byte *block2 = img2->pixels;
 162   int col_step, row_step;
 163   DBG("same_size_compare(trans=%d)",  trans);
 164   switch (trans)
 165     {
 166       case 0: ;
 167         col_step = 3;
 168         row_step = img2->row_size;
 169         break;
 170       case 1:
 171         col_step = -3;
 172         row_step = img2->row_size;
 173         block2 += 3 * (img2->cols - 1);
 174         break;
 175       case 2:
 176         col_step = 3;
 177         row_step = -img2->row_size;
 178         block2 += img2->row_size * (img2->rows - 1);
 179         break;
 180       case 3:
 181         col_step = -3;
 182         row_step = -img2->row_size;
 183         block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
 184         break;
 185       case 4:
 186         col_step = img2->row_size;
 187         row_step = 3;
 188         break;
 189       case 5:
 190         col_step = -img2->row_size;
 191         row_step = 3;
 192         block2 += img2->row_size * (img2->rows - 1);
 193         break;
 194       case 6:
 195         col_step = img2->row_size;
 196         row_step = -3;
 197         block2 += 3 * (img2->cols - 1);
 198         break;
 199       case 7:
 200         col_step = -img2->row_size;
 201         row_step = -3;
 202         block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
 203         break;
 204       default:
 205         ASSERT(0);
 206     }
 207   uint err = (err_sum_transformed(block1, block2, img1->cols, img1->rows, img1->row_size, col_step, row_step) / ((u64)img1->cols * img1->rows));
 208   DBG("average error=%d", err);
 209   ctx->error = err;
 210   return err <= ctx->error_threshold;
 211 }
 212
 213 uint
 214 image_dup_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2)
 215 {
 216   DBG("image_dup_compare(%p, %p)", dup1, dup2);
 217   if (!average_compare(ctx, dup1, dup2))
 218     return 0;
 219   struct image *img1 = &dup1->image;
 220   struct image *img2 = &dup2->image;
 221   uint flags = ctx->flags;
 222   if (flags & IMAGE_DUP_SCALE)
 223     {
 224       DBG("Scale support");
 225       if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->cols, img2->rows))
 226         flags &= ~0x0f;
 227       if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->rows, img2->cols))
 228         flags &= ~0xf0;
 229     }
 230   else
 231     {
 232       DBG("No scale support");
 233       if (!(img1->cols == img2->cols && img1->rows == img2->rows))
 234         flags &= ~0x0f;
 235       if (!(img1->cols == img2->rows && img1->rows == img2->cols))
 236         flags &= ~0xf0;
 237     }
 238   if (!(flags & 0xff))
 239     return 0;
 240   uint result = 0;
 241   if (flags & 0x0f)
 242     {
 243       uint cols = MIN(dup1->tab_cols, dup2->tab_cols);
 244       uint rows = MIN(dup1->tab_rows, dup2->tab_rows);
 245       for (uint t = 0; t < 4; t++)
 246         if (flags & (1 << t))
 247           {
 248             DBG("Testing trans %d", t);
 249             uint i = MAX(cols, rows), depth = 1;
 250             while (i--)
 251               {
 252                 depth++;
 253                 uint col = MAX(0, (int)(cols - i));
 254                 uint row = MAX(0, (int)(rows - i));
 255                 if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 256                   break;
 257                 if (!i &&
 258                     (img1->cols != img2->cols || img1->rows != img2->rows ||
 259                     same_size_compare(ctx, dup1, dup2, t)))
 260                   {
 261                     result |= 1 << t;
 262                     if (!(flags & IMAGE_DUP_WANT_ALL))
 263                       return result;
 264                     else
 265                       break;
 266                   }
 267               }
 268             ctx->sum_depth += depth;
 269           }
 270     }
 271   if (flags & 0xf0)
 272     {
 273       uint cols = MIN(dup1->tab_cols, dup2->tab_rows);
 274       uint rows = MIN(dup1->tab_rows, dup2->tab_cols);
 275       for (uint t = 4; t < 8; t++)
 276         if (flags & (1 << t))
 277           {
 278             DBG("Testing trans %d", t);
 279             uint i = MAX(cols, rows), depth = 1;
 280             while (i--)
 281               {
 282                 depth++;
 283                 uint col = MAX(0, (int)(cols - i));
 284                 uint row = MAX(0, (int)(rows - i));
 285                 if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 286                   break;
 287                 if (!i &&
 288                     (img1->cols != img2->rows || img1->rows != img2->cols ||
 289                     same_size_compare(ctx, dup1, dup2, t)) )
 290                   {
 291                     result |= 1 << t;
 292                     if (!(flags & IMAGE_DUP_WANT_ALL))
 293                       return result;
 294                     else
 295                       break;
 296                   }
 297               }
 298             ctx->sum_depth += depth;
 299           }
 300     }
 301   return result;
 302 }