summaryrefslogtreecommitdiffstats
path: root/src/trace
diff options
context:
space:
mode:
Diffstat (limited to 'src/trace')
-rw-r--r--src/trace/CMakeLists.txt31
-rw-r--r--src/trace/README18
-rw-r--r--src/trace/autotrace/inkscape-autotrace.cpp223
-rw-r--r--src/trace/autotrace/inkscape-autotrace.h101
-rw-r--r--src/trace/depixelize/inkscape-depixelize.cpp137
-rw-r--r--src/trace/depixelize/inkscape-depixelize.h100
-rw-r--r--src/trace/filterset.cpp422
-rw-r--r--src/trace/filterset.h57
-rw-r--r--src/trace/imagemap-gdk.cpp223
-rw-r--r--src/trace/imagemap-gdk.h51
-rw-r--r--src/trace/imagemap.cpp459
-rw-r--r--src/trace/imagemap.h393
-rw-r--r--src/trace/pool.h119
-rw-r--r--src/trace/potrace/bitmap.h117
-rw-r--r--src/trace/potrace/inkscape-potrace.cpp661
-rw-r--r--src/trace/potrace/inkscape-potrace.h141
-rw-r--r--src/trace/quantize.cpp597
-rw-r--r--src/trace/quantize.h23
-rw-r--r--src/trace/siox.cpp1733
-rw-r--r--src/trace/siox.h654
-rw-r--r--src/trace/trace.cpp613
-rw-r--r--src/trace/trace.h258
22 files changed, 7131 insertions, 0 deletions
diff --git a/src/trace/CMakeLists.txt b/src/trace/CMakeLists.txt
new file mode 100644
index 0000000..45b3125
--- /dev/null
+++ b/src/trace/CMakeLists.txt
@@ -0,0 +1,31 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+set(trace_SRC
+ 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
+ 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..156a7b3
--- /dev/null
+++ b/src/trace/autotrace/inkscape-autotrace.cpp
@@ -0,0 +1,223 @@
+// 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 "inkscape-autotrace.h"
+
+extern "C" {
+#include "3rdparty/autotrace/autotrace.h"
+#include "3rdparty/autotrace/output.h"
+#include "3rdparty/autotrace/spline.h"
+}
+
+#include <glibmm/i18n.h>
+#include <gtkmm/main.h>
+#include <iomanip>
+
+#include "trace/filterset.h"
+#include "trace/imagemap-gdk.h"
+#include "trace/quantize.h"
+
+#include "desktop.h"
+#include "message-stack.h"
+#include <inkscape.h>
+
+#include "object/sp-path.h"
+
+#include <svg/path-string.h>
+
+using Glib::ustring;
+
+static void updateGui()
+{
+ //## Allow the GUI to update
+ Gtk::Main::iteration(false); // at least once, non-blocking
+ while (Gtk::Main::events_pending())
+ Gtk::Main::iteration();
+}
+
+namespace Inkscape {
+
+namespace Trace {
+
+namespace Autotrace {
+
+static guchar* to_3channels(GdkPixbuf* input) {
+ int imgsize = gdk_pixbuf_get_height(input) * gdk_pixbuf_get_width(input);
+ guchar *out = (guchar*)malloc(3 * imgsize);
+ int x=0;
+ guchar* pix = gdk_pixbuf_get_pixels (input);
+ int rs = gdk_pixbuf_get_rowstride (input);
+ for(int row=0;row<gdk_pixbuf_get_height(input);row++) {
+ for (int col=0;col<gdk_pixbuf_get_width(input);col++) {
+ guchar alpha = *(pix + row * rs + col * 4 + 3);
+ guchar white = 255 - alpha;
+ for(int chan=0;chan<3;chan++) {
+ guchar *pnew = (pix + row * rs + col * 3 + chan);
+ guchar *pold = (pix + row * rs + col * 4 + chan);
+ out[x++] = (guchar)(((int)(*pold) * (int)alpha / 256) + white);
+ }
+ }
+ }
+ return out;
+}
+
+
+/**
+ *
+ */
+AutotraceTracingEngine::AutotraceTracingEngine()
+ : keepGoing(1)
+ , traceType(TRACE_OUTLINE)
+ , invert(false)
+{
+ /* get default parameters */
+ opts = at_fitting_opts_new();
+ opts->background_color = at_color_new(255,255,255);
+ autotrace_init();
+}
+
+AutotraceTracingEngine::~AutotraceTracingEngine() { at_fitting_opts_free(opts); }
+
+
+
+// TODO
+Glib::RefPtr<Gdk::Pixbuf> AutotraceTracingEngine::preview(Glib::RefPtr<Gdk::Pixbuf> thePixbuf) {
+ //auto x = thePixbuf.copy();
+ guchar *pb = to_3channels(thePixbuf->gobj());
+ return Gdk::Pixbuf::create_from_data(pb, thePixbuf->get_colorspace(), false, 8, thePixbuf->get_width(), thePixbuf->get_height(), (thePixbuf->get_width()*3));
+
+}
+
+int test_cancel (void* keepGoing){return !(* ((int*)keepGoing));}
+
+/**
+ * This is the working method of this interface, and all
+ * implementing classes. Take a GdkPixbuf, trace it, and
+ * return the path data that is compatible with the d="" attribute
+ * of an SVG <path> element.
+ */
+std::vector<TracingEngineResult> AutotraceTracingEngine::trace(Glib::RefPtr<Gdk::Pixbuf> pixbuf)
+{
+ GdkPixbuf *pb1 = pixbuf->gobj();
+ guchar *pb = to_3channels(pb1);
+
+ at_bitmap *bitmap =
+// at_bitmap_new(gdk_pixbuf_get_width(pb), gdk_pixbuf_get_height(pb), gdk_pixbuf_get_n_channels(pb));
+// bitmap->bitmap = gdk_pixbuf_get_pixels(pb);
+ at_bitmap_new(gdk_pixbuf_get_width(pb1), gdk_pixbuf_get_height(pb1), 3);
+ bitmap->bitmap = pb;
+
+ at_splines_type *splines = at_splines_new_full(bitmap, opts, NULL, NULL, NULL, NULL, test_cancel, &keepGoing);
+ // at_output_write_func wfunc = at_output_get_handler_by_suffix("svg");
+ at_spline_writer *wfunc = at_output_get_handler_by_suffix("svg");
+
+
+ int height = splines->height;
+ // const at_splines_type spline = *splines;
+ at_spline_list_array_type spline = *splines;
+
+ unsigned this_list;
+ at_spline_list_type list;
+ at_color last_color = { 0, 0, 0 };
+
+ std::stringstream theStyle;
+ std::stringstream thePath;
+ char color[10];
+ int nNodes = 0;
+
+ std::vector<TracingEngineResult> res;
+
+ // at_splines_write(wfunc, stdout, "", NULL, splines, NULL, NULL);
+
+ for (this_list = 0; this_list < SPLINE_LIST_ARRAY_LENGTH(spline); this_list++) {
+ unsigned this_spline;
+ at_spline_type first;
+
+ list = SPLINE_LIST_ARRAY_ELT(spline, this_list);
+ first = SPLINE_LIST_ELT(list, 0);
+
+ if (this_list == 0 || !at_color_equal(&list.color, &last_color)) {
+ if (this_list > 0) {
+ if (!(spline.centerline || list.open)) {
+ thePath << "z";
+ nNodes++;
+ }
+ TracingEngineResult ter(theStyle.str(), thePath.str(), nNodes);
+ res.push_back(ter);
+ theStyle.clear();
+ thePath.clear();
+ nNodes = 0;
+ }
+ sprintf(color, "#%02x%02x%02x;", list.color.r, list.color.g, list.color.b);
+
+ theStyle << ((spline.centerline || list.open) ? "stroke:" : "fill:") << color
+ << ((spline.centerline || list.open) ? "fill:" : "stroke:") << "none";
+ }
+ thePath << "M" << START_POINT(first).x << " " << height - START_POINT(first).y;
+ nNodes++;
+ for (this_spline = 0; this_spline < SPLINE_LIST_LENGTH(list); this_spline++) {
+ at_spline_type s = SPLINE_LIST_ELT(list, this_spline);
+
+ if (SPLINE_DEGREE(s) == AT_LINEARTYPE) {
+ thePath << "L" << END_POINT(s).x << " " << height - END_POINT(s).y;
+ nNodes++;
+ }
+ else {
+ thePath << "C" << CONTROL1(s).x << " " << height - CONTROL1(s).y << " " << CONTROL2(s).x << " "
+ << height - CONTROL2(s).y << " " << END_POINT(s).x << " " << height - END_POINT(s).y;
+ nNodes++;
+ }
+ last_color = list.color;
+ }
+ }
+ if (!(spline.centerline || list.open))
+ thePath << "z";
+ nNodes++;
+ if (SPLINE_LIST_ARRAY_LENGTH(spline) > 0) {
+ TracingEngineResult ter(theStyle.str(), thePath.str(), nNodes);
+ res.push_back(ter);
+ theStyle.clear();
+ thePath.clear();
+ nNodes = 0;
+ }
+
+ return res;
+}
+
+
+/**
+ * Abort the thread that is executing getPathDataFromPixbuf()
+ */
+void AutotraceTracingEngine::abort()
+{
+ // g_message("PotraceTracingEngine::abort()\n");
+ keepGoing = 0;
+}
+
+
+
+} // 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..f12eb35
--- /dev/null
+++ b/src/trace/autotrace/inkscape-autotrace.h
@@ -0,0 +1,101 @@
+// 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_AUTOTRACE_H__
+#define __INKSCAPE_AUTOTRACE_H__
+
+#include "3rdparty/autotrace/autotrace.h"
+#include <trace/trace.h>
+
+namespace Inkscape {
+
+namespace Trace {
+
+namespace Autotrace {
+enum TraceType { TRACE_CENTERLINE, TRACE_OUTLINE };
+
+class AutotraceTracingEngine : public TracingEngine {
+
+ public:
+ /**
+ *
+ */
+ AutotraceTracingEngine();
+
+ /**
+ *
+ */
+ ~AutotraceTracingEngine() override;
+
+
+ /**
+ * Sets/gets parameters
+ */
+ // TODO
+
+ /**
+ * This is the working method of this implementing class, and all
+ * implementing classes. Take a GdkPixbuf, trace it, and
+ * return the path data that is compatible with the d="" attribute
+ * of an SVG <path> element.
+ */
+ std::vector<TracingEngineResult> trace(Glib::RefPtr<Gdk::Pixbuf> pixbuf) override;
+
+ /**
+ * Abort the thread that is executing getPathDataFromPixbuf()
+ */
+ void abort() override;
+
+ /**
+ *
+ */
+ Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> pixbuf);
+
+ /**
+ *
+ */
+ int keepGoing;
+
+ //private:
+ // autotrace_param_t *autotraceParams;
+ TraceType traceType;
+ at_fitting_opts_type *opts;
+
+ //## do I invert at the end?
+ bool invert;
+
+}; // class AutotraceTracingEngine
+
+
+
+} // namespace Autotrace
+} // namespace Trace
+} // namespace Inkscape
+
+
+#endif //__INKSCAPE_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/depixelize/inkscape-depixelize.cpp b/src/trace/depixelize/inkscape-depixelize.cpp
new file mode 100644
index 0000000..23897f8
--- /dev/null
+++ b/src/trace/depixelize/inkscape-depixelize.cpp
@@ -0,0 +1,137 @@
+// 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 "inkscape-depixelize.h"
+
+#include <glibmm/i18n.h>
+#include <gtkmm/main.h>
+#include <gtkmm.h>
+#include <iomanip>
+
+#include "desktop.h"
+#include "message-stack.h"
+#include "helper/geom.h"
+#include "object/sp-path.h"
+
+#include <svg/path-string.h>
+#include <svg/svg.h>
+#include <svg/svg-color.h>
+#include "svg/css-ostringstream.h"
+
+using Glib::ustring;
+
+
+
+namespace Inkscape {
+
+namespace Trace {
+
+namespace Depixelize {
+
+
+/**
+ *
+ */
+DepixelizeTracingEngine::DepixelizeTracingEngine()
+ : keepGoing(1)
+ , traceType(TRACE_VORONOI)
+{
+ params = new ::Tracer::Kopf2011::Options();
+}
+
+
+
+DepixelizeTracingEngine::DepixelizeTracingEngine(TraceType traceType, double curves, int islands, int sparsePixels,
+ double sparseMultiplier)
+ : keepGoing(1)
+ , traceType(traceType)
+{
+ params = new ::Tracer::Kopf2011::Options();
+ params->curvesMultiplier = curves;
+ params->islandsWeight = islands;
+ params->sparsePixelsRadius = sparsePixels;
+ params->sparsePixelsMultiplier = sparseMultiplier;
+ params->nthreads = Inkscape::Preferences::get()->getIntLimited("/options/threading/numthreads",
+#ifdef HAVE_OPENMP
+ omp_get_num_procs(),
+#else
+ 1,
+#endif // HAVE_OPENMP
+ 1, 256);
+}
+
+DepixelizeTracingEngine::~DepixelizeTracingEngine() { delete params; }
+
+std::vector<TracingEngineResult> DepixelizeTracingEngine::trace(Glib::RefPtr<Gdk::Pixbuf> pixbuf)
+{
+ if (pixbuf->get_width() > 256 || pixbuf->get_height() > 256) {
+ char *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;
+// TODO
+ }
+
+ ::Tracer::Splines splines;
+
+ if (traceType == TRACE_VORONOI)
+ splines = ::Tracer::Kopf2011::to_voronoi(pixbuf, *params);
+ else
+ splines = ::Tracer::Kopf2011::to_splines(pixbuf, *params);
+
+ std::vector<TracingEngineResult> res;
+
+ for (::Tracer::Splines::const_iterator it = splines.begin(), end = splines.end(); it != end; ++it) {
+ gchar 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 << float(it->rgba[3]) / 255.;
+ gchar* style = g_strdup_printf("fill:%s;fill-opacity:%s;", b, osalpha.str().c_str());
+ printf("%s\n", style);
+ TracingEngineResult r(style, sp_svg_write_path(it->pathVector), count_pathvector_nodes(it->pathVector));
+ res.push_back(r);
+ g_free(style);
+ }
+ return res;
+}
+
+void DepixelizeTracingEngine::abort() { keepGoing = 0; }
+
+Glib::RefPtr<Gdk::Pixbuf> DepixelizeTracingEngine::preview(Glib::RefPtr<Gdk::Pixbuf> pixbuf) { return pixbuf; }
+
+
+} // 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..228e724
--- /dev/null
+++ b/src/trace/depixelize/inkscape-depixelize.h
@@ -0,0 +1,100 @@
+// 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_DEPIXTRACE_H__
+#define __INKSCAPE_DEPIXTRACE_H__
+
+#include <trace/trace.h>
+#include "3rdparty/libdepixelize/kopftracer2011.h"
+
+struct GrayMap_def;
+typedef GrayMap_def GrayMap;
+
+namespace Inkscape {
+
+namespace Trace {
+
+namespace Depixelize {
+
+enum TraceType
+ {
+ TRACE_VORONOI,
+ TRACE_BSPLINES
+ };
+
+
+class DepixelizeTracingEngine : public TracingEngine
+{
+
+ public:
+
+ /**
+ *
+ */
+ DepixelizeTracingEngine();
+ DepixelizeTracingEngine(TraceType traceType, double curves, int islands, int sparsePixels, double sparseMultiplier);
+
+ /**
+ *
+ */
+ ~DepixelizeTracingEngine() override;
+
+ /**
+ * This is the working method of this implementing class, and all
+ * implementing classes. Take a GdkPixbuf, trace it, and
+ * return the path data that is compatible with the d="" attribute
+ * of an SVG <path> element.
+ */
+ std::vector<TracingEngineResult> trace(
+ Glib::RefPtr<Gdk::Pixbuf> pixbuf) override;
+
+ /**
+ * Abort the thread that is executing getPathDataFromPixbuf()
+ */
+ void abort() override;
+
+ /**
+ *
+ */
+ Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> pixbuf);
+
+ /**
+ *
+ */
+ int keepGoing;
+
+ ::Tracer::Kopf2011::Options *params;
+ TraceType traceType;
+
+};//class PotraceTracingEngine
+
+
+
+} // namespace Depixelize
+} // namespace Trace
+} // namespace Inkscape
+
+
+#endif //__INKSCAPE_TRACE_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..fae6d66
--- /dev/null
+++ b/src/trace/filterset.cpp
@@ -0,0 +1,422 @@
+// 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 <cstdlib>
+
+#include "imagemap-gdk.h"
+#include "filterset.h"
+#include "quantize.h"
+
+/*#########################################################################
+### 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 *me)
+{
+ int width = me->width;
+ int height = me->height;
+ int firstX = 2;
+ int lastX = width-3;
+ int firstY = 2;
+ int lastY = height-3;
+
+ GrayMap *newGm = GrayMapCreate(width, height);
+ if (!newGm)
+ return nullptr;
+
+ 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(newGm, x, y, me->getPixel(me, 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(me, j, i) * weight;
+ }
+ }
+ sum /= 159;
+ newGm->setPixel(newGm, x, y, sum);
+ }
+ }
+
+ return newGm;
+}
+
+
+
+
+
+/**
+ *
+ */
+RgbMap *rgbMapGaussian(RgbMap *me)
+{
+ int width = me->width;
+ int height = me->height;
+ int firstX = 2;
+ int lastX = width-3;
+ int firstY = 2;
+ int lastY = height-3;
+
+ RgbMap *newGm = RgbMapCreate(width, height);
+ if (!newGm)
+ return nullptr;
+
+ 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->setPixelRGB(newGm, x, y, me->getPixel(me, 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(me, j, i);
+ sumR += weight * (int)rgb.r;
+ sumG += weight * (int)rgb.g;
+ sumB += weight * (int)rgb.b;
+ }
+ }
+ RGB rout;
+ rout.r = ( sumR / 159 ) & 0xff;
+ rout.g = ( sumG / 159 ) & 0xff;
+ rout.b = ( sumB / 159 ) & 0xff;
+ newGm->setPixelRGB(newGm, 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
+ */
+static GrayMap *grayMapSobel(GrayMap *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;
+
+ GrayMap *newGm = GrayMapCreate(width, height);
+ if (!newGm)
+ return nullptr;
+
+ for (int y = 0 ; y<height ; y++)
+ {
+ for (int x = 0 ; x<width ; x++)
+ {
+ unsigned long sum = 0;
+ /* image boundaries */
+ if (x<firstX || x>lastX || y<firstY || y>lastY)
+ {
+ sum = 0;
+ }
+ 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(gm, 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(gm, j, i) *
+ sobelY[sobelIndex++];
+ }
+ }
+ /*### GET VALUE ### */
+ sum = abs(sumX) + abs(sumY);
+
+ if (sum > 765)
+ sum = 765;
+
+#if 0
+ /*### GET ORIENTATION (slow, pedantic way) ### */
+ double orient = 0.0;
+ if (sumX==0)
+ {
+ if (sumY==0)
+ orient = 0.0;
+ else if (sumY<0)
+ {
+ sumY = -sumY;
+ orient = 90.0;
+ }
+ else
+ orient = 90.0;
+ }
+ else
+ {
+ orient = 57.295779515 * atan2( ((double)sumY),((double)sumX) );
+ if (orient < 0.0)
+ orient += 180.0;
+ }
+
+ /*### GET EDGE DIRECTION ### */
+ int edgeDirection = 0;
+ if (orient < 22.5)
+ edgeDirection = 0;
+ else if (orient < 67.5)
+ edgeDirection = 45;
+ else if (orient < 112.5)
+ edgeDirection = 90;
+ else if (orient < 157.5)
+ edgeDirection = 135;
+#else
+ /*### 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;*/
+ long slope = (sumY << 10)/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;
+ }
+
+#endif
+ /* 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(gm, x-1, y);
+ rightPixel = gm->getPixel(gm, x+1, y);
+ }
+ else if (edgeDirection == 45)
+ {
+ leftPixel = gm->getPixel(gm, x-1, y+1);
+ rightPixel = gm->getPixel(gm, x+1, y-1);
+ }
+ else if (edgeDirection == 90)
+ {
+ leftPixel = gm->getPixel(gm, x, y-1);
+ rightPixel = gm->getPixel(gm, x, y+1);
+ }
+ else /*135 */
+ {
+ leftPixel = gm->getPixel(gm, x-1, y-1);
+ rightPixel = gm->getPixel(gm, x+1, y+1);
+ }
+
+ /*### Compare current value to adjacent pixels ### */
+ /*### if less that either, suppress it ### */
+ if (sum < leftPixel || sum < rightPixel)
+ sum = 0;
+ else
+ {
+ unsigned long highThreshold =
+ (unsigned long)(dHighThreshold * 765.0);
+ unsigned long lowThreshold =
+ (unsigned long)(dLowThreshold * 765.0);
+ if (sum >= highThreshold)
+ sum = 765; /* EDGE. 3*255 this needs to be settable */
+ else if (sum < lowThreshold)
+ sum = 0; /* NONEDGE */
+ else
+ {
+ if ( gm->getPixel(gm, x-1, y-1)> highThreshold ||
+ gm->getPixel(gm, x , y-1)> highThreshold ||
+ gm->getPixel(gm, x+1, y-1)> highThreshold ||
+ gm->getPixel(gm, x-1, y )> highThreshold ||
+ gm->getPixel(gm, x+1, y )> highThreshold ||
+ gm->getPixel(gm, x-1, y+1)> highThreshold ||
+ gm->getPixel(gm, x , y+1)> highThreshold ||
+ gm->getPixel(gm, x+1, y+1)> highThreshold)
+ sum = 765; /* EDGE fix me too */
+ else
+ sum = 0; /* NONEDGE */
+ }
+ }
+
+
+ }/* else */
+ if (sum==0) /* invert light & dark */
+ sum = 765;
+ else
+ sum = 0;
+ newGm->setPixel(newGm, x, y, sum);
+ }/* for (x) */
+ }/* for (y) */
+
+ return newGm;
+}
+
+
+
+
+
+/**
+ *
+ */
+GrayMap *
+grayMapCanny(GrayMap *gm, double lowThreshold, double highThreshold)
+{
+ if (!gm)
+ return nullptr;
+
+ GrayMap *cannyGm = grayMapSobel(gm, lowThreshold, highThreshold);
+ if (!cannyGm)
+ return nullptr;
+ /*cannyGm->writePPM(cannyGm, "canny.ppm");*/
+
+ return cannyGm;
+}
+
+
+
+/*#########################################################################
+### Q U A N T I Z A T I O N
+#########################################################################*/
+
+/**
+ * Experimental. Work on this later
+ */
+GrayMap *quantizeBand(RgbMap *rgbMap, int nrColors)
+{
+
+ RgbMap *gaussMap = rgbMapGaussian(rgbMap);
+ //gaussMap->writePPM(gaussMap, "rgbgauss.ppm");
+
+ IndexedMap *qMap = rgbMapQuantize(gaussMap, nrColors);
+ //qMap->writePPM(qMap, "rgbquant.ppm");
+ gaussMap->destroy(gaussMap);
+
+ GrayMap *gm = GrayMapCreate(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++)
+ {
+ RGB rgb = qMap->getPixelValue(qMap, x, y);
+ int sum = rgb.r + rgb.g + rgb.b;
+ if (sum & 1)
+ sum = 765;
+ else
+ sum = 0;
+ // printf("%d %d %d : %d\n", rgb.r, rgb.g, rgb.b, index);
+ gm->setPixel(gm, x, y, sum);
+ }
+ }
+
+ qMap->destroy(qMap);
+
+ return gm;
+}
+
+
+/*#########################################################################
+### E N D O F F I L E
+#########################################################################*/
+
+
+
+
+
+
+
+
+
+
diff --git a/src/trace/filterset.h b/src/trace/filterset.h
new file mode 100644
index 0000000..d8da650
--- /dev/null
+++ b/src/trace/filterset.h
@@ -0,0 +1,57 @@
+// 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 __FILTERSET_H__
+#define __FILTERSET_H__
+
+#include "imagemap.h"
+
+#include <gdk-pixbuf/gdk-pixbuf.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * Apply gaussian blur to an GrayMap
+ */
+GrayMap *grayMapGaussian(GrayMap *gmap);
+
+/**
+ * Apply gaussian bluf to an RgbMap
+ */
+RgbMap *rgbMapGaussian(RgbMap *rgbmap);
+
+/**
+ *
+ */
+GrayMap *grayMapCanny(GrayMap *gmap,
+ double lowThreshold, double highThreshold);
+
+/**
+ *
+ */
+GrayMap *quantizeBand(RgbMap *rgbmap, int nrColors);
+
+
+
+#ifdef __cplusplus
+}
+#endif
+
+
+#endif /* __FILTERSET_H__ */
+
+/*#########################################################################
+### E N D O F F I L E
+#########################################################################*/
diff --git a/src/trace/imagemap-gdk.cpp b/src/trace/imagemap-gdk.cpp
new file mode 100644
index 0000000..d1c1c4e
--- /dev/null
+++ b/src/trace/imagemap-gdk.cpp
@@ -0,0 +1,223 @@
+// 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 <cstdlib>
+
+#include "imagemap-gdk.h"
+
+
+/*#########################################################################
+## G R A Y M A P
+#########################################################################*/
+
+GrayMap *gdkPixbufToGrayMap(GdkPixbuf *buf)
+{
+ if (!buf)
+ return nullptr;
+
+ int width = gdk_pixbuf_get_width(buf);
+ int height = gdk_pixbuf_get_height(buf);
+ guchar *pixdata = gdk_pixbuf_get_pixels(buf);
+ int rowstride = gdk_pixbuf_get_rowstride(buf);
+ int n_channels = gdk_pixbuf_get_n_channels(buf);
+
+ GrayMap *grayMap = GrayMapCreate(width, height);
+ if (!grayMap)
+ return nullptr;
+
+ //### Fill in the odd cells with RGB values
+ int x,y;
+ int row = 0;
+ for (y=0 ; y<height ; y++)
+ {
+ guchar *p = pixdata + row;
+ for (x=0 ; x<width ; x++)
+ {
+ int alpha = (int)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;
+ grayMap->setPixel(grayMap, x, y, bright);
+ p += n_channels;
+ }
+ row += rowstride;
+ }
+
+ return grayMap;
+}
+
+GdkPixbuf *grayMapToGdkPixbuf(GrayMap *grayMap)
+{
+ if (!grayMap)
+ return nullptr;
+
+ guchar *pixdata = (guchar *)
+ malloc(sizeof(guchar) * grayMap->width * grayMap->height * 3);
+ if (!pixdata)
+ return nullptr;
+
+ int n_channels = 3;
+ int rowstride = grayMap->width * 3;
+
+ GdkPixbuf *buf = gdk_pixbuf_new_from_data(pixdata, GDK_COLORSPACE_RGB,
+ 0, 8, grayMap->width, grayMap->height,
+ rowstride, (GdkPixbufDestroyNotify)g_free, nullptr);
+
+ //### Fill in the odd cells with RGB values
+ int x,y;
+ int row = 0;
+ for (y=0 ; y<grayMap->height ; y++)
+ {
+ guchar *p = pixdata + row;
+ for (x=0 ; x<grayMap->width ; x++)
+ {
+ unsigned long pix = grayMap->getPixel(grayMap, x, y) / 3;
+ p[0] = p[1] = p[2] = (guchar)(pix & 0xff);
+ p += n_channels;
+ }
+ row += rowstride;
+ }
+
+ return buf;
+}
+
+
+
+/*#########################################################################
+## P A C K E D P I X E L M A P
+#########################################################################*/
+
+PackedPixelMap *gdkPixbufToPackedPixelMap(GdkPixbuf *buf)
+{
+ if (!buf)
+ return nullptr;
+
+ int width = gdk_pixbuf_get_width(buf);
+ int height = gdk_pixbuf_get_height(buf);
+ guchar *pixdata = gdk_pixbuf_get_pixels(buf);
+ int rowstride = gdk_pixbuf_get_rowstride(buf);
+ int n_channels = gdk_pixbuf_get_n_channels(buf);
+
+ PackedPixelMap *ppMap = PackedPixelMapCreate(width, height);
+ if (!ppMap)
+ return nullptr;
+
+ //### Fill in the cells with RGB values
+ int x,y;
+ int row = 0;
+ for (y=0 ; y<height ; y++)
+ {
+ guchar *p = pixdata + row;
+ for (x=0 ; x<width ; x++)
+ {
+ int alpha = (int)p[3];
+ int white = 255 - alpha;
+ int r = (int)p[0]; r = r * alpha / 256 + white;
+ int g = (int)p[1]; g = g * alpha / 256 + white;
+ int b = (int)p[2]; b = b * alpha / 256 + white;
+
+ ppMap->setPixel(ppMap, x, y, r, g, b);
+ p += n_channels;
+ }
+ row += rowstride;
+ }
+
+ return ppMap;
+}
+
+
+/*#########################################################################
+## R G B M A P
+#########################################################################*/
+
+RgbMap *gdkPixbufToRgbMap(GdkPixbuf *buf)
+{
+ if (!buf)
+ return nullptr;
+
+ int width = gdk_pixbuf_get_width(buf);
+ int height = gdk_pixbuf_get_height(buf);
+ guchar *pixdata = gdk_pixbuf_get_pixels(buf);
+ int rowstride = gdk_pixbuf_get_rowstride(buf);
+ int n_channels = gdk_pixbuf_get_n_channels(buf);
+
+ RgbMap *rgbMap = RgbMapCreate(width, height);
+ if (!rgbMap)
+ return nullptr;
+
+ //### Fill in the cells with RGB values
+ int x,y;
+ int row = 0;
+ for (y=0 ; y<height ; y++)
+ {
+ guchar *p = pixdata + row;
+ for (x=0 ; x<width ; x++)
+ {
+ int alpha = (int)p[3];
+ int white = 255 - alpha;
+ int r = (int)p[0]; r = r * alpha / 256 + white;
+ int g = (int)p[1]; g = g * alpha / 256 + white;
+ int b = (int)p[2]; b = b * alpha / 256 + white;
+
+ rgbMap->setPixel(rgbMap, x, y, r, g, b);
+ p += n_channels;
+ }
+ row += rowstride;
+ }
+
+ return rgbMap;
+}
+
+
+
+/*#########################################################################
+## I N D E X E D M A P
+#########################################################################*/
+
+
+GdkPixbuf *indexedMapToGdkPixbuf(IndexedMap *iMap)
+{
+ if (!iMap)
+ return nullptr;
+
+ guchar *pixdata = (guchar *)
+ malloc(sizeof(guchar) * iMap->width * iMap->height * 3);
+ if (!pixdata)
+ return nullptr;
+
+ int n_channels = 3;
+ int rowstride = iMap->width * 3;
+
+ GdkPixbuf *buf = gdk_pixbuf_new_from_data(pixdata, GDK_COLORSPACE_RGB,
+ 0, 8, iMap->width, iMap->height,
+ rowstride, (GdkPixbufDestroyNotify)g_free, nullptr);
+
+ //### Fill in the cells with RGB values
+ int x,y;
+ int row = 0;
+ for (y=0 ; y<iMap->height ; y++)
+ {
+ guchar *p = pixdata + row;
+ for (x=0 ; x<iMap->width ; x++)
+ {
+ RGB rgb = iMap->getPixelValue(iMap, x, y);
+ p[0] = rgb.r & 0xff;
+ p[1] = rgb.g & 0xff;
+ p[2] = rgb.b & 0xff;
+ p += n_channels;
+ }
+ row += rowstride;
+ }
+
+ return buf;
+}
+
+/*#########################################################################
+## E N D O F F I L E
+#########################################################################*/
diff --git a/src/trace/imagemap-gdk.h b/src/trace/imagemap-gdk.h
new file mode 100644
index 0000000..d0eaf23
--- /dev/null
+++ b/src/trace/imagemap-gdk.h
@@ -0,0 +1,51 @@
+// 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 __GRAYMAP_GDK_H__
+#define __GRAYMAP_GDK_H__
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+
+#ifndef FALSE
+#define FALSE 0
+#endif
+
+#include "imagemap.h"
+
+#include <gdk-pixbuf/gdk-pixbuf.h>
+
+/*#########################################################################
+### I M A G E M A P --- GDK
+#########################################################################*/
+
+
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+GrayMap *gdkPixbufToGrayMap(GdkPixbuf *buf);
+GdkPixbuf *grayMapToGdkPixbuf(GrayMap *grayMap);
+PackedPixelMap *gdkPixbufToPackedPixelMap(GdkPixbuf *buf);
+RgbMap *gdkPixbufToRgbMap(GdkPixbuf *buf);
+GdkPixbuf *indexedMapToGdkPixbuf(IndexedMap *iMap);
+
+
+#ifdef __cplusplus
+}
+#endif
+
+
+#endif /* __GRAYMAP_GDK_H__ */
+
+/*#########################################################################
+### E N D O F F I L E
+#########################################################################*/
diff --git a/src/trace/imagemap.cpp b/src/trace/imagemap.cpp
new file mode 100644
index 0000000..796575a
--- /dev/null
+++ b/src/trace/imagemap.cpp
@@ -0,0 +1,459 @@
+// 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 <cstdlib>
+
+#include "imagemap.h"
+
+#include "io/sys.h"
+
+/*#########################################################################
+### G R A Y M A P
+#########################################################################*/
+
+
+static void gSetPixel(GrayMap *me, int x, int y, unsigned long val)
+{
+ if (val>765)
+ val = 765;
+ unsigned long *pix = me->rows[y] + x;
+ *pix = val;
+}
+
+static unsigned long gGetPixel(GrayMap *me, int x, int y)
+{
+ unsigned long *pix = me->rows[y] + x;
+ return *pix;
+}
+
+
+static int gWritePPM(GrayMap *me, char *fileName)
+{
+ if (!fileName)
+ return FALSE;
+
+ FILE *f = fopen(fileName, "wb");
+ if (!f)
+ return FALSE;
+
+ fprintf(f, "P6 %d %d 255\n", me->width, me->height);
+
+ for (int y=0 ; y<me->height; y++)
+ {
+ for (int x=0 ; x<me->width ; x++)
+ {
+ unsigned long pix = me->getPixel(me, x, y) / 3;
+ unsigned char pixb = (unsigned char) (pix & 0xff);
+ fputc(pixb, f);
+ fputc(pixb, f);
+ fputc(pixb, f);
+ }
+ }
+ fclose(f);
+ return TRUE;
+}
+
+
+static void gDestroy(GrayMap *me)
+{
+ if (me->pixels)
+ free(me->pixels);
+ if (me->rows)
+ free(me->rows);
+ free(me);
+}
+
+GrayMap *GrayMapCreate(int width, int height)
+{
+
+ GrayMap *me = (GrayMap *)malloc(sizeof(GrayMap));
+ if (!me)
+ return nullptr;
+
+ /** methods **/
+ me->setPixel = gSetPixel;
+ me->getPixel = gGetPixel;
+ me->writePPM = gWritePPM;
+ me->destroy = gDestroy;
+
+ /** fields **/
+ me->width = width;
+ me->height = height;
+ me->pixels = (unsigned long *)
+ malloc(sizeof(unsigned long) * width * height);
+ if (!me->pixels)
+ {
+ free(me);
+ return nullptr;
+ }
+ me->rows = (unsigned long **)
+ malloc(sizeof(unsigned long *) * height);
+ if (!me->rows)
+ {
+ free(me->pixels);
+ free(me);
+ return nullptr;
+ }
+
+ unsigned long *row = me->pixels;
+ for (int i=0 ; i<height ; i++)
+ {
+ me->rows[i] = row;
+ row += width;
+ }
+
+ return me;
+}
+
+
+
+
+
+/*#########################################################################
+### P A C K E D P I X E L M A P
+#########################################################################*/
+
+
+
+static void ppSetPixel(PackedPixelMap *me, int x, int y, int r, int g, int b)
+{
+ unsigned long *pix = me->rows[y] + x;
+ *pix = (((unsigned long)r)<<16 & 0xff0000L) |
+ (((unsigned long)g)<< 8 & 0x00ff00L) |
+ (((unsigned long)b) & 0x0000ffL);
+}
+
+static void ppSetPixelLong(PackedPixelMap *me, int x, int y, unsigned long rgb)
+{
+ unsigned long *pix = me->rows[y] + x;
+ *pix = rgb;
+}
+
+static unsigned long ppGetPixel(PackedPixelMap *me, int x, int y)
+{
+ unsigned long *pix = me->rows[y] + x;
+ return *pix;
+}
+
+
+
+static int ppWritePPM(PackedPixelMap *me, char *fileName)
+{
+ if (!fileName)
+ return FALSE;
+
+ FILE *f = fopen(fileName, "wb");
+ if (!f)
+ return FALSE;
+
+ fprintf(f, "P6 %d %d 255\n", me->width, me->height);
+
+ for (int y=0 ; y<me->height; y++)
+ {
+ for (int x=0 ; x<me->width ; x++)
+ {
+ unsigned long rgb = me->getPixel(me, x, y);
+ unsigned char r = (unsigned char) ((rgb>>16) & 0xff);
+ unsigned char g = (unsigned char) ((rgb>> 8) & 0xff);
+ unsigned char b = (unsigned char) ((rgb ) & 0xff);
+ fputc(r, f);
+ fputc(g, f);
+ fputc(b, f);
+ }
+ }
+ fclose(f);
+ return TRUE;
+}
+
+
+static void ppDestroy(PackedPixelMap *me)
+{
+ if (me->pixels)
+ free(me->pixels);
+ if (me->rows)
+ free(me->rows);
+ free(me);
+}
+
+
+
+PackedPixelMap *PackedPixelMapCreate(int width, int height)
+{
+
+ PackedPixelMap *me = (PackedPixelMap *)malloc(sizeof(PackedPixelMap));
+ if (!me)
+ return nullptr;
+
+ /** methods **/
+ me->setPixel = ppSetPixel;
+ me->setPixelLong = ppSetPixelLong;
+ me->getPixel = ppGetPixel;
+ me->writePPM = ppWritePPM;
+ me->destroy = ppDestroy;
+
+
+ /** fields **/
+ me->width = width;
+ me->height = height;
+ me->pixels = (unsigned long *) malloc(sizeof(unsigned long) * width * height);
+ if (!me->pixels){
+ free(me);
+ return nullptr;
+ }
+ me->rows = (unsigned long **) malloc(sizeof(unsigned long *) * height);
+ if (!me->rows){
+ free(me->pixels); //allocated as me->pixels is not NULL here: see previous check
+ free(me);
+ return nullptr;
+ }
+
+ unsigned long *row = me->pixels;
+ for (int i=0 ; i<height ; i++)
+ {
+ me->rows[i] = row;
+ row += width;
+ }
+
+ return me;
+}
+
+
+
+/*#########################################################################
+### R G B M A P
+#########################################################################*/
+
+
+
+static void rSetPixel(RgbMap *me, int x, int y, int r, int g, int b)
+{
+ RGB *pix = me->rows[y] + x;
+ pix->r = r;
+ pix->g = g;
+ pix->b = b;
+}
+
+static void rSetPixelRGB(RgbMap *me, int x, int y, RGB rgb)
+{
+ RGB *pix = me->rows[y] + x;
+ *pix = rgb;
+}
+
+static RGB rGetPixel(RgbMap *me, int x, int y)
+{
+ RGB *pix = me->rows[y] + x;
+ return *pix;
+}
+
+
+
+static int rWritePPM(RgbMap *me, char *fileName)
+{
+ if (!fileName)
+ return FALSE;
+
+ FILE *f = fopen(fileName, "wb");
+ if (!f)
+ return FALSE;
+
+ fprintf(f, "P6 %d %d 255\n", me->width, me->height);
+
+ for (int y=0 ; y<me->height; y++)
+ {
+ for (int x=0 ; x<me->width ; x++)
+ {
+ RGB rgb = me->getPixel(me, x, y);
+ fputc(rgb.r, f);
+ fputc(rgb.g, f);
+ fputc(rgb.b, f);
+ }
+ }
+ fclose(f);
+ return TRUE;
+}
+
+
+static void rDestroy(RgbMap *me)
+{
+ if (me->pixels){
+ free(me->pixels);
+ }
+ if (me->rows){
+ free(me->rows);
+ }
+ free(me);
+}
+
+
+
+RgbMap *RgbMapCreate(int width, int height)
+{
+
+ RgbMap *me = (RgbMap *)malloc(sizeof(RgbMap));
+ if (!me){
+ return nullptr;
+ }
+
+ /** methods **/
+ me->setPixel = rSetPixel;
+ me->setPixelRGB = rSetPixelRGB;
+ me->getPixel = rGetPixel;
+ me->writePPM = rWritePPM;
+ me->destroy = rDestroy;
+
+
+ /** fields **/
+ me->width = width;
+ me->height = height;
+ me->pixels = (RGB *) malloc(sizeof(RGB) * width * height);
+ if (!me->pixels){
+ free(me);
+ return nullptr;
+ }
+ me->rows = (RGB **) malloc(sizeof(RGB *) * height);
+ if (!me->rows){
+ free(me->pixels); //allocated as me->pixels is not NULL here: see previous check
+ free(me);
+ return nullptr;
+ }
+
+ RGB *row = me->pixels;
+ for (int i=0 ; i<height ; i++){
+ me->rows[i] = row;
+ row += width;
+ }
+
+ return me;
+}
+
+
+
+
+/*#########################################################################
+### I N D E X E D M A P
+#########################################################################*/
+
+
+
+static void iSetPixel(IndexedMap *me, int x, int y, unsigned int index)
+{
+ unsigned int *pix = me->rows[y] + x;
+ *pix = index;
+}
+
+
+static unsigned int iGetPixel(IndexedMap *me, int x, int y)
+{
+ unsigned int *pix = me->rows[y] + x;
+ return *pix;
+}
+
+static RGB iGetPixelValue(IndexedMap *me, int x, int y)
+{
+ unsigned int *pix = me->rows[y] + x;
+ RGB rgb = me->clut[((*pix)&0xff)];
+ return rgb;
+}
+
+
+
+static int iWritePPM(IndexedMap *me, char *fileName)
+{
+ if (!fileName)
+ return FALSE;
+
+ FILE *f = fopen(fileName, "wb");
+ if (!f)
+ return FALSE;
+
+ fprintf(f, "P6 %d %d 255\n", me->width, me->height);
+
+ for (int y=0 ; y<me->height; y++)
+ {
+ for (int x=0 ; x<me->width ; x++)
+ {
+ RGB rgb = me->getPixelValue(me, x, y);
+ fputc(rgb.r, f);
+ fputc(rgb.g, f);
+ fputc(rgb.b, f);
+ }
+ }
+ fclose(f);
+ return TRUE;
+}
+
+
+static void iDestroy(IndexedMap *me)
+{
+ if (me->pixels){
+ free(me->pixels);
+ }
+ if (me->rows){
+ free(me->rows);
+ }
+ free(me);
+}
+
+
+
+IndexedMap *IndexedMapCreate(int width, int height)
+{
+
+ IndexedMap *me = (IndexedMap *)malloc(sizeof(IndexedMap));
+ if (!me)
+ return nullptr;
+
+ /** methods **/
+ me->setPixel = iSetPixel;
+ me->getPixel = iGetPixel;
+ me->getPixelValue = iGetPixelValue;
+ me->writePPM = iWritePPM;
+ me->destroy = iDestroy;
+
+
+ /** fields **/
+ me->width = width;
+ me->height = height;
+ me->pixels = (unsigned int *) malloc(sizeof(unsigned int) * width * height);
+ if (!me->pixels){
+ free(me);
+ return nullptr;
+ }
+ me->rows = (unsigned int **) malloc(sizeof(unsigned int *) * height);
+ if (!me->rows){
+ free(me->pixels); //allocated as me->pixels is not NULL here: see previous check
+ free(me);
+ return nullptr;
+ }
+
+ unsigned int *row = me->pixels;
+ for (int i=0 ; i<height ; i++){
+ me->rows[i] = row;
+ row += width;
+ }
+
+ me->nrColors = 0;
+
+ RGB rgb;
+ rgb.r = rgb.g = rgb.b = 0;
+ for (auto & i : me->clut){
+ i = rgb;
+ }
+
+ return me;
+}
+
+
+
+
+
+
+/*#########################################################################
+### E N D O F F I L E
+#########################################################################*/
diff --git a/src/trace/imagemap.h b/src/trace/imagemap.h
new file mode 100644
index 0000000..9da057a
--- /dev/null
+++ b/src/trace/imagemap.h
@@ -0,0 +1,393 @@
+// 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 __IMAGEMAP_H__
+#define __IMAGEMAP_H__
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+
+#ifndef FALSE
+#define FALSE 0
+#endif
+
+
+/*#########################################################################
+### G R A Y M A P
+#########################################################################*/
+
+
+typedef struct GrayMap_def GrayMap;
+
+#define GRAYMAP_BLACK 0
+#define GRAYMAP_WHITE 765
+
+/**
+ *
+ */
+struct GrayMap_def
+{
+
+ /*#################
+ ### METHODS
+ #################*/
+
+ /**
+ *
+ */
+ void (*setPixel)(GrayMap *me, int x, int y, unsigned long val);
+
+ /**
+ *
+ */
+ unsigned long (*getPixel)(GrayMap *me, int x, int y);
+
+ /**
+ *
+ */
+ int (*writePPM)(GrayMap *me, char *fileName);
+
+
+
+ /**
+ *
+ */
+ void (*destroy)(GrayMap *me);
+
+
+
+ /*#################
+ ### FIELDS
+ #################*/
+
+ /**
+ *
+ */
+ int width;
+
+ /**
+ *
+ */
+ int height;
+
+ /**
+ * The pixel array
+ */
+ unsigned long *pixels;
+
+ /**
+ * Pointer to the beginning of each row
+ */
+ unsigned long **rows;
+
+};
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+GrayMap *GrayMapCreate(int width, int height);
+
+#ifdef __cplusplus
+}
+#endif
+
+
+
+
+/*#########################################################################
+### P A C K E D P I X E L M A P
+#########################################################################*/
+
+
+typedef struct PackedPixelMap_def PackedPixelMap;
+
+/**
+ *
+ */
+struct PackedPixelMap_def
+{
+
+ /*#################
+ ### METHODS
+ #################*/
+
+ /**
+ *
+ */
+ void (*setPixel)(PackedPixelMap *me, int x, int y, int r, int g, int b);
+
+
+ /**
+ *
+ */
+ void (*setPixelLong)(PackedPixelMap *me, int x, int y, unsigned long rgb);
+
+
+ /**
+ *
+ */
+ unsigned long (*getPixel)(PackedPixelMap *me, int x, int y);
+
+
+ /**
+ *
+ */
+ int (*writePPM)(PackedPixelMap *me, char *fileName);
+
+
+
+ /**
+ *
+ */
+ void (*destroy)(PackedPixelMap *me);
+
+
+
+ /*#################
+ ### FIELDS
+ #################*/
+
+ /**
+ *
+ */
+ int width;
+
+ /**
+ *
+ */
+ int height;
+
+ /**
+ * The allocated array of pixels
+ */
+ unsigned long *pixels;
+
+ /**
+ * Pointers to the beginning of each row of pixels
+ */
+ unsigned long **rows;
+
+
+};
+
+
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+PackedPixelMap *PackedPixelMapCreate(int width, int height);
+
+#ifdef __cplusplus
+}
+#endif
+
+
+
+/*#########################################################################
+### R G B M A P
+#########################################################################*/
+
+struct RGB
+{
+ unsigned char r;
+ unsigned char g;
+ unsigned char b;
+};
+
+
+
+typedef struct RgbMap_def RgbMap;
+
+/**
+ *
+ */
+struct RgbMap_def
+{
+
+ /*#################
+ ### METHODS
+ #################*/
+
+ /**
+ *
+ */
+ void (*setPixel)(RgbMap *me, int x, int y, int r, int g, int b);
+
+
+ /**
+ *
+ */
+ void (*setPixelRGB)(RgbMap *me, int x, int y, RGB rgb);
+
+ /**
+ *
+ */
+ RGB (*getPixel)(RgbMap *me, int x, int y);
+
+ /**
+ *
+ */
+ int (*writePPM)(RgbMap *me, char *fileName);
+
+
+
+ /**
+ *
+ */
+ void (*destroy)(RgbMap *me);
+
+
+
+ /*#################
+ ### FIELDS
+ #################*/
+
+ /**
+ *
+ */
+ int width;
+
+ /**
+ *
+ */
+ int height;
+
+ /**
+ * The allocated array of pixels
+ */
+ RGB *pixels;
+
+ /**
+ * Pointers to the beginning of each row of pixels
+ */
+ RGB **rows;
+
+};
+
+
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+RgbMap *RgbMapCreate(int width, int height);
+
+#ifdef __cplusplus
+}
+#endif
+
+
+
+
+/*#########################################################################
+### I N D E X E D M A P
+#########################################################################*/
+
+
+typedef struct IndexedMap_def IndexedMap;
+
+/**
+ *
+ */
+struct IndexedMap_def
+{
+
+ /*#################
+ ### METHODS
+ #################*/
+
+ /**
+ *
+ */
+ void (*setPixel)(IndexedMap *me, int x, int y, unsigned int index);
+
+
+ /**
+ *
+ */
+ unsigned int (*getPixel)(IndexedMap *me, int x, int y);
+
+ /**
+ *
+ */
+ RGB (*getPixelValue)(IndexedMap *me, int x, int y);
+
+ /**
+ *
+ */
+ int (*writePPM)(IndexedMap *me, char *fileName);
+
+
+
+ /**
+ *
+ */
+ void (*destroy)(IndexedMap *me);
+
+
+
+ /*#################
+ ### FIELDS
+ #################*/
+
+ /**
+ *
+ */
+ int width;
+
+ /**
+ *
+ */
+ int height;
+
+ /**
+ * The allocated array of pixels
+ */
+ unsigned int *pixels;
+
+ /**
+ * Pointers to the beginning of each row of pixels
+ */
+ unsigned int **rows;
+
+ /**
+ *
+ */
+ int nrColors;
+
+ /**
+ * Color look up table
+ */
+ RGB clut[256];
+
+};
+
+
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+IndexedMap *IndexedMapCreate(int width, int height);
+
+#ifdef __cplusplus
+}
+#endif
+
+
+
+
+#endif /* __IMAGEMAP_H__ */
+
+/*#########################################################################
+### E N D O F F I L E
+#########################################################################*/
diff --git a/src/trace/pool.h b/src/trace/pool.h
new file mode 100644
index 0000000..a6fed59
--- /dev/null
+++ b/src/trace/pool.h
@@ -0,0 +1,119 @@
+// 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 *) : realease 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 availlable) 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.
+
+*/
+
+#include <cstdlib>
+
+template <typename T>
+class pool {
+
+ public:
+
+ pool()
+ {
+ cblock = 0;
+ size = sizeof(T) > sizeof(void *) ? sizeof(T) : sizeof(void *);
+ next = nullptr;
+ for (auto & k : block) {
+ k = nullptr;
+ }
+ }
+
+ ~pool()
+ {
+ for (int k = 0; k < cblock; k++) {
+ 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));
+ //printf("pool allocating block: %d (size:%d)...", i, blocksize);//debug
+ block[i] = (void *)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];
+ //printf("done\n");//debug
+ }
+
+};
+
diff --git a/src/trace/potrace/bitmap.h b/src/trace/potrace/bitmap.h
new file mode 100644
index 0000000..bb50b2d
--- /dev/null
+++ b/src/trace/potrace/bitmap.h
@@ -0,0 +1,117 @@
+// 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) {
+ 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..710e5cf
--- /dev/null
+++ b/src/trace/potrace/inkscape-potrace.cpp
@@ -0,0 +1,661 @@
+// 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 "inkscape-potrace.h"
+
+#include <glibmm/i18n.h>
+#include <gtkmm/main.h>
+#include <iomanip>
+
+#include "trace/filterset.h"
+#include "trace/quantize.h"
+#include "trace/imagemap-gdk.h"
+
+#include <inkscape.h>
+#include "desktop.h"
+#include "message-stack.h"
+
+#include "object/sp-path.h"
+
+#include <svg/path-string.h>
+#include "bitmap.h"
+
+using Glib::ustring;
+
+static void updateGui()
+{
+ //## Allow the GUI to update
+ Gtk::Main::iteration(false); //at least once, non-blocking
+ while( Gtk::Main::events_pending() )
+ Gtk::Main::iteration();
+
+}
+
+
+static void potraceStatusCallback(double /*progress*/, void *userData) /* callback fn */
+{
+ updateGui();
+
+ if (!userData)
+ return;
+
+ //g_message("progress: %f\n", progress);
+
+ //Inkscape::Trace::Potrace::PotraceTracingEngine *engine =
+ // (Inkscape::Trace::Potrace::PotraceTracingEngine *)userData;
+}
+
+
+namespace {
+ustring twohex( int value )
+{
+ return ustring::format(std::hex, std::setfill(L'0'), std::setw(2), value);
+}
+} // namespace
+
+
+//required by potrace
+namespace Inkscape {
+
+namespace Trace {
+
+namespace Potrace {
+
+
+/**
+ *
+ */
+PotraceTracingEngine::PotraceTracingEngine() :
+ keepGoing(1),
+ traceType(TRACE_BRIGHTNESS),
+ invert(false),
+ quantizationNrColors(8),
+ brightnessThreshold(0.45),
+ brightnessFloor(0),
+ cannyHighThreshold(0.65),
+ multiScanNrColors(8),
+ multiScanStack(true),
+ multiScanSmooth(false),
+ multiScanRemoveBackground(false)
+{
+ /* get default parameters */
+ potraceParams = potrace_param_default();
+ potraceParams->progress.callback = potraceStatusCallback;
+ potraceParams->progress.data = (void *)this;
+}
+
+PotraceTracingEngine::PotraceTracingEngine(TraceType traceType, bool invert, int quantizationNrColors, double brightnessThreshold, double brightnessFloor, double cannyHighThreshold, int multiScanNrColors, bool multiScanStack, bool multiScanSmooth, bool multiScanRemoveBackground) :
+ keepGoing(1), traceType(traceType), invert(invert), quantizationNrColors(quantizationNrColors), brightnessThreshold(brightnessThreshold), brightnessFloor(brightnessFloor), cannyHighThreshold(cannyHighThreshold), multiScanNrColors(multiScanNrColors) , multiScanStack(multiScanStack), multiScanSmooth(multiScanSmooth), multiScanRemoveBackground(multiScanRemoveBackground)
+{
+ potraceParams = potrace_param_default();
+ potraceParams->progress.callback = potraceStatusCallback;
+ potraceParams->progress.data = (void *)this;
+}
+
+
+PotraceTracingEngine::~PotraceTracingEngine()
+{
+ potrace_param_free(potraceParams);
+}
+
+
+
+
+struct Point
+{
+ double x;
+ double y;
+};
+
+
+/**
+ * Check a point against a list of points to see if it
+ * has already occurred.
+ */
+static bool hasPoint(std::vector<Point> &points, double x, double y)
+{
+ for (auto p : points)
+ {
+ if (p.x == x && p.y == y)
+ return true;
+ }
+ return false;
+}
+
+
+/**
+ * Recursively descend the potrace_path_t node tree, writing paths in SVG
+ * format into the output stream. The Point vector is used to prevent
+ * redundant paths. Returns number of paths processed.
+ */
+static long writePaths(PotraceTracingEngine *engine, potrace_path_t *plist,
+ Inkscape::SVG::PathString& data, std::vector<Point> &points)
+{
+ long nodeCount = 0L;
+
+ potrace_path_t *node;
+ for (node=plist; node ; node=node->sibling)
+ {
+ potrace_curve_t *curve = &(node->curve);
+ //g_message("node->fm:%d\n", node->fm);
+ if (!curve->n)
+ continue;
+ const potrace_dpoint_t *pt = curve->c[curve->n - 1];
+ double x0 = 0.0;
+ double y0 = 0.0;
+ double x1 = 0.0;
+ double y1 = 0.0;
+ double x2 = pt[2].x;
+ double y2 = pt[2].y;
+ //Have we been here already?
+ if (hasPoint(points, x2, y2))
+ {
+ //g_message("duplicate point: (%f,%f)\n", x2, y2);
+ continue;
+ }
+ else
+ {
+ Point p;
+ p.x = x2; p.y = y2;
+ points.push_back(p);
+ }
+ data.moveTo(x2, y2);
+ nodeCount++;
+
+ for (int i=0 ; i<curve->n ; i++)
+ {
+ if (!engine->keepGoing)
+ return 0L;
+ pt = curve->c[i];
+ x0 = pt[0].x;
+ y0 = pt[0].y;
+ x1 = pt[1].x;
+ y1 = pt[1].y;
+ x2 = pt[2].x;
+ y2 = pt[2].y;
+ switch (curve->tag[i])
+ {
+ case POTRACE_CORNER:
+ data.lineTo(x1, y1).lineTo(x2, y2);
+ break;
+ case POTRACE_CURVETO:
+ data.curveTo(x0, y0, x1, y1, x2, y2);
+ break;
+ default:
+ break;
+ }
+ nodeCount++;
+ }
+ data.closePath();
+
+ for (potrace_path_t *child=node->childlist; child ; child=child->sibling)
+ {
+ nodeCount += writePaths(engine, child, data, points);
+ }
+ }
+
+ return nodeCount;
+
+}
+
+
+static GrayMap *filter(PotraceTracingEngine &engine, GdkPixbuf * pixbuf)
+{
+ if (!pixbuf)
+ return nullptr;
+
+ GrayMap *newGm = nullptr;
+
+ /*### Color quantization -- banding ###*/
+ if (engine.traceType == TRACE_QUANT)
+ {
+ RgbMap *rgbmap = gdkPixbufToRgbMap(pixbuf);
+ //rgbMap->writePPM(rgbMap, "rgb.ppm");
+ newGm = quantizeBand(rgbmap,
+ engine.quantizationNrColors);
+ rgbmap->destroy(rgbmap);
+ //return newGm;
+ }
+
+ /*### Brightness threshold ###*/
+ else if ( engine.traceType == TRACE_BRIGHTNESS ||
+ engine.traceType == TRACE_BRIGHTNESS_MULTI )
+ {
+ GrayMap *gm = gdkPixbufToGrayMap(pixbuf);
+
+ newGm = GrayMapCreate(gm->width, gm->height);
+ double floor = 3.0 *
+ ( engine.brightnessFloor * 256.0 );
+ double cutoff = 3.0 *
+ ( engine.brightnessThreshold * 256.0 );
+ for (int y=0 ; y<gm->height ; y++)
+ {
+ for (int x=0 ; x<gm->width ; x++)
+ {
+ double brightness = (double)gm->getPixel(gm, x, y);
+ if (brightness >= floor && brightness < cutoff)
+ newGm->setPixel(newGm, x, y, GRAYMAP_BLACK); //black pixel
+ else
+ newGm->setPixel(newGm, x, y, GRAYMAP_WHITE); //white pixel
+ }
+ }
+
+ gm->destroy(gm);
+ //newGm->writePPM(newGm, "brightness.ppm");
+ //return newGm;
+ }
+
+ /*### Canny edge detection ###*/
+ else if (engine.traceType == TRACE_CANNY)
+ {
+ GrayMap *gm = gdkPixbufToGrayMap(pixbuf);
+ newGm = grayMapCanny(gm, 0.1, engine.cannyHighThreshold);
+ gm->destroy(gm);
+ //newGm->writePPM(newGm, "canny.ppm");
+ //return newGm;
+ }
+
+ /*### Do I invert the image? ###*/
+ if (newGm && engine.invert)
+ {
+ for (int y=0 ; y<newGm->height ; y++)
+ {
+ for (int x=0 ; x<newGm->width ; x++)
+ {
+ unsigned long brightness = newGm->getPixel(newGm, x, y);
+ brightness = 765 - brightness;
+ newGm->setPixel(newGm, x, y, brightness);
+ }
+ }
+ }
+
+ return newGm;//none of the above
+}
+
+
+static IndexedMap *filterIndexed(PotraceTracingEngine &engine, GdkPixbuf * pixbuf)
+{
+ if (!pixbuf)
+ return nullptr;
+
+ IndexedMap *newGm = nullptr;
+
+ RgbMap *gm = gdkPixbufToRgbMap(pixbuf);
+ if (engine.multiScanSmooth)
+ {
+ RgbMap *gaussMap = rgbMapGaussian(gm);
+ newGm = rgbMapQuantize(gaussMap, engine.multiScanNrColors);
+ gaussMap->destroy(gaussMap);
+ }
+ else
+ {
+ newGm = rgbMapQuantize(gm, engine.multiScanNrColors);
+ }
+ gm->destroy(gm);
+
+ if (engine.traceType == TRACE_QUANT_MONO)
+ {
+ //Turn to grays
+ for (int i=0 ; i<newGm->nrColors ; i++)
+ {
+ RGB rgb = newGm->clut[i];
+ int grayVal = (rgb.r + rgb.g + rgb.b) / 3;
+ rgb.r = rgb.g = rgb.b = grayVal;
+ newGm->clut[i] = rgb;
+ }
+ }
+
+ return newGm;
+}
+
+
+
+
+Glib::RefPtr<Gdk::Pixbuf>
+PotraceTracingEngine::preview(Glib::RefPtr<Gdk::Pixbuf> thePixbuf)
+{
+ GdkPixbuf *pixbuf = thePixbuf->gobj();
+
+ if ( traceType == TRACE_QUANT_COLOR ||
+ traceType == TRACE_QUANT_MONO )
+ {
+ IndexedMap *gm = filterIndexed(*this, pixbuf);
+ if (!gm)
+ return Glib::RefPtr<Gdk::Pixbuf>(nullptr);
+
+ Glib::RefPtr<Gdk::Pixbuf> newBuf =
+ Glib::wrap(indexedMapToGdkPixbuf(gm), false);
+
+ gm->destroy(gm);
+
+ return newBuf;
+ }
+ else
+ {
+ GrayMap *gm = filter(*this, pixbuf);
+ if (!gm)
+ return Glib::RefPtr<Gdk::Pixbuf>(nullptr);
+
+ Glib::RefPtr<Gdk::Pixbuf> newBuf =
+ Glib::wrap(grayMapToGdkPixbuf(gm), false);
+
+ gm->destroy(gm);
+
+ return newBuf;
+ }
+}
+
+
+//*This is the core inkscape-to-potrace binding
+std::string PotraceTracingEngine::grayMapToPath(GrayMap *grayMap, long *nodeCount)
+{
+ if (!keepGoing)
+ {
+ g_warning("aborted");
+ return "";
+ }
+
+ potrace_bitmap_t *potraceBitmap = bm_new(grayMap->width, grayMap->height);
+ bm_clear(potraceBitmap, 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(grayMap, x, y) ? 0 : 1);
+ }
+ }
+
+ //##Debug
+ /*
+ FILE *f = fopen("poimage.pbm", "wb");
+ bm_writepbm(f, bm);
+ fclose(f);
+ */
+
+ /* trace a bitmap*/
+ potrace_state_t *potraceState = potrace_trace(potraceParams,
+ potraceBitmap);
+
+ //## Free the Potrace bitmap
+ bm_free(potraceBitmap);
+
+ if (!keepGoing)
+ {
+ g_warning("aborted");
+ potrace_state_free(potraceState);
+ return "";
+ }
+
+ Inkscape::SVG::PathString data;
+
+ //## copy the path information into our d="" attribute string
+ std::vector<Point> points;
+ long thisNodeCount = writePaths(this, potraceState->plist, data, points);
+
+ /* free a potrace items */
+ potrace_state_free(potraceState);
+
+ if (!keepGoing)
+ return "";
+
+ if ( nodeCount)
+ *nodeCount = thisNodeCount;
+
+ return data.string();
+}
+
+
+
+/**
+ * This is called for a single scan
+ */
+std::vector<TracingEngineResult> PotraceTracingEngine::traceSingle(GdkPixbuf * thePixbuf)
+{
+
+ std::vector<TracingEngineResult> results;
+
+ if (!thePixbuf)
+ return results;
+
+ brightnessFloor = 0.0; //important to set this
+
+ GrayMap *grayMap = filter(*this, thePixbuf);
+ if (!grayMap)
+ return results;
+
+ long nodeCount = 0L;
+ std::string d = grayMapToPath(grayMap, &nodeCount);
+
+ grayMap->destroy(grayMap);
+
+ char const *style = "fill:#000000";
+
+ //g_message("### GOT '%s' \n", d);
+ TracingEngineResult result(style, d, nodeCount);
+ results.push_back(result);
+
+ return results;
+}
+
+
+/**
+ * This allows routines that already generate GrayMaps to skip image filtering,
+ * increasing performance.
+ */
+std::vector<TracingEngineResult> PotraceTracingEngine::traceGrayMap(GrayMap *grayMap)
+{
+
+ std::vector<TracingEngineResult> results;
+
+ brightnessFloor = 0.0; //important to set this
+
+ long nodeCount = 0L;
+ std::string d = grayMapToPath(grayMap, &nodeCount);
+
+ char const *style = "fill:#000000";
+
+ //g_message("### GOT '%s' \n", d);
+ TracingEngineResult result(style, d, nodeCount);
+ results.push_back(result);
+
+ return results;
+}
+
+/**
+ * Called for multiple-scanning algorithms
+ */
+std::vector<TracingEngineResult> PotraceTracingEngine::traceBrightnessMulti(GdkPixbuf * thePixbuf)
+{
+ std::vector<TracingEngineResult> results;
+
+ if ( thePixbuf ) {
+ double low = 0.2; //bottom of range
+ double high = 0.9; //top of range
+ double delta = (high - low ) / ((double)multiScanNrColors);
+
+ brightnessFloor = 0.0; //Set bottom to black
+
+ int traceCount = 0;
+
+ for ( brightnessThreshold = low ;
+ brightnessThreshold <= high ;
+ brightnessThreshold += delta) {
+ GrayMap *grayMap = filter(*this, thePixbuf);
+ if ( grayMap ) {
+ long nodeCount = 0L;
+ std::string d = grayMapToPath(grayMap, &nodeCount);
+
+ grayMap->destroy(grayMap);
+
+ if ( !d.empty() ) {
+ //### get style info
+ int grayVal = (int)(256.0 * brightnessThreshold);
+ ustring style = ustring::compose("fill-opacity:1.0;fill:#%1%2%3", twohex(grayVal), twohex(grayVal), twohex(grayVal) );
+
+ //g_message("### GOT '%s' \n", style.c_str());
+ TracingEngineResult result(style, d, nodeCount);
+ results.push_back(result);
+
+ if (!multiScanStack) {
+ brightnessFloor = brightnessThreshold;
+ }
+
+ SPDesktop *desktop = SP_ACTIVE_DESKTOP;
+ if (desktop) {
+ ustring msg = ustring::compose(_("Trace: %1. %2 nodes"), traceCount++, nodeCount);
+ desktop->getMessageStack()->flash(Inkscape::NORMAL_MESSAGE, msg);
+ }
+ }
+ }
+ }
+
+ //# Remove the bottom-most scan, if requested
+ if (results.size() > 1 && multiScanRemoveBackground) {
+ results.erase(results.end() - 1);
+ }
+ }
+
+ return results;
+}
+
+
+/**
+ * Quantization
+ */
+std::vector<TracingEngineResult> PotraceTracingEngine::traceQuant(GdkPixbuf * thePixbuf)
+{
+ std::vector<TracingEngineResult> results;
+
+ if (thePixbuf) {
+ IndexedMap *iMap = filterIndexed(*this, thePixbuf);
+ if ( iMap ) {
+ //Create and clear a gray map
+ GrayMap *gm = GrayMapCreate(iMap->width, iMap->height);
+ for (int row=0 ; row<gm->height ; row++) {
+ for (int col=0 ; col<gm->width ; col++) {
+ gm->setPixel(gm, col, row, GRAYMAP_WHITE);
+ }
+ }
+
+ for (int colorIndex=0 ; colorIndex<iMap->nrColors ; colorIndex++) {
+ // Make a gray map for each color index
+ for (int row=0 ; row<iMap->height ; row++) {
+ for (int col=0 ; col<iMap->width ; col++) {
+ int indx = (int) iMap->getPixel(iMap, col, row);
+ if (indx == colorIndex) {
+ gm->setPixel(gm, col, row, GRAYMAP_BLACK); //black
+ } else if (!multiScanStack) {
+ gm->setPixel(gm, col, row, GRAYMAP_WHITE); //white
+ }
+ }
+ }
+
+ //## Now we have a traceable graymap
+ long nodeCount = 0L;
+ std::string d = grayMapToPath(gm, &nodeCount);
+
+ if ( !d.empty() ) {
+ //### get style info
+ RGB rgb = iMap->clut[colorIndex];
+ ustring style = ustring::compose("fill:#%1%2%3", twohex(rgb.r), twohex(rgb.g), twohex(rgb.b) );
+
+ //g_message("### GOT '%s' \n", style.c_str());
+ TracingEngineResult result(style, d, nodeCount);
+ results.push_back(result);
+
+ SPDesktop *desktop = SP_ACTIVE_DESKTOP;
+ if (desktop) {
+ ustring msg = ustring::compose(_("Trace: %1. %2 nodes"), colorIndex, nodeCount);
+ desktop->getMessageStack()->flash(Inkscape::NORMAL_MESSAGE, msg);
+ }
+ }
+ }// for colorIndex
+
+ gm->destroy(gm);
+ iMap->destroy(iMap);
+ }
+
+ //# Remove the bottom-most scan, if requested
+ if (results.size() > 1 && multiScanRemoveBackground) {
+ results.erase(results.end() - 1);
+ }
+ }
+
+ return results;
+}
+
+
+/**
+ * This is the working method of this interface, and all
+ * implementing classes. Take a GdkPixbuf, trace it, and
+ * return the path data that is compatible with the d="" attribute
+ * of an SVG <path> element.
+ */
+std::vector<TracingEngineResult>
+PotraceTracingEngine::trace(Glib::RefPtr<Gdk::Pixbuf> pixbuf)
+{
+
+ GdkPixbuf *thePixbuf = pixbuf->gobj();
+
+ //Set up for messages
+ keepGoing = 1;
+
+ if ( traceType == TRACE_QUANT_COLOR ||
+ traceType == TRACE_QUANT_MONO )
+ {
+ return traceQuant(thePixbuf);
+ }
+ else if ( traceType == TRACE_BRIGHTNESS_MULTI )
+ {
+ return traceBrightnessMulti(thePixbuf);
+ }
+ else
+ {
+ return traceSingle(thePixbuf);
+ }
+}
+
+
+/**
+ * Abort the thread that is executing getPathDataFromPixbuf()
+ */
+void PotraceTracingEngine::abort()
+{
+ //g_message("PotraceTracingEngine::abort()\n");
+ keepGoing = 0;
+}
+
+
+
+
+} // 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..1385521
--- /dev/null
+++ b/src/trace/potrace/inkscape-potrace.h
@@ -0,0 +1,141 @@
+// 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_POTRACE_H__
+#define __INKSCAPE_POTRACE_H__
+
+#include <trace/trace.h>
+#include <potracelib.h>
+
+struct GrayMap_def;
+typedef GrayMap_def GrayMap;
+
+namespace Inkscape {
+
+namespace Trace {
+
+namespace Potrace {
+
+enum TraceType
+ {
+ TRACE_BRIGHTNESS,
+ TRACE_BRIGHTNESS_MULTI,
+ TRACE_CANNY,
+ TRACE_QUANT,
+ TRACE_QUANT_COLOR,
+ TRACE_QUANT_MONO
+ };
+
+
+class PotraceTracingEngine : 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;
+
+ /**
+ * This is the working method of this implementing class, and all
+ * implementing classes. Take a GdkPixbuf, trace it, and
+ * return the path data that is compatible with the d="" attribute
+ * of an SVG <path> element.
+ */
+ std::vector<TracingEngineResult> trace(
+ Glib::RefPtr<Gdk::Pixbuf> pixbuf) override;
+
+ /**
+ * Abort the thread that is executing getPathDataFromPixbuf()
+ */
+ void abort() override;
+
+ /**
+ *
+ */
+ Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> pixbuf);
+
+ /**
+ *
+ */
+ int keepGoing;
+
+ std::vector<TracingEngineResult>traceGrayMap(GrayMap *grayMap);
+
+ potrace_param_t *potraceParams;
+ TraceType traceType;
+
+ //## do I invert at the end?
+ bool invert;
+
+ //## Color-->b&w quantization
+ int quantizationNrColors;
+
+ //## brightness items
+ double brightnessThreshold;
+ double brightnessFloor; //usually 0.0
+
+ //## canny items
+ double cannyHighThreshold;
+
+ //## Color-->multiscan quantization
+ int multiScanNrColors;
+ bool multiScanStack; //do we tile or stack?
+ bool multiScanSmooth;//do we use gaussian filter?
+ bool multiScanRemoveBackground; //do we remove the bottom trace?
+
+ private:
+ /**
+ * This is the actual wrapper of the call to Potrace. nodeCount
+ * returns the count of nodes created. May be NULL if ignored.
+ */
+ std::string grayMapToPath(GrayMap *gm, long *nodeCount);
+
+ std::vector<TracingEngineResult>traceBrightnessMulti(GdkPixbuf *pixbuf);
+ std::vector<TracingEngineResult>traceQuant(GdkPixbuf *pixbuf);
+ std::vector<TracingEngineResult>traceSingle(GdkPixbuf *pixbuf);
+
+
+};//class PotraceTracingEngine
+
+
+
+} // namespace Potrace
+} // namespace Trace
+} // namespace Inkscape
+
+
+#endif //__INKSCAPE_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..93dbb35
--- /dev/null
+++ b/src/trace/quantize.cpp
@@ -0,0 +1,597 @@
+// 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 <cassert>
+#include <cstdio>
+#include <cstdlib>
+#include <new>
+
+#include "pool.h"
+#include "imagemap.h"
+#include "quantize.h"
+
+typedef struct Ocnode_def Ocnode;
+
+/**
+ * an octree node datastructure
+ */
+struct Ocnode_def
+{
+ 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 brother is a leaf, the brother is deleted as well, both nodes
+ are then represented by their father.
+
+ | |
+ . ==> .
+ / \
+ A .
+
+ - otherwise the deletion of A deletes also his father, 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).
+
+*/
+
+inline 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;
+}
+inline bool operator==(RGB rgb1, RGB rgb2)
+{
+ return (rgb1.r == rgb2.r && rgb1.g == rgb2.g && rgb1.b == rgb2.b);
+}
+
+inline int childIndex(RGB rgb)
+{
+ return (((rgb.r)&1)<<2) | (((rgb.g)&1)<<1) | (((rgb.b)&1));
+}
+
+/**
+ * allocate a new node
+ */
+inline 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;
+}
+
+inline void ocnodeFree(pool<Ocnode> *pool, Ocnode *node) {
+ pool->drop(node);
+}
+
+
+/**
+ * free a full octree
+ */
+static 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
+static 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>
+ */
+static 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>
+ */
+static 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 =
+ node1->width > node2->width ? 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
+ */
+static inline 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.
+ */
+static void ocnodeStrip(pool<Ocnode> *pool, Ocnode **ref, int *count, unsigned long lvl)
+{
+ Ocnode *node = *ref;
+ if (!count || !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) //node is above strip level
+ return;
+ 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
+ */
+static void octreePrune(pool<Ocnode> *pool, Ocnode **ref, int ncolor)
+{
+ assert(ref);
+ assert(ncolor > 0);
+ //printf("pruning down to %d colors:\n", ncolor);//debug
+ int n = (*ref)->nleaf - ncolor;
+ if (!*ref || n <= 0) return;
+ while (n > 0)
+ {
+ //printf("removals to go: %10d\t", n);//debug
+ //printf("current prune impact: %10lu\n", (*ref)->mi);//debug
+ //calling strip with global minimum impact of the tree
+ 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.
+ */
+static void octreeBuildArea(pool<Ocnode> *pool, RgbMap *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(rgbmap, 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.
+ */
+static Ocnode *octreeBuild(pool<Ocnode> *pool, RgbMap *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);
+
+ //octreePrint(node);//debug
+
+ return node;
+}
+
+/**
+ * compute the color palette associated to an octree.
+ */
+static 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
+ */
+static 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
+ */
+static int findRGB(RGB *rgbpal, int ncolor, RGB rgb)
+{
+ //assert(ncolor > 0);
+ //assert(rgbpal);
+ int index = -1, dist = 0;
+ for (int k = 0; k < ncolor; k++)
+ {
+ int d = distRGB(rgbpal[k], rgb);
+ if (index == -1 || d < dist) { dist = d; index = k; }
+ }
+ return index;
+}
+
+/**
+ * (qsort) compare two colors for brightness
+ */
+static int compRGB(const void *a, const void *b)
+{
+ RGB *ra = (RGB *)a, *rb = (RGB *)b;
+ return (ra->r + ra->g + ra->b) - (rb->r + rb->g + rb->b);
+}
+
+/**
+ * quantize an RGB image to a reduced number of colors.
+ */
+IndexedMap *rgbMapQuantize(RgbMap *rgbmap, int ncolor)
+{
+ assert(rgbmap);
+ assert(ncolor > 0);
+
+ IndexedMap *newmap = nullptr;
+
+ pool<Ocnode> pool;
+
+ Ocnode *tree = nullptr;
+ try {
+ tree = octreeBuild(&pool, rgbmap, ncolor);
+ }
+ catch (std::bad_alloc &ex) {
+ //should do smthg else?
+ }
+
+ if ( tree ) {
+ RGB *rgbpal = new RGB[ncolor];
+ int indexes = 0;
+ octreeIndex(tree, rgbpal, &indexes);
+
+ octreeDelete(&pool, tree);
+
+ // stacking with increasing contrasts
+ qsort((void *)rgbpal, indexes, sizeof(RGB), compRGB);
+
+ // make the new map
+ newmap = IndexedMapCreate(rgbmap->width, rgbmap->height);
+ if (newmap) {
+ // fill in the color lookup table
+ for (int i = 0; i < indexes; i++) {
+ newmap->clut[i] = rgbpal[i];
+ }
+ newmap->nrColors = indexes;
+
+ // fill in new map pixels
+ for (int y = 0; y < rgbmap->height; y++) {
+ for (int x = 0; x < rgbmap->width; x++) {
+ RGB rgb = rgbmap->getPixel(rgbmap, x, y);
+ int index = findRGB(rgbpal, ncolor, rgb);
+ newmap->setPixel(newmap, x, y, index);
+ }
+ }
+ }
+ delete[] rgbpal;
+ }
+
+ return newmap;
+}
diff --git a/src/trace/quantize.h b/src/trace/quantize.h
new file mode 100644
index 0000000..43942f5
--- /dev/null
+++ b/src/trace/quantize.h
@@ -0,0 +1,23 @@
+// 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 __QUANTIZE_H__
+#define __QUANTIZE_H__
+
+#include "imagemap.h"
+
+/**
+ * Quantize an RGB image to a reduced number of colors.
+ */
+IndexedMap *rgbMapQuantize(RgbMap *rgbmap, int nrColors);
+
+#endif /* __QUANTIZE_H__ */
diff --git a/src/trace/siox.cpp b/src/trace/siox.cpp
new file mode 100644
index 0000000..12d7c20
--- /dev/null
+++ b/src/trace/siox.cpp
@@ -0,0 +1,1733 @@
+// 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 "siox.h"
+
+#include <cmath>
+#include <cstdarg>
+#include <map>
+#include <algorithm>
+#include <cstdlib>
+
+
+namespace org
+{
+
+namespace siox
+{
+
+
+
+//########################################################################
+//# C L A B
+//########################################################################
+
+/**
+ * Convert integer A, R, G, B values into an pixel value.
+ */
+static unsigned long getRGB(int a, int r, int g, int b)
+{
+ if (a<0) a=0;
+ else if (a>255) a=255;
+
+ if (r<0) r=0;
+ else if (r>255) r=255;
+
+ if (g<0) g=0;
+ else if (g>255) g=255;
+
+ if (b<0) b=0;
+ else if (b>255) b=255;
+
+ return (a<<24)|(r<<16)|(g<<8)|b;
+}
+
+
+
+/**
+ * Convert float A, R, G, B values (0.0-1.0) into an pixel value.
+ */
+static unsigned long getRGB(float a, float r, float g, float b)
+{
+ return getRGB((int)(a * 256.0),
+ (int)(r * 256.0),
+ (int)(g * 256.0),
+ (int)(b * 256.0));
+}
+
+
+
+//#########################################
+//# Root approximations for large speedup.
+//# By njh!
+//#########################################
+static const int ROOT_TAB_SIZE = 16;
+static float cbrt_table[ROOT_TAB_SIZE +1];
+
+double CieLab::cbrt(double x)
+{
+ double y = cbrt_table[int(x*ROOT_TAB_SIZE )]; // assuming x \in [0, 1]
+ y = (2.0 * y + x/(y*y))/3.0;
+ y = (2.0 * y + x/(y*y))/3.0; // polish twice
+ return y;
+}
+
+static float qn_table[ROOT_TAB_SIZE +1];
+
+double CieLab::qnrt(double x)
+{
+ double y = qn_table[int(x*ROOT_TAB_SIZE )]; // assuming x \in [0, 1]
+ double Y = y*y;
+ y = (4.0*y + x/(Y*Y))/5.0;
+ Y = y*y;
+ y = (4.0*y + x/(Y*Y))/5.0; // polish twice
+ return y;
+}
+
+double CieLab::pow24(double x)
+{
+ double onetwo = x*qnrt(x);
+ return onetwo*onetwo;
+}
+
+
+static bool _clab_inited_ = false;
+void CieLab::init()
+{
+ if (!_clab_inited_)
+ {
+ cbrt_table[0] = pow(float(1)/float(ROOT_TAB_SIZE*2), 0.3333);
+ qn_table[0] = pow(float(1)/float(ROOT_TAB_SIZE*2), 0.2);
+ for(int i = 1; i < ROOT_TAB_SIZE +1; i++)
+ {
+ cbrt_table[i] = pow(float(i)/float(ROOT_TAB_SIZE), 0.3333);
+ qn_table[i] = pow(float(i)/float(ROOT_TAB_SIZE), 0.2);
+ }
+ _clab_inited_ = true;
+ }
+}
+
+
+
+/**
+ * Construct this CieLab from a packed-pixel ARGB value
+ */
+CieLab::CieLab(unsigned long rgb)
+{
+ init();
+
+ int ir = (rgb>>16) & 0xff;
+ int ig = (rgb>> 8) & 0xff;
+ int ib = (rgb ) & 0xff;
+
+ float fr = ((float)ir) / 255.0;
+ float fg = ((float)ig) / 255.0;
+ float fb = ((float)ib) / 255.0;
+
+ //printf("fr:%f fg:%f fb:%f\n", fr, fg, fb);
+ if (fr > 0.04045)
+ //fr = (float) pow((fr + 0.055) / 1.055, 2.4);
+ fr = (float) pow24((fr + 0.055) / 1.055);
+ else
+ fr = fr / 12.92;
+
+ if (fg > 0.04045)
+ //fg = (float) pow((fg + 0.055) / 1.055, 2.4);
+ fg = (float) pow24((fg + 0.055) / 1.055);
+ else
+ fg = fg / 12.92;
+
+ if (fb > 0.04045)
+ //fb = (float) pow((fb + 0.055) / 1.055, 2.4);
+ fb = (float) pow24((fb + 0.055) / 1.055);
+ else
+ fb = fb / 12.92;
+
+ // Use white = D65
+ const float x = fr * 0.4124 + fg * 0.3576 + fb * 0.1805;
+ const float y = fr * 0.2126 + fg * 0.7152 + fb * 0.0722;
+ const 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);
+ if (vx > 0.008856)
+ //vx = (float) pow(vx, 0.3333);
+ vx = (float) cbrt(vx);
+ else
+ vx = (7.787 * vx) + (16.0 / 116.0);
+
+ if (vy > 0.008856)
+ //vy = (float) pow(vy, 0.3333);
+ vy = (float) cbrt(vy);
+ else
+ vy = (7.787 * vy) + (16.0 / 116.0);
+
+ if (vz > 0.008856)
+ //vz = (float) pow(vz, 0.3333);
+ vz = (float) cbrt(vz);
+ else
+ vz = (7.787 * vz) + (16.0 / 116.0);
+
+ C = 0;
+ L = 116.0 * vy - 16.0;
+ A = 500.0 * (vx - vy);
+ B = 200.0 * (vy - vz);
+}
+
+
+
+/**
+ * Return this CieLab's value converted to a packed-pixel ARGB value
+ */
+unsigned long CieLab::toRGB()
+{
+ float vy = (L + 16.0) / 116.0;
+ float vx = A / 500.0 + vy;
+ float vz = vy - B / 200.0;
+
+ float vx3 = vx * vx * vx;
+ float vy3 = vy * vy * vy;
+ float vz3 = vz * vz * vz;
+
+ if (vy3 > 0.008856)
+ vy = vy3;
+ else
+ vy = (vy - 16.0 / 116.0) / 7.787;
+
+ if (vx3 > 0.008856)
+ vx = vx3;
+ else
+ vx = (vx - 16.0 / 116.0) / 7.787;
+
+ if (vz3 > 0.008856)
+ vz = vz3;
+ else
+ vz = (vz - 16.0 / 116.0) / 7.787;
+
+ vx *= 0.95047; //use white = D65
+ vz *= 1.08883;
+
+ float vr =(float)(vx * 3.2406 + vy * -1.5372 + vz * -0.4986);
+ float vg =(float)(vx * -0.9689 + vy * 1.8758 + vz * 0.0415);
+ float vb =(float)(vx * 0.0557 + vy * -0.2040 + vz * 1.0570);
+
+ if (vr > 0.0031308)
+ vr = (float)(1.055 * pow(vr, (1.0 / 2.4)) - 0.055);
+ else
+ vr = 12.92 * vr;
+
+ if (vg > 0.0031308)
+ vg = (float)(1.055 * pow(vg, (1.0 / 2.4)) - 0.055);
+ else
+ vg = 12.92 * vg;
+
+ if (vb > 0.0031308)
+ vb = (float)(1.055 * pow(vb, (1.0 / 2.4)) - 0.055);
+ else
+ vb = 12.92 * vb;
+
+ return getRGB(0.0, vr, vg, vb);
+}
+
+
+/**
+ * Squared Euclidian distance between this and another color
+ */
+float CieLab::diffSq(const CieLab &other)
+{
+ float sum=0.0;
+ sum += (L - other.L) * (L - other.L);
+ sum += (A - other.A) * (A - other.A);
+ sum += (B - other.B) * (B - other.B);
+ return sum;
+}
+
+/**
+ * Computes squared euclidian distance in CieLab space for two colors
+ * given as RGB values.
+ */
+float CieLab::diffSq(unsigned int rgb1, unsigned int rgb2)
+{
+ CieLab c1(rgb1);
+ CieLab c2(rgb2);
+ float euclid = c1.diffSq(c2);
+ return euclid;
+}
+
+
+/**
+ * Computes squared euclidian distance in CieLab space for two colors
+ * given as RGB values.
+ */
+float CieLab::diff(unsigned int rgb0, unsigned int rgb1)
+{
+ return (float) sqrt(diffSq(rgb0, rgb1));
+}
+
+
+
+//########################################################################
+//# T U P E L
+//########################################################################
+
+/**
+ * Helper class for storing the minimum distances to a cluster centroid
+ * in background and foreground and the index to the centroids in each
+ * signature for a given color.
+ */
+class Tupel {
+public:
+
+ Tupel()
+ {
+ minBgDist = 0.0f;
+ indexMinBg = 0;
+ minFgDist = 0.0f;
+ indexMinFg = 0;
+ }
+ Tupel(float minBgDistArg, long indexMinBgArg,
+ float minFgDistArg, long indexMinFgArg)
+ {
+ minBgDist = minBgDistArg;
+ indexMinBg = indexMinBgArg;
+ minFgDist = minFgDistArg;
+ indexMinFg = indexMinFgArg;
+ }
+ Tupel(const Tupel &other)
+ {
+ minBgDist = other.minBgDist;
+ indexMinBg = other.indexMinBg;
+ minFgDist = other.minFgDist;
+ indexMinFg = other.indexMinFg;
+ }
+ Tupel &operator=(const Tupel &other)
+ = default;
+ virtual ~Tupel()
+ = default;
+
+ float minBgDist;
+ long indexMinBg;
+ float minFgDist;
+ long indexMinFg;
+
+ };
+
+
+
+//########################################################################
+//# S I O X I M A G E
+//########################################################################
+
+/**
+ * Create an image with the given width and height
+ */
+SioxImage::SioxImage(unsigned int widthArg, unsigned int heightArg)
+{
+ init(widthArg, heightArg);
+}
+
+/**
+ * Copy constructor
+ */
+SioxImage::SioxImage(const SioxImage &other)
+{
+ pixdata = nullptr;
+ cmdata = nullptr;
+ assign(other);
+}
+
+/**
+ * Assignment
+ */
+SioxImage &SioxImage::operator=(const SioxImage &other)
+{
+ assign(other);
+ return *this;
+}
+
+
+/**
+ * Clean up after use.
+ */
+SioxImage::~SioxImage()
+{
+ if (pixdata) delete[] pixdata;
+ if (cmdata) delete[] cmdata;
+}
+
+/**
+ * Error logging
+ */
+void SioxImage::error(const char *fmt, ...)
+{
+ char msgbuf[256];
+ va_list args;
+ va_start(args, fmt);
+ vsnprintf(msgbuf, 255, fmt, args);
+ va_end(args) ;
+#ifdef HAVE_GLIB
+ g_warning("SioxImage error: %s\n", msgbuf);
+#else
+ fprintf(stderr, "SioxImage error: %s\n", msgbuf);
+#endif
+}
+
+
+/**
+ * Returns true if the previous operation on this image
+ * was successful, else false.
+ */
+bool SioxImage::isValid()
+{
+ return valid;
+}
+
+/**
+ * Sets whether an operation was successful, and whether
+ * this image should be considered a valid one.
+ * was successful, else false.
+ */
+void SioxImage::setValid(bool val)
+{
+ valid = val;
+}
+
+
+/**
+ * Set a pixel at the x,y coordinates to the given value.
+ * If the coordinates are out of range, do nothing.
+ */
+void SioxImage::setPixel(unsigned int x,
+ unsigned int y,
+ unsigned int pixval)
+{
+ if (x >= width || y >= height)
+ {
+ error("setPixel: out of bounds (%d,%d)/(%d,%d)",
+ x, y, width, height);
+ return;
+ }
+ unsigned long offset = width * y + x;
+ pixdata[offset] = pixval;
+}
+
+/**
+ * Set a pixel at the x,y coordinates to the given r, g, b values.
+ * If the coordinates are out of range, do nothing.
+ */
+void SioxImage::setPixel(unsigned int x, unsigned int y,
+ unsigned int a,
+ unsigned int r,
+ unsigned int g,
+ unsigned int b)
+{
+ if (x >= width || y >= height)
+ {
+ error("setPixel: out of bounds (%d,%d)/(%d,%d)",
+ x, y, width, height);
+ return;
+ }
+ unsigned long offset = width * y + x;
+ unsigned int pixval = ((a << 24) & 0xff000000) |
+ ((r << 16) & 0x00ff0000) |
+ ((g << 8) & 0x0000ff00) |
+ ((b ) & 0x000000ff);
+ pixdata[offset] = pixval;
+}
+
+
+
+/**
+ * Get a pixel at the x,y coordinates given. If
+ * the coordinates are out of range, return 0;
+ */
+unsigned int SioxImage::getPixel(unsigned int x, unsigned int y)
+{
+ if (x >= width || y >= height)
+ {
+ error("getPixel: out of bounds (%d,%d)/(%d,%d)",
+ x, y, width, height);
+ return 0L;
+ }
+ unsigned long offset = width * y + x;
+ return pixdata[offset];
+}
+
+/**
+ * Return the image data buffer
+ */
+unsigned int *SioxImage::getImageData()
+{
+ return pixdata;
+}
+
+/**
+ * Set a confidence value at the x,y coordinates to the given value.
+ * If the coordinates are out of range, do nothing.
+ */
+void SioxImage::setConfidence(unsigned int x,
+ unsigned int y,
+ float confval)
+{
+ if (x >= width || y >= height)
+ {
+ error("setConfidence: out of bounds (%d,%d)/(%d,%d)",
+ x, y, width, height);
+ return;
+ }
+ unsigned long offset = width * y + x;
+ cmdata[offset] = confval;
+}
+
+/**
+ * Get a confidence valueat the x,y coordinates given. If
+ * the coordinates are out of range, return 0;
+ */
+float SioxImage::getConfidence(unsigned int x, unsigned int y)
+{
+ if (x >= width || y >= height)
+ {
+ g_warning("getConfidence: out of bounds (%d,%d)/(%d,%d)",
+ x, y, width, height);
+ return 0.0;
+ }
+ unsigned long offset = width * y + x;
+ return cmdata[offset];
+}
+
+/**
+ * Return the confidence data buffer
+ */
+float *SioxImage::getConfidenceData()
+{
+ return cmdata;
+}
+
+
+/**
+ * Return the width of this image
+ */
+int SioxImage::getWidth()
+{
+ return width;
+}
+
+/**
+ * Return the height of this image
+ */
+int SioxImage::getHeight()
+{
+ return height;
+}
+
+/**
+ * Initialize values. Used by constructors
+ */
+void SioxImage::init(unsigned int widthArg, unsigned int heightArg)
+{
+ valid = true;
+ width = widthArg;
+ height = heightArg;
+ imageSize = width * height;
+ pixdata = new unsigned int[imageSize];
+ cmdata = new float[imageSize];
+ for (unsigned long i=0 ; i<imageSize ; i++)
+ {
+ pixdata[i] = 0;
+ cmdata[i] = 0.0;
+ }
+}
+
+/**
+ * Assign values to that of another
+ */
+void SioxImage::assign(const SioxImage &other)
+{
+ if (pixdata) delete[] pixdata;
+ if (cmdata) delete[] cmdata;
+ valid = other.valid;
+ width = other.width;
+ height = other.height;
+ imageSize = width * height;
+ pixdata = new unsigned int[imageSize];
+ cmdata = new float[imageSize];
+ for (unsigned long i=0 ; i<imageSize ; i++)
+ {
+ pixdata[i] = other.pixdata[i];
+ cmdata[i] = other.cmdata[i];
+ }
+}
+
+
+/**
+ * Write the image to a PPM file
+ */
+bool SioxImage::writePPM(const std::string &fileName)
+{
+
+ FILE *f = fopen(fileName.c_str(), "wb");
+ if (!f)
+ return false;
+
+ fprintf(f, "P6 %u %u 255\n", width, height);
+
+ for (unsigned int y=0 ; y<height; y++)
+ {
+ for (unsigned int x=0 ; x<width ; x++)
+ {
+ unsigned int rgb = getPixel(x, y);
+ //unsigned int alpha = (rgb>>24) & 0xff;
+ unsigned int r = ((rgb>>16) & 0xff);
+ unsigned int g = ((rgb>> 8) & 0xff);
+ unsigned int b = ((rgb ) & 0xff);
+ fputc((unsigned char) r, f);
+ fputc((unsigned char) g, f);
+ fputc((unsigned char) b, f);
+ }
+ }
+ fclose(f);
+ return true;
+}
+
+
+#ifdef HAVE_GLIB
+
+/**
+ * Create an image from a GdkPixbuf
+ */
+SioxImage::SioxImage(GdkPixbuf *buf)
+{
+ if (!buf)
+ return;
+
+ unsigned int width = gdk_pixbuf_get_width(buf);
+ unsigned int height = gdk_pixbuf_get_height(buf);
+ init(width, height); //DO THIS NOW!!
+
+
+ guchar *pixldata = gdk_pixbuf_get_pixels(buf);
+ int rowstride = gdk_pixbuf_get_rowstride(buf);
+ int n_channels = gdk_pixbuf_get_n_channels(buf);
+
+ //### Fill in the cells with RGB values
+ int row = 0;
+ for (unsigned int y=0 ; y<height ; y++)
+ {
+ guchar *p = pixldata + row;
+ for (unsigned int x=0 ; x<width ; x++)
+ {
+ int r = (int)p[0];
+ int g = (int)p[1];
+ int b = (int)p[2];
+ int alpha = (int)p[3];
+
+ setPixel(x, y, alpha, r, g, b);
+ p += n_channels;
+ }
+ row += rowstride;
+ }
+
+}
+
+
+/**
+ * Create a GdkPixbuf from this image
+ */
+GdkPixbuf *SioxImage::getGdkPixbuf()
+{
+ bool has_alpha = true;
+ int n_channels = has_alpha ? 4 : 3;
+
+ guchar *pixdata = (guchar *)
+ malloc(sizeof(guchar) * width * height * n_channels);
+ if (!pixdata)
+ return nullptr;
+
+ int rowstride = width * n_channels;
+
+ GdkPixbuf *buf = gdk_pixbuf_new_from_data(pixdata,
+ GDK_COLORSPACE_RGB,
+ has_alpha, 8, width, height,
+ rowstride, (GdkPixbufDestroyNotify)free, nullptr);
+
+ //### Fill in the cells with RGB values
+ int row = 0;
+ for (unsigned int y=0 ; y < height ; y++)
+ {
+ guchar *p = pixdata + row;
+ for (unsigned x=0 ; x < width ; x++)
+ {
+ unsigned int rgb = getPixel(x, y);
+ p[0] = (rgb >> 16) & 0xff;//r
+ p[1] = (rgb >> 8) & 0xff;//g
+ p[2] = (rgb ) & 0xff;//b
+ if ( n_channels > 3 )
+ {
+ p[3] = (rgb >> 24) & 0xff;//a
+ }
+ p += n_channels;
+ }
+ row += rowstride;
+ }
+ return buf;
+}
+
+#endif /* GLIB */
+
+
+
+
+//########################################################################
+//# S I O X
+//########################################################################
+
+//##############
+//## PUBLIC
+//##############
+
+/**
+ * Confidence corresponding to a certain foreground region (equals one).
+ */
+const float Siox::CERTAIN_FOREGROUND_CONFIDENCE=1.0f;
+
+/**
+ * Confidence for a region likely being foreground.
+ */
+const float Siox::FOREGROUND_CONFIDENCE=0.8f;
+
+/**
+ * Confidence for foreground or background type being equally likely.
+ */
+const float Siox::UNKNOWN_REGION_CONFIDENCE=0.5f;
+
+/**
+ * Confidence for a region likely being background.
+ */
+const float Siox::BACKGROUND_CONFIDENCE=0.1f;
+
+/**
+ * Confidence corresponding to a certain background reagion (equals zero).
+ */
+const float Siox::CERTAIN_BACKGROUND_CONFIDENCE=0.0f;
+
+/**
+ * Construct a Siox engine
+ */
+Siox::Siox() :
+ sioxObserver(nullptr),
+ keepGoing(true),
+ width(0),
+ height(0),
+ pixelCount(0),
+ image(nullptr),
+ cm(nullptr),
+ labelField(nullptr)
+{
+ init();
+}
+
+/**
+ * Construct a Siox engine
+ */
+Siox::Siox(SioxObserver *observer) :
+ sioxObserver(observer),
+ keepGoing(true),
+ width(0),
+ height(0),
+ pixelCount(0),
+ image(nullptr),
+ cm(nullptr),
+ labelField(nullptr)
+{
+ init();
+}
+
+
+/**
+ *
+ */
+Siox::~Siox()
+{
+ cleanup();
+}
+
+
+/**
+ * Error logging
+ */
+void Siox::error(const char *fmt, ...)
+{
+ char msgbuf[256];
+ va_list args;
+ va_start(args, fmt);
+ vsnprintf(msgbuf, 255, fmt, args);
+ va_end(args) ;
+#ifdef HAVE_GLIB
+ g_warning("Siox error: %s\n", msgbuf);
+#else
+ fprintf(stderr, "Siox error: %s\n", msgbuf);
+#endif
+}
+
+/**
+ * Trace logging
+ */
+void Siox::trace(const char *fmt, ...)
+{
+ char msgbuf[256];
+ va_list args;
+ va_start(args, fmt);
+ vsnprintf(msgbuf, 255, fmt, args);
+ va_end(args) ;
+#ifdef HAVE_GLIB
+ g_message("Siox: %s\n", msgbuf);
+#else
+ fprintf(stdout, "Siox: %s\n", msgbuf);
+#endif
+}
+
+
+
+/**
+ * Progress reporting
+ */
+bool Siox::progressReport(float percentCompleted)
+{
+ if (!sioxObserver)
+ return true;
+
+ bool ret = sioxObserver->progress(percentCompleted);
+
+ if (!ret)
+ {
+ trace("User selected abort");
+ keepGoing = false;
+ }
+
+ return ret;
+}
+
+
+
+
+/**
+ * Extract the foreground of the original image, according
+ * to the values in the confidence matrix.
+ */
+SioxImage Siox::extractForeground(const SioxImage &originalImage,
+ unsigned int backgroundFillColor)
+{
+ trace("### Start");
+
+ init();
+ keepGoing = true;
+
+ SioxImage workImage = originalImage;
+
+ //# fetch some info from the image
+ width = workImage.getWidth();
+ height = workImage.getHeight();
+ pixelCount = width * height;
+ image = workImage.getImageData();
+ cm = workImage.getConfidenceData();
+ labelField = new int[pixelCount];
+
+ trace("### Creating signatures");
+
+ //#### create color signatures
+ std::vector<CieLab> knownBg;
+ std::vector<CieLab> knownFg;
+ CieLab *imageClab = new CieLab[pixelCount];
+ for (unsigned long i=0 ; i<pixelCount ; i++)
+ {
+ float conf = cm[i];
+ unsigned int pix = image[i];
+ CieLab lab(pix);
+ imageClab[i] = lab;
+ if (conf <= BACKGROUND_CONFIDENCE)
+ knownBg.push_back(lab);
+ else if (conf >= FOREGROUND_CONFIDENCE)
+ knownFg.push_back(lab);
+ }
+
+ /*
+ std::vector<CieLab> imageClab;
+ for (int y = 0 ; y < workImage.getHeight() ; y++)
+ for (int x = 0 ; x < workImage.getWidth() ; x++)
+ {
+ float cm = workImage.getConfidence(x, y);
+ unsigned int pix = workImage.getPixel(x, y);
+ CieLab lab(pix);
+ imageClab.push_back(lab);
+ if (cm <= BACKGROUND_CONFIDENCE)
+ knownBg.push_back(lab); //note: uses CieLab(rgb)
+ else if (cm >= FOREGROUND_CONFIDENCE)
+ knownFg.push_back(lab);
+ }
+ */
+
+ if (!progressReport(10.0))
+ {
+ error("User aborted");
+ workImage.setValid(false);
+ delete[] imageClab;
+ delete[] labelField;
+ return workImage;
+ }
+
+ trace("knownBg:%u knownFg:%u", static_cast<unsigned int>(knownBg.size()), static_cast<unsigned int>(knownFg.size()));
+
+
+ std::vector<CieLab> bgSignature ;
+ if (!colorSignature(knownBg, bgSignature, 3))
+ {
+ error("Could not create background signature");
+ workImage.setValid(false);
+ delete[] imageClab;
+ delete[] labelField;
+ return workImage;
+ }
+
+ if (!progressReport(30.0))
+ {
+ error("User aborted");
+ workImage.setValid(false);
+ delete[] imageClab;
+ delete[] labelField;
+ return workImage;
+ }
+
+
+ std::vector<CieLab> fgSignature ;
+ if (!colorSignature(knownFg, fgSignature, 3))
+ {
+ error("Could not create foreground signature");
+ workImage.setValid(false);
+ delete[] imageClab;
+ delete[] labelField;
+ return workImage;
+ }
+
+ //trace("### bgSignature:%d", bgSignature.size());
+
+ if (bgSignature.empty())
+ {
+ // segmentation impossible
+ error("Signature size is < 1. Segmentation is impossible");
+ workImage.setValid(false);
+ delete[] imageClab;
+ delete[] labelField;
+ return workImage;
+ }
+
+ if (!progressReport(30.0))
+ {
+ error("User aborted");
+ workImage.setValid(false);
+ delete[] imageClab;
+ delete[] labelField;
+ return workImage;
+ }
+
+
+ // classify using color signatures,
+ // classification cached in hashmap for drb and speedup purposes
+ trace("### Analyzing image");
+
+ std::map<unsigned int, Tupel> hs;
+
+ unsigned int progressResolution = pixelCount / 10;
+
+ for (unsigned int i=0; i<pixelCount; i++)
+ {
+ if (i % progressResolution == 0)
+ {
+ float progress =
+ 30.0 + 60.0 * (float)i / (float)pixelCount;
+ //trace("### progress:%f", progress);
+ if (!progressReport(progress))
+ {
+ error("User aborted");
+ delete[] imageClab;
+ delete[] labelField;
+ workImage.setValid(false);
+ return workImage;
+ }
+ }
+
+ 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
+ {
+ bool isBackground = true;
+ std::map<unsigned int, Tupel>::iterator iter = hs.find(i);
+ if (iter != hs.end()) //found
+ {
+ Tupel tupel = iter->second;
+ isBackground = tupel.minBgDist <= tupel.minFgDist;
+ }
+ else
+ {
+ CieLab lab = imageClab[i];
+ float minBg = lab.diffSq(bgSignature[0]);
+ int minIndex = 0;
+ for (unsigned int j=1; j<bgSignature.size() ; j++)
+ {
+ float d = lab.diffSq(bgSignature[j]);
+ if (d<minBg)
+ {
+ minBg = d;
+ minIndex = j;
+ }
+ }
+ Tupel tupel(0.0f, 0, 0.0f, 0);
+ tupel.minBgDist = minBg;
+ tupel.indexMinBg = minIndex;
+ float minFg = 1.0e6f;
+ minIndex = -1;
+ for (unsigned int j = 0 ; j < fgSignature.size() ; j++)
+ {
+ float d = lab.diffSq(fgSignature[j]);
+ if (d < minFg)
+ {
+ minFg = d;
+ minIndex = j;
+ }
+ }
+ tupel.minFgDist = minFg;
+ tupel.indexMinFg = minIndex;
+ if (fgSignature.empty())
+ {
+ isBackground = (minBg <= clusterSize);
+ // remove next line to force behaviour of old algorithm
+ //error("foreground signature does not exist");
+ //delete[] labelField;
+ //workImage.setValid(false);
+ //return workImage;
+ }
+ else
+ {
+ isBackground = minBg < minFg;
+ }
+ hs[image[i]] = tupel;
+ }
+
+ if (isBackground)
+ cm[i] = CERTAIN_BACKGROUND_CONFIDENCE;
+ else
+ cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
+ }
+ }
+
+
+ delete[] imageClab;
+
+ 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 (unsigned int i=0; i < pixelCount; i++)
+ {
+ if (cm[i] >= UNKNOWN_REGION_CONFIDENCE)
+ cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
+ else
+ cm[i] = CERTAIN_BACKGROUND_CONFIDENCE;
+ }
+
+ keepOnlyLargeComponents(UNKNOWN_REGION_CONFIDENCE, 1.5/*sizeFactorToKeep*/);
+ fillColorRegions();
+ dilate(cm, width, height);
+
+ if (!progressReport(100.0))
+ {
+ error("User aborted");
+ delete[] labelField;
+ workImage.setValid(false);
+ return workImage;
+ }
+
+
+ //#### We are done. Now clear everything but the background
+ for (unsigned long i = 0; i<pixelCount ; i++)
+ {
+ float conf = cm[i];
+ if (conf < FOREGROUND_CONFIDENCE)
+ image[i] = backgroundFillColor;
+ }
+
+ delete[] labelField;
+
+ trace("### Done");
+ keepGoing = false;
+ return workImage;
+}
+
+
+
+//##############
+//## PRIVATE
+//##############
+
+/**
+ * Initialize the Siox engine to its 'pristine' state.
+ * Performed at the beginning of extractForeground().
+ */
+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 = sqrEuclidianDist(limits, 3, negLimits);
+}
+
+
+/**
+ * Clean up any debris from processing.
+ */
+void Siox::cleanup()
+{
+}
+
+
+
+
+/**
+ * Stage 1 of the color signature work. 'dims' will be either
+ * 2 for grays, or 3 for colors
+ */
+void Siox::colorSignatureStage1(CieLab *points,
+ unsigned int leftBase,
+ unsigned int rightBase,
+ unsigned int recursionDepth,
+ unsigned int *clusterCount,
+ const unsigned int dims)
+{
+
+ unsigned int currentDim = recursionDepth % dims;
+ CieLab point = points[leftBase];
+ float min = point(currentDim);
+ float max = min;
+
+ for (unsigned int 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 int left = leftBase;
+ unsigned int 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.0 / (float)newpoint.C);
+ points[*clusterCount] = newpoint;
+ (*clusterCount)++;
+ }
+}
+
+
+
+/**
+ * Stage 2 of the color signature work
+ */
+void Siox::colorSignatureStage2(CieLab *points,
+ unsigned int leftBase,
+ unsigned int rightBase,
+ unsigned int recursionDepth,
+ unsigned int *clusterCount,
+ const float threshold,
+ const unsigned int dims)
+{
+ unsigned int currentDim = recursionDepth % dims;
+ CieLab point = points[leftBase];
+ float min = point(currentDim);
+ float max = min;
+
+ for (unsigned int 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 int left = leftBase;
+ unsigned int 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 int sum = 0;
+ for (unsigned int i = leftBase; i < rightBase; i++)
+ sum += points[i].C;
+
+ if ((float)sum >= threshold)
+ {
+ float scale = (float)(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)++;
+ }
+ }
+}
+
+
+
+/**
+ * Main color signature method
+ */
+bool Siox::colorSignature(const std::vector<CieLab> &inputVec,
+ std::vector<CieLab> &result,
+ const unsigned int dims)
+{
+
+ unsigned int length = inputVec.size();
+
+ if (length < 1) // no error. just don't do anything
+ return true;
+
+ CieLab *input = new CieLab [length];
+
+ if (!input)
+ {
+ error("Could not allocate buffer for signature");
+ return false;
+ }
+ for (unsigned int i=0 ; i < length ; i++)
+ {
+ input[i] = inputVec[i];
+ }
+
+ unsigned int stage1length = 0;
+ colorSignatureStage1(input, 0, length, 0, &stage1length, dims);
+
+ unsigned int stage2length = 0;
+ colorSignatureStage2(input, 0, stage1length, 0, &stage2length, length * 0.001, dims);
+
+ result.clear();
+ for (unsigned int i=0 ; i < stage2length ; i++)
+ {
+ result.push_back(input[i]);
+ }
+
+ delete[] input;
+
+ return true;
+}
+
+
+
+/**
+ *
+ */
+void Siox::keepOnlyLargeComponents(float threshold,
+ double sizeFactorToKeep)
+{
+ for (unsigned long 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 (unsigned long i=0 ; i<pixelCount ; i++)
+ {
+ int regionCount = 0;
+ if (labelField[i] == -1 && cm[i] >= threshold)
+ {
+ regionCount = depthFirstSearch(i, threshold, curlabel++);
+ labelSizes.push_back(regionCount);
+ }
+
+ if (regionCount>maxregion)
+ {
+ maxregion = regionCount;
+ maxblob = curlabel-1;
+ }
+ }
+
+ for (unsigned 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.push_back(startPos);
+ }
+
+
+ while (!pixelsToVisit.empty())
+ {
+ int pos = pixelsToVisit[pixelsToVisit.size() - 1];
+ pixelsToVisit.erase(pixelsToVisit.end() - 1);
+ unsigned int x = pos % width;
+ unsigned int y = pos / width;
+
+ // check all four neighbours
+ int left = pos - 1;
+ if (((int)x)-1>=0 && labelField[left]==-1 && cm[left]>=threshold)
+ {
+ labelField[left]=curLabel;
+ componentSize++;
+ pixelsToVisit.push_back(left);
+ }
+
+ int right = pos + 1;
+ if (x+1 < width && labelField[right]==-1 && cm[right]>=threshold)
+ {
+ labelField[right]=curLabel;
+ componentSize++;
+ pixelsToVisit.push_back(right);
+ }
+
+ int top = pos - width;
+ if (((int)y)-1>=0 && labelField[top]==-1 && cm[top]>=threshold)
+ {
+ labelField[top]=curLabel;
+ componentSize++;
+ pixelsToVisit.push_back(top);
+ }
+
+ int bottom = pos + width;
+ if (y+1 < height && labelField[bottom]==-1
+ && cm[bottom]>=threshold)
+ {
+ labelField[bottom]=curLabel;
+ componentSize++;
+ pixelsToVisit.push_back(bottom);
+ }
+
+ }
+ return componentSize;
+}
+
+
+
+/**
+ *
+ */
+void Siox::fillColorRegions()
+{
+ for (unsigned long idx = 0 ; idx<pixelCount ; idx++)
+ labelField[idx] = -1;
+
+ //int maxRegion=0; // unused now
+ std::vector<int> pixelsToVisit;
+ for (unsigned long i=0; i<pixelCount; i++)
+ { // for all pixels
+ if (labelField[i]!=-1 || cm[i]<UNKNOWN_REGION_CONFIDENCE)
+ {
+ continue; // already visited or bg
+ }
+
+ unsigned int origColor = image[i];
+ unsigned long curLabel = i+1;
+ labelField[i] = curLabel;
+ cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
+
+ // int componentSize = 1;
+ pixelsToVisit.push_back(i);
+ // depth first search to fill region
+ while (!pixelsToVisit.empty())
+ {
+ int pos = pixelsToVisit[pixelsToVisit.size() - 1];
+ pixelsToVisit.erase(pixelsToVisit.end() - 1);
+ unsigned int x=pos % width;
+ unsigned int y=pos / width;
+ // check all four neighbours
+ int left = pos-1;
+ if (((int)x)-1 >= 0 && labelField[left] == -1
+ && CieLab::diff(image[left], origColor)<1.0)
+ {
+ labelField[left]=curLabel;
+ cm[left]=CERTAIN_FOREGROUND_CONFIDENCE;
+ // ++componentSize;
+ pixelsToVisit.push_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.push_back(right);
+ }
+ int top = pos - width;
+ if (((int)y)-1>=0 && labelField[top]==-1
+ && CieLab::diff(image[top], origColor)<1.0)
+ {
+ labelField[top]=curLabel;
+ cm[top]=CERTAIN_FOREGROUND_CONFIDENCE;
+ // ++componentSize;
+ pixelsToVisit.push_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.push_back(bottom);
+ }
+ }
+ //if (componentSize>maxRegion) {
+ // maxRegion=componentSize;
+ //}
+ }
+}
+
+
+
+
+/**
+ * Applies the morphological dilate operator.
+ *
+ * Can be used to close small holes in the given confidence matrix.
+ */
+void Siox::dilate(float *cm, int xres, int yres)
+{
+
+ for (int y=0; y<yres; y++)
+ {
+ for (int x=0; x<xres-1; x++)
+ {
+ int idx=(y*xres)+x;
+ if (cm[idx+1]>cm[idx])
+ 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;
+ if (cm[idx-1]>cm[idx])
+ 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;
+ if (cm[((y+1)*xres)+x] > cm[idx])
+ cm[idx]=cm[((y+1)*xres)+x];
+ }
+ }
+
+ for (int y=yres-1; y>=1; y--)
+ {
+ for (int x=0; x<xres; x++)
+ {
+ int idx=(y*xres)+x;
+ if (cm[((y-1)*xres)+x] > cm[idx])
+ cm[idx]=cm[((y-1)*xres)+x];
+ }
+ }
+}
+
+/**
+ * Applies the morphological erode operator.
+ */
+void Siox::erode(float *cm, int xres, int yres)
+{
+ for (int y=0; y<yres; y++)
+ {
+ for (int x=0; x<xres-1; x++)
+ {
+ int idx=(y*xres)+x;
+ if (cm[idx+1] < cm[idx])
+ 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;
+ if (cm[idx-1] < cm[idx])
+ 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;
+ if (cm[((y+1)*xres)+x] < cm[idx])
+ cm[idx]=cm[((y+1)*xres)+x];
+ }
+ }
+ for (int y=yres-1; y>=1; y--)
+ {
+ for (int x=0; x<xres; x++)
+ {
+ int idx=(y*xres)+x;
+ if (cm[((y-1)*xres)+x] < cm[idx])
+ cm[idx]=cm[((y-1)*xres)+x];
+ }
+ }
+}
+
+
+
+/**
+ * Normalizes the matrix to values to [0..1].
+ */
+void Siox::normalizeMatrix(float *cm, int cmSize)
+{
+ float max= -1000000.0f;
+ for (int i=0; i<cmSize; i++)
+ if (cm[i] > max) max=cm[i];
+
+ //good to use STL, but max() is not iterative
+ //float max = *std::max(cm, cm + cmSize);
+
+ if (max<=0.0 || max==1.0)
+ return;
+
+ float alpha=1.00f/max;
+ premultiplyMatrix(alpha, cm, cmSize);
+}
+
+/**
+ * Multiplies matrix with the given scalar.
+ */
+void Siox::premultiplyMatrix(float alpha, float *cm, int cmSize)
+{
+ for (int i=0; i<cmSize; i++)
+ cm[i]=alpha*cm[i];
+}
+
+/**
+ * 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 Siox::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 Euclidian distance of p and q.
+ */
+float Siox::sqrEuclidianDist(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
+} // namespace org
+
+//########################################################################
+//# E N D O F F I L E
+//########################################################################
+
diff --git a/src/trace/siox.h b/src/trace/siox.h
new file mode 100644
index 0000000..e6012e9
--- /dev/null
+++ b/src/trace/siox.h
@@ -0,0 +1,654 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+#ifndef SEEN_SIOX_H
+#define SEEN_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>
+
+#define HAVE_GLIB
+
+#ifdef HAVE_GLIB
+#include <glib.h>
+#include <gdk-pixbuf/gdk-pixbuf.h>
+#endif
+
+
+namespace org
+{
+
+namespace siox
+{
+
+
+//########################################################################
+//# C L A B
+//########################################################################
+
+/**
+ *
+ */
+class CieLab
+{
+public:
+
+ /**
+ *
+ */
+ CieLab()
+ {
+ init();
+ C = 0;
+ L = A = B = 0.0f;
+ }
+
+
+ /**
+ *
+ */
+ CieLab(unsigned long rgb);
+
+
+ /**
+ *
+ */
+ CieLab(float lArg, float aArg, float bArg)
+ {
+ init();
+ C = 0;
+ L = lArg;
+ A = aArg;
+ B = bArg;
+ }
+
+
+ /**
+ *
+ */
+ CieLab(const CieLab &other)
+ {
+ init();
+ C = other.C;
+ L = other.L;
+ A = other.A;
+ B = other.B;
+ }
+
+
+ /**
+ *
+ */
+ CieLab &operator=(const CieLab &other)
+ {
+ init();
+ C = other.C;
+ L = other.L;
+ A = other.A;
+ B = other.B;
+ return *this;
+ }
+
+ /**
+ *
+ */
+ virtual ~CieLab()
+ = default;
+
+ /**
+ * Retrieve a CieLab value via index.
+ */
+ virtual float operator()(unsigned int index)
+ {
+ if (index==0) return L;
+ else if (index==1) return A;
+ else if (index==2) return B;
+ else return 0;
+ }
+
+
+ /**
+ *
+ */
+ virtual void add(const CieLab &other)
+ {
+ C += other.C;
+ L += other.L;
+ A += other.A;
+ B += other.B;
+ }
+
+
+ /**
+ *
+ */
+ virtual void mul(float scale)
+ {
+ L *= scale;
+ A *= scale;
+ B *= scale;
+ }
+
+
+ /**
+ *
+ */
+ virtual unsigned long toRGB();
+
+ /**
+ * Approximate cube roots
+ */
+ double cbrt(double x);
+
+ /**
+ *
+ */
+ double qnrt(double x);
+
+ /**
+ * Raise to the 2.4 power
+ */
+ double pow24(double x);
+
+ /**
+ * Squared Euclidian distance between this and another color
+ */
+ float diffSq(const CieLab &other);
+
+ /**
+ * Computes squared euclidian distance in CieLab space for two colors
+ * given as RGB values.
+ */
+ static float diffSq(unsigned int rgb1, unsigned int rgb2);
+
+ /**
+ * Computes squared euclidian distance in CieLab space for two colors
+ * given as RGB values.
+ */
+ static float diff(unsigned int rgb0, unsigned int rgb1);
+
+
+ unsigned int C;
+ float L;
+ float A;
+ float B;
+
+private:
+
+ /**
+ *
+ */
+ void init();
+
+
+};
+
+
+//########################################################################
+//# S I O X I M A G E
+//########################################################################
+
+/**
+ * This is a generic image type that provides a consistent interface
+ * to Siox, so that developers will not need to worry about data arrays.
+ */
+class SioxImage
+{
+public:
+
+ /**
+ * Create an image with the given width and height
+ */
+ SioxImage(unsigned int width, unsigned int height);
+
+ /**
+ * Copy constructor
+ */
+ SioxImage(const SioxImage &other);
+
+ /**
+ * Assignment
+ */
+ SioxImage &operator=(const SioxImage &other);
+
+ /**
+ * Clean up after use.
+ */
+ virtual ~SioxImage();
+
+ /**
+ * Returns true if the previous operation on this image
+ * was successful, else false.
+ */
+ virtual bool isValid();
+
+ /**
+ * Sets whether an operation was successful, and whether
+ * this image should be considered a valid one.
+ * was successful, else false.
+ */
+ virtual void setValid(bool val);
+
+ /**
+ * Set a pixel at the x,y coordinates to the given value.
+ * If the coordinates are out of range, do nothing.
+ */
+ virtual void setPixel(unsigned int x,
+ unsigned int y,
+ unsigned int pixval);
+
+ /**
+ * Set a pixel at the x,y coordinates to the given r, g, b values.
+ * If the coordinates are out of range, do nothing.
+ */
+ virtual void setPixel(unsigned int x, unsigned int y,
+ unsigned int a,
+ unsigned int r,
+ unsigned int g,
+ unsigned int b);
+
+ /**
+ * Get a pixel at the x,y coordinates given. If
+ * the coordinates are out of range, return 0
+ */
+ virtual unsigned int getPixel(unsigned int x, unsigned int y);
+
+
+ /**
+ * Return the image data buffer
+ */
+ virtual unsigned int *getImageData();
+
+ /**
+ * Set a confidence value at the x,y coordinates to the given value.
+ * If the coordinates are out of range, do nothing.
+ */
+ virtual void setConfidence(unsigned int x,
+ unsigned int y,
+ float conf);
+
+ /**
+ * Get a confidence value at the x,y coordinates given. If
+ * the coordinates are out of range, return 0
+ */
+ virtual float getConfidence(unsigned int x, unsigned int y);
+
+ /**
+ * Return the confidence data buffer
+ */
+ virtual float *getConfidenceData();
+
+ /**
+ * Return the width of this image
+ */
+ virtual int getWidth();
+
+ /**
+ * Return the height of this image
+ */
+ virtual int getHeight();
+
+ /**
+ * Saves this image as a simple color PPM
+ */
+ bool writePPM(const std::string &fileName);
+
+
+
+#ifdef HAVE_GLIB
+
+ /**
+ * Special constructor to create an image from a GdkPixbuf.
+ */
+ SioxImage(GdkPixbuf *buf);
+
+ /**
+ * Creates a GdkPixbuf from this image. The user must
+ * remember to destroy the image when no longer needed.
+ * with g_free(pixbuf)
+ */
+ GdkPixbuf *getGdkPixbuf();
+
+#endif
+
+private:
+
+ SioxImage()
+ = default;
+
+ /**
+ * Assign values to that of another
+ */
+ void assign(const SioxImage &other);
+
+ /**
+ * Initialize values. Used by constructors
+ */
+ void init(unsigned int width, unsigned int height);
+
+ bool valid;
+
+ unsigned int width;
+
+ unsigned int height;
+
+ unsigned long imageSize;
+
+ /**
+ * Pixel data
+ */
+ unsigned int *pixdata;
+
+ /**
+ * Confidence matrix data
+ */
+ float *cmdata;
+
+private:
+
+ /**
+ * Error logging
+ */
+ void error(const char *fmt, ...) G_GNUC_PRINTF(2,3);
+
+};
+
+
+
+//########################################################################
+//# S I O X O B S E R V E R
+//########################################################################
+class Siox;
+
+/**
+ * This is a class for observing the progress of a Siox engine. Overload
+ * the methods in your subclass to get the desired behaviour.
+ */
+class SioxObserver
+{
+public:
+
+ /**
+ * Constructor. Context can point to anything, and is usually
+ * used to point to a C++ object or C state object, to delegate
+ * callback processing to something else. Use NULL to ignore.
+ */
+ SioxObserver(void *contextArg) : context(nullptr)
+ { context = contextArg; }
+
+ /**
+ * Destructor
+ */
+ virtual ~SioxObserver()
+ = default;
+
+ /**
+ * Informs the observer how much has been completed.
+ * Return false if the processing should be aborted.
+ */
+ virtual bool progress(float /*percentCompleted*/)
+ {
+ return true;
+ }
+
+ /**
+ * Send an error string to the Observer. Processing will
+ * be halted.
+ */
+ virtual void error(const std::string &/*msg*/)
+ {
+ }
+
+protected:
+
+ void *context;
+
+};
+
+
+
+//########################################################################
+//# S I O X
+//########################################################################
+
+/**
+ *
+ */
+class Siox
+{
+public:
+
+ /**
+ * Confidence corresponding to a certain foreground region (equals one).
+ */
+ static const float CERTAIN_FOREGROUND_CONFIDENCE; //=1.0f;
+
+ /**
+ * Confidence for a region likely being foreground.
+ */
+ static const float FOREGROUND_CONFIDENCE; //=0.8f;
+
+ /**
+ * Confidence for foreground or background type being equally likely.
+ */
+ static const float UNKNOWN_REGION_CONFIDENCE; //=0.5f;
+
+ /**
+ * Confidence for a region likely being background.
+ */
+ static const float BACKGROUND_CONFIDENCE; //=0.1f;
+
+ /**
+ * Confidence corresponding to a certain background reagion (equals zero).
+ */
+ static const float CERTAIN_BACKGROUND_CONFIDENCE; //=0.0f;
+
+ /**
+ * Construct a Siox engine
+ */
+ Siox();
+
+ /**
+ * Construct a Siox engine. Use null to ignore
+ */
+ Siox(SioxObserver *observer);
+
+ /**
+ *
+ */
+ virtual ~Siox();
+
+ /**
+ * Extract the foreground of the original image, according
+ * to the values in the confidence matrix. If the operation fails,
+ * sioxImage.isValid() will be false.
+ * backgroundFillColor is any ARGB color, such as 0xffffff (white)
+ * or 0x000000 (black)
+ */
+ virtual SioxImage extractForeground(const SioxImage &originalImage,
+ unsigned int backgroundFillColor);
+
+private:
+
+ SioxObserver *sioxObserver;
+
+ /**
+ * Progress reporting
+ */
+ bool progressReport(float percentCompleted);
+
+ /**
+ * Flag this as false during processing to abort
+ */
+ bool keepGoing;
+
+ /**
+ * Image width
+ */
+ unsigned int width;
+
+ /**
+ * Image height
+ */
+ unsigned int height;
+
+ /**
+ * Image size in pixels
+ */
+ unsigned long pixelCount;
+
+ /**
+ * Image data
+ */
+ unsigned int *image;
+
+ /**
+ * Image confidence matrix
+ */
+ float *cm;
+
+ /**
+ * 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();
+
+ /**
+ * Clean up any debris from processing.
+ */
+ void cleanup();
+
+ /**
+ * Error logging
+ */
+ void error(const char *fmt, ...) G_GNUC_PRINTF(2,3);
+
+ /**
+ * Trace logging
+ */
+ void trace(const char *fmt, ...) G_GNUC_PRINTF(2,3);
+
+ /**
+ * Stage 1 of the color signature work. 'dims' will be either
+ * 2 for grays, or 3 for colors
+ */
+ void colorSignatureStage1(CieLab *points,
+ unsigned int leftBase,
+ unsigned int rightBase,
+ unsigned int recursionDepth,
+ unsigned int *clusters,
+ const unsigned int dims);
+
+ /**
+ * Stage 2 of the color signature work
+ */
+ void colorSignatureStage2(CieLab *points,
+ unsigned int leftBase,
+ unsigned int rightBase,
+ unsigned int recursionDepth,
+ unsigned int *clusters,
+ const float threshold,
+ const unsigned int dims);
+
+ /**
+ * Main color signature method
+ */
+ bool colorSignature(const std::vector<CieLab> &inputVec,
+ std::vector<CieLab> &result,
+ const unsigned int dims);
+
+
+ /**
+ *
+ */
+ void keepOnlyLargeComponents(float threshold,
+ double sizeFactorToKeep);
+
+ /**
+ *
+ */
+ int depthFirstSearch(int startPos, float threshold, int curLabel);
+
+
+ /**
+ *
+ */
+ void fillColorRegions();
+
+ /**
+ * 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);
+
+ /**
+ * Applies the morphological erode operator.
+ */
+ void erode(float *cm, int xres, int yres);
+
+ /**
+ * Normalizes the matrix to values to [0..1].
+ */
+ void normalizeMatrix(float *cm, int cmSize);
+
+ /**
+ * Multiplies matrix with the given scalar.
+ */
+ void premultiplyMatrix(float alpha, float *cm, int cmSize);
+
+ /**
+ * Blurs confidence matrix with a given symmetrically weighted kernel.
+ */
+ void smooth(float *cm, int xres, int yres,
+ float f1, float f2, float f3);
+
+ /**
+ * Squared Euclidian distance of p and q.
+ */
+ float sqrEuclidianDist(float *p, int pSize, float *q);
+
+};
+
+
+
+
+} // namespace siox
+} // namespace org
+
+#endif // SEEN_SIOX_H
+//########################################################################
+//# E N D O F F I L E
+//########################################################################
diff --git a/src/trace/trace.cpp b/src/trace/trace.cpp
new file mode 100644
index 0000000..4ffff86
--- /dev/null
+++ b/src/trace/trace.cpp
@@ -0,0 +1,613 @@
+// 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
+ *
+ * Copyright (C) 2004-2006 Bob Jamison
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+
+#include "trace/potrace/inkscape-potrace.h"
+
+#include "inkscape.h"
+#include "desktop.h"
+
+#include "document.h"
+#include "document-undo.h"
+#include "message-stack.h"
+#include <glibmm/i18n.h>
+#include <gtkmm/main.h>
+#include "selection.h"
+#include "xml/repr.h"
+#include "xml/attribute-record.h"
+#include <2geom/transforms.h>
+#include "verbs.h"
+
+#include "display/cairo-utils.h"
+#include "display/drawing.h"
+#include "display/drawing-shape.h"
+
+#include "object/sp-item.h"
+#include "object/sp-shape.h"
+#include "object/sp-image.h"
+
+#include "siox.h"
+#include "imagemap-gdk.h"
+
+namespace Inkscape {
+namespace Trace {
+
+SPImage *Tracer::getSelectedSPImage()
+{
+
+ SPDesktop *desktop = SP_ACTIVE_DESKTOP;
+ if (!desktop)
+ {
+ g_warning("Trace: No active desktop");
+ return nullptr;
+ }
+
+ Inkscape::MessageStack *msgStack = desktop->getMessageStack();
+
+ Inkscape::Selection *sel = desktop->getSelection();
+ if (!sel)
+ {
+ char *msg = _("Select an <b>image</b> to trace");
+ msgStack->flash(Inkscape::ERROR_MESSAGE, msg);
+ //g_warning(msg);
+ return nullptr;
+ }
+
+ if (sioxEnabled)
+ {
+ SPImage *img = nullptr;
+ auto list = sel->items();
+ std::vector<SPItem *> items;
+ sioxShapes.clear();
+
+ /*
+ First, things are selected top-to-bottom, so we need to invert
+ them as bottom-to-top so that we can discover the image and any
+ SPItems above it
+ */
+ for (auto i=list.begin() ; list.end()!=i ; ++i)
+ {
+ if (!SP_IS_ITEM(*i))
+ {
+ continue;
+ }
+ SPItem *item = *i;
+ items.insert(items.begin(), item);
+ }
+ std::vector<SPItem *>::iterator iter;
+ for (iter = items.begin() ; iter!= items.end() ; ++iter)
+ {
+ SPItem *item = *iter;
+ if (SP_IS_IMAGE(item))
+ {
+ if (img) //we want only one
+ {
+ char *msg = _("Select only one <b>image</b> to trace");
+ msgStack->flash(Inkscape::ERROR_MESSAGE, msg);
+ return nullptr;
+ }
+ img = SP_IMAGE(item);
+ }
+ else // if (img) //# items -after- the image in tree (above it in Z)
+ {
+ if (SP_IS_SHAPE(item))
+ {
+ SPShape *shape = SP_SHAPE(item);
+ sioxShapes.push_back(shape);
+ }
+ }
+ }
+
+ if (!img || sioxShapes.size() < 1)
+ {
+ char *msg = _("Select one image and one or more shapes above it");
+ msgStack->flash(Inkscape::ERROR_MESSAGE, msg);
+ return nullptr;
+ }
+ return img;
+ }
+ else
+ //### SIOX not enabled. We want exactly one image selected
+ {
+ SPItem *item = sel->singleItem();
+ if (!item)
+ {
+ char *msg = _("Select an <b>image</b> to trace"); //same as above
+ msgStack->flash(Inkscape::ERROR_MESSAGE, msg);
+ //g_warning(msg);
+ return nullptr;
+ }
+
+ if (!SP_IS_IMAGE(item))
+ {
+ char *msg = _("Select an <b>image</b> to trace");
+ msgStack->flash(Inkscape::ERROR_MESSAGE, msg);
+ //g_warning(msg);
+ return nullptr;
+ }
+
+ SPImage *img = SP_IMAGE(item);
+
+ return img;
+ }
+
+}
+
+
+
+typedef org::siox::SioxImage SioxImage;
+typedef org::siox::SioxObserver SioxObserver;
+typedef org::siox::Siox Siox;
+
+
+class TraceSioxObserver : public SioxObserver
+{
+public:
+
+ /**
+ *
+ */
+ TraceSioxObserver (void *contextArg) :
+ SioxObserver(contextArg)
+ {}
+
+ /**
+ *
+ */
+ ~TraceSioxObserver () override
+ = default;
+
+ /**
+ * Informs the observer how much has been completed.
+ * Return false if the processing should be aborted.
+ */
+ bool progress(float /*percentCompleted*/) override
+ {
+ //Tracer *tracer = (Tracer *)context;
+ //## Allow the GUI to update
+ Gtk::Main::iteration(false); //at least once, non-blocking
+ while( Gtk::Main::events_pending() )
+ Gtk::Main::iteration();
+ return true;
+ }
+
+ /**
+ * Send an error string to the Observer. Processing will
+ * be halted.
+ */
+ void error(const std::string &/*msg*/) override
+ {
+ //Tracer *tracer = (Tracer *)context;
+ }
+
+
+};
+
+
+
+
+
+Glib::RefPtr<Gdk::Pixbuf> Tracer::sioxProcessImage(SPImage *img, Glib::RefPtr<Gdk::Pixbuf>origPixbuf)
+{
+ if (!sioxEnabled)
+ return origPixbuf;
+
+ if (origPixbuf == lastOrigPixbuf)
+ return lastSioxPixbuf;
+
+ //g_message("siox: start");
+
+ //Convert from gdk, so a format we know. By design, the pixel
+ //format in PackedPixelMap is identical to what is needed by SIOX
+ SioxImage simage(origPixbuf->gobj());
+
+ SPDesktop *desktop = SP_ACTIVE_DESKTOP;
+ if (!desktop)
+ {
+ g_warning("%s", _("Trace: No active desktop"));
+ return Glib::RefPtr<Gdk::Pixbuf>(nullptr);
+ }
+
+ Inkscape::MessageStack *msgStack = desktop->getMessageStack();
+
+ Inkscape::Selection *sel = desktop->getSelection();
+ if (!sel)
+ {
+ char *msg = _("Select an <b>image</b> to trace");
+ msgStack->flash(Inkscape::ERROR_MESSAGE, msg);
+ //g_warning(msg);
+ return Glib::RefPtr<Gdk::Pixbuf>(nullptr);
+ }
+
+ Inkscape::DrawingItem *aImg = img->get_arenaitem(desktop->dkey);
+ //g_message("img: %d %d %d %d\n", aImg->bbox.x0, aImg->bbox.y0,
+ // aImg->bbox.x1, aImg->bbox.y1);
+
+ double width = aImg->geometricBounds()->width();
+ double height = aImg->geometricBounds()->height();
+
+ double iwidth = simage.getWidth();
+ double iheight = simage.getHeight();
+
+ double iwscale = width / iwidth;
+ double ihscale = height / iheight;
+
+ std::vector<Inkscape::DrawingItem *> arenaItems;
+ std::vector<SPShape *>::iterator iter;
+ for (iter = sioxShapes.begin() ; iter!=sioxShapes.end() ; ++iter)
+ {
+ SPItem *item = *iter;
+ Inkscape::DrawingItem *aItem = item->get_arenaitem(desktop->dkey);
+ arenaItems.push_back(aItem);
+ }
+
+ //g_message("%d arena items\n", arenaItems.size());
+
+ //PackedPixelMap *dumpMap = PackedPixelMapCreate(
+ // simage.getWidth(), simage.getHeight());
+
+ //g_message("siox: start selection");
+
+ for (int row=0 ; row<iheight ; row++)
+ {
+ double ypos = aImg->geometricBounds()->top() + ihscale * (double) row;
+ for (int col=0 ; col<simage.getWidth() ; col++)
+ {
+ //Get absolute X,Y position
+ double xpos = aImg->geometricBounds()->left() + iwscale * (double)col;
+ Geom::Point point(xpos, ypos);
+ point *= aImg->transform();
+ //point *= imgMat;
+ //point = desktop->doc2dt(point);
+ //g_message("x:%f y:%f\n", point[0], point[1]);
+ bool weHaveAHit = false;
+ std::vector<Inkscape::DrawingItem *>::iterator aIter;
+ for (aIter = arenaItems.begin() ; aIter!=arenaItems.end() ; ++aIter)
+ {
+ Inkscape::DrawingItem *arenaItem = *aIter;
+ arenaItem->drawing().update();
+ if (arenaItem->pick(point, 1.0f, 1))
+ {
+ weHaveAHit = true;
+ break;
+ }
+ }
+
+ if (weHaveAHit)
+ {
+ //g_message("hit!\n");
+ //dumpMap->setPixelLong(dumpMap, col, row, 0L);
+ simage.setConfidence(col, row,
+ Siox::UNKNOWN_REGION_CONFIDENCE);
+ }
+ else
+ {
+ //g_message("miss!\n");
+ //dumpMap->setPixelLong(dumpMap, col, row,
+ // simage.getPixel(col, row));
+ simage.setConfidence(col, row,
+ Siox::CERTAIN_BACKGROUND_CONFIDENCE);
+ }
+ }
+ }
+
+ //g_message("siox: selection done");
+
+ //dumpMap->writePPM(dumpMap, "siox1.ppm");
+ //dumpMap->destroy(dumpMap);
+
+ //## ok we have our pixel buf
+ TraceSioxObserver observer(this);
+ Siox sengine(&observer);
+ SioxImage result = sengine.extractForeground(simage, 0xffffff);
+ if (!result.isValid())
+ {
+ g_warning("%s", _("Invalid SIOX result"));
+ return Glib::RefPtr<Gdk::Pixbuf>(nullptr);
+ }
+
+ //result.writePPM("siox2.ppm");
+
+ Glib::RefPtr<Gdk::Pixbuf> newPixbuf = Glib::wrap(result.getGdkPixbuf());
+
+ //g_message("siox: done");
+
+ lastSioxPixbuf = newPixbuf;
+
+ return newPixbuf;
+}
+
+
+Glib::RefPtr<Gdk::Pixbuf> Tracer::getSelectedImage()
+{
+
+
+ SPImage *img = getSelectedSPImage();
+ if (!img)
+ return Glib::RefPtr<Gdk::Pixbuf>(nullptr);
+
+ if (!img->pixbuf)
+ return Glib::RefPtr<Gdk::Pixbuf>(nullptr);
+
+ GdkPixbuf *raw_pb = img->pixbuf->getPixbufRaw(false);
+ GdkPixbuf *trace_pb = gdk_pixbuf_copy(raw_pb);
+ if (img->pixbuf->pixelFormat() == Inkscape::Pixbuf::PF_CAIRO) {
+ convert_pixels_argb32_to_pixbuf(
+ gdk_pixbuf_get_pixels(trace_pb),
+ gdk_pixbuf_get_width(trace_pb),
+ gdk_pixbuf_get_height(trace_pb),
+ gdk_pixbuf_get_rowstride(trace_pb));
+ }
+
+ Glib::RefPtr<Gdk::Pixbuf> pixbuf = Glib::wrap(trace_pb, false);
+
+ if (sioxEnabled)
+ {
+ Glib::RefPtr<Gdk::Pixbuf> sioxPixbuf =
+ sioxProcessImage(img, pixbuf);
+ if (!sioxPixbuf)
+ {
+ return pixbuf;
+ }
+ else
+ {
+ return sioxPixbuf;
+ }
+ }
+ else
+ {
+ return pixbuf;
+ }
+
+}
+
+
+
+//#########################################################################
+//# T R A C E
+//#########################################################################
+
+void Tracer::enableSiox(bool enable)
+{
+ sioxEnabled = enable;
+}
+
+
+void Tracer::traceThread()
+{
+ //## Remember. NEVER leave this method without setting
+ //## engine back to NULL
+
+ //## Prepare our kill flag. We will watch this later to
+ //## see if the main thread wants us to stop
+ keepGoing = true;
+
+ SPDesktop *desktop = SP_ACTIVE_DESKTOP;
+ if (!desktop)
+ {
+ g_warning("Trace: No active desktop\n");
+ return;
+ }
+
+ Inkscape::MessageStack *msgStack = desktop->getMessageStack();
+
+ Inkscape::Selection *selection = desktop->getSelection();
+
+ if (!SP_ACTIVE_DOCUMENT)
+ {
+ char *msg = _("Trace: No active document");
+ msgStack->flash(Inkscape::ERROR_MESSAGE, msg);
+ //g_warning(msg);
+ engine = nullptr;
+ return;
+ }
+ SPDocument *doc = SP_ACTIVE_DOCUMENT;
+ doc->ensureUpToDate();
+
+
+ SPImage *img = getSelectedSPImage();
+ if (!img)
+ {
+ engine = nullptr;
+ return;
+ }
+
+ GdkPixbuf *trace_pb = gdk_pixbuf_copy(img->pixbuf->getPixbufRaw(false));
+ if (img->pixbuf->pixelFormat() == Inkscape::Pixbuf::PF_CAIRO) {
+ convert_pixels_argb32_to_pixbuf(
+ gdk_pixbuf_get_pixels(trace_pb),
+ gdk_pixbuf_get_width(trace_pb),
+ gdk_pixbuf_get_height(trace_pb),
+ gdk_pixbuf_get_rowstride(trace_pb));
+ }
+
+ Glib::RefPtr<Gdk::Pixbuf> pixbuf = Glib::wrap(trace_pb, false);
+
+ pixbuf = sioxProcessImage(img, pixbuf);
+
+ if (!pixbuf)
+ {
+ char *msg = _("Trace: Image has no bitmap data");
+ msgStack->flash(Inkscape::ERROR_MESSAGE, msg);
+ //g_warning(msg);
+ engine = nullptr;
+ return;
+ }
+
+ msgStack->flash(Inkscape::NORMAL_MESSAGE, _("Trace: Starting trace..."));
+ desktop->updateCanvasNow();
+
+ std::vector<TracingEngineResult> results =
+ engine->trace(pixbuf);
+ //printf("nrPaths:%d\n", results.size());
+ int nrPaths = results.size();
+
+ //### Check if we should stop
+ if (!keepGoing || nrPaths<1)
+ {
+ engine = nullptr;
+ return;
+ }
+
+ //### Get pointers to the <image> and its parent
+ //XML Tree being used directly here while it shouldn't be.
+ Inkscape::XML::Node *imgRepr = SP_OBJECT(img)->getRepr();
+ Inkscape::XML::Node *par = imgRepr->parent();
+
+ //### Get some information for the new transform()
+ double x = 0.0;
+ double y = 0.0;
+ double width = 0.0;
+ double height = 0.0;
+ double dval = 0.0;
+
+ if (sp_repr_get_double(imgRepr, "x", &dval))
+ x = dval;
+ if (sp_repr_get_double(imgRepr, "y", &dval))
+ y = dval;
+
+ if (sp_repr_get_double(imgRepr, "width", &dval))
+ width = dval;
+ if (sp_repr_get_double(imgRepr, "height", &dval))
+ height = dval;
+
+ double iwidth = (double)pixbuf->get_width();
+ double iheight = (double)pixbuf->get_height();
+
+ double iwscale = width / iwidth;
+ double ihscale = height / iheight;
+
+ Geom::Translate trans(x, y);
+ Geom::Scale scal(iwscale, ihscale);
+
+ //# Convolve scale, translation, and the original transform
+ Geom::Affine tf(scal * trans);
+ tf *= img->transform;
+
+
+ //#OK. Now let's start making new nodes
+
+ Inkscape::XML::Document *xml_doc = desktop->doc()->getReprDoc();
+ Inkscape::XML::Node *groupRepr = nullptr;
+
+ //# if more than 1, make a <g>roup of <path>s
+ if (nrPaths > 1)
+ {
+ groupRepr = xml_doc->createElement("svg:g");
+ par->addChild(groupRepr, imgRepr);
+ }
+
+ long totalNodeCount = 0L;
+
+ for (auto result : results)
+ {
+ totalNodeCount += result.getNodeCount();
+
+ Inkscape::XML::Node *pathRepr = xml_doc->createElement("svg:path");
+ pathRepr->setAttributeOrRemoveIfEmpty("style", result.getStyle());
+ pathRepr->setAttributeOrRemoveIfEmpty("d", result.getPathData());
+
+ if (nrPaths > 1)
+ groupRepr->addChild(pathRepr, nullptr);
+ else
+ par->addChild(pathRepr, imgRepr);
+
+ //### Apply the transform from the image to the new shape
+ SPObject *reprobj = doc->getObjectByRepr(pathRepr);
+ if (reprobj)
+ {
+ SPItem *newItem = SP_ITEM(reprobj);
+ newItem->doWriteTransform(tf);
+ }
+ if (nrPaths == 1)
+ {
+ selection->clear();
+ selection->add(pathRepr);
+ }
+ Inkscape::GC::release(pathRepr);
+ }
+
+ // If we have a group, then focus on, then forget it
+ if (nrPaths > 1)
+ {
+ selection->clear();
+ selection->add(groupRepr);
+ Inkscape::GC::release(groupRepr);
+ }
+
+ //## inform the document, so we can undo
+ DocumentUndo::done(doc, SP_VERB_SELECTION_TRACE, _("Trace bitmap"));
+
+ engine = nullptr;
+
+ char *msg = g_strdup_printf(_("Trace: Done. %ld nodes created"), totalNodeCount);
+ msgStack->flash(Inkscape::NORMAL_MESSAGE, msg);
+ g_free(msg);
+
+}
+
+
+
+
+
+void Tracer::trace(TracingEngine *theEngine)
+{
+ //Check if we are already running
+ if (engine)
+ return;
+
+ engine = theEngine;
+
+#if HAVE_THREADS
+ //Ensure that thread support is running
+ if (!Glib::thread_supported())
+ Glib::thread_init();
+
+ //Create our thread and run it
+ Glib::Thread::create(
+ sigc::mem_fun(*this, &Tracer::traceThread), false);
+#else
+ traceThread();
+#endif
+
+}
+
+
+
+
+
+void Tracer::abort()
+{
+
+ //## Inform Trace's working thread
+ keepGoing = false;
+
+ if (engine)
+ {
+ engine->abort();
+ }
+
+}
+
+
+
+} // namespace Trace
+
+} // namespace Inkscape
+
+
+//#########################################################################
+//# E N D O F F I L E
+//#########################################################################
+
diff --git a/src/trace/trace.h b/src/trace/trace.h
new file mode 100644
index 0000000..ddc4b96
--- /dev/null
+++ b/src/trace/trace.h
@@ -0,0 +1,258 @@
+// 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 SEEN_TRACE_H
+#define SEEN_TRACE_H
+
+# include <cstring>
+
+#include <glibmm/refptr.h>
+#include <gdkmm/pixbuf.h>
+#include <utility>
+#include <vector>
+
+class SPImage;
+class SPItem;
+class SPShape;
+
+namespace Inkscape {
+
+namespace Trace {
+
+
+
+/**
+ *
+ */
+class TracingEngineResult
+{
+
+public:
+
+ /**
+ *
+ */
+ TracingEngineResult(std::string theStyle,
+ std::string thePathData,
+ long theNodeCount) :
+ style(std::move(theStyle)),
+ pathData(std::move(thePathData)),
+ nodeCount(theNodeCount)
+ {}
+
+ TracingEngineResult(const TracingEngineResult &other)
+ { assign(other); }
+
+ virtual TracingEngineResult &operator=(const TracingEngineResult &other)
+ { assign(other); return *this; }
+
+
+ /**
+ *
+ */
+ virtual ~TracingEngineResult()
+ = default;
+
+
+ /**
+ *
+ */
+ std::string getStyle()
+ { return style; }
+
+ /**
+ *
+ */
+ std::string getPathData()
+ { return pathData; }
+
+ /**
+ *
+ */
+ long getNodeCount()
+ { return nodeCount; }
+
+private:
+
+ void assign(const TracingEngineResult &other)
+ {
+ style = other.style;
+ pathData = other.pathData;
+ nodeCount = other.nodeCount;
+ }
+
+ std::string style;
+
+ std::string pathData;
+
+ long nodeCount;
+
+};
+
+
+
+/**
+ * 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.
+ */
+ virtual std::vector<TracingEngineResult> trace(
+ Glib::RefPtr<Gdk::Pixbuf> /*pixbuf*/) = 0;
+
+ /**
+ * Abort the thread that is executing getPathDataFromPixbuf()
+ */
+ virtual void abort() = 0;
+
+
+
+};//class TracingEngine
+
+
+
+
+
+
+
+
+
+/**
+ * This simple class allows a generic wrapper around a given
+ * TracingEngine object. Its purpose is to provide a gateway
+ * to a variety of tracing engines, while maintaining a
+ * consistent interface.
+ */
+class Tracer
+{
+
+public:
+
+
+ /**
+ *
+ */
+ Tracer()
+ {
+ engine = nullptr;
+ sioxEnabled = false;
+ }
+
+
+
+ /**
+ *
+ */
+ ~Tracer()
+ = default;
+
+
+ /**
+ * A convenience method to allow other software to 'see' the
+ * same image that this class sees.
+ */
+ Glib::RefPtr<Gdk::Pixbuf> getSelectedImage();
+
+ /**
+ * This is the main working method. Trace the selected image, if
+ * any, and create a <path> element from it, inserting it into
+ * the current document.
+ */
+ void trace(TracingEngine *engine);
+
+
+ /**
+ * Abort the thread that is executing convertImageToPath()
+ */
+ void abort();
+
+ /**
+ * Whether we want to enable SIOX subimage selection.
+ */
+ void enableSiox(bool enable);
+
+
+private:
+
+ /**
+ * This is the single path code that is called by its counterpart above.
+ * Threaded method that does single bitmap--->path conversion.
+ */
+ void traceThread();
+
+ /**
+ * This is true during execution. Setting it to false (like abort()
+ * does) should inform the threaded code that it needs to stop
+ */
+ bool keepGoing;
+
+ /**
+ * During tracing, this is Non-null, and refers to the
+ * engine that is currently doing the tracing.
+ */
+ TracingEngine *engine;
+
+ /**
+ * Get the selected image. Also check for any SPItems over it, in
+ * case the user wants SIOX pre-processing.
+ */
+ SPImage *getSelectedSPImage();
+
+ std::vector<SPShape *> sioxShapes;
+
+ bool sioxEnabled;
+
+ /**
+ * Process a GdkPixbuf, according to which areas have been
+ * obscured in the GUI.
+ */
+ Glib::RefPtr<Gdk::Pixbuf> sioxProcessImage(SPImage *img, Glib::RefPtr<Gdk::Pixbuf> origPixbuf);
+
+ Glib::RefPtr<Gdk::Pixbuf> lastSioxPixbuf;
+ Glib::RefPtr<Gdk::Pixbuf> lastOrigPixbuf;
+
+};//class Tracer
+
+
+
+
+} // namespace Trace
+
+} // namespace Inkscape
+
+
+
+#endif // SEEN_TRACE_H
+
+//#########################################################################
+//# E N D O F F I L E
+//#########################################################################
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-01 07:55:27 +0000