Introduction

Twenty-first century is the age of industrial automation with information

technology spinning in its top gear. This in turn brings a new responsibility
of effectively and efficiently utilizing the available computer resources like
memory in order to achieve the maximum benefit at minimum expense.
Image is the major stored item which occupies a large storage space in most
of the computer systems. Techniques of compression and decompression are
often adopted in as and when necessary for storage and retrieval of images.
So now a day’s special attention is given in developing efficient compression
and decompression techniques which are highly organized, efficient and
application specific.
For all the foresaid reasons we have selected the development of
IMAGE PRO, an elegant bitmap image compression and decompression
techniques our final year project.

1.1 Overview and scope of IMAGE PRO:

IMAGE PRO is an image compression and decompression technique
devised in order to effectively store and retrieve an image from computer’s
memory. It uses RLE (Run Length Encoding) which is a lossless
compression algorithm suitable for the purpose. By employing this
technique it is possible to compress a bitmap image by 80% (approx.) with
little color variation.

1.2 Definitions

1
1.2.1 Definition: Image

An image is a spatial representation of an object, a two-dimensional or three

dimensional scenes or another image. It can be real or virtual.
An image may be abstractly thought of as a continuous function defining
usually a rectangular region of a plane.
A recorded image may be in a photographic, analog video or digital format.
In computer version, an image is usually a recorded image such as a video
image, digital image or a picture. In computer graphics, an image is always a
digital image.
An image might be thought of as a function with resulting values of the light
intensity at each point over a planar region. For digital computer operations,
this function needs to sample at discrete intervals. The sampling quantizes
the intensity values intensity values into discrete levels.
A digital image is represented by a matrix of numeric values each
representing a quantized intensity value. When I is a two-dimensional
matrix, then I(r, c) is the intensity value at the position corresponding to row
r and column c of the matrix.

1.2.2 Definition: Pixel (Picture elements)

• The point at which an image is sampled is known as picture element,
commonly abbreviated as pixel.
• The picture values of intensity images are called gray scale levels.
The intensity at each pixel is represented by an integer and is
determined from the continuous image by averaging over a small
neighborhood around the pixel location. If there are just two intensity
values, for example black and white, they are represented by two
numbers 0 and 1; such images are called binary-valued images.
When 8-bit integers are used to store each pixel value, the gray levels
ranges from 0(black) to 255(white).
• There are many different graphics file formats that can be created
using various imaging programs, such as .bmp, .jpg, .gif, .tiff, etc.
However, understanding the internal structure of each image file
format is necessary when manipulating and downloading images to
OSRAM OLED display.

2
1.2.3 Definition: BMP (File Format)
• The Windows DIB (device Independent Bitmap or BMP) format is the
most common file format used with Windows. DIB files may be
monochrome, color-mapped with 16or 256 colors or they may be of
24 bit true colored. They may also be stored in either an
uncompressed format or with run length encoded (RLE) format. They
are rarely supported by software on other Operating system. So they
are not suitable for porting image between platforms.

• The objectives of this application note are to explain the fundamental

concepts of the Internal structure of a 24-bit, uncompressed bitmap
file and provide instructions on how to convert a bitmap file from 24-
bit to 4-bit that still retains its highest resolution possible along with
the C/C++ source code.

Internal Structure of a 24-bit Uncompressed Bitmap File:

Figure 1: Bitmap Pixel Properties

• Windows BMP Bitmap file are characterized by the number of pixels

and the color depth per pixel. The color depth of each pixel is always
the same in a file. Figure 1 demonstrates the properties of a bitmap
pixel, which consists of 24 bits in 3 contiguous bytes: 1 byte (8 bits)
for Red, 1 byte or Green, and 1 byte for Blue. When reading bitmap
data pixel information, designer has to first read the File Header, the
Image Header Information, and then the Bitmap Pixel Data.

