Forums

encoding in compression using wavelet based method???

Started by A.E lover April 15, 2007
Hi all,

I need to implement the following algorithm: decompose a signal length
2^L to an orthonormal basis (In this case is a wavelet basis".
Uniformly quantize the coefficients: 2^M+1 quant. levels, then use L
bits to encode non zero quantized coefficients and M bits to encode
its value.


 I am confused with "an orthonormal basis". Does it mean that I
decompose the original signal only 1 level?I think it is not a good
idea because if i just encode wavelet coefficients that means I omit
alot of information from coarser space( approx space with scale funs
as a basis vector). 2. if the value of the coefficient is under 2^M+1,
is the simplest way to encode is to convert the interger value of the
quantized coefficients to binary number? is it sufficient?


Thanks

> I am confused with "an orthonormal basis". Does it mean that I > decompose the original signal only 1 level?
The decimated wavelet coefficients are yielded by wavelet functions. The decimated approximation coefficients are yielded by scaling functions. The wavelet functions and scaling functions together give you an orthornormal basis of your original image space. Thus, both approximation and wavelet coefficients should be encoded. I think a decomposition of the image until the max. scale J is beneficial (2^J = N, where N x N is the image size), since you will benefit from the sparsity of the wavelet domain.
> as a basis vector). 2. if the value of the coefficient is under 2^M+1, > is the simplest way to encode is to convert the interger value of the > quantized coefficients to binary number? is it sufficient?
You could do that, but I don't think it to be optimal. Indeed, as the wavelet domain is sparse, you will have many small coefficients which are actually zeros after quantification. Now you may use any lossless encoding scheme (RLE, Huffman, etc.) to encode the non-zero quantified coefficients and there locations to gain more compression.
A.E lover said the following on 15/04/2007 14:16:
> Hi all, > > I need to implement the following algorithm: decompose a signal length > 2^L to an orthonormal basis (In this case is a wavelet basis". > Uniformly quantize the coefficients: 2^M+1 quant. levels, then use L > bits to encode non zero quantized coefficients and M bits to encode > its value. > > > I am confused with "an orthonormal basis". Does it mean that I > decompose the original signal only 1 level?
An "orthonormal basis" means that your basis functions are orthogonal to each other, and that they are normalised such that each has a vector norm of 1, i.e.: \int |g_i(t)|^2 dt = 1 (where the integral is performed from -infinity to +infinity). -- Oli
Thanks Bo and Oli.

However I am still confused with the length of the obtained
coefficients (both detail and approx).
I use dwt in MATLAB (syntax:  [ac dc]=dwt(s,'db2'),  and decompose 8
times (= log_2 (256)) a signal s with length 256 (2^L), wavelet filter
is db2.  I obtained around 290 coefficient samples for  the union of
dc1, dc2,....,dc8 and ac8. (dc: detail coeff, ac: approx coeff).
As Bo wrote, I need to encode all of the non zero coefficients among
these 290 coefficents.
However the requirement of the project  is to use L  bits (8 in this
case) to encode positions of these non-zero coefficents and M bits for
it values, Prof doesn't allow to use  huffman or anything else
encoder. I just contact the Prof and learn this.

Well, with 290 coefficients and I need  more than 8 bits to encode the
positions.

Do you have any hint?  also I am a little bit confused, as I remember
from the lecture:
a signal has length 256 samples after we decompose it, the total
number of coeffcients will be the same as the origin : 256.
Why here in matlab I get more than 256. specifically  290 (not sure
290 but for sure it is greater than 256). Or my memory is incorrect.


By the way,in this link:

http://www.owlnet.rice.edu/~elec301/Projects00/wavelet_image_comp/


these students use only a single level to decompose the image and then
threshold it. As Bo suggests, I need to decompose until the max of J.
Is it better than decompose only one  time?

Thanks

Bo wrote:
> > I am confused with "an orthonormal basis". Does it mean that I > > decompose the original signal only 1 level? > > The decimated wavelet coefficients are yielded by wavelet functions. > The decimated approximation coefficients are yielded by scaling > functions. The wavelet functions and scaling functions together give > you an orthornormal basis of your original image space. Thus, both > approximation and wavelet coefficients should be encoded. I think a > decomposition of the image until the max. scale J is beneficial (2^J = > N, where N x N is the image size), since you will benefit from the > sparsity of the wavelet domain. > > > as a basis vector). 2. if the value of the coefficient is under 2^M+1, > > is the simplest way to encode is to convert the interger value of the > > quantized coefficients to binary number? is it sufficient? > > You could do that, but I don't think it to be optimal. Indeed, as the > wavelet domain is sparse, you will have many small coefficients which > are actually zeros after quantification. Now you may use any lossless > encoding scheme (RLE, Huffman, etc.) to encode the non-zero quantified > coefficients and there locations to gain more compression.
> However I am still confused with the length of the obtained > coefficients (both detail and approx). > I use dwt in MATLAB (syntax: [ac dc]=dwt(s,'db2'), and decompose 8 > times (= log_2 (256)) a signal s with length 256 (2^L), wavelet filter > is db2. I obtained around 290 coefficient samples for the union of
Matlab uses by default the symmetric border condition, so it yields more than N (=2^J) coefficients. You can use the periodic border condition to yield exactly N coefficients: [ac dc]=dwt(s,'db2', 'mode', 'per');
> Is it better than decompose only one time?
I think a full decomposition is better, since otherwise you need to encode every approx. coefs and you are not allowed to use any lossless coder. You should try and see. The compression performance denpends also on the choice of wavelet. db2 is not bad, but if you have a smototh signal, higher order db wavelets (but not too high) would perform better. Again, try and see it.
Great!!! Thanks Bo so much. I will try your way to see what will
happend. Thanks again.


On Apr 15, 6:25 pm, "Bo" <bo.zhang0...@gmail.com> wrote:
> > However I am still confused with the length of the obtained > > coefficients (both detail and approx). > > I use dwt in MATLAB (syntax: [ac dc]=dwt(s,'db2'), and decompose 8 > > times (= log_2 (256)) a signal s with length 256 (2^L), wavelet filter > > is db2. I obtained around 290 coefficient samples for the union of > > Matlab uses by default the symmetric border condition, so it yields > more than N (=2^J) > coefficients. You can use the periodic border condition to yield > exactly N coefficients: > [ac dc]=dwt(s,'db2', 'mode', 'per'); > > > Is it better than decompose only one time? > > I think a full decomposition is better, since otherwise you need to > encode every approx. coefs and you are not allowed to use any lossless > coder. You should try and see. The compression performance denpends > also on the choice of wavelet. db2 is not bad, but if you have a > smototh signal, higher order db wavelets (but not too high) would > perform better. Again, try and see it.

Hi BO:

As you said "db2' is okie, but you expected a smoother wavelet will
give a better result.
The problem is that when I calculate the distortion, the db2 gives me
a better result than the db3 or db4 does.

does this depend on the signal to compress?

My signal is f[n]=1 when n=0,1,2,3 and f[n]=-1 when n=4,5,6,7.  and
f[n]=0 otherwise

The length of f[n] is 256/

I got the smallest distortion with db2.

Can you explain why?

Thanks

> > I think a full decomposition is better, since otherwise you need to > > encode every approx. coefs and you are not allowed to use any lossless > > coder. You should try and see. The compression performance denpends > > also on the choice of wavelet. db2 is not bad, but if you have a > > smototh signal, higher order db wavelets (but not too high) would > > perform better. Again, try and see it.- Hide quoted text - > > - Show quoted text -