src/similar.c

   1 /*
   2  * Geeqie
   3  * (C) 2004 John Ellis
   4  * Copyright (C) 2008 - 2012 The Geeqie Team
   5  *
   6  * Author: John Ellis
   7  *
   8  * This software is released under the GNU General Public License (GNU GPL).
   9  * Please read the included file COPYING for more information.
  10  * This software comes with no warranty of any kind, use at your own risk!
  11  */
  12
  13
  14 #include "main.h"
  15 #include "similar.h"
  16
  17 /*
  18  * These functions are intended to find images with similar color content. For
  19  * example when an image was saved at different compression levels or dimensions
  20  * (scaled down/up) the contents are similar, but these files do not match by file
  21  * size, dimensions, or checksum.
  22  *
  23  * These functions create a 32 x 32 array for each color channel (red, green, blue).
  24  * The array represents the average color of each corresponding part of the
  25  * image. (imagine the image cut into 1024 rectangles, or a 32 x 32 grid.
  26  * Each grid is then processed for the average color value, this is what
  27  * is stored in the array)
  28  *
  29  * To compare two images, generate a ImageSimilarityData for each image, then
  30  * pass them to the compare function. The return value is the percent match
  31  * of the two images. (for this, simple comparisons are used, basically the return
  32  * is an average of the corresponding array differences)
  33  *
  34  * for image_sim_compare(), the return is 0.0 to 1.0:
  35  *  1.0 for exact matches (an image is compared to itself)
  36  *  0.0 for exact opposite images (compare an all black to an all white image)
  37  * generally only a match of > 0.85 are significant at all, and >.95 is useful to
  38  * find images that have been re-saved to other formats, dimensions, or compression.
  39  */
  40
  41
  42 /*
  43  * The experimental (alternate) algorithm is only for testing of new techniques to
  44  * improve the result, and hopes to reduce false positives.
  45  */
  46
  47 static gboolean alternate_enabled = FALSE;
  48
  49 void image_sim_alternate_set(gboolean enable)
  50 {
  51         alternate_enabled = enable;
  52 }
  53
  54 gboolean image_sim_alternate_enabled(void)
  55 {
  56         return alternate_enabled;
  57 }
  58
  59 ImageSimilarityData *image_sim_new(void)
  60 {
  61         ImageSimilarityData *sd = g_new0(ImageSimilarityData, 1);
  62
  63         return sd;
  64 }
  65
  66 void image_sim_free(ImageSimilarityData *sd)
  67 {
  68         g_free(sd);
  69 }
  70
  71 static gint image_sim_channel_eq_sort_cb(gconstpointer a, gconstpointer b)
  72 {
  73         gint *pa = (gpointer)a;
  74         gint *pb = (gpointer)b;
  75         if (pa[1] < pb[1]) return -1;
  76         if (pa[1] > pb[1]) return 1;
  77         return 0;
  78 }
  79
  80 static void image_sim_channel_equal(guint8 *pix, gint len)
  81 {
  82         gint *buf;
  83         gint i;
  84         gint p;
  85
  86         buf = g_new0(gint, len * 2);
  87
  88         p = 0;
  89         for (i = 0; i < len; i++)
  90                 {
  91                 buf[p] = i;
  92                 p++;
  93                 buf[p] = (gint)pix[i];
  94                 p++;
  95                 }
  96
  97         qsort(buf, len, sizeof(gint) * 2, image_sim_channel_eq_sort_cb);
  98
  99         p = 0;
 100         for (i = 0; i < len; i++)
 101                 {
 102                 gint n;
 103
 104                 n = buf[p];
 105                 p += 2;
 106                 pix[n] = (guint8)(255 * i / len);
 107                 }
 108
 109         g_free(buf);
 110 }
 111
 112 static void image_sim_channel_norm(guint8 *pix, gint len)
 113 {
 114         guint8 l, h, delta;
 115         gint i;
 116         gdouble scale;
 117
 118         l = h = pix[0];
 119
 120         for (i = 0; i < len; i++)
 121                 {
 122                 if (pix[i] < l) l = pix[i];
 123                 if (pix[i] > h) h = pix[i];
 124                 }
 125
 126         delta = h - l;
 127         scale = (delta != 0) ? 255.0 / (gdouble)(delta) : 1.0;
 128
 129         for (i = 0; i < len; i++)
 130                 {
 131                 pix[i] = (guint8)((gdouble)(pix[i] - l) * scale);
 132                 }
 133 }
 134
 135 /*
 136  * define these to enable various components of the experimental compare functions
 137  *
 138  * Convert the thumbprint to greyscale (ignore all color information when comparing)
 139  *  #define ALTERNATE_USES_GREYSCALE 1
 140  *
 141  * Take into account the difference in change from one pixel to the next
 142  *  #define ALTERNATE_INCLUDE_COMPARE_CHANGE 1
 143  */
 144
 145 void image_sim_alternate_processing(ImageSimilarityData *sd)
 146 {
 147 #ifdef ALTERNATE_USES_GREYSCALE
 148         gint i;
 149 #endif
 150
 151         if (!alternate_enabled) return;
 152
 153         image_sim_channel_norm(sd->avg_r, sizeof(sd->avg_r));
 154         image_sim_channel_norm(sd->avg_g, sizeof(sd->avg_g));
 155         image_sim_channel_norm(sd->avg_b, sizeof(sd->avg_b));
 156
 157         image_sim_channel_equal(sd->avg_r, sizeof(sd->avg_r));
 158         image_sim_channel_equal(sd->avg_g, sizeof(sd->avg_g));
 159         image_sim_channel_equal(sd->avg_b, sizeof(sd->avg_b));
 160
 161 #ifdef ALTERNATE_USES_GREYSCALE
 162         for (i = 0; i < sizeof(sd->avg_r); i++)
 163                 {
 164                 guint8 n;
 165
 166                 n = (guint8)((gint)(sd->avg_r[i] + sd->avg_g[i] + sd->avg_b[i]) / 3);
 167                 sd->avg_r[i] = sd->avg_g[i] = sd->avg_b[i] = n;
 168                 }
 169 #endif
 170 }
 171
 172 gint mround(gdouble x)
 173 {
 174         gint ipart = x;
 175         gdouble fpart = x-ipart;
 176         return (fpart < 0.5 ? ipart : ipart+1);
 177 }
 178
 179 void image_sim_fill_data(ImageSimilarityData *sd, GdkPixbuf *pixbuf)
 180 {
 181         gint w, h;
 182         gint rs;
 183         guchar *pix;
 184         gboolean has_alpha;
 185         gint p_step;
 186
 187         guchar *p;
 188         gint i;
 189         gint j;
 190         gint x_inc, y_inc, xy_inc;
 191         gint xs, ys;
 192         gint w_left, h_left;
 193
 194         gboolean x_small = FALSE;       /* if less than 32 w or h, set TRUE */
 195         gboolean y_small = FALSE;
 196         if (!sd || !pixbuf) return;
 197
 198         w = gdk_pixbuf_get_width(pixbuf);
 199         h = gdk_pixbuf_get_height(pixbuf);
 200         rs = gdk_pixbuf_get_rowstride(pixbuf);
 201         pix = gdk_pixbuf_get_pixels(pixbuf);
 202         has_alpha = gdk_pixbuf_get_has_alpha(pixbuf);
 203
 204         p_step = has_alpha ? 4 : 3;
 205         x_inc = w / 32;
 206         y_inc = h / 32;
 207         w_left = w;
 208         h_left = h;
 209
 210         if (x_inc < 1)
 211                 {
 212                 x_inc = 1;
 213                 x_small = TRUE;
 214                 }
 215         if (y_inc < 1)
 216                 {
 217                 y_inc = 1;
 218                 y_small = TRUE;
 219                 }
 220
 221         j = 0;
 222
 223         h_left = h;
 224         for (ys = 0; ys < 32; ys++)
 225                 {
 226                 if (y_small) j = (gdouble)h / 32 * ys;
 227                         else y_inc = mround((gdouble)h_left/(32-ys));
 228                 i = 0;
 229
 230                 w_left = w;
 231                 for (xs = 0; xs < 32; xs++)
 232                         {
 233                         gint x, y;
 234                         gint r, g, b;
 235                         gint t;
 236                         guchar *xpos;
 237
 238                         if (x_small) i = (gdouble)w / 32 * xs;
 239                                 else x_inc = mround((gdouble)w_left/(32-xs));
 240                         xy_inc = x_inc * y_inc;
 241                         r = g = b = 0;
 242                         xpos = pix + (i * p_step);
 243
 244                         for (y = j; y < j + y_inc; y++)
 245                                 {
 246                                 p = xpos + (y * rs);
 247                                 for (x = i; x < i + x_inc; x++)
 248                                         {
 249                                         r += *p; p++;
 250                                         g += *p; p++;
 251                                         b += *p; p++;
 252                                         if (has_alpha) p++;
 253                                         }
 254                                 }
 255
 256                         r /= xy_inc;
 257                         g /= xy_inc;
 258                         b /= xy_inc;
 259
 260                         t = ys * 32 + xs;
 261                         sd->avg_r[t] = r;
 262                         sd->avg_g[t] = g;
 263                         sd->avg_b[t] = b;
 264
 265                         i += x_inc;
 266                         w_left -= x_inc;
 267                         }
 268
 269                 j += y_inc;
 270                 h_left -= y_inc;
 271                 }
 272
 273         sd->filled = TRUE;
 274 }
 275
 276 ImageSimilarityData *image_sim_new_from_pixbuf(GdkPixbuf *pixbuf)
 277 {
 278         ImageSimilarityData *sd;
 279
 280         sd = image_sim_new();
 281         image_sim_fill_data(sd, pixbuf);
 282
 283         return sd;
 284 }
 285
 286 #ifdef ALTERNATE_INCLUDE_COMPARE_CHANGE
 287 static gdouble alternate_image_sim_compare_fast(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min)
 288 {
 289         gint sim;
 290         gint i;
 291         gint j;
 292         gint ld;
 293
 294         if (!a || !b || !a->filled || !b->filled) return 0.0;
 295
 296         min = 1.0 - min;
 297         sim = 0.0;
 298         ld = 0;
 299
 300         for (j = 0; j < 1024; j += 32)
 301                 {
 302                 for (i = j; i < j + 32; i++)
 303                         {
 304                         gint cr, cg, cb;
 305                         gint cd;
 306
 307                         cr = abs(a->avg_r[i] - b->avg_r[i]);
 308                         cg = abs(a->avg_g[i] - b->avg_g[i]);
 309                         cb = abs(a->avg_b[i] - b->avg_b[i]);
 310
 311                         cd = cr + cg + cb;
 312                         sim += cd + abs(cd - ld);
 313                         ld = cd / 3;
 314                         }
 315                 /* check for abort, if so return 0.0 */
 316                 if ((gdouble)sim / (255.0 * 1024.0 * 4.0) > min) return 0.0;
 317                 }
 318
 319         return (1.0 - ((gdouble)sim / (255.0 * 1024.0 * 4.0)) );
 320 }
 321 #endif
 322
 323 gdouble image_sim_compare_transfo(ImageSimilarityData *a, ImageSimilarityData *b, gchar transfo)
 324 {
 325         gint sim;
 326         gint i1, i2, *i;
 327         gint j1, j2, *j;
 328
 329         if (!a || !b || !a->filled || !b->filled) return 0.0;
 330
 331         sim = 0.0;
 332
 333         if (transfo & 1) { i = &j2; j = &i2; } else { i = &i2; j = &j2; }
 334         for (j1 = 0; j1 < 32; j1++)
 335                 {
 336                 if (transfo & 2) *j = 31-j1; else *j = j1;
 337                 for (i1 = 0; i1 < 32; i1++)
 338                         {
 339                         if (transfo & 4) *i = 31-i1; else *i = i1;
 340                         sim += abs(a->avg_r[i1*32+j1] - b->avg_r[i2*32+j2]);
 341                         sim += abs(a->avg_g[i1*32+j1] - b->avg_g[i2*32+j2]);
 342                         sim += abs(a->avg_b[i1*32+j1] - b->avg_b[i2*32+j2]);
 343                         }
 344                 }
 345
 346         return 1.0 - ((gdouble)sim / (255.0 * 1024.0 * 3.0));
 347 }
 348
 349 gdouble image_sim_compare(ImageSimilarityData *a, ImageSimilarityData *b)
 350 {
 351         gboolean test_transformations = TRUE; /* could be a function parameter */
 352         gint max_t = (test_transformations ? 8 : 1);
 353
 354         gint t;
 355         gdouble score, max_score = 0;
 356
 357         for(t = 0; t < max_t; t++)
 358         {
 359                 score = image_sim_compare_transfo(a, b, t);
 360                 if (score > max_score) max_score = score;
 361         }
 362         return max_score;
 363 }
 364
 365
 366 /*
 367 4 rotations (0, 90, 180, 270) combined with two mirrors (0, H)
 368 generate all possible isometric transformations
 369 = 8 tests
 370 = change dir of x, change dir of y, exchange x and y = 2^3 = 8
 371 */
 372 gdouble image_sim_compare_fast_transfo(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min, gchar transfo)
 373 {
 374         gint sim;
 375         gint i1, i2, *i;
 376         gint j1, j2, *j;
 377
 378 #ifdef ALTERNATE_INCLUDE_COMPARE_CHANGE
 379         if (alternate_enabled) return alternate_image_sim_compare_fast(a, b, min);
 380 #endif
 381
 382         if (!a || !b || !a->filled || !b->filled) return 0.0;
 383
 384         min = 1.0 - min;
 385         sim = 0.0;
 386
 387         if (transfo & 1) { i = &j2; j = &i2; } else { i = &i2; j = &j2; }
 388         for (j1 = 0; j1 < 32; j1++)
 389                 {
 390                 if (transfo & 2) *j = 31-j1; else *j = j1;
 391                 for (i1 = 0; i1 < 32; i1++)
 392                         {
 393                         if (transfo & 4) *i = 31-i1; else *i = i1;
 394                         sim += abs(a->avg_r[i1*32+j1] - b->avg_r[i2*32+j2]);
 395                         sim += abs(a->avg_g[i1*32+j1] - b->avg_g[i2*32+j2]);
 396                         sim += abs(a->avg_b[i1*32+j1] - b->avg_b[i2*32+j2]);
 397                         }
 398                 /* check for abort, if so return 0.0 */
 399                 if ((gdouble)sim / (255.0 * 1024.0 * 3.0) > min) return 0.0;
 400                 }
 401
 402         return (1.0 - ((gdouble)sim / (255.0 * 1024.0 * 3.0)) );
 403 }
 404
 405 /* this uses a cutoff point so that it can abort early when it gets to
 406  * a point that can simply no longer make the cut-off point.
 407  */
 408 gdouble image_sim_compare_fast(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min)
 409 {
 410         gboolean test_transformations = TRUE; /* could be a function parameter */
 411         gint max_t = (test_transformations ? 8 : 1);
 412
 413         gint t;
 414         gdouble score, max_score = 0;
 415
 416         for(t = 0; t < max_t; t++)
 417         {
 418                 score = image_sim_compare_fast_transfo(a, b, min, t);
 419                 if (score > max_score) max_score = score;
 420         }
 421         return max_score;
 422 }
 423 /* vim: set shiftwidth=8 softtabstop=0 cindent cinoptions={1s: */