Dear all, Can anybody tell me what are the key properties of DCT/IDCT(2D) which lend it to the such wide use in image processing? I mean, why FFT, DHT, and other transformations are not used in image processing/compression? Book says that DCT resembles K-L transformation mostly, but how about the other transforms? Anybody give me some explanations? Thanks a lot, -Walala

# what's the key properties of DCT/IDCT that lend it such wide use in image processing?

Started by ●August 19, 2003

Reply by ●August 19, 20032003-08-19

"walala" <mizhael@yahoo.com> wrote in message news:<bhsct1$o9h$1@mozo.cc.purdue.edu>...> Dear all, > > Can anybody tell me what are the key properties of DCT/IDCT(2D) which lend > it to the such wide use in image processing? > > I mean, why FFT, DHT, and other transformations are not used in image > processing/compression? > > Book says that DCT resembles K-L transformation mostly, but how about the > other transforms? > > Anybody give me some explanations? > > Thanks a lot, > > -WalalaHi Walala This link may help answer your questions: http://www.cs.technion.ac.il/Labs/Isl/Project/Projects_done/VisionClasses/DIP/DCT_and_Compression/DCT.html For the second part (DCT vs DFT) besides the better compression (less coefficents required for same Mean Squared Error there seem to be other benifits too. Here is an extract: "First of all, unlike with DFT, where the transform coefficient are in general case complex, DCT yields real coefficients (for real input), thus less storage space is needed. Another drawback of the DFT is the so called blocking artifact : as a rule original image is segmented into smaller blocks and because of the cyclicity assumption underlying Fourier transform pixels along two opposite borders of the block are expected to have similar values. When it's not the case, reconstruction of the image from only a partial number of coefficients will result in erroneous values along both borders (this is also known as Gibbs phenomenon). This phenomenon tends to make the block boundaries visible. Since assumptions, underlying DCT are different (mirror symmetry is assumed), the discontinuities are less severe, therefore blocking artifact is significantly reduced" Regards Piyush

Reply by ●August 19, 20032003-08-19

The only reason why DCT is used is the computational efficiency with the real 2d signal. FFT = DHT = 2*DCT. Other transforms like wavelets or Walsh transform are used also. Vladimir Vassilevsky, Ph.D. DSP and Mixed Signal Design Consultant http://www.abvolt.com walala wrote:> > Dear all, > > Can anybody tell me what are the key properties of DCT/IDCT(2D) which lend > it to the such wide use in image processing? > > I mean, why FFT, DHT, and other transformations are not used in image > processing/compression? > > Book says that DCT resembles K-L transformation mostly, but how about the > other transforms? > > Anybody give me some explanations? > > Thanks a lot, > > -Walala

Reply by ●August 19, 20032003-08-19

Hello Piyush Kaul, FFT, DHT and DCT are fully equivalent and can be derived one from the other. It is just a matter of convenience and computing efficiency which transform to use. For 2d real signal obviously DCT is the choice. Vladimir Vassilevsky, Ph.D. DSP and Mixed Signal Design Consultant http://www.abvolt.com Piyush Kaul wrote:> > "walala" <mizhael@yahoo.com> wrote in message news:<bhsct1$o9h$1@mozo.cc.purdue.edu>... > > Dear all, > > > > Can anybody tell me what are the key properties of DCT/IDCT(2D) which lend > > it to the such wide use in image processing? > > > > I mean, why FFT, DHT, and other transformations are not used in image > > processing/compression? > > > > Book says that DCT resembles K-L transformation mostly, but how about the > > other transforms? > > > > Anybody give me some explanations? > > > > Thanks a lot, > > > > -Walala > Hi Walala > > This link may help answer your questions: > http://www.cs.technion.ac.il/Labs/Isl/Project/Projects_done/VisionClasses/DIP/DCT_and_Compression/DCT.html > > For the second part (DCT vs DFT) besides the better compression (less > coefficents required for same Mean Squared Error there seem to be > other benifits too. Here is an extract: > > "First of all, unlike with DFT, where the transform coefficient are in > general case complex, DCT yields real coefficients (for real input), > thus less storage space is needed. > > Another drawback of the DFT is the so called blocking artifact : as a > rule original image is segmented into smaller blocks and because of > the cyclicity assumption underlying Fourier transform pixels along two > opposite borders of the block are expected to have similar values. > When it's not the case, reconstruction of the image from only a > partial number of coefficients will result in erroneous values along > both borders (this is also known as Gibbs phenomenon). This phenomenon > tends to make the block boundaries visible. Since assumptions, > underlying DCT are different (mirror symmetry is assumed), the > discontinuities are less severe, therefore blocking artifact is > significantly reduced" > > Regards > Piyush

Reply by ●August 19, 20032003-08-19

On Tue, 19 Aug 2003 11:14:41 -0500, Vladimir Vassilevsky <vlv@abvolt.com> wrote:>Hello Piyush Kaul, > >FFT, DHT and DCT are fully equivalent and can be derived one from the >other. It is just a matter of convenience and computing efficiency which >transform to use. For 2d real signal obviously DCT is the choice. > >Vladimir Vassilevsky, Ph.D.Just picking a large nit, but the FFT, DHT, and DCT are not fully equivalent, their outputs are very different with respect to each other. Each can be made to behave like the others, but only with some deliberate additional processing. Changing the basis function of a transform, which is what distinguishes the above from each other, has a necessary change on its output. Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org

Reply by ●August 19, 20032003-08-19

