Forums

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

Started by walala August 19, 2003
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


"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
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
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
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
"Piyush Kaul" <piyushkaul@yahoo.com> wrote in message
news:2e20232a.0308190421.2f57a743@posting.google.com...
> "walala" <mizhael@yahoo.com> wrote in message
news:<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 about
the
> > 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
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
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
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