RLE Encoding

RLE – Run Length Encoding:

It is a famous lossless compression algorithm widely used in many data compression applications and used with many image compression algorithms. In Run Length Encoding method the consecutive same data is compressed. This technique used in few type of BMP image formats particularly 8 bit and 16 bit BMP images, JPEG images and almost all compression application software like winzip, winrar etc..

RLE – Run Length Encoding Example.

Input data : qqqqqqqqqqwwwrrrrqqqqqqqiiioooopppppp
RLE compressed Data : 10q3w4r7q3i4o6p

Let’s consider the above sample data, in RLE compression the count and the data value is represented. i.e q is repeated at 10 times instead of writing ten q it can be written as 10q. likewise all other data’s are written.

Compression ratio = (37 (total number of chars in input data) - 15 (required no of chars to represent the data) ) / 37 * 100
= 59.5 %

Compression ratio for above case is 59.5 %;

Input data : qwertyqwerty
RLE compressed Data : 1q1w1e1r1t1y1q1w1e1r1t1y

In the above sample the compression ratio is -100%. I.e. negative compression. From the above two example RLE compression is good only when the data is repeated one. Otherwise it would give negative compression.

Advantages :

1. During implementation just one pass is required to compress the input data.
2. Easy understanding.
3. Less memory requirement.
4. High compression ratio on repeated data input.

Disadvantages:

1. If the data is not repeated one then the compression ratio would be negative.

Read More

ARITHMETIC CODING

ARITHMETIC CODING:

In arithmetic coding, Input data is represented by an interval of real numbers between 0 and 1. As the input data is large, the interval required to represent is smaller, i.e. the number of bits required to specify the interval increases. Successive symbols of the input data reduce the size of the interval according with the symbol probabilities generated by the arithmetic encoding. The repeated symbols reduce the range by less than the unlikely symbols and hence add fewer bits to the input data. The range of input data is the entire interval zero to one (0, l), which denotes the half-open interval 0.5 <> 1

ARITHMETIC CODING Example:

The Fixed model (alphabet is (a, e, i, o, u,!)) is used with the following probabilities shown in the Table.

Let’s take the input data become eaii!. Initially, both encoder and decoder know that the range is (0, 1).

From first symbol, e, the encoder narrows it to [0.2, 04],
The second symbol, a, will narrow this new range to the first one-fifth of it. Like the following









Representation of the Arithmetic Coding Process:


Suppose the input data is like a, aa, aaa, aaaa, the encoded number will be 0.0. To solve this ambiguity, In data model each data ends with a special EOF symbol known to both encoder and decoder. In the above table ! would be the EOF.

The Entropy of eaii! Is
-log0.3 – log0.2 – log0.1 – log0.1 – log0.1
= - log0.00006 ≈ 4.22

Arithmetic Encoding Algorithm:

/* Call Encode_Data repeatedly for each symbol in the input data. */
/* Ensure that a distinguished "terminator" symbol is encoded last, then */
/* transmit any value in the range [low, high]. */

Encode_Data(symbol, cum-freq)
range = high - low
high = low + range*cum-freq [symbol-1]
low = low + range*cum-freq [symbol]

/* ARITHMETIC DECODING ALGORITHM. */
/* "Value" is the number that has been received. */
/* Continue calling Decode_Data until the terminator symbol is returned. */

Decode_Data(cum-freq)
find symbol such that
cum-freq[symbol] <= (value-low)/(high-low) <>

range = high - low

high = low + range*cum-freq[symbol-1]

low = low + range*cum-freq[symbol]

return symbol

Read More