3
1.2.4 Definition: Compression and Decompression:
• Image compression is the process of reducing the size of image files
by methods such as abbreviating repeated information or eliminating
information which is difficult for the human eye to detect.
• Compressed images require low bandwidth and can be transferred
quickly hence they are convenient and economic.
• Compression Techniques are of two types:
1. Lossless Compression Techniques: It reduces the storage space
required for an image without the loss of data i.e. it abbreviates the
repeated information. If an image has undergone lossless compression
then it is possible to get back the original image by decompression.
Typically it reduces the storage space by 50%.
2. Lossy Compression Techniques: It reduces the storage space
required by an image by eliminating the information that is difficult
for the human eye to detect. If an image has undergone lossy
compression then it is not possible to get back the original image
though the change will be imperceptible to the human eye. It has a
better compression ratio than lossless compression.
• The opposite process of compression is decompression.

4
 Different Types of Compression Techniques:

Entropy Encoding 1 Run length Encoding

2 Huffman Coding
3 Arithmetic Coding
Source Coding Prediction 1 DPCM
2 DM
Transformation 1 FFT
2 DCT
Layered Coding 1 Bit position
2 Sub sampling
3 Sub
band coding
Hybrid Coding 1 Vector Quantization
2 JPEG
3 MPEG
4 H.261
5 DVI RTV, DVI PLV

1.3 Model followed in developing IMAGE

PRO:
A system development is a birth to death process (i.e. lifecycle). A system
project begins (is born) with a decision to analyze user processing
requirements. The project ends or dies once usable software is produced,
implemented and released.
Several models have been proposed according to which the
development process should be performed in a systematic and disciplined
manner.
The system development lifecycle followed in developing this system
is Classical Waterfall Model.

5
1.3.1 Steps Involved:

1. Problem Identification.
2. Feasibility Study.
3. Requirement Analysis and Specification.
4. Design.
5. Coding and Unit Testing.
6. Integration and System Testing.
7. Maintenance.

6
Chapter2
Problem Identification
One of the most difficult tasks of system analysis is identifying the real
problems of the proposed or of the existing system.

Problems:
1. Large storage space is required for storing images especially of
higher resolutions.
2. Large bandwidth is required for sending uncompressed images over
any network (like LANs, WANs and Internet).

Expected Solutions:
1. The large sized images can be compressed and stored thus effectively
and efficiently utilizing the memory of the computing system.
2. The compressed image when required can be decompressed and
viewed.

7
Chapter3
Feasibility Study
Feasibility study helps to determine the possibility and probability of either
improving the existing system or developing completely a new system
nonexistent before.
IMAGE PRO is a brand new system which is being developed and
implemented.

3.1 Economic Feasibility:

One Time Cost:
No cost will be incurred in any of the stages of the system development as it
is developed as a final year project.

Recurring Cost:
Minimum will be incurred as recurring cost (for maintenance) as it can be
easily maintained by introducing the required changes in the user defined
header files.

3.2 Operational Feasibility:

1. The software package IMAGE PRO is extremely simple, user-
friendly and requires no special expertise on the part of the user apart
from his fundamental knowledge in computing.
2. The users of IMAGE PRO will find it easy to use as well as it will
cater all their requirements of image compression and
decompression.
3. The user can send the compressed image over any network (LANs,
WANs and Internet).

3.3 Technical Feasibility:

IMAGE PRO is absolutely technically feasible with the present equipment,
current procedures and existing software technology. The input, processing
and output of the different modules along with the operating environment
are stated in the functional requirement section.

8
Chapter4
Requirement Analysis and
Specification
The aim of requirement analysis and specification phase is to understand the
exact requirements of the customers and to document them properly.
IMAGE PRO is aimed to be used for the purpose of simple
compression and decompression of uncompressed BMP image. IMAGE
PRO will be used by end users on standalone PC. It must be able to
compress the uncompressed BMP images/primitive BMP images effectively
and efficiently for the purpose of storage and decompress them to get back
the original ones

4.1 Requirement Gathering and Analysis:

The goal of this phase is to collect all relevant information from the
customers by interviews and discussions regarding the product to be
developed with a view to clearly understand the customer’s requirements
and weeding out the anomalies, ambiguities, inconsistencies and
incompleteness in them.
The required information for developing IMAGE PRO is being taken
from our mentor Mr. Sujay Saha as well as from Internet including books on
Multimedia like Ralf Steinmetz and Klara Nahrstedt.

