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
This tool would be aided by several steps performing pre-processing at tool activation. This means letting the tool store its own filtered, processed version of the image. I would need help with the Krita API here.
- Perform pre-blurring on the image. (Note: equivalent to using a wide derivative-of-gaussian filter)
- Consider Canny or other sophisticated edge detection algorithm.
- Generate a cache of edge gradients upon tool activation so they don't have to be re-computed all the time.
- Allow subpixel accuracy for computing the edge strength.
- Hook in with the pre-existing filtering classes, e.g. KisSobelFilter.
The algorithm itself will require major tweaking before it is competitive lasso tools in other software.
- //Done//: Switch to GSL for numerical optimization.
- //Done//: Save "committed" points so the path doesn't have to be recomputed with every redraw
- //Done//: Use a filtered/non-local optimization.
- Have the lasso procedurally create a spline instead of just individual points. (In other words, replace zig zags with smooth curves.)
A few subtle considerations that probably require a computer vision specialist.
- What rigorous metrics are there for generating a good trace? Even simply "following the literature" would be an improvement. What we do now is 100% ad-hoc.
- Multiscale edge detection and automatic orientation would be great. Following the above, doing these right requires coming up with a good metric that is "scale-independent."
- Edge detection currently uses only luminosity. What is the right way to do this with luminosity/hue/saturation all at once? (An example of why this is problematic: we will not detect an edge on canvas split down the middle red and green if the two pigments have the same luminosity.)
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 classic, 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.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 notes. Lecture 7 focuses on live wire methods. Other lectures focus on computation, including Image Foresting Transform, good for pre-processing. Another note [[http://www.ic.unicamp.br/~afalcao/talks/ift09.pdf | here]].
Edge detection
- [[ http://arxiv.org/abs/1406.5549 | Fast Edge Detection Using Structured Forests]]
- [[ http://web.mit.edu/phillipi/pmi-boundaries/ | Crisp Boundary Detection Using Pointwise Mutual Information ]]
- [[ http://arxiv.org/pdf/1406.6558v2.pdf | Neural Network Nearest Neighbor Fields for Image Transforms]]
- [[ 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 in Graph Cut Formulation: A Linear-Time Algorithm and a Comparative Analysis (2012) ]] Graph Cut Smackdown. 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 paper, motivates level set methods
- [[http://jgmalcolm.com/pubs/malcolm_lsdm.pdf | Fast approximate surface evolution in arbitrary
dimension (2008)]]
- [[ 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) ]]
- [[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]]
- [[ http://bigwww.epfl.ch/publications/bernard0901.pdf | Variational B-Spline Level Set (2009) ]] Returning B-splines as an output could be nice