| Author |
Message |
Jerry Coffin
Guest
|
 Posted:
Fri Dec 23, 2005 1:16 am Post subject:
Re: real-time compression algorithms on fpga |
|
|
news@rtrussell.co.uk wrote:
[ ... ]
| Quote: | Given that a lossless system is inevitably 'variable bit rate'
(VBR) the concept of "real time capability" is somewhat vague;
the latency is bound to be variable.
|
The output bit rate will vary, but can be bounded -- for an obvious
example, consider using LZW compression with 8-bit inputs and 12-bit
codes as the output. In the worst case, each 8-bit input produces a
12-bit output, and you have to clear and rebuild the dictionary every
4096 characters.
Real-time constraints are a more or less separate issue though -- here,
the output data stream isn't (usually) nearly as difficult to deal with
as things like dictionary searching in the compression process. Like
the compression rate, this will vary, but (again) it's usually pretty
easy to set an upper bound. Using the same example, in LZW you build up
a string out of characters, with one dictionary entry for each "next"
character following a current character. There can be no more than 256
next characters (worst case), so the worst case requirement is to
search all 256 entries for follow-on characters in N microseconds (or
nanoseconds, or whatever). You just about need more details to
guarantee this though -- a trie-based dictionary has different
characteristics than a hash-based dictionary (for an obvious example).
In nearly every case it's still pretty easy to place an upper bound on
the complexity and time involved though.
OTOH, you can run into a little bit of a problem with some of the
basics -- if you happen (for example) to be storing your dictionary in
SRAM, the time per access is pretty easy to estimate. If you're storing
it in something like SDRAM, the worst case can be a bit harder to
figure out.
--
Later,
Jerry. |
|
| Back to top |
|
 |
