Bit Plane Compression

                               This tutorial  explains in brief the compression of an image using bit plane slicing technique. This is a lossy compression technique. In other words,  part of the data is lost in the compression process compared to the original image.

Check out the post on bit plane slicing to understand better.

Let’s explain with a simple example how encoding and decoding is carried out in Bit plane compression. In this example, the Most Significant Bit(MSB) alone is considered and encoded. For better quality image retrieval, combination of various bit planes such as [8 7] ,[[8 7 6], [8 7 6 5] ..etc can be encoded and decoded. The numbers 8,7,6 , 5 ,..etc represent bit positions.

Compression:

Step 1: Consider a matrix A of size 3 x 5

Step 2: Obtain the binary equivalent of the values in the matrix A. The MATLAB function ‘dec2bin’ can be used for conversion

Step 3: Extract the Most Significant Bit(MSB)  for each value in the matrix from the binary representation. The MATLAB function ‘bitget’ can be used for the same.

Step 4:Rearrange the above MSB values such that each row  contains 8 columns or 8 bits.

In the above example, we  have 3x5=15 values but we need 8 columns in each row.  It can be achieved by padding the matrix with zeros in the end in order to form a matrix which has 8 columns in each row.

Step 5: Convert the binary representation in each row to a decimal number and store it.

Use ‘bin2dec’ MATLAB function to convert binary values to decimal values.

In our example, decimal equivalent of [1 0 0 0 1 0 0 0] = 136 and [1 0 1 0 1 0 1 0] = 170

MATLAB CODE:

clear all

clc

A = [180 4 80 33 201; 120 27 11 160 28; 224 1 133 67 144];

A = uint8(A);

%Encoding

%Check whether zeros has to be appended to the matrix

rem = mod(numel(A),8);

if rem~=0

rem = 8-rem;

end

%Extract the MSB

bit8 = bitget(A,8);

b8 = bit8';

b8 = b8(:);

b8 = [b8;zeros(rem,1)];

%Reshape the matrix as such each row contains 8 columns

mat8 = reshape(b8,8,[])';

str8 = num2str(mat8);

str8 = str8(:,1:3:end);

%Convert the binary to decimal

compressedbit8 = uint8(bin2dec(str8));

Verify the compressed data and original data size for comparison of size used for storage.

MATLAB CODE:

whos A compressedbit8

Decompression:

For Decoding an image/matrix, the compressed / encoded data has to be provided as the input along with size of the original image/matrix and  the vector containing the position of the bits used for encoding in order.

Step 1: Convert the decimal value of the compressed data into binary format.

Step 2: Remove the extra zeros appended to the matrix, if needed.

Step 3: Reshape the matrix to size of the original matrix A using the MATLAB function ‘reshape’.

Step 4: Preallocate a matrix of same size of original matrix A and replace the MSB(Most Significant Bit) of each value in the matrix with the bit we decompressed in the previous step.

Use the MATLAB function ‘bitset’

Step 5: Display the final data.

MATLAB CODE:

%Decoding

%Convert Decimal to Binary

decompressedbit8 = dec2bin(compressedbit8,8);

%Reshape the matrix to the size of original matrix size

%And remove extra zeros appended to the matrix

dbit8 = decompressedbit8';

dbit8 = dbit8(:);

dbit8 = dbit8(1:end-rem);

dbit8 = reshape(dbit8,size(A,2),size(A,1))';

%Preallocate a matrix

Image = zeros([size(A,1) size(A,2)]);

slice8 = zeros([size(A,1) size(A,2)]);

%Set the MSB with the binary values obtained from decompressed matrix

ind_bit8 = find(dbit8=='1');

slice8(ind_bit8) = 1;

Image = bitset(Image,8,slice8);

Image = uint8(Image);

%Display data

display(Image);

The above method can be extended for images by extracting combination of bits.

Example: The 7 and the 8 th bit can be extracted and stored or 2,4,6 and 8 bit can also be extracted.

COMPRESSION:

MATLAB CODE:

%ENCODING

clear all

clc

%INPUT IMAGE

A = imread('cameraman.tif');

%Encoding

bitnums = [6;7;8]; %BIT PLANES

%CHECK IF PADDING WITH ZEROS IS NEEDED OR NOT

rem = mod(numel(A),8);

if(rem~=0)

rem = 8-rem;

end

%EXTRACT EACH BIT AND STORE IT IN THE MATRIX

forinc =1:length(bitnums)

Ind = bitnums(inc);

%EXTRACT THE 'n'th BIT

bitval = bitget(A,Ind);

%PAD WITH ZEROS AND RESHAPE THE MATRIX

bval = bitval';

bval = bval(:);

bval = [bval;zeros(rem,1)];

matv = reshape(bval,8,[])';

strv = num2str(matv);

strv = strv(:,1:3:end);

%CONVERT BINARY TO DECIMAL

compressedbitv(:,inc) = uint8(bin2dec(strv));

end

%STORE THE COMPRESSED DATA IN A FILE

%OPTIONAL

fp = fopen('compressed_data678.data','wb');

fwrite(fp,compressedbitv','uint8');

fclose(fp);

EXPLANATION:

In the given example, 6,7 and 8 bit planes are extracted and compressed.

The compressed data can be stored in a file, if needed.

Original Image size       = 64 KB

Compressed Image size = 24 KB 

NOTE: bitnums = [6;7;8]; Modify this line to compress combination of bits.

Some examples: bitnums=[8] or bitnums=[2;4;6;8] or bitnums=[5;6;7;8]

DECOMPRESSION:

%DECOMPRESSION

clear all

clc

%INPUT FROM THE USER

M = 256; %SIZE OF THE ORIGINAL IMAGE

N = 256; %SIZE OF THE ORIGINAL IMAGE

bitnums = [6;7;8]; %BIT PLANES USED

rem = mod(M*N,8);

if(rem~=0)

rem = 8-rem;

end

%READ THE COMPRESSED DATA

fp = fopen('compressed_data678.data','rb');

compressedbitv = fread(fp,[length(bitnums),Inf],'uint8')';

fclose(fp);

%PREALLOCATE THE MATRIX

Image = zeros([M N]);

forinc = 1:length(bitnums)

Ind = bitnums(inc);

%CONVERT DECIMAL TO BINARY

decompressedbitv = dec2bin(compressedbitv(:,inc),8);

%REMOVE EXTRA ZEROS AND RESHAPE THE MATRIX

dbitv = decompressedbitv';

dbitv = dbitv(:);

dbitv = dbitv(1:end-rem);

dbitv = reshape(dbitv,N,M)';

%SET THE 'n'th BIT

slicev = zeros([M N]);

ind_bitv = find(dbitv == '1');

slicev(ind_bitv) = 1;

     Image = bitset(Image,Ind,slicev);

end

%DISPLAY THE IMAGE

Image = uint8(Image);

figure,imagesc(Image);colormap(gray);

Bit Plane 8

Bit Planes 7,8

Bit Planes 2,4,6 and 8

EXPLANATION:

The bit planes 6, 7 and 8 are extracted and the image is formed using those bits.

NOTE:

For decoding the following lines should be modified during each run.

%INPUT FROM THE USER

M = 256; %SIZE OF THE ORIGINAL IMAGE

N = 256; %SIZE OF THE ORIGINAL IMAGE

bitnums = [6;7;8]; %BIT PLANES USED

The size of the original image should be given as an input. Update M and N with the number of rows and columns of the original image.

The vector ‘bitnums’ should be exactly same as the one in the encoding procedure.

Whenever, ‘bitnums’ is modified during encoding then it should be modified during decoding process as well.

Partially Colored gray scale Images

                                  

                                          A RGB image contains three components. Namely: Red, Blue and Green.

The below figure represents various colors and their corresponding RGB (Red , Green and Blue) component values.

Gray scale value of the above RGB components:

A gray scale image can be formed from a RGB image by taking the sum of 29.89% of pixel value of Red component, 58.70% of pixel value of green component and 11.40% of pixel value of Blue component.

NOTE:  Check how toconvert rgb image into grayscale without using matlab built in function.

For instance, consider the second shade with values [150 9 22] from the color vector.

The corresponding gray scale value = (150*0.2989)+(9*.5870)+(22*.1140)

                                                                = 52.62

                                                                = 53 (approximately) 

Consider the gray scale values 61 ,106 and 83 from the gray scale vector.

If the gray scale value is updated in the RGB components of the colored vector then that particular shade will be in gray scale as shown below.

The value 61 is updated in Red, Green and Blue components. Similarly, 106 and 83 are also updated.

Using this principle, we can use both RGB and gray color in a single image to obtain a partially colored gray scale image.

Let us now learn how to obtain partially colored gray scale image.

Step 1: Read the input RGB image and its corresponding RGB components

 1.       Read an RGB Image

 2.       Store the Red component in matrix R, Green in matrix G and Blue in matrix B.

Step 2:  Define the Grayscale Image

1.       Convert RGB Image to Grayscale Image (GS)

2.       Create a matrix R1, G1 and B1 of the same size of matrix R, G and B

3.       Update the matrices R1,G1 and B1 with the value of the matrix GS

Step 3: Create a Mask

1.       Create a matrix of size GS

2.       Update the pixel positions with one if the pixel position should be RGB else zero or vice versa.

Step 4:  Find the index of the masked positions from the Mask

Step 5:  Create partial color and gray scale

1.       Obtain the Red component (R) for the corresponding index of the mask and update it in the R1 matrix. Similarly, update the other matrices G1 and B1 with values of G and B matrices based on the index of the mask.

2.       Create a Three dimensional matrix of the same size of RGB Image

3.       Update the three dimensional matrix with the R1, G1 and B1 components. This is the required partially coloured gray scale image.

Step 6:  Display the partially colored gray scale image

MATLAB CODE:

%Read a RGB image

A = imread('watch1.jpg');

R = A(:,:,1); %RED component

G = A(:,:,2); %GREEN component

B = A(:,:,3); %BLUE component

%RGB to Gray scale Image

GS = rgb2gray(A);

R1 = GS;

G1 = GS;

B1 = GS;

%Mask - Circle

wndow = uint8((gausswin(size(A,1),12)*gausswin(size(A,2),7)')*255);

wndow = ~wndow;

%Find Index

X = find(wndow==0);

R1(X) = R(X);

G1(X) = G(X);

B1(X) = B(X);

%Create a RGB matrix

C = zeros(size(A));

C(:,:,1) = R1;

C(:,:,2) = G1;

C(:,:,3) = B1;

C = uint8(C);

figure,imshow(C);

 The mask can also be created manually as shown below:

Edge detection using Local Variance

Local statistics can determine the gradient of the image. The local variance can be used to generate an edge map.

Steps to be performed:

1.       Read a grayscale image

2.       Define a window size (For eg: 3x3,5x5,7x7)

3.       Find the local variance

4.       Find the global mean of the local variance

5.       Set local variance to zero if it is less than the global mean else set it to one

MATLAB code:

%Boundary Detection - Local Variance

%Read an image

I = imread('rice.png');

figure,imagesc(I);colormap(gray);

I = double(I);

Explanation:

A grayscale image is taken as input for edge detection. If the input image is RGB then convert it to gray scaleusing ‘rgb2gray’.

MATLAB code:

%Define the window size

sz=3;

window = ones(sz)/sz.^2;

%Find the local mean

mu = conv2(I,window,'same');

%Find the local Variance

II = conv2(I.^2,window,'same');

Lvar = II-mu.^2;

figure,imagesc(Lvar);colormap(gray);title('Local Variance of the image');

Explanation:

A window size of 3 by 3 is defined and local variance is computed. Check ‘local variance- matlab code’ to understand how local variance is estimated.

MATLAB CODE:

%Define a Threshold

meanL = mean(Lvar(:));

%Set the pixel values based on threshold

Boundary = zeros(size(Lvar));

Boundary(Lvar < meanL)=1;

Boundary(Lvar >= meanL) = 0;

figure,imagesc(Boundary);colormap(gray);title('Boundary Extracted Image');

Explanation:

 The mean of the local variance is obtained and using the mean value as threshold, the boundary is defined for the image.  The mean value of the given image is 239.3638.

The threshold value can also be set randomly by the user. For instance, set the threshold value to 500.

Local Variance – MATLAB CODE

Variance Formula:

Let us understand how global variance works. First let us theoretically define variance in simple terms. In lay man terms, variance is defined as how divergent values are from the average value.

Consider a matrix A=[5 5 5;5 5 5]. The variance of the matrix A is zero.. In the given example, the average is 5 and all the elements in the matrix are equal to 5. So finding deviation in the above example is not possible.

Let us consider another matrix B =[3 7 1;5 4 2]. The variance of the matrix B is 3.8889.. Let us arrive at the result using theoretical formula as follows:

Variance of B = Mean of B^2 – (mean of B)^2

                        = 17.333 – 13.444

                        = 3.888

MATLAB CODE:

Var(B(:),1)

Local Variance

Instead of finding variance for the whole matrix, variance is computed based on a small sliding window.

Steps to Perform:

MATLAB CODE:

I = imread('cameraman.tif');

figure,imagesc(I);colormap(gray);title('Original Image');

I = double(I);

%Define the window size

sz = 5;

mn=floor(sz/2);

%Preallocate the matrix

Output = zeros(size(I));

%Pad the matrix with zeros

I = padarray(I,[mnmn]);

for i=1:size(I,1)-mn*2

for j=1:size(I,2)-mn*2

tmp = I(i:i+(sz-1),j:j+(sz-1));

mu = mean(tmp(:));

        tmp2 = mean(tmp(:).^2);

Output(i,j)=tmp2 - mu.^2;

end

end

figure,imagesc(Output);colormap(gray);

Quick Implementation:

Check Edge detection using Local variance for a faster implementation code.