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



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



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) '%'])


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
11x null
77x ones
33x 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 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) '%'])


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.




5. Other implementations

There are no comments on this page. [Add comment]

Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by WikkaWiki