Merging libdepixelize branch

(bzr r12533)

28 files changed, 4150 insertions, 10 deletions

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 42e091f43..c395ce957 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -560,6 +560,7 @@ add_subdirectory(libuemf)
 add_subdirectory(libvpsc)
 add_subdirectory(livarot)
 add_subdirectory(libnrtype)
+add_subdirectory(libdepixelize)
 
 
 get_property(inkscape_global_SRC GLOBAL PROPERTY inkscape_global_SRC)
diff --git a/src/Makefile.am b/src/Makefile.am
index 6fcfa421d..5fd9f36a1 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -23,15 +23,16 @@ endif
 
 
 noinst_LIBRARIES =	\
-	dom/libdom.a		\
-	libcroco/libcroco.a	\
-	libavoid/libavoid.a	\
-	$(internal_GDL)		\
-	libuemf/libuemf.a   \
-	libcola/libcola.a	\
-	libvpsc/libvpsc.a	\
-	livarot/libvarot.a	\
-	2geom/lib2geom.a	\
+	dom/libdom.a			\
+	libcroco/libcroco.a		\
+	libavoid/libavoid.a		\
+	$(internal_GDL)			\
+	libuemf/libuemf.a   		\
+	libcola/libcola.a		\
+	libvpsc/libvpsc.a		\
+	livarot/libvarot.a		\
+	2geom/lib2geom.a		\
+	libdepixelize/libdepixelize.a	\
 	libinkversion.a
 
 all_libs =			\
@@ -138,6 +139,7 @@ include ui/widget/Makefile_insert
 include util/Makefile_insert
 include trace/Makefile_insert
 include 2geom/Makefile_insert
+include libdepixelize/Makefile_insert
 
 # Extra files not mentioned as sources to include in the source tarball
 EXTRA_DIST +=	\
@@ -183,6 +185,7 @@ EXTRA_DIST +=	\
 	show-preview.bmp \
 	sp-skeleton.cpp sp-skeleton.h	\
 	winconsole.cpp \
+	libdepixelize/makefile.in	\
 	$(CXXTEST_TEMPLATE)
 
 # Extra files to remove when doing "make distclean"
diff --git a/src/desktop.cpp b/src/desktop.cpp
index cb56669a8..69d83d8da 100644
--- a/src/desktop.cpp
+++ b/src/desktop.cpp
@@ -1923,6 +1923,7 @@ SPDesktop::show_dialogs()
     mapVerbPreference.insert(std::make_pair ((int)SP_VERB_DIALOG_DISPLAY, "/dialogs/preferences") );
     mapVerbPreference.insert(std::make_pair ((int)SP_VERB_SELECTION_GRIDTILE, "/dialogs/gridtiler") );
     mapVerbPreference.insert(std::make_pair ((int)SP_VERB_SELECTION_TRACE, "/dialogs/trace") );
+    mapVerbPreference.insert(std::make_pair ((int)SP_VERB_SELECTION_PIXEL_ART, "/dialogs/pixelart") );
     mapVerbPreference.insert(std::make_pair ((int)SP_VERB_DIALOG_TEXT, "/dialogs/textandfont") );
     mapVerbPreference.insert(std::make_pair ((int)SP_VERB_DIALOG_EXPORT, "/dialogs/export") );
     mapVerbPreference.insert(std::make_pair ((int)SP_VERB_DIALOG_XML_EDITOR, "/dialogs/xml") );
diff --git a/src/interface.cpp b/src/interface.cpp
index 63d507f3e..ea5eaf16a 100644
--- a/src/interface.cpp
+++ b/src/interface.cpp
@@ -2009,6 +2009,15 @@ void ContextMenu::MakeImageMenu (void)
         mi->set_sensitive(FALSE);
     }
 
+    /* Trace Pixel Art */
+    mi = manage(new Gtk::MenuItem(_("Trace Pixel Art"),1));
+    mi->signal_activate().connect(sigc::mem_fun(*this, &ContextMenu::ImageTracePixelArt));
+    mi->show();
+    insert(*mi,positionOfLastDialog++);
+    if (_desktop->selection->isEmpty()) {
+        mi->set_sensitive(FALSE);
+    }
+
     /* Embed image */
     if (Inkscape::Verb::getbyid( "org.ekips.filter.embedselectedimages" )) {
         mi = manage(new Gtk::MenuItem(C_("Context menu", "Embed Image")));
@@ -2126,6 +2135,12 @@ void ContextMenu::ImageTraceBitmap(void)
     _desktop->_dlg_mgr->showDialog("Trace");
 }
 