Jerry Coffin
Guest
|
| Posted:
Fri Dec 23, 2005 1:16 am Post subject:
Re: real-time compression algorithms on fpga |
|
|
Melanie Nasic wrote:
| Quote: | Hello community,
I am thinking about implementing a real-time compression scheme on an FPGA
working at about 500 Mhz. Facing the fact that there is no "universal
compression" algorithm that can compress data regardless of its structure
and statistics I assume compressing grayscale image data. The image data is
delivered line-wise, meaning that one horizontal line is processed, than
the next one, a.s.o.
Because of the high data rate I cannot spend much time on DFT or DCT and on
data modelling. What I am looking for is a way to compress the pixel data in
spatial not spectral domain because of latency aspects, processing
complexity, etc. Because of the sequential data transmission line by line a
block matching is also not possible in my opinion. The compression ratio is
not so important, factor 2:1 would be sufficient. What really matters is the
real time capability. The algorithm should be pipelineable and fast. The
memory requirements should not exceed 1 kb.
What "standard" compression schemes would you recommend?
|
JPEG supports lossless encoding that can fit (at least roughly) within
the constraints you've imposed. It uses linear prediction of the
current pixel based on one or more previous pixels. The difference
between the prediction and the actual value is what's then encoded. The
difference is encoded in two parts: the number of bits needed for the
difference and the difference itself. The number of bits is Huffman
encoded, but the remainder is not.
This has a number of advantages. First and foremost, it can be done
based on only the curent scan line or (depending on the predictor you
choose) only one scan line plus one pixel. In the latter case, you need
to (minutely) modify the model you've outlined though -- instead of
reading, compressing, and discarding an entire scan line, then starting
the next, you always retain one scan line worth of data. As you process
pixel X of scan line Y, you're storing pixels 0 through X+1 of the
current scan line plus pixels X-1 through N (=line width) of the
previous scan line.
Another nice point is that the math involved is always simple -- the
most complex case is one addition, one subtraction and a one-bit right
shift.
| Quote: | Are there
potentialities for a non-standard "own solution"?
|
Yes, almost certainly. Lossless JPEG is open to considerable
improvement. Just for an obvious example, it's pretty easy to predict
the current pixel based on five neighboring pixels instead of three. At
least in theory, this should improve prediction accuracy by close to
40% -- thus reducing the number of bits needed to encode the difference
between the predicted and actual values. At a guess, you won't really
see 40% improvement, but you'll still see a little improvement.
In the JPEG 2000 standard, they added JPEG LS, which is certainly an
improvement, but if memory serves, it requires storing roughly two full
scan lines instead of roughly one scan line. OTOH, it would be pretty
easy to steal some of the ideas in JPEG LS without using the parts that
require more storage -- some things like its handling of runs are
mostly a matter of encoding that shouldn't really require much extra
storage.
The final question, however, is whether any of these is likely to give
you 2:1 compression. That'll depend in your input data -- for typical
photographs, I doubt that'll happen most of the time. For thngs like
line art, faxes, etc., you can probably do quite a bit better than 2:1
on a fairly regular basis. If you're willing to settle for nearl
lossless compression, you can improve ratios a bit further.
--
Later,
Jerry. |
|
| Back to top |
|
|
Melanie Nasic
Guest
|
| Posted:
Fri Dec 23, 2005 3:19 pm Post subject:
Re: real-time compression algorithms on fpga |
|
|
Hi Jerry,
thanks for your response(s). Sounds quite promising. Do you know something
about hardware implementation of the compression schemes you propose? Are
there already VHDL examples available or at least C reference models?
Regards, Melanie
"Jerry Coffin" <jerry.coffin@gmail.com> schrieb im Newsbeitrag
news:1135292121.200476.236850@g43g2000cwa.googlegroups.com...
| Quote: | Melanie Nasic wrote:
Hello community,
I am thinking about implementing a real-time compression scheme on an
FPGA
working at about 500 Mhz. Facing the fact that there is no "universal
compression" algorithm that can compress data regardless of its structure
and statistics I assume compressing grayscale image data. The image data
is
delivered line-wise, meaning that one horizontal line is processed, than
the next one, a.s.o.
Because of the high data rate I cannot spend much time on DFT or DCT and
on
data modelling. What I am looking for is a way to compress the pixel data
in
spatial not spectral domain because of latency aspects, processing
complexity, etc. Because of the sequential data transmission line by line
a
block matching is also not possible in my opinion. The compression ratio
is
not so important, factor 2:1 would be sufficient. What really matters is
the
real time capability. The algorithm should be pipelineable and fast. The
memory requirements should not exceed 1 kb.
What "standard" compression schemes would you recommend?
JPEG supports lossless encoding that can fit (at least roughly) within
the constraints you've imposed. It uses linear prediction of the
current pixel based on one or more previous pixels. The difference
between the prediction and the actual value is what's then encoded. The
difference is encoded in two parts: the number of bits needed for the
difference and the difference itself. The number of bits is Huffman
encoded, but the remainder is not.
This has a number of advantages. First and foremost, it can be done
based on only the curent scan line or (depending on the predictor you
choose) only one scan line plus one pixel. In the latter case, you need
to (minutely) modify the model you've outlined though -- instead of
reading, compressing, and discarding an entire scan line, then starting
the next, you always retain one scan line worth of data. As you process
pixel X of scan line Y, you're storing pixels 0 through X+1 of the
current scan line plus pixels X-1 through N (=line width) of the
previous scan line.
Another nice point is that the math involved is always simple -- the
most complex case is one addition, one subtraction and a one-bit right
shift.
Are there
potentialities for a non-standard "own solution"?
Yes, almost certainly. Lossless JPEG is open to considerable
improvement. Just for an obvious example, it's pretty easy to predict
the current pixel based on five neighboring pixels instead of three. At
least in theory, this should improve prediction accuracy by close to
40% -- thus reducing the number of bits needed to encode the difference
between the predicted and actual values. At a guess, you won't really
see 40% improvement, but you'll still see a little improvement.
In the JPEG 2000 standard, they added JPEG LS, which is certainly an
improvement, but if memory serves, it requires storing roughly two full
scan lines instead of roughly one scan line. OTOH, it would be pretty
easy to steal some of the ideas in JPEG LS without using the parts that
require more storage -- some things like its handling of runs are
mostly a matter of encoding that shouldn't really require much extra
storage.
The final question, however, is whether any of these is likely to give
you 2:1 compression. That'll depend in your input data -- for typical
photographs, I doubt that'll happen most of the time. For thngs like
line art, faxes, etc., you can probably do quite a bit better than 2:1
on a fairly regular basis. If you're willing to settle for nearl
lossless compression, you can improve ratios a bit further.
--
Later,
Jerry.
|
|
|
| Back to top |
|
|
Jerry Coffin
Guest
|
| Posted:
Sat Dec 24, 2005 12:59 am Post subject:
Re: real-time compression algorithms on fpga |
|
|
Melanie Nasic wrote:
| Quote: | Hi Jerry,
thanks for your response(s).
|
Sorry 'bout that -- Google claimed the first one hadn't posted, so I
tried again...
| Quote: | Sounds quite promising. Do you know something
about hardware implementation of the compression schemes you propose? Are
there already VHDL examples available or at least C reference models?
|
I don't believe I've seen any VHDL code for it. One place that has C
code is:
ftp://ftp.cs.cornell.edu/pub/multimed/ljpg.tar.Z
I suspect Google would turn up a few more implementations as well. If
you like printed information, you might consider _Image and Video
Compression Standards: Algorithms and Architectures; Second Edition_ by
Bhaskaran and Konstantinides. Published by Kluwer Academic Publishers,
ISBN 0-7923-9952-8. It doesn't go into tremendous detail, but it's one
of the few (that I know of) that discusses lossless JPEG at all.
--
Later,
Jerry. |
|
| Back to top |
|
|
Michael Schöberl
Guest
|
| Posted:
Thu Dec 29, 2005 7:41 am Post subject:
Re: real-time compression algorithms on fpga |
|
|
| Quote: | I am thinking about implementing a real-time compression scheme on an FPGA
working at about 500 Mhz.
|
I'm currently working on something similar ...
simple predictive schemes (like the 4th predictor from jpeg or MED (from
jpeg-ls)) look promising ... they require storage of one line
entropy coding:
huffman and multilevel arithmetic coding require a lot of ressources
(that easily ends up above 1kbit even for a table of probabilities)
binary arithmetic coding would be able to code less than 1bit/cycle
(which ends up at >5 cyles/pixel which is too slow in my case)
I'm currently investigating different schemes of golomb-rice codes
(static, adaptive or even context-adaptive like in jpeg-ls) ... so far
they look promising ...
jpeg-ls: the concept looks nice and quite powerful for a pipelined
encoder (like for fpgas) - unfortunately the decoder would require a
large feedback-loop (and pipelining is almost impossible) ...
jpeg-ls is only symmetric for software implementations :-(
I'm still curious how you plan to achieve 500MHz even on a Virtex4
(I would say something like 200MHz could be possible)
bye,
Michael |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in