Differential D241 Diff 542 krita/plugins/tools/selectiontools/kis_tool_select_magnetic.cc

Changeset View

Standalone View

krita/plugins/tools/selectiontools/kis_tool_select_magnetic.cc

This file was added.

		1		/*
		2		* Copyright (c) 2010 Adam Celarek <kdedev at xibo dot at>
		3		* Copyright (c) 2015 Michael Abrahams <miabraha@gmail.com>
		4		*
		5		* This program is free software; you can redistribute it and/or modify
		6		* it under the terms of the GNU General Public License as published by
		7		* the Free Software Foundation; either version 2 of the License, or
		8		* (at your option) any later version.
		9		*
		10		* This program is distributed in the hope that it will be useful,
		11		* but WITHOUT ANY WARRANTY; without even the implied warranty of
		12		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
		13		* GNU General Public License for more details.
		14		*
		15		* You should have received a copy of the GNU General Public License
		16		* along with this program; if not, write to the Free Software
		17		* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
		18		*/
		19
		20		#include "kis_tool_select_magnetic.h"
		21
		22		#include <QHBoxLayout>
		23		#include <QVBoxLayout>
		24		#include <QLabel>
		25		#include <QVector2D>
		26		#include <QDebug>
		27		#include <QLinkedList>
		28		#include <cmath>
		29
		30		#include <cstdlib>
		31
		32		#include <KoPathShape.h>
		33		#include <KoCanvasBase.h>
		34		#include <KoColorSpace.h>
		35		#include <KoCompositeOp.h>
		36		#include <KoCompositeOpRegistry.h>
		37
		38		#include "kis_cursor.h"
		39		#include "kis_canvas2.h"
		40		#include "kis_canvas_resource_provider.h"
		41		#include "kis_image.h"
		42		#include "kis_painter.h"
		43		#include "kis_selection_options.h"
		44		#include "kis_selection_tool_helper.h"
		45		#include "kis_random_accessor_ng.h"
		46		#include "kis_pixel_selection.h"
		47		#include "kis_global.h"
		48
		49
		50		#include "kis_tool_select_magnetic_option_widget.h"
		51		#include "ui_kis_tool_select_magnetic_option_widget.h"
		52
		53		#include <iostream>
		54
		55
		56		// Tangent direction of the i'th line sigment of a polyline
		57		inline QVector2D tangentAtSegment(const QPolygonF &polyline, int i)
		58		{
		59		return QVector2D(polyline.at(i)-polyline.at(i-1)).normalized();
		60		}
		61
		62		inline QVector2D rotateClockwise(const QVector2D &v)
		63		{
		64		return QVector2D(v.y(), -v.x());
		65		}
		66
		67		inline QVector2D rotateCounterclockwise(const QVector2D &v)
		68		{
		69		return QVector2D(-v.y(), v.x());
		70		}
		71
		72
		73		//List of properties used to estimate choice of lasso point:
		74		// (1) Edge strength, (2) Absolute difference between gradient angle and path angle,
		75		// (3) Distance from previous point, (4) Distance from drawn bezier/lasso curve.
		76		struct pathMetric {
		77		qreal strength;
		78		qreal dTheta;
		79		qreal dPrev;
		80		qreal dPath;
		81		};
		82		typedef QPair< QVector2D, pathMetric > pointInfo;
		83
		84		// Metric to determine edginess. (i.e., degree to which this is a good edge continuation)
		85		// TODO: This seems totally ad-hoc, what are the effects of varying these parameters?
		86		inline qreal edginess(const pathMetric& m)
		87		{
		88		return (m.strength/m.dPrev) + 0.1(m.strength/(1+m.dPath/m.dPrev)) - .03 m.strength * m.dTheta;
		89		}
		90
		91		inline bool maxEdginess(const pointInfo& v1, const pointInfo& v2)
		92		{
		93		return edginess(v1.second) > edginess(v2.second);
		94		}
		95
		96		// Sobel filter
		97		static const Matrix3d horizontalFilterMatrix = (Matrix3d() << -1, 0, 1,
		98		-2, 0, 2,
		99		-1, 0, 1).finished();
		100
		101		static const Matrix3d verticalFilterMatrix = (Matrix3d() << -1,-2,-1,
		102		0, 0, 0,
		103		1, 2, 1).finished();
		104
		105
		106		KisToolSelectMagnetic::KisToolSelectMagnetic(KoCanvasBase * canvas)
		107		: SelectionActionHandler<KisDelegatedSelectMagneticWrapper>(
		108		canvas,
		109		KisCursor::load("tool_magnetic_selection_cursor.png", 6, 6),
		110		i18n("Magnetic Selection"),
		111		(KisTool*) (new __KisSelectMagneticLocalTool(canvas, this)))
		112		{
		113		}
		114
		115		int KisToolSelectMagnetic::radius() const
		116		{
		117		return m_magneticOptions->m_radius->value();
		118		}
		119
		120		int KisToolSelectMagnetic::threshold() const
		121		{
		122		return m_magneticOptions->m_threshold->value();
		123		}
		124
		125		int KisToolSelectMagnetic::searchStartPoint() const
		126		{
		127		if(m_magneticOptions->m_searchFromLeft->isChecked())
		128		return KisToolSelectMagneticOptionWidget::SearchFromLeft;
		129		else
		130		return KisToolSelectMagneticOptionWidget::SearchFromRight;
		131		}
		132
		133		int KisToolSelectMagnetic::colorLimitation() const
		134		{
		135		return m_magneticOptions->m_colorLimitation->currentIndex();
		136		}
		137
		138		bool KisToolSelectMagnetic::limitToCurrentLayer() const
		139		{
		140		return m_magneticOptions->m_limitToCurrentLayer->isChecked();
		141		}
		142
		143
		144		QWidget* KisToolSelectMagnetic::createOptionWidget()
		145		{
		146		SelectionActionHandler<KisDelegatedSelectMagneticWrapper>::createOptionWidget();
		147		KisSelectionOptions *selectionWidget = selectionOptionWidget();
		148
		149		selectionWidget->disableAntiAliasSelectionOption();
		150		selectionWidget->disableSelectionModeOption();
		151
		152		KisToolSelectMagneticOptionWidget *magneticOptionsWidget;
		153		magneticOptionsWidget = new KisToolSelectMagneticOptionWidget(selectionWidget);
		154		m_magneticOptions = magneticOptionsWidget->ui;
		155
		156		QVBoxLayout* l = dynamic_cast<QVBoxLayout*>(selectionWidget->layout());
		157		Q_ASSERT(l);
		158		l->addWidget(magneticOptionsWidget);
		159
		160		return selectionWidget;
		161		}
		162
		163		void KisToolSelectMagnetic::mousePressEvent(KoPointerEvent* event)
		164		{
		165		if (!selectionEditable()) return;
		166		DelegatedSelectMagneticTool::mousePressEvent(event);
		167		}
		168
		169		void KisToolSelectMagnetic::requestStrokeEnd()
		170		{
		171		localTool()->endPathWithoutLastPoint();
		172		}
		173
		174		void KisToolSelectMagnetic::requestStrokeCancellation()
		175		{
		176		localTool()->cancelPath();
		177		}
		178
		179		void KisToolSelectMagnetic::setAlternateSelectionAction(SelectionAction action)
		180		{
		181		// We turn off the ability to change the selection in the middle of drawing a path.
		182		if (!m_localTool->listeningToModifiers()) {
		183		SelectionActionHandler<KisDelegatedSelectMagneticWrapper>::setAlternateSelectionAction(action);
		184		}
		185		}
		186
		187
		188		__KisSelectMagneticLocalTool::__KisSelectMagneticLocalTool(KoCanvasBase * canvas, KisToolSelectMagnetic* parentTool)
		189		: KoCreatePathTool(canvas), m_selectionTool(parentTool) {}
		190
		191
		192		void __KisSelectMagneticLocalTool::activate(ToolActivation toolActivation, const QSet<KoShape*> &shapes)
		193		{
		194		std::cout << verticalFilterMatrix << std::endl;
		195		KoCreatePathTool::activate(toolActivation, shapes);
		196		KisCanvas2* kisCanvas = dynamic_cast<KisCanvas2*>(canvas());
		197		Q_ASSERT(kisCanvas);
		198
		199		m_colorSpace = kisCanvas->image()->colorSpace();
		200		Q_ASSERT(m_colorSpace);
		201
		202		m_colorTransformation = m_colorSpace->createColorTransformation("desaturate_adjustment", QHash<QString,QVariant>());
		203		Q_ASSERT(m_colorTransformation);
		204		}
		205
		206		void __KisSelectMagneticLocalTool::deactivate()
		207		{
		208		KoCreatePathTool::deactivate();
		209		m_detectedBorder.clear();
		210		m_debugPolyline.clear();
		211		delete m_colorTransformation;
		212		}
		213
		214		void __KisSelectMagneticLocalTool::mouseReleaseEvent(KoPointerEvent *event)
		215		{
		216		KoCreatePathTool::mouseReleaseEvent(event);
		217		}
		218
		219		// Primary entry point for drawing the magnetic lasso visual ensemble.
		220		void __KisSelectMagneticLocalTool::paintPath(KoPathShape &pathShape, QPainter &painter, const KoViewConverter &converter)
		221		{
		222		Q_UNUSED(converter);
		223
		224		KisCanvas2 * kisCanvas = dynamic_cast<KisCanvas2*>(canvas());
		225		if (!kisCanvas) return;
		226
		227		QTransform matrix;
		228		matrix.scale(kisCanvas->image()->xRes(), kisCanvas->image()->yRes());
		229		matrix.translate(pathShape.position().x(), pathShape.position().y());
		230
		231
		232		qreal zoomX, zoomY;
		233		kisCanvas->viewConverter()->zoom(&zoomX, &zoomY);
		234		Q_ASSERT(qFuzzyCompare(zoomX, zoomY));
		235
		236		qreal width = m_selectionTool->radius()*2;
		237		width *= zoomX/(kisCanvas->image()->xRes());
		238
		239
		240		//Draw the border showing the radius.
		241		paintOutline(&painter, m_selectionTool->pixelToView(matrix.map(pathShape.outline())), width);
		242
		243		//Update and clean the snapped border.
		244		computeOutline(matrix.map(pathShape.outline()));
		245		// cleanDetectedBorder();
		246
		247		// Draw various line components
		248		painter.setPen(QColor(0,0,128));
		249		painter.drawPoints(m_selectionTool->pixelToView(m_debugPolyline));
		250
		251		painter.setPen(QPen(QColor(0,128,0), 1));
		252		painter.drawPoints(m_selectionTool->pixelToView(m_debugScannedPoints));
		253
		254		painter.setPen(QPen(QColor(128,0,0), 3, Qt::DotLine));
		255		painter.drawPolyline(m_selectionTool->pixelToView(m_detectedBorder));
		256
		257		m_debugScannedPoints.clear();
		258		}
		259
		260
		261		void __KisSelectMagneticLocalTool::paintOutline(QPainter *painter, const QPainterPath &path, qreal width)
		262		{
		263		painter->save();
		264		// painter->setCompositionMode(QPainter::CompositionMode_Difference);
		265		painter->setOpacity(.5);
		266		painter->setPen(QPen(QColor(128, 128, 128), width));
		267		painter->drawPath(path);
		268		m_selectionTool->updateCanvasViewRect(path.controlPointRect().adjusted(-width, -width, width, width));
		269		painter->restore();
		270		}
		271
		272
		273		// Compute whole "outline." Called from paintPath()
		274		void __KisSelectMagneticLocalTool::computeOutline(const QPainterPath &pixelPath)
		275		{
		276		/*
		277		* The algorithm works as follows:
		278		* Traverse along the given path and from one side of the path to the other.
		279		* Break the edge into pieces and call the subfunction to compute the most likely continuation edge.
		280		* Note that there is no global optimization involved.
		281		*/
		282
		283
		284		// Boilerplate to access the image
		285		KisCanvas2* kisCanvas = dynamic_cast<KisCanvas2*>(canvas());
		286		Q_ASSERT(kisCanvas);
		287
		288		KisPaintDeviceSP dev;
		289		if(m_selectionTool->limitToCurrentLayer()) {
		290		dev = m_selectionTool->currentNode()->paintDevice();
		291		}
		292		else {
		293		dev = kisCanvas->image()->projection();
		294		}
		295		KisRandomConstAccessorSP randomAccessor = dev->createRandomAccessorNG(0,0);
		296
		297
		298		// Boilerplate to start iterating over the line
		299		QPolygonF polyline = pixelPath.toFillPolygon();
		300		if(polyline.count()>1) polyline.remove(polyline.count()-1);
		301		if(polyline.count()<2) return;
		302
		303		QPolygonF points;
		304		points.append(polyline.at(0));
		305
		306		// Break the line into pieces based on the accuracy limit
		307		for(int i=1; i<polyline.count(); i++) {
		308		QPointF nextPoint = polyline.at(i);
		309		qreal d = kisDistance(points.last(), nextPoint);
		310		if(d < m_selectionTool->threshold()) {
		311		//points.append(nextPoint);
		312		continue;
		313		}
		314		else {
		315		QVector2D fragment(nextPoint-points.last());
		316		fragment.normalize();
		317		fragment*=m_selectionTool->threshold();
		318		for(int j=0; j<((int) d)/m_selectionTool->threshold(); j++) {
		319		points.append(fragment.toPointF() + points.last());
		320		}
		321		}
		322		}
		323
		324
		325		// Now apply the edge tracing algorithm one segment at a time
		326		m_detectedBorder.clear();
		327		m_debugScannedPoints = QPolygon(); // debugging
		328		if(m_selectionTool->searchStartPoint() == KisToolSelectMagneticOptionWidget::SearchFromLeft) {
		329		for(int i=1; i<points.count(); i++) {
		330		QVector2D tangent = tangentAtSegment(points, i);
		331		QVector2D startPos = QVector2D(points.at(i)) + rotateClockwise(tangent) * (m_selectionTool->radius());
		332		computeEdge(startPos, rotateCounterclockwise(tangent), randomAccessor);
		333		}
		334		}
		335		else { //SearchFromRight
		336		for(int i=1; i<points.count(); i++) {
		337		QVector2D tangent = tangentAtSegment(points, i);
		338		QVector2D startPos = QVector2D(points.at(i)) + rotateCounterclockwise(tangent) * (m_selectionTool->radius());
		339		computeEdge(startPos, rotateClockwise(tangent), randomAccessor);
		340		}
		341		}
		342
		343		m_debugPolyline = points; // Debugging display
		344
		345		}
		346
		347		// Compute an edge segment. Walk along candidates in the direction normal to the tangent vector,
		348		// then select the point which is the best overall fit. Called from computeOutline().
		349		void __KisSelectMagneticLocalTool::computeEdge(const QVector2D &startPoint, const QVector2D &normal, KisRandomConstAccessorSP pixelAccessor)
		350		{
		351		QVector2D currentPoint = startPoint;
		352		QVector2D lastPoint = m_detectedBorder.size()>0 ? QVector2D(m_detectedBorder.last()) : QVector2D(-1, -1);
		353		QVector2D centerPoint = startPoint+normal*m_selectionTool->radius();
		354
		355
		356		QList< pointInfo > pointCandidates;
		357
		358		while((currentPoint - startPoint).length() < m_selectionTool->radius()*2) {
		359		m_debugScannedPoints.append(currentPoint.toPoint());
		360
		361		// Compute distance metric components
		362		QVector2D dPrev = currentPoint-lastPoint;
		363		QVector2D gradient = getEdgeGradient(currentPoint, pixelAccessor);
		364
		365		// Edge detector magnitude, mismatch in edge angle, distance to prev. point, distance to line center
		366		pathMetric parameters {
		367		gradient.length(),
		368		qAbs(shortestAngularDistance(atan2(gradient.y(), gradient.x()),
		369		atan2(dPrev.y(), dPrev.x()))),
		370		dPrev.length(),
		371		(centerPoint-currentPoint).length()
		372		};
		373
		374		pointCandidates.append(pointInfo(currentPoint,parameters));
		375
		376		//move to next pixel in the normal direction
		377		currentPoint += normal;
		378		}
		379
		380		// Sort the candidates for maximum edginess
		381		qSort(pointCandidates.begin(), pointCandidates.end(), maxEdginess);
		382
		383		// For debugging
		384		// pathMetric maxEdgeMetric = pointCandidates.first().second;
		385		// qDebug()<< QString("Point %1 has edginess %3 (strength: %5; dTheta: %7; dPath: %9; dPrev: %11)").\
		386		// arg(m_detectedBorder.size(), 3).arg(edginess(maxEdgeMetric), 9).arg(maxEdgeMetric.strength, 9).\
		387		// arg(maxEdgeMetric.dTheta, 9).arg(maxEdgeMetric.dPath, 9).arg(maxEdgeMetric.dPrev, 9);
		388
		389
		390		// Append the winner
		391		m_detectedBorder.append(pointCandidates.first().first.toPoint());
		392		}
		393
		394
		395
		396		/* An alternate version of computeEdge
		397
		398		//void __KisSelectMagneticLocalTool::computeEdge(const QVector2D &startPoint, const QVector2D &direction, KisRandomConstAccessorSP pixelAccessor)
		399		//{
		400		//// take the colour value of the starting side and match it against the colour on the current position
		401		//// if the difference is beyond the threshold, there is a edge.
		402		// QVector2D currentPoint = startPoint;
		403		// KoColor transformedColor(m_colorSpace);
		404		//
		405		// pixelAccessor->moveTo(currentPoint.x(), currentPoint.y());
		406		// m_colorTransformation->transform(pixelAccessor->rawData(), transformedColor.data(), 1);
		407		//
		408		// int value = transformedColor.toQColor().value();
		409		//
		410		// while((currentPoint - startPoint).length() < m_selectionTool->radius()*2) {
		411		// m_debugScannedPoints.append(currentPoint.toPoint());
		412		//
		413		// pixelAccessor->moveTo(currentPoint.x(), currentPoint.y());
		414		// m_colorTransformation->transform(pixelAccessor->rawData(), transformedColor.data(), 1);
		415		//
		416		// int currentValue = transformedColor.toQColor().value();
		417		// if(std::abs(value-currentValue)>m_selectionTool->threshold()) {
		418		// m_tmpDetectedBorder.append(currentPoint.toPoint());
		419		// return;
		420		// }
		421		// else {
		422		// }
		423		// //move to next pixel
		424		// currentPoint+=direction*1;
		425		// }
		426		//// m_tmpDetectedBorder.append(currentPoint.toPoint());
		427		//}
		428
		429		*/
		430
		431		// TODO: smooth the image first to decrease noise
		432		// TODO: see if the desaturate transformation is feasible
		433		QVector2D __KisSelectMagneticLocalTool::getEdgeGradient(QVector2D& currentPoint, KisRandomConstAccessorSP& pixelAccessor) const
		434		{
		435		Matrix3d pointValues = getNearbyPixels(currentPoint, pixelAccessor);
		436
		437		// Estimate horizontal and vertical components of the gradient using filters
		438		Matrix3d dX = pointValues.array() * horizontalFilterMatrix.array(); // eigen arrays do componentwise operations
		439		Matrix3d dY = pointValues.array() * verticalFilterMatrix.array();
		440		return QVector2D(dX.sum(),dY.sum());
		441		}
		442
		443
		444		Matrix3d __KisSelectMagneticLocalTool::getNearbyPixels(const QVector2D &point, KisRandomConstAccessorSP pixelAccessor) const
		445		{
		446		QPoint currentPoint((qint32)point.x()-1, (qint32)point.y()-1);
		447		KoColor transformedColor(m_colorSpace);
		448
		449		double coeff[3][3];
		450		for(int i=0; i<3; i++) {
		451		for(int j=0; j<3; j++) {
		452		pixelAccessor->moveTo(currentPoint.x()+i, currentPoint.y()+j);
		453		// m_colorTransformation->transform(pixelAccessor->rawDataConst(), transformedColor.data(), 1);
		454		memcpy(transformedColor.data(), pixelAccessor->rawDataConst(), m_colorSpace->pixelSize());
		455		coeff[i][j]=transformedColor.toQColor().valueF();
		456		}
		457		}
		458
		459		Matrix3d val = (Matrix3d() << coeff[0][0], coeff[0][1], coeff[0][2],
		460		coeff[1][0], coeff[1][1], coeff[1][2],
		461		coeff[2][0], coeff[2][1], coeff[2][2]).finished();
		462
		463		return val;
		464		}
		465
		466		// Things seem to work fine if we don't do this clean up operation, so stick with that for now.
		467		// It also seems counter to an ultimate goal of using non-local optimization.
		468		const qreal minDeviation = .75;
		469		void __KisSelectMagneticLocalTool::cleanDetectedBorder()
		470		{
		471		//load the points into a linked list, because removing on a vector is expensive
		472		QLinkedList<QPointF> detectedBorder;
		473		foreach(const QPointF &point, m_detectedBorder) {
		474		detectedBorder << point;
		475		}
		476
		477		QLinkedList<QPointF>::iterator iter = detectedBorder.begin();
		478		while ((iter+2) != detectedBorder.end() && (iter+1) != detectedBorder.end() && iter != detectedBorder.end()) {
		479		// Look to the next two points in the border
		480		QVector2D toNext = QVector2D((iter+1) - iter);
		481		QVector2D toAfterNext = QVector2D((iter+2) - iter);
		482
		483		// qreal distToNext = toNext.length();
		484		qreal angleToNext = atan2(toNext.y(), toNext.x());
		485		qreal angleToAfterNext = atan2(toAfterNext.y(), toAfterNext.x());
		486
		487		// Throw away a point if it is close to being in a straight line with the successor.
		488		// If the three points are in a straight line, always throw the middle one away.
		489		qreal deviation = qAbs(angleToAfterNext-angleToNext)*toNext.length();
		490
		491		if( deviation< minDeviation) {
		492		// qDebug() << QString("Deleting point with nearness %2").arg(nearness);
		493		iter = detectedBorder.erase(iter);
		494		}
		495		else {
		496		iter++;
		497		}
		498		}
		499
		500		m_detectedBorder.clear();
		501		foreach(const QPointF &point, detectedBorder) {
		502		m_detectedBorder << point;
		503		}
		504		}
		505
		506		//Close the path and add it to the selection
		507		void __KisSelectMagneticLocalTool::addPathShape(KoPathShape* pathShape)
		508		{
		509		KisCanvas2 * kisCanvas = dynamic_cast<KisCanvas2*>(canvas());
		510		if (!kisCanvas) return;
		511
		512		KisSelectionToolHelper helper(kisCanvas, kundo2_i18n("Select by Magnetic Path"));
		513		if (m_selectionTool->selectionMode() == PIXEL_SELECTION) {
		514
		515		KisPixelSelectionSP tmpSel = KisPixelSelectionSP(new KisPixelSelection());
		516
		517		KisPainter painter(tmpSel);
		518		painter.setPaintColor(KoColor(Qt::black, tmpSel->colorSpace()));
		519		painter.setFillStyle(KisPainter::FillStyleForegroundColor);
		520		painter.setAntiAliasPolygonFill(m_selectionTool->antiAliasSelection());
		521		painter.setCompositeOp(tmpSel->colorSpace()->compositeOp(COMPOSITE_OVER));
		522
		523		QPolygonF path = QPolygonF(m_detectedBorder);
		524		painter.paintPolygon(path);
		525
		526		QPainterPath cache;
		527		cache.addPolygon(path);
		528		cache.closeSubpath();
		529		tmpSel->setOutlineCache(cache);
		530
		531		helper.selectPixelSelection(tmpSel, m_selectionTool->selectionAction());
		532
		533		m_detectedBorder.clear();
		534		m_debugPolyline.clear();
		535		delete pathShape;
		536		} else {
		537		helper.addSelectionShape(pathShape);
		538		}
		539		}
		540
		541		#include "kis_tool_select_magnetic.moc"