METHOD AND SYSTEM FOR HIGHLY EFFECTIVE AND EFFICIENT LOSSLESS IMAGE COMPRESSION USING 2-DIMENSIONAL RUN LENGTH ENCODING
FIELD OF THE INVENTION
The present invention pertains to a method and system for a fast, compact and computationally non-intensive image compression technique.
BACKGROUND OF THE INVENTION
Data compression is the process of encoding information using fewer bits or other information-bearing units than an unencoded representation would use through use of specific encoding and consequently decoding schemes. The goal of data compression is to represent an information source such as a data file, a speech signal, an image, or a video signal as accurately as possible using the fewest number of bits. However, data encoded and compressed at source can only be interpreted at the destination if the receiver knows the related decoding method.
Compression is useful because it helps reduce the consumption of expensive resources such as disk space or transmission bandwidth. Hence, an efficient encoding and related decoding methodology is very essential for a good compression technique in order to achieve maximum and quick compression.
There are different kinds of data compression schemes one of which includes lossless data compression. Lossless compression algorithms usually exploit statistical redundancy in such a way as to represent the sender's data more concisely, but nevertheless perfectly. One of the advantages of lossless data compression is that it allows the exact original data to be reconstructed from the compressed data.
For each of these algorithms, a certain amount of processing time is required to compute the encoded image or to decode the compressed image. The efficiency of the compression technique can be judged in terms of time efficiency on the basis of the processing time it takes to be carried out and its and computational intensity. Also, the efficiency can be ascertained on the basis of memory consumption of a particular technique. The amount of space required for storing the information exclusively required

for that particular encoding and related decoding method can be taken into account while choosing an efficient compression methodology to compress an image.
Huffman coding technique is an important lossless data compression algorithm. The basic idea in Huffman coding is to assign short code words to those input blocks with high probabilities and long code words to those with low probabilities.
UK patent GB2333655 describes a method of encoding digital information of n rows and m columns which define a plurality of cells (n X m) each of which has a pixel value. A current cell is selected and the largest rectangle adjacent to the current cell and having the same pixel value as the current cell is determined. A code is generated representing the location of the current cell, its pixel value, and the dimensions of the rectangle. A new cell is selected as the current cell and the method is repeated. If the size of an area selected exceeds a predetermined limit, the area is subdivided into smaller areas automatically without having to specify the sizes of the smaller areas, these smaller areas then being coded individually. However, the cited document has weaknesses pertaining to the fact that it looks for rectangular shapes in an image which are unlikely to occur. This is because images, such as those taken by a digital camera have large colour variations. These variations may occur in patterns different from a rectangular shape or any other geometric shape. As a result, it is inappropriate to impose any predefined structure on intensity repetitions in an image.
WO patent WO2002052836 defines an image encoding apparatus which is configured to receive data defining respective colour values for pixels arranged in rows and columns to make up an image. The apparatus applies coding for the pixel colour values, suitably through run-length encoding to provide image compression. The apparatus is configured to encode images as either sequential rows or sequential columns of pixel data, depending on which direction requires less storage. A reconfiguration of the apparatus, as a decoder for such compressed images is also provided. However, the degree of compression that will be achieved using this technique will be less than that obtained by horizontal and vertical run length encoding of the present invention. This is because, the cited technique compresses the image only in the direction which requires fewer bits for storing the encoded image data and the instant invention compresses the image using both horizontal and vertical runs of pixels simultaneously.

WO patent WO20023084205 discloses a process and a system for compressing highly correlated image data. The system comprises means for capturing the image, means for converting to digital form, means for reshaping the data, means for encoding the repetitions, means for storing the compressed data and means for retrieving the data. The method comprises steps like capturing the image, converting into digital form, reshaping the data into matrix form, encoding the repetitions into a bit-plane index and stored data values, storing the compressed data in storage memory and retrieving the data for decompression. However, in the cited system the image data is assumed to be highly correlated such as that in grey-scale MRI images. Further, two flags are required for each pixel, one to indicate its horizontal repetition and one to indicate its vertical repetition in the cited method. In contrast, the present invention requires only two flags per run. Also, the present invention requires less processing time than the cited methodology for both the encoding and the decoding procedure. Added to that, the instant invention also requires less storage space than the cited.
OBJECTS AND SUMMARY OF THE INVENTION
It is an object of the instant invention to obviate the above drawbacks and provide a method and system for highly effective and efficient lossless image compression using 2-dimensional run length encoding.
It is an object of the instant invention to provide the user with a computationally non-intensive method for a fast and compact image compression technique comprising of an encoding procedure and a corresponding decoding procedure.
It is yet another object of the instant invention to provide the user with a system for a fast and compact image compression technique comprising of an encoder and a corresponding decoder.
To achieve the aforementioned objectives the invention provides a method for image compression using run length encoding of colour digital images that operates both in the horizontal as well as vertical dimensions. The invention has been designed for lossless image compression on low end, embedded processors which cannot handle

