Revision [15760]
This is an old revision of RunLengthEncoding made by ToBo on 2013-03-14 20:17:30.
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).
1. RL-Encoder
I defined my own RLE to compress black and white bitmap images with long series of zeros and ones.
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
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
2. RL-Decoder
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
% 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
3. Test with an artifical seqence
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) '%'])
% 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!
4. Test with an image
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.
This image seems to be predestinated for run length encoeding as it has long sequences of 0 and 1.
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) '%'])
% 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.
Siehe auch