UNIT 5 | unit 5 image compression and recognition

UNIT 5

IMAGE COMPRESSION AND RECOGNITION

Q1) What is JPEG Compression?

A1)

JPEG is an image compression standard which was developed by "Joint Photographic Experts Group". In 1992, it was accepted as an international standard. JPEG is a lossy image compression method. JPEG compression uses the DCT (Discrete Cosine Transform) method for coding transformation. It allows a tradeoff between storage size and the degree of compression can be adjusted.

Following are the steps of JPEG Image Compression-

Step 1: The input image is divided into a small block which is having 8x8 dimensions. This dimension is sum up to 64 units. Each unit of the image is called a pixel.

Step 2: JPEG uses [Y,Cb,Cr] model instead of using the [R,G,B] model. So in the 2nd step, RGB is converted into YCbCr.

Step 3: After the conversion of colors, it is forwarded to DCT. DCT uses a cosine function and does not use complex numbers. It converts information which is in a block of pixels from the spatial domain to the frequency domain.

DCT Formula

Step 4: Humans are unable to see important aspects of the image because they are having high frequencies. The matrix after DCT conversion can only preserve values at the lowest frequency that to in certain point. Quantization is used to reduce the number of bits per sample.

There are two types of Quantization:

Uniform Quantization
Non-Uniform Quantization

Step 5: The zigzag scan is used to map the 8x8 matrix to a 1x64 vector. Zigzag scanning is used to group low-frequency coefficients to the top level of the vector and the high coefficient to the bottom. To remove the large number of zero in the quantized matrix, the zigzag matrix is used.

Step 6: Next step is vectoring, the different pulse code modulation (DPCM) is applied to the DC component. DC components are large and vary but they are usually close to the previous value. DPCM encodes the difference between the current block and the previous block.

Step 7: In this step, Run Length Encoding (RLE) is applied to AC components. This is done because AC components have a lot of zeros in them. It encodes in pair of (skip, value) in which skip is non zero value and value is the actual coded value of the non zero components.

Step 8: In this step, DC components are coded into Huffman.

Introduction to JPEG Compression

Q2) Explain data compression

A2)

Data compression is the process of encoding, restructuring, or otherwise modifying data to reduce its size. Fundamentally, it involves re-encoding information using fewer bits than the original representation.

Compression is done by a program that uses functions or an algorithm to effectively discover how to reduce the size of the data. For example, an algorithm might represent a string of bits with a smaller string of bits by using a ‘reference dictionary’ for conversion between them. Another example involves a formula that inserts a reference or pointer to a string of data that the program has already seen. A good example of this often occurs with image compression. When a sequence of colors, like ‘blue, red, red, blue’ is found throughout the image, the formula can turn this data string into a single bit, while still maintaining the underlying information.

Text compression can usually succeed by removing all unnecessary characters, instead of inserting a single character as a reference for a string of repeated characters, then replacing a smaller bit string for a more common bit string. With proper techniques, data compression can effectively lower a text file by 50% or more, greatly reducing its overall size.

For data transmission, compression can be run on the content or the entire transmission. When information is sent or received via the internet, larger files, either on their own or with others, or as part of an archive file, may be transmitted in one of many compressed formats, like ZIP, RAR, 7z, or MP3.

Q3) Explain Lossy vs Lossless

A3)

Compression is often broken down into two major forms, “lossy” and “lossless”. When choosing between the two methods, it is important to understand their strengths and weaknesses:

Lossless Compression: Removes bits by locating and removing statistical redundancies. Because of this technique, no information is removed. Lossless compression will often have a smaller compression ratio, with the benefit of not losing any data in the file. This is often very important when needing to maintain absolute quality, as with database information or professional media files. Formats such as FLAC and PNG offer lossless compression options.
Lossy Compression: Lowers size by deleting unnecessary information, and reducing the complexity of existing information. Lossy compression can achieve much higher compression ratios, at the cost of possible degradation of file quality. JPEG offers lossy compression options, and MP3 is based on lossy compression.

Q4) What is the use of data compression?

A4)

Data Compression Uses

