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 ImageSimilarityData *image_sim_new()
  53 {
  54         auto sd = g_new0(ImageSimilarityData, 1);
  55
  56         return sd;
  57 }
  58
  59 void image_sim_free(ImageSimilarityData *sd)
  60 {
  61         g_free(sd);
  62 }
  63
  64 static gint image_sim_channel_eq_sort_cb(gconstpointer a, gconstpointer b)
  65 {
  66         auto pa = static_cast<const gint *>(a);
  67         auto pb = static_cast<const gint *>(b);
  68         if (pa[1] < pb[1]) return -1;
  69         if (pa[1] > pb[1]) return 1;
  70         return 0;
  71 }
  72
  73 static void image_sim_channel_equal(guint8 *pix, gint len)
  74 {
  75         gint *buf;
  76         gint i;
  77         gint p;
  78
  79         buf = g_new0(gint, len * 2);
  80
  81         p = 0;
  82         for (i = 0; i < len; i++)
  83                 {
  84                 buf[p] = i;
  85                 p++;
  86                 buf[p] = static_cast<gint>(pix[i]);
  87                 p++;
  88                 }
  89
  90         qsort(buf, len, sizeof(gint) * 2, image_sim_channel_eq_sort_cb);
  91
  92         p = 0;
  93         for (i = 0; i < len; i++)
  94                 {
  95                 gint n;
  96
  97                 n = buf[p];
  98                 p += 2;
  99                 pix[n] = static_cast<guint8>(255 * i / len);
 100                 }
 101
 102         g_free(buf);
 103 }
 104
 105 static void image_sim_channel_norm(guint8 *pix, gint len)
 106 {
 107         guint8 l;
 108         guint8 h;
 109         guint8 delta;
 110         gint i;
 111         gdouble scale;
 112
 113         l = h = pix[0];
 114
 115         for (i = 0; i < len; i++)
 116                 {
 117                 if (pix[i] < l) l = pix[i];
 118                 if (pix[i] > h) h = pix[i];
 119                 }
 120
 121         delta = h - l;
 122         scale = (delta != 0) ? 255.0 / static_cast<gdouble>(delta) : 1.0;
 123
 124         for (i = 0; i < len; i++)
 125                 {
 126                 pix[i] = static_cast<guint8>(static_cast<gdouble>(pix[i] - l) * scale);
 127                 }
 128 }
 129
 130 /*
 131  * The Alternate algorithm is only for testing of new techniques to
 132  * improve the result, and hopes to reduce false positives.
 133  */
 134 void image_sim_alternate_processing(ImageSimilarityData *sd)
 135 {
 136         gint i;
 137
 138         if (!options->alternate_similarity_algorithm.enabled)
 139                 {
 140                 return;
 141                 }
 142
 143         image_sim_channel_norm(sd->avg_r, sizeof(sd->avg_r));
 144         image_sim_channel_norm(sd->avg_g, sizeof(sd->avg_g));
 145         image_sim_channel_norm(sd->avg_b, sizeof(sd->avg_b));
 146
 147         image_sim_channel_equal(sd->avg_r, sizeof(sd->avg_r));
 148         image_sim_channel_equal(sd->avg_g, sizeof(sd->avg_g));
 149         image_sim_channel_equal(sd->avg_b, sizeof(sd->avg_b));
 150
 151         if (options->alternate_similarity_algorithm.grayscale)
 152                 {
 153                 for (i = 0; i < (gint)sizeof(sd->avg_r); i++)
 154                         {
 155                         guint8 n;
 156
 157                         n = (guint8)((gint)(sd->avg_r[i] + sd->avg_g[i] + sd->avg_b[i]) / 3);
 158                         sd->avg_r[i] = sd->avg_g[i] = sd->avg_b[i] = n;
 159                         }
 160                 }
 161 }
 162
 163 gint mround(gdouble x)
 164 {
 165         gint ipart = x;
 166         gdouble fpart = x-ipart;
 167         return (fpart < 0.5 ? ipart : ipart+1);
 168 }
 169
 170 void image_sim_fill_data(ImageSimilarityData *sd, GdkPixbuf *pixbuf)
 171 {
 172         gint w;
 173         gint h;
 174         gint rs;
 175         guchar *pix;
 176         gboolean has_alpha;
 177         gint p_step;
 178
 179         guchar *p;
 180         gint i;
 181         gint j;
 182         gint x_inc;
 183         gint y_inc;
 184         gint xy_inc;
 185         gint xs;
 186         gint ys;
 187         gint w_left;
 188         gint h_left;
 189
 190         gboolean x_small = FALSE;       /* if less than 32 w or h, set TRUE */
 191         gboolean y_small = FALSE;
 192         if (!sd || !pixbuf) return;
 193
 194         w = gdk_pixbuf_get_width(pixbuf);
 195         h = gdk_pixbuf_get_height(pixbuf);
 196         rs = gdk_pixbuf_get_rowstride(pixbuf);
 197         pix = gdk_pixbuf_get_pixels(pixbuf);
 198         has_alpha = gdk_pixbuf_get_has_alpha(pixbuf);
 199
 200         p_step = has_alpha ? 4 : 3;
 201         x_inc = w / 32;
 202         y_inc = h / 32;
 203         w_left = w;
 204         h_left = h;
 205
 206         if (x_inc < 1)
 207                 {
 208                 x_inc = 1;
 209                 x_small = TRUE;
 210                 }
 211         if (y_inc < 1)
 212                 {
 213                 y_inc = 1;
 214                 y_small = TRUE;
 215                 }
 216
 217         j = 0;
 218
 219         h_left = h;
 220         for (ys = 0; ys < 32; ys++)
 221                 {
 222                 if (y_small) j = static_cast<gdouble>(h) / 32 * ys;
 223                 else y_inc = mround(static_cast<gdouble>(h_left)/(32-ys));
 224                 i = 0;
 225
 226                 w_left = w;
 227                 for (xs = 0; xs < 32; xs++)
 228                         {
 229                         gint x;
 230                         gint y;
 231                         gint r;
 232                         gint g;
 233                         gint b;
 234                         gint t;
 235                         guchar *xpos;
 236
 237                         if (x_small) i = static_cast<gdouble>(w) / 32 * xs;
 238                         else x_inc = mround(static_cast<gdouble>(w_left)/(32-xs));
 239                         xy_inc = x_inc * y_inc;
 240                         r = g = b = 0;
 241                         xpos = pix + (i * p_step);
 242
 243                         for (y = j; y < j + y_inc; y++)
 244                                 {
 245                                 p = xpos + (y * rs);
 246                                 for (x = i; x < i + x_inc; x++)
 247                                         {
 248                                         r += *p; p++;
 249                                         g += *p; p++;
 250                                         b += *p; p++;
 251                                         if (has_alpha) p++;
 252                                         }
 253                                 }
 254
 255                         r /= xy_inc;
 256                         g /= xy_inc;
 257                         b /= xy_inc;
 258
 259                         t = ys * 32 + xs;
 260                         sd->avg_r[t] = r;
 261                         sd->avg_g[t] = g;
 262                         sd->avg_b[t] = b;
 263
 264                         i += x_inc;
 265                         w_left -= x_inc;
 266                         }
 267
 268                 j += y_inc;
 269                 h_left -= y_inc;
 270                 }
 271
 272         sd->filled = TRUE;
 273 }
 274
 275 ImageSimilarityData *image_sim_new_from_pixbuf(GdkPixbuf *pixbuf)
 276 {
 277         ImageSimilarityData *sd;
 278
 279         sd = image_sim_new();
 280         image_sim_fill_data(sd, pixbuf);
 281
 282         return sd;
 283 }
 284
 285 static gdouble alternate_image_sim_compare_fast(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min)
 286 {
 287         gint sim;
 288         gint i;
 289         gint j;
 290         gint ld;
 291
 292         if (!a || !b || !a->filled || !b->filled) return 0.0;
 293
 294         min = 1.0 - min;
 295         sim = 0.0;
 296         ld = 0;
 297
 298         for (j = 0; j < 1024; j += 32)
 299                 {
 300                 for (i = j; i < j + 32; i++)
 301                         {
 302                         gint cr;
 303                         gint cg;
 304                         gint 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
 322 gdouble image_sim_compare_transfo(ImageSimilarityData *a, ImageSimilarityData *b, gchar transfo)
 323 {
 324         gint sim;
 325         gint i1;
 326         gint i2;
 327         gint *i;
 328         gint j1;
 329         gint j2;
 330         gint *j;
 331
 332         if (!a || !b || !a->filled || !b->filled) return 0.0;
 333
 334         sim = 0.0;
 335
 336         if (transfo & 1) { i = &j2; j = &i2; } else { i = &i2; j = &j2; }
 337         for (j1 = 0; j1 < 32; j1++)
 338                 {
 339                 if (transfo & 2) *j = 31-j1; else *j = j1;
 340                 for (i1 = 0; i1 < 32; i1++)
 341                         {
 342                         if (transfo & 4) *i = 31-i1; else *i = i1;
 343                         sim += abs(a->avg_r[i1*32+j1] - b->avg_r[i2*32+j2]);
 344                         sim += abs(a->avg_g[i1*32+j1] - b->avg_g[i2*32+j2]);
 345                         sim += abs(a->avg_b[i1*32+j1] - b->avg_b[i2*32+j2]);
 346                         }
 347                 }
 348
 349         return 1.0 - (static_cast<gdouble>(sim) / (255.0 * 1024.0 * 3.0));
 350 }
 351
 352 gdouble image_sim_compare(ImageSimilarityData *a, ImageSimilarityData *b)
 353 {
 354         gint max_t = (options->rot_invariant_sim ? 8 : 1);
 355
 356         gint t;
 357         gdouble score;
 358         gdouble max_score = 0;
 359
 360         for(t = 0; t < max_t; t++)
 361         {
 362                 score = image_sim_compare_transfo(a, b, t);
 363                 if (score > max_score) max_score = score;
 364         }
 365         return max_score;
 366 }
 367
 368
 369 /*
 370 4 rotations (0, 90, 180, 270) combined with two mirrors (0, H)
 371 generate all possible isometric transformations
 372 = 8 tests
 373 = change dir of x, change dir of y, exchange x and y = 2^3 = 8
 374 */
 375 gdouble image_sim_compare_fast_transfo(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min, gchar transfo)
 376 {
 377         gint sim;
 378         gint i1;
 379         gint i2;
 380         gint *i;
 381         gint j1;
 382         gint j2;
 383         gint *j;
 384
 385         if (options->alternate_similarity_algorithm.enabled)
 386                 {
 387                 return alternate_image_sim_compare_fast(a, b, min);
 388                 }
 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 (static_cast<gdouble>(sim) / (255.0 * 1024.0 * 3.0) > min) return 0.0;
 408                 }
 409
 410         return (1.0 - (static_cast<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;
 422         gdouble max_score = 0;
 423
 424         for(t = 0; t < max_t; t++)
 425         {
 426                 score = image_sim_compare_fast_transfo(a, b, min, t);
 427                 if (score > max_score) max_score = score;
 428         }
 429         return max_score;
 430 }
 431 /* vim: set shiftwidth=8 softtabstop=0 cindent cinoptions={1s: */