DCT vs. DFT

Hi!

Can anyone explain me, why you use DCT instead of DFT for transformation 
of image-data (like it is done for JPEG). I know that the DCT can be 
performed by a DFT with a post-rotation. But what are the advantages of 
the DCT compared to the DFT? Are there any benefits from the post-rotation?

Regards,
Matthias

"Matthias Alles" <alles@rhrk.uni-kl.de> wrote in message
news:bo8un4$sb$1@news.uni-kl.de...

> Can anyone explain me, why you use DCT instead of DFT for transformation
> of image-data (like it is done for JPEG). I know that the DCT can be
> performed by a DFT with a post-rotation. But what are the advantages of
> the DCT compared to the DFT? Are there any benefits from the
post-rotation?

I have never actually gone through the calculation.  You should also
consider that there is a sine transform, DST.

There are at least four different DCT's depending on the which points you
evaluate the transform at.

I believe, though, that DCT is better at hiding the transform blocks in the
decompressed image.  It is usual for the image to be considered as blocks of
8 by 8 pixels, each transformed separately.  If you look closely you can see
the blocks, especially near diagonal lines.

-- glen

Efficiency of computation and coding.

Remember the transforms are respectively for
DFT: general signal
DCT: even-symmetric signals
DST: odd-symmetric

For finite duration signals like blocks in images, they can be 
made odd/even-symmetric by tiling repeatedly or in mirror images.
So you need only either DCT or DST (simpler the better)
But DCT is preferrable than DST since mirror image version (even-symmetric)
does not introduce artificial jumps at the boundaries and signal
energies are more concentrated at lower freqencies suitable for
run-length coding after quantization.

Seung


Matthias Alles <alles@rhrk.uni-kl.de> wrote in message news:<bo8un4$sb$1@news.uni-kl.de>...
> Hi!
> 
> Can anyone explain me, why you use DCT instead of DFT for transformation 
> of image-data (like it is done for JPEG). I know that the DCT can be 
> performed by a DFT with a post-rotation. But what are the advantages of 
> the DCT compared to the DFT? Are there any benefits from the post-rotation?
> 
> Regards,
> Matthias

"Seung" <kim.seung@sbcglobal.net> wrote in message
news:fdf92243.0311042113.6704c460@posting.google.com...
> Efficiency of computation and coding.
>
> Remember the transforms are respectively for
> DFT: general signal
> DCT: even-symmetric signals
> DST: odd-symmetric

Well, I could get the book out, but that isn't the way I remembered them.

DFT is general, and periodic with a period equal to the block size.

DCT and DST are periodic twice the block size, so that they can represent
even or odd functions centered on the block.

The difference is in the expected boundary conditions.  DST goes to zero on
the boundary: sin(0), sin(pi), etc.    DCT has a zero derivative on the
boundary, as cos'(0), cos'(pi), cos'(2 pi), etc.  So the basis functions are
all sin() or all cos().

There is also the question as to which points the samples are taken at, the
points that are integer fractions of the period or the points half way in
between those points.    Numerical Recipes has a pretty good description of
sine and cosine transforms, though I don't know that they treat the
different sampling points.

-- glen

>>>>> "Matthias" == Matthias Alles <alles@rhrk.uni-kl.de> writes:

    Matthias> Hi!

    Matthias> Can anyone explain me, why you use DCT instead of DFT for
    Matthias> transformation of image-data (like it is done for JPEG). I know that
    Matthias> the DCT can be performed by a DFT with a post-rotation. But what are
    Matthias> the advantages of the DCT compared to the DFT? Are there any benefits
    Matthias> from the post-rotation?

I think DCT is used because for positively correlated signals it has
better compaction than DFT.  That is, there's less energy at the high
DCT coefficients than the DFT coefficients.

Jayant and Noll, among others, has a nice graph showing this.

I don't know what post-rotation is, so maybe what I've said is
irrelevant.

Ray

Matthias Alles wrote:
> Can anyone explain me, why you use DCT instead of DFT for transformation 
> of image-data (like it is done for JPEG). I know that the DCT can be 
> performed by a DFT with a post-rotation. But what are the advantages of 
> the DCT compared to the DFT? Are there any benefits from the post-rotation?

