[Haskell] Image manipulation

[Bjorn Lisper]

Jerzy Karczmarczuk:
>Dan Piponi adds to a short exchange: 
>
>> jerzy.karczmarczuk:
>>> [iso-8859-1] Bj�rn Wikstr�m writes: 
>>>
>>> > Hi! I have lots and lots of images (jpegs) that I would like to manipulate
>>> > and shrink (in size). They are around 5 Mb big, so I thought this would
>>> > be a good Haskell project since it's a lazy evaluating language.
>>> ...
>>> I must say that I don't see much use of laziness here.
>
>> Laziness plays a big role in real world image processing. Typically,
>> in applications like Apple's Shake, you build a dataflow
>> representation of the image processing operations you wish to perform,
>> and the final result is computed lazily so as to reduce the amount of
>> computation. For example, if you blur an image, and then zoom in on
>> the top left corner, then only the top left corner will be loaded up
>> from the original image (assuming your image file format supports
>> tiled access). You still work on tiles or scan-lines, rather than
>> individual pixels, so the laziness has a 'coarse' granularity. 
>> 
>> But I'm not sure if this is what the original poster was talking about.
>
>I am neither...
>Still, Dan, I think that there is quite a difference between incremental
>processing of signals, and images, etc., and the *lazy evaluation* of
>them. Of course, a stream is consumed as economically as it can, but
>not less. If you filter an image (shrinking, so some low-pass MUST be
>done), a pixel must be loaded with its neighbourhood, which means *some*
>scan lines.
>With a JPEG this means that a 8x8 block should be loaded also with its
>vicinity. But would you suggest that individual pixel processors should
>be lazy? It would be useless, and probably resulting in some penalties. 
>
>So, the laziness of Haskell for me here is less than useful.
>Noooow, the lazy *generation* of streams is another story...
>Generating music (low level, i.e. sound patterns) through lazy algorithms
>is quite interesting. 

Wait, Jerzy. Haskell implementations do not have to be lazy as long as they
preserve the more abstract semantics. Optimistic evaluation has been
considered, for instance by Robert Ennals. My former PhD student Karl-Filip
Faxen studied optimizations based on "cheap eagerness", simple cases where
it is easy to see that it pays off to generate code that is not totally
lazy. One case is if we know that a computation always terminates and takes
little time, then it can typically pay off to perform that computation
optimistically even in cases where a lazy evaluation strategy might have
avoided it.

For image processing, if we know that individual pixel computations
terminate then the compiler is free to carry (a finite number of) them out
in any order, even if some of them turn out not to be needed. So tiled
computation schemes are certainly possible, even if parts of some tiles fall
outside the final image.

Another thing is that current Haskell compiler don't work like this. But
Haskell itself does not prevent it.

A number of years back I worked on something called the "data field model",
a kind of generalized array construct intended for high-level data parallel
programming. We also defined and implemented a dialect of Haskell called
"Data Field Haskell" which extended Haskell with one particular instance of
data fields. Data Field Haskell had a function to force the evaluation of
all elements in a data field at once. The purpose of this function was
exactly to make possible computations like the above, where it pays off to
evaluate data fields, or parts of them, in a non-lazy fashion. I am quite
confident that it would be easy to express the image processing mentioned
above in Data Field Haskell.

Alas, we were never able to do anything else than a proof-of-concept
implementation. If anyone is interested to see what we did, there was a
paper in the Haskell Workshop 2000.

Björn Lisper