src/similar.cc

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