why DCT

Guido Vollbeding wrote:

> Here we have another example of a rather useless explanation.
> "Important" and "unimportant" components are too general terms,
> they rather hide the true reason and don't explain why the DCT
> is so useful for image compression.
> These are just phrases, and they don't explain anything.
> But this is typical for the current state in this field:
> The relevant people ignore and deny the true reasons, and
> thus they turn in a circle and no progress is being made.

As opposed to the stunning contribution made by your post?

Ciao,

Peter K.

"Peter K." schrieb:
> 
> Guido Vollbeding wrote:
> 
> > Here we have another example of a rather useless explanation.
> > "Important" and "unimportant" components are too general terms,
> > they rather hide the true reason and don't explain why the DCT
> > is so useful for image compression.
> > These are just phrases, and they don't explain anything.
> > But this is typical for the current state in this field:
> > The relevant people ignore and deny the true reasons, and
> > thus they turn in a circle and no progress is being made.
> 
> As opposed to the stunning contribution made by your post?

Of course, I have *real* arguments which are fruitful and which
are easily understood by reasonable people.
However, there are dark forces in action today which ignore and
deny any fruitful advances in this field.
That is the reason that we didn't see any progress in JPEG for
more than a decade, and as long as those forces dominate, we
will see more confusion and less enlightenment.
The truth is always simple, and the DCT *is* simple, but this
fact is suppressed by established people who don't want to
lose their dubious position.

Regards
Guido

Matt Timmermans wrote:

(someone wrote)

>>I was curious to know why is it that DCT is used in 
 >> image compression.  why not FFT?

> Argh.  I don't like any of the answers you have so far.

> The energy compaction property is useful for the lossless parts of the 
> compression process, but the reason the DCT is used for *lossy* compression 
> is that it separates the image into relatively important components, to 
> which they eye is quite sensitive, and relatively unimportant components, to 
> which the eye is relatively insensitive.

Well, there is that, but there is also that many signals don't have so
much high frequency content.  It is possible that if there was more high
frequency content, evolution would have supplied us with eyes to see it 
better, and required different compression algorithms.

> This allows the important components to be recorded accurately, with more 
> bits, while the unimportant components can be encoded less accurately, with 
> fewer bits.  Reducing the accuracy of these unimportant components is called 
> quantization.  It is the lossy part of lossy compression.

> The DCT is used instead of the DFT, because it accomplishes this separation 
> better w.r.t the human visual response.  It has basis vectors for the most 
> important components like overall brightness and ramps, while the DFT and 
> DST do not.

I believe that the main difference between DFT, DST, DCT, and the 
various MDCTs is the boundary conditions.  They are all based on 
sinusoidal basis functions but which functions are used depends on the 
boundary conditions.   DFT have periodic boundary conditions, DST have 
the function going to zero at the boundary.  It isn't hard to see that 
those would cause large artifacts in the reconstructed image.  DCT has 
the derivative go to zero at the boundary, relatively less visible.

-- glen

Guido Vollbeding wrote:

(snip)

> I think the DFT and DST provide similar features, but the DCT is
> real (while DFT is complex) and has better boundary conditions
> for block decomposition than the DST (see cosine zero slope
> property at interval ends).

Well, for the DFT case consider it as sines and cosines with
the appropriate amplitude.   For real input the cos terms have real 
coefficients and the sin terms imaginary coefficients.  After you
remove half the terms, you are still left with periodic boundary
conditions.

So, for a given number of coefficients, which transform provides
the best compression and resultant reconstruction?

-- glen

sandeep_mc81@yahoo.com wrote:

> glen herrmannsfeldt wrote:

(snip)

>>The difference in use between DST, DCT, and DFT are the boundary
>>conditions.  (This is explained in Numerical Recipes, where I looked
>>when I wondered some time ago.)

>>DFT has periodic boundary conditions, DST has the function go to
>>zero at the boundary, and DCT has the derivative go to zero at the
>>boundary.  It seems that DCT has a smaller effect on the image
>>than the others.   That is, the effect of the blocks is less
>>visible with DCT than DFT or DST.   FFT is an algorithm,
>>or class of algorithms, for evaluating DFT.

> Can you explain what is meant by "derivative go to zero" or "function
> go to zero" ? and when does it go to zero ?

Discrete transforms are used for blocks of data of a finite size,
8 by 8 in many image compression algorithms.

A transform such as DFT, DST, or DCT represents the input as a sum
of basis functions with transform supplied coefficients.

Consider the sine transform for f(x) where x is from 0 to 8.

