Lets Learn together... Happy Reading

" Two roads diverged in a wood, and I,
I took the one less traveled by,
And that has made all the difference "-Robert Frost

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.

like button Like "IMAGE PROCESSING" page

Lossless Predictive coding - MATLAB CODE

A new pixel value is obtained by finding the difference between the current pixel and the predicted pixel value.

Encoding:


STEPS TO BE PERFORMED:








clear all
clc
%Read the input image
% A=imread('rice.png');
% figure,imshow(A);
% A=double(A);

A=[10 2 3 4;5 6 7 8];
display(A);
e=A;

%Perform prediction error
for i = 1:size(A,1)
    for j = 2:size(A,2)
        e(i,j)=e(i,j)-A(i,j-1);
    end
end
display(e);

%Huffman coding
C=reshape(e,[],1);
[D1,x]=hist(C,min(min(e)):max(max(e)));
sym=x(D1>0);
prob=D1(D1>0)/numel(e);
[dict,avglen] = huffmandict(sym,prob);
comp = huffmanenco(C,dict);


%Huffman Decoding
dsig = huffmandeco(comp,dict);
e=reshape(dsig,size(A,1),size(A,2));
d=e;


for i = 1:size(A,1)
    for j = 2:size(A,2)
        d(i,j)=d(i,j-1)+e(i,j);
    end
end

display(d);

%Decompressed Image
%figure,imshow(uint8(d));





2-D Prediction:
Consider an array [ a  b
                    c  d]
To perform prediction error using 2-D linear operator, e(2,2)=d-(c+b) i.e subtract the pixels left and top to the current pixel
To decompress, perform inverse operation f(2,2)=d+(c+b)

clear all
clc

%Input sequence
A=[10 11 12 13; 2 14 26 39];
display(A);

e=A;
A1=padarray(A,[1,0],0);

%Prediction error
for i = 2:size(A1,1)-1
    for j = 2:size(A1,2)
        fx=round(A1(i,j-1)+A1(i-1,j));
         e(i-1,j)=e(i-1,j)-fx;
    end
end
display(e);

%Huffman encoding
C=reshape(e,[],1);
[D1,x]=hist(C,min(min(e)):max(max(e)));
sym=x(D1>0);
prob=D1(D1>0)/numel(e);
[dict,avglen] = huffmandict(sym,prob);
comp = huffmanenco(C,dict);

%Huffman decoding
dsig = huffmandeco(comp,dict);
e=reshape(dsig,size(A,1),size(A,2));

%Inverse operation
d=e;
e1=padarray(e,[1,0],0);
for i = 2:size(e1,1)-1
    for j = 2:size(e1,2)
        fx=round(e1(i,j-1)+e1(i-1,j));
        d(i-1,j)=d(i-1,j)+fx;
        e1=padarray(d,[1,0],0);
    end
end

display(d);
  
A is the input value, e is the encoded value, d is the decoded value


like button Like "IMAGE PROCESSING" page

Run Length Encoding


Consider a matrix A with 15 elements,
A= [10 10 9 9 9 9 4 0 0 0 0 0 10 10 10]
In the given example,
10 has occurred 2 times, 9 has occurred 4 times, 4 has occurred once, 0 has occurred 5 times and 10 has occurred 3 times.
After Run length encoding, we obtain the matrix without any repetition in the adjacent elements, [10     9     4     0    10].  And the occurrences of each element [2     4     1     5     3]
Thus the matrix is reduced to 10 elements from 15 elements.
Let’s see how to code this reduction method.
Consider the above matrix A,
1.     Find the difference between adjacent elements. Use the function ‘diff(A)’ to find the difference. 
[0    -1     0     0     0    -5    -4     0     0     0     0    10     0     0]
2.     Convert it to logical format.  The elements without repetition are denoted with one and the repeated elements with zero.
 [0         0     0     0     1     1     0     0     0     0     1     0     0     1]
3.     Find the position of the elements that has the value one in the above step.
[2     6     7    12    15].
4.     Find the unique element values using the positions obtained from the above step. In the matrix A, the element at the position 2 is 10, the element at the position 6 is 9, the element at the position 7 is 4, the element at the position 12 is 0 and the element at the position 15 is 10.
[10     9     4     0    10]
5.     The first element in the matrix is 10, it has occurred 2 times. We obtained the occurrence of the first element alone from the matrix in the step 3. For the remaining elements, find the difference of the matrix in the step 3.
i.e. diff([2     6     7    12    15]); The result after concatenating the first element of the matrix obtained in step 3 with difference for the matrix in the step 3 is [2     4     1     5     3]
6.     Thus in the step 4 we obtain the elements without repetition,
[10     9     4     0    10] and the occurrences in step 5, [2     4     1     5     3].

MATLAB CODE:
A=[5 2 2 2 3 3 3 3 4 4 1 1 1 1 1 1 1 6 6 4 4]
F=[logical(diff(A)) 1];
In=find(F~=0);

Ele=A(In);

C=[In(1) diff(In)];

Result=zeros([numel(Ele) 2]);
Result(:,1)=Ele;
Result(:,2)=C;
display(Result);

SAMPLE OUTPUT:
Result =

     5     1
     2     3
     3     4
     4     2
     1     7
     6     2
     4     2
EXPLANATION:
5  has occurred 1 times, 2 has occurred 3 times, 3 has occurred 4 times, 4 has occurred 2 times, 1 has occurred 7 times, 6 has occurred 2 times and 4 has occurred 2 times.
like button Like "IMAGE PROCESSING" page
Next Post Home
Google ping Hypersmash.com