Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.
Sign up to join this community
I have a basic implementation knowledge of the 2D 8x8 DCT used in image & video compression. Whilst reading about Principle Component Analysis, I can see a lot of similarity, albeit PCA is clearly more generic. When I've read about DCT previously it was always presented in relation to DFT. So my question is how can the DCT be derived from a PCA perspective? (even a hand-wavey explanation is sufficient)
Many thanks
The main difference between DCT and PCA (more precisely, representing a dataset in the basis formed by the eigenvectors of its correlation matrix - also known as the Karhunen Loeve Transform) is that the PCA must be defined with respect to a given dataset (from which the correlation matrix is estimated), while the DCT is "absolute" and is only defined by the input size. This makes the PCA an "adaptive" transform, while the DCT is data-independent.
One might wonder why the PCA is not used more often in image or audio compression, because of its adaptivity. There are two reasons :
Imagine an encoder computing a PCA of a dataset and encoding the coefficients. To reconstruct the dataset, the decoder will need not only the coefficients themselves, but also the transform matrix (it depends on the data, which it does not have access to!). The DCT or any other data-independent transform might be less efficient in removing statistical dependencies in the input data, but the transform matrix is known in advance by both the coder and decoder without the need for transmitting it. A "good enough" transform which requires little side information is sometimes better than an optimal transform which requires an extra load of side information...
Take a large collection of $N$ 8x8 tiles extracted from photos. Form a $N \times 64$ matrix with the luminosity of these tiles. Compute a PCA on this data, and plot the principal components that will be estimated. This is a very enlightening experiment! There is a very good chance that most of the higher-ranked eigenvectors will actually look like the kind of modulated sine-wave patterns of the DCT basis. This means that for a sufficiently large and generic set of image tiles, the DCT is a very good approximation of the eigenbasis. The same thing has also been verified for audio, where the eigenbasis for log- signal energy in mel-spaced frequency bands, estimated on a large volume of audio recordings, is close to the DCT basis (hence the use of DCT as a decorrelation transform when computing MFCC).
