Re: Efficient Evaluation of Image Expressions

Nick <Ibeam2000@gmail.com>
Sun, 22 Jul 2007 08:53:58 -0000

          From comp.compilers

Related articles
Efficient Evaluation of Image Expressions hermann.rodrigues@gmail.com (Hermann) (2007-07-18)
Re: Efficient Evaluation of Image Expressions torbenm@app-2.diku.dk (2007-07-19)
Re: Efficient Evaluation of Image Expressions tmk@netvision.net.il (Michael Tiomkin) (2007-07-19)
Re: Efficient Evaluation of Image Expressions Ibeam2000@gmail.com (Nick) (2007-07-22)
Re: Efficient Evaluation of Image Expressions hermann.rodrigues@gmail.com (Hermann) (2007-07-23)
Re: Efficient Evaluation of Image Expressions Ibeam2000@gmail.com (Nick) (2007-07-30)
Re: Efficient Evaluation of Image Expressions Ibeam2000@gmail.com (Nick) (2007-08-01)
| List of all articles for this month |

From: Nick <Ibeam2000@gmail.com>
Newsgroups: comp.compilers
Date: Sun, 22 Jul 2007 08:53:58 -0000
Organization: Compilers Central
References: 07-07-066
Keywords: optimize, analysis

> I have a language used perform map/image algebra calculations using
> expressions like the following:
>
> if isNull(i1) or isNull(i2) or isNull(i3) or isNull(i4) or isNull(i5)
> or isNull(i6) or isNull(i7) or isNull(i8)
> then null
> else
> (if (-4113.26 + 0.07*i7 - 5.08*i8/100 + 47.89*abs(i1) + 99.72*abs(i2) + 214.96*
> (
> -2.332 + 2.561*i4 + 0.55*i6
> ) +
> 1.57*i3) > 0 then .....


This sounds to me like a typical array programming problem. If the
code fragment you've supplied is the inner part of a larger loop which
iterates across eight potentially large bitmaps (arrays), and the
interpretive overhead of an expression far exceeds the time to
actually do the arithmetic, then one of your choices is to attempt the
operations as arrays.


As a programmer, I would definitely write the expression having
eliminated the common subexpression myself. (This was mentioned
earlier) At the very least, your code is much, much clearer.


Or use a max function. r := max(0, (-4113.26 + 0.07*i7 -
5.08*i8/100 .....


But if you can change your computational procedure to deal with i1,
i2, i3 as entire matrices, then at least you have a force multiplier
where you have do the parsing and tree traversal once, but get the
answers for a million or more pixels.


The operations +, -, /, *, abs, max, etc. should have the correct
missing value handing for nulls. 1 2 3 + 4 MV 6 should be 5 MV 9 and
so on.


If a substantial fraction of the pixels are nulls, then you can build
a mask, weed out only the relevant values, perform the computations,
then build a result using a null or the computed value for the
corresponding element, depending on the mask.


If i1 through i8 are small integer values always in the range of
0..255, then you can do the computations with pre-calculated tables.
(You can return scaled large integer values with just enough digits
behind the decimal places). If you truncate to get back a pixel
value, all that excess precision will be cut off.


Use 4 byte floats, rather than 8 byte doubles. (This is not a big
help)


I would suggest reading Jim Blinn's books, and Jon Bentley's book
"Writing Efficient Programs".


Also, have a look at "J", www.jsoftware.com, for ideas.


Regards, Nick



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.