[Bug 149485] Advanced image resize for the digikam editor

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





--- Comment #187 from Carlo Baldassi <carlobaldassi gmail com>  2009-05-15 01:44:25 ---
> Here is a message from Joe Auman the author of CAIR about parallelization of
> the content aware resizing algorithm:
Thanks a lot (to Joe for the interesting explanation and to Julien for
reporting it)!

About these points:

> For me, though, the most costly part of the algorithm is the actual seam
> removal. This is where multithreading helped me considerably. You may want to
> push Liquid Resize through a performance analyzer to determine the which parts
> would benefit most.
>
> For me, multithreading CAIR worked very well. However, Liquid Resize does
> things very differently (at least, thats what I can gather from the code). The
> benefits may or may not be as good as it was for me. Probably the only way to
> be truly sure is to multithread it and see what kind of performance you get
> out of it.
>

I went through a profiler, of course, and what I could see for large images is
that most of the time (~ 70%) was spent in the energy map updating, and almost
all the rest (~ 20%) in the actual seam removal. These operations are both
O(N^2) per seam (where N is the linear size of the image), while all the rest
is O(N) and therefore much less relevant. In LqR the seam operation is
extremely simple, however (it's in the function called lqr_carver_carve if you
want to have a look).
(Note: the energy update takes less than 1% with standard gradients but, since
now it is also possible to introduce custom energy functions, computing the
energy has also become a potentially expensive task if one uses some
computationally heavy function.)
Parallelising the the energy computation and the seam removal in LqR can be
done right away (a single OpenMP pragma is enough): I have now tried to
parallelise the carving operation and, to my surprise, I actually got a
performance loss. I have tested this on 2 and 4 core PC's and my results are
that more threads -> less performance, suggesting that the overhead cost for
this  operation is too high. I could still try something a little more
sophisticated, though.

About the energy map update: it should be indeed possible, with some
modification to the algorithm, to adapt the method described by Joe to the way
in which this is done by LqR (forcing only 2 threads to be started by OpenMP),
but given the above results I'm having doubts about the overhead. The method
proposed by Julien should also work, but it doesn't fit within the optimised
update function in LqR, because the for loop has variable extremes, and
furthermore starting and stopping the multithreading at each row would increase
the overhead even more, I guess.
I'm still looking for an alternative way to do it which could support more than
2 threads running in parallel and possibly without lockings and the like. I
have had some ideas about how to change the representation which could lead to
an improvement, but I haven't had the time to check them throughly yet (don't
know when I will have, actually). In the case I find out anything useful I'll
let you know.

P.S.: a note about terminology: here I used "energy map" just as Joe did, but
in the LqR documentation "energy map" means just "energy computed over the
image". Within the code, the equivalent of the CAIR "energy map" is called
"mmap". The relevant portion of the code we're discussing is therefore called
"lqr_carver_update_mmap".

Carlo

--
Configure bugmail: https://bugs.kde.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.
_______________________________________________
Digikam-devel mailing list
[hidden email]
https://mail.kde.org/mailman/listinfo/digikam-devel