f(x)=A sin(pi x/8) + B sin(2 pi x/8) + C sin(3 pi x/8)
    + D sin(4 pi x/8) + E sin(5 pi x/8) + F sin(6 pi x/8)
    + G sin(7 pi x/8);

Since sin() goes to zero at zero and pi, f(0) and f(8) will be zero.
DST is a useful transform for functions that naturally go to zero.

Consider the vibration of a violin string, tied down at each end.
The sine transform would be a useful transform in that case.

The DFT has periodic boundary conditions, so it would generate
reconstructions where f(0)=f(8), also not a property of image blocks.

DCT has the boundary condition f'(0)=f'(8), which, while not necessarily 
true is much less visible than the others.

-- glen

glen herrmannsfeldt wrote:
> 
> Matt Timmermans wrote:
> 
> (someone wrote)
> 
> >>I was curious to know why is it that DCT is used in
>  >> image compression.  why not FFT?
> 
> > Argh.  I don't like any of the answers you have so far.
> 
> > The energy compaction property is useful for the lossless parts of the
> > compression process, but the reason the DCT is used for *lossy* compression
> > is that it separates the image into relatively important components, to
> > which they eye is quite sensitive, and relatively unimportant components, to
> > which the eye is relatively insensitive.
> 
> Well, there is that, but there is also that many signals don't have so
> much high frequency content.  It is possible that if there was more high
> frequency content, evolution would have supplied us with eyes to see it
> better, and required different compression algorithms.
> 

Get a good magnifying glass or better yet a microscope. There's lots of
high frequency that you aren't seeing.

> > This allows the important components to be recorded accurately, with more
> > bits, while the unimportant components can be encoded less accurately, with
> > fewer bits.  Reducing the accuracy of these unimportant components is called
> > quantization.  It is the lossy part of lossy compression.
> 
> > The DCT is used instead of the DFT, because it accomplishes this separation
> > better w.r.t the human visual response.  It has basis vectors for the most
> > important components like overall brightness and ramps, while the DFT and
> > DST do not.
> 
> I believe that the main difference between DFT, DST, DCT, and the
> various MDCTs is the boundary conditions.  They are all based on
> sinusoidal basis functions but which functions are used depends on the
> boundary conditions.   DFT have periodic boundary conditions, DST have
> the function going to zero at the boundary.  It isn't hard to see that
> those would cause large artifacts in the reconstructed image.  DCT has
> the derivative go to zero at the boundary, relatively less visible.

The DCT coefficients are discrete numbers they don't have derivatives.
But, you are talking about the underlying continuous function. The DCT
used in JPEG is not really a cosine function. Its something like
cos(pi*(2*x+1)/16) (for x:0..7) so the derivative of underlying function
at the first and last sample point is different for each of the 8
frequencies.

-jim

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

"Guido Vollbeding" <guido@jpegclub.org> wrote in message 
news:427F1599.9C942CAE@jpegclub.org...
> These are just phrases, and they don't explain anything.

I provided a very concrete mathematical explanation two posts down.

--
Matt 

jim wrote:
> 
> The DCT coefficients are discrete numbers they don't have derivatives.
> But, you are talking about the underlying continuous function. The DCT
> used in JPEG is not really a cosine function. Its something like
> cos(pi*(2*x+1)/16) (for x:0..7) so the derivative of underlying function
> at the first and last sample point is different for each of the 8
> frequencies.

Right.
I will present a clear diagram and explanation later when uploading
my draft magazine article on http://jpegclub.org .

Here is an excerpt (in German, sorry, too lazy to translate now):

 "Ausgangspunkt sind kontinuierliche Cosinus-Schwingungen mit
  unterschiedlicher Frequenz:

    cos t u pi   ;   u = 0,1,...,7   ;   0 < t < 1

  u ist der diskrete Index mit wachsender Frequenz, t ist die
  kontinuierliche Variable im Interval 0 bis 1.
  So ergibt sich f&#4294967295;r u = 0 eine konstante Funktion, f&#4294967295;r u = 1 ergibt
  sich eine halbe Cosinus-Vollschwingung, f&#4294967295;r u = 2 eine ganze
  Cosinus-Vollschwingung usw.
  Die kontinuierliche Variable t wird nun statt im ganzen Interval
  0 bis 1 an den diskreten Stellen

        2 x + 1
    t = -------   ;   x = 0,1,...,7
          16

  abgetastet. So entsteht innerhalb des Intervals (Block bei JPEG)
  eine &#4294967295;quidistante Abtastung mit Abstand 1/8 zwischen den Punkten,
  an den Intervalgrenzen (Blockgrenzen bei JPEG) vorn und hinten
  ein Abstand von 1/16 zum Randpunkt. Auf diese Weise entsteht
  durch die Aneinanderreihung von Bl&#4294967295;cken bei JPEG ein gleichm&#4294967295;&#4294967295;iger
  Abstand (1/8) zwischen den Pixeln &#4294967295;ber das gesamte Bild."