Most businesses today rely on data compression in some major way, especially as the functional quality of data increases, storage capacity concerns have to be resolved. Data compression is one of the major tools that help with this. There several file types that are frequently compressed:

Audio Compression: Implemented as audio codecs, compression of audio files is necessary to guarantee bandwidth and storage limits aren’t exceeded. Audio compression can be either lossy or lossless, MP3 being the most ubiquitous lossy codec. FLAC is a major lossless encoding format.
Video Compression: Videos combine image compression with audio compression. There are usually separate codecs for each aspect of a video, which are then wrapped together as a single compression codec. Because of the high data rate required for uncompressed video, most video files are compressed using lossy compression. The most prevalent form of (lossy) video compression is MPEG.

Q5) Why Data Compression is Important?

A5)

The main advantages of compression are reductions in storage hardware, data transmission time, and communication bandwidth. This can result in significant cost savings. Compressed files require significantly less storage capacity than uncompressed files, meaning a significant decrease in expenses for storage. A compressed file also requires less time for transfer while consuming less network bandwidth. This can also help with costs, and also increases productivity.

The main disadvantage of data compression is the increased use of computing resources to apply compression to the relevant data. Because of this, compression vendors prioritize speed and resource efficiency optimizations to minimize the impact of intensive compression tasks.

Q6) Explain in detail Huffman coding

A6)

Huffman coding is one of the basic compression methods, that have proven useful in image and video compression standards. When applying the Huffman encoding technique on an Image, the source symbols can be either pixel intensities of the Image or the output of an intensity mapping function.

The first step of the Huffman coding technique is to reduce the input image to an ordered histogram, where the probability of occurrence of a certain pixel intensity value is as

prob_pixel = numpix/totalnum

Where numpix is the number of occurrence of a pixel with a certain intensity value and totalnum is the total number of pixels in the input image.

Let us take a 8 X 8 Image

The pixel intensity values are :

This image contains 46 distinct pixel intensity values, hence we will have 46 unique Huffman code words.

It is evident that not all pixel intensity values may be present in the image and hence will not have a non-zero probability of occurrence.

From here on, the pixel intensity values in the input Image will be addressed as leaf nodes.

Now, there are 2 essential steps to build a Huffman Tree :

Build a Huffman Tree :
1. Combine the two lowest probability leaf nodes into a new node.
2. Replace the two leaf nodes with the new node and sort the nodes according to the new probability values.
3. Continue the steps (a) and (b) until we get a single node with a probability value of 1.0. We will call this node as root
Backtrack from the root, assigning ‘0’ or ‘1’ to each intermediate node, till we reach the leaf nodes

Q7) Write an example of Huffman coding

A7)

In this example, we will assign ‘0’ to the left child node and ‘1’ to the right one.

Now, let’s look into the implementation :
Step 1 :
Read the Image into a 2D array(image)
If the Image is in .bmp format, then the Image can be read into the 2D array.

Int i, j;

Char filename[] = "Input_Image.bmp";

Int data = 0, offset, bpp = 0, width, height;

Long bmpsize = 0, bmpdataoff = 0;

Int** image;

Int temp = 0;

// Reading the BMP File

FILE* image_file;

Image_file = fopen(filename, "rb");

If (image_file == NULL)

{

Printf("Error Opening File!!");

Exit(1);

}

Else