computationally intensive compression schemes. The instant invention works effectively when applied to both colour digital images as well as grey-level digital images.
The instant invention provides a computationally non-intensive method for a fast and compact image compression technique, comprising encoding the colored or gray-scale image to be compressed using two-dimensional run length encoding while storing said image and subsequently decoding the compressed image using the decoding technique corresponding to the encoding procedure used while presenting the said image.
The instant invention further provides an encoding procedure used in the above method that comprises receiving the image to be compressed represented in the form of RGB pixel data as input, separating the input data into R, G and B planes, computing the horizontal and vertical run of pixels with substantially the same intensity for each pixel in each of the planes in the input data, setting the run information for the pixels depending on the computed run for each pixel in the plane in the input data and finally providing or storing the computed coded image produced along with the run information.
The instant invention also provides a decoding procedure used in the above method that comprises receiving the compressed image code to be decoded along with the run information for said image as input, deciding the type of run by reading the current two bits from the bit array provided, retrieving the run information for the current pixel from the compressed image provided depending upon the run type, setting the pixel intensities of decoded image according to the run to compute the actual image for each plane and finally providing the final decoded image information for each plane for viewing the said image.
The instant invention further provides a system for a computationally non-intensive, fast and compact image compression technique, comprising an encoding means to accept the colored or gray-scale image to be compressed, encode it using two-dimensional run length encoding and output or store the compressed image and a decoding means to accept the compressed image encoded using the above encoding means, decode it using the corresponding decoding technique and present the original image.

The instant invention further provides an encoder used in the above system that comprises input means responsive to operator commands enabling an operator to enter input image data to be compressed, memory for storing the image data to be encoded in various formats during the encoding procedure, processor coupled to the input, output and the memory programmed to process and analyze the said input data and decode it, said processor including means configured to separating the input data into R, G and B planes, means configured to computing the horizontal and vertical run of pixels with the same intensity for each pixel in each of the planes in the input data, means configured to setting the run information for the pixels depending on the computed run for each pixel in the plane in the input data and means configured to writing the intensity of that pixel into the code being computed for said image and output means responsive to operator commands enabling an operator to display or provide the encoded data.
The instant invention further provides a decoder used in the above system that comprises input means responsive to operator commands enabling an operator to enter input encoded image data to be decompressed, memory for storing the compressed image data to be decoded in various formats during the decoding procedure, processor coupled to the input, output and the memory programmed to process and analyze the said input data and decode it, said processor including means configured to deciding the type of run by reading the current two bits from the bit array provided, means configured to retrieving the run information for the current pixel from the compressed image provided depending upon the run type and means configured to setting the pixel intensities of decoded image according to the run to compute the actual image for each plane and output means responsive to operator commands enabling an operator to display or provide the decompressed image.
BRIEF DESCRIPTION OF THE DRAWINGS
• FIG 1 illustrates a diagram related to the working of the invention described in
prior art application GB2333655
• FIG 1 illustrates a flowchart depicting the basic operation of the encoder
• FIG 2 illustrates a flowchart depicting the procedure involved in computing the
horizontal and vertical run of the pixels
• FIG 3 illustrates a flowchart depicting the basic operation of the decoder

