Signal and Image Compression

Part I: Perfect Reconstruction FIR QMF Bank Design

Part 1a: Design a PR Filter Bank

Algorithm for Designing H0(z)

- Design G(z) with ws=0.6 and delta_s =(delta_s_h0)² /2 and delta_p=delta_s using Remez algorithm for equiripple linear phase filter design. Start with alower order and keep increasing N until the stopband and passband specifications are met.

- Obtain coefficients of H0(z), h(n) as follows

h(n) = g(n) n not equal to N

h(N)= g(n) + delta_s

- Using Complex Cepstral Analysis (Appendix D of Vaidyanathan), obtain H0(z) as the Minimum phase real coefficent spectral factor of H(z).

- Obtaining h1,f0,f1

h1(n)=(-1)ⁿ h0(N-n)

f0(n)=h0(N-n)

f1(n)=(-1)ⁿ h0(n)

Observations:

- Obtained a filter with N=25.

- Plots of H(w) and H0(w) attached

Part 1b: Repeat the above process for ds_h0=0.001

- Obtain a filter with N=39

Part 1c: Signal Compression of x1

Variable Bit Allocation to Subbands:

· Use the Algorithm described in Appendix C of Vaidyanathan to allocate bits to the subbands

· For M subbands and an average b bits per pixel ,Bits allocated to the kth subband is given by

N_k = b + 0.5 * log(var(k)/product) …………… (A)

Where

Product = ( var(1)* var(2).. var(k) ..* var(M) ) ^(1/M)

· The bit allocation can be non-integral and we can quantize the image into round(2^N_k) bits because finally the codes are assigned using Huffman encoding which can be done for any number of symbols.

Time Varying Quantization:

Allocate different number of bits in different time intervals. But this does not help much since the variance of the signals in all time intervals is same

DPCM Encoding

Best Results were obtained using DPCM encoding followed by non-uniform quantization. The optimum codebook is designed using the Matlab function dpcmopt. The encoding is done using dpcmenco.

Huffman Encoding

Variable Bit Allocation using Huffman Encoding helps reduce the Bits per Pixel(BPP) especially for the Upper subband where only the lower values occur with higher probability

Observations and Conclusions

1. For Variable Bit Allocation to Subbands using Formula A , best results were obtained for x1

- Lower subband = 7

- Upper subband = 5

- MSE = 0.003 which is <0.01.

- BPP = 6

2. Since the signal is very random Time Varying quantization does not help because the variance of the signal even over a short period is as high as over a long period.

3. Best Results were obtained using DPCM encoding followed by non-uniform quantization. The optimum codebook is designed using the Matlab function dpcmopt. The encoding is done using dpcmenco.

4. This was followed by Huffman encoding of the signal

- Lower subband = 5bits reduce to 4.8bits per pixel and Upper subband = 3 bits reduce to 1 bits per pixel ( abig reduction) because in Upper subband only the lower vaues are higly probable and thus Huffman encoding really reduces the Bits per pixel

- MSE = 0.0052

- Mean bits per pixel is BPP = 3.7

Signal compression of x2

Observations & Conclusions:

- Best results were obtained by DPCM encoding followed by Huffman coding with 4 bits for Lower subband and 1 bit for upper subband

- MSE=0.0021

- BPP=2.6 after Huffman encoding

- The BPP obtained is lower because this signal has a lower high frequency component, so lesser bits can be allocated to the high freq component.

Final Conclusion :

- Minimum Bpp for x1 = 3.7

- Minimum Bpp for x2 = 2.6

- Since the signal is very random not much compression can be achieved. For the image in part 2 which is highly correlated, using Causal Linear Prediction for the Lower subband helps remove a lot of redundancy.

Part II: Subband Coding for Image Compression

Basic Compression Strategy:

The image is a highly correlated 2-D signal unlike the signal given in part 1. The correlation can be exploited to obtain a very large amount of compression.

The basic strategy used in all the 4 parts is similar

Bit Allocation to Subbands:

· Use the Algorithm described in Appendix C of Vaidyanathan to allocate bits to the subbands

· For M subbands and an average b bits per pixel ,Bits allocated to the kth subband is given by

N_k = b + 0.5 * log(var(k)/product) …………… (A)

Where

Product = ( var(1)* var(2).. var(k) ..* var(M) ) ^(1/M)

· The bit allocation can be non-integral and we can quantize the image into round(2^N_k) bits because finally the codes are assigned using Huffman encoding which can be done for any number of symbols.

Lower Subband Compression

1. 2D Linear Predictive Coding on the image to get a prediction. This can be done by applying Levinson’s algorithm to obtain the predictor coefficients using the 4 causal nearest neighbors(assuming rowwise encoding) of the image. This is done as follows

· Find the 2-D autocorrelation of the image for delays of 1 and 2 bits in both x and y directions

· Solve the following system of equations to get the predictor coefficients a(i)

