=====Run Length Encoding=====

Run Length Enoding (kurz RLE), German "Lauflängenkodierung" is used in image formats like pcx, bmp, jpeg and for FAX (ITU-recommendation T.4).

==a==RL-Encoder==a==

I defined my own RLE to compress black and white bitmap images with long series of zeros and ones.

%%(matlab;;rleCoder.m)
function [ c ] = rleCoder( s )

sa = 0; % Last bit
n = 0; % Count series of equal bits
c = []; % Output byte array
r = 0; % Byte array index


for k=1:length(s)
if (s(k) == sa)
n = n + 1;
if (n == 255)
r = r + 1;
c(r) = 0;
sa = s(k);
n = 0;
end
else
r = r + 1;
c(r) = n;
sa = s(k);
n = 1;
end
end
r = r + 1;
c(r) = n;
sa = s(k);
n = 1;


end
%%


==a==RL-Decoder==a==

%%(matlab;;rleDeoder.m)
function [ d ] = rleDecoder( c )

% Decoder
d = [];
sk = 1;
sa = 0;
if (c(1) == 0)
sa = 1;
sk = 2;
end

h1 = 1;
for k=sk:length(c)

if (c(k)>0)
for h=h1:(h1+c(k) - 1)
d(h) = sa;
end
h1 = h1 + c(k);
if (sa == 1)
sa = 0;
else
sa = 1;
end
else
for h=h1:(h1+255 - 1)
d(h) = sa;
end
h1 = h1 + 255;
end

end

end
%%


==a==Test with an artifical seqence==a==

%%(matlab)
clc

% Test sequence
s = [ ones(1, 5) zeros(1, 300) ones(1, 11) zeros(1, 1) ones(1, 7) zeros(1, 3) ];

% run length encoding
RLE = rleCoder(s);

disp(RLE)

% run length decoding
d = rleDecoder(RLE);

% Test
isequal(s,d)

% alculate compression ratio assuming byte storage
disp (['Copression ratio: ' num2str(round(length(RLE)/ceil(length(s)/8)*1000)/10) '%'])

%%

Result
%%
0 5 0 45 11 1 7 3


ans =

1

Copression ratio: 19.5%
%%


Decoder interpretation
||0|| First 0 -> start with a logical 1||
||5|| 5x ones ||
||0 ||255x nulls (a 0 within the stream meens 255x and keep the symbol)||
||45|| 45x nulls||
||11|| 11x ones ||
||1||1x null||
||7||7x ones||
||3||3x null||

The coded and decoded arrays are equal --> good

Copression ratio: 19.5% -> like it!



==a==Test with an image==a==

This is a real examle. I used this image for a embedded system (see project page [[RapidAccessTerminal RAT]]). I was lo0king for a basic compression for embedded systems. I dicided to implement my own RLE algorithm to convert bit streams to run-length-encoded byte streams.

||{{image url="images/TM.bmp" alt=""}}||

This image seems to be predestinated for run length encoeding as it has long sequences of 0 and 1.


%%(matlab)
clc

% Load image as a bit stream of zeros and ones
im = imread('TM.bmp');
[pheight, pwidth, temp] = size(im);
disp(['Image size: ' num2str(pwidth) 'x' num2str(pheight)])
k=1;
for y=1:pheight
for x=1:pwidth
s(k)=im(y,x);
k=k+1;
end
end

% run length encoding
RLE = rleCoder(s);

% alculate compression ratio assuming byte storage
disp (['Copression ratio: ' num2str(round(length(RLE)/ceil(length(s)/8)*1000)/10) '%'])
%%

Result

%%
Image size: 160x128

Copression ratio: 10%
%%


Copression ratio 10% ! --> works for me

Instead of 2560 byte using RLE this image can be stored in 257 byte of memory. This might be uninteresting on a PC or smart phone but on a small microcontroller it probably safes your programmer life.




==a==Other implementations==a==

http://sourceforge.net/projects/bmp2rle




---
Siehe auch {{backlinks}}