2
$\begingroup$

I want to implement 8x8 DCT and 8x8 KLT matrices to the 8-length vectors of 256x256 Lena image (e.g. each row of image there is 32 vectors 256/8 = 32 and for all rows 256x32 = 8192). I do the eigen analysis for finding KLT matrix in MATLAB as:

co = corr(I); % I is Lena image
co = co(1:8,1:8); % 8x8 autocorrelatin matrix
[V,D] = eig(co); % eigen analysis
eigval = diag(D); % eigen values
[desc, ind] = sort(eigval,'descend'); % sorting eigen values for optimum KLT
eigvec = V(:,ind); %sorted eigenvectors = 8x8 KLT matrix
y = transpose(eigvec*transpose(I(t,m:(m+7)))); % KLT matrix*8-lenght vectors-- t=1:256 and m=1:8:256 iterations of for loop
xtilda = transpose(inv(eigvec)*transpose(y)); % inverse KLT matrix*basis restricted vectors
MSE(k) = MSE(k) + immse(I(t,m:(m+7)),xtilda); % MSE between restricted vector and original vector, k iteration of for loop
MSEfor32vec(g) = mean(MSE); % average error for one row=32 vectors, g iteration of for loop

In the same way I calculated MSEfor32vec of 8x8 DCT matrix using dctmtx command.

When I got the result, I was expecting KLT had less error; but DCT had less error. In the most of signal processing books, it is concluded that KLT must have less error. What is my mistake or if my solution is true what is the point that I miss in the books? I tried to explain my question in the best way, please ask me if it is not crystal clear..

Improve this question
$\endgroup$
7
  • $\begingroup$ That's something I ought to do for a long time. I suspect here that one should compute the covariance matrix on each $8\times8$ subblocks. Not subblocks of the whole coravariance $\endgroup$
    – Laurent Duval
    Apr 26, 2020 at 12:13
  • $\begingroup$ So, every iteration there will be different KLT matrices right? $\endgroup$
    – sfw monster
    Apr 26, 2020 at 12:19
  • $\begingroup$ Though I never implemented it fully (shame on me), that's the idea: the KLT should better pack energy, but the basis vectors change, so they have to be transmitted to reconstruct the image. The latter cost (basis vectors per block) is considered prohibitive. And the DCT is a good proxy to the KLT for AR(1) models $\endgroup$
    – Laurent Duval
    Apr 26, 2020 at 12:29
  • 1
    $\begingroup$ @LaurentDuval I'm still here for your answer, so please when you are available... :) $\endgroup$
    – sfw monster
    Apr 29, 2020 at 5:55
  • 1
    $\begingroup$ You smashed it and better late than never :) Do you have a blog, if so I would like to follow your articles. $\endgroup$
    – sfw monster
    May 5, 2020 at 21:18

1 Answer 1

Reset to default
1
$\begingroup$

Natural images can seem complicated. However, the set of humanly interpretable images is relatively limited, with respect to all possible images ($24^{x\textrm{millions of pixels}}$). There is a belief that their structure can be better summarized. Indeed, lossless compaction can achieve 2-3 factor ratios, and lossy compression about 8-16 with little perceivable loss.

Most of the present image compression methods (that I know of) are based on some kind of interpolation/extrapolation schemes. The rationale is to predict some samples, and to code the hopefully smaller prediction errors either on less bits (lossless), or with less precision (lossy). Those schemes can be applied either in the original space domain, or in a transformed space: either on fixed bases (Fourier, discrete cosine transforms, wavelets, etc.), on adaptive bases (PCA, NMF, KLT), learnt dictionaries, machine learning or artificial intelligence dabases.

Adaptivity sounds sound. One can thus adapt to image features. Globally on images? Why not, but the computational prize can be important: eigen-algorithms can be $O(N^3)$. One can reduce the size to smaller image patches. You have to compute eigenvectors for each patch, passed on its second-ordre statistics (covariance). Then, less memory is required, and this can be parallelized easily. Adaptive bases are thought optimal in several cases to pack information. But they come with a price for compression. Since bases are different from patch to patch, one should code the eigenvectors and transmit them as well. For traditional rate/distortion rates, this is not favorable.

So is there a good-enough fixed-basis? Among the many choices, it turned out than one discrete cosine transform, the DCT-II, could do a good job, either theoretically or practically. This is celebrated in a 1974 paper by N. Ahmed et al.: Discrete cosine transform It is better suited to small patches, and possesses fast algorithms. There are other options, adaptations, but let's keep it simple for now.

So, assuming that one is working on patches, and computing covariance, DCT should be close to KLT in energy, and somehow better as one does not have to code vectors.

Below are previous answers related to properties of the DCT

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think that the use of DCTs for lossy compression are due to 1) there being a fast (fft-like) way of computing it, 2) it having the «energy compaction» property similar to KLT/PCA, 3) it has a «frequency domain» interpretation, thus one can treat high frequencies different from low frequencies. There cant be one static linear transform that does energy compaction for any input. Thus one would expect for some (contrived) images that the DCT makes things worse. $\endgroup$
    – Knut Inge
    May 5, 2020 at 22:15
  • $\begingroup$ True, possibly what I meant behind "a good job, either theoretically or practically" and Ahmed reference. I have added a couple of links to other related DCT answers $\endgroup$
    – Laurent Duval
    May 6, 2020 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.