Home > Archive > Compression > November 2007 > Huffman codes and embedded systems
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Huffman codes and embedded systems
|
|
| LiloLilo 2007-11-18, 6:56 pm |
| Dear all,
are Huffman codes too difficult to use in embedded systems? For example,
digital cameras always store photos in jpg, and jpg uses Huffman. But in
this case, is the tree really builded or it is used a standard code?
Thank you all!
| |
| Thomas Richter 2007-11-18, 6:56 pm |
| LiloLilo wrote:
> Dear all,
>
> are Huffman codes too difficult to use in embedded systems?
Not at all.
> For example,
> digital cameras always store photos in jpg, and jpg uses Huffman. But in
> this case, is the tree really builded or it is used a standard code?
The huffman tables for JPEG are static.
So long,
Thomas
| |
| Pete Fraser 2007-11-18, 6:56 pm |
|
"LiloLilo" <danilobrambilla@tiscali.it> wrote in message
news:47407165$0$16026$5fc30a8@news.tiscali.it...
> Dear all,
>
> are Huffman codes too difficult to use in embedded systems?
No. They's quite easy.
> For example, digital cameras always store photos in jpg, and jpg uses
> Huffman. But in this case, is the tree really builded or it is used a
> standard code?
It uses a stndard code.
The JPEG standard allows for a variety of Huffman tables, but I've
never seen anything other than the standard's suggestion used.
However, there is no default table, so the Huffman table is
included in every codestream (some motion JPEG implementations
-- OpenDML for example -- omit the tables).
| |
| Steven Pigeon 2007-11-18, 6:56 pm |
| LiloLilo wrote:
> Dear all,
>
> are Huffman codes too difficult to use in embedded systems? For example,
> digital cameras always store photos in jpg, and jpg uses Huffman. But in
> this case, is the tree really builded or it is used a standard code?
>
> Thank you all!
>
>
Digital cameras often use rather powerful, specialized
chips to do image processing and compression. Canon has
its Dig!c (digic) series, while Nikon use its own (although
I do not know its name).
The Dig!c III is powerful enough to enable face detection
software, so I don't think huffman would be much of a problem.
Moreover, building a tailored Huffman code isn't very
costly: it's merely a two pass algorithm, and in the
case of JPEG, you can use a precomputed one, one that
works well with the quantization settings you'll be
using. Also, even today's "embedded" CPUs or MPUs are
in the multi-MHz range, so it should'nt be too hard.
Google around to look for low memory consumption, fast,
in place, huffman codecs, you'll find plenty.
best,
S.
| |
| LiloLilo 2007-11-19, 6:58 pm |
| Thank you all for help.
do you think that build an Huffman code for each line of each channel of
an image would be too heavy using a 16 word code for an embedded device?
D.
"Steven Pigeon" <steven.pigeon@videotron.ca> wrote in message
news:hH00j.4649$4Q5.3544@wagner.videotron.net...
> LiloLilo wrote:
>
> Digital cameras often use rather powerful, specialized
> chips to do image processing and compression. Canon has
> its Dig!c (digic) series, while Nikon use its own (although
> I do not know its name).
>
> The Dig!c III is powerful enough to enable face detection
> software, so I don't think huffman would be much of a problem.
>
> Moreover, building a tailored Huffman code isn't very
> costly: it's merely a two pass algorithm, and in the
> case of JPEG, you can use a precomputed one, one that
> works well with the quantization settings you'll be
> using. Also, even today's "embedded" CPUs or MPUs are
> in the multi-MHz range, so it should'nt be too hard.
>
> Google around to look for low memory consumption, fast,
> in place, huffman codecs, you'll find plenty.
>
>
> best,
>
> S.
>
>
| |
| Steven Pigeon 2007-11-19, 6:58 pm |
| LiloLilo wrote:
> Thank you all for help.
>
> do you think that build an Huffman code for each line of each channel of
> an image would be too heavy using a 16 word code for an embedded device?
>
> D.
Of course, it can be done, but it depends on your speed
requirements and the CPU/MPU you will be using. If you expect
to do 3 channels at 1280x720 at 30 frames/s on a 2MHz CPU,
well, good luck ;)
What are your speed requirements? What MPU/CPU would be used?
Do you have the luxury of extra hardware (like some helper
chips)?
Best,
S.
>
> "Steven Pigeon" <steven.pigeon@videotron.ca> wrote in message
> news:hH00j.4649$4Q5.3544@wagner.videotron.net...
>
>
| |
| LiloLilo 2007-11-20, 10:00 pm |
| Well, the algorithm won't encode a video stream, but a single image/photo.
Because of the algorithm should suit if possible embedded devices (es.
digital cameras, so I have only the hardware provided in this kind of
devices or similar) I was interested to understand if building an Huffman
code for each line of each channel of an image would be too heavy or not.
This is only an ipotetic solution, I am just studying the problem...may be a
Golomb code solve it.
D.
"Steven Pigeon" <steven.pigeon@videotron.ca> wrote in message
news:2wo0j.10131$4Q5.19162@wagner.videotron.net...[color=darkred]
> LiloLilo wrote:
>
> Of course, it can be done, but it depends on your speed
> requirements and the CPU/MPU you will be using. If you expect
> to do 3 channels at 1280x720 at 30 frames/s on a 2MHz CPU,
> well, good luck ;)
>
> What are your speed requirements? What MPU/CPU would be used?
> Do you have the luxury of extra hardware (like some helper
> chips)?
>
>
>
> Best,
>
> S.
>
| |
| Steven Pigeon 2007-11-20, 10:00 pm |
| LiloLilo wrote:
> Well, the algorithm won't encode a video stream, but a single image/photo.
> Because of the algorithm should suit if possible embedded devices (es.
> digital cameras, so I have only the hardware provided in this kind of
> devices or similar) I was interested to understand if building an Huffman
> code for each line of each channel of an image would be too heavy or not.
> This is only an ipotetic solution, I am just studying the problem...may be a
> Golomb code solve it.
Run length encoding is generally rather bad for pictures. If you
have very little repetition of consecutive pixels, even less of
longer runs, you should forget about it. If you want to compress
an image, say in a digital camera, you would be much better off
using lossy, transform-based encoding. You will get much better
compression ratio because you will exploit 2D properties of the
picture. If you are careful about setting the parameters, the
data destroyed will be of the same magnitude than the noise from
your sensor, so no perceivable loss occurs.
On this, you may read:
http://en.wikipedia.org/wiki/Transform_coding
http://en.wikipedia.org/wiki/Image_compression
(or rather, the pointers contained in those two)
best,
S.
| |
| Thomas Richter 2007-11-21, 3:56 am |
| LiloLilo schrieb:
> Thank you all for help.
>
> do you think that build an Huffman code for each line of each channel of
> an image would be too heavy using a 16 word code for an embedded device?
It's probably the wrong approach. What you usually need is to make use of the correlations in the image,
and for that you typically first run a decorrelation transformation (DWT,DCT, overlapped block transfer...)
and later on, you use a context-modelling entropy coder backend. Yes, one can do that with Huffman,
but it is much easier to introduce contexts into arithmetic coders.
You should also take a serious look at the JPEG-LS (aka "loco") compressor. It's surprisingly simple,
and surprisingly good.
So long,
Thomas
|
|
|
|
|