4.4 Karhunen-Loeve Transform (KLT)
So far no transformation has been found for images that completely removes statistical dependence between transformation coefficients.
Suppose a reversible transformation is carried out on N-dimensional vector to produce and N-dimensional vector of transform coefficients, denoted by,
,
where is a linear transformation matrix that is orthonormal or unitary;
ie
(where “1” denotes transpose)
Denote the mth column of matrix by column vector , then eqn ( ) is equivalent to
The vectors are called orthonormal basis vectors for linear transform .
from eqn ( ) we can express as,
where are transform coefficients, and is represented as a weighted sum of basis vectors.
KTL transform is an orthogonal linear transformation that can remove pairwise statistical correlation between the transform coefficients; ie the KTL transform coefficients satisfy
where summation is over all possible values and and P( ) represents the probability.
This is usually written using the statistical averaging operator E as,
or
where is the variance of .
Note that statistical independence implies uncorrelation, but the reverse is not generally true (except for jointly Gaussian r v s )
The KTL can be derived by assuming
The N x N correlation matrix of then becomes
From the normality or unitary transform condition i.e.,
We get with the variances of along the main diagonal of the matrix. Thus, in terms of column vectors of , the above equation becomes
We see that the basis vectors of the KTL are the eigenvectors of , orthonormalised to satisfy
[Note that whereas the other image transforms like DFT, DCT were independent of data, the KTL transformation depends on 2nd order satisfies of the data.]
The variances of the KTL coefficients are the eigenvalues of and since is symmetric and positive definite, eigenvalues are real and positive. The KTL basic vectors and transform coefficients are also real. Besides decorrelating transform coefficients, the KTL has another useful property: it maximizes the number of transform coefficients that are small enough so that they are insignificant. For example, suppose the KTL coefficients are ordered according to decreasing variance ie
Also suppose that for reasons of economy, we transmit only the 1st pN coefficients where .
The receiver then uses the truncated column vector to form the reconstructed values as
The mean squared error (MSE) between the original and the reconstructed pels is then
It can be shown that KTL minimizes the MSE due to truncation.
To show that of all possible linear transforms operation on length N vectors having stationary statistics, the KTL minimizes the MSE due to truncation.
Let be some other transform having unit length basis vectors
First we show heuristically that the truncation error is minimum if the basis vectors are orthogonalised using the well known Gram Schmidt procedure.
Let be the vector space spanned by the “transmitted” vectors: for and let be the space spanned by the remaining vectors. Therefore any vector can be represented by plus vector i.e, as shown in figure below.
Fig ( ): If is the space spanned by transmitted basis vector, then truncation error is the length of vector. Error is minimized if is to.
If only is transmitted, then MSE is the squared length of the error vector , which is clearly minimized if is orthogonal to i.e., , is orthogonal to . Further ortghogonalisation of the basis vectors within , or within , does not affect MSE.
Thus we assume to be unitary i.e., has orthogonal basis vectors i.e.
Its transform coefficients are then given by
The mean square truncation error is as given by eqn ( ) is,
Now suppose we represent the vectors in terms of KTL basis vectors
i.e.,
and, This follows from
Since is unitary
(because basis vectors are of unit length)
Now from equation ( ) we have
and therefore can be written in terms of as,
Since the KTL is unitary,
We may now write
which form eqn , gives
As , we have
ie
which is
(Since for)
Thus from eqn for
we have
The second summation ie
and since
we have
ie which is = MSE for KTL
This concludes that the MSE for any other linear transform exceeds that of the KTL transform.