"Piyush Kaul" <piyushkaul@yahoo.com> wrote in message news:2e20232a.0308190421.2f57a743@posting.google.com...> "walala" <mizhael@yahoo.com> wrote in messagenews:<bhsct1$o9h$1@mozo.cc.purdue.edu>... (snip)> > I mean, why FFT, DHT, and other transformations are not used in image > > processing/compression? > > > > Book says that DCT resembles K-L transformation mostly, but how aboutthe> > other transforms? > > > > Anybody give me some explanations?(snip)> For the second part (DCT vs DFT) besides the better compression (less > coefficents required for same Mean Squared Error there seem to be > other benifits too. Here is an extract: > > "First of all, unlike with DFT, where the transform coefficient are in > general case complex, DCT yields real coefficients (for real input), > thus less storage space is needed.Well, with consideration for even/odd functions that part can be corrected.> Another drawback of the DFT is the so called blocking artifact : as a > rule original image is segmented into smaller blocks and because of > the cyclicity assumption underlying Fourier transform pixels along two > opposite borders of the block are expected to have similar values. > When it's not the case, reconstruction of the image from only a > partial number of coefficients will result in erroneous values along > both borders (this is also known as Gibbs phenomenon). This phenomenon > tends to make the block boundaries visible. Since assumptions, > underlying DCT are different (mirror symmetry is assumed), the > discontinuities are less severe, therefore blocking artifact is > significantly reduced"Discontinuities in the function value are more visible than discontinuities in the derivative. -- glen

Reply by ●August 19, 20032003-08-19

Hi Vladimir, I believe you are not correct. While the three transforms are equivalent when infinite precision arithmetic is assumed, their QoR varies widely if behavior with coefficient quantization is considered. Coefficient quantization is the lossy step in image/video compression that gives us the great results (good picture quality and small filesize) that we are all used to by now. The DCT is primarily used for image/video compression due to its 'nice' features in terms of quality loss due to coefficient quantization. As the original poster noted, it is the most similar to the Karhunen-Loeve Transform, which by its very definition minimizes error induced by coefficient quantization (under conditions of optimal coefficient-bit allocation). Ljubisa Bajic ATI Technologies -- My opinions do not represent those of my employer -- Vladimir Vassilevsky <vlv@abvolt.com> wrote in message news:<3F4218FC.770F0C8A@abvolt.com>...> The only reason why DCT is used is the computational efficiency with the > real 2d signal. FFT = DHT = 2*DCT. > Other transforms like wavelets or Walsh transform are used also. > > Vladimir Vassilevsky, Ph.D. > > DSP and Mixed Signal Design Consultant > > http://www.abvolt.com > > > > > walala wrote: > > > > Dear all, > > > > Can anybody tell me what are the key properties of DCT/IDCT(2D) which lend > > it to the such wide use in image processing? > > > > I mean, why FFT, DHT, and other transformations are not used in image > > processing/compression? > > > > Book says that DCT resembles K-L transformation mostly, but how about the > > other transforms? > > > > Anybody give me some explanations? > > > > Thanks a lot, > > > > -Walala

Reply by ●August 19, 20032003-08-19

Hi Ljubisa, I digest the following as the enabling feature of DCT in the field of image compression:> DCT by its very definition minimizes error induced by coefficient > quantization (under conditions of optimal coefficient-bit allocation).However, I am interested in the order of invention of DCT and quantization for use in image compression: People first applied DCT into image compression then designed the corresponding quantization matrix; or People first designed the quantization matrix then found the minimal error transform for it? It seems to me that with the addition of quantization matrix, things get perplexed... Thanks -Walala

Reply by ●August 20, 20032003-08-20

Hi What about the phase information of the image. I think it is reduntant, so DCT (computationally efficient than DFT) is used instead of DFT. Also DCT is a variant of DFT, fast algorithms are available. I am not sure about quantization noise issue or i didnot come across compression techniques. so i am not sure about the advantage of DCT over DFT related to those fields. regards ajith eternal_nan@yahoo.com (Ljubisa Bajic) wrote in message news:<9b0afb2c.0308191408.21782c8@posting.google.com>...> Hi Vladimir, > > I believe you are not correct. While the three transforms are > equivalent when > infinite precision arithmetic is assumed, their QoR varies widely if > behavior > with coefficient quantization is considered. Coefficient quantization > is the > lossy step in image/video compression that gives us the great results > (good > picture quality and small filesize) that we are all used to by now. > The DCT is primarily used for image/video compression due to its > 'nice' features in terms of quality loss due to coefficient > quantization. As the > original poster noted, it is the most similar to the Karhunen-Loeve > Transform, > which by its very definition minimizes error induced by coefficient > quantization (under conditions of optimal coefficient-bit allocation). > > Ljubisa Bajic > ATI Technologies > -- My opinions do not represent those of my employer -- > > > Vladimir Vassilevsky <vlv@abvolt.com> wrote in message news:<3F4218FC.770F0C8A@abvolt.com>... > > The only reason why DCT is used is the computational efficiency with the > > real 2d signal. FFT = DHT = 2*DCT. > > Other transforms like wavelets or Walsh transform are used also. > > > > Vladimir Vassilevsky, Ph.D. > > > > DSP and Mixed Signal Design Consultant > > > > http://www.abvolt.com > > > > > > > > > > walala wrote: > > > > > > Dear all, > > > > > > Can anybody tell me what are the key properties of DCT/IDCT(2D) which lend > > > it to the such wide use in image processing? > > > > > > I mean, why FFT, DHT, and other transformations are not used in image > > > processing/compression? > > > > > > Book says that DCT resembles K-L transformation mostly, but how about the > > > other transforms? > > > > > > Anybody give me some explanations? > > > > > > Thanks a lot, > > > > > > -Walala