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 From f26093b0c3d95f1c0c29696325e52a3b748cd881 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Mon, 23 Sep 2013 15:20:04 -0300 Subject: Bumping new version of libdepixelize (bzr r12579) --- src/libdepixelize/kopftracer2011.cpp | 51 ++++++++++++++++++++++++++++++------ 1 file changed, 43 insertions(+), 8 deletions(-) (limited to 'src/libdepixelize/kopftracer2011.cpp') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index 26ad8863b..50b12d527 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -37,7 +37,7 @@ #include "priv/colorspace.h" #include "priv/homogeneoussplines.h" #include "priv/branchless.h" -#include "priv/splines.h" +#include "priv/splines-kopf2011.h" #include "priv/iterator.h" namespace Tracer { @@ -142,6 +142,12 @@ SimplifiedVoronoi Kopf2011::_voronoi(const Glib::RefPtr &b _remove_crossing_edges_unsafe(graph, options); +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + _remove_puzzle_pattern(graph); + #ifndef NDEBUG graph.checkConsistency(); #endif @@ -309,6 +315,33 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, } } +inline +void Kopf2011::_remove_puzzle_pattern(PixelGraph &graph) +{ + if ( graph.width() < 2 || graph.height() < 2 ) + return; + + PixelGraph::iterator it = graph.begin(); + for ( int i = 0 ; i + 1 != graph.height() ; ++i ) { + PixelGraph::iterator it2 = it; + for ( int j = 0 ; j + 1 != graph.width() ; ++j ) { + // Evil pattern currently not handled correctly in SimplifiedVoronoi + if ( it2->adj.right + it2->adj.bottom + + graph.nodeBottomRight(it2)->adj.left + + graph.nodeBottomRight(it2)->adj.top == 3 ) { + // We fake a new connection =) + it2->adj.right = true; + it2->adj.bottom = true; + graph.nodeBottomRight(it2)->adj.left = true; + graph.nodeBottomRight(it2)->adj.top = true; + } + + it2 = graph.nodeRight(it2); + } + it = graph.nodeBottom(it); + } +} + inline int Heuristics::curves(const PixelGraph &graph, PixelGraph::const_iterator a, PixelGraph::const_iterator b) @@ -383,22 +416,25 @@ inline void Heuristics::SparsePixels::operator ()(const PixelGraph &graph, { 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; + { + unsigned minor = std::min(x, y); + + if ( displace > minor ) { + displace = minor; + radius = displace + 1; + } } displace = radius; - if ( x + displace >= graph.width() ) { + if ( x + displace >= unsigned(graph.width()) ) { displace = unsigned(graph.width()) - x - 1; radius = displace; } - if ( y + displace >= graph.height() ) { + if ( y + displace >= unsigned(graph.height()) ) { displace = unsigned(graph.height()) - y - 1; radius = displace; } @@ -434,7 +470,6 @@ inline void Heuristics::SparsePixels::operator ()(const PixelGraph &graph, 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); } -- cgit v1.2.3 From 4b879c238ff2f4f52ca55c68ea3f887137e5cab6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Wed, 25 Sep 2013 01:37:17 -0300 Subject: Updating libdepixelize version (bzr r12589) --- src/libdepixelize/kopftracer2011.cpp | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'src/libdepixelize/kopftracer2011.cpp') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index 50b12d527..5e6e26048 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -331,9 +331,16 @@ void Kopf2011::_remove_puzzle_pattern(PixelGraph &graph) + graph.nodeBottomRight(it2)->adj.top == 3 ) { // We fake a new connection =) it2->adj.right = true; + graph.nodeRight(it2)->adj.left = true; + it2->adj.bottom = true; + graph.nodeBottom(it2)->adj.top = true; + graph.nodeBottomRight(it2)->adj.left = true; + graph.nodeBottom(it2)->adj.right = true; + graph.nodeBottomRight(it2)->adj.top = true; + graph.nodeRight(it2)->adj.bottom = true; } it2 = graph.nodeRight(it2); -- cgit v1.2.3 From 858a1a2d5395cca9f26b32c305d8c7d1dcd3c9b4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Sat, 5 Oct 2013 23:09:30 -0300 Subject: Bumping a new release of libdepixelize (bzr r12663) --- src/libdepixelize/kopftracer2011.cpp | 54 ++++++------------------------------ 1 file changed, 8 insertions(+), 46 deletions(-) (limited to 'src/libdepixelize/kopftracer2011.cpp') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index 5e6e26048..95f91fdcb 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -86,7 +86,7 @@ Splines Kopf2011::to_voronoi(const std::string &filename, Splines Kopf2011::to_voronoi(const Glib::RefPtr &buf, const Options &options) { - return Splines(_voronoi(buf, options)); + return Splines(_voronoi(buf, options)); } Splines Kopf2011::to_splines(const std::string &filename, @@ -98,13 +98,15 @@ Splines Kopf2011::to_splines(const std::string &filename, Splines Kopf2011::to_splines(const Glib::RefPtr &buf, const Options &options) { - HomogeneousSplines splines(_voronoi(buf, options)); + HomogeneousSplines splines(_voronoi + (buf, options)); return Splines(splines, options.optimize, options.nthreads); } -template -SimplifiedVoronoi Kopf2011::_voronoi(const Glib::RefPtr &buf, - const Options &options) +template +SimplifiedVoronoi +Kopf2011::_voronoi(const Glib::RefPtr &buf, + const Options &options) { PixelGraph graph(buf); @@ -146,13 +148,7 @@ SimplifiedVoronoi Kopf2011::_voronoi(const Glib::RefPtr &b graph.checkConsistency(); #endif - _remove_puzzle_pattern(graph); - -#ifndef NDEBUG - graph.checkConsistency(); -#endif - - return SimplifiedVoronoi(graph); + return SimplifiedVoronoi(graph); } // TODO: move this function (plus connectAllNeighbors) to PixelGraph constructor @@ -315,40 +311,6 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, } } -inline -void Kopf2011::_remove_puzzle_pattern(PixelGraph &graph) -{ - if ( graph.width() < 2 || graph.height() < 2 ) - return; - - PixelGraph::iterator it = graph.begin(); - for ( int i = 0 ; i + 1 != graph.height() ; ++i ) { - PixelGraph::iterator it2 = it; - for ( int j = 0 ; j + 1 != graph.width() ; ++j ) { - // Evil pattern currently not handled correctly in SimplifiedVoronoi - if ( it2->adj.right + it2->adj.bottom - + graph.nodeBottomRight(it2)->adj.left - + graph.nodeBottomRight(it2)->adj.top == 3 ) { - // We fake a new connection =) - it2->adj.right = true; - graph.nodeRight(it2)->adj.left = true; - - it2->adj.bottom = true; - graph.nodeBottom(it2)->adj.top = true; - - graph.nodeBottomRight(it2)->adj.left = true; - graph.nodeBottom(it2)->adj.right = true; - - graph.nodeBottomRight(it2)->adj.top = true; - graph.nodeRight(it2)->adj.bottom = true; - } - - it2 = graph.nodeRight(it2); - } - it = graph.nodeBottom(it); - } -} - inline int Heuristics::curves(const PixelGraph &graph, PixelGraph::const_iterator a, PixelGraph::const_iterator b) -- cgit v1.2.3 From 1a36f75406b76a837ac8d79719a7c23f8d693fed Mon Sep 17 00:00:00 2001 From: Kris De Gussem Date: Mon, 7 Oct 2013 21:25:41 +0200 Subject: cppcheck (bzr r12669) --- src/libdepixelize/kopftracer2011.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/libdepixelize/kopftracer2011.cpp') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index 95f91fdcb..ab31d05c3 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -336,8 +336,7 @@ inline int Heuristics::curves(const PixelGraph &graph, { // There are only two values that won't be zero'ed // and one of them has the same value of prev - guintptr aux = guintptr(to_ptr(it)); - aux = (it->adj.top + guintptr aux = (it->adj.top * guintptr(to_ptr(graph.nodeTop(it)))) + (it->adj.topright * guintptr(to_ptr(graph.nodeTopRight(it)))) -- cgit v1.2.3 From 3e3246729a56694574405f5d72307f536d05dcad Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Mon, 24 Mar 2014 22:34:31 -0300 Subject: Updating libdepixelize. This update is not focused on new features, but on stability. Bugs affecting weird image sizes (single line or single row images) were fixed. A bug on algorithm that could cause wrong result of heuristics on very rare images was also fixed. The correct behaviour required storing all votes before really doing any removal and this extra work made this step of the algorithm 328% slower on one sample image. If the old *_safe function was used, the slowdown could be decreased to 7.7% on the same sample image, but current focus on Inkscape timeline is stabilization, then I'll delay performance optimization to later. Also, the affected step is only responsible for 18% (on the maximum case) of the performance. The performance tests were done using new profiling code that is disabled by default and shouldn't impact stability. (bzr r13209) --- src/libdepixelize/kopftracer2011.cpp | 415 +++++++++++++++++++++++++---------- 1 file changed, 305 insertions(+), 110 deletions(-) (limited to 'src/libdepixelize/kopftracer2011.cpp') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index ab31d05c3..e2f387c86 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -31,7 +31,6 @@ #include #endif -#include #include #include "kopftracer2011.h" #include "priv/colorspace.h" @@ -40,6 +39,11 @@ #include "priv/splines-kopf2011.h" #include "priv/iterator.h" +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 +#include +#include +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + namespace Tracer { namespace Heuristics { @@ -86,7 +90,95 @@ Splines Kopf2011::to_voronoi(const std::string &filename, Splines Kopf2011::to_voronoi(const Glib::RefPtr &buf, const Options &options) { +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + SimplifiedVoronoi voronoi + = _voronoi(buf, options); + + Glib::DateTime profiling_info[2]; + profiling_info[0] = Glib::DateTime::create_now_utc(); + + Splines ret(voronoi); + + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::Splines construction time: " + << profiling_info[1].difference(profiling_info[0]) + << std::endl; + + return ret; +#else // LIBDEPIXELIZE_PROFILE_KOPF2011 return Splines(_voronoi(buf, options)); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 +} + +Splines Kopf2011::to_grouped_voronoi(const std::string &filename, + const Options &options) +{ + return to_grouped_voronoi(Gdk::Pixbuf::create_from_file(filename), options); +} + +Splines Kopf2011::to_grouped_voronoi(const Glib::RefPtr &buf, + const Options &options) +{ +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + SimplifiedVoronoi voronoi + = _voronoi(buf, options); + + Glib::DateTime profiling_info[2]; + profiling_info[0] = Glib::DateTime::create_now_utc(); + + HomogeneousSplines splines(voronoi); + +#else // LIBDEPIXELIZE_PROFILE_KOPF2011 + HomogeneousSplines splines(_voronoi + (buf, options)); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::HomogeneousSplines<" << typeid(Precision).name() + << ">(Tracer::SimplifiedVoronoi<" << typeid(Precision).name() + << ",false>) construction time: " + << profiling_info[1].difference(profiling_info[0]) + << std::endl; + profiling_info[0] = Glib::DateTime::create_now_utc(); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + + for ( HomogeneousSplines::iterator it = splines.begin(), + end = splines.end() ; it != end ; ++it ) { + for ( HomogeneousSplines::Polygon::points_iter + it2 = it->vertices.begin(), end2 = it->vertices.end() + ; it2 != end2 ; ++it2 ) { + it2->smooth = false; + } + for ( HomogeneousSplines::Polygon::holes_iter + it2 = it->holes.begin(), end2 = it->holes.end() + ; it2 != end2 ; ++it2 ) { + for ( HomogeneousSplines::Polygon::points_iter + it3 = it2->begin(), end3 = it2->end() + ; it3 != end3 ; ++it3 ) { + it3->smooth = false; + } + } + } + +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::Kopf2011::to_grouped_voronoi internal work time: " + << profiling_info[1].difference(profiling_info[0]) + << std::endl; + profiling_info[0] = Glib::DateTime::create_now_utc(); + + Splines ret(splines, false, options.nthreads); + + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::Splines construction time: " + << profiling_info[1].difference(profiling_info[0]) + << std::endl; + + return ret; +#else // LIBDEPIXELIZE_PROFILE_KOPF2011 + return Splines(splines, false, options.nthreads); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 } Splines Kopf2011::to_splines(const std::string &filename, @@ -98,9 +190,36 @@ Splines Kopf2011::to_splines(const std::string &filename, Splines Kopf2011::to_splines(const Glib::RefPtr &buf, const Options &options) { +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + SimplifiedVoronoi voronoi + = _voronoi(buf, options); + + Glib::DateTime profiling_info[2]; + profiling_info[0] = Glib::DateTime::create_now_utc(); + + HomogeneousSplines splines(voronoi); + + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::HomogeneousSplines<" << typeid(Precision).name() + << "> construction time: " + << profiling_info[1].difference(profiling_info[0]) + << std::endl; + + profiling_info[0] = Glib::DateTime::create_now_utc(); + + Splines ret(splines, options.optimize, options.nthreads); + + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::Splines construction time: " + << profiling_info[1].difference(profiling_info[0]) + << std::endl; + + return ret; +#else // LIBDEPIXELIZE_PROFILE_KOPF2011 HomogeneousSplines splines(_voronoi (buf, options)); return Splines(splines, options.optimize, options.nthreads); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 } template @@ -108,47 +227,131 @@ SimplifiedVoronoi Kopf2011::_voronoi(const Glib::RefPtr &buf, const Options &options) { +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + Glib::DateTime profiling_info[2]; + profiling_info[0] = Glib::DateTime::create_now_utc(); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + PixelGraph graph(buf); - /*if ( !graph.width() || !graph.height() ) - return;*/ +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::PixelGraph creation time: " + << profiling_info[1].difference(profiling_info[0]) << std::endl; +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + + // gdk-pixbuf2 already checks if image size is meaningful, but asserts state + // preconditions and will be useful if gdk-pixbuf is replaced later + assert(graph.width() > 0); + assert(graph.height() > 0); #ifndef NDEBUG graph.checkConsistency(); #endif +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[0] = Glib::DateTime::create_now_utc(); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + // This step could be part of the initialization of PixelGraph // and decrease the necessary number of passes graph.connectAllNeighbors(); +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::PixelGraph::connectAllNeighbors() time: " + << profiling_info[1].difference(profiling_info[0]) << std::endl; +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + #ifndef NDEBUG graph.checkConsistency(); #endif +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[0] = Glib::DateTime::create_now_utc(); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + // This step can't be part of PixelGraph initilization without adding some // cache misses due to random access patterns that might be injected _disconnect_neighbors_with_dissimilar_colors(graph); +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::Kopf2011::" + "_disconnect_neighbors_with_dissimilar_colors(Tracer::PixelGraph) time: " + << profiling_info[1].difference(profiling_info[0]) << std::endl; +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + #ifndef NDEBUG graph.checkConsistency(); #endif - // This and below steps must be executed in separate. - // Otherwise, there will be colateral effects due to misassumption about the - // data being read. - _remove_crossing_edges_safe(graph); +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[0] = Glib::DateTime::create_now_utc(); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + + { + // edges_safe and edges_unsafe must be executed in separate. + // Otherwise, there will be colateral effects due to misassumption about + // the data being read. + PixelGraph::EdgePairContainer edges = graph.crossingEdges(); + +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::PixelGraph::crossingEdges() time: " + << profiling_info[1].difference(profiling_info[0]) << std::endl; + profiling_info[0] = Glib::DateTime::create_now_utc(); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + + _remove_crossing_edges_safe(edges); + +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::Kopf2011::_remove_crossing_edges_safe" + "(Tracer::PixelGraph) time: " + << profiling_info[1].difference(profiling_info[0]) + << std::endl; +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 #ifndef NDEBUG - graph.checkConsistency(); + graph.checkConsistency(); #endif - _remove_crossing_edges_unsafe(graph, options); +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[0] = Glib::DateTime::create_now_utc(); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + + _remove_crossing_edges_unsafe(graph, edges, options); + } + +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::Kopf2011::_remove_crossing_edges_unsafe" + "(Tracer::PixelGraph) time: " + << profiling_info[1].difference(profiling_info[0]) << std::endl; +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 #ifndef NDEBUG graph.checkConsistency(); #endif + assert(graph.crossingEdges().size() == 0); + +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + profiling_info[0] = Glib::DateTime::create_now_utc(); + + SimplifiedVoronoi ret(graph); + + profiling_info[1] = Glib::DateTime::create_now_utc(); + std::cerr << "Tracer::SimplifiedVoronoi<" << typeid(T).name() << ',' + << (adjust_splines ? "true" : "false") + << ">(Tracer::PixelGraph) construction time: " + << profiling_info[1].difference(profiling_info[0]) << std::endl; + + return ret; +#else // LIBDEPIXELIZE_PROFILE_KOPF2011 return SimplifiedVoronoi(graph); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 } // TODO: move this function (plus connectAllNeighbors) to PixelGraph constructor @@ -192,123 +395,115 @@ Kopf2011::_disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph) * * In this case the two diagonal connections can be safely removed without * affecting the final result. - * - * \TODO: It should remember/cache who are the unsafe crossing edges? */ -inline void Kopf2011::_remove_crossing_edges_safe(PixelGraph &graph) +template +void Kopf2011::_remove_crossing_edges_safe(T &container) { - if ( graph.width() < 2 || graph.height() < 2 ) - return; - - PixelGraph::iterator it = graph.begin(); - for ( int i = 0 ; i != graph.height() - 1 ; ++i, ++it ) { - for ( int j = 0 ; j != graph.width() - 1 ; ++j, ++it ) { - // this <-> right - if ( !it->adj.right ) - continue; - - // this <-> down - if ( !it->adj.bottom ) - continue; - - PixelGraph::iterator down_right = it + graph.width() + 1; - - // down_right <-> right - if ( !down_right->adj.top ) - continue; + for ( typename T::reverse_iterator it = container.rbegin(), + end = container.rend() ; it != end ; ) { + /* A | B + --+-- + C | D */ + PixelGraph::iterator a = it->first.first; + PixelGraph::iterator b = it->second.first; + PixelGraph::iterator c = it->second.second; + PixelGraph::iterator d = it->first.second; + + if ( !a->adj.right || !a->adj.bottom || !b->adj.bottom + || !c->adj.right ) { + ++it; + continue; + } - // down_right <-> down - if ( !down_right->adj.left ) - continue; + // main diagonal + a->adj.bottomright = 0; + d->adj.topleft = 0; - // main diagonal - // this <-> down_right - it->adj.bottomright = 0; - down_right->adj.topleft = 0; + // secondary diagonal + b->adj.bottomleft = 0; + c->adj.topright = 0; - // secondary diagonal - // right <-> down - (it + 1)->adj.bottomleft = 0; - (it + graph.width())->adj.topright = 0; - } + // base iterator is always past one + typename T::iterator current = --(it.base()); + ++it; + container.erase(current); } } /** * This method removes crossing edges using the heuristics. */ -inline -void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, +template +void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, T &edges, const Options &options) { - if ( graph.width() < 2 || graph.height() < 2 ) - return; - - // Iterate over the graph, 2x2 blocks at time - PixelGraph::iterator it = graph.begin(); - for (int i = 0 ; i != graph.height() - 1 ; ++i, ++it ) { - for ( int j = 0 ; j != graph.width() - 1 ; ++j, ++it ) { - using std::pair; - using std::make_pair; - - typedef pair Edge; - typedef pair EdgeWeight; - - EdgeWeight diagonals[2] = { - make_pair(make_pair(it, graph.nodeBottomRight(it)), 0), - make_pair(make_pair(graph.nodeRight(it), graph.nodeBottom(it)), - 0) - }; - - // Check if there are crossing edges - if ( !diagonals[0].first.first->adj.bottomright - || !diagonals[1].first.first->adj.bottomleft ) { - continue; - } - - // Compute weights - for ( int i = 0 ; i != 2 ; ++i ) { - // Curves and islands heuristics - PixelGraph::const_iterator a = diagonals[i].first.first; - PixelGraph::const_iterator b = diagonals[i].first.second; - - diagonals[i].second += Heuristics::curves(graph, a, b) - * options.curvesMultiplier; - - diagonals[i].second += Heuristics::islands(a, b) - * options.islandsWeight; - } - - { - // Sparse pixels heuristic - Heuristics::SparsePixels sparse_pixels; - - for ( int i = 0 ; i != 2 ; ++i ) - sparse_pixels.diagonals[i] = diagonals[i]; - - sparse_pixels(graph, options.sparsePixelsRadius); - - for ( int i = 0 ; i != 2 ; ++i ) { - diagonals[i].second += sparse_pixels.diagonals[i].second - * options.sparsePixelsMultiplier; - } - } + std::vector< std::pair > weights(edges.size(), + std::make_pair(0, 0)); + + // Compute weights + for ( typename T::size_type i = 0 ; i != edges.size() ; ++i ) { + /* A | B + --+-- + C | D */ + PixelGraph::iterator a = edges[i].first.first; + PixelGraph::iterator b = edges[i].second.first; + PixelGraph::iterator c = edges[i].second.second; + PixelGraph::iterator d = edges[i].first.second; + + // Curves heuristic + weights[i].first += Heuristics::curves(graph, a, d) + * options.curvesMultiplier; + weights[i].second += Heuristics::curves(graph, b, c) + * options.curvesMultiplier; + + // Islands heuristic + weights[i].first += Heuristics::islands(a, d) * options.islandsWeight; + weights[i].second += Heuristics::islands(b, c) * options.islandsWeight; + + // Sparse pixels heuristic + using Heuristics::SparsePixels; + SparsePixels sparse_pixels; + + sparse_pixels.diagonals[SparsePixels::MAIN_DIAGONAL].first + = edges[i].first; + sparse_pixels.diagonals[SparsePixels::SECONDARY_DIAGONAL].first + = edges[i].second; + + sparse_pixels(graph, options.sparsePixelsRadius); + + weights[i].first + += sparse_pixels.diagonals[SparsePixels::MAIN_DIAGONAL].second + * options.sparsePixelsMultiplier; + weights[i].second + += sparse_pixels.diagonals[SparsePixels::SECONDARY_DIAGONAL].second + * options.sparsePixelsMultiplier; + } - // Remove edges with lower weight - if ( diagonals[0].second > diagonals[1].second ) { - diagonals[1].first.first->adj.bottomleft = 0; - diagonals[1].first.second->adj.topright = 0; - } else if ( diagonals[0].second < diagonals[1].second ) { - diagonals[0].first.first->adj.bottomright = 0; - diagonals[0].first.second->adj.topleft = 0; - } else { - diagonals[0].first.first->adj.bottomright = 0; - diagonals[0].first.second->adj.topleft = 0; - diagonals[1].first.first->adj.bottomleft = 0; - diagonals[1].first.second->adj.topright = 0; - } + // Remove edges with lower weight + for ( typename T::size_type i = 0 ; i != edges.size() ; ++i ) { + /* A | B + --+-- + C | D */ + PixelGraph::iterator a = edges[i].first.first; + PixelGraph::iterator b = edges[i].second.first; + PixelGraph::iterator c = edges[i].second.second; + PixelGraph::iterator d = edges[i].first.second; + + if ( weights[i].first > weights[i].second ) { + b->adj.bottomleft = 0; + c->adj.topright = 0; + } else if ( weights[i].first < weights[i].second ) { + a->adj.bottomright = 0; + d->adj.topleft = 0; + } else { + a->adj.bottomright = 0; + b->adj.bottomleft = 0; + c->adj.topright = 0; + d->adj.topleft = 0; } } + + edges.clear(); } inline int Heuristics::curves(const PixelGraph &graph, -- cgit v1.2.3