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