r = Ra’

where

r = [ r(1,0) r(0,1) r(1,1) r(1,-1)]’

a’= [ a(1) a(2) a(3) a(4)]’

R= [ r(0,0) r(1,-1) r(0,1) r(0,1)

r(1,-1) r(0,0) r(1,0) r(1,-2)

r(0,1) r(1,0) r(0,0) r(0,2)

r(0,1) r(1,-2) r(0,2) r(0,0) ]

· Use these coefficients for DPCM encoding of the image .

· Include the decoder in the encoder and use the reconstructed image for prediction. Predict the (y,x) pixel using (y-1,x-1), (y-1,x), (y-1,x+1) and (y,x-1) pixels of the reconstructed image.

· Obtain error between the predicted and actual image and quantize it and use the quatized error to obtain the reconstructed pixel which is used for prediction of the next pixel.

· The 2-D Levinson’s predictor, DPCM encoder and decoder were implemented in Matlab

2. Uniform Quantization :

· The error signal requires much lesser bits per pixel as compared to the original low pass component.

· Apply Uniform Quantization only because non-uniform quantization as in part 1 will suppress the higher errors which are the more observable ones in case of an image even though they are less probable.

3. Huffman Coding

· Since the pdf of the various intensities in the quantized signal is non-uniform, variable length encoding using Huffman’s algorithm helps to reduce the bits per pixel required to encode the image.

Upper Subband Compression

1. The correlation of the high pass component is quite low so Linear prediction does not help.

2. Uniform Quantization :

· Since the high frequency component is much lower in magnitude and also less observable to the Human eye it can be encoded with fewer bits.

3. After quantization large runs of the image have the same value so Run-Length Coding which can be called a type of Vector encoding can be used to further reduce the number of bits per pixel.

4. Huffman Encoding is very useful reduces the number of bits per pixel by almost half because of the skewed pdf.

Just Noticeable Distortion Metric:

For an image, the MSE is not a good measure of the distortion because the human eye is differently sensitive to different intensities. The eye is least sensitive to very high and very low intensities and very sensitive to intensities in the range 40 to 100.

1. Based on experiments on Human subjects, the Just Noticeable Distortion (JND) can be plotted between the mean background intensity and the JND at that intensity (Refer ‘Image Scaling using Directional Modeling by ’ ) .

2. To decide whether the reconstructed image is of acceptable quality or not,

· Obtain the error image.

· Obtain the standard deviation or mean or more exactly norm of the error image in an 8X8 block.

· Obtain the background intensity as the mean of the 8X8 block and use the JND curve to obtain JND at that background level.

· For at least 70% of the pixels the norm of error(mean of absolute error) should be less than the JND for the image to be acceptable.

Parameters Required for Decompression

• 4 coefficients of the Causal Linear Predictor.
• The minimum intensity of the subband .
• The scaling factor (max-min)/2^b where b = number of bits allocated to the subband
• Compressed Signal

The Min, Scaling Factor and Predictor coefficients can be encoded using 8 bits because they are bnegligibe compared to total image size.

Part 2A: PR FIR QMF Bank

Use the PR QMF bank and apply to each row of the image separately. This is more efficient than applying it to a 1D signal generated by appending the rows together because in that case there is a sudden discontinuity at the end of each row hich will introduce false high frequency components

Observations:

1. Causal predictor Coefficients for the Lower subband obtained as a(1)=0.8346 , a(2)=0.6929, a(3)=-0.6125 a(4)=0.0845

· Bit allocation : Lower subband : 5bits , Higher subband : 3bits using A

o Image quality is very good

o Bits per pixel(bpp) after Huffman encoding = 1.65

2. Bit Allocation: Lower subband: 4.93 , Higher subband: 2.011

· Since the DPCM error is encoded for the low pass component the image variance to be used in the formula is the error variance and thus ratio of bits of low pass & high pass reduces.

· Bits per pixel after Huffman = 1.611

3. Bit allocation : Lower subband : 4.5 Upper subband : 2.5

· Image quality is sharper because bits allocated to high pass component are increased

· BPP minimum = 1.59.

· Even though bits allocated to high pass are more, because of very low probailty of higher values, Huffman encoding still results in minimum bits per pixel

· JND metric satisfied for 87% pixels

Results:

Best bits per pixel and image quality obtained with (4.5,2.5) bits to lower & higher subbands

BPP = 1.59

Part 2B: Uniform DFT Bank with minimal Amplitude Distortion

Designing a U-DFT Bank

1. Design the filters h0(n) and h1(n) such that h1(n)=(-1)^n * h0(n)

2. Take f0(n)=h0(n) and f1(n)=-h1(n)

3. Design h0(n) to minimize amplitude distortion

