diff --git a/libs/image/kis_gaussian_kernel.cpp b/libs/image/kis_gaussian_kernel.cpp index 4326558c25..29390ea21c 100644 --- a/libs/image/kis_gaussian_kernel.cpp +++ b/libs/image/kis_gaussian_kernel.cpp @@ -1,358 +1,399 @@ /* * Copyright (c) 2014 Dmitry Kazakov * * This program is free software; you can redistribute it and/or modify * it 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. * * This program 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 General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "kis_gaussian_kernel.h" #include "kis_global.h" #include "kis_convolution_kernel.h" #include #include #include qreal KisGaussianKernel::sigmaFromRadius(qreal radius) { return 0.3 * radius + 0.3; } int KisGaussianKernel::kernelSizeFromRadius(qreal radius) { return 6 * ceil(sigmaFromRadius(radius)) + 1; } Eigen::Matrix KisGaussianKernel::createHorizontalMatrix(qreal radius) { int kernelSize = kernelSizeFromRadius(radius); Eigen::Matrix matrix(1, kernelSize); const qreal sigma = sigmaFromRadius(radius); const qreal multiplicand = 1 / (sqrt(2 * M_PI * sigma * sigma)); const qreal exponentMultiplicand = 1 / (2 * sigma * sigma); /** * The kernel size should always be odd, then the position of the * central pixel can be easily calculated */ KIS_ASSERT_RECOVER_NOOP(kernelSize & 0x1); const int center = kernelSize / 2; for (int x = 0; x < kernelSize; x++) { qreal xDistance = center - x; matrix(0, x) = multiplicand * exp( -xDistance * xDistance * exponentMultiplicand ); } return matrix; } Eigen::Matrix KisGaussianKernel::createVerticalMatrix(qreal radius) { int kernelSize = kernelSizeFromRadius(radius); Eigen::Matrix matrix(kernelSize, 1); const qreal sigma = sigmaFromRadius(radius); const qreal multiplicand = 1 / (sqrt(2 * M_PI * sigma * sigma)); const qreal exponentMultiplicand = 1 / (2 * sigma * sigma); /** * The kernel size should always be odd, then the position of the * central pixel can be easily calculated */ KIS_ASSERT_RECOVER_NOOP(kernelSize & 0x1); const int center = kernelSize / 2; for (int y = 0; y < kernelSize; y++) { qreal yDistance = center - y; matrix(y, 0) = multiplicand * exp( -yDistance * yDistance * exponentMultiplicand ); } return matrix; } KisConvolutionKernelSP KisGaussianKernel::createHorizontalKernel(qreal radius) { Eigen::Matrix matrix = createHorizontalMatrix(radius); return KisConvolutionKernel::fromMatrix(matrix, 0, matrix.sum()); } KisConvolutionKernelSP KisGaussianKernel::createVerticalKernel(qreal radius) { Eigen::Matrix matrix = createVerticalMatrix(radius); return KisConvolutionKernel::fromMatrix(matrix, 0, matrix.sum()); } KisConvolutionKernelSP KisGaussianKernel::createUniform2DKernel(qreal xRadius, qreal yRadius) { Eigen::Matrix h = createHorizontalMatrix(xRadius); Eigen::Matrix v = createVerticalMatrix(yRadius); Eigen::Matrix uni = v * h; return KisConvolutionKernel::fromMatrix(uni, 0, uni.sum()); } void KisGaussianKernel::applyGaussian(KisPaintDeviceSP device, const QRect& rect, qreal xRadius, qreal yRadius, const QBitArray &channelFlags, KoUpdater *progressUpdater, bool createTransaction) { QPoint srcTopLeft = rect.topLeft(); if (KisConvolutionPainter::supportsFFTW()) { KisConvolutionPainter painter(device, KisConvolutionPainter::FFTW); painter.setChannelFlags(channelFlags); painter.setProgress(progressUpdater); KisConvolutionKernelSP kernel2D = KisGaussianKernel::createUniform2DKernel(xRadius, yRadius); QScopedPointer transaction; if (createTransaction && painter.needsTransaction(kernel2D)) { transaction.reset(new KisTransaction(device)); } painter.applyMatrix(kernel2D, device, srcTopLeft, srcTopLeft, rect.size(), BORDER_REPEAT); } else if (xRadius > 0.0 && yRadius > 0.0) { KisPaintDeviceSP interm = new KisPaintDevice(device->colorSpace()); KisConvolutionKernelSP kernelHoriz = KisGaussianKernel::createHorizontalKernel(xRadius); KisConvolutionKernelSP kernelVertical = KisGaussianKernel::createVerticalKernel(yRadius); qreal verticalCenter = qreal(kernelVertical->height()) / 2.0; KisConvolutionPainter horizPainter(interm); horizPainter.setChannelFlags(channelFlags); horizPainter.setProgress(progressUpdater); horizPainter.applyMatrix(kernelHoriz, device, srcTopLeft - QPoint(0, ceil(verticalCenter)), srcTopLeft - QPoint(0, ceil(verticalCenter)), rect.size() + QSize(0, 2 * ceil(verticalCenter)), BORDER_REPEAT); KisConvolutionPainter verticalPainter(device); verticalPainter.setChannelFlags(channelFlags); verticalPainter.setProgress(progressUpdater); verticalPainter.applyMatrix(kernelVertical, interm, srcTopLeft, srcTopLeft, rect.size(), BORDER_REPEAT); } else if (xRadius > 0.0) { KisConvolutionPainter painter(device); painter.setChannelFlags(channelFlags); painter.setProgress(progressUpdater); KisConvolutionKernelSP kernelHoriz = KisGaussianKernel::createHorizontalKernel(xRadius); QScopedPointer transaction; if (createTransaction && painter.needsTransaction(kernelHoriz)) { transaction.reset(new KisTransaction(device)); } painter.applyMatrix(kernelHoriz, device, srcTopLeft, srcTopLeft, rect.size(), BORDER_REPEAT); } else if (yRadius > 0.0) { KisConvolutionPainter painter(device); painter.setChannelFlags(channelFlags); painter.setProgress(progressUpdater); KisConvolutionKernelSP kernelVertical = KisGaussianKernel::createVerticalKernel(yRadius); QScopedPointer transaction; if (createTransaction && painter.needsTransaction(kernelVertical)) { transaction.reset(new KisTransaction(device)); } painter.applyMatrix(kernelVertical, device, srcTopLeft, srcTopLeft, rect.size(), BORDER_REPEAT); } } Eigen::Matrix -KisGaussianKernel::createLoGMatrix(qreal radius, qreal coeff) +KisGaussianKernel::createLoGMatrix(qreal radius, qreal coeff, bool zeroCentered, bool includeWrappedArea) { - int kernelSize = 4 * std::ceil(radius) + 1; + int kernelSize = 2 * (includeWrappedArea ? 2 : 1) * std::ceil(radius) + 1; Eigen::Matrix matrix(kernelSize, kernelSize); const qreal sigma = radius/* / sqrt(2)*/; const qreal multiplicand = -1.0 / (M_PI * pow2(pow2(sigma))); const qreal exponentMultiplicand = 1 / (2 * pow2(sigma)); /** * The kernel size should always be odd, then the position of the * central pixel can be easily calculated */ KIS_ASSERT_RECOVER_NOOP(kernelSize & 0x1); const int center = kernelSize / 2; for (int y = 0; y < kernelSize; y++) { const qreal yDistance = center - y; for (int x = 0; x < kernelSize; x++) { const qreal xDistance = center - x; const qreal distance = pow2(xDistance) + pow2(yDistance); const qreal normalizedDistance = exponentMultiplicand * distance; matrix(x, y) = multiplicand * (1.0 - normalizedDistance) * exp(-normalizedDistance); } } qreal lateral = matrix.sum() - matrix(center, center); matrix(center, center) = -lateral; + qreal totalSum = 0; + + if (zeroCentered) { + for (int y = 0; y < kernelSize; y++) { + for (int x = 0; x < kernelSize; x++) { + const qreal value = matrix(x, y); + totalSum += value; + } + } + } + qreal positiveSum = 0; qreal sideSum = 0; qreal quarterSum = 0; + totalSum = 0; + + const qreal offset = totalSum / pow2(qreal(kernelSize)); for (int y = 0; y < kernelSize; y++) { for (int x = 0; x < kernelSize; x++) { - const qreal value = matrix(x, y); + qreal value = matrix(x, y); + value -= offset; + matrix(x, y) = value; + if (value > 0) { positiveSum += value; } if (x > center) { sideSum += value; } if (x > center && y > center) { quarterSum += value; } + totalSum += value; } } const qreal scale = coeff * 2.0 / positiveSum; matrix *= scale; positiveSum *= scale; sideSum *= scale; quarterSum *= scale; //qDebug() << ppVar(positiveSum) << ppVar(sideSum) << ppVar(quarterSum); return matrix; } void KisGaussianKernel::applyLoG(KisPaintDeviceSP device, const QRect& rect, qreal radius, qreal coeff, const QBitArray &channelFlags, KoUpdater *progressUpdater) { QPoint srcTopLeft = rect.topLeft(); KisConvolutionPainter painter(device); painter.setChannelFlags(channelFlags); painter.setProgress(progressUpdater); - Eigen::Matrix matrix = createLoGMatrix(radius, coeff); + Eigen::Matrix matrix = + createLoGMatrix(radius, coeff, false, true); + KisConvolutionKernelSP kernel = + KisConvolutionKernel::fromMatrix(matrix, + 0, + 0); + + painter.applyMatrix(kernel, device, srcTopLeft, srcTopLeft, rect.size(), BORDER_REPEAT); +} + +void KisGaussianKernel::applyTightLoG(KisPaintDeviceSP device, + const QRect& rect, + qreal radius, qreal coeff, + const QBitArray &channelFlags, + KoUpdater *progressUpdater) +{ + QPoint srcTopLeft = rect.topLeft(); + + KisConvolutionPainter painter(device); + painter.setChannelFlags(channelFlags); + painter.setProgress(progressUpdater); + + Eigen::Matrix matrix = + createLoGMatrix(radius, coeff, true, false); KisConvolutionKernelSP kernel = KisConvolutionKernel::fromMatrix(matrix, 0, 0); painter.applyMatrix(kernel, device, srcTopLeft, srcTopLeft, rect.size(), BORDER_REPEAT); } Eigen::Matrix KisGaussianKernel::createDilateMatrix(qreal radius) { const int kernelSize = 2 * std::ceil(radius) + 1; Eigen::Matrix matrix(kernelSize, kernelSize); const qreal fadeStart = qMax(1.0, radius - 1.0); /** * The kernel size should always be odd, then the position of the * central pixel can be easily calculated */ KIS_ASSERT_RECOVER_NOOP(kernelSize & 0x1); const int center = kernelSize / 2; for (int y = 0; y < kernelSize; y++) { const qreal yDistance = center - y; for (int x = 0; x < kernelSize; x++) { const qreal xDistance = center - x; const qreal distance = std::sqrt(pow2(xDistance) + pow2(yDistance)); qreal value = 1.0; if (distance >= radius) { value = 0.0; } else if (distance > fadeStart) { value = radius - distance; } matrix(x, y) = value; } } return matrix; } void KisGaussianKernel::applyDilate(KisPaintDeviceSP device, const QRect &rect, qreal radius, const QBitArray &channelFlags, KoUpdater *progressUpdater, bool createTransaction) { KIS_SAFE_ASSERT_RECOVER_RETURN(device->colorSpace()->pixelSize() == 1); QPoint srcTopLeft = rect.topLeft(); KisConvolutionPainter painter(device); painter.setChannelFlags(channelFlags); painter.setProgress(progressUpdater); Eigen::Matrix matrix = createDilateMatrix(radius); KisConvolutionKernelSP kernel = KisConvolutionKernel::fromMatrix(matrix, 0, 1.0); QScopedPointer transaction; if (createTransaction && painter.needsTransaction(kernel)) { transaction.reset(new KisTransaction(device)); } painter.applyMatrix(kernel, device, srcTopLeft, srcTopLeft, rect.size(), BORDER_REPEAT); } #include "kis_sequential_iterator.h" void KisGaussianKernel::applyErodeU8(KisPaintDeviceSP device, const QRect &rect, qreal radius, const QBitArray &channelFlags, KoUpdater *progressUpdater, bool createTransaction) { KIS_SAFE_ASSERT_RECOVER_RETURN(device->colorSpace()->pixelSize() == 1); { KisSequentialIterator dstIt(device, rect); while (dstIt.nextPixel()) { quint8 *dstPtr = dstIt.rawData(); *dstPtr = 255 - *dstPtr; } } applyDilate(device, rect, radius, channelFlags, progressUpdater, createTransaction); { KisSequentialIterator dstIt(device, rect); while (dstIt.nextPixel()) { quint8 *dstPtr = dstIt.rawData(); *dstPtr = 255 - *dstPtr; } } } diff --git a/libs/image/kis_gaussian_kernel.h b/libs/image/kis_gaussian_kernel.h index c9c300fbdd..d1ae29e8c4 100644 --- a/libs/image/kis_gaussian_kernel.h +++ b/libs/image/kis_gaussian_kernel.h @@ -1,83 +1,90 @@ /* * Copyright (c) 2014 Dmitry Kazakov * * This program is free software; you can redistribute it and/or modify * it 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. * * This program 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 General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef __KIS_GAUSSIAN_KERNEL_H #define __KIS_GAUSSIAN_KERNEL_H #include "kritaimage_export.h" #include "kis_types.h" #include class QRect; class KRITAIMAGE_EXPORT KisGaussianKernel { public: static Eigen::Matrix createHorizontalMatrix(qreal radius); static Eigen::Matrix createVerticalMatrix(qreal radius); static KisConvolutionKernelSP createHorizontalKernel(qreal radius); static KisConvolutionKernelSP createVerticalKernel(qreal radius); static KisConvolutionKernelSP createUniform2DKernel(qreal xRadius, qreal yRadius); static qreal sigmaFromRadius(qreal radius); static int kernelSizeFromRadius(qreal radius); static void applyGaussian(KisPaintDeviceSP device, const QRect& rect, qreal xRadius, qreal yRadius, const QBitArray &channelFlags, KoUpdater *updater, bool createTransaction = false); - static Eigen::Matrix createLoGMatrix(qreal radius, qreal coeff = 1.0); + static Eigen::Matrix createLoGMatrix(qreal radius, qreal coeff, bool zeroCentered, bool includeWrappedArea); static void applyLoG(KisPaintDeviceSP device, const QRect& rect, qreal radius, qreal coeff, const QBitArray &channelFlags, KoUpdater *progressUpdater); + static void applyTightLoG(KisPaintDeviceSP device, + const QRect& rect, + qreal radius, qreal coeff, + const QBitArray &channelFlags, + KoUpdater *progressUpdater); + + static Eigen::Matrix createDilateMatrix(qreal radius); static void applyDilate(KisPaintDeviceSP device, const QRect& rect, qreal radius, const QBitArray &channelFlags, KoUpdater *progressUpdater, bool createTransaction = false); static void applyErodeU8(KisPaintDeviceSP device, const QRect& rect, qreal radius, const QBitArray &channelFlags, KoUpdater *progressUpdater, bool createTransaction = false); }; #endif /* __KIS_GAUSSIAN_KERNEL_H */ diff --git a/plugins/tools/selectiontools/KisMagneticWorker.cc b/plugins/tools/selectiontools/KisMagneticWorker.cc index a8f38c9195..7182b3739c 100644 --- a/plugins/tools/selectiontools/KisMagneticWorker.cc +++ b/plugins/tools/selectiontools/KisMagneticWorker.cc @@ -1,231 +1,232 @@ /* * Copyright (c) 2019 Kuntal Majumder * * 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; version 2.1 of the License. * * 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. * * You should have received a copy of the GNU Lesser General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "KisMagneticWorker.h" #include #include #include #include #include #include #include #include #include "KisMagneticGraph.h" struct DistanceMap { typedef VertexDescriptor key_type; typedef double data_type; typedef std::pair value_type; explicit DistanceMap(double const& dval) : m_default(dval) { } data_type &operator [] (key_type const& k) { if (m.find(k) == m.end()) m[k] = m_default; return m[k]; } private: std::map m; data_type const m_default; }; struct PredecessorMap { PredecessorMap() = default; PredecessorMap(PredecessorMap const& that) = default; typedef VertexDescriptor key_type; typedef VertexDescriptor value_type; typedef boost::read_write_property_map_tag category; VertexDescriptor &operator [] (VertexDescriptor v) { return m_map[v]; } std::map m_map; }; VertexDescriptor get(PredecessorMap const &m, VertexDescriptor v) { auto found = m.m_map.find(v); return found != m.m_map.end() ? found->second : v; } void put(PredecessorMap &m, VertexDescriptor key, VertexDescriptor value) { m.m_map[key] = value; } double EuclideanDistance(VertexDescriptor p1, VertexDescriptor p2) { return std::sqrt(std::pow(p1.y - p2.y, 2) + std::pow(p1.x - p2.x, 2)); } class AStarHeuristic : public boost::astar_heuristic { private: VertexDescriptor m_goal; public: explicit AStarHeuristic(VertexDescriptor goal) : m_goal(goal) { } double operator () (VertexDescriptor v) { return EuclideanDistance(v, m_goal); } }; struct GoalFound { }; class AStarGoalVisitor : public boost::default_astar_visitor { public: explicit AStarGoalVisitor(VertexDescriptor goal) : m_goal(goal){ } void examine_vertex(VertexDescriptor u, KisMagneticGraph const &g) { Q_UNUSED(g) if (u == m_goal) { throw GoalFound(); } } private: VertexDescriptor m_goal; }; struct WeightMap { typedef std::pair key_type; typedef double data_type; typedef std::pair value_type; WeightMap() = default; explicit WeightMap(const KisMagneticGraph &g) : m_graph(g) { } data_type& operator [] (key_type const& k) { if (m_map.find(k) == m_map.end()) { double edge_gradient = (m_graph.getIntensity(k.first) + m_graph.getIntensity(k.second)) / 2; m_map[k] = EuclideanDistance(k.first, k.second) + 255.0 - edge_gradient; } return m_map[k]; } private: std::map m_map; KisMagneticGraph m_graph; }; KisMagneticWorker::KisMagneticWorker(const KisPaintDeviceSP& dev, qreal radius) { m_dev = KisPainter::convertToAlphaAsGray(dev); KisPainter::copyAreaOptimized(dev->exactBounds().topLeft(), dev, m_dev, dev->exactBounds()); - KisGaussianKernel::applyLoG(m_dev, m_dev->exactBounds(), radius, -1.0, QBitArray(), nullptr); + KisGaussianKernel::applyTightLoG(m_dev, m_dev->exactBounds(), radius, -1.0, QBitArray(), nullptr); KisLazyFillTools::normalizeAlpha8Device(m_dev, m_dev->exactBounds()); + m_graph = new KisMagneticGraph(m_dev); } QVector KisMagneticWorker::computeEdge(int radius, QPoint begin, QPoint end) { QRect rect; KisAlgebra2D::accumulateBounds(QVector { begin, end }, &rect); rect = kisGrowRect(rect, radius); VertexDescriptor goal(end); VertexDescriptor start(begin); m_graph->m_rect = rect; // How many maps does it require? // Take a look here, if it doesn't make sense, https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/astar_search.html PredecessorMap pmap; DistanceMap dmap(std::numeric_limits::max()); dmap[start] = 0; std::map rmap; std::map cmap; std::map imap; WeightMap wmap(*m_graph); AStarHeuristic heuristic(goal); QVector result; try{ boost::astar_search_no_init( *m_graph, start, heuristic, boost::visitor(AStarGoalVisitor(goal)) .distance_map(boost::associative_property_map(dmap)) .predecessor_map(boost::ref(pmap)) .weight_map(boost::associative_property_map(wmap)) .vertex_index_map(boost::associative_property_map >(imap)) .rank_map(boost::associative_property_map >(rmap)) .color_map(boost::associative_property_map >(cmap)) .distance_combine(std::plus()) .distance_compare(std::less()) ); }catch (GoalFound const&) { for (VertexDescriptor u = goal; u != start; u = pmap[u]) { result.push_front(QPointF(u.x, u.y)); } } result.push_front(QPoint(start.x, start.y)); return result; } // KisMagneticWorker::computeEdge void KisMagneticWorker::saveTheImage(vQPointF points) { QImage img = m_dev->convertToQImage(0, m_dev->exactBounds()); img = img.convertToFormat(QImage::Format_ARGB32); QPainter gc(&img); QPainterPath path; for (int i = 0; i < points.size(); i++) { if (i == 0) { path.moveTo(points[i]); } else { path.lineTo(points[i]); } } gc.setPen(Qt::blue); gc.drawPath(path); gc.setPen(Qt::green); gc.drawEllipse(points[0], 3, 3); gc.setPen(Qt::red); gc.drawEllipse(points[points.count() -1], 2, 2); img.save("result.png"); } quint8 KisMagneticWorker::intensity(QPoint pt) { return m_graph->getIntensity(VertexDescriptor(pt)); }