lossy and lossless image compression using huffman encoding.docx

8









LOSSY AND LOSSLESS IMAGE
COMPRESSION USING HUFFMAN ALGORITHM



E.Cinthuriya B.Tech., ME (communication systems)










ABSTRACT

Image compression is an implementation of the data compression which encodes actual image with some bits. The purpose of the image compression is to decrease the redundancy and irrelevance of image data to be capable to record or send data in an effective form. Hence the image compression decreases the time of transmit in the network and raise the transmission speed. In Lossless technique of image compression, no data get lost while doing the compression.
To solve these types of issues various techniques for the image compression are used. Now questions like how to do image compression and second one is which types of technology is used, may be arises.
For this reason commonly two types' of approaches are explained called as lossless and the lossy image compression approaches. These techniques are easy in their applications and consume very little memory. An algorithm has also been applied to compress images by using the Huffman encoding techniques.












LIST OF CONTENTS
CHAPTER TITLE PAGE
NUMBER NUMBER
ABSTRACT i
LIST OF FIGURE ii
LIST OF TABLES iii
1 INTRODUCTION 01
1.1 INTRODUCTION 01
1.2 IMAGE 02
1.3 IMAGE COMPRESSION 02
1.4 WHY DO WE NEED COMPRESSION? 02
1.5 HOW AN IMAGE IS STORED? 03
1.6 BANDWIDTH AND TRANSMISSION 04
1.7 ADVANTAGES AND DISADVANTAGES OF IMAGE COMPRESSION 05

2 DIGITAL IMAGE COMPRESSION 06

2.1 DATA COMPRESSION AND DATA
REDUNDANCY 06

2.2 COMPRESSION METHODS 06
2.2.1 LOSSY COMPRESSION METHOD 07

2.2.2 LOSSLESS COMPRESSION METHOD 07

LIST OF CONTENTS
CHAPTER TITLE PAGE
NUMBER NUMBER
3 IMAGE FORMATS 11
3.1 INTRODUCTION 14

3.2 TYPES OF GRAPHICS FORMAT 14

3.2.1 RASTER GRAPHICS 14

3.2.2 VECTOR GRAPHICS 17

3.3 GRAPHICS INTERCHANGE FORMAT (GIF) 18
3.4 JPEG FILE FORMATS (JFIF AND SPIFF) 19
3.5 JPEG 2000(JP2) 20
3.5 PORTABLE NETWORK GRAPHICS (PNG) 21
3.6 TAGGED IMAGE FILE FORMAT (TIFF) 22
3.7 WINDOWS BITMAP (BMP) 23

4 PERFORMANCE CRITERIA FOR IMAGE COMPRESSION 26
4.1 MEAN SQUARED ERROR 26
4.1.1 BASIC DEFINISTION AND BASIC PROPERTIES 26
4.2 SIGNALS-TO-NOISE RATIO 32
4.3 PEAK SIGNAL-TO-NOISE RATIO 35

LIST OF CONTENTS
CHAPTER TITLE PAGE
NUMBER NUMBER

5 HUFFMAN CODING 38
5.1 HUFFMAN CODING 38
5.2 BUILDING A HUFFMAN TREE 38
5.3 CALCULATING BITS SAVED 41
5.4 HUFFMAN CODING IS AN OPTIMAL PREFIX CODE 42
5.5 THE HUFFMAN ALGORITHM 45

6 ALORITHM AND WORKING OF HUFFMAN CODING 46
6.1 ALORITHM AND WORKING OF HUFFMAN CODING 46
6.2 OUTPUT SNAPSHOTS 50
CONCLUSION 51
APPENDIX I
REFERENCES 69





LIST OF FIGURES
FIGURE NO TITLE PAGE NO
2.1 Lossy Image Compression 07
2.2 Lossless Image Compression 10
3.1 A Raster Image Comprises a Two-Dimensional
Grid of Pixels 15

3.2 Various Image Formats 25
4.1 Quality of Image by PSNR Values 37
6.1 Original Image 51
6.2 Compressed Image 55














LIST OF TABLES
TABLE NO TITLE PAGE NO
1.1 Download Time Comparison 04
3.1 Table of Image Formats 24





















CHAPTER - 1
INTRODUCTION
1.1 INTRODUCTION
Image compression is a type of an application for data/image compression in which the basic image gets encoded with the limited bits. To lower the irrelevance and the redundancy of image data is the major target of the image compression is to enable them to get saved or transmit the data in the better form. Image compression is the lowering of the image data size, also with maintaining the required details. The basic objective of the image compression is to show an image in small quantity of bits also the needed content of information is not lost within the actual image. Compression techniques are developed rapidly to compress huge files of data like images.
By the rapid growth of the technology a large quantity of image data should be managed to store those images in the proper manner by the use of effective techniques normally results in the compressing images. Some algorithms are there which are used to perform these types of compression in various manners like the lossless and the lossy. The image which is needs to be compressed is a gray scale having the pixel values ranges from 0 to 255.
Compression addressed to the decreasing the number of data to be used to show content of an image, file or the video without decreasing excessively quality of actual data. Also it lowers the quantity of the bits that is needed to save and send the digital media. To do compression of something implies that there is a piece of data whose size is forced to decrease. This technique may have various implementations and performs a vital role in the effective storage and transmission of the images.
The image compression targeted at decreasing the redundancy in the image data to record or sends only few numbers of the samples and by this also a good accession can be reconstruct for the actual image corresponding with the perception of human visual.
To compress images is the major target of this paper by decreasing the number of the bits on the basis of per pixel which is needed to show it and also to lower the time of transmission for the transmission of images and for reconstructing again by the Huffman encoding algorithm.
1.2 IMAGE
An image is a 2-D signal that is processed by human visual systems. These signals that are representing an image are commonly in the form of analog. Although for the storage, processing and the transmission through the computer applications, these signals needed to be converted from the analog form to their digital form. An image or a digital image is usually a 2-Dimensional array of the pixels. In the raw form, the images may cover a huge amount of the memory in the RAM and in the storage, both. Image compression is for reducing the redundancy and irrelevance of image/data to allow them to either store or transmit the data in a better way.
1.3 IMAGE COMPRESSION
Decreasing the irrelevance or redundancy of an image is the fundamental aim of the image compression techniques to provide the facility for storing and transmitting the data in an effective manner .The initial step in this technique is to convert the image from the representation of their spatial domain into a separate type of the representation by the use of few already known conversions and then encodes the converted values i.e., coefficients. This technique allows the huge compression of data as compared to the predictive techniques, though at the cost of the huge computational needs. Compression is obtained by eliminating any of one or more of the below three fundamental data redundancies
1. Coding redundancy: This is presented when the less than best (that is the smallest length) code words were used.
2. Inter-pixel redundancy: This results from the correlations between the pixels of and image.
3. Psycho-visual redundancy: This is because of the data which is neglected by human visual-system (that is, visually not required I information).
1.4 WHY DO WE NEED COMPRESSION?
Increased enough amount of the storage space.
Decrease the transmission time of an image to get sent on the internet or get downloaded from web pages.
Multimedia Applications: Desktop Editing
Image Archiving: Data from Satellite.
Image Transmission: Data from the web.
1.5 HOW AN IMAGE IS STORED?
Considering a black and white image, it can be assumed to be made up of many pixels of different shades of gray which have a number value corresponding to the brightness or darkness of the shade. Black is 0, white is 255, and all the numbers in between are shades of gray.
So, each pixel is coded as some integer from 0 to 255. To encode these integers are encoded using binary bit string. The maximum number of bits needed to code any number between 0 and 255 is 8.
Bits will appear in the following form using binary code: 0 0 0 0 0 0 0 0 This 8-bit representations will code integer 0. Similarly 11111111 will code integer 255. As we move from right to left in a string the significance of that bit becomes twice.
Thus the LSB holds a value ISSN: 2320-0790 COMPUSOFT, An international journal of advanced computer technology, 4 (4), April-2015 (Volume-IV, Issue-IV) 1586 20(=1), similarly the nest LSB holds a value 21(=2) and so on. Thus the MSB will hold a value 27(=128). So, the 8-bit representation of 153 would look likes this…
142 = 1 0 0 0 1 1 1 0
128 + 0 + 0 + 0 + 8 + 4 + 2 + 0 = 142
So, now we are able to encode these images using 8- bit representations of each pixel to code for a specific shade of gray. Now, once we have coded this image using this method, image compression is utilized in order to reduce the size of the image down so that fewer bits per pixel are used in the coding of the image.
The idea behind image compression is to use the fewest possible bits per pixel to code the image while still having a compressed image comparable to the original image. Image compression may be lossy or lossless.
1.6 BANDWIDTH AND TRANSMISSION
In our high stress, high productivity society, efficiency is key. Most people do not have the time or patience to wait for extended periods of time while an image is downloaded or retrieved.

In fact, it has been shown that the average person will only wait 20 seconds for an image to appear on a web page. Given the fact that the average Internet user still has a 28k or 56k modem, it is essential to keep image sizes under control.
Without some type of compression, most images would be too cumbersome and impractical for use. The following table is used to show the correlation between modem speeds and download time. Note that even high speed Internet users require over one second to download the image.

Modem Speed

Throughput – How Much Data Per Second
Download Time For a
40k Image
14.4k
1Kb
40 seconds
28.8k
2kB
20 seconds
33.6k
3kB
13.5 seconds
56k
5kB
8 seconds
256k DSL
32kB
1.25 seconds
1.5M T1
197kB
0.2 seconds

Table1.1: Download Time Comparison

1.5. ADVANTAGES AND DISADVANTAGES OF IMAGE COMPRESSION
ADVANTAGES:
Less disk space (more data in reality).
Faster writing and reading.
Faster file transfer.
Variable dynamic range.
Byte order independent.
DISADVANTAGES:
Added complication.
Effect of errors in transmission.
Slower for sophisticated methods (but simple methods can be faster for writing to disk).
Need to decompress all previous data.












CHAPTER – 2

DIGITAL IMAGE COMPRESSION

2.1 DATA COMPRESSION AND DATA REDUNDANCY

Data compression is defined as the process of encoding data using a representation that reduces the overall size of data. This reduction is possible when the original dataset contains some type of redundancy. Digital image compression is a field that studies methods for reducing the total number of bits required to represent an image.

