Merge branch 'rot-invariant'

This implements the rotation invariant duplicates search, implemented by Cyril
Roussillon.

The Feature is enabled by default but can be disabled in preferences dialog.

Please note that, due a slightly different fingerprint algorithm, the .sim files
needs to be deleted manually and recreated to get the full benefit.

* rot-invariant:
  Allow to configure rotation invariance
  Slightly better similarity samples
  Implementing rotation invariant duplicates search

diff --git a/src/options.c b/src/options.c
index 460b9cb..f8d0a80 100644 (file)
--- a/src/options.c
+++ b/src/options.c
@@ -38,6 +38,7 @@ ConfOptions *init_options(ConfOptions *options)
 
        options->dnd_icon_size = 48;
        options->duplicates_similarity_threshold = 99;
+       options->rot_invariant_sim = TRUE;
 
        options->file_filter.disable = FALSE;
        options->file_filter.show_dot_directory = FALSE;

diff --git a/src/options.h b/src/options.h
index 138de5a..b44db26 100644 (file)
--- a/src/options.h
+++ b/src/options.h
@@ -29,6 +29,7 @@ struct _ConfOptions
        gboolean update_on_time_change;
 
        guint duplicates_similarity_threshold;
+       gboolean rot_invariant_sim;
 
        gint open_recent_list_maxsize;
        gint dnd_icon_size;

diff --git a/src/preferences.c b/src/preferences.c
index 6707690..1f0e136 100644 (file)
--- a/src/preferences.c
+++ b/src/preferences.c
@@ -290,6 +290,7 @@ static void config_window_apply(void)
        options->image.exif_proof_rotate_enable = c_options->image.exif_proof_rotate_enable;
 
        options->duplicates_similarity_threshold = c_options->duplicates_similarity_threshold;
+       options->rot_invariant_sim = c_options->rot_invariant_sim;
 
        options->tree_descend_subdirs = c_options->tree_descend_subdirs;
 
@@ -1888,11 +1889,12 @@ static void config_tab_behavior(GtkWidget *notebook)
        pref_checkbox_new_int(group, _("Mouse wheel scrolls image"),
                              options->mousewheel_scrolls, &c_options->mousewheel_scrolls);
 
-       group = pref_group_new(vbox, FALSE, _("Miscellaneous"), GTK_ORIENTATION_VERTICAL);
+       group = pref_group_new(vbox, FALSE, _("Similarities"), GTK_ORIENTATION_VERTICAL);
 
        pref_spin_new_int(group, _("Custom similarity threshold:"), NULL,
                          0, 100, 1, options->duplicates_similarity_threshold, (int *)&c_options->duplicates_similarity_threshold);
-
+       pref_checkbox_new_int(group, _("Rotation invariant duplicate check"),
+                             options->rot_invariant_sim, &c_options->rot_invariant_sim);
 
 #ifdef DEBUG
        group = pref_group_new(vbox, FALSE, _("Debugging"), GTK_ORIENTATION_VERTICAL);

diff --git a/src/rcfile.c b/src/rcfile.c
index 0a13784..1e8c569 100644 (file)
--- a/src/rcfile.c
+++ b/src/rcfile.c
@@ -281,6 +281,7 @@ static void write_global_attributes(GString *outstr, gint indent)
        WRITE_NL(); WRITE_BOOL(*options, progressive_key_scrolling);
 
        WRITE_NL(); WRITE_UINT(*options, duplicates_similarity_threshold);
+       WRITE_NL(); WRITE_BOOL(*options, rot_invariant_sim);
        WRITE_SEPARATOR();
 
        WRITE_NL(); WRITE_BOOL(*options, mousewheel_scrolls);
@@ -543,6 +544,7 @@ static gboolean load_global_params(const gchar **attribute_names, const gchar **
                if (READ_BOOL(*options, update_on_time_change)) continue;
 
                if (READ_UINT_CLAMP(*options, duplicates_similarity_threshold, 0, 100)) continue;
+               if (READ_BOOL(*options, rot_invariant_sim)) continue;
 
                if (READ_BOOL(*options, progressive_key_scrolling)) continue;
 

diff --git a/src/similar.c b/src/similar.c
index 52ff7fd..0294711 100644 (file)
--- a/src/similar.c
+++ b/src/similar.c
@@ -169,6 +169,13 @@ void image_sim_alternate_processing(ImageSimilarityData *sd)
 #endif
 }
 