"The" DCT (actually, there are 8 types) has better energy-compaction 
properties than the DFT; DCTs are actually the optimal Karhunen-Loeve 
transforms for signals whose statistics are given by certain limits of 
Markov processes (see e.g. the book by Rao and Yip).

Intuitively, the DCT of a finite section of an infinite signal has less 
discontinuity at the boundaries compared to the DFT, I think.  The DFT, 
with its implicit periodic boundaries, tends to have discontinuous 
signal values at the boundaries.  DCTs (esp. types I and II and V and VI 
which correspond to even symmetry at both the left and right boundaries) 
automatically have continuous signal values at the boundaries, but will 
tend to have discontinuous first derivatives.  (JPEG uses type II.)

(Other applications of DCTs and DSTs are, of course, for solving partial 
differential equations with known even/odd boundary conditions.)

And then the even/odd boundary-condition combinations that one can get 
with various DCTs (e.g. type IV) makes it possible to do time-domain 
aliasing cancellation, which gives rise to the MDCT for lapped signal 
blocks.

"Steven G. Johnson" <stevenj@alum.mit.edu> wrote in message
news:3fa9e4ff$0$577$b45e6eb0@senator-bedfellow.mit.edu...
> Matthias Alles wrote:
> > Can anyone explain me, why you use DCT instead of DFT for transformation
> > of image-data (like it is done for JPEG). I know that the DCT can be
> > performed by a DFT with a post-rotation. But what are the advantages of
> > the DCT compared to the DFT? Are there any benefits from the
post-rotation?
>
> "The" DCT (actually, there are 8 types) has better energy-compaction
> properties than the DFT; DCTs are actually the optimal Karhunen-Loeve
> transforms for signals whose statistics are given by certain limits of
> Markov processes (see e.g. the book by Rao and Yip).
>
> Intuitively, the DCT of a finite section of an infinite signal has less
> discontinuity at the boundaries compared to the DFT, I think.  The DFT,
> with its implicit periodic boundaries, tends to have discontinuous
> signal values at the boundaries.  DCTs (esp. types I and II and V and VI
> which correspond to even symmetry at both the left and right boundaries)
> automatically have continuous signal values at the boundaries, but will
> tend to have discontinuous first derivatives.  (JPEG uses type II.)

(snip)

Much better description of what I was trying to say.

I also recommend the Rao and Yip book.  I bought mine used for much less
than new.

-- glen

>Hi!
>
>Can anyone explain me, why you use DCT instead of DFT for transformation

>of image-data (like it is done for JPEG). I know that the DCT can be 
>performed by a DFT with a post-rotation. But what are the advantages of 
>the DCT compared to the DFT? Are there any benefits from the
post-rotation?
>
>Regards,
>Matthias

DCT is preferred over DFT in image compression algorithms like JPEG
because DCT is a real transform which results in a single real number per
data point. In contrast, a DFT results in a complex number (real and
imaginary parts) which requires double the memory for storage. 


---------------------------------------
Posted through http://www.DSPRelated.com

On 11.06.16 21.17, rvinayb wrote:
> DCT is preferred over DFT in image compression algorithms like JPEG
> because DCT is a real transform which results in a single real number per
> data point. In contrast, a DFT results in a complex number (real and
> imaginary parts) which requires double the memory for storage.

No memory is doubled.

Real to complex DFT return complex conjugate for all high bins. There is 
no need to store this values at all and any reasonable DFT 
implementation will not even compute them.


Marcel

On Saturday, June 11, 2016 at 1:45:03 PM UTC-7, Marcel Mueller wrote:
> On 11.06.16 21.17, rvinayb wrote:
> > DCT is preferred over DFT in image compression algorithms like JPEG
> > because DCT is a real transform which results in a single real number per
> > data point. In contrast, a DFT results in a complex number (real and
> > imaginary parts) which requires double the memory for storage.

> No memory is doubled.
 
> Real to complex DFT return complex conjugate for all high bins. There is 
> no need to store this values at all and any reasonable DFT 
> implementation will not even compute them.

Yes.

More specifically, the DFT has periodic boundary conditions, the DCT has derivative zero
(Neumann) boundary conditions, and DST has the value zero (Dirichlet) boundary conditions.

For images and audio, the boundary effects are less noticeable in the DCT case.

There should also be a transform with zero value at one end, and zero derivative at the other end.  I don't know the name for that one.