{

// Set file position of the

// stream to the beginning

// Contains file signature

// or ID "BM"

Offset = 0;

// Set offset to 2, which

// contains size of BMP File

Offset = 2;

Fseek(image_file, offset, SEEK_SET);

// Getting size of BMP File

Fread(&bmpsize, 4, 1, image_file);

// Getting offset where the

// pixel array starts

// Since the information

// is at offset 10 from

// the start, as given

// in BMP Header

Offset = 10;

Fseek(image_file, offset, SEEK_SET);

// Bitmap data offset

Fread(&bmpdataoff, 4, 1, image_file);

// Getting height and width of the image

// Width is stored at offset 18 and height

// at offset 22, each of 4 bytes

Fseek(image_file, 18, SEEK_SET);

Fread(&width, 4, 1, image_file);

Fread(&height, 4, 1, image_file);

// Number of bits per pixel

Fseek(image_file, 2, SEEK_CUR);

Fread(&bpp, 2, 1, image_file);

// Setting offset to start of pixel data

Fseek(image_file, bmpdataoff, SEEK_SET);

// Creating Image array

Image = (int**)malloc(height * sizeof(int*));

For (i = 0; i < height; i++)

{

Image[i] = (int*)malloc(width * sizeof(int));

}

// int image[height][width]

// can also be done

// Number of bytes in the

// Image pixel array

Int numbytes = (bmpsize - bmpdataoff) / 3;

// Reading the BMP File

// into Image Array

For (i = 0; i < height; i++)

{

For (j = 0; j < width; j++)

{

Fread(&temp, 3, 1, image_file);

// the Image is a

// 24-bit BMP Image

Temp = temp & 0x0000FF;

Image[i][j] = temp;

}

Q8) Create a Histogram of the pixel intensity values present in the Image

A8)

// Creating the Histogram

Int hist[256];

For (i = 0; i < 256; i++)

Hist[i] = 0;

For (i = 0; i < height; i++)

For (j = 0; j < width; j++)

Hist[image[i][j]] += 1;

Q9) Find the number of pixel intensity values having the non-zero probability of occurrence

A9)

Since the values of pixel intensities range from 0 to 255, and not all pixel intensity values may be present in the image (as evident from the histogram and also the image matrix) and hence will not have a non-zero probability of occurrence. Also, another purpose this step serves, is that the number of pixel intensity values having non-zero probability values will give us the number of leaf nodes in the Image.

// Finding number of

// non-zero occurrences

Int nodes = 0;

For (i = 0; i < 256; i++)

{

If (hist[i] != 0)

Nodes += 1;

}

Q10) Why use two struct arrays?

A10)

Initially, the struct array pix_freq, as well as the struct array huffcodes will only contain the information of all the leaf nodes in the Huffman Tree.

The struct array pix_freq will be used to store all the nodes of the Huffman Tree and the array huffcodes will be used as the updated (and sorted) tree.

Remember that, only huffcodes will be sorted in each iteration, and not pix_freq

The new nodes created by combining two nodes of the lowest frequency, in each iteration, will be appended to the end of the pix_freq array, and also to huffcodes array.

But the array huffcodes will be sorted again according to the probability of occurrence after the new node is added to it.

The position of the new node in the array pix_freq will be stored in the arrloc field of the struct huffcode.
The arrloc field will be used when assigning the pointer to the left and right child of a new node.

UNIT 5

IMAGE COMPRESSION AND RECOGNITION

Q1) What is JPEG Compression?

A1)

Following are the steps of JPEG Image Compression-

Step 1: The input image is divided into a small block which is having 8x8 dimensions. This dimension is sum up to 64 units. Each unit of the image is called a pixel.

Step 2: JPEG uses [Y,Cb,Cr] model instead of using the [R,G,B] model. So in the 2nd step, RGB is converted into YCbCr.

DCT Formula

There are two types of Quantization:

Uniform Quantization
Non-Uniform Quantization

Step 8: In this step, DC components are coded into Huffman.

Introduction to JPEG Compression

Q2) Explain data compression

A2)

Q3) Explain Lossy vs Lossless

A3)

Compression is often broken down into two major forms, “lossy” and “lossless”. When choosing between the two methods, it is important to understand their strengths and weaknesses:

Lossless Compression: Removes bits by locating and removing statistical redundancies. Because of this technique, no information is removed. Lossless compression will often have a smaller compression ratio, with the benefit of not losing any data in the file. This is often very important when needing to maintain absolute quality, as with database information or professional media files. Formats such as FLAC and PNG offer lossless compression options.
Lossy Compression: Lowers size by deleting unnecessary information, and reducing the complexity of existing information. Lossy compression can achieve much higher compression ratios, at the cost of possible degradation of file quality. JPEG offers lossy compression options, and MP3 is based on lossy compression.