+void ContextMenu::ImageTracePixelArt(void)
+{
+    inkscape_dialogs_unhide();
+    _desktop->_dlg_mgr->showDialog("PixelArt");
+}
+
 void ContextMenu::ImageEmbed(void)
 {
     if (_desktop->selection->isEmpty()) {
diff --git a/src/interface.h b/src/interface.h
index 13fbaf9ac..215a3bfc9 100644
--- a/src/interface.h
+++ b/src/interface.h
@@ -239,6 +239,11 @@ class ContextMenu : public Gtk::Menu
         void ImageTraceBitmap(void);
 
         /**
+         * callback, is executed on clicking the "Trace Pixel Art" menu entry
+         */
+        void ImageTracePixelArt(void);
+
+        /**
          * callback, is executed on clicking the "Extract Image" menu entry
          */
         void ImageExtract(void);
diff --git a/src/libdepixelize/CMakeLists.txt b/src/libdepixelize/CMakeLists.txt
new file mode 100644
index 000000000..64a72f9d9
--- /dev/null
+++ b/src/libdepixelize/CMakeLists.txt
@@ -0,0 +1,11 @@
+
+set(libdepixelize_SRC
+	kopftracer2011.cpp
+
+	# -------
+	# Headers
+        kopftracer2011.h
+        splines.h
+)
+
+add_inkscape_lib(depixelize_LIB "${libdepixelize_SRC}")
diff --git a/src/libdepixelize/Makefile_insert b/src/libdepixelize/Makefile_insert
new file mode 100644
index 000000000..75b19bf5c
--- /dev/null
+++ b/src/libdepixelize/Makefile_insert
@@ -0,0 +1,11 @@
+## Makefile.am fragment sourced by src/Makefile.am.
+
+libdepixelize/all: libdepixelize/libdepixelize.a
+
+libdepixelize/clean:
+	rm -f libdepixelize/libdepixelize.a $(libdepixelize_libdepixelize_a_OBJECTS)
+
+libdepixelize_libdepixelize_a_SOURCES =	 \
+	libdepixelize/kopftracer2011.cpp \
+        libdepixelize/kopftracer2011.h   \
+        libdepixelize/splines.h
diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp
new file mode 100644
index 000000000..26ad8863b
--- /dev/null
+++ b/src/libdepixelize/kopftracer2011.cpp
@@ -0,0 +1,470 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+// Build fix under Inkscape build tree
+#if GLIBMM_DISABLE_DEPRECATED && HAVE_GLIBMM_THREADS_H
+#include <glibmm/threads.h>
+#endif
+
+#include <utility>
+#include <algorithm>
+#include "kopftracer2011.h"
+#include "priv/colorspace.h"
+#include "priv/homogeneoussplines.h"
+#include "priv/branchless.h"
+#include "priv/splines.h"
+#include "priv/iterator.h"
+
+namespace Tracer {
+namespace Heuristics {
+
+int curves(const PixelGraph &graph, PixelGraph::const_iterator a,
+           PixelGraph::const_iterator b);
+bool islands(PixelGraph::const_iterator a, PixelGraph::const_iterator b);
+
+struct SparsePixels
+{
+    enum Diagonal {
+        /**
+         * From (first) the top left corner to (second) the bottom right.
+         */
+        MAIN_DIAGONAL      = 0,
+        /**
+         * From (first) the top right to (second) the bottom left.
+         */
+        SECONDARY_DIAGONAL = 1
+    };
+
+    typedef std::pair<PixelGraph::const_iterator, PixelGraph::const_iterator>
+    Edge;
+    typedef std::pair<Edge, int> EdgeWeight;
+
+    void operator()(const PixelGraph &graph, unsigned radius);
+
+    static bool similar_colors(PixelGraph::const_iterator n,
+                               const guint8 (&a)[4], const guint8 (&b)[4]);
+
+    /*
+     * Precondition: Must be filled according to Diagonal enum.
+     */
+    EdgeWeight diagonals[2];
+};
+
+} // namespace Heuristics
+
+Splines Kopf2011::to_voronoi(const std::string &filename,
+                             const Options &options)
+{
+    return to_voronoi(Gdk::Pixbuf::create_from_file(filename), options);
+}
+
+Splines Kopf2011::to_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+                             const Options &options)
+{
+    return Splines(_voronoi<Precision>(buf, options));
+}
+
+Splines Kopf2011::to_splines(const std::string &filename,
+                             const Options &options)
+{
+    return to_splines(Gdk::Pixbuf::create_from_file(filename), options);
+}
+
+Splines Kopf2011::to_splines(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+                             const Options &options)
+{
+    HomogeneousSplines<Precision> splines(_voronoi<Precision>(buf, options));
+    return Splines(splines, options.optimize, options.nthreads);
+}
+
+template<class T>
+SimplifiedVoronoi<T> Kopf2011::_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+                                        const Options &options)
+{
+    PixelGraph graph(buf);
+
+    /*if ( !graph.width() || !graph.height() )
+        return;*/
+
+#ifndef NDEBUG
+    graph.checkConsistency();
+#endif
+
+    // This step could be part of the initialization of PixelGraph
+    // and decrease the necessary number of passes
+    graph.connectAllNeighbors();
+
+#ifndef NDEBUG
+    graph.checkConsistency();
+#endif
+
+    // 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);
+
+#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);
+
+#ifndef NDEBUG
+    graph.checkConsistency();
+#endif
+
+    _remove_crossing_edges_unsafe(graph, options);
+
+#ifndef NDEBUG
+    graph.checkConsistency();
+#endif
+
+    return SimplifiedVoronoi<T>(graph);
+}
+
+// TODO: move this function (plus connectAllNeighbors) to PixelGraph constructor
+inline void
+Kopf2011::_disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph)
+{
+    using colorspace::similar_colors;
+    for ( PixelGraph::iterator it = graph.begin(), end = graph.end() ; it != end
+              ; ++it ) {
+        if ( it->adj.top )
+            it->adj.top = similar_colors(it->rgba, (it - graph.width())->rgba);
+        if ( it->adj.topright ) {
+            it->adj.topright
+                = similar_colors(it->rgba, (it - graph.width() + 1)->rgba);
+        }
+        if ( it->adj.right )
+            it->adj.right = similar_colors(it->rgba, (it + 1)->rgba);
+        if ( it->adj.bottomright ) {
+            it->adj.bottomright
+                = similar_colors(it->rgba, (it + graph.width() + 1)->rgba);
+        }
+        if ( it->adj.bottom ) {
+            it->adj.bottom
+                = similar_colors(it->rgba, (it + graph.width())->rgba);
+        }
+        if ( it->adj.bottomleft ) {
+            it->adj.bottomleft
+                = similar_colors(it->rgba, (it + graph.width() - 1)->rgba);
+        }
+        if ( it->adj.left )
+            it->adj.left = similar_colors(it->rgba, (it - 1)->rgba);
+        if ( it->adj.topleft ) {
+            it->adj.topleft = similar_colors(it->rgba,
+                                             (it - graph.width() - 1)->rgba);
+        }
+    }
+}
+
+/**
+ * This method removes crossing edges if the 2x2 block is fully connected.
+ *
+ * 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)
+{
+    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;
+
+            // down_right <-> down
+            if ( !down_right->adj.left )
+                continue;
+
+            // main diagonal
+            // this <-> down_right
+            it->adj.bottomright = 0;
+            down_right->adj.topleft = 0;
+
+            // secondary diagonal
+            // right <-> down
+            (it + 1)->adj.bottomleft = 0;
+            (it + graph.width())->adj.topright = 0;
+        }
+    }
+}
+
+/**
+ * This method removes crossing edges using the heuristics.
+ */
+inline
+void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph,
+                                             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;
+                }
+            }
+
+            // 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;
+            }
+        }
+    }
+}
+
+inline int Heuristics::curves(const PixelGraph &graph,
+                              PixelGraph::const_iterator a,
+                              PixelGraph::const_iterator b)
+{
+    int count = 1;
+    ToPtr<PixelGraph::Node> to_ptr;
+    ToIter<PixelGraph::Node> to_iter(graph.begin());
+
+    // b -> a
+    // and then a -> b
+    for ( int i = 0 ; i != 2 ; ++i ) {
+        PixelGraph::const_iterator it = i ? a : b;
+        PixelGraph::const_iterator prev = i ? b : a;
+        int local_count = 0;
+
+        // Used to avoid inifinite loops in circular-like edges
+        const PixelGraph::const_iterator initial = it;
+
+        while ( it->adjsize() == 2 ) {
+            ++local_count;
+
+            // Iterate to next
+            {
+                // There are only two values that won't be zero'ed
+                // and one of them has the same value of prev
+                guintptr aux = guintptr(to_ptr(it));
+                aux = (it->adj.top
+                       * guintptr(to_ptr(graph.nodeTop(it))))
+                    + (it->adj.topright
+                       * guintptr(to_ptr(graph.nodeTopRight(it))))
+                    + (it->adj.right
+                       * guintptr(to_ptr(graph.nodeRight(it))))
+                    + (it->adj.bottomright
+                       * guintptr(to_ptr(graph.nodeBottomRight(it))))
+                    + (it->adj.bottom
+                       * guintptr(to_ptr(graph.nodeBottom(it))))
+                    + (it->adj.bottomleft
+                       * guintptr(to_ptr(graph.nodeBottomLeft(it))))
+                    + (it->adj.left
+                       * guintptr(to_ptr(graph.nodeLeft(it))))
+                    + (it->adj.topleft
+                       * guintptr(to_ptr(graph.nodeTopLeft(it))))
+                    - guintptr(to_ptr(prev));
+                prev = it;
+                it = to_iter(reinterpret_cast<PixelGraph::Node const*>(aux));
+            }
+
+            // Break infinite loops
+            if ( it == initial )
+                return local_count;
+        }
+        count += local_count;
+    }
+
+    return count;
+}
+
+inline void Heuristics::SparsePixels::operator ()(const PixelGraph &graph,
+                                                  unsigned radius)
+{
+    if ( !graph.width() || !graph.height() )
+        return;
+
+    // Clear weights
+    for ( int i = 0 ; i != 2 ; ++i )
+        diagonals[i].second = 0;
+
+    if ( !radius )
+        return;
+
+    // Fix radius/bounds
+    {
+        unsigned x = graph.toX(diagonals[MAIN_DIAGONAL].first.first);
+        unsigned y = graph.toY(diagonals[MAIN_DIAGONAL].first.first);
+        unsigned minor = std::min(x, y);
+        unsigned displace = radius - 1;
+
+        if ( displace > minor ) {
+            displace = minor;
+            radius = displace + 1;
+        }
+
+        displace = radius;
+
+        if ( x + displace >= graph.width() ) {
+            displace = unsigned(graph.width()) - x - 1;
+            radius = displace;
+        }
+
+        if ( y + displace >= graph.height() ) {
+            displace = unsigned(graph.height()) - y - 1;
+            radius = displace;
+        }
+    }
+
+    if ( !radius )
+        return;
+
+    // Iterate over nodes and count them
+    {
+        PixelGraph::const_iterator it = diagonals[MAIN_DIAGONAL].first.first;
+        for ( unsigned i = radius - 1 ; i ; --i )
+            it = graph.nodeTopLeft(it);
+
+        bool invert = false;
+        for ( unsigned i = 0 ; i != 2 * radius ; ++i ) {
+            for ( unsigned j = 0 ; j != 2 * radius ; ++j ) {
+                for ( int k = 0 ; k != 2 ; ++k ) {
+                    diagonals[k].second
+                        += similar_colors(it, diagonals[k].first.first->rgba,
+                                          diagonals[k].first.second->rgba);
+                }
+                it = (invert ? graph.nodeLeft(it) : graph.nodeRight(it));
+            }
+            it = (invert ? graph.nodeRight(it) : graph.nodeLeft(it));
+
+
+            invert = !invert;
+            it = graph.nodeBottom(it);
+        }
+    }
+
+    int minor = std::min(diagonals[0].second, diagonals[1].second);
+    for ( int i = 0 ; i != 2 ; ++i )
+        diagonals[i].second -= minor;
+
+    std::swap(diagonals[0].second, diagonals[1].second);
+}
+
+inline bool
+Heuristics::SparsePixels::similar_colors(PixelGraph::const_iterator n,
+                                         const guint8 (&a)[4],
+                                         const guint8 (&b)[4])
+{
+    using colorspace::similar_colors;
+    return similar_colors(n->rgba, a) || similar_colors(n->rgba, b);
+}
+
+inline bool Heuristics::islands(PixelGraph::const_iterator a,
+                                PixelGraph::const_iterator b)
+{
+    if ( a->adjsize() == 1 || b->adjsize() == 1 )
+        return true;
+
+    return false;
+}
+
+} // namespace Tracer
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/libdepixelize/kopftracer2011.h b/src/libdepixelize/kopftracer2011.h
new file mode 100644
index 000000000..73f3b7274
--- /dev/null
+++ b/src/libdepixelize/kopftracer2011.h
@@ -0,0 +1,123 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_KOPFTRACER2011_H
+#define LIBDEPIXELIZE_TRACER_KOPFTRACER2011_H
+
+#include <string>
+
+// Contains exception definitions
+#include <glibmm/fileutils.h>
+#include <gdkmm/pixbuf.h>
+#include "splines.h"
+
+namespace Tracer {
+
+class PixelGraph;
+template<typename T> class SimplifiedVoronoi;
+template<typename T> class HomogeneousSplines;
+
+class Kopf2011
+{
+public:
+    struct Options
+    {
+        enum Defaults {
+            CURVES_MULTIPLIER        = 1,
+            ISLANDS_WEIGHT           = 5,
+            SPARSE_PIXELS_MULTIPLIER = 1,
+            SPARSE_PIXELS_RADIUS     = 4
+        };
+
+        Options() :
+            curvesMultiplier(CURVES_MULTIPLIER),
+            islandsWeight(ISLANDS_WEIGHT),
+            sparsePixelsMultiplier(SPARSE_PIXELS_MULTIPLIER),
+            sparsePixelsRadius(SPARSE_PIXELS_RADIUS),
+            optimize(true),
+            nthreads(1)
+        {}
+
+        // Heuristics
+        double curvesMultiplier;
+        int islandsWeight;
+        double sparsePixelsMultiplier;
+        unsigned sparsePixelsRadius;
+
+        // Other options
+        bool optimize;
+        int nthreads;
+    };
+
+    /**
+     * # Exceptions
+     *
+     * Glib::FileError
+     * Gdk::PixbufError
+     */
+    static Splines to_voronoi(const std::string &filename,
+                              const Options &options = Options());
+
+    static Splines to_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+                              const Options &options = Options());
+
+    /**
+     * # Exceptions
+     *
+     * Glib::FileError
+     * Gdk::PixbufError
+     */
+    static Splines to_splines(const std::string &filename,
+                              const Options &options = Options());
+
+    static Splines to_splines(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+                              const Options &options = Options());
+
+private:
+    typedef double Precision;
+
+    template<class T>
+    static SimplifiedVoronoi<T> _voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+                                         const Options &options);
+
+    static void _disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph);
+    static void _remove_crossing_edges_safe(PixelGraph &graph);
+    static void _remove_crossing_edges_unsafe(PixelGraph &graph,
+                                              const Options &options);
+};
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_KOPFTRACER2011_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/libdepixelize/makefile.in b/src/libdepixelize/makefile.in
new file mode 100644
index 000000000..51d020db1
--- /dev/null
+++ b/src/libdepixelize/makefile.in
@@ -0,0 +1,17 @@
+# Convenience stub makefile to call the real Makefile.
+
+@SET_MAKE@
+
+OBJEXT = @OBJEXT@
+
+# Explicit so that it's the default rule.
+all:
+	cd .. && $(MAKE) libdepixelize/all
+
+clean %.a %.$(OBJEXT):
+	cd .. && $(MAKE) libdepixelize/$@
+
+.PHONY: all clean
+
+.SUFFIXES:
+.SUFFIXES: .a .$(OBJEXT)
diff --git a/src/libdepixelize/priv/branchless.h b/src/libdepixelize/priv/branchless.h
new file mode 100644
index 000000000..487a9688d
--- /dev/null
+++ b/src/libdepixelize/priv/branchless.h
@@ -0,0 +1,58 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_BRANCHLESS_H
+#define LIBDEPIXELIZE_TRACER_BRANCHLESS_H
+
+namespace Tracer {
+
+/**
+ * Branch misprediction proof operations
+ */
+namespace branchless {
+
+/*
+ * All modern processors optimize the branch to a conditional move
+ */
+template<class T>
+T first_if(T first, T second, bool cond)
+{
+    return cond ? first : second;
+}
+
+} // namespace branchless
+} // namespace Tracer {
+
+#endif // LIBDEPIXELIZE_TRACER_BRANCHLESS_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/libdepixelize/priv/colorspace.h b/src/libdepixelize/priv/colorspace.h
new file mode 100644
index 000000000..4982630ad
--- /dev/null
+++ b/src/libdepixelize/priv/colorspace.h
@@ -0,0 +1,111 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_YUV_H
+#define LIBDEPIXELIZE_TRACER_YUV_H
+
+#include <glib.h>
+
+namespace Tracer {
+namespace colorspace {
+
+/**
+ * The same algorithm used in hqx filter
+ */
+inline void rgb2yuv(guint8 r, guint8 g, guint8 b,
+                    guint8 &y, guint8 &u, guint8 &v)
+{
+    y = 0.299 * r + 0.587 * g + 0.114 * b;
+    u = guint16(-0.169 * r - 0.331 * g + 0.5 * b) + 128;
+    v = guint16(0.5 * r - 0.419 * g - 0.081 * b) + 128;
+}
+
+inline void rgb2yuv(const guint8 rgb[], guint8 yuv[])
+{
+    rgb2yuv(rgb[0], rgb[1], rgb[2], yuv[0], yuv[1], yuv[2]);
+}
+
+inline bool same_color(const guint8 (&a)[4], const guint8 (&b)[4])
+{
+    return (a[0] == b[0]
+            && a[1] == b[1]
+            && a[2] == b[2]
+            && a[3] == b[3]);
+}
+
+inline bool dissimilar_colors(const guint8 a[], const guint8 b[])
+{
+    // C uses row-major order, so 
+    // A[2][3] = { {1, 2, 3}, {4, 5, 6} } = {1, 2, 3, 4, 5, 6}
+    guint8 yuv[2][3];
+    rgb2yuv(a, yuv[0]);
+    rgb2yuv(b, yuv[1]);
+
+    // Magic numbers taken from hqx algorithm
+    // Only used to describe the level of tolerance
+    return abs(yuv[0][0] - yuv[1][0]) > 0x30
+        || abs(yuv[0][1] - yuv[1][1]) > 7
+        || abs(yuv[0][2] - yuv[1][2]) > 6;
+}
+
+inline bool similar_colors(const guint8 a[], const guint8 b[])
+{
+    return !dissimilar_colors(a, b);
+}
+
+inline bool shading_edge(const guint8 a[], const guint8 b[])
+{
+    // C uses row-major order, so 
+    // A[2][3] = { {1, 2, 3}, {4, 5, 6} } = {1, 2, 3, 4, 5, 6}
+    guint8 yuv[2][3];
+    rgb2yuv(a, yuv[0]);
+    rgb2yuv(b, yuv[1]);
+
+    // Magic numbers taken from Kopf-Lischinski algorithm
+    // Only used to describe the level of tolerance
+    return abs(yuv[0][0] - yuv[1][0]) <= 100
+        && abs(yuv[0][1] - yuv[1][1]) <= 100
+        && abs(yuv[0][2] - yuv[1][2]) <= 100;
+}
+
+inline bool contour_edge(const guint8 a[], const guint8 b[])
+{
+    return !shading_edge(a, b);
+}
+
+} // namespace colorspace
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_YUV_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/libdepixelize/priv/homogeneoussplines.h b/src/libdepixelize/priv/homogeneoussplines.h
new file mode 100644
index 000000000..57c77a163
--- /dev/null
+++ b/src/libdepixelize/priv/homogeneoussplines.h
@@ -0,0 +1,465 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H
+#define LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H
+
+#include "simplifiedvoronoi.h"
+#include "point.h"
+#include <algorithm>
+#include <utility>
+
+namespace Tracer {
+
+template<typename T>
+class HomogeneousSplines
+{
+public:
+    struct Polygon
+    {
+        Polygon() {}
+        Polygon(const guint8 (&rgba)[4])
+        {
+            for ( int i = 0 ; i != 4 ; ++i )
+                this->rgba[i] = rgba[i];
+        }
+
+        std::vector< Point<T> > vertices;
+
+        /**
+         * It may be benefited from C++11 move references.
+         */
+        std::vector< std::vector< Point<T> > > holes;
+
+        guint8 rgba[4];
+    };
+
+    typedef typename std::vector<Polygon>::iterator iterator;
+    typedef typename std::vector<Polygon>::const_iterator const_iterator;
+    typedef typename std::vector<Polygon>::size_type size_type;
+
+    HomogeneousSplines(const SimplifiedVoronoi<T> &voronoi);
+
+    // Iterators
+    iterator begin()
+    {
+        return _polygons.begin();
+    }
+
+    const_iterator begin() const
+    {
+        return _polygons.begin();
+    }
+
+    iterator end()
+    {
+        return _polygons.end();
+    }
+
+    const_iterator end() const
+    {
+        return _polygons.end();
+    }
+
+    size_type size() const
+    {
+        return _polygons.size();
+    }
+
+    int width() const
+    {
+        return _width;
+    }
+
+    int height() const
+    {
+        return _height;
+    }
+
+private:
+    typedef typename SimplifiedVoronoi<T>::Cell Cell;
+    typedef std::vector< Point<T> > Points;
+
+    typedef typename SimplifiedVoronoi<T>::iterator voronoi_iter;
+    typedef typename SimplifiedVoronoi<T>::const_iterator voronoi_citer;
+
+    typedef typename Points::iterator points_iter;
+    typedef typename Points::const_iterator points_citer;
+    typedef typename Points::reverse_iterator points_riter;
+    typedef typename Points::const_reverse_iterator points_criter;
+
+    typedef std::pair<points_iter, points_iter> points_range;
+    typedef std::pair<points_citer, points_citer> points_crange;
+
+    struct CommonEdge
+    {
+        bool ok; //< share an edge
+        Points *dst;
+        const Points *src;
+
+        // the interval is closed on both ends
+        // different from [begin, end) STL style
+        points_iter dst_begin, dst_end;
+        points_citer src_begin, src_end;
+    };
+
+    struct SelfCommonEdge
+    {
+        bool ok; //< share an edge
+
+        // Greater range. The one that should be erased from the vector.
+        points_riter grt_begin, grt_end;
+
+        // Smaller range. The one that should be used to create a new vector.
+        points_riter sml_begin, sml_end;
+    };
+
+    /**
+     * Return ok == true if they share an edge (more than one point).
+     */
+    CommonEdge _common_edge(Points &dst, const Points &src);
+
+    /**
+     * Return ok == true if they share an edge (more than one point).
+     *
+     *  - [dst_begin, dst_end) will contain the hole polygon
+     *  - [src_begin, src_end) will contain the range to be erased
+     *
+     * It's required to do the search in backward order.
+     */
+    SelfCommonEdge _common_edge(Points &points, points_riter it);
+
+    /*!
+     * Add polygon represented by \p common_edge.src to \p common_edge.dst.
+     */
+    void _polygon_union(CommonEdge common_edge);
+
+    /**
+     * Weird recursive function created to solve the complex problem to fill
+     * polygons holes without the need to store temporaries on the heap nor
+     * changing requirements to some data type that don't invalidate iterators
+     * that point before the current element (maybe I'll write some poetry about
+     * the problem someday).
+     */
+    void _fill_holes(std::vector<Points> &holes, points_iter region_begin,
+                     points_iter region_end);
+
+    std::vector<Polygon> _polygons;
+    int _width;
+    int _height;
+};
+
+template<class T>
+HomogeneousSplines<T>::HomogeneousSplines(const SimplifiedVoronoi<T> &voronoi) :
+    _width(voronoi.width()),
+    _height(voronoi.height())
+{
+    //if (!voronoi.size())
+    //    return;
+    using colorspace::same_color;
+
+    // Identify visible edges (group polygons with the same color)
+    for ( voronoi_citer cell_it = voronoi.begin(), cell_end = voronoi.end()
+              ; cell_it != cell_end ; ++cell_it ) {
+        bool found = false;
+        for ( iterator polygon_it = _polygons.begin(),
+                  polygon_end = _polygons.end()
+                  ; polygon_it != polygon_end ; ++polygon_it ) {
+            if ( same_color(polygon_it->rgba, cell_it->rgba) ) {
+                CommonEdge common_edge = _common_edge(polygon_it->vertices,
+                                                      cell_it->vertices);
+                if ( common_edge.ok ) {
+                    _polygon_union(common_edge);
+                    found = true;
+
+                    for ( iterator polygon2_it = polygon_it + 1
+                              ; polygon2_it != polygon_end ; ++polygon2_it ) {
+                        if ( same_color(polygon_it->rgba, polygon2_it->rgba) ) {
+                            CommonEdge common_edge2
+                                = _common_edge(polygon_it->vertices,
+                                               polygon2_it->vertices);
+                            if ( common_edge2.ok ) {
+                                _polygon_union(common_edge2);
+                                _polygons.erase(polygon2_it);
+                                break;
+                            }
+                        }
+                    }
+
+                    break;
+                }
+            }
+        }
+        if ( !found ) {
+            Polygon polygon(cell_it->rgba);
+            polygon.vertices = cell_it->vertices;
+            _polygons.insert(_polygons.end(), polygon);
+        }
+    }
+
+    // Find polygons with holes and fix them
+    // This iteration runs such complex time-consuming algorithm, but each
+    // polygon has an independent result. They wouldn't even need to share/sync
+    // results and the only waste would be a join at the end of the for.
+    for ( typename std::vector<Polygon>::iterator it = _polygons.begin(),
+              end = _polygons.end() ; it != end ; ++it ) {
+        SelfCommonEdge ce = _common_edge(it->vertices, it->vertices.rbegin());
+        while ( ce.ok ) {
+            _fill_holes(it->holes, ce.sml_end.base(), ce.sml_begin.base());
+            it->vertices.erase(ce.grt_end.base() + 1, ce.grt_begin.base());
+            ce = _common_edge(it->vertices, ce.grt_end);
+        }
+    }
+}
+
+// it can infinite loop if points of both entities are equal,
+// but this shouldn't happen if user has only access to Kopf2011 interface
+template<class T>
+typename HomogeneousSplines<T>::CommonEdge
+HomogeneousSplines<T>::_common_edge(Points &dst, const Points &src)
+{
+    // It's an edge, then the points are closer together. After we find the
+    // first point, there is no need for check against all points of the src
+    // a second time
+
+    const points_iter dst_begin = dst.begin();
+    const points_iter dst_end = dst.end();
+
+    const points_citer src_begin = src.begin();
+    const points_citer src_end = src.end();
+
+    for ( points_iter it = dst_begin ; it != dst_end ; ++it ) {
+        points_citer src_it = std::find(src_begin, src_end, *it);
+
+        if ( src_it == src_end )
+            continue;
+
+        points_iter dst_common_edge_begin = it;
+        points_citer src_common_edge_end = src_it;
+
+        // iterate until find the beginning of the common edge range
+        while ( *dst_common_edge_begin == *src_common_edge_end ) {
+            if ( dst_common_edge_begin == dst_begin )
+                dst_common_edge_begin = dst_end - 1;
+            else
+                --dst_common_edge_begin;
+
+            ++src_common_edge_end;
+            if ( src_common_edge_end == src_end )
+                src_common_edge_end = src_begin;
+        }
+
+        // fix {dst_begin, src_end} range
+        ++dst_common_edge_begin;
+        if ( dst_common_edge_begin == dst_end )
+            dst_common_edge_begin = dst_begin;
+
+        if ( src_common_edge_end == src_begin )
+            src_common_edge_end = src_end - 1;
+        else
+            --src_common_edge_end;
+
+        points_iter dst_common_edge_end = it;
+        points_citer src_common_edge_begin = src_it;
+
+        // find the end of the common edge range
+        while ( *dst_common_edge_end == *src_common_edge_begin ) {
+            ++dst_common_edge_end;
+            if ( dst_common_edge_end == dst_end )
+                dst_common_edge_end = dst_begin;
+
+            if ( src_common_edge_begin == src_begin )
+                src_common_edge_begin = src_end - 1;
+            else
+                --src_common_edge_begin;
+        }
+
+        // fix {dst_end, src_begin} range
+        if ( dst_common_edge_end == dst_begin )
+            dst_common_edge_end = dst_end - 1;
+        else
+            --dst_common_edge_end;
+
+        ++src_common_edge_begin;
+        if ( src_common_edge_begin == src_end )
+            src_common_edge_begin = src_begin;
+
+        CommonEdge ret;
+
+        // if only one point in common
+        if ( dst_common_edge_begin == dst_common_edge_end )
+            continue;
+
+        ret.ok = true;
+
+        ret.dst = &dst;
+        ret.dst_begin = dst_common_edge_begin;
+        ret.dst_end = dst_common_edge_end;
+
+        ret.src = &src;
+        ret.src_begin = src_common_edge_begin;
+        ret.src_end = src_common_edge_end;
+
+        return ret;
+    }
+
+    CommonEdge ret;
+    ret.ok = false;
+    return ret;
+}
+
+template<class T>
+typename HomogeneousSplines<T>::SelfCommonEdge
+HomogeneousSplines<T>::_common_edge(Points &points, points_riter it)
+{
+    SelfCommonEdge ret;
+
+    ret.grt_end = points.rend();
+
+    for ( ; it != ret.grt_end ; ++it ) {
+        ret.sml_end = std::find(it + 1, ret.grt_end, *it);
+
+        if ( ret.sml_end == ret.grt_end )
+            continue;
+
+        ret.grt_begin = it;
+        ret.grt_end = ret.sml_end + 1;
+
+        ret.sml_begin = it;
+
+        while ( *ret.sml_begin == *ret.sml_end ) {
+            ++ret.sml_begin;
+            --ret.sml_end;
+        }
+
+        --ret.sml_begin;
+        ++ret.sml_end;
+        ++ret.sml_end;
+
+        ret.ok = true;
+        return ret;
+    }
+
+    ret.ok = false;
+    return ret;
+}
+
+template<class T>
+void HomogeneousSplines<T>::_polygon_union(CommonEdge common_edge)
+{
+    Points &dst = *common_edge.dst;
+    const Points &src = *common_edge.src;
+
+    // the rotated cell must be inserted before (dst.begin() + index)
+    typename Points::difference_type index;
+
+    // first, we remove the common edge in dst
+    if ( common_edge.dst_begin < common_edge.dst_end ) {
+        // common edge is in the middle of dst
+
+        index = dst.erase(common_edge.dst_begin,
+                          common_edge.dst_end + 1) - dst.begin();
+    } else {
+        // common edge cross the end of dst
+
+        dst.erase(common_edge.dst_begin, dst.end());
+        dst.erase(dst.begin(), common_edge.dst_end);
+        index = dst.end() - dst.begin();
+    }
+
+    // second, we copy src points to polygon
+    if ( common_edge.src_begin < common_edge.src_end ) {
+        // common edge is in the middle of src
+
+        const typename Points::difference_type nfirstinserted
+            = src.end() - common_edge.src_end;
+        const typename Points::difference_type nsecondinserted
+            = 1 + (common_edge.src_begin - src.begin());
+
+        dst.reserve(dst.size() + nfirstinserted + nsecondinserted);
+
+        dst.insert(dst.begin() + index, common_edge.src_end, src.end());
+
+        dst.insert(dst.begin() + index + nfirstinserted,
+                   src.begin(), common_edge.src_begin + 1);
+    } else {
+        // common edge cross the end of src
+
+        dst.reserve(dst.size() + 1
+                    + (common_edge.src_begin - common_edge.src_end));
+
+        dst.insert(dst.begin() + index,
+                   common_edge.src_end, common_edge.src_begin + 1);
+    }
+}
+
+// The following piece of code is so evil that you could end up invoking an
+// ancient beast if you proceed to read it, but I'll be able to explain it in
+// the form of some video (text is not so representative as an image).
+template<class T>
+void HomogeneousSplines<T>::_fill_holes(std::vector<Points> &holes,
+                                        points_iter region_begin,
+                                        points_iter region_end)
+{
+    // the exact location might not always be back and iterators will be
+    // invalidated after some insertions, then the index is required
+    const typename std::vector<Points>::size_type hole_index = holes.size();
+    holes.resize(hole_index + 1);
+
+    for ( points_iter it = region_begin + 1 ; it != region_end ; ++it ) {
+        points_iter res = std::find(it + 1, region_end, *it);
+        if ( res == region_end )
+            continue;
+
+        holes[hole_index].insert(holes[hole_index].end(), region_begin,
+                                 it);
+        region_begin = res;
+
+        do {
+            ++it;
+            --res;
+        } while ( *it == *res );
+        _fill_holes(holes, it - 1, res + 2);
+
+        it = region_begin;
+    }
+
+    holes[hole_index].insert(holes[hole_index].end(), region_begin,
+                             region_end - 1);
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/libdepixelize/priv/iterator.h b/src/libdepixelize/priv/iterator.h
new file mode 100644
index 000000000..7caa9bfa9
--- /dev/null
+++ b/src/libdepixelize/priv/iterator.h
@@ -0,0 +1,123 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_ITERATOR_H
+#define LIBDEPIXELIZE_TRACER_ITERATOR_H
+
+#include <vector>
+#include <iterator>
+
+namespace Tracer {
+
+template<typename T>
+const T *to_ptr(typename std::vector<T>::const_iterator it)
+{
+    return &*it;
+}
+
+template<typename T>
+T *to_ptr(typename std::vector<T>::iterator it)
+{
+    return &*it;
+}
+
+template<typename T>
+typename std::vector<T>::const_iterator to_iterator(T const *ptr,
+                                                    typename std::vector<T>
+                                                    ::const_iterator begin)
+{
+    typedef typename std::vector<T>::const_iterator It;
+    typedef typename std::iterator_traits<It>::difference_type difference_type;
+    difference_type idx = ptr - to_ptr<T>(begin);
+    return begin + idx;
+}
+
+template<typename T>
+typename std::vector<T>::iterator to_iterator(T *ptr,
+                                              typename std::vector<T>::iterator
+                                              begin)
+{
+    typedef typename std::vector<T>::iterator It;
+    typedef typename std::iterator_traits<It>::difference_type difference_type;
+    difference_type idx = ptr - to_ptr<T>(begin);
+    return begin + idx;
+}
+
+template<typename T>
+class ToIter
+{
+public:
+    typedef typename std::vector<T>::const_iterator const_iterator;
+    typedef typename std::vector<T>::iterator iterator;
+
+    ToIter(const_iterator begin) :
+        begin(begin)
+    {}
+
+    const_iterator operator()(T const *ptr) const
+    {
+        return to_iterator<T>(ptr, begin);
+    }
+
+    iterator operator()(T *ptr) const
+    {
+        return to_iterator<T>(ptr, begin);
+    }
+
+private:
+    typename std::vector<T>::const_iterator begin;
+};
+
+template<typename T>
+class ToPtr
+{
+public:
+    typedef typename std::vector<T>::const_iterator const_iterator;
+    typedef typename std::vector<T>::iterator iterator;
+
+    const T *operator()(const_iterator it) const
+    {
+        return to_ptr<T>(it);
+    }
+
+    T *operator()(iterator it) const
+    {
+        return to_ptr<T>(it);
+    }
+};
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_ITERATOR_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/libdepixelize/priv/pixelgraph.h b/src/libdepixelize/priv/pixelgraph.h
new file mode 100644
index 000000000..32523d8ee
--- /dev/null
+++ b/src/libdepixelize/priv/pixelgraph.h
@@ -0,0 +1,490 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_PIXELGRAPH_H
+#define LIBDEPIXELIZE_TRACER_PIXELGRAPH_H
+
+#include <gdkmm/pixbuf.h>
+#include <vector>
+#include <cassert>
+
+namespace Tracer {
+
+class PixelGraph
+{
+public:
+    class Node
+    {
+    public:
+        /*
+         * Hamming weight of \p adj
+         */
+        unsigned adjsize() const
+        {
+            unsigned all[8] = {
+                adj.top,
+                adj.topright,
+                adj.right,
+                adj.bottomright,
+                adj.bottom,
+                adj.bottomleft,
+                adj.left,
+                adj.topleft
+            };
+            return all[0] + all[1] + all[2] + all[3]
+                + all[4] + all[5] + all[6] + all[7];
+        }
+
+        guint8 rgba[4];
+        // Nodes pointing from this
+        struct Adj
+        {
+            unsigned top: 1;
+            unsigned topright: 1;
+            unsigned right: 1;
+            unsigned bottomright: 1;
+            unsigned bottom: 1;
+            unsigned bottomleft: 1;
+            unsigned left: 1;
+            unsigned topleft: 1;
+        } adj;
+    };
+
+    typedef std::vector<Node>::iterator iterator;
+    typedef std::vector<Node>::const_iterator const_iterator;
+    typedef std::vector<Node>::reverse_iterator reverse_iterator;
+    typedef std::vector<Node>::const_reverse_iterator const_reverse_iterator;
+
+    class ColumnView
+    {
+    public:
+        ColumnView(std::vector<Node> &nodes, int width, int column) :
+            _nodes(nodes), _width(width), _column(column)
+        {}
+
+        Node &operator[](int line);
+
+    private:
+        std::vector<Node> &_nodes;
+        const int _width;
+        const int _column;
+    };
+
+    PixelGraph(Glib::RefPtr<Gdk::Pixbuf const> pixbuf);
+
+    void checkConsistency();
+
+    /**
+     * It'll let you access the nodes using the syntax:
+     *
+     *     graph[x][y]
+     *
+     * Where x is the column and y is the line.
+     */
+    ColumnView operator[](int column);
+
+    // Iterators
+    iterator begin()
+    {
+        return _nodes.begin();
+    }
+
+    const_iterator begin() const
+    {
+        return _nodes.begin();
+    }
+
+    iterator end()
+    {
+        return _nodes.end();
+    }
+
+    const_iterator end() const
+    {
+        return _nodes.end();
+    }
+
+    reverse_iterator rbegin()
+    {
+        return _nodes.rbegin();
+    }
+
+    const_reverse_iterator rbegin() const
+    {
+        return _nodes.rbegin();
+    }
+
+    reverse_iterator rend()
+    {
+        return _nodes.rend();
+    }
+
+    const_reverse_iterator rend() const
+    {
+        return _nodes.rend();
+    }
+
+    size_t size() const
+    {
+        return _nodes.size();
+    }
+
+    int width() const
+    {
+        return _width;
+    }
+
+    int height() const
+    {
+        return _height;
+    }
+
+    // Algorithms
+    void connectAllNeighbors();
+
+    int toX(const_iterator n) const
+    {
+        return (&*n - &_nodes[0]) % _width;
+    }
+
+    int toY(const_iterator n) const
+    {
+        return (&*n - &_nodes[0]) / _width;
+    }
+
+    iterator nodeTop(iterator n)
+    {
+        return n - _width;
+    }
+
+    iterator nodeBottom(iterator n)
+    {
+        return n + _width;
+    }
+
+    iterator nodeLeft(iterator n)
+    {
+        return n - 1;
+    }
+
+    iterator nodeRight(iterator n)
+    {
+        return n + 1;
+    }
+
+    iterator nodeTopLeft(iterator n)
+    {
+        return n - _width - 1;
+    }
+
+    iterator nodeTopRight(iterator n)
+    {
+        return n - _width + 1;
+    }
+
+    iterator nodeBottomLeft(iterator n)
+    {
+        return n + _width - 1;
+    }
+
+    iterator nodeBottomRight(iterator n)
+    {
+        return n + _width + 1;
+    }
+
+    const_iterator nodeTop(const_iterator n) const
+    {
+        return n - _width;
+    }
+
+    const_iterator nodeBottom(const_iterator n) const
+    {
+        return n + _width;
+    }
+
+    const_iterator nodeLeft(const_iterator n) const
+    {
+        return n - 1;
+    }
+
+    const_iterator nodeRight(const_iterator n) const
+    {
+        return n + 1;
+    }
+
+    const_iterator nodeTopLeft(const_iterator n) const
+    {
+        return n - _width - 1;
+    }
+
+    const_iterator nodeTopRight(const_iterator n) const
+    {
+        return n - _width + 1;
+    }
+
+    const_iterator nodeBottomLeft(const_iterator n) const
+    {
+        return n + _width - 1;
+    }
+
+    const_iterator nodeBottomRight(const_iterator n) const
+    {
+        return n + _width + 1;
+    }
+
+private:
+    PixelGraph(const PixelGraph&);
+
+    int _width;
+    int _height;
+
+    // The data representation follows the image data pattern from gdk-pixbuf.
+    //
+    // Quoting:
+    // "Image data in a pixbuf is stored in memory in uncompressed, packed
+    // format. Rows in the image are stored top to bottom, and in each row
+    // pixels are stored from left to right. There may be padding at the end of
+    // a row."
+    //
+    // Differently, _nodes don't put padding among rows.
+    std::vector<Node> _nodes;
+};
+
+inline PixelGraph::PixelGraph(Glib::RefPtr<Gdk::Pixbuf const> pixbuf) :
+    _width(pixbuf->get_width()),
+    _height(pixbuf->get_height()),
+    _nodes(size_t(_width) * _height)
+{
+    if ( !_width || !_height )
+        return;
+
+    // Initialize the graph using the pixels' color data
+    guint8 *pixels = pixbuf->get_pixels();
+    Node *dest = &_nodes[0];
+    const int n_channels = pixbuf->get_n_channels();
+    const int rowpadding = pixbuf->get_rowstride() - _width * n_channels;
+
+    if ( n_channels == 4 ) {
+        for ( int i = 0 ; i != _height ; ++i ) {
+            for ( int j = 0 ; j != _width ; ++j ) {
+                for ( int k = 0 ; k != 4 ; ++k )
+                    dest->rgba[k] = pixels[k];
+                {
+                    dest->adj.top = 0;
+                    dest->adj.topright = 0;
+                    dest->adj.right = 0;
+                    dest->adj.bottomright = 0;
+                    dest->adj.bottom = 0;
+                    dest->adj.bottomleft = 0;
+                    dest->adj.left = 0;
+                    dest->adj.topleft = 0;
+                }
+                pixels += n_channels;
+                ++dest;
+            }
+            pixels += rowpadding;
+        }
+    } else {
+        assert(n_channels == 3);
+        for ( int i = 0 ; i != _height ; ++i ) {
+            for ( int j = 0 ; j != _width ; ++j ) {
+                for ( int k = 0 ; k != 3 ; ++k )
+                    dest->rgba[k] = pixels[k];
+                dest->rgba[3] = '\xFF';
+                {
+                    dest->adj.top = 0;
+                    dest->adj.topright = 0;
+                    dest->adj.right = 0;
+                    dest->adj.bottomright = 0;
+                    dest->adj.bottom = 0;
+                    dest->adj.bottomleft = 0;
+                    dest->adj.left = 0;
+                    dest->adj.topleft = 0;
+                }
+                pixels += n_channels;
+                ++dest;
+            }
+            pixels += rowpadding;
+        }
+    }
+}
+
+inline void PixelGraph::checkConsistency()
+{
+    PixelGraph::Node *it = &_nodes.front();
+    for ( int i = 0 ; i != _height ; ++i ) {
+        for ( int j = 0 ; j != _width ; ++j, ++it ) {
+            if ( it->adj.top )
+                assert((it - _width)->adj.bottom);
+            if ( it->adj.topright )
+                assert((it - _width + 1)->adj.bottomleft);
+            if ( it->adj.right )
+                assert((it + 1)->adj.left);
+            if ( it->adj.bottomright )
+                assert((it + _width + 1)->adj.topleft);
+            if ( it->adj.bottom )
+                assert((it + _width)->adj.top);
+            if ( it->adj.bottomleft )
+                assert((it + _width - 1)->adj.topright);
+            if ( it->adj.left )
+                assert((it - 1)->adj.right);
+            if ( it->adj.topleft )
+                assert((it - _width - 1)->adj.bottomright);
+        }
+    }
+}
+
+inline PixelGraph::ColumnView PixelGraph::operator[](int column)
+{
+    return ColumnView(_nodes, _width, column);
+}
+
+inline void PixelGraph::connectAllNeighbors()
+{
+    //  ...the "center" nodes first...
+    if ( _width > 2 && _height > 2 ) {
+        iterator it = nodeBottomRight(begin()); // [1][1]
+        for ( int i = 1 ; i != _height - 1 ; ++i ) {
+            for ( int j = 1 ; j != _width - 1 ; ++j ) {
+                it->adj.top = 1;
+                it->adj.topright = 1;
+                it->adj.right = 1;
+                it->adj.bottomright = 1;
+                it->adj.bottom = 1;
+                it->adj.bottomleft = 1;
+                it->adj.left = 1;
+                it->adj.topleft = 1;
+
+                it = nodeRight(it);
+            }
+            // After the previous loop, 'it' is poiting to the last node from
+            // the row.
+            // Go south, then first node in the row (increment 'it' by 1)
+            // Go to the second node in the line (increment 'it' by 1)
+            it += 2;
+        }
+    }
+
+    //  ...then the "top" nodes...
+    if ( _width > 2 ) {
+        Node *it = &_nodes[1];
+        for ( int i = 1 ; i != _width - 1 ; ++i ) {
+            it->adj.right = 1;
+            it->adj.bottomright = 1;
+            it->adj.bottom = 1;
+            it->adj.bottomleft = 1;
+            it->adj.left = 1;
+
+            ++it;
+        }
+    }
+
+    //  ...then the "bottom" nodes...
+    if ( _width > 2 && _height > 1 ) {
+        Node *it = &((*this)[1][_height - 1]);
+        for ( int i = 1 ; i != _width - 1 ; ++i ) {
+            it->adj.left = 1;
+            it->adj.topleft = 1;
+            it->adj.top = 1;
+            it->adj.topright = 1;
+            it->adj.right = 1;
+
+            ++it;
+        }
+    }
+
+    //  ...then the "left" nodes...
+    if ( _height > 2 ) {
+        iterator it = nodeBottom(begin()); // [0][1]
+        for ( int i = 1 ; i != _height - 1 ; ++i ) {
+            it->adj.top = 1;
+            it->adj.topright = 1;
+            it->adj.right = 1;
+            it->adj.bottomright = 1;
+            it->adj.bottom = 1;
+
+            it = nodeBottom(it);
+        }
+    }
+
+    //  ...then the "right" nodes...
+    if ( _height > 2 && _width > 1 ) {
+        iterator it = nodeBottom(begin() + _width - 1);// [_width - 1][1]
+        for ( int i = 1 ; i != _height - 1 ; ++i ) {
+            it->adj.bottom = 1;
+            it->adj.bottomleft = 1;
+            it->adj.left = 1;
+            it->adj.topleft = 1;
+            it->adj.top = 1;
+
+            it = nodeBottom(it);
+        }
+    }
+
+    //  ...and the 4 corner nodes
+    {
+        Node *const top_left = &(*this)[0][0];
+        top_left->adj.right = 1;
+        top_left->adj.bottomright = 1;
+        top_left->adj.bottom = 1;
+    }
+    if ( _width > 1 ) {
+        Node *const top_right = &(*this)[_width - 1][0];
+        top_right->adj.bottom = 1;
+        top_right->adj.bottomleft = 1;
+        top_right->adj.left = 1;
+    }
+    if ( _height > 1 ) {
+        Node *const down_left = &(*this)[0][_height - 1];
+        down_left->adj.top = 1;
+        down_left->adj.topright = 1;
+        down_left->adj.right = 1;
+    }
+    if ( _width > 1 && _height > 1 ) {
+        Node *const down_right = &(*this)[_width - 1][_height - 1];
+        down_right->adj.left = 1;
+        down_right->adj.topleft = 1;
+        down_right->adj.top = 1;
+    }
+}
+
+inline PixelGraph::Node &PixelGraph::ColumnView::operator[](int line)
+{
+    return _nodes[line * _width + _column];
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_PIXELGRAPH_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/libdepixelize/priv/point.h b/src/libdepixelize/priv/point.h
new file mode 100644
index 000000000..6bea752ed
--- /dev/null
+++ b/src/libdepixelize/priv/point.h
@@ -0,0 +1,75 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_POINT_H
+#define LIBDEPIXELIZE_TRACER_POINT_H
+
+namespace Tracer {
+
+template<class T>
+struct Point
+{
+    Point() {}
+    Point(T x, T y) : x(x), y(y) {}
+    Point(T x, T y, bool smooth) : smooth(smooth), x(x), y(y) {}
+
+    Point operator+(const Point &rhs) const
+    {
+        return Point(x + rhs.x, y + rhs.y);
+    }
+
+    Point operator/(T foo) const
+    {
+        return Point(x / foo, y / foo);
+    }
+
+    bool smooth;
+
+    T x, y;
+};
+
+template<class T>
+inline bool operator==(const Point<T> &lhs, const Point<T> &rhs)
+{
+    return
+#ifndef LIBDEPIXELIZE_IS_VERY_WELL_TESTED
+        lhs.smooth == rhs.smooth &&
+#endif // LIBDEPIXELIZE_IS_VERY_WELL_TESTED
+        lhs.x == rhs.x && lhs.y == rhs.y;
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_POINT_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/libdepixelize/priv/simplifiedvoronoi.h b/src/libdepixelize/priv/simplifiedvoronoi.h
new file mode 100644
index 000000000..a33695ff7
--- /dev/null
+++ b/src/libdepixelize/priv/simplifiedvoronoi.h
@@ -0,0 +1,1324 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_SIMPLIFIEDVORONOI_H
+#define LIBDEPIXELIZE_TRACER_SIMPLIFIEDVORONOI_H
+
+#include "pixelgraph.h"
+#include "colorspace.h"
+#include "point.h"
+#include "branchless.h"
+
+namespace Tracer {
+
+template<typename T>
+class SimplifiedVoronoi
+{
+public:
+    /**
+     * The "smooth" attribute of each vertex is only accurate if edge is
+     * visible. This decision was made because invisible edges will disappear
+     * during polygon-union, the next phase of Kopf-Lischinski.
+     */
+    struct Cell
+    {
+        // There may not exist more than 8 vertices per cell and a
+        // "small vector optimization" could improve the performance
+        // by avoiding memory fragmentation. Serious testing is needed.
+
+        // The vertices are filled in clockwise order
+        std::vector< Point<T> > vertices;
+        guint8 rgba[4];
+    };
+
+    typedef typename std::vector<Cell>::iterator iterator;
+    typedef typename std::vector<Cell>::const_iterator const_iterator;
+    typedef typename std::vector<Cell>::reverse_iterator reverse_iterator;
+
+    typedef typename std::vector<Cell>::const_reverse_iterator
+    const_reverse_iterator;
+
+    /*
+      It will work correctly if no crossing-edges are present.
+     */
+    SimplifiedVoronoi(const PixelGraph &graph);
+
+    // Iterators
+    iterator begin()
+    {
+        return _cells.begin();
+    }
+
+    const_iterator begin() const
+    {
+        return _cells.begin();
+    }
+
+    iterator end()
+    {
+        return _cells.end();
+    }
+
+    const_iterator end() const
+    {
+        return _cells.end();
+    }
+
+    reverse_iterator rbegin()
+    {
+        return _cells.rbegin();
+    }
+
+    const_reverse_iterator rbegin() const
+    {
+        return _cells.rbegin();
+    }
+
+    reverse_iterator rend()
+    {
+        return _cells.rend();
+    }
+
+    const_reverse_iterator rend() const
+    {
+        return _cells.rend();
+    }
+
+    size_t size() const
+    {
+        return _cells.size();
+    }
+
+    int width() const
+    {
+        return _width;
+    }
+
+    int height() const
+    {
+        return _height;
+    }
+
+private:
+    typedef void (*PointTransform)(Point<T> &p, T dx, T dy);
+    typedef bool (*NodeTransform)(PixelGraph::const_iterator);
+
+    static Point<T> _midpoint(const Point<T> &p1, const Point<T> p2)
+    {
+        return Point<T>((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
+    }
+
+    /**
+     * Output is translated by -.5 in each axis. This function fixes this error.
+     */
+    static Point<T> _adjust(Point<T> p)
+    {
+        return Point<T>(p.x + .5, p.y + .5);
+    }
+
+    /**
+     * Output is translated by -.5 in each axis. This function fixes this error.
+     */
+    static Point<T> _adjust(Point<T> p, bool smooth)
+    {
+        return Point<T>(p.x + .5, p.y + .5, smooth);
+    }
+
+    void _complexTopLeft(const PixelGraph &graph,
+                         PixelGraph::const_iterator graph_it,
+                         Cell *const cells_it, int x, int y);
+    void _complexTopRight(const PixelGraph &graph,
+                          PixelGraph::const_iterator graph_it,
+                          Cell *const cells_it, int x, int y);
+    void _complexBottomRight(const PixelGraph &graph,
+                             PixelGraph::const_iterator graph_it,
+                             Cell *const cells_it, int x, int y);
+    void _complexBottomLeft(const PixelGraph &graph,
+                            PixelGraph::const_iterator graph_it,
+                            Cell *const cells_it, int x, int y);
+
+    static void _complexTopLeftTransform(Point<T> &p, T dx, T dy);
+    static void _complexTopRightTransform(Point<T> &p, T dx, T dy);
+    static void _complexBottomRightTransform(Point<T> &p, T dx, T dy);
+    static void _complexBottomLeftTransform(Point<T> &p, T dx, T dy);
+
+    static bool _complexTopLeftTransformTop(PixelGraph::const_iterator graph_it);
+    static bool _complexTopLeftTransformTopRight(PixelGraph::const_iterator graph_it);
+    static bool _complexTopLeftTransformRight(PixelGraph::const_iterator graph_it);
+    static bool _complexTopLeftTransformBottomRight(PixelGraph::const_iterator graph_it);
+    static bool _complexTopLeftTransformBottom(PixelGraph::const_iterator graph_it);
+    static bool _complexTopLeftTransformBottomLeft(PixelGraph::const_iterator graph_it);
+    static bool _complexTopLeftTransformLeft(PixelGraph::const_iterator graph_it);
+    static bool _complexTopLeftTransformTopLeft(PixelGraph::const_iterator graph_it);
+
+    static bool _complexTopRightTransformTop(PixelGraph::const_iterator graph_it);
+    static bool _complexTopRightTransformTopRight(PixelGraph::const_iterator graph_it);
+    static bool _complexTopRightTransformRight(PixelGraph::const_iterator graph_it);
+    static bool _complexTopRightTransformBottomRight(PixelGraph::const_iterator graph_it);
+    static bool _complexTopRightTransformBottom(PixelGraph::const_iterator graph_it);
+    static bool _complexTopRightTransformBottomLeft(PixelGraph::const_iterator graph_it);
+    static bool _complexTopRightTransformLeft(PixelGraph::const_iterator graph_it);
+    static bool _complexTopRightTransformTopLeft(PixelGraph::const_iterator graph_it);
+
+    static bool _complexBottomRightTransformTop(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomRightTransformTopRight(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomRightTransformRight(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomRightTransformBottomRight(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomRightTransformBottom(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomRightTransformBottomLeft(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomRightTransformLeft(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomRightTransformTopLeft(PixelGraph::const_iterator graph_it);
+
+    static bool _complexBottomLeftTransformTop(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomLeftTransformTopRight(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomLeftTransformRight(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomLeftTransformBottomRight(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomLeftTransformBottom(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomLeftTransformBottomLeft(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomLeftTransformLeft(PixelGraph::const_iterator graph_it);
+    static bool _complexBottomLeftTransformTopLeft(PixelGraph::const_iterator graph_it);
+
+    /*
+     * The memory layout assumed goes like this (with a_it being the current
+     * iterated element):
+     *
+     *   (a_it) | (b_it)
+     *   -------+-------
+     *   (c_it) | (d_it)
+     *
+     * If you want to use it with another directions (topleft, topright, ...)
+     * **DO NOT**  invert x or y axis, because the insertion order will go mad.
+     *
+     * The idea behind this abstraction is to rotate the iterators, then the
+     * insertion order will be preserved.
+     *
+     * The initial value of all nodes that will be inserted is {x, y}. All
+     * changes to this node **MUST** occur through \p transform or _adjust.
+     *
+     * Some maintainers may like this function because they will handle a
+     * code base 4 times smaller and bugs will be MUCH MUCH difficult to hide.
+     *
+     * Some maintainers may go mad because the level extra level of
+     * abstracation.
+     *
+     * "All problems in computer science can be solved by another level of
+     *  indirection, except for the problem of too many layers of indirection."
+     *         -- David J. Wheeler
+     */
+    void _genericComplexBottomRight(PixelGraph::const_iterator a_it,
+                                    PixelGraph::const_iterator b_it,
+                                    PixelGraph::const_iterator c_it,
+                                    PixelGraph::const_iterator d_it,
+                                    Cell *const cells_it, int x, int y,
+                                    PointTransform transform,
+                                    NodeTransform top,
+                                    NodeTransform topright,
+                                    NodeTransform right,
+                                    NodeTransform bottomright,
+                                    NodeTransform bottom,
+                                    NodeTransform bottomleft,
+                                    NodeTransform left,
+                                    NodeTransform topleft);
+
+    int _width;
+    int _height;
+    std::vector<Cell> _cells;
+};
+
+template<class T>
+SimplifiedVoronoi<T>::SimplifiedVoronoi(const PixelGraph &graph) :
+    _width(graph.width()),
+    _height(graph.height()),
+    _cells(graph.size())
+{
+    if (!graph.size())
+        return;
+
+    // ...the "center" cells first...
+    if ( _width > 2 && _height > 2 ) {
+        PixelGraph::const_iterator graph_it = graph.begin() + _width + 1;
+        Cell *cells_it = &_cells.front() + _width + 1;
+
+        for ( int i = 1 ; i != _height - 1 ; ++i ) {
+            for ( int j = 1 ; j != _width - 1 ; ++j, ++graph_it, ++cells_it ) {
+                for ( int k = 0 ; k != 4 ; ++k )
+                    cells_it->rgba[k] = graph_it->rgba[k];
+                // Top-left
+                _complexTopLeft(graph, graph_it, cells_it, j, i);
+
+                // Top-right
+                _complexTopRight(graph, graph_it, cells_it, j, i);
+
+                // Bottom-right
+                _complexBottomRight(graph, graph_it, cells_it, j, i);
+
+                // Bottom-left
+                _complexBottomLeft(graph, graph_it, cells_it, j, i);
+            }
+            // After the previous loop, 'it' is poiting to the last cell from
+            // the row.
+            // Go south, then first node in the row (increment 'it' by 1)
+            // Go to the second node in the line (increment 'it' by 1)
+            graph_it += 2;
+            cells_it += 2;
+        }
+    }
+
+    //  ...then the "top" cells...
+    if ( _width > 2 ) {
+        PixelGraph::const_iterator graph_it = graph.begin() + 1;
+        Cell *cells_it = &_cells.front() + 1;
+
+        for ( int i = 1 ; i != _width - 1 ; ++i, ++graph_it, ++cells_it ) {
+            for ( int j = 0 ; j != 4 ; ++j )
+                cells_it->rgba[j] = graph_it->rgba[j];
+
+            // Top-left
+            cells_it->vertices.push_back(Point<T>(i, 0, false));
+
+            // Top-right
+            cells_it->vertices.push_back(Point<T>(i + 1, 0, false));
+
+            // Bottom-right
+            _complexBottomRight(graph, graph_it, cells_it, i, 0);
+
+            // Bottom-left
+            _complexBottomLeft(graph, graph_it, cells_it, i, 0);
+        }
+    }
+
+    //  ...then the "bottom" cells...
+    if ( _width > 2 && _height > 1 ) {
+        // Node *it = &((*this)[1][_height - 1]);
+        PixelGraph::const_iterator graph_it
+            = graph.begin() + (_height - 1) * _width + 1;
+        Cell *cells_it = &_cells.front() + (_height - 1) * _width + 1;
+
+        for ( int i = 1 ; i != _width - 1 ; ++i, ++graph_it, ++cells_it ) {
+            for ( int j = 0 ; j != 4 ; ++j )
+                cells_it->rgba[j] = graph_it->rgba[j];
+
+            // Top-left
+            _complexTopLeft(graph, graph_it, cells_it, i, _height - 1);
+
+            // Top-right
+            _complexTopRight(graph, graph_it, cells_it, i, _height - 1);
+
+            // Bottom-right
+            cells_it->vertices.push_back(Point<T>(i + 1, _height, false));
+
+            // Bottom-left
+            cells_it->vertices.push_back(Point<T>(i, _height, false));
+        }
+    }
+
+    //  ...then the "left" cells...
+    if ( _height > 2 ) {
+        PixelGraph::const_iterator graph_it = graph.begin() + _width;
+        Cell *cells_it = &_cells.front() + _width;
+
+        for ( int i = 1 ; i != _height - 1 ; ++i) {
+            for ( int j = 0 ; j != 4 ; ++j )
+                cells_it->rgba[j] = graph_it->rgba[j];
+
+            // Top-left
+            cells_it->vertices.push_back(Point<T>(0, i, false));
+
+            // Top-right
+            _complexTopRight(graph, graph_it, cells_it, 0, i);
+
+            // Bottom-right
+            _complexBottomRight(graph, graph_it, cells_it, 0, i);
+
+            // Bottom-left
+            cells_it->vertices.push_back(Point<T>(0, i + 1, false));
+
+            graph_it += _width;
+            cells_it += _width;
+        }
+    }
+
+    // ...then the "right" cells...
+    if ( _height > 2 && _width > 1 ) {
+        PixelGraph::const_iterator graph_it = graph.begin() + 2 * _width - 1;
+        Cell *cells_it = &_cells.front() + 2 * _width - 1;
+
+        for ( int i = 1 ; i != _height - 1 ; ++i ) {
+            for ( int j = 0 ; j != 4 ; ++j )
+                cells_it->rgba[j] = graph_it->rgba[j];
+
+            // Top-left
+            _complexTopLeft(graph, graph_it, cells_it, _width - 1, i);
+
+            // Top-right
+            cells_it->vertices.push_back(Point<T>(_width, i, false));
+
+            // Bottom-right
+            cells_it->vertices.push_back(Point<T>(_width, i + 1, false));
+
+            // Bottom-left
+            _complexBottomLeft(graph, graph_it, cells_it, _width - 1, i);
+
+            graph_it += _width;
+            cells_it += _width;
+        }
+    }
+
+    //  ...and the 4 corner nodes
+    // top-left
+    {
+        PixelGraph::const_iterator graph_it = graph.begin();
+        Cell *cells_it = &_cells.front();
+
+        for ( int i = 0 ; i != 4 ; ++i )
+            cells_it->rgba[i] = graph_it->rgba[i];
+
+        // Top-left
+        cells_it->vertices.push_back(Point<T>(0, 0, false));
+
+        // Top-right
+        cells_it->vertices.push_back(Point<T>(1, 0, false));
+
+        // Bottom-right
+        if ( _width > 1 && _height > 1 )
+            _complexBottomRight(graph, graph_it, cells_it, 0, 0);
+        else
+            cells_it->vertices.push_back(Point<T>(1, 1, false));
+
+        // Bottom-left
+        cells_it->vertices.push_back(Point<T>(0, 1, false));
+    }
+
+    // top-right
+    if ( _width > 1 ) {
+        PixelGraph::const_iterator graph_it = graph.begin() + _width - 1;
+        Cell *cells_it = &_cells.front() + _width - 1;
+
+        for ( int i = 0 ; i != 4 ; ++i )
+            cells_it->rgba[i] = graph_it->rgba[i];
+
+        // Top-left
+        cells_it->vertices.push_back(Point<T>(_width - 1, 0, false));
+
+        // Top-right
+        cells_it->vertices.push_back(Point<T>(_width, 0, false));
+
+        // Bottom-right
+        cells_it->vertices.push_back(Point<T>(_width, 1, false));
+
+        // Bottom-left
+        if ( _height > 1 )
+            _complexBottomLeft(graph, graph_it, cells_it, _width - 1, 0);
+        else
+            cells_it->vertices.push_back(Point<T>(_width - 1, 1, false));
+    }
+
+    // bottom-left
+    if ( _height > 1 ) {
+        PixelGraph::const_iterator graph_it
+            = graph.begin() + (_height - 1) * _width;
+        Cell *cells_it = &_cells.front() + (_height - 1) * _width;
+
+        for ( int i = 0 ; i != 4 ; ++i )
+            cells_it->rgba[i] = graph_it->rgba[i];
+
+        // Top-left
+        cells_it->vertices.push_back(Point<T>(0, _height - 1, false));
+
+        // Top-right
+        if ( _width > 1)
+            _complexTopRight(graph, graph_it, cells_it, 0, _height - 1);
+        else
+            cells_it->vertices.push_back(Point<T>(1, _height - 1, false));
+
+        // Bottom-right
+        cells_it->vertices.push_back(Point<T>(1, _height, false));
+
+        // Bottom-left
+        cells_it->vertices.push_back(Point<T>(0, _height, false));
+    }
+
+    // bottom-right
+    if ( _width > 1 && _height > 1 ) {
+        PixelGraph::const_iterator graph_it = --graph.end();
+        Cell *cells_it = &_cells.back();
+
+        for ( int i = 0 ; i != 4 ; ++i )
+            cells_it->rgba[i] = graph_it->rgba[i];
+
+        // Top-left
+        _complexTopLeft(graph, graph_it, cells_it, _width - 1, _height - 1);
+
+        // Top-right
+        cells_it->vertices.push_back(Point<T>(_width, _height - 1, false));
+
+        // Bottom-right
+        cells_it->vertices.push_back(Point<T>(_width, _height, false));
+
+        // Bottom-left
+        cells_it->vertices.push_back(Point<T>(_width - 1, _height, false));
+    }
+}
+
+template<class T> void
+SimplifiedVoronoi<T>::_complexTopLeft(const PixelGraph &graph,
+                                      PixelGraph::const_iterator graph_it,
+                                      Cell *const cells_it, int x, int y)
+{
+    _genericComplexBottomRight(graph_it,
+                               graph.nodeLeft(graph_it),
+                               graph.nodeTop(graph_it),
+                               graph.nodeTopLeft(graph_it),
+                               cells_it, x, y,
+                               &SimplifiedVoronoi::_complexTopLeftTransform,
+                               &SimplifiedVoronoi::_complexTopLeftTransformTop,
+                               &SimplifiedVoronoi::_complexTopLeftTransformTopRight,
+                               &SimplifiedVoronoi::_complexTopLeftTransformRight,
+                               &SimplifiedVoronoi::_complexTopLeftTransformBottomRight,
+                               &SimplifiedVoronoi::_complexTopLeftTransformBottom,
+                               &SimplifiedVoronoi::_complexTopLeftTransformBottomLeft,
+                               &SimplifiedVoronoi::_complexTopLeftTransformLeft,
+                               &SimplifiedVoronoi::_complexTopLeftTransformTopLeft);
+}
+
+template<class T> void
+SimplifiedVoronoi<T>::_complexTopRight(const PixelGraph &graph,
+                                       PixelGraph::const_iterator graph_it,
+                                       Cell *const cells_it, int x, int y)
+{
+    _genericComplexBottomRight(graph_it,
+                               graph.nodeTop(graph_it),
+                               graph.nodeRight(graph_it),
+                               graph.nodeTopRight(graph_it),
+                               cells_it, x, y,
+                               &SimplifiedVoronoi::_complexTopRightTransform,
+                               &SimplifiedVoronoi::_complexTopRightTransformTop,
+                               &SimplifiedVoronoi::_complexTopRightTransformTopRight,
+                               &SimplifiedVoronoi::_complexTopRightTransformRight,
+                               &SimplifiedVoronoi::_complexTopRightTransformBottomRight,
+                               &SimplifiedVoronoi::_complexTopRightTransformBottom,
+                               &SimplifiedVoronoi::_complexTopRightTransformBottomLeft,
+                               &SimplifiedVoronoi::_complexTopRightTransformLeft,
+                               &SimplifiedVoronoi::_complexTopRightTransformTopLeft);
+}
+
+template<class T> void
+SimplifiedVoronoi<T>::_complexBottomRight(const PixelGraph &graph,
+                                          PixelGraph::const_iterator graph_it,
+                                          Cell *const cells_it, int x, int y)
+{
+    _genericComplexBottomRight(graph_it,
+                               graph.nodeRight(graph_it),
+                               graph.nodeBottom(graph_it),
+                               graph.nodeBottomRight(graph_it),
+                               cells_it, x, y,
+                               &SimplifiedVoronoi::_complexBottomRightTransform,
+                               &SimplifiedVoronoi::_complexBottomRightTransformTop,
+                               &SimplifiedVoronoi::_complexBottomRightTransformTopRight,
+                               &SimplifiedVoronoi::_complexBottomRightTransformRight,
+                               &SimplifiedVoronoi::_complexBottomRightTransformBottomRight,
+                               &SimplifiedVoronoi::_complexBottomRightTransformBottom,
+                               &SimplifiedVoronoi::_complexBottomRightTransformBottomLeft,
+                               &SimplifiedVoronoi::_complexBottomRightTransformLeft,
+                               &SimplifiedVoronoi::_complexBottomRightTransformTopLeft);
+}
+
+template<class T> void
+SimplifiedVoronoi<T>::_complexBottomLeft(const PixelGraph &graph,
+                                         PixelGraph::const_iterator graph_it,
+                                         Cell *const cells_it, int x, int y)
+{
+    _genericComplexBottomRight(graph_it,
+                               graph.nodeBottom(graph_it),
+                               graph.nodeLeft(graph_it),
+                               graph.nodeBottomLeft(graph_it),
+                               cells_it, x, y,
+                               &SimplifiedVoronoi::_complexBottomLeftTransform,
+                               &SimplifiedVoronoi::_complexBottomLeftTransformTop,
+                               &SimplifiedVoronoi::_complexBottomLeftTransformTopRight,
+                               &SimplifiedVoronoi::_complexBottomLeftTransformRight,
+                               &SimplifiedVoronoi::_complexBottomLeftTransformBottomRight,
+                               &SimplifiedVoronoi::_complexBottomLeftTransformBottom,
+                               &SimplifiedVoronoi::_complexBottomLeftTransformBottomLeft,
+                               &SimplifiedVoronoi::_complexBottomLeftTransformLeft,
+                               &SimplifiedVoronoi::_complexBottomLeftTransformTopLeft);
+}
+
+template<class T> void
+SimplifiedVoronoi<T>::_complexTopLeftTransform(Point<T> &p, T dx, T dy)
+{
+    p.x -= dx;
+    p.y -= dy;
+}
+
+template<class T> void
+SimplifiedVoronoi<T>::_complexTopRightTransform(Point<T> &p, T dx, T dy)
+{
+    p.x += dy;
+    p.y -= dx;
+}
+
+template<class T> void
+SimplifiedVoronoi<T>::_complexBottomRightTransform(Point<T> &p, T dx, T dy)
+{
+    p.x += dx;
+    p.y += dy;
+}
+
+template<class T> void
+SimplifiedVoronoi<T>::_complexBottomLeftTransform(Point<T> &p, T dx, T dy)
+{
+    p.x -= dy;
+    p.y += dx;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopLeftTransformTop(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottom;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopLeftTransformTopRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottomleft;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopLeftTransformRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.left;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopLeftTransformBottomRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.topleft;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopLeftTransformBottom(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.top;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopLeftTransformBottomLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.topright;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopLeftTransformLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.right;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopLeftTransformTopLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottomright;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopRightTransformTop(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.left;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopRightTransformTopRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.topleft;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopRightTransformRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.top;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopRightTransformBottomRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.topright;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopRightTransformBottom(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.right;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopRightTransformBottomLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottomright;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopRightTransformLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottom;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexTopRightTransformTopLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottomleft;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomRightTransformTop(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.top;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomRightTransformTopRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.topright;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomRightTransformRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.right;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomRightTransformBottomRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottomright;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomRightTransformBottom(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottom;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomRightTransformBottomLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottomleft;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomRightTransformLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.left;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomRightTransformTopLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.topleft;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomLeftTransformTop(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.right;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomLeftTransformTopRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottomright;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomLeftTransformRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottom;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomLeftTransformBottomRight(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.bottomleft;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomLeftTransformBottom(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.left;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomLeftTransformBottomLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.topleft;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomLeftTransformLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.top;
+}
+
+template<class T>
+bool SimplifiedVoronoi<T>::_complexBottomLeftTransformTopLeft(PixelGraph::const_iterator graph_it)
+{
+    return graph_it->adj.topright;
+}
+
+template<class T>
+void
+SimplifiedVoronoi<T>
+::_genericComplexBottomRight(PixelGraph::const_iterator a_it,
+                             PixelGraph::const_iterator b_it,
+                             PixelGraph::const_iterator c_it,
+                             PixelGraph::const_iterator d_it,
+                             Cell *const cells_it, int x, int y,
+                             PointTransform transform,
+                             NodeTransform top,
+                             NodeTransform topright,
+                             NodeTransform right,
+                             NodeTransform bottomright,
+                             NodeTransform bottom,
+                             NodeTransform bottomleft,
+                             NodeTransform left,
+                             NodeTransform topleft)
+{
+    using colorspace::contour_edge;
+    using colorspace::same_color;
+
+    const Point<T> initial(x, y);
+
+    if ( bottomright(a_it) ) {
+        // this and bottom-right are connected
+
+        bool smooth[2] = {
+            same_color(a_it->rgba, d_it->rgba) + right(a_it),
+            same_color(a_it->rgba, d_it->rgba) + bottom(a_it)
+        };
+
+        Point<T> borderMid = initial;
+        {
+            transform(borderMid, 1, 1);
+            borderMid = _midpoint(initial, borderMid);
+        }
+
+        Point<T> vertices[2] = {initial, initial};
+        {
+            transform(vertices[0], 1, 0);
+            vertices[0] = _adjust(_midpoint(borderMid, vertices[0]), smooth[0]);
+
+            transform(vertices[1], 0, 1);
+            vertices[1] = _adjust(_midpoint(borderMid, vertices[1]), smooth[1]);
+        }
+
+        if ( !smooth[0] ) {
+            cells_it->vertices.push_back(vertices[0]);
+            {
+                Point<T> another = vertices[0];
+                transform(another,
+                          - ( 0.1875
+                              - ( topright(a_it) - topleft(b_it) ) * 0.1875 ),
+                          // y
+                          - ( 0.5625
+                              - ( topright(a_it) + topleft(b_it) ) * 0.1875 ));
+                cells_it->vertices.push_back(another);
+            }
+            {
+                Point<T> another = vertices[0];
+                transform(another,
+                          - ( 0.0625
+                              - ( topright(a_it) - topleft(b_it) ) * 0.0625 ),
+                          // y
+                          - ( 0.1875
+                              - ( topright(a_it) + topleft(b_it) ) * 0.0625) );
+                another.smooth = true;
+                cells_it->vertices.push_back(another);
+            }
+            {
+                Point<T> another = vertices[0];
+                transform(another,
+                          0.1875
+                          - ( bottomright(b_it) + topright(d_it) ) * 0.0625,
+                          // y
+                          0.0625
+                          + ( bottomright(b_it) - topright(d_it) ) * 0.0625);
+                cells_it->vertices.push_back(another);
+            }
+            {
+                transform(vertices[0],
+                          0.0625
+                          + ( topright(a_it) - topright(d_it) - topleft(b_it)
+                              - bottomright(b_it) ) * 0.03125,
+                          // y
+                          - ( 0.0625
+                              + ( topright(d_it) - topright(a_it)
+                                  - topleft(b_it) - bottomright(b_it) )
+                              * 0.03125 ));
+            }
+        }
+
+        cells_it->vertices.push_back(vertices[0]);
+
+        if ( !smooth[1] ) {
+            {
+                Point<T> another = vertices[1];
+                transform(another,
+                          - ( 0.0625
+                              + ( bottomleft(d_it) - bottomleft(a_it)
+                                  - topleft(c_it) - bottomright(c_it) )
+                              * 0.03125 ),
+                          // y
+                          0.0625
+                          + ( bottomleft(a_it) - bottomleft(d_it)
+                              - topleft(c_it) - bottomright(c_it) ) * 0.03125);
+                cells_it->vertices.push_back(another);
+            }
+            {
+                Point<T> another = vertices[1];
+                transform(another,
+                          0.0625
+                          + ( bottomright(c_it) - bottomleft(d_it) ) * 0.0625,
+                          // y
+                          0.1875
+                          - ( bottomright(c_it) + bottomleft(d_it) ) * 0.0625);
+                cells_it->vertices.push_back(another);
+            }
+            {
+                Point<T> another = vertices[1];
+                transform(another,
+                          - ( 0.1875
+                              - ( bottomleft(a_it) + topleft(c_it) )
+                              * 0.0625 ),
+                          // y
+                          - ( 0.0625
+                              - ( bottomleft(a_it) - topleft(c_it) )
+                              * 0.0625 ));
+                another.smooth = true;
+                cells_it->vertices.push_back(another);
+            }
+            {
+                Point<T> another = vertices[1];
+                transform(another,
+                          - ( 0.5625
+                              - ( bottomleft(a_it) + topleft(c_it) )
+                              * 0.1875 ),
+                          // y
+                          - ( 0.1875
+                              - ( bottomleft(a_it) - topleft(c_it) )
+                              * 0.1875 ));
+                cells_it->vertices.push_back(another);
+            }
+        }
+
+        cells_it->vertices.push_back(vertices[1]);
+    } else if ( bottomleft(b_it) ) {
+        // right and bottom are connected
+
+        Point<T> vertex = initial;
+        transform(vertex, 1, 1);
+        vertex = _adjust(_midpoint(_midpoint(initial, vertex), initial), true);
+        cells_it->vertices.push_back(vertex);
+    } else {
+        // Connections don't affect the shape of this squared-like
+        // pixel
+
+        Point<T> vertex = initial;
+        transform(vertex, 1, 1);
+        vertex = _adjust(_midpoint(initial, vertex));
+
+        // compute smoothness
+        if ( right(a_it) ) {
+            // this and right are connected
+
+            if ( !right(c_it) && !( bottom(a_it) && bottom(b_it) ) ) {
+                // bottom and bottom-right are disconnected
+
+                bool foreign_is_contour = contour_edge(c_it->rgba, d_it->rgba);
+                bool twin_is_contour = contour_edge(b_it->rgba, d_it->rgba);
+                bool another_is_contour = contour_edge(a_it->rgba, c_it->rgba);
+
+                if ( another_is_contour + twin_is_contour
+                     + foreign_is_contour == 2 ) {
+                    vertex.smooth = !foreign_is_contour;
+
+                    if ( !vertex.smooth ) {
+                        if ( another_is_contour ) {
+                            {
+                                Point<T> another = vertex;
+                                T amount = 0.125
+                                    - ( ( bottomright(c_it) + topleft(c_it) )
+                                        * 0.03125 );
+                                transform(another, - amount, amount);
+                                cells_it->vertices.push_back(another);
+                            }
+                            {
+                                Point<T> another = vertex;
+                                T amount = 0.0625 * bottomright(c_it);
+                                transform(another, amount, 0.25 - amount);
+                                cells_it->vertices.push_back(another);
+                            }
+                            {
+                                Point<T> another = vertex;
+                                T amount = 0.0625 * topleft(c_it);
+                                transform(another, - ( 0.25 - amount ),
+                                          - amount);
+                                another.smooth = true;
+                                cells_it->vertices.push_back(another);
+                            }
+                            {
+                                Point<T> another = vertex;
+                                T amount = 0.1875 * topleft(c_it);
+                                transform(another, - ( 0.75 - amount ),
+                                          - amount);
+                                cells_it->vertices.push_back(another);
+                            }
+                        } else if ( twin_is_contour ) {
+                            T amount = 0.125
+                                - ( ( bottomleft(d_it) + topright(d_it) )
+                                    * 0.03125 );
+                            transform(vertex, amount, amount);
+                        }
+                    }
+                } else {
+                    // {this, right} is the pair with the angle
+                    // closest to 180 degrees
+                    vertex.smooth = true;
+                }
+            } else {
+                // there might be 2-color, then vertex.smooth = true
+
+                // or it might be 1-color and doesn't matter,
+                // because the current node will disappear
+                vertex.smooth
+                    = !( bottom(a_it) ^ bottom(b_it) );
+
+                if ( vertex.smooth ) {
+                    vertex.smooth
+                        = same_color(a_it->rgba, b_it->rgba)
+                        + same_color(a_it->rgba, c_it->rgba)
+                        + same_color(d_it->rgba, b_it->rgba)
+                        + same_color(d_it->rgba, c_it->rgba) == 2;
+                }
+            }
+        } else if ( bottom(a_it) ) {
+            // this and bottom are connected
+
+            if ( !bottom(b_it) && !( right(a_it) && right(c_it) ) ) {
+                // right and bottom-right are disconnected
+
+                bool foreign_is_contour = contour_edge(b_it->rgba, d_it->rgba);
+                bool twin_is_contour = contour_edge(c_it->rgba, d_it->rgba);
+                bool another_is_contour = contour_edge(a_it->rgba, b_it->rgba);
+
+                if ( another_is_contour + twin_is_contour
+                     + foreign_is_contour == 2 ) {
+                    vertex.smooth = !foreign_is_contour;
+
+                    if ( !vertex.smooth ) {
+                        if ( another_is_contour ) {
+                            cells_it->vertices.push_back(vertex);
+                            {
+                                Point<T> another = vertex;
+                                T amount = 0.1875 * topleft(b_it);
+                                transform(another, - amount,
+                                          - ( 0.75 - amount ));
+                                cells_it->vertices.push_back(another);
+                            }
+                            {
+                                Point<T> another = vertex;
+                                T amount = 0.0625 * topleft(b_it);
+                                transform(another, - amount,
+                                          - ( 0.25 - amount ));
+                                another.smooth = true;
+                                cells_it->vertices.push_back(another);
+                            }
+                            {
+                                Point<T> another = vertex;
+                                T amount = 0.0625 * bottomright(b_it);
+                                transform(another, 0.25 - amount, amount);
+                                cells_it->vertices.push_back(another);
+                            }
+                            {
+                                T amount = 0.125
+                                    - (bottomright(b_it) + topleft(b_it))
+                                    * 0.03125;
+                                transform(vertex, amount, - amount);
+                            }
+                        } else if ( twin_is_contour ) {
+                            T amount = 0.125
+                                - ( ( topright(d_it) + bottomleft(d_it) )
+                                    * 0.03125 );
+                            transform(vertex, amount, amount);
+                        }
+                    }
+                } else {
+                    // {this, bottom} is the pair with the angle
+                    // closest to 180 degrees
+                    vertex.smooth = true;
+                }
+            } else {
+                // there might be 2-color, then vertex.smooth = true
+
+                // or it might be 1-color and doesn't matter,
+                // because the current node will disappear
+                vertex.smooth = !( right(a_it) ^ right(c_it) );
+
+                if ( vertex.smooth ) {
+                    vertex.smooth
+                        = same_color(a_it->rgba, c_it->rgba)
+                        + same_color(a_it->rgba, b_it->rgba)
+                        + same_color(d_it->rgba, b_it->rgba)
+                        + same_color(d_it->rgba, c_it->rgba) == 2;
+                }
+            }
+        } else if ( bottom(b_it) ) {
+            // right and bottom-right are connected
+
+            bool special = false;
+
+            bool foreign_is_contour = contour_edge(c_it->rgba, d_it->rgba);
+
+            // the neighbor similar in 90° feature
+            bool similar_neighbor_is_contour
+                = contour_edge(a_it->rgba, c_it->rgba);
+
+            if ( contour_edge(a_it->rgba, b_it->rgba)
+                 + similar_neighbor_is_contour
+                 + foreign_is_contour == 2 ) {
+                vertex.smooth = !foreign_is_contour;
+
+                if ( !vertex.smooth ) {
+                    if ( similar_neighbor_is_contour ) {
+                        {
+                            Point<T> another = vertex;
+                            T amount = 0.125
+                                - ( topleft(c_it) + bottomright(c_it) )
+                                * 0.03125;
+                            transform(another, - amount, amount);
+                            cells_it->vertices.push_back(another);
+                        }
+                        {
+                            Point<T> another = vertex;
+                            T amount = 0.0625 * bottomright(c_it);
+                            transform(another, amount, 0.25 - amount);
+                            cells_it->vertices.push_back(another);
+                        }
+                        {
+                            Point<T> another = vertex;
+                            T amount = 0.0625 * topleft(c_it);
+                            transform(another, - ( 0.25 - amount ), - amount);
+                            another.smooth = true;
+                            cells_it->vertices.push_back(another);
+                        }
+                        {
+                            Point<T> another = vertex;
+                            T amount = 0.1875 * topleft(c_it);
+                            transform(another, - ( 0.75 - amount ), - amount);
+                            cells_it->vertices.push_back(another);
+                        }
+                    } else {
+                        special = true;
+                    }
+                }
+            } else {
+                // {right, bottom-right} is the pair with the
+                // angle closest to 180 degrees
+                vertex.smooth = false;
+
+                special = true;
+            }
+
+            if ( special ) {
+                cells_it->vertices.push_back(vertex);
+                {
+                    Point<T> another = vertex;
+                    T amount = 0.1875;
+                    transform(another,
+                              - ( topleft(b_it) - topright(a_it) ) * amount,
+                              // y
+                              - ( 0.75
+                                  - ( topleft(b_it) + topright(a_it) )
+                                  * amount ));
+                    cells_it->vertices.push_back(another);
+                }
+                {
+                    Point<T> another = vertex;
+                    T amount = 0.0625;
+                    transform(another,
+                              - ( topleft(b_it) - topright(a_it) ) * amount,
+                              // y
+                              - ( 0.25
+                                  - ( topleft(b_it) + topright(a_it) )
+                                  * amount ));
+                    another.smooth = true;
+                    cells_it->vertices.push_back(another);
+                }
+                {
+                    Point<T> another = vertex;
+                    T amount = 0.0625;
+                    transform(another, - amount
+                              * ( bottomleft(d_it) - bottomright(c_it) ),
+                              // y
+                              0.25 - amount
+                              * ( bottomleft(d_it) + bottomright(c_it) ));
+                    cells_it->vertices.push_back(another);
+                }
+                {
+                    transform(vertex,
+                              - ( topleft(b_it) + bottomleft(d_it)
+                                  - topright(a_it) - bottomright(c_it) )
+                              * 0.03125,
+                              // y
+                              ( topleft(b_it) - bottomleft(d_it)
+                                + topright(a_it) - bottomright(c_it) )
+                              * 0.03125);
+                }
+            }
+        } else if ( right(c_it) ) {
+            // bottom and bottom-right are connected
+
+            bool special = false;
+
+            bool foreign_is_contour = contour_edge(b_it->rgba, d_it->rgba);
+
+            // the neighbor similar in 90° feature
+            bool similar_neighbor_is_contour
+                = contour_edge(a_it->rgba, b_it->rgba);
+
+            if ( contour_edge(a_it->rgba, c_it->rgba)
+                 + similar_neighbor_is_contour
+                 + foreign_is_contour == 2 ) {
+                vertex.smooth = !foreign_is_contour;
+
+                if ( !vertex.smooth ) {
+                    if ( similar_neighbor_is_contour ) {
+                        cells_it->vertices.push_back(vertex);
+                        {
+                            Point<T> another = vertex;
+                            T amount = 0.1875 * topleft(b_it);
+                            transform(another, - amount, - ( 0.75 - amount ));
+                            cells_it->vertices.push_back(another);
+                        }
+                        {
+                            Point<T> another = vertex;
+                            T amount = 0.0625 * topleft(b_it);
+                            transform(another, - amount, - ( 0.25 - amount ));
+                            another.smooth = true;
+                            cells_it->vertices.push_back(another);
+                        }
+                        {
+                            Point<T> another = vertex;
+                            T amount = 0.0625 * bottomright(b_it);
+                            transform(another, 0.25 - amount, amount);
+                            cells_it->vertices.push_back(another);
+                        }
+                        {
+                            T amount = 0.125
+                                - 0.03125 * (topleft(b_it) + bottomright(b_it));
+                            transform(vertex, amount, - amount);
+                        }
+                    } else {
+                        special = true;
+                    }
+                }
+            } else {
+                // {bottom, bottom-right} is the pair with the
+                // angle closest to 180 degrees
+                vertex.smooth = false;
+
+                special = true;
+            }
+
+            if ( special ) {
+                {
+                    Point<T> another = vertex;
+                    T amount = 0.03125;
+                    transform(another,
+                              amount
+                              * ( topleft(c_it) - topright(d_it)
+                                  + bottomleft(a_it) - bottomright(b_it) ),
+                              // y
+                              - amount
+                              * ( topleft(c_it) + topright(d_it)
+                                  - bottomleft(a_it) - bottomright(b_it) ));
+                    cells_it->vertices.push_back(another);
+                }
+                {
+                    Point<T> another = vertex;
+                    T amount = 0.0625;
+                    transform(another,
+                              0.25 - amount
+                              * ( topright(d_it) + bottomright(b_it) ),
+                              // y
+                              - amount
+                              * ( topright(d_it) - bottomright(b_it) ));
+                    cells_it->vertices.push_back(another);
+                }
+                {
+                    Point<T> another = vertex;
+                    T amount = 0.0625;
+                    transform(another,
+                              - ( 0.25 - amount
+                                  * ( topleft(c_it) + bottomleft(a_it) ) ),
+                              // y
+                              - amount
+                              * ( topleft(c_it) - bottomleft(a_it) ));
+                    another.smooth = true;
+                    cells_it->vertices.push_back(another);
+                }
+                {
+                    Point<T> another = vertex;
+                    T amount = 0.1875;
+                    transform(another,
+                              - ( 0.75 - amount
+                                  * ( topleft(c_it) + bottomleft(a_it) ) ),
+                              // y
+                              -  amount
+                              * ( topleft(c_it) - bottomleft(a_it) ));
+                    cells_it->vertices.push_back(another);
+                }
+            }
+        } else {
+            // there is a 4-color pattern, where the current node
+            // won't be smooth
+            vertex.smooth = false;
+        }
+
+        cells_it->vertices.push_back(vertex);
+    }
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_SIMPLIFIEDVORONOI_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/libdepixelize/priv/splines.h b/src/libdepixelize/priv/splines.h
new file mode 100644
index 000000000..c7ef2b492
--- /dev/null
+++ b/src/libdepixelize/priv/splines.h
@@ -0,0 +1,155 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_SPLINES_PRIV_H
+#define LIBDEPIXELIZE_TRACER_SPLINES_PRIV_H
+
+#include "../splines.h"
+#include "homogeneoussplines.h"
+
+namespace Tracer {
+
+template<class T>
+Geom::Point to_geom_point(Point<T> p)
+{
+    return Geom::Point(p.x, p.y);
+}
+
+template<class T>
+Geom::Path worker_helper(const std::vector< Point<T> > &source, bool optimize)
+{
+    typedef Geom::LineSegment Line;
+    typedef Geom::QuadraticBezier Quad;
+    typedef typename std::vector< Point<T> >::const_iterator iterator;
+
+    iterator it = source.begin();
+    Geom::Path ret(to_geom_point((source.back() + *it) / 2));
+
+    for ( iterator end = --source.end() ; it != end ; ++it ) {
+        Point<T> next = *(it + 1);
+        Point<T> middle = (*it + next) / 2;
+
+        if ( !it->smooth ) {
+            // TODO: remove redundant colinear points
+            ret.appendNew<Line>(Geom::Point(it->x, it->y));
+            ret.appendNew<Line>(Geom::Point(middle.x, middle.y));
+        } else {
+            ret.appendNew<Quad>(Geom::Point(it->x, it->y),
+                                Geom::Point(middle.x, middle.y));
+        }
+    }
+
+    {
+        Point<T> next = source.front();
+        Point<T> middle = (*it + next) / 2;
+
+        if ( !it->smooth ) {
+            ret.appendNew<Line>(Geom::Point(it->x, it->y));
+            ret.appendNew<Line>(Geom::Point(middle.x, middle.y));
+        } else {
+            ret.appendNew<Quad>(Geom::Point(it->x, it->y),
+                                Geom::Point(middle.x, middle.y));
+        }
+    }
+
+    return ret;
+}
+
+/**
+ * It should be used by worker threads. Convert only one object.
+ */
+template<class T>
+void worker(const typename HomogeneousSplines<T>::Polygon &source,
+            Splines::Path &dest, bool optimize)
+{
+    dest.pathVector.reserve(source.holes.size() + 1);
+
+    for ( int i = 0 ; i != 4 ; ++i )
+        dest.rgba[i] = source.rgba[i];
+
+    dest.pathVector.push_back(worker_helper(source.vertices, optimize));
+
+    for ( typename std::vector< std::vector< Point<T> > >::const_iterator
+              it = source.holes.begin(), end = source.holes.end()
+              ; it != end ; ++it ) {
+        dest.pathVector.push_back(worker_helper(*it, optimize));
+    }
+}
+
+template<typename T>
+Splines::Splines(const SimplifiedVoronoi<T> &diagram)
+{
+    _paths.reserve(diagram.size());
+
+    for ( typename SimplifiedVoronoi<T>::const_iterator it = diagram.begin()
+              , end = diagram.end() ; it != end ; ++it ) {
+        Path path;
+
+        path.pathVector
+            .push_back(Geom::Path(to_geom_point(it->vertices.front())));
+
+        for ( typename std::vector< Point<T> >::const_iterator
+                  it2 = it->vertices.begin(), end2 = it->vertices.end()
+                  ; it2 != end2 ; ++it2 ) {
+            path.pathVector.back()
+                .appendNew<Geom::LineSegment>(Geom::Point(it2->x, it2->y));
+        }
+
+        for ( int i = 0 ; i != 4 ; ++i )
+            path.rgba[i] = it->rgba[i];
+
+        _paths.push_back(path);
+    }
+}
+
+template<class T>
+Splines::Splines(const HomogeneousSplines<T> &homogeneousSplines,
+                 bool optimize, int nthreads) :
+    _paths(homogeneousSplines.size()),
+    _width(homogeneousSplines.width()),
+    _height(homogeneousSplines.height())
+{
+    // TODO: It should be threaded
+    iterator paths_it = begin();
+    for ( typename HomogeneousSplines<T>::const_iterator
+              it = homogeneousSplines.begin(), end = homogeneousSplines.end()
+              ; it != end ; ++it, ++paths_it ) {
+        worker<T>(*it, *paths_it, optimize);
+    }
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_SPLINES_PRIV_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/libdepixelize/splines.h b/src/libdepixelize/splines.h
new file mode 100644
index 000000000..c4b455aae
--- /dev/null
+++ b/src/libdepixelize/splines.h
@@ -0,0 +1,120 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_SPLINES_H
+#define LIBDEPIXELIZE_TRACER_SPLINES_H
+
+#include <2geom/pathvector.h>
+#include <glib.h>
+
+namespace Tracer {
+
+template<typename T>
+class SimplifiedVoronoi;
+
+template<typename T>
+class HomogeneousSplines;
+
+class Splines
+{
+public:
+    struct Path
+    {
+        /**
+         * It may be benefited from C++11 move references.
+         */
+        Geom::PathVector pathVector;
+
+        guint8 rgba[4];
+    };
+
+    typedef std::vector<Path>::iterator iterator;
+    typedef std::vector<Path>::const_iterator const_iterator;
+
+    Splines() /* = default */ {}
+
+    template<typename T>
+    Splines(const SimplifiedVoronoi<T> &simplifiedVoronoi);
+
+    /**
+     * There are two levels of optimization. The first level only removes
+     * redundant points of colinear points. The second level uses the
+     * Kopf-Lischinski optimization. The first level is always enabled.
+     * The second level is enabled using \p optimize.
+     */
+    template<typename T>
+    Splines(const HomogeneousSplines<T> &homogeneousSplines, bool optimize,
+            int nthreads);
+
+    // Iterators
+    iterator begin()
+    {
+        return _paths.begin();
+    }
+
+    const_iterator begin() const
+    {
+        return _paths.begin();
+    }
+
+    iterator end()
+    {
+        return _paths.end();
+    }
+
+    const_iterator end() const
+    {
+        return _paths.end();
+    }
+
+    int width() const
+    {
+        return _width;
+    }
+
+    int height() const
+    {
+        return _height;
+    }
+
+private:
+    std::vector<Path> _paths;
+    int _width;
+    int _height;
+};
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_SPLINES_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/menus-skeleton.h b/src/menus-skeleton.h
index 5b141902b..2334a08c1 100644
--- a/src/menus-skeleton.h
+++ b/src/menus-skeleton.h
@@ -222,6 +222,7 @@ static char const menus_skeleton[] =
 "       <verb verb-id=\"ObjectToPath\" />\n"
 "       <verb verb-id=\"StrokeToPath\" />\n"
 "       <verb verb-id=\"SelectionTrace\" />\n"
+"       <verb verb-id=\"SelectionPixelArt\" />\n"
 "       <separator/>\n"
 "       <verb verb-id=\"SelectionUnion\" />\n"
 "       <verb verb-id=\"SelectionDiff\" />\n"
diff --git a/src/sp-image.h b/src/sp-image.h
index 055b3f13b..bfc10e7f2 100644
--- a/src/sp-image.h
+++ b/src/sp-image.h
@@ -17,7 +17,7 @@
 #include <gdk-pixbuf/gdk-pixbuf.h>
 #include <glibmm/ustring.h>
 #include "svg/svg-length.h"
-#include "sp-item.h"
+#include "sp-shape.h"
 
 #define SP_IMAGE(obj) (dynamic_cast<SPImage*>((SPObject*)obj))
 #define SP_IS_IMAGE(obj) (dynamic_cast<const SPImage*>((SPObject*)obj) != NULL)
diff --git a/src/ui/CMakeLists.txt b/src/ui/CMakeLists.txt
index c95dd35cc..233e01862 100644
--- a/src/ui/CMakeLists.txt
+++ b/src/ui/CMakeLists.txt
@@ -71,6 +71,7 @@ set(ui_SRC
 	dialog/text-edit.cpp
 	dialog/tile.cpp
 	dialog/tracedialog.cpp
+	dialog/pixelartdialog.cpp
 	dialog/transformation.cpp
 	dialog/undo-history.cpp
 	# dialog/whiteboard-connect.cpp
diff --git a/src/ui/dialog/Makefile_insert b/src/ui/dialog/Makefile_insert
index 09a7ef573..c37767a08 100644
--- a/src/ui/dialog/Makefile_insert
+++ b/src/ui/dialog/Makefile_insert
@@ -101,6 +101,8 @@ ink_common_sources +=		\
 	ui/dialog/tile.h			\
 	ui/dialog/tracedialog.cpp		\
 	ui/dialog/tracedialog.h			\
+	ui/dialog/pixelartdialog.cpp		\
+	ui/dialog/pixelartdialog.h		\
 	ui/dialog/transformation.cpp		\
 	ui/dialog/transformation.h		\
 	ui/dialog/undo-history.cpp		\
diff --git a/src/ui/dialog/dialog-manager.cpp b/src/ui/dialog/dialog-manager.cpp
index 0ce74f54e..17f6ae74d 100644
--- a/src/ui/dialog/dialog-manager.cpp
+++ b/src/ui/dialog/dialog-manager.cpp
@@ -35,6 +35,7 @@
 #include "ui/dialog/symbols.h"
 #include "ui/dialog/tile.h"
 #include "ui/dialog/tracedialog.h"
+#include "ui/dialog/pixelartdialog.h"
 #include "ui/dialog/transformation.h"
 #include "ui/dialog/undo-history.h"
 #include "ui/dialog/panel-dialog.h"
@@ -118,6 +119,7 @@ DialogManager::DialogManager() {
         registerFactory("Symbols",             &create<SymbolsDialog,        FloatingBehavior>);
         registerFactory("TileDialog",          &create<TileDialog,           FloatingBehavior>);
         registerFactory("Trace",               &create<TraceDialog,          FloatingBehavior>);
+        registerFactory("PixelArt",            &create<PixelArtDialog,       FloatingBehavior>);
         registerFactory("Transformation",      &create<Transformation,       FloatingBehavior>);
         registerFactory("UndoHistory",         &create<UndoHistory,          FloatingBehavior>);
         registerFactory("InputDevices",        &create<InputDialog,          FloatingBehavior>);
@@ -151,6 +153,7 @@ DialogManager::DialogManager() {
         registerFactory("Symbols",             &create<SymbolsDialog,        DockBehavior>);
         registerFactory("TileDialog",          &create<TileDialog,           DockBehavior>);
         registerFactory("Trace",               &create<TraceDialog,          DockBehavior>);
+        registerFactory("PixelArt",            &create<PixelArtDialog,       DockBehavior>);
         registerFactory("Transformation",      &create<Transformation,       DockBehavior>);
         registerFactory("UndoHistory",         &create<UndoHistory,          DockBehavior>);
         registerFactory("InputDevices",        &create<InputDialog,          DockBehavior>);
diff --git a/src/ui/dialog/pixelartdialog.cpp b/src/ui/dialog/pixelartdialog.cpp
new file mode 100644
index 000000000..6f0845ada
--- /dev/null
+++ b/src/ui/dialog/pixelartdialog.cpp
@@ -0,0 +1,490 @@
+/**
+ * @file
+ * Pixel art tracing settings dialog - implementation.
+ */
+/* Authors:
+ *   Bob Jamison <rjamison@titan.com>
+ *   Stéphane Gimenez <dev@gim.name>
+ *   Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+ *   Other dudes from The Inkscape Organization
+ *
+ * Copyright (C) 2004-2013 Authors
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include "pixelartdialog.h"
+#include <gtkmm/radiobutton.h>
+#include <gtkmm/stock.h>
+
+#include <gtk/gtk.h> //for GTK_RESPONSE* types
+#include <glibmm/i18n.h>
+
+#include "ui/widget/spinbutton.h"
+#include "ui/widget/frame.h"
+
+#include "desktop.h"
+#include "desktop-tracker.h"
+#include "message-stack.h"
+#include "selection.h"
+#include "preferences.h"
+
+#include "sp-image.h"
+#include "libdepixelize/kopftracer2011.h"
+#include <algorithm>
+#include "document.h"
+#include "xml/repr.h"
+#include "xml/document.h"
+#include "svg/svg.h"
+#include "svg/svg-color.h"
+#include "color.h"
+#include "svg/css-ostringstream.h"
+#include "document-undo.h"
+
+#ifdef HAVE_OPENMP
+#include <omp.h>
+#endif // HAVE_OPENMP
+
+namespace Inkscape {
+namespace UI {
+namespace Dialog {
+
+template<class T>
+T move(T &obj)
+{
+#ifdef LIBDEPIXELIZE_ENABLE_CPP11
+    return std::move(obj);
+#else
+    T ret;
+    std::swap(obj, ret);
+    return ret;
+#endif // LIBDEPIXELIZE_ENABLE_CPP11
+}
+
+/**
+ * A dialog for adjusting pixel art -> vector tracing parameters
+ */
+class PixelArtDialogImpl : public PixelArtDialog
+{
+public:
+    PixelArtDialogImpl();
+
+    ~PixelArtDialogImpl();
+
+private:
+    void setDesktop(SPDesktop *desktop);
+    void setTargetDesktop(SPDesktop *desktop);
+
+    //############ Events
+
+    void responseCallback(int response_id);
+
+    //############ UI Logic
+
+    Tracer::Kopf2011::Options options();
+
+    void vectorize();
+    void processLibdepixelize(SPImage *img);
+    void setDefaults();
+    void updatePreview();
+
+    bool ignorePreview;
+    bool pendingPreview;
+
+    //############ UI
+
+    Gtk::HBox             buttonsHBox;
+
+    Gtk::Button           *mainOkButton;
+    Gtk::Button           *mainCancelButton;
+    Gtk::Button           *mainResetButton;
+
+    Gtk::VBox         heuristicsVBox;
+    UI::Widget::Frame heuristicsFrame;
+
+    Gtk::HBox                        curvesMultiplierHBox;
+    Gtk::Label                       curvesMultiplierLabel;
+    Inkscape::UI::Widget::SpinButton curvesMultiplierSpinner;
+
+    Gtk::HBox                        islandsWeightHBox;
+    Gtk::Label                       islandsWeightLabel;
+    Inkscape::UI::Widget::SpinButton islandsWeightSpinner;
+
+    Gtk::HBox                        sparsePixelsMultiplierHBox;
+    Gtk::Label                       sparsePixelsMultiplierLabel;
+    Inkscape::UI::Widget::SpinButton sparsePixelsMultiplierSpinner;
+
+    Gtk::HBox                        sparsePixelsRadiusHBox;
+    Gtk::Label                       sparsePixelsRadiusLabel;
+    Inkscape::UI::Widget::SpinButton sparsePixelsRadiusSpinner;
+
+    Gtk::VBox             outputVBox;
+    UI::Widget::Frame     outputFrame;
+    Gtk::RadioButtonGroup outputGroup;
+
+    Gtk::RadioButton voronoiRadioButton;
+    Gtk::RadioButton noOptimizeRadioButton;
+    Gtk::RadioButton optimizeRadioButton;
+
+    SPDesktop *desktop;
+    DesktopTracker deskTrack;
+    sigc::connection desktopChangeConn;
+};
+
+void PixelArtDialogImpl::setDesktop(SPDesktop *desktop)
+{
+    Panel::setDesktop(desktop);
+    deskTrack.setBase(desktop);
+}
+
+void PixelArtDialogImpl::setTargetDesktop(SPDesktop *desktop)
+{
+    this->desktop = desktop;
+}
+
+PixelArtDialogImpl::PixelArtDialogImpl() :
+    PixelArtDialog(),
+    ignorePreview(false),
+    pendingPreview(false)
+{
+
+    Gtk::Box *contents = _getContents();
+
+    // Heuristics
+    {
+        curvesMultiplierLabel.set_label(_("_Curves (multiplier)"));
+        curvesMultiplierLabel.set_use_underline(true);
+        curvesMultiplierLabel.set_mnemonic_widget(curvesMultiplierSpinner);
+        curvesMultiplierLabel.set_tooltip_text(_("Favors connections that are part of a long curve"));
+        curvesMultiplierSpinner.set_increments(0.125, 0);
+        curvesMultiplierSpinner.set_digits(3);
+        curvesMultiplierSpinner.set_range(-10, 10);
+        curvesMultiplierSpinner.get_adjustment()->signal_value_changed()
+            .connect(sigc::mem_fun(*this, &PixelArtDialogImpl::updatePreview));
+
+        curvesMultiplierHBox.pack_start(curvesMultiplierLabel, false, false);
+        curvesMultiplierHBox.pack_end(curvesMultiplierSpinner, false, false);
+        heuristicsVBox.pack_start(curvesMultiplierHBox, false, false);
+
+        islandsWeightLabel.set_label(_("_Islands (weight)"));
+        islandsWeightLabel.set_use_underline(true);
+        islandsWeightLabel.set_mnemonic_widget(islandsWeightSpinner);
+        islandsWeightLabel.set_tooltip_text(_("Avoid single disconnected pixels"));
+
+        islandsWeightSpinner.set_tooltip_text(_("A constant vote value"));
+        islandsWeightSpinner.set_increments(1, 0);
+        islandsWeightSpinner.set_range(-20, 20);
+        islandsWeightSpinner.get_adjustment()->signal_value_changed()
+            .connect(sigc::mem_fun(*this, &PixelArtDialogImpl::updatePreview));
+
+        islandsWeightHBox.pack_start(islandsWeightLabel, false, false);
+        islandsWeightHBox.pack_end(islandsWeightSpinner, false, false);
+        heuristicsVBox.pack_start(islandsWeightHBox, false, false);
+
+        sparsePixelsRadiusLabel.set_label(_("Sparse pixels (window _radius)"));
+        sparsePixelsRadiusLabel.set_use_underline(true);
+        sparsePixelsRadiusLabel.set_mnemonic_widget(sparsePixelsRadiusSpinner);
+
+        sparsePixelsRadiusSpinner.set_increments(1, 0);
+        sparsePixelsRadiusSpinner.set_range(2, 8);
+        sparsePixelsRadiusSpinner.get_adjustment()->signal_value_changed()
+            .connect(sigc::mem_fun(*this, &PixelArtDialogImpl::updatePreview));
+
+        sparsePixelsRadiusSpinner.set_tooltip_text(_("The radius of the window analyzed"));
+        sparsePixelsMultiplierLabel.set_label(_("Sparse pixels (_multiplier)"));
+        sparsePixelsMultiplierLabel.set_use_underline(true);
+        sparsePixelsMultiplierLabel.set_mnemonic_widget(sparsePixelsMultiplierSpinner);
+
+        sparsePixelsMultiplierSpinner.set_increments(0.125, 0);
+        sparsePixelsMultiplierSpinner.set_digits(3);
+        sparsePixelsMultiplierSpinner.set_range(-10, 10);
+        sparsePixelsMultiplierSpinner.get_adjustment()->signal_value_changed()
+            .connect(sigc::mem_fun(*this, &PixelArtDialogImpl::updatePreview));
+
+        {
+            char const *str = _("Favors connections that are part of foreground color");
+            sparsePixelsRadiusLabel.set_tooltip_text(str);
+            sparsePixelsMultiplierLabel.set_tooltip_text(str);
+        }
+
+        {
+            char const *str = _("The heuristic computed vote will be multiplied by this value");
+            curvesMultiplierSpinner.set_tooltip_text(str);
+            sparsePixelsMultiplierSpinner.set_tooltip_text(str);
+        }
+
+        sparsePixelsRadiusHBox.pack_start(sparsePixelsRadiusLabel, false, false);
+        sparsePixelsRadiusHBox.pack_end(sparsePixelsRadiusSpinner, false, false);
+        heuristicsVBox.pack_start(sparsePixelsRadiusHBox, false, false);
+
+        sparsePixelsMultiplierHBox.pack_start(sparsePixelsMultiplierLabel, false, false);
+        sparsePixelsMultiplierHBox.pack_end(sparsePixelsMultiplierSpinner, false, false);
+        heuristicsVBox.pack_start(sparsePixelsMultiplierHBox, false, false);
+
+        heuristicsFrame.set_label(_("Heuristics"));
+        heuristicsFrame.add(heuristicsVBox);
+        contents->pack_start(heuristicsFrame, false, false);
+    }
+
+    // Output
+    {
+        voronoiRadioButton.set_label(_("_Voronoi diagram"));
+        voronoiRadioButton.set_tooltip_text(_("Output composed of straight lines"));
+        voronoiRadioButton.set_use_underline(true);
+        outputGroup = voronoiRadioButton.get_group();
+
+        outputVBox.pack_start(voronoiRadioButton, false, false);
+
+        noOptimizeRadioButton.set_label(_("Convert to _B-spline curves"));
+        noOptimizeRadioButton.set_tooltip_text(_("Preserve staircasing artifacts"));
+        noOptimizeRadioButton.set_use_underline(true);
+        noOptimizeRadioButton.set_group(outputGroup);
+
+        outputVBox.pack_start(noOptimizeRadioButton, false, false);
+
+        optimizeRadioButton.set_label(_("_Smooth curves"));
+        optimizeRadioButton.set_tooltip_text(_("The Kopf-Lischinski algorithm"));
+        optimizeRadioButton.set_use_underline(true);
+        optimizeRadioButton.set_group(outputGroup);
+
+        outputVBox.pack_start(optimizeRadioButton, false, false);
+
+        outputFrame.set_label(_("Output"));
+        outputFrame.add(outputVBox);
+        contents->pack_start(outputFrame, true, false);
+    }
+
+    // Buttons
+    {
+        mainResetButton = addResponseButton(_("Reset"), GTK_RESPONSE_HELP, true);
+        mainResetButton ->set_tooltip_text(_("Reset all settings to defaults"));
+
+        //## The OK button
+        mainCancelButton = addResponseButton(Gtk::Stock::STOP, GTK_RESPONSE_CANCEL);
+        if (mainCancelButton) {
+            mainCancelButton->set_tooltip_text(_("Abort a trace in progress"));
+            mainCancelButton->set_sensitive(false);
+        }
+        mainOkButton = addResponseButton(Gtk::Stock::OK, GTK_RESPONSE_OK);
+        mainOkButton->set_tooltip_text(_("Execute the trace"));
+
+        contents->pack_start(buttonsHBox);
+    }
+
+    setDefaults();
+
+    show_all_children();
+
+    desktopChangeConn = deskTrack.connectDesktopChanged( sigc::mem_fun(*this, &PixelArtDialogImpl::setTargetDesktop) );
+    deskTrack.connect(GTK_WIDGET(gobj()));
+
+    signalResponse().connect(sigc::mem_fun(*this, &PixelArtDialogImpl::responseCallback));
+}
+
+void PixelArtDialogImpl::responseCallback(int response_id)
+{
+    if (response_id == GTK_RESPONSE_OK) {
+        vectorize();
+    } else if (response_id == GTK_RESPONSE_CANCEL) {
+        // TODO
+    } else if (response_id == GTK_RESPONSE_HELP) {
+        setDefaults();
+    } else {
+        hide();
+        return;
+    }
+}
+
+Tracer::Kopf2011::Options PixelArtDialogImpl::options()
+{
+    Tracer::Kopf2011::Options options;
+
+    options.curvesMultiplier = curvesMultiplierSpinner.get_value();
+    options.islandsWeight = islandsWeightSpinner.get_value_as_int();
+    options.sparsePixelsMultiplier = sparsePixelsMultiplierSpinner.get_value();
+    options.sparsePixelsRadius = sparsePixelsRadiusSpinner.get_value_as_int();
+    options.optimize = optimizeRadioButton.get_active();
+
+    options.nthreads = Inkscape::Preferences::get()
+        ->getIntLimited("/options/threading/numthreads",
+#ifdef HAVE_OPENMP
+                        omp_get_num_procs(),
+#else
+                        1,
+#endif // HAVE_OPENMP
+                        1, 256);
+
+    return options;
+}
+
+void PixelArtDialogImpl::vectorize()
+{
+    Inkscape::MessageStack *msgStack = desktop->messageStack();
+
+    if ( !desktop->selection ) {
+        char *msg = _("Select an <b>image</b> to trace");
+        msgStack->flash(Inkscape::ERROR_MESSAGE, msg);
+        return;
+    }
+
+    bool found = false;
+
+    for ( GSList const *list = desktop->selection->itemList() ; list
+              ; list = list->next ) {
+        if ( !SP_IS_IMAGE(list->data) )
+            continue;
+
+        found = true;
+
+        processLibdepixelize(SP_IMAGE(list->data));
+    }
+
+    if ( !found ) {
+        char *msg = _("Select an <b>image</b> to trace");
+        msgStack->flash(Inkscape::ERROR_MESSAGE, msg);
+        return;
+    }
+
+    DocumentUndo::done(desktop->doc(), SP_VERB_SELECTION_PIXEL_ART,
+                       _("Trace pixel art"));
+
+    // Flush pending updates
+    desktop->doc()->ensureUpToDate();
+}
+
+void PixelArtDialogImpl::processLibdepixelize(SPImage *img)
+{
+    Tracer::Splines out;
+
+    if ( voronoiRadioButton.get_active() ) {
+        out = Tracer::Kopf2011::to_voronoi(Glib::wrap(img->pixbuf, true),
+                                           options());
+    } else {
+        out = Tracer::Kopf2011::to_splines(Glib::wrap(img->pixbuf, true),
+                                           options());
+    }
+
+    Inkscape::XML::Document *xml_doc = desktop->doc()->getReprDoc();
+    Inkscape::XML::Node *group = xml_doc->createElement("svg:g");
+
+    for ( Tracer::Splines::iterator it = out.begin(), end = out.end()
+              ; it != end ; ++it ) {
+        Inkscape::XML::Node *repr = xml_doc->createElement("svg:path");
+
+        {
+            SPCSSAttr *css = sp_repr_css_attr_new();
+
+            {
+                gchar b[64];
+                sp_svg_write_color(b, sizeof(b),
+                                   SP_RGBA32_U_COMPOSE(unsigned(it->rgba[2]),
+                                                       unsigned(it->rgba[1]),
+                                                       unsigned(it->rgba[0]),
+                                                       unsigned(it->rgba[3])));
+
+                sp_repr_css_set_property(css, "fill", b);
+            }
+
+            {
+                Inkscape::CSSOStringStream osalpha;
+                osalpha << float(it->rgba[3]) / 255.;
+                sp_repr_css_set_property(css, "fill-opacity",
+                                         osalpha.str().c_str());
+            }
+
+            sp_repr_css_set(repr, css, "style");
+            sp_repr_css_attr_unref(css);
+        }
+
+        gchar *str = sp_svg_write_path(move(it->pathVector));
+        repr->setAttribute("d", str);
+        g_free(str);
+
+        group->appendChild(repr);
+
+        Inkscape::GC::release(repr);
+    }
+
+    {
+        group->setAttribute("transform",
+                            (std::string("translate(")
+                             + sp_svg_length_write_with_units(img->x)
+                             + ' ' + sp_svg_length_write_with_units(img->y)
+                             + ')').c_str());
+    }
+
+    desktop->currentLayer()->appendChildRepr(group);
+
+    Inkscape::GC::release(group);
+}
+
+void PixelArtDialogImpl::setDefaults()
+{
+    ignorePreview = true;
+
+    curvesMultiplierSpinner.set_value(Tracer::Kopf2011::Options
+                                      ::CURVES_MULTIPLIER);
+
+    islandsWeightSpinner.set_value(Tracer::Kopf2011::Options::ISLANDS_WEIGHT);
+
+    sparsePixelsRadiusSpinner.set_value(Tracer::Kopf2011::Options
+                                        ::SPARSE_PIXELS_RADIUS);
+
+    sparsePixelsMultiplierSpinner.set_value(Tracer::Kopf2011::Options
+                                            ::SPARSE_PIXELS_MULTIPLIER);
+
+    optimizeRadioButton.set_active();
+
+    ignorePreview = false;
+
+    if ( pendingPreview )
+        updatePreview();
+}
+
+void PixelArtDialogImpl::updatePreview()
+{
+    if ( ignorePreview ) {
+        pendingPreview = true;
+        return;
+    }
+
+    // TODO: update preview
+    pendingPreview = false;
+}
+
+/**
+ * Factory method.  Use this to create a new PixelArtDialog
+ */
+PixelArtDialog &PixelArtDialog::getInstance()
+{
+    PixelArtDialog *dialog = new PixelArtDialogImpl();
+    return *dialog;
+}
+
+PixelArtDialogImpl::~PixelArtDialogImpl()
+{
+    desktopChangeConn.disconnect();
+}
+
+
+} //namespace Dialog
+} //namespace UI
+} //namespace Inkscape
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/ui/dialog/pixelartdialog.h b/src/ui/dialog/pixelartdialog.h
new file mode 100644
index 000000000..165cb8699
--- /dev/null
+++ b/src/ui/dialog/pixelartdialog.h
@@ -0,0 +1,58 @@
+/** @file
+ * @brief Bitmap tracing settings dialog
+ */
+/* Authors:
+ *   Bob Jamison
+ *   Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+ *   Other dudes from The Inkscape Organization
+ *
+ * Copyright (C) 2004, 2005 Authors
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef __PIXELARTDIALOG_H__
+#define __PIXELARTDIALOG_H__
+
+#include "ui/widget/panel.h"
+#include "verbs.h"
+
+namespace Inkscape {
+namespace UI {
+namespace Dialog {
+
+
+/**
+ * A dialog that displays log messages
+ */
+class PixelArtDialog : public UI::Widget::Panel
+{
+
+public:
+
+    PixelArtDialog() : 
+        UI::Widget::Panel("", "/dialogs/pixelart", SP_VERB_SELECTION_PIXEL_ART)
+    {}
+
+
+    static PixelArtDialog &getInstance();
+
+    virtual ~PixelArtDialog() {};
+};
+
+
+} //namespace Dialog
+} //namespace UI
+} //namespace Inkscape
+
+#endif /* __PIXELARTDIALOGDIALOG_H__ */
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/verbs.cpp b/src/verbs.cpp
index 737d9e150..23a560423 100644
--- a/src/verbs.cpp
+++ b/src/verbs.cpp
@@ -1173,6 +1173,10 @@ void SelectionVerb::perform(SPAction *action, void *data)
             inkscape_dialogs_unhide();
             dt->_dlg_mgr->showDialog("Trace");
             break;
+        case SP_VERB_SELECTION_PIXEL_ART:
+            inkscape_dialogs_unhide();
+            dt->_dlg_mgr->showDialog("PixelArt");
+            break;
         case SP_VERB_SELECTION_CREATE_BITMAP:
             sp_selection_create_bitmap_copy(dt);
             break;
@@ -2545,6 +2549,8 @@ Verb *Verb::_base_verbs[] = {
     // TRANSLATORS: "to trace" means "to convert a bitmap to vector graphics" (to vectorize)
     new SelectionVerb(SP_VERB_SELECTION_TRACE, "SelectionTrace", N_("_Trace Bitmap..."),
                       N_("Create one or more paths from a bitmap by tracing it"), INKSCAPE_ICON("bitmap-trace")),
+    new SelectionVerb(SP_VERB_SELECTION_PIXEL_ART, "SelectionPixelArt", N_("Trace Pixel Art..."),
+                      N_("Create paths using Kopf-Lischinski algorithm to vectorize pixel art"), INKSCAPE_ICON("pixelart-trace")),
     new SelectionVerb(SP_VERB_SELECTION_CREATE_BITMAP, "SelectionCreateBitmap", N_("Make a _Bitmap Copy"),
                       N_("Export selection to a bitmap and insert it into document"), INKSCAPE_ICON("selection-make-bitmap-copy") ),
     new SelectionVerb(SP_VERB_SELECTION_COMBINE, "SelectionCombine", N_("_Combine"),
diff --git a/src/verbs.h b/src/verbs.h
index c4b01dfbf..40292745a 100644
--- a/src/verbs.h
+++ b/src/verbs.h
@@ -134,6 +134,7 @@ enum {
     SP_VERB_SELECTION_SIMPLIFY,
     SP_VERB_SELECTION_REVERSE,
     SP_VERB_SELECTION_TRACE,
+    SP_VERB_SELECTION_PIXEL_ART,
     SP_VERB_SELECTION_CREATE_BITMAP,
     SP_VERB_SELECTION_COMBINE,
     SP_VERB_SELECTION_BREAK_APART,