Re: [Gimp-developer] Hints on image reduction algorithm

[Vincent Cadet <v_cadet yahoo fr>]

Thanks for your hints, Daniel.

--- En date de : Lun 11.2.13, Daniel Hornung <daniel hornung gmx de> a écrit :

> On Monday, 11. February 2013 16:15:06
> Vincent Cadet wrote:
> > Hello people.
> > 
> > I am looking for an algorithm to reduce a screen image to a very small size,
> > e.g. 3x2 pixels width x height so as each pixel is the average colour (RGB)
> > of the corresponding screen area. 
> > ...
> > There are Arduino kits for the hardware part so I'm focusing on the software
> > part right. Most algorithms I saw are screen grabbing and involve nested
> > loops for each pixel and I'm sure there's a better way. (E.g. MMX
> > instructions?) I thought of JPEG reduction since it corresponds to what I
> > need if you keep only the average from the spectrum. So my question is: can
> > the JPEG compression algorithm be effectively used and optimized to get
> > that to work? Or if you have better ideas or hints, I'm open.
> 
> Hello Vincent,
> 
> first of all, you probably don't want to use GIMP for this task, I assume you 
> just write here because you guess that people here can answer anyway. :-)

Exactly. I came to ask here as there are some of you who have far more skills than I have (none actually). My guess is dev's behind Gimp are the ones who must know which algorithm best fits and what considerations to take into account, especially in that very case: smallest image size.


> What do you mean by nested loops?  Averaging over a (very) large number of 
> elements is not trivial, since you don't want to run into numerical precision 
> or overflow problems.

It is not trivial, indeed. That's what I thought. The algorithm I had in mind when posting is like this:

. loop through each row, skipping one line over two:
    loop through each column, skipping one columns over two:
      sum RGB value for the current pixel

. when nested loops are done divide RGB value with the number of steps

This is of course the definition of "average" or "mean" but there had to be a better way to me. My take is for instance when you consider low pass filters, it's far more efficient (IIRC) to use shift registers while one would think of looping, summing and averaging. I'm referring to my courses in signal theory (taken like 20 years ago, you get the picture :D) when "mapping" complex functions into discrete algorithms. So I assumed there are similar formulas for image computations.


> But all in all you probably don't want jpeg or other fancy and time-consuming 
> stuff, but just average the R, G and B components.

That I didn't know. Thanks for the hint.


> Your compiler should do  all the processor specific optimization for you anyway, I
> think.  In a few  little tests I did with XGetImage(...), most of the time was
> used by copying  the screenshot into memory, I ended up at around 30ms per
> image.

I know the compiler is smart enough to optimize if I tell it so. But I also know a compiler is blind to wishes and you have to lay your code as optimization-friendly as can be so it "guesses" right how to efficiently optimize it (that's a couple of years of development have taught me ;-).

Note that I have read about GCC and it looks like it's now able to "parallel'ize" loops. That would probably be useful in this very case since screen regions are predictable so as are the memory portions the nested loops inspect. I just wonder if that's enough of an optimization though.

Also 30 ms, even in this worst case, leaves me with another 70ms to do the analysis.


> If you are looking for optimization: Reduce the resolution you work with (if 
> that's possible with your preferred screengrabber library), you won't see the 
> details in your 6 LEDs anyway ;-)  And reduce your framerate and simply 
> interpolate the color in between, your eyes probably won't see a difference.

Talking about it (reducing the resolution) are there any wise paths to follow (to add to those you gave)? Like taking one pixel out of 4 or 16 or... is it that simple? From your experience, what would then be the best ratio? One pixel out of a 8x8 square, for instance (referring somehow to JPEG image "slicing")? I can also use smaller areas, like stripes near the borders of the image, I guess...

Or can I for instance sample random, small regions of contiguous pixels from the grabbed image and compute the average from that? Do you know if there's an API that can do that (might be not the right place to ask, I admit)?

As for the screen grabber library... well it's my first attempt into Linux development :D . Quite a nice challenge you'll say. So I have basically no idea what grabbing functions do exist. I can Google that of course but do you by chance have an idea if (and which) are the best candidate for the job? I also would like one that works even with full-screen OpenGL games.


> Have fun with this project and show some photos later on!

Hehe, thanks for your interest, I'm flattered, no kidding. But I'd rather show the code beforehand instead ;-) .

Vincent



> Daniel
> 
> -- 
> Mein öffentlicher Schlüssel / My public key:
> 4096R/600ACB3B 2012-04-01
> Fingerabdruck / Fingerprint:
> 9902 575B B9A0 C339 CFDF  250B 9267 CA6B 600A CB3B
> Runterladen z.B. bei/ Get it e.g. from:
> pgp.mit.edu, subkeys.pgp.net, pgp.uni-mainz.de,
> pool.sks-keyservers.net, ...
> -----La pièce jointe associée suit-----
> 
> _______________________________________________
> gimp-developer-list mailing list
> gimp-developer-list gnome org
> https://mail.gnome.org/mailman/listinfo/gimp-developer-list
>