+gint mround(gdouble x)
+{
+       gint ipart = x;
+       gdouble fpart = x-ipart;
+       return (fpart < 0.5 ? ipart : ipart+1);
+}
+
 void image_sim_fill_data(ImageSimilarityData *sd, GdkPixbuf *pixbuf)
 {
        gint w, h;
@@ -182,10 +189,10 @@ void image_sim_fill_data(ImageSimilarityData *sd, GdkPixbuf *pixbuf)
        gint j;
        gint x_inc, y_inc, xy_inc;
        gint xs, ys;
+       gint w_left, h_left;
 
        gboolean x_small = FALSE;       /* if less than 32 w or h, set TRUE */
        gboolean y_small = FALSE;
-
        if (!sd || !pixbuf) return;
 
        w = gdk_pixbuf_get_width(pixbuf);
@@ -197,6 +204,8 @@ void image_sim_fill_data(ImageSimilarityData *sd, GdkPixbuf *pixbuf)
        p_step = has_alpha ? 4 : 3;
        x_inc = w / 32;
        y_inc = h / 32;
+       w_left = w;
+       h_left = h;
 
        if (x_inc < 1)
                {
@@ -209,16 +218,16 @@ void image_sim_fill_data(ImageSimilarityData *sd, GdkPixbuf *pixbuf)
                y_small = TRUE;
                }
 
-       xy_inc = x_inc * y_inc;
-
        j = 0;
 
+       h_left = h;
        for (ys = 0; ys < 32; ys++)
                {
                if (y_small) j = (gdouble)h / 32 * ys;
-
+                       else y_inc = mround((gdouble)h_left/(32-ys));
                i = 0;
 
+               w_left = w;
                for (xs = 0; xs < 32; xs++)
                        {
                        gint x, y;
@@ -227,7 +236,8 @@ void image_sim_fill_data(ImageSimilarityData *sd, GdkPixbuf *pixbuf)
                        guchar *xpos;
 
                        if (x_small) i = (gdouble)w / 32 * xs;
-
+                               else x_inc = mround((gdouble)w_left/(32-xs));
+                       xy_inc = x_inc * y_inc;
                        r = g = b = 0;
                        xpos = pix + (i * p_step);
 
@@ -253,9 +263,11 @@ void image_sim_fill_data(ImageSimilarityData *sd, GdkPixbuf *pixbuf)
                        sd->avg_b[t] = b;
 
                        i += x_inc;
+                       w_left -= x_inc;
                        }
 
                j += y_inc;
+               h_left -= y_inc;
                }
 
        sd->filled = TRUE;
@@ -308,33 +320,59 @@ static gdouble alternate_image_sim_compare_fast(ImageSimilarityData *a, ImageSim
 }
 #endif
 
-gdouble image_sim_compare(ImageSimilarityData *a, ImageSimilarityData *b)
+gdouble image_sim_compare_transfo(ImageSimilarityData *a, ImageSimilarityData *b, gchar transfo)
 {
        gint sim;
-       gint i;
+       gint i1, i2, *i;
+       gint j1, j2, *j;
 
        if (!a || !b || !a->filled || !b->filled) return 0.0;
 
        sim = 0.0;
 
-       for (i = 0; i < 1024; i++)
+       if (transfo & 1) { i = &j2; j = &i2; } else { i = &i2; j = &j2; }
+       for (j1 = 0; j1 < 32; j1++)
                {
-               sim += abs(a->avg_r[i] - b->avg_r[i]);
-               sim += abs(a->avg_g[i] - b->avg_g[i]);
-               sim += abs(a->avg_b[i] - b->avg_b[i]);
+               if (transfo & 2) *j = 31-j1; else *j = j1;
+               for (i1 = 0; i1 < 32; i1++)
+                       {
+                       if (transfo & 4) *i = 31-i1; else *i = i1;
+                       sim += abs(a->avg_r[i1*32+j1] - b->avg_r[i2*32+j2]);
+                       sim += abs(a->avg_g[i1*32+j1] - b->avg_g[i2*32+j2]);
+                       sim += abs(a->avg_b[i1*32+j1] - b->avg_b[i2*32+j2]);
+                       }
                }
 
        return 1.0 - ((gdouble)sim / (255.0 * 1024.0 * 3.0));
 }
 
-/* this uses a cutoff point so that it can abort early when it gets to
- * a point that can simply no longer make the cut-off point.
- */
-gdouble image_sim_compare_fast(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min)
+gdouble image_sim_compare(ImageSimilarityData *a, ImageSimilarityData *b)
+{
+       gint max_t = (options->rot_invariant_sim ? 8 : 1);
+
+       gint t;
+       gdouble score, max_score = 0;
+
+       for(t = 0; t < max_t; t++)
+       {
+               score = image_sim_compare_transfo(a, b, t);
+               if (score > max_score) max_score = score;
+       }
+       return max_score;
+}
+
+
+/*
+4 rotations (0, 90, 180, 270) combined with two mirrors (0, H)
+generate all possible isometric transformations
+= 8 tests
+= change dir of x, change dir of y, exchange x and y = 2^3 = 8
+*/
+gdouble image_sim_compare_fast_transfo(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min, gchar transfo)
 {
        gint sim;
-       gint i;
-       gint j;
+       gint i1, i2, *i;
+       gint j1, j2, *j;
 
 #ifdef ALTERNATE_INCLUDE_COMPARE_CHANGE
        if (alternate_enabled) return alternate_image_sim_compare_fast(a, b, min);
@@ -345,13 +383,16 @@ gdouble image_sim_compare_fast(ImageSimilarityData *a, ImageSimilarityData *b, g
        min = 1.0 - min;
        sim = 0.0;
 
-       for (j = 0; j < 1024; j += 32)
+       if (transfo & 1) { i = &j2; j = &i2; } else { i = &i2; j = &j2; }
+       for (j1 = 0; j1 < 32; j1++)
                {
-               for (i = j; i < j + 32; i++)
+               if (transfo & 2) *j = 31-j1; else *j = j1;
+               for (i1 = 0; i1 < 32; i1++)
                        {
-                       sim += abs(a->avg_r[i] - b->avg_r[i]);
-                       sim += abs(a->avg_g[i] - b->avg_g[i]);
-                       sim += abs(a->avg_b[i] - b->avg_b[i]);
+                       if (transfo & 4) *i = 31-i1; else *i = i1;
+                       sim += abs(a->avg_r[i1*32+j1] - b->avg_r[i2*32+j2]);
+                       sim += abs(a->avg_g[i1*32+j1] - b->avg_g[i2*32+j2]);
+                       sim += abs(a->avg_b[i1*32+j1] - b->avg_b[i2*32+j2]);
                        }
                /* check for abort, if so return 0.0 */
                if ((gdouble)sim / (255.0 * 1024.0 * 3.0) > min) return 0.0;
@@ -359,4 +400,22 @@ gdouble image_sim_compare_fast(ImageSimilarityData *a, ImageSimilarityData *b, g
 
        return (1.0 - ((gdouble)sim / (255.0 * 1024.0 * 3.0)) );
 }
+
+/* this uses a cutoff point so that it can abort early when it gets to
+ * a point that can simply no longer make the cut-off point.
+ */
+gdouble image_sim_compare_fast(ImageSimilarityData *a, ImageSimilarityData *b, gdouble min)
+{
+       gint max_t = (options->rot_invariant_sim ? 8 : 1);
+
+       gint t;
+       gdouble score, max_score = 0;
+
+       for(t = 0; t < max_t; t++)
+       {
+               score = image_sim_compare_fast_transfo(a, b, min, t);
+               if (score > max_score) max_score = score;
+       }
+       return max_score;
+}
 /* vim: set shiftwidth=8 softtabstop=0 cindent cinoptions={1s: */