Q4) What is the use of data compression?

A4)

Data Compression Uses

Audio Compression: Implemented as audio codecs, compression of audio files is necessary to guarantee bandwidth and storage limits aren’t exceeded. Audio compression can be either lossy or lossless, MP3 being the most ubiquitous lossy codec. FLAC is a major lossless encoding format.
Video Compression: Videos combine image compression with audio compression. There are usually separate codecs for each aspect of a video, which are then wrapped together as a single compression codec. Because of the high data rate required for uncompressed video, most video files are compressed using lossy compression. The most prevalent form of (lossy) video compression is MPEG.

Q5) Why Data Compression is Important?

A5)

Q6) Explain in detail Huffman coding

A6)

The first step of the Huffman coding technique is to reduce the input image to an ordered histogram, where the probability of occurrence of a certain pixel intensity value is as

prob_pixel = numpix/totalnum

Where numpix is the number of occurrence of a pixel with a certain intensity value and totalnum is the total number of pixels in the input image.

Let us take a 8 X 8 Image

The pixel intensity values are :

This image contains 46 distinct pixel intensity values, hence we will have 46 unique Huffman code words.

It is evident that not all pixel intensity values may be present in the image and hence will not have a non-zero probability of occurrence.

From here on, the pixel intensity values in the input Image will be addressed as leaf nodes.

Now, there are 2 essential steps to build a Huffman Tree :

Build a Huffman Tree :
1. Combine the two lowest probability leaf nodes into a new node.
2. Replace the two leaf nodes with the new node and sort the nodes according to the new probability values.
3. Continue the steps (a) and (b) until we get a single node with a probability value of 1.0. We will call this node as root
Backtrack from the root, assigning ‘0’ or ‘1’ to each intermediate node, till we reach the leaf nodes

Q7) Write an example of Huffman coding

A7)

In this example, we will assign ‘0’ to the left child node and ‘1’ to the right one.

Now, let’s look into the implementation :
Step 1 :
Read the Image into a 2D array(image)
If the Image is in .bmp format, then the Image can be read into the 2D array.

Int i, j;

Char filename[] = "Input_Image.bmp";

Int data = 0, offset, bpp = 0, width, height;

Long bmpsize = 0, bmpdataoff = 0;

Int** image;

Int temp = 0;

// Reading the BMP File

FILE* image_file;

Image_file = fopen(filename, "rb");

If (image_file == NULL)

{

Printf("Error Opening File!!");

Exit(1);

}

Else

{

// Set file position of the

// stream to the beginning

// Contains file signature

// or ID "BM"

Offset = 0;

// Set offset to 2, which

// contains size of BMP File

Offset = 2;

Fseek(image_file, offset, SEEK_SET);

// Getting size of BMP File

Fread(&bmpsize, 4, 1, image_file);

// Getting offset where the

// pixel array starts

// Since the information

// is at offset 10 from

// the start, as given

// in BMP Header

Offset = 10;

Fseek(image_file, offset, SEEK_SET);

// Bitmap data offset

Fread(&bmpdataoff, 4, 1, image_file);

// Getting height and width of the image

// Width is stored at offset 18 and height

// at offset 22, each of 4 bytes

Fseek(image_file, 18, SEEK_SET);

Fread(&width, 4, 1, image_file);

Fread(&height, 4, 1, image_file);

// Number of bits per pixel

Fseek(image_file, 2, SEEK_CUR);

Fread(&bpp, 2, 1, image_file);

// Setting offset to start of pixel data

Fseek(image_file, bmpdataoff, SEEK_SET);

// Creating Image array

Image = (int**)malloc(height * sizeof(int*));

For (i = 0; i < height; i++)

{

Image[i] = (int*)malloc(width * sizeof(int));

}

// int image[height][width]

// can also be done

// Number of bytes in the

// Image pixel array

Int numbytes = (bmpsize - bmpdataoff) / 3;

// Reading the BMP File

// into Image Array

For (i = 0; i < height; i++)

{

For (j = 0; j < width; j++)

{

Fread(&temp, 3, 1, image_file);

// the Image is a

// 24-bit BMP Image

Temp = temp & 0x0000FF;

Image[i][j] = temp;

}

Q8) Create a Histogram of the pixel intensity values present in the Image

A8)

