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

[Julien Narboux]

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





--- Comment #185 from Julien Narboux <Julien narboux fr>  2009-05-14 14:02:07 ---
Hi all,

Here is a message from Joe Auman the author of CAIR about parallelization of
the content aware resizing algorithm:


Before I begin, I would like to clarify a few terms so we're all on the same
page. The really basic steps to seam carving are generating a representation of
the energy of the image, from that representation then generating an energy map
and determining the least energy seam, and then removing that seam from the
image.

The way CAIR (and I believe Liquid Rescale) represents the energy of the image
is gradients, ie edge detection. Its a simple process that works very well for
seam carving, and can also be done fairly quickly. In your email I think you
refer to this as simply “energy”. When you say “seams of minimum energy”, I
assume you mean the energy map. (This might help if you haven't seen it before:
http://c-a-i-r.wiki.sourceforge.net/Image+Energy)


CAIR uses mulithreading in of the steps: calculating gradients, building the
energy map, and removing the seam. The general rule for multithreading is: if
it takes less time to perform a context switch and handle other threading
overhead than it does to actually perform the calculations, then its beneficial
to perform mulithreading. For me, I found that even if you only update affected
areas, it was still beneficial to multithread.

The energy map is obviously the problem. By the very nature of the algorithm,
it cannot be easily multithreaded since there is a dependency of values between
areas where the threads are working.
For CAIR, the way I tackled the problem was to create two threads, one handling
the left side of the image and one for the right side. Between them there was a
boundary, where one thread would need a value that was maintained by the other
thread. I protected each one of these boundary pixels by mutexes. When one
thread finished updating a boundary pixel, it unlocked the associated mutex.
When it needed a value from the other side of the boundary, it tried to lock
that mutex. I have some comments in my code that might explain it a bit better:
//=========================================================================================================//
//threading procedure for Energy Map
//-main signals to start left
//-main waits for left to signal locks_done
//+left starts and locks mutexes
//+left signals main locks_done
//+left waits for good_to_go
//-main starts and signals start right
//-main waits for right to signal locks_done
//#right starts and lock mutexes
//#right signals main locks_done
//#right waits for good_to_go
//-main starts and signals good_to_go twice
//-main waits for finish twice
//+#left and right start and do there thing
//#+left and right signal finish when done
//+#left and right wait for their start
//-main starts and continues on

//The reason for the crazy mutex locking is because I need to evenly split the
matrix in half for each thread.
//So, for the boundry between the two threads, they will try to access a value
that the other thread is
//managing. For example, the left thread needs the value of an element on the
boundry between the left and right threads.
//It needs the value of the three pixels above it, one of them, the top-right,
is managed by the right thread.
//The right thread might not have gotten around to filling that value in, so
the Left thread must check.
//It does that by trying to lock the mutex on that value. If the right thread
already filled that value in,
//it'll get it immediately and continue. If not, the left thread will block
until the right thread gets around
//to filling it in and unlocking the mutex. That means each value along the
border has its own mutex.
//The thread responsible for those values must lock those mutexes first before
the other thread can try.
//This limits one thread only getting about 2 rows ahead of the other thread
before it finds itself blocked.
//=========================================================================================================//

My threading was all done in pthreads. Whatever threading scheme you use may
not have the problems I ran into with the energy map. It is also possible to
have more than two threads dealing with the energy map. Interior threads would
have to wait on values from threads on both sides of its working area. My other
investigations into how to break the algorithm into more thread-easy methods
pretty much failed, though, I would be happy to investigate alternatives.

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.


If you have any other questions, please, don't hesitate to ask.

- Joe Auman

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