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