The objective of this project is to understand the algorithm beneath the magnetic lasso tool. Magnetic lasso tool is one of the common tools found in tools like Gimp, Adobe Photoshop etc. In this project we build a tool which allows a user to cut an object out of an image and paste it into another. The tool is intelligent in the sense that it snaps to the edges it detects in the underlying image.
This project was done as a part of the course “Computer Vision (COMP-5421)” at HKUST during spring 2014 (Feb-May 2014). The project partners were Manohar Kuse (myself) and Sunil Jaiswal. The course instructor for this course was Prof. Chi Keung Tang. Further, I also acknowledge that part of the text presented here comes from the course website of COMP-5421.
Thanks to David Doria for providing the CMake file.
Artifacts Created with this Tool
Source code & executable can be downloaded from : [link]
View the GUI demonstration video here : [YouTube]
Read “Other Technical Info” section (below) for more details on implementation related info.
CMakeFile for the project thanks to David Doria [CMakefile.txt] .
This program is based on the paper titled Intelligent Scissors for Image Composition, by Eric Mortensen and William Barrett, published in the proceedings of SIGGRAPH 1995. The way it works is that the user first clicks on a “seed point” which can be any pixel in the image. The program then computes a path from the seed point to the mouse cursor that hugs the contours of the image as closely as possible. This path, called the “live wire”, is computed by converting the image into a graph where the pixels correspond to nodes. Each node is connected by links to its 8 immediate neighbors. Note that we use the term “link” instead of “edge” of a graph to avoid confusion with edges in the image. Each link has a cost relating to the derivative of the image across that link. The path is computed by finding the minimum cost path in the graph, from the seed point to the mouse position. The path will tend to follow edges in the image instead of crossing them, since the latter is more expensive. The path is represented as a sequence of links in the graph.
The paths from the seed point to the subsequent points is the graph-shortest path. Note that the entire image is represented as a graph. This shortest path is computed with the Dijkstra’s Algorithm .
- File –> Open : Browse files and open image to mark
- File –> Write Contour : Write the delineated path as a PNG image
- File –> Write Mask : Write the marked mask as a PNG image
- File –> Quit : Quit the program
- Scissor –> Activate Scissor (check-able) : Activate/De-activate the intelligent scissor tool
- Scissor –> Reset Contour : Reset the delineated contour.
- Scissor –> Overlay Contour (check-able) : Activate/De-activate the display of delineated contours
- Image –> Zoom In : Zoom into the image
- Image –> Zoom Out : Zoom out of the image
- Image –> Blur : Blur image with 3×3 kernel
- Image –> Blur : Blur image with 5×5 kernel
- Image –> Gaussian Blur : Gaussian blur image
- About –> Help : Display usage
- About –> Authors : Gives the names of the software’s creators
- About –> Qt : Gives the version of Qt
Other Technical Info
The language of this software is C++. The entire software is built using the Qt-creator on Ubuntu 12.04. GUI uses the Qt libraries. Image processing is done using OpenCV 2.3. C++ STL libraries is used for the priority Queue. QMake & Makefiles is used for built configuration. The software is developed and tested on Ubuntu 12.04. However, Qt being cross platform, the entire code is possible to be executed on Windows without changes to source-code. If you are deploying it on Windows, be sure to have OpenCV 2.3 (or above) working with MinGW. If you do get this working on Windows do let me know, I would be happy to post that code here and acknowledge you for the efforts.
The run time for each run of Dijstras is about 400ms for images of size 640×480. This is real-time. However, for images of sizes more than 2000×2000 it takes about 4 sec.
Download artifacts & related files here : [link]
<<<PUT MORE ARTIFACTS HERE >>>
Possible Future Work
- Extend the GUI to handle deletion & changes to seed points.
- Use path fast path finding algorithms like A-star
- Optimize implementation of Dijkstra’s.
- Use of parallel Dijkstra’s algorithm either on GPU and/or Multi-core CPUs. Look at the paper by John Owens titled “Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths”
Mortensen, Eric N., and William A. Barrett. “Intelligent scissors for image composition.” Proceedings of the 22nd annual conference on Computer graphics and interactive techniques. ACM, 1995.