Re: Efficient Evaluation of Image Expressions

> 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

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