Sign in to follow this  
Adam42

Magic wand performing badly on some images

Recommended Posts

The magic wand tool performs badly on some images.

 

Reproduction steps:

 

1. Create a 1000x1000 image.

2. Use the add noise effect to add some full intensity noise.

3. Select the magic want tool and pick global flood mode, 50% tolerance.

4. Click somewhere on the image, and press finish.

5. It will take about a minute, and use only one CPU core.

 

The same steps complete in a few seconds on an 800x600 image. A 2000x2000 image doesn't finish in a reasonable amount of time.

 

There's some sort of scaling issue here - surely the performance should be proportional to the number of pixels in the image.

 

Note that I've seen this slow performance of the magic wand tool in an actual photo from my camera, this is just a simple way to recreate it.

 

PC spec:

 

Intel Core i5 2500K (3.3 GHz).

8GB RAM

NVIDIA GeForce GTX 660

Windows 7 SP1 64-bit

Share this post


Link to post
Share on other sites

With the magic wand tolerance set at 50% and global you are locking on to the color you are touching with it,, in all shades. In a 800x600 image there are less of these spots to lock on to than a 2000x2000 image. It doesn't have warp drive you know,lol.  :)

Share this post


Link to post
Share on other sites

An 800x600 image is just under half a million pixels. The magic wand takes about 5 seconds, which is not too bad. A 1024x1024 image is just over a million pixels. With double the pixels you might expect it to take about 10 seconds. It actually takes about 60 seconds. The 2048x2048 image is just over 4 million pixels, and I got bored waiting for it to finish.

 

The photo I found the problem was 20MP but not as bad for performance as the random noise. Selections with the magic wand were taking over a minute though, which is a right pain when you want to play with the tolerance to find a value that works.

 

I've just done a touch more investigation. It seems most of the time is spent in a polygon cliiper. Here's an example call stack grabbed with Process Explorer:

 

PaintDotNet.SystemLayer.Native.x64.dll!gpc_polygon_clip+0x16ab
PaintDotNet.SystemLayer.Native.x64.dll!gpc_polygon_clip+0x1958
PaintDotNet.SystemLayer.Native.x64.dll!gpc_polygon_clip+0xe8
[Native Frame: IL Method without Metadata]
[Managed to Unmanaged Transition]
PaintDotNet.SystemLayer.dll!PaintDotNet.SystemLayer.FastMath.CombinePolyLists+0xa92
PaintDotNet.Core.dll!PaintDotNet.Rendering.GeometryList.Combine+0xd0
PaintDotNet.Core.dll!PaintDotNet.Rendering.GeometryList.FromNonOverlappingScans+0x178
PaintDotNet.Core.dll!PaintDotNet.Rendering.GeometryList.FromStencil+0x159
PaintDotNet.exe!PaintDotNet.Tools.MagicWand.MagicWandTool.CreateSelectionGeometry+0x449
PaintDotNet.exe!PaintDotNet.Tools.AsyncSelectionToolBase`2.<CreateSelectionOnBackgroundThread>b__9+0x5e
PaintDotNet.Base.dll!PaintDotNet.Functional.Func.Eval+0x31
PaintDotNet.exe!PaintDotNet.Tools.AsyncSelectionToolBase`2.CreateSelectionOnBackgroundThread+0x15a
PaintDotNet.Core.dll!PaintDotNet.Threading.ActionWorkItemQueue.OnExecuteNextWorkItem+0x52
PaintDotNet.Core.dll!PaintDotNet.Threading.MultithreadedWorkItemDispatcher.WorkThreadProc+0x345
mscorlib.dll!System.Threading.ExecutionContext.RunInternal+0x285
mscorlib.dll!System.Threading.ExecutionContext.Run+0x9
mscorlib.dll!System.Threading.ExecutionContext.Run+0x57
mscorlib.dll!System.Threading.ThreadHelper.ThreadStart+0x5d
[unmanaged to Managed Transition]
clr.dll!CoUninitializeEE+0x66b6b
clr.dll!CoUninitializeEE+0x66be6
clr.dll!CoUninitializeEE+0x66c58
clr.dll!StrongNameSignatureVerification+0x12f5d
clr.dll!CoUninitializeEE+0x712f4
clr.dll!CoUninitializeEE+0x71282
clr.dll!CoUninitializeEE+0x711f9
clr.dll!CoUninitializeEE+0x71357
clr.dll!StrongNameSignatureVerification+0x12e41
clr.dll!GetMetaDataInternalInterface+0x1def2
KERNEL32.dll!BaseThreadInitThunk+0xd
ntdll.dll!RtlUserThreadStart+0x21
 

If the "GeometryList.FromStencil()" function is doing what I think it is, I suspect it would be easy to optimize - something like http://en.wikipedia.org/wiki/Marching_squares springs to mind.

Share this post


Link to post
Share on other sites

Yeah. It's CPU intensive.

 

If the "GeometryList.FromStencil()" function is doing what I think it is, I suspect it would be easy to optimiz

IT IS NOT EASY TO OPTIMIZE. What algorithm do you think it's using, ffs?!

 

I mean c'mon you're purposefully tossing it into the absolute worst case scenario possible and expecting it to not be "boring." 

 

It's definitely faster than 3.5.

Share this post


Link to post
Share on other sites

If the "GeometryList.FromStencil()" function is doing what I think it is, I suspect it would be easy to optimize - something like http://en.wikipedia.org/wiki/Marching_squares springs to mind.

 

It's not a big surprize that the function spends a lot of time in a polygon clipping library. Polygon clipping is one of the basic parts of a software like Paint.NET. But optimizing this part is not trivial and it is risky because there are so many boundary cases which makes it difficult to test. From the function name you can expect that Paint.NET uses the General Polygon Clipping Library from University of Manchester. Personally I switched at some point from this library to Clipper form Angus Johnson. It perfoms much better than GPL (in my test cases). This does not mean that Paint.NET should change something in this area. At least not in a Beta phase.

Share this post


Link to post
Share on other sites

If the "GeometryList.FromStencil()" function is doing what I think it is, I suspect it would be easy to optimize - something like http://en.wikipedia.org/wiki/Marching_squares springs to mind.

What is wrong with people? If you're not a programmer, you don't have a clue how easy it is. If you are a programmer, you should know better. How do you have the slightest idea what Rick's codebase looks like? If you're not happy with PdN's performance, make your own image editor. Seriously, I would like to see it.
  • Upvote 4

Share this post


Link to post
Share on other sites

It's not a big surprize that the function spends a lot of time in a polygon clipping library. Polygon clipping is one of the basic parts of a software like Paint.NET. But optimizing this part is not trivial and it is risky because there are so many boundary cases which makes it difficult to test. From the function name you can expect that Paint.NET uses the General Polygon Clipping Library from University of Manchester. Personally I switched at some point from this library to Clipper form Angus Johnson. It perfoms much better than GPL (in my test cases). This does not mean that Paint.NET should change something in this area. At least not in a Beta phase.

 

Interesting ... that is a library worth checking out. The speed boost seems quite nice. I've been using GPC for a long time and one of the appeals is that, well, "it still works" :) (it hasn't broken, hasn't caused major problems other than out-of-memory which isn't really its fault, hasn't required me to keep up on big source code updates every over release, etc)

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this