Wiki source for RunLengthEncoding
=====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}}
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}}