How implementation works

How implementation works

Julien Narboux (guest) 25 Apr 2009 09:22

Hi,

We have a question about your implementation, what do you implement ? I think you implement V ersion B, did you ever tried to implement Version A ? does it create too many artefacts ?
Is your implementation O(h*w*s) where h= height w=widht and s= number of pixel to delete in one direction (assuming we just reduce in one direction) ? or is it O(h*w) ?

Version A

1- Compute energy
2- Find all paths of least energy
3- Delete the required number of paths

Version B

1- Compute energy
2- Find one path of least energy
3- Delete this path and update energy
4- Find another path of least energy, go to step 3

Thanks for your help.

Julien

Re: How implementation works

CarloB 25 Apr 2009 14:18

I implemented version B, which is O(h*w*s), but I have optimised it in order to retain as much information as possible from one step to the next. As for version A, an easy way to test how it performs is to try using the "Null" gradient in the GIMP lqr plugin and using the preservation mask as a gradient function (e.g. by duplicating a layer and filtering it with some edge detection algorithm such as sobel - note thar doing it that way is still O(w*h*s) because the algorithm it is not optimised for that specific situation, but the result is the same).
One could consider adding an option like "carve x seams at a time", to gain a factor x at the expense of a little accuracy, but it would need a lot of work in the core. Maybe I'll try to include this in version 0.5 or later.