Changeset View
Changeset View
Standalone 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 | | ||||
21 | #include "kis_tool_select_magnetic.h" | ||||
22 | | ||||
23 | #include <QHBoxLayout> | ||||
24 | #include <QVBoxLayout> | ||||
25 | #include <QLabel> | ||||
26 | #include <QVector2D> | ||||
27 | #include <QDebug> | ||||
28 | #include <QLinkedList> | ||||
29 | #include <cmath> | ||||
30 | | ||||
31 | #include <cstdlib> | ||||
32 | | ||||
33 | #include <KoPathShape.h> | ||||
34 | #include <KoCanvasBase.h> | ||||
35 | #include <KoColorSpace.h> | ||||
36 | #include <KoCompositeOp.h> | ||||
37 | #include <KoCompositeOpRegistry.h> | ||||
38 | | ||||
39 | #include "kis_cursor.h" | ||||
40 | #include "kis_canvas2.h" | ||||
41 | #include "kis_canvas_resource_provider.h" | ||||
42 | #include "kis_image.h" | ||||
43 | #include "kis_painter.h" | ||||
44 | #include "kis_selection_options.h" | ||||
45 | #include "kis_selection_tool_helper.h" | ||||
46 | #include "kis_random_accessor_ng.h" | ||||
47 | #include "kis_pixel_selection.h" | ||||
48 | #include "kis_global.h" | ||||
49 | | ||||
50 | | ||||
51 | #include "kis_tool_select_magnetic_option_widget.h" | ||||
52 | #include "ui_kis_tool_select_magnetic_option_widget.h" | ||||
53 | | ||||
54 | #include <iostream> | ||||
55 | | ||||
56 | | ||||
57 | #ifdef HAVE_GSL | ||||
58 | #include <gsl/gsl_errno.h> | ||||
59 | #include <gsl/gsl_sort_double.h> | ||||
60 | const gsl_min_fminimizer_type *T = gsl_min_fminimizer_brent; | ||||
61 | #endif | ||||
62 | | ||||
63 | | ||||
64 | | ||||
65 | // Tangent direction of the i'th line sigment of a polyline. | ||||
66 | // Start point zero with the same tangent as point one. | ||||
67 | inline QVector2D tangentAtSegment(const QPolygonF &polyline, int i) | ||||
68 | { | ||||
69 | i = std::max(i,1); | ||||
70 | return QVector2D(polyline.at(i)-polyline.at(i-1)).normalized(); | ||||
71 | } | ||||
72 | | ||||
73 | inline QVector2D rotateClockwise(const QVector2D &v) | ||||
74 | { | ||||
75 | return QVector2D(v.y(), -v.x()); | ||||
76 | } | ||||
77 | | ||||
78 | inline QVector2D rotateCounterclockwise(const QVector2D &v) | ||||
79 | { | ||||
80 | return QVector2D(-v.y(), v.x()); | ||||
81 | } | ||||
82 | | ||||
83 | | ||||
84 | //List of properties used to estimate choice of lasso point: | ||||
85 | // (1) Edge strength, (2) Absolute difference between gradient angle and path angle, | ||||
86 | // (3) Distance from previous point, (4) Distance from drawn bezier/lasso curve. | ||||
87 | struct pathMetric { | ||||
88 | qreal strength; | ||||
89 | qreal dTheta; | ||||
90 | qreal dPrev; | ||||
91 | qreal dPath; | ||||
92 | qreal radius; | ||||
93 | }; | ||||
94 | typedef QPair< QVector2D, pathMetric > pointInfo; | ||||
95 | | ||||
96 | // Metric to determine edginess, i.e. whether this is a good edge continuation. Note: negative value. | ||||
97 | // Inner expression should be increasing in strength, decreasing in dPrev and dPath, decreasing in dTheta. | ||||
98 | // Discussion. This is ad-hoc, but seems to do the job. We just need a reasonable metric. | ||||
99 | // The further we stray from the path the more we should penalize it. | ||||
100 | inline qreal edginess(const qreal strength, const qreal dTheta, const qreal dPrev, const qreal dPath, const qreal radius) | ||||
101 | { | ||||
102 | qreal dPrevScaled = dPrev/radius; | ||||
103 | qreal dPathScaled = dPath/radius; | ||||
104 | return -1. * ((strength + .1)/(.5+dPrevScaled) + (strength + .1)/(1+(dPathScaled)*(dPathScaled)) - 0*strength*dTheta*dPrevScaled ) ; | ||||
105 | } | ||||
106 | | ||||
107 | inline bool maxEdginess(const pointInfo& v1, const pointInfo& v2) | ||||
108 | { | ||||
109 | // return edginess(v1.second) < edginess(v2.second); | ||||
110 | return v1.second.radius - v2.second.radius; | ||||
111 | } | ||||
112 | | ||||
113 | // Scharr filter | ||||
114 | static const Matrix3d horizontalFilterMatrix = (Matrix3d() << -3, 0, 3, | ||||
115 | -10, 0, 10, | ||||
116 | -3, 0, 3).finished(); | ||||
117 | | ||||
118 | static const Matrix3d verticalFilterMatrix = horizontalFilterMatrix.transpose(); | ||||
119 | | ||||
120 | | ||||
121 | KisToolSelectMagnetic::KisToolSelectMagnetic(KoCanvasBase * canvas) | ||||
122 | : SelectionActionHandler<KisDelegatedSelectMagneticWrapper>( | ||||
123 | canvas, | ||||
124 | KisCursor::load("tool_magnetic_selection_cursor.png", 6, 6), | ||||
125 | i18n("Magnetic Selection"), | ||||
126 | (KisTool*) (new KisSelectMagneticLocalTool(canvas, this))) | ||||
127 | { | ||||
128 | } | ||||
129 | | ||||
130 | int KisToolSelectMagnetic::radius() const | ||||
131 | { | ||||
132 | return m_magneticOptions->m_radius->value(); | ||||
133 | } | ||||
134 | | ||||
135 | int KisToolSelectMagnetic::threshold() const | ||||
136 | { | ||||
137 | return m_magneticOptions->m_threshold->value(); | ||||
138 | } | ||||
139 | | ||||
140 | bool KisToolSelectMagnetic::searchFromLeft() const | ||||
141 | { | ||||
142 | return (m_magneticOptions->m_searchFromLeft->isChecked()); | ||||
143 | } | ||||
144 | | ||||
145 | int KisToolSelectMagnetic::colorLimitation() const | ||||
146 | { | ||||
147 | return m_magneticOptions->m_colorLimitation->currentIndex(); | ||||
148 | } | ||||
149 | | ||||
150 | bool KisToolSelectMagnetic::limitToCurrentLayer() const | ||||
151 | { | ||||
152 | return m_magneticOptions->m_limitToCurrentLayer->isChecked(); | ||||
153 | } | ||||
154 | | ||||
155 | | ||||
156 | QWidget* KisToolSelectMagnetic::createOptionWidget() | ||||
157 | { | ||||
158 | SelectionActionHandler<KisDelegatedSelectMagneticWrapper>::createOptionWidget(); | ||||
159 | KisSelectionOptions *selectionWidget = selectionOptionWidget(); | ||||
160 | | ||||
161 | selectionWidget->disableAntiAliasSelectionOption(); | ||||
162 | selectionWidget->disableSelectionModeOption(); | ||||
163 | | ||||
164 | KisToolSelectMagneticOptionWidget *magneticOptionsWidget; | ||||
165 | magneticOptionsWidget = new KisToolSelectMagneticOptionWidget(selectionWidget); | ||||
166 | m_magneticOptions = magneticOptionsWidget->ui; | ||||
167 | | ||||
168 | QVBoxLayout* l = dynamic_cast<QVBoxLayout*>(selectionWidget->layout()); | ||||
169 | Q_ASSERT(l); | ||||
170 | l->addWidget(magneticOptionsWidget); | ||||
171 | | ||||
172 | return selectionWidget; | ||||
173 | } | ||||
174 | | ||||
175 | void KisToolSelectMagnetic::mousePressEvent(KoPointerEvent* event) | ||||
176 | { | ||||
177 | if (!selectionEditable()) return; | ||||
178 | DelegatedSelectMagneticTool::mousePressEvent(event); | ||||
179 | } | ||||
180 | | ||||
181 | void KisToolSelectMagnetic::requestStrokeEnd() | ||||
182 | { | ||||
183 | localTool()->endPathWithoutLastPoint(); | ||||
184 | } | ||||
185 | | ||||
186 | void KisToolSelectMagnetic::requestStrokeCancellation() | ||||
187 | { | ||||
188 | localTool()->cancelPath(); | ||||
189 | } | ||||
190 | | ||||
191 | void KisToolSelectMagnetic::setAlternateSelectionAction(SelectionAction action) | ||||
192 | { | ||||
193 | // We turn off the ability to change the selection in the middle of drawing a path. | ||||
194 | if (!m_localTool->listeningToModifiers()) { | ||||
195 | SelectionActionHandler<KisDelegatedSelectMagneticWrapper>::setAlternateSelectionAction(action); | ||||
196 | } | ||||
197 | } | ||||
198 | | ||||
199 | | ||||
200 | KisSelectMagneticLocalTool::KisSelectMagneticLocalTool(KoCanvasBase * canvas, KisToolSelectMagnetic* parentTool) | ||||
201 | : KoCreatePathTool(canvas), m_selectionTool(parentTool), minimizer() | ||||
202 | { | ||||
203 | minimizer = gsl_min_fminimizer_alloc(T); | ||||
204 | gsl_set_error_handler_off(); | ||||
205 | } | ||||
206 | | ||||
207 | KisSelectMagneticLocalTool::~KisSelectMagneticLocalTool() | ||||
208 | { | ||||
209 | gsl_min_fminimizer_free(minimizer); | ||||
210 | } | ||||
211 | | ||||
212 | void KisSelectMagneticLocalTool::activate(ToolActivation toolActivation, const QSet<KoShape*> &shapes) | ||||
213 | { | ||||
214 | std::cout << verticalFilterMatrix << std::endl; | ||||
215 | KoCreatePathTool::activate(toolActivation, shapes); | ||||
216 | KisCanvas2* kisCanvas = dynamic_cast<KisCanvas2*>(canvas()); | ||||
217 | Q_ASSERT(kisCanvas); | ||||
218 | | ||||
219 | m_colorSpace = kisCanvas->image()->colorSpace(); | ||||
220 | Q_ASSERT(m_colorSpace); | ||||
221 | | ||||
222 | m_colorTransformation = m_colorSpace->createColorTransformation("desaturate_adjustment", QHash<QString,QVariant>()); | ||||
223 | Q_ASSERT(m_colorTransformation); | ||||
224 | } | ||||
225 | | ||||
226 | void KisSelectMagneticLocalTool::deactivate() | ||||
227 | { | ||||
228 | KoCreatePathTool::deactivate(); | ||||
229 | cleanEstimates(); | ||||
230 | delete m_colorTransformation; | ||||
231 | } | ||||
232 | | ||||
233 | void KisSelectMagneticLocalTool::cleanEstimates() | ||||
234 | { | ||||
235 | m_detectedBorder.clear(); | ||||
236 | m_detectedOffset.clear(); | ||||
237 | m_lastPoints.clear(); | ||||
238 | m_converged.clear(); | ||||
239 | m_debugScannedPoints.clear(); | ||||
240 | } | ||||
241 | | ||||
242 | void KisSelectMagneticLocalTool::cancelPath() | ||||
243 | { | ||||
244 | cleanEstimates(); | ||||
245 | KoCreatePathTool::cancelPath(); | ||||
246 | } | ||||
247 | | ||||
248 | | ||||
249 | void KisSelectMagneticLocalTool::mouseReleaseEvent(KoPointerEvent *event) | ||||
250 | { | ||||
251 | KoCreatePathTool::mouseReleaseEvent(event); | ||||
252 | } | ||||
253 | | ||||
254 | // Primary entry point for drawing the magnetic lasso visual ensemble. | ||||
255 | void KisSelectMagneticLocalTool::paintPath(KoPathShape &pathShape, QPainter &painter, const KoViewConverter &converter) | ||||
256 | { | ||||
257 | Q_UNUSED(converter); | ||||
258 | | ||||
259 | KisCanvas2 * kisCanvas = dynamic_cast<KisCanvas2*>(canvas()); | ||||
260 | if (!kisCanvas) return; | ||||
261 | | ||||
262 | QTransform matrix; | ||||
263 | matrix.scale(kisCanvas->image()->xRes(), kisCanvas->image()->yRes()); | ||||
264 | matrix.translate(pathShape.position().x(), pathShape.position().y()); | ||||
265 | | ||||
266 | | ||||
267 | qreal zoomX, zoomY; | ||||
268 | kisCanvas->viewConverter()->zoom(&zoomX, &zoomY); | ||||
269 | Q_ASSERT(qFuzzyCompare(zoomX, zoomY)); | ||||
270 | | ||||
271 | qreal width = m_selectionTool->radius()*2; | ||||
272 | width *= zoomX/(kisCanvas->image()->xRes()); | ||||
273 | | ||||
274 | | ||||
275 | //Draw the border showing the radius. | ||||
276 | paintOutline(&painter, m_selectionTool->pixelToView(matrix.map(pathShape.outline())), width); | ||||
277 | | ||||
278 | //Update and clean the snapped border. | ||||
279 | computeSections(matrix.map(pathShape.outline())); | ||||
280 | // cleanDetectedBorder(); | ||||
281 | | ||||
282 | // Draw various line components | ||||
283 | painter.setPen(QColor(0,0,128)); | ||||
284 | painter.drawPoints(m_selectionTool->pixelToView(m_lastPoints)); | ||||
285 | | ||||
286 | painter.setPen(QPen(QColor(128,0,0), 3, Qt::DotLine)); | ||||
287 | painter.drawPolyline(m_selectionTool->pixelToView(m_detectedBorder)); | ||||
288 | | ||||
289 | painter.setPen(QPen(QColor(0,128,0), 1)); | ||||
290 | painter.drawPoints(m_selectionTool->pixelToView(m_debugScannedPoints)); | ||||
291 | | ||||
292 | m_debugScannedPoints.clear(); | ||||
293 | } | ||||
294 | | ||||
295 | | ||||
296 | void KisSelectMagneticLocalTool::paintOutline(QPainter *painter, const QPainterPath &path, qreal width) | ||||
297 | { | ||||
298 | painter->save(); | ||||
299 | // painter->setCompositionMode(QPainter::CompositionMode_Difference); | ||||
300 | painter->setOpacity(.3); | ||||
301 | painter->setPen(QPen(QColor(128, 128, 128), width)); | ||||
302 | painter->drawPath(path); | ||||
303 | m_selectionTool->updateCanvasViewRect(path.controlPointRect().adjusted(-width, -width, width, width)); | ||||
304 | painter->restore(); | ||||
305 | } | ||||
306 | | ||||
307 | | ||||
308 | // Compute whole "outline." Called from paintPath() | ||||
309 | void KisSelectMagneticLocalTool::computeSections(const QPainterPath &pixelPath) | ||||
310 | { | ||||
311 | /* | ||||
312 | * The algorithm works as follows: | ||||
313 | * Traverse along the given path and from one side of the path to the other. | ||||
314 | * Break the edge into pieces and call the subfunction to compute the most likely continuation edge. | ||||
315 | * Note that there is no global optimization involved. | ||||
316 | */ | ||||
317 | | ||||
318 | | ||||
319 | // Boilerplate to access the image | ||||
320 | KisCanvas2* kisCanvas = dynamic_cast<KisCanvas2*>(canvas()); | ||||
321 | Q_ASSERT(kisCanvas); | ||||
322 | | ||||
323 | KisPaintDeviceSP dev; | ||||
324 | if(m_selectionTool->limitToCurrentLayer()) { | ||||
325 | dev = m_selectionTool->currentNode()->paintDevice(); | ||||
326 | } | ||||
327 | else { | ||||
328 | dev = kisCanvas->image()->projection(); | ||||
329 | } | ||||
330 | | ||||
331 | | ||||
332 | // Boilerplate to start iterating over the line | ||||
333 | QPolygonF polyline = pixelPath.toFillPolygon(); | ||||
334 | if(polyline.count()>1) polyline.remove(polyline.count()-1); | ||||
335 | if(polyline.count()<2) return; | ||||
336 | | ||||
337 | QPolygonF points; | ||||
338 | points.append(polyline.at(0)); | ||||
339 | | ||||
340 | // Break the pen line into pieces | ||||
341 | for(int i=1; i<polyline.count(); i++) { | ||||
342 | QPointF nextPoint = polyline.at(i); | ||||
343 | qreal d = kisDistance(points.last(), nextPoint); | ||||
344 | if(d < m_selectionTool->threshold()) { | ||||
345 | //points.append(nextPoint); | ||||
346 | continue; | ||||
347 | } | ||||
348 | else { | ||||
349 | QVector2D fragment(nextPoint-points.last()); | ||||
350 | fragment.normalize(); | ||||
351 | fragment*=m_selectionTool->threshold(); | ||||
352 | for(int j=0; j<((int) d)/m_selectionTool->threshold(); j++) { | ||||
353 | points.append(fragment.toPointF() + points.last()); | ||||
354 | } | ||||
355 | } | ||||
356 | } | ||||
357 | | ||||
358 | | ||||
359 | // Now apply the edge tracing algorithm one segment at a time | ||||
360 | m_detectedBorder.clear(); | ||||
361 | m_debugScannedPoints.clear(); // debugging | ||||
362 | if (points.count() > 1) { | ||||
363 | qDebug() << "Estimating lasso path"; | ||||
364 | KisRandomConstAccessorSP pixelAccessor= dev->createRandomAccessorNG(0,0); | ||||
365 | for(int i=0; i<points.count(); i++) { | ||||
366 | computeEdge(points, i, pixelAccessor); | ||||
367 | } | ||||
368 | | ||||
369 | // Iterate backwards in the style of Kalman filtering | ||||
370 | for(int i=1; i<points.count(); i++) { | ||||
371 | optimizeEdge(points, (points.count() - i - 1), pixelAccessor); | ||||
372 | } | ||||
373 | } | ||||
374 | m_lastPoints = points; | ||||
375 | } | ||||
376 | | ||||
377 | | ||||
378 | | ||||
379 | // Compute an edge segment. Walk along candidates in the direction normal to the tangent vector, | ||||
380 | // then select the point which is the best overall fit. Called from computeOutline(). | ||||
381 | const int max_iter=100; | ||||
382 | | ||||
383 | // Struct of parameters for GSL minimizer | ||||
384 | struct edge_params | ||||
385 | { | ||||
386 | QVector2D lastPoint; | ||||
387 | QVector2D centerPoint; | ||||
388 | QVector2D normal; | ||||
389 | qreal radius; | ||||
390 | KisRandomConstAccessorSP pixelAccessor; | ||||
391 | bool isFirst; | ||||
392 | KisSelectMagneticLocalTool *tool; | ||||
393 | }; | ||||
394 | | ||||
395 | // Function to use in gsl minimizer | ||||
396 | double f (double x, void * params) | ||||
397 | { | ||||
398 | struct edge_params *p = (struct edge_params *) params; | ||||
399 | | ||||
400 | // Compute distance metric components | ||||
401 | QVector2D newPoint = p->centerPoint + x * p->normal; | ||||
402 | QVector2D fromLastPt = newPoint-p->lastPoint; | ||||
403 | QVector2D gradient = p->tool->getEdgeGradient(newPoint, p->pixelAccessor); | ||||
404 | | ||||
405 | qreal dTheta = p->isFirst ? 0 : qAbs(shortestAngularDistance(atan2(gradient.y(), gradient.x()), | ||||
406 | atan2(fromLastPt.y(), fromLastPt.x()))); | ||||
407 | | ||||
408 | qreal dPrev = p->isFirst ? 0 : fromLastPt.length(); | ||||
409 | | ||||
410 | return edginess(gradient.length(), dTheta, dPrev, x, p->radius); | ||||
411 | } | ||||
412 | | ||||
413 | // Construct parameter vector for the penalty function | ||||
414 | edge_params constructEdgeParams(const QPolygonF &points, | ||||
415 | int i, | ||||
416 | const bool fromLeft, | ||||
417 | QVector2D lastPoint, | ||||
418 | qreal radius, | ||||
419 | const KisRandomConstAccessorSP &pixelAccessor, | ||||
420 | KisSelectMagneticLocalTool *tool) | ||||
421 | { | ||||
422 | | ||||
423 | QVector2D outwardNormal; // Outward as in "away from the edge" | ||||
424 | if (fromLeft) { | ||||
425 | outwardNormal = rotateCounterclockwise(tangentAtSegment(points, i)); | ||||
426 | } else { | ||||
427 | outwardNormal = rotateClockwise(tangentAtSegment(points, i)); | ||||
428 | } | ||||
429 | | ||||
430 | QVector2D centerPoint = QVector2D(points.at(i)); | ||||
431 | bool isFirst = (i == 0); | ||||
432 | return {lastPoint, centerPoint, outwardNormal, radius, pixelAccessor, isFirst, tool}; | ||||
433 | } | ||||
434 | | ||||
435 | | ||||
436 | // Struct of parameters for GSL minimizer | ||||
437 | struct neighbor_params | ||||
438 | { | ||||
439 | edge_params p1; | ||||
440 | const QPolygonF points; | ||||
441 | const int i; | ||||
442 | const bool fromLeft; | ||||
443 | const qreal x_next; | ||||
444 | const KisRandomConstAccessorSP pixelAccessor; | ||||
445 | }; | ||||
446 | | ||||
447 | // Compute the combined edge penalty function for this and the successor point | ||||
448 | double f_neighbor (double x, void * params) | ||||
449 | { | ||||
450 | neighbor_params *p = (neighbor_params *) params; | ||||
451 | | ||||
452 | // Easy part: The parameters for penalty at point i are fixed | ||||
453 | double res = f(x, &(p->p1)); | ||||
454 | | ||||
455 | // To evaluate the score at point i+1 we do two things: | ||||
456 | // 1) feed this point (i.e. currentGuess) as the previous point. | ||||
457 | // 2) pull x_next, which is from existing records. | ||||
458 | QVector2D currentGuess = p->p1.centerPoint + x * p->p1.normal; | ||||
459 | edge_params p2 = constructEdgeParams(p->points, p->i+1, p->fromLeft, currentGuess, | ||||
460 | p->p1.radius, p->pixelAccessor, p->p1.tool); | ||||
461 | | ||||
462 | return res + f(p->x_next, &p2); | ||||
463 | } | ||||
464 | | ||||
465 | | ||||
466 | // computeEdge does not use GSL optimization, just an ordinary search. | ||||
467 | // computeEdge constructs detectedBorder from an empty vector. | ||||
468 | const qreal SHORT_DISTANCE = 0.05; | ||||
469 | void KisSelectMagneticLocalTool::computeEdge(const QPolygonF &points, int i, const KisRandomConstAccessorSP &pixelAccessor) | ||||
470 | { | ||||
471 | qreal radius = m_selectionTool->radius(); | ||||
472 | bool fromLeft = m_selectionTool->searchFromLeft(); | ||||
473 | bool longestPathSeen = (m_detectedOffset.size() < (i+1)); | ||||
474 | bool pathShifted = (m_lastPoints.size() < (i+1)) ? true : (((QVector2D(m_lastPoints.at(i) - points.at(i)).length()) > SHORT_DISTANCE)); | ||||
475 | | ||||
476 | // Only recompute if (1) we are certain this is a new point, (2) we updated previous points in the path, or (3) the path changed significantly | ||||
477 | bool needsUpdate; | ||||
478 | QVector2D prevPoint; | ||||
479 | if (i == 0) { | ||||
480 | prevPoint = QVector2D(); | ||||
481 | needsUpdate = longestPathSeen || pathShifted; | ||||
482 | } else { | ||||
483 | prevPoint = QVector2D(m_detectedBorder.at(i-1)); | ||||
484 | needsUpdate = longestPathSeen || pathShifted || !m_converged.at(i-1); | ||||
485 | } | ||||
486 | | ||||
487 | | ||||
488 | edge_params p = constructEdgeParams(points, i, fromLeft, prevPoint, radius, pixelAccessor, this); | ||||
489 | if (needsUpdate) { | ||||
490 | double currMin = 0; | ||||
491 | int currMinOffset = 0; | ||||
492 | for (int k = -radius; k < radius+1; k++) { | ||||
493 | double testMin = f(k,&p); | ||||
494 | if (testMin < currMin) { | ||||
495 | currMin = testMin; | ||||
496 | currMinOffset = k; | ||||
497 | } | ||||
498 | } | ||||
499 | if (longestPathSeen) | ||||
500 | { | ||||
501 | m_detectedOffset.append(currMinOffset); | ||||
502 | m_converged.append(false); | ||||
503 | } | ||||
504 | else { | ||||
505 | m_detectedOffset[i] = currMinOffset; | ||||
506 | m_converged[i] = false; | ||||
507 | } | ||||
508 | qDebug() << QString("Estimated center x=%1").arg(m_detectedOffset.at(i)); | ||||
509 | } | ||||
510 | | ||||
511 | m_detectedBorder.append((p.centerPoint + m_detectedOffset.at(i) * p.normal).toPointF()); | ||||
512 | } | ||||
513 | | ||||
514 | // Backward filtering step. It tries to use GSL; if it cannot, it backs up to search. | ||||
515 | // It assumes m_detectedBorder, m_detectedOffset and m_converged are the correct size. | ||||
516 | // To combine the previous function and this one, we might want to start with a computeEdge step and add a GSL step with a shrunken boundary. | ||||
517 | void KisSelectMagneticLocalTool::optimizeEdge(const QPolygonF &points, int i, const KisRandomConstAccessorSP &pixelAccessor) | ||||
518 | { | ||||
519 | Q_ASSERT( i < (m_detectedBorder.size() - 1) ); // We cannot perform this step on the very last point | ||||
520 | | ||||
521 | int radius = m_selectionTool->radius(); | ||||
522 | qreal fromLeft = m_selectionTool->searchFromLeft(); | ||||
523 | QVector2D prevPoint = (i>0) ? QVector2D(m_detectedBorder.at(i-1)) : QVector2D(0, 0); | ||||
524 | edge_params p1 = constructEdgeParams(points, i, fromLeft, prevPoint, radius, pixelAccessor, this); | ||||
525 | neighbor_params p = {p1, points, i, fromLeft, m_detectedOffset.at(i+1), pixelAccessor}; | ||||
526 | | ||||
527 | gsl_function F = {&f_neighbor, &p}; | ||||
528 | int iter = 0; | ||||
529 | double guess = m_detectedOffset.at(i); | ||||
530 | double a =-radius; | ||||
531 | double b = radius; | ||||
532 | int status = gsl_min_fminimizer_set(minimizer, &F, guess, a, b); | ||||
533 | | ||||
534 | // If we encounter an error backup using brute force search method | ||||
535 | if (status) { | ||||
536 | double currMin = 0; | ||||
537 | int currMinOffset = 0; | ||||
538 | for (int k = a; k < b+1; k++) { | ||||
539 | double testMin = f(k,&p); | ||||
540 | if (testMin < currMin) { | ||||
541 | currMin = testMin; | ||||
542 | currMinOffset = k; | ||||
543 | } | ||||
544 | } | ||||
545 | m_detectedOffset[i] = currMinOffset; | ||||
546 | m_converged[i] = false; | ||||
547 | | ||||
548 | qDebug() << QString("gsl reported error %1; estimates are %2 %3 %4").arg(QString::fromLatin1(gsl_strerror(status))).arg(f(a,&p)).arg(f((a+b)/2,&p)).arg(f(b,&p)); | ||||
549 | } | ||||
550 | // Don't waste CPU cycles if we've already double-checked the estimate | ||||
551 | else if (!m_converged[i]) { | ||||
552 | status = GSL_CONTINUE; | ||||
553 | do { | ||||
554 | iter++; | ||||
555 | gsl_min_fminimizer_iterate(minimizer); | ||||
556 | if (iter > 10) { | ||||
557 | a = gsl_min_fminimizer_x_lower(minimizer); | ||||
558 | b = gsl_min_fminimizer_x_upper(minimizer); | ||||
559 | status = gsl_min_test_interval (a, b, 0.0001, 0.0); | ||||
560 | } | ||||
561 | } | ||||
562 | while (status == GSL_CONTINUE && iter < max_iter); | ||||
563 | | ||||
564 | // Store the result of the minimization. | ||||
565 | qreal x = (a + b)/2; | ||||
566 | qDebug() << QString("Converged in %1 iterations to x=%2 (center of interval [%3,%4])").arg(iter, 2).arg(x).arg(a).arg(b); | ||||
567 | if ((m_detectedOffset[i] - x) < SHORT_DISTANCE) { | ||||
568 | m_converged[i] = true; | ||||
569 | } | ||||
570 | m_detectedOffset[i] = x; | ||||
571 | } | ||||
572 | | ||||
573 | | ||||
574 | QVector2D currentGuess = p1.centerPoint + m_detectedOffset[i] * p1.normal; | ||||
575 | m_detectedBorder[i] = currentGuess.toPointF(); | ||||
576 | } | ||||
577 | | ||||
578 | | ||||
579 | | ||||
580 | // TODO: smooth the image first to decrease noise | ||||
581 | // TODO: see if the desaturate transformation is feasible | ||||
582 | QVector2D KisSelectMagneticLocalTool::getEdgeGradient(QVector2D& currentPoint, KisRandomConstAccessorSP& pixelAccessor) const | ||||
583 | { | ||||
584 | Matrix3d pointValues = getNearbyPixels(currentPoint, pixelAccessor); | ||||
585 | | ||||
586 | // Estimate horizontal and vertical components of the gradient using filters | ||||
587 | Matrix3d dX = pointValues.array() * horizontalFilterMatrix.array(); // eigen arrays do componentwise operations | ||||
588 | Matrix3d dY = pointValues.array() * verticalFilterMatrix.array(); | ||||
589 | return QVector2D(dX.sum(),dY.sum()); | ||||
590 | } | ||||
591 | | ||||
592 | | ||||
593 | Matrix3d KisSelectMagneticLocalTool::getNearbyPixels(const QVector2D &point, KisRandomConstAccessorSP pixelAccessor) const | ||||
594 | { | ||||
595 | QPoint currentPoint((qint32)point.x()-1, (qint32)point.y()-1); | ||||
596 | KoColor transformedColor(m_colorSpace); | ||||
597 | | ||||
598 | double coeff[3][3]; | ||||
599 | for(int i=0; i<3; i++) { | ||||
600 | for(int j=0; j<3; j++) { | ||||
601 | pixelAccessor->moveTo(currentPoint.x()+i, currentPoint.y()+j); | ||||
602 | // m_colorTransformation->transform(pixelAccessor->rawDataConst(), transformedColor.data(), 1); | ||||
603 | memcpy(transformedColor.data(), pixelAccessor->rawDataConst(), m_colorSpace->pixelSize()); | ||||
604 | coeff[i][j]=transformedColor.toQColor().valueF(); | ||||
605 | } | ||||
606 | } | ||||
607 | | ||||
608 | Matrix3d val = (Matrix3d() << coeff[0][0], coeff[0][1], coeff[0][2], | ||||
609 | coeff[1][0], coeff[1][1], coeff[1][2], | ||||
610 | coeff[2][0], coeff[2][1], coeff[2][2]).finished(); | ||||
611 | | ||||
612 | return val; | ||||
613 | } | ||||
614 | | ||||
615 | // Things seem to work fine if we don't do this clean up operation, so stick with that for now. | ||||
616 | // It also seems counter to an ultimate goal of using non-local optimization. | ||||
617 | const qreal minDeviation = .75; | ||||
618 | void KisSelectMagneticLocalTool::cleanDetectedBorder() | ||||
619 | { | ||||
620 | //load the points into a linked list, because removing on a vector is expensive | ||||
621 | QLinkedList<QPointF> detectedBorder; | ||||
622 | foreach(const QPointF &point, m_detectedBorder) { | ||||
623 | detectedBorder << point; | ||||
624 | } | ||||
625 | | ||||
626 | QLinkedList<QPointF>::iterator iter = detectedBorder.begin(); | ||||
627 | while ((iter+2) != detectedBorder.end() && (iter+1) != detectedBorder.end() && iter != detectedBorder.end()) { | ||||
628 | // Look to the next two points in the border | ||||
629 | QVector2D toNext = QVector2D(*(iter+1) - *iter); | ||||
630 | QVector2D toAfterNext = QVector2D(*(iter+2) - *iter); | ||||
631 | | ||||
632 | // qreal distToNext = toNext.length(); | ||||
633 | qreal angleToNext = atan2(toNext.y(), toNext.x()); | ||||
634 | qreal angleToAfterNext = atan2(toAfterNext.y(), toAfterNext.x()); | ||||
635 | | ||||
636 | // Throw away a point if it is close to being in a straight line with the successor. | ||||
637 | // If the three points are in a straight line, always throw the middle one away. | ||||
638 | qreal deviation = qAbs(angleToAfterNext-angleToNext)*toNext.length(); | ||||
639 | | ||||
640 | if( deviation< minDeviation) { | ||||
641 | // qDebug() << QString("Deleting point with nearness %2").arg(nearness); | ||||
642 | iter = detectedBorder.erase(iter); | ||||
643 | } | ||||
644 | else { | ||||
645 | iter++; | ||||
646 | } | ||||
647 | } | ||||
648 | | ||||
649 | m_detectedBorder.clear(); | ||||
650 | foreach(const QPointF &point, detectedBorder) { | ||||
651 | m_detectedBorder << point; | ||||
652 | } | ||||
653 | } | ||||
654 | | ||||
655 | //Close the path and add it to the selection | ||||
656 | void KisSelectMagneticLocalTool::addPathShape(KoPathShape* pathShape) | ||||
657 | { | ||||
658 | KisCanvas2 * kisCanvas = dynamic_cast<KisCanvas2*>(canvas()); | ||||
659 | if (!kisCanvas) return; | ||||
660 | | ||||
661 | KisSelectionToolHelper helper(kisCanvas, kundo2_i18n("Select by Magnetic Path")); | ||||
662 | if (m_selectionTool->selectionMode() == PIXEL_SELECTION) { | ||||
663 | | ||||
664 | KisPixelSelectionSP tmpSel = KisPixelSelectionSP(new KisPixelSelection()); | ||||
665 | | ||||
666 | KisPainter painter(tmpSel); | ||||
667 | painter.setPaintColor(KoColor(Qt::black, tmpSel->colorSpace())); | ||||
668 | painter.setFillStyle(KisPainter::FillStyleForegroundColor); | ||||
669 | painter.setAntiAliasPolygonFill(m_selectionTool->antiAliasSelection()); | ||||
670 | painter.setCompositeOp(tmpSel->colorSpace()->compositeOp(COMPOSITE_OVER)); | ||||
671 | | ||||
672 | QPolygonF path = QPolygonF(m_detectedBorder); | ||||
673 | painter.paintPolygon(path); | ||||
674 | | ||||
675 | QPainterPath cache; | ||||
676 | cache.addPolygon(path); | ||||
677 | cache.closeSubpath(); | ||||
678 | tmpSel->setOutlineCache(cache); | ||||
679 | | ||||
680 | helper.selectPixelSelection(tmpSel, m_selectionTool->selectionAction()); | ||||
681 | | ||||
682 | cleanEstimates(); | ||||
683 | delete pathShape; | ||||
684 | } else { | ||||
685 | helper.addSelectionShape(pathShape); | ||||
686 | } | ||||
687 | } | ||||
688 | | ||||
689 | #include "kis_tool_select_magnetic.moc" |