DETAILED DESCRIPTION OF THE INVENTION
The present invention discloses a method for image compression using run length encoding of colour digital images that operates both in the horizontal as well as vertical dimensions. The invention has been designed for lossless image compression on low end, embedded processors which cannot handle computationally intensive compression schemes such as JPEG. It can be applied to colour as well as grey-level digital images. It offers fast image compression on low-end slow processors.
The invention comprises of an encoder and a decoder. The input to the encoder is the image to be compressed. The encoder outputs the compressed, coded image which is fed to the decoder when the image is to be viewed. The invention achieves higher compression than the standard one dimensional run length encoding.
FIG 2 illustrates a flowchart depicting the basic operation of the encoder described in the instant invention, the procedure involved in compressing the provided image wherein the compression technique provides lossless image compression.
In step 101, the input means receive the image to be compressed in the form of RGB pixel data. The image may be a coloured or a gray-scale digital image. This data is stored in the memory and is accessed from here while processing at different stages.
Next, in step 102, the processor analyzes the input data and separates it into R, G and B planes.
Further, in step 103, the processor computes and sets the horizontal and vertical run of pixels with the same intensity for the current pixel in the current plane. For this purpose, it selects each pixel one by one, and then searches for those pixels adjacent to the current pixel, that have the same intensity as the chosen one. A pixel may be repeated only horizontally, only vertically, horizontally and vertically or not be repeated at all.
A 2-bit binary code is used to indicate the type of run of the current pixel and the run information is stored accordingly. If the pixel repeats horizontally and vertically, the horizontal as well as vertical count of repeated pixels along with the intensity of the

current pixel are stored. If the pixel repeats only horizontally or vertically, only the horizontal or vertical along with the intensity is stored. The maximum length of horizontal and vertical counts is restricted so that they may be stored in a single byte.
Once a pixel has been counted in a horizontal or vertical run it is marked as accounted for, so that it is not counted in another run. The pixels are processed from left to right and from top to bottom.
Next, in step 104, the processor checks if the horizontal and vertical run has been computed for all pixels in the current plane.
If the horizontal and vertical run for all the pixels in the current plane has not been calculated, then the processor moves to the next unaccounted pixel in step 105.
If the horizontal and vertical run for al the pixels in the current plane has been calculated, then in step 106 the processor checks if the pixel run of all the planes has been calculated.
If not, then in step 107, the processor shifts to the next plane. For colour images with RGB or RGBA planes each plane is encoded separately in order to get maximum compression.
If it has been calculated, then in step 108, the encoded data is provided through the output means with the run information.
FIG 3 illustrates a flowchart depicting the procedure of computing the horizontal and vertical run of the pixels in the encoding procedure.
In the first step, step 201, the current pixel is checked to determine if it has been accounted for.
If it has not been accounted for, then in step 202, the system advances vertically to count the number of pixels having the same intensity as the current pixel.

Next, similarly in step 203, the system advances horizontally to count the number of pixels having the same intensity as the current pixel.
Further, in step 204 the above pixels counted horizontally and vertically are set as been accounted for.
Next, and also as a consequence of the current pixel already been accounted (determined in step 202), in step 205 it is checked if all the pixels have been accounted for.
If they have, then the procedure stops; else in step 306 the system advances to the next pixel.
FIG 4 illustrates a flowchart depicting the basic operation of the decoder described in the instant invention, the procedure involved in decompressing the provided image in its compressed form and providing the original image.
Firstly, in step 301, the system receives the encoded image and its run information from the user. This data is stored in the memory and accessed, processed and stored back at various stages in the decoding procedure.
Next, in step 302, the category of the run is decided by retrieving the 2-bit binary code in the current two bits in the bit array received as input.
Further, in step 303, the bit array is further read to interpret the run information for the current pixel based on the run type decided above. If the current run is horizontal and vertical the decoder reads three bytes which give the horizontal and vertical counts and the intensity of the pixel. If the run is horizontal / vertical, only two bytes providing the horizontal / vertical count and intensity are read. If the run corresponds to an unrepeated pixel only one byte providing the pixel intensity is read.
Next, in step 304, the read pixel intensities according to the run type are set for the number of pixels as read for each plane in order to form the image. The system keeps advancing in the bit array as the intensity for each pixel is set to account for each pixel in