// Creating the Histogram

Int hist[256];

For (i = 0; i < 256; i++)

Hist[i] = 0;

For (i = 0; i < height; i++)

For (j = 0; j < width; j++)

Hist[image[i][j]] += 1;

Q9) Find the number of pixel intensity values having the non-zero probability of occurrence

A9)

// Finding number of

// non-zero occurrences

Int nodes = 0;

For (i = 0; i < 256; i++)

{

If (hist[i] != 0)

Nodes += 1;

}

Q10) Why use two struct arrays?

A10)

Initially, the struct array pix_freq, as well as the struct array huffcodes will only contain the information of all the leaf nodes in the Huffman Tree.

The struct array pix_freq will be used to store all the nodes of the Huffman Tree and the array huffcodes will be used as the updated (and sorted) tree.

Remember that, only huffcodes will be sorted in each iteration, and not pix_freq

The new nodes created by combining two nodes of the lowest frequency, in each iteration, will be appended to the end of the pix_freq array, and also to huffcodes array.

But the array huffcodes will be sorted again according to the probability of occurrence after the new node is added to it.

UNIT 5

IMAGE COMPRESSION AND RECOGNITION

Q1) What is JPEG Compression?

A1)

Following are the steps of JPEG Image Compression-

Step 1: The input image is divided into a small block which is having 8x8 dimensions. This dimension is sum up to 64 units. Each unit of the image is called a pixel.

Step 2: JPEG uses [Y,Cb,Cr] model instead of using the [R,G,B] model. So in the 2nd step, RGB is converted into YCbCr.

DCT Formula

There are two types of Quantization:

Uniform Quantization
Non-Uniform Quantization

Step 8: In this step, DC components are coded into Huffman.

Introduction to JPEG Compression

Q2) Explain data compression

A2)

Q3) Explain Lossy vs Lossless

A3)

Compression is often broken down into two major forms, “lossy” and “lossless”. When choosing between the two methods, it is important to understand their strengths and weaknesses:

Lossless Compression: Removes bits by locating and removing statistical redundancies. Because of this technique, no information is removed. Lossless compression will often have a smaller compression ratio, with the benefit of not losing any data in the file. This is often very important when needing to maintain absolute quality, as with database information or professional media files. Formats such as FLAC and PNG offer lossless compression options.
Lossy Compression: Lowers size by deleting unnecessary information, and reducing the complexity of existing information. Lossy compression can achieve much higher compression ratios, at the cost of possible degradation of file quality. JPEG offers lossy compression options, and MP3 is based on lossy compression.

Q4) What is the use of data compression?

A4)

Data Compression Uses

Audio Compression: Implemented as audio codecs, compression of audio files is necessary to guarantee bandwidth and storage limits aren’t exceeded. Audio compression can be either lossy or lossless, MP3 being the most ubiquitous lossy codec. FLAC is a major lossless encoding format.
Video Compression: Videos combine image compression with audio compression. There are usually separate codecs for each aspect of a video, which are then wrapped together as a single compression codec. Because of the high data rate required for uncompressed video, most video files are compressed using lossy compression. The most prevalent form of (lossy) video compression is MPEG.

Q5) Why Data Compression is Important?

A5)

Q6) Explain in detail Huffman coding

A6)

The first step of the Huffman coding technique is to reduce the input image to an ordered histogram, where the probability of occurrence of a certain pixel intensity value is as

prob_pixel = numpix/totalnum

Where numpix is the number of occurrence of a pixel with a certain intensity value and totalnum is the total number of pixels in the input image.

Let us take a 8 X 8 Image

The pixel intensity values are :

This image contains 46 distinct pixel intensity values, hence we will have 46 unique Huffman code words.

It is evident that not all pixel intensity values may be present in the image and hence will not have a non-zero probability of occurrence.

From here on, the pixel intensity values in the input Image will be addressed as leaf nodes.

