update to trunk

(bzr r12588.1.32)

1 files changed, 305 insertions, 110 deletions

diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp
index ab31d05c3..e2f387c86 100644
--- a/src/libdepixelize/kopftracer2011.cpp
+++ b/src/libdepixelize/kopftracer2011.cpp
@@ -31,7 +31,6 @@
 #include <glibmm/threads.h>
 #endif
 
-#include <utility>
 #include <algorithm>
 #include "kopftracer2011.h"
 #include "priv/colorspace.h"
@@ -40,6 +39,11 @@
 #include "priv/splines-kopf2011.h"
 #include "priv/iterator.h"
 
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+#include <glibmm/datetime.h>
+#include <iostream>
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
 namespace Tracer {
 namespace Heuristics {
 
@@ -86,7 +90,95 @@ Splines Kopf2011::to_voronoi(const std::string &filename,
 Splines Kopf2011::to_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
                              const Options &options)
 {
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    SimplifiedVoronoi<Precision, false> voronoi
+        = _voronoi<Precision, false>(buf, options);
+
+    Glib::DateTime profiling_info[2];
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+
+    Splines ret(voronoi);
+
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::Splines construction time: "
+        << profiling_info[1].difference(profiling_info[0])
+        << std::endl;
+
+    return ret;
+#else // LIBDEPIXELIZE_PROFILE_KOPF2011
     return Splines(_voronoi<Precision, false>(buf, options));
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+}
+
+Splines Kopf2011::to_grouped_voronoi(const std::string &filename,
+                             const Options &options)
+{
+    return to_grouped_voronoi(Gdk::Pixbuf::create_from_file(filename), options);
+}
+
+Splines Kopf2011::to_grouped_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+                             const Options &options)
+{
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    SimplifiedVoronoi<Precision, false> voronoi
+        = _voronoi<Precision, false>(buf, options);
+
+    Glib::DateTime profiling_info[2];
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+
+    HomogeneousSplines<Precision> splines(voronoi);
+
+#else // LIBDEPIXELIZE_PROFILE_KOPF2011
+    HomogeneousSplines<Precision> splines(_voronoi<Precision, false>
+                                          (buf, options));
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::HomogeneousSplines<" << typeid(Precision).name()
+              << ">(Tracer::SimplifiedVoronoi<" << typeid(Precision).name()
+              << ",false>) construction time: "
+              << profiling_info[1].difference(profiling_info[0])
+              << std::endl;
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+    for ( HomogeneousSplines<Precision>::iterator it = splines.begin(),
+              end = splines.end() ; it != end ; ++it ) {
+        for ( HomogeneousSplines<Precision>::Polygon::points_iter
+                  it2 = it->vertices.begin(), end2 = it->vertices.end()
+                  ; it2 != end2 ; ++it2 ) {
+            it2->smooth = false;
+        }
+        for ( HomogeneousSplines<Precision>::Polygon::holes_iter
+                  it2 = it->holes.begin(), end2 = it->holes.end()
+                  ; it2 != end2 ; ++it2 ) {
+            for ( HomogeneousSplines<Precision>::Polygon::points_iter
+                      it3 = it2->begin(), end3 = it2->end()
+                      ; it3 != end3 ; ++it3 ) {
+                it3->smooth = false;
+            }
+        }
+    }
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::Kopf2011::to_grouped_voronoi internal work time: "
+              << profiling_info[1].difference(profiling_info[0])
+              << std::endl;
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+
+    Splines ret(splines, false, options.nthreads);
+
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::Splines construction time: "
+        << profiling_info[1].difference(profiling_info[0])
+        << std::endl;
+
+    return ret;
+#else // LIBDEPIXELIZE_PROFILE_KOPF2011
+    return Splines(splines, false, options.nthreads);
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
 }
 
 Splines Kopf2011::to_splines(const std::string &filename,
@@ -98,9 +190,36 @@ Splines Kopf2011::to_splines(const std::string &filename,
 Splines Kopf2011::to_splines(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
                              const Options &options)
 {
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    SimplifiedVoronoi<Precision, true> voronoi
+        = _voronoi<Precision, true>(buf, options);
+
+    Glib::DateTime profiling_info[2];
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+
+    HomogeneousSplines<Precision> splines(voronoi);
+
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::HomogeneousSplines<" << typeid(Precision).name()
+        << "> construction time: "
+        << profiling_info[1].difference(profiling_info[0])
+        << std::endl;
+
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+
+    Splines ret(splines, options.optimize, options.nthreads);
+
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::Splines construction time: "
+        << profiling_info[1].difference(profiling_info[0])
+        << std::endl;
+
+    return ret;
+#else // LIBDEPIXELIZE_PROFILE_KOPF2011
     HomogeneousSplines<Precision> splines(_voronoi<Precision, true>
                                           (buf, options));
     return Splines(splines, options.optimize, options.nthreads);
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
 }
 
 template<class T, bool adjust_splines>
@@ -108,47 +227,131 @@ SimplifiedVoronoi<T, adjust_splines>
 Kopf2011::_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
                    const Options &options)
 {
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    Glib::DateTime profiling_info[2];
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
     PixelGraph graph(buf);
 
-    /*if ( !graph.width() || !graph.height() )
-        return;*/
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::PixelGraph creation time: "
+              << profiling_info[1].difference(profiling_info[0]) << std::endl;
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+    // gdk-pixbuf2 already checks if image size is meaningful, but asserts state
+    // preconditions and will be useful if gdk-pixbuf is replaced later
+    assert(graph.width() > 0);
+    assert(graph.height() > 0);
 
 #ifndef NDEBUG
     graph.checkConsistency();
 #endif
 
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
     // This step could be part of the initialization of PixelGraph
     // and decrease the necessary number of passes
     graph.connectAllNeighbors();
 
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::PixelGraph::connectAllNeighbors() time: "
+              << profiling_info[1].difference(profiling_info[0]) << std::endl;
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
 #ifndef NDEBUG
     graph.checkConsistency();
 #endif
 
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
     // This step can't be part of PixelGraph initilization without adding some
     // cache misses due to random access patterns that might be injected
     _disconnect_neighbors_with_dissimilar_colors(graph);
 
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::Kopf2011::"
+        "_disconnect_neighbors_with_dissimilar_colors(Tracer::PixelGraph) time: "
+              << profiling_info[1].difference(profiling_info[0]) << std::endl;
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
 #ifndef NDEBUG
     graph.checkConsistency();
 #endif
 
-    // This and below steps must be executed in separate.
-    // Otherwise, there will be colateral effects due to misassumption about the
-    // data being read.
-    _remove_crossing_edges_safe(graph);
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+    {
+        // edges_safe and edges_unsafe must be executed in separate.
+        // Otherwise, there will be colateral effects due to misassumption about
+        // the data being read.
+        PixelGraph::EdgePairContainer edges = graph.crossingEdges();
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::PixelGraph::crossingEdges() time: "
+              << profiling_info[1].difference(profiling_info[0]) << std::endl;
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+        _remove_crossing_edges_safe(edges);
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+        profiling_info[1] = Glib::DateTime::create_now_utc();
+        std::cerr << "Tracer::Kopf2011::_remove_crossing_edges_safe"
+            "(Tracer::PixelGraph) time: "
+                  << profiling_info[1].difference(profiling_info[0])
+                  << std::endl;
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
 
 #ifndef NDEBUG
-    graph.checkConsistency();
+        graph.checkConsistency();
 #endif
 
-    _remove_crossing_edges_unsafe(graph, options);
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+        profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+        _remove_crossing_edges_unsafe(graph, edges, options);
+    }
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::Kopf2011::_remove_crossing_edges_unsafe"
+        "(Tracer::PixelGraph) time: "
+              << profiling_info[1].difference(profiling_info[0]) << std::endl;
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
 
 #ifndef NDEBUG
     graph.checkConsistency();
 #endif
 
+    assert(graph.crossingEdges().size() == 0);
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+    profiling_info[0] = Glib::DateTime::create_now_utc();
+
+    SimplifiedVoronoi<T, adjust_splines> ret(graph);
+
+    profiling_info[1] = Glib::DateTime::create_now_utc();
+    std::cerr << "Tracer::SimplifiedVoronoi<" << typeid(T).name() << ','
+              << (adjust_splines ? "true" : "false")
+              << ">(Tracer::PixelGraph) construction time: "
+              << profiling_info[1].difference(profiling_info[0]) << std::endl;
+
+    return ret;
+#else // LIBDEPIXELIZE_PROFILE_KOPF2011
     return SimplifiedVoronoi<T, adjust_splines>(graph);
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
 }
 
 // TODO: move this function (plus connectAllNeighbors) to PixelGraph constructor
@@ -192,123 +395,115 @@ Kopf2011::_disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph)
  *
  * In this case the two diagonal connections can be safely removed without
  * affecting the final result.
- *
- * \TODO: It should remember/cache who are the unsafe crossing edges?
  */
-inline void Kopf2011::_remove_crossing_edges_safe(PixelGraph &graph)
+template<class T>
+void Kopf2011::_remove_crossing_edges_safe(T &container)
 {
-    if ( graph.width() < 2 || graph.height() < 2 )
-        return;
-
-    PixelGraph::iterator it = graph.begin();
-    for ( int i = 0 ; i != graph.height() - 1 ; ++i, ++it ) {
-        for ( int j = 0 ; j != graph.width() - 1 ; ++j, ++it ) {
-            // this <-> right
-            if ( !it->adj.right )
-                continue;
-
-            // this <-> down
-            if ( !it->adj.bottom )
-                continue;
-
-            PixelGraph::iterator down_right = it + graph.width() + 1;
-
-            // down_right <-> right
-            if ( !down_right->adj.top )
-                continue;
+    for ( typename T::reverse_iterator it = container.rbegin(),
+              end = container.rend() ; it != end ; ) {
+        /* A | B
+           --+--
+           C | D */
+        PixelGraph::iterator a = it->first.first;
+        PixelGraph::iterator b = it->second.first;
+        PixelGraph::iterator c = it->second.second;
+        PixelGraph::iterator d = it->first.second;
+
+        if ( !a->adj.right || !a->adj.bottom || !b->adj.bottom
+             || !c->adj.right ) {
+            ++it;
+            continue;
+        }
 
-            // down_right <-> down
-            if ( !down_right->adj.left )
-                continue;
+        // main diagonal
+        a->adj.bottomright = 0;
+        d->adj.topleft = 0;
 
-            // main diagonal
-            // this <-> down_right
-            it->adj.bottomright = 0;
-            down_right->adj.topleft = 0;
+        // secondary diagonal
+        b->adj.bottomleft = 0;
+        c->adj.topright = 0;
 
-            // secondary diagonal
-            // right <-> down
-            (it + 1)->adj.bottomleft = 0;
-            (it + graph.width())->adj.topright = 0;
-        }
+        // base iterator is always past one
+        typename T::iterator current = --(it.base());
+        ++it;
+        container.erase(current);
     }
 }
 
 /**
  * This method removes crossing edges using the heuristics.
  */
-inline
-void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph,
+template<class T>
+void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, T &edges,
                                              const Options &options)
 {
-    if ( graph.width() < 2 || graph.height() < 2 )
-        return;
-
-    // Iterate over the graph, 2x2 blocks at time
-    PixelGraph::iterator it = graph.begin();
-    for (int i = 0 ; i != graph.height() - 1 ; ++i, ++it ) {
-        for ( int j = 0 ; j != graph.width() - 1 ; ++j, ++it ) {
-            using std::pair;
-            using std::make_pair;
-
-            typedef pair<PixelGraph::iterator, PixelGraph::iterator> Edge;
-            typedef pair<Edge, int> EdgeWeight;
-
-            EdgeWeight diagonals[2] = {
-                make_pair(make_pair(it, graph.nodeBottomRight(it)), 0),
-                make_pair(make_pair(graph.nodeRight(it), graph.nodeBottom(it)),
-                          0)
-            };
-
-            // Check if there are crossing edges
-            if ( !diagonals[0].first.first->adj.bottomright
-                 || !diagonals[1].first.first->adj.bottomleft ) {
-                continue;
-            }
-
-            // Compute weights
-            for ( int i = 0 ; i != 2 ; ++i ) {
-                // Curves and islands heuristics
-                PixelGraph::const_iterator a = diagonals[i].first.first;
-                PixelGraph::const_iterator b = diagonals[i].first.second;
-
-                diagonals[i].second += Heuristics::curves(graph, a, b)
-                    * options.curvesMultiplier;
-
-                diagonals[i].second += Heuristics::islands(a, b)
-                    * options.islandsWeight;
-            }
-
-            {
-                // Sparse pixels heuristic
-                Heuristics::SparsePixels sparse_pixels;
-
-                for ( int i = 0 ; i != 2 ; ++i )
-                    sparse_pixels.diagonals[i] = diagonals[i];
-
-                sparse_pixels(graph, options.sparsePixelsRadius);
-
-                for ( int i = 0 ; i != 2 ; ++i ) {
-                    diagonals[i].second += sparse_pixels.diagonals[i].second
-                        * options.sparsePixelsMultiplier;
-                }
-            }
+    std::vector< std::pair<int, int> > weights(edges.size(),
+                                               std::make_pair(0, 0));
+
+    // Compute weights
+    for ( typename T::size_type i = 0 ; i != edges.size() ; ++i ) {
+        /* A | B
+           --+--
+           C | D */
+        PixelGraph::iterator a = edges[i].first.first;
+        PixelGraph::iterator b = edges[i].second.first;
+        PixelGraph::iterator c = edges[i].second.second;
+        PixelGraph::iterator d = edges[i].first.second;
+
+        // Curves heuristic
+        weights[i].first += Heuristics::curves(graph, a, d)
+            * options.curvesMultiplier;
+        weights[i].second += Heuristics::curves(graph, b, c)
+            * options.curvesMultiplier;
+
+        // Islands heuristic
+        weights[i].first += Heuristics::islands(a, d) * options.islandsWeight;
+        weights[i].second += Heuristics::islands(b, c) * options.islandsWeight;
+
+        // Sparse pixels heuristic
+        using Heuristics::SparsePixels;
+        SparsePixels sparse_pixels;
+
+        sparse_pixels.diagonals[SparsePixels::MAIN_DIAGONAL].first
+            = edges[i].first;
+        sparse_pixels.diagonals[SparsePixels::SECONDARY_DIAGONAL].first
+            = edges[i].second;
+
+        sparse_pixels(graph, options.sparsePixelsRadius);
+
+        weights[i].first
+            += sparse_pixels.diagonals[SparsePixels::MAIN_DIAGONAL].second
+            * options.sparsePixelsMultiplier;
+        weights[i].second
+            += sparse_pixels.diagonals[SparsePixels::SECONDARY_DIAGONAL].second
+            * options.sparsePixelsMultiplier;
+    }
 
-            // Remove edges with lower weight
-            if ( diagonals[0].second > diagonals[1].second ) {
-                diagonals[1].first.first->adj.bottomleft = 0;
-                diagonals[1].first.second->adj.topright = 0;
-            } else if ( diagonals[0].second < diagonals[1].second ) {
-                diagonals[0].first.first->adj.bottomright = 0;
-                diagonals[0].first.second->adj.topleft = 0;
-            } else {
-                diagonals[0].first.first->adj.bottomright = 0;
-                diagonals[0].first.second->adj.topleft = 0;
-                diagonals[1].first.first->adj.bottomleft = 0;
-                diagonals[1].first.second->adj.topright = 0;
-            }
+    // Remove edges with lower weight
+    for ( typename T::size_type i = 0 ; i != edges.size() ; ++i ) {
+        /* A | B
+           --+--
+           C | D */
+        PixelGraph::iterator a = edges[i].first.first;
+        PixelGraph::iterator b = edges[i].second.first;
+        PixelGraph::iterator c = edges[i].second.second;
+        PixelGraph::iterator d = edges[i].first.second;
+
+        if ( weights[i].first > weights[i].second ) {
+            b->adj.bottomleft = 0;
+            c->adj.topright = 0;
+        } else if ( weights[i].first < weights[i].second ) {
+            a->adj.bottomright = 0;
+            d->adj.topleft = 0;
+        } else {
+            a->adj.bottomright = 0;
+            b->adj.bottomleft = 0;
+            c->adj.topright = 0;
+            d->adj.topleft = 0;
         }
     }
+
+    edges.clear();
 }
 
 inline int Heuristics::curves(const PixelGraph &graph,