Best way to compress 1-Bit Bitmap
Harry Muscle
microcontroller (limited memory) ... so even a 1 bit bitmap needs to be
compressed. The maximum size of the bitmap will be 240*128 (size of the
LCD). Usually smaller though. The bitmaps will range from a font to a
black and white picture (ie: fair bit of detail ... halftoning, etc.). The
only type of compression I can think of is Run Length Encoding ... but it
doesn't seem to be too efficient on 1 bit bitmaps.
I would prefer a simple type of compression that I could code myself (in C).
However, I'm open to all suggestions ... size is of the most importance
though.
Thanks for any and all help,
Harry
Jesper Nordenberg
An adaptive binary coder is good, for example the Z-Coder.
/Jesper Nordenberg
Harry Muscle
news:3C90F901...@nnl.se.remove.this...
Any idea where I can get an explanation of the algorithm ... or source code
... etc. Search on google, doesn't turn up anything too interesting.
Thanks,
Harry
Willem
)> > What's the best way to compress a 1 bit bitmap? It's being used in a
)> > microcontroller (limited memory) ... so even a 1 bit bitmap needs to be
)> > compressed. The maximum size of the bitmap will be 240*128 (size of the
)> > LCD). Usually smaller though. The bitmaps will range from a font to a
)> > black and white picture (ie: fair bit of detail ... halftoning, etc.).
) The
)> > only type of compression I can think of is Run Length Encoding ... but
) it
)> > doesn't seem to be too efficient on 1 bit bitmaps.
)> >
)> > I would prefer a simple type of compression that I could code myself (in
) C).
)> > However, I'm open to all suggestions ... size is of the most importance
)> > though.
)>
)>
)> An adaptive binary coder is good, for example the Z-Coder.
)>
)> /Jesper Nordenberg
)>
)
) Any idea where I can get an explanation of the algorithm ... or source code
) ... etc. Search on google, doesn't turn up anything too interesting.
You could try looking for LBIG, which is the 1-bit lossless variant of
JPEG, IIRC.
SaSW, Willem (at stack dot nl)
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Tom St Denis
"Harry Muscle" <harry.DOT.muscle@AT@usa.DOT.net> wrote in message
news:U26k8.642$RR3.3...@carnaval.risq.qc.ca...
You could easily use a high order range coder [or arithmetic coder]. The
model would be
typedef struct {
unsigned long counts[2];
} model;
model state[2^(n+1)];
A 1st order state would require 2^2 * 8 == 32 bytes of memory.
Say you divide the range into 0..16383 [see Mark Nelsons data compression
book for example], then you can calc the interval for the two symbols on the
fly.
unsigned long zero_end, one_begin;
zero_end = (16384 * state[history].counts[0]) / (state[history].counts[0] +
state[history].counts[1]);
one_begin = zero_end + 1;
[I think that should be right... note the obvious optimization by removing
the *16384 and using <<14].
So if "history" represents the current n-bit history [e.g the previous bits
of input] then the 0 interval is 0..zero_end and the 1 interval is
one_begin..16383. Note that to calculate zero_end you need the double
precision copy of 16384 * state[history].counts[0] [e.g. the full 64-bit
result, or full 32-bits if you use 16-bit counters].
Of course you could optimize this further. Since you are dealing with small
images you could use 16-bit counters [would require 2^2 * 4 == 16 bytes].
For a 16-bit version the model and current arithmetic coder state all come
out to less than 32 bytes of memory.
If your images have runs of the same color you could probably just use a
0-order model which would simplify the code [no array indexing] and still
get decent compression. That and a 0-order model with 16-bit counters would
only require 4 bytes of memory [or about 16 bytes for the entire coder
state].
I can email code [based on Mark Nelsons book] for an arithmetic coder if you
want. Its not particularly suited for this purpose but it should fit the
bill.
Tom
Marco Schmidt
>What's the best way to compress a 1 bit bitmap?
TIC is for images with text in them:
http://freshmeat.net/redir/tic/10519/url_mirror/ Maybe it also works
for you. The halftone images could be a problem...
DjVu can also deal with b&w images: http://www.djvuzone.org/
A good general purpose image file format is PNG.
There is no best way. As I mentioned above, the good text image
compressor will probably fail on halftoned images. The more you
specialize on a class of data, the better the encoder will be for that
type of data. But it will not work well for other data classes. If you
can pick different algorithms for text and halftoned images, you'll
probably have the best results. If you can, compress each image with
all encoders and pick the smallest file. That won't help much if your
images contain different types of images.
Regards,
Marco
Malcolm Taylor
>What's the best way to compress a 1 bit bitmap? It's being used in a
>microcontroller (limited memory) ... so even a 1 bit bitmap needs to be
>compressed. The maximum size of the bitmap will be 240*128 (size of the
>LCD). Usually smaller though. The bitmaps will range from a font to a
>black and white picture (ie: fair bit of detail ... halftoning, etc.). The
>only type of compression I can think of is Run Length Encoding ... but it
>doesn't seem to be too efficient on 1 bit bitmaps.
Do a internet search for JBIG. Some of the ideas in that standard
would be particularly applicable to your problem, as it is a fax
compression standard.
Malcolm
Jesper Nordenberg
Here's a link to some Z-Coder source code:
It's used in the DjVuLibre project, http://djvu.sourceforge.net/. I
think the Z-Coder is patented, but free to use for open source projects.
/Jesper Nordenberg