[Digikam-devel] [Bug 149485] Advanced image resize for the digikam editor

[Carlo Baldassi]

https://bugs.kde.org/show_bug.cgi?id=149485





--- Comment #165 from Carlo Baldassi <carlobaldassi gmail com>  2009-04-28 02:13:34 ---

> Andi, you are right speed should/could be improved.
Yes, I don't know how they do it in Photoshop of course (nor which hardware the
demos were run onto), but I suspect some approximation with respect to the
original algorithm is taken in order to speed up things. Also, lacking some
options as the step and rigidity, it can be more optimised as Julien said. It
is also possible that the GPU is used, as I've been told that PS can do that.
Is there anyone who can make a direct comparison?

> 1- First we should use the Lqr library properly, in the current code each time
> we resize we rebuild every thing from scratch ! but Lqr library maintains data
> structures to have a quicker rescale after the first rescale if we use it
> properly, we simply do not use this for the time being, I will talk about that
> with Gilles.
You can have a look at the interactive code in the GIMP plugin if you wish,
which exploits that feature of lqr. And you can ask me of course if in doubt
(there are some tricky issues; for example it is not possible to keep the
carving information when scaling in 2 directions at the same time - this is a
long-standing problem which should be addressed somehow).

> 2- Second, Lqr implementation of the rigidity option may not be optimal, when
> rigidity=1 (default value) It may be possible to write specialized code which
> would be better optimized by gcc. From a post I read comparing ocaml
> implentation of seamcarving and Lqr, it seems that Carlo is aware of that.
Actually, that discussion was mainly about the step rather than the rigidity
(BTW increasing the step slows down everything much more than increasing the
rigidity, as you might have noted). Unfortunately, it wouldn't be very useful
now to optimise the update function in the way which was considered in that
post about the ocaml implementation, because to do that I would need to give
away another optimisation I'm using (and which is more general and gives
comparable results in terms of computational time).

> 3- Current implementation of Lqr computes the energy then finds the path of
> least energy, then removes it, then updates energy, then finds again path of
> least energy and so on...
> To compute the path of least energy in fact one computes all the paths of least
> energy, so in fact several seams could be removed at the same time without
> recomputing the updated energy. When need to study if this leads to too many
> artefacts. Lqr author may implement this optimization in 0.5.
> Look at http://liblqr.wikidot.com/forum/t-151301/how-implementation-works
This also is a little bit more tricky, as the library does not really compute
_all_ the paths of least energy. I hope to come up with a solution to do this
efficiently, but as I wrote in the liblqr thread it will need quite some work
(+ lots of testing).

> 4- Parallel computation: we could compute the paths of minimum energy using
> several threads.
I like the idea of Gilles to use OpenMP: I know it a little bit and it's
amazingly simple to adapt code to use it - if the code is already written in a
way which makes it easy to distribute the computation among several cores. The
problem here is that the task (finding the path of minimum energy) is a global
one in nature. It's still not obvious to me how this could be consistently
divided into local parallel computations, but I'm quite confident that this is
possible - this is a major future goal for the library development (and any
ideas would be very appreciated, of course).

That said: I have completed the new framework for the energy computation which
allows 1) to use custom energy functions and 2) to get previews of the energy.
I have pushed it in the master branch of the git repo, and since it is
backwards compatible it can already be uses with the DigiKam code. It is not
documented yet, however.
I have also written a function to add a bias pixel by pixel, the synopsis is:

LqrRetVal lqr_carver_bias_add_xy(LqrCarver * carver, gdouble bias, gint x, gint
y)

(the usage should be obvious - just keep using values of the order of 10k for
the bias)
Please, report me any problems you might find, I did a lot of testing (also
with valgrind) and everything seems to work fine, but you never know...

Carlo

-- 
Configure bugmail: https://bugs.kde.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.