This can be achieved by eliminating various types of redundancy that exist in the pixel values. In general, three basic redundancies exist in digital images that follow.

[a] Psycho-visual Redundancy:
It is a redundancy corresponding to different sensitivities to all image signals by human eyes. Therefore, eliminating some less relative important information in our visual processing may be acceptable.
[b] Inter-pixel Redundancy:
It is a redundancy corresponding to statistical dependencies among pixels, especially between neighboring pixels.
[c] Coding Redundancy:
The uncompressed image usually is coded with each pixel by a fixed length. For example, an image with 256 gray scales is represented by an array of 8-bit integers. Using some variable length code schemes such as Huffman coding and arithmetic coding may produce compression. There are different methods to deal with different kinds of aforementioned redundancies. As a result, an image compressor often uses a multi-step algorithm to reduce these redundancies.

2.2 COMPRESSION METHODS

During the past two decades, various compression methods have been developed to address major challenges faced by digital imaging. These compression methods can be classified broadly into lossy or lossless compression. Lossy compression can achieve a high compression ratio, 50:1 or higher, since it allows some acceptable degradation. Yet it cannot completely recover the original data. On the other hand, lossless compression can completely recover the original data but this reduces the compression ratio to around

In medical applications, lossless compression has been a requirement because it facilitates accurate diagnosis due to no degradation on the original image. Furthermore, there exist several legal and regulatory issues that favor lossless compression in medical applications.


2.2.1 LOSSY COMPRESSION METHODS

Generally most lossy compressors (Figure 2.1) are three-step algorithms, each of which is in accordance with three kinds of redundancy mentioned above.
The first stage is a transform to eliminate the inter-pixel redundancy to pack
information efficiently.





Then a quantizer is applied to remove psycho-visual redundancy to represent the packed information with as few bits as possible. The quantized bits are then efficiently encoded to get more compression from the coding redundancy.

[a] Quantization

Quantization is a many-to-one mapping that replaces a set of values with only one representative value. Scalar and vector quantization are two basic types of quantization. SQ (scalar quantization) performs many-to-one mapping on each value.
VQ (vector quantization) replaces each block of input pixels with the index of a vector in the codebook, which is close to the input vector by using some closenessmeasurements. The decoder simply receives each index and looks up the corresponding vector in the codebook. Shannon12 first showed that VQ would result in a lower bit rate than SQ. But VQ suffers from a lack of generality, since the codebook must be trained on some set of initial images.

As a result, the design of the codebook will directly affect the bit rate and distortion of the compression. Riskin et. al.5 presented variable-rate VQ design and applied it to MR images.Cosman et. al.13 used similar methods to compress CT and MR chest scans. Xuan et. al.14 also used similar VQ techniques to compress mammograms and brain MRI.

[b]Transform Coding

Transform coding is a general scheme for lossy image compression. It uses a reversible and linear transform to de correlate the original image into a set of coefficients in transform domain. The coefficients are then quantized and coded sequentially in transform domain.Numerous transforms are used in a variety of applications.

The discrete KLT (Karhunen-Loeve transform), which is based on the Hotelling transform, is optimal with its information packing properties, but usually not practical since it is difficult to compute. 15,16 The DFT (discrete Fourier transform) and DCT (discrete cosine transform) approximate the energy-packing efficiency of the KLT, and have more efficient implementation. In practice, DCT is used by most practical transform systems since the DFT coefficients require twice the storage space of the DCT coefficients.

[c] Block Transform Coding

Since the adoption of the JPEG standard, the algorithm has been the subject of considerable research. Collins et. al.20 studied the effects of a 10:1 lossy image compression scheme based on JPEG, with modifications to reduce the blocking artifacts. Baskurt et. al.21 used an algorithm similar to JPEG to compress mammograms with a bit rate as low as 0.27 bpp (bits per pixel) while retaining detection ability of pathologies by radiologists. Kostas et. al.22 used JPEG modified for use with 12-bit images and custom quantization tables to compress mammograms and chest radiographs.

Moreover, the ISO JPEG committee is currently developing a new still-image compression standard called JPEG-2000 for delivery to the marketplace by the end of the year 2000. The new JPEG-2000 standard is based upon wavelet decompositions combined with more powerful quantization and encoding strategies such as embedded quantization and context-based arithmetic.

It provides the potential for numerous advantages over the existing JPEG standard. Performance gains include improved compression efficiency at low bit rates for large images, while new functionalities include multi-resolution representation, scalability and embedded bit stream architecture, lossy to lossless progression, ROI (region of interest) coding, and a rich file format

[d] Full-Frame Transform Coding

To avoid the artifacts generated by block transforms, full-frame methods, in which the transform is applied to the whole image as a single block, have been investigated in medical imaging research.24-26 The tradeoff is the increased computational requirements and the appearance of ringing artifacts (a periodic pattern due to the quantization of high frequencies).Subband coding is one example among full-frame methods. It will produce a number of sub-images with specific properties such as a smoothed version of the original plus a set of images with the horizontal, vertical, and diagonal edges that are missing from the smoothed version according to different frequencies.27-29 Rompelman30 applied subband coding to compress 12-bit CT images at rates of 0.75 bpp and 0.625 bpp without significantly affecting diagnostic quality.
Recently, much research has been devoted to the DWT (discrete wavelet transform) for subband coding of images.

DWT is a hierarchical subband decomposition particularly suited to image compression.31 Many different wavelet functions can be applied to different applications.

In general, more complicated wavelet functions provide better performance. The wavelet transform can avoid the blocking artifacts presented in block transform methods and allow easy progressive coding due to its multiresolution nature.Bramble et. al. 32 used full-frame Fourier transform compression on 12 bpp digitized hand radiographs at average rates from about 0.75 bpp to 0.1 bpp with no significant degradation in diagnostic quality involving the detection of pathology characterized by a lack of sharpness in a bone edge.

However, Cook et. al.33 investigated the effects of full-frame DCT compression on low-contrast detection of chest lesions and found significant degradation at rates of about 0.75 bpp. These results illustrate that both imaging modality and the task play an important role in determining achievable compression.

2.2.2 LOSSLESS COMPRESSION METHODS

Lossless compressors (Figure 2.2) are usually two-step algorithms. The first step transforms the original image to some other format in which the inter-pixel redundancy is reduced. The second step uses an entropy encoder to remove the coding redundancy. The lossless decompressor is a perfect inverse process of the lossless compressor.