each plane to form the complete image. The decoder stops when there are no more 2-bit codes left.
Finally, in step 306, the final decoded original image is provided to the user. The following is the algorithm for the encoder: ENCODER ALGORITHM:
Input: RGB pixel data of an mxn digital colour image.
1. Separate pixel data into R, G and B planes. The planes are represented as two
dimensional character arrays.
2. Initialise a one dimensional bit array, bit_arr, of size 2x3xmxn. Reset all bits. This
will be used to store information about the intensity runs. The actual size of this
array will be the total number of runs. This number may be less than the initalised
value.
3. Initialise an unsigned character array, output, to store the coded image.
4. Initialise bit count bit_ctr to 0
5. Initialise another bit array, plane_bit, of size mxn and reset all its bits.
6. For each plane P = R, G, B
a. For each row r of P
i. For each column c of r
1. If plane_bit(r,c)= 1
a. continue
2. Else
a. Initialise hrun and vrun to 1
b. Advance vertically and count vrun, the number of consecutive
pixels which have the same intensity as l(r, c).

c. Advance horizontally and count hrun, the number of consecutive
pixels which have the same intensity as l(r, c). Advance c by
hrun number of pixels.
d. lf vrun=1
i. If hrun=1
1. This type of run is indicated by the bit code 00. Increment
bit array counter twice
2. Write only the intensity l(r, c) to output,
ii. Else if hrun>1
1. This type of run is indicated by the bit code 10. Set the
first bit for this run and increment the bit array counter
once.
2. Write hrun and the intensity l(r, c) to output.
e. Else
i. If hrun =1
1. This type of run is indicated by the bit code 01. Increment
the bit array counter once and set the second bit for this
run.
2. Write vrun and the intensity l(r, c) to output,
ii. Else if hrun>1
1. This type of run is indicated by the bit code 11. Set the
first and second bits for this run.
2. Write hrun, vrun and the intensity l(r, c) to output.
iii. Set the bits in plane_bit corresponding to pixels in the
vertical run to indicate that they have already been accounted for.
Output: Coded image intensities in output and bit array

The following is the algorithm for the decoder:
DECODER ALGORlTHM:
Input: The coded image, img_code, and bit array, bit_arr.
1. Initialise three two-dimensional unsigned character arrays, of size mxn, to store
the pixel values for the R G and B planes.
2. Initialise a one dimensional bit array, plane_bit, of size mxn. This will be used to
indicate whether a pixel has been written or not. Reset all bits.
3. Set the current plane to R plane
4. Initialise a flag planejd to indicate which plane is being written. Set it to 0.
5. Initialise pixel location (j, k) to (0, 0) in the current plane.
6. While the bit array is not empty
a. Read two bits, b1 and b2, from the bit array
b. Determine the type of the run- if b1=0 & b2=0, type= 1, else if b1=0 & b2=1,
type=2, else if b1 = 1 & b2=0, type=3, else if b1=1 & b2=1, type=4
c. lf type=1
i. Read intensity from the img_code.
ii Set the intensity of the current pixel with this intensity
iii. Increment k once and adjust j if required
d. Else if type=2
i Read vrun and intensity from img_code
ii Set intensity of vrun pixels vertically from (j, k). Set the plane bit for these
pixels. iii. Increment k once and adjust j if required
e. Else if type=3
i. Read hrun and intensity from img_code

ii. Set intensity of hrun pixels horizontally from (j, k). Set plane_bit for these pixels. Advance (j, k) by hrun pixels.
f. Else if type=4
i. Read hrun, vrun and intensity from img_code
ii. Set intensity of hrun pixels horizontally from (j, k) and vrun pixels vertically. Set plane_bit for these pixels. Advance (j, k) by hrun pixels.
g. Check plane_bit for the next pixel location. Advance (j, k) as long as set
pixels are encountered.
h. If (j, k) = (m,n), if plane_id=0 set current plane as G plane. Set plane_id=1.
Set pixel location (j, k) = (0, 0). i. Else if plane_id=1, set current plane as B plane. Set plane_id=2. Set pixel
location (j, k) = (0, 0).
j. Else exit from while loop as all planes have been written
Output: Three R G B planes with decoded image intensities

