DSPRelated.com
Forums

DCT vs. DFT

Started by Matthias Alles November 4, 2003
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.