2 * Copyright (C) 2004 John Ellis
3 * Copyright (C) 2008 - 2016 The Geeqie Team
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.
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.
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.
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.
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)
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)
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.
54 ImageSimilarityData *image_sim_new()
56 auto sd = g_new0(ImageSimilarityData, 1);
61 void image_sim_free(ImageSimilarityData *sd)
66 static gint image_sim_channel_eq_sort_cb(gconstpointer a, gconstpointer b)
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;
75 static void image_sim_channel_equal(guint8 *pix, gint len)
81 buf = g_new0(gint, len * 2);
84 for (i = 0; i < len; i++)
88 buf[p] = static_cast<gint>(pix[i]);
92 qsort(buf, len, sizeof(gint) * 2, image_sim_channel_eq_sort_cb);
95 for (i = 0; i < len; i++)
101 pix[n] = static_cast<guint8>(255 * i / len);
107 static void image_sim_channel_norm(guint8 *pix, gint len)
117 for (i = 0; i < len; i++)
119 if (pix[i] < l) l = pix[i];
120 if (pix[i] > h) h = pix[i];
124 scale = (delta != 0) ? 255.0 / static_cast<gdouble>(delta) : 1.0;
126 for (i = 0; i < len; i++)
128 pix[i] = static_cast<guint8>(static_cast<gdouble>(pix[i] - l) * scale);
133 * The Alternate algorithm is only for testing of new techniques to
134 * improve the result, and hopes to reduce false positives.
136 void image_sim_alternate_processing(ImageSimilarityData *sd)
140 if (!options->alternate_similarity_algorithm.enabled)
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));
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));
153 if (options->alternate_similarity_algorithm.grayscale)
155 for (i = 0; i < (gint)sizeof(sd->avg_r); i++)
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;
165 gint mround(gdouble x)
168 gdouble fpart = x-ipart;
169 return (fpart < 0.5 ? ipart : ipart+1);
172 void image_sim_fill_data(ImageSimilarityData *sd, GdkPixbuf *pixbuf)
192 gboolean x_small = FALSE; /* if less than 32 w or h, set TRUE */
193 gboolean y_small = FALSE;
194 if (!sd || !pixbuf) return;
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);
202 p_step = has_alpha ? 4 : 3;
222 for (ys = 0; ys < 32; ys++)
224 if (y_small) j = static_cast<gdouble>(h) / 32 * ys;
225 else y_inc = mround(static_cast<gdouble>(h_left)/(32-ys));
229 for (xs = 0; xs < 32; xs++)
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;
243 xpos = pix + (i * p_step);
245 for (y = j; y < j + y_inc; y++)
248 for (x = i; x < i + x_inc; x++)
277 ImageSimilarityData *image_sim_new_from_pixbuf(GdkPixbuf *pixbuf)
279 ImageSimilarityData *sd;
281 sd = image_sim_new();
282 image_sim_fill_data(sd, pixbuf);
287 static gdouble alternate_image_sim_compare_fast(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min)
294 if (!a || !b || !a->filled || !b->filled) return 0.0;
300 for (j = 0; j < 1024; j += 32)
302 for (i = j; i < j + 32; i++)
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]);
314 sim += cd + abs(cd - ld);
317 /* check for abort, if so return 0.0 */
318 if ((gdouble)sim / (255.0 * 1024.0 * 4.0) > min) return 0.0;
321 return (1.0 - ((gdouble)sim / (255.0 * 1024.0 * 4.0)) );
324 gdouble image_sim_compare_transfo(ImageSimilarityData *a, ImageSimilarityData *b, gchar transfo)
334 if (!a || !b || !a->filled || !b->filled) return 0.0;
338 if (transfo & 1) { i = &j2; j = &i2; } else { i = &i2; j = &j2; }
339 for (j1 = 0; j1 < 32; j1++)
341 if (transfo & 2) *j = 31-j1; else *j = j1;
342 for (i1 = 0; i1 < 32; i1++)
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]);
351 return 1.0 - (static_cast<gdouble>(sim) / (255.0 * 1024.0 * 3.0));
354 gdouble image_sim_compare(ImageSimilarityData *a, ImageSimilarityData *b)
356 gint max_t = (options->rot_invariant_sim ? 8 : 1);
360 gdouble max_score = 0;
362 for(t = 0; t < max_t; t++)
364 score = image_sim_compare_transfo(a, b, t);
365 if (score > max_score) max_score = score;
372 4 rotations (0, 90, 180, 270) combined with two mirrors (0, H)
373 generate all possible isometric transformations
375 = change dir of x, change dir of y, exchange x and y = 2^3 = 8
377 gdouble image_sim_compare_fast_transfo(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min, gchar transfo)
387 if (options->alternate_similarity_algorithm.enabled)
389 return alternate_image_sim_compare_fast(a, b, min);
392 if (!a || !b || !a->filled || !b->filled) return 0.0;
397 if (transfo & 1) { i = &j2; j = &i2; } else { i = &i2; j = &j2; }
398 for (j1 = 0; j1 < 32; j1++)
400 if (transfo & 2) *j = 31-j1; else *j = j1;
401 for (i1 = 0; i1 < 32; i1++)
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]);
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;
412 return (1.0 - (static_cast<gdouble>(sim) / (255.0 * 1024.0 * 3.0)) );
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.
418 gdouble image_sim_compare_fast(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min)
420 gint max_t = (options->rot_invariant_sim ? 8 : 1);
424 gdouble max_score = 0;
426 for(t = 0; t < max_t; t++)
428 score = image_sim_compare_fast_transfo(a, b, min, t);
429 if (score > max_score) max_score = score;
433 /* vim: set shiftwidth=8 softtabstop=0 cindent cinoptions={1s: */