I'm going to wait for the lazy fill brush to be implemented and then build off that work, since there should be many similarities between the way those tools function under the hood.
-------
The magnetic lasso tool was lost in the port to Qt4. The code was in bad shape, but is now in working condition. Before it is possible to add to Krita as an experimental feature, the magnetic lasso tool will need:
- New icons
- New cursors
- Redesign the on-screen feedback
Some of the changes need to hook into existing Krita API. Anyone know more about these?
- Hook in with the pre-existing filtering classes, e.g. KisSobelFilter, Gaussian Filter.
- Mip-maps
but there is a working version in https://phabricator.kde.org/D241. - StBefore pre-computed data caches, e.g. pre-blurring, edge gradients, color space transformations, IFTit is possible to add to Krita as an experimental feature, watershed regions / superpixels...
- Subpixel accessors for e.g.the magnetic lasso tool will need an internal rework, computing the edge strength interpolated between pixels.
- Using signals&slots to keep cache up to date. (If someone asks for it)
- Parallel processing (Get a single threaded approach working first,including an implementation of the A* algorithm. worry about this later)
Finally the tool itself will have to be resdesigned. This is completely open. It barely even has to look like a magnetic lasso. Doesn't even have to be called a magnetic lasso! "Refine edge," "Paint selection," "Smart Contours"I would suggest looking at Dmitry's implementation of the watershed algorithm to see how to do a fast parallel implementation of an image processing algo inside a tool.
Edge / Live-wire methods: somewhat similar to the existing tool
- [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.2987&rep=rep1&type=pdf | Intelligent Scissors (1998) ]] The classicThe main thing that needs work is ergonomics, implemented by GIMP
- [[ http://wcours.gel.ulaval.ca/2013/a/GIF7002/default/5notes/diapositives/pdf_A13/lectures%20supplementaires/C08e.pdf | Edge and line oriented contour detection: State of the art (2011) ]]
- [[http://www.ic.unicamp.br/~afalcao/mo815-grafos/a13.pdf | Live Wire On The Fly (2000) ]] Super fast,which is all about finding a really nice "edge detection" algorithm and weighting scheme. perhaps also straightforward to implement
- [[http://www.math.lsa.umich.edu/~esedoglu/Papers_Preprints/xbresson_gmac_jmiv05.pdf | Fast global minimization of the active contour/ snake model (2005) ]]
- [[ https://hal-upec-upem.archives-ouvertes.fr/hal-00622510/document | Power Watersheds: A Unifying Graph Based Optimization Framework (2012) ]]
- [[ http://www.cb.uu.se/~filip/ImageProcessingUsingGraphs/schedule.html | Image Processing Using Graphs ]] Lecture noteYou need to be clever about how you do "edge detection" - a simple Sobel filter gives really rough noisy results. Lecture 7 focuses on live wire methods.To get a good result you'll want to find edges based on hue and value changes separately at a minimum, Several lectures on computation.maybe mix different edge detection filters, Another note [[http://www.ic.unicamp.br/~afalcao/talks/ift09.pdf | here]]or other clever stuff, you'd need to play with it. Another ergonomic concern is figuring out the timing of "commits" where the lasso path freezes and you start your A* path search in the next section.
Edge detection
- [[ http://arxiv.org/abs/1406.5549 | Fast Edge Detection Using Structured Forests]]Here are a few papers about high quality edge detection. They seem way too bright and shiny for something as old as the magnetic lasso, but perhaps they cite other interesting, older methods that could be useful for realtime applications.
- [[ http://web.mit.edu/phillipi/pmi-boundaries/ | Crisp Boundary Detection Using Pointwise Mutual Information ]]
- [[ http://arxiv.org/pdfabs/1406.6558v2.pdf | Neural Network Nearest Neighbor Fields for Image Transforms5549 | Fast Edge Detection Using Structured Forests]]
- [[ http://arxiv.org/abs/1412.1123 | DeepEdge (2014) ]]
Graph cuts: fast approximate global methods well adapted for interactive use
- [[ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.297.9821&rep=rep1&type=pdf | Image Segmentation by Iterated Region Merging with Localized Graph Cuts (2011) ]] Results look great, but speed?
- [[ http://research-srv.microsoft.com/en-us/um/people/jiansun/papers/PaintSelection_SIGGRAPH09.pdf | Paint Selection (2009) ]]
- [[ http://medialab.sjtu.edu.cn/teaching/DIP/Projects/chapter_seg/SurveyGraphImageSegmentation.pdf | A survey of graph theoretical approaches to image segmentation (2013) ]] Authors ultimately recommend their own paper, listed above.
- [[ http://www.math.wvu.edu/~kcies/Other/ElectronicReprints/106.FCvsGCReprint.pdf | Fuzzy Connectedness Image Segmentation: A Linear-Time Algorithm (2012) ]] Supposedly a new, fast algorithm is buried under the math?
Level sets: robust class of global methods, numerically slow
- [[https://vision.in.tum.de/_media/spezial/bib/cremers_rousson_deriche_ijcv07.pdf | A Review of Statistical Approaches to Level Set Segmentation (2007) ]] Overview paperAfter all that, motivates level set methods
- [[http://jgmalcolm.com/pubs/malcolm_lsdm.pdf | Fast approximate surface evolution in arbitrary dimension (2008)]]it will need:
- [[ http://www.ntu.edu.sg/home/asjfcai/TIP-07763-2011_2column.pdf | Robust Interactive Segmentation using Convex Active Contours (2011) ]] Champion performer, though speed is a concern
- [[http://ocw.mit.edu/courses/mathematics/18-336-numerical-methods-for-partial-differential-equations-spring-2009/readings/MIT18_336s09_read04_levelsetpres.pdf | Level set method - MIT 336 lecture notes (2009) ]] - New icons
- [[http://www.robots.ox.ac.uk/~varun/research/gsc.pdf | Geodesic star convexity (2010) ]] Code available [[http://www.robots.ox.ac.uk/~vgg/software/iseg/ | here]] - New cursors
- [[ http://bigwww.epfl.ch/publications/bernard0901.pdf | Variational B-Spline Level Set (2009) ]] Returning B-splines as an output could be nice
- Redesign of the on-screen feedback