Home > Archive > Compression > May 2004 > Re: very basic simple question
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 |
Re: very basic simple question
|
|
| Guido Vollbeding 2004-05-12, 9:28 pm |
| Thomas Richter wrote:
>
> It is a problem of DCT that you need to pick a block size -
> thus, DCT is not "scale invariant".
In any imaging model you need to pick *appropriate* parameter selections.
The DCT 8x8 block size has proven to be an appropriate selection for a
large range of applications. Given that, the 8x8 DCT allows for *optimal*
multi-scale representation of images in typical applications:
The 8-point 1-D DCT transforms 8 spatial pixel values into a sequence of 8
linearly increasing scale representations.
You can hardly do better than that.
> Other transforms like DWT are.
The DWT, due to its dyadic subband decomposition scheme (Mallat),
has inferior multi-scale capabilities compared with the DCT!
You can only extract 1/(2^n) scaled representations from a wavelet
image, while n/8 scaled from a DCT image. See also chapter 4 in
my paper at http://kb-bmts.rz.tu-ilmenau.de/gcg/GCGMAT1.HTM .
The other major mistake with DWT, beside its supposed multi-scale
features, is its supposed spatial localization feature. The
spatial localization of Wavelets is only existent in 1 dimension.
It is an error to believe that the spatial localization capability
of Wavelets extents to more than 1 dimension. In fact, there is
no advantage of Wavelets for representing spatial localization of
edges in 2 dimensions, but only of point singularities, which is
less important. That is the reason that Wavelet coding schemes
failed to outperform the DCT for two dimensional images.
The result is that Wavelets are suboptimal for image coding.
It has been found by recent research of Candes and Donoho that
Wavelets are easily outperformed in more than 1-D signal
representations by Curvelets and Ridgelets, in particular.
They show that Wavelets are unable to efficiently represent
edges in images, and they instead recommend Curvelets and
Ridgelets, particularly. See Candes and Donoho: "Curvelets -
A Surprisingly Effective Nonadaptive Representation for Objects
with Edges":
http://www-stat.stanford.edu/~emman...let-SMStyle.pdf
More about Ridgelets and Curvelets:
http://www.acm.caltech.edu/~emmanuel/publications.html
http://www-stat.Stanford.EDU/~donoho/reports.html
Regards
Guido
| |
| Alexis Gallet 2004-05-12, 9:28 pm |
| Hi Guido,
> The DWT, due to its dyadic subband decomposition scheme (Mallat),
> has inferior multi-scale capabilities compared with the DCT!
> You can only extract 1/(2^n) scaled representations from a wavelet
> image, while n/8 scaled from a DCT image.
Sure. In other words, the DCT has a better spectral resolution than the
Mallat DWT, but a worse spatial resolution than the DWT. It's just a
different tradeoff, the choice depends on what you want to do with your
images.
By the way, don't forget that with wavelet packet decompositions, you can
obtain lots of different spatial resolution / spectral resolution tradeoffs,
including the linear scale representation you like so much ! (just filter
all the subbands at each pass, rather than only the lowest-frequency
subband). So the DWT is more flexible than the DCT. But of course, if you
are only concerned with spectral issues, there is no reason at all to use
the DWT.
> The other major mistake with DWT, beside its supposed multi-scale
> features, is its supposed spatial localization feature. The
> spatial localization of Wavelets is only existent in 1 dimension.
> It is an error to believe that the spatial localization capability
> of Wavelets extents to more than 1 dimension. In fact, there is
> no advantage of Wavelets for representing spatial localization of
> edges in 2 dimensions, but only of point singularities, which is
> less important.
I don't agree with you, the localization is worse in 2d than in 1d, but it
still exists. Take a big N*N white image with some sharp black edge
somewhere.
With a DWT, at each scale the nonzero coeffs will be localized in a square
corresponding to the edge location.
With a M*M DCT, you'll have nonzero coeffs almost everywhere in the M*M
blocks containing a part of the edge : no localization. If M is too big,
you'll have annoying artefacts in the blocks containing the edge. If M is
too small, the compression of the uniform parts of the image will be
suboptimal. And adapting M dynamically in the image would be complicated.
Pfff, I keep my beloved DWT ;-)
> That is the reason that Wavelet coding schemes
> failed to outperform the DCT for two dimensional images.
It may be almost true for natural imagery, but not for computer generated
imagery & bi-level/text... Wavelet coding schemes bring above all
flexibility : they perform well on a much wider class of images than DCT
coding schemes, and work at least as well as DCT on natural imagery. In
addition, there is no Forgent Networks claiming royalties in the DWT world
;-)
Regards,
Alexis
| |
| Dr. T Strutz 2004-05-12, 9:28 pm |
| Guido Vollbeding wrote:
> Thomas Richter wrote:
>
>
>
>
> The DWT, due to its dyadic subband decomposition scheme (Mallat),
> has inferior multi-scale capabilities compared with the DCT!
> You can only extract 1/(2^n) scaled representations from a wavelet
> image, while n/8 scaled from a DCT image. See also chapter 4 in
> my paper at http://kb-bmts.rz.tu-ilmenau.de/gcg/GCGMAT1.HTM .
>
Unfortunately, this site was not accessible today.
Guido, please check your arguments.
The scaling by 1/2 is finer than by 1/8, thus you have a finer
multiscale representation.
By the way, the wavelet transform is performed typically by a filter
bank. If we change the sub-sampling from 2 to an other value (and new
filter design) we get other scaling properties.
> The other major mistake with DWT, beside its supposed multi-scale
> features, is its supposed spatial localization feature. The
> spatial localization of Wavelets is only existent in 1 dimension.
> It is an error to believe that the spatial localization capability
> of Wavelets extents to more than 1 dimension. In fact, there is
> no advantage of Wavelets for representing spatial localization of
> edges in 2 dimensions, but only of point singularities, which is
> less important. That is the reason that Wavelet coding schemes
> failed to outperform the DCT for two dimensional images.
>
This argument is weak as well, in my opinion. The localization of signal
features depends on the length of the basis function. Using 8x8-DCT
(e.g. DCT-based JPEG) we have a length of 8 per cosine function (only 1D
as well!). Using any kind of wavelet transform the maximum resolution
depends on the length of the filter applied.
What do you mean with 2D representation of edges?
In compression application we are only interested in the decorrelation
behaviour of the transform (and sometimes in error distribution in the
decoder stage). It is not necessary to represent/approximate any special
kind of pattern.
Concerning the performance of image codecs you have always to consider
the interplay of transformation result (transform coefficients) and the
style of quantization and coding.
Please tell me, which DCT-based image coder can compete with JPEG2000,
perhaps I am not up-to-date.
> The result is that Wavelets are suboptimal for image coding.
This statement is definitely wrong.
> It has been found by recent research of Candes and Donoho that
> Wavelets are easily outperformed in more than 1-D signal
> representations by Curvelets and Ridgelets, in particular.
> They show that Wavelets are unable to efficiently represent
> edges in images, and they instead recommend Curvelets and
> Ridgelets, particularly. See Candes and Donoho: "Curvelets -
> A Surprisingly Effective Nonadaptive Representation for Objects
> with Edges":
>
> http://www-stat.stanford.edu/~emman...let-SMStyle.pdf
>
> More about Ridgelets and Curvelets:
>
> http://www.acm.caltech.edu/~emmanuel/publications.html
> http://www-stat.Stanford.EDU/~donoho/reports.html
Is there any paper at these web pages related to image compression ???
To my knowledge, ridgelets, curvelets etc. are rather fancy things then
useful for image compression. Maybe there is somebody who can correct
me. There is for instance a critical discussion in:
Mali, Alexander; Palfner, Torsten; Müller, Erika
A Study of Ridgelets - Problems and Discussions.
In: Proceedings of the 3rd IASTED International Conference on Signal and
Image Processing (SIP`2001), Honolulu, Hawaii, USA, pp. 334-337, August,
13-16,2001
Regards
T.Strutz
| |
| Guido Vollbeding 2004-05-12, 9:28 pm |
| NNTP-Posting-Host: p3e9e5d6e.dip.t-dialin.net (62.158.93.110)
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Trace: news.uni-berlin.de 1083310515 12450613 I 62.158.93.110 ([96731])
X-Mailer: Mozilla 4.78 [de] (Windows NT 5.0; U)
X-Accept-Language: de
Xref: number1.nntp.ash.giganews.com comp.compression:58754
Alexis Gallet wrote:
>
>
> Sure. In other words, the DCT has a better spectral resolution than the
> Mallat DWT, but a worse spatial resolution than the DWT. It's just a
> different tradeoff, the choice depends on what you want to do with your
> images.
No, you misunderstand.
What I present is a *new* discovery about the DCT which was *not* known
before! The spectral resolution of the DCT corresponds *directly* to
the *spatial* resolution! So indeed the DCT has better *spatial*
resolution than Mallat DWT!
> By the way, don't forget that with wavelet packet decompositions, you can
> obtain lots of different spatial resolution / spectral resolution tradeoffs,
> including the linear scale representation you like so much ! (just filter
> all the subbands at each pass, rather than only the lowest-frequency
> subband). So the DWT is more flexible than the DCT. But of course, if you
> are only concerned with spectral issues, there is no reason at all to use
> the DWT.
There is no reason to use the DWT because the DCT already provides the
best *spatial* resolution! How could you do better if you already get
8 spatial resolution scales from 8 points?
> In addition, there is no Forgent Networks claiming royalties in the DWT
> world ;-)
You are kidding, huh? There are much more and fresher patents involved
with DWT than DCT. They are only enforced, however, *after* the scheme
gets popular and widespread, that's what you learn from the Forgent
story. So you DWT folks don't really need to worry, it will never
get popular and widespread enough for being interesting for patent
enforcements by companies like Forgent, simply because it's inferior ;-).
Regards
Guido
| |
| Guido Vollbeding 2004-05-12, 9:28 pm |
| "Dr. T Strutz" wrote:
>
> Unfortunately, this site was not accessible today.
You can find the paper also here: http://jpegclub.org/temp/ .
> Guido, please check your arguments.
> The scaling by 1/2 is finer than by 1/8, thus you have a finer
> multiscale representation.
With the DCT I can get directly a 75% (6/8) scaled image version,
for example. How can you do that with DWT?
> By the way, the wavelet transform is performed typically by a filter
> bank. If we change the sub-sampling from 2 to an other value (and new
> filter design) we get other scaling properties.
The popular schemes, particularly JPEG2000, work with fixed dyadic
filter decompositions.
> Please tell me, which DCT-based image coder can compete with JPEG2000,
> perhaps I am not up-to-date.
The standard JPEG DCT-based image coder outperforms JPEG2000.
There is no advantage in JPEG2000.
> There is for instance a critical discussion in:
>
> Mali, Alexander; Palfner, Torsten; Müller, Erika
> A Study of Ridgelets - Problems and Discussions.
> In: Proceedings of the 3rd IASTED International Conference on Signal and
> Image Processing (SIP`2001), Honolulu, Hawaii, USA, pp. 334-337, August,
> 13-16,2001
It shows the weaknesses of Wavelets. See also the discussion in
http://www.e-technik.uni-rostock.de...1_mi/26mali.pdf
However, they all come to wrong conclusions regarding DCT rating,
because they all fail to recognize and utilize the fundamental
DCT property.
Regards
Guido
| |
| T.Strutz 2004-05-12, 9:28 pm |
| Guido Vollbeding wrote:
> "Dr. T Strutz" wrote:
>
>
>
> You can find the paper also here: http://jpegclub.org/temp/ .
>
Now, I understand. You mean the spectral selection in the progressive
mode of JPEG.
A corresponding picture of a decomposed image you can find in my
textbook "Bilddatenkompression" in the chapter about transforms and
filter banks, which illustrate the resolution levels for different
transformations.
The advantage of the wavelet transform is that you get a scaled version
(at 1/2 per dimension) directly from the approximation signal. If you
intend to do something similar with the DCT, you need a re-combination
of the DC coefficients with some AC coefficients in addition.
>
>
>
> With the DCT I can get directly a 75% (6/8) scaled image version,
> for example. How can you do that with DWT?
>
as Alexis Gallet said: via wavelet-packets
the dyadic implementation is only one choice. In general you can be much
more flexible.
>
>
>
> The popular schemes, particularly JPEG2000, work with fixed dyadic
> filter decompositions.
>
Well, the JPEG2000 standard offers at least the opportunity to extract
different resolutions (image scalings) from the bit stream directly.
There is no similar feature in the *Old*JPEG implementation.
I would never say the wavelet transform is better than the DCT per se.
There enough examples (standardized Video Coding for instance), where
the DCT does a good job (or derivatives of it as in MPEG4).
>
>
> The standard JPEG DCT-based image coder outperforms JPEG2000.
> There is no advantage in JPEG2000.
Sorry???
Perhaps we should define a measurement for the performance of an image
codec at first.
The hard facts are: at the same compression rate you can reach higher
PSNR values with JPEG2000, even if you optimize the quantisation tables
in the *OLD*JPEG (in order to skip the adaption to the human visual
system).
Or, if you want to meet a certain objective quality than you need less
bits using JPEG2000.
I would be very surprised, whether there is somebody else who can
underline your statement about the outperformance of the *OLD*JPEG in
terms of PSNR.
>
>
>
> It shows the weaknesses of Wavelets. See also the discussion in
weakness of wavelet?
Common Guido, every transformation has its advantages and drawbacks. My
impression is that you argue very subjective and emotionally.
First, it is not necessary to defend the DCT.
Secondly, the DCT does not get better if you denigrate the wavelet
transform.
Best regards
T.Strutz
| |
| Sebastian Gesemann 2004-05-12, 9:28 pm |
| On Fri, 30 Apr 2004, Guido Vollbeding wrote:
> No, you misunderstand.
> What I present is a *new* discovery about the DCT which was *not* known
> before! The spectral resolution of the DCT corresponds *directly* to
> the *spatial* resolution! So indeed the DCT has better *spatial*
> resolution than Mallat DWT!
I think you are mixing the term "spatial resolution" with some
other property.
If you modify one transform coefficient a certain frequency region
within a certain time region is affected. The dimensions of this
region many refer to as spatial / frequency resolution.
Because of the DCT's nature ONE transform coefficient affets the
whole transform space (8x8 pixels) but only a narrow subband of it.
The transforms are not that different, they all are some kind of
subbandfilters, just with different time/frequency resolution
trade-offs. (you CAN'T have both, high frequency and high spacial
resolution)
If you do a 2-band subband decomposition (via wavelets) the new
transform coefficients each affect a broad frequency band but only
a small spatial region => That's why we keep saying that higher
subbands of a typical wavelet decompisition have a high spatial
resolution.
bye,
Sebi
--
PGP-Key-ID (long): 572B1778A4CA0707
| |
| Guido Vollbeding 2004-05-12, 9:28 pm |
| Sebastian Gesemann wrote:
>
>
> I think you are mixing the term "spatial resolution" with some
> other property.
Well, I mean the spatial multi-scale property, which the Waveletiers
claim for their transform, but is really optimally supported by the DCT.
Regards
Guido
| |
| Guido Vollbeding 2004-05-12, 9:28 pm |
| "T.Strutz" wrote:
>
> Now, I understand. You mean the spectral selection in the progressive
> mode of JPEG.
Also. You need to adapt the coefficient-sequentialization from the
zig-zag-scheme to a square-border-scheme for optimal utilization of
the fundamental spatial multi-scale DCT property.
The fact that the original JPEG authors introduced a special
(and inferior!) "Hierarchical Mode" to achieve the same effect
shows that they didn't know that fundamental DCT property.
> Well, the JPEG2000 standard offers at least the opportunity to extract
> different resolutions (image scalings) from the bit stream directly.
> There is no similar feature in the *Old*JPEG implementation.
I have implemented a similar feature for the *Old*JPEG implementation!
See http://jpegclub.org/djpeg/ .
It is based on the discovered fundamental DCT property which was not
known before!
>
> Sorry???
> Perhaps we should define a measurement for the performance of an image
> codec at first.
> The hard facts are: at the same compression rate you can reach higher
> PSNR values with JPEG2000, even if you optimize the quantisation tables
> in the *OLD*JPEG (in order to skip the adaption to the human visual
> system).
> Or, if you want to meet a certain objective quality than you need less
> bits using JPEG2000.
> I would be very surprised, whether there is somebody else who can
> underline your statement about the outperformance of the *OLD*JPEG in
> terms of PSNR.
JPEG2000 uses arithmetic coding. Have you used arithmetic coding
with standard JPEG in your comparisons?
Sorry, I have not seen any Wavelet coder which would outperform
standard DCT JPEG.
> Common Guido, every transformation has its advantages and drawbacks.
> My impression is that you argue very subjective and emotionally.
My impression is that the Wavelet advocates often argue false and with
ignorance. I see no advantage in Wavelets, and even di vantages
(worse multi-scale property).
> First, it is not necessary to defend the DCT.
It is necessary to mention fundamental DCT properties which were
not recognized and utilized before.
> Secondly, the DCT does not get better if you denigrate the wavelet
> transform.
It is necessary to point out weaknesses of the wavelet transform
which are ignored by its advocates.
Regards
Guido
| |
| Marco Al 2004-05-12, 9:28 pm |
| Guido Vollbeding wrote:
> JPEG2000 uses arithmetic coding. Have you used arithmetic coding
> with standard JPEG in your comparisons?
> Sorry, I have not seen any Wavelet coder which would outperform
> standard DCT JPEG.
What is the PSNR for Barbara and Lena at .25 bpp?
Marco
|
|
|
|
|