Bord R.V., Segeda N.E., Atanova M.E.

Oles Honchar Dnipropetrovsk National University, Ukraine

SOFTWARE-CREATED BITMAP IMAGES CODING-DECODING PROJECT

Compressing of graphic information is one of the most important problems of modern science: despite the rapid computer memory resources growth, the memory required tosave many image files is very large. Therefore it is necessary to sacrifice completeness of the information (eg format jpeg), or spend a lot of memory resources. Of course, there are many professional archivators. But, in my opinion, it does not mean that the problem of archiving image files is solved and new ideas are no longer needed.

The research is dedicated to the creation of a program for fast encoding and decoding of BMP-files, which works on the algorithm «Smart Bitmap», developed during the work. It also includes a project, which aim is analysing of the encoding speed of BitMap images using the algorithm «Smart Bitmap».

The program consists of three sections "encoding BMP / decoding SBF files", "Encoding speed analysis" and "Program Information". The integrated section "encoding BMP / decoding SBF files" is intended to encode BitMap images to SBF files, saving their original quality, and to decode the received SBF files into the original BMP-files. The "Encoding speed analysis" is an independent module to provide users information of the maximum possible encoding speed of BMP-files on this PC, using the «Smart Bitmap» algorithm. The "Program Information" is a section where you can see samples of the algorithm.

The program was created in Delphi 7.

Now a little more details about the algorithm.

First of all, the program analyses the occurrence rate for each of the 256 elements and using that data, builds a rates table.

 After that, the program sorts that table in descending order of occurrence rate. 

Then, using the sorted table, 2 (or 4, depending on chosen encoding mode) binary tables are being created, which contain 12 (or 20, using 4 trees) elements, which occur most frequent (12 first elements of sorted rates table). 

After these actions, the program is ready to start encoding the BMP image.

Encoding part of program analyses every element of the BitMap image and encodes it: 

1) If 2 (4) binary trees contain that element:

1st bit set to 1, it indicates, that received element is being encoded.

2nd bit (or 2nd and 3rd, for «4 trees») set to number of binary tree, which contains this element.

Remaining 6 (or 5, for «4 trees») bits filled with element code in the tree, but only necessary amount of bits are used. For example, 3rd symbol is encoded with sequence of 3 bits: 110. 

Let’s examine an example:

Element 219 is contained in 2nd tree and it is 2nd element in this tree.

Initial sequence: 

11011011 

Encoded sequence: 

1110

2) If the trees don’t contain that element:

1st bit set to 0, it indicates, that received element isn’t being encoded. 

Remaining 8 bits are filled with initial element code. 

Let’s examine an example:

Element 136 isn’t contained in one of the binary trees.

Initial sequence: 

10001000 

Encoded sequence:

110001000

Saving encoded file

After encoding all elements of BitMap image, the user is offered to save encoded file with extension SBF2 (or SBF4 for «4 trees»). 

Encoded file contains:

1) Encoding type, chosen by the user.

2) Encoded element in consecutive order. 

Encoding types

Program Smart Bitmap Convertor offers user to choose one of three available encoding types: 

1) Encoding type «2 trees». Program creates 2 binary trees and encodes file, using these trees.

2) Encoding type «4 trees». Program creates 4 binary trees and encodes file, using these trees.

3) Automatic choice of the optimal encoding type. Program uses table of occurrence rates, sorted in descending order, to analyze estimated compressed file size, using both «2 trees» and «4 trees» encoding types. Then it compares these values and chooses optimal encoding type.

Table 1. BitMap images encoding results, with varying color depth, 

created programmatically by "Smart Bitmap" algorithm