Compression - Karhunen-Loeve Image Compression

Author

Karhunen-Loeve Image Compression

sularome

2006-02-23, 3:55 am

hi all,

I have for a student project to develop a software compressing images
by the Karhunen-Loeve Transform (KLT) method. I've read 3 days and did
not found anything useful in Google. :(( if anybody of you can send me
something similar that he has developed or give me link with a good
example i will be really grateful.

thanks,

Arne Demmers

2006-02-23, 6:55 pm

"sularome" <sularome@gmail.com> schreef in bericht
news:1140684408.039046.257060@z14g2000cwz.googlegroups.com...
> hi all,
>
>
> I have for a student project to develop a software compressing images
> by the Karhunen-Loeve Transform (KLT) method. I've read 3 days and did
> not found anything useful in Google. :(( if anybody of you can send me
> something similar that he has developed or give me link with a good
> example i will be really grateful.
>
>
> thanks,
>

What you can do is do something similar like jpeg in which you change the
DCT by your own KLT function... (in my knowledge of these things they do
about the same, please someone correct me if I'm wrong).

Arne

Thomas Richter

2006-02-24, 3:55 am

Hi,

> What you can do is do something similar like jpeg in which you change the
> DCT by your own KLT function... (in my knowledge of these things they do
> about the same, please someone correct me if I'm wrong).

Not really. The KLT is defined by diagonalizing the correlation matrix, the
DCT is a time/frequency transformation.

So long,
Thomas

Jani Huhtanen

2006-02-24, 6:55 pm

Hi,

Thomas Richter wrote:
> Hi,
>
>
> Not really. The KLT is defined by diagonalizing the correlation matrix,
> the DCT is a time/frequency transformation.
>
> So long,
> Thomas

KLT diagonalizes the correlation matrix, but for natural images DCT is a
really good approximation for KLT (i.e. DCT almost diagonalizes the
corr.matrix). Both can be applied in the same way (i.e. linearly
transforming a NxN block of pixels). The problem of the KLT based
compression is that the transform is data dependant. You have to somehow
transmit the transform matrix and this results as overhead.

--
Jani Huhtanen
Tampere University of Technology, Pori

sularome

2006-02-25, 6:55 pm

ok
But may some of you give me an example. Because I have a problem with
the calculating of the eigenvectors :(( I don't really understand
them. So if you give me a good example i think that will clear the
things (I hope (:-))).

thanks in advance

Jani Huhtanen

2006-02-26, 7:55 am

sularome wrote:

> ok
> But may some of you give me an example. Because I have a problem with
> the calculating of the eigenvectors :(( I don't really understand
> them. So if you give me a good example i think that will clear the
> things (I hope (:-))).
>
> thanks in advance

If you calculate eigenvectors from a covariance matrix, then the eigenvector
corresponding to largest eigenvalue points to direction of maximum
variance. Second eigenvector is orthogonal to first one and points to
direction of the second largest variance. Look the image at this link, it
should clarify what I meant:
http://w1.cz3.nus.edu.sg/~wangjs/CZ3205/Notes6_2.htm

You can draw similar scatter plots, for example, in Matlab by constructing
x-coordinates from pixels x(n,m) and y-coordinates from pixels x(n-1,m).

When you apply the transformation you essentially replace the original
coordinate axis (look at the image) x1 and x2 by the new axis w1 and w2.

How to calculate the eigenvectors? Well, there's many ways. One way is to
decompose the covariance matrix M as M = VDV^T, where ^T is a transpose, D
is a diagonal matrix containing the eigenvalues and V is a matrix composed
of eigenvectors as columns. Such decompositions can be calculated easily
with libraries such as LAPACK http://netlib.org/lapack/lug/node48.html and
http://netlib.org/lapack/

If you use Matlab then you can just do [V,D] = eig(M).

Alternatively you could look for some numerical methods from Numerical
Recipes online book http://www.library.cornell.edu/nr/cbookcpdf.html (see
section 11 Eigensystems).

Here's some more info (nothing about finding eigenvectors though):
http://csnet.otago.ac.nz/cosc453/st..._components.pdf

--
Jani Huhtanen
Tampere University of Technology, Pori

Gustavo

2006-03-01, 6:55 pm

Some time ago I wrote a piece of code to compress images using KLT .
Documentation is in spanish, though, but you might take a look at the code
(which was written in Java).
http://www.fing.edu.uy/~gbrown/klt/index.html

Regards,
Gustavo

James G.

2006-03-11, 6:56 pm

If the picture information y(t) can be modeled as a correlation of the
white noise w(t) and the impulse response a(t) such as y(t) = a(t) *
w(t), then DCT is indentical to KLT when the operator is the circular
convolution.

- James GOLD

Sponsored Links