4.2 Requirement Specification:

The customer’s requirements identified during the previous phase are
organized and documented into System Requirement Specification
Document (SRS). The SRS is produced at the culmination of the analysis
task. The function and performance of the system are refined by the
complete information description. The introduction of the SRS states the
goals and objectives of the system.

9
4.2.1 System Requirement Specification (SRS):
4.2.1.1 Introduction:

• Background: We have taken up IMAGE PRO as our final year

project because image compression and decompression is of
significant importance in modern world where we try to exploit all
possible ways at our disposal for efficient and effective delivery and
storage of images. Image PRO is a smart, adaptive and user friendly
compression and decompression technique meant for bitmap images.

• Scope: IMAGE PRO can be applied for the bitmap of 24 bits and
generated by paint applications but its jurisdiction can be extended by
adding new features. Thus IMAGE PRO is flexible.

• References: The information necessary for the project have been

obtained from our mentor, Internet and the book on multimedia by
Ralf Steinmetz and Klara Nahrstedt.

• Assumptions: The image that is being provided as the input to

IMAGE PRO is always a bitmap image with maximum image
resolution 24bits and must be generated by paint applications.

• Environmental Characteristics: It is something which decides how

the s/w or the program should be developed. There are several of
factors on which the characteristics of the environment will depend
upon. They are viz., h/w, peripherals, and the category of the people
who will be using the s/w. Those factors in details are as follows:
Hardware: (Mandatory)
• Processor (Minimum of Pentium based processor).
• Main Memory (i.e., RAM, say) (Minimum of 16MB).
• Storage Device (can be considered as peripheral if it is
removable).

Peripheral: (Optional)
• Printer (required, if the user wants to take the printout of
the image. This is fully optional).

10
 • Removable Storage Device (for some disc-less computer,
or also for computers with the disc support, the user may
need to store the compressed as well as the decompressed
image in the removable drive, if the person wants to carry
the compressed data or the decompressed image with
self).
• Network (as mention earlier, the large image can be send
through the network by only sending the compressed
data, for the same, we need network connections).

People:
This s/w or the program package is developed with a simple
UI (Developed using C-graphics in most simply way) so
that, a novice with minimum knowledge to use the computer
can use this program, to compress and decompress image.

• Dependencies:
Minimum Hardware Requirements:
• Any Windows or MS DOS based Operating System
(Windows 98, Windows XP etc.).
• 16 bit processor (minimum).
• Minimum 8 MB RAM (Recommended 16 MB).
• Minimum 10MB free hard disk space.
• CD ROM Drive or Floppy Drive for installation of
IMAGE PRO.
• IMAGE PRO is portable and can be run from any
removable drive.
Software requirements:
• Language used: C.
• Compiler: Turbo C V3.0 with BGI graphics support.
• Input Image Format: bmp.

4.2.1.2 Goals of Implementation:

The goal of implementing IMAGEPRO is to efficiently and effectively
utilize the valuable computer resource, memory in order to store bulky data
like those of high-resolution images. A compressed image is not only
convenient for storage but also occupies lower bandwidth when transmitted
over a network.

11
4.2.1.3 Functional Requirements:

R1: Compress Original BMP Image:

Description: The COMPRESS function takes the input from the user as the
name of the original BMP image along with the appropriate path. It then
creates 2 empty files namely tmp_char.cpr and tmp_indx.cpr. It fetches the
ASCII values of each unrepeated pixel of the original BMP image and stores
them in the tmp_char.cpr file. It stores the position of a pixel and the
number of repetitions of a pixel in tmp_indx.cpr file.

R1.1: Compress:

Input: The name of the original BMP image with appropriate path.

Processing: It opens the file provide by the user as input and creating two
more empty files (tmp_char.cpr, tmp_indx.cpr).

Output: It transfers reference of the 3 files to the RLE function.

R1.2: Rle:
Input: The reference of the 3 files (the original BMP image, tmp_char.cpr,
tmp_indx.cpr).

Processing: It fetches the ASCII values of each unrepeated pixel of the

original BMP image and stores them in the tmp_char.cpr file. It stores the
position of a pixel and the number of repetitions of a pixel in tmp_indx.cpr
file.

