1. Introduction
- Krita already had a magnetic lasso but that got lost while it was being ported to Qt4.
- This task was set up to port the tool but was later paused by the author who was working on it.
- This project aims to continue the work and complete the porting to the current version of Krita.
2. Project Goals
- Add the Magnetic Lasso Selection Tool in Krita.
- The tool when used should stick to the edges found in the picture.
- Starts after the user left clicks and makes an anchor, edges are scanned from the anchor point.
- After the mouse moves a fixed amount of distance the tool automatically places another anchor point and uses it as a reference.
- The user can also manually set an anchor point, him/herself.
- The search radius which is used to determine, up to what area the tool would search for an edge, as well as the frequency of anchors can be adjusted by the user.
- The above-mentioned parameters, as well as the threshold for determining edges, can be adjusted using the tool options widget.
The UI layout for the Tool Options Widget would be something like this
3. Implementation
How do we calculate the edge?
- Draw a straight line hypothetically from the last node to the current mouse position.
- Add the radius to get the approximate search area.
- Apply LoG to get the possible edges.
- Search area would be constant for a given radius and frequency of adding nodes.
- Start searching from the last node to get the nearest edge point, if the pixel determined as the nearest edge is not in the immediate neighborhood of the last node, just draw a straight line to it.
- Continue this process to the mouse position.
- If the length of the edge exceeds the frequency of nodes, add a node and continue.
Laplacian of Gaussian (LoG)
Implementation of LoG can be found in kis_gauss_kernel.cpp inside KisGaussianKernel::applyLoG, which was written during the implementation of the colorize mask. The implementation of KisMagneticSelectionWorker will be done in 2 stages. In the first stage, a test will be implemented so that we can verify the accuracy of our algorithm. For that, LoG will be applied to the whole KisPaintDevice. Later on, after we have done implementing the mouse-events we can adapt the algorithm for the selected region.
A-star search
We can use boost::astar_search from “boost/graph/astar_search.hpp” to implement the required A* search for the algorithm. The heuristic function for the A* search algorithm would be, given pi(xi,yi) the point for which the heuristic will be calculated, based on the Euclidean distance of the mouse cursor, pm(xm,ym) and distance from the base-line from last node p0(x0,y0) to pm , let’s take it as di, where
di= abs((ym-y0)*xi - (xm-x0)*yi + xm*y0 + x0*ym)/sqrt((ym-y0)^2 + (xm-x0)^2)
And taking the Euclidean distance from mouse cursor dm we get,
dm = sqrt((ym-yi)^2 + (xm-xi)^2)
We would be wanting the minimum distance from the mouse cursor and at the same time for as little deviation from the baseline as possible. So we could have the final result as a combination of the previous values,
dv = a*di+b*dm
where the values of a and b need to be derived experimentally.
I have worked on a small proof of concept, though not complete, it shows out how the original image, after applying the first approximation, will transform into something like this. On top of which we will be applying the A-star algorithm based on the source and final points.
4. Timeline
Community Bonding Period [May 6 to May 27]
- Know more about the development and the communication process in the Krita team.
- Add my blog to planet.kde.org .
- Create a task regarding the project on phabricator.
- Learn more about how KisPaintDevice is prepared for boost::graph.
- Prepare a skeleton for the test following KisWaterShedWorkerTest.
- Create a separate branch for the feature.
Deliverables Timeline
Implement KisMagneticSelectionWorker and a base test for it [May 27 to June 24]
- KisMagneticSelectionWorker should accept a KisPaintDevice and a radius for calculating edges for it.
- Reuse KisGaussianKernel::applyLoG for the first approximation.
- Develop the heuristic function for the A-star algorithm which would be used.
- Implement computeEdge() which takes lastEdgePoint, currentMousePos and returns a vector of QPoints representing the edge.
- KisMagneticSelectionWorkerTest should be implemented which would load a test image and run the algorithm.
- Write a blog post about the feature progress and the results obtained.
- Document the code.
Setup KisToolSelectMagnetic for basic line selections [June 25 to July 3]
- Overload the mousePressEvent for drawing nodes on Left Mouse Click and delete points on Right Mouse Click.
- Should be able to draw straight lines between the points.
- Overload the mouseMoveEvent for making the line follow the Mouse Pointer.
- Automatically place points after the mouse travels a certain distance.
Make room in KisMagneticSelectionWorker for KisToolSelectMagnetic [July 4 to July 22]
- Overload computeEdge() for taking a KisPaintDevice and a search area along with the other parameters.
- This will probably take some time to settle down, so need time for proper debugging.
- Another blog post detailing the progress.
- If possible a video on it too.
Add KisToolSelectMagneticOptionWidget for adjusting the constants [July 23 to August 5]
- Add a Tools Option Widget just like the other tools.
- Options to be adjusted: fuzziness, radius, and frequency of points.
Buffer Time [August 5 to August 26]
- If something goes wrong, we have time for that.
- Krita Sprints.
- Experiment with Sobel and fuzz based system.
- The final blog post.
- Again a video on the feature if possible.
- Prepare the branch for merging into master.
- Complete missing documentation of code and also document the feature on the Krita Manual.
The complete proposal can be found here, https://docs.google.com/document/d/1AF1U1Qb8JKS6Ky8pC_daDgeMDBrzVU8C7ulK_-0kg28/edit?usp=sharing
