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 vs. DFT
Started by ●November 4, 2003
Reply by ●November 4, 20032003-11-04
"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 thepost-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
Reply by ●November 5, 20032003-11-05
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
Reply by ●November 5, 20032003-11-05
"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-symmetricWell, 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
Reply by ●November 5, 20032003-11-05
>>>>> "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
Reply by ●November 6, 20032003-11-06
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.
Reply by ●November 6, 20032003-11-06
"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 thepost-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
Reply by ●June 11, 20162016-06-11
>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 thepost-rotation?> >Regards, >MatthiasDCT 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
Reply by ●June 11, 20162016-06-11
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
Reply by ●June 16, 20162016-06-16
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.