[ptx] RLE encoding images.

[Terje Mathisen]

[Terje, all your messages are being delayed on the server because
they are being sent to ptx-bounces at email-lists.org instead of
the right address: ptx at email-lists.org - Bruno]

ptx-bounces at email-lists.org wrote:

> On Tue, 04 May 2004, Terje Mathisen wrote:
>>>Now we just need vigra::RLEImage.
>>
>>I suggest a very simple encoding:
>>
>>[count][value] pairs stored as unsigned bytes. This could require a few 
>>extra pairs for very long repeat counts, but at 128:1 compression, it 
>>really doesn't matter.
>>
>>If you want to be fancy, then you use the fact that a repeat count of 
>>zero is impossible: Instead, this means that the next byte will be a 
>>count of uncompressed bytes following:
>>
>>[0][count][a,b,c,d,e,...]
>>
>>I.e. you'd use this for graduated masks where the repeat count averages 
>>less than two.
> 
> Yes, that sounds quite nice. However, I want to stick to the vigra idea and
> write a generic RLEImage<PixelType> class that can work with any pixel type,
> not just bytes. therefore I plan to use two arrays, one for the pixels and
> one for the count's. Then it would be possible to use other image types as
> well.

Using templates and two arrays would allow you to fix the type of the 
run-length array as bytes (or short/int etc) while allowing arbitrary 
data types, so that's probably a good idea.

   count = *pcount++;
   if (count) {
     <PixelType> p = *pixels++;
     for (int i = 0; i < count; i++) {
       *output++ = p;
     }
   }
   else {
     count = *pcount++;
     for (int i = 0; i < count; i++) {
       *output++ = *pixels++;
     }
   }

> I'd also like to provide iterators, so that I can modify RLE encoded images
> directly, without completely decoding. Should be very efficient for
> situations where no random access is needed, and even for random access, it
> should be quite fast for the typical mask image with huge uniform areas. I
> suspect the memory accesses on big images are a real performance killer, so
> its probably even faster than the usual bitmap.

It will be faster for read access, and _much_ faster for reading off 
disks, but random, in-place, updates are going to be quite slow:

There is almost no chance of doing any modifications to an RL-encoded 
line without changing the total length, which means that you'll need to 
reallocate memory for it.

The easiest approach is to use copy-on-write, where you allow random 
access to the compressed array, but expand it when starting any updates, 
and re-compress when you're done, or when flushing back to disk.

Terje

-- 
- <Terje.Mathisen at hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"