Title and Due Date
Lazy Snapping: Optimizations and Extensions – Due March 10, 2006

Problem Statement
The current implementation of Lazy Snapping has severe bottlenecks which prevent it from being a truly real-time and interactive method for performing image cutout.  Several parts of the system need to be optimized or implemented differently.  Lazy Snapping also lacks some features which would improve usability, specifically editable cutout borders.  Finally, Lazy Snapping has room for improvement in terms of speed, accuracy, and interface.  We need to fine tune variables such as minimum segment sizes and edge weights in order to assure the best results and may be able to eliminate the need for user  interaction by incorporating saliency into the algorithm.       

Methods
The segmentation of the image can be improved by replacing the mean shift algorithm with the Watershed algorithm.

The accuracy and usability of Lazy Snapping can be improved by allowing users to perform boundary editing on the image cutout to better specify edges and user intent.  This will be accomplished by implementing a local color recalculation and cut.  By using image data, border editing will truly reflect the users intent and provide more accurate cuts.  Beyond this, improving the user interface by allowing for the drawing of new lines as borders will make for a robust tool. 

Saliency should transfer easily into Grab Cut, and should allow for image cutout without user interaction.  It is unlikely that saliency will be able to be transferred into Lazy Snapping easily, but this still needs to be explored.

Plan
Milestone 1: Replace mean-shift image segmentation with the Watershed algorithm.
Milestone 2: Profile the Lazy Snapping code to find bottlenecks and work to remove 		         them.
Milestone 3: Optimize Lazy Snapping by improving clustering and graph cut.
Milestone 4: Add Lazy Snapping to the existing image library.  
Milestone 5: Improve the Lazy Snapping UI by implementing an editable cutout 		          	         border which allows users to fine tune the results.
Milestone 6: Use the modular algorithms developed for Lazy Snapping to implement 		         Grab Cut, which should prove valuable for saliency research.
Milestone 7: Research the effects of using saliency for seed values.

Evaluation Criterion
Lazy Snapping should be able to operate at interactive speeds.  Users should be able to load an image, easily separate foreground and background, quickly receive feedback on the results of the algorithm, and edit those results until they obtain a satisfactory and accurate result.  Our results should be similar in quality to those present in the Lazy Snapping paper.

Lazy Snapping should be integrated into the image library in a modular and easy to use fashion.  Each part of the algorithm should be a separate implementation which could be used on any image for any purpose. (i.e. Separate image segmentation, clustering, graph cut, etc.)

Data should be collected on the running times of Lazy Snapping, especially with different segmentation methods and color models (if GMM's are transferable to Lazy Snapping).

Deliverables
A stand alone Lazy Snapping application which allows for users to load images, perform image cutout, edit the resulting cut easily by drawing new borders, and save the final foreground image.  The application will run at interactive speeds and include documentation to detail features and use.

The implementations of image segmentation, color clustering, graph cut, and lazy snapping with good documentation and easy to re-use code.  These will be combined with the image library for future use.

A final write up on the project, as outlined in the Instructions for "Handing-In" a 699 Project.


Readings
I have already read...
1)Lazy Snapping
2)Interactive Graph Cuts for Optimal Boundary and Region segmentation of objects in N-D images.
3)Watershed Segmentation from Digital Image Processing
4)"GrabCut": interactive foreground extraction using iterated graph cuts
5)Watersheds in Digital Spaces: An Efficient Algorithm Based on Immersion Simulations
6)Graphcut Textures: Image and Video Synthesis Using Graph Cuts
7)Complexity of Multiway Cuts
8)Interactive Digital Photomontage


Risks
Many of our goals have arbitrary time constraints as they focus on optimization and speedup.  This could lead to work taking longer than projected or needed and result in pushing many goals to the end of the project time line.  If we want to avoid a crunch at the end of 5 weeks, we will need to stay focused on our long term goals and ensure we don't get caught up in early optimizations. 

Motivation
Image cutout is a complex problem which has been solved with some success, but still contains much room for improvement.  A fast and accurate method to perform image cutout would be useful not only for image editing applications, but also in other image processing work.  If saliency proves a useful method for performing image cutout without user interaction, many other applications could benefit.  Also, each chunk of Lazy Snapping will prove useful to other image processing task, and will prove a beneficial addition to the image library.