6
$\begingroup$

I am aware of image-independent basis, i.e. DCT, and image-dependent basis, i.e. Karhunen–Loève, which are used in compacting energies for image compression. These bases are orthorgonal.

Are there any compression basis which are non-orthogonal that delivers better compaction than the optimal KL transformation? They can either be independent or dependent upon the statistics of the image.

EDIT: I have forgotten to mention that I am looking at block-based transformation coding.

The motivation of the question is due to the following paper Optimized Nonorthogonal Transforms for Image Compression. The premise of this paper is that the block based Karhunen–Loève transformation yields compacted coefficients, but the coefficients are still correlated across different blocks as it is often the case where adjacent blocks of a natural image are correlated to one another. To eliminate correlation across blocks, the optimal transformation would involve the use of non-orthogonal basis.

$\endgroup$
  • 2
    $\begingroup$ I may be wrong, but it seems like orthogonality itself would be an optimal criteria for compression. Otherwise you encode similar information several times, while truly distinct components don't get enough bits under quantization. $\endgroup$ – Phonon Jan 28 '12 at 18:30
  • $\begingroup$ I agree with Phonon; what motivates your search specifically for non-orthogonal basis solutions? $\endgroup$ – Jason R Jan 28 '12 at 19:10
7
$\begingroup$

Given a signal $x(t)$ of energy $\mathcal E$, suppose that $x(t)$ can be expressed as $\sum_i x_i\psi_i(t)$. If the $\psi_i(t)$ are a complete set of orthonormal signals, then $$\sum_i |x_i|^2 =\mathcal E$$ and one measure of energy compaction is the number of $x_i$ whose squared magnitude is larger than some fraction of $\mathcal E$, say $0.01\mathcal E$. Another could be the smallest number of $x_i$ such that $\sum_i |x_i|^2$ captures $99\%$, say, of the energy.

  • Some sets of orthonormal signals can be much better for representing a specific $x(t)$ than other sets of orthonormal signals. For example, sinusoids and complex exponentials are commonly used to represent periodic signals, and do a good job with respect to energy compaction when used with low pass or bandpass signals. But they require infinitely many components to represent signals such as sawtooth waves that can be represented using just one or two coefficients using orthonormal Legendre polynomials. So why are generations of electrical engineering students forced to calculate Fourier series of sawtooth waves at all? Well, Fourier series simplify life in other calculations such as what happens when the signal passes through a linear time-invariant system while Legendre polynomials do not

  • If signal-dependent orthonormal bases are allowed, then if we start a Gram-Schmidt orthonormalization procedure beginning with taking $\psi_1(t)$ to be the unit energy signal $x(t)/\sqrt{\mathcal E}$ as the first member of a set of orthonormal signals, then this orthonormal set can be used to represent $x(t)$ with $x_1 = \sqrt{\mathcal E}, x_i = 0, i > 1$ for maximal compaction! In fact, we don't even need to bother to find $\psi_i(t)$ for $i > 1$. So, how much compaction can be achieved with signal-dependent bases depends on the degree of dependence allowed between the signal and the basis to be used, etc.

  • The representation of $x(t)$ with respect to a set of non-orthonormal signals is more complicated to determine. With orthonormal signals, the coefficient $x_i$ of $\psi(t)$ is easily determined since $$\langle x(t), \psi_i(t)\rangle = \langle \sum_k x_k\psi_k(t), \psi_i(t)\rangle = \sum_k x_k \langle \psi_k(t), \psi_i(t)\rangle = x_i,$$ since $$ \langle \psi_k(t), \psi_i(t)\rangle = \begin{cases}1, & \text{if}~k = i,\\0, & \text{if}~k \neq i.,\end{cases}$$ while the simplification obtained via the orthonormality is not available for non-orthonormal signals. The question of how many of the $x_i$ are needed to capture most of the energy is also difficult to determine since the energy is not $\sum_i |x_i|^2$; it is necessary to take the cross-products $x_ix_k$ into account as well.

So, unless there are specific reasons why a particular non-orthonormal basis is important to use (e.g. it helps with things one needs to do in image processing or video processing or audio processing etc), simply using such a basis because it provides better energy compaction might well be putting the cart before the horse. But, as always, your mileage may vary, and there may be non-orthonormal signal bases that not only achieve better energy compaction but also ease your life in other aspects. It is just that it is doubtful that a general theory exists saying that non-orthonormal bases achieve better energy compaction than orthonormal bases.

$\endgroup$
  • $\begingroup$ On bullet point 2, that would mean I have to transmit the basis corresponding to the entire x(t), which defeats the purpose of compression! $\endgroup$ – Ang Zhi Ping Jan 30 '12 at 2:31
  • $\begingroup$ @AngZhiPing Did you read the last sentence in bullet point 2? Perhaps you could explain in more detail what you mean by signal-dependent basis and how you manage to avoid transmitting your signal-dependent basis. And while you are at it, tell us how you are measuring energy compaction too. $\endgroup$ – Dilip Sarwate Jan 30 '12 at 3:16
  • $\begingroup$ For a video sequence, say transmitting at 25 fps, the signal statistics will not change that drastically for maybe a few seconds. So the signal-dependent basis can be transmitted once out of every n frames. Or if the characteristics of the video is known beforehand, a basis can be formed by training with representative input. I would consider a basis to have higher energy compaction if for a given mean squared error it would consistently use less basis elements to encode an image as compared to other bases. $\endgroup$ – Ang Zhi Ping Jan 30 '12 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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