Typically, medical images can be compressed losslessly to about 50% of their original size. Boncelet et. al.34 investigated the use of three entropy coding methods for lossless compression with an application to digitized radiographs and found that a bit rate of about 4 to 5 bpp was best. Tavakoli35, 36 applied various lossless coding techniques to MR images and reported a compression down to about 5 to 6 bpp, with LZ (Lempel-Ziv) coding achieving the best results.
Lossless compression works best with decorrelated data. Roose et. al.5, 37 investigated prediction, linear transformation, and multiresolution methods for decorrelating medical image data before coding them. The compression result was 3:1 and less than 2:1 for angiograms and MRI respectively. Kuduvalli and Rangayyan6 studied similar techniques and found linear prediction and interpolation techniques gave the best results with similar compression ratios.
Here, we summarize the lossless compression methods into four categories.
[a] Run Length Coding
Run length coding replaces data by a (length, value) pair, where "value" is the repeated value and "length" is the number of repetitions. This technique is especially successful in compressing bi-level images since the occurrence of a long run of a value is rare in ordinary gray-scale images. A solution to this is to decompose the gray-scale image into bit planes and compress every bit-plane separately. Efficient run-length coding method38 is one of the variations of run length coding.
[b] Lossless Predictive Coding
Lossless predictive coding predicts the value of each pixel by using the values of its neighboring pixels. Therefore, every pixel is encoded with a prediction error rather than its original value. Typically, the errors are much smaller compared with the original value so that fewer bits are required to store them.
DPCM (differential pulse code modulation) is a predictive coding based losslessimage compression method. It is also the base for lossless JPEG compression.
A variation of the lossless predictive coding is the adaptive prediction that splits the image into blocks and computes the prediction coefficients independently for each block to achieve high prediction performance. It can also be combined with other methods to get a hybrid coding algorithm with higher performance.
[c] Entropy Coding
Entropy represents the minimum size of dataset necessary to convey a particular amount of information. Huffman coding, LZ (Lempel-Ziv) coding and arithmetic coding are the commonly used entropy coding schemes.
Huffman coding utilizes a variable length code in which short code words are
assigned to more common values or symbols in the data, and longer code words are assigned to less frequently occurring values. Modified Huffman coding40 and dynamic Huffman coding41are two examples among many variations of Huffman's technique.
LZ coding replaces repeated substrings in the input data with references to earlier instances of the strings. It often refers to two different approaches to dictionary-based compression: the LZ7742 and the LZ7843. LZ77 utilizes a sliding window to search for the substrings encountered before and then substitutes them by the (position, length) pair to point back to the existing substring. LZ78 dynamically constructs a dictionary from the input file and then replaces the substrings by the index in the dictionary. Several compression methods, among which LZW (Lempel-Ziv-Welch) is one of the most well known methods, have been developed based on these ideas. Variations of LZ coding are used in the Unix utilities Compress and Gzip.
Arithmetic coding45 represents a message as some finite intervals between 0 and 1 on the real number line. Basically, it divides the intervals between 0 and 1 into a number of smaller intervals corresponding to the probabilities of the message's symbols. Then the first input symbol selects an interval, which is further divided into smaller intervals. The next input symbol selects one of these intervals, and the procedure is repeated. As a result, the selected interval narrows with every symbol, and in the end,any number inside the final interval can be used to represent the message. That is to say, each bit in the output code refines the precision of the value of the input code in the interval.
A variation of arithmetic coding is the Q-coder46, developed by IBM in the late 1980's. Two references are provided for the latest Q-coder variation.
[d] Multiresolution Coding
` HINT (hierarchical interpolation)5, 37 is a multiresolution coding scheme based on sub-samplings. It starts with a low-resolution version of the original image, and interpolates the pixel values to successively generate higher resolutions. The errors between the interpolation values and the real values are stored, along with the initial low-resolution image.
Compression is achieved since both the low-resolution image and the error values can be stored with fewer bits than the original image. Laplacian Pyramid49 is another multiresolution image compression method developed by Burt and Adelson. It successively constructs lower resolution versions of the original image by down sampling so that the number of pixels decreases by a factor of two at each scale.
The differences between successive resolution versions together with the lowest resolution image are stored and utilized to perfectly reconstruct the original image. But it cannot achieve a high compression ratio because the number of data values is increased by 4/3 of the original image size. In general, the image is reversibly transformed into a group of different resolution sub-images in multire solution coding. Usually, it reduces the entropy of the image. Some kinds of tree representation could be used to get more compression by exploiting the tree structure of the multire solution methods.















CHAPTER - 3
IMAGE FORMATS
3.1 INTRODUCTION

This document is one in a series of guidance notes produced by The National Archives, giving general advice on issues relating to the preservation and management of electronic records. It is intended for use by anyone involved in the creation of electronic records that may need to be preserved over the long term, as well as by those responsible for preservation.

This guidance note provides advice on the general issues that should be considered by the creators and managers of electronic records when selecting file formats for use with images. Please note that The National Archives does not specify or require the use of any particular image file formats for records that are to be transferred. Choice of file format should always be determined by the functional requirements of the record-creating process. Record creators should be aware however, that long-term sustainability might well become a requirement, both for ongoing business purposes and archival preservation.

Advice on criteria for selecting file formats for long-term preservation is provided in Guidance Note 1 of this series. This chapter provides information about the most common graphics file formats in current use, with pointers to more detailed sources. Its aim is to enable data creators, managers and archivists to make informed decisions when selecting graphics file formats. Please note that the advice provided here is limited in scope to static images, and specifically does not include animation, video formats, Page Description Language or presentation file formats such as PostScript and Portable Document Format, which may include image data.

3.2 TYPES OF GRAPHICS FORMAT

Two distinct approaches exist for digitally encoding static images. These are known as raster and vector graphics. A further group of formats can store both raster and vector data within a single file, and are known as metafiles. A variety of file formats exist for encoding each type of image.

3.2.1 RASTER GRAPHICS

A raster image comprises a two-dimensional grid of pixels, each pixel having a specific colour value. A simple example is shown below

Figure 3.1 A raster image comprises a two-dimensional grid of pixels

The image data is usually stored as a series of scan-lines, each representing one row of the image grid. Each scan-line comprises sets of consecutive values representing the colour of each pixel in the row. These scan-lines may be stored contiguously within the file, or be aggregated into strips or tiles, which can speed up the decoding and decompression of the image. A number of issues need to be considered when using raster images

[a] Colour Depth

Colour depth describes the number of distinct colours that can be displayed by a single pixel within a raster image, and is a function of the number of bits allocated to each pixel.

For example, pixels described by a single bit can only display 2 colours (represented by 0 or 1), whereas pixels using 24 bits can display 224 (16,777,216) colours. The most common colour depths are as follows:
1-bit: Monochrome (2 colours)
4-bit: Greyscale or colour (16 colours)
8-bit: Greyscale or colour (256 colours)
16-bit: High Colour (65,536 colours)
24-bit: True Colour (16,777,216 colours)
32-bit: True Colour (4,294,967,296 colours)
True Colour is so-called because it corresponds approximately to the number of unique colours distinguishable by the human eye.

[b] Colour Spaces and Palettes

Colours are defined by specifying a number of values; the scheme that defines the nature of these values is referred to as a colour space. The most common colour space is RGB, which defines colours in terms of their red, green and blue components. Typically, each component is stored as one byte, having a range of possible values between 0 and 255. Any colour can therefore be specified as a combination of red, green and blue values.

example:
Colour
Red
Green
Blue
Black
0
0
0
White
255
255
255
Blue
0
0
255
Yellow
255
255
0

Note that yellow, is created by mixing red and green because RGB uses additive colours, i.e. those created by light rather than pigment. RGB is most commonly used for electronic display of graphics.
Subtractive (pigment) colours, as used most commonly in printing, are usually defined using the CMYK colour space. This specifies colours in terms of their cyan, magenta and yellow components (the K represents black, which is defined separately for convenience).
Another common colour space is HSV, which specifies colours through a combination of their hue, saturation and value. Like RGB, this uses an additive colour system. The colours of individual pixels may be stored within a file in one of three ways, depending upon the colour depth For 1-bit pixels, the colour is defined by either a 0 or 1, representing black or white. For colour depths up to 8-bits per pixel, indexed colours are generally used. Each pixel value refers to an entry in an index (otherwise known as a palette or look-up table), usually stored elsewhere in the file. The index relates these values to actual colour values for display.
This allows the image data to be stored more efficiently, since the real colour values need only be stored once, rather than for each pixel. It also allows the colours used by an 8-bit file to be selected from a palette of 16,777,216 colours, even though only 256 separate colours can be used within the image. With colour depths above 8-bits per pixel, colours are generally stored as literal values for each pixel (for example, as RGB values).
This is because any palette would be too large to represent a real saving inspace.

[c] Transparency
Raster images are normally opaque, but some formats allow regions of an image to be transparent. This is useful when overlaying images, or creating icons. This effect is usually achieved by allocating 8 bits per pixel to an alpha channel, which can be set to any level of transparency from 0 (opaque) to 256 (completely transparent). Transparency is only supported by certain image formats.
[d] Interlacing
Raster images are typically stored as a series of consecutive scan lines. However, image data can also be interlaced whereby the scan lines are stored out of sequence. In its simplest form, even rows might be stored first, followed by odd rows. The image would then be displayed in two passes, the first showing the even rows, and the second building up the complete image with the addition of the odd rows. Interlacing allows users to see an image before all the image data has been read, which can be helpful when the data is being downloaded from the Internet. It is only supported by certain file formats.

[e] Compression
Various compression algorithms may be employed to reduce the physical size of a file. Graphics compression techniques work by compressing the image information within a file, and are entirely distinct from file compression methods, such as WinZip, which compress the entire file bitstream.
Graphics compression algorithms fall into two categories:
Lossy compression (such as JPEG) achieves its effect at the cost of a loss in image quality, by removing some image information. Lossless compression techniques (such as CCITT Group 4) reduce size whilst preserving all of the original image information, and therefore without degrading the quality of the image.
3.2.2 Vector Graphics
Vector graphics formats store images as mathematical representations of image elements, such as shapes or lines. For example, a line segment might be defined in terms of the coordinates of its starting point, a direction, and a length. More complex shapes can be built up from simple shapes.
Enclosed shapes can also be filled with colours. Some vector formats support 3-D objects as well, such as wire frame models. Vector formats are most commonly used in the field of Computer-Aided Design (CAD), since they are ideally suited to the creation of architectural and engineering drawings, maps, schematics, and charts. They also form the basis for 3-D modelling and animation, although this is beyond the scope of this Guidance Note. Vector files can be easily manipulated, and rescaled without loss of quality.
The size of a vector file is proportional to the complexity of the image (unlike raster images). Vector files do not usually support compression. However, vector file sizes are typically far smaller than the equivalent raster image.
[a]Metafiles
A third category of file, known as a metafile, allows both raster and vector versions of an image to be stored within a single file. Metafiles are frequently developed to provide hardware/ software-independent methods of transferring image data. Use of metafiles tends to be limited to very specific applications. the following sections describe the most common file formats currently available in each category, including information about the developers, different versions of the format which may exist, the main features of the format, and sources of more detailed technical information.

3.3 GRAPHICS INTERCHANGE FORMAT (GIF)
The GIF format was developed in 1987 by CompuServe Incorporated, primarily for use on the Internet. The current version, GIF89a, was released in 1990. It supports colour depths from 1-bit (monochrome) to 8-bit (256 colours) and always stores images in compressed form, using lossless LZW compression. Other supported features include interlacing and transparency.
GIF is a proprietary format. In addition, the patent for the LZW algorithm is owned by Unisys Corporation, which has licensed its use by CompuServe. Despite the controversy that surrounded the application of license fees to GIF readers and writers and the developments of alternative open formats such as PNG the GIF format remains one of the most widespread in use, particularly on the Internet. The full technical specifications for GIF version 89a are available from CompuServe Incorporated
Benefits
Small file sizes makes these ideal for use on the web
Files can contain animation
Can support transparency
Can do small animation effects
'Lossless' quality–they contain the same amount of quality as the original, except of course it now only has 256 colors
Great for images with limited colors, or with flat regions of color
Negatives
Limited colours means it is not the best choice for photos
Does not support partial transparency like drop shadows
Only supports 256 colors
It's the oldest format in the web, having existed since 1989. It hasn't been updated since, and sometimes, the file size is larger than PNG.
3.4 JPEG FILE FORMATS (JFIF AND SPIFF)
JPEG itself is not a file format, but rather an image compression algorithm developed by the Joint Photographic Experts Group in 1990. The original specification did not describe a file format for data exchange. However, the Independent JPEG Group and C-Cube Microsystems developed a JPEG File Interchange Format (JFIF) in 1992, which has become a de facto standard; this is what is commonly referred to as the JPEG file format.
In 1996, Part 3 of the JPEG standard was released, containing the specification for an official file format, called SPIFF (Still Picture Interchange File Format). This is more complex than JFIF, and it also supports other compression schemes. It is designed to be interoperable with JFIF. The JPEG algorithm is also supported by a number of other raster image formats, including TIFF.
JFIF and SPIFF are 24-bit colour formats and use lossy compression, although a lossless extension to JPEG is also available (but not widely used). JPEG is particularly suited to the storage of complex colour images, such as photographs.
The arithmetic encoding extension of JPEG's patent expired in 2004. The full technical specifications for the current version of the JFIF specification (version 1.02) are freely available from the official JPEG website (www.jpeg.org) and from C-Cube Microsystems.
The full technical specifications for the SPIFF specification are freely available from the official JPEG website (www.jpeg.org ), as an extract from ISO/IEC 10918 Part 3.
Benefits
Small file sizes means more can be stored on a memory card
Quicker file transfer times, due to smaller file size
Negatives
Loss of quality due to image compression
Less opportunity for image manipulation in photo editing software

3.5 JPEG 2000 (JP2)
JPEG 2000 is a replacement for the JPEG algorithm, developed by the ISO JPEG group in 2000. The JPEG 2000 standard defines a minimum file interchange format (JP2), in a similar manner to JFIF and SPIFF. JPEG 2000 provides for lossy and lossless compression, and uses wavelet compression to achieve higher compression rates with a lower corresponding reduction in image quality. It supports colour depths up to 24-bit (true colour) and is best suited to complex colour images, such as photographs.
JPEG 2000 may utilise some patented technologies, but is intended to be made available on a license- and royalty-free basis. This format is supported in most modern image editing software tools, although it remains far less widely adoptedtheJPEG.
The full technical specifications for the core JPEG 2000 format have been published as an international standard (ISO/IEC 15444 Part 1).
Benefits
24-bit color, with up to 16 million colors
Rich colors, great for photographs that need fine attention to color detail
Most used and most widely accepted image format
Compatible in most OS (Mac, PC, Linux)
Negatives
They tend to discard a lot of data
After compression, JPEG tends to create artifacts
Cannot be animated
Does not support transparency

3.6 PORTABLE NETWORK GRAPHICS (PNG)
The Portable Network Graphics (PNG) format was developed by the PNG Development Group in 1996, to provide an open alternative to GIF and the associated licensing issues with LZW compression.
It supports colour depths from 1-bit to 48-bit. Image data is always stored compressed, using a variation on the lossless LZ77-based deflate compression algorithm which is not patented, and therefore free to use. Support for interlacing and transparency is also provided, and the format incorporates a number of error detection mechanisms.
The PNG specification is entirely public domain and free to use. It also has a very rich feature set. However, it has not yet achieved very wide scale adoption.
The full technical specifications for PNG 1.0 have been published as RFC-2083,
and as a W3C recommendation. Version 1.2 is intended to be released as an ISO
standard (ISO/IEC International Standard 15948).
Benefits
Lossless compression means good image quality, which isn't compromised when editing
The ability to maintain transparency, which is ideal for things like overlays or logos
Lossless, so it does not lose quality and detail after image compression
In a lot ways better then GIF. To start, PNG often creates smaller file sizes than GIF
Supports transparency better than GIF



Negatives
Not good for large images because they tend to generate a very large file, sometimes creating larger files than JPEG.
Unlike GIF however, it cannot be animated.
Not all web browsers can support PNG.
Quality will not be good enough for printing at any size

3.7 TAGGED IMAGE FILE FORMAT (TIFF)
The TIFF format was originally developed by the Aldus Corporation, and was intended primarily for use in scanning and desktop publishing. Aldus first published the specification in 1986. When Adobe Systems Incorporated purchased Aldus in 1994, they acquired the rights to the TIFF specification, and have maintained it since then. The current version of the specification (revision 6.0) was released in 1992.
TIFF supports colour depths from 1- bit to 24- bit (e.g. monochrome to true colour), and a wide range of compression types (RLE, LZW, CCITT Group 3 and Group 4, and JPEG), as well as uncompressed data. It should be noted that the implementation of JPEG compression described in Revision 6.0 is flawed: a revised design was issued as TIFF Technical Note #2, which should be followed instead. TIFF also incorporates perhaps the most comprehensive metadata support of any raster format, allowing the addition of a wide variety of technical and resource discovery information to be included. TIFF is designed to be an extensible format, and new tags can be registered with Adobe. A number of official and unofficial extensions exist, but should be treated with care since support may not be widespread.
Adobe owns the TIFF specification, but makes it freely available for use. The same licensing issues apply to the use of LZW compression in TIFF files as GIF (see 3.1). An unofficial TIFF extension has been developed using the same Deflate algorithm as the PNG format (see 3.5). However, this is not generally supported.

TIFF is one of the most flexible, popular and widely supported raster formats in use today.The full technical specification for TIFF revision 6.0 is freely available from the Adobe website (www.adobe.com).
Benefits
Ability to manipulate photos extensively in photo editing software
Option to print at the highest quality and at much larger sizes
Very flexible format, it supports several types of compression like JPEG, LZW, ZIP or no compression at all.
High quality image format, all color and data information are stored
TIFF format can now be saved with layers
Negatives
Much bigger file sizes (more storage needed)
Longer transfer and loading times due to file size
Very large file size–long transfer time, huge disk space consumption, and slow loading time.
3.8 WINDOWS BITMAP (BMP)
The bmp format (sometimes referred to as a device independent bitmap) was developed by microsoft as the native raster format of the windows operating system. Versions of the format have therefore coincided with releases of windows, the first version appearing in 1985 with windows 1.0. Additional versions were developed for use with ibm's os/2 operating system.
the bmp format supports colour depths from 1-bit to 32-bit and provides optional lossless rle compression (windows 3.0 versions and later only).although proprietary, this format is free to use and is widely supported, due to its association with windows. However, its popularity has declined in recent years with the advent of more advanced formats.
a formal technical specification for bmp has not been released by microsoft, although information may be available through the microsoft developers network knowledge base.
Benefits
Can be used for printing as images are saved in high quality format
Works well with most Windows programs and OS, you can use it as a Windows wallpaper

Negatives
Large file sizes means a lot of storage is required
Does not scale or compress well
Again, very huge image files making it not web friendly
No real advantage over other image formats



Table 3.1 table of image formats

Figure 3.2 various image formats



CHAPTER - 4
PERFORMANCE CRITERIA FOR IMAGE COMPRESSION
4.1 MEAN SQUARED ERROR
Mean squared error "Mean squared deviation" redirects here. It is not to be confused with Mean squared displacement. In statistics, the mean squared error (MSE) or mean squared deviation (MSD) of an estimator (of a procedure for estimating an unobserved quantity) measures the average of the squares of the errors or deviations—that is, the difference between the estimator and what is estimated. MSE is a risk function, corresponding to the expected value of the squared error loss or quadratic loss.
The difference occurs because of randomness or because the estimator doesn't account for information that could produce a more accurate estimate. The MSE is a measure of the quality of an estimator—it is always non-negative, and values closer to zero are better. The MSE is the second moment (about the origin) of the error, and thus incorporates both the variance of the estimator and its bias. For an unbiased estimator, the MSE is the variance of the estimator.
Like the variance, MSE has the same units of measurement as the square of the quantity being estimated. In an analogy to standard deviation, taking the square root of MSE yields the root-meansquare error or root-mean-square deviation (RMSE or RMSD), which has the same units as the quantity being estimated; for an unbiased estimator, the RMSE is the square root of the variance, known as the standard deviation.
4.1.1 DEFINITION AND BASIC PROPERTIES
The MSE assesses the quality of an estimator (i.e., a mathematical function mapping a sample of data to a parameter of the population from which the data is sampled) or a predictor (i.e., a function mapping arbitrary inputs to a sample of values of some random variable). Definition of an MSE differs according to whether one is describing an estimator or a predictor.



[a] Predictor
If Y ^ is a vector of n predictions, and Y is the vector of observed values corresponding to the inputs to the function which generated the predictions, then the MSE of the predictor can be estimated by

I.e., the MSE is the mean ( n 1 n i=1) of the square of the errors ( (Y ^i-Yi)2 ). This is an easily computable quantity for a particular sample (and hence is sample-dependent).
[b] Estimator
The MSE of an estimator θ ^ with respect to an unknown parameter θ is defined as
MSE(θ ^) = E[(θ ^- θ)2]
This definition depends on the unknown parameter, and the MSE in this sense is a property of an estimator. Since an MSE is an expectation, it is not technically a random variable. That being said, the MSE could be a function of unknown parameters, in which case any estimator of the MSE based on estimates of these parameters would be a function of the data and thus a random variable.
if the estimator is derived from a sample statistic and is used to estimate some population statistic, then the expectation is with respect to the sampling distribution of the sample statistic.
The MSE can be written as the sum of the variance of the estimator and the squared bias of the estimator, providing a useful way to calculate the MSE and implying that in the case of unbiased estimators, the MSE and variance
areequivalent.
MSE(θ ^) = Var(θ ^) + Bias(θ; θ ^ )2:



Proof of variance and bias relationship
MSE(θ^) = E [(θ^- θ)2]
= E [(θ^- E[θ^] + E[θ^] - θ)2]
= E [(θ^- E[θ^])2 + 2 (θ^- E[θ^]) (E[θ^] - θ) + (E[θ^] - θ)2]
= E [(θ^- E[θ^])2] + E [2 (θ^- E[θ^]) (E[θ^] - θ)] + E [(E[θ^] - θ)2]
= E [(θ^- E[θ^])2] + 2 (E[θ^] - θ) E [θ^- E[θ^]] + (E[θ^] - θ)2 E[θ^] - θ = const.
= E [(θ^- E[θ^])2] + 2 (E[θ^] - θ) (E[θ^] - E[θ^]) + (E[θ^] - θ)2 E[θ^] = const.
= E [(θ^- E[θ^])2] + (E[θ^] - θ)2
= Var(θ^) + Bias(θ; θ ^ )2
[c] Regression
In regression analysis, the term mean squared error is sometimes used to refer to the unbiased estimate of error variance: the residual sum of squares divided by the number of degrees of freedom. This definition for a known, computed quantity differs from the above definition for the computed MSE of a predictor in that a different denominator is used.
The denominator is the sample size reduced by the number of model parameters estimated from the same data, (n-p) for p regressors or (n-p-1) if an intercept is used.[3] For more details, see errors and residuals in statistics. Note that, although the MSE (as defined in the present article) is not an unbiased estimator of the error variance, it is consistent, given the consistency of the predictor.
Also in regression analysis, "mean squared error", often referred to as mean squared prediction error or "out-ofsample mean squared error", can refer to the mean value of the squared deviations of the predictions from the true values, over an out-of-sample test space, generated by a model estimated over a particular sample space. This also is a known, computed quantity, and it varies by sample and by out-of-sample test space.

[d] Mean
Suppose we have a random sample of size n from a population, X1; : : : ; Xn . Suppose the sample units were chosen with replacement. That is, the n units are selected one at a time, and previously selected units are still eligible for selection for all n draws.

The usual estimator for the mean is the sample average which has an expected value equal to the true mean μ (so it is unbiased) and a mean square error of MSE (X) = E [(X - µ)2] = (p σn )2 = σ n 2 where σ2 is the population variance.
For a Gaussian distribution this is the best unbiased estimator (that is, it has the lowest MSE among all unbiased estimators), but not, say, for a uniform distribution.
[e] Variance
Further information: Sample variance
The usual estimator for the variance is the corrected sample variance:

This is unbiased (its expected value is σ2 ), hence also called the unbiased sample variance, and its MSE

where µ4 is the fourth central moment of the distribution or population and γ2 = µ4/σ4 -3 is the excess kurtosis. However, one can use other estimators for σ2 which are proportional to Sn 2-1 , and an appropriate choice can always give a lower mean square error. If we define

then we calculate:

MSE(Sa 2) = E [(n - a 1Sn 2-1 - σ2)2]
= E [(n - a21)2 Sn 4-1 - 2 (n - a 1Sn 2-1) σ2 + σ4]
= (n - 1)2 a2 E [Sn 4-1] - 2 (n - a 1) E [Sn 2-1] σ2 + σ4
= (n - 1)2 a2 E [Sn 4-1] - 2 (n - a 1) σ4 + σ4 E [Sn 2-1] = σ2
= (n - 1)2 a2 (γ n 2 + n n + 1 - 1) σ4 - 2 (n - a 1) σ4 + σ4 E [Sn 4-1]
= MSE(Sn 2-1) σ4
=n - 1na2 ((n - 1)γ2 + n2 + n) σ4 - 2 (n - a 1) σ4 + σ4
This is minimized when


For a Gaussian distribution, where γ2 = 0 , this means the MSE is minimized when dividing the sum by a = n+ 1 . The minimum excess kurtosis is γ2 = -2 ,[lower-alpha 1] which is achieved by a Bernoulli distribution with p = ½ (a coin flip), and the MSE is minimized for a = n-1+ n 2 : So no matter what the kurtosis, we get a "better" estimate (in the sense of having a lower MSE) by scaling down the unbiased estimator a little bit; this is a simple example of a shrinkage estimator: one "shrinks" the estimator towards zero (scales down the unbiased estimator).
Further, while the corrected sample variance is the best unbiased estimator (minimum mean square error among unbiased estimators) of variance for Gaussian distributions, if the distribution is not Gaussian then even among unbiased estimators, the best unbiased estimator of the variance may not be
Sn 2-1
[f] Gaussian distribution
The following table gives several estimators of the true parameters of the population, μ and σ2, for the Gaussian case.



Note that:
1. The MSEs shown for the variance estimators assume
Xi N ( n (as measured by MSE): the MSE of S2 n-1 is larger than that of Sn 2+1 or Sn 2 .
2. Estimators with the smallest total variation may produce biased estimates: S2
n+1 typically underestimates σ2 by n 2 σ2
[g] Interpretation
An MSE of zero, meaning that the estimator θ^ predicts observations of the parameter θ with perfect accuracy, is the ideal, but is typically not possible.
Values of MSE may be used for comparative purposes.
Two or more statistical models may be compared using their MSEs as a measure of how well they explain a given set of observations: An unbiased estimator (estimated from a statistical model) with the smallest variance among all unbiased estimators is the best unbiased estimator or MVUE (Minimum Variance Unbiased Estimator).
Both linear regression techniques such as analysis of variance estimate the MSE as part of the analysis and use the estimated MSE to determine the statistical significance of the factors or predictors under study.
The goal of experimental design is to construct experiments in such a way that when the observations are analyzed, the MSE is close to zero relative to the magnitude of at least one of the estimated treatment effects.
MSE is also used in several stepwise regression techniques as part of the determination as to how many predictors from a candidate set to include in a model for a given set of observations.
[h] Applications
Minimizing MSE is a key criterion in selecting estimators: see minimum mean-square error.
Among unbiased estimators, minimizing the MSE is equivalent to minimizing the variance, and the estimator that does this is the minimum variance unbiased estimator. However, a biased estimator may have lower MSE; see estimator bias.
In statistical modelling the MSE, representing the difference between the actual observations and the observation values predicted by the model, is used to determine the extent to which the model fits the data and whether the removal or some explanatory variables, simplifying the model, is possible without significantly harming the model's predictive ability.
4.2 SIGNAL-TO-NOISE RATIO
The signal-to-noise ratio (SNR) is used in imaging as a physical measure of the sensitivity of a (digital or film) imaging system. Industry standards measure SNR in decibels (dB) of power and therefore apply the 10 log rule to the "pure" SNR ratio (a ratio of 1:1 yields 0 decibels, for instance). In turn, yielding the "sensitivity." Industry standards measure and define sensitivity in terms of the ISO film speed equivalent; SNR:32.04 dB = excellent image quality and SNR:20 dB = acceptable image quality.
[a] Definition of SNR
An operator arbitrarily defines a box area in the signal and background regions of a back-illuminated half moon or knife-edge test target. The data, (such as pixel intensity), is used to determine the average signal and background values.Traditionally,
SNR has been defined as the ratio of the average signal value µsig to the standard deviation σbg of the background:
SNR =µsig/σbg
However, when presented with a high-contrast scene,many imaging systems clamp the background to uniform black, forcing σbg to zero, artificially making the SNR infinite. In this case a better definition of SNR is the ratio of the average signal value µsig to the standard deviation of the signal σsig :
SNR = µsig/σsig
which gives a meaningful result in the presence of clamping.

4.2.1 Calculations
[a] Explanation
The line data is gathered from the arbitrarily defined signal and background regions and input into an array (refer to image to the right).
To calculate the average signal and background values, a second order polynomial is fitted to the array of line data and subtracted from the original array line data. This is done to remove any trends. Finding the mean of this data yields the average signal and background values. The net signal is calculated from the difference of the average signal and background values.
The RMS or root mean square noise is defined from the background region. Finally, SNR is determined as the ratio of the net signal to the RMS noise.
[b] Polynomial and coefficients
The second order polynomial is calculated by the following double summation.
i
f = output sequence
m = the polynomial order
x = the input sequence (array/line values)
from the signal region or background region,
respectively.
n = the number of lines
aj = the polynomial fit coefficients
The polynomial fit coefficients can thus be calculated by a system of equations.


Which can be written...


Computer software or rigorous row operations will solve for the coefficients.
[c] Net signal, signal, and background\
The second-order polynomial is subtracted from the original data to remove any trends and then averaged. This yields the signal and background values:

where
µsig = average signal value
µbkg = average background value
n = number of lines in background or signal region
Xi = value of the ith line in the signal region or background region, respectively.
fi = value of the ith output of the second order polynomial.
Hence, the net signal value is determined by :
signal = µsig - µbkg

[d] RMS noise and SNR The RMS Noise is defined as the square root of the mean of variances from the background region.





4.3 PEAK SIGNAL-TO-NOISE RATIO
Peak signal-to-noise ratio, often abbreviated PSNR, is an engineering term for the ratio between the maximum possible power of a signal and the power of corrupting noise that affects the fidelity of its representation.Because many signals have a very wide dynamic range, PSNR is usually expressed in terms of the logarithmic decibel scale.
PSNR is most commonly used to measure the quality of reconstruction of lossy compression codecs (e.g., for image compression). The signal in this case is the original data, and the noise is the error introduced by compression. When comparing compression codecs, PSNR is an approximation to human perception of reconstruction quality. Although a higher PSNR generally indicates that the reconstruction is of higher quality, in some cases it may not. One has to be extremely careful with the range of validity of this metric; it is only conclusively valid when it is used to compare results from the same codec (or codec type) and same content.
PSNR is most easily defined via the mean squared error (MSE). Given a noise-free m×n monochrome image I and its noisy approximation K, MSE is defined as:


Here, MAXI is the maximum possible pixel value of the image. When the pixels are represented using 8 bits per sample, this is 255. More generally, when samples are represented using linear PCM with B bits per sample, MAXI is 2B-1

For color images with three RGB values per pixel, the definition of PSNR is the same except the MSE is the sum over all squared value differences divided by image size and by three.
Alternately, for color images the image is converted to a different color space and PSNR is reported against each channel of that color space, e.g., YCbCr or HSL. Typical values for the PSNR in lossy image and video compression are between 30 and 50 dB, provided the bit depth is 8 bits, where higher is better.
For 16-bit data typical values for the PSNR are between 60 and 80 dB. Acceptable values for wireless transmission quality loss are considered to be about 20 dB to 25 dB. In the absence of noise, the two images I and K are identical, and thus the MSE is zero. In this case the PSNR is infinite (or undefined, see Division by zero).



Original uncompressed image Q=30, PSNR=36.81dB

Q=90, PSNR =45.53dB Q=10, PSNR=31.45db

Figure 4.1: Quality Of Image By PSNR Values










CHAPTER - 5
HUFFMAN CODING
5.1 HUFFMAN CODING
The idea behind Huffman coding is to find a way to compress the storage of data using variable length codes. Our standard model of storing data uses fixed length codes. For example, each character in a text file is stored using 8 bits. There are certain advantages to this system. When reading a file, we know to ALWAYS read 8 bits at a time to read a single character. But as you might imagine, this coding scheme is inefficient. The reason for this is that some characters are more frequently used than other characters. Let's say that the character 'e' is used 10 times more frequently than the character 'q'. It would then be advantageous for us to use a 7 bit code for e and a 9 bit code for q instead because that could shorten our overall message length. Huffman coding finds the optimal way to take advantage of varying character frequencies in a particular file. On average, using Huffman coding on standard files can shrink them anywhere from 10% to 30% depending to the character distribution. (The more skewed the distribution, the better Huffman coding will do.)The idea behind the coding is to give less frequent characters and groups of characters longer codes. Also, the coding is constructed in such a way that no two constructed codes are prefixes of each other. This property about the code is crucial with respect to easily deciphering the code.
5.2 BUILDING A HUFFMAN TREE
The easiest way to see how this algorithm works is to work through an example. Let's assume that after scanning a file we find the following character frequencies: Character Frequency
'a' 12
'b' 2
'c' 7
'd' 13
'e' 14
'f' 85
Now, create a binary tree for each character that also stores the frequency with which it occurs.
The algorithm is as follows: Find the two binary trees in the list that store minimum frequencies at their nodes. Connect these two nodes at a newly created common node that will store NO character but will store the sum of the frequencies of all the nodes connected below it. So our picture looks like follows:
9 12 'a' 13 'd' 14 'e' 85 'f'

2 'b' 7 'c'

Now, repeat this process until only one tree is left:
21

9 12 'a' 13 'd' 14 'e' 85 'f'

2 'b' 7 'c'

21 27

9 12 'a' 13 'd' 14 'e' 85 'f'

2 'b' 7 'c'





48

21 27

9 12 'a' 13 'd' 14 'e' 85 'f'

2 'b' 7 'c'


133

48 85 'f'

21 27

9 12 'a' 13 'd' 14 'e'

2 'b' 7 'c'


Once the tree is built, each leaf node corresponds to a letter with a code. To determine the code for a particular node, walk a standard search path from the root to the leaf node in question.
For each step to the left, append a 0 to the code and for each step right append a 1. Thus for the tree above we get the following codes:
Letter Code
'a' 001
'b' 0000
'c' 0001
'd' 010
'e' 011
'f' 1
Why are we guaranteed that one code is NOT the prefix of another?
Find a set of valid Huffman codes for a file with the given character frequencies:
Character Frequency
'a' 15
'b' 7
'c' 5
'd' 23
'e' 17
'f' 19
5.3 CALCULATING BITS SAVED
All we need to do for this calculation is figure out how many bits are originally used to store the data and subtract from that how many bits are used to store the data using the Huffman code.
In the first example given, since we have six characters, let's assume each is stored with a three bit code. Since there are 133 such characters, the total number of bits used is 3*133 = 399.
Now, using the Huffman coding frequencies we can calculate the new total number of bits used:
Letter Code Frequency Total Bits
'a' 001 12 36
'b' 0000 2 8
'c' 0001 7 28
'd' 010 13 39
'e' 011 14 42
'f' 1 85 85
Total 238

Thus, we saved 399 - 238 = 161 bits, or nearly 40% storage space. Of course there is a small detail we haven't taken into account here. What is that?
5.4 HUFFMAN CODING IS AN OPTIMAL PREFIX CODE
Of all prefix codes for a file, Huffman coding produces an optimal one. In all of our examples from class on Monday, we found that Huffman coding saved us a fair percentage of storage space. But, we can show that no other prefix code can do better than Huffman coding.
First, we will show the following:
Let x and y be two characters with the least frequencies in a file. Then there exists an optimal prefix code for C in which the codewords for x and y have the same length and differ only in the last bit.
Here is how we will prove this:
Assume that a tree T stores an optimal prefix code. Let and characters a and b be sibling nodes stored at the maximum depth of the tree. We will show that we can create T' with x and y as siblings at the lowest depth of the tree such that the number of bits used for the coding with T' is the same as with T. (Let f(a) denote the frequency of the character a. Without loss of generality, assume f(x) f(y) and f(a) f(b). It also follows that f(x) f(a) and f(y) f(b). Let h be the height of the tree T. Let x have a depth of dx in T and y have a depth of dx in T.)
Create T' as follows: swap the nodes storing a and x, and then swap the nodes storing b and y. Now, we have that the depth of x and y in T' is h, the depth of a is dx and the depth of b is dy in T'.
Now, let's calculate the change in the number of bits used for the coding with tree T' with the coding in tree T. (Note: Since all other codes remain unchanged, we only need to analyze the total number of bits it takes to code a, b, x and y.)
# bits for tree T (for a,b,x and y) = hf(a) + hf(b) + dxf(x) dyf(y)
# bits for tree T' (for a, b, x, and y) = dxf(a) + dyf(b) + hf(x) + hf(y).
Difference =hf(a) + hf(b) + dxf(x) dyf(y) - (dxf(a) + dyf(b) + hf(x) + hf(y))
= hf(a) + hf(b) + dxf(x) dyf(y) - dxf(a) - dyf*b) - hf(x) - hf(y)
= h(f(a) - f(x)) + h(f(b)-f(y)) + dx(f(x) - f(a)) + dy(f(y) - f(b))
=h(f(a) - f(x)) + h(f(b)-f(y)) - dx(f(a) - f(x)) - dy(f(b) - f(y))
= (h - dx)(f(a) - f(x)) + (h - dy)(f(b) - f(y))

Notice that all four of the terms above must be non-negative since we know that h dx, h dy, f(a) f(x), and f(b) f(y). Thus, it follows that this difference must be 0. Thus, the number of bits to used in a code where x and y (the two characters with lowest frequency) are siblings at maximum depth of the coding tree is optimal.
In layman's terms, give me what you think is an optimal coding tree, and I can create a new one from it with the two nodes corresponding to low frequencies at the bottom of the tree.
To complete the proof, you'll notice that by construction, Huffman coding ALWAYS makes sure that the nodes with the lowest frequencies are at the bottom of the coding tree, all the way through the construction.

5.5 THE HUFFMAN ALGORITHM
We are given an alphabet {ai} with frequencies 'f (ai)". We wish to find a set of binary codewords C ˘ 'c(a1), . . . , c(an)" such that the average number of bits used to represent the data is minimized:


Equivalently, if we represent our code as a tree T with leaf nodes a1, . . . ,an, then we want to minimize

where d(ai) is the depth of ai, which is also equal to the number of bits in the codeword for ai.
The following algorithm, due to Huffman, creates an optimal prefix tree for a given set of characters C ˘ {ai}. Actually, the Huffman code is optimal among all uniquely readable codes, though we don't show it here.




[a] Running time
Initially, we build a minqueue Q with n elements. Next, the main loop runs n ¡ 1 times, with each iteration consisting of two EXTRACT-MIN operations and one INSERT operation. Finally, we call EXTRACT-MIN one last time; at this point Q has only one element left. Thus, the running time for Q a binary min heap would be
If instead we use a van Emde Boas structure for Q, we achieve the running time










CHAPTER – 6
ALORITHM AND WORKING OF HUFFMAN CODING
6.1 ALORITHM AND WORKING OF HUFFMAN CODING
Following steps describes working and algorithm for Huffman coding.

1. Read a BMP image using image box control in Delphi language. The Image control can be used to display a graphical image - Icon (ICO), Bitmap (BMP), Metafile (WMF), GIF, JPEG, etc. This control will read an image and
convert them in a text file.

2. Call a function that will Sort or prioritize characters based on frequency count of each characters in file.

3. Call a function that will create an initial heap. Then re heap that tree according to occurrence of each node in the tree, lower the occurrence earlier it is attached in heap. Create a new node where the left child is the lowest in the sorted list and the right is the second lowest in the sorted list.

4 .Build Huffman code tree based on prioritized list. Chopoff those two elements in the sorted list as they are now part of one node and add the probabilities. The result is the probability for the new node.

5. Perform insertion sort on the list with the new node.

6. Repeat STEPS 3,4,5 UNTIL you only have 1 node left.

7. Perform a traversal of tree to generate code table. This will determine code for each element of tree in the following way. The code for each symbol may be obtained by tracing a path to the symbol from the root of the tree.
A 1 is assigned for a branch in one direction and a 0 is assigned for a branch in the other direction. For example a symbol which is reached by branching right twice, then left once may be represented by the pattern '110'.
8. Once a Huffman tree is built, Canonical Huffman codes, which require less information to rebuild, may be generated by the following steps:

Step 1. Remember the lengths of the codes resulting from a Huffman tree generated per above.

Step 2. Sort the symbols to be encoded by the lengths of their codes (use symbol value to break ties).

Step 3. Initialize the current code to all zeros and assign code values to symbols from longest to shortest code as follows:

A. If the current code length is greater than the length of the code for the current symbol, right shift off the extra bits.

B. Assign the code to the current symbol.

C. Increment the code value.

D. Get the symbol with the next longest code.

E.Repeat from A until all symbols are assigned codes.

9. Encoding Data- Once a Huffman code has been generated, data may be encoded simply by replacing each symbol with its code.

10. The original image is reconstructed i.e. decompression is done by using Huffman Decoding.

11. Generate a tree equivalent to the encoding tree. If you know the Huffman code for some encoded data, decoding may be accomplished by reading the encoded data one bit at a time. Once the bits read match a code for symbol, write out the symbol and start collecting bits again.

12. Read input character wise and left to the tree until last element is reached in the tree.

13 . Output the character encodes in the leaf and returns to the root, and continues the step 12 until all the codes of corresponding symbols is known.


Figure 6.1 Original Image Figure 6.2 Compressed Image









6.2 SNAP SHOT OF OUTPUT




COMPARISON OF DIFFERENT IMAGE TYPES


MSE
SNR
PSNR
BMP
193.606
13.3182
25.2958
TIFF
187.96
12.6205
25.424
PNG
195.695
13.5265
25.249
JPEG
188.065
25.4882
25.4882



CONCLUSION

Thus the compression is a theme which gains much significance and it can be used in many applications. This thesis presents the lossy and lossless image compression on different file format of images. Many different types of methods have been assessed in account of quantity of compression that they offer effectiveness of the method used and the sensitivity of error. The effectiveness of the method used and the sensitivity to error are sovereign of the feature of the group of source.
The level of the compression attained greatly depends on the source file. It is terminated that the higher data redundancy favors to reach more compressed image. The proposed method has the advantage of Huffman encoding algorithm the major goal is to reduce the computational time and minimize the space occupancy. The tests were carried on the different types of image sets and their results were assessed by the clarity and then by bits per pixel. The demonstrational rating gives that the proposed method has improvement while comparing with other conventional methods.













APPENDIX I
MATLAB CODINGS
function varargout = LOSSY_LOSSLESS(varargin)
% LOSSY_LOSSLESS MATLAB code for LOSSY_LOSSLESS.fig
% LOSSY_LOSSLESS, by itself, creates a new LOSSY_LOSSLESS or raises the existing
% singleton*.
%
% H = LOSSY_LOSSLESS returns the handle to a new LOSSY_LOSSLESS or the handle to
% the existing singleton*.
%
% LOSSY_LOSSLESS('CALLBACK',hObject,eventData,handles,...) calls the local
% function named CALLBACK in LOSSY_LOSSLESS.M with the given input arguments.
%
% LOSSY_LOSSLESS('Property','Value',...) creates a new LOSSY_LOSSLESS or raises the
% existing singleton*. Starting from the left, property value pairs are
% applied to the GUI before LOSSY_LOSSLESS_OpeningFcn gets called. An
% unrecognized property name or invalid value makes property application
% stop. All inputs are passed to LOSSY_LOSSLESS_OpeningFcn via varargin.
%
% *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one
% instance to run (singleton)".
%
% See also: GUIDE, GUIDATA, GUIHANDLES

% Edit the above text to modify the response to help LOSSY_LOSSLESS

% Last Modified by GUIDE v2.5 28-Apr-2016 19:54:48

% Begin initialization code - DO NOT EDIT
gui_Singleton = 1;
gui_State = struct('gui_Name', mfilename, ...
'gui_Singleton', gui_Singleton, ...
'gui_OpeningFcn', @LOSSY_LOSSLESS_OpeningFcn, ...
'gui_OutputFcn', @LOSSY_LOSSLESS_OutputFcn, ...
'gui_LayoutFcn', [] , ...
'gui_Callback', []);
if nargin && ischar(varargin{1})
gui_State.gui_Callback = str2func(varargin{1});
end

if nargout
[varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
else
gui_mainfcn(gui_State, varargin{:});
end
% End initialization code - DO NOT EDIT


% --- Executes just before LOSSY_LOSSLESS is made visible.
function LOSSY_LOSSLESS_OpeningFcn(hObject, eventdata, handles, varargin)
% This function has no output args, see OutputFcn.
% hObject handle to figure
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% varargin command line arguments to LOSSY_LOSSLESS (see VARARGIN)

% Choose default command line output for LOSSY_LOSSLESS
handles.output = hObject;

% Update handles structure
guidata(hObject, handles);

% UIWAIT makes LOSSY_LOSSLESS wait for user response (see UIRESUME)
% uiwait(handles.figure1);


% --- Outputs from this function are returned to the command line.
function varargout = LOSSY_LOSSLESS_OutputFcn(hObject, eventdata, handles)
% varargout cell array for returning output args (see VARARGOUT);
% hObject handle to figure
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Get default command line output from handles structure
varargout{1} = handles.output;


% --- Executes on button press in pushbutton6.
function pushbutton6_Callback(hObject, eventdata, handles)
% hObject handle to pushbutton6 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
fname=uigetfile('*.png');
I=imread(fname);
I=imresize(I,[128 128]);
axes(handles.axes24),imshow(I);title('Original Image');drawnow;
tic;
s=qtdecomp(I,0.2,[2 64]);

[i,j,blksz] = find(s);
blkcount=length(i);
avg=zeros(blkcount,1);
for k=1:blkcount
avg(k)=mean2(I(i(k):i(k)+blksz(k)-1,j(k):j(k)+blksz(k)-1));

end
avg=uint8(avg);
axes(handles.axes23),imshow((full(s)));title('Compressed image');drawnow;

i(end+1)=0;j(end+1)=0;blksz(end+1)=0;
data=[i;j;blksz;avg];
data=single(data);
symbols= unique(data);
counts = hist(data(:), symbols);
p = counts./ sum(counts);
sp=round(p*1000);
dict = huffmandict(symbols,p');
comp = huffmanenco(data,dict);
t=toc;
fprintf('Time taken for compression = %f seconds\n',t);
bits_in_original=8*256*256;
bits_in_final=length(comp)+8*length(symbols)+8*length(sp);
CR= bits_in_original/bits_in_final;
fprintf('compression ratio= %f\n',CR);
tic;
datanew = huffmandeco(comp,dict);
zeroindx=find(data==0);
inew=datanew(1:zeroindx(1)-1);
jnew=datanew(zeroindx(1)+1:zeroindx(2)-1);
blksznew=datanew(zeroindx(2)+1:zeroindx(3)-1);
avgnew=datanew(zeroindx(3)+1:end);
avgnew=uint8(avgnew);
for k=1:blkcount
outim(inew(k):inew(k)+blksznew(k)-1,jnew(k):jnew(k)+blksznew(k)-1)=avgnew(k);
end
axes(handles.axes22),imshow(outim);title('Decompressed Image');drawnow;
%figure,imshow(outim);title('Decompressed Image');drawnow;
t=toc;
fprintf('Time taken for Decompression = %f seconds\n',t);
hpsnr = vision.PSNR;
psnr = step(hpsnr, I,outim);
%fprintf('PSNR= %f\n',psnr);
[rows columns] = size(I);
set(gcf, 'Position', get(0,'Screensize'));
noisyImage = imnoise(I, 'gaussian', 0, 0.003);
squaredErrorImage = (double(I) - double(noisyImage)) .^ 2;
mse = sum(sum(squaredErrorImage)) / (rows * columns);
PSNR = 10 * log10( 256^2 / mse);
img=I;
img=double(img(:));
ima=max(img(:));
imi=min(img(:));
ims=std(img(:));
snr=20*log10((ima-imi)./ims);
set(handles.edit18,'String',PSNR)
set(handles.edit17,'String',snr)
set(handles.edit16,'String',mse)
guidata(hObject,handles);


% --- Executes on button press in pushbutton1.
function pushbutton1_Callback(hObject, eventdata, handles)
% hObject handle to pushbutton1 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
fname=uigetfile('*.bmp');
I=imread(fname);
I=imresize(I,[128 128]);
axes(handles.axes1),imshow(I);title('Original Image');drawnow;
tic;
s=qtdecomp(I,0.2,[2 64]);

[i,j,blksz] = find(s);
blkcount=length(i);
avg=zeros(blkcount,1);
for k=1:blkcount
avg(k)=mean2(I(i(k):i(k)+blksz(k)-1,j(k):j(k)+blksz(k)-1));

end
avg=uint8(avg);
axes(handles.axes2),imshow((full(s)));title('Compressed image');drawnow;

i(end+1)=0;j(end+1)=0;blksz(end+1)=0;
data=[i;j;blksz;avg];
data=single(data);
symbols= unique(data);
counts = hist(data(:), symbols);
p = counts./ sum(counts);
sp=round(p*1000);
dict = huffmandict(symbols,p');
comp = huffmanenco(data,dict);
t=toc;
fprintf('Time taken for compression = %f seconds\n',t);
bits_in_original=8*256*256;
bits_in_final=length(comp)+8*length(symbols)+8*length(sp);
CR= bits_in_original/bits_in_final;
fprintf('compression ratio= %f\n',CR);
tic;
datanew = huffmandeco(comp,dict);
zeroindx=find(data==0);
inew=datanew(1:zeroindx(1)-1);
jnew=datanew(zeroindx(1)+1:zeroindx(2)-1);
blksznew=datanew(zeroindx(2)+1:zeroindx(3)-1);
avgnew=datanew(zeroindx(3)+1:end);
avgnew=uint8(avgnew);
for k=1:blkcount
outim(inew(k):inew(k)+blksznew(k)-1,jnew(k):jnew(k)+blksznew(k)-1)=avgnew(k);
end
axes(handles.axes3),imshow(outim);title('Decompressed Image');drawnow;
%figure,imshow(outim);title('Decompressed Image');drawnow;
t=toc;
fprintf('Time taken for Decompression = %f seconds\n',t);
hpsnr = vision.PSNR;
psnr = step(hpsnr, I,outim);
%fprintf('PSNR= %f\n',psnr);
[rows columns] = size(I);
set(gcf, 'Position', get(0,'Screensize'));
noisyImage = imnoise(I, 'gaussian', 0, 0.003);
squaredErrorImage = (double(I) - double(noisyImage)) .^ 2;
mse = sum(sum(squaredErrorImage)) / (rows * columns);
PSNR = 10 * log10( 256^2 / mse);
img=I;
img=double(img(:));
ima=max(img(:));
imi=min(img(:));
ims=std(img(:));
snr=20*log10((ima-imi)./ims);
set(handles.edit1,'String',PSNR)
set(handles.edit2,'String',snr)
set(handles.edit3,'String',mse)
guidata(hObject,handles);


function edit18_Callback(hObject, eventdata, handles)
% hObject handle to edit18 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit18 as text
% str2double(get(hObject,'String')) returns contents of edit18 as a double


% --- Executes during object creation, after setting all properties.
function edit18_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit18 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit17_Callback(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit17 as text
% str2double(get(hObject,'String')) returns contents of edit17 as a double
% --- Executes during object creation, after setting all properties.
function edit17_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit16_Callback(hObject, eventdata, handles)
% hObject handle to edit16 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit16 as text
% str2double(get(hObject,'String')) returns contents of edit16 as a double


% --- Executes during object creation, after setting all properties.
function edit16_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit16 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
% --- Executes on button press in pushbutton5.
function pushbutton5_Callback(hObject, eventdata, handles)
% hObject handle to pushbutton5 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
fname=uigetfile('*.jpg');
I=imread(fname);
I=imresize(I,[128 128]);
axes(handles.axes20),imshow(I);title('Original Image');drawnow;
tic;
s=qtdecomp(I,0.2,[2 64]);

[i,j,blksz] = find(s);
blkcount=length(i);
avg=zeros(blkcount,1);
for k=1:blkcount
avg(k)=mean2(I(i(k):i(k)+blksz(k)-1,j(k):j(k)+blksz(k)-1));

end
avg=uint8(avg);
axes(handles.axes19),imshow((full(s)));title('Compressed image');drawnow;

i(end+1)=0;j(end+1)=0;blksz(end+1)=0;
data=[i;j;blksz;avg];
data=single(data);
symbols= unique(data);
counts = hist(data(:), symbols);
p = counts./ sum(counts);
sp=round(p*1000);
dict = huffmandict(symbols,p');
comp = huffmanenco(data,dict);
t=toc;
fprintf('Time taken for compression = %f seconds\n',t);
bits_in_original=8*256*256;
bits_in_final=length(comp)+8*length(symbols)+8*length(sp);
CR= bits_in_original/bits_in_final;
fprintf('compression ratio= %f\n',CR);
tic;
datanew = huffmandeco(comp,dict);
zeroindx=find(data==0);
inew=datanew(1:zeroindx(1)-1);
jnew=datanew(zeroindx(1)+1:zeroindx(2)-1);
blksznew=datanew(zeroindx(2)+1:zeroindx(3)-1);
avgnew=datanew(zeroindx(3)+1:end);
avgnew=uint8(avgnew);
for k=1:blkcount
outim(inew(k):inew(k)+blksznew(k)-1,jnew(k):jnew(k)+blksznew(k)-1)=avgnew(k);
end
axes(handles.axes18),imshow(outim);title('Decompressed Image');drawnow;
%figure,imshow(outim);title('Decompressed Image');drawnow;
t=toc;
fprintf('Time taken for Decompression = %f seconds\n',t);
hpsnr = vision.PSNR;
psnr = step(hpsnr, I,outim);
%fprintf('PSNR= %f\n',psnr);
[rows columns] = size(I);
set(gcf, 'Position', get(0,'Screensize'));
noisyImage = imnoise(I, 'gaussian', 0, 0.003);
squaredErrorImage = (double(I) - double(noisyImage)) .^ 2;
mse = sum(sum(squaredErrorImage)) / (rows * columns);
PSNR = 10 * log10( 256^2 / mse);
img=I;
img=double(img(:));
ima=max(img(:));
imi=min(img(:));
ims=std(img(:));
snr=20*log10((ima-imi)./ims);
set(handles.edit15,'String',PSNR)
set(handles.edit14,'String',snr)
set(handles.edit13,'String',mse)
guidata(hObject,handles);


function edit15_Callback(hObject, eventdata, handles)
% hObject handle to edit15 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit15 as text
% str2double(get(hObject,'String')) returns contents of edit15 as a double


% --- Executes during object creation, after setting all properties.
function edit15_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit15 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit14_Callback(hObject, eventdata, handles)
% hObject handle to edit14 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit14 as text
% str2double(get(hObject,'String')) returns contents of edit14 as a double
% --- Executes during object creation, after setting all properties.
function edit14_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit14 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit13_Callback(hObject, eventdata, handles)
% hObject handle to edit13 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit13 as text
% str2double(get(hObject,'String')) returns contents of edit13 as a double
% --- Executes during object creation, after setting all properties.
function edit13_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit13 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit6_Callback(hObject, eventdata, handles)
% hObject handle to edit6 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit6 as text
% str2double(get(hObject,'String')) returns contents of edit6 as a double
% --- Executes during object creation, after setting all properties.
function edit6_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit6 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit5_Callback(hObject, eventdata, handles)
% hObject handle to edit5 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit5 as text
% str2double(get(hObject,'String')) returns contents of edit5 as a double
% --- Executes during object creation, after setting all properties.
function edit5_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit5 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit4_Callback(hObject, eventdata, handles)
% hObject handle to edit4 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit4 as text
% str2double(get(hObject,'String')) returns contents of edit4 as a double
% --- Executes during object creation, after setting all properties.
function edit4_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit4 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
% --- Executes on button press in pushbutton2.
function pushbutton2_Callback(hObject, eventdata, handles)
% hObject handle to pushbutton2 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
fname=uigetfile('*.tif');
I=imread(fname);
I=imresize(I,[128 128]);
axes(handles.axes5),imshow(I);title('Original Image');drawnow;
tic;
s=qtdecomp(I,0.2,[2 64]);

[i,j,blksz] = find(s);
blkcount=length(i);
avg=zeros(blkcount,1);
for k=1:blkcount
avg(k)=mean2(I(i(k):i(k)+blksz(k)-1,j(k):j(k)+blksz(k)-1));

end
avg=uint8(avg);
axes(handles.axes6),imshow((full(s)));title('Compressed image');drawnow;

i(end+1)=0;j(end+1)=0;blksz(end+1)=0;
data=[i;j;blksz;avg];
data=single(data);
symbols= unique(data);
counts = hist(data(:), symbols);
p = counts./ sum(counts);
sp=round(p*1000);
dict = huffmandict(symbols,p');
comp = huffmanenco(data,dict);
t=toc;
fprintf('Time taken for compression = %f seconds\n',t);
bits_in_original=8*256*256;
bits_in_final=length(comp)+8*length(symbols)+8*length(sp);
CR= bits_in_original/bits_in_final;
fprintf('compression ratio= %f\n',CR);
tic;
datanew = huffmandeco(comp,dict);
zeroindx=find(data==0);
inew=datanew(1:zeroindx(1)-1);
jnew=datanew(zeroindx(1)+1:zeroindx(2)-1);
blksznew=datanew(zeroindx(2)+1:zeroindx(3)-1);
avgnew=datanew(zeroindx(3)+1:end);
avgnew=uint8(avgnew);
for k=1:blkcount
outim(inew(k):inew(k)+blksznew(k)-1,jnew(k):jnew(k)+blksznew(k)-1)=avgnew(k);
end
axes(handles.axes7),imshow(outim);title('Decompressed Image');drawnow;
%figure,imshow(outim);title('Decompressed Image');drawnow;
t=toc;
fprintf('Time taken for Decompression = %f seconds\n',t);
hpsnr = vision.PSNR;
psnr = step(hpsnr, I,outim);
%fprintf('PSNR= %f\n',psnr);
[rows columns] = size(I);
set(gcf, 'Position', get(0,'Screensize'));
noisyImage = imnoise(I, 'gaussian', 0, 0.003);
squaredErrorImage = (double(I) - double(noisyImage)) .^ 2;
mse = sum(sum(squaredErrorImage)) / (rows * columns);
PSNR = 10 * log10( 256^2 / mse);
img=I;
img=double(img(:));
ima=max(img(:));
imi=min(img(:));
ims=std(img(:));
snr=20*log10((ima-imi)./ims);
set(handles.edit4,'String',PSNR)
set(handles.edit5,'String',snr)
set(handles.edit6,'String',mse)
guidata(hObject,handles);
% --- Executes on button press in pushbutton1.
function pushbutton1_Callback(hObject, eventdata, handles)
% hObject handle to pushbutton1 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
fname=uigetfile('*.bmp');
I=imread(fname);
I=imresize(I,[128 128]);
axes(handles.axes1),imshow(I);title('Original Image');drawnow;
tic;
s=qtdecomp(I,0.2,[2 64]);

[i,j,blksz] = find(s);
blkcount=length(i);
avg=zeros(blkcount,1);
for k=1:blkcount
avg(k)=mean2(I(i(k):i(k)+blksz(k)-1,j(k):j(k)+blksz(k)-1));

end
avg=uint8(avg);
axes(handles.axes2),imshow((full(s)));title('Compressed image');drawnow;

i(end+1)=0;j(end+1)=0;blksz(end+1)=0;
data=[i;j;blksz;avg];
data=single(data);
symbols= unique(data);
counts = hist(data(:), symbols);
p = counts./ sum(counts);
sp=round(p*1000);
dict = huffmandict(symbols,p');
comp = huffmanenco(data,dict);
t=toc;
fprintf('Time taken for compression = %f seconds\n',t);
bits_in_original=8*256*256;
bits_in_final=length(comp)+8*length(symbols)+8*length(sp);
CR= bits_in_original/bits_in_final;
fprintf('compression ratio= %f\n',CR);
tic;
datanew = huffmandeco(comp,dict);
zeroindx=find(data==0);
inew=datanew(1:zeroindx(1)-1);
jnew=datanew(zeroindx(1)+1:zeroindx(2)-1);
blksznew=datanew(zeroindx(2)+1:zeroindx(3)-1);
avgnew=datanew(zeroindx(3)+1:end);
avgnew=uint8(avgnew);
for k=1:blkcount
outim(inew(k):inew(k)+blksznew(k)-1,jnew(k):jnew(k)+blksznew(k)-1)=avgnew(k);
end
axes(handles.axes3),imshow(outim);title('Decompressed Image');drawnow;
%figure,imshow(outim);title('Decompressed Image');drawnow;
t=toc;
fprintf('Time taken for Decompression = %f seconds\n',t);
hpsnr = vision.PSNR;
psnr = step(hpsnr, I,outim);
%fprintf('PSNR= %f\n',psnr);
[rows columns] = size(I);
set(gcf, 'Position', get(0,'Screensize'));
noisyImage = imnoise(I, 'gaussian', 0, 0.003);
squaredErrorImage = (double(I) - double(noisyImage)) .^ 2;
mse = sum(sum(squaredErrorImage)) / (rows * columns);
PSNR = 10 * log10( 256^2 / mse);
img=I;
img=double(img(:));
ima=max(img(:));
imi=min(img(:));
ims=std(img(:));
snr=20*log10((ima-imi)./ims);
set(handles.edit1,'String',PSNR)
set(handles.edit2,'String',snr)
set(handles.edit3,'String',mse)
guidata(hObject,handles);


function edit1_Callback(hObject, eventdata, handles)
% hObject handle to edit1 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit1 as text
% str2double(get(hObject,'String')) returns contents of edit1 as a double


% --- Executes during object creation, after setting all properties.
function edit1_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit1 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit2_Callback(hObject, eventdata, handles)
% hObject handle to edit2 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit2 as text
% str2double(get(hObject,'String')) returns contents of edit2 as a double
% --- Executes during object creation, after setting all properties.
function edit2_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit2 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit3_Callback(hObject, eventdata, handles)
% hObject handle to edit3 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit3 as text
% str2double(get(hObject,'String')) returns contents of edit3 as a double
% --- Executes during object creation, after setting all properties.
function edit3_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit3 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end























REFERENCES
"Lossy and lossless compression using combinational methods" Ms. C.S Sree Thayanandeswari,M.E, MISTE,Assistant Professor, Department of ECE, PET Engineering College, Vallioor.J Jeya Christy Bindhu Sheeba, Dept of ECE,
IIndM.E(C.S) PE Engineering College,Vallioor .

"lossless huffman coding technique for image compression and reconstruction using binary trees" Mridul Kumar Mathur, 2Seema Loonker, Dr. Dheeraj Saxena Lachoo Memorial College of Science & Technology, Jodhpur mathur_ Lachoo Memorial College of Science & Technology, Jodhpur

Mamta Sharma,"Compression Using Huffman Coding",IJCSNS International Journal of Computer Science and Network Security, VOL.10 No.5, May 2010,pp 133-141

D.A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., September 1952, pp 1098–1102. Huffman's original article.

[5]Albertus joko santoso , Dr. Lukito edi nugroho : "Compression ratio and peak signal to noise ratio in grayscale image compression." IJCST Vol. 2 , j


[6]Huffman's original article: D.A. Huffman,"coding" (PDF),Proceedings of the I.R.E., sept 1952, pp 1098- 1102

[7]Lehmann, E. L.; Casella, George (1998). Theory of Point Estimation (2nd ed.). New York: Springer. ISBN 0-387-98502-6. MR 1639875.

[8]"image compression using huffman coding based on histogram information and image segmentation" Dr. Monisha Sharma (Professor) Mr. Chandrashekhar K{ Professor) , Shri Shankaracharya College of Engg. And Technology Bhilai (C.G.) INDIA

[9]C. Saravanan , R. Ponalagusamy : "Lossless Grey-scale image compression using source symbols reduction and Huffman coding."International journal of image processing, vol 3