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