| |
 |
|
| Science Forum Index » Compression Forum » 4-level image compression ?... |
|
Page 1 of 1 |
|
| Author |
Message |
| whygee... |
 Posted: Thu Jul 02, 2009 9:36 pm |
|
|
|
Guest
|
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 ?
--
http://ygdes.com / http://yasep.org |
|
|
| Back to top |
|
|
|
| cr88192... |
| Posted: Thu Jul 02, 2009 11:56 pm |
|
|
|
Guest
|
"whygee" <whygee at (no spam) yg.yg> wrote in message
news:4a4d820e$0$297$7a628cd7 at (no spam) news.club-internet.fr...
[quote:6f9e0caff8]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 ?
[/quote:6f9e0caff8]
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<< | (*cs++);
*ct++=encode(0, k);
}
for(i=1;i<ys; i++)
{
k=0; l=0;
for(j=0; j<w; j++)
{
l=(l<< | (*(cs-w));
k=(k<< | (*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.
[quote:6f9e0caff8]--
http://ygdes.com / http://yasep.org[/quote:6f9e0caff8] |
|
|
| Back to top |
|
|
|
| Thomas Richter... |
| Posted: Thu Jul 02, 2009 11:58 pm |
|
|
|
Guest
|
whygee wrote:
[quote:a992d50e7d]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 ?
[/quote:a992d50e7d]
Lossy? Lossless?
JPEG-LS? (Yes, can do 16 grey levels) in lossless.
Lossless JPEG (ditto, can do 4bpp, but less efficient)
JPEG 2000 (can also do 4bpp)
So long,
Thomas |
|
|
| Back to top |
|
|
|
| cr88192... |
| Posted: Fri Jul 03, 2009 12:12 am |
|
|
|
Guest
|
"Thomas Richter" <thor at (no spam) math.tu-berlin.de> wrote in message
news:h2k6a7$jgp$1 at (no spam) infosun2.rus.uni-stuttgart.de...
[quote:8b4950b7b4]whygee wrote:
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 ?
Lossy? Lossless?
JPEG-LS? (Yes, can do 16 grey levels) in lossless.
Lossless JPEG (ditto, can do 4bpp, but less efficient)
JPEG 2000 (can also do 4bpp)
[/quote:8b4950b7b4]
I had thought he meant 2bpp, not 4bpp...
he says 4 gray levels, not 16 gray levels...
I have my doubts as to how well the coding scheme used by JPEG-LS will work
with 2bpp images.
also, in special-use cases, dragging around a full JPEG-LS or JPEG-2000
codec may well be too expensive...
as well, a little bit-twiddling and a LUT can handle much of the process as
well.
[quote:8b4950b7b4]So long,
Thomas
[/quote:8b4950b7b4] |
|
|
| Back to top |
|
|
|
| Thomas Richter... |
| Posted: Fri Jul 03, 2009 4:58 am |
|
|
|
Guest
|
cr88192 wrote:
[quote:1ba416e18e]
I had thought he meant 2bpp, not 4bpp...
he says 4 gray levels, not 16 gray levels...
I have my doubts as to how well the coding scheme used by JPEG-LS will work
with 2bpp images.
[/quote:1ba416e18e]
Of course it will work.
[quote:1ba416e18e]also, in special-use cases, dragging around a full JPEG-LS or JPEG-2000
codec may well be too expensive...
[/quote:1ba416e18e]
JPEG-LS, expensive? I beg your pardon, but this is very light-weighted.
[quote:1ba416e18e]as well, a little bit-twiddling and a LUT can handle much of the process as
well.
[/quote:1ba416e18e]
Not quite.
So long,
Thomas |
|
|
| Back to top |
|
|
|
| cr88192... |
| Posted: Fri Jul 03, 2009 8:59 am |
|
|
|
Guest
|
"Thomas Richter" <thor at (no spam) math.tu-berlin.de> wrote in message
news:h2kntk$rjl$1 at (no spam) infosun2.rus.uni-stuttgart.de...
[quote:2394cf7be9]cr88192 wrote:
I had thought he meant 2bpp, not 4bpp...
he says 4 gray levels, not 16 gray levels...
I have my doubts as to how well the coding scheme used by JPEG-LS will
work with 2bpp images.
Of course it will work.
[/quote:2394cf7be9]
the question though is, how well?...
sadly, I can't answer as presently I don't know the specifics of its coding
scheme, but it is sounding like it is using rice-coding for the residuals.
rice coding would take at least 2 bits per item, meaning it is not a good
scheme (a lumping scheme would be needed, ...).
2-bits per item with 2-bpp input means no compression, or worse, inflation.
FWIW, if the input were 1bpp, I would likely have suggested a scheme based
on xor...
[quote:2394cf7be9]also, in special-use cases, dragging around a full JPEG-LS or JPEG-2000
codec may well be too expensive...
JPEG-LS, expensive? I beg your pardon, but this is very light-weighted.
[/quote:2394cf7be9]
compared to?...
well, I guess the big question is what kind of CPU and how much RAM is
available, how much space is available in the process image, ...
a general-purpose library could easily take 10s of kB to store the code, and
maybe a bit more in order to run (say, 100-200kB?...).
by most definitions a PNG codec is light-weight as well, but there are cases
where PNG may well be too expensive...
[quote:2394cf7be9]as well, a little bit-twiddling and a LUT can handle much of the process
as well.
Not quite.
[/quote:2394cf7be9]
depending on available RAM, FWIW, there may not even be enough for a
table-based huffman decoder...
of course, the LUT would be a good way to prepare the data for a huffman
compressor (or deflate).
this way, we can worry not as much about the actual encoding, as to how to
condition the bits so they best go through huffman. a scheme which reduces
most of the bytes to 0x00 doesn't hurt, and LZ would be better, if
affordable.
another strategy would be to use a specialized PAQ-style codec, which could
be adapted to this particular use case. the problem would be, however, that
it would deliver good compression at the cost of poor speed (or how most
people use the term, performance...).
(a PAQ-style coder could be made to work, and would require approx 512 bytes
for the context...).
I guess the big question is "how much?"
I was making a conservative guess:
maybe it is in the kB range?...
one can probably infer that the space is small, after all, the issue of
compressing 2-bpp images came up in the first place, and from the way the
message is written, it is very well possible it is in this range (or, maybe
the low MB range, but with a lot of RAM needed for other stuff...).
similarly, since it is mentioned that the final version would be in
assembler, it can be inferred that either CPU time or memory is rather
tight, ...
sadly, to know how to best compress images in this case would likely require
experimentation...
[quote:2394cf7be9]So long,
Thomas[/quote:2394cf7be9] |
|
|
| Back to top |
|
|
|
| Thomas Richter... |
| Posted: Fri Jul 03, 2009 10:28 am |
|
|
|
Guest
|
cr88192 wrote:
[quote:a6d71fa385]"Thomas Richter" <thor at (no spam) math.tu-berlin.de> wrote in message
news:h2kntk$rjl$1 at (no spam) infosun2.rus.uni-stuttgart.de...
cr88192 wrote:
I had thought he meant 2bpp, not 4bpp...
he says 4 gray levels, not 16 gray levels...
I have my doubts as to how well the coding scheme used by JPEG-LS will
work with 2bpp images.
Of course it will work.
the question though is, how well?...
[/quote:a6d71fa385]
The question is, why not trying and *then* developing something by
yourself if insufficient - in that order.
[quote:a6d71fa385]sadly, I can't answer as presently I don't know the specifics of its coding
scheme, but it is sounding like it is using rice-coding for the residuals.
[/quote:a6d71fa385]
Almost, but not quite. It also includes a runlength code, and since the
images are 2bpp, this would also be used quite a lot.
[quote:a6d71fa385]rice coding would take at least 2 bits per item, meaning it is not a good
scheme (a lumping scheme would be needed, ...).
[/quote:a6d71fa385]
If the prediction is fair enough, then this would be acceptable. RLE is
not a very sophisticated "lumping scheme", but it could be understood as
one.
[quote:a6d71fa385]2-bits per item with 2-bpp input means no compression, or worse, inflation.
[/quote:a6d71fa385]
Depends on the nature of the data.
[quote:a6d71fa385]also, in special-use cases, dragging around a full JPEG-LS or JPEG-2000
codec may well be too expensive...
JPEG-LS, expensive? I beg your pardon, but this is very light-weighted.
compared to?...
[/quote:a6d71fa385]
Did you check the source? You cannot really do much simpler.
[quote:a6d71fa385]well, I guess the big question is what kind of CPU and how much RAM is
available, how much space is available in the process image, ...
[/quote:a6d71fa385]
JPEG-LS requires to buffer one line of the image. That's it. The RLE
coding is one function, the regular coding another, one control function
- that's all. It is a very light-weight scheme.
[quote:a6d71fa385]a general-purpose library could easily take 10s of kB to store the code, and
maybe a bit more in order to run (say, 100-200kB?...).
[/quote:a6d71fa385]
Again, *DID* you check the code? JPEG-LS is in the order of 1-4K of
code, and buffer of the size O(width of image).
[quote:a6d71fa385]by most definitions a PNG codec is light-weight as well, but there are cases
where PNG may well be too expensive...
[/quote:a6d71fa385]
PNG is probably heavier than JPEG-LS, and the coding part for the
residuals is just the wrong answer to the problem.
[quote:a6d71fa385]depending on available RAM, FWIW, there may not even be enough for a
table-based huffman decoder...
[/quote:a6d71fa385]
FYI, JPEG-LS was good enough for the Mars Rover.
[quote:a6d71fa385]sadly, to know how to best compress images in this case would likely require
experimentation...
[/quote:a6d71fa385]
The first experiment should be: Is there something on the market that
does this already pretty well. And I suspect, "probably yes", so try
that first, and come back if it doesn't.
Greetings,
Thomas |
|
|
| Back to top |
|
|
|
| Mark Adler... |
| Posted: Fri Jul 03, 2009 11:17 am |
|
|
|
Guest
|
On 2009-07-02 20:36:33 -0700, whygee <whygee at (no spam) yg.yg> said:
[quote:c12208ca7b]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)
[/quote:c12208ca7b]
A quick and easy solution would be to split the image into two 2-level
images (high bit and low bit) and use 2-level fax compression. The
high bit will compress better than the low bit, but both will compress.
You should also try coding the four levels to minimize transitions
(assuming that the images are "smooth" in some sense) and see if
compression is improved. That would be the transformation: 00 -> 00,
01 -> 01, 10 -> 11, 11 -> 10. Then as you smoothly go up levels, the
low bit changes less often.
Mark |
|
|
| Back to top |
|
|
|
| whygee... |
| Posted: Fri Jul 03, 2009 4:29 pm |
|
|
|
Guest
|
Thomas Richter wrote:
[quote:a4417cd006]whygee wrote:
Can someone point me to a more suitable method ?
Lossy? Lossless?
My apologies, I thought from the context that it was obvious[/quote:a4417cd006]
that it was lossless. Think of Nintendo-GameBoy-like pictures
(just a bit larger).
[quote:a4417cd006]JPEG-LS? (Yes, can do 16 grey levels) in lossless.
Lossless JPEG (ditto, can do 4bpp, but less efficient)
JPEG 2000 (can also do 4bpp)
Here it is 2bpp (hence 4 levels)[/quote:a4417cd006]
I could maybe manage the complexity of a huffman code,
but I'm probably too unexperienced with deflate, as cr88192 suggested.
But I lack time for this.
[quote:a4417cd006]So long,
Thomas
yg[/quote:a4417cd006]
--
http://ygdes.com / http://yasep.org |
|
|
| Back to top |
|
|
|
| whygee... |
| Posted: Fri Jul 03, 2009 4:43 pm |
|
|
|
Guest
|
Thomas Richter wrote:
[quote:62ace01529]cr88192 wrote:
sadly, to know how to best compress images in this case would likely
require experimentation...
The first experiment should be: Is there something on the market that
does this already pretty well. And I suspect, "probably yes", so try
that first, and come back if it doesn't.
[/quote:62ace01529]
Now that I think about this...
since compression is likely to be used in other parts of the system
(and if it is available, it /will/ be used) then the best bet would
be to port deflate (or a similar, very low footprint compression/decompression algo).
Then the 2bpp encoder will just plug into this functionality.
Ouch, it's going to need some serious development 
and now that I think about it, the fixed huffman scheme
would be inefficient in some cases.
I've read in the past about a very small LZW for microcontrollers.
how does it compare to a stripped-down zlib ?
thanks for the insights everybody,
[quote:62ace01529]Greetings,
Thomas
yg[/quote:62ace01529]
--
http://ygdes.com / http://yasep.org |
|
|
| Back to top |
|
|
|
| whygee... |
| Posted: Fri Jul 03, 2009 4:52 pm |
|
|
|
Guest
|
Mark Adler wrote:
[quote:3e198fcbdc]On 2009-07-02 20:36:33 -0700, whygee <whygee at (no spam) yg.yg> said:
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)
A quick and easy solution would be to split the image into two 2-level
images (high bit and low bit) and use 2-level fax compression. The high
bit will compress better than the low bit, but both will compress.
[/quote:3e198fcbdc]
compression could be better if the contexts were preserved accross the planes...
[quote:3e198fcbdc]You should also try coding the four levels to minimize transitions
(assuming that the images are "smooth" in some sense) and see if
compression is improved. That would be the transformation: 00 -> 00, 01
-> 01, 10 -> 11, 11 -> 10. Then as you smoothly go up levels, the low
bit changes less often.
[/quote:3e198fcbdc]
oh yes, I've played with a similar recoding in the past,
with a binary-to-Gray code, it can sometimes give good results
with little efforts. However I'm not sure that it would change
much the compression ratio here.
Maybe, if I implement a deflate routine, I could make one version
that is bound to 2 or 3bits per value, which could optimise a bit
the speed and overall code+data size. The history/context tables
could be smaller and easier to search...
oh well, that's a lot of work in perspective :-/
regards,
[quote:3e198fcbdc]Mark
yg[/quote:3e198fcbdc]
--
http://ygdes.com / http://yasep.org |
|
|
| Back to top |
|
|
|
| cr88192... |
| Posted: Fri Jul 03, 2009 5:46 pm |
|
|
|
Guest
|
"Mark Adler" <madler at (no spam) alumni.caltech.edu> wrote in message
news:2009070310170116807-madler at (no spam) alumnicaltechedu...
[quote:af73607f61]On 2009-07-02 20:36:33 -0700, whygee <whygee at (no spam) yg.yg> said:
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)
A quick and easy solution would be to split the image into two 2-level
images (high bit and low bit) and use 2-level fax compression. The high
bit will compress better than the low bit, but both will compress.
You should also try coding the four levels to minimize transitions
(assuming that the images are "smooth" in some sense) and see if
compression is improved. That would be the transformation: 00 -> 00,
01 -> 01, 10 -> 11, 11 -> 10. Then as you smoothly go up levels, the low
bit changes less often.
[/quote:af73607f61]
seems like a worthwhile idea IMO...
I guess the major cost is the bit-repacking issue.
another mystery is if the 'j=i^(i>>1);' trick would help much with anything
(AKA: for predicting adjacent pixels).
hmm:
j=i^(i>>2);
could be adapted and applied on a whole scanline, essentially working as a
sort of simplistic predictor.
result is then Huffman+RLE coded.
the inversion could be done manually, or with the help of a 10-bit LUT
(would use 2 bits from the prior decoded group), or shift+xor and an 8-bit
LUT.
00 00,00,00,00 -> 00,00,00,00
01 01,01,01,01 -> 00,00,00,00
10 10,10,10,10 -> 00,00,00,00
11 11,11,11,11 -> 00,00,00,00
10 11,11,11,11 -> 01,00,00,00
....
[quote:af73607f61]Mark
[/quote:af73607f61] |
|
|
| Back to top |
|
|
|
| cr88192... |
| Posted: Fri Jul 03, 2009 6:36 pm |
|
|
|
Guest
|
"whygee" <whygee at (no spam) yg.yg> wrote in message
news:4a4e8ef3$0$296$7a628cd7 at (no spam) news.club-internet.fr...
[quote:f07f15af7e]Thomas Richter wrote:
cr88192 wrote:
sadly, to know how to best compress images in this case would likely
require experimentation...
The first experiment should be: Is there something on the market that
does this already pretty well. And I suspect, "probably yes", so try that
first, and come back if it doesn't.
Now that I think about this...
since compression is likely to be used in other parts of the system
(and if it is available, it /will/ be used) then the best bet would
be to port deflate (or a similar, very low footprint
compression/decompression algo).
Then the 2bpp encoder will just plug into this functionality.
[/quote:f07f15af7e]
makes sense.
[quote:f07f15af7e]Ouch, it's going to need some serious development
and now that I think about it, the fixed huffman scheme
would be inefficient in some cases.
[/quote:f07f15af7e]
maybe, but huffman+RLE should work acceptably I would think.
[quote:f07f15af7e]I've read in the past about a very small LZW for microcontrollers.
how does it compare to a stripped-down zlib ?
[/quote:f07f15af7e]
I guess if zlib could be made to work...
I have a fairly minimalistic deflater, but the problem in this case is that
it is designed for computers with much more memory (for example, using big
tables for decoding the huffman values, ...), whereas likely a deflater
using an explicit huffman tree would be better (needing much less memory to
decode).
as for LZW, it is good for patterns, but has no real entropy-coding
capability.
I have doubts that it would work well in this case (as in, not be able to
compress much).
[quote:f07f15af7e]thanks for the insights everybody,
Greetings,
Thomas
yg
--
http://ygdes.com / http://yasep.org[/quote:f07f15af7e] |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sun Nov 08, 2009 8:48 am
|
|