src/similar.c

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