Adding upstream version 1.3+ds.upstream/1.3+dsupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

24 files changed, 4538 insertions, 0 deletions

diff --git a/src/trace/CMakeLists.txt b/src/trace/CMakeLists.txt
new file mode 100644
index 0000000..bb98981
--- /dev/null
+++ b/src/trace/CMakeLists.txt
@@ -0,0 +1,33 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+set(trace_SRC
+	cielab.cpp
+	filterset.cpp
+	imagemap.cpp
+	imagemap-gdk.cpp
+	quantize.cpp
+	siox.cpp
+	trace.cpp
+
+	potrace/inkscape-potrace.cpp
+	autotrace/inkscape-autotrace.cpp
+	depixelize/inkscape-depixelize.cpp
+
+	# -------
+	# Headers
+	cielab.h
+	filterset.h
+	imagemap-gdk.h
+	imagemap.h
+	pool.h
+	quantize.h
+	siox.h
+	trace.h
+
+	potrace/bitmap.h
+	potrace/inkscape-potrace.h
+	autotrace/inkscape-autotrace.h
+	depixelize/inkscape-depixelize.h
+)
+
+add_inkscape_source("${trace_SRC}")
+
diff --git a/src/trace/README b/src/trace/README
new file mode 100644
index 0000000..f436aa0
--- /dev/null
+++ b/src/trace/README
@@ -0,0 +1,18 @@
+
+This directory contains code for converting bitmap images to vector images.
+The subdirectories contain code for the three tracers used in Inkscape: potrace
+(external dependency), autotrace, and libdepixelize (currently in src/3rdparty).
+
+
+To do:
+
+* Think about conceptually changing how the tracing works: Ideally, it should
+  be three steps clearly separated:
+  1/ Preprocessing (color reduction, blurring, background removing, image
+    inversion...)
+  2/ Tracing the preprocessed image, using some tracing engine
+  3/ Post-processing (suppressing speckles, optimizing paths...)
+  
+  The main problem is that the tracing engine sometimes *also* does 1 and 3, so
+  there is some discussion to have whether this can be done.
+
diff --git a/src/trace/autotrace/inkscape-autotrace.cpp b/src/trace/autotrace/inkscape-autotrace.cpp
new file mode 100644
index 0000000..9a8f6eb
--- /dev/null
+++ b/src/trace/autotrace/inkscape-autotrace.cpp
@@ -0,0 +1,226 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * This is the C++ glue between Inkscape and Autotrace
+ *//*
+ *
+ * Authors:
+ *   Marc Jeanmougin
+ *
+ * Copyright (C) 2018 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ */
+#include <iomanip>
+#include <2geom/path-sink.h>
+#include <glibmm/i18n.h>
+
+#include "inkscape-autotrace.h"
+#include "async/progress.h"
+
+extern "C" {
+#include "3rdparty/autotrace/autotrace.h"
+#include "3rdparty/autotrace/output.h"
+#include "3rdparty/autotrace/spline.h"
+}
+
+namespace Inkscape {
+namespace Trace {
+namespace Autotrace {
+namespace {
+
+struct at_splines_deleter { void operator()(at_splines_type *p) { at_splines_free(p); }; };
+using at_splines_uniqptr = std::unique_ptr<at_splines_type, at_splines_deleter>;
+
+/**
+ * Eliminate the alpha channel by overlaying on top of white, and ensure the result is in packed RGB8 format.
+ * If nothing needs to be done, the original pixbuf is returned, otherwise a new pixbuf is returned.
+ */
+Glib::RefPtr<Gdk::Pixbuf> to_rgb8_packed(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf)
+{
+    int width     = pixbuf->get_width();
+    int height    = pixbuf->get_height();
+    int rowstride = pixbuf->get_rowstride();
+    int nchannels = pixbuf->get_n_channels();
+    auto data     = pixbuf->get_pixels();
+
+    if (nchannels == 3 && rowstride == width * 3) {
+        return pixbuf;
+    }
+
+    int imgsize = width * height;
+    auto out = new unsigned char[3 * imgsize];
+    auto q = out;
+
+    for (int y = 0; y < height; y++) {
+        auto p = data + rowstride * y;
+        for (int x = 0; x < width; x++) {
+            unsigned char alpha = nchannels == 3 ? 255 : p[3];
+            unsigned char white = 255 - alpha;
+            for (int c = 0; c < 3; c++) {
+                *(q++) = (int)p[c] * alpha / 256 + white;
+            }
+            p += nchannels;
+        }
+    }
+
+    return Gdk::Pixbuf::create_from_data(out, Gdk::COLORSPACE_RGB, false, 8, width, height, width * 3, [out] (auto) { delete [] out; });
+}
+
+} // namespace
+
+AutotraceTracingEngine::AutotraceTracingEngine()
+{
+    // Create options struct, automatically filled with defaults.
+    opts = at_fitting_opts_new();
+    opts->background_color = at_color_new(255, 255, 255);
+    autotrace_init();
+}
+
+AutotraceTracingEngine::~AutotraceTracingEngine()
+{
+    at_fitting_opts_free(opts);
+}
+
+Glib::RefPtr<Gdk::Pixbuf> AutotraceTracingEngine::preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf)
+{
+    // Todo: Actually generate a meaningful preview.
+    return to_rgb8_packed(pixbuf);
+}
+
+TraceResult AutotraceTracingEngine::trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+    auto pb = to_rgb8_packed(pixbuf);
+    
+    at_bitmap bitmap;
+    bitmap.height = pb->get_height();
+    bitmap.width  = pb->get_width();
+    bitmap.bitmap = pb->get_pixels();
+    bitmap.np     = 3;
+
+    auto throttled = Async::ProgressStepThrottler(progress, 0.02);
+    auto sub_trace = Async::SubProgress(throttled, 0.0, 0.8);
+    
+    auto splines = at_splines_uniqptr(at_splines_new_full(
+        &bitmap, opts,
+        nullptr, nullptr,
+        [] (gfloat frac, gpointer data) { reinterpret_cast<decltype(sub_trace)*>(data)->report(frac); }, &sub_trace,
+        [] (gpointer data) -> gboolean { return !reinterpret_cast<decltype(sub_trace)*>(data)->keepgoing(); }, &sub_trace
+    ));
+    // at_output_write_func wfunc = at_output_get_handler_by_suffix("svg");
+    // at_spline_writer *wfunc = at_output_get_handler_by_suffix("svg");
+    // at_splines_write(wfunc, stdout, "", NULL, splines, NULL, NULL);
+
+    sub_trace.report_or_throw(1.0);
+    auto sub_convert = Async::SubProgress(throttled, 0.8, 0.2);
+
+    int height = splines->height;
+    at_spline_list_type list;
+    at_color last_color = { 0, 0, 0 };
+
+    std::string style;
+    Geom::PathBuilder pathbuilder;
+    TraceResult res;
+
+    auto get_style = [&] {
+        char color[10];
+        std::sprintf(color, "#%02x%02x%02x;", list.color.r, list.color.g, list.color.b);
+
+        std::stringstream ss;
+        ss << (splines->centerline || list.open ? "stroke:" : "fill:") << color
+           << (splines->centerline || list.open ? "fill:" : "stroke:") << "none";
+
+        return ss.str();
+    };
+
+    auto to_geom = [=] (at_real_coord const &c) {
+        return Geom::Point(c.x, height - c.y);
+    };
+
+    int const num_splines = SPLINE_LIST_ARRAY_LENGTH(*splines);
+    for (int list_i = 0; list_i < num_splines; list_i++) {
+        sub_convert.report_or_throw((double)list_i / num_splines);
+
+        list = SPLINE_LIST_ARRAY_ELT(*splines, list_i);
+
+        if (list_i == 0 || !at_color_equal(&list.color, &last_color)) {
+            if (list_i > 0) {
+                if (!(splines->centerline || list.open)) {
+                    pathbuilder.closePath();
+                } else {
+                    pathbuilder.flush();
+                }
+                res.emplace_back(std::move(style), pathbuilder.peek());
+                pathbuilder.clear();
+            }
+
+            style = get_style();
+        }
+
+        auto const first = SPLINE_LIST_ELT(list, 0);
+        pathbuilder.moveTo(to_geom(START_POINT(first)));
+
+        for (int spline_i = 0; spline_i < SPLINE_LIST_LENGTH(list); spline_i++) {
+            auto const spline = SPLINE_LIST_ELT(list, spline_i);
+
+            if (SPLINE_DEGREE(spline) == AT_LINEARTYPE) {
+                pathbuilder.lineTo(to_geom(END_POINT(spline)));
+            } else {
+                pathbuilder.curveTo(to_geom(CONTROL1(spline)), to_geom(CONTROL2(spline)), to_geom(END_POINT(spline)));
+            }
+
+            last_color = list.color;
+        }
+    }
+
+    if (SPLINE_LIST_ARRAY_LENGTH(*splines) > 0) {
+        if (!(splines->centerline || list.open)) {
+            pathbuilder.closePath();
+        } else {
+            pathbuilder.flush();
+        }
+        res.emplace_back(std::move(style), pathbuilder.peek());
+    }
+
+    return res;
+}
+
+void AutotraceTracingEngine::setColorCount(unsigned color_count)
+{
+    opts->color_count = color_count;
+}
+
+void AutotraceTracingEngine::setCenterLine(bool centerline)
+{
+    opts->centerline = centerline;
+}
+
+void AutotraceTracingEngine::setPreserveWidth(bool preserve_width)
+{
+    opts->preserve_width = preserve_width;
+}
+
+void AutotraceTracingEngine::setFilterIterations(unsigned filter_iterations)
+{
+    opts->filter_iterations = filter_iterations;
+}
+
+void AutotraceTracingEngine::setErrorThreshold(float error_threshold)
+{
+    opts->error_threshold = error_threshold;
+}
+
+} // namespace Autotrace
+} // namespace Trace
+} // namespace Inkscape
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/autotrace/inkscape-autotrace.h b/src/trace/autotrace/inkscape-autotrace.h
new file mode 100644
index 0000000..a117592
--- /dev/null
+++ b/src/trace/autotrace/inkscape-autotrace.h
@@ -0,0 +1,61 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * This is the C++ glue between Inkscape and Autotrace
+ *//*
+ *
+ * Authors:
+ *   Marc Jeanmougin
+ *
+ * Copyright (C) 2018 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ * Autotrace is available at http://github.com/autotrace/autotrace.
+ *
+ */
+#ifndef INKSCAPE_TRACE_AUTOTRACE_H
+#define INKSCAPE_TRACE_AUTOTRACE_H
+
+#include "trace/trace.h"
+using at_fitting_opts_type = struct _at_fitting_opts_type;
+
+namespace Inkscape {
+namespace Trace {
+namespace Autotrace {
+
+class AutotraceTracingEngine final
+    : public TracingEngine
+{
+public:
+    AutotraceTracingEngine();
+    ~AutotraceTracingEngine() override;
+
+    TraceResult trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress) override;
+    Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) override;
+
+    void setColorCount(unsigned);
+    void setCenterLine(bool);
+    void setPreserveWidth(bool);
+    void setFilterIterations(unsigned);
+    void setErrorThreshold(float);
+
+private:
+    at_fitting_opts_type *opts;
+};
+
+} // namespace Autotrace
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_AUTOTRACE_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/cielab.cpp b/src/trace/cielab.cpp
new file mode 100644
index 0000000..222fb91
--- /dev/null
+++ b/src/trace/cielab.cpp
@@ -0,0 +1,216 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping
+ * Conversion to C++ for Inkscape by Bob Jamison
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <algorithm>
+#include <cmath>
+#include "cielab.h"
+
+namespace Inkscape {
+namespace Trace {
+
+namespace {
+
+/**
+ * Convert integer RGB values into a pixel value.
+ */
+uint32_t getRGB(int r, int g, int b)
+{
+    r = std::clamp(r, 0, 255);
+    g = std::clamp(g, 0, 255);
+    b = std::clamp(b, 0, 255);
+    return (r << 16) | (g << 8) | b;
+}
+
+/**
+ * Convert float RGB values (0.0-1.0) into a pixel value.
+ */
+uint32_t getRGB(float r, float g, float b)
+{
+    return getRGB((int)(r * 256.0f),
+                  (int)(g * 256.0f),
+                  (int)(b * 256.0f));
+}
+
+//#########################################
+//# Root approximations for large speedup.
+//# By njh!
+//#########################################
+
+class Tables
+{
+public:
+    static int constexpr SIZE = 16;
+    float cbrt[SIZE + 1];
+    float qn[SIZE + 1];
+
+    static auto &get()
+    {
+        static Tables const instance;
+        return instance;
+    }
+
+private:
+    Tables();
+};
+
+template <typename T>
+auto sq(T t)
+{
+    return t * t;
+}
+
+// Cube root.
+double cbrt(double x)
+{
+    auto polish = [x] (double y) {
+        return (2.0 * y + x / sq(y)) / 3.0;
+    };
+    double y = Tables::get().cbrt[(int)(x * Tables::SIZE)]; // assuming x \in [0, 1]
+    y = polish(y);
+    y = polish(y);
+    return y;
+}
+
+// Quintic root.
+double qnrt(double x)
+{
+    auto polish = [x] (double y) {
+        return (4.0 * y + x / sq(sq(y))) / 5.0;
+    };
+    double y = Tables::get().qn[(int)(x * Tables::SIZE)]; // assuming x \in [0, 1]
+    y = polish(y);
+    y = polish(y);
+    return y;
+}
+
+double pow24(double x)
+{
+    return sq(x * qnrt(x));
+}
+
+Tables::Tables()
+{
+    auto entry = [&] (int i, float x) {
+        cbrt[i] = std::pow(x / SIZE, 0.3333f);
+        qn[i]   = std::pow(x / SIZE, 0.2f);
+    };
+
+    entry(0, 0.5f);
+    for (int i = 1; i < SIZE + 1; i++) {
+        entry(i, i);
+    }
+}
+
+} // namespace
+
+CieLab::CieLab(uint32_t rgb)
+{
+    uint8_t ir  = (rgb >> 16) & 0xff;
+    uint8_t ig  = (rgb >>  8) & 0xff;
+    uint8_t ib  = (rgb      ) & 0xff;
+
+    float fr = ir / 255.0f;
+    float fg = ig / 255.0f;
+    float fb = ib / 255.0f;
+
+    // printf("fr:%f fg:%f fb:%f\n", fr, fg, fb);
+
+    auto to_linear = [] (float &x) {
+        if (x > 0.04045) {
+            x = pow24((x + 0.055) / 1.055);
+        } else {
+            x /= 12.92;
+        }
+    };
+
+    to_linear(fr);
+    to_linear(fg);
+    to_linear(fb);
+
+    // Use white = D65
+    float x = fr * 0.4124 + fg * 0.3576 + fb * 0.1805;
+    float y = fr * 0.2126 + fg * 0.7152 + fb * 0.0722;
+    float z = fr * 0.0193 + fg * 0.1192 + fb * 0.9505;
+
+    float vx = x / 0.95047;
+    float vy = y;
+    float vz = z / 1.08883;
+
+    // printf("vx:%f vy:%f vz:%f\n", vx, vy, vz);
+
+    auto f = [] (float &x) {
+        if (x > 0.008856) {
+            x = cbrt(x);
+        } else {
+            x = (7.787 * x) + (16.0 / 116.0);
+        }
+    };
+
+    f(vx);
+    f(vy);
+    f(vz);
+
+    C = 0;
+    L = 116.0 * vy - 16.0;
+    A = 500.0 * (vx - vy);
+    B = 200.0 * (vy - vz);
+}
+
+uint32_t CieLab::toRGB() const
+{
+    float vy = (L + 16.0) / 116.0;
+    float vx = A / 500.0 + vy;
+    float vz = vy - B / 200.0;
+
+    auto finv = [] (float &x) {
+        float x3 = x * x * x;
+        if (x3 > 0.008856) {
+            x = x3;
+        } else {
+            x = (x - 16.0 / 116.0) / 7.787;
+        }
+    };
+
+    finv(vx);
+    finv(vy);
+    finv(vz);
+
+    vx *= 0.95047; // use white = D65
+    vz *= 1.08883;
+
+    float vr = vx *  3.2406 + vy * -1.5372 + vz * -0.4986;
+    float vg = vx * -0.9689 + vy *  1.8758 + vz *  0.0415;
+    float vb = vx *  0.0557 + vy * -0.2040 + vz *  1.0570;
+
+    auto from_linear = [] (float &x) {
+        if (x > 0.0031308) {
+            x = 1.055 * std::pow(x, 1.0 / 2.4) - 0.055;
+        } else {
+            x *= 12.92;
+        }
+    };
+
+    from_linear(vr);
+    from_linear(vg);
+    from_linear(vb);
+
+    return getRGB(vr, vg, vb);
+}
+
+float CieLab::diffSq(CieLab const &c1, CieLab const &c2)
+{
+    return sq(c1.L - c2.L)
+         + sq(c1.A - c2.A)
+         + sq(c1.B - c2.B);
+}
+
+float CieLab::diff(CieLab const &c1, CieLab const &c2)
+{
+    return std::sqrt(diffSq(c1, c2));
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/cielab.h b/src/trace/cielab.h
new file mode 100644
index 0000000..66b0ea6
--- /dev/null
+++ b/src/trace/cielab.h
@@ -0,0 +1,106 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping
+ * Conversion to C++ for Inkscape by Bob Jamison
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_CIELAB_H
+#define INKSCAPE_TRACE_CIELAB_H
+
+#include <cstdint>
+
+namespace Inkscape {
+namespace Trace {
+
+class CieLab
+{
+public:
+    CieLab()
+    {
+        C = 0;
+        L = A = B = 0.0f;
+    }
+
+    /**
+     * Construct this CieLab from an ARGB value
+     */
+    CieLab(uint32_t rgb);
+
+    CieLab(float l, float a, float b)
+    {
+        C = 0;
+        L = l;
+        A = a;
+        B = b;
+    }
+
+    CieLab(CieLab const &other)
+    {
+        C = other.C;
+        L = other.L;
+        A = other.A;
+        B = other.B;
+    }
+
+    CieLab &operator=(CieLab const &other)
+    {
+        C = other.C;
+        L = other.L;
+        A = other.A;
+        B = other.B;
+        return *this;
+    }
+
+    /**
+     * Retrieve a CieLab value via index.
+     */
+    float operator()(unsigned index) const
+    {
+        switch (index) {
+            case 0: return L;
+            case 1: return A;
+            case 2: return B;
+            default: return 0;
+        }
+    }
+
+    void add(CieLab const &other)
+    {
+        C += other.C;
+        L += other.L;
+        A += other.A;
+        B += other.B;
+    }
+
+    void mul(float scale)
+    {
+        L *= scale;
+        A *= scale;
+        B *= scale;
+    }
+
+    /**
+     * Return this CieLab's value converted to an ARGB value
+     */
+    uint32_t toRGB() const;
+
+    /**
+     * Squared Euclidean distance between two colors in CieLab space.
+     */
+    static float diffSq(CieLab const &c1, CieLab const &c2);
+
+    /**
+     * Computes euclidean distance in CieLab space between two colors.
+     */
+    static float diff(CieLab const &c1, CieLab const &c2);
+
+    unsigned C;
+    float L;
+    float A;
+    float B;
+};
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_CIELAB_H
diff --git a/src/trace/depixelize/inkscape-depixelize.cpp b/src/trace/depixelize/inkscape-depixelize.cpp
new file mode 100644
index 0000000..ae3c783
--- /dev/null
+++ b/src/trace/depixelize/inkscape-depixelize.cpp
@@ -0,0 +1,107 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * This is the C++ glue between Inkscape and Potrace
+ *
+ * Authors:
+ *   Bob Jamison <rjamison@titan.com>
+ *   Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ * Potrace, the wonderful tracer located at http://potrace.sourceforge.net,
+ * is provided by the generosity of Peter Selinger, to whom we are grateful.
+ *
+ */
+#include <iomanip>
+#include <thread>
+#include <glibmm/i18n.h>
+
+#include "inkscape-depixelize.h"
+
+#include "color.h"
+#include "preferences.h"
+#include "async/progress.h"
+#include "svg/svg-color.h"
+#include "svg/css-ostringstream.h"
+
+namespace Inkscape {
+namespace Trace {
+namespace Depixelize {
+
+DepixelizeTracingEngine::DepixelizeTracingEngine(TraceType traceType, double curves, int islands, int sparsePixels, double sparseMultiplier, bool optimize)
+    : traceType(traceType)
+{
+    params.curvesMultiplier = curves;
+    params.islandsWeight = islands;
+    params.sparsePixelsRadius = sparsePixels;
+    params.sparsePixelsMultiplier = sparseMultiplier;
+    params.optimize = optimize;
+    params.nthreads = Inkscape::Preferences::get()->getIntLimited("/options/threading/numthreads", std::thread::hardware_concurrency(), 1, 256);
+}
+
+TraceResult DepixelizeTracingEngine::trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+    TraceResult res;
+
+    ::Tracer::Splines splines;
+
+    if (traceType == TraceType::VORONOI) {
+        splines = ::Tracer::Kopf2011::to_voronoi(pixbuf, params);
+    } else {
+        splines = ::Tracer::Kopf2011::to_splines(pixbuf, params);
+    }
+
+    progress.report_or_throw(0.5);
+
+    auto subprogress = Async::SubProgress(progress, 0.5, 0.5);
+    auto throttled = Async::ProgressStepThrottler(subprogress, 0.02);
+
+    int num_splines = std::distance(splines.begin(), splines.end());
+    int i = 0;
+
+    for (auto &it : splines) {
+        throttled.report_or_throw((double)i / num_splines);
+        i++;
+
+        char b[64];
+        sp_svg_write_color(b, sizeof(b),
+                           SP_RGBA32_U_COMPOSE(unsigned(it.rgba[0]),
+                                               unsigned(it.rgba[1]),
+                                               unsigned(it.rgba[2]),
+                                               unsigned(it.rgba[3])));
+        Inkscape::CSSOStringStream osalpha;
+        osalpha << it.rgba[3] / 255.0f;
+        char *style = g_strdup_printf("fill:%s;fill-opacity:%s;", b, osalpha.str().c_str());
+        res.emplace_back(style, std::move(it.pathVector));
+        g_free(style);
+    }
+
+    return res;
+}
+
+Glib::RefPtr<Gdk::Pixbuf> DepixelizeTracingEngine::preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf)
+{
+    return pixbuf;
+}
+
+bool DepixelizeTracingEngine::check_image_size(Geom::IntPoint const &size) const
+{
+    return size.x() > 256 || size.y() > 256;
+}
+
+} // namespace Depixelize
+} // namespace Trace
+} // namespace Inkscape
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/depixelize/inkscape-depixelize.h b/src/trace/depixelize/inkscape-depixelize.h
new file mode 100644
index 0000000..adeefdc
--- /dev/null
+++ b/src/trace/depixelize/inkscape-depixelize.h
@@ -0,0 +1,60 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * This is the C++ glue between Inkscape and Potrace
+ *
+ * Copyright (C) 2019 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ * Potrace, the wonderful tracer located at http://potrace.sourceforge.net,
+ * is provided by the generosity of Peter Selinger, to whom we are grateful.
+ *
+ */
+#ifndef INKSCAPE_TRACE_DEPIXELIZE_H
+#define INKSCAPE_TRACE_DEPIXELIZE_H
+
+#include "trace/trace.h"
+#include "3rdparty/libdepixelize/kopftracer2011.h" // Cannot move to source file due to nested class.
+
+namespace Inkscape {
+namespace Trace {
+namespace Depixelize {
+
+enum class TraceType
+{
+    VORONOI,
+    BSPLINES
+};
+
+class DepixelizeTracingEngine final
+    : public TracingEngine
+{
+public:
+    DepixelizeTracingEngine() = default;
+    DepixelizeTracingEngine(TraceType traceType, double curves, int islands, int sparsePixels, double sparseMultiplier, bool optimize);
+
+    TraceResult trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress) override;
+    Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) override;
+    bool check_image_size(Geom::IntPoint const &size) const override;
+
+private:
+    ::Tracer::Kopf2011::Options params;
+    TraceType traceType = TraceType::VORONOI;
+};
+
+} // namespace Depixelize
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_DEPIXELIZE_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/filterset.cpp b/src/trace/filterset.cpp
new file mode 100644
index 0000000..1be5228
--- /dev/null
+++ b/src/trace/filterset.cpp
@@ -0,0 +1,272 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Some filters for Potrace in Inkscape
+ *
+ * Authors:
+ *   Bob Jamison <rjamison@titan.com>
+ *   Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <cstdio>
+#include "imagemap-gdk.h"
+#include "filterset.h"
+#include "quantize.h"
+
+namespace Inkscape {
+namespace Trace {
+
+/*#########################################################################
+### G A U S S I A N  (smoothing)
+#########################################################################*/
+
+static int gaussMatrix[] =
+{
+    2,  4,  5,  4, 2,
+    4,  9, 12,  9, 4,
+    5, 12, 15, 12, 5,
+    4,  9, 12,  9, 4,
+    2,  4,  5,  4, 2
+};
+
+GrayMap grayMapGaussian(GrayMap const &me) // Todo: Make member function, keep implementation here
+{
+    int width  = me.width;
+    int height = me.height;
+    int firstX = 2;
+    int lastX  = width - 3;
+    int firstY = 2;
+    int lastY  = height - 3;
+
+    auto newGm = GrayMap(width, height);
+
+    for (int y = 0; y < height; y++) {
+        for (int x = 0; x < width; x++) {
+            // image boundaries
+            if (x < firstX || x > lastX || y < firstY || y > lastY) {
+                newGm.setPixel(x, y, me.getPixel(x, y));
+                continue;
+            }
+
+            // all other pixels
+            int gaussIndex = 0;
+            unsigned long sum = 0;
+            for (int i = y - 2; i <= y + 2; i++) {
+                for (int j = x - 2; j <= x + 2; j++) {
+                    int weight = gaussMatrix[gaussIndex++];
+                    sum += me.getPixel(j, i) * weight;
+                }
+            }
+            sum /= 159;
+            sum = std::min(sum, GrayMap::WHITE);
+            newGm.setPixel(x, y, sum);
+        }
+    }
+
+    return newGm;
+}
+
+RgbMap rgbMapGaussian(RgbMap const &me)
+{
+    int width  = me.width;
+    int height = me.height;
+    int firstX = 2;
+    int lastX  = width-3;
+    int firstY = 2;
+    int lastY  = height-3;
+
+    auto newGm = RgbMap(width, height);
+
+    for (int y = 0; y < height; y++) {
+        for (int x = 0; x < width; x++) {
+            // image boundaries
+            if (x < firstX || x > lastX || y < firstY || y > lastY) {
+                newGm.setPixel(x, y, me.getPixel(x, y));
+                continue;
+            }
+
+            // all other pixels
+            int gaussIndex = 0;
+            int sumR       = 0;
+            int sumG       = 0;
+            int sumB       = 0;
+            for (int i = y - 2; i <= y + 2; i++) {
+                for (int j = x - 2; j <= x + 2; j++) {
+                    int weight = gaussMatrix[gaussIndex++];
+                    RGB rgb = me.getPixel(j, i);
+                    sumR += weight * rgb.r;
+                    sumG += weight * rgb.g;
+                    sumB += weight * rgb.b;
+                }
+	        }
+            RGB rout;
+            rout.r = (sumR / 159) & 0xff;
+            rout.g = (sumG / 159) & 0xff;
+            rout.b = (sumB / 159) & 0xff;
+            newGm.setPixel(x, y, rout);
+	    }
+	}
+
+    return newGm;
+}
+
+/*#########################################################################
+### C A N N Y    E D G E    D E T E C T I O N
+#########################################################################*/
+
+static int sobelX[] =
+{
+    -1,  0,  1 ,
+    -2,  0,  2 ,
+    -1,  0,  1 
+};
+
+static int sobelY[] =
+{
+     1,  2,  1 ,
+     0,  0,  0 ,
+    -1, -2, -1 
+};
+
+/**
+ * Perform Sobel convolution on a GrayMap.
+ */
+GrayMap grayMapCanny(GrayMap const &gm, double dLowThreshold, double dHighThreshold)
+{
+    int width  = gm.width;
+    int height = gm.height;
+    int firstX = 1;
+    int lastX  = width - 2;
+    int firstY = 1;
+    int lastY  = height - 2;
+
+    auto map = GrayMap(width, height);
+
+    for (int y = 0; y < height; y++) {
+        for (int x = 0; x < width; x++) {
+            bool edge;
+            // image boundaries
+            if (x < firstX || x > lastX || y < firstY || y > lastY) {
+                edge = false;
+            } else {
+                // SOBEL FILTERING
+                long sumX = 0;
+                long sumY = 0;
+                int sobelIndex = 0;
+                for (int i = y-1; i <= y + 1; i++) {
+                    for (int j = x - 1; j <= x + 1; j++) {
+                        sumX += gm.getPixel(j, i) * sobelX[sobelIndex++];
+                    }
+	            }
+
+                sobelIndex = 0;
+                for (int i = y - 1; i <= y + 1; i++) {
+                    for (int j = x - 1; j <= x + 1; j++) {
+                        sumY += gm.getPixel(j, i) * sobelY[sobelIndex++];
+                    }
+	            }
+
+                // GET VALUE
+                unsigned long sum = std::abs(sumX) + std::abs(sumY);
+                sum = std::min(sum, GrayMap::WHITE);
+
+                // GET EDGE DIRECTION (fast way)
+                int edgeDirection = 0; // x, y = 0
+                if (sumX == 0) {
+                    if (sumY != 0) {
+                        edgeDirection = 90;
+                    }
+                } else {
+                    long slope = sumY * 1024 / sumX;
+                    if (slope > 2472 || slope< -2472) { // tan(67.5) * 1024
+                        edgeDirection = 90;
+                    } else if (slope > 414) { // tan(22.5) * 1024
+                        edgeDirection = 45;
+                    } else if (slope < -414) { // -tan(22.5) * 1024
+                        edgeDirection = 135;
+                    }
+                }
+
+                // printf("%ld %ld %f %d\n", sumX, sumY, orient, edgeDirection);
+
+                // Get two adjacent pixels in edge direction
+                unsigned long leftPixel;
+                unsigned long rightPixel;
+                if (edgeDirection == 0) {
+                    leftPixel  = gm.getPixel(x - 1, y);
+                    rightPixel = gm.getPixel(x + 1, y);
+                } else if (edgeDirection == 45) {
+                    leftPixel  = gm.getPixel(x - 1, y + 1);
+                    rightPixel = gm.getPixel(x + 1, y - 1);
+                } else if (edgeDirection == 90) {
+                    leftPixel  = gm.getPixel(x, y - 1);
+                    rightPixel = gm.getPixel(x, y + 1);
+                } else { // 135
+                    leftPixel  = gm.getPixel(x - 1, y - 1);
+                    rightPixel = gm.getPixel(x + 1, y + 1);
+                }
+
+                // Compare current value to adjacent pixels. (If less than either, suppress it.)
+                if (sum < leftPixel || sum < rightPixel) {
+                    edge = false;
+                } else {
+                    unsigned long highThreshold = dHighThreshold * GrayMap::WHITE;
+                    unsigned long lowThreshold  = dLowThreshold  * GrayMap::WHITE;
+                    if (sum >= highThreshold) {
+                        edge = true;
+                    } else if (sum < lowThreshold) {
+                        edge = false;
+                    } else {
+                        edge = gm.getPixel(x - 1, y - 1) > highThreshold ||
+                               gm.getPixel(x    , y - 1) > highThreshold ||
+                               gm.getPixel(x + 1, y - 1) > highThreshold ||
+                               gm.getPixel(x - 1, y    ) > highThreshold ||
+                               gm.getPixel(x + 1, y    ) > highThreshold ||
+                               gm.getPixel(x - 1, y + 1) > highThreshold ||
+                               gm.getPixel(x    , y + 1) > highThreshold ||
+                               gm.getPixel(x + 1, y + 1) > highThreshold;
+                    }
+                }
+            }
+
+            // show edges as dark over light
+            map.setPixel(x, y, edge ? GrayMap::BLACK : GrayMap::WHITE);
+        }
+    }
+
+    // map.writePPM("canny.ppm");
+    return map;
+}
+
+/*#########################################################################
+### Q U A N T I Z A T I O N
+#########################################################################*/
+
+GrayMap quantizeBand(RgbMap const &rgbMap, int nrColors)
+{
+    auto gaussMap = rgbMapGaussian(rgbMap);
+    // gaussMap->writePPM(gaussMap, "rgbgauss.ppm");
+
+    auto qMap = rgbMapQuantize(gaussMap, nrColors);
+    // qMap->writePPM(qMap, "rgbquant.ppm");
+
+    auto gm = GrayMap(rgbMap.width, rgbMap.height);
+
+    // RGB is quantized. There should now be a small set of (R+G+B)
+    for (int y = 0; y < qMap.height; y++) {
+        for (int x = 0; x < qMap.width; x++) {
+            auto rgb = qMap.getPixelValue(x, y);
+            int sum = rgb.r + rgb.g + rgb.b;
+            auto result = (sum & 1) ? GrayMap::WHITE : GrayMap::BLACK;
+            // printf("%d %d %d : %d\n", rgb.r, rgb.g, rgb.b, index);
+            gm.setPixel(x, y, result);
+        }
+    }
+
+    return gm;
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/filterset.h b/src/trace/filterset.h
new file mode 100644
index 0000000..a85714d
--- /dev/null
+++ b/src/trace/filterset.h
@@ -0,0 +1,39 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Some filters for Potrace in Inkscape
+ *
+ * Authors:
+ *   Bob Jamison <rjamison@titan.com>
+ *   Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_FILTERSET_H
+#define INKSCAPE_TRACE_FILTERSET_H
+
+#include <gdk-pixbuf/gdk-pixbuf.h>
+#include "imagemap.h"
+
+namespace Inkscape {
+namespace Trace {
+
+/**
+ * Apply gaussian blur to an GrayMap.
+ */
+GrayMap grayMapGaussian(GrayMap const &gmap);
+
+/**
+ * Apply gaussian blur to an RgbMap.
+ */
+RgbMap rgbMapGaussian(RgbMap const &rgbmap);
+
+GrayMap grayMapCanny(GrayMap const &gmap, double lowThreshold, double highThreshold);
+
+GrayMap quantizeBand(RgbMap const &rgbmap, int nrColors);
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_FILTERSET_H
diff --git a/src/trace/imagemap-gdk.cpp b/src/trace/imagemap-gdk.cpp
new file mode 100644
index 0000000..9d47b3b
--- /dev/null
+++ b/src/trace/imagemap-gdk.cpp
@@ -0,0 +1,110 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <cassert>
+#include "imagemap-gdk.h"
+
+namespace Inkscape {
+namespace Trace {
+
+GrayMap gdkPixbufToGrayMap(Glib::RefPtr<Gdk::Pixbuf> const &buf)
+{
+    int width     = buf->get_width();
+    int height    = buf->get_height();
+    int rowstride = buf->get_rowstride();
+    int nchannels = buf->get_n_channels();
+    auto data     = buf->get_pixels();
+
+    auto map = GrayMap(width, height);
+
+    for (int y = 0; y < height; y++) {
+        auto p = data + rowstride * y;
+        for (int x = 0; x < width; x++) {
+            int alpha = nchannels == 3 ? 255 : p[3];
+            int white = 3 * (255 - alpha);
+            unsigned long sample = (int)p[0] + (int)p[1] + (int)p[2];
+            unsigned long bright = sample * alpha / 256 + white;
+            map.setPixel(x, y, bright);
+            p += nchannels;
+        }
+    }
+
+    return map;
+}
+
+Glib::RefPtr<Gdk::Pixbuf> grayMapToGdkPixbuf(GrayMap const &map)
+{
+    auto buf = Gdk::Pixbuf::create(Gdk::COLORSPACE_RGB, false, 8, map.width, map.height);
+
+    int rowstride = buf->get_rowstride();
+    int nchannels = buf->get_n_channels();
+    auto data     = buf->get_pixels();
+
+    for (int y = 0; y < map.height; y++) {
+        auto p = data + rowstride * y;
+        for (int x = 0; x < map.width; x++) {
+            unsigned long pix = map.getPixel(x, y) / 3;
+            p[0] = p[1] = p[2] = pix & 0xff;
+            p += nchannels;
+        }
+    }
+
+    return buf;
+}
+
+RgbMap gdkPixbufToRgbMap(Glib::RefPtr<Gdk::Pixbuf> const &buf)
+{
+    int width     = buf->get_width();
+    int height    = buf->get_height();
+    int rowstride = buf->get_rowstride();
+    int nchannels = buf->get_n_channels();
+    auto data     = buf->get_pixels();
+
+    auto map = RgbMap(width, height);
+
+    for (int y = 0; y < height; y++) {
+        auto p = data + rowstride * y;
+        for (int x = 0; x < width; x++) {
+            int alpha = nchannels == 3 ? 255 : p[3];
+            int white = 255 - alpha;
+            unsigned char r = (int)p[0] * alpha / 256 + white;
+            unsigned char g = (int)p[1] * alpha / 256 + white;
+            unsigned char b = (int)p[2] * alpha / 256 + white;
+            map.setPixel(x, y, {r, g, b});
+            p += nchannels;
+        }
+    }
+
+    return map;
+}
+
+Glib::RefPtr<Gdk::Pixbuf> indexedMapToGdkPixbuf(IndexedMap const &map)
+{
+    auto buf = Gdk::Pixbuf::create(Gdk::COLORSPACE_RGB, false, 8, map.width, map.height);
+
+    auto data     = buf->get_pixels();
+    int rowstride = buf->get_rowstride();
+    int nchannels = buf->get_n_channels();
+
+    for (int y = 0; y < map.height; y++) {
+        auto p = data + rowstride * y;
+        for (int x = 0; x < map.width; x++) {
+            auto rgb = map.getPixelValue(x, y);
+            p[0] = rgb.r & 0xff;
+            p[1] = rgb.g & 0xff;
+            p[2] = rgb.b & 0xff;
+            p += nchannels;
+        }
+    }
+
+    return buf;
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/imagemap-gdk.h b/src/trace/imagemap-gdk.h
new file mode 100644
index 0000000..58ebbbb
--- /dev/null
+++ b/src/trace/imagemap-gdk.h
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2013 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_IMAGEMAP_GDK_H
+#define INKSCAPE_TRACE_IMAGEMAP_GDK_H
+
+#include <gdkmm/pixbuf.h>
+#include "imagemap.h"
+
+namespace Inkscape {
+namespace Trace {
+
+GrayMap gdkPixbufToGrayMap(Glib::RefPtr<Gdk::Pixbuf> const &);
+Glib::RefPtr<Gdk::Pixbuf> grayMapToGdkPixbuf(GrayMap const &);
+RgbMap gdkPixbufToRgbMap(Glib::RefPtr<Gdk::Pixbuf> const &);
+Glib::RefPtr<Gdk::Pixbuf> indexedMapToGdkPixbuf(IndexedMap const &);
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_IMAGEMAP_GDK_H
diff --git a/src/trace/imagemap.cpp b/src/trace/imagemap.cpp
new file mode 100644
index 0000000..48acd8c
--- /dev/null
+++ b/src/trace/imagemap.cpp
@@ -0,0 +1,128 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <cstdio>
+#include "imagemap.h"
+
+namespace Inkscape {
+namespace Trace {
+
+/*
+ * GrayMap
+ */
+
+GrayMap::GrayMap(int width, int height)
+    : MapBase(width, height)
+{
+}
+
+bool GrayMap::writePPM(char const *fileName)
+{
+    if (!fileName) {
+        return false;
+    }
+
+    auto f = std::fopen(fileName, "wb");
+    if (!f) {
+        return false;
+    }
+
+    std::fprintf(f, "P6 %d %d 255\n", width, height);
+
+    for (int y = 0; y < height; y++) {
+        for (int x = 0; x < width; x++) {
+            auto pix = getPixel(x, y) / 3;
+            unsigned char pixb = pix & 0xff;
+            std::fputc(pixb, f);
+            std::fputc(pixb, f);
+            std::fputc(pixb, f);
+        }
+    }
+
+    std::fclose(f);
+
+    return true;
+}
+
+/*
+ * RgbMap
+ */
+
+RgbMap::RgbMap(int width, int height)
+    : MapBase(width, height)
+{
+}
+
+bool RgbMap::writePPM(char const *fileName)
+{
+    if (!fileName) {
+        return false;
+    }
+
+    auto f = std::fopen(fileName, "wb");
+    if (!f) {
+        return false;
+    }
+
+    std::fprintf(f, "P6 %d %d 255\n", width, height);
+
+    for (int y = 0; y < height; y++) {
+        for (int x = 0; x < width; x++) {
+            auto rgb = getPixel(x, y);
+            std::fputc(rgb.r, f);
+            std::fputc(rgb.g, f);
+            std::fputc(rgb.b, f);
+        }
+    }
+
+    std::fclose(f);
+
+    return true;
+}
+
+/*
+ * IndexedMap
+ */
+
+IndexedMap::IndexedMap(int width, int height)
+    : MapBase(width, height)
+    , nrColors(0)
+{
+    clut.fill(RGB{0, 0, 0});
+}
+
+bool IndexedMap::writePPM(char const *fileName)
+{
+    if (!fileName) {
+        return false;
+    }
+
+    auto f = std::fopen(fileName, "wb");
+    if (!f) {
+        return false;
+    }
+
+    std::fprintf(f, "P6 %d %d 255\n", width, height);
+
+    for (int y = 0; y < height; y++) {
+        for (int x = 0; x < width; x++) {
+            auto rgb = getPixelValue(x, y);
+            std::fputc(rgb.r, f);
+            std::fputc(rgb.g, f);
+            std::fputc(rgb.b, f);
+        }
+    }
+
+    std::fclose(f);
+
+    return true;
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/imagemap.h b/src/trace/imagemap.h
new file mode 100644
index 0000000..542e641
--- /dev/null
+++ b/src/trace/imagemap.h
@@ -0,0 +1,91 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_IMAGEMAP_H
+#define INKSCAPE_TRACE_IMAGEMAP_H
+
+#include <vector>
+#include <array>
+
+namespace Inkscape {
+namespace Trace {
+
+template <typename T>
+struct MapBase
+{
+    int width;
+    int height;
+    std::vector<T> pixels;
+
+    MapBase(int width, int height)
+        : width(width)
+        , height(height)
+        , pixels(width * height) {}
+
+    int offset(int x, int y) const { return x + y * width; }
+    T       *row(int y)       { return pixels.data() + y * width; }
+    T const *row(int y) const { return pixels.data() + y * width; }
+    void setPixel(int x, int y, T val) { pixels[offset(x, y)] = val; }
+    T getPixel(int x, int y) const { return pixels[offset(x, y)]; }
+};
+
+/*
+ * GrayMap
+ */
+
+struct GrayMap
+    : MapBase<unsigned long>
+{
+    static unsigned long constexpr BLACK = 0;
+    static unsigned long constexpr WHITE = 255 * 3;
+
+    GrayMap(int width, int height);
+
+    bool writePPM(char const *fileName);
+};
+
+/*
+ * RgbMap
+ */
+
+struct RGB
+{
+    unsigned char r;
+    unsigned char g;
+    unsigned char b;
+};
+
+struct RgbMap
+    : MapBase<RGB>
+{
+    RgbMap(int width, int height);
+
+    bool writePPM(char const *fileName);
+};
+
+/*
+ * IndexedMap
+ */
+
+struct IndexedMap
+    : MapBase<unsigned>
+{
+    IndexedMap(int width, int height);
+
+    RGB getPixelValue(int x, int y) const { return clut[getPixel(x, y) % clut.size()]; }
+    bool writePPM(char const *fileName);
+
+    int nrColors;
+    std::array<RGB, 256> clut; ///< Color look-up table.
+};
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_IMAGEMAP_H
diff --git a/src/trace/pool.h b/src/trace/pool.h
new file mode 100644
index 0000000..742050a
--- /dev/null
+++ b/src/trace/pool.h
@@ -0,0 +1,117 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Pool memory allocation
+ *
+ * Authors:
+ *   Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+
+// not thread safe (a pool cannot be shared by threads safely)
+
+/*
+-- principle:
+
+ - user operations on a pool of objects of type T are:
+   - T *draw() : obtain a unused slot to store an object T
+   - void drop(T *) : release a slot
+
+-- implementation:
+
+ - a pool for objects T is:
+
+   * blocks[64] : an array of allocated blocks of memory:
+     |---0--> block with capacity 64
+     |---1--> block with capacity 64
+     |---2--> block with capacity 128
+     |---3--> block with capacity 128
+     |---4--> block with capacity 256
+     |---5--> block with capacity 256
+     |---6--> block with capacity 512
+     |---7--> not yet allocated
+     :
+     |---k--> not yet allocated (future capacity ~ 2^(6+k/2))
+     :
+     '--63--> not yet allocated
+   * cblock : the index of the next unallocated block (here 7).
+   * next : a pointer to an unused slot inside an allocated bloc
+
+ - the first bytes of an unallocated slot inside a bloc are used to store a
+   pointer to some other unallocated slot. (this way, we keep a list of all
+   unused slots starting at <next>)
+
+ - insertions and deletions in this list are done at the root <next>.
+   if <next> points to NULL (no slots are available) when a draw()
+   operation is performed a new block is allocated, and the unused slots
+   list is filled with the allocated slots.
+
+ - memory is freed only at pool's deletion.
+*/
+#ifndef INKSCAPE_TRACE_POOL_H
+#define INKSCAPE_TRACE_POOL_H
+
+#include <cstdlib>
+#include <exception>
+#include <algorithm>
+
+template <typename T>
+class Pool
+{
+public:
+    Pool()
+    {
+        cblock = 0;
+        size = std::max(sizeof(T), sizeof(void *));
+        next = nullptr;
+        for (auto &k : block) {
+            k = nullptr;
+        }
+    }
+
+    ~Pool()
+    {
+        for (int k = 0; k < cblock; k++) {
+            std::free(block[k]);
+        }
+    }
+
+    T *draw()
+    {
+        if (!next) addblock();
+        void *p = next;
+        next = *(void **)p;
+        return (T *)p;
+    }
+
+    void drop(T *p)
+    {
+        *(void **)p = next;
+        next = (void *)p;
+    }
+
+private:
+    int size;
+    int cblock;
+    void *block[64]; // enough to store unlimited number of objects, if 64 is changed: see constructor too
+    void *next;
+
+    void addblock()
+    {
+        int i = cblock++;
+        int blocksize = 1 << (6 + (i / 2));
+        block[i] = (void *)std::malloc(blocksize * size);
+        if (!block[i]) throw std::bad_alloc();
+        char *p = (char *)block[i];
+        for (int k = 0; k < blocksize - 1; k++) {
+            *(void**)p = (void *)(p + size);
+            p += size;
+        }
+        *(void **)p = next;
+        next = block[i];
+    }
+};
+
+#endif // INKSCAPE_TRACE_POOL_H
diff --git a/src/trace/potrace/bitmap.h b/src/trace/potrace/bitmap.h
new file mode 100644
index 0000000..2fb07e8
--- /dev/null
+++ b/src/trace/potrace/bitmap.h
@@ -0,0 +1,118 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * inline macros for accessing bitmaps
+ */
+/* Copyright (C) 2001-2015 Peter Selinger.
+   This file is part of Potrace. It is free software and it is covered
+   by the GNU General Public License. See the file COPYING for details. */
+
+#ifndef BITMAP_H
+#define BITMAP_H
+
+#include <cstring>
+#include <cstdlib>
+#include <cerrno>
+#include <cstddef>
+
+/* The bitmap type is defined in potracelib.h */
+#include "potracelib.h"
+
+/* The present file defines some convenient macros and static inline
+   functions for accessing bitmaps. Since they only produce inline
+   code, they can be conveniently shared by the library and frontends,
+   if desired */
+
+/* ---------------------------------------------------------------------- */
+/* some measurements */
+
+#define BM_WORDSIZE ((int)sizeof(potrace_word))
+#define BM_WORDBITS (8*BM_WORDSIZE)
+#define BM_HIBIT (((potrace_word)1)<<(BM_WORDBITS-1))
+#define BM_ALLBITS (~(potrace_word)0)
+
+/* macros for accessing pixel at index (x,y). U* macros omit the
+   bounds check. */
+
+#define bm_scanline(bm, y) ((bm)->map + (ptrdiff_t)(y)*(ptrdiff_t)(bm)->dy)
+#define bm_index(bm, x, y) (&bm_scanline(bm, y)[(x)/BM_WORDBITS])
+#define bm_mask(x) (BM_HIBIT >> ((x) & (BM_WORDBITS-1)))
+#define bm_range(x, a) ((int)(x) >= 0 && (int)(x) < (a))
+#define bm_safe(bm, x, y) (bm_range(x, (bm)->w) && bm_range(y, (bm)->h))
+#define BM_UGET(bm, x, y) ((*bm_index(bm, x, y) & bm_mask(x)) != 0)
+#define BM_USET(bm, x, y) (*bm_index(bm, x, y) |= bm_mask(x))
+#define BM_UCLR(bm, x, y) (*bm_index(bm, x, y) &= ~bm_mask(x))
+#define BM_UINV(bm, x, y) (*bm_index(bm, x, y) ^= bm_mask(x))
+#define BM_UPUT(bm, x, y, b) ((b) ? BM_USET(bm, x, y) : BM_UCLR(bm, x, y))
+#define BM_GET(bm, x, y) (bm_safe(bm, x, y) ? BM_UGET(bm, x, y) : 0)
+#define BM_SET(bm, x, y) (bm_safe(bm, x, y) ? BM_USET(bm, x, y) : 0)
+#define BM_CLR(bm, x, y) (bm_safe(bm, x, y) ? BM_UCLR(bm, x, y) : 0)
+#define BM_INV(bm, x, y) (bm_safe(bm, x, y) ? BM_UINV(bm, x, y) : 0)
+#define BM_PUT(bm, x, y, b) (bm_safe(bm, x, y) ? BM_UPUT(bm, x, y, b) : 0)
+
+/* free the given bitmap. Leaves errno untouched. */
+static inline void bm_free(potrace_bitmap_t *bm) {
+  if (bm) {
+    free(bm->map);
+  }
+  free(bm);
+}
+
+/* return new un-initialized bitmap. NULL with errno on error.
+   Assumes w, h >= 0. */
+static inline potrace_bitmap_t *bm_new(int w, int h) {
+  potrace_bitmap_t *bm;
+  int dy = w == 0 ? 0 : (w - 1) / BM_WORDBITS + 1;
+  ptrdiff_t size = (ptrdiff_t)dy * (ptrdiff_t)h * (ptrdiff_t)BM_WORDSIZE;
+
+  /* check for overflow error */
+  if (size < 0 || (h != 0 && dy != 0 && size / h / dy != BM_WORDSIZE)) {
+    errno = ENOMEM;
+    return nullptr;
+  }
+
+  bm = (potrace_bitmap_t *) malloc(sizeof(potrace_bitmap_t));
+  if (!bm) {
+    return nullptr;
+  }
+  bm->w = w;
+  bm->h = h;
+  bm->dy = dy;
+  bm->map = (potrace_word *) malloc(size);
+  if (!bm->map) {
+    g_warning("bm_new: can not allocate memory for bitmap (%td).", size);
+    free(bm);
+    return nullptr;
+  }
+  return bm;
+}
+
+/* clear the given bitmap. Set all bits to c. */
+static inline void bm_clear(potrace_bitmap_t *bm, int c) {
+  /* Note: if the bitmap was created with bm_new, then it is
+     guaranteed that size will fit into the ptrdiff_t type. */
+  ptrdiff_t size = (ptrdiff_t)bm->dy * (ptrdiff_t)bm->h * (ptrdiff_t)BM_WORDSIZE;
+  memset(bm->map, c ? -1 : 0, size);
+}
+
+/* duplicate the given bitmap. Return NULL on error with errno set. */
+static inline potrace_bitmap_t *bm_dup(const potrace_bitmap_t *bm) {
+  potrace_bitmap_t *bm1 = bm_new(bm->w, bm->h);
+  ptrdiff_t size = (ptrdiff_t)bm->dy * (ptrdiff_t)bm->h * (ptrdiff_t)BM_WORDSIZE;
+  if (!bm1) {
+    return nullptr;
+  }
+  memcpy(bm1->map, bm->map, size);
+  return bm1;
+}
+
+/* invert the given bitmap. */
+static inline void bm_invert(potrace_bitmap_t *bm) {
+  ptrdiff_t i;
+  ptrdiff_t size = (ptrdiff_t)bm->dy * (ptrdiff_t)bm->h;
+
+  for (i = 0; i < size; i++) {
+    bm->map[i] ^= BM_ALLBITS;
+  }
+}
+
+#endif /* BITMAP_H */
diff --git a/src/trace/potrace/inkscape-potrace.cpp b/src/trace/potrace/inkscape-potrace.cpp
new file mode 100644
index 0000000..24fe173
--- /dev/null
+++ b/src/trace/potrace/inkscape-potrace.cpp
@@ -0,0 +1,456 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * This is the C++ glue between Inkscape and Potrace
+ *
+ * Authors:
+ *   Bob Jamison <rjamison@titan.com>
+ *   Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ * Potrace, the wonderful tracer located at http://potrace.sourceforge.net,
+ * is provided by the generosity of Peter Selinger, to whom we are grateful.
+ *
+ */
+#include <iomanip>
+#include <glibmm/i18n.h>
+#include <gtkmm/main.h>
+#include <potracelib.h>
+
+#include "inkscape-potrace.h"
+#include "bitmap.h"
+
+#include "async/progress.h"
+#include "trace/filterset.h"
+#include "trace/quantize.h"
+#include "trace/imagemap-gdk.h"
+
+namespace {
+
+struct potrace_state_deleter { void operator()(potrace_state_t *p) { potrace_state_free(p); }; };
+using potrace_state_uniqptr = std::unique_ptr<potrace_state_t, potrace_state_deleter>;
+
+struct potrace_bitmap_deleter { void operator()(potrace_bitmap_t *p) { bm_free(p); }; };
+using potrace_bitmap_uniqptr = std::unique_ptr<potrace_bitmap_t, potrace_bitmap_deleter>;
+
+Glib::ustring twohex(int value)
+{
+    return Glib::ustring::format(std::hex, std::setfill(L'0'), std::setw(2), value);
+}
+
+} // namespace
+
+namespace Inkscape {
+namespace Trace {
+namespace Potrace {
+
+PotraceTracingEngine::PotraceTracingEngine() { common_init(); }
+
+PotraceTracingEngine::PotraceTracingEngine(TraceType traceType, bool invert, int quantizationNrColors, double brightnessThreshold, double brightnessFloor, double cannyHighThreshold, int multiScanNrColors, bool multiScanStack, bool multiScanSmooth, bool multiScanRemoveBackground)
+    : traceType(traceType)
+    , invert(invert)
+    , quantizationNrColors(quantizationNrColors)
+    , brightnessThreshold(brightnessThreshold)
+    , brightnessFloor(brightnessFloor)
+    , cannyHighThreshold(cannyHighThreshold)
+    , multiScanNrColors(multiScanNrColors)
+    , multiScanStack(multiScanStack)
+    , multiScanSmooth(multiScanSmooth)
+    , multiScanRemoveBackground(multiScanRemoveBackground) { common_init(); }
+
+void PotraceTracingEngine::common_init()
+{
+    potraceParams = potrace_param_default();
+}
+
+PotraceTracingEngine::~PotraceTracingEngine()
+{
+    potrace_param_free(potraceParams);
+}
+
+void PotraceTracingEngine::setOptiCurve(int opticurve)
+{
+    potraceParams->opticurve = opticurve;
+}
+
+void PotraceTracingEngine::setOptTolerance(double opttolerance)
+{
+    potraceParams->opttolerance = opttolerance;
+}
+
+void PotraceTracingEngine::setAlphaMax(double alphamax)
+{
+    potraceParams->alphamax = alphamax;
+}
+
+void PotraceTracingEngine::setTurdSize(int turdsize)
+{
+    potraceParams->turdsize = turdsize;
+}
+
+/**
+ * Recursively descend the potrace_path_t node tree \a paths, writing paths to \a builder.
+ * The \a points set is used to prevent redundant paths.
+ */
+void PotraceTracingEngine::writePaths(potrace_path_t *paths, Geom::PathBuilder &builder, std::unordered_set<Geom::Point, geom_point_hash> &points, Async::Progress<double> &progress) const
+{
+    auto to_geom = [] (potrace_dpoint_t const &c) {
+        return Geom::Point(c.x, c.y);
+    };
+
+    for (auto path = paths; path; path = path->sibling) {
+        progress.throw_if_cancelled();
+
+        auto const &curve = path->curve;
+        // g_message("node->fm:%d\n", node->fm);
+        if (curve.n == 0) {
+            continue;
+        }
+
+        auto seg = curve.c[curve.n - 1];
+        auto const pt = to_geom(seg[2]);
+        // Have we been here already?
+        auto inserted = points.emplace(pt).second;
+        if (!inserted) {
+            // g_message("duplicate point: (%f,%f)\n", x2, y2);
+            continue;
+        }
+        builder.moveTo(pt);
+
+        for (int i = 0; i < curve.n; i++) {
+            auto seg = curve.c[i];
+            switch (curve.tag[i]) {
+                case POTRACE_CORNER:
+                    builder.lineTo(to_geom(seg[1]));
+                    builder.lineTo(to_geom(seg[2]));
+                    break;
+                case POTRACE_CURVETO:
+                    builder.curveTo(to_geom(seg[0]), to_geom(seg[1]), to_geom(seg[2]));
+                    break;
+                default:
+                    break;
+            }
+        }
+        builder.closePath();
+
+        for (auto child = path->childlist; child; child = child->sibling) {
+            writePaths(child, builder, points, progress);
+        }
+    }
+}
+
+std::optional<GrayMap> PotraceTracingEngine::filter(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) const
+{
+    std::optional<GrayMap> map;
+
+    if (traceType == TraceType::QUANT) {
+
+        // Color quantization -- banding
+        auto rgbmap = gdkPixbufToRgbMap(pixbuf);
+        // rgbMap->writePPM(rgbMap, "rgb.ppm");
+        map = quantizeBand(rgbmap, quantizationNrColors);
+
+    } else if (traceType == TraceType::BRIGHTNESS || traceType == TraceType::BRIGHTNESS_MULTI) {
+
+        // Brightness threshold
+        auto gm = gdkPixbufToGrayMap(pixbuf);
+        map = GrayMap(gm.width, gm.height);
+
+        double floor = 3.0 * brightnessFloor * 256.0;
+        double cutoff = 3.0 * brightnessThreshold * 256.0;
+        for (int y = 0; y < gm.height; y++) {
+            for (int x = 0; x < gm.width; x++) {
+                double brightness = gm.getPixel(x, y);
+                bool black = brightness >= floor && brightness < cutoff;
+                map->setPixel(x, y, black ? GrayMap::BLACK : GrayMap::WHITE);
+            }
+        }
+
+        // map->writePPM(map, "brightness.ppm");
+
+    } else if (traceType == TraceType::CANNY) {
+
+        // Canny edge detection
+        auto gm = gdkPixbufToGrayMap(pixbuf);
+        map = grayMapCanny(gm, 0.1, cannyHighThreshold);
+        // map->writePPM(map, "canny.ppm");
+
+    }
+
+    // Invert the image if necessary.
+    if (map && invert) {
+        for (int y = 0; y < map->height; y++) {
+            for (int x = 0; x < map->width; x++) {
+                auto brightness = map->getPixel(x, y);
+                brightness = GrayMap::WHITE - brightness;
+                map->setPixel(x, y, brightness);
+            }
+        }
+    }
+
+    return map;
+}
+
+IndexedMap PotraceTracingEngine::filterIndexed(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) const
+{
+    auto map = gdkPixbufToRgbMap(pixbuf);
+
+    if (multiScanSmooth) {
+        map = rgbMapGaussian(map);
+    }
+
+    auto imap = rgbMapQuantize(map, multiScanNrColors);
+
+    auto tomono = [] (RGB c) -> RGB {
+        unsigned char s = ((int)c.r + (int)c.g + (int)c.b) / 3;
+        return { s, s, s };
+    };
+
+    if (traceType == TraceType::QUANT_MONO || traceType == TraceType::BRIGHTNESS_MULTI) {
+        // Turn to grays
+        for (auto &c : imap.clut) {
+            c = tomono(c);
+        }
+    }
+
+    return imap;
+}
+
+Glib::RefPtr<Gdk::Pixbuf> PotraceTracingEngine::preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf)
+{
+    if (traceType == TraceType::QUANT_COLOR ||
+        traceType == TraceType::QUANT_MONO  ||
+        traceType == TraceType::BRIGHTNESS_MULTI) // this is a lie: multipass doesn't use filterIndexed, but it's a better preview approx than filter()
+    {
+        auto gm = filterIndexed(pixbuf);
+
+        return indexedMapToGdkPixbuf(gm);
+
+    } else {
+
+        auto gm = filter(pixbuf);
+        if (!gm) {
+            return {};
+        }
+
+        return grayMapToGdkPixbuf(*gm);
+    }
+}
+
+/**
+ * This is the actual wrapper of the call to Potrace.
+ */
+Geom::PathVector PotraceTracingEngine::grayMapToPath(GrayMap const &grayMap, Async::Progress<double> &progress)
+{
+    auto potraceBitmap = potrace_bitmap_uniqptr(bm_new(grayMap.width, grayMap.height));
+    if (!potraceBitmap) {
+        return {};
+    }
+
+    bm_clear(potraceBitmap.get(), 0);
+
+    // Read the data out of the GrayMap
+    for (int y = 0; y < grayMap.height; y++) {
+        for (int x = 0; x < grayMap.width; x++) {
+            BM_UPUT(potraceBitmap, x, y, grayMap.getPixel(x, y) ? 0 : 1);
+        }
+    }
+
+    progress.throw_if_cancelled();
+
+    //##Debug
+    /*
+    FILE *f = fopen("poimage.pbm", "wb");
+    bm_writepbm(f, bm);
+    fclose(f);
+    */
+
+    // Trace the bitmap.
+
+    auto throttled = Async::ProgressStepThrottler(progress, 0.02);
+
+    potraceParams->progress.data = &throttled;
+    potraceParams->progress.callback = [] (double progress, void *data) { reinterpret_cast<decltype(throttled)*>(data)->report(progress); };
+    auto potraceState = potrace_state_uniqptr(potrace_trace(potraceParams, potraceBitmap.get()));
+
+    potraceBitmap.reset();
+
+    progress.throw_if_cancelled();
+
+    // Extract the paths into a pathvector and return it.
+    Geom::PathBuilder builder;
+    std::unordered_set<Geom::Point, geom_point_hash> points;
+    writePaths(potraceState->plist, builder, points, progress);
+    return builder.peek();
+}
+
+/**
+ * This is called for a single scan.
+ */
+TraceResult PotraceTracingEngine::traceSingle(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+    brightnessFloor = 0.0; // important to set this, since used by filter()
+
+    auto grayMap = filter(pixbuf);
+    if (!grayMap) {
+        return {};
+    }
+
+    progress.report_or_throw(0.2);
+
+    auto sub_gm = Async::SubProgress(progress, 0.2, 0.8);
+    auto pv = grayMapToPath(*grayMap, sub_gm);
+
+    TraceResult results;
+    results.emplace_back("fill:#000000", std::move(pv));
+    return results;
+}
+
+/**
+ * This allows routines that already generate GrayMaps to skip image filtering, increasing performance.
+ */
+TraceResult PotraceTracingEngine::traceGrayMap(GrayMap const &grayMap, Async::Progress<double> &progress)
+{
+    auto pv = grayMapToPath(grayMap, progress);
+
+    TraceResult results;
+    results.emplace_back("fill:#000000", std::move(pv));
+    return results;
+}
+
+/**
+ * Called for multiple-scanning algorithms
+ */
+TraceResult PotraceTracingEngine::traceBrightnessMulti(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+    double constexpr low   = 0.2; // bottom of range
+    double constexpr high  = 0.9; // top of range
+    double const     delta = (high - low) / multiScanNrColors;
+
+    brightnessFloor = 0.0; // Set bottom to black
+
+    TraceResult results;
+
+    for (int i = 0; i < multiScanNrColors; i++) {
+        auto subprogress = Async::SubProgress(progress, (double)i / multiScanNrColors, 1.0 / multiScanNrColors);
+
+        brightnessThreshold = low + delta * i;
+
+        auto grayMap = filter(pixbuf);
+        if (!grayMap) {
+            continue;
+        }
+
+        subprogress.report_or_throw(0.2);
+
+        auto sub_gmtopath = Async::SubProgress(subprogress, 0.2, 0.8);
+        auto pv = grayMapToPath(*grayMap, sub_gmtopath);
+        if (pv.empty()) {
+            continue;
+        }
+
+        // get style info
+        int grayVal = 256.0 * brightnessThreshold;
+        auto style = Glib::ustring::compose("fill-opacity:1.0;fill:#%1%2%3", twohex(grayVal), twohex(grayVal), twohex(grayVal));
+
+        // g_message("### GOT '%s' \n", style.c_str());
+        results.emplace_back(style.raw(), std::move(pv));
+
+        if (!multiScanStack) {
+            brightnessFloor = brightnessThreshold;
+        }
+
+        subprogress.report_or_throw(1.0);
+    }
+
+    // Remove the bottom-most scan, if requested.
+    if (results.size() > 1 && multiScanRemoveBackground) {
+        results.pop_back();
+    }
+
+    return results;
+}
+
+/**
+ * Quantization
+ */
+TraceResult PotraceTracingEngine::traceQuant(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+    auto imap = filterIndexed(pixbuf);
+
+    // Create and clear a gray map
+    auto gm = GrayMap(imap.width, imap.height);
+    for (int row = 0; row < gm.height; row++) {
+        for (int col = 0; col < gm.width; col++) {
+            gm.setPixel(col, row, GrayMap::WHITE);
+        }
+    }
+
+    TraceResult results;
+
+    for (int colorIndex = 0; colorIndex < imap.nrColors; colorIndex++) {
+        auto subprogress = Async::SubProgress(progress, (double)colorIndex / imap.nrColors, 1.0 / imap.nrColors);
+
+        // Update the graymap for the current color index
+        for (int row = 0; row < imap.height; row++) {
+            for (int col = 0; col < imap.width; col++) {
+                int index = imap.getPixel(col, row);
+                if (index == colorIndex) {
+                    gm.setPixel(col, row, GrayMap::BLACK);
+                } else if (!multiScanStack) {
+                    gm.setPixel(col, row, GrayMap::WHITE);
+                }
+            }
+        }
+
+        subprogress.report_or_throw(0.2);
+
+        // Now we have a traceable graymap
+        auto sub_gmtopath = Async::SubProgress(subprogress, 0.2, 0.8);
+        auto pv = grayMapToPath(gm, sub_gmtopath);
+
+        if (!pv.empty()) {
+            // get style info
+            auto rgb = imap.clut[colorIndex];
+            auto style = Glib::ustring::compose("fill:#%1%2%3", twohex(rgb.r), twohex(rgb.g), twohex(rgb.b));
+            results.emplace_back(style.raw(), std::move(pv));
+        }
+
+        subprogress.report_or_throw(1.0);
+    }
+
+    // Remove the bottom-most scan, if requested.
+    if (results.size() > 1 && multiScanRemoveBackground) {
+        results.pop_back();
+    }
+
+    return results;
+}
+
+TraceResult PotraceTracingEngine::trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+    if (traceType == TraceType::QUANT_COLOR || traceType == TraceType::QUANT_MONO) {
+        return traceQuant(pixbuf, progress);
+    } else if (traceType == TraceType::BRIGHTNESS_MULTI) {
+        return traceBrightnessMulti(pixbuf, progress);
+    } else {
+        return traceSingle(pixbuf, progress);
+    }
+}
+
+} // namespace Potrace
+} // namespace Trace
+} // namespace Inkscape
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/potrace/inkscape-potrace.h b/src/trace/potrace/inkscape-potrace.h
new file mode 100644
index 0000000..0e4a9c6
--- /dev/null
+++ b/src/trace/potrace/inkscape-potrace.h
@@ -0,0 +1,140 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * This is the C++ glue between Inkscape and Potrace
+ *
+ * Authors:
+ *   Bob Jamison <rjamison@titan.com>
+ *   Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ * Potrace, the wonderful tracer located at http://potrace.sourceforge.net,
+ * is provided by the generosity of Peter Selinger, to whom we are grateful.
+ *
+ */
+#ifndef INKSCAPE_TRACE_POTRACE_H
+#define INKSCAPE_TRACE_POTRACE_H
+
+#include <optional>
+#include <unordered_set>
+#include <boost/functional/hash.hpp>
+#include <2geom/point.h>
+#include <2geom/path-sink.h>
+#include "trace/trace.h"
+#include "trace/imagemap.h"
+using potrace_param_t = struct potrace_param_s;
+using potrace_path_t  = struct potrace_path_s;
+
+namespace Inkscape {
+namespace Trace {
+namespace Potrace {
+
+enum class TraceType
+{
+    BRIGHTNESS,
+    BRIGHTNESS_MULTI,
+    CANNY,
+    QUANT,
+    QUANT_COLOR,
+    QUANT_MONO,
+    // Used in tracedialog.cpp
+    AUTOTRACE_SINGLE,
+    AUTOTRACE_MULTI,
+    AUTOTRACE_CENTERLINE
+};
+
+// Todo: Make lib2geom types hashable.
+struct geom_point_hash
+{
+    std::size_t operator()(Geom::Point const &pt) const
+    {
+        std::size_t hash = 0;
+        boost::hash_combine(hash, pt.x());
+        boost::hash_combine(hash, pt.y());
+        return hash;
+    }
+};
+
+class PotraceTracingEngine final
+    : public TracingEngine
+{
+public:
+    PotraceTracingEngine();
+    PotraceTracingEngine(TraceType traceType,
+                         bool invert,
+                         int quantizationNrColors,
+                         double brightnessThreshold,
+                         double brightnessFloor,
+                         double cannyHighThreshold,
+                         int multiScanNrColors,
+                         bool multiScanStack,
+                         bool multiScanSmooth ,
+                         bool multiScanRemoveBackground);
+    ~PotraceTracingEngine() override;
+
+    TraceResult trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress) override;
+    Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) override;
+
+    TraceResult traceGrayMap(GrayMap const &grayMap, Async::Progress<double> &progress);
+
+    void setOptiCurve(int);
+    void setOptTolerance(double);
+    void setAlphaMax(double);
+    void setTurdSize(int);
+
+private:
+    potrace_param_t *potraceParams;
+
+    TraceType traceType = TraceType::BRIGHTNESS;
+
+    // Whether the image should be inverted at the end.
+    bool invert = false;
+
+    // Color -> b&w quantization
+    int quantizationNrColors = 8;
+
+    // Brightness items
+    double brightnessThreshold = 0.45;
+    double brightnessFloor = 0.0;
+
+    // Canny items
+    double cannyHighThreshold = 0.65;
+
+    // Color -> multiscan quantization
+    int multiScanNrColors = 8;
+    bool multiScanStack = true; // do we tile or stack?
+    bool multiScanSmooth = false; // do we use gaussian filter?
+    bool multiScanRemoveBackground = false; // do we remove the bottom trace?
+
+    void common_init();
+
+    TraceResult traceQuant          (Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress);
+    TraceResult traceBrightnessMulti(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress);
+    TraceResult traceSingle         (Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress);
+
+    IndexedMap filterIndexed(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) const;
+    std::optional<GrayMap> filter(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) const;
+
+    Geom::PathVector grayMapToPath(GrayMap const &gm, Async::Progress<double> &progress);
+
+    void writePaths(potrace_path_t *paths, Geom::PathBuilder &builder, std::unordered_set<Geom::Point, geom_point_hash> &points, Async::Progress<double> &progress) const;
+};
+
+} // namespace Potrace
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_POTRACE_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/quantize.cpp b/src/trace/quantize.cpp
new file mode 100644
index 0000000..a79ec01
--- /dev/null
+++ b/src/trace/quantize.cpp
@@ -0,0 +1,555 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Quantization for Inkscape
+ *
+ * Authors:
+ *   Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <memory>
+#include <cassert>
+#include <cstdio>
+#include <glib.h>
+
+#include "pool.h"
+#include "imagemap.h"
+#include "quantize.h"
+
+namespace Inkscape {
+namespace Trace {
+
+namespace {
+
+/**
+ * an octree node datastructure
+ */
+struct Ocnode
+{
+    Ocnode *parent;           // parent node
+    Ocnode **ref;             // node's reference
+    Ocnode *child[8];         // children
+    int nchild;               // number of children
+    int width;                // width level of this node
+    RGB rgb;                  // rgb's prefix of that node
+    unsigned long weight;     // number of pixels this node accounts for
+    unsigned long rs, gs, bs; // sum of pixels colors this node accounts for
+    int nleaf;                // number of leaves under this node
+    unsigned long mi;         // minimum impact
+};
+
+/*
+-- algorithm principle:
+
+- inspired by the octree method, we associate a tree to a given color map
+
+- nodes in those trees have this shape:
+
+                                parent
+                                   |
+        color_prefix(stored in rgb):width
+     colors_sum(stored in rs,gs,bs)/weight
+         /               |               \
+     child1           child2           child3
+
+- (grayscale) trees associated to pixels with colors 87 = 0b1010111 and
+  69 = 0b1000101 are:
+
+           .                 .    <-- roots of the trees
+           |                 |
+    1010111:0  and    1000101:0   <-- color prefixes, written in binary form
+         87/1              69/1   <-- color sums, written in decimal form
+
+- the result of merging the two trees is:
+
+                   .
+                   |
+                 10:5       <----- longest common prefix and binary width
+                156/2       <---.  of the covered color range.
+            /            \      |
+    1000101:0      1010111:0    '- sum of colors and quantity of pixels
+         69/1           87/1       this node accounts for
+
+  one should consider three cases when two trees are to be merged:
+  - one tree range is included in the range of the other one, and the first
+    tree has to be inserted as a child (or merged with the corresponding
+    child) of the other.
+  - their ranges are the same, and their children have to be merged under
+    a single root.
+  - ranges have no intersection, and a fork node has to be created (like in
+    the given example).
+
+- a tree for an image is built dividing the image in 2 parts and merging
+  the trees obtained recursively for the two parts. a tree for a one pixel
+  part is a leaf like one of those which were given above.
+
+- last, this tree is reduced a specified number of leaves, deleting first
+  leaves with minimal impact i.e. [ weight * 2^(2*parentwidth) ] value :
+  a fair approximation of the impact a leaf removal would have on the final
+  result : it's the corresponding covered area times the square of the
+  introduced color distance.
+
+  deletion of a node A below a node with only two children is done as
+  follows :
+
+  - when the sibling is a leaf, the sibling is deleted as well, both nodes
+    are then represented by their parent.
+
+     |               |
+     .       ==>     .
+    / \
+   A   .
+
+  - otherwise the deletion of A deletes also its parent, which plays no
+    role anymore:
+
+     |                |
+     .       ==>       \
+    / \                 |
+   A   .                .
+      / \              / \
+
+  in that way, every leaf removal operation really decreases the remaining
+  total number of leaves by one.
+
+- very last, color indexes are attributed to leaves; associated colors are
+  averages, computed from weight and color components sums.
+
+-- improvements to the usual octree method:
+
+- since this algorithm shall often be used to perform quantization using a
+  very low (2-16) set of colors and not with a usual 256 value, we choose
+  more carefully which nodes are to be deleted.
+
+- depth of leaves is not fixed to an arbitrary number (which should be 8
+  when color components are in 0-255), so there is no need to go down to a
+  depth of 8 for each pixel (at full precision), unless it is really
+  required.
+
+- tree merging also fastens the overall tree building, and intermediate
+  processing could be done.
+
+- a huge optimization against the stupid removal algorithm (i.e. find a best
+  match over the whole tree, remove it and do it again) was implemented:
+  nodes are marked with the minimal impact of the removal of a leaf below
+  it. we proceed to the removal recursively. we stop when current removal
+  level is above the current node minimal, otherwise reached leaves are
+  removed, and every change over minimal impacts is propagated back to the
+  whole tree when the recursion ends.
+
+-- specific optimizations
+
+- pool allocation is used to allocate nodes (increased performance on large
+  images).
+
+*/
+
+RGB operator>>(RGB rgb, int s)
+{
+    RGB res;
+    res.r = rgb.r >> s;
+    res.g = rgb.g >> s;
+    res.b = rgb.b >> s;
+    return res;
+}
+
+bool operator==(RGB rgb1, RGB rgb2)
+{
+    return rgb1.r == rgb2.r && rgb1.g == rgb2.g && rgb1.b == rgb2.b;
+}
+
+int childIndex(RGB rgb)
+{
+    return ((rgb.r & 1) << 2) | ((rgb.g & 1) << 1) | (rgb.b & 1);
+}
+
+/**
+ * allocate a new node
+ */
+Ocnode *ocnodeNew(Pool<Ocnode> &pool)
+{
+    Ocnode *node = pool.draw();
+    node->ref = nullptr;
+    node->parent = nullptr;
+    node->nchild = 0;
+    for (auto &i : node->child) {
+        i = nullptr;
+    }
+    node->mi = 0;
+    return node;
+}
+
+void ocnodeFree(Pool<Ocnode> &pool, Ocnode *node)
+{
+    pool.drop(node);
+}
+
+/**
+ * free a full octree
+ */
+void octreeDelete(Pool<Ocnode> &pool, Ocnode *node)
+{
+    if (!node) return;
+    for (auto &i : node->child) {
+        octreeDelete(pool, i);
+    }
+    ocnodeFree(pool, node);
+}
+
+/**
+ *  pretty-print an octree, debugging purposes
+ */
+#if 0
+void ocnodePrint(Ocnode *node, int indent)
+{
+    if (!node) return;
+    printf("width:%d weight:%lu rgb:%6x nleaf:%d mi:%lu\n",
+           node->width,
+           node->weight,
+           (unsigned int)(
+           ((node->rs / node->weight) << 16) +
+           ((node->gs / node->weight) << 8) +
+           (node->bs / node->weight)),
+           node->nleaf,
+           node->mi
+           );
+    for (int i = 0; i < 8; i++) if (node->child[i])
+        {
+        for (int k = 0; k < indent; k++) printf(" ");//indentation
+        printf("[%d:%p] ", i, node->child[i]);
+        ocnodePrint(node->child[i], indent+2);
+        }
+}
+
+void octreePrint(Ocnode *node)
+{
+    printf("<<octree>>\n");
+    if (node) printf("[r:%p] ", node); ocnodePrint(node, 2);
+}
+#endif
+
+/**
+ * builds a single <rgb> color leaf at location <ref>
+ */
+void ocnodeLeaf(Pool<Ocnode> &pool, Ocnode **ref, RGB rgb)
+{
+    assert(ref);
+    Ocnode *node = ocnodeNew(pool);
+    node->width = 0;
+    node->rgb = rgb;
+    node->rs = rgb.r; node->gs = rgb.g; node->bs = rgb.b;
+    node->weight = 1;
+    node->nleaf = 1;
+    node->mi = 0;
+    node->ref = ref;
+    *ref = node;
+}
+
+/**
+ *  merge nodes <node1> and <node2> at location <ref> with parent <parent>
+ */
+int octreeMerge(Pool<Ocnode> &pool, Ocnode *parent, Ocnode **ref, Ocnode *node1, Ocnode *node2)
+{
+    assert(ref);
+    if (!node1 && !node2) return 0;
+    assert(node1 != node2);
+    if (parent && !*ref) parent->nchild++;
+    if (!node1) {
+        *ref = node2; node2->ref = ref; node2->parent = parent;
+        return node2->nleaf;
+    }
+    if (!node2) {
+        *ref = node1; node1->ref = ref; node1->parent = parent;
+        return node1->nleaf;
+    }
+    int dwitdth = node1->width - node2->width;
+    if (dwitdth > 0 && node1->rgb == node2->rgb >> dwitdth) {
+        // place node2 below node1
+        *ref = node1; node1->ref = ref; node1->parent = parent;
+        int i = childIndex(node2->rgb >> (dwitdth - 1));
+        node1->rs += node2->rs; node1->gs += node2->gs; node1->bs += node2->bs;
+        node1->weight += node2->weight;
+        node1->mi = 0;
+        if (node1->child[i]) node1->nleaf -= node1->child[i]->nleaf;
+        node1->nleaf += octreeMerge(pool, node1, &node1->child[i], node1->child[i], node2);
+        return node1->nleaf;
+    } else if (dwitdth < 0 && node2->rgb == node1->rgb >> (-dwitdth)) {
+        // place node1 below node2
+        *ref = node2; node2->ref = ref; node2->parent = parent;
+        int i = childIndex(node1->rgb >> (-dwitdth - 1));
+        node2->rs += node1->rs; node2->gs += node1->gs; node2->bs += node1->bs;
+        node2->weight += node1->weight;
+        node2->mi = 0;
+        if (node2->child[i]) node2->nleaf -= node2->child[i]->nleaf;
+        node2->nleaf += octreeMerge(pool, node2, &node2->child[i], node2->child[i], node1);
+        return node2->nleaf;
+    } else {
+        // nodes have either no intersection or the same root
+        Ocnode *newnode;
+        newnode = ocnodeNew(pool);
+        newnode->rs = node1->rs + node2->rs;
+        newnode->gs = node1->gs + node2->gs;
+        newnode->bs = node1->bs + node2->bs;
+        newnode->weight = node1->weight + node2->weight;
+        *ref = newnode; newnode->ref = ref; newnode->parent = parent;
+        if (dwitdth == 0 && node1->rgb == node2->rgb) {
+            // merge the nodes in <newnode>
+            newnode->width = node1->width; // == node2->width
+            newnode->rgb = node1->rgb;     // == node2->rgb
+            newnode->nchild = 0;
+            newnode->nleaf = 0;
+            if (node1->nchild == 0 && node2->nchild == 0) {
+                newnode->nleaf = 1;
+            } else {
+                for (int i = 0; i < 8; i++) {
+                    if (node1->child[i] || node2->child[i]) {
+                        newnode->nleaf += octreeMerge(pool, newnode, &newnode->child[i], node1->child[i], node2->child[i]);
+                    }
+                }
+            }
+            ocnodeFree(pool, node1); ocnodeFree(pool, node2);
+            return newnode->nleaf;
+        } else {
+            // use <newnode> as a fork node with children <node1> and <node2>
+            int newwidth = std::max(node1->width, node2->width);
+            RGB rgb1 = node1->rgb >> (newwidth - node1->width);
+            RGB rgb2 = node2->rgb >> (newwidth - node2->width);
+            // according to the previous tests <rgb1> != <rgb2> before the loop
+            while (!(rgb1 == rgb2)) {
+                rgb1 = rgb1 >> 1;
+                rgb2 = rgb2 >> 1;
+                newwidth++;
+            }
+            newnode->width = newwidth;
+            newnode->rgb = rgb1; // == rgb2
+            newnode->nchild = 2;
+            newnode->nleaf = node1->nleaf + node2->nleaf;
+            int i1 = childIndex(node1->rgb >> (newwidth - node1->width - 1));
+            int i2 = childIndex(node2->rgb >> (newwidth - node2->width - 1));
+            node1->parent = newnode;
+            node1->ref = &newnode->child[i1];
+            newnode->child[i1] = node1;
+            node2->parent = newnode;
+            node2->ref = &newnode->child[i2];
+            newnode->child[i2] = node2;
+            return newnode->nleaf;
+        }
+    }
+}
+
+/**
+ * upatade mi value for leaves
+ */
+void ocnodeMi(Ocnode *node)
+{
+    node->mi = node->parent ? node->weight << (2 * node->parent->width) : 0;
+}
+
+/**
+ * remove leaves whose prune impact value is lower than <lvl>. at most
+ * <count> leaves are removed, and <count> is decreased on each removal.
+ * all parameters including minimal impact values are regenerated.
+ */
+void ocnodeStrip(Pool<Ocnode> &pool, Ocnode **ref, int &count, unsigned long lvl)
+{
+    Ocnode *node = *ref;
+    if (!node) return;
+    assert(ref == node->ref);
+    if (node->nchild == 0) { // leaf node
+        if (!node->mi) ocnodeMi(node); // mi generation may be required
+        if (node->mi > lvl) return; // leaf is above strip level
+        ocnodeFree(pool, node);
+        *ref = nullptr;
+        count--;
+    } else {
+        if (node->mi && node->mi > lvl) return; // node is above strip level
+        node->nchild = 0;
+        node->nleaf = 0;
+        node->mi = 0;
+        Ocnode **lonelychild = nullptr;
+        for (auto & i : node->child) {
+            if (i) {
+                ocnodeStrip(pool, &i, count, lvl);
+                if (i) {
+                    lonelychild = &i;
+                    node->nchild++;
+                    node->nleaf += i->nleaf;
+                    if (!node->mi || node->mi > i->mi) {
+                        node->mi = i->mi;
+                    }
+                }
+            }
+        }
+        // tree adjustments
+        if (node->nchild == 0) {
+            count++;
+            node->nleaf = 1;
+            ocnodeMi(node);
+        } else if (node->nchild == 1) {
+            if ((*lonelychild)->nchild == 0) {
+                // remove the <lonelychild> leaf under a 1 child node
+                node->nchild = 0;
+                node->nleaf = 1;
+                ocnodeMi(node);
+                ocnodeFree(pool, *lonelychild);
+                *lonelychild = nullptr;
+            } else {
+                // make a bridge to <lonelychild> over a 1 child node
+                (*lonelychild)->parent = node->parent;
+                (*lonelychild)->ref = ref;
+                ocnodeFree(pool, node);
+                *ref = *lonelychild;
+            }
+        }
+    }
+}
+
+/**
+ * reduce the leaves of an octree to a given number
+ */
+void octreePrune(Pool<Ocnode> &pool, Ocnode **ref, int ncolor)
+{
+    assert(ref);
+    assert(ncolor > 0);
+    int n = (*ref)->nleaf - ncolor;
+    if (!*ref || n <= 0) return;
+    while (n > 0) {
+        ocnodeStrip(pool, ref, n, (*ref)->mi);
+    }
+}
+
+/**
+ * build an octree associated to the area of a color map <rgbmap>,
+ * included in the specified (x1,y1)--(x2,y2) rectangle.
+ */
+void octreeBuildArea(Pool<Ocnode> &pool, RgbMap const &rgbmap, Ocnode **ref, int x1, int y1, int x2, int y2, int ncolor)
+{
+    int dx = x2 - x1, dy = y2 - y1;
+    int xm = x1 + dx / 2, ym = y1 + dy / 2;
+    Ocnode *ref1 = nullptr;
+    Ocnode *ref2 = nullptr;
+    if (dx == 1 && dy == 1) {
+        ocnodeLeaf(pool, ref, rgbmap.getPixel(x1, y1));
+    } else if (dx > dy) {
+        octreeBuildArea(pool, rgbmap, &ref1, x1, y1, xm, y2, ncolor);
+        octreeBuildArea(pool, rgbmap, &ref2, xm, y1, x2, y2, ncolor);
+        octreeMerge(pool, nullptr, ref, ref1, ref2);
+    } else {
+        octreeBuildArea(pool, rgbmap, &ref1, x1, y1, x2, ym, ncolor);
+        octreeBuildArea(pool, rgbmap, &ref2, x1, ym, x2, y2, ncolor);
+        octreeMerge(pool, nullptr, ref, ref1, ref2);
+	}
+
+    // octreePrune(ref, 2 * ncolor);
+    // affects result quality for almost same performance :/
+}
+
+/**
+ * build an octree associated to the <rgbmap> color map,
+ * pruned to <ncolor> colors.
+ */
+Ocnode *octreeBuild(Pool<Ocnode> &pool, RgbMap const &rgbmap, int ncolor)
+{
+    // create the octree
+    Ocnode *node = nullptr;
+    octreeBuildArea(pool,
+                    rgbmap, &node,
+                    0, 0, rgbmap.width, rgbmap.height, ncolor);
+
+    // prune the octree
+    octreePrune(pool, &node, ncolor);
+
+    return node;
+}
+
+/**
+ * compute the color palette associated to an octree.
+ */
+void octreeIndex(Ocnode *node, RGB *rgbpal, int &index)
+{
+    if (!node) return;
+    if (node->nchild == 0) {
+        rgbpal[index].r = node->rs / node->weight;
+        rgbpal[index].g = node->gs / node->weight;
+        rgbpal[index].b = node->bs / node->weight;
+        index++;
+    } else {
+        for (auto &i : node->child) {
+            if (i) {
+                octreeIndex(i, rgbpal, index);
+            }
+        }
+    }
+}
+
+/**
+ * compute the squared distance between two colors
+ */
+int distRGB(RGB rgb1, RGB rgb2)
+{
+    return (rgb1.r - rgb2.r) * (rgb1.r - rgb2.r)
+         + (rgb1.g - rgb2.g) * (rgb1.g - rgb2.g)
+         + (rgb1.b - rgb2.b) * (rgb1.b - rgb2.b);
+}
+
+/**
+ * find the index of closest color in a palette
+ */
+int findRGB(RGB const *rgbs, int ncolor, RGB rgb)
+{
+    int index = -1, dist = 0;
+    for (int k = 0; k < ncolor; k++) {
+        int d = distRGB(rgbs[k], rgb);
+        if (index == -1 || d < dist) { dist = d; index = k; }
+    }
+    return index;
+}
+
+} // namespace
+
+/**
+ * quantize an RGB image to a reduced number of colors.
+ */
+IndexedMap rgbMapQuantize(RgbMap const &rgbmap, int ncolor)
+{
+    assert(ncolor > 0);
+
+    auto imap = IndexedMap(rgbmap.width, rgbmap.height);
+
+    Pool<Ocnode> pool;
+    auto tree = octreeBuild(pool, rgbmap, ncolor);
+
+    auto rgbs = std::make_unique<RGB[]>(ncolor);
+    int index = 0;
+    octreeIndex(tree, rgbs.get(), index);
+
+    octreeDelete(pool, tree);
+
+    // stacking with increasing contrasts
+    std::sort(rgbs.get(), rgbs.get() + ncolor, [] (auto &ra, auto &rb) {
+        return (ra.r + ra.g + ra.b) < (rb.r + rb.g + rb.b);
+    });
+
+    // make the new map
+    // fill in the color lookup table
+    for (int i = 0; i < index; i++) {
+        imap.clut[i] = rgbs[i];
+    }
+    imap.nrColors = index;
+
+    // fill in new map pixels
+    for (int y = 0; y < rgbmap.height; y++) {
+        for (int x = 0; x < rgbmap.width; x++) {
+            auto rgb = rgbmap.getPixel(x, y);
+            int index = findRGB(rgbs.get(), ncolor, rgb);
+            imap.setPixel(x, y, index);
+        }
+    }
+
+    return imap;
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/quantize.h b/src/trace/quantize.h
new file mode 100644
index 0000000..fea2d39
--- /dev/null
+++ b/src/trace/quantize.h
@@ -0,0 +1,28 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ *  Quantization for Inkscape
+ *
+ * Authors:
+ *   Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_QUANTIZE_H
+#define INKSCAPE_TRACE_QUANTIZE_H
+
+#include "imagemap.h"
+
+namespace Inkscape {
+namespace Trace {
+
+/**
+ * Quantize an RGB image to a reduced number of colors.
+ */
+IndexedMap rgbMapQuantize(RgbMap const &rgbmap, int nrColors);
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_QUANTIZE_H
diff --git a/src/trace/siox.cpp b/src/trace/siox.cpp
new file mode 100644
index 0000000..a958821
--- /dev/null
+++ b/src/trace/siox.cpp
@@ -0,0 +1,770 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+   Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping
+
+   Conversion to C++ for Inkscape by Bob Jamison
+
+   Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <cmath>
+#include <cstdarg>
+#include <unordered_map>
+#include <algorithm>
+#include <cstdlib>
+#include <cassert>
+
+#include "siox.h"
+#include "async/progress.h"
+
+namespace Inkscape {
+namespace Trace {
+
+//########################################################################
+//#  S I O X    I M A G E
+//########################################################################
+
+SioxImage::SioxImage(Glib::RefPtr<Gdk::Pixbuf> const &buf)
+{
+    width = buf->get_width();
+    height = buf->get_height();
+
+    // Allocate data arrays.
+    int size = width * height;
+    pixdata.resize(size);
+    cmdata.resize(size);
+
+    int rowstride = buf->get_rowstride();
+    int nchannels = buf->get_n_channels();
+    auto data     = buf->get_pixels();
+
+    // Copy pixel data.
+    for (int y = 0; y < height; y++) {
+        auto p = data + rowstride * y;
+        for (int x = 0; x < width; x++) {
+            uint32_t r = p[0];
+            uint32_t g = p[1];
+            uint32_t b = p[2];
+            uint32_t a = nchannels == 3 ? 255 : p[3];
+            pixdata[offset(x, y)] = (a << 24) | (r << 16) | (g << 8) | b;
+            p += nchannels;
+        }
+    }
+
+    // Zero confidence matrix.
+    std::fill(cmdata.begin(), cmdata.end(), 0.0f);
+}
+
+Glib::RefPtr<Gdk::Pixbuf> SioxImage::getGdkPixbuf() const
+{
+    auto buf = Gdk::Pixbuf::create(Gdk::COLORSPACE_RGB, true, 8, width, height);
+
+    int rowstride = buf->get_rowstride();
+    int nchannels = buf->get_n_channels();
+    auto data     = buf->get_pixels();
+
+    for (int y = 0; y < height; y++) {
+        auto p = data + rowstride * y;
+        for (int x = 0; x < width; x++) {
+            uint32_t rgb = pixdata[offset(x, y)];
+            p[0] = (rgb >> 16) & 0xff; // r
+            p[1] = (rgb >>  8) & 0xff; // g
+            p[2] = (rgb      ) & 0xff; // b
+            p[3] = (rgb >> 24) & 0xff; // a
+            p += nchannels;
+        }
+    }
+
+    return buf;
+}
+
+bool SioxImage::writePPM(char const *filename) const
+{
+    auto f = std::fopen(filename, "wb");
+    if (!f) {
+        return false;
+    }
+
+    std::fprintf(f, "P6 %u %u 255\n", width, height);
+
+    for (int y = 0; y < height; y++) {
+        for (int x = 0; x < width; x++) {
+            uint32_t rgb = pixdata[offset(x, y)];
+            uint8_t r = (rgb >> 16) & 0xff;
+            uint8_t g = (rgb >>  8) & 0xff;
+            uint8_t b = (rgb      ) & 0xff;
+            std::fputc(r, f);
+            std::fputc(g, f);
+            std::fputc(b, f);
+        }
+    }
+
+    std::fclose(f);
+
+    return true;
+}
+
+unsigned SioxImage::hash() const
+{
+    unsigned result = width * height;
+
+    for (int i = 0; i < width * height; i++) {
+        result = 3 * result + (unsigned)pixdata[i] + (unsigned)((1 << 16) * cmdata[i]);
+    }
+
+    return result;
+}
+
+//########################################################################
+//#  S I O X
+//########################################################################
+
+namespace {
+
+/**
+ * Apply a function which updates each pixel depending on the value of its neighbours.
+ */
+template <typename F>
+void apply_adjacent(float *cm, int xres, int yres, F f)
+{
+    for (int y = 0; y < yres; y++) {
+        for (int x = 0; x < xres - 1; x++) {
+            int idx = y * xres + x;
+            f(cm[idx], cm[idx + 1]);
+        }
+    }
+    for (int y = 0; y < yres; y++) {
+        for (int x = xres - 1; x >= 1; x--) {
+            int idx = y * xres + x;
+            f(cm[idx], cm[idx - 1]);
+        }
+    }
+    for (int y = 0; y < yres - 1; y++) {
+        for (int x = 0; x < xres; x++) {
+            int idx = y * xres + x;
+            f(cm[idx], cm[idx + xres]);
+        }
+    }
+    for (int y = yres - 1; y >= 1; y--) {
+        for (int x = 0; x < xres; x++) {
+            int idx = y * xres + x;
+            f(cm[idx], cm[idx - xres]);
+        }
+    }
+}
+
+/**
+ * Applies the morphological dilate operator.
+ *
+ * Can be used to close small holes in the given confidence matrix.
+ */
+void dilate(float *cm, int xres, int yres)
+{
+    apply_adjacent(cm, xres, yres, [] (float &a, float b) {
+        if (b > a) {
+            a = b;
+        }
+    });
+}
+
+/**
+ * Applies the morphological erode operator.
+ */
+void erode(float *cm, int xres, int yres)
+{
+    apply_adjacent(cm, xres, yres, [] (float &a, float b) {
+        if (b < a) {
+            a = b;
+        }
+    });
+}
+
+/**
+ * Multiplies matrix with the given scalar.
+ */
+void premultiplyMatrix(float alpha, float *cm, int cmSize)
+{
+    for (int i = 0; i < cmSize; i++) {
+        cm[i] *= alpha;
+    }
+}
+
+/**
+ * Normalizes the matrix to values to [0..1].
+ */
+void normalizeMatrix(float *cm, int cmSize)
+{
+    float max = 0.0f;
+    for (int i = 0; i < cmSize; i++) {
+        if (cm[i] > max) {
+            max = cm[i];
+        }
+    }
+
+    if (max <= 0.0f || max == 1.0f) {
+        return;
+    }
+
+    float alpha = 1.0f / max;
+    premultiplyMatrix(alpha, cm, cmSize);
+}
+
+/**
+ * Blurs confidence matrix with a given symmetrically weighted kernel.
+ *
+ * In the standard case confidence matrix entries are between 0...1 and
+ * the weight factors sum up to 1.
+ */
+void smooth(float *cm, int xres, int yres, float f1, float f2, float f3)
+{
+    for (int y = 0; y < yres; y++) {
+        for (int x = 0; x < xres - 2; x++) {
+            int idx = y * xres + x;
+            cm[idx] = f1 * cm[idx] + f2 * cm[idx + 1] + f3 * cm[idx + 2];
+        }
+    }
+    for (int y = 0; y < yres; y++) {
+        for (int x = xres - 1; x >= 2; x--) {
+            int idx = y * xres + x;
+            cm[idx] = f3 * cm[idx - 2] + f2 * cm[idx - 1] + f1 * cm[idx];
+        }
+    }
+    for (int y = 0; y < yres - 2; y++) {
+        for (int x = 0; x < xres; x++) {
+            int idx = y * xres + x;
+            cm[idx] = f1 * cm[idx] + f2 * cm[((y + 1) * xres) + x] + f3 * cm[((y + 2) * xres) + x];
+        }
+    }
+    for (int y = yres - 1; y >= 2; y--) {
+        for (int x = 0; x < xres; x++) {
+            int idx = y * xres + x;
+            cm[idx] = f3 * cm[((y - 2) * xres) + x] + f2 * cm[((y - 1) * xres) + x] + f1 * cm[idx];
+        }
+    }
+}
+
+/**
+ * Squared Euclidean distance of p and q.
+ */
+float sqrEuclideanDist(float *p, int pSize, float *q)
+{
+    float sum = 0.0;
+    for (int i = 0; i < pSize; i++) {
+        float v = p[i] - q[i];
+        sum += v * v;
+    }
+    return sum;
+}
+
+} // namespace
+
+Siox::Siox(Async::Progress<double> &progress)
+    : progress(&progress)
+    , width(0)
+    , height(0)
+    , pixelCount(0)
+    , image(nullptr)
+    , cm(nullptr) {}
+
+void Siox::error(std::string const &msg)
+{
+     g_warning("Siox error: %s\n", msg.c_str());
+}
+
+void Siox::trace(std::string const &msg)
+{
+    g_message("Siox: %s\n", msg.c_str());
+}
+
+SioxImage Siox::extractForeground(SioxImage const &originalImage, uint32_t backgroundFillColor)
+{
+    trace("### Start");
+
+    init();
+
+    SioxImage workImage = originalImage;
+
+    // Fetch some info from the image.
+    width      = workImage.getWidth();
+    height     = workImage.getHeight();
+    pixelCount = width * height;
+    image      = workImage.getImageData();
+    cm         = workImage.getConfidenceData();
+
+    // Create labelField.
+    auto labelField_storage = std::make_unique<int[]>(pixelCount);
+    labelField = labelField_storage.get();
+
+    trace("### Creating signatures");
+
+    // Create color signatures.
+    std::vector<CieLab> knownBg, knownFg;
+    auto imageClab = std::make_unique<CieLab[]>(pixelCount);
+    for (int i = 0; i < pixelCount; i++) {
+        float conf = cm[i];
+        uint32_t pix = image[i];
+        CieLab lab = pix;
+        imageClab[i] = lab;
+        if (conf <= BACKGROUND_CONFIDENCE) {
+            knownBg.emplace_back(lab);
+        } else if (conf >= FOREGROUND_CONFIDENCE) {
+            knownFg.emplace_back(lab);
+        }
+    }
+
+    progress->report_or_throw(0.1);
+
+    trace("knownBg:" + std::to_string(knownBg.size()) + " knownFg:" + std::to_string(knownFg.size()));
+
+    std::vector<CieLab> bgSignature;
+    colorSignature(knownBg, bgSignature, 3);
+
+    progress->report_or_throw(0.2);
+
+    std::vector<CieLab> fgSignature;
+    colorSignature(knownFg, fgSignature, 3);
+
+    // trace("### bgSignature:" + std::to_string(bgSignature.size()));
+
+    if (bgSignature.empty()) {
+        // segmentation impossible
+        error("Signature size is < 1. Segmentation is impossible");
+        throw Exception();
+    }
+
+    progress->report_or_throw(0.3);
+
+    // classify using color signatures,
+    // classification cached in hashmap for drb and speedup purposes
+    trace("### Analyzing image");
+
+    std::unordered_map<uint32_t, bool> hs;
+
+    int progressResolution = pixelCount / 10;
+
+    for (int i = 0; i < pixelCount; i++) {
+        if (i % progressResolution == 0) {
+            progress->report_or_throw(0.3 + 0.6 * i / pixelCount);
+        }
+
+        if (cm[i] >= FOREGROUND_CONFIDENCE) {
+            cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
+        } else if (cm[i] <= BACKGROUND_CONFIDENCE) {
+            cm[i] = CERTAIN_BACKGROUND_CONFIDENCE;
+        } else { // somewhere in between
+            auto [it, inserted] = hs.emplace(image[i], false);
+            if (inserted) {
+                auto const &lab = imageClab[i];
+
+                float minBg = std::numeric_limits<float>::max();
+                for (auto const &s : bgSignature) {
+                    minBg = std::min(minBg, CieLab::diffSq(lab, s));
+                }
+
+                float minFg;
+                if (fgSignature.empty()) {
+                    minFg = clusterSize;
+                } else {
+                    minFg = std::numeric_limits<float>::max();
+                    for (auto const &s : fgSignature) {
+                        minFg = std::min(minFg, CieLab::diffSq(lab, s));
+                    }
+                }
+
+                it->second = minBg < minFg;
+            }
+
+            bool isBackground = it->second;
+            cm[i] = isBackground ? CERTAIN_BACKGROUND_CONFIDENCE : CERTAIN_FOREGROUND_CONFIDENCE;
+        }
+    }
+
+    hs.clear();
+    imageClab.reset();
+
+    trace("### postProcessing");
+
+    // Postprocessing
+    smooth(cm, width, height, 0.333f, 0.333f, 0.333f); // average
+    normalizeMatrix(cm, pixelCount);
+    erode(cm, width, height);
+    keepOnlyLargeComponents(UNKNOWN_REGION_CONFIDENCE, 1.0/*sizeFactorToKeep*/);
+
+    // for (int i = 0; i < 2/*smoothness*/; i++)
+    //     smooth(cm, width, height, 0.333f, 0.333f, 0.333f); // average
+
+    normalizeMatrix(cm, pixelCount);
+
+    for (int i = 0; i < pixelCount; i++) {
+        cm[i] = cm[i] >= UNKNOWN_REGION_CONFIDENCE
+              ? CERTAIN_FOREGROUND_CONFIDENCE
+              : CERTAIN_BACKGROUND_CONFIDENCE;
+    }
+
+    keepOnlyLargeComponents(UNKNOWN_REGION_CONFIDENCE, 1.5/*sizeFactorToKeep*/);
+    fillColorRegions();
+    dilate(cm, width, height);
+
+    progress->report_or_throw(1.0);
+
+    // We are done. Now clear everything but the background.
+    for (int i = 0; i < pixelCount; i++) {
+        if (cm[i] < FOREGROUND_CONFIDENCE) {
+            image[i] = backgroundFillColor;
+        }
+    }
+
+    trace("### Done");
+    return workImage;
+}
+
+void Siox::init()
+{
+    limits[0] = 0.64f;
+    limits[1] = 1.28f;
+    limits[2] = 2.56f;
+
+    float negLimits[3];
+    negLimits[0] = -limits[0];
+    negLimits[1] = -limits[1];
+    negLimits[2] = -limits[2];
+
+    clusterSize = sqrEuclideanDist(limits, 3, negLimits);
+}
+
+void Siox::colorSignatureStage1(CieLab *points,
+                                unsigned leftBase,
+                                unsigned rightBase,
+                                unsigned recursionDepth,
+                                unsigned *clusterCount,
+                                unsigned dims)
+{
+    unsigned currentDim = recursionDepth % dims;
+    CieLab point = points[leftBase];
+    float min = point(currentDim);
+    float max = min;
+
+    for (unsigned i = leftBase + 1; i < rightBase; i++) {
+        point = points[i];
+        float curval = point(currentDim);
+        if (curval < min) min = curval;
+        if (curval > max) max = curval;
+    }
+
+    // Do the Rubner-rule split (sounds like a dance)
+    if (max - min > limits[currentDim]) {
+        float pivotPoint = (min + max) / 2.0; // average
+        unsigned left  = leftBase;
+        unsigned right = rightBase - 1;
+
+        // partition points according to the dimension
+        while (true) {
+            while (true) {
+                point = points[left];
+                if (point(currentDim) > pivotPoint) {
+                    break;
+                }
+                left++;
+            }
+            while (true) {
+                point = points[right];
+                if (point(currentDim) <= pivotPoint) {
+                    break;
+                }
+                right--;
+            }
+
+            if (left > right) {
+                break;
+            }
+
+            point = points[left];
+            points[left] = points[right];
+            points[right] = point;
+
+            left++;
+            right--;
+        }
+
+        // Recurse and create sub-trees
+        colorSignatureStage1(points, leftBase, left, recursionDepth + 1, clusterCount, dims);
+        colorSignatureStage1(points, left, rightBase, recursionDepth + 1, clusterCount, dims);
+
+    } else {
+        // create a leaf
+        CieLab newpoint;
+
+        newpoint.C = rightBase - leftBase;
+
+        for (; leftBase < rightBase; leftBase++) {
+            newpoint.add(points[leftBase]);
+        }
+
+        // printf("clusters:%d\n", *clusters);
+
+        if (newpoint.C != 0) {
+            newpoint.mul(1.0f / newpoint.C);
+        }
+        points[*clusterCount] = newpoint;
+        (*clusterCount)++;
+    }
+}
+
+void Siox::colorSignatureStage2(CieLab  *points,
+                                unsigned leftBase,
+                                unsigned rightBase,
+                                unsigned recursionDepth,
+                                unsigned *clusterCount,
+                                float threshold,
+                                unsigned dims)
+{
+    unsigned currentDim = recursionDepth % dims;
+    CieLab point = points[leftBase];
+    float min = point(currentDim);
+    float max = min;
+
+    for (unsigned i = leftBase+ 1; i < rightBase; i++) {
+        point = points[i];
+        float curval = point(currentDim);
+        if (curval < min) min = curval;
+        if (curval > max) max = curval;
+    }
+
+    // Do the Rubner-rule split (sounds like a dance)
+    if (max - min > limits[currentDim]) {
+        float pivotPoint = (min + max) / 2.0; //average
+        unsigned left  = leftBase;
+        unsigned right = rightBase - 1;
+
+        // partition points according to the dimension
+        while (true) {
+            while (true) {
+                point = points[left];
+                if (point(currentDim) > pivotPoint) {
+                    break;
+                }
+                left++;
+            }
+            while (true) {
+                point = points[right];
+                if (point(currentDim) <= pivotPoint) {
+                    break;
+                }
+                right--;
+            }
+
+            if (left > right) {
+                break;
+            }
+
+            point = points[left];
+            points[left] = points[right];
+            points[right] = point;
+
+            left++;
+            right--;
+        }
+
+        //# Recurse and create sub-trees
+        colorSignatureStage2(points, leftBase, left, recursionDepth + 1, clusterCount, threshold, dims);
+        colorSignatureStage2(points, left, rightBase, recursionDepth + 1, clusterCount, threshold, dims);
+
+    } else {
+        //### Create a leaf
+        unsigned sum = 0;
+        for (unsigned i = leftBase; i < rightBase; i++) {
+            sum += points[i].C;
+        }
+
+        if (sum >= threshold) {
+            float scale = rightBase - leftBase;
+            CieLab newpoint;
+
+            for (; leftBase < rightBase; leftBase++) {
+                newpoint.add(points[leftBase]);
+            }
+
+            if (scale != 0.0) {
+                newpoint.mul(1.0 / scale);
+            }
+            points[*clusterCount] = newpoint;
+            (*clusterCount)++;
+        }
+    }
+}
+
+void Siox::colorSignature(std::vector<CieLab> const &inputVec,
+                          std::vector<CieLab> &result,
+                          unsigned dims)
+{
+    if (inputVec.empty()) { // no error. just don't do anything
+        return;
+    }
+
+    unsigned length = inputVec.size();
+    result = inputVec;
+
+    unsigned stage1length = 0;
+    colorSignatureStage1(result.data(), 0, length, 0, &stage1length, dims);
+
+    unsigned stage2length = 0;
+    colorSignatureStage2(result.data(), 0, stage1length, 0, &stage2length, length * 0.001, dims);
+
+    result.resize(stage2length);
+}
+
+void Siox::keepOnlyLargeComponents(float threshold, double sizeFactorToKeep)
+{
+    for (int idx = 0; idx < pixelCount; idx++) {
+        labelField[idx] = -1;
+    }
+
+    int curlabel  = 0;
+    int maxregion = 0;
+    int maxblob   = 0;
+
+    // slow but easy to understand:
+    std::vector<int> labelSizes;
+    for (int i = 0; i < pixelCount; i++) {
+        int regionCount = 0;
+        if (labelField[i] == -1 && cm[i] >= threshold) {
+            regionCount = depthFirstSearch(i, threshold, curlabel++);
+            labelSizes.emplace_back(regionCount);
+        }
+
+        if (regionCount > maxregion) {
+            maxregion = regionCount;
+            maxblob   = curlabel-1;
+        }
+    }
+
+    for (int i = 0; i < pixelCount; i++) {
+        if (labelField[i] != -1) {
+            // remove if the component is to small
+            if (labelSizes[labelField[i]] * sizeFactorToKeep < maxregion) {
+                cm[i] = CERTAIN_BACKGROUND_CONFIDENCE;
+            }
+
+            // add maxblob always to foreground
+            if (labelField[i] == maxblob) {
+                cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
+            }
+        }
+    }
+}
+
+int Siox::depthFirstSearch(int startPos, float threshold, int curLabel)
+{
+    // stores positions of labeled pixels, where the neighbours
+    // should still be checked for processing:
+
+    // trace("startPos:%d threshold:%f curLabel:%d",
+    //     startPos, threshold, curLabel);
+
+    std::vector<int> pixelsToVisit;
+    int componentSize = 0;
+
+    if (labelField[startPos] == -1 && cm[startPos] >= threshold) {
+        labelField[startPos] = curLabel;
+        componentSize++;
+        pixelsToVisit.emplace_back(startPos);
+    }
+
+    while (!pixelsToVisit.empty()) {
+        int pos = pixelsToVisit[pixelsToVisit.size() - 1];
+        pixelsToVisit.erase(pixelsToVisit.end() - 1);
+        int x = pos % width;
+        int y = pos / width;
+
+        // check all four neighbours
+        int left = pos - 1;
+        if (x - 1 >= 0 && labelField[left] == -1 && cm[left] >= threshold) {
+            labelField[left] = curLabel;
+            componentSize++;
+            pixelsToVisit.emplace_back(left);
+        }
+
+        int right = pos + 1;
+        if (x + 1 < width && labelField[right] == -1 && cm[right] >= threshold) {
+            labelField[right] = curLabel;
+            componentSize++;
+            pixelsToVisit.emplace_back(right);
+        }
+
+        int top = pos - width;
+        if (y - 1 >= 0 && labelField[top] == -1 && cm[top] >= threshold) {
+            labelField[top] = curLabel;
+            componentSize++;
+            pixelsToVisit.emplace_back(top);
+        }
+
+        int bottom = pos + width;
+        if (y + 1 < height && labelField[bottom] == -1 && cm[bottom] >= threshold) {
+            labelField[bottom] = curLabel;
+            componentSize++;
+            pixelsToVisit.emplace_back(bottom);
+        }
+    }
+
+    return componentSize;
+}
+
+void Siox::fillColorRegions()
+{
+    for (int idx = 0; idx < pixelCount; idx++) {
+        labelField[idx] = -1;
+    }
+
+    std::vector<int> pixelsToVisit;
+    for (int i = 0; i < pixelCount; i++) { // for all pixels
+        if (labelField[i] != -1 || cm[i] < UNKNOWN_REGION_CONFIDENCE) {
+            continue; // already visited or bg
+        }
+
+        uint32_t origColor = image[i];
+        int curLabel       = i+1;
+        labelField[i]      = curLabel;
+        cm[i]              = CERTAIN_FOREGROUND_CONFIDENCE;
+
+        // int componentSize = 1;
+        pixelsToVisit.emplace_back(i);
+        // depth first search to fill region
+        while (!pixelsToVisit.empty()) {
+            int pos = pixelsToVisit[pixelsToVisit.size() - 1];
+            pixelsToVisit.erase(pixelsToVisit.end() - 1);
+            int x = pos % width;
+            int y = pos / width;
+            // check all four neighbours
+            int left = pos - 1;
+            if (x - 1 >= 0 && labelField[left] == -1 && CieLab::diff(image[left], origColor) < 1.0) {
+                labelField[left] = curLabel;
+                cm[left] = CERTAIN_FOREGROUND_CONFIDENCE;
+                // ++componentSize;
+                pixelsToVisit.emplace_back(left);
+            }
+            int right = pos + 1;
+            if (x + 1 < width && labelField[right] == -1 && CieLab::diff(image[right], origColor) < 1.0) {
+                labelField[right] = curLabel;
+                cm[right] = CERTAIN_FOREGROUND_CONFIDENCE;
+                // ++componentSize;
+                pixelsToVisit.emplace_back(right);
+            }
+            int top = pos - width;
+            if (y - 1 >= 0 && labelField[top] == -1 && CieLab::diff(image[top], origColor) < 1.0) {
+                labelField[top] = curLabel;
+                cm[top] = CERTAIN_FOREGROUND_CONFIDENCE;
+                // ++componentSize;
+                pixelsToVisit.emplace_back(top);
+            }
+            int bottom = pos + width;
+            if (y + 1 < height && labelField[bottom] == -1 && CieLab::diff(image[bottom], origColor) < 1.0) {
+                labelField[bottom] = curLabel;
+                cm[bottom] = CERTAIN_FOREGROUND_CONFIDENCE;
+                // ++componentSize;
+                pixelsToVisit.emplace_back(bottom);
+            }
+        }
+    }
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/siox.h b/src/trace/siox.h
new file mode 100644
index 0000000..55d0ce4
--- /dev/null
+++ b/src/trace/siox.h
@@ -0,0 +1,219 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+#ifndef INKSCAPE_TRACE_SIOX_H
+#define INKSCAPE_TRACE_SIOX_H
+/*
+ *  Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping
+ *
+ *  Conversion to C++ for Inkscape by Bob Jamison
+ *
+ *  Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+
+/*
+ * Note by Bob Jamison:
+ * After translating the siox.org Java API to C++ and receiving an
+ * education into this wonderful code, I began again,
+ * and started this version using lessons learned. This version is
+ * an attempt to provide an dependency-free SIOX engine that anyone
+ * can use in their project with minimal effort.
+ *
+ * Many thanks to the fine people at siox.org.
+ */
+
+#include <string>
+#include <vector>
+#include <gdkmm/pixbuf.h>
+#include <glib.h>
+#include "cielab.h"
+
+namespace Inkscape {
+namespace Async { template <typename... T> class Progress; }
+namespace Trace {
+
+/**
+ * SioxImage is the input/output format of Siox.
+ * It pairs a 32-bit image with an equally-sized matrix of floats representing foreground confidence values.
+ */
+class SioxImage
+{
+public:
+    /**
+     * Create an image from a Gdk::Pixbuf.
+     * A copy of the pixbuf is set as the pixel data, while the confidence matrix is initialized to zero.
+     */
+    SioxImage(Glib::RefPtr<Gdk::Pixbuf> const &buf);
+
+    /**
+     * Create a Gdk::Pixbuf from this image.
+     */
+    Glib::RefPtr<Gdk::Pixbuf> getGdkPixbuf() const;
+
+    /**
+     * Return the image data buffer.
+     */
+    uint32_t *getImageData() { return pixdata.data(); }
+    uint32_t const *getImageData() const { return pixdata.data(); }
+
+    /**
+     * Set a confidence value at the x, y coordinates to the given value.
+     */
+    void setConfidence(int x, int y, float conf) { cmdata[offset(x, y)] = conf; }
+
+    /**
+     * Return the confidence data buffer.
+     */
+    float *getConfidenceData() { return cmdata.data(); }
+    float const *getConfidenceData() const { return cmdata.data(); }
+
+    /**
+     * Return the width of this image
+     */
+    int getWidth() const { return width; }
+
+    /**
+     * Return the height of this image
+     */
+    int getHeight() const { return height; }
+
+    /**
+     * Save this image as a simple color PPM
+     */
+    bool writePPM(char const *filename) const;
+
+    /**
+     * Return an extremely naive but fast hash of the image/confidence map contents.
+     */
+    unsigned hash() const;
+
+private:
+    int width;                     ///< Width of the image
+    int height;                    ///< Height of the image
+    std::vector<uint32_t> pixdata; ///< Pixel data
+    std::vector<float> cmdata;     ///< Confidence matrix data
+
+    /**
+     * Return the offset of a given pixel within both data arrays.
+     */
+    int constexpr offset(int x, int y) const { return width * y + x; }
+};
+
+class Siox
+{
+public:
+    /**
+     * Confidence corresponding to a certain foreground region (equals one).
+     */
+    static constexpr float CERTAIN_FOREGROUND_CONFIDENCE = 1.0f;
+
+    /**
+     * Confidence for a region likely being foreground.
+     */
+    static constexpr float FOREGROUND_CONFIDENCE = 0.8f;
+
+    /**
+     * Confidence for foreground or background type being equally likely.
+     */
+    static constexpr float UNKNOWN_REGION_CONFIDENCE = 0.5f;
+
+    /**
+     * Confidence for a region likely being background.
+     */
+    static constexpr float BACKGROUND_CONFIDENCE = 0.1f;
+
+    /**
+     * Confidence corresponding to a certain background reagion (equals zero).
+     */
+    static constexpr float CERTAIN_BACKGROUND_CONFIDENCE = 0.0f;
+
+    Siox(Async::Progress<double> &progress);
+
+    /**
+     * Extract the foreground of the original image, according to the values in the confidence matrix.
+     * If the operation fails or is aborted, an exception is thrown.
+     * \param backgroundFillColor Any ARGB color, such as 0xffffff (white) or 0x000000 (black).
+     * \throws Siox::Exception on error.
+     * \throws Async::CancelledException on cancellation.
+     */
+    SioxImage extractForeground(SioxImage const &originalImage, uint32_t backgroundFillColor);
+
+    class Exception {};
+
+private:
+    Async::Progress<double> *progress;
+
+    int width;       ///< Width of the image
+    int height;      ///< Height of the image
+    int pixelCount;  ///< Number of pixels in the image
+    uint32_t *image; ///< Working image data
+    float *cm;       ///< Working image confidence matrix
+
+    /**
+     * Markup for image editing
+     */
+    int *labelField;
+
+    /**
+     * Our signature limits
+     */
+    float limits[3];
+
+    /**
+     * Maximum distance of two lab values.
+     */
+    float clusterSize;
+
+    /**
+     * Initialize the Siox engine to its 'pristine' state.
+     * Performed at the beginning of extractForeground().
+     */
+    void init();
+
+    /**
+     * Error logging
+     */
+    void error(std::string const &str);
+
+    /**
+     * Trace logging
+     */
+    void trace(std::string const &str);
+
+    /**
+     * Stage 1 of the color signature work. 'dims' will be either 2 for grays, or 3 for colors.
+     */
+    void colorSignatureStage1(CieLab *points,
+                              unsigned leftBase,
+                              unsigned rightBase,
+                              unsigned recursionDepth,
+                              unsigned *clusters,
+                              unsigned dims);
+
+    /**
+     * Stage 2 of the color signature work
+     */
+    void colorSignatureStage2(CieLab *points,
+                              unsigned leftBase,
+                              unsigned rightBase,
+                              unsigned recursionDepth,
+                              unsigned *clusters,
+                              float    threshold,
+                              unsigned dims);
+
+    /**
+     * Main color signature method
+     */
+    void colorSignature(std::vector<CieLab> const &inputVec,
+                        std::vector<CieLab> &result,
+                        unsigned dims);
+
+    void keepOnlyLargeComponents(float threshold, double sizeFactorToKeep);
+
+    int depthFirstSearch(int startPos, float threshold, int curLabel);
+
+    void fillColorRegions();
+};
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_SIOX_H
diff --git a/src/trace/trace.cpp b/src/trace/trace.cpp
new file mode 100644
index 0000000..ed39825
--- /dev/null
+++ b/src/trace/trace.cpp
@@ -0,0 +1,538 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * A generic interface for plugging different
+ *  autotracers into Inkscape.
+ *
+ * Authors:
+ *   Bob Jamison <rjamison@earthlink.net>
+ *   Jon A. Cruz <jon@joncruz.org>
+ *   Abhishek Sharma
+ *   PBS <pbs3141@gmail.com>
+ *
+ * Copyright (C) 2004-2022 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <limits>
+#include <mutex>
+#include <algorithm>
+#include <cassert>
+#include <2geom/transforms.h>
+#include <glibmm/i18n.h>
+
+#include "trace.h"
+#include "siox.h"
+
+#include "desktop.h"
+#include "document.h"
+#include "document-undo.h"
+#include "helper/geom.h"
+#include "inkscape.h"
+#include "message-stack.h"
+#include "selection.h"
+#include "svg/svg.h"
+
+#include "async/async.h"
+#include "async/progress-splitter.h"
+#include "async/background-progress.h"
+
+#include "display/cairo-utils.h"
+#include "display/drawing.h"
+#include "display/drawing-context.h"
+
+#include "object/sp-item.h"
+#include "object/sp-image.h"
+#include "object/weakptr.h"
+
+#include "ui/icon-names.h"
+
+#include "xml/repr.h"
+#include "xml/attribute-record.h"
+
+namespace Inkscape {
+namespace Trace {
+namespace {
+
+/**
+ * Grab the image and siox items from the current selection, performing some validation.
+ * \pre SP_ACTIVE_DESKTOP must not be null.
+ */
+std::optional<std::pair<SPImage*, std::vector<SPItem*>>> getImageAndItems(bool sioxEnabled, bool notifications = true)
+{
+    auto desktop = SP_ACTIVE_DESKTOP;
+    auto msgStack = desktop->getMessageStack();
+    auto sel = desktop->getSelection();
+
+    if (sioxEnabled) {
+        auto selection = std::vector<SPItem*>(sel->items().begin(), sel->items().end());
+        std::sort(selection.begin(), selection.end(), sp_item_repr_compare_position_bool);
+
+        SPImage *img = nullptr;
+        std::vector<SPItem*> items;
+
+        for (auto item : selection) {
+            if (auto itemimg = cast<SPImage>(item)) {
+                if (img) { // we want only one
+                    if (notifications) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Select only one <b>image</b> to trace"));
+                    return {};
+                }
+                img = itemimg;
+            } else if (img) { // Items are processed back-to-front, so this means "above the image".
+                items.emplace_back(item);
+            }
+        }
+
+        if (!img || items.empty()) {
+            if (notifications) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Select one image and one or more shapes above it"));
+            return {};
+        }
+
+        return std::make_pair(img, std::move(items));
+    } else {
+        // SIOX not enabled. We want exactly one image selected.
+        auto item = sel->singleItem();
+        if (!item) {
+            if (notifications) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Select an <b>image</b> to trace")); // same as above
+            return {};
+        }
+
+        auto img = cast<SPImage>(item);
+        if (!img) {
+            if (notifications) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Select an <b>image</b> to trace"));
+            return {};
+        }
+
+        return {{ img, {} }};
+    }
+}
+
+/**
+ * Given an SPImage, get the transform from pixbuf coordinates to the document.
+ */
+Geom::Affine getImageTransform(SPImage const *img)
+{
+    double x = img->x.computed;
+    double y = img->y.computed;
+    double w = img->width.computed;
+    double h = img->height.computed;
+
+    int iw = img->pixbuf->width();
+    int ih = img->pixbuf->height();
+
+    double wscale = w / iw;
+    double hscale = h / ih;
+
+    return Geom::Scale(wscale, hscale) * Geom::Translate(x, y) * img->transform;
+}
+
+Geom::IntPoint dimensions(Inkscape::Pixbuf const &pixbuf)
+{
+    return { pixbuf.width(), pixbuf.height() };
+}
+
+bool confirm_image_size(TracingEngine const *engine, Geom::IntPoint const &dimensions)
+{
+    if (engine->check_image_size(dimensions)) {
+        char const *msg = _("Image looks too big. Process may take a while and it is"
+                            " wise to save your document before continuing."
+                            "\n\nContinue the procedure (without saving)?");
+        Gtk::MessageDialog dialog(msg, false, Gtk::MESSAGE_WARNING, Gtk::BUTTONS_OK_CANCEL, true);
+
+        if (dialog.run() != Gtk::RESPONSE_OK) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
+/**
+ * Given a list of SPItems, apply a transform and rasterize them to a surface of the specified dimensions.
+ */
+Cairo::RefPtr<Cairo::ImageSurface> rasterizeItems(std::vector<SPItem*> &items, Geom::Affine const &affine, Geom::IntPoint dimensions)
+{
+    auto surface = Cairo::ImageSurface::create(Cairo::FORMAT_ARGB32, dimensions.x(), dimensions.y());
+    auto dc = Inkscape::DrawingContext(surface->cobj(), {});
+    auto const inv = affine.inverse();
+
+    auto dkey = SPItem::display_key_new(1);
+    Inkscape::Drawing drawing;
+
+    for (auto item : items) {
+        auto ai = item->invoke_show(drawing, dkey, SP_ITEM_SHOW_DISPLAY);
+        drawing.setRoot(ai);
+        auto rect = Geom::IntRect({0, 0}, dimensions);
+        drawing.update(rect, inv);
+        drawing.render(dc, rect);
+        item->invoke_hide(dkey);
+    }
+
+    return surface;
+}
+
+class SioxImageCache
+{
+public:
+    static auto &get()
+    {
+        static SioxImageCache const instance;
+        return instance;
+    }
+
+    Glib::RefPtr<Gdk::Pixbuf> process(SioxImage const &sioximage, Async::Progress<double> &progress) const;
+
+private:
+    mutable std::mutex mutables;
+    mutable unsigned last_hash = 0;
+    mutable Glib::RefPtr<Gdk::Pixbuf> last_result;
+
+    SioxImageCache() = default;
+};
+
+Glib::RefPtr<Gdk::Pixbuf> SioxImageCache::process(SioxImage const &sioximage, Async::Progress<double> &progress) const
+{
+    auto hash = sioximage.hash();
+
+    auto g = std::lock_guard(mutables);
+
+    if (hash == last_hash) {
+        return last_result;
+    }
+
+    auto result = Siox(progress).extractForeground(sioximage, 0xffffff);
+
+    // result.writePPM("siox2.ppm");
+
+    last_hash = hash;
+    last_result = result.getGdkPixbuf();
+
+    return last_result;
+}
+
+Glib::RefPtr<Gdk::Pixbuf> sioxProcessImage(Glib::RefPtr<Gdk::Pixbuf> pixbuf, Cairo::RefPtr<Cairo::ImageSurface> siox_mask, Async::Progress<double> &progress)
+{
+    // Copy the pixbuf into the siox image.
+    auto sioximage = SioxImage(pixbuf);
+    int iwidth = sioximage.getWidth();
+    int iheight = sioximage.getHeight();
+
+    // Copy the mask into the siox image.
+    assert(iwidth == siox_mask->get_width());
+    assert(iheight == siox_mask->get_height());
+    for (int y = 0; y < iheight; y++) {
+        for (int x = 0; x < iwidth; x++) {
+            auto p = siox_mask->get_data() + y * siox_mask->get_stride() + 4 * x;
+            float a = p[3] / 255.0f;
+            float cm = Siox::CERTAIN_BACKGROUND_CONFIDENCE + (Siox::UNKNOWN_REGION_CONFIDENCE - Siox::CERTAIN_BACKGROUND_CONFIDENCE) * a;
+            sioximage.setConfidence(x, y, cm);
+        }
+    }
+
+    /*auto tmp = simage;
+    for (int i = 0; i < iwidth * iheight; i++) {
+        tmp.getImageData()[i] = 255 * tmp.getConfidenceData()[i];
+    }
+    tmp.writePPM("/tmp/x1.ppm");*/
+
+    // Process or retrieve from cache.
+    return SioxImageCache::get().process(sioximage, progress);
+}
+
+} // namespace
+
+namespace detail {
+
+struct TraceFutureCreate
+{
+    TraceFutureCreate() = delete;
+
+    static auto create(decltype(TraceFuture::channel) &&channel, decltype(TraceFuture::image_watcher) &&image_watcher)
+    {
+        TraceFuture result;
+        result.channel = std::move(channel);
+        result.image_watcher = std::move(image_watcher);
+        return result;
+    }
+};
+
+} // namespace detail
+
+// Todo: Consider rewriting using C++20 coroutines.
+class TraceTask
+{
+public:
+    TraceTask(std::unique_ptr<TracingEngine> engine, bool sioxEnabled, std::function<void(double)> onprogress, std::function<void()> onfinished)
+        : engine(std::move(engine))
+        , sioxEnabled(sioxEnabled)
+        , type(Type::Trace)
+        , onprogress(std::move(onprogress))
+        , onfinished_trace(std::move(onfinished)) {}
+
+    TraceTask(std::unique_ptr<TracingEngine> engine, bool sioxEnabled, std::function<void(Glib::RefPtr<Gdk::Pixbuf>)> onfinished)
+        : engine(std::move(engine))
+        , sioxEnabled(sioxEnabled)
+        , type(Type::Preview)
+        , onprogress([] (auto&&) {})
+        , onfinished_preview(std::move(onfinished)) {}
+
+    TraceTask(TraceTask const &) = delete;
+    TraceTask &operator=(TraceTask const &) = delete;
+
+    TraceFuture launch(std::unique_ptr<TraceTask> self);
+
+private:
+    std::unique_ptr<TracingEngine> engine;
+    bool sioxEnabled;
+
+    // Whether this is the full trace task, or just the preview task.
+    enum class Type
+    {
+        Trace,
+        Preview
+    };
+    Type type;
+
+    // Unsafe. Cannot call from worker thread since may perform actions in main thread. (This isn't Rust so we need a comment.)
+    std::function<void(double)> onprogress;
+    std::function<void()> onfinished_trace; // For trace task.
+    std::function<void(Glib::RefPtr<Gdk::Pixbuf>)> onfinished_preview; // For preview task.
+
+    // Unsafe. Cannot lock from worker thread since must be destroyed by main thread. (See above.)
+    std::weak_ptr<SPWeakPtr<SPImage>> image_watcher_weak;
+
+    std::shared_ptr<Inkscape::Pixbuf const> image_pixbuf;
+    Geom::Affine image_transform;
+    Cairo::RefPtr<Cairo::ImageSurface> siox_mask;
+    Async::Channel::Source channel;
+
+    TraceResult traceresult;
+
+    void do_async_work(std::unique_ptr<TraceTask> self);
+    void do_final_work(std::unique_ptr<TraceTask> self);
+};
+
+TraceFuture trace(std::unique_ptr<TracingEngine> engine, bool sioxEnabled, std::function<void(double)> onprogress, std::function<void()> onfinished)
+{
+    auto task = std::make_unique<TraceTask>(std::move(engine), sioxEnabled, std::move(onprogress), std::move(onfinished));
+    auto saved = task.get();
+    return saved->launch(std::move(task));
+}
+
+TraceFuture preview(std::unique_ptr<TracingEngine> engine, bool sioxEnabled, std::function<void(Glib::RefPtr<Gdk::Pixbuf>)> onfinished)
+{
+    auto task = std::make_unique<TraceTask>(std::move(engine), sioxEnabled, std::move(onfinished));
+    auto saved = task.get();
+    return saved->launch(std::move(task));
+}
+
+TraceFuture TraceTask::launch(std::unique_ptr<TraceTask> self)
+{
+    // Grab data and validate setup.
+
+    auto desktop = SP_ACTIVE_DESKTOP;
+    if (!desktop) {
+        g_warning("Trace: No active desktop\n");
+        return {};
+    }
+
+    auto msgStack = desktop->getMessageStack();
+
+    auto doc = SP_ACTIVE_DOCUMENT;
+    if (!doc) {
+        if (type == Type::Trace) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Trace: No active document"));
+        return {};
+    }
+    doc->ensureUpToDate();
+
+    auto imageanditems = getImageAndItems(sioxEnabled, type == Type::Trace);
+    if (!imageanditems) {
+        return {};
+    }
+
+    // Copy into coroutine frame.
+
+    auto image = imageanditems->first;
+
+    image_pixbuf = image->pixbuf; // Note: image->pixbuf is immutable, so can be shared thread-safely.
+    if (!image_pixbuf) {
+        if (type == Type::Trace) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Trace: Image has no bitmap data"));
+        return {};
+    }
+
+    if (type == Type::Trace && !confirm_image_size(engine.get(), dimensions(*image_pixbuf))) {
+        // Image is too big and user decided to cancel.
+        return {};
+    }
+
+    image_transform = getImageTransform(image);
+
+    if (sioxEnabled) {
+        siox_mask = rasterizeItems(imageanditems->second, image_transform, dimensions(*image_pixbuf));
+    }
+
+    if (type == Type::Trace) msgStack->flash(Inkscape::NORMAL_MESSAGE, _("Trace: Starting trace..."));
+
+    // Open channel and launch background task.
+
+    auto [src, dst] = Async::Channel::create();
+    auto image_watcher = std::make_shared<SPWeakPtr<SPImage>>(image);
+
+    channel = std::move(src);
+    image_watcher_weak = image_watcher;
+
+    Async::fire_and_forget([this, self = std::move(self)] () mutable {
+        do_async_work(std::move(self));
+    });
+
+    return detail::TraceFutureCreate::create(std::move(dst), std::move(image_watcher));
+}
+
+void TraceTask::do_async_work(std::unique_ptr<TraceTask> self)
+{
+    if (!channel) {
+        // Cancelled while suspended.
+        return;
+    }
+
+    try {
+        auto progress = Async::BackgroundProgress(channel, onprogress);
+        auto throttled = Async::ProgressTimeThrottler(progress, std::chrono::milliseconds(10));
+
+        // Get progress subobjects for siox and trace sub-tasks.
+        std::optional<Async::SubProgress<double>> sub_siox, sub_trace;
+
+        Async::ProgressSplitter(throttled)
+            .add_if(sub_siox, 0.1, sioxEnabled)
+            .add_if(sub_trace, 0.9, type == Type::Trace);
+
+        // Convert the pixbuf to a GdkPixbuf, which due to immutability requires making a copy first.
+        auto copy = Pixbuf(*image_pixbuf);
+        auto gdkpixbuf = Glib::wrap(copy.getPixbufRaw(), true);
+
+        // If SIOX has been enabled, run SIOX processing.
+        if (sioxEnabled) {
+            gdkpixbuf = sioxProcessImage(gdkpixbuf, siox_mask, *sub_siox);
+            siox_mask.clear();
+            sub_siox->report_or_throw(1.0);
+        }
+
+        // If in preview mode, compute and return the preview and exit now.
+        if (type == Type::Preview) {
+            gdkpixbuf = engine->preview(gdkpixbuf);
+            channel.run(std::bind(onfinished_preview, std::move(gdkpixbuf)));
+            return;
+        }
+
+        // Actually perform the tracing.
+        traceresult = engine->trace(gdkpixbuf, *sub_trace);
+
+        gdkpixbuf.reset();
+
+        progress.report_or_throw(1.0);
+
+        // Return to the original thread for the remainder of the processing.
+        channel.run([this, self = std::move(self)] () mutable {
+            do_final_work(std::move(self));
+        });
+
+    } catch (Async::CancelledException const &) {
+
+        // no need to emit signals if manually aborted
+
+    } catch (...) {
+
+        g_warning("TraceTask::do_async_work: tracing aborted due to exception");
+        if (type == Type::Trace) {
+            channel.run(onfinished_trace);
+        } else {
+            channel.run(std::bind(onfinished_preview, Glib::RefPtr<Gdk::Pixbuf>()));
+        }
+
+    }
+}
+
+void TraceTask::do_final_work(std::unique_ptr<TraceTask> self)
+{
+    assert(type == Type::Trace);
+    assert(channel);
+
+    auto doc = SP_ACTIVE_DOCUMENT;
+    auto desktop = SP_ACTIVE_DESKTOP;
+    auto image_watcher = image_watcher_weak.lock();
+
+    if (!doc || !desktop || !image_watcher || traceresult.empty()) {
+        onfinished_trace();
+        return;
+    }
+
+    auto image = image_watcher->get();
+    if (!image) {
+        // Image was deleted.
+        onfinished_trace();
+        return;
+    }
+
+    auto msgStack = desktop->getMessageStack();
+    auto selection = desktop->getSelection();
+
+    // Get pointers to the <image> and its parent.
+    // XML Tree being used directly here while it shouldn't be
+    Inkscape::XML::Node *imgRepr = image->getRepr();
+    Inkscape::XML::Node *par     = imgRepr->parent();
+
+    // Update the image transform - it may have changed from its initial value.
+    image_transform = getImageTransform(image);
+
+    // OK. Now let's start making new nodes.
+    Inkscape::XML::Document *xml_doc = desktop->doc()->getReprDoc();
+    Inkscape::XML::Node *groupRepr = nullptr;
+
+    // If more than one path, make a <g>roup of <path>s.
+    int nrPaths = traceresult.size();
+    if (nrPaths > 1) {
+        groupRepr = xml_doc->createElement("svg:g");
+        par->addChild(groupRepr, imgRepr);
+    }
+
+    long totalNodeCount = 0;
+
+    for (auto const &result : traceresult) {
+        totalNodeCount += count_pathvector_nodes(result.path);
+
+        Inkscape::XML::Node *pathRepr = xml_doc->createElement("svg:path");
+        pathRepr->setAttributeOrRemoveIfEmpty("style", result.style);
+        pathRepr->setAttributeOrRemoveIfEmpty("d", sp_svg_write_path(result.path * image_transform));
+
+        if (nrPaths > 1) {
+            groupRepr->addChild(pathRepr, nullptr);
+        } else {
+            par->addChild(pathRepr, imgRepr);
+        }
+
+        if (nrPaths == 1) {
+            selection->clear();
+            selection->add(pathRepr);
+        }
+
+        Inkscape::GC::release(pathRepr);
+    }
+
+    // If we have a group, then focus on it.
+    if (nrPaths > 1) {
+        selection->clear();
+        selection->add(groupRepr);
+        Inkscape::GC::release(groupRepr);
+    }
+
+    // Inform the document, so we can undo.
+    DocumentUndo::done(doc, _("Trace bitmap"), INKSCAPE_ICON("bitmap-trace"));
+
+    char *msg = g_strdup_printf(_("Trace: Done. %ld nodes created"), totalNodeCount);
+    msgStack->flash(Inkscape::NORMAL_MESSAGE, msg);
+    g_free(msg);
+
+    onfinished_trace();
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/trace.h b/src/trace/trace.h
new file mode 100644
index 0000000..0bb39d6
--- /dev/null
+++ b/src/trace/trace.h
@@ -0,0 +1,103 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Authors:
+ *   Bob Jamison <rjamison@titan.com>
+ *
+ * Copyright (C) 2004-2006 Bob Jamison
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_H
+#define INKSCAPE_TRACE_H
+
+#include <vector>
+#include <utility>
+#include <cstring>
+#include <2geom/pathvector.h>
+#include <gdkmm/pixbuf.h>
+#include "async/channel.h"
+#include "object/weakptr.h"
+#include "object/sp-image.h"
+
+namespace Inkscape {
+namespace Async { template <typename... T> class Progress; }
+namespace Trace {
+
+struct TraceResultItem
+{
+    TraceResultItem(std::string style_, Geom::PathVector path_)
+        : style(std::move(style_))
+        , path(std::move(path_)) {}
+
+    std::string style;
+    Geom::PathVector path;
+};
+
+using TraceResult = std::vector<TraceResultItem>;
+
+/**
+ * A generic interface for plugging different autotracers into Inkscape.
+ */
+class TracingEngine
+{
+public:
+    TracingEngine() = default;
+    virtual ~TracingEngine() = default;
+
+    /**
+     * This is the working method of this interface, and all implementing classes. Take a
+     * GdkPixbuf, trace it, and return a style attribute and the path data that is
+     * compatible with the d="" attribute of an SVG <path> element.
+     *
+     * This function will be called off-main-thread, so is required to be thread-safe.
+     * The lack of const however indicates that it is not required to be re-entrant.
+     */
+    virtual TraceResult trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress) = 0;
+
+    /**
+     * Generate a quick preview without any actual tracing. Like trace(), this must be thread-safe.
+     */
+    virtual Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) = 0;
+
+    /**
+     * Return true if the user should be checked with before tracing because the image is too big.
+     */
+    virtual bool check_image_size(Geom::IntPoint const &size) const { return false; }
+};
+
+namespace detail { struct TraceFutureCreate; }
+
+class TraceFuture
+{
+public:
+    void cancel() { channel.close(); image_watcher.reset(); }
+    explicit operator bool() const { return (bool)channel; }
+
+private:
+    Async::Channel::Dest channel;
+    std::shared_ptr<SPWeakPtr<SPImage>> image_watcher;
+    friend class detail::TraceFutureCreate;
+};
+
+/**
+ * Launch an asynchronous trace operation taking as input \a engine and \a sioxEnabled.
+ * If this returns null, the task failed to launch and no further action will be taken.
+ * Otherwise, a background task is launched which will call \a onprogress some number of times
+ * followed by \a onfinished exactly once. Both callbacks are invoked from the GTK main loop.
+ */
+TraceFuture trace(std::unique_ptr<TracingEngine> engine,
+                  bool sioxEnabled,
+                  std::function<void(double)> onprogress,
+                  std::function<void()> onfinished);
+
+/**
+ * Similar to \a trace(), but computes the preview and passes it to \a onfinished when done.
+ */
+TraceFuture preview(std::unique_ptr<TracingEngine> engine,
+                    bool sioxEnabled,
+                    std::function<void(Glib::RefPtr<Gdk::Pixbuf>)> onfinished);
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_H