How does Photoshop's magnetic lasso work?

Question

Seems like GIMP's intelligent scissor is based on a paper from SIGGRAPH '95 on "Intelligent Scissors for Image Composition", as seen in one of the comments in the source.

However Magnetic Lasso in Photoshop differs a lot, while GIMP's tool gives users an option to click vertices of desired figure and approximates along edges found in the image, photoshop's magnetic lasso on the other hand, gives users a way to run freehand and gives something between computerized approximation and what the user desired to draw.

Looking at this behavior its quite obvious that Magnetic Lasso style selection would quite cool for selection in touch based interfaces. Any pointers on how magnetic lasso differs from the GIMP's tool? Any specific papers/algorithms to look into?

Landpoor

~ Are you able to say what language or platform you'ld be writing this for? Will this be for an iPhone or Android or ... Depending on the available languages and APIs it might be easier or more difficult – Prothrombin

I am targeting iPads, the idea is to try creating it with canvas/svg+javascript, if that becomes computationally infeasible or too tough to do with them, then probably with DrawKit's vector support as a native app. – Landpoor

Answer 1

One algorithm you can look into is Marching Squares.

Barrack

Answer 2

The Magnetic Lasso tool is especially useful for quickly selecting objects with complex edges set against high-contrast backgrounds.

1. Detect the edges in the picture using an edge detection algorithm.
2. Wait for the left mouse click event.

3. Snap to the nearest detected edge and begin a line segment.

   3A. Track mouse movement, snapping to detected edges.

   3B. If the left mouse button is clicked begin a line segment from the end of the previous one or finish the current one.

   3C. If a line segment was created, conform the line to the detected edges in the area.

   3D. If the ESC key or right mouse button is clicked, enclose the detected area by creating a line segment from the first point to the last point.

Voilà, you have a 'magnetic lasso'.

Escolar

He's targeting iPads ... not much call for a left mouse button, etc. How do you know for sure which edge to highlight on a narrow item? But the idea is sound. – Prothrombin

Sounds nice, but what if you have a soft contour 10 pixels from pointer and strong contour 20 pixels from pointer? To which contour should you snap? There are many other unanswered questions in this approach ... – Anaglyph

Answer 3

Seems like GIMP's intelligent scissor is based on a paper from SIGGRAPH '95 on "Intelligent Scissors for Image Composition", as seen in one of the comments in the source.

However Magnetic Lasso in Photoshop differs a lot,

The document with the algorithm for Intelligent Scissors is here

Regarding the relation between algorithms, this article says

Software company Adobe, which has long had a relationship with BYU's computer scientists, helped fund the research for development of Live Surface. An earlier software, developed by Barrett and his students under the name Intelligent Scissors, was renamed Magnetic Lasso and is now incorporated into 5.0 Adobe PhotoShop, where it quickly yanks two-dimensional objects out of images.

Amadis

Answer 4

I have successfully implemented Magnetic Lasso using the article that you mentioned - Intelligent Scissors for Image Composition. I also implemented iterative extending of searched area and "path cooling".

You can see my implementation at www.Photopea.com (drag and drop your own image, roll over lasso, choose Magnetic Lasso). So it is possible and not that hard to implement :)

Anaglyph

Did you really use the original paper? If so, how did you handle graph search for large images? When the size of the image grows, the graph grows tremendously, hurting the interactivity of the algorithm – Coltish

That photopea app is super awesome. Did you create that entire program yourself? – Lupulin

@Mr.Me Thanks! Yes, I did :) – Anaglyph