Re: 4-level image compression ?


"whygee" <whygee@xxxxx> wrote in message
news:4a4d820e$0$297$7a628cd7@xxxxxxxxxxxxxxxxxxxxxxxx
Hello,

I'm playing with a small system where the display is 320x240 pixels,
with 4 grey levels. So a picture takes about 19200 bytes.
Now I'm quite sure that these images can be reduced in size
but the algorithms I'm aware of deal with 2-level only (fax) or many-level
images (GIF/PNG etc.). Furthermore, my CPU power and RAM are quite reduced
so even a sub-optimal algorithm could do the trick, as long as it saves
some storage space. The final decoder will be hand-coded in asm
and developed in C.

currently, my idea is to use a paeth predictor followed
by a static huffman encoded entropy coder.
I'm not at ease currently with adaptative huffman
and too shy for range-coding (though with 4 or even 8
grey levels, it could be simplified).

Can someone point me to a more suitable method ?


only to comment that, in this case, Paeth could be implemented with a lookup
table, at which point one could also encode the delta.

just my own untested thoughts here...


similarly, decoding the value would use a similar lookup table.

A B
C x

could pack pixels into a byte (for encode):
00aabbcc

and for decode:
aabbccxx


the above would use 64 bytes for the encode table, and 256 for decode.
bit-packing could reduce the tables to 16 and 64 bytes, but would hurt
performance.


potentially, groups of pixels could be transformed at the same time via
lookup tables, however transforming 4 pixels at a time would require 20 bits
(or a 1MB table). and, in this case, the cost of composing the table is
likely to outweigh the cost of encoding/decoding images at this resolution
(unless, of course, the tables were pre-built and made as a part of the
binary, but it would depend a lot on the specific arch/use-case if this is
reasonable).

of course, if lots of images needed to be decoded quickly, it could be
reasonable.


huffman should work reasonably well on this sort of data (and, for
non-dithered images, RLE may help as well). if it can be afforded, deflate
may be a reasonable option (could help compress many common patterns, such
as text, borders, ...).

encode:
byte etab[64]; //encode table
byte dtab[256]; //decode table
short ar, br; //ar=above-pixels, br=same-pixels
byte cr; //coded result
int i;

ar=pixels_above; br=pixels_inline; cr=0;
for(i=0; i<4; i++)
{
j=(((ar>>(i*2))&15)<<2)|((br>>(i*2+2))&3);
cr|=etab[j]<<(i*2);
}

decode:
ar=pixels_above; br=pixels_inline; cr=coded_input;
for(i=0; i<4; i++)
{
j=(((ar>>(i*2))&15)<<4)|(((br>>(i*2+2))&3)<<2)|((cr>>(i*2))&3);
br|=dtab[j]<<(i*2);
}


note that ar/br assume a byte-oriented space, with the high-byte of ar and
br being the previous byte (AKA: MSB, or Big-Endian, ordering, but it does
not matter what the CPU itself uses).

note that, presumably, the whole process would be done in a loop.

w=(xs+3)/4;

k=0; cs=ibuf; ct=obuf;
for(j=0; j<w; j++)
{
k=(k<<8) | (*cs++);
*ct++=encode(0, k);
}
for(i=1;i<ys; i++)
{
k=0; l=0;
for(j=0; j<w; j++)
{
l=(l<<8) | (*(cs-w));
k=(k<<8) | (*cs++);
*ct++=encode(l, k);
}
}

obuf would then by huffman coded or deflated (could be done inline if needed
though).


or, encode more directly (no LUT):
for(i=0; i<4; i++)
{
a=(ar>>(i*2+2))&3;
b=(ar>>(i*2))&3;
c=(br>>(i*2+2))&3;
d=(br>>(i*2))&3;

j=paeth(a, b, c);
cr|=((d-j)&3)<<(i*2);
}

int paeth (int a, int b, int c)
{
int p, pa, pb, pc;
p=b+c-a;
pa=abs(p-a); pb=abs(p-b); pc=abs(p-c);
if((pc<=pb)&&(pc<=pa))return(c);
if(pb<=pa)return(b);
return(a);
}

which is, FWIW, why I suggested the idea of a LUT.


--
http://ygdes.com / http://yasep.org


.

Relevant Pages

  • Decoding function in vb.net
    ... I am having encode & decode functions in C. ... int i, len,j; ...
    (microsoft.public.dotnet.languages.vb)
  • Decode function in vb.net
    ... I am having encode & decode functions in C. ... int i, len,j; ...
    (microsoft.public.dotnet.general)
  • Re: Transparent Blit with NT4
    ... >> I should copy pixels form src to dest skipping pixels with color ... > bool ChromaBlt(HDC outDC, int inX, int inY, int outWidth, int ... > If you can't use any kind of mask at all then if the image you're ... transparent colour set to &00FFFFFF. ...
    (microsoft.public.win32.programmer.gdi)
  • Re: [Linux-fbdev-devel] [PATCH] fbdev: fix fillrect for 24bpp modes
    ... pixels per machine word is not an integer. ... the native cpu endians. ... int dst_idx, unsigned long pat, int left, ...
    (Linux-Kernel)