Output: tmp_char.cpr, tmp_indx.cpr.

R2: Decompress the compressed BMP Image:

Description: It reads the position of the repeated pixels as well as the

number of repetitions from the tmp_indx.cpr and the corresponding
characters from tmp_char.cpr. It then restores the characters with their

12
repetitions in the proper order in the final BMP image file, finl_img.bmp.
this is the decompressed image.

R2.1: Decompress:

Input: It takes the 2 file pointers (tmp_indx.cpr, tmp_char.cpr) as input

from the system.

Processing: It opens the 2 files (tmp_indx.cpr, tmp_char.cpr) and creates a

3rd file finl_img.bmp as an empty file to store the decompressed image.

Output: It transfers reference to the 3 files (tmp_indx.cpr, tmp_char.cpr,

finl_img.bmp ) to the Rle_op function.

R2.2: Rle_op:

Input: It takes the reference to the 3 files (tmp_indx.cpr, tmp_char.cpr,

finl_img.bmp) as input.
Processing: It reads the position of the repeated pixels as well as the number
of repetitions from the tmp_indx.cpr and the corresponding characters from
tmp_char.cpr. It then restores the characters with their repetitions in the
proper order in the final BMP image file, finl_img.bmp. This is the
decompressed image.

Output: The reference to the file finl_img.bmp.

4.2.1.4 Nonfunctional Requirements (Software Quality

Requirements):

Maintainability:
IMAGE PRO is easy to maintain as it can be easily updated by simply
updating the user-defined header files.

13
Portability:
IMAGE PRO is easily portable from one platform to another by changing
certain commands and hence it can be easily made platform independent.

Usability:
IMAGE PRO is extremely user-friendly, simple and easy to use.

Reliability:
IMAGE PRO is not very reliable as it is implemented using a procedural
language and very basic implementation techniques.

Accuracy of result:

• Once an image is compressed, it cannot be viewed unless it is

decompressed as data contained in the compressed image is stored
in two different files:
TMP_CHAR.CPR
TMP_INDX.CPR
• Compression percentage is better for images with less color
variation.
• Images with 256-colors (maximum) can be compressed.
• Only bitmap images can be compressed.
• Decompressed image or the image before the compression cannot
be viewed using this application (IMAGE PRO).
• Installation of C compiler which supports BGI graphics is
necessary even if we run the exe file only.

Human Computer Interface:

IMAGE PRO has a simple GUI that uses Graphics in C.

System Implementation:
At Present it is meant to run under any Windows environment.

Revisions to the system functionalities:

IMAGE PRO is easily portable from one platform to another by changing
certain commands and hence it can be easily made platform independent. At
Present it is meant to run under any Windows environment.

14
Chapter5
Design
The goal of the design phase is to transform the requirements specified in
the SRS document into a structure that is suitable for implementation in
some programming language.

5.1 Algorithms required and their explanation:

Run Length Encoding (Compression):
It is the simplest form of lossless bitmap compression technique. Here
recurring pixels are stored as a single pixel following by a count value both
separated by a special character acting as a separator. Here the compression
ratio is highly variable and depends on the recurrence of the pixels.

Program code:

long int char_pt=1;

void rle(FILE *fp1,FILE *fp2,int *a,int size)

{
int temp,i,count=0,bin;
clrscr();
for(i=0;i<=size;i++)
{
if (count==0)
temp=a[i];

if (temp==a[i] && i<size)

count++;
else
{
if (i<size)
i--;
if (count>3)
{

15
 fprintf(fp2,"%ld %d\n",char_pt,count);
putc(temp,fp1);
char_pt++;
}
else
{
while((count--)>0)
{
putc(temp,fp1);
char_pt++;
}
}
Count=0;
}
}
}

Algorithm:

Public initializations: char_pt 0

Input: A, SIZE
Output: FP1, FP2
Description: Here we are taking array A and size of the array, SIZE as input,
and storing the output characters and indexes in the two file “tmp_char.cpr”
and “tmp_indx.cpr” represented by file pointers FP1 and FP2 respectively.
We are using a public variable char_pt as initialized it as 1 before caIMAGE
PROing the procedure RLE, to keep track on the positions of the characters
repeated.