• Use the Matlab function fminunc to perform optimization of the Objective function given on Page 201 of Vaidyanathan, with a=0.9 and minimize wrt to the 1^st N/2 coefficients of h0(n) , since h0(n) is real and symmetric (for linear phase and thus zero phase distortion)
• Design the filter using Remez algorithm for odd N and use that as the initial guess for the optimization routine.
• Optimum filter obtained with

- N=41

- Minimum stopband attenuation = -50dB

- Maximum Amplitude distortion = 0.0077dB

Apply the U-DFT bank to each low of the image

Compression Observations:

1. Obtain Casual predictor coeffs for Lower band

2. Bit Allocation using Formula A

· Lower=5.38, Upper = 1.6

· Image quality acceptable

· Bpp after Huffman = 1.81

3. Bit Allocation using DPCM error variance for lower subband

· Lower= 4.88, Upper = 2.11

· Image quality acceptable

· Bpp after Huffman = 1.64

4. Allocate more bits to higher subband to get best Imag equalty and minimum Bpp

· Lower=4.88, Upper =2.6

· Image quality is best

· Bpp after Huffman =1.53

· JND metric satisfied for 90.65% pixels

Result s:

Best Image quality and Bpp obtained in 4 . Bpp=1.53

Part 2C: Non-Uniform 3 Channel PR bank

Use the PR filter bank design in part 1.

While reconstructing, delay the High pass image by N(order of h0) before adding to the Low pass image obtained by reconstructing from LL & LH components

Compression Observations:

For bit allocation use Formula A twice for obtaining bits for LL and LH image

1. Obtain Causal Predictor Coeffs for LL image – a(0) =0.922 , a(1)=0.6797 a(2)=-0.6477 a(3)=0.0456

2. Bit Allocation with b=2.5 bits in Formula A.

· Image quality unacceptable

3. Bit Allocation with b=3.5 in Formula A.

· Image quality is not too good, Vertical lines observed because of aliasing

· Bit Allocation : LL=7.74, LH=4.88, H=2.69

· Bpp after Huffman = 2.281

4. To remove aliasing effects allocate more bits to LH and H

· Image quality very good

· Bit Allocation: LL=7.74, LH=5.5, H=4

· Bpp after Huffman = 2.577

Results

Although min Bpp obtained in (3) , the imag equality is not too good. Bets image quality obtained in 4

Bpp=2.577.

Part 2D: 2-D Subband Coding

Use the PR filters designed in Part 1 for row-wise flowed by column-wise subband coding to get the 4 subbands

Compression Observations:

The 4 subbands can be considered as 4 frequency components in 2-D

Apply Formula A taking the variances of the 4 components

1. Obtain predictor coefficients for the LL image – a(1)=0.6360 a(2)=0.6778 a(3)=-0.4742 a(4)=0.1592
2. Integer Bit allocation according to Formula A

· LL=6, LH=4, HL=4, HH=0

• Image quality is acceptable (satisfies JND metric for 91% pixels)

· Bpp=1.63

3. Bit Allocation taking DPCM error variance

· LL=5, LH=3, HL=3 , HH=1

· Image quality is acceptable according to JND metric(for 70% pixels)

· Bpp=1.43

4. Bit Allocation acc to Formula A

· LL=5.1 LH=3.1 HL=3.4 HH=0

· Image quality is good

· Bpp=1.18

Results

Minimum BPP obtained as compared to all other parts

MIN BPP=1.18

Conclusions:

1. Min BPP in 2a = 1.59

2. Min BPP in 2b = 1.53

3. Parts 2a and 2b are quite similar except that Uniform DFt bank is used in part 2b. But since the amplitude distortion is minimized to 0.0077dB, it is almost as good as a PR bank. Thus similar compression rates are obtained

4. 2D-Linear Predictive Coding helps reduce a large amount of the redundancy in the LL component of the image. For part 2d , the error variance is only about 13% of the actual image variance and thus requires about 3bits less to encode.

5. Min BPP in part c = 2.577.

6. Bit allocation using the entire image variance is not actually valid in parts a,b and c because only image rows are separated not the columns, actually a mean of row variances would be a better measure

7. Overall Min BPP obtained in 2d = 1.18 because of the following reasons

• This exploits the 2-D frequency variations of the image. Allocating more bits to lower frequencies is the most efficient way of coding images because the High frequencies are anyway filtered out by the human eye. Thus maximum compression can be obtained in this part because it divides both the row and column vectors into Low & High freq subbands.
• Formula A for variable bit allocation to subbands is exactly applicable for part d only and thus gives minimum possible BPP for it (1.18BPP)
• 2D-Linear Predictive Coding is most efficient for the LL image because this is low frequency in both rows and columns and thus can be most easily predicted.

8. The compression is very poor for part c) because the LL component is very Low frequency so requires larger no of pixels

9. Compression Part c can be improved by using a Higher order Causal predictor for LL , since it is very highly correlated.

10. BPP in all the parts can be reduced by applying Run-Length Coding especially on the High frequency components which have runs of zeros because of quantization.