From dd18c27c36c9138bc68161ad365bfc61b8d135f8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Thu, 12 Sep 2013 07:23:11 -0300 Subject: Integrating with libdepixelize (bzr r12506.1.1) --- src/libdepixelize/kopftracer2011.cpp | 433 +++++++++++++++++++++++++++++++++++ 1 file changed, 433 insertions(+) create mode 100644 src/libdepixelize/kopftracer2011.cpp (limited to 'src/libdepixelize/kopftracer2011.cpp') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp new file mode 100644 index 000000000..96a415f2c --- /dev/null +++ b/src/libdepixelize/kopftracer2011.cpp @@ -0,0 +1,433 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + GNU Lesser General Public License Usage + This library is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by the + Free Software Foundation; either version 2.1 of the License, or (at your + option) any later version. + You should have received a copy of the GNU Lesser General Public License + along with this library. If not, see . + + GNU General Public License Usage + Alternatively, this library may be used under the terms of the GNU General + Public License as published by the Free Software Foundation, either version + 2 of the License, or (at your option) any later version. + You should have received a copy of the GNU General Public License along with + this library. If not, see . + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. +*/ + +#ifdef HAVE_CONFIG_H +# include +#endif + +// Build fix under Inkscape build tree +#if GLIBMM_DISABLE_DEPRECATED && HAVE_GLIBMM_THREADS_H +#include +#endif + +#include +#include +#include "kopftracer2011.h" +#include "priv/colorspace.h" +#include "priv/homogeneoussplines.h" +#include "priv/branchless.h" +#include "priv/splines.h" + +namespace Tracer { +namespace Heuristics { + +int curves(PixelGraph &graph, PixelGraph::Node *a, PixelGraph::Node *b); +bool islands(PixelGraph &graph, PixelGraph::Node *a, PixelGraph::Node *b); + +struct SparsePixels +{ + typedef std::pair Edge; + typedef std::pair EdgeWeight; + + void operator()(PixelGraph &graph, unsigned radius); + + static bool similar_colors(PixelGraph::Node *n, Edge edge); + + EdgeWeight diagonals[2]; +}; + +} // namespace Heuristics + +Splines Kopf2011::to_voronoi(const std::string &filename, + const Options &options) +{ + return to_voronoi(Gdk::Pixbuf::create_from_file(filename), options); +} + +Splines Kopf2011::to_voronoi(const Glib::RefPtr &buf, + const Options &options) +{ + return Splines(_voronoi(buf, options)); +} + +Splines Kopf2011::to_splines(const std::string &filename, + const Options &options) +{ + return to_splines(Gdk::Pixbuf::create_from_file(filename), options); +} + +Splines Kopf2011::to_splines(const Glib::RefPtr &buf, + const Options &options) +{ + HomogeneousSplines splines(_voronoi(buf, options)); + return Splines(splines, options.optimize, options.nthreads); +} + +template +SimplifiedVoronoi Kopf2011::_voronoi(const Glib::RefPtr &buf, + const Options &options) +{ + PixelGraph graph(buf); + + /*if ( !graph.width() || !graph.height() ) + return;*/ + +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + // This step could be part of the initialization of PixelGraph + // and decrease the necessary number of passes + graph.connectAllNeighbors(); + +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + // This step can't be part of PixelGraph initilization without adding some + // cache misses due to random access patterns that might be injected + _disconnect_neighbors_with_dissimilar_colors(graph); + +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + // This and below steps must be executed in separate. + // Otherwise, there will be colateral effects due to misassumption about the + // data being read. + _remove_crossing_edges_safe(graph); + +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + _remove_crossing_edges_unsafe(graph, options); + +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + return SimplifiedVoronoi(graph); +} + +// TODO: move this function (plus connectAllNeighbors) to PixelGraph constructor +inline void +Kopf2011::_disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph) +{ + using colorspace::similar_colors; + for ( PixelGraph::iterator it = graph.begin(), end = graph.end() ; it != end + ; ++it ) { + if ( it->adj.top ) + it->adj.top = similar_colors(it->rgba, (it - graph.width())->rgba); + if ( it->adj.topright ) { + it->adj.topright + = similar_colors(it->rgba, (it - graph.width() + 1)->rgba); + } + if ( it->adj.right ) + it->adj.right = similar_colors(it->rgba, (it + 1)->rgba); + if ( it->adj.bottomright ) { + it->adj.bottomright + = similar_colors(it->rgba, (it + graph.width() + 1)->rgba); + } + if ( it->adj.bottom ) { + it->adj.bottom + = similar_colors(it->rgba, (it + graph.width())->rgba); + } + if ( it->adj.bottomleft ) { + it->adj.bottomleft + = similar_colors(it->rgba, (it + graph.width() - 1)->rgba); + } + if ( it->adj.left ) + it->adj.left = similar_colors(it->rgba, (it - 1)->rgba); + if ( it->adj.topleft ) { + it->adj.topleft = similar_colors(it->rgba, + (it - graph.width() - 1)->rgba); + } + } +} + +/** + * This method removes crossing edges if the 2x2 block is fully connected. + * + * In this case the two diagonal connections can be safely removed without + * affecting the final result. + * + * \TODO: It should remember/cache who are the unsafe crossing edges? + */ +inline void Kopf2011::_remove_crossing_edges_safe(PixelGraph &graph) +{ + if ( graph.width() < 2 || graph.height() < 2 ) + return; + + PixelGraph::iterator it = graph.begin(); + for ( int i = 0 ; i != graph.height() - 1 ; ++i, ++it ) { + for ( int j = 0 ; j != graph.width() - 1 ; ++j, ++it ) { + // this <-> right + if ( !it->adj.right ) + continue; + + // this <-> down + if ( !it->adj.bottom ) + continue; + + PixelGraph::iterator down_right = it + graph.width() + 1; + + // down_right <-> right + if ( !down_right->adj.top ) + continue; + + // down_right <-> down + if ( !down_right->adj.left ) + continue; + + // main diagonal + // this <-> down_right + it->adj.bottomright = 0; + down_right->adj.topleft = 0; + + // secondary diagonal + // right <-> down + (it + 1)->adj.bottomleft = 0; + (it + graph.width())->adj.topright = 0; + } + } +} + +/** + * This method removes crossing edges using the heuristics. + */ +inline +void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, + const Options &options) +{ + if ( graph.width() < 2 || graph.height() < 2 ) + return; + + // Iterate over the graph, 2x2 blocks at time + PixelGraph::iterator it = graph.begin(); + for (int i = 0 ; i != graph.height() - 1 ; ++i, ++it ) { + for ( int j = 0 ; j != graph.width() - 1 ; ++j, ++it ) { + using std::pair; + using std::make_pair; + + typedef pair Edge; + typedef pair EdgeWeight; + + EdgeWeight diagonals[2] = { + make_pair(make_pair(&*it, &*(it + graph.width() + 1)), 0), + make_pair(make_pair(&*(it + 1), &*(it + graph.width())), 0) + }; + + // Check if there are crossing edges + if ( !diagonals[0].first.first->adj.bottomright + || !diagonals[1].first.first->adj.bottomleft ) { + continue; + } + + // Compute weights + for ( int i = 0 ; i != 2 ; ++i ) { + // Curves and islands heuristics + PixelGraph::Node *a = diagonals[i].first.first; + PixelGraph::Node *b = diagonals[i].first.second; + + diagonals[i].second += Heuristics::curves(graph, a, b) + * options.curvesMultiplier; + + diagonals[i].second += Heuristics::islands(graph, a, b) + * options.islandsWeight; + } + + { + // Sparse pixels heuristic + Heuristics::SparsePixels sparse_pixels; + + for ( int i = 0 ; i != 2 ; ++i ) + sparse_pixels.diagonals[i] = diagonals[i]; + + sparse_pixels(graph, options.sparsePixelsRadius); + + for ( int i = 0 ; i != 2 ; ++i ) { + diagonals[i].second += sparse_pixels.diagonals[i].second + * options.sparsePixelsMultiplier; + } + } + + // Remove edges with lower weight + if ( diagonals[0].second > diagonals[1].second ) { + diagonals[1].first.first->adj.bottomleft = 0; + diagonals[1].first.second->adj.topright = 0; + } else if ( diagonals[0].second < diagonals[1].second ) { + diagonals[0].first.first->adj.bottomright = 0; + diagonals[0].first.second->adj.topleft = 0; + } else { + diagonals[0].first.first->adj.bottomright = 0; + diagonals[0].first.second->adj.topleft = 0; + diagonals[1].first.first->adj.bottomleft = 0; + diagonals[1].first.second->adj.topright = 0; + } + } + } +} + +inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a, + PixelGraph::Node *b) +{ + int count = 1; + + // b -> a + // and then a -> b + for ( int i = 0 ; i != 2 ; ++i ) { + PixelGraph::Node *it = i ? a : b; + PixelGraph::Node *prev = i ? b : a; + int local_count = 0; + + // Used to avoid inifinite loops in circular-like edges + PixelGraph::Node *const initial = it; + + while ( it->adjsize() == 2 ) { + ++local_count; + + // Iterate to next + { + // There are only two values that won't be zero'ed + // and one of them has the same value of prev + guintptr aux = guintptr(it); + aux = it->adj.top * guintptr(it - graph.width()) + + it->adj.topright * guintptr(it - graph.width() + 1) + + it->adj.right * guintptr(it + 1) + + it->adj.bottomright * guintptr(it + graph.width() + 1) + + it->adj.bottom * guintptr(it + graph.width()) + + it->adj.bottomleft * guintptr(it + graph.width() - 1) + + it->adj.left * guintptr(it - 1) + + it->adj.topleft * guintptr(it - graph.width() - 1) + - guintptr(prev); + prev = it; + it = reinterpret_cast(aux); + } + + // Break infinite loops + if ( it == initial ) + return local_count; + } + count += local_count; + } + + return count; +} + +inline void Heuristics::SparsePixels::operator ()(PixelGraph &graph, + unsigned radius) +{ + if ( !graph.width() || !graph.height() ) + return; + + // Clear weights + for ( int i = 0 ; i != 2 ; ++i ) + diagonals[i].second = 0; + + // Compute begin and end nodes under a (2*radius)^2 window + std::pair begin(0, 0); + + // Get midpoint + { + using branchless::max_consecutive; + + unsigned x1 = graph.toX(diagonals[0].first.first); + unsigned x2 = graph.toX(diagonals[0].first.second); + begin.first = max_consecutive(x1, x2); + + unsigned y1 = graph.toY(diagonals[0].first.first); + unsigned y2 = graph.toY(diagonals[0].first.second); + begin.second = max_consecutive(y1, y2); + } + + std::pair end(begin.first + radius, + begin.second + radius); + + // Get beginning point + { + using branchless::first_if; + + begin.first = first_if(begin.first - radius, 0u, begin.first >= radius); + + begin.second = first_if(begin.second - radius, 0u, + begin.second >= radius); + } + + // Fix ending point if misplaced + { + using branchless::first_if; + + end.first = first_if(unsigned(graph.width()), end.first, + end.first > graph.width()); + + end.second = first_if(unsigned(graph.height()), end.second, + end.second > graph.height()); + } + + // Iterate over nodes and count them + for ( int i = begin.second ; i != end.second ; ++i ) { + PixelGraph::Node *it = &graph[begin.first][i]; + for ( int j = begin.first ; j != end.first ; ++j, ++it ) { + for ( int k = 0 ; k != 2 ; ++k ) + diagonals[k].second += similar_colors(it, diagonals[k].first); + } + } + + int minor = branchless::min(diagonals[0].second, diagonals[1].second); + for ( int i = 0 ; i != 2 ; ++i ) + diagonals[i].second -= minor; + std::swap(diagonals[0].second, diagonals[1].second); +} + +inline bool +Heuristics::SparsePixels::similar_colors(PixelGraph::Node *n, + Heuristics::SparsePixels::Edge edge) +{ + using colorspace::similar_colors; + return (similar_colors(n->rgba, edge.first->rgba) + || similar_colors(n->rgba, edge.second->rgba)); +} + +inline bool Heuristics::islands(PixelGraph &graph, PixelGraph::Node *a, + PixelGraph::Node *b) +{ + if ( a->adjsize() == 1 || b->adjsize() == 1 ) + return true; + + return false; +} + +} // namespace Tracer + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 : -- cgit v1.2.3 From 0f397bdb1eae4d190a5a7d7a4792d0571917753b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Fri, 13 Sep 2013 04:00:18 -0300 Subject: Bumping new version of libdepixelize (bzr r12506.1.3) --- src/libdepixelize/kopftracer2011.cpp | 179 +++++++++++++++++++++-------------- 1 file changed, 108 insertions(+), 71 deletions(-) (limited to 'src/libdepixelize/kopftracer2011.cpp') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index 96a415f2c..26ad8863b 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -38,22 +38,40 @@ #include "priv/homogeneoussplines.h" #include "priv/branchless.h" #include "priv/splines.h" +#include "priv/iterator.h" namespace Tracer { namespace Heuristics { -int curves(PixelGraph &graph, PixelGraph::Node *a, PixelGraph::Node *b); -bool islands(PixelGraph &graph, PixelGraph::Node *a, PixelGraph::Node *b); +int curves(const PixelGraph &graph, PixelGraph::const_iterator a, + PixelGraph::const_iterator b); +bool islands(PixelGraph::const_iterator a, PixelGraph::const_iterator b); struct SparsePixels { - typedef std::pair Edge; + enum Diagonal { + /** + * From (first) the top left corner to (second) the bottom right. + */ + MAIN_DIAGONAL = 0, + /** + * From (first) the top right to (second) the bottom left. + */ + SECONDARY_DIAGONAL = 1 + }; + + typedef std::pair + Edge; typedef std::pair EdgeWeight; - void operator()(PixelGraph &graph, unsigned radius); + void operator()(const PixelGraph &graph, unsigned radius); - static bool similar_colors(PixelGraph::Node *n, Edge edge); + static bool similar_colors(PixelGraph::const_iterator n, + const guint8 (&a)[4], const guint8 (&b)[4]); + /* + * Precondition: Must be filled according to Diagonal enum. + */ EdgeWeight diagonals[2]; }; @@ -231,12 +249,13 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, using std::pair; using std::make_pair; - typedef pair Edge; + typedef pair Edge; typedef pair EdgeWeight; EdgeWeight diagonals[2] = { - make_pair(make_pair(&*it, &*(it + graph.width() + 1)), 0), - make_pair(make_pair(&*(it + 1), &*(it + graph.width())), 0) + make_pair(make_pair(it, graph.nodeBottomRight(it)), 0), + make_pair(make_pair(graph.nodeRight(it), graph.nodeBottom(it)), + 0) }; // Check if there are crossing edges @@ -248,13 +267,13 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, // Compute weights for ( int i = 0 ; i != 2 ; ++i ) { // Curves and islands heuristics - PixelGraph::Node *a = diagonals[i].first.first; - PixelGraph::Node *b = diagonals[i].first.second; + PixelGraph::const_iterator a = diagonals[i].first.first; + PixelGraph::const_iterator b = diagonals[i].first.second; diagonals[i].second += Heuristics::curves(graph, a, b) * options.curvesMultiplier; - diagonals[i].second += Heuristics::islands(graph, a, b) + diagonals[i].second += Heuristics::islands(a, b) * options.islandsWeight; } @@ -290,20 +309,23 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, } } -inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a, - PixelGraph::Node *b) +inline int Heuristics::curves(const PixelGraph &graph, + PixelGraph::const_iterator a, + PixelGraph::const_iterator b) { int count = 1; + ToPtr to_ptr; + ToIter to_iter(graph.begin()); // b -> a // and then a -> b for ( int i = 0 ; i != 2 ; ++i ) { - PixelGraph::Node *it = i ? a : b; - PixelGraph::Node *prev = i ? b : a; + PixelGraph::const_iterator it = i ? a : b; + PixelGraph::const_iterator prev = i ? b : a; int local_count = 0; // Used to avoid inifinite loops in circular-like edges - PixelGraph::Node *const initial = it; + const PixelGraph::const_iterator initial = it; while ( it->adjsize() == 2 ) { ++local_count; @@ -312,18 +334,26 @@ inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a, { // There are only two values that won't be zero'ed // and one of them has the same value of prev - guintptr aux = guintptr(it); - aux = it->adj.top * guintptr(it - graph.width()) - + it->adj.topright * guintptr(it - graph.width() + 1) - + it->adj.right * guintptr(it + 1) - + it->adj.bottomright * guintptr(it + graph.width() + 1) - + it->adj.bottom * guintptr(it + graph.width()) - + it->adj.bottomleft * guintptr(it + graph.width() - 1) - + it->adj.left * guintptr(it - 1) - + it->adj.topleft * guintptr(it - graph.width() - 1) - - guintptr(prev); + guintptr aux = guintptr(to_ptr(it)); + aux = (it->adj.top + * guintptr(to_ptr(graph.nodeTop(it)))) + + (it->adj.topright + * guintptr(to_ptr(graph.nodeTopRight(it)))) + + (it->adj.right + * guintptr(to_ptr(graph.nodeRight(it)))) + + (it->adj.bottomright + * guintptr(to_ptr(graph.nodeBottomRight(it)))) + + (it->adj.bottom + * guintptr(to_ptr(graph.nodeBottom(it)))) + + (it->adj.bottomleft + * guintptr(to_ptr(graph.nodeBottomLeft(it)))) + + (it->adj.left + * guintptr(to_ptr(graph.nodeLeft(it)))) + + (it->adj.topleft + * guintptr(to_ptr(graph.nodeTopLeft(it)))) + - guintptr(to_ptr(prev)); prev = it; - it = reinterpret_cast(aux); + it = to_iter(reinterpret_cast(aux)); } // Break infinite loops @@ -336,7 +366,7 @@ inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a, return count; } -inline void Heuristics::SparsePixels::operator ()(PixelGraph &graph, +inline void Heuristics::SparsePixels::operator ()(const PixelGraph &graph, unsigned radius) { if ( !graph.width() || !graph.height() ) @@ -346,72 +376,79 @@ inline void Heuristics::SparsePixels::operator ()(PixelGraph &graph, for ( int i = 0 ; i != 2 ; ++i ) diagonals[i].second = 0; - // Compute begin and end nodes under a (2*radius)^2 window - std::pair begin(0, 0); + if ( !radius ) + return; - // Get midpoint + // Fix radius/bounds { - using branchless::max_consecutive; - - unsigned x1 = graph.toX(diagonals[0].first.first); - unsigned x2 = graph.toX(diagonals[0].first.second); - begin.first = max_consecutive(x1, x2); - - unsigned y1 = graph.toY(diagonals[0].first.first); - unsigned y2 = graph.toY(diagonals[0].first.second); - begin.second = max_consecutive(y1, y2); - } - - std::pair end(begin.first + radius, - begin.second + radius); + unsigned x = graph.toX(diagonals[MAIN_DIAGONAL].first.first); + unsigned y = graph.toY(diagonals[MAIN_DIAGONAL].first.first); + unsigned minor = std::min(x, y); + unsigned displace = radius - 1; + + if ( displace > minor ) { + displace = minor; + radius = displace + 1; + } - // Get beginning point - { - using branchless::first_if; + displace = radius; - begin.first = first_if(begin.first - radius, 0u, begin.first >= radius); + if ( x + displace >= graph.width() ) { + displace = unsigned(graph.width()) - x - 1; + radius = displace; + } - begin.second = first_if(begin.second - radius, 0u, - begin.second >= radius); + if ( y + displace >= graph.height() ) { + displace = unsigned(graph.height()) - y - 1; + radius = displace; + } } - // Fix ending point if misplaced - { - using branchless::first_if; + if ( !radius ) + return; - end.first = first_if(unsigned(graph.width()), end.first, - end.first > graph.width()); + // Iterate over nodes and count them + { + PixelGraph::const_iterator it = diagonals[MAIN_DIAGONAL].first.first; + for ( unsigned i = radius - 1 ; i ; --i ) + it = graph.nodeTopLeft(it); + + bool invert = false; + for ( unsigned i = 0 ; i != 2 * radius ; ++i ) { + for ( unsigned j = 0 ; j != 2 * radius ; ++j ) { + for ( int k = 0 ; k != 2 ; ++k ) { + diagonals[k].second + += similar_colors(it, diagonals[k].first.first->rgba, + diagonals[k].first.second->rgba); + } + it = (invert ? graph.nodeLeft(it) : graph.nodeRight(it)); + } + it = (invert ? graph.nodeRight(it) : graph.nodeLeft(it)); - end.second = first_if(unsigned(graph.height()), end.second, - end.second > graph.height()); - } - // Iterate over nodes and count them - for ( int i = begin.second ; i != end.second ; ++i ) { - PixelGraph::Node *it = &graph[begin.first][i]; - for ( int j = begin.first ; j != end.first ; ++j, ++it ) { - for ( int k = 0 ; k != 2 ; ++k ) - diagonals[k].second += similar_colors(it, diagonals[k].first); + invert = !invert; + it = graph.nodeBottom(it); } } - int minor = branchless::min(diagonals[0].second, diagonals[1].second); + int minor = std::min(diagonals[0].second, diagonals[1].second); for ( int i = 0 ; i != 2 ; ++i ) diagonals[i].second -= minor; + std::swap(diagonals[0].second, diagonals[1].second); } inline bool -Heuristics::SparsePixels::similar_colors(PixelGraph::Node *n, - Heuristics::SparsePixels::Edge edge) +Heuristics::SparsePixels::similar_colors(PixelGraph::const_iterator n, + const guint8 (&a)[4], + const guint8 (&b)[4]) { using colorspace::similar_colors; - return (similar_colors(n->rgba, edge.first->rgba) - || similar_colors(n->rgba, edge.second->rgba)); + return similar_colors(n->rgba, a) || similar_colors(n->rgba, b); } -inline bool Heuristics::islands(PixelGraph &graph, PixelGraph::Node *a, - PixelGraph::Node *b) +inline bool Heuristics::islands(PixelGraph::const_iterator a, + PixelGraph::const_iterator b) { if ( a->adjsize() == 1 || b->adjsize() == 1 ) return true; -- cgit v1.2.3