RLE (FP1, FP2, A, SIZE)

1 for i 0 to SIZE
2 if count = 0
3 temp A[i]
4 if temp = A[i] and i < SIZE
5 count count + 1
6 else
7 if i > SIZE
8 i i–1

16
9 if count > 3
10 Values of char_pt and count are inserted into file pointed by FP2
respectively leaving a space between them.
11 Value of temp is inserted into the file pointed by FP1.
12 char_pt char_pt + 1
13 else
14 while count > 0
15 count count – 1
16 Value of temp is inserted into the file pointed by FP1.
17 char_pt char_pt + 1
18 count 0

Opposite of RLE (Decompression):

Algorithm:

Public Initialization: structure INDX

Long integer pos
Integer count
Input: FS1, FS2
Output: FD
Description: In this procedure we are taking “tmp_char.cpr” and
“tmp_indx.cpr” as input, represented using FS1 and FS2 respectively.
Decompressed image is saved in the output file “FINL_IMG.BMP”
represented by the FD. A derived data type was created using structure by
the name “INDX” and is used for creating a variable pt to store the position
of the repeated characters and number repetitions.

RLE_OP (FS1, FS2, FD)

1 i 1
2 while End of file pointed by FS2 is not reached.
3 Numerical value of long integer type is read from file pointed by
FS2 and stored in a structure variable “pt.pos”.
4 Numerical value of integer type is read from file pointed by FS2
and stored in a structure variable “pt.count”.

17
5 while i < pt.pos
6 A character a read from the file pointed by FS1 and inserted in
the file pointed by FD.
7 i i+1
8 A character is read from FS1 and stored in a variable tmp.
10 for j 0 to pt.count
11 Value of tmp is inserted into the file pointed by FD.
12 i i+1

5.2 Working Principle:

Compression: We are using two files (TMP_CHAR.CPR and

TMP_INDX.CPR) for keeping the information of the original image in
compressed form. TMP_CHAR.CPR is used to store data in the original
image. TMP_INDX.CPR is storing the positions where data in the
TMP_CHAR.CPR is repeated and the count which calculates the number of
times they are repeated. First of all, we are storing the data present in the
original image in a buffer (say array), then, we are applying RLE algorithm
to that buffer and from there we are reading the character and writing
position of the repeated characters and number of repetitions of the
characters in the TMP_INDX.CPR file. We are writing both the repeated and
unrepeated characters in the TMP_CHAR.CPR. For example, if we are
applying RLE of the following series of characters, then we will save it in
the following manner:

Characters: ABBBBBCCCAAAAAAASSAAAAA

File: TMP_CHAR.CPR: ABCCCASSA

File: TMP_INDX.CPR:

Position Repetition
-------- ---------
2 5
6 7
8 5

We are not considering the characters which are repeated 3times or less
to calculate their count and we are directly copying them in TMP_

18
CHAR.CPR file. It takes 4bytes to point the repeated characters, and to save
3 consecutive characters in the TMP_CHAR.CPR it will take 3bytes.

There is also another difference is our method of RLE implementation

from the actual RLE technique. In the actual RLE Compression, the above
series of characters are stored in a single file in the following format using a
special character
(Say '$'):-
A5$BCCC7$ASS5$A

In the actual RLE, the original file gets much more compressed than
in ours. Here we are not using any special character, instead we are using
two files, because, an image file uses all the 255 ASCII character as the
image information, so all the characters can appear as the image data, and it
will be difficult for us to distinguish the special characters from image data.

Decompression: Here we are first initializing a buffer (a temporary array of

size 2), to store the position and the count of the number of repetitions of the
next immediate character .When we finish writing the characters that many
number of times (count) in the output image file, we are coping the position
of the next character to be repeated and number of repetitions from the
TMP_INDX.CPR file, and wait for that position in the TMP_CHAR.CPR
file to come. Till that we write all the characters we come across, in the
output image file without repeating, and when we come to the position as in
the buffer, we write the character that many times in the output image file as
in the buffer. By this we can retrieve the original image in uncompressed
form.

19