Compression - Combining features of JPEG-LS (Pre-Proc Filter) with LZ-77 ?????

Author

Combining features of JPEG-LS (Pre-Proc Filter) with LZ-77 ?????

2008-02-22, 9:57 pm

Hi,
Sorry, If this topic has already been discussed on this group. I want
to
implement an efficient lossless compression engine for my research on
an FPGA platform.
I assumed from my studies that dictionary based compression technique
like deflate
perform well with data containing regular patterns and less variance.
While
lossless compression techniques like JPEG-LS rely heavily on its
filters for
efficient distibution identification and may perform less efficiently
on data
with less variance.

If my above assumption on efficiency of algorithms based upon the
distibution of
input data is true,

1-- Is it possible to choose the right algorithm for data/ Image
compression
based on statistical values (entropy, variance) as to whether
compression technique
based on PNG or JPEG-LS suits the given data set ? Has anyone tried
this ?

2-- Is it possible to merge the steps of Pre-Proc (JPEG-LS) filters
with dictionay
based compression technique (LZ77) followed by Golomb-Rice or
Arithmetic encoding to
formulate an efficient compression engine, where Pre-Proc filter would
reduce
the variance of input data and dictionay based technique would work
efficiently on
it and appropriate encoding to further reduce the size of stream ?

Any comments ?

Regards
/MH

Stefano Brocchi

2008-02-23, 7:56 am

Hello,

> 1-- Is it possible to choose the right algorithm for data/ Image
> compression
> based on statistical values (entropy, variance) as to whether
> compression technique
> based on PNG or JPEG-LS suits the given data set ? Has anyone tried
> this ?

This depends much on the candidate algorithms you want to consider,
but generally I would consider other factors. First of all, PNG is
rarely a good algorithm for lossless image compression, you could
discard it and consider lossless Jpeg2000 instead. In this case an
analysis on image characteristics could be compress computer generated
images of high-edged images with JPEG-LS (JPeg2000 does badly in these
cases) and other images with JPEG-LS.

In the general case I think other factors in an image have more weight
in making an algorithm better than another on a given image. Some
could be image size, edge number, image quality and color variety.

> 2-- Is it possible to merge the steps of Pre-Proc (JPEG-LS) filters
> with dictionay
> based compression technique (LZ77) followed by Golomb-Rice or
> Arithmetic encoding to
> formulate an efficient compression engine, where Pre-Proc filter would
> reduce
> the variance of input data and dictionay based technique would work
> efficiently on
> it and appropriate encoding to further reduce the size of stream ?
>

Yes it is. In fact, PNG makes a filtering phase before compressing
with a ZIP-like algorithm (maybe exactly LZ77, not sure though) and
achieves much better results than just ZIPping images. I also created
an image compression algorithm that preprocesses the image with a
filtering phase and eventually compresses the resulting data. If you
are interested, my website describes the pre-processing stage quite
well at

http://www.researchandtechnology.ne...m_filtering.php
Homepage: http://www.researchandtechnology.net/pcif/index.php

(BTW, if you want to discuss my algorithm there is already a thread on
comp.compression about it)

Best and kind regards
Stefano

cr88192

2008-02-25, 9:56 pm

"Stefano Brocchi" <stefano.brocchi@researchandtechnology.net> wrote in
message
news:fcc83869-bed5-4a46-bea7-99081dc9bd07@m23g2000hsc.googlegroups.com...
> Hello,
>
>
> This depends much on the candidate algorithms you want to consider,
> but generally I would consider other factors. First of all, PNG is
> rarely a good algorithm for lossless image compression, you could
> discard it and consider lossless Jpeg2000 instead. In this case an
> analysis on image characteristics could be compress computer generated
> images of high-edged images with JPEG-LS (JPeg2000 does badly in these
> cases) and other images with JPEG-LS.
>

<snip>

>
> Yes it is. In fact, PNG makes a filtering phase before compressing
> with a ZIP-like algorithm (maybe exactly LZ77, not sure though) and
> achieves much better results than just ZIPping images. I also created
> an image compression algorithm that preprocesses the image with a
> filtering phase and eventually compresses the resulting data. If you
> are interested, my website describes the pre-processing stage quite
> well at
>

PNG uses Deflate.

all in all, PNG is pretty good IMO (and, is also one of the most widely
supported lossless image codecs around, which for many uses IS the major
deciding factor).

however, PNG does have a few weaknesses IMO:
it does not do any decorellation;
this hurts some, because most images, even artificial ones, have a good deal
of relation between the components.

the image is also compressed with interleaved components.
this makes sense for incremental download and memory usage during
decompression, but does not help much with compression ratio (a decorrelated
planar represention likely compressing better with Deflate).

the particular linear filter most often used (Paeth) is also not always
ideal (for "natural" images, or even CG rendered images, a plain linear
B+C-A filter is often better).

one could also choose filters per-block, rather than per-scanline (since
image properties tend more often to be block-localized than scanline
localized).

....

so, PNG is not really the theoretically best option, but it is still often a
pretty good option.

now, what do I think a worthwhile PNG-alternative would look like:
decorelate and planarize image, sort of like this: Y=G plane, U=R-G plane,
V=B-G plane, A plane;
planes are filtered using per-block filters (stored in another plane, say,
the P plane);
planes are then compressed with something like deflate (simpler being to
lump them all together, say, PYUVA or YUVAP, better may be to compress each
separately).

of course, unlike PNG this will not allow per-scanline decompression (thus
we would need the whole image, and enough memory, to decode it at all).

per-blockline interlacing would also be possible, but would somewhat
increase codec complexity (or, alternatively, we could use block-level
interlacing sort of like JPEG, however, with deflate this would introduce a
similar compression issue to that of per-pixel interlacing, and would
actually make things worse by breaking patterns at block boundaries).

so, as a result, such a format would likely be limited to
whole-image-at-once decoding.

PNG works though...

> http://www.researchandtechnology.ne...m_filtering.php
> Homepage: http://www.researchandtechnology.net/pcif/index.php
>
> (BTW, if you want to discuss my algorithm there is already a thread on
> comp.compression about it)
>
> Best and kind regards
> Stefano

Sponsored Links