So the slope of the underlying continuous functions is indeed zero
at the interval boundaries.
The discretization is done in such a way that an equidistant grid
of sample points is accomplished when putting more blocks together.

Regards
Guido

Guido Vollbeding wrote:
> 
> jim wrote:
> >
> > The DCT coefficients are discrete numbers they don't have derivatives.
> > But, you are talking about the underlying continuous function. The DCT
> > used in JPEG is not really a cosine function. Its something like
> > cos(pi*(2*x+1)/16) (for x:0..7) so the derivative of underlying function
> > at the first and last sample point is different for each of the 8
> > frequencies.
> 
> Right.
> I will present a clear diagram and explanation later when uploading
> my draft magazine article on http://jpegclub.org .
> 
> Here is an excerpt (in German, sorry, too lazy to translate now):
> 
>  "Ausgangspunkt sind kontinuierliche Cosinus-Schwingungen mit
>   unterschiedlicher Frequenz:
> 
>     cos t u pi   ;   u = 0,1,...,7   ;   0 < t < 1
> 
>   u ist der diskrete Index mit wachsender Frequenz, t ist die
>   kontinuierliche Variable im Interval 0 bis 1.
>   So ergibt sich f&#4294967295;r u = 0 eine konstante Funktion, f&#4294967295;r u = 1 ergibt
>   sich eine halbe Cosinus-Vollschwingung, f&#4294967295;r u = 2 eine ganze
>   Cosinus-Vollschwingung usw.
>   Die kontinuierliche Variable t wird nun statt im ganzen Interval
>   0 bis 1 an den diskreten Stellen
> 
>         2 x + 1
>     t = -------   ;   x = 0,1,...,7
>           16
> 
>   abgetastet. So entsteht innerhalb des Intervals (Block bei JPEG)
>   eine &#4294967295;quidistante Abtastung mit Abstand 1/8 zwischen den Punkten,
>   an den Intervalgrenzen (Blockgrenzen bei JPEG) vorn und hinten
>   ein Abstand von 1/16 zum Randpunkt. Auf diese Weise entsteht
>   durch die Aneinanderreihung von Bl&#4294967295;cken bei JPEG ein gleichm&#4294967295;&#4294967295;iger
>   Abstand (1/8) zwischen den Pixeln &#4294967295;ber das gesamte Bild."
> 
> So the slope of the underlying continuous functions is indeed zero
> at the interval boundaries.

Yes, I'll buy that. The 'interval boundary' is between pixels and the
period of each interval extends from the mid point of the previous
adjoining interval to the mid-point of the next adjoining interval. It's
essentially what you get when you take the DFT and apply the Shift
Theorem with a non-integer half sample shift.
	But I said in my previous post the derivative at the "first and last
sample point" which is what I interpreted Glen's comments to mean.
	
	I would be curious to see the German translated.

-jim

> The discretization is done in such a way that an equidistant grid
> of sample points is accomplished when putting more blocks together.
> 
> Regards
> Guido

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

jim wrote:

(snip)

> Yes, I'll buy that. The 'interval boundary' is between pixels and the
> period of each interval extends from the mid point of the previous
> adjoining interval to the mid-point of the next adjoining interval. It's
> essentially what you get when you take the DFT and apply the Shift
> Theorem with a non-integer half sample shift.
> 	But I said in my previous post the derivative at the "first and last
> sample point" which is what I interpreted Glen's comments to mean.

It was supposed to be the boundary condition for the transform, which,
as you say, in this case is not at a sample point.

(To me a pixel has a finite width, as in an image, where a sample point
has no width.  I don't know if that is standard notation, though.)

The book by Rao and Hwang, "Techniques and Standards for Image, Video,
and Audio Coding" has a description of the four DCT's.  That is, with
the forward and inverse samples at integer or half integer points.

They call DCT-II (roman numeral two) the one with forward samples at
half integers, and inverse at integers.  At some point they indicate
that this is the one that DCT means through the rest of the book.

Somehow the symmetry of DCT-I and DCT-IV seem nicer to me, but DCT-II 
seems to be what is being used.

-- glen