We claim:
1. A computationally non-intensive method for a fast and compact image
compression technique, comprising the steps of:
encoding the colored or gray-scale image to be compressed using two-dimensional run length encoding while storing said image
decoding the compressed image using the decoding technique corresponding to the encoding procedure used while presenting the said image
2. An encoding procedure for a computationally non-intensive method for a fast and
compact image compression technique, comprising the steps of:
receiving the image to be compressed represented in the form of RGB pixel data as input
separating the input data into R, G and B planes
computing the horizontal and vertical run of pixels with substantially the same intensity for each pixel in each of the planes in the input data
setting the run information for the pixels depending on the computed run for each pixel in the plane in the input data
providing or storing the computed coded image produced along with the run information
3. A method as claimed in claim 1, wherein computing the horizontal and vertical
run of pixels comprises the steps of:
selecting each pixel of the image in succession
checking if it the said pixel has been accounted for
advancing to the next pixel, if said pixel has already been accounted for
advancing vertically to count the number of pixels having same intensity as said pixel, if said pixel has not been accounted for
advancing horizontally to count the number of pixels having same intensity as said pixel, if said pixel has not been accounted for
setting the pixels in the vertical and horizontal runs as been accounted for
4. A method as claimed in claim 1, wherein the intensity of each pixel is also noted
into the code being computed for the said image.
5. A decoding procedure for a computationally non-intensive method for a fast and
compact image compression technique, comprising the steps of:
receiving the compressed image code to be decoded along with the run information for said image as input
deciding the type of run by reading the current two bits from the bit array provided
retrieving the run information for the current pixel from the compressed image provided depending upon the run type
setting the pixel intensities of decoded image according to the run to compute the actual image for each plane
providing the final decoded image information for each plane for viewing the said image
6. A method as claimed in claim 1, wherein the image compression is performed
using run length encoding of digital images that operates both in the horizontal as
well as vertical dimensions.
7. A method as claimed in claim 1, wherein the image compression is performed on
low-end, embedded processors that cannot handle computationally intensive
compression schemes.
8. A method as claimed in claim 1, wherein a two-bit binary code is used to indicate
the type of run of the current pixel and run information is stored accordingly.
9. A method as claimed in claim 1, wherein the maximum length of horizontal and
vertical counts is restricted so that they may be stored in a single byte.
10. A method as claimed in claim 1, wherein the pixels are processed from left to
right and top to bottom till all pixels have been accounted for.
11. A system for a computationally non-intensive, fast and compact image
compression technique, comprising:
an encoding means to accept the colored or gray-scale image to be compressed, encode it using two-dimensional run length encoding and output or store the compressed image
a decoding means to accept the compressed image encoded using the above encoding means, decode it using the corresponding decoding technique and present the original image
12. An encoder for a computationally non-intensive method for a fast and compact
image compression technique, comprising:
input means responsive to operator commands enabling an operator to enter input image data to be compressed

memory for storing the image data to be encoded in various formats during the encoding procedure
processor coupled to the input, output and the memory programmed to process and analyze the said input data and decode it, said processor including means configured to separating the input data into R, G and B planes, means configured to computing the horizontal and vertical run of pixels with the same intensity for each pixel in each of the planes in the input data, means configured to setting the run information for the pixels depending on the computed run for each pixel in the plane in the input data and means configured to writing the intensity of that pixel into the code being computed for said image
output means responsive to operator commands enabling an operator to display or provide the encoded data
13. A decoder for a computationally non-intensive method for a fast and compact image compression technique, comprising:
input means responsive to operator commands enabling an operator to enter input encoded image data to be decompressed
memory for storing the compressed image data to be decoded in various formats during the decoding procedure
processor coupled to the input, output and the memory programmed to process and analyze the said input data and decode it, said processor including means configured to deciding the type of run by reading the current two bits from the bit array provided, means configured to retrieving the run information for the current pixel from the compressed image provided depending upon the run type and means configured to setting the pixel intensities of decoded image according to the run to compute the actual image for each plane
output means responsive to operator commands enabling an operator to display or provide the decompressed image
14. A system as claimed in claim 9, wherein the image being compressed is a
colored digital image.
15. A system as claimed in claim 9, wherein the image being compressed is a gray-
level digital image.
16. A system as claimed in claim 9, wherein lossless compression is performed on
the image.
17. A system as claimed in claim 9, for the color images with RGB or RGBA planes, each plane is encoded separately in order to get maximum compression.