Now, there are 2 essential steps to build a Huffman Tree :

Build a Huffman Tree :
1. Combine the two lowest probability leaf nodes into a new node.
2. Replace the two leaf nodes with the new node and sort the nodes according to the new probability values.
3. Continue the steps (a) and (b) until we get a single node with a probability value of 1.0. We will call this node as root
Backtrack from the root, assigning ‘0’ or ‘1’ to each intermediate node, till we reach the leaf nodes

Q7) Write an example of Huffman coding

A7)

In this example, we will assign ‘0’ to the left child node and ‘1’ to the right one.

Now, let’s look into the implementation :
Step 1 :
Read the Image into a 2D array(image)
If the Image is in .bmp format, then the Image can be read into the 2D array.

Int i, j;

Char filename[] = "Input_Image.bmp";

Int data = 0, offset, bpp = 0, width, height;

Long bmpsize = 0, bmpdataoff = 0;

Int** image;

Int temp = 0;

// Reading the BMP File

FILE* image_file;

Image_file = fopen(filename, "rb");

If (image_file == NULL)

{

Printf("Error Opening File!!");

Exit(1);

}

Else

{

// Set file position of the

// stream to the beginning

// Contains file signature

// or ID "BM"

Offset = 0;

// Set offset to 2, which

// contains size of BMP File

Offset = 2;

Fseek(image_file, offset, SEEK_SET);

// Getting size of BMP File

Fread(&bmpsize, 4, 1, image_file);

// Getting offset where the

// pixel array starts

// Since the information

// is at offset 10 from

// the start, as given

// in BMP Header

Offset = 10;

Fseek(image_file, offset, SEEK_SET);

// Bitmap data offset

Fread(&bmpdataoff, 4, 1, image_file);

// Getting height and width of the image

// Width is stored at offset 18 and height

// at offset 22, each of 4 bytes

Fseek(image_file, 18, SEEK_SET);

Fread(&width, 4, 1, image_file);

Fread(&height, 4, 1, image_file);

// Number of bits per pixel

Fseek(image_file, 2, SEEK_CUR);

Fread(&bpp, 2, 1, image_file);

// Setting offset to start of pixel data

Fseek(image_file, bmpdataoff, SEEK_SET);

// Creating Image array

Image = (int**)malloc(height * sizeof(int*));

For (i = 0; i < height; i++)

{

Image[i] = (int*)malloc(width * sizeof(int));

}

// int image[height][width]

// can also be done

// Number of bytes in the

// Image pixel array

Int numbytes = (bmpsize - bmpdataoff) / 3;

// Reading the BMP File

// into Image Array

For (i = 0; i < height; i++)

{

For (j = 0; j < width; j++)

{

Fread(&temp, 3, 1, image_file);

// the Image is a

// 24-bit BMP Image

Temp = temp & 0x0000FF;

Image[i][j] = temp;

}

Q8) Create a Histogram of the pixel intensity values present in the Image

A8)

// Creating the Histogram

Int hist[256];

For (i = 0; i < 256; i++)

Hist[i] = 0;

For (i = 0; i < height; i++)

For (j = 0; j < width; j++)

Hist[image[i][j]] += 1;

Q9) Find the number of pixel intensity values having the non-zero probability of occurrence

A9)

// Finding number of

// non-zero occurrences

Int nodes = 0;

For (i = 0; i < 256; i++)

{

If (hist[i] != 0)

Nodes += 1;

}

Q10) Why use two struct arrays?

A10)

Initially, the struct array pix_freq, as well as the struct array huffcodes will only contain the information of all the leaf nodes in the Huffman Tree.

The struct array pix_freq will be used to store all the nodes of the Huffman Tree and the array huffcodes will be used as the updated (and sorted) tree.

Remember that, only huffcodes will be sorted in each iteration, and not pix_freq

The new nodes created by combining two nodes of the lowest frequency, in each iteration, will be appended to the end of the pix_freq array, and also to huffcodes array.

But the array huffcodes will be sorted again according to the probability of occurrence after the new node is added to it.

Sign Up